信息论与编码8.pptx
《信息论与编码8.pptx》由会员分享,可在线阅读,更多相关《信息论与编码8.pptx(47页珍藏版)》请在咨信网上搜索。
1、第八章第八章 循环码循环码第八章第八章 循环码循环码 内容提要循环码是线性分组码中一个重要的子类。本章首先介绍抽象代数中与循环码直接相关的基础知识,主要包括有限域的概念、有限域的本原元及有限域的结构;然后提出循环码的定义以及循环码的多项式描述方法,给出生成多项式和校验多项式的定义,论述了循环码构成的有关重要定理;接着讨论循环码的编译码方法及其实现电路;最后介绍已获得广泛应用的循环汉明码、BCH码等。8.1 8.1 有限域及其结构有限域及其结构8.1.1 8.1.1 域的定义域的定义1多项式多项式几个有关概念:(1)多项式:;(2)系数:fiK(集合)i=1,2,n;(3)首一多项式:若多项式最
2、高幂次项的系数fn=1,称该多项式为首一多项式;(4)多项式f(x)的阶次n记为f(x)=n;(5)多项式因式分解:将多项式分解为若干个因式相乘,这种分解是唯一的;(6)即约多项式:阶大于0且在给定集合K上除了常数和本身的乘积外,不能被其他多项式除尽的多项式。2有关多项式的一些运算有关多项式的一些运算(1)多项式带余除法若p(x)不能整除a(x),商Q(x),余r(x),记为:a(x)=Q(x)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)运算的剩余类集
3、合。【例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.1域是一些元素的集合,在这些元素中定义了加法和乘法两种运算,且满足如下11条性质:(1)对加法它是一个交换群(满足5条性质:封闭性、结合律、交换律、存在幺元、存在逆元);(2)对乘法它也是一个交换群(满足5条性质:封闭性、结合律、交换律、存在幺元、存在逆元(除去0元素);(3)对加法、乘法满足分配律:a(b+c)=ab+ac,(a+b)c=ac+bc
4、。1整数在带余运算条件下构成一个有限域必要条件:模d运算,d必是一个素数。2多项式在余式运算条件下构成一个有限域多项式集合Fa(x)被p(x)除所得的余式记为,则剩余类集合构成一个域的充要条件是p(x)为即约多项式。若p(x)=m,则是所有阶次低于m的多项式集合。【例8.5】根据域的定义,判断例8.2中的剩余类集合是否为有限域?v(1)在中定义加法、乘法二种运算,满足结合律、交换律、分配律;v(2)元素0为加法幺元,元素1为乘法幺元;v(3)通过表8-5和表8-6可以看出对于加法、乘法运算都满足封闭性,且都存在逆元。因此是一个有限域将 简记为r(x)+01xx+1x2x2+1x2+xx2+x+
5、1001xx+1x2x2+1x2+xx2+x+1110 x+1xx2+1x2x2+x+1x2+xxxx+101x2+xx2+x+1x2x2+1x+1x+1x10 x2+x+1x2+xx2+1x2x2x2x2+1x2+xx2+x+101xx+1x2+1x2+1x2x2+x+1x2+x10 x+1xx2+xx2+xx2+x+1x2x2+1xx+101x2+x+1x2+x+1x2+xx2+1x2x+1x10表8-5模p(x)=x3+x+1的加法表1xx+1x2x2+1x2+xx2+x+111xx+1x2x2+1x2+xx2+x+1xxx2x2+xx+1x2+x+1x2+1x+1x+1x2+xx2+1
6、x2+x+1x21xx2x2x+1x2+x+1x2+xxx2+11x2+1x2+11x2xx2+x+1x+1x2+xx2+xx2+xx2+x+11x2+1x+1xx2x2+x+1x2+x+1x2+1x1x2+xx2x+1表8-6模p(x)=x3+x+1的乘法表在上例中8.1.2 有限域的本原元有限域的本原元定义8.2在有限域GF(q)中,若某一元素的阶为q=1,则称此元素为本原元,记为,即则GF(q)中的其他所有非零元素都可写成的方幂。以本原元为根的即约多项式称为本原多项式。【例8.7】基域GF(2)=0,1,扩展域,生成多项,是p(x)的根,即是所有阶次小于3的多项式集合,共有8个元素:将中
7、的8个元素分别用剩余类、的方幂、的线性组合及二进制三维矢量表示列于表8-7中。剩余类方幂表示的线性组合二进制三维矢量000000111001x010 x222100 x2+132+1101x2+x+142+1111x+16+1011x2+x62+110表8-7GF(23)中元素的四种表示方法加法运算宜采用线性组合表示,乘法运算宜采用幂级数表示。8.1.3 8.1.3 有限域的结构有限域的结构定义8.3满足pe=0的最小整数p称为域的特征,其中e为乘法幺元。定理8.2 每个有限域GF(q)的特征必为素数。定义8.4设GF(Q)是GF(q)的扩展域,GF(Q),以为根的阶次最低的多项式(系数取自G
8、F(q)),称作在GF(q)上的最小多项式,显然它是即约的(否则就不会阶次最低)。定理8.3的最小多项式是唯一的,且能整除任何以为根的多项式。定理8.4域GF(q)中的每个元素均是多项式的根,反之的根都是GF(q)中的元素。推论8.1 设 是GF(q)中各元素的最小多项式,则定理8.5有限域的阶必为其子域阶之幂。推论8.2有限域的阶必为其特征之幂。推论8.3有限域其子域的阶必为特征之幂。定理8.6设p是有限域GF(q)的特征,n是正整数,GF(q),则8.1.4 最小多项式的共轭根组最小多项式的共轭根组定理8.7 对GF(pm)中的任意元素,恒有 。【例8.10】基域GF(2)=0,1,扩展域
9、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)的根。定理8.9 设 ,共轭根组的最小多项式为:定义8.5两个元素共享同一个最小多项式,则称它们互为共轭,同一最小多项式的共轭根称为共轭根组。由定理8.8知:若是f(x)的根,则也都是f(x)的根,它们是共轭根组。有关有限域的小结剩余类线性组合幂级数矢量00000001110001x0010 x2220100 x3331000 x+1+140011x2+x
10、2+50110 x3+x23+261100 x3+x+13+171011x2+12+180101x3+x3+91010 x2+x+12+1100111x3+x2+x3+2+111110 x3+x2+x+13+2+1121111x3+x2+13+2+1131101x3+13+1141001表8-8GF(24)中元素的四种表示方法(1)本原元;(2)本征多项式p(x),满足p()=0;(3)特征:特征是素数(4)最小多项式;(5)最小多项式的共轭根组;(6)的因式分解(等于最小多项式的连乘);(7)元素的四种表示法:剩余类、幂级数、线性组合、矢量表示;(8)素域:p为素数;子域:;扩展域:。【例8
11、.12】在GF(2)=0,1系数域上,以p(x)=x4+x+1为模构成有限域GF(24),在GF(2)上分解多项式x16x。(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,a8,a4,a8对应最小多项式x4x1;a3,a6,a12,a24=a9对应最小多项式x4xxx1;a5,a10对应最小多项式xx1;a7,a14,a13,a26=a11对应最小多项式x4x1;a15=对应最小多项式x1;0对应最小多项式x(5)的因
12、式分解根据推论8.1,有(6)子域,素域因为16=44,16=(22)2,所以GF(Q)只有一个素域GF(p)=GF(2)=0,1,一个子域(7)本原元是否唯一?否!若i与Q1互素,则就是本原元,与Q-1=15互素的数有1,2,4,7,8,11,13,14,则都是本原元,其中对应的本原多项式为()对应的本原多项式为【例8.13】(7,4)线性分组码,生成矩阵 ,这是一个标准生成矩阵,将其生成的全部16个码矢按重量分类列于表8-9。8.2 8.2 循环码的一般概念循环码的一般概念表8-9 将(7,4)码按重量分类重量=0重量=3重量=4重量=700000000001011001110111111
13、11001011001110100101100111010010110001101001011000110100111100010010011110001011001110在表中的16个码字中,重量为3的7个码字形成一个循环,重量为4的7个码字形成另一个循环,全“0”码字和全“1”码字可以看成自身循环。图8-1 (7,4)线性码的码字循环图8.2.1 循环码的定义循环码的定义定义定义8.6一个(n,k)线性码C,若对任意c=(cn1,cn2,c0)C,将码矢中的各码符号循环左移(或右移)一位,恒有c=(cn2,c0,cn1)C,就称C为(n,k)循环码。由于(n,k)线性分组码是n维线性空间V
14、n中的一个k维子空间,因此(n,k)循环码是n维线性空间Vn中的一个k维循环子空间。为了借助代数这一工具研究循环码,可以将一个码矢c=(cn1,cn2,c0)中的各码元ci(i=0,1,n1)看成一个多项式的系数,从而将码矢c表示成码多项式的形式。码的循环移位可用代数表示,即码多项式:c(x)=cn1xn1+cn2xn2+c1x+c0 xc(x)mod(xn1)=(cn1xn+cn2xn1+c1x2+c0 x)mod(xn1)=cn2xn+c1x2+c0 x+cn1即循环码的一位循环移位可由模xn1下的码多项式c(x)乘以x的运算给出。后面给出的多项式,都要对其进行模xn1运算。8.2.2 循
15、环码的多项式描述循环码的多项式描述定理定理8.12(n,k)循环码的生成多项式g(x),其幂次为nk,且常数项必不为零。8.3 8.3 循环码的生成多项式和生成矩阵循环码的生成多项式和生成矩阵定理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)循环
16、码C中,有唯一的最低次首一码多项式。综合定理8.10至定理8.13可知,构造(n,k)循环码的的问题在于分解因式xn1,找到nk次多项式g(x),g(x)就是(n,k)循环码的生成矩阵。将GF(q)上的所有qk个(k1)次信息组多项式与g(x)相乘,就得到qk个码多项式c(x)。【例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次多项式,都可作为生成多
17、项式g(x),此例中选g(x)=(x3+x+1),其所生成的循环码如表8-10所示。表8-10 由g(x)生成码多项式信 息 位信息多项式g(x)的倍式码 多 项 式码 矢000000(x3+x+1)00000000000111(x3+x+1)x3+x+100010110010 xx(x3+x+1)x4+x2+x00101100011x+1(x+1)(x3+x+1)x4+x3+x2+100111010100 x2(x2)(x3+x+1)x5+x3+x201011000101x2+1(x2+1)(x3+x+1)x5+x2+x+101001110110 x2+x(x2+x)(x3+x+1)x5+x
18、4+x3+x01110100111x2+x+1(x2+x+1)(x3+x+1)x5+x4+101100011000 x3x3(x3+x+1)x6+x4+x310110001001x3+1(x3+1)(x3+x+1)x6+x4+x+110100111010 x3+x(x3+x)(x3+x+1)x6+x3+x2+x10011101011x3+x+1(x3+x+1)(x3+x+1)x6+x2+110001011100 x3+x2(x3+x2)(x3+x+1)x6+x5+x4+x211101001101x3+x2+1(x3+x2+1)(x3+x+1)x6+x5+x4+x3+x2+x+111111111
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 编码
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。