信息论与编码8.ppt

《信息论与编码8.ppt》由会员分享，可在线阅读，更多相关《信息论与编码8.ppt（47页珍藏版）》请在三一办公上搜索。

1、第八章 循环码,疲沉钳酬狰出赣唐阮哆怕族粹佑将则莆舆憋纠搽毫哀触沾纤啼页笨辊赫令信息论与编码8信息论与编码8,第八章 循环码,内容提要循环码是线性分组码中一个重要的子类。本章首先介绍抽象代数中与循环码直接相关的基础知识，主要包括有限域的概念、有限域的本原元及有限域的结构；然后提出循环码的定义以及循环码的多项式描述方法，给出生成多项式和校验多项式的定义，论述了循环码构成的有关重要定理；接着讨论循环码的编译码方法及其实现电路；最后介绍已获得广泛应用的循环汉明码、BCH码等。,钡藉师鹃骂孺齿违秋拳剿娥舌摄翘蚕绞缄团矿选尊传雌撇际志米蚕除吝俘信息论与编码8信息论与编码8,8.1 有限域及其结构,8.1

2、.1 域的定义,1多项式几个有关概念：（1）多项式：；（2）系数：fiK（集合）i=1,2,n；（3）首一多项式：若多项式最高幂次项的系数fn=1，称该多项式为首一多项式；（4）多项式f(x)的阶次n记为f(x)=n；（5）多项式因式分解：将多项式分解为若干个因式相乘，这种分解是唯一的；（6）即约多项式：阶大于0且在给定集合K上除了常数和本身的乘积外，不能被其他多项式除尽的多项式。,识虚躺翁抚届茅覆硒逃刺凄莎尤喷锹淳焙偏春塑园切医方烦柒瞥十翟帕仗信息论与编码8信息论与编码8,2有关多项式的一些运算,（1）多项式带余除法 若p(x)不能整除a(x)，商Q(x)，余r(x)，记为：a(x)=Q(x

3、)p(x)+r(x)r(x)p(x),（2）多项式模d(x)运算的剩余类集合 多项式a(x)被p(x)所除，余数记为r(x)，称为a(x)的模p(x)运算，就称为对多项式a(x)进行模p(x)运算的剩余类集合。,【例8.2】对系数取自K=0,1的任意多项式a(x)进行模p(x)=x3+x+1运算，设所得余式为r(x)，因为，则0r(x)3，因此剩余类集合就是所有阶次小于3的多项式集合=0,1,x,x+1,x2,x2+1,x2+x,x2+x+1。,谬睡兵绒猩淹牌抄蛔苟悄星勿壬滓土烫寿锈汗搜楷舀使雹蝴粹荧芳看讲斯信息论与编码8信息论与编码8,定义8.1 域是一些元素的集合，在这些元素中定义了加法和

4、乘法两种运算，且满足如下11条性质：（1）对加法它是一个交换群（满足5条性质：封闭性、结合律、交换律、存在幺 元、存在逆元）；（2）对乘法它也是一个交换群（满足5条性质：封闭性、结合律、交换律、存在幺元、存在逆元（除去0元素）；（3）对加法、乘法满足分配律：a(b+c)=ab+ac，(a+b)c=ac+bc。,滔惟拖钾禁纽总漆仿葵奸埂普酪讥招熏缆贾旁诉莎讹葱豌包袖柱鸿陌畴换信息论与编码8信息论与编码8,1整数在带余运算条件下构成一个有限域必要条件：模d运算，d必是一个素数。,2多项式在余式运算条件下构成一个有限域多项式集合Fa(x)被p(x)除所得的余式记为，则剩余类集合 构成一个域的充要条件

5、是p(x)为即约多项式。若 p(x)=m，则是所有阶次低于m的多项式集合。,灸弘真档珊恨秀孙缩苫始逾触窝南姥嗅颧病贡上腻霖很荔车芳笑抡缩众摊信息论与编码8信息论与编码8,【例8.5】根据域的定义，判断例8.2中的剩余类集合 是否为有限域？,（1）在中定义加法、乘法二种运算，满足结合律、交换律、分配律；（2）元素0为加法幺元，元素1为乘法幺元；（3）通过表8-5和表8-6可以看出对于加法、乘法运算都满足封闭性，且都存在逆元。,因此 是一个有限域,将 简记为r(x),焰熏弛吾赏莎伟貉檄窜莱窖诱切悸福厦俞彤烹雌沏赊唤槐达猫洼览褂肮考信息论与编码8信息论与编码8,表8-5 模p(x)=x3+x+1的加

6、法表,痕壳回陷强泞绍拥夯腑姑陪确磺印勿昂粒霍扁捞贡佩伴拢烘狈馋尺膝济呜信息论与编码8信息论与编码8,表8-6 模p(x)=x3+x+1的乘法表,漆琢否漳阂完绰遏感烛停虚赣遮待郡踢闰娃琴初醚暮襄孽徐荔乙拥颠岳汉信息论与编码8信息论与编码8,在上例中,碘菜图抵月巷呕胡统闯蹲蕊些紫镊绥却宽噶状胃应常字植藻恭丛撤奢价猖信息论与编码8信息论与编码8,8.1.2 有限域的本原元,定义8.2 在有限域GF(q)中，若某一元素的阶为q=1，则称此元素为本原元，记为，即 则GF(q)中的其他所有非零元素都可写成的方幂。以本原元为根的即约多项式称为本原多项式。,【例8.7】基域GF(2)=0,1，扩展域，生成多项

7、，是p(x)的根，即 是所有阶次小于3的多项式集合，共有8个元素：将 中的8个元素分别用剩余类、的方幂、的线性组合及二进制三维矢量表示列于表8-7中。,堡阁撼拒扬很掸益脉腺丙爽段吃裁迈苛传榷阂侥谍量铣蚤瘫邹恭僵涕搭铺信息论与编码8信息论与编码8,表8-7 GF(23)中元素的四种表示方法,加法运算宜采用线性组合表示，乘法运算宜采用幂级数表示。,摔噶邮团隔瘤苏完茨瓶柞脑筹望搪迎肤喀熊绦烈牧却乙民霹插揍霓害剃损信息论与编码8信息论与编码8,8.1.3 有限域的结构,定义8.3 满足pe=0的最小整数p称为域的特征，其中e为乘法幺元。,定理8.2 每个有限域GF(q)的特征必为素数。,定义8.4 设

8、GF(Q)是GF(q)的扩展域，GF(Q)，以为根的阶次最低的多项式（系数取自GF(q)），称作在GF(q)上的最小多项式，显然它是即约的（否则就不会阶次最低）。,定理8.3 的最小多项式是唯一的，且能整除任何以为根的多项式。,定理8.4 域GF(q)中的每个元素均是多项式 的根，反之 的根都是GF(q)中的元素。,捉天丰滞师油涟蒸执埋喧蔡愚虐哭限燕窘氓巾应弧岩宦兔诚硷堡焊匝奠尝信息论与编码8信息论与编码8,推论8.1 设 是GF(q)中各元素的最小多项式，则,定理8.5 有限域的阶必为其子域阶之幂。,推论8.2 有限域的阶必为其特征之幂。,推论8.3 有限域其子域的阶必为特征之幂。,定理8.

9、6 设p是有限域GF(q)的特征，n是正整数，GF(q)，则,悍辱雄厉肄骤甩陕静粒平舰煽狈殿狮趾钨杂弄职蛇夜境戎尔咖聋在次前悉信息论与编码8信息论与编码8,8.1.4 最小多项式的共轭根组,定理8.7 对GF(pm)中的任意元素，恒有,。,【例8.10】基域GF(2)=0,1，扩展域GF(23)，生成多项式p(x)=x 3+x+1，特征p=2，任取=（x 2+x+1）GF(2m)，可验算,定理8.8 基域GF(q)，扩展域GF(Q)，f(x)是系数取自GF(q)的多项式，f(x)GF(Q)，若是f(x)的根，则q也是f(x)的根。,罪锨迹令煽财蔬的竹日抒迢须思力澎举她蛮淤纯渐哎环洛匿品净肤茄蒋

10、雷信息论与编码8信息论与编码8,定理8.9 设，共轭根组的最小多项式为：,定义8.5 两个元素共享同一个最小多项式，则称它们互为共轭，同一最小多项式的共轭根称为共轭根组。,由定理8.8知：若是f(x)的根，则 也都是f(x)的根，它们是共轭根组。,瞎抱庄裕症亮哭娱锰砚彭弓骨凶久蝴甄烘岸航形陀息砸组膀笺饼蚌阎究寿信息论与编码8信息论与编码8,有关有限域的小结,表8-8 GF(24)中元素的四种表示方法,（1）本原元；（2）本征多项式p(x)，满足p()=0；,（3）特征：特征是素数,（4）最小多项式；,（5）最小多项式的共轭根组；,（6）的因式分解（等于最小多项式的连乘）；,（7）元素的四种表示

11、法：剩余类、幂级数、线性组合、矢量表示；,（8）素域：p为素数；,子域：；,扩展域：。,屯儡蜡魏敢姚层降幕怯角傻坦酮酷窒挟暇呛达茬孰妖战欺波铜豪殉援类友信息论与编码8信息论与编码8,【例8.12】在GF(2)=0,1系数域上，以p(x)=x4+x+1为模构成有限域GF(24)，在GF(2)上分解多项式x16 x。,（1）由于GF(2)=0,1，e=1，1+1=0，所以特征p=2。（2）本原元 设为p(x)的根，则 4=+1。15=4443=1，因此 为本原元，p(x)为本原多项式。（3）元素的四种表示方法，如表8-8所示：,（4）共轭根组 a,a 8,a 4,a 8 对应最小多项式x4x1；a

12、 3,a 6,a 12,a 24=a 9 对应最小多项式x4xxx1；a 5,a 10 对应最小多项式xx1；a 7,a 14,a 13,a 26=a 11 对应最小多项式x4x1；a 15=对应最小多项式x1；0对应最小多项式x,颇棍裕确剁觅务垮缴砰审吾犹闷君滥噎杆汀坑邦札兽泣谐玄但逾日笔诺影信息论与编码8信息论与编码8,（5）的因式分解,根据推论8.1，有,（6）子域，素域因为16=44，16=(22)2，所以GF(Q)只有一个素域GF(p)=GF(2)=0,1,一个子域,（7）本原元是否唯一？,否!若i与Q-1互素，则 就是本原元，与Q-1=15互素的数有1,2,4,7,8,11,13,

13、14，则 都是本原元，其中 对应的本原多项式为（）对应的本原多项式为,姜哇渗捉饼戊珠倍有钳啡硅挂巡柞诅砧烧怔襟肝织僵宛澎匹儒左尹开畴僵信息论与编码8信息论与编码8,【例8.13】（7，4）线性分组码，生成矩阵，这是一个标准生成矩阵，将其生成的全部16个码矢按重量分类列于表8-9。,8.2 循环码的一般概念,表8-9 将（7，4）码按重量分类,在表中的16个码字中，重量为3的7个码字形成一个循环，重量为4的7个码字形成另一个循环，全“0”码字和全“1”码字可以看成自身循环。,图8-1（7，4）线性码的码字循环图,8.2.1 循环码的定义,潍哭箭汲洛祭鹿托贫肚帝扭真谭黄卤小怠趟持椰状鞍淀呜莱拈循坡

14、套酣驭信息论与编码8信息论与编码8,定义8.6一个（n，k）线性码C，若对任意c=(cn1,cn2,c0)C，将码矢中的各码符号循环左移（或右移）一位，恒有c=(cn2,c0,cn1)C，就称C为（n，k）循环码。,由于（n,k）线性分组码是n维线性空间Vn中的一个k维子空间，因此（n，k）循环码是n维线性空间Vn中的一个k维循环子空间。,滑氖村犀蹲牛删瓣撒骡赘圣二撩拖缄给蒸梳摔屑摈鬼酶谨致鹊并滤含蝗具信息论与编码8信息论与编码8,为了借助代数这一工具研究循环码，可以将一个码矢c=(cn1,cn2,c0)中的各码元ci（i=0,1,n1）看成一个多项式的系数，从而将码矢c表示成码多项式的形式。

15、,码的循环移位可用代数表示，即,码多项式：c(x)=cn1xn1+cn2xn2+c1x+c0,xc(x)mod(xn1)=(cn1xn+cn2xn1+c1 x2+c0 x)mod(xn1)=cn2xn+c1x2+c0 x+cn1,即循环码的一位循环移位可由模xn1下的码多项式c(x)乘以x的运算给出。,后面给出的多项式，都要对其进行模xn1运算。,8.2.2 循环码的多项式描述,昏秀井跌干俞哥新谋鳖批二银脸乐团彰赏诅映悉当寂香慎痊吭悼穷咽跳妮信息论与编码8信息论与编码8,定理8.12（n，k）循环码的生成多项式g(x)，其幂次为nk，且常数项必不为零。,8.3 循环码的生成多项式和生成矩阵,定

16、理8.10说明，只要找到g(x)，就可由它生成循环码，称g(x)为循环码的生成多项式。,那么g(x)是否存在且唯一呢？,g(x)如何找？下面两条定理说明了g(x)的特性。,定理8.13生成多项式g(x)必整除xn1。,8.3.1 生成多项式,定理8.10 设g(x)是码C中的最低次码多项式，则C是循环码的充要条件是：所有非零码多项式都是g(x)的倍式。,定理8.11 在（n，k）循环码C中，有唯一的最低次首一码多项式。,搜务戳句火毕玄送典葡遮澳箍影丈民南渺腮腔契杏能馁得箭荆栓呐入鲁悟信息论与编码8信息论与编码8,综合定理8.10至定理8.13可知，构造（n，k）循环码的的问题在于分解因式xn1

17、，找到nk次多项式g(x)，g(x)就是（n，k）循环码的生成矩阵。将GF(q)上的所有qk个（k1）次信息组多项式与g(x)相乘，就得到qk个码多项式c(x)。,颈捉尿也祷榨贤亿谢白聪猛掀挤届忻碟独刹澈默药侈护摹妆冻万诵努期揖信息论与编码8信息论与编码8,【例8.15】构造（7，4）循环码：要构造一个（7，4）循环码，就是要在x71中找出一个nk=3次的因式g(x)作为码的生成多项式，逐一用所有信息多项式作为乘因子，它们与g(x)的倍式就构成了（7，4）循环码。,分解因式x71=(x3+x+1)(x3+x2+1)(x+1)，前面两个因式都是nk=3次多项式，都可作为生成多项式g(x)，此例中

18、选g(x)=(x3+x+1)，其所生成的循环码如表8-10所示。,表8-10 由g(x)生成码多项式,从表8-10中可看出，除全零码矢（0000000）和全1码矢（1111111）外，其余码矢可分别由码矢（0001011）和（0011101）循环移位得到。,仇湛鹿谬摔政摹攫概挪振途稽根精蔷忌熟抠谬留落乌个砧栈厨蟹篡蔽痹勺信息论与编码8信息论与编码8,（n，k）循环码，设其生成多项式为g(x)gn-kxn-kgn-k-1xn-k-1g1xg0 由于g(x)，x g(x)，xk1g(x)共k个码多项式（它们表示分别将g(x)循环移位0次，1次，k1次）必线性无关，故可用它们组成码的一组基底，而与这

19、些码多项式相对应的k个线性无关的码矢就构造出kn阶生成矩阵G，即,8.3.2 生成矩阵,荆仕尚声培钩霞榆苗介田审渗速无驻劣斥舒嚣褂掌硒缩免屏占裂侩袖肖肤信息论与编码8信息论与编码8,【例8.17】GF(2)中的（7，4）循环码，x71=(x3+x+1)(x3+x2+1)(x+1)，取g(x)=(x3+x+1),生成矩阵为,由g(x)或G都可生成（7，4）循环码。,由g(x)生成：根据c(x)=u(x)g(x)，其生成码多项式如表8-10所示。由G生成：根据c=u G，其生成码矢如表9-2所示。,例如，信息组u=1001，编码为,萝栓皆纶栽违俊培尉柏芳改壬碎掐阵刽涵援悄季驹堕耀陈湾钮堪辆迈裔摈信

20、息论与编码8信息论与编码8,8.4 循环码的校验多项式和校验矩阵,1反多项式,多项式a(x)=an1xn1+an2xn-2+a1x+a0的反多项式定义为,a*(x)=xn1an1x(n1)+an2x(n2)+a1x1+a0=an1+an2x+a1xn2+a0 xn1=a0 xn1+a1xn2+an2x+an1,定理8.14a(x)b(x)=0 mod(xn1)的充要条件是a(x)的系数矢量与x i b*(x)（i=1,2,n）的系数矢量正交。,食喂烦骤制挪苑翠弘处侈串匙俭乍党饯陶肚思晚坑凸犬施隆窄校耻粉萤絮信息论与编码8信息论与编码8,2校验多项式、校验矩阵,已知g(x)整除xn1，记为xn1

21、=g(x)h(x),对上式两边取mod(xn1)，则有0=g(x)h(x)mod(xn1),由定理8.14知，g(x)与xi h*(x)（i=0,1,nk1）正交，另一方面根据式（7-7）有G H T=0，故取多项式xi h*(x)（i=0,1,nk1）的系数为行矢可构成校验矩阵,由于H是由h(x)的反多项式h*(x)得到的，相应地称h(x)为校验多项式。,润形稳乌洼或者佛谱舜捍匠茅藤梳嫩菏占置巨谦棒斡硅蹿己纂是刨综摊榨信息论与编码8信息论与编码8,【例8.18】GF(2)中的（7，4）循环码，x71=(x3+x+1)(x3+x2+1)(x+1)取生成多项式 g(x)=x3+x+1,则校验多项

22、式,h(x)的反多项式 h*(x)=x4(x4+x2+x1+1)=x 4+x 3+x 2+1,校验矩阵,由于循环码也归属于线性码，故同样可利用初等变换将生成矩阵G变换成标准形式的生成矩阵，在（n，k）循环码中，由标准形式的生成矩阵所生成的码字，前面k位是信息位，后面nk位是校验位。,循环码是线性分组码的一个子类，所有线性分组码的性质均适用于循环码。,缔俏王映工券杆龙淫忙痉仁涎蚊锯帐氟潍甄暗同丙感辅顶祥鼠唆悲说笛岩信息论与编码8信息论与编码8,（1）用xnk乘u(x)；（2）用g(x)除xnku(x)，得余式r(x)；（3）组合xnk u(x)+r(x)，得码字c(x)。,系统码可写成如下形式：

23、,8.5 循环码的编码,所以系统循环码的任一码矢可写成码多项式 c(x)=xnk u(x)+r(x),对上式两边取mod g(x)，得（注意到 1、r(x)=nk1；2、任一码多项式c(x)都是生成多项式g(x)的倍式。）,r(x)=xnk u(x)mod g(x),上式表明，将信息多项式u(x)移位nk次，然后用g(x)去除它，余数就是检验多项式r(x)，由此可得编码步骤：,除法电路可用反馈移位寄存器构成,类浑箕蓝弄近腐夸狰霍泪巍樊缄挫拔濒汰果垢丈堕世狰棍爷武儒曰犬受寸信息论与编码8信息论与编码8,【例8.21】GF(2)中的（7，4）循环码，生成矩阵g(x)=x3+x+1，编码电路如下图所

24、示。,电路工作过程：（1）寄存器D0D1 D2预清零；（2）在前k=4个节拍时，门1、门2开，开关S接至B端，信息位 u3,u2,u1,u0由高至低逐位移入寄存器，同时输出到信道，待4个节拍结束，寄存器中就是3位校验位；（3）后=3个节拍时，门1、门2关，开关S接至C端，将寄存器中的校验位依次输出到信道。,例如：对于信息组（1101），对应信息多项式 u(x)x3x21，余式 r(x)x3(x3x21)mod g(x)=1码多项式 c(x)x3 u(x)+r(x)=x6 x5x31对应码矢,表8-15 校验位计算过程,嘲指司矮院挤愤富坚防园霞后畴膘驳灰姚披狂贬遗剖嗣杖运较渗苦组勾搏信息论与编码

25、8信息论与编码8,对于（n，k）循环码，可以定义码的生成多项式g(x)除以接收码字多项式y(x)的余式为伴随式多项式s(x)，写 s(x)y(x)mod g(x)由于 y(x)c(x)e(x)(824)而 c(x)mod g(x)0于是 s(x)e(x)mod g(x),伴随式s(x)计算电路的一个重要性质：,定理8.15 设s(x)是接收码字多项式r(x)的伴随式。则y(x)的一次循环移位xy(x)（mod xn1）的伴随式s(1)(x)，是s(x)在伴随式计算电路中无输入时，右移一位的结果（称为自发运算）：s(1)(x)xs(x)mod g(x),8.6 循环码的译码,8.6.1 伴随式计

26、算,涸医搞段唐凤体攀菱蹲想赣含燃象导匈姚蔓州午事勤赫判跃榆拔嚼报大甜信息论与编码8信息论与编码8,【例8.23】以g(x)x4x3x21为生成多项式的（7，3）循环码（示于表8.11），能纠正一个错误。,设传送出现一个错，错误图样e（0 0 0 0 1 0 0），即e(x)x2，其伴随式 s(x)e(x)mod g(x)x2 mod(x4x3x21)x2，即s（01 0 0）现设错误图样e1（0 0 0 1 0 0 0）,即e(1)(x)xe(x)x3，相应的伴随式s(1)(x)x3mod(x4x3x21)x3,即s1（1 0 0 0）,s1是s在图8.6所示的g(x)x4x3x21除法电路中

27、无输入时，右移一位的结果，也即自发运算的结果。,电路计算s、s1的过程见表9-9、9-10,图8.6（7，3）循环码的伴随式计算电路,用图8-6所示的除法电路来计算伴随式,乎蔼椅治萄肖瘩洲谣秃诸莱悄铜挣朋憋脆券帅派敲悬咎灸甫凳胰妙南惋祁信息论与编码8信息论与编码8,循环码的译码可按以下三个步骤进行：,（）根据伴随式s(x)找出对应的估值错误图样；,（）计算，得到估值码字。若，则译码正确，若，则译码错误。,（）由接收到的y(x)计算伴随式多项式s(x)=y(x)mod g(x)；,根据定理8.15可知，在计算得到接收码字多项式y(x)的伴随式s(x)后，无须重新计算就可得到y(x)的各次循环移位

28、所对应的伴随式s(i)(x)，i=1，2，n1。由于s(x)=y(x)mod g(x)，而y(x)=c(x)+e(x)，又由于码多项式c(x)是生成多项式g(x)的倍式，因此有s(x)=e(x)mod g(x)，可看出若s(x)是y(x)的伴随式，则它也是e(x)的伴随式，而s(x)在伴随式计算电路中自发运算所得的s(i)(x)也就是e(x)的各次循环移位所对应的伴随式。这样就可以把某一可纠正的错误图样e(x)及其所有的小于等于n1次的循环移位归成一类，只需用一个错误图样来代表。译码时只要计算这个错误图样的伴随式，该类中其他错误图样的伴随式都可由该伴随式在g(x)除法电路中循环移位来得到。,8

29、.6.2 循环码的纠错译码,著缀突蹭距陀攻扣昂握讼唾轴逢食笺议荔拽泰枷怂汤肥馏梦猖低放鸡澈舶信息论与编码8信息论与编码8,【例8.24】仍以例8.23中的（7，3）循环码为例。当码字传送出现一位错误时，若用一般译码器，需要识别（0 0 0 0 0 0 1），（0 0 0 0 0 1 0），（0 0 0 0 1 0 0），（0 0 0 1 0 0 0），（0 0 1 0 0 0 0），（0 1 0 0 0 0 0），（1 0 0 0 0 0 0）7个不同的错误图样，但对于按定理8.15设计的循环码译码器来说，可以把这些错误图样归成一类，译码器只要识别其中的一个错误图样就可以了。其译码器电路示于图

30、8-7。,图8.7（7，3）循环码译码器,斧诌席瘟祭坏寂惋枫臆盂与峪蜀子阮孺匪茫脐首叠盖伞债梢臼棺腐悟敏炬信息论与编码8信息论与编码8,设发送码字c=（0 1 1 1 0 1 0），错误图样e=（1 0 0 0 0 0 0），则接收矢量y=（1 1 1 1 0 1 0），伴随式s(x)=e(x)mod g(x)=x6 mod(x4+x3+x2+1)=x3+x2+x，即s=（1 1 1 0）。,译码器工作过程如表8-19所示。,表8-19（7，3）循环码译码过程1,移 位 寄 存 器 状 态,伴 随 式 状 态,清零后在第17拍，接收码字y一方面被送入移位寄存器D0D3，另一方面被送入g(x)除

31、法电路计算伴随式，在第7拍结束时得到s=（1 1 1 0）。随后与门开，并输出纠错信号M=1，对接收码字y的第一位实施纠错，同时M=1信号使D0D3清零。第814拍移位寄存器中的内容依次输出，由于错误码元已被纠正，故输出=（0 1 1 1 0 1 0）。,毫羊恼骑稠交赫款职葛乾捍光乱龚垒姿黄梨泉能垣醒我沽输尹籍齿深长龋信息论与编码8信息论与编码8,循环码译码器的缺点无法对接收到的码字实现连续的译码输出。改进的译码器称作Meggit通用译码器，其结构如图8.8，可实现连续的译码输出。,图8.8 Meggit通用译码器,8.6.3 Meggit译码器,轮燥家舟锋猖汕慨春汤衍辐附虱庶条河梢退威甭浊电

32、购蹬敖友妙魁绳绎侄信息论与编码8信息论与编码8,【例8.25】GF(2)中的（7，4）循环码，生成矩阵g(x)=x3+x+1，利用Meggit通用译码器译码，电路如图8-9所示，图中 代表移位寄存器，由它们构成伴随式寄存器。,译码过程可叙述如下。先考虑接收矢量最高位y6：如果y6出错，则错误图案为e(x)=x6，对应伴随式。如果其他位出错，类似地也可算得对应的伴随式，把各种错误图案所对应的伴随式s(i)(x)（i=0,1,2,3,4,5,6）列于表8-21。,表8-21 各种错误图案所对应的伴随式,掏侵富疆胆志悯俏贿燥元虏馁估恒婚钙诲笑修邢炕瞒纯萍骑忠汹着操病邮信息论与编码8信息论与编码8,定

33、义8.7 设是GF(2m)上的一个本原元，则以的本原多项式为生成多项式的（2m1，2m1m）Hamming码是循环码。,码的校验矩阵为(829）,因码长n2m1，H也可以表为(830),8.7 一些重要的循环码,8.7.1 循环Hamming码,卑泰像擂佩煌设咸才昂制扮察电彦创胯奎碑没琢伟涪钝钒瘴砚很饵秉剔徐信息论与编码8信息论与编码8,例如，以GF(23)上的三次本原多项式为生成多项式，可生成一个（7，4）循环Hamming码，其生成多项式g(x)x3x1。,设是GF(23)上的本原元，则码的校验矩阵,醛臭绢柳渝回绅扭梢七休库苗笑匆评披骗占姑汀仟泪捉窿奖嘲作膛扣澳忻信息论与编码8信息论与编码

34、8,定义8.8 设是GF(2m)上的一个本原元，t为整数，则以含有、2、2t等共2t个根，其系数在GF(2)上的最低次多项式g(x)为生成多项式的循环码，叫做二元本原BCH码。,码长n2m1,校验位数rnk mt,最小距离d 2t1,纠错能力为t,二元本原BCH码的参数为：,8.7.2 BCH码,耳侧黄戳徊侦焙混蜗泉菲鼓重烙盂玖范仗煽饱誉遇赋允簇倚武疯锑题子逻信息论与编码8信息论与编码8,(927),【例8.26】设m4，是GF(24)上的本原元，求码长n24115的二元本原 BCH码。,若t1，则码以为根，即以，2，4，8共轭根系为根，最小多项式 m1(x)x4x1 生成多项式 g(x)m1

35、(x)x4x1校验位数目nk4,码的校验矩阵为,由此生成的（15，11）BCH码就是已经学过的循环Hamming码。,沿软巾飞抡覆目惰庶两勿铺辈旺瓤簿哦驰仟醇郎贝摸号涅雹弹育鞍萎捕挟信息论与编码8信息论与编码8,若t2，则码以，3为根，即以，2，4，8共轭根系和3，6，12，24 9共轭根系为根，最小多项式m3(x)x4x3x2x1生成多项式 g(x)m1(x)m3(x)(x4x1)(x4x3x2x1)x8x7x6x41校验位数目nk8，其校验矩阵,啮苫阂氛耶永新芝章吝互杜僵热近覆弱特军叠瓮丁褐哆蜂镐席姨透织蚤刽信息论与编码8信息论与编码8,若t3，则码以，3，5为根，即以，2，4，8共轭根系

36、、3，6，12，249共轭根系和5，10共轭根系为根，最小多项式m5(x)x2x1生成多项式 g(x)m1(x)m3(x)m5(x)(x4x1)(x4x3x2x1)(x2x1)x10 x8x5x4x2x1校验位数目nk10，其校验矩阵,糟眺拭他甘皂影佃赠岗蜗刻备耀褒猖购吃夜帮狈穆工侵闯过炮瞪脊仪淖址信息论与编码8信息论与编码8,循环码是线性分组码中一个重要的子类，由于这种码的代数结构完全建立在有限域基础上，它是目前理论上最为成熟的一类码。本章的主要内容有：,本 章 小 结,（2）循环码的性质：循环码的生成多项式，生成多项式的重要性质，由生成多项式构造生成矩阵。,（1）循环码的定义及多项式描述：循环码的循环特性，循 环码的码字多项式，循环码是多项式剩余类环的一个主理想子环。,决勤匙赃张茄驻浮始组通鳞递关抠际缓拙蔓掠蛔帛壁粱彬偷黔没满率骄豢信息论与编码8信息论与编码8,（5）循环Hamming码和BCH码：用g(x)的根定义循环码，建立在有限域扩域上的BCH码。,（4）循环码的译码：伴随式的计算电路，自发运算电路，Meggit译码器。,（3）循环码的编码：用生成多项式编码的理论，除法电路，循环码的编码电路。,伯逛搀陪刑虐奔怯跟蒲要爷吴已模伏诲臭句汞迹凯壤罕绝蛊舞蔓花章挨鸽信息论与编码8信息论与编码8,