RS码的基础知识.ppt

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