F 3 上极化码的核矩阵

2024-01-03李文慧高俊杰李秀丽

青岛科技大学学报（自然科学版） 2023年5期

李文慧, 高俊杰, 李秀丽

(青岛科技大学数理学院,山东青岛 266061)

极化码是近年来备受关注的一种纠错码,它在理论上可用于任何具有低复杂度的对称二进制离散无记忆信道[1]。极化码是目前唯一被严格证明能够达到信道容量的编码方式,这使得极化码与其他传统编码相比有较为明显的区别,可用于帮助证明许多理论问题,且极化码在无线通信中有广泛应用。文献[1]中的二进制极化码构造基于以下结论:设,对长度为N=2n比特的码块应用变换F⊗n(其中⊗n表示n次克罗内克幂),并通过BDMC信道的独立副本发送输出。随着n逐渐增大,单个比特对应的信道开始发生极化现象,一部分接近无噪声信道,另一部分接近全噪信道。KORADA 等[2]证明了极化是一种普遍现象,并不局限于特定的变换F⊗n。他们还考虑了G⊗n形式的变换,其中G是一个l×l矩阵,l≥3,并给出了B-DMC信道下该矩阵G能够极化的充要条,证明了任意列排列不是上三角的l×l二进制可逆矩阵都可以产生极化。MORI等[3]发现在域Fq上也有同样的结论。在文献[4]中,学者们研究了块长度为N=3n的二进制极化码核矩阵。本工作主要研究域F3上块长为N=3n的三进制极化码核矩阵。与F2上的同阶核矩阵相比,它产生的极化码具有更好的可靠性和极化率。本研究对三进制三阶核矩阵的构造原理及满足极化要求的核矩阵选取标准进行了阐述,给出了一种核矩阵的构造方法和最优核矩阵的选取标准,为高阶核矩阵的构造提供了研究思路。

1 信道极化

设W是一个q进制离散无记忆信道:X→Y,其中X=Fq。

定义1q进制输入信道W:X→Y对称容量为

定义2信道W的巴特查里亚参数(巴氏参数)为

这些参数分别用作速率和可靠性的度量[5]。I(W)是在信道W间进行可靠传输的最高速率。Z(W)是当信道W只被用于传输Fq中某一个元素时最大似然决策错误概率的上确界。上面的公式中使用底数为q的对数,因此I(W)和Z(W)的取值范围均为[0,1]。当W为对称信道时,对称容量I(W)等于Shannon容量[6]。

设G是取值于X的l×l矩阵。考虑一个在域上是均匀分布的随机l维向量,令=,其中乘法运算是在域Fq上进行的[7]。同样表示信道W的l次副本的输入所对应的输出。和之间的信道转移概率为

其中i=0,1,…,l-1。

W(i):X→Yl×Xi-1是输入ui,输出(,的信道,转移概率为

i=0,1,…,l-1。

设{Bi}(i=0,1,…)是一个独立随机变量,即对于任意k=0,…,l-1,Bi=k的概率为。存在一个随机量I∞,当n→∞时,绝对收敛于I∞。在映射G→VG下W(i)的统计性质是不变的,其中V是l×l满秩上三角矩阵。此外,矩阵G的列排列也不会改变W(i)的统计性质。任意满秩矩阵都可以分解成VLP的形式,其中V、L和P分别是上三角、下三角和置换矩阵。这种与可逆矩阵G等价的主对角线元素为单位的下三角矩阵被称为是G的标准形式,记为。在文献[3]中,作者证明了任意非对角下三角l×l矩阵,其P(I∞∈{0 ,1})=1。因此,任意列排列不是上三角的l×l三进制可逆矩阵都可以使信道发生极化。这些可以极化信道的l×l矩阵称为核矩阵。

定义3[5]给定域Fq上的一个l×l矩阵G=,Di(i=1,2,…,1)的定义为

其中＜gi+1,…,gl＞是由gi+1,…,gl生成的空间;dH(…,…)是指向量间的汉明距离。

定理1[8]设W是一个q进制输入离散无记忆信道。设P(I∞∈ {0 ,1})=1。对于β＜,

2 F 3 上核矩阵的选取

在以下的讨论中,假设q=3。W:X={0,1,2}→Y是一个对称三进制输入离散无记忆信道。

巴氏参数为

G是一个3×3核矩阵,那么3个三进制输入信道W(i):{0,1,2}→Y3×{0,1,2}i(i=0,1,2)的转移概率如下:

对于任意给定的T-DMCW,可将(W,W,W)→(W(0),W(1),W(2))写成以突显字符串长度。更一般地说

其中i≥0。

根据文献[3,5],对于核矩阵G的选择有多种。显然不同的核矩阵会导致不同的性能,因此在有限的块长度条件下找到一种标准来设计一个好的核矩阵G是非常有必要的。以下讨论如何在所有可能的核矩阵中选择最优的核矩阵。

2.1 极化速率

根据文献[5],如果矩阵G的指数更大,则可以更快地完成信道极化,从而获得更好的性能。因此,如果想找到更好的块长度为N=3n的极化码,我们需要找到尽可能大的指数的矩阵。对于3×3核矩阵,指数最大可能为。

2.2 的可靠性

Z描述的是的可靠性,且每一个信息位仅由其对应的信道传输,因此Z直接决定了性能。核矩阵G决定了的递归公式,这启示尽可能选择一个可以提高的可靠性的矩阵。

定理2对任意的下三角核矩阵G,如果最后一行的非零元素数是m,则

证明首先考虑m=3的情况。xi是u0,u1,u2的函数,用gi(u0,u1,u2)或gi(xi)表示W(yi|xi),i=0,1,2。那么

因此

u0和g31(非零)取任意值,那么{u0,u0+g31},{u0,u0+2g31}和{u0+g31,u0+2g31}分别取值于{0,1},{0,2}和{1,2};u1和g32(非零)取任意值,那么{u1,u1+g32},{u1,u1+2g32}和{u1+g32,u1+2g32}分别取值于{0,1},{0,2}和{1,2};u0≠u0+g31,u0≠u0+2g31,u0+g31≠u0+2g31;u1≠u1+g32,u1≠u1+2g32,u1+g32≠u1+2g32。经过变换,得到

如果一个变量x在[0,1]中取值,与函数y=x和y=x2相比,y=x3的值最小。受此启发,因为所有的的取值范围为[0,1],选择最后一行有3个非零元素的矩阵G,对于每次递归,至少可以确保的会尽可能地小。这也是解决一些优化问题常用的方法。由此,可以得到最优核矩阵的选取标准为

1) 矩阵的标准形式为下三角矩阵。

2) 最后一行均为非0元素。

矩阵G的标准形式为,因为的最后一行均为1,所以矩阵G满足上述两条可以使得三进制输入信道极化的标准。