太原理工大学，数学学院，山西 晋中

收稿日期：2022年2月9日；录用日期：2022年3月3日；发布日期：2022年3月10日

摘要

Polar码的优势和局限性都在于其严格的结构。Polar码常用的信息位选择方式为根据串行抵消(SC)译码算法中的信道可靠度进行选择，但是这样的选择方法不适用所有的情况。在基于SC译码算法的基础上改进的列表(SCL)译码算法中，选择信息位需要考虑码重量谱和可靠度，得到的性能较好。目前，已经有很多通过改善码谱进而改善性能的方法了。为了去寻找一种通用的改善码谱的方法，我们需要刻画原码重量谱的分布规则，探索在不同情形下选择信息位的方法。在本文中，提出了一种新的行表示方法，在此基础上验证了码谱唯一的信息集的数量范围，引入容斥原理推出二元域下码重的通用公式。

关键词

Polar码，RM码，码重量谱，信息集，容斥原理

A Verification of Polar Code Weight Spectrum

Yujie Qiao, Weihua Yang

School of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi

Received: Feb. 9^th, 2022; accepted: Mar. 3^rd, 2022; published: Mar. 10^th, 2022

ABSTRACT

The advantages and disadvantages of Polar codes lie in its strict structure. At present, the existing information set selection method is based on the reliability of Successive Cancellation (SC) decoding algorithm, which may not be suitable for other algorithms. Improved SCL (SC List) decoding based on SC decoding needs to consider reliability and code weight spectrum. Various methods to improve the spectrum have been proposed and achieved better performance. In order to find a good way to improve the spectrum, we characterize the distribution law of weight spectrum and try to find suitable information set selection methods in different situations. In this paper, a new row representation method is proposed. On this basis, the number range of the information set of the unique code spectrum is verified, and the general formula of code weight in the binary field is derived by introducing the principle of tolerance and exclusion.

Keywords:Polar Codes, RM Codes, Code Weight Spectrum, Information Set, The Principle of Tolerance and Exclusion

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

E Arikan [1] 在2009年发现并分析了信道联合和信道极化的现象，并据此提出了Polar码和其使用的SC译码算法。Polar码在编码理论中作为容量可达的码字是一个很大的突破。在5G通信网络中，Polar码在短码长度的应用范围上可以代替LDPC码。Tae和A. Vardy [2] 针对Polar码的SC译码算法引入列表辅助验证，提出了SCL译码算法改善性能，并且该算法的性能在列表较大的时候可以达到最大似然(ML)译码性能。Li B [3] 提出了一类新的混合码字“RM-Polar”码。这类码字通过混合RM码和Polar码构造而成，其最小汉明距离比Polar码的最小汉明距离大，因此性能要优于Polar码。为了提升Polar码的最小距离，建议使用RM-Polar码或者将Polar码与CRC [4] 和PC [5] 串联以显著提高性能。最近，E. Arikan [6] 提出了一类新的PAC Polar码，通过在RM码之前进行卷积运算，可以提供比以前的纠错码更好的性能。Li B [7] 简单证明了预变换Polar码的最小距离不会变小，并且提出了一种通过分类和总结级联码的特性来设计上三角预变换的构造方法。2016年， [8] 提出，Polar码和RM码是很相近的，因为它们具有相同的代数结构，也就是说，他们可以组合单项式构成。特别的，这种构造提供了一种有效的方法去计算递减单项式码和Polar码的最小码字的数量。通过在Polar码编码器的中间的阶中加入交织器 [9]，Chiu M C [10] 提出了一类新的Polar 码——交织Polar码(I-Polar码)。假设交织器是均匀分布的，他们衍生出重量枚举函数(WEF)来计算从I-Polar码集中随机选择的码的误块率(BLER)的上限。在 [11] 中，他们修正了之前关于Polar码的信息位的选择方式，并且提出了基于可靠度和和行重选择的方法。通过阅读大量文献，我们发现了很多改善Polar码和RM码码谱的方法。这些方法没有改变信息位的选择，而且易于实现。

2. 预备知识

2.1. Polar码

n阶Polar码由生成矩阵 $G^{\otimes n}$ 构成，其中二元核矩阵定义为

$G=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$

n表示n阶克罗内克积。该Polar码的码长为 $N=2^n$ 并且包含K个信息比特。

码字由 $x=G^{\otimes n}Bu$ 得到，其中 $u={\left\{u_1,u_2,\cdots ,u_n\right\}}^{\text{T}}$，$s={\left\{s_1,s_2,\cdots ,s_n\right\}}^{\text{T}}$ 分别表示输入的信息序列和输出

的码字序列。B表示比特逆序排列操作。由于Polar码的特殊结构，其可以使用SC译码器来进行编译码操作，复杂度为 $\text{O}\left(N{\log }_{2}N\right)$。随着码长N趋于无穷时，Polar码可以达到信道容量 [1]。

u中的N个比特可以根据它们在信道中的可靠度分为两组，K个最可靠的比特被看作信息比特用来传递信息，剩余的 $N-K$ 个比特作为冻结比特被设置为固定值，该固定值在编译码器两端均已知。我们用 $\mathbb{K}$ 和 $\bar{\mathbb{K}}$ 表示u的子集，分别包含对应信息比特和冻结比特的位置索引值。可靠度序列可以通过下列方法获得，比如，巴氏参数 [1]，密度进化 [12]，高斯近似 [13]，遗传算法 [14]，beta扩展 [15] 和深度学习 [16]。

2.2. RM码

RM码(Reed Muller)，码长为 $N=2^m$，包含 $K={\displaystyle {\sum }_{i=1}^r{C}_m^r}$ 个信息比特，最小距离为 $d=2^{m-r}$。RM码的K个信息比特是根据矩阵 $G^{\otimes m}$ 中行的重量由大到小选取的，并且将重量为 $2^{m-r}$ 的行全部选入信息集。行重最大的对应的K个比特作为信息比特，剩余的作为冻结比特，固定值为“0”。我们用 $\mathcal{R}\left(m,r\right)$ 表示RM码，汉明距离d，最小汉明距离 $d_{\min }$。

2.3. 行的表示方法

假设一个Polar码的码长为 $N=2^m,\left(m\ge 1\right)$，我们将会得到一个明确的矩阵。通过 [1] 的比特索引法，可以得出一个长度为 $N=2^m$ 的向量 $a_1^N$。我们将其第i个元素表示为 $a_{b_1{b}_2\cdots b_m}$，其中 $1\le i\le N$，$b_1{b}_2\cdots b_m$ 是整数 $i-1$ 的二元表示。也就是说， $i=1+{\displaystyle {\sum }_{j=1}^m{b}_j{2}^{m-j}}$，可以看作是行的另一种表示。同样的，一个 $N\times N$ 的矩阵A中的元素 $A_{ij}$ 可以表示为 $A_{b_1{b}_2\cdots b_m,{b^{\prime }}_1{b^{\prime }}_2\cdots {b^{\prime }}_m}$，其中， $b_1{b}_2\cdots b_m,{b^{\prime }}_1{b^{\prime }}_2\cdots {b^{\prime }}_m$ 分别是 $i-1$ 和 $j-1$ 的二元表示。然后，就可以得到 $G^{\otimes m}$ 中的元素为 $G_{b_1{b}_2\cdots b_m,{b^{\prime }}_1{b^{\prime }}_2\cdots {b^{\prime }}_m}^{\otimes m}={\displaystyle {\prod }_{i=1}^m{G}_{b_i{b^{\prime }}_i}}={\displaystyle {\prod }_{i=1}^m\left(1\oplus {b^{\prime }}_i\oplus b_i{b^{\prime }}_i\right)}$。

基于上述的分析，我们提出了一个新的行表示，关于行号i与行中“1”的位置索引值集合的双射如下：

$f\left(i\right)=\left(\begin{array}{cccc}1& & & \\ 1+2^{b_1}& & & \\ 1+2^{b_2}& 1+2^{b_1}+2^{b_2}& & \\ 1+2^{b_3}& 1+2^{b_1}+2^{b_3}& 1+2^{b_2}+2^{b_3}& 1+2^{b_1}+2^{b_2}+2^{b_3}\\ ⋮& ⋮& ⋮& ⋮\end{array}\right)$

等号左侧的i为行号，等号右侧的集合是矩阵 $G^{\otimes m}$ 第i行中“1”的位置索引值。例如，矩阵中的最后一行(全“1”行)的行号为 $i=1+{\displaystyle {\sum }_{j=1}^m{b}_j{2}^{m-j}}$，则 $f\left(i\right)$ 包含所有的列索引值。在剩余的行中，重量为 $w=2^{m-1}$ 的行的二元表示与全“1”行相比缺失了一项，也就是说，对应的 $f\left(i\right)$ 中的元素不包含缺失的项。我们将每一个 $f\left(i\right)$ 都看作一个事件。

为了方便理解，让我们通过以下例子来解释。

例： $m=4$，

行号16， $i=1+2^0+2^1+2^2+2^3,w=2^m=16$

$f\left(i\right)=\left(\begin{array}{cccc}1& & & \\ 1+2^0& & & \\ 1+2^1& 1+2^0+2^1& & \\ 1+2^2& 1+2^0+2^2& 1+2^1+2^2& 1+2^0+2^1+2^2\\ 1+2^3& 1+2^0+2^3& 1+2^1+2^3& 1+2^0+2^1+2^3\\ 1+2^2+2^3& 1+2^0+2^2+2^3& 1+2^1+2^2+2^3& 1+2^0+2^1+2^2+2^3\end{array}\right)$

行号15， $i=1+2^1+2^2+2^3,w=2^{m-1}=8$

$f\left(i\right)=\left(\begin{array}{cccc}1& & & \\ ~& & & \\ 1+2^1& ~& & \\ 1+2^2& ~& 1+2^1+2^2& ~\\ 1+2^3& ~& 1+2^1+2^3& ~\\ 1+2^2+2^3& ~& 1+2^1+2^2+2^3& ~\end{array}\right)$

行号14， $i=1+2^0+2^2+2^3,w=2^{m-1}=8$

$f\left(i\right)=\left(\begin{array}{cccc}1& & & \\ 1+2^0& & & \\ ~& ~& & \\ 1+2^2& 1+2^0+2^2& ~& ~\\ 1+2^3& 1+2^0+2^3& ~& ~\\ 1+2^2+2^3& 1+2^0+2^2+2^3& ~& ~\end{array}\right)$

$\cdots$

我们可以按行重将矩阵中所有的行分为以下几组，每组中的元素都是行重固定的长度为m的行的二元表示。 $C_m^i$ 表示每一组元素的数量，w表示对应的行重。

$\begin{array}{cccccc}{C}_m^m,w=2^m& C_m^{m-1},w=2^{m-1}& C_m^{m-2},w=2^{m-2}& & C_m^1,w=2^1& C_m^0,w=2^0\\ & & & & & \\ & \left(0,1,1,\cdots ,1,1,1\right)& \left(0,0,1,\cdots ,1,1,1\right)& & \left(1,0,0,\cdots ,0,0,0\right)& \\ \left(1,1,1,\cdots ,1,1,1\right)& \left(1,0,1,\cdots ,1,1,1\right)& \left(0,1,0,\cdots ,1,1,1\right)& & \left(0,1,0,\cdots ,0,0,0\right)& \left(0,0,0,\cdots ,0,0,0\right)\\ & \left(1,1,0,\cdots ,1,1,1\right)& \left(1,0,0,\cdots ,1,1,1\right)& \cdots & \left(0,0,1,\cdots ,0,0,0\right)& \\ & ⋮& ⋮& & ⋮& \\ & \left(1,1,1,\cdots ,1,1,0\right)& \left(1,1,1,\cdots ,1,0,0\right)& & \left(0,0,0,\cdots ,0,0,1\right)& \end{array}$

3. 码谱分析

由假设Polar码码长为 $2^m$，包含K个信息比特，是根据行重从大到小选取的。在K确定之后，如果满足 $K={\displaystyle {\sum }_{i=0}^s{C}_m^i},s\in \left(1,2,\cdots ,m\right)$，码谱与RM码相同且信息位的选择是唯一的。如果不满足 $K={\displaystyle {\sum }_{i=0}^s{C}_m^i},s\in \left(1,2,\cdots ,m\right)$，信息位的选择不唯一。那么不同的信息集产生的码谱有什么规律吗？

基于仿真结果，我们可以得到以下定理。

定理3.1：码长为 $2^m$ 的Polar码若选用RM码选择信息位的方式，则当K的范围满足 $K\in \left\{0,1,\cdots ,C_m^0+C_m^1+1\right\}\cup \left\{{\displaystyle {\sum }_{i=0}^{i=m-2}{C}_m^i-1},\cdots ,{\displaystyle {\sum }_{i=0}^{i=m}{C}_m^i}\right\}\cup \left\{{\displaystyle {\sum }_{i=0}^j{C}_m^i\pm 1}|j=1,2,\cdots ,m\right\}$ 时，可以得到唯一的重量谱。

证明：假设我们按照RM码的方法选择信息位，也就是说，根据行重从大到小(分组中从左到右)。

如果K满足 $K={\displaystyle {\sum }_{i=0}^s{C}_m^i},s\in \left(1,2,\cdots ,m\right)$，码谱和信息位的选择都是唯一的，与RM码相同。在其他情况下，

K个信息位的选择方式是不唯一的。因为会出现在相同重量的组中只选取一部分行作为信息位。我们可以定义从这个组取出的元素数量为 $K_1$，这些元素进行线性组合时的系数为“1”的数量为s，码字的重量为 $w_s$，重量为 $w_s$ 的码字数量为 $N_s$。首先，我们刻画同组内的线性组合的情况。

1) 当 $w=2^{m-1},0\le K_1\le C_m^{m-1}$ 时，

$s=1,w_1=2^{m-1},N_1=C_{K_1}^1$

$s=2,w_2=w_1+2^{m-1}-2\ast \left(\frac{w_1}{2}\right)=2^{m-1},N_2=C_{K_1}^2$

$s=3,w_3=w_2+2^{m-1}-2\ast \left(\frac{w_2}{2}\right)=2^{m-1},N_3=C_{K_1}^3$

$⋮$

$s=K_1,w_{K_1}=w_{K_1-1}+2^{m-1}-2\ast \left(\frac{w_{K_1-1}}{2}\right)=2^{m-1},N_{K_1}=C_{K_1}^{K_1}$

2) 当 $w=2^{m-2},0\le K_1\le C_m^{m-2}$ 时，

$s=1,w_1=2^{m-2},N_1=C_{K_1}^1$

$s=2,w_2=\{\begin{array}{ll}2\ast 2^{m-2}-2\ast 2^{m-4}\hfill & 缺失的项完全不同\hfill \\ 2\ast 2^{m-2}-2\ast 2^{m-3}\hfill & 缺失的项有两项相同\hfill \end{array}$

$s=3,w_3=\{\begin{array}{ll}7\ast 2^{m-4}\hfill & 缺失的项完全不同\hfill \\ 3\ast 2^{m-3}\hfill & 缺失的项有两项相同\hfill \\ 2^{m-1}\hfill & 缺失的项有三项相同\hfill \\ 3\ast 2^{m-3}\hfill & 缺失的项有四项相同\hfill \end{array}$

$⋮$

m) 当 $w=2^{m-\left(m-1\right)}=2,0\le K_1\le C_m^1$ 时，

$s=1,w_1=2^1,N_1=C_{K_1}^1$

$s=2,w_2=w_1+2^1-2\ast \left(\frac{w_1}{2}\right)=2,N_2=C_{K_1}^2$

$s=3,w_3=w_2+2^1=4,N_3=C_{K_1}^3$

$⋮$

$s=2i-1,w_{2i-1}=2i,N_{2i-1}=C_{K_1}^{2i-1}$

$s=2i,w_{2i}=2i,N_{2i}=C_{K_1}^{2i}$

$s=2i+1,w_{2i+1}=2i+2,N_{2i}=C_{K_1}^{2i+1}$

$⋮$

$s=K_1,w_{K_1}=\{\begin{array}{ll}{K}_1\hfill & s是偶数\hfill \\ K_1+1\hfill & s是奇数\hfill \end{array}$

接下来，我们刻画不同组之间的线性组合的情况。我们首先解释说明 $K\in \left\{0,1,\cdots ,C_m^0+C_m^1+1\right\}$ 的情况。

因为选择方法的要求，全“1”行一定会被选入信息集的K行中。

情况1：对于 $K=C_m^0$ 和 $K=C_m^0+C_m^1$，信息集的选择方式唯一，码重量谱自然唯一。

情况2：对于 $C_m^0+1\le K\le C_m^0+C_m^1$，$w=2^{m-1}$ 组中有 $C_m^1$ 行，其中的 $K-1$ 行被选择。与全“1”行相比

较，被选择的行的二元表示均缺少一项。我们可以得知被选择的K行的线性组合满足：

$w=\{\begin{array}{cc}{2}^{m-1}& 如果全“1”行的系数为“1”\\ 2^{m-1}& 如果全“1”行的系数为“1”\end{array}$

在这个情形下，所得到的码字重量是相同的。在上述两种情况下，该重量所对应的数量是相同的，均为 $C_m^{K-1}$。如果K值确定，码谱唯一。

情况3：对于 $K=C_m^0+C_m^1+1$，在 $K=C_m^0+C_m^1$ 的基础上，要从重量为 $w=2^{m-2}$ 的组中取出一行，有 $C_{C_m^2}^1$ 种取法。与全“1”行相比，被选择的行的二元表示缺失两项，这样的行有 $C_m^2$ 个。我们可以这样考虑：

首先我们固定之前的线性组合，将其看作一个码字，然后将这样的码字按照是否与新选择的行具有相同的缺失项分类。

$w=\{\begin{array}{l}\begin{array}{ll}{2}^{m-1}\hfill & 如果固定的码字缺失一项，且缺失项与选择的行的缺失项完全不同\hfill \\ 2^{m-2}\hfill & 如果固定的码字缺失一项，且缺失项与选择的行的缺失项有一项相同\hfill \\ 5\ast 2^{m-3}\hfill & 如果固定的码字缺失两项，且缺失项与选择的行的缺失项完全不同\hfill \\ 2^{m-1}\hfill & 如果固定的码字缺失两项，且缺失项与选择的行的缺失项有一项相同\hfill \\ 3\ast 2^{m-2}\hfill & 如果固定的码字缺失两项，且缺失项与选择的行的缺失项完全相同\hfill \end{array}\\ ⋮\end{array}$

很明显，因为组合排列的随机性，会出现新的重量的码字。通过行的二元表示的规则，我们可以知道从 $w=2^{m-2}$ 组中选择的每一行都会出现上述的情况。所以在这样的情况下，同样会出现这样重量的码字。最终，将会获得一个唯一的码谱。

情况4：对于 $K=C_m^0+C_m^1+2$，也就是，在情况3的基础上再从 $w=2^{m-2}$ 中再选取一行。此时，我们从(2)中得知，从 $w=2^{m-2}$ 中选取的两行会根据彼此之间的关系将会形成不同的重量和码谱。同理，如果从该组中抽取更多的行，将会出现更多的组合和不同的码谱。

情况5：对于 $K={\displaystyle {\sum }_{i=0}^{i=m-2}{C}_m^i-1}$，我们可以在 ${\displaystyle {\sum }_{i=0}^{i=m-2}{C}_m^i}$ 得到唯一码谱的基础上考虑。因为二元域的计算特性(假设 $A,B$ 都是二元码字，则 $A-B=A+B$ )，该情况等同于在 $K={\displaystyle {\sum }_{i=0}^{i=m-2}{C}_m^i}$ 的情况下从 $w=2^2$ 组

中选择一行相加，即等效于情况3，最终得到一个唯一的码谱。

情况6：同理可得， $K=\left\{{\displaystyle {\sum }_{i=0}^j{C}_m^i}\pm 1|j=1,2,\cdots ,m\right\}$ 和 ${\displaystyle {\sum }_{i=0}^{i=m-2}{C}_m^i}-1\le K\le {\displaystyle {\sum }_{i=0}^{i=m}{C}_m^i}$ 的情况可以按照排列

组合和重量分布的对称性解释。

定理成立。

上述方法只能列出一些简单情况，我们可以应用组合数学中的容斥原理及其推论来刻画一般情况，见图1。

定理3.2：(容斥原理) 假设S是一个有限集， $A_i\subseteq S\left(i=1,2,\cdots ,n,n\ge 2\right)$，则

$\begin{array}{c}\left|{\displaystyle \underset{i=1}{\overset{n}{\cup }}{A}_i}\right|=\underset{1\le i_1\le n}{{\displaystyle \sum }}\left|A_{i_1}\right|-\underset{1\le i_1<i_2\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\right|+\cdots \\ +{\left(-1\right)}^{k-1}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|+\cdots +{\left(-1\right)}^{n-1}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_n}\right|\\ ={\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(-1\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|\end{array}$

推论3.3：假设S是一个有限集， $A_i\subseteq S\left(i=1,2,\cdots ,n,n\ge 2\right)$，则

$\left|S-{\displaystyle \underset{i=1}{\overset{n}{\cup }}{A}_i}\right|=\left|S\right|+{\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(-1\right)}^k}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|$

定理3.4：假设S是一个有限集， $a_1,a_2,\cdots ,a_n$ 是n条性质。对于任意 $k\left(1\le k\le n\right)$ 个正整数， $i_1,i_2,\cdots ,i_k,\left(1\le i_1<i_2<\cdots <i_k\le n\right)$，以 $N\left(a_{i_1},a_{i_2},\cdots ,a_{i_k}\right)$ 表示S中同时具有性质 $a_{i_1},a_{i_2},\cdots ,a_{i_k}$ 的元素个数，以 $N\left({a^{\prime }}_{i_1}{a^{\prime }}_{i_2},\cdots ,{a^{\prime }}_{i_n}\right)$ 表示S中不具有 $a_{i_1},a_{i_2},\cdots ,a_{i_n}$ 中任一个性质的元素个数，则

$N\left({a^{\prime }}_{i_1},{a^{\prime }}_{i_2},\cdots ,{a^{\prime }}_{i_k}\right)=\left|S\right|+{\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(-1\right)}^k}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}N\left(a_{i_1},a_{i_2},\cdots ,a_{i_k}\right)$

我们将上述定理应用到二元域 $F_2$ 上，得到一个新的定理。在 $F_2$ 上，偶数次重复的部分被消除，奇数次重复的部分被保留一份。我们将每一个事件 $f\left(i\right)$ 记为 $A_i$。

图1. 容斥原理例图

定理3.5：假设S是二元域上的一个有限集， $A_i\subseteq S\left(i=1,2,\cdots ,n,n\ge 2\right)$，则

$\begin{array}{c}\left|{\displaystyle \underset{i=1}{\overset{n}{\cup }}{A}_i}\right|=\underset{1\le i_1\le n}{{\displaystyle \sum }}\left|A_{i_1}\right|-2\underset{1\le i_1<i_2\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\right|+4\underset{1\le i_1<i_2<i_3\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap A_{i_3}\right|\\ -8\underset{1\le i_1<i_2<i_3<i_4\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap A_{i_4}\right|+\cdots \\ +{\left(-1\right)}^{k-1}{2}^{k-1}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|+\cdots \\ +{\left(-1\right)}^{n-1}{2}^{n-1}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_n}\right|\\ ={\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(-2\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|\end{array}$

证明：当 $n=2$ 时，

$\left|{\displaystyle \underset{i=1}{\overset{2}{\cup }}{A}_i}\right|=\left|A_1\right|+\left|A_2\right|-2\left|A_1\cap A_2\right|$

当 $n=3$ 时，

$\begin{array}{c}\left|{\displaystyle \underset{i=1}{\overset{3}{\cup }}{A}_i}\right|=\left|\left({\displaystyle \underset{i=1}{\overset{2}{\cup }}{A}_i}\right)\cup A_3\right|=\left|{\displaystyle \underset{i=1}{\overset{2}{\cup }}{A}_i}\right|+\left|A_3\right|-2\left|\left({\displaystyle \underset{i=1}{\overset{2}{\cup }}{A}_i}\right)\cap A_3\right|\\ =\left|A_1\right|+\left|A_2\right|-2\left|A_1\cap A_2\right|+\left|A_3\right|-2\left|\left(\left|A_1\right|+\left|A_2\right|-2\left|A_1\cap A_2\right|\right)\cap A_3\right|\\ =\left|A_1\right|+\left|A_2\right|+\left|A_3\right|-2\left|A_1\cap A_2\right|-2\left|A_1\cap A_3\right|-2\left|A_2\cap A_3\right|+4\left|A_1\cap A_2\cap A_3\right|\\ =\underset{1\le i_1\le n}{{\displaystyle \sum }}\left|A_{i_1}\right|-2\underset{1\le i_1<i_2\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\right|+4\underset{1\le i_1<i_2<i_3\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap A_{i_3}\right|\end{array}$

假设当 $n=s\left(s\ge 3\right)$ 时，该结论成立。

那么当 $n=s+1$ 时，

$\begin{array}{c}\left|{\displaystyle \underset{i=1}{\overset{s+1}{\cup }}{A}_i}\right|=\left|\left({\displaystyle \underset{i=1}{\overset{s}{\cup }}{A}_i}\right)\cup A_{s+1}\right|=\left|{\displaystyle \underset{i=1}{\overset{s}{\cup }}{A}_i}\right|+\left|A_{s+1}\right|-2\left|\left({\displaystyle \underset{i=1}{\overset{s}{\cup }}{A}_i}\right)\cap A_{s+1}\right|\\ =\underset{1\le i_1\le s+1}{{\displaystyle \sum }}\left|A_{i_1}\right|+{\displaystyle \underset{k=2}{\overset{s}{\sum }}{\left(-2\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_k\le s}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|\\ +{\displaystyle \underset{k=1}{\overset{s-1}{\sum }}{\left(-2\right)}^k}\underset{1\le i_1<i_2<\cdots <i_k\le s}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\cap A_{s+1}\right|\\ +{\left(-2\right)}^s\left|A_1\cap A_2\cap \cdots \cap A_s\cap A_{s+1}\right|\end{array}$

$\begin{array}{c}=\underset{1\le i_1\le s+1}{{\displaystyle \sum }}\left|A_{i_1}\right|+[{\displaystyle \underset{k=2}{\overset{s}{\sum }}{\left(-2\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_k\le s}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|\\ +{\displaystyle \underset{k=2}{\overset{s}{\sum }}{\left(-2\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_{k-1}\le s}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\cap A_{s+1}\right|]\\ +{\left(-2\right)}^s\left|A_1\cap A_2\cap \cdots \cap A_s\cap A_{s+1}\right|\end{array}$

$\begin{array}{c}=\underset{1\le i_1\le s+1}{{\displaystyle \sum }}\left|A_{i_1}\right|+{\displaystyle \underset{k=2}{\overset{s}{\sum }}{\left(-2\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_k\le s+1}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|\\ +{\left(-2\right)}^s\left|A_1\cap A_2\cap \cdots \cap A_s\cap A_{s+1}\right|\\ ={\displaystyle \underset{k=1}{\overset{s+1}{\sum }}{\left(-2\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_k\le s+1}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|\\ ={\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(-2\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|\end{array}$

综上所述，定理成立 $\left(n\ge 2\right)$。

推论3.6：假设S是二元域上的一个有限集， $a_1,a_2,\cdots ,a_n$ 是n条性质。对于任意 $k\left(1\le k\le n\right)$ 个正整数， $i_1,i_2,\cdots ,i_k,\left(1\le i_1<i_2<\cdots <i_k\le n\right)$，以 $N\left(a_{i_1},a_{i_2},\cdots ,a_{i_k}\right)$ 表示S中同时具有性质 $a_{i_1},a_{i_2},\cdots ,a_{i_k}$ 的元素个数，以 $N\left({a^{\prime }}_{i_1},{a^{\prime }}_{i_2},\cdots ,{a^{\prime }}_{i_n}\right)$ 表示S中不具有 $a_{i_1},a_{i_2},\cdots ,a_{i_n}$ 中任一个性质的元素个数，则

$N\left({a^{\prime }}_{i_1},{a^{\prime }}_{i_2},\cdots ,{a^{\prime }}_{i_k}\right)=\left|S\right|+{\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(-2\right)}^k}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}N\left(a_{i_1},a_{i_2},\cdots ,a_{i_k}\right)$

证明：我们将 $A_i\left(i=1,2,\cdots ,n\right)$ 看作S中具有性质 $a_i$ 的全部元素所成之集，则 $S-{\displaystyle {\sum }_{i=1}^n{A}_i}$ 表示S中不具有 $a_1,a_2,\cdots ,a_n$ 中任一个性质的全部元素所成之集，所以

$N\left({a^{\prime }}_{i_1},{a^{\prime }}_{i_2},\cdots ,{a^{\prime }}_{i_k}\right)=\left|S-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{A}_i}\right|=\left|S\right|+{\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(-2\right)}^{k-1}}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|$

因为 $A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}$ 表示S中同时具有性质 $a_1,a_2,\cdots ,a_n$ 的全部元素所成之集，所以 $A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}=N\left(a_{i_1},a_{i_2},\cdots ,a_{i_k}\right)$，从而

$N\left({a^{\prime }}_{i_1},{a^{\prime }}_{i_2},\cdots ,{a^{\prime }}_{i_k}\right)=\left|S\right|+{\displaystyle \underset{k=1}{\overset{n}{\sum }}{\left(-2\right)}^k}\underset{1\le i_1<i_2<\cdots <i_k\le n}{{\displaystyle \sum }}N\left(a_{i_1},a_{i_2},\cdots ,a_{i_k}\right)$

综上所述，定理成立。

这里，我们认为更好的码谱是具有更少的最小距离码字数量。那么当信息集选择不唯一的时候，什么样的信息集选择方式可以有更好的码谱呢？

通过上述定理3.5和3.6，我们可以得到可能出现的码字重量及其补集。如果我们想要得到更好的码谱，我们需要选择在相同事件的条件下具有最小重量码字的数量较少的情况。也就是说，我们需要将定理3.5的结果进行量化，选择最小重量最少的情况所对应的选择方式。

通过图1，如果想要码字的最小距离最大，即使得重复奇数次的部分尽可能大，重复偶数次的部分

尽可能小。让我们定义一个函数为 $F={\displaystyle {\sum }_{t=1}^{t=s}f\left(i_t\right)}$ 作为线性组合的结果。在 $F_2$ 中，出现偶数次的项被消除，

出现奇数次的项被保留一次。虽然不甚准确，但是可以用它来衡量得到的码字重量。因此F中的项越多，说明这样组合后得到的码字重量越大，即所选择的行的二元表示尽可能不同。虽然没有给出具体的结果，但逻辑具有一定的意义，因此该衡量函数将在后续工作中进行实验。

4. 总结与展望

在本文中，我们已经刻画了原Polar码的重量谱分布规则，给出了一些结构化改善的想法。目前大部分的码谱优化方法也可以从这个角度进行分析。已经证明PAC-Polar码的结构和在阶之间添加交织器可以改善码谱。我们可以利用F函数的计算结果来分析优化后的结果，甚至可以根据一些已知的结果来预测哪个交织器可以获得更好的码谱。我们也可以根据定理3.5设计阶之间的交织器。通过定理3.5得到某些码字的具体形式，然后通过交织器将其他码字的“1”置于已知码字的“0”位置，得到一个更大权重的码字。我们可以使用一个符合条件的线性组合以获得更好的码谱的方法，想一想，有没有可能基于这个想法来设计动态交织器？

例如Polar码的生成矩阵可以表示为：

$G=\left[\begin{array}{cc}{G}_1& \\ G_2& G_2\end{array}\right]$

其中 $G_1=G_2$。

因为信息集的不同选择方式，我们定义 $G$ 构成的码字 $c_0$ 重量为 $d$，$G_1$ 构成的码字 $c_1$ 重量为 $d_1$，$G_2$ 构成的码字 $c_2$ 重量为 $d_2$，$c_1$ 和 $c_2$ 中共同为“1”的位置的数量为c。如果我们想要在 $G_1$ 中设计一个交织器，我们需要将 $c_1$ 中的“1”尽可能放置在 $c_2$ 中“0”的位置上， $c_1$ 中多余的“1”可以随机放置在 $c_2$ 中“0”的位置上。然后原始重量为 $d_1+2d_2-2c$ 的码字，现在重量为 $d_1+2d_2-2\left(d_1+d_2-2^{m-1}\right)=2^m-d_1$，即这是可能达到的最大重量。

文章引用

乔玉洁,杨卫华. 关于Polar码重量谱的一个验证
A Verification of Polar Code Weight Spectrum[J]. 应用数学进展, 2022, 11(03): 956-965. https://doi.org/10.12677/AAM.2022.113102

参考文献