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

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.