新浪博客
也适合于纠正突发错误。纠正t
个错误RS 码有如下参数:
每个符号比特数 m
每个符号可以看成是有限域GF (2m) 中的一个元素
码长 n = 2m - 1
信息段 k符号
监督段 n - k = 2t 符号
最小码距d = 2t + 1
RS 码用于纠正的突发错误图样有:
总长度为b1 = (t - 1) m + 1 比特的单个突发
总长度为b2 = (t - 3) m + 1 比特的两个突发
…
总长度为bi = (t - 2i + 1) m + 2i - 1 比特的i个突发
RS 码的编码器和译码器可以用专门的硬件芯片实现,若用DSP 芯片来实现的话,需讨论有限域GF (2m)的结构,RS 码的编码和译码算法,并推导出RS 码生成多项式。
RS 码编码算法
我们将信息段看成信息码多项式,Cn - 1 Xn -1 + Cn - 2 Xn - 2 + …+ Cn - kXn - k 用信息码多项式去除以生成多项式,所得的余数是监督码多项式,将监督码多项式置于信息码多项式之后,形成RS 码。
纠t 个符号错误的RS 码的生成多项式G( X) = Π ( X +αj) = ΣgiXi ,α是有限域GF ( 2m ) 的域元素。码字多项式为
Cn - 1 Xn - 1 + Cn - 2 Xn - 2 +…+ Cn - kXn - k +Cn - k - 1 Xn - k - 1 + …+ C1 X + C0 。
RS 码译码算法和流程
纠错码的译码是这种编码能否得到应用的关键,译码算法通常比编码算法要复杂得多。RS 码译码是从计算接收字的伴随式入手,我们用多项式c (X) 表示码字,e (X) 表示有γ(γ≤t ) 个错误的错误图样, r (X) 表示接收字, r( X)=c( X)+e( X) , e ( X) = Y1 X1+ Y2 X2 + ⋯+ YγXγ ,Xi 是第i 个差错的错误位置,定义Xi = αi , Yi 是它的错误值。
(1) 根据接收到的码多项式计算伴随式S由于RS 码是由有限域GF (2m) 上某个
元素的2t 个相继幂次为根的生成多项式所定义的,用这些根去估算一个码字多项式,从本质上说,译码器就是求解有限域GF(2m) 上的这组伴随式非线性联立方程,由伴随式值S 找出错误图样时,先确定错误位置Xi ,再求错误值YI。一般避免直接求解错误位置Xi ,而代之以间接法。
(2) 采用MasseyFSR 算法,确定错误位置多项式,1960 年Peterson 提出二进制BCH 码译码的第一个有效算法。Peterson 证明,不必计算上面的非线性联立方程组,而是将其转换为一组线性方程式,用错误位置多项式σ(x) 对其求解。
Peterson 采用直接法解牛顿恒等式,需要完成大量的乘、除运算来求出错误位置多项式σ(x) 的系数,当错误数t ≥6 时,繁琐而低效。1965 年Berlekamp 提出求错误位置多项式的牛顿恒等式迭代算法,易于在计算机上实现; 1969 年Massey 提出求错误位置多项式的另一种迭代算法- 线性反馈寄存器算法简称FSR 算法;目前用得最普遍。当差错数大于t 时,在算法结束可能得到L > t ,此时应通告检出差错,所对应的错误位置多项式是不正确的。
(3) 采用钱氏搜索法,寻找错误位置,为了确定错误位置多项式σ( x) 的根,即标明错误位置,1964 年钱闻天提出搜索错误位置的方法, 不需直接求解σ( x) 。
对于差错数大于t 时,Massey FSR 算法也可能得到阶数小于t 的错误位置多项式σ(x) ,假设错误位置多项式σ( x) 阶数为l ,这时在很多情况下,钱氏搜索得到的根少于l ,也应通告检出差错。
(4) 计算错误值
当得到错误位置值后,将其代入伴随式非线性联立方程,求错误值,变为求解线性代数方程组。
(5) 将所得的错误值加到相应的错误位置上,完成纠错。 （转自通信仿真网：http://www.comsim.cn/read.php?tid=64）
每个符号比特数 m
每个符号可以看成是有限域GF (2m) 中的一个元素
码长 n = 2m - 1
信息段 k符号
监督段 n - k = 2t 符号
最小码距d = 2t + 1
RS 码用于纠正的突发错误图样有:
总长度为b1 = (t - 1) m + 1 比特的单个突发
总长度为b2 = (t - 3) m + 1 比特的两个突发
…
总长度为bi = (t - 2i + 1) m + 2i - 1 比特的i个突发
RS 码的编码器和译码器可以用专门的硬件芯片实现,若用DSP 芯片来实现的话,需讨论有限域GF (2m)的结构,RS 码的编码和译码算法,并推导出RS 码生成多项式。
RS 码编码算法
我们将信息段看成信息码多项式,Cn - 1 Xn -1 + Cn - 2 Xn - 2 + …+ Cn - kXn - k 用信息码多项式去除以生成多项式,所得的余数是监督码多项式,将监督码多项式置于信息码多项式之后,形成RS 码。
纠t 个符号错误的RS 码的生成多项式G( X) = Π ( X +αj) = ΣgiXi ,α是有限域GF ( 2m ) 的域元素。码字多项式为
Cn - 1 Xn - 1 + Cn - 2 Xn - 2 +…+ Cn - kXn - k +Cn - k - 1 Xn - k - 1 + …+ C1 X + C0 。
RS 码译码算法和流程
纠错码的译码是这种编码能否得到应用的关键,译码算法通常比编码算法要复杂得多。RS 码译码是从计算接收字的伴随式入手,我们用多项式c (X) 表示码字,e (X) 表示有γ(γ≤t ) 个错误的错误图样, r (X) 表示接收字, r( X)=c( X)+e( X) , e ( X) = Y1 X1+ Y2 X2 + ⋯+ YγXγ ,Xi 是第i 个差错的错误位置,定义Xi = αi , Yi 是它的错误值。
(1) 根据接收到的码多项式计算伴随式S由于RS 码是由有限域GF (2m) 上某个
元素的2t 个相继幂次为根的生成多项式所定义的,用这些根去估算一个码字多项式,从本质上说,译码器就是求解有限域GF(2m) 上的这组伴随式非线性联立方程,由伴随式值S 找出错误图样时,先确定错误位置Xi ,再求错误值YI。一般避免直接求解错误位置Xi ,而代之以间接法。
(2) 采用MasseyFSR 算法,确定错误位置多项式,1960 年Peterson 提出二进制BCH 码译码的第一个有效算法。Peterson 证明,不必计算上面的非线性联立方程组,而是将其转换为一组线性方程式,用错误位置多项式σ(x) 对其求解。
Peterson 采用直接法解牛顿恒等式,需要完成大量的乘、除运算来求出错误位置多项式σ(x) 的系数,当错误数t ≥6 时,繁琐而低效。1965 年Berlekamp 提出求错误位置多项式的牛顿恒等式迭代算法,易于在计算机上实现; 1969 年Massey 提出求错误位置多项式的另一种迭代算法- 线性反馈寄存器算法简称FSR 算法;目前用得最普遍。当差错数大于t 时,在算法结束可能得到L > t ,此时应通告检出差错,所对应的错误位置多项式是不正确的。
(3) 采用钱氏搜索法,寻找错误位置,为了确定错误位置多项式σ( x) 的根,即标明错误位置,1964 年钱闻天提出搜索错误位置的方法, 不需直接求解σ( x) 。
对于差错数大于t 时,Massey FSR 算法也可能得到阶数小于t 的错误位置多项式σ(x) ,假设错误位置多项式σ( x) 阶数为l ,这时在很多情况下,钱氏搜索得到的根少于l ,也应通告检出差错。
(4) 计算错误值
当得到错误位置值后,将其代入伴随式非线性联立方程,求错误值,变为求解线性代数方程组。
(5) 将所得的错误值加到相应的错误位置上,完成纠错。 （转自通信仿真网：http://www.comsim.cn/read.php?tid=64）