In this work, we present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distribution that arises in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, at code length n, we can compute the weight distribution of any polar cosets in time O(n^2). We show that any polar code can be represented as a disjoint union of such polar cosets; moreover, this representation extends to polar codes with dynamically frozen bits. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call the mixing factor. To upper bound the complexity of our algorithm for polar codes being decreasing monomial codes, we study the range of their mixing factors. We prove that among all decreasing monomial codes with rates at most 1/2, self-dual Reed-Muller codes have the largest mixing factors. To further reduce the complexity of our algorithm, we make use of the fact that, as decreasing monomial codes, polar codes have a large automorphism group. That automorphism group includes the block lower-triangular affine group (BLTA), which in turn contains the lower-triangular affine group (LTA). We prove that a subgroup of LTA acts transitively on certain subsets of decreasing monomial codes, thereby drastically reducing the number of polar cosets that we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of polar codes at length n = 128.
翻译:在这项工作中, 我们为计算极地代码的全部重量分布提供了一种确定性算法。 作为第一步, 我们得出一个高效的递归程序, 以计算在任何解码路径沿任何解码路径连续取消对极代码解码时产生的重量分布。 这解决了最近由 Polyanskaya、 Davletshin 和 Polyanskii 所构成的开放问题。 使用这个循环程序, 在代码长度 n 上, 我们可以用时间 O (n) 2 来计算任何极 Cots 的重量分布。 我们显示, 任何极地代码都可以作为这种极地直径数的脱节结合; 此外, 这个表达方式会扩展为动态冻结点的极地代码。 然而, 在这种代表尺度中, 极地的极地共集数会数以指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数指数的指数值会进一步降低, 我们使用极地极地极地平数的正数组的数值指数指数指数, 。