Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

TELKOMNIKA (Telecommunication Computing Electronics and Control)

Decoding of the extended Golay code by the simplified successive-cancellation list decoder adapted to multi-kernel polar codes

Driss Khebbou, Idriss Chana, Hussain Ben-Azza

Published Mar 29, 2023• 3 citations
Publisher

Abstract

This paper describes an adaptation of a polar code decoding technique in favor of the extended Golay code. Based on the bridge provided by a permutation matrix between the code words of these two classes of codes, the Golay code can be decoded by any polar code technique. Contrary to the successive-cancellation list technique which is characterized by a serial estimation of the bits, we propose in this work an adaptation of the simplified successive-cancellation list technique to polar codes equivalent to the Golay code. The simulations have achieved the performance of a maximum likelihood decoding, with the low decoding complexity of polar codes, compared to one of the universal decoders of linear codes most known in the literature.

DOI
10.12928/telkomnika.v21i3.23360

Related papers

SIMPLIFIED SUCCESSIVE-CANCELLATION LIST POLAR DECODING FOR BINARY LINEAR BLOCK CODES

Driss Khebbou, Reda Benkhouya, Idriss Chana +1 more

This paper aims to take advantage of the performances of polar decoding techniques for the benefit of binary linear block codes (BLBCs) with the main objective is to study the performances of the SSCL decoding for short-length BLBCs. Polar codes are one of the most recent error-correcting codes to be invented, and they have been mathematically demonstrated to be able to correct all errors under a specific situation, using the successive-cancellation decoder. However, their performances for real-time wireless communications at short block lengths remain less attractive. To take advantage of the performance of these codes in favor of error correction codes of short block length, an adaptation of the simplified successive-cancellation list as a decoder for polar codes for the benefit of short block length binary linear block codes is presented in this paper. This adaptation makes it possible to take advantage of the performances of less complex decoding methods for polar codes for BLBCs with latency and complexity optimization of the standard successive-cancellation list decoder. The experiment shows that the method can achieve the performances of the most famous order statistic decoder for binary linear block codes, which can achieve the performances of maximum-likelihood decoding with computational complexity and memory constraints.

Journal of Southwest Jiaotong University•Dec 24, 2021•3 citations

Chained successive cancellation decoding of the extended Golay code

Peter Trifonov

The extended Golay code is shown to be representable as a chained polar subcode. This enables its decoding with the successive cancellation algorithm and its sequential generalization. The decoder can be further simplified by employing fast Hadamard transform. The complexity of the obtained algorithm is comparable with that of the Vardy algorithm.

arXiv:1801.06315•Iran Workshop on Communication and Information Theory (IWCIT)•Apr 1, 2018•0 citations

On the Successive Cancellation Decoding of Polar Codes with Arbitrary Linear Binary Kernels

Zhiliang Huang, Zhang, Shiyi, Zhang, Feiyan +2 more

A method for efficiently successive cancellation (SC) decoding of polar codes with high-dimensional linear binary kernels (HDLBK) is presented and analyzed. We devise a $l$-expressions method which can obtain simplified recursive formulas of SC decoder in likelihood ratio form for arbitrary linear binary kernels to reduce the complexity of corresponding SC decoder. By considering the bit-channel transition probabilities $W_{G}^{(\cdot)}(\cdot|0)$ and $W_{G}^{(\cdot)}(\cdot|1)$ separately, a $W$-expressions method is proposed to further reduce the complexity of HDLBK based SC decoder. For a $m\times m$ binary kernel, the complexity of straightforward SC decoder is $O(2^{m}N\log N)$. With $W$-expressions, we reduce the complexity of straightforward SC decoder to $O(m^{2}N\log N)$ when $m\leq 16$. Simulation results show that $16\times16$ kernel polar codes offer significant advantages in terms of error performances compared with $2\times2$ kernel polar codes under SC and list SC decoders.

arXiv:1701.03264•Jan 12, 2017•9 citations

Polar-Code Construction of Golay Codes

Valerio Bioglio, Ingmar Land

This letter proposes a reinterpretation of the classical binary Golay codes as Polar codes with additional inner permutations and puncturing. This establishes a novel relationship between algebraic codes and codes based on Kronecker products, like polar codes. Naturally, this construction also allows for polar-code-type decoding of the Golay codes using successive cancellation list decoding. Using the Golay code as a driving example, we conjecture that other algebraic codes may be represented in a similar way.

IEEE Communications Letters•Jan 15, 2018•9 citations

Simplified Successive-Cancellation List decoding of polar codes

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

The Successive-Cancellation List (SCL) decoding algorithm is one of the most promising approaches towards practical polar code decoding. It is able to provide a good trade-off between error-correction performance and complexity, tunable through the size of the list. In this paper, we show that in the conventional formulation of SCL, there are redundant calculations which do not need to be performed in the course of the algorithm. We simplify SCL by removing these redundant calculations and prove that the proposed simplified SCL and the conventional SCL algorithms are equivalent. The simplified SCL algorithm is valid for any code and can reduce the time-complexity of SCL without affecting the space complexity.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•72 citations

Polar List Decoding for Large Polarization Kernels

Bhaskar Gupta, Hanwen Yao, Arman Fazeli +1 more

Polar codes constructed with large polarization kernels were recently proven to be able to achieve optimal finite-length scaling properties. However, straightforward decoding for large kernel polar codes introduces a complexity coefficient that is exponential to the kernel sizes, which makes such codes generally believed to be impractical. In this paper, we present a new method that decodes large kernel polar codes with a complexity coefficient that is polynomial to the kernel sizes. This could facilitate the implementation of large kernel polar codes for practical use in the future.Successive cancellation decoding for large kernel polar codes requires calculation on the probabilities of its bit channels. Similar to conventional polar codes, those bit channels follow a recursive relation, which make this calculation boil down to computing the probabilities for bit channels of a single polarization kernel. This kernel-level computation can be shown equivalent to soft-output maximum-likelihood (ML) decoding on a single bit of a linear block code. In our proposed method, we first use linear operations to represent the considered linear block code as a polar code with dynamically frozen bits, and then use a modified polar list decoder to get an approximate value on the soft-output of the desired bit. This method is motivated by the observation that at short block lengths, polar list decoding with a large enough list size can well-approximate ML decoding. The proposed low-complexity method allows us to decode polar codes constructed with a 64 × 64 polarization kernel with scaling exponent µ ≈ 2.87 for the first time.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2021•7 citations
This paper describes an adaptation of a polar code decoding technique in favor of the extended Golay code. Based on the bridge provided by a permutation matrix between the code words of these two classes of codes, the Golay code can be decoded by any polar code technique. Contrary to the successive-cancellation list technique which is characterized by a serial estimation of the bits, we propose in this work an adaptation of the simplified successive-cancellation list technique to polar codes equivalent to the Golay code. The simulations have achieved the performance of a maximum likelihood decoding, with the low decoding complexity of polar codes, compared to one of the universal decoders of linear codes most known in the literature.
This paper aims to take advantage of the performances of polar decoding techniques for the benefit of binary linear block codes (BLBCs) with the main objective is to study the performances of the SSCL decoding for short-length BLBCs. Polar codes are one of the most recent error-correcting codes to be invented, and they have been mathematically demonstrated to be able to correct all errors under a specific situation, using the successive-cancellation decoder. However, their performances for real-time wireless communications at short block lengths remain less attractive. To take advantage of the performance of these codes in favor of error correction codes of short block length, an adaptation of the simplified successive-cancellation list as a decoder for polar codes for the benefit of short block length binary linear block codes is presented in this paper. This adaptation makes it possible to take advantage of the performances of less complex decoding methods for polar codes for BLBCs with latency and complexity optimization of the standard successive-cancellation list decoder. The experiment shows that the method can achieve the performances of the most famous order statistic decoder for binary linear block codes, which can achieve the performances of maximum-likelihood decoding with computational complexity and memory constraints.
A method for efficiently successive cancellation (SC) decoding of polar codes with high-dimensional linear binary kernels (HDLBK) is presented and analyzed. We devise a lll-expressions method which can obtain simplified recursive formulas of SC decoder in likelihood ratio form for arbitrary linear binary kernels to reduce the complexity of corresponding SC decoder. By considering the bit-channel transition probabilities WG(⋅)(⋅∣0)W_{G}^{(\cdot)}(\cdot|0)WG(⋅)​(⋅∣0) and WG(⋅)(⋅∣1)W_{G}^{(\cdot)}(\cdot|1)WG(⋅)​(⋅∣1) separately, a WWW-expressions method is proposed to further reduce the complexity of HDLBK based SC decoder. For a m×mm\times mm×m binary kernel, the complexity of straightforward SC decoder is O(2mNlog⁡N)O(2^{m}N\log N)O(2mNlogN). With WWW-expressions, we reduce the complexity of straightforward SC decoder to O(m2Nlog⁡N)O(m^{2}N\log N)O(m2NlogN) when m≤16m\leq 16m≤16. Simulation results show that 16×1616\times1616×16 kernel polar codes offer significant advantages in terms of error performances compared with 2×22\times22×2 kernel polar codes under SC and list SC decoders.
This letter proposes a reinterpretation of the classical binary Golay codes as Polar codes with additional inner permutations and puncturing. This establishes a novel relationship between algebraic codes and codes based on Kronecker products, like polar codes. Naturally, this construction also allows for polar-code-type decoding of the Golay codes using successive cancellation list decoding. Using the Golay code as a driving example, we conjecture that other algebraic codes may be represented in a similar way.
The Successive-Cancellation List (SCL) decoding algorithm is one of the most promising approaches towards practical polar code decoding. It is able to provide a good trade-off between error-correction performance and complexity, tunable through the size of the list. In this paper, we show that in the conventional formulation of SCL, there are redundant calculations which do not need to be performed in the course of the algorithm. We simplify SCL by removing these redundant calculations and prove that the proposed simplified SCL and the conventional SCL algorithms are equivalent. The simplified SCL algorithm is valid for any code and can reduce the time-complexity of SCL without affecting the space complexity.
Polar codes constructed with large polarization kernels were recently proven to be able to achieve optimal finite-length scaling properties. However, straightforward decoding for large kernel polar codes introduces a complexity coefficient that is exponential to the kernel sizes, which makes such codes generally believed to be impractical. In this paper, we present a new method that decodes large kernel polar codes with a complexity coefficient that is polynomial to the kernel sizes. This could facilitate the implementation of large kernel polar codes for practical use in the future.Successive cancellation decoding for large kernel polar codes requires calculation on the probabilities of its bit channels. Similar to conventional polar codes, those bit channels follow a recursive relation, which make this calculation boil down to computing the probabilities for bit channels of a single polarization kernel. This kernel-level computation can be shown equivalent to soft-output maximum-likelihood (ML) decoding on a single bit of a linear block code. In our proposed method, we first use linear operations to represent the considered linear block code as a polar code with dynamically frozen bits, and then use a modified polar list decoder to get an approximate value on the soft-output of the desired bit. This method is motivated by the observation that at short block lengths, polar list decoding with a large enough list size can well-approximate ML decoding. The proposed low-complexity method allows us to decode polar codes constructed with a 64 × 64 polarization kernel with scaling exponent µ ≈ 2.87 for the first time.