RS码简介与编译码算法综述PPT课件.ppt

RS码简介 熊竹林 1 RS码是一种BCH码BCH码是一种循环码循环码是一种线性分组码线性分组码是一种信道编码 背景知识 2 2020 3 23 信道的非理想性传输差错香农告诉我们要纠错必须增加冗余信道编码就是一门增加冗余的学问亡羊补牢 反馈重传未雨绸缪 前向纠错线性分组码就是前向纠错码的一种 背景知识 信道编码 3 2020 3 23 分组 将码字分为许用码字和禁用码字两组线性 许用码字的线性组合还是许用码字 背景知识 线性分组码 4 2020 3 23 例子 7 3 线性分组码C0 0000000 C1 0101110 C2 0010111 C3 1001011 C4 1100101 C5 1110010 C6 0111001 C7 1011100 27个码字中只有23个码字是许用码字 许用码字对线性运算具有封闭性 仔细观察还会发现许用码字对循环移位也具有封闭性 具有这种性质的线性分组码称为循环码 5 2020 3 23 BCH码是一类最重要的循环码 能纠正多个随机错误 它是1959年由Bose Chaudhuri及Hocquenghem各自独立发现的线性循环码 人们以他们的名字字头命名为BCH码 BCH码打破了一般线性分组码先编码再验证性能的模式 能够根据实际纠错需求进行编码 BCH码 引入 6 2020 3 23 给定有限域GF q 及其扩域GF 其中q是素数或素数的幂 m为正整数 若GF q 上循环码的生成多项式g x 的根中含有 1个连续根 1 2 则由g x 生成的循环码称为q元BCH码 其中 是域GF 中的n级元素 是任意整数 BCH码 定义 7 2020 3 23 满足交换律 结合律和分配率的元素个数有限的域称为有限域 实际应用中使用最多的有限域是二元域 记为GF 2 BCH码 有限域 8 2020 3 23 GF 2 域在工程中可以看做是m个比特的0 1序列 在数学上映射为如下2 个有限元素 0 0 1 1 2 3 2 2 各元素之间的约束关系由本原多项式唯一确定 BCH码 GF 2 9 2020 3 23 例子 证明多项式 3 1为本原多项式并构造GF 23 一个多项式是本原多项式的充要条件 一个m阶的不可约多项式f x 如果f x 整除 1的最小正整数n满足n 2 1 则该多项式是本原的 多项式 3 1为3阶不可约多项式 且能够整除 1的最小正整数为23 1 7 符合本原多项式的定义 构造出的GF 23 元素满足 0 1 1 2 2 3 1 4 2 5 2 1 6 2 1 7 0 10 2020 3 23 BCH码 设计准则 给定m t t 2 1 其中 m为GF 2 的本原多项式的次数 t为设计所需的纠错个数 则有 编码的最小汉明距离2t 1 BCH码生成多项式包含的连续根的最小个数为2t 证明从略 码长n 2 1 取等号时称为本原BCH码 否则称为非本原BCH码 m 1的本原BCH码就是今天要说的RS码 11 2020 3 23 RS编码起源于1960年MITLincoln实验室的S Reed和G Solomon在JournaloftheSocietyforIndustrialandAppliedMathematics上发表的一篇论文 PolynomialCodesoverCertainFiniteFields 某些有限域上的多项式码 经历了数十年的发展 RS码成为了研究最详尽 分析最透彻 应用最广泛 研究成果最多的码类之一 RS码 引入 12 2020 3 23 GF q 上 q 2 通常q 2 码长n q 1的本原BCH码称为RS码 RS码是迄今为止发现的一类很好的线性纠错码 其纠错能力很强 特别是在较短和中等码长下 性能接近于理论限 且构造方便 编码和译码简单 特别是它具有严格的代数结构 因此 RS码在编码理论中起到重要作用 RS码 定义与特点 13 2020 3 23 RS码的编码系统是建立在比特组基础上的 即字节 而不是单个的0和1 因此它是非二进制BCH码 这使得它处理突发错误的能力特别强 RS码 定义与特点 14 2020 3 23 码长 n 2 1信息段 k监督段 n k 2t最小码距 d 2t 1 RS码 编码参数 15 2020 3 23 例子 试构造一个能纠3个错误符号 码长n 15 m 4的RS码 解 已知t 3 n 15 m 4 所以有码距 d 2t 1 7个符号 28bit 监督段 2t 6个符号 24bit 信息段 n 6 9个符号 36bit 码长 n 15个符号 60bit 因此该码是 15 9 RS码 同时也可以看作是 60 36 二进制码 生成多项式g x x x 2 x 6 x6 10 x5 14x4 4x3 6x2 9x 6 16 2020 3 23 最小距离为d的本原RS码的生成多项式为g x x x 2 x 3 x d 2 信息元多项式为m x m0 m1x m2x2 mk 1xk 1编码器主要有三种类型 1 基于乘法形式的编码器2 基于除法形式的编码器3 基于校验多项式形式的编码器 RS编码 编码器设计 17 2020 3 23 1 基于乘法形式的编码器公式 c x m x g x 原理图 RS编码 编码器设计 18 2020 3 23 2 基于除法形式的编码器公式 b x c x xn ka x r x 原理图 RS编码 编码器设计 19 2020 3 23 3 基于校验矩阵的编码器公式 cn k i 0 1 i 1 2 3 n k原理图 RS码 编码器设计 20 2020 3 23 根据生成多项式 可以构造出快速的硬件编码器 而对RS码的译码 由于它是循环码的一个子类 任何对循环码的标准译码过程都适用于RS码 下面我们讨论专门针对RS码的译码算法 PGZ算法BM算法Forney算法 RS译码 译码算法 21 2020 3 23 PGZ算法的名字来源于三位作者Peterson Gorenstein和Zierler 该算法是解决BCH译码问题的通用算法 它的出现奠定了BCH译码算法的理论基础 该方法实现简单 易于理解 对于较短的BCH码非常有效 RS译码 PGZ译码算法 22 2020 3 23 PGZ算法的译码过程分为以下5步 1 由接收字r x 求得Sj r j j 1 2t 1 2 由Sj求出错误位置多项式 3 用Chien搜索解出 的根 得到错误位置数 确定出错误位置 4 由错误位置数求得错误值 从而得到错误图样 5 计算 完成纠错过程 PGZ译码算法 23 2020 3 23 将接收码字R x 看做发送码字C x 与错误码字E x 的叠加 R x C x E x m x g x E x 将g x 在GF 2m 域上的2t个根 1 2 2 代入可以得到与发送码字完全无关的2t组方程 Sk R k E k 1 1 2 2 其中 1 k 2t k是错误多项式的系数表示错误的程度 表示错误的位置 方程左侧的SK就是k阶校正子 PGZ译码算法 第一步 计算校正子Sj 24 2020 3 23 给定错误多项式 1 1 1 1 其中 是实际错误的数目 对上式进行如下操作 1 将多项式的根x 1代入错误多项式2 两端同乘 3 将左右两端同时对参数h从1到 累加求和得到 元方程组 其中 t 1 k k 1 2 3 1 1 2 2 1 1 这是一组校正子Si和 系数的相关的线性方程组将它表示为矩阵形式 PGZ译码算法 第二步 计算错误位置多项式 25 2020 3 23 PGZ译码算法 第二步 计算错误位置多项式 左侧矩阵的阶数 是个不定参数 正常情况下小于纠错长度t 大于t将无法正确纠错 PGZ译码采用穷举法来确定 同时得到错误位置多项式 26 2020 3 23 求得错误位置数多项式 之后 下一步便在于如何求得 0的根从而得到错误位置数 数学上的实现方法是穷举法 就是将域GF 2m 上的所有元素 i代入 看结果是否为0 华裔科学家钱闻天提出一个找根的物理实现方法 如图所示 PGZ译码算法 第三步 定位错误位置 27 2020 3 23 钱搜索法要求t个乘法器 先分别输入 2 t 1 2 存放在乘法器的寄存器上 在第 节拍时 寄存器里的内容依次是 1 2 2 所以取得和数 1 1 2 2 若 0 则 便是错误位置数 否则便不是 运算器依次按节拍输出 若 0 则第n h位有错 另一路 通过延迟与缓冲 将接收信号与搜索运算的节拍同步 使得错误检测电路的结果恰好能够反馈到对应的接收信号 从而实现纠错 PGZ译码算法 第三步 定位错误位置 28 2020 3 23 对于二元BCH码而言 错误多项式的系数必为1 这一步可以省略 由于RS码是非二元BCH码 所以必须求出多项式系数的具体值 才能完成错误多项式的构造 实现纠错 求多项式系数的数学方法在理论上非常简单 需要用到译码第一步时得到的2t组线性方程 Sk R k E k 1 1 2 2 1 k 2t 此时Sk和 k已知 只需从方程组中选取 组线性无关方程就能够得到唯一解 再将错误多项式从接受序列中移除就实现了RS码译码的全部过程 PGZ译码算法 第四步 求出错误多项式的系数 29 2020 3 23 PGZ译码算法 流程图 输入R x 计算S1 N级移位寄存器 计算错误位置多项式 用钱搜索法求 的根 计算 i R x C x 输出 计算S2 计算S2t E x 30 2020 3 23 在前面给出的BCH码译码算法中 第 2 步由sj求 x 和第 4 步求 的计算量为最大 通常需要解一组线性方程组 其计算量与系数矩阵阶数的三次方成正比 因此 当码长较长 纠错能力较大时 计算量很大 要求译码器的运算速度很高 如果实际产生的错误数 远大于码的纠错能力t时 这一步的计算量不但没有减小 反而增大 这是因为它必须首先计算校正子矩阵的行列式 若为0 必须在降阶之后再次计算 PGZ译码算法 算法总结 31 2020 3 23 这样降阶一次计算一次 直到矩阵的行列式不为0为止 需要降阶t 次 然后在求解方程组 解出 1 2 第 3 步求 x 的根 可以用钱搜索较简单地实现 第 4 对于二元BCH码而言可以省略 但对于RS译码来说仍然是困难而又重要的一步 针对第 2 步和第 4 步 学者进行了研究并给出了非常有效地简化算法 它们分别是BM算法和Forney算法 PGZ译码算法 算法总结 32 2020 3 23 1965年E R Berlekamp提出了由伴随式求 x 的迭代译码算法 极大地加快了求 x 的速度 实现时比较简单 且易于用计算机完成译码 因而从工程上解决了BCH码的译码问题 1969年J L Massey指出 迭代译码算法与序列的最短线性移位寄存器的综合之间的关系 并进行了简化 自此以后把这种算法成为BM迭代译码算法 BM译码算法 引入 33 2020 3 23 BM迭代译码算法的基础是牛顿等式 1 1 1 0 1 0 1 1 2 2 1 联立两式得 S1 1 0 S2 S1 1 2 2 0 1 1 2 2 2 2 1 1 0 再加上之前在PGZ译码得到的 组方程 1 1 2 2 1 1 k 1 2 就构成了BM算法迭代的数学基础 BM译码算法 算法基础 34 2020 3 23 BM译码算法的原理非常简单 1 从第一个等式S1 1 0出发 求出 1 2 将 1 代入第二个等式验证 若等式满足取 2 1 若不满足则需要对 2 进行修正 使 2 同时满足前两个等式 3 将 2 代入第三个等式验证 4 迭代次数满足要求 一般设为2t 则终止 得到的 2 就是错误位置多项式 BM译码算法 算法原理 35 2020 3 23 1 设初值为 1 x 1 1 x 0 D 1 0 1 1和 0 x 1 0 x 1 D 0 0 0 s1 2 dj sj 1 1 1 若dj 0 则有 j 1 x j x 1 x x D j 1 D j 如不相等 则有 j 1 x j x dj 1 x j 1 x j x dj 1 x D j 1 max D j j i D j 3 重复 2 进行下一次迭代 共迭代2t次 BM译码算法 迭代的具体实现 36 2020 3 23 例子 GF 24 上16元 15 9 7 RS码 它的生成多项式g x x x 2 x 6 已知r x 6x4 11x12 求错误位置 解 计算伴随式S1 S2 12 S3 6 S4 S5 0 S6 2 使用迭代法求 x 的过程如表所示 37 2020 3 23 得到 x 1 6x x2 解得 x 的根为 11和 3 求得错误位置数是X1 4和X2 12 所以可以断定x4和x12位置发生了错误 例毕从算法原理和举例可以看出 与一般译码方法相比 迭代译码有以下显著优点 1 计算比较简单 特别是可以用微处理机及软件实现译码 且程序不复杂 2 实际产生的错误个数 t时 计算量不仅不会增加 反而减少 3 无论实际发生的错误个数 t 是大是小 用迭代算法计算所需时间较为一致 4 在二元情况下 迭代步骤可以减少一半 至此 BM迭代算法介绍完毕 下面介绍求解错误多项式系数的简化算法 Forney算法 38 2020 3 23 假定错误发生在位置 1 2 j1 j2 n 1 则 1 1 1 2 1 1 1 2 2 1 1 N x x S x mod 1 其中S x 1 S1x S x Forney算法 算法原理 39 2020 3 23 Forney算法 算法原理 40 2020 3 23 所以有 Forney算法 算法原理 Forney算法就是通过上式求解错误多项式的系数 41 2020 3 23 例子 RS 31