Source-linked AI summary
An Adaptive Successive Cancellation List Decoder for Polar Codes with Cyclic Redundancy Check
Bin Li, Hui Shen, David Tse
TL;DR
Finite-length polar codes need stronger decoding than SC, while CRC concatenation makes approaching ML performance require very large list sizes. The paper proposes an adaptive SC-List decoder that increases list size until a survival path passes CRC, reducing complexity while preserving or improving performance. For a (2048, 1024) polar code with a 24-bit CRC, it achieves FER ≤ 10^-3 at Eb/No=1.1 dB, about 0.2 dB from the information theoretic limit.
Problem
CRC-concatenated polar codes require very large list sizes to approach ML performance, causing very high decoding complexity.
Method
The adaptive SC-List decoder starts with a small list size and iteratively increases it until at least one survival path passes CRC or L reaches L_max.
Results
FER ≤ 10^-3 at Eb/No=1.1 dB is achieved for a (2048, 1024) polar code with a 24-bit CRC, about 0.2 dB from the information theoretic limit.
Takeaways & Limitations
Compared with constant-list SC-List decoding, the adaptive decoder achieves the same performance with significantly lower complexity or much better performance at the same decoding complexity.
Abstract
from arXiv · showhide
In this letter, we propose an adaptive SC (Successive Cancellation)-List decoder for polar codes with CRC. This adaptive SC-List decoder iteratively increases the list size until the decoder outputs contain at least one survival path which can pass CRC. Simulation shows that the adaptive SC-List decoder provides significant complexity reduction. We also demonstrate that polar code (2048, 1024) with 24-bit CRC decoded by our proposed adaptive SC-List decoder with very large list size can achieve a frame error rate FER=0.001 at Eb/No=1.1dB, which is about 0.2dB from the information theoretic limit at this block length.
I. INTRODUCTION
The introduction motivates adaptive SC-List decoding by the poor short- and moderate-length performance of SC decoding and the high list sizes required after CRC concatenation. It positions adaptive list sizing as a way to reduce the resulting complexity.
- Motivation: Polar codes can achieve Shannon capacity with simple, low-complexity encoding and successive cancellation decoding at sufficiently large block lengths.The stated complexity is of order O(N log N).
- Motivation: SC decoding performs worse than LDPC and turbo codes for short and moderate block lengths.
- Motivation: CRC concatenation improves polar-code performance, and a (2048, 1024) polar code with a 16-bit CRC was reported to outperform Turbo and LDPC codes using SC-List decoding.
- Motivation: CRC concatenation requires much larger list sizes to approach ML performance, making conventional SC-List decoding highly complex.
- Motivation: Low average complexity can reduce handset processing energy and support efficient statistical sharing of base-station decoding resources.
A. Polar Codes
This section defines polar-code construction through Kronecker-powered generator matrices, information and frozen-bit index sets, and the resulting encoded sequence. It also notes the SC decoder's low complexity and asymptotic capacity achievement.
- Construction: The block length satisfies N = 2^n, and F^{⊗n} denotes the nth Kronecker power of the kernel matrix F.
- Construction: The polar-code generator matrix is defined as G_N = B_N F^{⊗n}, where B_N is a bit-reversal permutation matrix.
- Encoding: The encoding sequence is generated by x = uG_N, with information bits indexed by A and frozen bits indexed by A^c.
- Encoding: The codeword can be decomposed into contributions from information and frozen bits through the corresponding submatrices of G_N.
- Decoding: The SC decoder has O(N log N) decoding complexity and can achieve capacity when N is very large.
B. SC-List Decoder for Polar Codes
SC-List decoding improves finite-length polar-code performance by retaining multiple candidate paths, while simulations and weight enumeration characterize its behavior for L=32 and large list sizes.
- SC-List decoding: SC-List decoding retains L survival paths, splits paths on unfrozen bits, and discards the least probable paths when their number exceeds L.
- SC-List decoding: L=32 SC-List decoding performs much better than SC decoding and can match optimal ML decoding at high SNR for rate-1/2 polar codes with N=2048 and 8192.
- Performance evaluation: Fig. 1 evaluates FER for the (2048, 1024) polar code with BPSK over an AWGN channel and compares it with an ML bound and an approximate union bound.
- Performance evaluation: The approximate union bound uses minimum distance d_0=16, second least distance d_1=24, and codeword counts N_16=11648 and N_24=215040.
- Weight analysis: The approximate union bound closely matches the ML lower bound, while large-list decoding finds only codewords of weights 16, 24, and 32.
- Weight analysis: The weight-16 and weight-24 codeword counts saturate at L=11648 and L=215040, respectively, supporting that those codewords were fully identified.
III. A NEW ADAPTIVE SC-LIST DECODER FOR POLAR CODES WITH CRC
The proposed adaptive SC-List decoder starts with a small list and doubles it only when no surviving path passes CRC, reducing average complexity while preserving or improving performance. Simulations report substantial complexity savings and near-Shannon-limit FER for a polar code with CRC.
- CRC concatenation: 16-bit CRCs eliminate the weight-16 and weight-24 codewords for five of six tested CRCs, increasing minimum Hamming distance from 16 to 32.The exception was CRC-16-DNP.
- Adaptive decoding: The decoder begins with a small list size and iteratively doubles it when no survival path passes CRC, up to a predefined maximum.CRC is applied to each surviving path after SC-List decoding; a highest-probability CRC-valid path is output when available.
- Complexity: At Eb/No=1.6 dB, maximum list size 8192 gives a mean list size of 2.47 and about 3316 times complexity reduction versus constant list size 8192.The performance is reported as the same as the constant-list decoder.
- Performance: With maximum list size 262144, a (2048, 1024) polar code with 24-bit CRC achieves FER ≤ 10^-3 at Eb/No=1.1 dB, 0.2 dB from the Shannon limit.The corresponding calculated minimum Eb/No for FER=10^-3 is 0.9 dB.
IV. CONCLUSION
The proposed adaptive SC-List decoder uses a variable list size to reduce decoding complexity while preserving or improving performance relative to constant-list decoding. With a large maximum list size, it approaches the information-theoretic limit for a (2048, 1024) polar code with 24-bit CRC.
- Adaptive list sizing achieves the same performance with significantly lower complexity than conventional constant-list SC-List decoding.Alternatively, it can achieve much better performance at the same decoding complexity.
- FER ≤ 0.001 is achieved at Eb/No=1.1dB for a polar code (2048, 1024) with a 24-bit CRC.
- The reported operating point is about 0.2dB from the information theoretic limit at the same block length.