《编码chapter7.》由会员分享，可在线阅读，更多相关《编码chapter7.（26页珍藏版）》请在金锄头文库上搜索。
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
2、+cn-2xn-2+c1x+c0是一个码字多项 式的充要条件 是HcT=0,其中: 计算在Fqm上进行。 证明：（一）必要性 设c(x)=a(x)g(x)= cn-1xn-1 +cn-2xn-2+c1x+c0 c(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(j)+s(j)=cn-1j n-1 +cn-2j n-2+c1j +c0=0 则s(j)=0，即s(x)在
3、Fqm上的根为1，2，, n-k，又s(x) g(x), 所以s(x)=0 即c(x)=g(x)q(x)，所以c(x)是码字多项式。 (1)n-1 (1)t (1)0 (j)n-1 (j)0 线性相关 把H中的jt(j=1,n-k, t=0,n-1）用Fq上的m重表 示 共扼根 (i )t 去掉线性 相关的行 一、在扩展域从描述和构成循环码 定理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)的根，且：
4、 g(x)根共扼根系级最小多项式 i1 R i1 e i1 m i1(x) i2 R i2 e i2 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中共扼根属于
5、 同一共扼根系，即R i1, R i2, R in-k 中可能重复，而mi1(x), m i2(x), , m in-k(x)有相同。 去掉重复部分 一、在扩展域从描述和构成循环码 方法1：g(x)=LCM (m i1(x) , m i2(x) , m in-k(x) ) 方法2：直接由构造H。 在每个共扼根系选取一个共扼根（一般选次数最小的，计算简单）,得 j1, j2, jw, 构成H: 把H中的j1, j2, jw转为m重，H仍有线性相关的行，在这些行中 保留一行，其余去掉。 一、在扩展域从描述和构成循环码 例（例5.5)：求以F16中, 2, 3, 4, 5为根的F2上的循环码。 分析
6、： , 2, 3, 4, 5 同一共扼根系, 级15， 最小多项式x4+x+1 另一共扼根系, 级5， 最小多项式x4+x3+x2+x+1 另一共扼根系, 级3， 最小多项式x2+x+1 g(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+1 n=LCM(15,5,3)=15 g(x)=n-k=15-k=10, k=5 与课本 不同， 可按个 人习惯 全0， 去掉 相同，去 掉1行 共43-2=10行 二、二进制BCH码 若g(x)在扩展域Fqm上的
7、根为i1, i2, in-k，则 若i1,i2, in-k中含有1,2,d-1, 则抽这d-1行和任意d-1列，得 每一列提取公因式，得 二、二进制BCH码 若i1,i2, in-k中含有1,2,d-1, 则抽这d-1行和任意d-1列，得 每一列提取公因式，得 范得蒙行列式，若g(x)没有重根，即ju， jv, 则行列式不为零，行列式对应的 矩阵满秩，原矩阵任意d-1列线性无关，所以码的距离至少为d。 1. 定理3：Fq上多项式xn-1在最小分裂域无重根的充要条件为 (n,q)=1。 二、二进制BCH码 2. 定义：设F2上循环码的生成多项式g(x)在扩展域F2m上的根含有, 2, 3, ,
8、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属于同一共扼根系，偶数下标一律取消，所以st。 ej为Rj
9、根系的根的级数，含本原元 。 二、二进制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+1 g(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+1 同一共扼根系,
10、 级15/(15,3)=5， 方次数4，最小多项式(4次素多项 式）x4+x3+x2+x+1 另一共扼根系, 级 15/(15,5)=3，方次数2， 最小多项式(2次素多项式 ）x2+x+1 g(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+
11、x+1 另一共扼根系, 阶 15/(15,5)=3，方次 数2，最小多项式 (2次素多项式） x2+x+1 另一共扼根系, 阶 15/(15,7)=15，方 次数4，最小多项 式(本原多项式） x4+x3+1 g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1)= x14+x13+x12+x+1 h(x)=x+1 h*(x)=x+1 g(x)的次数已到极限，而t=5,6,7必须以g(x)为因子，所以等于g(x)。 g(x)的根为, 2, 3, 4 , 5, 6 , 7, 8 , 9, 10 同一共扼根系 同一共扼根系 同一共扼根系 同一共扼根系 重复码 三、
12、多元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限） 尚有各种距离限，HT限, CHT限, ROOS限, GR限，ER限，LW限等，力图 缩小
13、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+1 d=5, dmin=7 其扩展码（24，12，8）用于ITU-T H.324中ITU-T H.261 n384kb/s可视
14、音 频业务, (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+1 H.324是用28.8kb/s调制解调器在模拟电话线连接的设备之间 共享图像、声音和数据。H.324系列是一个低位速率多媒体通 信终端标准，在它的旗号下的标准包括： H.263：电视图像编码标准，压缩后的速
15、率为20kb/s。 H.223：低位速率多媒体通信的多路复合协议。 H.245：多媒体通信终端之间的控制协议。 T120：实时数据会议标准（可视电话应用中不一定是必须的） 。 里德索洛蒙 60年构造Reedsolomon FqFqm 1. 基本概念 令m=1 定义：Fq(q2)上码长N=q-1的本原BCH码称为RS码 g(x)的根：m0， m01 ，m0+d-2 最小多项式 x -m0，x -m01 ，x -m0+d-2 g(x)= (x -m0)(x -m01 ) (x -m0+d-2) 一般取m0=1,得 g(x)=(x -) (x -2) (x -d-1) n=LCM(e 1 ,e 2, ed-1), e 1 ,e 2, ed-1 分别为, 2 , , 2的级数 ,其 中, 为本原元, 得e 1=q-1, 所以: n=q-1 n-k=og(x)=d-1 四、RS码-基本概念 码域（符号域）与根域一样的多元BCH码 d=n-k+1 H的秩为n-k，所以线性码的最小距离dmin上限为n-k+1 n-k+1 dmin d =n-k+1
