2025-11-20T14:55:15.130233

On the Weight Spectrum of Rate-Compatible Polar Codes

Ye, Li, Liu et al.

The weight spectrum plays a crucial role in the performance of error-correcting codes. Despite substantial theoretical exploration of polar codes with mother code length, a framework for the weight spectrum of rate-compatible polar codes remains elusive. In this paper, we address this gap by presenting the theoretical results for enumerating the number of minimum-weight codewords for quasi-uniform punctured, Wang-Liu shortened, and bit-reversal shortened decreasing polar codes. Additionally, we propose efficient algorithms for computing the average spectrum of random upper-triangular pre-transformed shortened and punctured polar codes. Notably, our algorithms operate with polynomial complexity relative to the code length. Simulation results affirm that our findings yield a precise estimation of the performance of rate-compatible polar codes.

academic

율-호환 극화 부호의 무게 스펙트럼에 관한 연구

기본 정보

논문 ID: 2410.19242
제목: On the Weight Spectrum of Rate-Compatible Polar Codes
저자: Zicheng Ye, Yuan Li, Zhichao Liu, Huazi Zhang, Jun Wang, Guiying Yan, Zhiming Ma
분류: cs.IT math.IT
발표 시간: 2024년 10월
논문 링크: https://arxiv.org/abs/2410.19242

초록

무게 스펙트럼은 오류정정 부호의 성능에서 중요한 역할을 한다. 모 부호 길이의 극화 부호에 대한 광범위한 이론적 탐구에도 불구하고, 율-호환 극화 부호의 무게 스펙트럼 프레임워크는 여전히 파악하기 어렵다. 본 논문은 준균일 천공(quasi-uniform puncturing, QUP), Wang-Liu 단축 및 비트 반전 단축 감소 극화 부호의 최소 무게 부호어 개수 열거에 대한 이론적 결과를 제시함으로써 이러한 공백을 해결한다. 더욱이, 우리는 무작위 상삼각 사전변환 단축 및 천공 극화 부호의 평균 스펙트럼을 계산하기 위한 효율적인 알고리즘을 제안한다. 주목할 만한 점은 우리의 알고리즘이 부호 길이에 대해 다항식 복잡도를 가진다는 것이다. 시뮬레이션 결과는 우리의 발견이 율-호환 극화 부호의 성능에 대한 정확한 추정을 제공함을 확인한다.

연구 배경 및 동기

문제 배경

극화 부호의 제한성: 극화 부호는 Kronecker 곱의 고유한 구조로 인해 원래 부호 길이가 2의 거듭제곱으로 제한된다. 그러나 실제 응용에서는 일반적으로 다양한 부호 길이의 메시지를 전송해야 하며, 이는 필요한 부호 길이 유연성을 제공하기 위해 천공(puncturing) 및 단축(shortening) 기술이 필요하다.
무게 스펙트럼의 중요성: 무게 스펙트럼은 최대우도(ML) 복호 성능에 상당한 영향을 미치며, 낮은 무게 부호어 개수를 기반으로 한 결합 한계(union bound)를 통해 근사할 수 있다. 그러나 정확한 무게 스펙트럼을 계산하는 복잡도는 일반적으로 부호 길이에 따라 지수적으로 증가한다.
기존 연구의 부족: 모 부호 길이의 극화 부호 무게 스펙트럼에 대한 광범위한 연구에도 불구하고, 율-호환 극화 부호 무게 스펙트럼에 대한 체계적인 프레임워크는 여전히 부족하다. 기존 방법은 복잡도가 너무 높거나 적용 범위가 제한적이다.

연구 동기

본 논문은 율-호환 극화 부호의 무게 스펙트럼 이론의 공백을 메우고, 준균일 천공(QUP), Wang-Liu 단축 및 비트 반전 단축 극화 부호에 대한 체계적인 무게 스펙트럼 분석 프레임워크를 제공하는 것을 목표로 한다.

핵심 기여

이론적 기여: QUP, Wang-Liu 단축 및 비트 반전 단축 감소 극화 부호의 최소 무게 부호어 개수를 계산하기 위한 완전한 이론적 프레임워크 및 공식을 제시한다.
알고리즘 혁신: 무작위 상삼각 사전변환 단축 및 천공 극화 부호의 평균 무게 스펙트럼을 계산하기 위한 다항식 복잡도 알고리즘을 개발한다.
성능 평가: 제안된 방법이 율-호환 극화 부호의 성능을 정확하게 추정할 수 있음을 시뮬레이션을 통해 검증하며, 특히 높은 신호대잡음비 조건에서 그러하다.
복잡도 최적화: 제안된 모든 알고리즘은 부호 길이에 대해 다항식 복잡도를 가지므로 방법의 확장성과 실용성을 보장한다.

M ≜ {x₁^(a₁)...xₘ^(aₘ) | (a₁,...,aₘ) ∈ F₂ᵐ}

|Tf(d,Y'ᵢ)| = λf(1 - βf(i)/2ʳ)

여기서 βf(i)는 f가 Y'ᵢ에서 인수분해되는 횟수이다.

알고리즘 1은 계산 과정을 설명한다:

복잡도: O(|Y'||Iᵣ|) = O(N²)
각 r차 단항식 f에 대해 단축된 인수 개수를 계산
남은 부호어 개수를 반복적으로 업데이트

2. QUP 극화 부호

보조정리 5를 통해 Pf(d,a)를 계산하기 위한 반복 방정식을 수립한다:

단항식 f = xᵢ₁...xᵢₜ에 대해, Nf(w,a)를 처음 a 비트에서 무게 w인 부호어의 개수라고 정의하면:

a ≤ 2^(it-1), w≠0일 때: Nf(w,a) = Σₛ∈B(f,t) 2^αf(s)Nf(s)(w,a) + Nf(0)(w,a)
2^(it-1) < a ≤ 2^it일 때: Nf(w,a) = Nf(2^(it-t) - w, 2^it - a)
a > 2^it일 때: Nf(w,a) = Nf(w - 2^(it-t), a - 2^it)

3. 사전변환 극화 부호 평균 무게 스펙트럼

정리 7은 사전변환 극화 부호의 평균 무게 스펙트럼을 제시한다:

E[N(d,T,X)] = Σ₁≤j≤K 2^(K-j)Ad(m,(0₁^(Ij-1),1),X) / 2^(N-Ij)

알고리즘 3을 통해 구현되며, 복잡도는 O(N³)이다.

기술적 혁신점

통일된 프레임워크: 처음으로 다양한 율 매칭 패턴에 대한 통일된 무게 스펙트럼 분석 프레임워크를 제공한다.
다항식 복잡도: 모든 알고리즘이 다항식 복잡도를 달성하여 기존의 지수 복잡도 제한을 돌파한다.
대칭성 활용: 부호어의 대칭성을 교묘하게 활용하여 계산을 단순화한다. 예를 들어 Wang-Liu 단축은 QUP의 대칭성을 통해 얻을 수 있다.
재귀적 분해: 길이 N의 부호를 두 개의 길이 N/2 부호로 분해하여 계산 복잡도를 감소시킨다.