IEEE Transactions on Information Theory
PED: A Method to Determine the Weight Distribution of Polar Codes With Arbitrary Binary Kernel
Ying Liu, Bolin Wu, Yuxin Han, Kai Niu
Abstract
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.