RS码的基础知识

.,RS编码的基础知识,报告人：李睿报告时间：2013年10月12日桂林电子科技大学信息安全研究所,.,目录,2,1,3,代数引论,RS码的译码,近期的工作安排,.,1代数引论,群一个定义了二院运算*的集合G如果满足一下的条件，则称其为群：i.二元运算*满足结合律；ii.G中包含一个元素e，使得对G中任意元素a，有iii.对G中任意元素a，在G中存在另一个元素,满足交换群如果群G二元运算同时满足下面的条件，则称群G是交换群：对G中任意的a和b，有a*b=b*a,.,域设F为一组元素的集合，在其上定义了加法“+”和乘法“.”两种运算。如果满足下列条件，则集合F与这两种运算一起成为域：i.在加法下F是一个交换群。ii.F中的非零元素在乘法下构成一个交换群。iii.乘法对加法满足分配率，即对F中任意的三个元素a，b和c，有,伽罗华域（GF（q）有限域也称为伽罗华域,.,域元素的阶必然存在一个使得的最小正整数n，这个n就称为域元素a的阶。本原元在有限域GF（q）中，如果a的阶为q-1，则非零元素a被称为本原元。性质：本原元的幂生成了GF(q)中的所有的非零元素。本原多项式GF(2)上的m次多项式p(x)若不能被GF(2)上任意次数小于m且大于0的多项式整除，则称p(x)在GF(2)上是不可约的。M次不可约多项式p(x)若满足能被p(x)整除的的最小正整数n为，则称p(x)为本原多项式。,.,定理：设f(x)是一个以GF(2)中元素为系数的多项式，是GF(2)扩域中的一个元素。如果是f(X)的一个根，则对任意,也是f(X)的根。元素称为的一个共轭。,最小多项式为GF()中的任意元素，令为GF(2)上满足的最低次数多项式，则多项式称为的最小多项式,.,由生成的GF()中元素的最小多项式,.,生成多项式,在（n，k）的RS中，存在唯一的n-k次多项式g(x)，使得每一个码多项式c(x)都是g(x)的倍式.g(x)称为RS码的生成多项式。,其中：n为码长，k为信息位,一般情况下：,是本原多项式p(x)的根,.,2RS码的译码BCH码BCH码是一种获得广泛应用的能够纠正多个错码的循环码。RS码RS码是一类具有很强纠错能力的多进制BCH码。符号取自GF(q)，纠t个错误的RS码具有以下参数：,分组长度：n=q-1,奇偶校验符号数：n-k=2t,最小距离：,.,RS译码RS码的译码分成以下5步：,由接收的r(x)求得伴随多项式,由求得错误位置多项式,用钱搜索解出的根，得到错误位置数，确定错误位置。,由错误位置数求得错误值，从而得到错误图样,完成纠错,.,校验矩阵,接收值,1）求伴随多项式,.,所以：,或表示为,2）BM迭代算法求错误位置多项式,BM迭代算法利用S伴随矩阵得到错误多项式,迭代步骤如下：,a由初始值,开始迭代,其中:是错误位置多项式的次数，为第j步和第j+1步的差值,.,b若则有并计算，再进行下一次迭代若，则找出之前的某一行，它在所有行之前各行中的最大，且，于是按,计算,这就是第步的解,c计算，重复步进行下一步迭代，这样迭代次后得到的即为所求的。,.,3）用钱搜索解出的根，得到错误位置数。（上一步已经求得）。,下面介绍钱搜索错误位置数的步骤：,对接收向量,进行逐比特译码。最高位比特被首先译码。为了译，译码器检验是否是错误位置数；也就等价于检验于检验它的倒数是否是的根。如果是，则：,.,因此，为了译，译码器需要构造，,。如果，则是错误位置数，并且是错误位，否则，是正确位。,为了译，译码器需要构造，并校验和式：,如果和式为0，则是的根，且是错误位；否则，是正确位。,.,4）由错误位置数求得错误值，从而得到错误图样。RS码错误值（）计算公式：,求出,为,的导数形式,被称为错误