Polar Complexity: A New Descriptive Complexity with Applications to Source and Joint Source-Channel Coding

기술적 요약: 극화 복잡도 및 적응형 이중 극화 부호화

문제 제기
유한 길이의 이진 시퀀스를 개별적으로 효율적으로 기술하는 것은 정보 이론에서 근본적인 과제로 남아 있습니다. 섀넌의 프레임워크는 알려진 통계를 가진 확률적 소스에 대한 평균 기술 길이를 최적화하지만, 확률적 모델이 부재한 개별 시퀀스에는 직접 적용되지 않습니다. 반면, 시퀀스를 생성하는 가장 짧은 프로그램의 길이로 시퀀스의 복잡도를 정의하는 콜모고로프 복잡도는 이론적으로 보편적이지만 계산 불가능합니다. 레펠 - 지브 (LZ) 복잡도나 선형 복잡도와 같은 기존 계산 가능한 접근법들은 반복된 패턴이나 선형 재귀와 같은 특정 구조적 가정에 의존하며, 이는 임의의 시퀀스가 가진 전체 규칙성을 포착하지 못할 수 있습니다. 또한, 확률적 소스에 대해 엔트로피를 달성하는 기존 고정 길이 극화 소스 부호화는 특정 개별 시퀀스의 정확한 재구성에 필요한 최소 압축 길이를 결정하는 메커니즘을 본질적으로 제공하지 않습니다.

방법론
본 논문은 연속 취소 복호 (SCD) 를 사용하여 특정 이진 시퀀스를 정확하게 재구성하는 데 필요한 최소 극화 압축 길이 (PCL) 로 정의된 새로운 기술적 복잡도 척도인 **극화 복잡도 (Polar Complexity)**를 소개합니다. 이 방법론은 임의의 블록 길이에 대해 극화 변환을 일반화하는 이진 균형 트리 (BBT) 극화 부호화 프레임워크에 기반합니다.

1. 극화 복잡도 정의 및 계산:

   • 저자들은 시퀀스 $\mathbf{s}$의 극화 복잡도 $L^\star(\mathbf{s})$를 고정 노드 선택을 위한 극화 가중치 (Polarization-Weight) 방법과 결정론적 SCD 매개변수 $\tau=0$을 사용하는 표준 구성 하에서 시퀀스를 완벽하게 복원할 수 있는 최소 PCL $L$로 정의합니다.
   • 정확한 계산: 복원 가능성의 단조성 (만약 시퀀스가 길이 $L$에서 복원 가능하면 임의의 $L' > L$에서도 복원 가능함) 을 활용하여, 시퀀스 길이에 대해 선형에서 로그 수준으로 SCD 시도 횟수를 줄이는 이분 탐색 알고리즘을 통해 $L^\star(\mathbf{s})$를 효율적으로 계산하는 방법을 제안합니다.
   • 저복잡도 추정: 반복적인 복호화 시도를 피하기 위해 예측 극화 복잡도가 도입됩니다. 이 방법은 국소적으로 모호하거나 오류에 취약한 "임계 집합 (critical set)"의 리프 노드를 식별하기 위해 신 (Genie) 보조 SCD (GA-SCD) 를 활용합니다. 예측된 복잡도는 이 임계 집합 내 가장 우선순위가 높은 노드의 선택 우선순위에 의해 결정되며, 이는 실제 극화 복잡도에 대한 보수적인 상한을 제공합니다.

2. 극화 기반 2 단계 소스 부호화:

   • 각 소스 시퀀스를 극화 복잡도의 이진 표현을 포함하는 고정 길이 헤더와 그 뒤에 이어지는 가변 길이 극화 압축 시퀀스의 쌍으로 인코딩하는 새로운 소스 부호화 방식이 제안됩니다.
   • 이 방식은 엄격히 무손실이며 프리픽스 프리 (prefix-free) 성질을 가집니다.
   • 이론적 분석에 따르면, 블록 길이가 2 의 거듭제곱인 이진 메모리리스 소스 (BMS) 의 경우, 고정 노드 선택과 SCD 매개변수가 소스 분포에 최적화되어 있다면, 이 방식의 정규화된 평균 압축 길이는 점근적으로 소스 엔트로피에 수렴함이 증명됩니다.

3. 적응형 이중 극화 결합 소스 - 채널 부호화 (JSCC):

   • 저자들은 제안된 소스 부호화를 극화 채널 부호화와 통합하여 적응형 JSCC 방식을 구축합니다.
   • 메커니즘: 인코더와 디코더는 사전 정의된 후보 PCL 집합을 공유합니다. 주어진 소스 시퀀스에 대해 인코더는 시퀀스의 예측된 극화 복잡도보다 크거나 같은 가장 작은 후보 PCL 을 선택합니다. 이렇게 선택된 PCL 은 채널 인코더에서 활성 노드와 고정 노드의 할당을 결정합니다.
   • 복호화: 디코더는 후보 PCL 집합에 대해 가설 검정을 수행합니다. 각 가설에 대해 후보 소스 시퀀스를 재구성하고, CRC 검사를 사용하여 무효한 후보를 필터링한 후 최대 사후 확률 (MAP) 기준에 따라 최종 추정을 선택합니다.
   • 최적화: 후보 PCL 집합의 설계는 프레임 오류율 (FER) 을 최소화하는 최적화 문제로 공식화됩니다. 이는 성능 (더 세분화된 그레들리티) 과 복잡도 (후보 집합의 크기) 간의 균형을 맞추기 위해 동적 계획법을 사용하여 효율적으로 해결됩니다.

주요 기여

• 극화 복잡도: 정확한 SCD 재구성을 위한 최소 PCL 기반의 새로운 계산 가능한 기술적 복잡도 척도의 도입.
• 효율적 알고리즘: 정확한 계산을 위한 이분 탐색 알고리즘 개발 및 극화 복잡도 추정을 위한 저복잡도 GA-SCD 기반 예측 방법 개발.
• 2 단계 소스 부호화: 소스 통계에 대한 사전 지식을 필요로 하지 않으면서 (엔트로피 달성 증명은 매개변수 조정을 위해 통계 지식을 가정함) 점근적으로 소스 엔트로피를 달성하는 엄격히 무손실 프리픽스 프리 부호화 방식.
• 적응형 JSCC: 개별 소스 실현의 압축 가능성에 채널 부호화율을 적응시키는 통합된 이중 극화 JSCC 프레임워크. 성능 - 복잡도 균형을 최적화하기 위해 동적 계획법 기반의 후보 PCL 집합 최적화 방법을 포함합니다.

결과

• 소스 부호화 성능: 시뮬레이션은 제안된 2 단계 방식이 짧은 블록 길이 ($K=64$) 에서 열거 부호화와 비교 가능한 압축 성능을 달성하지만, 계산 복잡도가 훨씬 낮음 ($O(K \log K)$ 대 $O(K^2)$) 을 보여줍니다. 이 방식은 다양한 소스 분포에 걸쳐 견고하며 사전 통계 지식을 필요로 하지 않습니다.
• 복잡도 추정: 이분 탐색 방법은 순차 탐색에 비해 극화 복잡도를 결정하는 계산 비용을 크게 줄입니다. 예측된 극화 복잡도는 작은 간격으로 실제 복잡도를 일관되게 상한으로 제한하여 JSCC 설계에서의 유용성을 입증합니다.
• JSCC 성능: 적응형 이중 극화 JSCC 시뮬레이션 (블록 길이 $N=128$ 및 $N=1024$) 에서 제안된 방식은 기존 극화 코드 기반 JSCC 기준 (이중-CRC-극화 및 결합 SCLD 방식 포함) 보다 우수한 성능을 보입니다. 프레임 오류율 (FER) 은 후보 PCL 집합의 크기가 증가함에 따라 단조 감소하며, 디코더가 실제 PCL 을 알고 있는 경우의 이론적 하한에 접근합니다.

의의
본 논문은 확률적 소스 속성에서 개별 시퀀스의 극화 부호화 하에서의 복원 행동으로 초점을 이동시킴으로써, 실용적이고 계산 가능한 기술적 복잡도 척도를 제공한다고 주장합니다. 이 "극화 복잡도"는 엄격히 무손실이며 적응적인 새로운 부호화 방식의 클래스를 가능하게 합니다. 제안된 적응형 이중 극화 JSCC 방식은 유연한 성능 - 복잡도 균형을 제공하며, 개별 소스 실현의 특정 압축 가능성에 채널 보호를 맞춤화하는 것이 정적이거나 비적응형 결합 부호화 접근법보다 우수한 오류율 성능을 달성할 수 있음을 보여줍니다. 이 연구는 알고리즘적 복잡도 개념과 실용적인, 용량에 근접하는 부호화 기법 간의 간극을 메웁니다.