PaperlayerView exact revision on arXiv

Source-linked AI summary

Belief Propagation List Decoding of Polar Codes

Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer, Stephan ten Brink

arXiv:1806.10503v1cs.ITmath.IT

TL;DR

Finite-length polar codes motivate alternatives to SCL because its serial, hard-output decoding has practical drawbacks, while BP has not matched its error-rate performance. BPL runs parallel BP decoders on permuted factor graphs without changing the code. It reaches SCL error-rate performance in the reported comparison, with a lower-list-size example matching SCL’s larger list.

  • Problem

    BP decoding of polar codes still lagged SCL in error-rate performance, while SCL’s serial, hard-output decoding limits throughput, latency, and iterative detection and decoding.

    Source: §I · p. 1

  • Method

    BPL runs L independent BP decoders on differently permuted polar factor graphs, retains valid codeword candidates, and selects the one nearest the received vector.

    Source: §I · p. 2, A. Algorithm · p. 3

  • Results

    At Eb/N0 = 3.2 dB, BPL (L = 5) achieves SCL (L = 32) error-rate performance and requires 1.01×10^6 PE updates.

    Source: B. Potential Benefits · p. 3

  • Takeaways & Limitations

    BPL does not require changes to the polar code structure and provides soft-output decoding, with the possibility of low-latency implementations.

    Source: §I · p. 2, §V · p. 4

    A naive BPL implementation is more computationally complex than SCL, with complexity increasing linearly with the number of BP iterations.

    Source: B. Potential Benefits · p. 3

Abstract

from arXiv · show

We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size $L$. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are lower decoding latency compared to the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.

I. INTRODUCTION

SCL decoding can approach the ML bound but is serial and hard-output, while BP offers parallel, soft-output decoding yet has lagged in error-rate performance. BPL addresses this gap with parallel BP decoders on permuted graphs without changing the polar code.

I. INTRODUCTION

  • SCL can achieve the ML bound for sufficiently large L, but its serial decoding reduces throughput and increases latency, and its hard output limits iterative detection and decoding.CRC- and parity-check-aided polar codes were reported to outperform state-of-the-art LDPC codes under SCL.Source: §I · p. 1
  • BP message passing over the encoding graph can be parallelized and inherently provides soft-in/soft-out decoding for joint iterative detection and decoding.These properties make BP a candidate for applications demanding high data rate and low latency.Source: §I · p. 1
  • Prior BP enhancements still left a large performance gap to SCL, and some approaches were incompatible with standardized CRC/PC-aided polar codes.The cited methods include post-processing, appended LDPC coding, and altered information/frozen-channel selection.Source: §I · p. 1
  • BPL uses L parallel independent BP decoders on permuted factor graphs without changing the polar code or concatenating an outer code.Unlike the approach in, the code structure is left unchanged.Source: §I · p. 2

II. POLAR CODES AND ITERATIVE DECODING

A polar code maps information and frozen bits through a generator matrix, with information positions chosen during code construction. Iterative BP passes messages over the encoding factor graph and can stop when a consistency test succeeds or an iteration limit is reached.

II. POLAR CODES AND ITERATIVE DECODING

  • The generator matrix is G = F^⊗n, arising from recursive combination of N = 2^n identical channels.The recursive combination produces channel polarization.Source: §II · p. 2
  • A polar codeword is x = u · G, where u contains k information bits and N − k frozen bits, and the information set A contains the k most reliable positions.The default design is Bhattacharyya-based, though other constructions can use a different A.Source: §II · p. 2
  • BP applies iterative message passing to the encoding factor graph, which has n + 1 stages with N nodes per stage and log2(N)·N/2 processing elements.It uses left-to-right R-messages and right-to-left L-messages; the channel LLRs initialize the L-messages at the last stage, while frozen and non-frozen positions determine the initial R-messages.Source: §II · p. 2
  • BP can stop at a maximum iteration count or when an early stopping condition is met; practical conditions test intermediate hard decisions on u or x.The G-matrix condition checks whether x̂ = û·G; the CRC condition checks û and requires an outer CRC code.Source: §II · p. 2

III. BELIEF PROPAGATION LIST DECODER

Polar factor graphs can be permuted across stages while preserving the encoding relation, producing different loop structures. The decoder uses distinct permutations because which graph performs best can depend on the input.

III. BELIEF PROPAGATION LIST DECODER

  • The n stages admit n! factor-graph permutations, represented by a permutation vector Π whose entries determine stage separations s_j = 2^(π_j−1).For n = 3, the examples Π = [3,2,1] and [2,1,3] yield separations [4,2,1] and [2,1,4], respectively.Source: §III · p. 2
  • The graph can be described by separation vector s, while Π is used to represent a permutation of the stage indices.The authors note that Π may be more convincing from an implementation perspective.Source: §III · p. 2
  • Permuting the factor graph changes its loops, so one permutation may perform better than another for a particular transmitted codeword and noise realization.The decoder is depicted as L parallel independent BP decoders.Source: §III · p. 3, Figure 3 · p. 3

A. Algorithm

BPL’s error-rate performance converges to SCL’s for the same information set, and improves as list size and maximum iterations increase. It runs BP on selected permuted graphs and chooses among valid codeword candidates.

A. Algorithm

  • The decoder runs L independent BP decoders on different permuted graphs, including the n − 1 cyclic shifts of the original graph for reproducibility.Each decoder runs until the G-matrix stopping condition is met or Nit,max iterations have been performed.Source: A. Algorithm · p. 3
  • After decoding, only candidates satisfying the G-matrix stopping condition are valid, and BPL outputs the valid codeword nearest the channel output in Euclidean distance.The candidate list contains up to L codewords.Source: A. Algorithm · p. 3
  • BPL error-rate performance converges to SCL for the same information set A, and increasing L and Nit,max enhances BPL performance.The comparison is reported for Fig. 1.Source: A. Algorithm · p. 3

B. Potential Benefits

At Eb/N0 = 3.2 dB, BPL with L = 5 matches the error-rate performance of SCL with L = 32. BPL also provides soft output and avoids intermediate sorting, but its parallel BP decoders increase computational complexity.

B. Potential Benefits

  • BPL is a soft-output decoder that can support joint detection and decoding, unlike hard-output decoders such as SCL.Source: B. Potential Benefits · p. 3
  • BPL latency scales as O(Nit,max·logN), with fully parallelizable stages and possible stage-combining without performance loss.For a constant number of iterations, latency scales with log2 N; the passage contrasts this with SCL's O(N) latency without further pruning.Source: B. Potential Benefits · p. 3
  • BPL avoids intermediate sorting and sorts only once at the end to select the codeword closest to y.The passage describes SCL's metric sorter as time-consuming and expensive for large L.Source: B. Potential Benefits · p. 3
  • BPL uses L parallel BP decoders with O(L·N·logN) complexity for a constant iteration count, and its operation count can exceed SCL's.Its complexity increases linearly with the number of BP iterations.Source: B. Potential Benefits · p. 3
  • At Eb/N0 = 3.2 dB, BPL with L = 5 matches SCL (L = 32) error-rate performance and requires 1.01×10^6 PE updates.PE and unit calculation updates have similar complexity; the passage describes this as feasible complexity compared with plain SCL in the high-SNR region.Source: B. Potential Benefits · p. 3

IV. RM-POLAR CODES UNDER BPL DECODING

The section presents a hybrid RM-polar construction that changes frozen and information bit selection, yielding better error-rate performance than Bhattacharyya-based construction under BPL and SCL. The reported BPL gain comes without extra complexity or CRC concatenation.

IV. RM-POLAR CODES UNDER BPL DECODING

  • The construction combines RM and polar selection rules because polar construction targets SC error probability, whereas RM construction targets large minimum Hamming distance.The passage notes that distance properties have greater impact than polarization for finite-length codes.Source: §IV · pp. 3–4
  • Hybrid RM-polar construction yields significantly better error-rate performance than Bhattacharyya-based construction under BPL and SCL decoding.Fig. 4 compares BLER for BP, SCL (L = 32), and BPL; the prose reports the hybrid-construction advantage.Source: Figure 4 · p. 4, §IV · p. 4
  • The hybrid construction freezes bits whose generator-matrix row weights are at most threshold d, then selects the k most reliable remaining channels as information bits.The resulting code is denoted PRM(N,k,d).Source: §IV · p. 4
  • PRM(2048,1024,16) uses SCL list size L > 512 to closely approach its ML bound, while P(2048,1024) needs L = 32 in the high-SNR region Eb/N0 > 1.5 dB.Source: §IV · p. 4
  • BPL gains from hybrid RM-polar construction come at no extra complexity cost and use no additional CRC.The compared codes differ only in frozen/information bit selection.Source: §IV · p. 4

V. CONCLUSION

The proposed BPL decoder matches SCL error-rate performance using multiple permuted factor graphs, without changing the polar-code structure. It offers soft-output and low-latency potential, while complexity and CRC/PC compatibility remain open issues.

V. CONCLUSION

  • The BPL decoder reaches the same error-rate performance as SCL decoding for polar codes.The authors describe it as the best iterative decoder for plain polar codes known to them.Source: §V · p. 4
  • The decoder's gains come solely from the decoding algorithm and require no changes or additions to the polar-code structure.Source: §V · p. 4
  • Carefully constructed polar codes under BPL decoding are less than 0.5 dB away from CRC-aided polar codes under SCL decoding.A hybrid RM-polar design can further enhance performance by improving the polar code's distance spectrum.Source: §V · p. 4
  • BPL provides soft-in/soft-out decoding and the possibility of low-latency implementations.Source: §V · p. 4
  • High decoding complexity and missing CRC/PC compatibility are identified as open issues for future research.Source: §V · p. 4
Loading 1806.10503v1…