RS编码和纠错算法

RS编码和纠错算法 RS编码和纠错算法 张 海 摘 要 几乎所有的现代化通信 系统都把纠错编码作为一个基本组成部分。RS码 由于 具有强有力的纠错功能，已经被NASA、ESA、CCSDS等空间组织接受，用于空间信道纠错。 本文简单论述了RS编码原理，纠错算法及工作流程，能使大家初步了解RS编码。 关键词 RS码 编码原理 纠错算法 工作流程 1 引言 前向纠错 (FEc)方式是一种无反馈差错控制方式。编码过程选用纠错编码，在接收端 译码器不仅能检查出有无错误，而且能够自动纠错而不要求重发，系统只需单向信道，即 可实现自动纠错。FEC方式可分为两大类，即分组码与卷积码。另外它们还可以级联使用。 所谓分组码是将信源送出的二进制数字序列先进行分段，如每一段由 K个信息码元组 成{ⅡlK-l，mK_2一一-m2，ml，mo)，然后在 K个信息码元后面加上N—K个监督码元 (也称为 校验码元){rN-K-l，rN-K-2，⋯一-rl，r0)构成长度为N的码组{mK-l，mK-2一一 m2，ml，mo， rN-K-l，rN-K-2一一-rl，r0)由于码长为N，信息码数为K，此码称为 (N，K)码。监督码元中 任一码元，仅由该码组中某些信息码元线性摸 2加法关系得到。 BCH码是循环码中最重要的编码 ，目前在卫星编码 中广泛应用。本文着重介绍 cc1Tr 协议中的 RS码，它是 BCH码中业已成为工业标准的编码方式 。 2 RS码的基本结构和原理 2．1 RS码的构造 RS码是 Reed—Solomon码 (理德一所罗门码 )的简称 ，它是一种扩展的非二进制 BCH 码 。因为RS码是在伽罗华域(Galois Field，G10中运算的，所以在介绍RS码之前先简要介 绍一下伽罗华域。 例：RS(255，223)中，GF(2 )=GF(2。) 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示域中有 256个元素，除0，1之外的254个元素由 本原多项式P(x)生成。本原多项式P(x)的特性(X +1 (x)是得到的余式等于O。构造GF(2 ) 域的 P(x)是 P(x)=X8+)(4+x。+x +1 (1) 而 cF(28)t~中的本原元素为 维普资讯 http://www.cqvip.com RS编码和纠错算法 a =(o o o o o o 1 0) 下面以一个较简单例子说明域的构造。 【例 l】构造 GF(2 )域的本原多项式假定为 P(x)=X +X+1 a定义为 P(x)=0的根，即 Q + Q+1=0 和 Q = Q+1 GF(23)中的元素可计算如下： 表 1 GF( 元素表 0 mod(Q + Q+1)=0 ’ Q O rood(Q + Q+1)= Q。=1 Q 1 rood(Q + Q+1)= Q Q 2 rood(Q。+ Q+1)= Q a 3 mod(a + a+1)= a+1 Q 4 rood(Q + Q+1)= Q + Q Q 5 rood(Q + Q+1)= Q + Q +I Q 6 rood(Q + Q+1)= Q +l Q 7 mod(Q + Q+ 1)= Q o Q 8 rood(Q + Q+1)= Q 用二进制数表示域元素得到表 2所示的对照表 P(x)=X +X_+1 表2 GF(2b域中与二进制代码对照表 GF(2 )域元素 二进制对代码 0 (000) Q 0 (001) Q l (0l0) Q 2 (100) Q 3 (011) Q 4 (110) Q 5 (111) Q 6 (101) 从而建立了GF(2 )域中的元素与 3位二进制数之间的一一对应关系。 用同样的方法可 建立 GF(2s)域中的 256个元素与 8位二进制数之间的一一对应关系。在纠错编码运算过程 中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(23)域中运算为例： 维普资讯 http://www.cqvip.com RS编码和纠错算法 79 加法例：a。+a =001+011=010：Q 减法例：与加法相同 乘法例：a ．a ： a(5 4)mad'／=a 除法例：a s／Q = a Q 3／a 5= a一2_ a(一2+’)= a 5 这些运算的结果仍在 GF(2 )域中。 2．2 RS码及其编码算法 在 RS码中，输入信号分成(N m)比特一组，每组包括 N个符号，每个符号由 m个 比特 组成 。 在 GF(2m)J*J~中，符号 RS(N，K)的含义如下 ： m 表示符号的大小，如 m=8表示符号由8位二进制数组成； N 表示码块长度 ； K 表示码块中的信息长度； k=N--K=2t表示校验码 的符号数； t表示能够纠正的错误数目。 RS码不但可以纠正随机错误，突发错误，以及二者的组合，而且可以构造其它码类，如级联 码。同时它具有极低的未探测差错率，这意味着与它配合使用的译码器能可靠地指出是否 正确的校正的码字，因此 RS码成为一种很重要 的纠错码。 例如，(255，223)RS码表示码块长度共255个符号，其中信息代码的长度为223，检验 码有 32个检验符号 。在这个由 255个符号组成的码块中，可以纠正在这个码块中出现的 l6 个分散的或者 l6个连续的符号错误，但不能纠正 l7个或者 l7个以上的符号错误。 RS码属于循环码 的一种，它的编码过程就是用它的信息多项式除以校验码生成多项式 求出校验位的过程。也就是计算信息码符多项式除以校验码生成多项式之后的余数。 对一个信息码符多项式，RS校验码生成多项式的一般形式为： G (x)= (x-Q。)(x-Q )⋯ ．(x-Q k0+k- ) (2) 式中： 是偏移量 ，通常取 Ko=0或 Ko=l。而 (N．K)≥2t(t为要校正的错误符号数)。 下面用一个例子来说明 RS码的编码原理 。 【仞j 2】设在 GF(2 )域中的元素对应表如表 l所示。假设(7，3)RS码中的 3个信息符号为 m2、ml和mo，信息码符多项为：M (x)=m2x +mlX +mox (3) 并假设 Rs校验码的4个符号：Q3、Q2、Q。和 Q0，xN。K／G(x)=M(x)rd G(x)的剩余多项式 R(x) 为： R(x)=Q3x +Q2x +Qlx+Qo (4) 如果 Ko=0，t=2，由导出的 RS校验码生成多项式就为 G (x)= (x—a o)(x．a ) (x．a 2)(x．a 3) (5) 维普资讯 http://www.cqvip.com RS编码和纠错算法 根据多项式的运算，由 G(x)和 M(x)司以得出： 讲 m1x5+n1o】【=4 3+ 1) (x-Q 0)(x-Q )(x-Q 2)(x-Q 3)Q(x) (6) 当用 x：Q。、x=Q 、x=Q 、x=Q 代人上式时，得到下面的方程组： m2+ml+mo+Q3+Q2+Q14-Q~--o m 2 Q 6+ m 1 Q 5+ mo Q 4+Q3 Q 3+Q2 Q 2+Q1 Q+Q~--0 m2(Q 2)6+m1(Q 2)5+mo (Q 2)4+Q3(Q 2)3+Q2(Q 2)2 +Q1(Q )+Q~--o m2(Q 3)6+m1(Q 3)5+mo (Q 3)4+Q3(Q 3)3+Q2(Q 3)2 +Q1(Q )+Q~--0 (7) 经过整理可以得到用矩阵表示 的(7，3)RS码的校验方程： HQ × (VQ) --0 HQ=r，1 1 1 1 1 1 l Q 6 Q 5 Q 4 Q 3 Q 2 Q I(Q ) (Q ) (Q )4(Q ) (Q ) (Q ) 【(Q 3)6 (Q 3)5 (Q 3)4 (Q 3)3(Q 3)2(Q 3) vo=【m2 m1 mo Q3 0．2 Q1 Qo] (8) 求解方程组可以得到 RS校验码的 4个符号为 Q3、Q2、Q1和 Q0，在读出时的校验因子可按 下式计算 ： So=m2+m1+too+Q3+Q2+Q1+Q0 S1----ID．2 Q 6+ m 1 Q 5+ mo Q 4+Q3 Q 3+Q2 Q 2+Q1 Q+Qo s2----ID．2(Q 6)2+m1(Q 5)2+mo(Q 4)2+Q3(Q 3)2+Q2(Q 2)2 +Q1(Q) +Qo s3----ID．2(Q 6)3+m1(Q 5)3+mo (Q 4)3+Q3(Q 3)3+Q2(Q 2)3 +Q1(Q) +Qo (9) 2．3工程实现 我们在实际使用中，往往只是利用本原多项式计算出伽罗华域 GF(2i)的元素表，用 Maflab计算出 G(x)的系数，并利用伽罗华域将系数化简为一位域内的元素，从而得出生成 多项式 G(x)。 G(x)=(x．Q)(x．Q 2)(x．Q 3)⋯ ．(x．Q )=xN·K+Q xN-K-1 ⋯一+Q j x+Q 利用下图实现编码 电路 ： 维普资讯 http://www.cqvip.com RS编码和纠错算法 81 图1 RS绾码电路 RS 其中乘法器、加法器及移位寄存器都是位多元域 GF(2m)中的运算及存储器件。以 RS(255，223)为例，说明其工作过程： (1)开关 K先打到 1，移入 223位信息位，此时编码电路也将 223位信息位移入编码电路， 产生校验位，但是不输出。 (2)223位信息位传输完毕，开关 K打到 2，编码器产生 32位校验位。此时信息流 M(X) 要暂停(可通过停信息流码钟或利用码片之间的空隙，但要保证空隙足够大)。 (3)校验位传输完毕，开关 K再打到 1，传输信息流，循环下去。 实现 RS编码有几种不同的方法：一种是使用软件查询的微码顺序结构，它要使用大量 的存储器，同时查表所需要的时间会产生一个无法接收的延时，使得速度也受到限制；另 外就是硬件实现的方法，有适用于高速率的柯西表达式的生成阵列固化结构，还有适用于低 速率的 BerleKamp算法，用硬件实现可大大缩短延时，但难点在于硬件的规模。图 1中每 个乘法器都是两个多位数相乘，我们在这里介绍一种用模 2加法器实现的多位乘法器。 例：GF(2 )中任意元素可以用基底 1、 a的线性组合表示为： Q 2+ Q 1 Q + Q O 乘得出： Q‘(Q‘Q 2+Q 1 Q+Q o)=(Q 2-t-Q 0) Q +(Q 2-t-Q 1)+ Q l Q 2、Q 2+ Q 1、Q + Q O、 Q 2 ‘= Q 2-t-Q 0 Q 1‘= Q 2-t-Q 1 Q 0 ‘= Q 1 因此，乘以a 的电路如下图所示： 维普资讯 http://www.cqvip.com RS编码和纠错算法 图2固定乘法器实现 通过此方法可以构造较高速度的乘法器，满足中低速编码的需要。 3 结束语 Rs码是一种纠错能力很强的纠错码，广泛用于数字通信和数字存储领域及卫星通信中。 它与卷积码级联使用，在中速的数据率下，在误码率为 lff 时，可以有 8．5-9．5dB的编码增 益，这样可以大大降低星上发射功率，降低误码率，也可以减小天线的口径，提高性价比， 有很高的商业价值。 参考文献 1 张鸣瑞 编码理论 北京航空航天大学出版社 2 聂涛 卢玉民 李振玉 译 数字通信中的纠错编码 国防工业出版社 3 樊昌信 詹道庸 通信原理 国防工业出版社 维普资讯 http://www.cqvip.com