RS码的基础知识PPT课件

1、目录目录 代数引论代数引论RSRS码的译码码的译码近期的工作安排近期的工作安排第1页/共19页1 代数引论 群 一个定义了二院运算*的集合G如果满足一下的条件，则称其为群： i.二元运算*满足结合律； 中包含一个元素e，使得对G中任意元素a，有 iii.对G中任意元素a，在G中存在另一个元素 ,满足 交换群 如果群G二元运算同时满足下面的条件，则称群G是交换群：对G中任意的a和b，有 a*b=b*a aaeea *eaaaa *a第2页/共19页cabacba)(域设F为一组元素的集合，在其上定义了加法“+”和乘法“ .”两种运算。如果满足下列条件，则集合F与这两种运算一起成为域：i.在加法下

2、F是一个交换群。中的非零元素在乘法下构成一个交换群。iii.乘法对加法满足分配率，即对F中任意的三个元素a，b和c，有伽罗华域（GF（q）有限域也称为伽罗华域第3页/共19页 域元素的阶 必然存在一个使得 的最小正整数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(

3、x)为本原多项式。1na1nX12mn第4页/共19页0ll2l2定理：设f(x)是一个以GF(2)中元素为系数的多项式， 是GF(2)扩域中的一个元素。如果 是f(X)的一个根，则对任意 , 也是f(X)的根。元素 称为 的一个共轭。最小多项式 为GF( )中的任意元素，令 为GF(2)上满足 的最低次数多项式，则多项式 称为的 最小多项式m2)(X0)()(X第5页/共19页 共轭根 最小多项式 842,14 XX01X1X12963,1234XXXX105,12 XX1413117,134XX由 生成的GF( )中元素的最小多项式1)(34XXXp42第6页/共19页生成多项式在（n，k

4、）的RS中，存在唯一的n-k次多项式g(x)，使得每一个码多项式c(x)都是g(x)的倍式.g(x)称为RS码的生成多项式。其中：n为码长，k为信息位一般情况下：).()()(22txxxxg是本原多项式p(x)的根第7页/共19页2 RS码的译码 BCH码 BCH码是一种获得广泛应用的能够纠正多个错码的循环码。 RS码 RS码是一类具有很强纠错能力的多进制BCH码。 符号取自GF(q)，纠t个错误的RS码具有以下参数： 分组长度： n=q-1奇偶校验符号数：n-k=2t最小距离：12min td第8页/共19页 RS译码译码 RS码的译码分成以下5步： er jSjS)(X)(X由接收的r(

5、x)求得伴随多项式由 求得错误位置多项式用钱搜索解出 的根，得到错误位置数，确定错误位置。 由错误位置数求得错误值，从而得到错误图样完成纠错第9页/共19页校验矩阵接收值1）求伴随多项式第10页/共19页)(),.(),(22tTRRRRHS所以：或表示为tjRSjj2,.,2 , 1),(2）BM迭代算法求错误位置多项式 BM迭代算法利用S伴随矩阵得到错误多项式迭代步骤如下：a 由初始值 10)0(1) 1(, 0)0(, 1)(1, 0) 1(, 1)(SdDxdDx开始迭代其中: 是错误位置多项式 的次数， 为第j步和第j+1步的差值 )(jD)()(xjjd)(1)()(1)(2)(1

6、1.jDjjjDjjjjjjSSSSd)()()(2)(2)(1)(.1)(jDjjDjjjXXXX第11页/共19页 b 若 则有 并计算 ，再进行下一次迭代 若 ，则找出 之前的某一行 ，它在所有 行之前各行中的 最大，且 ，于是按 0jd)()()() 1(xxjj1jd0jd0id)()()()(1)() 1(xxddxxiijijjj计算)()1(xj这就是第 步的解 c 计算 ，重复 步进行下一步迭代，这样迭代 次后得到的 即为所求的 。 1jd)()2(xt)(x)( jDi ijj1jt2b第12页/共19页3）用钱搜索解出 的根，得到错误位置数。（上一步已经求得 ） 。)(x

7、)(x下面介绍钱搜索错误位置数的步骤：对接收向量112210.)(nnXrXrXrrXr进行逐比特译码。最高位比特被首先译码。为了译 ，译码器检验 是否是错误位置数；也就等价于检验于检验它的倒数 是否是 的根。如果是，则：1nr1n)(X0.1221vv第13页/共19页因此，为了译 ，译码器需要构造 ， , 。如果 ，则 是错误位置数，并且是错误位，否则， 是正确位。 1nr122vv0.1221vv1n1nr1nr为了译 ，译码器需要构造 ， ， 并校验和式：lnrl1l 22vlvvlvll.1221如果和式为0，则 是 的根，且 是错误位；否则， 是正确位。 l)(Xlnrlnr第14页/共19页 4）由错误位置数求得错误值，从而得到错误图样。 RS码错误值（ ） 计算公式： 求出0)( xike)()(11kkikXXe)(x为的导数形式)(x)(mod()()(2txxxSx被称为错误估值函数)(x