Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 1 RS 纠错编码原理 ―及其实现方法 陈文礼 January 08 于郑州 If you have any suggestion or criticism . please email to ciciendi163.com QQ83902112 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 2 前言 随着越来越多的系统采用数字技术来实现纠错编码技术也得到了越来越广泛的应用。 RS 码既可以纠正随机错误又可以纠正突发错误具有很强的纠错能力在通信系统中应用广泛。 近些年来随着软件无线电技术的发展 RS 编码、译码一般都在通用的硬件平台上实现。通常采用基于 FPGA 的 VHDL 编码硬件实现或者在 DSP、单片机上用 C 和汇编编程软件实现。 RS 纠错编码涉及的领域很广特别是设计到很多数学知识。这对那些对数学不太感冒的工程技术人员来书是个不小的挑战。尽管讲 RS 编码的书籍很多但是那些书都是采用循序渐进逐步引入的方式从汉明码到循环码从循环码到 BCH 码 BCH 码再引入 RS 码。对于工程技术人员他们需要的是简明扼要的讲解和详细的实现方法。 本人写这篇文章的宗旨就是尽量最简单的语言最简短的篇幅来讲 RS 纠错编码原理把重点来放在实现方法上。 为了便于读者仿真本文采样 MATLAB 程序实现程序尽量符合硬件 C 语言写法读者经过简单修改即可应用到工程中去。 本文读者对象 本文是为那些初识 RS 编码的学生、工程技术人员而写并不适合做理论研究如果你是纠错编码方面的学者、 专家那么本文并不适合你。 由于作者水平有限错误在所难免恳请读者批评指正。 陈文礼 2008-01 于郑州 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 3 一、必备的一些代数知识 1、在纠错编码代数中把以二进制数字表示的一个数据系列看成一个多项式。例如二进制数字序列 10101111 可以表示成 式中的 ix 表示代码的位置或某个二进制数位的位置ix 前面的系数 ia 表示码的值。若 ia 是一位二进制代码则取值是 0 或 1。Mx 称为信息代码多项式。 多项式次数 称系数不为 0 的 x 的最高次数为多项式 fx 的次数记为 fx ∂ 。 2、域 域在 RS 编码理论中起着至关重要的作用。 简单点说域 2mGF 有 2m 设 2mq 个符号 0120q α α α − 且具有以下性质 域中的每个元素都可以用 0121ma α α α − 的和来表示。 11q α − α 为本原多项式 px 的根。 运算规则有 在纠错编码运算过程中加、减、乘和除的运算是在伽罗华域中进行。 现以 GF24 域中运算为例 加法例 108001001110101 α α α 模2 加法相当于 0010 与 0111 异或 减法运算与加法相同 乘法例 810810mod153 α α α α • 除法例810221513/ α α α α α − − 不理解没关系下面的例子也许对你有帮助。 例 m4 41pxxx 求 2mGF 的所有元素 因为 α 为 px 的根 得到 410 α α 或 41 α α 根据运算规则 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 4 由此可以得到域的所有元素 元素 二进制对应码 十进制对应值 0 0 0000 0 0 α 1 0001 1 1 α 1 α 0010 2 2 α 2 α 0100 4 3 α 3 α 1000 8 4 α 1 α 0011 3 5 α 21 α α α α modp α 0110 6 6 α 232 α α α α α modp α 1100 12 7 α 3231 α α α α α modp α 1011 11 8 α 3211 α α α α modp α 0101 5 9 α 231 α α α α modp α 1010 10 10 α 321 α α α α α modp α 0111 7 11 α 2321 α α α α α α modp α 1110 14 12 α 32321 α α α α α α α modp α 1111 15 13 α 323211 α α α α α α modp α 1101 13 14 α 32311 α α α α modp α 1001 9 15 α 311 α α modp α 0001 1 由此可以看出本原多项式是求解域的全部元素的关键。读者也许会有这样的疑问我们如何得到 px 呢 本原多项式 px 的特性是 211mxpx−得到的余式等于0。 由于作者也是工程技术人员具体怎么得到 px 也没有深究过。 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 5 作者在设计 RS 编码时候都是根据 MATLAB 指令 rsgenpoly 来得到 px。 其格式为rsgenpolynk 参数 n 为码长一般 21mn−k 为信息码元个数。 例如 m4 码长 n15 信息码元长度为 9 GF24 的本原多项式可以根据指令 gtgtrsgenpoly159 得到 ans GF24 array. Primitive polynomial D4D1 19 decimal 二、线性分组码的一些基本概念 1、线性分组码一般用 nk 或 nkd 表示 n 为码长 k 为信息码元的数目 nk−为监督码元的数目。 d 表示码元距离。 定义两个码组上对应位置上数字不同的个数称为码组的距离。 发送的码字 123...nccccc 接收的矢量 123...nrrrrr 信道错误图样 ecr 例如 c11000 r10001 e111000000101001 从而可以看出从左端起第 2 位和第 5 位是错误的。 2、校验矩阵概念 码长为 n 信息数为 k 监督数为 r。 这样的一组码形式为 1212......krcmmmppp im 表示第 i 个信息码 jp 表示第 j 个校验码 各个校验码可从下列线性方程组求得。 111122112211222212112212...10...00...01...00......00...10kkrkkrrrrkkrhmhmhmppphmhmhmppphmhmhmppp 1-1 式中 ijh 是常数 校验方程组可写成校验矩阵 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 611121212221210000100.....0001kkrrrkhhhhhhHhhh………………… 该矩阵具有 r 行和 n 列 故
