范德蒙阵列纠删码在嵌入式系统中的应用

程志洪，龚志勇

(中国电子科技集团公司第五十四研究所，河北石家庄 050081)

0 引言

范德蒙阵列纠删码是一种低密度纠删码，具有较低的迭代译码复杂度，而且是目前接近信道容量限的最佳编码技术之一。

卫星数字化视频广播系统(DVB-S)采用卷积码与里德-所罗门编码(Reed-Solomon Codes，RS)级联纠错。卫星数字化视频广播的第2代标准(DVBS2)系统采用低密度校验码(LDPC)与BCH码级联纠错。空间数据系统咨询委员会(CCSDS)推荐采用卷积码与RS码级联或Turbo码等纠错。在网络数据传输、数据存储等通信系统中，多采用纠删码来提高数据传输可靠性。在Internet工程任务组织(IETF)草案中，推荐采用RS纠删码、LDPC纠删码和数字喷泉码等来提高网络通信的可靠性和有效性。分布式存储系统和磁盘阵列技术(RAID)中也采用了纠删码来提高数据的可靠性［1］。

1 纠删码编译码

纠删码具有在嵌入式系统和计算机上处理速度快的特点。嵌入式系统输出的数据经过无线通信系统传输，当系统可靠性不能达到指标要求时，可以考虑在嵌入式系统中加入纠删码来提高无线通信系统的可靠性［2］。

目前，有关纠删码的研究主要集中在两大类，一类是低密度纠删码，如LDPC纠删码、数字喷泉码等，一类是传统的编码方法如RS类纠删码。LDPC纠删码依靠单一异或操作产生冗余，具有相对较低的计算复杂度。尽管数字喷泉码的研究已取得一些可喜成果，但目前的应用还不是非常广泛。RS纠删码为最大距离可分(MDS)码，具有最好的纠删性能［3］，它平衡了容错性能和码利用率，但是它在纠删码中具有较大的计算复杂度［4］。

一个(n，k)纠删码是把k包数据编码为n包数据，使得用这n包数据中的任意k包数据均可重构原来k包源数据，其中每包数据长度为m(m为正整数)个字节，其编译码过程示意图如图1所示。纠删码通常适用于数据整包丢失或包中有数据错误的通信系统中。

图1 纠删码编译码过程

原始数据包为a包～f包，编码后数据包为A包～H包，其中G包和H包为冗余包，输出编码数据 G 的生成过程可示意为 G=f(a，b，c，d，e，f)，f为满足一定规则的异或运算。对RS纠删码来说，f为一个生成矩阵，生成矩阵可以为范德蒙矩阵和柯西矩阵，对应的纠删码分别成为范德蒙纠删码和柯西纠删码。对LDPC纠删码来说，F为一个与二部图对应的稀疏矩阵。纠删码的译码过程为G=f'(a，b，c，d，e，f)，其中 f'为 f的逆运算。

2 范德蒙阵列纠删码算法

若选取纠删码的生成矩阵为范德蒙矩阵或柯西矩阵，则可得相应的纠删码——范德蒙码(Vandermonde Code，VC)或柯西码(Cauchy Code，CC)，它们都属于RS码类。

2.1 范德蒙矩阵

设a为佳伽罗华域上的8次本原多项式p(x)=1+x2+x3+x4+x8，则伽罗华域GF(28)可由p(x)的本原根 a 来生成:GF(28)={0，1，a，a2，…，a254}，其各个元素互不相同。构造如式(1)所示的n×k范德蒙矩阵G，其中n＞k。

2.2 范德蒙码编码算法

使用上面的生成矩阵G进行编码，y=Gx，其中x=(x0，x1，…，xk-1)T，y=(y0，y1，…，yn-1)T，可以看出编码后的数据y完全和源数据不同，不是系统码，这种编码一定程度上增加了信息的保密性，但是也大大增加了编码和解码的复杂度，并不适用。线性码的生成矩阵G的构造常常使用k×k单位矩阵与(n-k)×k的范德蒙矩阵联合构成。使用Gauss-Jordan消去法，把G转换为式(2)所示的形式:

式中，Ik为k级单位矩阵。在矩阵变换过程中，所有的运算都是伽罗华域上的模2运算。

待编码的k包数据为D:

式中，m为任意正整数，包长可以为任意字节数。编码可表示为(假设需要L(L≤n-k)个检验包):

矩阵E的前k包为待编码数据D，直接复制原始数据，只需计算L个检验行。例如 c11=a11*d11+a12*d21+… +a1k*dK1，“+”和“* ”为伽罗华域上的运算。

2.3 范德蒙码译码算法

假设接收到的数据第2行与第k行发生错误(1行中错误比特数≥1，整行标识为错误)，则从冗余行中选则2行构造如式(5)所表示的矩阵:

并对G'求逆，其逆矩阵为G'-1，则恢复数据可用式(7)表示:

只需计算D的第2行和第k行，其他行直接从D'中复制即可。

2.4 范德蒙码编译码快速算法

在范德蒙码编译码过程中，所有涉及到矩阵变换过程的运算都是伽罗华域上的模2运算。伽罗华域上的运算与实数域上的运算不同，其主要区别为［5］:

①伽罗华域上的加减运算以域元素的矢量形式进行，加减运算为域元素的矢量表示所对应位模2加;②域上元素见的乘除运算以本原元素的形式进行，乘除运算为本原元素的冥次模加减。

由式(5)和式(6)可知，编解码过程中涉及大量伽罗华域乘法与加法运算。为了提高速度，事先把所有的可能加法和乘法运算结果都计算出来存储在表中，实际运算的过程中只需进行查表，可大大提高处理速度。

3 仿真结果分析

3.1 信道误码仿真

图2为DVB-S传输系统的结构框图。在Matlab中构建该系统，纠错码外码采用RS码，内码采用卷积码。RS选用(255，239)，交织采用32×8卷积交织，卷积编码采用(2，1，7)，调制方式采用BPSK，AWGN信道的SNR值设为1.14 dB［6］。经过Viterbi译码、解交织和RS解码之后误码率为1.0×10-5。

图2 信道误码仿真框图

通过对该系统的仿真，得到其误码出现分布如图3所示，其中横轴为统计数据包的序号，纵轴为数据包内误码个数。可以看出，数据经过图2所示通信系统处理后，误码不再体现AWGN信道的随机误码特性，误码的表现形式为一包数据中出现多个错误，且出现误码的时间间隔较大。该仿真结果表明DVB-S适合采用纠删码来进一步降低系统的误码率。

3.2 纠错性能仿真

为了验证纠删码与无线通信系统中的纠错码级联使用的效果及测试纠删码的运算速度，设计了如图4所示的仿真系统。在数字信号处理器(DSP)上对数据进行纠删码编码，编码之后的数据DVB-S系统传输，并把最终的数据送进计算机由计算机完成纠删码解码工作。

图3 误码出现分布图

图4 仿真系统结构框图

DSP 选用 TI TMS320C6416，频率为850 MHz，片内RAM为1 MB，计算机配置为 CPU P4，主频为3.0 GHz，4 G 内存。

在该验证系统中RS纠删码参数如下:源数据包k=17，包长N=256字节，编码之后数据包n=20，即冗余包为3包。经过实际测试:当图2所示的系统误码率为1.0×10-5时，加入纠删码之后的误码率将为1.0×10-8左右，当图2所示的系统误码率为1.0×10-6时，加入纠删码之后的误码率将为1.0×10-10左右。随着信道误码率的提高，纠错性能会下降，如果增加冗余包，能够进一步提高纠错性能。

DSP数据输出速率为8 Mbps时，占用的DSP处理时间非常少，计算机进行纠删码解码运算占用的CPU为2%左右。

4 结束语

通过分析范德蒙阵列纠删码的编解码算法，得到一种范德蒙码编解码快速算法。将范德蒙码编解码快速算法应用于Matlab构建的系统信道误码仿真。实验结果表明，范德蒙阵列纠删码与通信系统中的纠错码级联使用大大提高系统的抗误码性能，在利用快速算法完成较高数据速率的实时处理，进一步提高了系统的可靠性。

［1］LIN Shu，COSTELLO D J.著差错控制编码［M］.晏坚，何元智，潘亚汉译.北京:机械工业出版社，2007.

［2］RIZZO L.Effective Erasure Codes for Reliable Computer Communication Protocols ［J］. ACM Computer Communication，Review，1997，27(2):24-36.

［3］张传达，李小文.卷积编码及其 Viterbi译码的实现［J］. 无线电工程，2006，36(7):45-48.

［4］王新梅，肖国镇.纠错码-原理与方法［M］.西安:西安电子科技大学出版社，2002.

［5］向茜，刘钊.伽罗华域上代数运算的最简实现［J］.电子科技大学学报，2000，29(1):5-8.

［6］李隽.卫星导航信号模拟器体系结构分析［J］.无线电工程，2006，36(8):30-21，39.