编码chapter7

1、第七章 BCH码陆以勤2005年5月一、在扩展域描述和构成循环码Fqg(x) = f1(x) f2(x). fj(x)存在最小分裂域Fqm g(x)=(x-1)(x-2)(x-j). (x-n-k) 素多项式素多项式最小多项式g(x)=LCM(m1(x), m1(x), mj(x),., mn-k(x)m1(x) m2(x)mj(x)mn-k(x)最小多项式如果如果j1， j2是共扼根，则是共扼根，则mj1(x)=mj2(x)一、在扩展域从描述和构成循环码定理1：设Fq上的循环码的生成多项式g(x)在最小分裂域Fqm上的根为1， 2，, n-k。则Fq上多项式c(x)= cn-1xn-1 +c

2、n-2xn-2+c1x+c0是一个码字多项式的充要条件是HcT=0,其中:),.,( ,1.1.1.H0121212221212111cccccnnknnknnknnnnn计算在Fqm上进行。证明：（一）必要性证明：（一）必要性设设c(x)=a(x)g(x)= cn-1xn-1 +cn-2xn-2+c1x+c0c(j)= cn-1j n-1 +cn-2j n-2+c1j +c0=a(j)g(j)=a(j)*0=0，(j=1,2, n-k)(二）充分性二）充分性设c(x)满足HcT=0，c(x)=g(x)q(x)+s(x)，对于j=1,2, n-k，c(j)=g(j)q(j)+s(j)=0*q(

3、j)+s(j)=cn-1j n-1 +cn-2j n-2+c1j +c0=0则s(j)=0，即s(x)在Fqm上的根为1，2，, n-k，又s(x) g(x), 所以s(x)=0即c(x)=g(x)q(x)，所以c(x)是码字多项式。(0)k,0n(0)2k,mn(0)1k,mn(1)k,0n(1)2k,mn(1)1k,mn(t)k,0n(t)2k,mn(t)1k,mn2)(nk,0n2)(n2k,mn2)(n1k,mn1)(nk,0n1)(n2k,mn1)(n1k,mn(0)j,0(0)2j,m(0)1j,m(1)j,0(1)2j,m(1)1j,m(t)j,0(t)2j,m(t)1j,m2)

4、(nj,02)(n2j,m2)(n1j,m1)(nj,01)(n2j,m1)(n1j,m(0)i,0(0)2i,m(0)1i,m(1)i,0(1)2i,m(1)1i,m(t)i,0(t)2i,m(t)1i,m2)(ni,02)(n2i,m2)(n1i,m1)(ni,01)(n2i,m1)(n1i,m(0)1,0(0)21,m(0)11,m(1)1,0(1)21,m(1)11,m(t)1,0(t)21,m(t)11,m2)(n1,02)(n21,m2)(n11,m1)(n1,01)(n21,m1)(n11,m.( 1)n-1( 1)t( 1)0( j)n-1T(t)j,(t)j,m(t)j,mt

5、j),.,(021( j)0线性相关线性相关把H中的jt(j=1,n-k, t=0,.n-1）用Fq上的m重表示T(t)j,(t)j,m(t)j,mtj),.,(021共扼根( i )tsqij 去掉线性去掉线性相关的行相关的行一、在扩展域从描述和构成循环码定理2: 若H在Fqm中第j行元素和第i行相应元素为q次幂，则在Fq 中，第j行分裂的m行与第i行分裂的m行之间，行线性相关。已知g(x)在扩展域Fqm中根，生成Fq上的循环码Fqm=0, 2, qm-1设i1, i2, in-k为g(x)的根，且：g(x)根共扼根系级最小多项式i1 R i1e i1 m i1(x) i2 R i2 e i

6、2 m i2(x) .in-k R in-k e in-k m in-k(x) 而g(x)|xn-1, i1, i2, in-k也为 xn-1的根，即(ik)n=1, 由循环群的性质（a为n 级元素，则am = e n| m ),得i1, i2, in-k的级数为n的因数(必要条件)，可取 n=LCM(e i1, e i2, e in-k)方法1：g(x)=LCM (m i1(x) , m i2(x) , m in-k(x) )方法2：直接由构造H。i1, i2, in-k中共扼根属于同一共扼根系，即R i1, R i2, R in-k中可能重复，而mi1(x), m i2(x), , m i

7、n-k(x)有相同。去掉重复部分去掉重复部分一、在扩展域从描述和构成循环码方法1：g(x)=LCM (m i1(x) , m i2(x) , m in-k(x) )方法2：直接由构造H。在每个共扼根系选取一个共扼根（一般选次数最小的，计算简单）,得 j1, j2, jw, 构成H:1.).1.)1.)H212121222111wwwjnjnjjnjnjjnjnj（把H中的j1, j2, jw转为m重，H仍有线性相关的行，在这些行中保留一行，其余去掉。一、在扩展域从描述和构成循环码例（例5.5)：求以F16中, 2, 3, 4, 5为根的F2上的循环码。分析： , 2, 3, 4, 5同一共扼根

8、系, 级15，最小多项式x4+x+1另一共扼根系, 级5，最小多项式x4+x3+x2+x+1另一共扼根系, 级3，最小多项式x2+x+1g(x)=LCM(x4+x+1, x4+x3+x2+x+1, x2+x+1)=(x4+x+1)( x4+x3+x2+x+1)( x2+x+1) (素多项式） = x10+x8+x5+x4+x2+x+1n=LCM(15,5,3)=15g(x)=n-k=15-k=10, k=510.0101.1101.1100.0010.0100.1100.0101.1110.1101.0000.100.1.)1.)1.H55103912131451351453

9、1331431314（与课本不同，可按个人习惯全0，去掉相同，去掉1行共43-2=10行二、二进制BCH码若g(x)在扩展域Fqm上的根为i1, i2, in-k，则1.).1.)1.)H212121222111knknknininiininiinini（若i1,i2, in-k中含有1,2,d-1, 则抽这d-1行和任意d-1列，得121121121)(.).)(.).111222dddjdjdjdjjjjjj（每一列提取公因式，得12.222.)().).1.11H121121121121vuvuddddjjdjjjjjdjdjdjjjjjjj（二、二进制BCH码若i1,i2, in-k中

10、含有1,2,d-1, 则抽这d-1行和任意d-1列，得121121121)(.).)(.).111222dddjdjdjdjjjjjj（每一列提取公因式，得12.222.)().).1.11H121121121121vuvuddddjjdjjjjjdjdjdjjjjjjj（范得蒙行列式，若g(x)没有重根，即ju， jv, 则行列式不为零，行列式对应的矩阵满秩，原矩阵任意d-1列线性无关，所以码的距离至少为d。1. 定理3：Fq上多项式xn-1在最小分裂域无重根的充要条件为 (n,q)=1。二、二进制BCH码2. 定义：定义：设F2上循环码的生成多项式g(x)在扩展域F2m上的根含有, 2,

11、3, , d-1 (其中为本原元），则这种循环码称为二元（狭义）本 原BCH码3. 定理定理4：本原BCH码的最小距离dmind.4. BCH码设计步骤码设计步骤1）给定）给定n,t,找合适的找合适的F2m ，使，使n=2m-1或或n|2m-1,且且(n, 2m)=1(保证无重根保证无重根);2）选）选, 2, 3, , 2t为根，把它们组成不同的根系R1, R2, Rj, , Rs, 对于每一根系Rj，求其最小多项式mj(x),则g(x)=m1(x)m2(x)mj(x)ms(x) g(x)=n-kmt ( mj(x) m) n=LCM(e1,e2,ej,es)最多2t个，而j和2j属于同一共

12、扼根系，偶数下标一律取消，所以st。ej为Rj根系的根的级数，含本原元。二、二进制BCH码例：求n=15,能纠t=2,3,4,5,6,7个错的F2上的本原BCH码(1) t=2, g(x)的根为, 2, 3, 4同一共扼根系, 阶15，最小多项式(本原多项式)x4+x+1另一共扼根系, 阶15/(15,3)=5，方次数4最小多项式(4次素多项式）x4+x3+x2+x+1g(x)=(x4+x+1)(x4+x3+x2+x+1)=x8+x7+x6+x4+1(15,7,5)BCH码(2) t=3, g(x)的根为, 2, 3, 4 , 5, 6同一共扼根系, 级15，最小多项式(本原多项式)x4+x+

13、1同一共扼根系, 级15/(15,3)=5，方次数4，最小多项式(4次素多项式）x4+x3+x2+x+1另一共扼根系, 级15/(15,5)=3，方次数2，最小多项式(2次素多项式）x2+x+1g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)=x10+x8+x5+x4+x2+x+1(15,5,7)BCH码二、二进制BCH码(3) t=4, g(x)的根为, 2, 3, 4 , 5, 6 , 7, 8同一共扼根系, 阶15，最小多项式(本原多项式)x4+x+1同一共扼根系, 阶15/(15,3)=5，方次数4，最小多项式(4次素多项式）x4+x3+x2+x+1另一共扼根系,

14、 阶15/(15,5)=3，方次数2，最小多项式(2次素多项式）x2+x+1另一共扼根系, 阶15/(15,7)=15，方次数4，最小多项式(本原多项式）x4+x3+1g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1)= x14+x13+x12+x+1140iixh(x)=x+1h*(x)=x+1100.001010.001.000.101000.011110.000011.000.000.110000.011Hg(x)的次数已到极限，而t=5,6,7必须以g(x)为因子，所以等于g(x)。g(x)的根为, 2, 3, 4 , 5, 6 , 7, 8 ,

15、9, 10同一共扼根系 同一共扼根系 同一共扼根系 同一共扼根系 重复码重复码三、多元BCH码 当n很大时，可以查表(p255-259),其中b和z分别表该码纠突发错误能力和最佳程度5. BCH码的扩展三、多元三、多元BCH码码定义：若Fq上循环码的生成多项式g(x)在扩域Fqm上的根含有m0, m0+1, m0+d-2,则称为q元BCH码，d称为设计距离。m0=0或1，为狭义BCH码。g(x)=LCM (m0(x),m1(x),md-1(x)n=LCM(e0,e1,ed-2)定理5 (定理7.1.1,7.1.9)：BCH码的最小距离ddminqd+q-2 (下限称为BCH限）尚有各种距离限，

16、HT限, CHT限, ROOS限, GR限，ER限，LW限等，力图缩小dmin的范围。下面给出dmin=d的两个充分条件。定理6 (定理7.1.7)：若二进制BCH码的设计距离d|n, 则dmin=d。定理7 (定理7.1.8)：若Fq上BCH码的码长n=qm-1,其设计距离d=qh-1,则dmin=d三、多元BCH码汉明码，实际距离等于设计距离（23,12)戈莱码，典型的非本原元BCH码，n2n-1 g1(x)=x11+ x9+ x7+ x6+ x5+x+1或g2(x)=x11+ x10+ x7+ x6+ x5+x4+x2+1d=5, dmin=7其扩展码（24，12，8）用于ITU-T H

17、.324中ITU-T H.261 n384kb/s可视音频业务, (511,493,11)本原BCH码n=29-1=511国际无限寻呼标准（32，21，6）扩展本原BCH码模拟蜂窝移动通信系统TACS和AMPS采用（63，51，5）本原BCH码，下行缩短为（40，28），上行缩短为（48，36）。日本数字蜂窝移动通信PDC采用(15,11)BCH码和缩短的（12,8)和（14，10,3）BCH码，生成多项式g(x)=x4+x+1H.324是用28.8kb/s调制解调器在模拟电话线连接的设备之间共享图像、声音和数据。H.324系列是一个低位速率多媒体通信终端标准，在它的旗号下的标准包括：H.26

18、3：电视图像编码标准，压缩后的速率为20kb/s。H.223：低位速率多媒体通信的多路复合协议。H.245：多媒体通信终端之间的控制协议。T120：实时数据会议标准（可视电话应用中不一定是必须的）。里德索洛蒙 60年构造ReedsolomonFqFqm1. 基本概念基本概念令m=1定义：Fq(q2)上码长N=q-1的本原BCH码称为RS码 g(x)的根：m0， m01 ，m0+d-2最小多项式x -m0，x -m01 ，x -m0+d-2g(x)= (x -m0)(x -m01 ) (x -m0+d-2)一般取m0=1,得 g(x)=(x -) (x -2) (x -d-1)n=LCM(e 1

19、 ,e 2, ed-1), e 1 ,e 2, ed-1 分别为, 2 , , 2的级数 ,其中, 为本原元, 得e 1=q-1, 所以: n=q-1n-k=og(x)=d-1四、RS码-基本概念码域（符号域）与根域一样的多元码域（符号域）与根域一样的多元BCH码码d=n-k+1H的秩为n-k，所以线性码的最小距离dmin上限为n-k+1n-k+1 dmin d =n-k+1, 所以d=dmin =n-k+1,RS码达到上限k=n-d+1=q-1-d+1=q-d 生成（q-1，q-d，d）循环码列向量所张开的空间的维数存在n-k线性无关的列不存在n-k+1线性无关的列由定理4， dmind称为

20、称为Singleton限。达到限。达到Singleton限的码称为极大最小距离可分码（限的码称为极大最小距离可分码（MDS)。定理定理7也也支持支持非系统码：333333110001100011G33662544110010101001G1000010000101110001H36564324 系统码：例：构造例：构造F8上上d=5的的RS码码F8 见表4-1n=8-1=7, k=8-5=3, (7,3,5)g(x)=(x - )(x -2)(x -3)(x -4)经运算F8上的加法、乘法表式化为多项式运算g(x)=x4 + 3x3 + x2 + x + 3四、RS码h(x)=(x7-1)/g

21、(x)=x3+3x2 +2 x + 42 编码电路编码电路q进制(第五章介绍)q=pm ，多项式或m元，当p2用二进制实现乘g(x)电路 非系统码除g(x)电路 系统码n-k级基于h(x)电路： 系统码：n级四、RS码-编码电路h(x)=(x7-1)/g(x)=x3+3x2 +2 x + 4+-hk-1.m(x)C(x)k0n时钟+-hk-2+-h1-h0.+n+k2n寄存器3重，所以为3级乘法：任一元素可以表示为自然基1,2的线性组合？(p127例4.11下面一段，但课本没有说清楚）因为用多项式a2x2+a1x+a0表示,而x为本原元,换为幂表示法a22 + a1 + a0用二进制电路实现用

22、二进制电路实现(p172-174)乘另一元素如2则 2 (a22 + a1 + a0) = a24 + a13 + a02 表示为= a2(2 + ) + a1( + 1) + a02 = (a2 + a0) 2 + (a2 + a1) + a1同理，乘3，则3 (a22+a1+a0) = a25 + a14 + a03= (a2+a1)2+ (a2 + a1 + a0) +(a2 +a0) 乘4，则4 (a22 + a1 + a0) = (a2 + a1 + a0) 2 + (a1 + a0) + (a2 + a1)替代替代课本有错四、RS码-频域编码3. 频域编码信息多项式 m(x) =m

23、k-1xk-1+mk-2xk-2+m1x+m0 c(x)= m(q-2 )xq-2+m(q-3 )xq-3+m()x+m(1)可证，c(x)以,2, q-k 为根, d=q-k频域？频域？有限域的离散傅立叶变换有限域的离散傅立叶变换(p178,定义定义5.8.1): GF(q)多项式多项式a(x) 在在GF(qm)上的谱多项式上的谱多项式A(z)= a(n-1 )zn-1+a(n-2 )zn-2+a()z+a(1) ,其中 =a(i) ，为为GF(qGF(qm m) )中的中的n n级单位原根。级单位原根。10njjjZA10nijiijaA10njjjxa谱多项式也称谱多项式也称MS(Mattson-Solomon)多项式，称多项式，称A=(An-1,A1,A0)为为a=(an-1,a1,a0)的的GF(qm)离散傅立