RS码的基础知识.ppt

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码错误值 计算公式 求出 为 的导数形式 被称