信息论与编码第五讲

1、第五讲1主要内容1、循环码代数基础2、 BCH码3、 RS码21.1 几个名词元素：近代代数的运算对象。集合：一组元素或若干个元素的全体。代数系统：包含集合和一种或几种代数运算（用符号“*”表示）的系统。一、循环码代数基本知识31.2 群群，是包含集合G和一种代数运算*，且满足下列条件的代数系统：（a）运算封闭；（b）有恒等元；（c）有逆元；（d）满足结合律。加法群：满足加法和逆运算的群。乘法群：满足乘法和逆运算的群。交换群：满足交换律的群。子群：一个非空集合S G，S满足群G的全部条件，则S称为子群。4 加群一定是交换群，加群一定含零元素；乘群不一定是交换群，乘群一定不含零元素。 无限群：包

2、含无数个元素的群。 有限群：包含有限个元素的群。有限群元素的个数称为该群的阶。 循环群： 某一元素a（称作生成元a）的一切乘幂a0, a1, a2,的全体组成一个群，称为循环群，写作G = a0, a1, a2, ,其中a0= e是单位元。 若序列a0= e，a1, a2, 中没有两个元素是相等的，称之为无限循环群。5 若上述序列中有两个相等的元素a i= a j, (ij)，可推出G 的元素必以n为周期重复，即an = a0=e , 这样的循环群称为有限循环群。 循环群也叫幂群，具有以下性质： （a）循环群是交换群； （b）循环群的子群仍是循环群； （c）n阶循环群子群的阶数一定是n的因子。

3、6例例1：令R、I、E分别是有理数、整数、偶数集合，则(E,+)是(I,+)的子群，则(I,+)是(R,+)的子群，单位元均是0。奇数集合O在加法运算下构不成群，因不满足封闭性条件。例3 集合G = 0,1,2 m-1在模m加（用符号表示）运算下构成一个群（G，）。 该加群是m阶有限群，单位元是0。元素0的逆元是0，1的逆元是m-1, 2的逆元是m-2,。例4：集合G = 1,2 q-1在模q乘（q是素数）运算下构成一个乘群（G，）。71.3 环 环，包含集合R和两种代数运算，且满足下列条件的代数系统： （a）按第一种运算（不妨称为加法）构成交换群； （b）第二种运算（不妨称为乘法）满足以下条

4、件：封闭性；结合律；恒等元；（c）与加法间满足分配律：对于a,b,c R，a(b+c)=ab+ac, (a+b)c=ac+bc。交换环： 对于a,b R，ab=ba(交换律)，则称R为交换环。81.4 域域，具有交换环的性质，且在乘法运算时具有逆元的代数系统。域具有加和乘两种运算及它们的逆运算。无限域 有理数、实数和复数都是无限域。有限域：包含有限个（q）元素的域，或称伽罗华域。q称为域的阶。在信道编码中用到的是有限域，GF(q)。(0,1) 二元域GF(2)，或称基本域。由GF(2) GF(2m )，称扩域。9 可以证明，伽逻华域GF(q) 的 (q-1)个非零元素在模 q 乘运算下构成一个

5、循环群（幂群），即所有非零元素可由一个元素（该元素称作生成元或本原元）的各次幂 0、1、2、q-2 生成。 10元素各 次 幂元素的阶加法逆元乘法逆元012311111141212434333134242241414214表2-1 GF(5) 各非零元素的幂、阶及逆元111.5 既约多项式 对于某数域上的多项式PI（x），若除了常数C以及CPI（x）外不能被该数域上的任何其它多项式整除，则称为是该数域上的既约多项式。 如：x4+x+1 121.6 本原多项式 对于有限域GF(q)上的m次既约多项式P(x)，若能被它整除的最简单多项式(x n -1)的次数n qm 1, 则称该多项式为本原多项式

6、。本原多项式一定既约；既约多项式未必本原。如： m 本原多项式 3 1+x+x3 4 1+x+x4 5 1+x2+x5 6 1+x+x6 13比如：在GF(2)域上，x4+x+1 (q=2, m=4, 2m-1=15) 不能被 x5+1 整除； 不能被 x6+1 整除； 不能被 x14+1 整除； 能被 x15+1 整除；所以 x4+x+1 是本原多项式。 而 x4+ x3+ x2+ x+1 能被 x5+1 整除； 能被 x15+1 整除；所以，x4+x3+x2+x+1是既约的，但不是本原的。14本原元 对于m次本原多项式p(x)，如果p(a)=0, 那么a是GF(2m)的一个本原元。利用本原

7、多项式可求扩域GF(2m)的全部元素为：15举例p(x)=x2+x+1，求GF(22)的全部元素及加法乘法表。分析：令p(a)=0，得a2+a+1=0 ，a2a+1。那么全部元素为：幂表示矢量表示多项式表示0a0a1a2=a+10001101101xx+1161.6 GF(q)的加法和乘法在GF(q)中，对元0,1,2,q-1使用mod q的计算方法：进行加法和乘法，如果结果在q以上，就用q除，把余数作为结果。如GF(3)的加法和乘法如下表：+0 1 20120 1 21 2 02 0 1.0 1 20120 0 00 1 20 2 117减法：a-b=a-b+q mod q如: 1-2=1-

8、2+3=2 mod 3除法：b/a=b. a-1 mod q如：因为22=1 mod 3，2的乘法逆元2-1为2，所以：2/2=2 2-1=2 2=1 18二、BCH码19 2.1 扩域GF(2m)域元素乘法任意扩域元素都是同一个本原多项式根的幂次，因此域元素乘法与本原多项式密切关联。首先以一个例子看i的算法：例4.16 GF(24)中是本原多项式P(x)=x4+x+1的根。解：任何非零域元素既可以写成的幂次i， 也可以写成次数低于4的多项式，不妨设 i =a33+ a22+ a1+ a0i= a34+ a23+ a12+ a0 (由P(x),4 =+1) = a23+ a12+(a0+a3)

9、+ a3比较多项式i和i，发现只要将i的各系数向高位移一位，而最高位按P(x) 系数规则反馈到相应位，便可以得到i的系数。20实现i运算的电路 1 x x2 x3 x4 1 1 0 0 1 a0a1a2a3例4.16 作i运算的电路可以推广到一般的域元素乘法运算。利用ij=(i)，只要将i预置入移存器，再循环反馈 j次，便得到乘积ij。21 ij算法之二：化为两个m次多项式相乘设GF(24)的两个域元素为i=a33+ a22+ a1+ a0 和 j=b33+ b22+ b1+ b0则多项式乘积ij可整理成以下形式： ij =i(b33+b22+b1+b0)= (b3i)+b2i)+b1i)+b

10、0i) (4-41) 式中系数bm与i的乘法可化为二元域标乘： bmi= bm(a33+ a22+ a1+ a0) = bma33+ bma22+bma1+bma0 m=0,1,2,3 (4-42)22 1 x x2 x3 1 2 3 图4-12 m次多项式形式的ij乘法电路完成ij运算的时间固定，需m个时钟周期。a0a1a2a3DDDDb0b1b3b2 ij =(b3i)+b2i)+b1i)+b0i) (4-41) bmi= bma33+ bma22+bma1+bma0 (4-42)23上面i和j可随意取。若j固定(乘式j不变)，可设计一专用电路，只一个周期就能完成乘j运算例:设i =a33

11、+ a22+ a1+ a0 (随意) ，j=3 (固定) 则 i3 =a36+ a25+ a14+ a03 以关系式4=+1代入，得i3 =( a0+a3)3+ ( a2+a3)2+( a1+a2) + a1 该电路也可完成bj数乘。只要令上面i 的系数(a3,a2,a1,a0 )=(0,0,0,1)，代入i3 即得b3。 图4-13 i3乘法电路a0a1a3a2b24计算域元素多项式R(i )的值在循环码译码中，经常要计算R(i )= R(x)|x=i, 这里R(x)= rn-1xn-1+ rn-2xn-2+ r1x+ r0 是接收的码多项式。分解R(i )成如下形式R(i )= rn-1(

12、i )n-1+ rn-2(i )n-2+ r1i+ r0 =(.( rn-1i+rn-2) i+ rn-3) i+ r1 )i+ r0可见，R(i )的计算可以用乘i电路来实现。比如GF(24)中i=3时，可用图4-13的电路来计算R(3 ).在输入端依次送入rn-1、rn-2r1、r0，乘3电路每一时钟周期运行一次。第一拍完成rn-13，第二拍完成( rn-13+rn-2) 3，第三拍完成( rn-1i+rn-2) i+ rn-3) i，依此类推，到第n拍输入最后一位r0，这时保存在寄存器中的就是R(3 )的结果。 252.2 GF(2m)域上构造循环码的方法26 xn-1 因式分解 (4-

13、17)这里，既约因式mj(x)（j=0,l-1）分成两部分，它们的乘积分别是g(x)和 h(x)。循环码并不强调g(x)的既约性，它可以是既约的，也可以是非既约的。若某既约因式mj(x)是非既约g(x)的一个因式，必有 mj(x) | g(x) | (xn-1) (4-18) 换一个角度，如果将(xn-1)看成是一个n次多项式，那么它在复数域应该有n个根，记作ai，i=0,n-1，此时(xn-1)可表示成xn-1=(x-a0) (x-a1) (x-an-1) (4-19)27例4 -7 （x4-1）在不同域上的因式分解在实数域的分解：x4-1= (x2+1)(x+1)(x-1)在复数域的分解：

14、x4-1= (x+i) (x-i) (x+1)(x-1)在二元域的分解：x4-1= x4+1= (x+1)(x+1) (x+1)(x+1)上例说明：域不同则分解亦不同，在一个域的既约不等于在另一个域的既约。既约多项式mj(x)在GF(2)上不能再分解，其系数在数域取值于0,1；但它在二元扩域GF(2m)未必就不能再分解，因GF(2m) 是多项式域，系数取值于0、1、2、 。28根据定理4. 1，只要找到与循环码对应的一个n 阶元素，就可以将(xn -1)在GF(2m)上完全分解为： xn-1 =证：若 a是循环群n 阶元素，必有an = 1 即(an -1)=0 将ai,i=0n-1代入(xn

15、-1)验根， 得 (ai)n-1= (a n) i -1= (1)i-1= 0 ai,i=0n-1是(xn-1)的n个根，以根为一次项可将(xn-1 )完全分解为 xn-1=(x-a0) (x-a1) (x-an-1) 29 二元扩域GF(2m)是由一m次本原多项式生成的。当n=2m-1时，这个n阶域元素a就是(2m-1)阶本原元，通常用表示本原元；当n(2m-1)且n|(2m-1)时，这个n阶域元素a为非本原元，通常用表示非本原元。这里不强调域元素是否本原，所以用中性字母a来表示。 = xn-1 = GF(2m)扩域 | GF(2)域 系数1既是扩域又是二元域元素或改变顺序为 = = xn-

16、1 30若(xn-1)的某一个根ai , i0,1n-1又是某个既约因式mj(x), j0,1l-1的根，也是(n-k)次生成多项式g(x)的根，那么必有a为n阶本原元时： (x-ai) | mj(x) | g(x) | (xn-1)=( )(4-22)a为n阶非本原元时： (x-ai) | mj(x) | g(x) | (xn-1) | ( )(4-23)以上两式说明：生成多项式g(x)的（n-k）个根也是(xn-1)的根，只要能够以适当的方法找出这些根，就可以从这些根得到生成多项式g(x)。31研究表明，有重根的g(x)不能产生好码。而如果 (xn-1)无重根，则g(x)肯定无重根。在GF

17、(qm)上(xn-1)无重根的充要条件是n、q互素。(xn-1)的n个根中，(n-k)个根也是g(x)的根，剩下的k个根一定也是h(x)的根。 因此如果 (xn-1)无重根，h(x)肯定也无重根。32 用(xn-1)在GF(2m)域上的根来构造循环码的方法，那就是： 在(xn-1)的n个根中选取若干个r1、r2rj, 其中 rj ai,i=0,1n-1找出各根对应的既约多项式r1m1(x)、 r2m2(x)rjmj (x)。求出这些既约多项式的最小公倍式： g(x)=LCMm1(x), m2(x)mj (x) LCM (Least Common Multiple) - 最小公倍式若选取的根是连

18、续幂次的根，则所得的g(x)可以产生一个BCH码，否则就是一般的循环码。332.3 BCH码的定义 GF(q)域循环码生成多项式g(x)，若含有2t个连续幂次的根 ，则由g(x)生成的(n,k)循环码称为q进制BCH码。连续幂次起始值m0的选取并无多大实际意义，通常固定取m0=1。 若q=2，称为二进制（二元）BCH码。 若根a是本原元，称该码为本原BCH码，其码长n=qm-1。 若根a是非本原元，称该码为非本原BCH码，其码长n是qm-1的因子，满足n | (qm-1)。 34BCH码限定理：若BCH码生成多项式g(x)中含有2t个连续幂次的根，则该码的最小距离dmim 2t+1证明： BC

19、H码多项式C(x)=m(x)g(x) g(x)的2t个连续幂次根、2t也是C(x)的根设 C(x)= c0+ c1x + c2 x2+ cn-1 xn-1以根x = 代入， 得 c0+ c1 + c2 2+ cn-1 n-1 = 0以x = 2代入，得 c0+c12 +c2(2) 2+cn-1(2)n-1= 0 以x = 2t代入，得c0+c12t+c2(2t)2+cn-1(2t)n-1= 0 35将上面2t个方程写作矩阵形式，得CAT= 0(4-24) 其中 A = =可见，A是范得蒙矩阵。数学证明：范得蒙矩阵一定是满秩矩阵，即矩阵A的秩是2t或者说有2t列线性无关。码的最小距离dmin等于

20、校验矩阵中线性无关的列数加1，因此BCH码的dmin = 2t +1 (4-26) 1 2 n-1 1 2 (2)2 (2) n-1 1 2t (2t)2 (2t) n-1 1 2 n-1 1 2 (2)2 (n-1)2 1 2t (2)2t (n-1)2t36 2.4 本原BCH码构造法 由关系式n=2m-1算出m，查表4-5，找到一个m次本原多项式P(x)，产生一个GF(2m)扩域。 在GF(2m)上找一个本原元，分别计算2t个连续幂次根、2、2t所对应的GF(2)域上的最小多项式m1(x)、m2(x)m2t(x)。m8时连续幂次根i所对应的最小多项式见表4-6。 计算这些最小多项式的最小

21、公倍式，得到生成多项式g (x) g(x)=LCMm1(x) m2(x) m2t(x) (4-27) 由关系式C(x)=m(x)g(x) 求BCH码字。 37对于二元BCH码，无需列出全部2t个连续幂次的根，而只要列出其中一半（奇数幂次的根）就可以了。这是因为任何一个偶数ie 可写成一个小于它的奇数io 与2的l次幂的乘积 ie =io2l , ioie(4-28)比如2=121，4=122，10=521，12=322 因此任何一个偶次幂根都是奇次幂根的共轭元 对照2.2节定理2.7和定理2.8，可知它们对应同一个最小多项式。38i最小多项式i最小多项式i最小多项式i最小多项式m = 21(0

22、,1,2)m = 31(0,1,3)3(0,2,3)m = 41(0,1,4)3(0,1,2,3,4)5(0,1,2)7(0,3,4)m = 51(0,2,5)3(0,2,3,4,5)5(0,1,2,4,5)7(0,1,2,3,5)11(0,1,3,4,5)15(0,3,5)m = 61(0,1,6)3(0,l,2,4,6)5(0,l,2,5,6)7(0,3,6)9(0,2,3)11(0,2,3,5,6)13(0,1,3,4;6)15(0,2,4,5,6)21(0,1,2)23(0,1,4,5,6)27(0,1,3)31(0,5,6)m = 71(0,3,7)3(0,1,2,3,7)5(0,2

23、,3,4,7)7(0,1,2,4,5,6,7)9(0,1,2,3,4,5,7)11(0,2,4,6,7)13(0,1,7)15(0,1,2,3,5,6,7)19(0,1,6,7)21(0,2,5,6,7)23(0,6,7)27(0,1,4,6,7)29(0,1,3,5,7)31(0,4,5,6,7)43(0,l,2,5,7)47(0,3,4,5,7)55(0,2,3,4,5,6,7)63(0,4,7)m = 81(0,2,3,4,8)3(0,1,2,4,5,6,8)5(0,1,4,5,6,7,8)7(0,3,5,6,8)9(0,2,3,4,5,7,8)11(0,1,2,5,6,7,8)13(0

24、,1,3,5,8)15(0,1,2,4,6,7,8)17(0,1,4)19(0,2,5,6,8)21(0,l,3,7,8)23(0,1,5,6,8)25(0,1,3,4,8)27(0,1,2,3,4,5,8)29(0,2,3,7,8)31(0,2,3,5,8)表4-6二元扩域GF(2m)中连续幂次根所对应的最小多项式 39比如t=4时8个连续幂次根 2 3 4 5 6 7 8中， 2 4 8是共轭元，3 6是共轭元，于是g(x)=LCMm1(x) m2(x) m3(x) m4(x) m5(x)m6(x)m7(x)m8(x)= LCMm1(x) m2(x) m4(x) m8(x) m3(x) m

25、6(x) m5(x) m7(x)= LCMm1(x) m3(x) m5(x) m7(x)因此对于二进制码，构造本原BCH码的步骤改为: 分别计算t个连续奇次幂之根、32t-1所对应的最小多项式m1(x)、m3(x)m2t-1(x)。40当码长n确定后，BCH码纠错能力t的选择并不是任意的，而要受到一定限制。对于q元BCH码，2t个根对应2t个最小多项式，每个最小多项式的次数不会超过m，于是2t个最小多项式的最小公倍式g(x)的次数 degg(x) = (n-k) 2t (4-29)对于二元BCH码，t个根对应t个最小多项式，因此 degg(x) = (n-k) tm(4-30) (xn-1)一

26、共有n个根，连续幂次根不能超过根的总数 2t n (4-31)式(4-29) (4-30)给出了t的下限，式(4-31)给出了t的上限。41例4.8 设计一个码长n = 15的二元本原BCH码，在不同纠错能力下的生成多项式应是怎样的？解： 15=24-1本题m = 4第一步：查表，找到一个m=4的本原多项式P(x)=x4+ x+1。令是该本原多项式P(x)的根，满足4+ +1=0。由式(4-31)，本码纠错能力t 7。第二步：对于二元码，分别计算t=7个连续奇次幂之根 3 57 9 11 13所对应的最小多项式。本例可参考例2.2.3的表2-3，我们看到3、9是共轭元，7、11和13是共轭元（

27、利用教材p124“共轭根系”定义分析）。42根和根所对应的最小多项式（例2.10）如下：根 m1(x) =p(x)=x4+ x+1 根3 m3(x) =(x+a3) (x+a6) (x+a9) (x+a12)=x4+ x3+ x2+ x+1 根5 m5(x) =(x+a5)(x+a10)=x2+ x+1 根7 m7(x) =x4+ x3+ 1 根9同3，根11、13同7。这里，m(x)的全部根为下列系列：并把w序列换成a的序列。43 第三步：求最小公倍式得到生成多项式g(x)。若t =1，g1(x)=LCMm1(x) = x4+ x+1g1(x)是4次多项式，即n-k=4， k =15-4=1

28、1, 这就是(15,11)BCH码，也是汉明码。若t=2，g2(x)=LCMm1(x), m3(x) = m1(x)m3(x) = x8+ x7+ x6+x4+1，degg2(x)= n-k = 8， k =15-8=7，这是(15,7) BCH码。44若t=3， g3(x)=LCMm1(x), m3(x), m5(x) = m1(x)m3(x) m5(x) = x10+ x8+ x5+ x4+x2 + x +1， degg3(x)= n-k = 10， k =15-10=5，这是(15,5) BCH码。若t=4， g4(x)=LCMm1(x), m3(x), m5(x), m7(x) = m

29、1(x)m3(x) m5(x) m7(x) = x14+ x13+ x12+ x11+x10+ x9+ x8+ x7+x6 + x5+ x4+ x3 +x2 + x +1 degg4(x)= n-k = 14， k =15-14=1，这是(15,1) BCH码。45若t=5，g5(x)=LCMm1(x), m3(x), m5(x), m7(x), m9(x) = m1(x)m3(x) m5(x) m7(x)= g4(x)若t=6，g6(x)=LCMm1(x), m3(x), m5(x), m7(x), m9(x) , m11(x)= m1(x)m3(x) m5(x) m7(x)= g4(x)

30、若t=7，g7(x)=LCMm1(x),m3(x),m5(x),m7(x), m9(x), m11(x),m13(x)=m1(x)m3(x) m5(x) m7(x)=g4(x)可见，当t=4、5、6、7时的BCH码均是(15,1)码，生成多项式g4(x)拥有x的所有各次幂，意味着编码时将一位信息“0”或“1”重复发送15次。因此，实际上只有t=1,2,3的(15,11)、(15,7)、(15,5) BCH码才有实用价值。46 非本原BCH码与本原BCH码的主要区别在于所用的根是否本原元。 当码长n和纠错能力t给定后，本原BCH码的根一定是n=2m-1阶, n已知就是m已知，因而GF(qm)好找

31、。 非本原BCH码的根是n阶元素, 满足n | (qm-1)， n已知不等于m已知，需要多一道计算。 47已知n和t后二元非本原BCH码的设计步骤： 求出满足 n | (2m-1)关系的m的最小值。n是(2m-1) 的因子，可以借助2m-1的素因子分解表（如表4-7）来寻找m值。 查表4-5，找出一个m阶的本原多项式P(x)， 产生一个二元扩域GF(2m)。 以P(x)的根为中介找出一个n阶的非本原元。 计算与、3、52t-1对应的最小多项式m1(x)、m3(x)m2t-1(x)。 求生成多项式g(x)=LCMm1(x) m3(x) m2t-1(x)。48表4-7 2m-1的素因子分解（m34

32、） m素因子分解m素因子分解m素因子分解123456789101113735313371273517773311312389121314151617181920212233571381913431277311513517257131071333719735242873551l 314177127337323896832324252627282930313233471784813357131724131601180132731819177326265735294311312723311032089337113115133121474836473517257655377238959947949例4.9 试设计一个码长n = 23，纠两个随机差错(t =2)的二元BCH码。 解： 由于码长n 2m-1比如15、31、 255等值，可知要求设计的是二元