RS纠错编码及其实现（初学者）.pdf-资料库

Zhengzhou Oriole Xinda Electronic Information Co.,Ltd. RS 纠错编码原理 ―及其实现方法陈文礼 January 08 于郑州 If you have any suggestion or criticism . please email to ciciendi@163.com QQ：83902112 1

Zhengzhou Oriole Xinda Electronic Information Co.,Ltd. 修订说明自从发表《RS 纠错编码原理及其实现方法》以来，收到很多初识 RS 编码的读者的来信，大家纷纷表示这篇文章对初学者很有帮助，但同时也指出了很多不足。比如第一版的例子中都是按照码长 2 n = 1m − ，但在实际应用中并不总是这种情况，还有就是 MATLAB 程序，由于作者在工程中是在 DSP 上用 C 实现的，所以文章中的 MATLAB 程序只是用来说明问题，并没有经过调试。做事应该有始有终，这次修改，附有详细的经过调试的 MATLAB 程序。并尽量做到程序具有通用性。（注：红色标记部分为修改部分）陈文礼 2008-11 于郑州 2

Zhengzhou Oriole Xinda Electronic Information Co.,Ltd. 前言随着越来越多的系统采用数字技术来实现，纠错编码技术也得到了越来越广泛的应用。RS 码既可以纠正随机错误，又可以纠正突发错误，具有很强的纠错能力，在通信系统中应用广泛。近些年来，随着软件无线电技术的发展，RS 编码、译码一般都在通用的硬件平台上实现。通常采用基于 FPGA 的 VHDL 编码硬件实现，或者在 DSP、单片机上用 C 和汇编编程软件实现。 RS 纠错编码涉及的领域很广，特别是设计到很多数学知识。这对那些对数学不太感冒的工程技术人员来书是个不小的挑战。尽管讲 RS 编码的书籍很多，但是那些书都是采用循序渐进，逐步引入的方式，从汉明码到循环码，从循环码到 BCH 码，BCH 码再引入 RS 码。对于工程技术人员他们需要的是简明扼要的讲解，和详细的实现方法。本人写这篇文章的宗旨就是尽量最简单的语言，最简短的篇幅，来讲 RS 纠错编码原理，把重点来放在实现方法上。为了便于读者仿真，本文采样 MATLAB 程序实现，程序尽量符合硬件 C 语言写法，读者经过简单修改即可应用到工程中去。本文读者对象本文是为那些初识 RS 编码的学生、工程技术人员而写，并不适合做理论研究，如果你是纠错编码方面的学者、专家，那么本文并不适合你。由于作者水平有限，错误在所难免，恳请读者批评指正。陈文礼 2008-01 于郑州 3

Zhengzhou Oriole Xinda Electronic Information Co.,Ltd. 一、必备的一些代数知识 1、在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如二进制数字序列 10101111，可以表示成： = 式中的 ix 表示代码的位置，或某个二进制数位的位置， ix 前面的系数 ia 表示码的值。若 ia 是一位二进制代码，则取值是 0 或 1。 ( )M x 称为信息代码多项式。多项式次数：称系数不为 0 的 x 的最高次数为多项式 ( ) f x 的次数，记为 ∂ f x ( ) 。 2、域域在 RS 编码理论中起着至关重要的作用。简单点说域 (2 )m GF 有 2m (设 2m = q )个符号   且具有以下性质： 0, 1 0  q  α α α − , 2 域中的每个元素都可以用 0 aα α , , 1 2 α − 的和来表示。 1 1 qα − = m 1 α为本原多项式 ( )p x 的根。运算规则有：在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。现以 GF(24)域中运算为例：加法例： 10 α α + = 0010 0111 0101 + = = 8 α （模 2 加法相当于 0010 与 0111 异或）减法运算与加法相同乘法例： 8 α α α = • 10 (8 10)mod15 + = 3 α 除法例： 8 /α α α α = = 2 − 10 2 15 − + = 13 α 不理解没关系，下面的例子也许对你有帮助。例： m=4, p x ( ) = 4 x + + 求 (2 )m GF 1 x 的所有元素：因为α为 ( )p x 的根得到 4 α α+ + = 或 4 1 0 α α= + (根据运算规则) 1 4

Zhengzhou Oriole Xinda Electronic Information Co.,Ltd. 由此可以得到域的所有元素二进制对应十进制对应 0 1 1α 2α 3α 1α+ 1)αα + = ( 2 α α + (mod ( p α )) 2 αα α α α + = + ( ) 2 3 (mod ( p α )) αα α α α + + (mod ( p α )) + = 1 ( ) 3 2 3 αα α + + = 1) ( 3 2 α + (mod ( 1 p α )) 2 αα ( 1) + = 3 α α + (mod ( p α )) αα α α α + + (mod ( p α )) + = 1 ( ) 3 2 αα α + + = 1) ( 2 3 α α α + + 2 (mod ( p α )) 码 0000 0001 0010 0100 1000 0011 0110 1100 1011 0101 1010 0111 1110 值 0 1 2 4 8 3 6 12 11 5 10 7 14 15 13 9 1 元素 0 0α 1α 2α 3α 4α 5α 6α 7α 8α 9α 10α 11α 12α 13α 14α 15α αα α α α α α + + (mod ( + + + = 1 ( ) 3 3 2 2 p α 1111 )) αα α α + + = + 1) ( 3 2 3 2 α α + + (mod ( 1 p α )) 2 αα α + ( 3 1) + = 3 α + (mod ( 1 p α )) αα + = (mod ( 1) 1 p α )) ( 3 1101 1001 0001 由此可以看出本原多项式是求解域的全部元素的关键。读者也许会有这样的疑问我们如何得到 ( )p x 呢？本原多项式 ( )p x 的特性是 mx 1 1 2 − + p x ( ) 得到的余式等于 0。由于作者也是工程技术人员，具体怎么得到 ( )p x ，也没有深究过。 5

Zhengzhou Oriole Xinda Electronic Information Co.,Ltd. 作者在设计 RS 编码时候都是根据 MATLAB 指令 rsgenpoly 来得到 ( )p x 。其格式为 rsgenpoly(n,k) 参数 n 为码长一般 2 n = 1m − ，k 为信息码元个数。例如 m=4, 码长 n＝15，信息码元长度为 9 GF(24)的本原多项式可以根据指令 >>rsgenpoly(15,9) 得到： ans = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal) 有读者来信问：我要做一个（158，128，31）的 RS 编码，在 MATLAB 中输入命令 rsgenpoly(158,128)，结果 MATLAB 报错： Error using ==> rsgenpoly N must equal 2^m-1 for some integer m between 3 and 16. 这里做一下解释，我们做 RS 编码时首先要根据码长选取 m ，选择原则是 n < ， 2m 若码长为 158，那么我们可以选择 8m = ，rsgenpoly 命令的第一个参数必须为 2 1m − ，第二个参数可以随便选择只要小于 2 1m − 就形了。在此给出 m ∈ (2,16) 的所有本原多项式。 (m = 2) P[m+1] = { 1, 1, 1 }; (m = 3) /* 1 + x + x^3 */ P[m+1] = { 1, 1, 0, 1 }; (m = 4) /* 1 + x + x^4 */ P[m+1] = { 1, 1, 0, 0, 1 }; (m = 5) /* 1 + x^2 + x^5 */ P[m+1] = { 1, 0, 1, 0, 0, 1 }; 6

Zhengzhou Oriole Xinda Electronic Information Co.,Ltd. (m = 6) /* 1 + x + x^6 */ P[m+1] = { 1, 1, 0, 0, 0, 0, 1 }; (m = 7) /* 1 + x^3 + x^7 */ P[m+1] = { 1, 0, 0, 1, 0, 0, 0, 1 }; (m = 8) /* 1+x^2+x^3+x^4+x^8 */ P[m+1] = { 1, 0, 1, 1, 1, 0, 0, 0, 1 }; (m = 9) /* 1+x^4+x^9 */ P[m+1] = { 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }; (m = 10) /* 1+x^3+x^10 */ P[m+1] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 }; (m = 11) /* 1+x^2+x^11 */ P[m+1] = { 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 }; (m = 12) /* 1+x+x^4+x^6+x^12 */ P[m+1] = { 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1 }; (m = 13) /* 1+x+x^3+x^4+x^13 */ P[m+1] = { 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 }; (m = 14) /* 1+x+x^6+x^10+x^14 */ P[m+1] = { 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1 }; (m = 15) /* 1+x+x^15 */ P[m+1] = { 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }; (m = 16) /* 1+x+x^3+x^12+x^16 */ P[m+1] = { 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 }; 7

Zhengzhou Oriole Xinda Electronic Information Co.,Ltd. 二、线性分组码的一些基本概念 1、线性分组码一般用 ( , )n k 或( , n k d 表示 n 为码长，k 为信息码元的数目，n k− 为监督 ) , 码元的数目。 d 表示码元距离。定义：两个码组上对应位置上数字不同的个数称为码组的距离。发送的码字 c = ( c c c , 1 3 , 2 c ,... n ) ) r = 2 c 接收的矢量 r ,... n r = + r r r , ( , 1 3 信道错误图样： e 例如 c ＝（1，1，0，0，0） r ＝（1，0，0，0，1） e ＝（1＋1，1＋0，0＋0，0＋0，0＋1）＝（0，1，0，0，1）从而可以看出从左端起第 2 位和第 5 位是错误的。 2、校验矩阵概念码长为 n,信息数为 k，监督数为 r。这样的一组码形式为： c m m m p p 2 ,... = , , , 1 2 1 k ,... p r im 表示第i 个信息码， jp 表示第 j 个校验码 k p ... 0 + + r p ... 0 + + r 0 = 0 = (1-1) 1 1 22 12 + + ... + + ... + + h m k k 1 h m k 2 p 1 + 1 p 0 + 1 p 0 + 2 p 1 + 2 各个校验码可从下列线性方程组求得。 h m h m 11 2 h m h m 21 2 ... h m h m ... + + r 2 式中 ijh 是常数 h m rk k p 2 p 1 + + + 0 0 1 r 2 1 ... 1 + + p r = 0 校验方程组可写成校验矩阵 H = h  11  h  21 .....   h  r 1 h 12 h 22 h r 2 … … … … h k 1 h 2 k h rk 1 0 0 0 1 0 … … 0 0 0 … 0 0 1       该矩阵具有 r 行和 n 列故式(1-1)可以写成 THc = 或 0 TcH = 0 8

资料库

RS纠错编码及其实现（初学者）.pdf

相关推荐

课程资源

热门标签

最新资料