RS码类的构建及在数据链模拟系统中的应用

刘翠海 ,姜 波,温 东,徐松岩

(海军潜艇学院,山东 青岛266071)

1 引 言

数据链是以无线传输为主,按照统一的消息标准和通信协议,链接传感器平台、指挥控制平台和武器平台,实时处理和分发战场态势、指挥引导、战术协同、武器控制等格式化消息的系统,其本质是一种高效传输、实时分发格式化消息的信息链路[1]。其中,严格科学的格式化消息标准是数据链广泛应用的前提条件,战术数据若不能准确传输可能会造成提供虚假信息,致使战机贻误。为了保证战场上的各类作战数据信息准确无误地按照统一约定的格式传输分发达到共享,保证作战系统的效能得到最大的发挥,在复杂的无线信道通信环境中,数据传输必须要有容错措施来增加传输数据的可靠性。由于RS码具有同时纠随机错误和突发错误的能力,且纠突发错误更有效,因此在数据通信和数据存储系统的差错控制中得到了广泛的应用,其中RS(31,15)码现已经成为美军在三军联合战术信息分发系统(JTIDS)中采用的标准码。

本文以战术数据链通信系统为对象,详细分析了RS编译码模型及其编程实现方法,并采用VC++语言和面向对象的程序设计方法,设计且实现了应用于数据链模拟系统中的CRSCode类,并针对数据传输过程中产生的突发和随机错误的极限情况进行了检验。仿真验证表明,设计的RS编译码类的纠错能力与理论分析一致,满足模拟系统的设计要求。

2 RS编译码模型及编程实现

RS码是一种多进制BCH循环分组码,其码字符号均在GF(2m)上取值。对于(n,k)RS码,n=2m-1为码长,k为信息码元数目,n-k为监督码元数目,d=n-k+1表示码元距离。RS码是一种极大最小距离可分码,即在所有线性分组码中其最小距离最大,也就意味着RS码(纠2t=n-k个差错)的纠错能力最强[4-5]。

RS码的基本思想就是选择一合适的多项式g(x),并且使得对每个信息码计算得到的码字多项式c(x)都是g(x)的倍式,即使得c(x)除以g(x)的余数多项式为0。这样,如果接收到的码字多项式除以g(x)的余数多项式不为0,则可以知道接收的码字中存在错误,因此可以进一步计算并纠正t个错误。

2.1 RS编码模型及编程实现

RS码属于循环码的一种,它的编码过程就是用其信息多项式m(x)乘以 xn-k后再除以生成多项式g(x),所得余式即为校验多项式h(x),然后将h(x)置于m(x)之后,即形成RS码。其中,各多项式的所有运算均在伽罗华域进行,因此,在计算机仿真实现中,有必要首先完成伽罗华域元素产生的程序。

2.1.1 构造伽罗华域GF(2m)[2]

对于GF(2m)中的元素,首先给定1=α0,连乘 α可以在m重的形式里通过对α0连续左移来产生α1、α2、…、αm-1。对 αm-1的左移生成 10…0(共 m 个0),左移结果该元素为m+1比特,因此必须要映射到m比特,即通过 αm=α+1多项式。其比特数据计算方法是将 m+1重数中的最高位掩去得到 m重数后,通过按比特的模2加“11”到掩码后的m 重结果(即加 α+1)来实现的。随后继续左移可以产生 αm+1、αm+2、…、α2m-1。伽罗华域元素产生编程实现的框图如图1所示。

图1 伽罗华域元素产生流程图Fig.1 Generation of a Galois Field′s element

2.1.2 多项式的计算机表示及数学运算模型

有限域GF(pm)中的每个元素均可由一个多达m项的多项式表示,每一项的系数是一个模 p值。在计算机中,系数可以存储在一个数组里,其中 xn的系数存放到数组中的位置n,即假设数组从0开始标记,如C和C++。对于像Matlab从1开始标记的语言,xn的系数将存到数组中n+1的位置。对于GF(2m)中的元素,多项式可以存储在一个整型变量中,用每比特代表一个二进制系数。

RS编码、译码过程中用到了大量的多项式元素的乘法、加法和倒数运算。我们知道,其运算均是在伽罗华域GF(2m)中进行的,其乘法运算对应的是指数模2m相加,加法运算则是模2运算。为此,在实现了伽罗华域元素产生函数的基础上,需要编程实现RS编译码中常用的多项式加法、乘法、除法等基本运算函数。

假设有两个多项式

多项式加法运算实现起来非常简单,多项式乘法与除法编程实现基本相同,图2给出了多项式乘法计算电路。

图2 多项式乘法电路Fig.2 Circuit of multiplicity of the polynomial

按照图2所示电路多项式乘法的实现步骤如下[6]:

步骤1:r个寄存器全部清零;

步骤2:A(x)最高次系数 ak首先送入时,乘法器输出乘积的最高次项xk+r的系数akbr,同时 ak存入寄存器的第一级;

步骤3:A(x)的第二个系数 ak-1送入时,ak由第一级寄存器进入第二级寄存器,同时与 br-1相乘,乘法器输出 ak-1br+akbr-1,即得到了乘积的xk+r-1的系数;

步骤4:如此重复进行,直至 k+r+1次移位后,乘法器输出乘积的常数项a0b0。

2.1.3 RS编码的编程实现

假设需发送的信息码字序列为m1,m2,…,mk,RS码的编码电路如图3所示。

图3 RS编码电路Fig.3 Encoding circuit for RS code

按照图3所示电路实现的RS编码计算机程序流程如图4所示。

图4 R S编码程序流程图Fig.4 Flowchart of encoding program of RS code

2.2 RS译码模型及编程实现[6]

相对于RS编码,其译码过程比较繁琐、复杂。RS译码主要包括计算伴随多项式、确定差错位置多项式、计算差错位置多项式的根和求错误图样4个步骤。第一、三、四步计算机编程实现起来比较简单,第一步求伴随多项式是将 αi(i=1,2,…,2t)代入接收多项式r(x)而得到的;第三步依据钱氏搜索算法确定错误位置,得到差错数量;第四步根据错误位置和错误值得到错误图样。第二步是整个译码过程中最复杂的一步,大多采用BM迭代算法。实现BM迭代算法可以以列表形式完成,如表1所示,表中 lu是σ(u)(x)的次数。

表1 BM迭代过程Table 1 BM algorithm

假设我们已经填满了第u行,可以这样来填第u+1行:

(1)如果 du=0,则 σ(u+1)(x)=σ(u)(x)且 lu+1=lu;

(2)如果du≠0,寻找第 u行前的第ρ行,使 dρ≠0及最后一列(ρ-lρ)为最大值,则由式(1)可得σ(u+1)(x),且

(3)不管du是否等于零,都要依据式(3)计算du+1:

最后一行的多项式 σ(2t)(x)即为需要的 σ(x)。如果它的次数大于t,则表明接收序列的错误多于t,一般来说就无法决定它们的位置。

3 RS码类的构建和在模拟系统中的实现

数据链模拟系统以战术数据链通信系统为模拟对象,以VC++语言为编程实现平台,采用面向对象的程序设计方法,以战术数据链通信系统各模块为类对象,编程实现了各类对象并进行了封装。基于RS编译码的数据链模拟系统结构如图5所示。

图5 数据链模拟系统信号流程图Fig.5 Block diagram of the data link simulating system

依据图5各模块的划分,数据链模拟系统设计并实现了CModel类,该类是VC++中CObject类的派生类,定义了供所有模型类调用的公共过程,是图5所有模块的基类。CRSCode类、CCSK类、CMSK类以及CDSSS类都是CModel类的派生类,它们分别是RS编译码类、循环码移位键控类、最小移频键控类、直接序列扩频类的基类。

3.1 RS编译码类的整体设计

根据上一节的分析,CRSCode类定义有自己的成员变量和成员函数,完成整个模拟系统中的编码和译码。下面给出了CRSCode类定义的部分内容:

class CRSCode:public CModel

{

public:

int n;//码字长度

int k;//消息字长度

int m;//伽罗华域各元素的比特数

int generate-GF(int m);//生成GF(2m)域所有元素

int multiply-rs(int a,int b,int m);

int reverse-rs(int a,int m);

int polymul-rs(int a,int b,int m);

int polydiv-rs(int a,int b,int m);

}

CRSCode类中的成员函数multiply-rs(int a,int b,int m),参数a、b为十进制表示的多项式中xn的系数,参数m为GF(2m)域中各元素的比特数;函数返回值为系数a与b相乘的结果。

成员函数reverse-rs(int a,int m),参数a为十进制表示的多项式中xn的系数,参数m为GF(2m)域中各元素的比特数;函数返回值为系数a-1的结果。

成员函数polymul-rs(int a,int b,int m),参数a、b为一数组,是以十进制表示的多项式中从 x0～xn各项的系数,a、b的排列顺序是以多项式次数从低到高的顺序排列,参数m为GF(2m)域中各元素的比特数;函数返回值为系数多项式 a(x)与b(x)相乘的结果。

成员函数polydiv-rs(int a,int b,int m),参数a、b为一数组,是以十进制表示的多项式中从 x0～xn各项的系数,a、b的排列顺序是以多项式次数从低到高的顺序排列。参数 a为待发送信息码字,参数b为生成多项式,参数m为GF(2m)域中各元素的比特数;函数返回值为校验多项式各系数,排列顺序是以多项式次数从低到高的顺序排列。

3.2 RS编译码类在模拟系统中的应用及校验

数据链模拟系统模拟了时分多址的工作方式,每个时隙长为7.8125 ms。在不考虑同步信息的情况下,传输的消息包括信息标志和数据两部分[3]。信息标志部分主要包括了时隙号、用户号、消息类型等报头信息。数据部分模拟了固定格式的消息字,每个消息字包含15个码元,每个码元5 b字符,其中数据占70 b,奇偶校验位占5 b。为保证传输消息的可靠性,信息标志部分采用的是RS(16,7)编码,对消息字采用的是RS(31,15)编码。通过(16,7)RS编码,在传输中即使这7个码元有4个码元出现了错误也可得到纠正。数据部分的(31,15)RS编码,每组可纠8个错误,7组交织可纠56个错误。这种编码使得在由31个字符组成的大组中,由于干扰或传播等原因,即便有16个字符无法判决或有8个字符判决错误,在译码时也能得到纠正。

为了检验CRSCode类的运算速度和纠错能力及正确性,分别对数据传输过程中产生的突发和随机错误的极限情况进行了检验,表2给出了信源产生104个符号、信噪比在0～7 dB范围测得的实验数据,根据数据绘出的性能曲线如图6所示。仿真结果表明CRSCode类的纠错能力与理论分析一致,与设计的功能相符,达到了译码的预期效果。

表2 误码率实验测量数据Table 2 BER data of test

图6 RS编码BER性能曲线Fig.6 Reed-Solomon error performance evaluation

4 结束语

数据链模拟系统的实现大体可分为建立模型、用建立的模型构造目标系统和系统仿真三部分工作,构造系统的模型是完成所有工作的基础。由于RS编译码在战术数据链通信系统中有着重要的意义,它能够提高整个系统的可靠性和抗干扰能力,进而提高系统性能,因而准确地对其建模、编程实现及封装是整个数据链模拟系统中关键的环节。本文以VC++为软件平台,以面向对象的程序设计方法实现了RS编译码类,并简要介绍了数据链模拟系统的程序组成。本模拟系统只考虑了编码、交织、CCSK基带调制以及MSK调制等模型,没有考虑同步以及其他信道模型,因此还需要进一步完善。

[1]刘翠海.美军战术数据链的发展及作战运用[J].电讯技术,2007,47(5):6-10.LIU Cui-hai.The Development and OperationalApplication of the U.S.Forces′Tactical Dada Links[J].Telecommunication Engineering,2007,47(5):6-10.(in Chinese)

[2]王昕.无线通信系统仿真-C++实用模型[M].北京:电子工业出版社,2005.WANG Xin.Simulating Wireless Communication Systems PracticalModels in C++[M].Beijing:Publishing House of Electronics Industry,2005.(in Chinese)

[3]梅文华,蔡善法.JTIDS/Link16数据链[M].北京:国防工业出版社,2007.MEI Wen-hua,CAI Shan-fa.JTIDS/Link16 Data Link[M].Beijing:National Defense Industry Press,2007.(in Chinese)

[4]陶德元,何小海,吴志华.RS码编译码算法的实现[J].四川大学学报(自然科学版),2000,37(6):868-872.TAO De-yuan,HEXiao-hai,WU Zhi-hua.The Implementation of RS Encoding and Decoding[J].Journal of Sichuan U-niversity(Natural Science Edition),2000,37(6):868-872.(in Chinese)

[5]韩作生,袁东风.RS码频域编译码的计算机模拟[J].通信学报,1994,15(6):104-112.HAN Zuo-sheng,YUAN Dong-feng.Computer Simulation of the Coding and Decoding of RS Code in Frequency Domain[J].Journal of China Institute of Communications,1994,15(6):104-112.(in Chinese)

[6]杨爵,郎宗木炎.实用纠错编码[M].北京:中国铁道出版社,1988.YANG Jue,LANG Zong-yan.Practical Error Correcting Coding[M].Beijing:Chinese Railroad Publishing House,1988.(in Chinese)