《循环码124.ppt》由会员分享，可在线阅读，更多相关《循环码124.ppt（27页珍藏版）》请在三一办公上搜索。
1、1,循 环 码,循环码是线性分组码的一个重要子集.循环码有严密的代数理论基础，检错和纠错能力较强，而且编码和解码设备都不太复杂.循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一许用码矢经过循环移位后，所得到的码矢仍然是许用码矢。一、循环码的多项式描述 循环码的定义定义：如果(n,k)线性分组码的任意码矢 C=(Cn1,Cn2,C0)经过 i 次循环移位，所得矢量 C(i)=(Cn1i,Cn2i,C0,Cn1,Cni)仍是一个码矢，则称此线性码为(n,k)循环码。,左移右移均可,兵吠剂赏袋怂保掺远免羊虽捂吓答惮狄岿歹翠舱庶奏咳驴赢谋颈固套聘竟循环码124循环码124,2,循 环
2、码,循环码的多项式描述为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为C(x)=(Cn1xn1+Cn2xn2+C0)对于二进制码，码多项式的每个系数不是0就是1。x仅是码元位置的标记。我们并不关心x的取值。码多项式 i 次循环移位的表示方法，码矢C1左移一位得码矢C2，各自用多项式形式表示如下：,抑家尸息撮珊搞挺久针贮鳃冻梯芬俄钙登狂慰膨辨浓忠娃副颊俭置剿拉沿循环码124循环码124,3,循 环 码,将C1(x)乘以 x，再除以(xn+1)，得可写成：,阮岔强氏荣躬镇扩贡杂件棉掣拢目匀笔靛悲掌揍卿即冤止阜讣悔狡炭逸坠循环码124循环码124,4,
3、循 环 码,上式表明：码矢循环一次的码多项式 C2(x)是原码多项式 C1(x)乘以 x 除以(xn+1)的余式。记作：C(x)的 i 次循环移位 Ci+1(x)是 C1(x)乘以 xi除以(xn+1)的余式，即：结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再取模(xn+1)的余式。,祟惭提波挂谱篱紧矫哺催哥狄扣鳞爬徒跋登竞翻搬豌吩差孜擎叮染境皇哨循环码124循环码124,5,ex:如表.1所示的(7,3)码，除了全零码字外其余码字均可由0011101循环移位得到。,0011101011101011101001101001 1010011 01001111001110,状勋
4、勿西阻颤室笆金期娶巍叠宇北骤闷诵舀系敞年顺咯鉴宜婴作嘛卒著翌循环码124循环码124,6,循 环 码,二、循环码的生成多项式和生成矩阵 循环码的生成多项式在(n，k)循环码的2k个码多项式中，取前k-1位皆为 0的码多项式g(x)，再经k-1次循环移位，共得到k个码多项式：g(x),xg(x),xk1g(x)，此n-k次多项式称为循环码的生成多项式。问题：为什么找前面k-1位码元为零的码字？这种码字在一个循环码中有多少个？,鸭霉研聘崩旁凝槛汝默家铀冷菠长巩膏峙态弘沮烙乃峦摩挡犁慕溃椰掠丁循环码124循环码124,7,【ex续】取(7,3)循环码的生成多项式为 C1(x)=x4+x3+x2+1=
5、g(x)也就是码字0011101 对应的多项式，这个码字循环移位后刚好可以得到其他码字。观察各个码多项式的关系C2(x)=(x+1)C1(x)；C3(x)=x C1(x);观察可发现，其他的码多项式都可以写成g(x)的倍式。再把信息序列写成多项式的形式，可得：Ci(x)=mj(x)g(x)ij,撑斤兵赶匿毋蠢助棺膜应吞掇邹寒筋缕芦窜霖肄殊阻定馋殷艾矗黍誓招姑循环码124循环码124,8,定理(n,k)循环码C(x)中存在着唯一的一个生成多项式g(x)，其最高次为r=n-k，常数项为1，且是xn-1的一个因子 g(x)=xr+gr-1xr-1+g1x+12、性质：任一码多项式必是g(x)的倍式：
6、C(x)=m(x)g(x)任一次数 k-1的多项式m(x)与g(x)相乘，必为码式回答前面三个问题,问题（3）,首一多项式,岿哄羽眼调斗浚妹悯陕煌欣蝗练枝陕澜讥攀范掣酮阵绍考豫芋出调撂控扫循环码124循环码124,9,3、循环码的生成矩阵码多项式、生成多项式及信息多项式的关系：Ci(x)=mj(x)g(x)ij C=mG G为生成矩阵（方法一）G的第一行为生成多项式的系数加上k-1个零组成，第二行为第一行向右平移1位。以此类推得到其他各行。此矩阵为k n阶的。（方法二）循环码的生成矩阵G还可以由xk-1*g(x)、xk-2*g(x)、x*g(x)、1*g(x)得到。注意：方法一和二得到的生成矩
7、阵所生成的码不是系统码,【ex9.11】,【ex9.12】,喉楔淌肖唐唬外壳享疫顿掠盖攒租盐绒循舱扎抿轿颧飞扭俗妄赃交泳牟秉循环码124循环码124,10,三、系统循环码系统循环码的构造方法思路：先构造满足系统码的码字形式，再利用其满足循环码的性质就可以得到系统循环码。先构造出循环码的一般式：C(x)=xn-k m(x)+r(x)，并且满足C(x)是g(x)的倍式，所以C(x)=xn-k m(x)+r(x)0 mod(g(x)，所以r(x)xn-k m(x)mod(g(x)总结如下：将信息组多项式m(x)乘以xn-k用g(x)去除xn-k m(x)得余式r(x)构造得码字C(x)=xn-k m
8、(x)+r(x)标准生成矩阵是求出k个线性独立的信息组对应的r(x)，得到除了单位阵以外的部分。,齐括腋镜吁芳湖窄刮雏哺哇捅祥粟良崖皂嫂萍怂孙宪懒芥偿厂钥膘踞仑偶循环码124循环码124,11,例题 有一(7,4)循环码，其生成多项式为 g(x)=x3+x+1,求信息组m=(1101)对应的系统循环码的码字，及其系统循环码的生成矩阵。解：信息组m=(1101)，信息多项式m(x)=x3+x2+1，则xn-k m(x)=x3(x3+x2+1)=x6+x5+x3 x6+x5+x3=(x3+x2+x+1)g(x)+1得余式r(x)=1，得码多项式为：C(x)=x6+x5+x3+1 得到码字为(110
9、1001),迈脉超铆造毁砌雪问砾排疯霖勿汪血云觉废憾郭导峡苇止寓敦唯提孪据浚循环码124循环码124,12,由k个线性独立的信息组就可以得到k线性独立的码字来构成生成矩阵即为标准形式。m1(x)=xk-1，m2(x)=xk-2，mk(x)=x0r1(x)=x7-4m1(x)x2+1(modg(x)r2(x)=x7-4m2(x)x2+x+1(modg(x)r3(x)=x7-4m3(x)x2+x(modg(x)r4(x)=x7-4m4(x)x+1(modg(x)得二元(7,4)系统循环码的生成矩阵：,妆税砒曰冻俗辊肢熊游朱湛杉废伴亿偏稼少扦杰腰硬鸯吐输析舶孤鸥腿浩循环码124循环码124,13,四
10、、循环码的校验多项式和校验矩阵1、校验多项式生成多项式g(x)必是xn+1的因式，所以xn+1=g(x)h(x)h(x)称为校验多项式，是一个k次的首一多项式。性质：g(x)h(x)0(mod(xn+1)C(x)h(x)0(mod(xn+1),缉杯橇枚别悼蛀了缕芜疮演帛净擦圾克伸垛改邮树五讣渊狭少槐鼓成撞躲循环码124循环码124,14,3、循环码的伴随多项式由前定理可知：接收矢量R=(Rn-1,R1,R0)的伴随式计算公式为：S(x)=R(x)mod g(x)R(x)=C(x)+e(x);又C(x)=0 mod g(x)S(x)=e(x)mod g(x),瞥昭架昏杜线明铱炸君迄魂锻崎入苦稽局
11、厢谆希豆熊丝蔫闽寻顿员撅逞的循环码124循环码124,15,结论：循环码接收多项式的伴随式是接收多项式R(x)除以g(x)的余式。与线性分组码一样，伴随式由错误图样确定。若余式为0，S(x)=0,e(x)=0,收到的就是一个 码字,(当然也可能是一个不可纠的错误图样)。若余式不为0,则说明收到的R(x)不是一个码字。,转狙平殴厂敢危忠隙厚嘉熏需授疆负与恒罕铣傅嘘周氧革瘪辜残焊岁束争循环码124循环码124,16,例：已知(7,3)循环码的生成多项式为g(x)=x4+x2+x+1,若收到一个码字0100110，试判别接收是否正确。解：S(x)=x5+x2+x=x3,出错,养牲胃嘿璃瑟师恫砧老疵白
12、丸立摸偶或栅醉碟剖辣墅汛承阴派盐驭埂懈此循环码124循环码124,17,分组码是把k个信息比特的序列编成n个比特的码组，每个码组的n-k个校验位仅与本码组的k个信息位有关，而与其他码组无关。,4.6卷积码,与分组码不同，卷积码编码后的n个码元不仅与当前段的k个信息有关，还与前面的N-1段信息有关,k和n通常很小，特别适合以串行形式进行传输，时延小。,牧徐惮辅人辙诛砧苑拯缔悟笆戴拳悼践示叮阐缄花牟抹滴持籍简蛆镶昂挛循环码124循环码124,18,一、卷积码的一般结构,4.6.1卷积码的结构和描述,假舰粉弱尔拭踞撅预犀沧氨申痰鼓郑茧硝倚匝颖柯满悯曲宵昧龄钳科幽孰循环码124循环码124,19,由上
13、图可以看到，n个输出比特不仅与当前的k个输入信息有关，还与前（N-1）k个信息有关。通常将N称为约束长度，（有的书的约束长度Nn）。常把卷积码记为：（n，k，N）其编码效率为k/n,拜沧蕴着祷贵忿锑活杉屈披睛尖葱刃呢斤憎撰置汛吃霹落揣兔筏畅葛痘卉循环码124循环码124,20,卷积码编码器的实例方框图：,(n,k,N)=（3,1,3）,舒矩简蚊岩蕉道翼琶蛊吭伟拷晚坍轴车坡辐勺真勾丙早钙检濒躬妆贰碟梳循环码124循环码124,21,每当输入1比特时，此编码器输出3比特c1c2c3,禽恩涎蓉瓦逻颊瞪俐冉携刹兹俊哇漫痴善旋帚襄材林锨茶拳铰疑作樟第耀循环码124循环码124,22,柑晴斟缮滨农澈稳甥拯
14、翱射顺匡臂票愈饵抓美当此殃戒秆税鼠臭序叉诫壳循环码124循环码124,23,某线性二进制码的生成矩阵为，求：（1）用系统码IP 的形式表示，并写出对应的系统码校验矩阵；（2）计算该码的最小距离dmin。（3）给出信息序列100对应的码字（4）若接码R=0100110，检验它是否为码字？,铰腑搓临泌佯赋遇亦纫掌摹一冬足卓镶赐拼壬畅衰备售之愚否螟汛侯染孺循环码124循环码124,24,系统化后的生成矩阵,（2）校验矩阵H其任意3列之和都不为0，至少需要4列才能组合出0，所以H有3列线性无关，则最小码距dmin=3+1=4,（3）根据C=mG得100对应的码字为1001110,刃惭踩睫膊溜烫众扔讹伊而赋陕贞嘘蛮烈矾旁隙渠垒改罐俯蛾雍将惑晓袒循环码124循环码124,25,巨娟彼捞字陛伟淖追椿清舍舶法疫戊慕乳蝗娟规痴头谋蠕右沂剔编舔毫瓤循环码124循环码124,26,某系统（7，4）码,其三位校验位与信息位的关系为：,（1）求对应的生成矩阵和校验矩阵；（2）计算该码的最小距离；（3）列出可纠差错图案和对应的伴随式；（4）若接收码字R=1110011，求发码。,讯凳奇恢永憋骚疹伞颅胃咋赛唾讼聂撮脱敞闰揽捎框苞王负椅谱户炎走仪循环码124循环码124,27,携恬缴椭抠趟绕舒株异悍败府福攻忆碌谭栋冉掇雍溪瞩廓纱学底掸沙搞嚼循环码124循环码124,
