RS码编码及译码.docx

西安电子科技大学学报(自然科学版) OURNAL OF XIDIAN UNIVERSITY RS 码的编码和译码算法的实现摘要: RS 码是对突发错误具有良好纠错能力的通信信道编码。本文主要讨论了 RS 码的编码和译码, 主要推导了伽罗华域的生成方法和 BM 迭代译码算法。关键词: RS 码;伽罗华域;编码; BM 译码 1 RS 码的基本介绍 RS 码是一类有很强纠错能力的 BCH 码,也是一类典型的代数几何码[ 1] ,是由里德和索罗蒙于 1960 年构造出来的。 RS 码是非二进制 BCH 码的一个重要子类,是一类最大距离可分组码。 RS 码已经被广泛应用于通信和存储系统中,以进行差错控制。的q 进制的 BCH 码是 q 进制 BCH 码中最重要的一个子类。这一子类的编码被称为里德—所罗门(Reed-Solomon,RS) 码。令α为 GF(q) 中的本原元。符号取自 GF(q) 、纠正 t 个错误的 RS码, 其生成多项式 g(x) 以α,,…, 为其全部的根。由于是 GF(q) 中的元素,因此其最小多项式(x) 即为。因此,得到+ 其中 GF(q) ,由于α,,…,是-1 的根,因此-1 能够被 g(X) 整除。所以, g(X) 将生成恰好具有 2t个奇偶校验符号、长度为 n=q–1的q 进制循环码[ 2] 。符号取自 GF(q) 、纠正 t 个错误的 RS 码具有如下参数: 分组长度: n=q-1 奇偶校验符号数:n–k= 2t 维数:k=q–1– 2t 2: RS码的编码和译码算法的实现最小距离:= 2t+1 于是,我们看到 RS 码具有如下特性:(1 )码的长度比码字母表的大小少 1;(2 )最小距离比奇偶校验符号数多 1。最小距离比奇偶校验符号数多 1 的编码称为极大最小距离可分( Maximum Distance Separable , MDS )码。 2 伽罗华域元素和二进制代码表的生成伽罗华域是以 q= 为元素的有限域, p 为素数, m 为正整数。其特征是域中各元素可以用基本元素及其表达式来表示,并且域中各元素经过域内运算,其结果仍为域内元素。在计算机中,数据是以二进制的形式存在,所以 p 通常取值为 2 [ 3] 。在计算机的编程过程中,最常生成的是 GF() 域,共含有 256 个元素, 其中除 0,1 之外的-2 个元素都是由本原多项式 P(X) 生成。本原多项式的特征是得到的余式等于 0。在我们编写 RS 编码程序之前,必须首先生成 GF() 域中元素与二进制数之间的对照表。方法就是用 GF() 中的元素 0,…, 分别模 2 除以本原多项式 P(X) 。这样一来就建立了 GF() 域中元素与二进制数之间的一一对应的关系。为了使用方便,存储一个字节的十进制整数形式,避免存储成二进制数组的形式。在本次仿真中 m=4 ,多项式 P(X) =1+X+是 GF(2) 上的一个本原多项式。设 P(α)= 1+ α+=0 即=1+α,用这个关系式可以构造 GF() 。在构造 GF() 元素的多项式表示中重复使用等式=1+α。例如, =α﹒=α(1+ α)= α+ : RS码的编码和译码算法的实现=α﹒=α(α+)= =α﹒=α()==+1+ α=1+ α+ 将元素和相乘,只要简单的把它们的指数相加并且使用关系式=1 。在 RS