RS译码

RS译码（精选四篇）

RS译码篇1

现代通信系统中,前向纠错码技术是实现可靠通信的基本方法。非二进制循环纠错码RS(Reed-Solomon)码是一种性能优良的线性分组码,在同样的编码冗余度下,RS码有最强的纠错能力。由于可以纠正随机错误和突发错误,常作为级联编码的外码,以纠正其他编译码造成的突发错误。RS码已广泛应用于数字通信各领域及数据存储系统中,主要应用于实时性较高的移动通信系统、深空通信、数字卫星电视、磁记录系统等方面。

RS码的编译码存在时域和频域两种算法[1,2]。其中,时域编译码算法出现的比较早,由于比较成熟而被广泛采用;频域编译码算法虽然出现较晚[3],但是可以借助快速傅里叶变换(Fast Fourier Transform,FFT)及快速傅里叶反变换(Inverse Fast Fourier Transform,IFFT)提高编译码速度,具有较大的发展潜力。

目前有关时域编码、频域译码[4,5,6,7,8]的研究,仅针对b=1时的RS码本原生成表达式的编译码进行,而没有针对更一般的本原生成表达式。本文提出一种针对通用伽罗华域的快速RS编译码技术,适用于所有RS码本原生成表达式,与传统的时域编译码相比,复杂度明显降低,但仍具有相同的编译码能力。

1 伽罗华域中的算术运算

RS码的编译码均在伽罗华域(Galois Field,GF)上进行,在此先研究伽罗华域中的算术运算。若运算为双目运算符,则两个操作数为A,B;若运算为单目运算符,则操作数为A,结果记为C。其中:

1.1 伽罗华域的加减运算

伽罗华域上加减运算等同,结果为对应位进行异或运算。即:

undefined

1.2 伽罗华域的乘法运算

考虑伽罗华域GF(28)中,每个符号由m =8位数字来表示。其本原多项式为:

undefined

则有C=(A×B)mod p(x),不难推出:

1.3 伽罗华域的求逆运算

除法运算可以分为两部分,先对除数求逆,再与被除数相乘。因此除法运算的重点在于求逆。

由费马小定理及级数展开可得:

可见求逆的基本操作为幂次运算与乘法运算,而幂次结果的各个系数可由上节中乘法运算推出。考虑伽罗华域GF(28),其原理框图[9]如图1所示。

2 RS码的编码方法

对于RS编码,时域和频域算法都比较简单,时域编码需要做一次多项式求模运算,频域编码需要做一次IFFT运算。不同的是,用时域编码编出的码字是系统码,可用于截短编码,而频域编码编出的码字是非系统码,不能用于截短编码。因此,对于截短编码,只能用时域编码的方法。

2.1 时域编码原理

令α为GF(2m)域中的本原元素,则长为n=2m-1,且纠正t=(n-k)/2个错误的RS(n,k)码,其本原RS码的生成多项式是:

式中:gi为GF(2m)域中的元素;b为任意整数。

记待编码的信息多项式:

编码后的信息多项式为:

则RS码可以用式(3)进行编码:

上式可以由伽罗华域加法器、乘法器及2t级的移位寄存器来实现。典型的RS编码器结构如图2所示。

将g(x)中的各个常系数gi转换成自然基,即可求得伽罗华域乘法器系数,可以简化掉中间结果为0的结构,且当b=(k+1)/2时,生成多项式的系数具有对称性,即gi=g2t-i,且g0=g2t=1,可以减少近1/2的伽罗华域乘法器的设计。

2.2 时域编码工作原理

RS编码电路的工作原理如下:

(1) 2t级移位寄存器初始状态全部清零,开关1闭合,开关2处于下面的位置。按照从高次位到低次位的顺序将m(x)的系数输入,一部分直接输出,另一部分进入移位寄存器。

(2) k次移位后,m(x)已全部输出,开关1断开,开关2移到上面位置。此时移位寄存器内保留的数据即为校验位,共n - k位,逐位输出后,与最初的k位信息组成长为n的码字。

(3) 对于缩短码,可使用相同的步骤。

3 RS码的译码方法

对于RS译码,时域译码算法要比频域译码算法复杂得多。在时域译码算法中,解出错位多项式σ(x)后,还需要求出σ(x)的根,以找到错误位置,再根据错误位置求出错误样式;而在频域译码算法中,解出错误多项式后,直接利用简单的线性递归扩展方法就可求得错误图样的频谱,计算步骤比时域译码算法少。借助于FFT算法,相比时域译码,频域译码更为简单快捷。

3.1 频域译码原理

RS码的频域译码涉及伽罗华域的FFT/IFFT,定义如下:

设x={xi|i=n-1,n-2,…,0}为GF(2m)域内的一个矢量,其伽罗华域的FFT为GF(2m)域上的另一个矢量X={Xj|j=n-1,n-2,…,0},则有:

式(4)为伽罗华域的FFT公式,式(5)为伽罗华域的IFFT公式。

设编码端输出的码字为:

由式(2)知,g(αi)=0,i=b,b+1,…,b+2t-1,则:

即RS码FFT的第b至第b + 2t -1谱分量为0。

若信道中有s个可纠正的错误(0 ≤ s ≤ t),令错误图样为e(x)=ei0xi0+ei1xi1+…+eisxis,接收到的码字为r(x),其FFT满足:Rj=Cj+Ej。由式(6)定义接收码字的伴随式为:

若伴随式全为零,则接收码字无错误。否则,引入错误位置多项式:

记Λ={0,0,…,0,σs,σs-1,…,σ0},其IFFT为:

由式(8),式(9)得:

若第i位未出错,则ei=0;若第i位出错,则 λi=0。因此λ·e=0,则其FFT有Λ*E=0。易得:

σ(x)的各系数σj(j=1,2,…,s)可由BM(Berlekamp-Massey)[10] 算法或RiBM(Reformed inverse-free Berlekamp-Messey)算法[11]求出,则:

正确的码字{dn-1,dn-2,…,d0}为R-E的IFFT,dn-1位至dn-k位为信息位,dn-k-1位至d0位为校验位。

当b = 1时,生成多项式g(x)的系数gi将不具有对称性,在时域编码设计时会略增加工作量。而在频域译码时,由式(10)可知,由于不再需要伽罗华域求逆,以及低位频域错误图样递归的模块,可以有效降低频域译码的复杂度。

3.2 频域译码工作原理

RS频域译码的流程图如图3所示。

将接收码元序列进行FFT,得到伴随式s(x),由BM算法求解关键方程,解得σ(x),经递归求得频域错误图样Ej,纠除频域错误后,再进行IFFT,其输出即为译码码元序列[2]。

频域错误图样递归原理框图如图4,图5所示。其中对σs求逆可由图1所示的原理框图得到。

4 仿真及仿真分析

在Xilinx ISE 12.2及ModelSim SE 6.5下,完成对RS(255,239)时域编码的实现与验证。当输入为1～239连续递增的239个自然数时,其16位校验位输出如图6所示,与理论编码结果输出完全相同。

采用Matlab 7.11进行RS(255,239)频域译码的仿真。每个信噪比仿真10 000帧,每一帧内系数b取1～239的随机数,采用QPSK调制,同时仿真Matlab提供的时域译码算法的误码率性能,并与RS(255,239)在QPSK调制下的误码率性能的理论值进行对比。仿真结果如图7所示,复杂度较低的频域译码与复杂度较高的时域译码的误码率性能完全相同。

5 结论

本文提出一种针对通用伽罗华域的快速RS编译码技术,适用于所有RS码本原生成表达式。仿真结果表明,b=1本原生成表达式时RS编译码整系统的复杂度最低,资源占用最小。

摘要：提出一种针对通用伽罗华域的快速RS编译码技术。该编译码技术利用了时域编码、频域译码,适用于通用的RS码本原生成表达式。分析表明,该技术与传统的时域编译码相比,复杂度明显降低,但仍具有相同的编译码能力,同时b=1本原生成表达式的RS编译码整系统的复杂度最低,仿真结果与理论分析一致。

关键词：RS码,时域编码,频域译码,伽罗华域

参考文献

[1]王新梅,肖国镇.纠错码:原理与方法[M].西安:西安电子科技大学出版社,2001.

[2]LIN S,COSTELLO D J JR.Error control coding[M].Second Edition.New Jersey:Prentice Hall,2004.

[3]BLAHUT R E.差错控制码的理论与实践[M].徐秉铮,译.广州:华南理工大学出版社,1998.

[4]韩作生,袁东风.RS码频域编译码的计算机模拟[J].通信学报,1994,15(6):104-112.

[5]侯正信,胡浩.RS码的时域编码/频域译码技术[J].电视技术,2002(1):32-34.

[6]董昌孝.RS码的时域编码频域译码技术[J].西安航空技术高等专科学校学报,2008,26(5):48-49.

[7]余亚芳,张勇,王化深.RS码的译码算法及软件实现[J].现代电子技术,2003,26(22):99-104.

[8]张定云.一种减少RS截短码译码延时的优化设计[J].现代电子技术,2010,33(23):33-38.

[9]沈晓强.有限域乘除法研究与实现[D].长沙:国防科学技术大学,2006.

[10]MASSEY J L.Shift-register synthesis and BCH decoding[J].IEEE Transactions on Information Theory,1969,15(1):122-127.

RS译码篇2

1 RS编码的实现方法

RS码是一种多进制BCH (Bose-ChaudhuriHocquenghem) 码, 在给定每个码字所具有多少冗余量的情况下, RS码具有极大的最小距离。即RS码的最小距离d、信息长度k以及码字长度n满足d=n-k+1。而RS (255 239) 码是在伽罗华 (Galois Field) GF (28) 中运算得到的[2], 编码器实现的关键是伽罗华域乘法器的设计。设计中的乘法是2个有限域中元素的指数相加与255取模。GF (28) 编码参数如下:码长n=255;信息位个数k=239;校验位r=n-k=16;纠错能力t=8;码距d=17。生成多项式为

展开多项式, 合并同类项, 并运用伽罗华域4则运算化简得

根据式 (3) 画出RS编码的电路图, 如图1所示。

n-k级RS编码器主要由一组线性反馈移位寄存器和控制电路组成, 其是n-k=16级编码器, 亦是线性反馈寄存器的反馈系数, reg16寄存器的值与当前输入的信息码元异或得到的结果即为feedback寄存器的值[3]。

编码步骤:

步骤1将所有寄存器清零, 开关放到1上, 则239个信息码元一边依次进入除法电路, 一边依次输出。

步骤2当最后一个信息码进入电路后, 将开关放到2上, 第一个校验位输出。

步骤3校验码按时钟节拍载入寄存器, 并依次输出。当最后一个校验位输出时, 编码结束。

2 RS编码的仿真结果及分析

设计的RS (255 239) 编码器使用Verilog HDL对整个模型进行描述, 以Xilinx FPGA芯片Spartan-6XC6SLX45为硬件平台进行实现, 并利用ISim仿真工具对RS编码进行仿真。

设计的RS (255, 239) 编码器, 信息位239位编码为0, 1, 2, …, 238, 则16位校验位的值为58, 236, 152, 44, 88, 31, 20, 168, 121, 60, 32, 10, 191, 166, 4, 101。设计的RS (255, 239) 编码器的仿真图如图2所示, 当DI_VAL=0时, 输出239个信息位;当DI_VAL=1时, 输出16个校验位。该编码器实现了预期的编码功能。

3 RS译码的实现方法

RS译码主要有时域译码和频域译码, 时域译码一般采用BM迭代算法或欧式算法 (Euclid's Algorithm) 。RS译码中最重要的环节是求解关键方程, 欧式算法在求解关键方程时需进行多项式次数的判断, 因此造成硬件电路复杂, 译码速度下降, BM迭代算法具有快速、消耗资源少、控制电路较为简单等优点。文中改进后的BM迭代原理及以该算法为基础的RS译码器的FPGA实现。RS译码可分为4步: (1) 由接收到的码组计算伴随式。 (2) 求关键方程。 (3) 计算出错误图样。 (4) 由错误图样和接收码组计算出可能发送的码字。图3给出了RS译码器的一般步骤框图[4]。

假定一码字C (x) =cn-1xn-1+cn-2xn-2+…+c2x2+c1x1+c0, 在传送过程中由于传输错误使接收序列变为R (x) =rn-1xn-1+rn-2xn-2+…+r1x1+r0。设错误图样为E (x) , 则R (x) =C (x) +E (x) 。RS码的译码可分为3步: (1) 由接收到的R (x) 计算出伴随多项式S。 (2) 由伴随式计算出错误图样E (x) 。 (3) 由C (x) =R (x) -E (x) 计算得到发送码字, 并完成译码。伴随式是对接收序列R (x) 进行奇偶校验的结果, 用以判断R (x) 是否为有效码字, 若R (x) 为有效码字则伴随式S为零, 任何S的非零值表示R (x) 有错误。为译出一个纠正t个错误的RS码, 伴随式S是2t重的, 即S= (s1, s2, …, s2t-1, s2t) 。

假定发送码字为C (x) =cn-1xn-1+cn-2xn-2+…+c2x2+c1x1+c0。

接收码字为R (x) =rn-1xn-1+rn-2xn-2+…+r1x1+r0。

以E (x) =en-1xn-1+en-2xn-2+…+e2x2+e1x+e0表示含有e个错误的错误图样, 则有R (x) =C (x) +E (x) , 令E (x) =X1Y1+X2Y2+…+Xe-1Ye-1, 其中Xi是第i个错误位置, Yi是第i个错误值。将aj (j=1, 2, …, 2t) 代入j, j=1, 2, …, 2t则有

以上运算均可用流水线结构硬件实现。

初始化时, 所有寄存器置零。经255个周期, 接收完所有255个符号后, 便可得到全部16个伴随式。因整个译码器采用流水线结构, 所以在伴随式计算完后, 产生一个时钟周期有效的“sc_done”信号, 用以启动后续电路进行新的计算。由于在BM模块中, 用到了Λ (x) 与S的卷积求和, 因此本模块将计算出的伴随式序列串行输出。

关键方程的计算采用BM算法, BM算法不仅在RS码的译码中起着关键作用, 且也是目前已知的求序列线性复杂度最快且最佳的方法之一。该算法采用规整的脉动阵列, 硬件实现更为方便。通过求解关键方程, 得到Λ0~Λ8, 其为后续的Chien搜索模块提供了参数。

Λ (x) 可用来搜索错误位置, 具体方法为:依次将a- (n-1) , a- (n-2) , …, a-1, 1代入Λ (x) , 若Λ (a-i) =0, 则在该位置出现误码。Chien搜索模块框图如图5所示。

错误计算多项式Ω (x) =Λ (x) S (x mod x2t) , 因Ω (x) 的结果为mod x2t, 所以Ω (x) 的最高次数为2t-1。因此, Ω (x) 可表示为Ω (x) =Ω0+Ω1x+Ω2x2+…+Ω2t-1x2t-1, Ω (x) 的系数则可分别表示为

从上式可看出, 两个多项式的相乘实质就是两个多项式对应的系数卷积求和[5]。因此, 该运算也可采用FIR滤波技术来实现, 当初始化时, 所有寄存器置零。然后每个时钟周期, 伴随式从S1, S2, …, S2t依次移入寄存器。最终2t个Ωi移位寄存器的内容从左向右依次为Ω2t-1, …, Ω1, Ω0。错误多项式可得, 整个译码过程如图6所示。

该过程完全实现流水线结构, 其中包括伴随式计算、关键方程求解、Chien搜索、Forney算法等模块并行工作。在经过295个固有延迟后, 每个时钟周期均可连续输出经校正的码字[6]。

4 RS译码的仿真结果及分析

因设计的译码器最大纠错能力为8个符号, 该文设定错误情况是第140位到第147位全错, 正确值为140, 141, 142, 143, 144, 145, 146, 147, 错误值为5, 11, 56, 98, 35, 15, 132, 159, 图7是输入到译码器中含8个连续错误码字的255位编码序列, 图8是译码器输出全部纠错以后的编码序列, 由ISim仿真波形图可知, Err_Indicator表示错误标志, 设计的译码器能实现最大的纠错能力[7]。

5 结束语

文中阐述了RS (255, 239) 编译码器的设计原理[8], 并对编码器给出了在ISim中的时序仿真结果, 其结果证明了该编码器设计的正确性。而在对译码器的设计中, 假定出现连续8个误码的情况, 并用ISim对所设计的译码器进行验证, 由时序仿真结果表明, 设计的RS (255, 239) 译码器能实现最大的纠错能力。设计的RS (255, 239) 编译码器达到了预定的目标, 且该编译码器可应用于数据通信和数据存储系统的差错控制中[9]。

参考文献

[1]CARDARILLI G C, PONTARELLI S R M.University of rome“Tor Vergata”[C].Italy:FPGA Oriented Design of Parity Sharing RS Codecs, 2005.

[2]刘大力, 孙文方.一种RS码编译码器的FPGA实现方法[J].电子科技, 2009, 22 (12) :88-90.

[3]王新梅, 肖国镇.纠错码原理与方法[M].西安:西安电子科技大学出版社, 2003.

[4]刘福奇, 刘波.Verilog HDL应用程序设计实例精讲[M].北京:电子工业出版社, 2009.

[5]夏宇闻.Verilog数字系统设计教程[M].北京:北京航空航天大学出版社, 2005.

[6]万力铭.RS译码器的研究与实现[D].长春:长春理工大学, 2008.

[7]朱起悦.RS码编码和译码的算法[J].电讯技术, 1999 (4) :25-30.

[8]普罗科斯.数字通信[M].北京:电子工业出版社, 2001.

RS译码篇3

关键词：RS码,LDPC码,交织编码,迭代译码

随着作战样式和规模的变化, 不同武器系统和平台的信息应用范围不断扩大, 信息共享和互操作的需求成为联合作战的突出问题。研制适用于多军兵种使用的通用型战术数据链成为各国军队的首选, 例如美军的联合战术信息分发系统 (JTIDS) 。采用纠错编码技术是确保数据链安全可靠通信的一种有效手段。然而由于通信距离的需求和通信频段的设置, 通用型战术数据链的信息传输速率一般在10 Kbit/s左右, 如美军最新装备的Link22的单网数据传输速率最高只有12.6 Kbit/s[1]。

Turbo码和LDPC码都是性能接近香农限的好码, 但是Turbo码和LDPC码每个码字的译码都需要迭代译码[2], 而且多是分组结构, 存在一个固定的编译码时延, 只适用于高速率数据传输系统。对于低速率数据传输系统, 若需减小时延则要选择分组长度较短的分组码, 但随着分组长度的减小, 码纠错性能下降很快, 所以纠错码的性能和时延通常是一对矛盾。因此, 如何降低编译码时延, 实现实时通信, 并且具有高性能的纠错能力, 一直是信道纠错编码的研究课题。现行通用型战术数据链采用单一的卷积码或者Reed-Solomon码, 难以满足实际战场复杂电磁环境的需要[3]。本文借鉴传统级联码形式, 受交叠编译码[4,5]和卷积LDPC码随机编码[6]思想启发, 提出一种RS码与LDPC码“交织迭代”编译码结构。

与传统级联码相比, 本文提出的方案, 每一分组信息位和冗余位都参与了RS、LDPC编码, 增强了码组的相关性。根据信道信噪比变化, 采用硬判决译码和联合迭代译码结合的灵活译码方式, 能够在相同编译码时延基础上, 有更高的编码增益, 或在相同编码增益时, 有超低的编译码时延。

1 交织迭代编译码方案概述

传统的RS码与LDPC码串行级联编码如图1, 是先进行RS编码再进行LDPC编码, 这种编码使得LDPC的编码冗余未参加RS编码, 两种码字只是简单的级联, 造成编码性能的损失。而且译码时, 先进行LDPC软译码, 再进行RS硬判决译码, 没有充分利用软信息, 导致译码性能损失。

RS码与LDPC码交织迭代编译码方案的基本原理是:每个码字校验位分为两部分, 编码时, 第一部分校验位由LDPC编码生成, 既与本码字信息位有关又与先前多个码字有关, 而第二部分校验位由RS编码产生, 只与本码字信息位和第一部分校验位有关, 这样增加了前后码字之间的约束联系, 而且信息位和校验位都参与了编码, 增强了码字的相关性;而在译码时, 若信道信噪比较高, 可以只进行RS译码, 若信噪比较低, 可以采用联合迭代译码方式, RS码用自适应置信传播 (ABP) 译码[7], LDPC码用LLR-BP译码, 使得RS码字与LDPC码字之间的软信息能相互传递, 提高整体的译码性能。

2 交织迭代编译码方案的交织编码

RS码与LDPC码交织迭代编译码方案的编码过程如图2所示。

传统的串行级联编码是先进行外码RS编码, 再进行内码LDPC编码。译码时先进行内码译码, 再进行外码译码。和传统的级联编码不同, 本方案中RS编码和LDPC编码是交替进行的。在图1中, r是LDPC编码冗余, r'是RS编码冗余。收到一个k位信息位后, 就可以形成一个分组进入编码缓冲区最右端, 并预留LDPC编码冗余r和RS编码冗余r'。在编码缓冲区内, 首先进行LDPC编码得到编码冗余r。从图2中可以看出, 缓冲区中的已完成编码的码组都参与了LDPC编码, LDPC编码信息位是从所约束的码字按一定规则选取的, 生成校验位为最右端分组码中的r。然后将新得到的r位冗余与分组内的k位信息当作RS编码的信息位, 进行RS编码生成冗余r'。当收到新的k位信息位后重复上面过程进行LDPC编码和RS编码。

本方案中, LDPC编码器的冗余r参与了RS编码, RS编码冗余r'参与了LDPC编码, 因此本文提出的编码方案叫做LDPC码与RS码的“交织”编码。

3 交织迭代编译码方案的迭代译码

3.1 LDPC码与RS码迭代译码算法分析

LDPC译码采用对数似然比测度下的BP算法, 即LLR BP算法[2], RS译码采用自适应置信传播 (ABP) 译码[7]。

其中, RS码ABP迭代译码算法是借鉴LLR-BP译码而发展来的。用二进制形式b2b= (b1, b2, …, bnm-1, bnm) 表示RS码字, 采用BPSK调制, 发送的矢量x=-2b2b+1, 经过AWGN信道, 接收矢量为r=x+n, n是方差为σ2的高斯白噪声, 接收矢量的可信度由对数似然比 (LLR) 表示, 即L (0) (bi) =2ri/σ2。详细的ABP算法描述如下:

(1) 初始化:L (0) (bi) =2ri/σ2, 设定衰减系数u=0.1, 最大迭代次数jmax。

(2) 校验矩阵自适应调整:根据比特可信度信息L (j) 进行高斯消去, 将矩阵化成单位阵的形式。

(3) 可信度更新:计算外部信息L (j) ext, 并计算校验式L (j+1) =L (j) +u L (j) ext。

(4) 硬判决:如果L (j+1) (bi) >0, 则, 否则。

(5) 终止条件:或者达到最大迭代次数, 否则回到步骤 (2) , 重新迭代。

从上述译码过程可以看出, ABP译码和LLR-BP译码初始消息都是接收信息的对数似然比。ABP迭代译码算法在矩阵自适应调整后, 可信度的更新过程与LLR-BP译码的可信度更新过程一致, 迭代译码的目的都是逼近最佳后验概率。ABP译码的最大迭代次数不同, 对译码性能有影响。以Eb/No代表每比特的信噪比, 单位d B, 不同最大迭代次数下RS (255, 223) 的ABP译码性能如图3。ABP译码算法运算量与最大迭代次数成线性关系, 从图3可以看出, RS (255, 233) 在ABP最大迭代次数设定为5时, 在误比特率为10-3时比设定为3时有0.3 d B增益, 与最大迭代次数为10时只有0.1d B的差距。RS (255, 233) 在ABP最大迭代次数为5时, 译码性能和复杂度之间能取得最佳的平衡。

3.2 迭代译码方案

若信道信噪比高, 对接收到的分组数据仅进行RS译码, 直接输出k位信息。并将接收到的码字的对数似然比信息输入到译码缓冲区。

若信道信噪比低, 在译码缓冲区内, 根据接收到的码字信息, 进行LDPC和RS的联合迭代译码。详细过程如图4所示, 待译码组进入译码缓冲区最右端, 首先进行RS码的ABP译码, 更新码字软信息。然后, 提取该码组中r所组成的LDPC码信息位和校验位, 进行LLR-BP译码, 更新信息节点的软信息, 将更新后的软信息返回到RS码组中。最后, 最右端的码组再进行ABP迭代译码, 最终得到译码输出的码字, 极大提高译码的正确性。

4 性能仿真与分析

仿真采用RS (255, 223) 码和码长1 024、码率1/2的LDPC码, 即每个码字信息位k=1 272, 码长n=2 040, 整体码率为0.62。设定编码缓冲区内码字个数为5, LDPC编码时从前4个码字和待编码码字的信息位中等间隔选取512位信息位。在平稳无记忆AWGN信道下, 采用BPSK调制。根据3.1节的仿真分析, 设定ABP最大迭代次数为5。仿真结果如图5所示。

从图5中可以看出, 在信噪比较高时只进行RS码的硬判决译码, 在误码率在10-5, 能获得3.6 d B。在信噪比较低, 单纯的硬判决译码无法满足对译码性能的要求时, 要在译码缓冲区进行迭代软译码, 在误码率在10-5时, 迭代软译码比单纯的RS软判决译码有近0.9 d B增益, 比单纯RS硬判决译码有近1.6 d B增益。

理论分析认为, 本文提出的编译码方案增加了前后码组的相关性, 既有利于抗突发错误, 又有利于抗随机错误。而在译码时, 相对于单纯的RS软判决译码, 通过LDPC译码后更新RS码软信息, 相当于提高了RS码译码的初始软信息的准确度, 从而有效提高RS码译码性能。

虽然采用迭代译码必然造成译码复杂度的上升和译码延时的增加。但是, 在实际信道传输时, 绝大概率下, 信道的信噪比较高, 只用RS的硬判决译码进行译码就可以满足误码率10-5的性能要求。只有在很小概率情况下, 需要进行迭代软译码。因此, 从总体上看, 这种交织迭代编译码结构能在保证译码性能的前提下, 有效减小译码时延。

5 结语

本文提出的RS码与LDPC码的交织迭代编译码方案, 相对于传统串行级联编码方案有较好的结构优越性。采取交织编码方式有效提高码字相关性和抗误码能力, 通过采取RS硬判决译码和RS与LDPC联合迭代软译码相结合的方式, 能在保证译码性能的前提下, 有效缩短系统译码时间, 实现性能和译码延时的良好折中。

进一步的研究有两个方面:一是对于结构中使用的不同码字的探索, 如RS码对不同码长的码字的选取, LDPC码采用卷积LDPC码对编译码时延的减小等;二是对于交织编码时约束长度的优化探索, 不同的约束长度对于码字抗突发错误和随机错误的能力影响不同, 应研究最佳的约束长度。

参考文献

[1] 骆光明.数据链—信息系统连接武器系统的捷径.北京:国防工业出版社, 2008

[2] Zengyou S, Jin Z, Juan D.Research of LDPC decoding based on LLR BP algorithm.Cross Strait Quad-Regional Radio Science and Wireless Technology Conference (CSQRWC) , 2011.IEEE, 2011;2 :889—892

[3] 宋飞飞.无人机数据链信道编码方法研究.计算机测量与控制, 2012;20 (006) :1602—1605

[4] 刘铭, 史治平, 周亮.一种新的缩短RS码迭代译码方案.电讯技术, 2008;48 (03) :37—39

[5] 朱辉, 周亮, 伍佳佳.基于三个戈莱码码字的交叠编码和译码.通信技术, 2009; (012) :24—26

[6] Linhua M A, Jun L I U, Chang Y.Irregular low-density convolutional codes.IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2005;88 (8) :2240—2243

RS译码篇4

IEEE 802.16d[1] 是固定宽带无线接入接口的标准协议。Reed-Solomon 编码是其中信道编码的一部分,主要用于纠正信道中的突发错误。为了能够适应不同的信道条件,协议中使用了截短和删除的RS码,以提供不同的码率和纠错能力。本文在传统的RS译码的基础上,提出了一种适用于IEEE 802.16d 标准的RS译码实现方式。

1 RS译码的原理

802.16d 中所有的RS码都是由定义在GF(28)上的RS(N=255,K=239,T=8)码得到的。

其中,N为编码后码字的字节长度,K为编码前输入信息的字节长度,T为能够纠错的最大字节数。

域本原多项式为:

$p (x) = x^{8} + x^{4} + x^{3} + x^{2} + 1$

码生成多项式为:

$g (x) = (x + λ^{0}) (x + λ^{1}) (x + λ^{2}) \dots (x + λ^{2 Τ - 1}), λ = 02_{Η E X}$

如果输入的信息为m(x),利用循环码的编码公式,可以得到码字c(x)。

$c (x) = m (x) x^{Ν - Κ} + [x^{2 Τ} m (x)] m o d g (x)$

得到的码字经过截短信息位和删除校验位后得到需要的RS码。802.16d协议中支持的RS码有RS(32,24,4),RS(40,36,2),RS(64,48,8),RS(80,72,4),RS(108,96,6),RS(120,108,6)。

由于RS码经过了截短和删除,所以不能适用普通的RS译码算法,而必须使用能够纠错纠删的译码算法。RS译码的算法很多,有时域译码和频域译码之分。本文采用基于修正的欧几里德算法(MEA)的时域译码算法。

纠错纠删的RS译码算法通常分为以下几步[2]:

(1) 根据接收码字R(x)计算出伴随式S(x);

(2) 根据删除位置计算删除位置多项式Λ(x);

(3) 由伴随式S(x)和删除位置多项式Λ(x)计算出修正的伴随多项式T(x);

(4) 由Λ(x)和T(x),通过MEA算法解关键方程,得到错误位置多项式σ(x)和错误值多项式ω(x);

(5) 利用钱搜索(Chien search)计算出σ(x)的根,从而得出错误位置;

(6) 根据ω(x)和Λ(x)计算出错误/删除位置多项式Ψ(x),再利用Forney公式计算出错误值和删除值,并与原来的码字相加,得到正确的码字。

2 RS译码器的硬件结构

RS译码器使用四级流水线结构,以提高系统的吞吐率,满足实时性传输的要求。

RS译码器的硬件框图如图1所示。

2.1 伴随式计算

根据接收到的码字R(x),可以计算出伴随多项式S(x):

$S (x) = \sum_{k = 0}^{2 Τ - 1} S_{k} x^{k} ‚ S_{k} = R (x) |_{x = α^{k}}, α = 02_{Η E X}$

在计算之前需要先将截短的信息位位置和删除的校验位位置填充零,得到完整的RS(255,239)码字,然后再去计算伴随式。根据IEEE 802.16d的协议,输入信息经过编码后,先发送校验位信息,再发送信息位。所以接收端收到的码字经过填充后如图2所示:

对于普通的RS译码器,要求信息位在接收码字R(x)的高次项,校验位在低次项。但经过观察可知,图2所示的排列顺序可以看作正常顺序的码字经过循环移位得到。因为RS码是一种循环码,根据循环码的性质,码字经过任意的循环移位后仍是对应码的一个码字。所以,可以把接收到的码字按照原始顺序输入译码器,不需要将其转换为正常顺序。

伴随式的计算可以通过脉动阵列实现[3]。将补零后得到的完全的RS(255,239)码字顺序输入脉动阵列,在全部输入完成后寄存器中就是所要的伴随多项式的系数。

在802.16d协议中,RS码的码长都比较短。对于RS(n,k)码,会有255-n个时钟周期电路的输入为零,使伴随式计算模块的延时很大。文献[4]提出了一种使硬件电路的延时只依赖于实际码长n的方法。但是该方法需要对接收码字的校验位和信息位互换,需要额外的缓冲区,并且互换本身就增加了延时,使译码器和前面电路的接口变得复杂。我们注意到,对于每一个基本单元,在其输入为零的情况下,经过255-n个时钟周期,寄存器的值连续和系数相乘255-n次。所以,在校验位输入完毕后,对于第一个信息位,将系数换成原系数的255-n次方即可。经修改后的硬件结构如图 3所示,事先计算出每个系数的255-n次方值,和原系数作为选择器的输入端,在信息位的第一个字节时切换系数,在其他位置使用原系数。经修改后使电路消除了空转周期,可以允许码字连续输入,减少了255-n个时钟延时。

2.2 删除位置多项式计算

通常,删除的位置由解调器给出,根据删除位置,可以得到删除位置多项式:

$Λ (x) = \prod_{α^{- i} \in Λ} (x - α^{- i})$

其中i为删除位置。

可以用多项式展开电路来计算此多项式,具体电路结构参见文献[2]。对于802.16d系统,所有RS码的删除位置都是确定的,所以每种模式下的删除位置多项式可以通过事先计算确定,存于ROM中,在需要时读入即可。在按照前述的码字排列顺序下,各种模式下的Λ(x)如表1所示。

由表1可知,所有多项式的常数项都为1,不需要存储;而且后两种RS模式的Λ(x)相同,只需要存储一个,所以,只需要32 B的存储空间即可,省去了利用多项式展开电路计算删除位置多项式的开支。

2.3 修正伴随多项式计算

修正的伴随多项式T(x)由下式得到:

$Τ (x) = S (x) Λ (x) m o d x^{2 Τ}$

多项式相乘相当于其系数的卷积,所以可以通过卷积电路(FIR滤波器结构)实现T(x)的计算。S(x)由伴随式模块并行输出,不需要做串并转换,直接用来初始化滤波器的系数。然后,从ROM中顺序载入Λ(x)的系数作为滤波器的输入,滤波器的输出便是T(x)的系数。同时,Λ(x)也顺序输出,恰好作为下一个模块的输入。该部分的结构框图如图4所示。

2.4 关键方程求解

错误位置多项式σ(x)和错误值多项式ω(x)可以通过解关键方程T(x)σ(x)=ω(x)mod x2T来得到。文献[2]提供了一种采用修正的欧几里德算法(MEA)解关键方程的实现方法,并且通过改变算法的初始值直接计算出错误/删除位置多项式Ψ(x)。MEA算法本质上是基于多项式分解原理,求两多项式最大公因子的迭代算法。通过将迭代过程使用基本单元实现,可以使用脉动阵列实现整个计算过程。具体的算法过程可以参见文献[2]。

下面讨论需要的基本单元的个数。MEA算法迭代完成,需要(2T)2=256个时钟周期。如果能够连续解码,在最差的情况下,需要的基本迭代单元的个数为 256/n=256/32=8个。但是,根据IEEE 802.16d协议,不论哪种RS编码方式,每个RS块都恰好对应一个OFDM符号,而且每个OFDM符号含有256个子载波,即使在取最小的保护间隔1/32的情况下,每个OFDM符号至少含有264个子载波。所以从整体系统考虑,解调模块给出的RS码流并不是严格连续的。每个RS分组至少持续264个时钟周期,在解调和解码模块采用相同时钟的条件下,只需要一个基本单元足以完成整个迭代过程。

2.5 错误位置和错误值计算

通过对Ψ(x)求根可以得到错误位置。工程上通常用钱搜索算法求根,即将有限域中每个元素代入多项式求值,判断多项式的值是否为零。如果Xi是方程的根,则代入Forney公式 $e_{i} = - \frac{ω (X_{i}^{- 1})}{Ψ^{'} (X_{i}^{- 1})}$ ,可得到相应的错误值。将错误值加到接收码字的相应位置,便得到正确的码字。

钱搜索模块和错误值计算模块的硬件结构与计算伴随多项式相似,都是对多项式求值,具体实现方法可以参见文献[2]。

和2.1所述的方法类似,在计算之前,先将第i个寄存器初始化为αi(255-n),可以减少255-n个时钟周期的延时。

3 RS译码器性能分析

3.1 译码延时

对于RS(n,k,t)码,伴随式计算模块延时n个时钟周期;修正伴随式计算模块延时(16-2t)个时钟周期;关键方程求解模块延时256个时钟周期;钱搜索和错误值计算模块延时k个时钟周期,再为流水线的设计和硬件实现20个时钟余量,可得总的延时为(n+16-2t+256+k+20)个时钟周期。

3.2 译码速度

由于采用了流水线结构,整个译码器的数据处理速度取决于流水线中最慢模块的处理速度。在本设计中,MEA模块的速度最慢,处理完一个RS块需要256个时钟周期。

对于不同的系统时钟,译码器的实际延时和译码速度会有所不同。

本设计实际应用于8 M带宽的WiMAX系统中,系统时钟为32 M。在该应用环境下,在RS(120,108,6)模式下系统延时最大,为(120+16-2*6+256+108+20)/32=15.9 μs。在RS(32,24,4)模式下处理速度最低,为[(24*8)/256]*32 M=24 Mb/s。

4 结语

本文通过对IEEE 802.16d协议中RS码的特点分析,提出了一种适用于该标准的RS译码实现方法。本文所设计的RS译码器使用Verilog语言实现,在ModelSim 6.0环境下仿真通过。使用Synplify 8.1综合,ISE 8.1布局布线,并在Xilinx VirtexⅡ-8000系列FPGA上验证通过。该模块单独综合布线时可以达到80 M工作时钟,占用资源9%,满足系统要求。

摘要：Reed-Solomon(RS)码是IEEE 802.16d标准中信道编码的重要组成部分。通过对标准中RS码特点的分析,对传统的RS译码器进行改进,提出了一种适用于该标准的RS译码方法。利用循环码的性质,改进伴随式计算模块,减少延迟时间;利用RS码中已知删除位置的特点,简化删除位置多项式计算电路;通过对RS码实际应用环境的分析,减少利用迭代方法解关键方程时所需的基本单元数目。最终利用Verilog语言实现硬件电路,在FPGA上验证通过并应用于WiMAX802.16d系统。

关键词：RS码,IEEE802.16d,信道编码,FPGA

参考文献

[1]IEEE Standard 802.16d.Air Interface for Fixed BroadbandWireless Access Systems[S].New York Institute of Elec-trical and Electronics Engineers,2004.

[2]Shao H M,Reed I S.On the VLSI Design of a Pipeline ReedSolomon Decoder Using Systolic Arrays[J].IEEE Transac-tions on Computer,1988,37(10):1 273-1 280.

[3] Shao H M,Truong T K.A VLSI Design of a Pipeline Reed-Solomon Decoder [J].IEEE Transactions on Computer,1985,34:393-403.

本文来自古文书网(www.gwbook.cn)，转载请保留网址和出处

基本力学性能02-17