A Deterministic Algorithm for Computing the Weight Distribution of Polar Codes
A Deterministic Algorithm for Computing the Weight Distribution of Polar Codes
复制标题
DOI：
10.1109/isit45174.2021.9517950
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Hanwen Yao;Arman Fazeli;A. Vardy
中科院分区：
文献类型：
--
作者：
Hanwen Yao;Arman Fazeli;A. Vardy
我们提出了一种确定性算法来计算极性码的整个重量分布。第一步，我们推导了一个有效的递归过程来计算极性码沿着任何解码路径的连续抵消解码中出现的权重分布，这解决了Polyanskaya，Davletshin和Polyanskii最近提出的公开问题。使用这个递归过程，我们可以计算某些极陪集的整个重量分布在时间$O（n^{2}）$。任何极化码都可以表示为这种陪集的不相交并集;此外，这种表示扩展到具有动态冻结比特的极化码。这意味着我们的方法也可以用于计算具有CRC预编码的极化码、极化调整卷积（PAC）码以及实际上一般线性码的权重分布。然而，这种表示中的极陪集的数量与本文引入的参数呈指数关系，我们称之为混合因子。为了降低我们算法的指数复杂度，我们利用极化码具有大的自同构群的事实，该自同构群包括下三角仿射群LTA $（m，2）$。我们证明了LTA $（m，2）$在极化码的某些子集上具有传递性，从而大大减少了我们需要评估的极化陪集的数量。这种复杂度降低使得可以计算长度高达$n=128$的任何极化码的权重分布。
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 distributions that arise 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, we can compute the entire weight distribution of certain polar cosets in time $O(n^{2})$. Any polar code can be represented as a disjoint union of such cosets; moreover, this representation extends to polar codes with dynamically frozen bits. This implies that our methods can be also used to compute the weight distribution of polar codes with CRC precoding, of pol-arization-adjusted convolutional (PAC) codes and, in fact, general linear codes. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call the mixing factor. To reduce the exponential complexity of our algorithm, we make use of the fact that polar codes have a large automorphism group, which includes the lower-triangular affine group LTA $(m,2)$. We prove that LTA $(m,2)$ acts transitively on certain subsets of polar codes, thereby drastically reducing the number of polar cosets we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of any polar code of length up to $n=128$.