Scaling Exponent of List Decoders with Applications to Polar Codes

Motivated by the significant performance gains which polar codes experience when they are decoded with successive cancellation list decoders, we study how the scaling exponent changes as a function of the list size L. In particular, we fix the block error probability P-e and we analyze the tradeoff between the blocklength N and the back-off from capacity C-R using scaling laws. By means of a Divide and Intersect procedure, we provide a lower bound on the error probability under MAP decoding with list size L for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the blocklength grows large. We show that, although list decoding can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected. This result applies in particular to polar codes, since their minimum distance tends to infinity as N increases. Some considerations are also pointed out for the genie-aided successive cancellation decoder when transmission takes place over the binary erasure channel.

Scaling Exponent of List Decoders With Applications to Polar Codes

Seyed Hamed Hassani, Marco Mondelli, Rüdiger Urbanke

Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed, and the tradeoff between the block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under MAP decoding with list size L for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under MAP decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open.

Ieee-Inst Electrical Electronics Engineers Inc2015

From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance

Seyed Hamed Hassani, Marco Mondelli, Rüdiger Urbanke

{\mathcal C}_{\rm inter} = \{C_{\alpha} : \alpha \in [0, 1]\}

, where

C_{\alpha} \big |_{\alpha = 1}

is the original polar code, and

C_{\alpha} \big |_{\alpha = 0}

is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of

\alpha

. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family

{\mathcal C}_{\rm inter}

even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

2014

From Polar to Reed-Muller Codes: A Technique to Improve the Finite-Length Performance

Seyed Hamed Hassani, Marco Mondelli, Rüdiger Urbanke

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family C-inter = {C-alpha : alpha is an element of [0, 1]}, where C-alpha vertical bar(alpha=1) is the original polar code, and C-alpha vertical bar(alpha=0) is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of a. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family C-inter even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

Ieee-Inst Electrical Electronics Engineers Inc2014

From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance

Seyed Hamed Hassani, Marco Mondelli, Rüdiger Urbanke

{\mathcal C}_{\rm inter} = \{C_{\alpha} : \alpha \in [0, 1]\}

, where

C_{\alpha} \big |_{\alpha = 1}

is the original polar code, and

C_{\alpha} \big |_{\alpha = 0}

is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of

\alpha

. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family

{\mathcal C}_{\rm inter}

2014