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

arXiv:2501.07279 · IEEE Transactions on Communications

Toward Universal Decoding of Binary Linear Block Codes via Enhanced Polar Transformations

Chien-Ying Lin, Yu-Chih Huang, Shin-Lin Shieh, Po‐Ning Chen

Published Jul 8, 2025• 5 citations
arXivHTMLPDF

Abstract

Binary linear block codes (BLBCs) are essential to modern communication, but their diverse structures often require tailor-made decoders, increasing complexity. This work introduces enhanced polar decoding ($\textsf {PD}^{+}$), a universal soft decoding algorithm that transforms any BLBC into a polar-like code compatible with efficient polar code decoders such as successive cancellation list (SCL) decoding. Key innovations in$\textsf {PD}^{+}$include pruning polar kernels, shortening codes, and leveraging a simulated annealing algorithm to optimize transformations. These enable$\textsf {PD}^{+}$to achieve competitive or superior performance to state-of-the-art algorithms like OSD and GRAND across various codes, including extended BCH, extended Golay, and binary quadratic residue codes, with significantly lower complexity. Moreover,$\textsf {PD}^{+}$is designed to be forward-compatible with advancements in polar code decoding techniques and AI-driven search methods, making it a robust and versatile solution for universal BLBC decoding in both present and future systems.

DOI
10.1109/tcomm.2025.3587044

Related papers

Parallel Decoding of Binary Linear Block Codes via Equivalent Polar Transformation Class

P. Li, Yu-Chih Huang

A parameterized universal decoding framework based on polar transformations was recently proposed to enable polar-style decoding of general binary linear block codes (BLBCs). However, existing parallelization methods for polar codes cannot be directly applied to this framework. The key obstacle is that these methods rely on static frozen-set structures, which are incompatible with the dynamic frozen constraints induced by polar transformations. To address this challenge, we revisit code automorphisms from a new perspective: instead of applying them to the codeword space, we let them act on the transformation parameter itself. We show that the BLBC automorphism group induces equivalence polar transformation classes. Crucially, all transformations within an equivalence class share the same polar subcode structure, eliminating the need for separate decoder designs. This insight enables a novel parallel decoding framework termed polar ensemble decoding (PED). By decoding multiple equivalent transformations simultaneously, PED exploits transformation diversity while maintaining decoder compatibility. Simulation results on extended BCH and extended Golay codes demonstrate that PED achieves near maximum-likelihood performance while significantly reducing the decoding latency compared to successive cancellation list (SCL) decoding.

arXiv:2601.11373•Jan 16, 2026•0 citations

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

Practical Decoding for Deep Polar Codes

Donghwa Han, Min Jang, Donghun Lee +2 more

Pre-transformed polar codes constitute a broad class of codes constructed through the serial concatenation of outer codes and polar codes, enhancing the performance of standalone polar codes either by improving the weight distribution or by increasing the error-decay rate. Deep polar codes, a novel variant within this class, are constructed through a pre-transformation that involves a series of nested polar codes with increasing dimensions across layers. The proposed successive cancellation list with backpropagation parity check (SCL-BPC) decoder exploits the parity equations naturally arising from this nested encoding structure. In certain scenarios, deep polar codes with SCL-BPC decoding demonstrate superior performance compared to other pre-transformed polar codes. However, the SCL-BPC algorithm incurs additional decoding complexity and results in uneven decoding times. To address these issues, we investigate the matrix representation of the pre-transformation in deep polar codes and develop efficient implementation solutions for SCL-BPC decoding. Additionally, we introduce a low-complexity approach to SCL-BPC, which exhibits only a marginal reduction in performance.

IEEE Globecom Workshops (GC Wkshps)•Dec 8, 2024•1 citation

A Universal List Decoding Algorithm With Application to Decoding of Polar Codes

Xiangping Zheng, Xiao Ma

This paper is concerned with a guessing codeword decoding (GCD) of linear block codes, which is optimal and typically requires a fewer number of searches than the naive exhaustive search decoding (ESD). Compared with the guessing random additive noise decoding (GRAND), which is only efficient for high-rate codes, the GCD is efficient for not only high-rate codes but also low-rate codes. We prove that the GCD typically requires a fewer number of queries than the GRAND. Compared with the conventional ordered statistics decoding (OSD), the GCD does not require the online Gaussian elimination (GE). In addition to limiting the maximum number of searches, we suggest limiting the radius of searches in terms of soft weights or tolerated performance loss to further reduce the decoding complexity, resulting in the so-called truncated GCD. The performance gap between the truncated GCD and the optimal decoding can be upper bounded approximately by the saddlepoint approach or other numerical approaches. The derived upper bound captures the relationship between the performance and the decoding parameters, enabling us to balance the performance and the complexity by optimizing the decoding parameters of the truncated GCD. We also introduce a parallel implementation of the (truncated) GCD algorithm to reduce decoding latency without compromising performance. Another contribution of this paper is the application of the GCD to the polar codes. We propose a multiple-bit-wise decoding algorithm over a pruned tree for the polar codes, referred to as the successive-cancellation list (SCL) decoding algorithm by GCD. First, we present a strategy for pruning the conventional polar decoding tree based on the complexity analysis rather than the specific bit patterns. Then we apply the GCD algorithm in parallel aided by the early stopping criteria to the leaves of the pruned tree. Simulation results show that, without any performance loss as justified by analysis, the proposed decoding algorithm can significantly reduce the decoding latency of the polar codes.

arXiv:2405.03252•IEEE Transactions on Information Theory•Dec 2, 2024•18 citations

Single parity check node adapted to polar codes with dynamic frozen bit equivalent to binary linear block codes

Driss Khebbou, Idriss Chana, Hussain Ben-Azza

In the context of decoding binary linear block codes by polar code decoding techniques, we propose in this paper a new optimization of the serial nature of decoding the polar codes equivalent to binary linear block codes. In addition to the special nodes proposed by the simplified successive-cancellation list technique, we propose a new special node allowing to estimate in parallel the bits of its sub-code. The simulation is done in an additive white gaussian noise channel (AWGN) channel for several linear block codes, namely bose–chaudhuri–hocquenghem codes (BCH) codes, quadratic-residue (QR) codes, and linear block codes recently designed in the literature. The performance of the proposed technique offers the same performance in terms of frame error rate (FER) as the ordered statistics decoding (OSD) algorithm, which achieves that of maximum likelihood decoder (MLD), but with high memory requirements and computational complexity.

Indonesian Journal of Electrical Engineering and Computer Science•Nov 18, 2022•4 citations

SCL Decoding of Non-Binary Linear Block Codes

Jingyu Lin, Li Chen, Xiaoqian Ye

Non-binary linear block codes (NB-LBCs) are an important class of error-correcting codes that are especially competent in correcting burst errors. They have broad applications in modern communications and storage systems. However, efficient soft-decision decoding of these codes remains to be further developed. This paper proposes successive cancellation list (SCL) decoding for NB-LBCs that are defined over a finite field of characteristic two, i.e., F2r, whereris the extension degree. By establishing a one-to-r mapping between the binary composition of each non-binary codeword andrbinary polar codewords, SCL decoding of therpolar codes can be performed with a complexity that is sub-quadratic in the codeword length. A simplified path sorting is further proposed to facilitate the decoding. Simulation results on short-length extended Reed-Solomon (eRS) and non-binary extended BCH (NB-eBCH) codes show that SCL decoding can outperform their state-of-the-art soft-decision decoding with fewer finite field arithmetic operations. For length-16 eRS codes, their maximum-likelihood (ML) decoding performances can be approached with a moderate list size.

arXiv:2511.11256•IEEE Communications Letters•Jan 1, 2026•0 citations
Binary linear block codes (BLBCs) are essential to modern communication, but their diverse structures often require tailor-made decoders, increasing complexity. This work introduces enhanced polar decoding (PD+\textsf {PD}^{+}PD+), a universal soft decoding algorithm that transforms any BLBC into a polar-like code compatible with efficient polar code decoders such as successive cancellation list (SCL) decoding. Key innovations inPD+\textsf {PD}^{+}PD+include pruning polar kernels, shortening codes, and leveraging a simulated annealing algorithm to optimize transformations. These enablePD+\textsf {PD}^{+}PD+to achieve competitive or superior performance to state-of-the-art algorithms like OSD and GRAND across various codes, including extended BCH, extended Golay, and binary quadratic residue codes, with significantly lower complexity. Moreover,PD+\textsf {PD}^{+}PD+is designed to be forward-compatible with advancements in polar code decoding techniques and AI-driven search methods, making it a robust and versatile solution for universal BLBC decoding in both present and future systems.
A parameterized universal decoding framework based on polar transformations was recently proposed to enable polar-style decoding of general binary linear block codes (BLBCs). However, existing parallelization methods for polar codes cannot be directly applied to this framework. The key obstacle is that these methods rely on static frozen-set structures, which are incompatible with the dynamic frozen constraints induced by polar transformations. To address this challenge, we revisit code automorphisms from a new perspective: instead of applying them to the codeword space, we let them act on the transformation parameter itself. We show that the BLBC automorphism group induces equivalence polar transformation classes. Crucially, all transformations within an equivalence class share the same polar subcode structure, eliminating the need for separate decoder designs. This insight enables a novel parallel decoding framework termed polar ensemble decoding (PED). By decoding multiple equivalent transformations simultaneously, PED exploits transformation diversity while maintaining decoder compatibility. Simulation results on extended BCH and extended Golay codes demonstrate that PED achieves near maximum-likelihood performance while significantly reducing the decoding latency compared to successive cancellation list (SCL) decoding.
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.
Pre-transformed polar codes constitute a broad class of codes constructed through the serial concatenation of outer codes and polar codes, enhancing the performance of standalone polar codes either by improving the weight distribution or by increasing the error-decay rate. Deep polar codes, a novel variant within this class, are constructed through a pre-transformation that involves a series of nested polar codes with increasing dimensions across layers. The proposed successive cancellation list with backpropagation parity check (SCL-BPC) decoder exploits the parity equations naturally arising from this nested encoding structure. In certain scenarios, deep polar codes with SCL-BPC decoding demonstrate superior performance compared to other pre-transformed polar codes. However, the SCL-BPC algorithm incurs additional decoding complexity and results in uneven decoding times. To address these issues, we investigate the matrix representation of the pre-transformation in deep polar codes and develop efficient implementation solutions for SCL-BPC decoding. Additionally, we introduce a low-complexity approach to SCL-BPC, which exhibits only a marginal reduction in performance.
This paper is concerned with a guessing codeword decoding (GCD) of linear block codes, which is optimal and typically requires a fewer number of searches than the naive exhaustive search decoding (ESD). Compared with the guessing random additive noise decoding (GRAND), which is only efficient for high-rate codes, the GCD is efficient for not only high-rate codes but also low-rate codes. We prove that the GCD typically requires a fewer number of queries than the GRAND. Compared with the conventional ordered statistics decoding (OSD), the GCD does not require the online Gaussian elimination (GE). In addition to limiting the maximum number of searches, we suggest limiting the radius of searches in terms of soft weights or tolerated performance loss to further reduce the decoding complexity, resulting in the so-called truncated GCD. The performance gap between the truncated GCD and the optimal decoding can be upper bounded approximately by the saddlepoint approach or other numerical approaches. The derived upper bound captures the relationship between the performance and the decoding parameters, enabling us to balance the performance and the complexity by optimizing the decoding parameters of the truncated GCD. We also introduce a parallel implementation of the (truncated) GCD algorithm to reduce decoding latency without compromising performance. Another contribution of this paper is the application of the GCD to the polar codes. We propose a multiple-bit-wise decoding algorithm over a pruned tree for the polar codes, referred to as the successive-cancellation list (SCL) decoding algorithm by GCD. First, we present a strategy for pruning the conventional polar decoding tree based on the complexity analysis rather than the specific bit patterns. Then we apply the GCD algorithm in parallel aided by the early stopping criteria to the leaves of the pruned tree. Simulation results show that, without any performance loss as justified by analysis, the proposed decoding algorithm can significantly reduce the decoding latency of the polar codes.
In the context of decoding binary linear block codes by polar code decoding techniques, we propose in this paper a new optimization of the serial nature of decoding the polar codes equivalent to binary linear block codes. In addition to the special nodes proposed by the simplified successive-cancellation list technique, we propose a new special node allowing to estimate in parallel the bits of its sub-code. The simulation is done in an additive white gaussian noise channel (AWGN) channel for several linear block codes, namely bose–chaudhuri–hocquenghem codes (BCH) codes, quadratic-residue (QR) codes, and linear block codes recently designed in the literature. The performance of the proposed technique offers the same performance in terms of frame error rate (FER) as the ordered statistics decoding (OSD) algorithm, which achieves that of maximum likelihood decoder (MLD), but with high memory requirements and computational complexity.
Non-binary linear block codes (NB-LBCs) are an important class of error-correcting codes that are especially competent in correcting burst errors. They have broad applications in modern communications and storage systems. However, efficient soft-decision decoding of these codes remains to be further developed. This paper proposes successive cancellation list (SCL) decoding for NB-LBCs that are defined over a finite field of characteristic two, i.e., F2r, whereris the extension degree. By establishing a one-to-r mapping between the binary composition of each non-binary codeword andrbinary polar codewords, SCL decoding of therpolar codes can be performed with a complexity that is sub-quadratic in the codeword length. A simplified path sorting is further proposed to facilitate the decoding. Simulation results on short-length extended Reed-Solomon (eRS) and non-binary extended BCH (NB-eBCH) codes show that SCL decoding can outperform their state-of-the-art soft-decision decoding with fewer finite field arithmetic operations. For length-16 eRS codes, their maximum-likelihood (ML) decoding performances can be approached with a moderate list size.