信息论与编码-第16讲-信道编码-循环码_第1页
信息论与编码-第16讲-信道编码-循环码_第2页
信息论与编码-第16讲-信道编码-循环码_第3页
信息论与编码-第16讲-信道编码-循环码_第4页
信息论与编码-第16讲-信道编码-循环码_第5页
已阅读5页,还剩50页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第1页2024/4/14

第9章循环码9.1循环码的多项式描述9.2循环码的生成多项式9.3系统循环码9.4多项式运算电路9.5循环码的编码电路9.6循环码的译码ElectronicsEngineeringDepartment,XXXXXxxXxxx第2页2024/4/149.1循环码的多项式描述(1)循环码的性质(2)循环码的定义(3)码多项式(4)举例第3页2024/4/149.1循环码的多项式描述(1)循环码的性质循环码是线性分组码的一个重要子类;由于循环码具有优良的代数结构,可用简单的反馈移位寄存器实现编码和伴随式计算,并可使用多种简单而有效的译码方法;循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。第4页2024/4/149.1循环码的多项式描述(2)循环码的定义

循环码:如果(n,k)线性分组码的任意码字:C=(cn-1,cn-2,…,c0)

的i次循环移位,所得矢量:C(i)=(cn-1-i,cn-2-i,…,c0,cn-1,…,cn-i)

仍是一个码字,则称此线性码为(n,k)循环码。第5页2024/4/149.1循环码的多项式描述(3)码多项式

码多项式:为了运算的方便,将码字的各分量作为多项式的系数,把码字表示成多项式,称为码多项式。其一般表示式为:C(x)=cn-1xn-1+cn-2xn-2+…+c0

码多项式i

次循环移位的表示方法记码多项式C(x)的一次左移循环为C(1)(x)

,i次左移循环为C(i)(x)第6页2024/4/149.1循环码的多项式描述(3)码多项式

码多项式的模(xn+1)运算

0和1两个元素模2运算下构成域。若p为素数,则整数全体在模p运算下的剩余类全体在模p下构成域。第7页2024/4/149.1循环码的多项式描述(3)码多项式码多项式的模(xn+1)运算以p=3为模的剩余类全体模3运算的规则如下:第8页2024/4/149.1循环码的多项式描述(3)码多项式

码多项式的模(xn+1)运算码字C

循环i次所得码字的码多项式:

C(x)乘以x,再除以(xn+1),得:第9页2024/4/149.1循环码的多项式描述(3)码多项式

码多项式的模(xn+1)运算

上式表明:码字循环一次的码多项式C(1)(x)是原码多项式C(x)乘以x除以(xn+1)的余式。写作:

C(x)的i次循环移位C(i)(x)是C(x)乘以xi除以(xn+1)的余式,即:

结论:循环码的码字的i次循环移位等效于将码多项式乘xi后再模(xn+1)。第10页2024/4/149.1循环码的多项式描述(4)举例:(7,3)循环码可由任一个码字,比如(0011101)经过循环移位,得到其它6个非0

码字;可由相应的码多项式(x4+x3+x2+1),乘以

xi(i=1,2,…,6),再模(x7+1)运算得到其它6个非0

码多项式。移位过程和相应的多项式运算如表9-1所示。第11页2024/4/149.1循环码的多项式描述(4)举例:(7,3)循环码第12页2024/4/149.2循环码的生成多项式(1)循环码的生成矩阵(2)循环码的生成多项式(3)生成多项式和码多项式的关系(4)如何寻找一个合适的生成多项式(5)循环码的监督多项式和监督矩阵第13页2024/4/149.2循环码的生成多项式(1)循环码的生成矩阵循环码的循环特性:可由一个码字的循环移位得到其它的非0

码字。在(n,k)循环码的2k个码字中,取前

(k-1)位皆为0的码字g(x)(次数r=n-k),再经

(k-1)次循环移位,共得到k个码字:g(x),xg(x),…,xk-1g(x)

第14页2024/4/149.2循环码的生成多项式(1)循环码的生成矩阵这k个码字是相互独立的,可作为码生成矩阵的k行,得到循环码的生成矩阵G(x)。矩阵中的元素是多项式:第15页2024/4/149.2循环码的生成多项式(1)循环码的生成矩阵将矩阵中的多项式改写成对应的n重矢量形式:第16页2024/4/149.2循环码的生成多项式(2)循环码的生成多项式码的生成矩阵一旦确定,码就确定了;(n,k)循环码可由它的一个(n-k)次码多项式g(x)来确定;g(x)生成了(n,k)循环码,称g(x)为码的生成多项式。

g(x)是一个(n-k)次首1多项式第17页2024/4/149.2循环码的生成多项式(3)生成多项式和码多项式的关系定理9-1:在(n,k)循环码中,生成多项式g(x)是惟一的(n-k)次码多项式,且次数是最低的。定理9-2:在(n,k)循环码中,每个码多项式C(x)都是g(x)的倍式;而每个为g(x)倍式且次数小于或等于(n-1)的多项式,必是一个码多项式。第18页2024/4/149.2循环码的生成多项式(3)生成多项式和码多项式的关系定理9-3(定理9-2的逆定理):在一个(n,k)线性码中,如果全部码多项式都是最低次的(n-k)次码多项式的倍式,则此线性码为一个(n,k)循环码。注:一般说来,这种循环码仍具有把(n,k)线性码码中任一非0

码字循环移位必为一码字的循环特性,但从一个非0

码字出发,进行循环移位,就未必能得到码的所有非0

码字了。所以称这种循环码为推广循环码。第19页2024/4/149.2循环码的生成多项式(3)生成多项式和码多项式的关系

码字循环关系图单纯循环码的码字循环图:(7,3)循环码第20页2024/4/149.2循环码的生成多项式(3)生成多项式和码多项式的关系

码字循环关系图推广循环码的码字循环图:

(6,3)循环码(4)如何寻找一个合适的生成多项式循环码的码多项式等于信息多项式乘以生成多项式:对一个循环码只要生成多项式一旦确定,码就确定了,编码问题就解决了。作一循环码的关键,就在于寻找一个适当的生成多项式。第21页2024/4/149.2循环码的生成多项式第22页2024/4/149.2循环码的生成多项式(4)如何寻找一个合适的生成多项式定理9-4:(n,k)循环码的生成多项式g(x)是(xn+1)的因式,即:xn+1=h(x)

g(x)。欧几里德除法:设

b是正整数,则任意正整数a>b

皆可唯一地表示成:a=q·b+r0≤r<b第23页2024/4/149.2循环码的生成多项式(4)如何寻找一个合适的生成多项式定理9-5:若g(x)是一个(n-k)次多项式,且为(xn+1)的因式,则g(x)生成一个(n,k)循环码。结论:求作一个(n,k)循环码时,只要分解多项式(xn+1),从中取出(n-k)次因式作生成多项式即可。第24页2024/4/149.2循环码的生成多项式(4)如何寻找一个合适的生成多项式例:求(7,3)循环码的生成多项式。[解]:分解多项式x7+1,取其4次因式作生成多项式:x7+1=(x+1)(x3+x2+1)(x3+x+1)

可将一次和任一个三次因式的乘积作为生成多项式,可取:g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1

或g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1第25页2024/4/149.2循环码的生成多项式(5)循环码的监督多项式和监督矩阵

循环码的监督多项式:设g(x)为(n,k)循环码的生成多项式,必为(xn+1)的因式,则有:xn+1=h(x)

g(x),式中h(x)为k次多项式,称为(n,k)循环码的监督多项式。

(n,k)循环码也可由其监督多项式完全确定。第26页2024/4/149.2循环码的生成多项式(5)循环码的监督多项式和监督矩阵

循环码的监督多项式:举例:(7,3)循环码:x7+1=(x3+x+1)(x4+x2+x+1)4次多项式为生成多项式:g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g03次多项式是监督多项式:h(x)=x3+x+1=h3x3+h2x2+h1x+h0第27页2024/4/149.2循环码的生成多项式(5)循环码的监督多项式和监督矩阵循环码的监督矩阵由等式x7+1=h(x)

g(x)两端同次项系数相等得:第28页2024/4/149.2循环码的生成多项式(5)循环码的监督多项式和监督矩阵循环码的监督矩阵将上面的方程组写成矩阵形式:第29页2024/4/149.2循环码的生成多项式(5)循环码的监督多项式和监督矩阵循环码的监督矩阵上式中,列阵的元素是生成多项式g(x)的系数,是一个码字,那么第一个矩阵则为(7,3)循环码的监督矩阵,即:第30页2024/4/14(5)循环码的监督多项式和监督矩阵循环码监督矩阵的构成由式(9-18)可见,监督矩阵的第一行是码的监督多项式h(x)的系数的反序排列,第二、三、四行是第一行的移位;9.2循环码的生成多项式第31页2024/4/14(5)循环码的监督多项式和监督矩阵循环码监督矩阵的构成可用监督多项式的系数来构成监督矩阵:

其中h*(x)表示h(x)的反多项式9.2循环码的生成多项式第32页2024/4/149.2循环码的生成多项式(5)循环码的监督多项式和监督矩阵循环码监督矩阵的构成(n,k)循环码的监督矩阵:第33页2024/4/149.2循环码的生成多项式(5)循环码的监督多项式和监督矩阵对偶问题如果xn+1=h(x)

g(x),其中g(x)为(n-k)

次多项式,以g(x)为生成多项式,则生成一个(n,k)循环码;以h(x)为生成多项式,则生成(n,n-k)循环码;这两个循环码互为对偶码。第34页2024/4/14(1)系统循环码构成信息向量:m=(mk-1,mk-2,…,m0)信息多项式:m(x)=mk-1xk-1+mk-2xk-2+…+m0

码多项式的高次幂部分等于m(x),即:

C(x)=cn-1xn-1+…+cn-kxn-k+cn-k-1xn-k-1

…+c1x+c0

=xn-km(x)+q(x)(q(x)的次数<n-k)监督位多项式:q(x)9.3系统循环码第35页2024/4/14(1)系统循环码构成由于码多项式是生成多项式的倍式,所以:C(x)=xn-km(x)+q(x)=a(x)g(x)≡0(modg(x))q(x)=C(x)+xn-km(x)≡xn-km(x)

(modg(x))9.3系统循环码第36页2024/4/149.3系统循环码(1)系统循环码构成

循环码的系统码形式为:C(x)=xn-km(x)+

(xn-km(x)

modg(x))

系统循环码构造过程步骤:

信息多项式乘xn-k:xn-km(x)

对xn-km(x)求余式:q(x)≡xn-km(x)(modg(x))

求码多项式:C(x)=xn-km(x)+(xn-km(x)modg(x))=xn-km(x)+q(x)第37页2024/4/149.3系统循环码(2)举例[例9-5]:在由g(x)=x4+x3+x2+1生成的(7,3)循环码中,求信息码组m=(101)的对应码多项式。第38页2024/4/149.4多项式运算电路(1)多项式加法电路(2)多项式乘法电路(3)多项式除法电路第39页2024/4/149.4多项式运算电路(1)多项式加法电路多项式a(x)=anxn+an-1xn-1+…+a1x+a0表示的是时间序列

a=(an,an-1,…,a1,a0),因此多项式的计算表现为对时间序列的操作;对二进制多项式系数的基本操作为模2加和模2乘;电路图运算符号的意义:第40页2024/4/149.4多项式运算电路(1)多项式加法电路

a(x)与b(x)的相加电路第41页2024/4/149.4多项式运算电路(2)多项式乘法电路多项式乘法电路:第42页2024/4/149.4多项式运算电路(3)多项式除法电路一般的多项式模g(x)=grxr+gr-1xr-1+…+g1x+g0

的运算电路如图所示。移位寄存器初态全为0;当a(x)输入完后,移位寄存器内容(qr-1,…,q1,

q0)就是余式:q(x)=qr-1xr-1+qr-2xr-2+…+q1x+q0≡a(x)

(modg(x))(3)多项式除法电路多项式除法电路举例

(x5+x2)÷(x4+x3+x+1)运算电路工作过程:第43页2024/4/149.4多项式运算电路第44页2024/4/149.4多项式运算电路(3)多项式除法电路多项式除法电路举例第45页2024/4/149.5循环码的编码电路系统码编码电路(1)系统码编码的基本原理(2)用(n-k)

级移位寄存器实现的编码电路第46页2024/4/149.5循环码的编码电路(1)系统码编码的基本原理

求生成多项式g(x):分解多项式(xn+1),取(n-k)次因式作生成多项式g(x),一般可通过查表完成。利用g(x)实现编码:设信息多项式为:m(x)=mk-1xk-1+mk-2xk-2+…+m0

设监督多项式为:q(x)=qr-1xr-1+qr-2xr-2+…+q0(n,k)循环码的码多项式为:

C(x)=cn-1xn-1+cn-2xn-2+…+cn-kxn-k

+cn-k-1xn-k-1+…+c1x+c0前k项系数为信息位,后r=n-k项为监督位。第47页2024/4/149.5循环码的编码电路(1)系统码编码的基本原理

求生成多项式g(x):分解多项式(xn+1),取(n-k)次因式作生成多项式g(x),一般可通过查表完成。利用g(x)实现编码所以:cn-1xn-1+…+cn-kxn-k=xn-k(mk-1xk-1+…+m0)=xn-km(x)cn-k-1xn-k-1+…+c0=qr-1xr-1+…+q0=q(x)第48页2024/4/149.5循环码的编码电路(2)用(n-k)

级移位寄存器实现的编码电路

循环码编码电路结构和工作原理

工作原理:二元(n,k)循环码的编码是将信息多项式m(x)乘xn-k后再除以生成多项式g(x)求出它的余式,即为监督位多项式q(x)。C(x)=xn-km(x)+(xn-km(x)

modg(x))二元(n,k)循环码的编码电路就是以g(x)为除式的除法电路,而输入的被除式为xn-km(x)。第49页2024/4/149.5循环码的编码电路(2)用(n-k)

级移位寄存器实现的编码电路循环码编码电路结构和工作原理实际的编码电路如图9-11所示:其级数等于g(x)的次数(n-k);反馈连接决定于g(x)的系数当gi=0时(i=0,1,2,…,n-k),反馈断开;当gi=1时,对应级加入反馈。第50页2024/4/149.5循环码的编码电路(2)用(n-k)

级移位寄存器实现的编码电路循环码编码电路结构和工作原理由于被除式中含有因子

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论