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:2601.07515 · IEEE International Symposium on Information Theory (ISIT)

A Parity-Consistent Decomposition Method for the Weight Distribution of Pre-Transformed Polar Codes

Yang Liu, Bolin Wu, Yuxin Han, Kai Niu

Published Jun 1, 2026• 0 citations
arXivHTMLPDF

Abstract

This paper introduces an efficient algorithm based on the Parity-Consistent Decomposition (PCD) method to determine the WD of pre-transformed polar codes. First, to address the bit dependencies introduced by the pre-transformation matrix, we propose an iterative algorithm to construct an \emph{Expanded Information Set}. By expanding the information bits within this set into 0s and 1s, we eliminate the correlations among information bits, thereby enabling the recursive calculation of the Hamming weight distribution using the \emph{PCD method}. Second, to further reduce computational complexity, we establish the theory of equivalence classes for pre-transformed polar codes. Codes within the same equivalence class share an identical weight distribution but correspond to different \emph{Expanded Information Set} sizes. By selecting the pre-transformation matrix that minimizes the \emph{Expanded Information Set} size within an equivalence class, we optimize the computation process. Numerical results demonstrate that the proposed method significantly reduces computational complexity compared to existing deterministic algorithms.

DOI
10.1109/isit62367.2026.11654040

Related papers

A Parity-Consistent Decomposition Method to Determine the Weight Distribution of Polar Codes

Ying Liu, Bolin Wu, Yuxin Han +1 more

This paper introduces a novel parity-consistent decomposition (PCD) method for accurately determining the weight distribution (WD) of polar codes. In the PCD method, polar codes are represented as a union of a new type of polar cosets, characterized by the property that any two adjacent bits in the uncoded sequence are either both information bits or both frozen bits. This representation reduces the number of polar cosets compared to the existing automorphism-based (AUT) method. We introduce a recursive decomposition method for this new polar coset, which facilitates efficient recursive computation of the WD of polar codes. The PCD method is organized within a tree structure, which facilitates the evaluation of its computational complexity. We then investigate the transitivity of the action of lower triangular affine (LTA) transformations on a code set composed of the new polar cosets. This transitivity property enables a further reduction in the number of cosets that need to be computed. Furthermore, we propose a pruning algorithm to determine the partial weight distribution (PWD) of polar codes based on the tree structure of the PCD method. Given an upper bound on the Hamming weight for the PWD, we update the Hamming weight threshold for each code in the tree and remove the codes whose minimum Hamming weights exceed their corresponding thresholds. Numerical results demonstrate the superiority of the PCD method over existing methods.

IEEE Transactions on Communications•Jan 1, 2026•1 citation

A Parity-Consistent Decomposition Algorithm to Determine the Weight Distribution of Polar Codes

Yang Liu, Bolin Wu, Yuxin Han +1 more

This paper introduces a novel parity-consistent decomposition (PCD) algorithm for accurately determining the weight distribution (WD) of polar codes. In the PCD algorithm, polar codes are represented as a union of a new type of polar cosets, which avoids fixing two adjacent information bits as 0 and 1. This representation reduces the number of polar cosets compared to the existing automorphism-based algorithm. Furthermore, we introduce a recursive decomposition method for this new polar coset, which facilitates efficient recursive computation of the WD of polar codes. The PCD algorithm is organized within a tree-like structure, which facilitates the evaluation of its computational complexity. Comparative analysis with the automorphism-based method demonstrates that the PCD algorithm significantly reduces computational complexity.

IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•3 citations

PED: A Method to Determine the Weight Distribution of Polar Codes With Arbitrary Binary Kernel

Ying Liu, Bolin Wu, Yuxin Han +1 more

This paper introduces a permutation-enumerationdecomposition (PED) method for accurately determining the weight distribution (WD) of polar codes with an arbitrary binaryl×lkernel. In the PED method, the indices in the information and frozen sets of a polar code are permuted to reduce a complexity-determining parameter λ calledMixed Exponent. Subsequently, the enumeration of specific information bits over {0, 1} represents the polar code as a union of disjoint cosets. Each coset is further represented as a direct sum oflcomponent codes, which corresponds to the decomposition process. Moreover, the obtained component codes are operated in the same manner. Based on this structure, the WD of the original polar code is recursively obtained from the WDs of cosets and component codes by summation and convolution operations, respectively. Analytically, we demonstrate that the PED method achieves an exponential complexity reduction compared to the brute-force search method, with the upper-bounded reduction rate asymptotically dominated byK−λ/Kl2−(1−1/l)(K−λ)as λ decreases, whereKdenotes the cardinality of the information set. Furthermore, we apply the PED method in two settings. For polar codes with Arıkan’s 2×2 kernel, we prove that permuting the binary expansions of the indices does not reduce λ for decreasing monomial codes, which allows the permutation step to be omitted. Beyond this special case, we apply the PED method to polar-spectrum computation for general binaryl×lkernels, where the polar spectrum is used for bit-channel reliability estimation under successive cancellation (SC) decoding. At each recursive step, the enumerated cosets can be grouped into at mostl+ 1 distinct coset WD types. Asn= loglNtends to infinity, the multiplicative increase in the derived complexity upper bound whennis increased by one converges to (l+ 1)2.

IEEE Transactions on Information Theory•Jan 1, 2026•0 citations

Computing the Low-Weight codewords of Punctured and Shortened Pre-Transformed Polar Codes

Malek Ellouze, Romain Tajan, Camille Leroux +2 more

In this paper, we present a deterministic algorithm to count the low-weight codewords of punctured and shortened pure and pre-transformed polar codes. The method first evaluates the weight properties of punctured/shortened polar cosets. Then, a method that discards the cosets that have no impact on the computation of the low-weight codewords is introduced. A key advantage of this method is its applicability, regardless of the frozen bit set, puncturing/shortening pattern, or pre-transformation. Results confirm the method’s efficiency while showing reduced computational complexity compared to state-of-the-art algorithms.

arXiv:2411.05433•International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•4 citations

Computing the Partial Weight Distribution of Punctured, Shortened, Precoded Polar Codes

Vera Miloslavskaya, Branka S. Vucetic, Yonghui Li

The problem of computing the Hamming weight distribution of linear codes is considered in this paper. A novel method to enumerate all codewords up to a certain Hamming weight for binary linear block codes in general and in particular for the punctured, shortened, precoded polar codes is introduced. The proposed approach performs a recursive decomposition of the codes using construction X4 that is typically used to combine codes of different lengths. This allows to enumerate the low-weight codewords of the overall code as combinations of the low-weight codewords of the component codes. Numerical results show that the proposed approach can efficiently compute the exact partial weight distribution of the 5G New Radio punctured/shortened polar codes with CRC11 and pure polar codes. In the former and latter cases, the low-weight codeword number is up to 106 and 108, respectively. Besides, randomly punctured and shortened polar codes and randomly precoded polar codes are also considered. To the best of the authors’ knowledge, this is the first method able to solve these problems.

IEEE Transactions on Communications•Sep 12, 2022•21 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
This paper introduces an efficient algorithm based on the Parity-Consistent Decomposition (PCD) method to determine the WD of pre-transformed polar codes. First, to address the bit dependencies introduced by the pre-transformation matrix, we propose an iterative algorithm to construct an \emph{Expanded Information Set}. By expanding the information bits within this set into 0s and 1s, we eliminate the correlations among information bits, thereby enabling the recursive calculation of the Hamming weight distribution using the \emph{PCD method}. Second, to further reduce computational complexity, we establish the theory of equivalence classes for pre-transformed polar codes. Codes within the same equivalence class share an identical weight distribution but correspond to different \emph{Expanded Information Set} sizes. By selecting the pre-transformation matrix that minimizes the \emph{Expanded Information Set} size within an equivalence class, we optimize the computation process. Numerical results demonstrate that the proposed method significantly reduces computational complexity compared to existing deterministic algorithms.
This paper introduces a novel parity-consistent decomposition (PCD) method for accurately determining the weight distribution (WD) of polar codes. In the PCD method, polar codes are represented as a union of a new type of polar cosets, characterized by the property that any two adjacent bits in the uncoded sequence are either both information bits or both frozen bits. This representation reduces the number of polar cosets compared to the existing automorphism-based (AUT) method. We introduce a recursive decomposition method for this new polar coset, which facilitates efficient recursive computation of the WD of polar codes. The PCD method is organized within a tree structure, which facilitates the evaluation of its computational complexity. We then investigate the transitivity of the action of lower triangular affine (LTA) transformations on a code set composed of the new polar cosets. This transitivity property enables a further reduction in the number of cosets that need to be computed. Furthermore, we propose a pruning algorithm to determine the partial weight distribution (PWD) of polar codes based on the tree structure of the PCD method. Given an upper bound on the Hamming weight for the PWD, we update the Hamming weight threshold for each code in the tree and remove the codes whose minimum Hamming weights exceed their corresponding thresholds. Numerical results demonstrate the superiority of the PCD method over existing methods.
This paper introduces a novel parity-consistent decomposition (PCD) algorithm for accurately determining the weight distribution (WD) of polar codes. In the PCD algorithm, polar codes are represented as a union of a new type of polar cosets, which avoids fixing two adjacent information bits as 0 and 1. This representation reduces the number of polar cosets compared to the existing automorphism-based algorithm. Furthermore, we introduce a recursive decomposition method for this new polar coset, which facilitates efficient recursive computation of the WD of polar codes. The PCD algorithm is organized within a tree-like structure, which facilitates the evaluation of its computational complexity. Comparative analysis with the automorphism-based method demonstrates that the PCD algorithm significantly reduces computational complexity.
This paper introduces a permutation-enumerationdecomposition (PED) method for accurately determining the weight distribution (WD) of polar codes with an arbitrary binaryl×lkernel. In the PED method, the indices in the information and frozen sets of a polar code are permuted to reduce a complexity-determining parameter λ calledMixed Exponent. Subsequently, the enumeration of specific information bits over {0, 1} represents the polar code as a union of disjoint cosets. Each coset is further represented as a direct sum oflcomponent codes, which corresponds to the decomposition process. Moreover, the obtained component codes are operated in the same manner. Based on this structure, the WD of the original polar code is recursively obtained from the WDs of cosets and component codes by summation and convolution operations, respectively. Analytically, we demonstrate that the PED method achieves an exponential complexity reduction compared to the brute-force search method, with the upper-bounded reduction rate asymptotically dominated byK−λ/Kl2−(1−1/l)(K−λ)as λ decreases, whereKdenotes the cardinality of the information set. Furthermore, we apply the PED method in two settings. For polar codes with Arıkan’s 2×2 kernel, we prove that permuting the binary expansions of the indices does not reduce λ for decreasing monomial codes, which allows the permutation step to be omitted. Beyond this special case, we apply the PED method to polar-spectrum computation for general binaryl×lkernels, where the polar spectrum is used for bit-channel reliability estimation under successive cancellation (SC) decoding. At each recursive step, the enumerated cosets can be grouped into at mostl+ 1 distinct coset WD types. Asn= loglNtends to infinity, the multiplicative increase in the derived complexity upper bound whennis increased by one converges to (l+ 1)2.
In this paper, we present a deterministic algorithm to count the low-weight codewords of punctured and shortened pure and pre-transformed polar codes. The method first evaluates the weight properties of punctured/shortened polar cosets. Then, a method that discards the cosets that have no impact on the computation of the low-weight codewords is introduced. A key advantage of this method is its applicability, regardless of the frozen bit set, puncturing/shortening pattern, or pre-transformation. Results confirm the method’s efficiency while showing reduced computational complexity compared to state-of-the-art algorithms.
The problem of computing the Hamming weight distribution of linear codes is considered in this paper. A novel method to enumerate all codewords up to a certain Hamming weight for binary linear block codes in general and in particular for the punctured, shortened, precoded polar codes is introduced. The proposed approach performs a recursive decomposition of the codes using construction X4 that is typically used to combine codes of different lengths. This allows to enumerate the low-weight codewords of the overall code as combinations of the low-weight codewords of the component codes. Numerical results show that the proposed approach can efficiently compute the exact partial weight distribution of the 5G New Radio punctured/shortened polar codes with CRC11 and pure polar codes. In the former and latter cases, the low-weight codeword number is up to 106 and 108, respectively. Besides, randomly punctured and shortened polar codes and randomly precoded polar codes are also considered. To the best of the authors’ knowledge, this is the first method able to solve these problems.
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.