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

Seyed Hamed Hassani, Marco Mondelli, Rüdiger Urbanke
Ieee-Inst Electrical Electronics Engineers Inc, 2014
Article

Résumé

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.

Official source

https://infoscience.epfl.ch/record/204206?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

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 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 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.

Ieee2014

Chargement

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

Chargement

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algorithms. Recent results prove that another way to achieve capacity is via symmetry, which is the case of the Reed-Muller and extended Bose-Chaudhuri-Hocquenghem (BCH) codes. However, this proof holds only for erasure channel and maximum a posteriori decoding, which is computationally intractable for the general channels.In the first part of this thesis, we talk about the performance improvements that an automorphism group of the code brings on board. We propose two decoding algorithms for the Reed-Muller codes, which are invariant under a large group of permutations and are expected to benefit the most. The former is based on plugging the codeword permutations in successive cancellation decoding, and the latter utilizes the code representation as the evaluations of Boolean monomials. However, despite the performance improvements, it is clear that the decoding complexity grows quickly and becomes impractical for moderate-length codes. In the second part of this thesis, we provide an explanation for this observation. We use the Boolean polynomial representation of the code in order to show that polar-like decoding of sufficiently symmetric codes asymptotically needs an exponential complexity. The automorphism groups of the Reed-Muller and eBCH codes limit the efficiency of their polar-like decoding for long codes, hence we either should focus on short lengths or find another way. We demonstrate that asymptotically same restrictions (although with a slower convergence) hold for more relaxed condition that we call partial symmetry. The developed framework also enables us to prove that the automorphism group of polar codes cannot include a large affine subgroup.In the last part of this thesis, we address a completely different problem. A device-independent quantum key distribution (DIQKD) aims to provide private communication between parties and has the security guarantees that come mostly from quantum physics, without making potentially unrealistic assumptions about the nature of the communication devices. After the quantum part of the DIQKD protocol, the parties share a secret key that is not perfectly correlated. In order to synchronize, some information needs to be revealed publicly, which makes this formulation equivalent to the asymmetric Slepian-Wolf problem that can be solved using binary linear error-correction codes. As any amount of the revealed information reduces the key secrecy, the utilized code should operate close to the finite-length limits. The channel in consideration is non-standard and, due to its experimental nature, it can actually slightly differ from the considered models. In order to solve this problem, we designed a simple scheme using universal SC-LDPC codes and used in the first successful experimental demonstration of DIQKD protocol.

EPFL2022

Chargement

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

EPFL2022