2013年第09期，第46卷 通 信 技 术 Vol.46，No.09,2013 总第261期 Communications Technology No.261,Totally
doi:10.3969/j.issn.1002-0802.2013.09.008
张涛涛﹡﹡， 蒋宇中， 梁 振
（海军工程大学，湖北武汉 430033）
【摘要】在通信系统中，为了保证通信系统的可靠性，克服信道中的噪声和干扰，需要引入信道编码。当利用计算机搜索到大约束长度的卷积码生成多项式，为了剔除搜索到的恶性卷积码生成多项式，必须对搜索到的生成多项式进行检验。判定一个编码器的生成多项式是否是恶性的方法是数学推导和Matlab 计算。然而这些方法只适合约束长度较短的卷积码，而当约束长度较大时，运用现有的计算手段很难对编码器生成多项式进行检验。提出了一种基于卷积码自身状态特性的适用于并行就算的检验算法，实验表明该算法可在很大程度上提高检验的效率，有很大的实用价值。 【关键词】卷积码；恶码检验；并行计算
【中图分类号】TN911.22 【文献标识码】A 【文章编号】1002-0802(2013)09-0026-03
Malicious Code Inspection Algorithm for Parallel-Computing
Convolution Code
ZHANG Tao-tao， JIANG Yu-zhong， LIANG Zhen
(Navy Engineering University, Wuhan Hubei 430033, China)
【Abstract】In order to ensure the reliability of communication system and overcome the noise and interference, channel coding is introduced in communication system. With computer to search the convolution code generator polynomial of long constraint length, the searched convolutional code generator polynomial must be tested, thus to remove the malignant polynomial. The mathematical and Matlab methods are used to determine whether the encoder generator polynomial is malicious or not. However, these methods are only suitable for the short constraint length convolutional code, whereas when the constraint length is longer, the existing computing means is hard to test the generator polynomial of the encoder. This paper proposes a parallel computing inspection algorithm based on the features of convolutional code itself. The experiment result shows that the proposed algorithm could greatly improve the inspection efficiency, and is thus of great practical value.
【Key words】convolution code; mailcious code inspection; parallel computation
0 引言
1955年Elias最早提出了不同于分组码的卷积码。如果卷积码的约束长度越长则其性能越好，然而到目前为止，在寻大长度的好卷积码方面取得的进展非常少[1]。大部分性能较好的卷积码都是通过计算机搜索得到的，对于卷积码来说，很难到类似于线性分组码BCH码那样能够保证好的距离特性的代数结构。一种有效的搜索大约束长度卷积码编码器的算法由Bahl，Cullum,Frazer和Jelinek提出，并由Larsen修改[2]。
卷积码是由连续输入的信息序列得到连续输出的编码序列。一个（n，k，v）卷积编码器，其中k 为编码器输入数据的位数，n为编码器输出数据的位数，v表示约束长度，R=k/n表示编码速率（码率），它是衡量卷积码传输信息有效性的一个重要指标。为了达到一定的纠错能力和编码效率，分组码的码组长度一般比较大。编译码时必须把整个信息码组存储起来，由此产生的译码延迟会随着n的增加而
﹡收稿日期：2013-04-23；修回日期：2013-08-19。﹡﹡通讯作者：******************。
26
27
增加。卷积码把k 个信息bit 编成n 个信息bit ，但k 和n 通常都很小，延时也较小，因此特别适合于传
输串行形式的信息。编码后的n 个码元不但与当前段的k 个信息有关，而且与前面v 段的信息有关。由于卷积码在编码过程中，充分地利用了码组之间的相关性，且k 和n 都比较小，因此，在与分组码同样的码率和设备复杂度条件下，从理论和实际两个方面，均已证明卷积码的性能至少不比分组码差，且实现最佳和准最佳也较分组码容易。
由于大约束长度的卷积码在深太空通信、超低频通信领域有更加广泛的应用，急需到大约束长
度好的卷积码编码器[3-4]
。如果对信道进行编码的编码器是有恶性传播特性的卷积码多项式，则可能导致差错的传播，从而在对由恶性传播特性编码器所生成的码字进行译码时，则会导致误判。通过制定一些规则，利用卷积码的距离谱得到生成多项式。当利用计算机搜索到了大约束长度的卷积码编码器，迫切的需要对搜索到的编码器进行检验，剔除恶性卷积码编码器。
1 检验编码器生成多项式的数学方法
Massey 和Sain [5]
通过数学推导的方法验证卷积
码编码器是否是恶性的。对于一个(n ,1,v )卷积码编码
器，生成矩阵()D G 有前馈逆1()G D −，当且仅当
01(1)[(),()()]n l GCD g D g D g D D −⋅⋅⋅= （1）
对某个0l ≥成立，其中GCD 代表最大公因子。考虑如图1所示的卷积码编码器的生成矩阵 012
()[()()][11]D g D g D D D ==++G （2） 显然 2[()][11]1GCD G D GCD D D D =++=+ （3）
因而其前馈逆不存在。如果信息序列是()u D =
2111D D D
=++++ ，则输出序列是0
()1v D =和
1()1v D D =+，即使信息序列有无限重量，输出码
字重量为3。如果该码字在BSC 上传播，其中的三比
特的非零信息位由于受信道噪声干扰变为零，则接
收序列全是零。最大似然译码器则把码重为零码字
作为其估计，因为这是一个有效码字，并且正好和
接收序列相同。因此，估计的信息序列式
()0()v D D =，意味着有限数量（这里仅有三个）的
信道错误引起了无数的译码错误。明显地这是不希
望的，译码器遭受了恶性误码扩散，即它是一个恶
性编码器[6]
。因此，在选择编码器用于差错控制编
码系统时，避免选择恶性编码器是非常重要的。数
学推导的方法偏重于计算约束长度较小的卷积码编码器，然而当约束长度较大时，运用数学计算的方法显然是不可行的。
2 适用于检验卷积码生成多项式的并行计算方法
假定编码器的初始状态为0S (全零状态)，通过在状态图中沿着信息序列决定的路径且记录分支上的相应输出，可以得到对应于任何给定信息序列的码字。图1给出了约束长度为3，编码多项式为2()[11]G D D D =++的卷积码编码器的各状态之间的转换关系。
S0S1
S2
S3
S6
S7
S4S5
0/00
1/010/10
0/01
1/10
0/101/01
1/10
0/01
1/00
1/00
0/11
1/11
0/00
0/11
1/11
图1 (2,1,3)编码器的状态
一个编码器是恶性的，当且仅当状态图除了有一个围绕状态0S 的零重量圈之外，还包含一个零输出重量圈。图2所示(2,1,3)编码器的状态图中，我们
注意到，围绕状态7S 的单个分支圈有零重量输出[7]
。
现有的恶码检验方法是使用Matlab 方法。该方
法首先要构造出一种栅格型结构，这种栅格结构主要用于建立各种状态之间的转换关系，实际上就是
一个矩阵，将所有的关系在矩阵中表示出来。这样
做的好处是可以根据当前的状态以及输入变量确定下一刻的状态，但有一个很大的缺点就是随着编码
器中寄存器的数量增加，需要存储的数据在急剧的
膨胀，最终会因为需要存储的数据量过大超过计算
机的内存存储范围而无法进行正常的检验。首先在
栅格结构中到输出为零重量的结点，然后以此结
点作为作为运算的起点。遍历每一个零重量的结点。
寻栅格结构中的零重量环。首先寻长度为2的零重量环，再寻长度为3的零重量环…，直到完长度为约束长度的零重量环。在检验的过程中需构造大小为112*2v v −−（v 为约束长度）的矩阵。 利用现有的方法进行检验恶码有二个突出特点： ①运算量大，每一次循环都要做一次矩阵乘，总共需做12m −次矩阵乘法，当约束长度较大时，计算量是非常惊人的。实验仿真有效的见证了这一点。 ②进行检验所需存储的数据过多。 为了对大约束长度的卷积码编码多项式进行检验，必须运用一种能够克服现有检验方法自身不足的新方法对计算机搜索到的大约束长度的卷积码编码器进行检验。考虑到恶性卷积码编码器除有一个围绕初始状态(0S )的零重量环之外至少还有一个零重量环的特性，通过对堆栈译码算法的研究
[8-10]
，利用对堆栈译码算法的巧妙改造使之能够应用于检验大约束长度卷积码编码器。因为是对编码器中的全部状态进行检验，所以这一检验算法是完备的。
28 卷积码编码器的单个状态检验算法的步骤如下： 1）任意选择当前寄存器中的状态为初始状态放到长度为v 的移位寄存器。
2）每左移一位，判断是否回到了初始状态，移出寄存器的最高位放到寄存器的末位，计算输出码字的码重，根据输出的码重判定是否进行下一次操作。
3）如果输出码字重量始终为0，则重复2中的操作直到m 次，使寄存器中的状态在经过m 次循环移位后回到开始时的状态，移位操作结束，跳出循环；否则移位结束，跳出循环。
4）当移位操作结束时，如果输出的汉明重量为0，则该编码器是恶性编码器，否则该状态不能说明编码器是恶性的。
(n,1,m)卷积码编码器的全状态检验算法的步骤如下：
1）从初始状态开始。
2）对每个状态分别进行单个检验。
3）如果检验的结果能说明编码器是恶性的，跳出循环，否则让状态加一进入下一个状态。
4）重复2）和3）中的操作，直至当寄存器中的状态为全一仍未跳出循环，则跳出循环图2给出了检验卷积码编码器是否是恶性编码器的流程图。
图2 恶性编码器检验流程
当卷积码编码器的约束长度是v 时，则该编码
器中共有2v 个状态，随着约束长度的增加寄存器中状态的数量在急剧的膨胀，检验编码器性质的计算量在成倍增加，如果这些计算量全部由一个顺序执行的程序完成，则将耗费较长的时间完成验证的计算。针对这一问题的解决办法只能是并行处理所有的状态。满足并行处理的条件是单个的计算单元之间不能进行通信，并且被处理的数据结构应该是一致的。由于所需检验的编码器的所有状态在一定的程度上可以认为是一样的，并且单个状态之间互不影响，这为进行并行处理提供了前提条件。如果把待执行的计算量由多个并发执行程序完成，在实际应用中获得的性能提升是十分可观的。
3 结语
利用现有工具Matlab 验证卷积码编码器，所能
做到的最大约束长度不超过25，就因为需要存储过多的数据而导致内存不够用，更不用说计算更大约束长度的卷积码。文中所提出的并行计算的方法并不需要存储编码器中的状态，目前可以对约束长度为40的卷积码进行检验，并且在计算速度上有很大的优势。当前的大规模可编程逻辑器件的发展为该算法的实现提供了硬件平台，如果能够把硬件平台和文中提出的方法结合起来，将会使性能得到进一步的提升。
参考文献
卷积编码
[1] ELIAS P.Coding for Noisy Channels[J]. IRE Conv,
1955(04):37-47.
[2] BAHL L,CULLUM C,FRAZER W,et al.An Effcient
Algorithm for Computing Free Distance[J]. IEEE Trans.Inform.Theory,1972(IT-18):437-439. [3] 黄湧，朱琦，酆广增.卷积码技术研究[J].通信技术,
2003(11):
[4] 杜超，郭庆.深空通信中基于喷泉码的前向纠删方法[J].
通信技术,2010,43(03):
[5] MASSEY J L, SAIN M K.Inverses of Linear Sequential
Circuts[J].IEEE.Trans.Computer,1960(C-17):330-337. [6] 王新梅，肖国镇.纠错码原理与方法[M].西安：西安电子
科技大学出版社,2001:378-458.
[7] (美)林舒(Lin S.),(美)科斯特洛(costello,D.J).差错
控制编码[M].北京：机械工业出版,2007:320-337. [8] CEDERVALL M L, JOHNNESSON R.A Fast Algorithm for
Computing Distance Spectrum of Convolutional Codes[J]. IEEE Trans. Inform .Theory,1989(IT-35): 1164-59.
[9] FORNEY G Jr. Use of a Sequential Decoder to Analyze
Convolutional Code Structure[J].IEEE Trans. Inform .Theory, 1970(IT-16):793-95.
[10] MASSEY J L, COSTELLO D J Jr. Nonsystematic
Covolutional Codes for Sequential Decoding in space application[J].IEEE Trans. Commun. Technol, 1971,Pt II,(COM-19):806.
作者简介：
张涛涛（1989-），男，硕士研究生，主要研究方向为通信信号处理；
蒋宇中（1963-），男，教授，博士生导师，电子工程学院通信系，主要研究方向为通信相关技术研究，低频大气噪声和水下噪声建模等；
梁 振（1990-），男，硕士研究生，主要研究方向为通信信号处理。
任一状态 S
初始状态
左移一位
是否回 到状态S
跳出循环
是 码重为 0 否
否
是 码重为 0
跳出循环
是 否
状态加 1
终止状态 否
是
(a) 任一状态的恶性编码器
检验流程
(b) 遍历所有状态恶性编码器
检验流
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议