Low-Pathwidth GRAND: Exact Likelihood-Ordered Enumeration for BPSK Transmission over Correlated Gaussian Noise

시끄럽고 북적이는 방에서 비밀 메시지를 보내려고 한다고 상상해 보십시오. 당신은 일련의 단어들을 외치지만, 바람과 웅성거림, 그리고 메아리가 당신의 목소리를 왜곡합니다. 듣고 있는 사람은 당신이 실제로 의도했던 단어가 무엇인지 추측해야 합니다. 디지털 통신 세계에서 이 "방"은 채널이고, "단어"는 데이터 비트이며, "소음"은 신호를 뒤섞는 무작위 간섭입니다. 디코더(decoder)의 목표는 이 혼돈 속에서도 원래의 메시지를 찾아내는 것입니다.

수십 년 동안 엔지니어들은 "무작위 가법 노이즈 추측 디코딩(Guessing Random Additive Noise Decoding, GRAND)"이라는 영리한 전략을 사용해 왔습니다. 메시지를 직접 추측하는 대신, GRAND는 거꾸로 작동합니다. 즉, 노이즈가 무엇이었을지를 추측하는 것입니다. 이 방식은 가장 가능성 높은 노이즈 패턴(예: 부드러운 미풍)에서 시작하여 가능성이 낮은 패턴(예: 허리케인)으로 나아갑니다. 만약 받은 신호에서 추측한 노이즈 패턴을 뺐을 때 결과가 유효한 메시지가 된다면, 디코더는 승리를 선언하며 멈춥니다. 이 기술이 완벽하게 작동하기 위한 핵심은 디코더가 노이즈 패턴을 가장 확률이 높은 것부터 가장 낮은 것까지 정확한 순서대로 추측해야 한다는 점입니다.

하지만 노이즈가 단순히 무작위 정전기가 아니라 "상관관계(correlated)"를 가질 때 상황은 매우 복잡해집니다. 예를 들어, 바람이 한순간에 돌풍을 일으켰다면 잠시 후에도 다시 돌풍이 불 가능성이 높습니다. 이는 비트들 사이에 복잡한 연결망을 만들어내며, 노이즈 패턴의 순위를 올바르게 매기는 것을 매우 어렵게 만듭니다. 기존의 방법들은 이러한 연결성을 무시하거나 메시지를 작고 독립적인 덩어리로 나누어 문제를 단순화하려고 시도했지만, 이러한 지름길은 종종 잘못된 추측으로 이어졌습니다.

이 논문은 **LP-GRAND(Low-Pathwidth GRAND)**라고 불리는 새롭고 매우 정밀한 디코더를 소개합니다. 이를 생각해보면, 단순히 노이즈를 추측하는 것이 아니라, 완벽한 탐색 순서를 찾기 위해 노이즈의 전체 "상호작용 그래프"를 그려내는 숙련된 형사와 같습니다. 저자들은 노이즈를 특정 수학적 형태(이차 에너지 지형)로 취급하고 영리한 "트렐리스(trellis, 격자 구조)"를 사용하여, 상관관계가 높은 노이즈 환경에서도 모든 가능한 노이즈 패턴을 가능성 순서대로 나열할 수 있음을 보여줍니다. 그들은 만약 이 목록을 하나도 빠짐없이 따른다면, 처음 발견한 유효한 메시지가 반드시 최선의 답이라는 것을 수학적으로 증명했습니다. 특정 코드들을 이용한 시뮬레이션에서, 이 새로운 방식은 기존의 "덩어리 기반(chunk-based)" 지름길보다 더 자주, 그리고 더 빠르게 올바른 메시지를 찾아냈으며, 복잡한 연결성을 파악하는 데 시간을 들이는 것이 결국 보상받는다는 것을 입증했습니다.

핵심 아이디어: 노이즈 미로 매핑하기

LP-GRAND의 작동 원리를 이해하기 위해, 노이즈를 거대한 다차원 미로라고 상상해 봅시다. 단순한 "무기억(memoryless)" 세계에서는 미로의 모든 경로가 독립적입니다. 즉, 이전의 선택과 상관없이 어느 지점에서든 왼쪽이나 오른쪽을 선택할 수 있습니다. 하지만 "상관관계가 있는" 세계에서는 미로가 뒤틀려 있습니다. 5단계에서 왼쪽으로 도는 것이 6단계에서 오른쪽으로 돌도록 강제할 수도 있습니다. 이러한 뒤틀림이 수학을 어렵게 만드는 요소입니다.

저자들은 특정 유형의 노이즈(알려진 "정밀도 행렬"을 가진 가우시안 노이즈)의 경우, 이 뒤틀린 미로를 **트렐리스(trellis)**라고 불리는 구조화되고 층이 있는 지도로 평탄화할 수 있다는 점을 깨달았습니다. 만약 노이즈 연결이 "희소(sparse)"하다면(즉, 이웃한 비트들끼리만 연결되어 있는 것처럼 근처의 비트들만 연결한다면), 이 지도는 무한히 커지지 않습니다. 대신, 제한된 수의 발판을 가진 사다리처럼 관리 가능한 수준을 유지합니다.

LP-GRAND는 이 사다리를 사용하여 "최선 우선 탐색(best-first search)"을 수행합니다. 단순히 사다리를 내려가는 것이 아니라, 모든 가능한 경로의 "에너지 비용"을 계산합니다. 에너지가 낮을수록 해당 노이즈 패턴이 발생할 확률이 높습니다. **접미사 동적 계획법(suffix dynamic programming)**을 사용하여, 디코더는 다음에 탐색할 가장 저렴한 경로가 무엇인지 미리 내다볼 수 있습니다. 이는 마치 단순히 출구까지의 거리뿐만 아니라, 가장 짧은 경로를 가장 먼저 찾기 위해 모든 가능한 경로를 방문해야 하는 정확한 순서를 알려주는 GPS를 가진 것과 같습니다.

기존 지름길들이 실패한 이유

이 논문 이전의 엔지니어들은 메시지를 작은 블록으로 나누고 한 블록의 노이즈가 다음 블록에 영향을 주지 않는다고 가정함으로써 문제를 단순화하곤 했습니다. 이는 퍼즐 조각 하나에 그려진 그림이 옆 조각의 그림과 어떻게 연결되는지 무시한 채 퍼즐을 맞추려는 것과 같습니다.

본 논문은 이러한 "블록 기반 근사법(block-based approximations)"에 대해 명시적으로 반박합니다. 저자들은 노이즈가 상관관계를 가질 때, 이러한 지름길들이 "교차 좌표 간 상호작용(cross-coordinate interactions)", 즉 한 부분의 노이즈가 다른 부분에 미치는 미묘한 영향력을 놓친다는 것을 보여줍니다. 테스트 결과, 이러한 지름길들은 종종 잘못된 노이즈 패턴을 먼저 추측하여 디코 decoding 오류를 일으켰습니다. 논문은 이러한 지름길들이 계산 속도는 빠를지 모르나, "최대 가능도(Maximum Likelihood, ML)" 최적은 아니라는 점을 입증합니다. 즉, 절대적인 최선의 답을 찾는다는 보장이 없습니다. 반면 LP-GRAND는 타협하지 않습니다. 전체 상관관계 노이즈의 정확한 에너지를 계산함으로써, 처음 발견한 유효한 메시지가 수학적으로 가장 가능성 높은 것임을 보장합니다.

결과: 완벽한 일치

저자들은 단순히 이론을 제시하는 데 그치지 않고, 자신들의 디코더를 엄격하게 테스트했습니다. 그들은 두 가지 유형의 코드, 즉 작은 [20, 12] 코드와 더 큰 [64, 52] 코드를 대상으로 시뮬레이션을 실행했습니다.

작은 코드 테스트에서, LP-GRAND를 "전수 조사(exhaustive search)" 방식—가장 좋은 메시지를 찾기 위해 가능한 모든 메시지를 하나씩 확인하는 방식—과 비교했습니다. 전수 조사는 골드 스탠다드(표준)이지만 실제 사용에는 너무 느립니다. 10,000 프레임의 데이터에 대해, LP-GRAND는 전수 조사 방식과 100% 일치했습니다. 매번 정확히 동일한 "최선의" 메시지를 찾아냈으며, 이는 노이즈 패턴의 순서가 수학적으로 완벽했음을 증명합니다.

더 큰 [64, 52] 코드의 경우, LP-GRAND를 대중적인 블록 기반 지름길들(ORBGRAND-AI 및 ExactBlockProduct 등)과 비교했습니다. 2 dB의 신호 품질에서, LP-GRAND는 다른 모든 방법보다 낮은 "블록 오류율(Block Error Rate, BLER)"을 달-성했습니다. 간단히 말해, 실수를 훨씬 적게 했다는 뜻입니다. 예를 들어, 특정 랜덤 코드에 대해 LP-GRAND의 오류율은 약 0.022였던 반면, 가장 뛰어난 블록 기반 근사법의 오류율은 0.040이었습니다. 이는 LP-GRAND가 이 테스트에서 거의 두 배 더 신뢰할 수 있음을 의미합니다.

"경로 폭(Pathwidth)"의 마법

이 디코더의 핵심 비결은 **경로 폭(pathwidth)**이라는 개념입니다. 노이즈 연결을 점(비트)들이 선으로 연결된 그래프라고 상상해 보십시오. 만약 그래프가 긴 직선 형태라면 경로 폭은 작습니다. 만약 엉킨 실타래 형태라면 경로 폭은 매우 큽니다. 저자들은 노이즈 행렬이 "하프 대역폭(half-bandwidth)"을 가진다면(즉, 인접한 비트들만 연결한다면), 경로 폭이 관리 가능한 수준의 트렐리스를 구축할 수 있을 만큼 작다는 것을 보여주었습니다.

그들은 경로, 사다리 등 다양한 형태의 그래프에 대해 이를 테스트했습니다. 많은 실제 채널에서 발견되는 형태인 "경로"와 "사다리" 모양의 경우, 디코더는 완벽하게 작동했습니다. 심지어 노이즈 연결이 순서 없이 뒤섞인(permuted) 시나리오에서도 테스트를 진행했습니다. **역 순서 컷힐-맥키(Reverse Cuthill–McKee, RCM)**라는 영리한 재정렬 기법을 사용하여, 여전히 낮은 경로 폭을 찾아내고 디코더를 효율적으로 실행할 수 있었습니다. 64비트 코드가 뒤섞인 환경에서의 한 테스트에서, LP-GRAND는 테스트된 모든 50 프레임에서 올바른 메시지를 찾아낸 반면, 블록 기반 방식들은 17~25 프레임에서 오류를 범했습니다.

결론

이 논문은 특정하고 중요한 클래스의 노이즈 채널에 대해 정확하면서도 효율적인 디코더를 제시합니다. 적절한 수학적 지도를 사용할 용의가 있다면, 속도와 정확성 사이에서 하나를 포기할 필요가 없다는 것을 입증합니다. 노이즈를 구조화된 에너지 지형으로 취급하고 "낮은 경로 폭" 접근 방식을 사용하여 탐색함으로써, LP-GRAND는 처음 발견한 유효한 메시지가 반드시 최선의 메시지임을 보장합니다. 기존의 지름길들보다 더 복잡한 설정이 필요하지만, 시뮬레이션 결과 상관관계가 있는 노이즈 환경에서는 이러한 추가적인 노력이 현저히 적은 오류로 이어진다는 것을 보여주었으며, 이는 미래의 고신뢰 통신 시스템을 위한 강력한 도구가 될 수 있음을 시사합니다.