《信息论与编码》PPT课件(I)

《《信息论与编码》PPT课件(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章循环码第八章循环码内容提要循环码是线性分组码中一个重要的子类。本章首先介绍抽象代数中与循环码直接相关的基础知识，主要包括有限域的概念、有限域的本原元及有限域的结构；然后提出循环码的定义以及循环码的多项式描述方法，给出生成多项式和校验多项式的定义，论述了循环码构成的有关重要定理；接着讨论循环码的编译码方法及其实现电路；最后介绍已获得广泛应用的循环汉明码、BCH码等。8.1有限域及其结构8.1.1域的定义1．多项式几个有关概念：（1）多项式：；（2）系数：fi∈K（集合）i=1, 2, …,n；

2、（3）首一多项式：若多项式最高幂次项的系数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

3、(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)，因为，则0≤r(x)<3，因此剩余类集合就是所有阶次小于3的多项式集合={0,1,x,x+1,x2,x2+1,x2+x,x2+x+1}。定义8.1域是一些元素的集合，在这些元素中定义了加法和乘法两种运算，且满足如下11条性质：（1）对加法它是一个交换群（满足5条

4、性质：封闭性、结合律、交换律、存在幺元、存在逆元）；（2）对乘法它也是一个交换群（满足5条性质：封闭性、结合律、交换律、存在幺元、存在逆元（除去0元素））；（3）对加法、乘法满足分配律：a(b+c)=ab+ac，(a+b)c=ac+bc。1．整数在带余运算条件下构成一个有限域必要条件：模d运算，d必是一个素数。2．多项式在余式运算条件下构成一个有限域多项式集合F[a(x)]被p(x)除所得的余式记为，则剩余类集合构成一个域的充要条件是p(x)为即约多项式。若p(x)=m，则是所有阶次低于m的多

5、项式集合。【例8.5】根据域的定义，判断例8.2中的剩余类集合是否为有限域？（1）在中定义加法、乘法二种运算，满足结合律、交换律、分配律；（2）元素0为加法幺元，元素1为乘法幺元；（3）通过表8-5和表8-6可以看出对于加法、乘法运算都满足封闭性，且都存在逆元。因此是一个有限域将简记为r(x)+01xx+1x2x2+1x2+xx2+x+1001xx+1x2x2+1x2+xx2+x+1110x+1xx2+1x2x2+x+1x2+xxxx+101x2+xx2+x+1x2x2+1x+1x+1x10x2+

6、x+1x2+xx2+1x2x2x2x2+1x2+xx2+x+101xx+1x2+1x2+1x2x2+x+1x2+x10x+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+1１x2+x+1x2+1x+1x+1x2+xx2+1x2+x+1x21xx2x2x+1x2+x+1x2+xxx2+11x

7、2+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、式集合，共有8个元素：将中的8个元素分别用剩余类、α的方幂、的线性组合及二进制三维矢量表示列于表8-7中。剩余类方幂表示的线性组合二进制三维矢量000000111001xαα010x2α2α2100x2+1α3α2+1101x2+x+1α4α2+α+1111x+1α6α+1011x2+xα6α2+α110表8-7GF(23)中元素的四种表示方法加法运算宜采用线性组合表示，乘法运算宜采用幂级数表示。8.1.3有限域的结构定义8.3满足pe=0的最小整数p称为域的特征，其中e为乘法幺元