非平稳信道下极化码的评估
达芳+方勇
摘 要: 极化码是基于信道极化现象的一种新的信道编码方法。直到现在,许多研究极化码的学者仍致力于在平稳信道下对极化码进行应用研究。在此,主要研究将极化码应用于非平稳信道,此研究需要利用蒙特卡洛方法来进行。将一个特殊二进制对称信道(BSC)的交叉概率的变化视为服从正弦函数分布。根据大量的实验结果发现,当极化码应用于非平稳信道下时,仍然存在信道极化现象,但是其极化现象并没有像极化码应用于平稳信道那样的显著。
关键词: 信道极化; 极化码; 非平稳信道; 蒙特卡洛方法
中图分类号: TN711?34; TN911.2 文献标识码: A 文章编号: 1004?373X(2017)14?0001?04
Abstract: The polarization code is a new channel coding method based on the phenomenon of channel polarization. Up to now, most of researches on polarization code are devoted to the applications of polarization codes in stationary channels. In this paper, the research on polarization codes is applied to nonstationary channels, in which Monte Carlo method should be used for it. The variation of crossover probability of the special binary symmetric channel (BSC) is regarded as the sine function distribution. According to numerous experimental results, it is found that the phenomenon of channel polarization still exists when polarization codes are applied to nonstationary channels, but the polarization phenomenon is not so obvious as that when polarization codes are applied to stationary channels.
Keywords: channel polarization; polarization code; nonstationary channel; Monte Carlo method
0 引 言
在通信理论中,传统的编码问题可以被分为两大类,即信道编码与信源编码。信道编码,可以提高信号传输的可靠性,这对于信息论领域来说是十分重要的[1]。信道码可以大致分为随机码和结构码。Turbo码 [2]和低密度奇偶校验码[3](LDPC)是两种代表性的随机码,并长时间对结构码造成压倒性的优势。然而在2008年,E.Arikan提出一种新的构造码:极化码,并且证明了它可以近乎达到香农极限[4]。从那时起,极化码和其他构造码又重新成为了热门话题。自从极化码的出现,一些学者将极化码应用于联合信源信道编码[5],分布式信源编码[6]和级联极化码[7]。尽管Arikan提出了利用计巴氏系数来进行递归计算[4],但是它的应用范围是非常狭窄的。在2010年,Mori将极化码由二维信道拓展到了多维信道[8],这使得极化码有了更广阔的应用领域。然而,研究学者们主要将注意力集中在了平稳信道下的极化码。事实上,非平稳信道则是更常见的,因其信道特性是不稳定的甚至是波动的。自然,会猜想在非平稳信道下,极化现象是否还能存在,这显然是一个极具意义的挑战。因为非平稳信道在人类社会生活中更加普遍并且难以规律掌控,研究在非平稳信道下的极化码有利于今后极化码更普遍地应用于生活多方面。通过大量的实验发现,当极化码应用于非平稳信道时,确实存在信道极化现象。本文主要给出实验和数据说明,对极化码译码做出改进,对信道容量计算方法进行改进。
1 背景回顾
1.1 信道极化
信道组合过程与信道拆分过程是基于链式法则的[1]。信道组合过程是通过特定的方法将N个二进制离散无记忆信道(B?DMC)W整合为一个独立的N维矢量信道。信道拆分过程是将组合的矢量信道拆分为一组相关的N个信道。根据这个原理,E.Arikan提出一种构造信道极化使用方法,此方法正是由信道组合与信道拆分组成,并且在信道容量方面可以达到无损。
1.2 极化码
极化现象是用来构造极化码从而可以达到对称信道容量I(W)。极化码的编码原理是建立一个系统通过分离的信道来分别传递每一个二进制输入。然而,只有接近于1的信道来传递有用的信息。
每一个二进制输入向量都将编码为码字。再将码字送入一组非平稳信道,其交叉概率为。在极化码译码过程中,将改变4个不同的参数来观察其极化现象。连续删除译码(SC)器是利用和来得到的估计。如果,意味着发生了译码错误。在估计完成后,误码率(BER)可以被计算出来。
2 非平稳信道下的极化码译码
2.1 非平稳对称信道
如图1所示,两种概率将被进行测试,N?1 024和N?4 096),重复次数设置为1 024次。非平稳信道BSC的信道容量可以由平穩信道BSC推出:
式中,为每个符号的误码率。
实验步骤总结如下:
(1) 随机生成信源序列。
(2) 编码为码字,将码字送入非平稳信道BSC,其交叉概率为。
(3) 利用SC算法来译码得到输出。与通常的极化码译码算法的不同之处是估计时假设均是已知的。
(4) 对估计进行多次试验,目的是通过比较与来得到误码率。根据BER,利用式(1)来计算非平稳信道下的信道容量。这种方法称为蒙特卡洛方法。
2.2 实验方法
蒙特卡洛方法也称为随机仿真方法,根据重复随机抽样来得到数值结果。众所周知,对于普遍的B?DMC信道,是没有有效的算法来计算的。因此,蒙特卡洛方法则被认为是一种最合适的方法。设送入似然比(LR)递归第一层的值为初始参数,将蒙特卡洛方法应用于非平稳信道是为了获得BER,然而,由于不同的初始参数,BER的值可能會不同。初始参数的值分别设定为,其中。
SC译码器由N个决策元素(DEs)组成,其决策元素是从1~N进行激活的。LR递归的计算也是从1~N进行的,易得出。当给定原始值与不同概率值时,该决策将会定义为:
3 非平稳信道下极化码的应用
信道极化现象是一部分信道容量趋近于1而另一部分趋近于0。当块的长度增大时,信道极化现象越明显。在此,需要提前做一些准备工作。表示随机变量概率密度函数,则的熵定义为。BSC的信息容量为。紧接着,需要计算每个参数的熵值与信息容量值。对于,计算结果见表1。
对于,计算结果见表2。
3.1 平稳信道下码的性能
BEC信道下的极化现象如图2(a)所示,其删除概率,所有的可以通过式(4)计算得出[3]。由于有效的递归使得BEC是一个很合适的信道来构造极化码,但其递归公式只适用于BEC。本文实验中,的递归计算公式如下:
由于在BSC信道下没有有效的算法,因此在BSC信道下选用蒙特卡洛方法来构造极化码,如图2(b)所示。
3.2 非平稳信道下码的性能
将非平稳信道设置为BSC而不是BEC,是因为变化的交叉概率在递归关系中并不适用。已知BEC信道存在递归关系来构造极化码,因此将非平稳信道设置为BSC,且利用蒙特卡洛随机仿真方法来构造非平稳信道下的极化码是正确的。如图3、图4所示,在非平稳BSC下,极化现象仍然存在。值得注意的是在不同的信道或不同的码字长度下,极化图像均是不同的。从图2与图3中可以看出在平稳信道下的极化现象比在非平稳信道下的极化现象更加显著。从图像的角度出发,平稳信道中大量的点都趋近于0或1,中间的点较少,即极化程度比非平稳信道下较高。
4 实验比较
比较BEC与非平稳信道下极化码的构造情况,在非平稳BSC下,对于较小的值,更趋近于0,对于较大的值,更趋近于1,这一点与在BEC信道下是相同的。对处于中间值的,的值是振荡的,并且在非平稳信道下,中间点的值更加扩散,点数目也更多。另外,BEC信道下极化图像是中心对称的,而非平稳信道下的极化图像并无此特征,但平稳信道BSC下的极化图像也无此特征,这是由于BSC信道特征采取的不同方法所决定的。
同样,对比平稳BSC信道与非平稳BSC信道,图2与图3有许多相同之处,原因是他们运用相同的处理方法。但是平稳BSC信道极化现象仍然比非平稳信道显著。非平稳信道下的点更加散乱。由于不同信道下的处理方法不同,会导致极化码信道容量不同,则最后极化现象就会有差别。在BEC信道下,极化码的构造是通过严格的递归公式,而BSC信道下是利用不断随机仿真试验来获得BER,从而计算信道容量。根据图3~图5,可以计算出信道容量所占区间的比率,容量趋近于1与趋近于0的结果如表3~表5所示。
表3~表5可以作为一种在非平稳信道下的极化现象的评估指标,可以根据其容量比率来判断极化程度。极化码出现的一个重大意义是利用其无损信道来传输有用信息,因此,评估极化性能时会根据这一指标进行。如结果所示,不同的初始参数也会导致不同程度的极化现象,当交叉概率越大,图像中更多的点趋近于0,反之,则更趋近于1。
在实验中,4个初始参数作为LR第一层迭代所需的参数,根据表格易得,当初始参数为和时,具有相似的结果,更重要的是,在初始参数为和时,极化现象更加规则、明显。再比较图3与图5,当N越大时,极化现象越明显,这与文献[4]具有相同的结论。
5 结 语
在现实生活中的信道通常是非平稳的,而极化码的基本原则意味着极化码应当可以被应用于各种信道。本文就是基于这一点来展开的。总体来说,能得出结论极化码与极化现象在非平稳信道下是可行的。本文利用实验证明了极化现象在非平稳信道下是仍然存在的,只是极化现象并没有在平稳信道下那样显著。另外,实验结果也表明了当极化码应用于非平稳信道时,可以通过改变修正译码参数来提高信道极化程度。在此之后,极化码在非平稳信道下的一些其他研究工作可以更加顺利的展开。
参考文献
[1] 科弗,托马斯.信息论基础[M].2版.北京:机械工业出版社,2014:114?116.
[2] ANDREI M, TRIFINA L, TARNICERIU D. Influence of trellis termination methods on turbo code performances [C]// 2013 4th International Symposium on Electrical and Electronics Engineering. [S.l.]: IEEE, 2013: 1?6.
[3] BANDI S, TRALLI V, CONTI A, et al. On girth conditioning for low?density parity?check codes [J]. IEEE transactions on communications, 2011, 59(2): 357?362.
[4] ARIKAN E. Channel polarization: A method for constructing capacity?achieving codes for symmetric binary?input memoryless channels [J]. IEEE transaction on information theory, 2008, 55(7): 3051?3073.
[5] HUSSAMI N, KORADA S B, URBANKE R. Performance of polar codes for channel and source coding [C]// IEEE International Symposium on Information Theory. [S.l.]: IEEE, 2009: 1488?1492.
[6] ONAY S. Polar codes for distributed source coding [J]. Electronics letters, 2013, 49(5): 346?348.
[7] TRIFONOV P, SEMENOV P. Generalized concatenated codes based on polar codes [C]// 8th International Symposium on Wireless Communication System. [S.l.] : ISWCS, 2011: 442?446.
[8] MORI R, TANAKA T. Non?binary polar codes using Reed?Solomon codes and algebraic geometry codes [J]. Information theory workshop, 2010, 23 (3): 1?5.
[9] FANG Yong. LDPC?based lossless compression of nonstationary binary sources using sliding?window belief propagation [J]. IEEE Transactions on Communication, 2012, 60(11): 3161?3166.
摘 要: 极化码是基于信道极化现象的一种新的信道编码方法。直到现在,许多研究极化码的学者仍致力于在平稳信道下对极化码进行应用研究。在此,主要研究将极化码应用于非平稳信道,此研究需要利用蒙特卡洛方法来进行。将一个特殊二进制对称信道(BSC)的交叉概率的变化视为服从正弦函数分布。根据大量的实验结果发现,当极化码应用于非平稳信道下时,仍然存在信道极化现象,但是其极化现象并没有像极化码应用于平稳信道那样的显著。
关键词: 信道极化; 极化码; 非平稳信道; 蒙特卡洛方法
中图分类号: TN711?34; TN911.2 文献标识码: A 文章编号: 1004?373X(2017)14?0001?04
Abstract: The polarization code is a new channel coding method based on the phenomenon of channel polarization. Up to now, most of researches on polarization code are devoted to the applications of polarization codes in stationary channels. In this paper, the research on polarization codes is applied to nonstationary channels, in which Monte Carlo method should be used for it. The variation of crossover probability of the special binary symmetric channel (BSC) is regarded as the sine function distribution. According to numerous experimental results, it is found that the phenomenon of channel polarization still exists when polarization codes are applied to nonstationary channels, but the polarization phenomenon is not so obvious as that when polarization codes are applied to stationary channels.
Keywords: channel polarization; polarization code; nonstationary channel; Monte Carlo method
0 引 言
在通信理论中,传统的编码问题可以被分为两大类,即信道编码与信源编码。信道编码,可以提高信号传输的可靠性,这对于信息论领域来说是十分重要的[1]。信道码可以大致分为随机码和结构码。Turbo码 [2]和低密度奇偶校验码[3](LDPC)是两种代表性的随机码,并长时间对结构码造成压倒性的优势。然而在2008年,E.Arikan提出一种新的构造码:极化码,并且证明了它可以近乎达到香农极限[4]。从那时起,极化码和其他构造码又重新成为了热门话题。自从极化码的出现,一些学者将极化码应用于联合信源信道编码[5],分布式信源编码[6]和级联极化码[7]。尽管Arikan提出了利用计巴氏系数来进行递归计算[4],但是它的应用范围是非常狭窄的。在2010年,Mori将极化码由二维信道拓展到了多维信道[8],这使得极化码有了更广阔的应用领域。然而,研究学者们主要将注意力集中在了平稳信道下的极化码。事实上,非平稳信道则是更常见的,因其信道特性是不稳定的甚至是波动的。自然,会猜想在非平稳信道下,极化现象是否还能存在,这显然是一个极具意义的挑战。因为非平稳信道在人类社会生活中更加普遍并且难以规律掌控,研究在非平稳信道下的极化码有利于今后极化码更普遍地应用于生活多方面。通过大量的实验发现,当极化码应用于非平稳信道时,确实存在信道极化现象。本文主要给出实验和数据说明,对极化码译码做出改进,对信道容量计算方法进行改进。
1 背景回顾
1.1 信道极化
信道组合过程与信道拆分过程是基于链式法则的[1]。信道组合过程是通过特定的方法将N个二进制离散无记忆信道(B?DMC)W整合为一个独立的N维矢量信道。信道拆分过程是将组合的矢量信道拆分为一组相关的N个信道。根据这个原理,E.Arikan提出一种构造信道极化使用方法,此方法正是由信道组合与信道拆分组成,并且在信道容量方面可以达到无损。
1.2 极化码
极化现象是用来构造极化码从而可以达到对称信道容量I(W)。极化码的编码原理是建立一个系统通过分离的信道来分别传递每一个二进制输入。然而,只有接近于1的信道来传递有用的信息。
每一个二进制输入向量都将编码为码字。再将码字送入一组非平稳信道,其交叉概率为。在极化码译码过程中,将改变4个不同的参数来观察其极化现象。连续删除译码(SC)器是利用和来得到的估计。如果,意味着发生了译码错误。在估计完成后,误码率(BER)可以被计算出来。
2 非平稳信道下的极化码译码
2.1 非平稳对称信道
如图1所示,两种概率将被进行测试,N?1 024和N?4 096),重复次数设置为1 024次。非平稳信道BSC的信道容量可以由平穩信道BSC推出:
式中,为每个符号的误码率。
实验步骤总结如下:
(1) 随机生成信源序列。
(2) 编码为码字,将码字送入非平稳信道BSC,其交叉概率为。
(3) 利用SC算法来译码得到输出。与通常的极化码译码算法的不同之处是估计时假设均是已知的。
(4) 对估计进行多次试验,目的是通过比较与来得到误码率。根据BER,利用式(1)来计算非平稳信道下的信道容量。这种方法称为蒙特卡洛方法。
2.2 实验方法
蒙特卡洛方法也称为随机仿真方法,根据重复随机抽样来得到数值结果。众所周知,对于普遍的B?DMC信道,是没有有效的算法来计算的。因此,蒙特卡洛方法则被认为是一种最合适的方法。设送入似然比(LR)递归第一层的值为初始参数,将蒙特卡洛方法应用于非平稳信道是为了获得BER,然而,由于不同的初始参数,BER的值可能會不同。初始参数的值分别设定为,其中。
SC译码器由N个决策元素(DEs)组成,其决策元素是从1~N进行激活的。LR递归的计算也是从1~N进行的,易得出。当给定原始值与不同概率值时,该决策将会定义为:
3 非平稳信道下极化码的应用
信道极化现象是一部分信道容量趋近于1而另一部分趋近于0。当块的长度增大时,信道极化现象越明显。在此,需要提前做一些准备工作。表示随机变量概率密度函数,则的熵定义为。BSC的信息容量为。紧接着,需要计算每个参数的熵值与信息容量值。对于,计算结果见表1。
对于,计算结果见表2。
3.1 平稳信道下码的性能
BEC信道下的极化现象如图2(a)所示,其删除概率,所有的可以通过式(4)计算得出[3]。由于有效的递归使得BEC是一个很合适的信道来构造极化码,但其递归公式只适用于BEC。本文实验中,的递归计算公式如下:
由于在BSC信道下没有有效的算法,因此在BSC信道下选用蒙特卡洛方法来构造极化码,如图2(b)所示。
3.2 非平稳信道下码的性能
将非平稳信道设置为BSC而不是BEC,是因为变化的交叉概率在递归关系中并不适用。已知BEC信道存在递归关系来构造极化码,因此将非平稳信道设置为BSC,且利用蒙特卡洛随机仿真方法来构造非平稳信道下的极化码是正确的。如图3、图4所示,在非平稳BSC下,极化现象仍然存在。值得注意的是在不同的信道或不同的码字长度下,极化图像均是不同的。从图2与图3中可以看出在平稳信道下的极化现象比在非平稳信道下的极化现象更加显著。从图像的角度出发,平稳信道中大量的点都趋近于0或1,中间的点较少,即极化程度比非平稳信道下较高。
4 实验比较
比较BEC与非平稳信道下极化码的构造情况,在非平稳BSC下,对于较小的值,更趋近于0,对于较大的值,更趋近于1,这一点与在BEC信道下是相同的。对处于中间值的,的值是振荡的,并且在非平稳信道下,中间点的值更加扩散,点数目也更多。另外,BEC信道下极化图像是中心对称的,而非平稳信道下的极化图像并无此特征,但平稳信道BSC下的极化图像也无此特征,这是由于BSC信道特征采取的不同方法所决定的。
同样,对比平稳BSC信道与非平稳BSC信道,图2与图3有许多相同之处,原因是他们运用相同的处理方法。但是平稳BSC信道极化现象仍然比非平稳信道显著。非平稳信道下的点更加散乱。由于不同信道下的处理方法不同,会导致极化码信道容量不同,则最后极化现象就会有差别。在BEC信道下,极化码的构造是通过严格的递归公式,而BSC信道下是利用不断随机仿真试验来获得BER,从而计算信道容量。根据图3~图5,可以计算出信道容量所占区间的比率,容量趋近于1与趋近于0的结果如表3~表5所示。
表3~表5可以作为一种在非平稳信道下的极化现象的评估指标,可以根据其容量比率来判断极化程度。极化码出现的一个重大意义是利用其无损信道来传输有用信息,因此,评估极化性能时会根据这一指标进行。如结果所示,不同的初始参数也会导致不同程度的极化现象,当交叉概率越大,图像中更多的点趋近于0,反之,则更趋近于1。
在实验中,4个初始参数作为LR第一层迭代所需的参数,根据表格易得,当初始参数为和时,具有相似的结果,更重要的是,在初始参数为和时,极化现象更加规则、明显。再比较图3与图5,当N越大时,极化现象越明显,这与文献[4]具有相同的结论。
5 结 语
在现实生活中的信道通常是非平稳的,而极化码的基本原则意味着极化码应当可以被应用于各种信道。本文就是基于这一点来展开的。总体来说,能得出结论极化码与极化现象在非平稳信道下是可行的。本文利用实验证明了极化现象在非平稳信道下是仍然存在的,只是极化现象并没有在平稳信道下那样显著。另外,实验结果也表明了当极化码应用于非平稳信道时,可以通过改变修正译码参数来提高信道极化程度。在此之后,极化码在非平稳信道下的一些其他研究工作可以更加顺利的展开。
参考文献
[1] 科弗,托马斯.信息论基础[M].2版.北京:机械工业出版社,2014:114?116.
[2] ANDREI M, TRIFINA L, TARNICERIU D. Influence of trellis termination methods on turbo code performances [C]// 2013 4th International Symposium on Electrical and Electronics Engineering. [S.l.]: IEEE, 2013: 1?6.
[3] BANDI S, TRALLI V, CONTI A, et al. On girth conditioning for low?density parity?check codes [J]. IEEE transactions on communications, 2011, 59(2): 357?362.
[4] ARIKAN E. Channel polarization: A method for constructing capacity?achieving codes for symmetric binary?input memoryless channels [J]. IEEE transaction on information theory, 2008, 55(7): 3051?3073.
[5] HUSSAMI N, KORADA S B, URBANKE R. Performance of polar codes for channel and source coding [C]// IEEE International Symposium on Information Theory. [S.l.]: IEEE, 2009: 1488?1492.
[6] ONAY S. Polar codes for distributed source coding [J]. Electronics letters, 2013, 49(5): 346?348.
[7] TRIFONOV P, SEMENOV P. Generalized concatenated codes based on polar codes [C]// 8th International Symposium on Wireless Communication System. [S.l.] : ISWCS, 2011: 442?446.
[8] MORI R, TANAKA T. Non?binary polar codes using Reed?Solomon codes and algebraic geometry codes [J]. Information theory workshop, 2010, 23 (3): 1?5.
[9] FANG Yong. LDPC?based lossless compression of nonstationary binary sources using sliding?window belief propagation [J]. IEEE Transactions on Communication, 2012, 60(11): 3161?3166.