Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On the Efficiency of Polar-Like Decoding for Symmetric Codes
 
research article

On the Efficiency of Polar-Like Decoding for Symmetric Codes

Ivanov, Kirill  
•
Urbanke, Ruediger L.  
January 1, 2022
Ieee Transactions On Communications

The recently introduced polar codes constitute a breakthrough in coding theory due to their capacity-achieving property. This goes hand in hand with a quasilinear construction, encoding, and successive cancellation list decoding procedures based on the Plotkin construction. The decoding algorithm can be applied with slight modifications to Reed-Muller or eBCH codes, that both achieve the capacity of erasure channels, although the list size needed for good performance grows too fast to make the decoding practical even for moderate block lengths. The key ingredient for proving the capacity-achieving property of Reed-Muller and eBCH codes is their group of symmetries. It can be plugged into the concept of Plotkin decomposition to design various permutation decoding algorithms. Although such techniques allow to outperform the straightforward polar-like decoding, the complexity stays impractical. In this paper, we show that although invariance under a large automorphism group is valuable in a theoretical sense, it also ensures that the list size needed for good performance grows exponentially. We further establish the bounds that arise if we sacrifice some of the symmetries. Although the theoretical analysis of the list decoding algorithm remains an open problem, our result provides an insight into the factors that impact the decoding complexity.

  • Details
  • Metrics
Type
research article
DOI
10.1109/TCOMM.2021.3121442
Web of Science ID

WOS:000742731500016

Author(s)
Ivanov, Kirill  
Urbanke, Ruediger L.  
Date Issued

2022-01-01

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

Published in
Ieee Transactions On Communications
Volume

70

Issue

1

Start page

163

End page

170

Subjects

Engineering, Electrical & Electronic

•

Telecommunications

•

Engineering

•

codes

•

maximum likelihood decoding

•

polar codes

•

codecs

•

boolean functions

•

complexity theory

•

symmetric matrices

•

reed-muller codes

•

list decoding

•

permutation decoding

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTHC  
Available on Infoscience
April 11, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/186936
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés