文档RS纠错编码原理及其实现方法.doc

Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 1 RS纠错编码原理 及其实现方法 陈文礼 January 08 于郑州 If you have any suggestion or criticism . please email to QQ83902112 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 2前言 随着越来越多的系统采用数字技术来实现纠错编码技术也得到了越来越广泛的应用。RS码既可以纠正随机错误又可以纠正突发错误具有很强的纠错能力在通信系统中应用广泛。近些年来随着软件无线电技术的发展RS编码、译码一般都在通用的硬件平台上实现。通常采用基于FPGA的VHDL编码硬件实现或者在DSP、单片机上用C和汇编编程软件实现。 RS纠错编码涉及的领域很广特别是设计到很多数学知识。这对那些对数学不太感冒的工程技术人员来书是个不小的挑战。尽管讲RS编码的书籍很多但是那些书都是采用循序渐进逐步引入的方式从汉明码到循环码从循环码到BCH码BCH码再引入RS码。对于工程技术人员他们需要的是简明扼要的讲解和详细的实现方法。 本人写这篇文章的宗旨就是尽量最简单的语言最简短的篇幅来讲RS纠错编码原理把重点来放在实现方法上。 为了便于读者仿真本文采样MATLAB程序实现程序尽量符合硬件C语言写法读者经过简单修改即可应用到工程中去。 本文读者对象 本文是为那些初识RS编码的学生、工程技术人员而写并不适合做理论研究如果你是纠错编码方面的学者、专家那么本文并不适合你。 由于作者水平有限错误在所难免恳请读者批评指正。 陈文礼 2008-01 于郑州 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 3一、必备的一些代数知识 1、在纠错编码代数中把以二进制数字表示的一个数据系列看成一个多项式。例如二进制数字序列10101111可以表示成 式中的ix表示代码的位置或某个二进制数位的位置ix前面的系数ia表示码的值。若ia是一位二进制代码则取值是0或1。Mx称为信息代码多项式。 多项式次数 称系数不为0 的x的最高次数为多项式fx的次数记为fx。 2、域 域在RS编码理论中起着至关重要的作用。 简单点说域2mGF有2m 设2mq个符号 0120q 且具有以下性质 域中的每个元素都可以用0121ma的和来表示。11q 为本原多项式px的根。 运算规则有 在纠错编码运算过程中加、减、乘和除的运算是在伽罗华域中进行。现以GF24域中运算为例 加法例108001001110101 模2加法相当于0010与0111异或 减法运算与加法相同 乘法例810810mod153 除法例810221513/ 不理解没关系下面的例子也许对你有帮助。 例 m4 41pxxx 求2mGF的所有元素 因为为px的根 得到410 或41 根据运算规则 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 4由此可以得到域的所有元素 元素 二进制对应码 十进制对应值 0 0 0000 0 0 1 0001 1 1 1 0010 2 2 2 0100 4 3 3 1000 8 4 1 0011 3 5 21modp 0110 6 6 232modp 1100 12 7 3231modp 1011 11 8 3211modp 0101 5 9 231modp 1010 10 10 321modp 0111 7 11 2321modp 1110 14 12 32321modp1111 15 13 323211modp 1101 13 14 32311modp 1001 9 15 311modp 0001 1 由此可以看出本原多项式是求解域的全部元素的关键。读者也许会有这样的疑问我们如何得到px呢 本原多项式px的特性是211mxpx得到的余式等于0。 由于作者也是工程技术人员具体怎么得到px也没有深究过。 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 5作者在设计RS编码时候都是根据MATLAB指令rsgenpoly来得到px。 其格式为rsgenpolynk 参数n为码长一般21mnk为信息码元个数。 例如m4 码长n15信息码元长度为9 GF24的本原多项式可以根据指令 gtgtrsgenpoly159 得到 ans GF24 array. Primitive polynomial D4D1 19 decimal 二、线性分组码的一些基本概念 1、线性分组码一般用nk或nkd表示 n为码长k为信息码元的数目nk为监督码元的数目。d表示码元距离。 定义两个码组上对应位置上数字不同的个数称为码组的距离。 发送的码字 123.nccccc 接收的矢量123.nrrrrr 信道错误图样ecr 例如c11000 r10001 e111000000101001 从而可以看出从左端起第2位和第5位是错误的。 2、校验矩阵概念 码长为n信息数为k监督数为r。 这样的一组码形式为1212.krcmmmppp im表示第i个信息码jp表示第j个校验码 各个校验码可从下列线性方程组求得。 111122112211222212112212.10.00.01.00.00.10kkrkkrrrrkkrhmhmhmppphmhmhmppphmhmhmppp 1-1 式中ijh是常数 校验方程组可写成校验矩阵 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 611121212221210000100.0001kkrrrkhhhhhhHhhh 该矩阵具有r行和n列 故式1-1可以写成 0THc或0TcH H矩阵称为nkr码的校验矩阵。 发送矢量为c接收矢量为r 若0TrH 则说明接收到的码有错误。 设错误图样为e 则可写成以下关系式 rce 为了纠错必须知道那些位上存在错误。这可由校正子又称伴随式s来确定 TTTTsrHcHeHeH 译码器的主要任务就是如何从s中得到最像e的错误图样e 从而译出rce 设第i个是错误的 因此e0 0 0 1 0 0 第i个有错误 112111222212120 0 . 0 1 0 . 0100010001rrkkrkTiirihhhhhhhhhsrHhhh 计算出的矢量示出i是出错误的位置。 3、生成矩阵概念 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 7 生成矩阵G 它是一个k行n列的矩阵 若已知信息组m通过生存矩阵可求得相应的码字。 cmG m是k个信息元组成的信息组 这个应该比较容易理解在此就不做过多解释。 三、RS码的一些重要性质 1、RS 码生成多项式 码长21mn 监督元数目2rnkt能纠正t个错误。 定义在nkd的RS码中存在唯一的nk次多项式gx使得每一个码多项式cx都是gx的倍式。gx称为nkdRS码的生成多项式。 一般情况下 22tgxxxx 2、定理 在2mGF中每个非0元素2221m均满足211mx反之2110mx的根必在2mGF中。 所以 01211nnxxaxaxaxa 3、RS码的校验多项式 由于生成多项式gx是1nx的因式 1nxgxhx gx为nk次多项式则hx为k次多项式 1nxgxhx1010nkknkkgxgxghxhxh 由右式可以看出12nnxxx的系数均等于0 即 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 80001100110112110001iinkinknnnkknkkghghghghghghghghghgh 式中011iinkinkghghgh表示ix的系数 上式可简写为 0110iinkinkghghgh 121in 000nkkghgh 我们称 1/nhxxgx为码的校验多项式。 4、RS码的生成矩阵 kGIp 左边是kk阶单位方阵。这相当于码字多项式的第1n次至nk次的系数是信息位。而其余的位校验位。 根据前面的定义 cx是gx的倍式 0modnkcxmxxrxgx nkmxx表示在信息组后面插nk个监督码元 modnkrxmxxgx 由kGIp可知生成矩阵里的信息组又叫基底矢量分别为 1000 01000001 所以很容易得到 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 9121000mod0100mod0001modnnknkxgxxgxGIpxgx 例 求735RS码生成矩阵G 根据n7k3t2我们选取域32GF 32GF 本原多项式31pxxx 为px的根 310p 或 31 我们可以推算出32GF域的全部元素 元素 二进制对应码 0 0 000 0 1 001 1 1 010 2 2 100 3 1 011 4 1a2 110 5 2a21modp 111 6 21a21modp 101 7 21a1modp 001 D5 其生成多项式为 23443323gxxxxxxxxx 143245modmodnxgxxxxgx Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 10223266modmodnxgxxxxgx 33323modmodnxgxxxxgx 由此可知其生成矩阵为 44526633100101010011G 5、RS码的校验矩阵 由于系统码时生成多项式的倍式 Cxqxgx 22tgxxxx 所以cx必以22t为根。 即若码字 121210nnnnCxcxcxcxc 则 121210iinininnCcccc 22it 由此可得出RS码的校验矩阵 121222212222111nnnnnntttH Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 11四、一些基本运算的软件实现 由于编码译码的运算都是在域中进行的那么我们首先要计算出域中的元素对应的二进制或十进制表示。 MATLAB程序如下 generate_gf生成域中的所有元素。 alpha_tozeros12m mask 1 alpha_tom1 0 for i1:m alpha_toi mask if Ppi0 alpha_tom1bitxoralpha_tom1mask end mask mask2 end maskalpha_tom for im2 : n if alpha_toi-1 gt mask alpha_toi bitxor alpha_tom1 bitxoralpha_toi-1mask2 else alpha_toi alpha_toi-12 end end alpha_to2m 0 把元素0放在最后一位。 例如可以根据计算出52GF的全部元素 alpha_to 1 2 4 8 16 5 10 20 13 26 17 7 14 28 29 31 27 19 3 6 12 24 21 15 30 25 23 11 22 9 18 0 在前面的例子中 108001001110101 42GF 810810mod153 这样的计算看似简单但是在实际的计算中i都是用对应的二进制表示例如在本例中8用0101表示我们并不能直观看出0101对应的的指数。为 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 12了便于运算我们计算出一个检索数组:index_of如index_ofmm index_ofnn 。 mnalpha_toindex_ofmindex_of n 这样以来运算就变得简单多了。 index_of检索数组可以由下面程序得出。 index_ofzeros12m for i1:2m-1 index_ofalpha_toii-1 end index_of 例m5 index_of 0 1 18 2 5 19 11 3 29 6 27 20 8 12 23 4 10 30 17 7 22 28 26 21 25 9 16 13 14 24 15 0 乘法运算就可以通过下面的程序很简单的实现。 function yrs_mulab if ab0 y0 else a1 index_ofa b1 index_ofb cmoda1b1n n2m-1即码长 y alpha_toc1 end 把x代入多项式fx即计算fx的值x为一常数。 程序中T为GF中元素对应的二进制表示值。 function yrs_polyfx xx index_of x-1 Llengthf-1 多项式的次数 y1f1 常数项 for i1:L y1rs_addy1rs_mulfi1 alpha_to modixxn1 累加 end yy1 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 13 五、RS编码 RS编码软件实现 其编码电路基本上可分为两类k级和nk级编码器 1、nk级编码器 其原理比较容易理解 由于系统码时生成多项式的倍式 Cxqxgx 1212.nkkcrrrmmm nkCxqxgxmxxrx 信息码乘以nkx然后再除gx就得到了余式rx也就得到了校验位。 这里难点就是如何实现多项式乘法除法运算。 多项式乘法 设两多项式 1110kkkkAxaxaxaxa 1110rrrrBxbxbxbxb 相乘过程可用下图表示 00kaaarb1rb2rb2b1b0b 图1 实现步骤如下 1 r个寄存器全部清0。 2 Ax最高次系数ka首先送入时乘法器输出乘积的最高次项krx的系数krab同时ka 存入寄存器的第一级。 3 Ax的第二个系数1ka送入时ka由第一级进入第二级寄存器同时与1rb相乘 11krkrabab就得到了乘积的1krx的系数。 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 144 这样重复进行直至1kr次移位后乘法器输出乘积的常数项00ab。 乘法过程还有另外一种表示方法。 输入输出 00kaaarb1rb2rb2b1b0b 图2 它的工作过程和图1类似。 多项式除法 设 1110kkkkAxaxaxaxa 1110rrrrBxbxbxbxb 流程图 0b1b2b1rb1rb01kaaa 图3 1 开始运算时 r 个寄存器全部清0第一次移位时Ax最高次系数ka首先进入最左一级寄存器r 次移位后寄存器1至寄存器2t的数值分别为 121krkrkkaaaa 2 第r1次移位时除法器输出1krab这就是商的第一项krx的系数1krab同时反馈到后面的各级寄存器中即得到第一次除运算的余式。 3 以此类推经k次移位后完成了整个除法运算过程移位寄存器中的值就是余式rx Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 15多项式相乘相除 分别设 1110kkkkAxaxaxaxa 1110rrrrHxhxhxhxh 1110rrrrGxgxgxgxg 计算/AxHxGx 该电路图是图2图3两种电路的结合。 输入 00kaaa 0h1h2h1rh2rhrh0g1g2g1rg2rg1rg商输出 图4 如果HxGx次数不等只需按最高次数设计即可。 RS编码电路 22122110ttttgxgxgxgxg 21tg 12111000nknnnknkkkmxxmxmxmxxx 那么/nkmxxgx的除法电路根据图3可用下图表示 0g1g2g21tg21/tg 输入为nkmxx 因为21tg加法减法运算规则相同 所以又可以表示为 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 16 21tg0g1g2g 寄存器1 . 寄存器2t 上述方法相当于事先做好nkmxx再做除法这样需要移位n次 而图4的电路我们只需移位k次。 根据 221122110110ttnknkttnknkgxgxgxgxggxgxgxg 1nkg 1000nknknkxxxx 根据图4/nkmxxgx的电路可表示为 输入 商输出12kmmm1nkg2nkg2g1g0g MATLAB程序实现 rrzeros1 n-k for ik:-1:1 feedback rs_adddatairrnn-kk if feedback 0 for jn-k-1:-1:1 if gj 0 rrj1 rs_add bbjrs_mulgjfeedback else rrj1 rrj end rr1 rs_mul gg1feedback end Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 17 else for jn-k-1:-1:1 rrj1 rrj end rr1 0 end end 下面的程序是另一种比较简洁的程序 rrzeros1n-k for i1:k feedback rs_addrrn-kdatak-i1 rrn-krs_addrrn-k-1rs_mulfeedbackgn-k rrn-k-1rs_addrrn-k-