信息论与编码课件第5章

第五章信息论对于每一个有噪声存在的信确如何来构造这组信号也没有保证在现实世界上确实可以建立起这样的通信系差错控制编码是信道编码的重要组成部。通过线性分组码来阐明码的编码方力。性分组码中，有一类所谓循环码，别是通信系统中在本章最后一。在大多数通自动控制系统和计所以我们也主要是在二元域F2中来讨论纠不难直接推广到任意有限Fq上去。道编码的基本概念一.有扰信道噪噪声是指信息系统中导致有用信号失真信道，噪声不可忽略的信道称为有扰信道。k(t)n(t)，它的存在独立于有用信②自然噪声，③内部噪声。信号在有中的传输过程可用下式来eo(t)=k(t)·ei 其中，ei(t)为发信端发出的信号，eo(t)为接收端收到的信号。我们希望k(t)=K（常数，n(t)=0.ei(teo(t译编解调调制媒质所经过的所有转换器及传输媒质统称为编ei(teo(t译编解调调制媒质5-1广义信道示意 p(y1/x1) p(y2/x1p(y2/x1)p(y1/x2)p(y2/x2)发 收端 5-2二元信道模型5-2所表示的是一般二元信道的模型。p(yj/xi)xiyj的概率，称为转移概率(i,j=1,2).也可以用表格表示，如表5-1；或用矩阵表示，如式(5-P(y/x)

p12

表5-1元信道转移概p(yp(y/x)y1 y2x1x2p(y1/x1) p(y2/x1)p(y1/x2) p(y2/x2)

p22

其中pijp(yj平均错误概率的计算由式（5-3） pep(xi)p(yi/xi

i

jp(y/x)y1y2x10.80.2x20.40.6例5-1p(y/x)y1y2x10.80.2x20.40.6P(y

x)

p(x10.6p(x20.4时，平均错误概率pe=p(x1)·p(y2/x1)＋p(x2)·p(y1/x2)=0.6×0.2＋0.4×0.4=无二元对称信道，而道为对称信道。在二元信道中，若p(y2/x1)p(y1/x2)的数字信道我们所讨论的主要种信道二元删除它的模型5-3所示。其中q为错误概1率，x

pqpqx15-3BEC号按错码分布规律的以下态分布的白噪声引起的错码就具有这种性产生突发错码的主要原因是脉冲干扰和信道现象。响，则需从其它途径解决。进行信道是其中一种重要而有效的统的能力。由于我们仅讨论第二类，近年来，编码理论发展十分迅速。主要拥挤。如何有效地利用信道，可靠地So/NoB按指数律增加。而调集成电路和计算机通信的发展也是编码理下面我们以打为例来说明信道编“别用01当收0时就认为是无雨，当收到1时就认为是有雨。当把0错收为1时，就会把无雨当成有雨。我000表示无雨111表示有雨。例如，发送000时，由于干扰而错收为010.在假定三个码元中最多有一个码元发生错误时，我们就可以认为发送的是000，而不是111.这样的编码具有纠正一位错码的能多可有两个码元发生错误，例如，把000错收为011，我们就无法确定发送的是哪一个个码元都发生错误这样可能会将000错收为111这时， 仍以上述为例，假如老王只是一个那么他可以，但是无法确定是哪个字听错了进制数来表示，见表5-2。但是这样的代码错，都会使一个消息错收成另一个消且无法被接收者发现如果将上述1位码“1偶数个,如表5-2所示收端就可以发现代码中的1位3位错码，但是无法确定哪一位

5-2监晴0云1阴1雨0“1代码中原有的代表消息的码元称为信息督位n位长的码字。这些码重复码和奇偶监督码是两种最简单的编一种适合实际需要既具有较强的现的编码。这就是对信道编码的基本要道编码的分检错码只能在译码中自动发现错误纠错码不仅能发现而且能自动纠正纠删码能自动纠正和删除错误根据信息元与监督元的关系线性码监督元与信息元之间是线性关系。非线性码监督元与信息元之间不是线性关分组码监督元仅与本组的信息元有卷积码监督元不仅与本组而且与前后若干纠正随机错误的码；纠正突发错误的正混合错误的码；纠正同步错误的码述划分方法用图5-4来表示。5-4信道编码分类检错重发法（ARQ）接收端在收到的前向纠错法（FEC）接收端在收到的反馈校验法收端将收到的消息全部返回到发端，由发端进行检测，发现错误后，ARQ系统组成方框图发发收检错检错纠检纠检5-5差错控制方法信编和缓存双向译缓存信源重发控指令产错误时宿图5- 组码和信道编码定理一.分组码的概念它分成信息组，每个信息组有k位码元，因而可有2k种不同的全体构成F2{0,1}上的一k维向量空间，记作：Vk(F2).Vk(F2)={(mk－1mk－2…m1m0=0,1,…,m表示。m=(mk－1mk－2…m1m0的能力把每个k位长的信息组变换（n＞k.A称为码长n，信息位为k的码r=n－k位，它们不含有信息，但可r个监督元可以分布在码字的不同位置上，若恰好集中rk位码元衡量分组码性能的一个重要参数是分组用R表示：R=k/ 分组码的另外两个重要参数是码重码距abA中的两个码a=(an－1an－2…a1b=(bn－1bn－2…b1b0)定义为码0码元的个数，wa表示 ai∈F2时

wa

i0

ai∈Fq

waai0所有非0码字的码重当中最小的一个称最小码重wmin表示定义码距又叫汉明（Hamming）距离，值不同的个数d并用dmin≠0)表ai,bi∈F2时，d(ab

aii

aibi∈Fqd(a,b)

1i0aibia= ),b= )码字awa=4b的重量wb=3码字ab之间的距d(ab5设某种三进制码中的两个码字为a= ),b= )码字awa=4b的重量wb=3码字ab之间的距d(ab5{00000011001}它的最小码wmin2;最小码dmin2除了上节介绍的重复码和奇偶监督码之二维奇偶监督码（方阵码它是把上述奇偶监督码的若干码字排成的方向增加第二监个监行。如图5-7所示，最右边的一列是一维a21

a22am

a2n amn5-7。能被发现数情形的错误不能被发现。。方阵码保留了一维奇偶监督码的编码效率高的优点。当码长为n时，一维奇偶监督.→1m－1n位长的码字构成一个矩阵，再加上一行监督位行，则构成一个×n阶矩阵。它R=(m－1)(n－1)/mnmn→∞时，同样R等重码（恒比码当每个码字中所含1的个这种编码为因为1的个数恒只要计算接收码字1知道是说，它能够检测出码字中除了“0变1”与“1变0”成对出现错码之外的其它所有错优点：简单和适合做各种键盘字符的代缺点：是剩余度大，编码效率低其中每字都有三个1和两个0.因为组5合数C3=10,所以码集中共有十个这样的改进后能使错码率降至原来的十分之一左右表5-3a是五单元国际电码中的数5数保电国电数保电国电1627384950取三码其中每字都由三个1和四个

335个码字。见5-3b75-3b国际通用七中取三 001101 010101 001100 100010 100110 011001D001110 100100 011100 010010 001001 001011G110000 001010H101001Z011000 111000100001J010001101100 000101010011 110001000111 101000110100 101010(不用000011 100011011010 100101α010100 000110β010110 110010正反，1的个数而定。现以电报通信中常用的五单元电码为例说报通信用的正反码的码长n=10..位中有奇数个1时，监督位是位中有偶数个1时，监督位是例5-3若信息元为11001码字为.接收端译码的方法先将接收向B的前五ML异或，得到一个合成码组Q，即：B= Q=然后，由此合成码组产生一组P.产生的方法仍按“偶反奇不反”的规则M中有1P最后根据P中1的个数进行并纠正①若P=00000，则无错码②若P中有四个1和一个0，则信息元在与P中的0对应的位置上有一位错③若P中有四个0和一个1，则监督元在与P中的1对应的位置上有一位错④若不是上述三种情况，则接收序例5-4发送码字为A 码组Q11001⊕11001＝00000.M中有奇数个所以，P=Q=00000.根据规则①，无错码若B= ，则合成码组Q=10001⊕11001＝01000.由于M中有偶数个所以P=Q=10111.根据规则②，信息元在第二位上有若B= ，则合成码组Q=11001⊕01001＝10000。由于M中有奇数若B= ，则合成码组Q=10011⊕11001=01010。由于M中有奇数个1，所以，P=Q=01010。根据规则B中有多个错码。R=0.5。汉明（Hamming）使码字中1的个数为偶数关系可an－1⊕an－2⊕…⊕a1⊕a0= 因为在偶监督码中1的个S0在接收端按式(5-7)为校正子或伴随式由于S0和1无错有错(5-7)类似的监督方校正子S1和S2)00011011例如前面的重复码{000,111}就具有这A=(a2a1a0)，则有a2a1a0，即a2a1，a2a0，a2⊕a10，a2⊕a00。因此它的两个监督方程为

S2

S2

容易验证SS1S200时，表示无错S=11,10,01时，分别表示码元a2,a1,a0发生了错误。而把a1a0们也可a1a0当做信息位，而把其余两位

S2

校1 校111110101011100010001000无若继续增加监督码情况。一般说来，增r个监督码元，可以产生r个监督方程，能组码，其监督位数r=n－k，若想指示出所有一位的错码情况（共有n种，则要求：2r－1≥n或2r≥n＋1 能使式(5-10)中等号成立的编码就是汉明码。可见码长n=3的重复码同时又是一种汉明下面再举一个例子来说明如何具体构造5-5设(nk)分组码k4为了能纠正一位错码，根据式(5-102rn＋1k＋a6a5,…,a1,a07S=(S1S2S3)表示三位校正子，并按表5-4建立校生在a6a5a4a2S1=1，否则S10这就意味a6a5a4a2四个码元与S1有关，可构成一个偶监督关系式：a6

S1a6

S2

a6

S3a6a5a6a5a6

0

a6a5a4a3当作信息位，把其它三位a6

a2a6

a1

a6

a0可见，只要给出信息位a6a5a4a3,就可按上式求出a2a1a0的值而可以得到这种码的全部码字，见表5-5.5-5(7,4)汉明码信息监督信息监督a6a5a4aa2a1aa6a5a4aa2a1a0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111当接收到一个n元序列时，先按式(5-11)并予以纠正。例如，接收到的n，由式(5-11)可求得(S1S2S3)= 不难求出，汉明码的编码R=k/n=(2r－1－r)/(2r－1)n很大时，R趋近1.所以，汉明码是先介绍几个发送向量：aan－1an－2…a1接收向量：bbn－1bn－2…b1错误格式：een－1en－2…e1e0a⊕b，其中ei=ai⊕bi;i=0,1,…,(n－1)。e1的个数ab时的ab的汉明距离等于t时，我们就t重错误图样。由概率的知识可知，ab的概率为pt=pt(1－p) pt＋1=pt＋1(1－p) 用式(5-15)去除式(5-16K=pt＋1/pt=p/p＜0.5时，有K＜1，即：pt＋1pt上述结果表明，码字在平均错误概率0.5的二元无信道中传输时,发生一个＋1)重错误的概t重错误的.绝大多数信道中p<<0.5但在理论证明过程中，还必须考虑p>0.5的情况，而在况下，只要把接收向量取反码就一定可使p<0.5，从而上述p=0.5而错误重数等于发送向量与接收向量间的离的性质，然后，再给出最小码dmin与纠汉明距离的性质对任abc有d(a,b)

0a

⒉对称性：d(a,b)=d(b, d(a,b)＋d(b,c)≥d(a, 明距离的定义来证，下面只证性3。aan－1an－2…a1a0bbn－1bn－2…b1b0),c=(cn－1cn－2…c1c0)。ac时，由性1d(ac0仍由性质1的非负性可得式(5-19)的左端≥0故=ci不能同时成或者ai≠bi,或者bi≠ci，二者必居其一。因此式(5-19)总有左≥右，于是性3成立。定理5-1码距dmin与纠检能力的关A是码长为n的分组码，最小码距dmin总存在tt1t2使下列命题成立dmin≥t＋1时，A是可以检测所≤t重错的检错码tdmin≥2t＋1时，A是可以纠正所≤t重错的纠错码tdmin≥2t1＋t2＋1时，A是可以纠正所有≤t1重错并同时检测≤(t1＋t2)重错的纠检码，简称为“t1(t1＋t2)码”证Ai（≤t的错误图样，由性质3得d(Aj,Ai＋e)＋d(Ai＋e,Ai)≥d(Aj,Ai)≥t＋1由假设d(AiAi＋e)≤上式减去此式得：d(Aj,Ai＋e)≥t＋1－t=1此式说明，A中任字发生≤t重错误都对于(2)dmin≥2t＋1e重数≤t的错误图样，由性质3得d(Ai＋e,Aj＋e)＋d(Ai,Ai＋e)＋d(Aj,Aj＋≥d(Ai,Aj＋e)＋d(Aj,Aj＋e)≥d(Aj,Ai)用此二式去减上式得Aj＋e)此式说明，A中任意两个码字发生t重错（已知dmin≥2t1＋t2＋1，设是t2]区间的错误图样dmin≥2t1t2＋1>2t1＋1,（2）t1重的＋＋(＋,A＋(＋,d(Ai＋e d(AjAj＋e)≤t1用此二式去d(Ai＋e,Aj＋e)≥1A量能在纠正t1重错的同时检测(t1＋t2)重错。 上述结论的几何解释见图5-8.11t11tt1 例5-6某分组码A={A1,A2,A3,A4}。其中 A1=(000000),A2=(011101),A3=(100111),A4=(111010).容易求得其最小码距为dminmin{d(Ai,│i,j=1,2,3,4;i≠j}=4dmin3＋1t3.A可3码，它可检测所有≤3重的错误dmin＞2×1＋1，即t1dmin=2×1＋1＋1t1=1，t21,t1＋t22,A可作成纠12码。它由于经过信道编码的数字信号具有一定码错误率即误码字率pw.下面介绍它的计i重错误的概率为：pi=pi(1－p)当码长n时，所有可能i重错误图样nCi种，所以码字中发in概率为pCpC

i=

ipnC假定这种码的纠检能t，即能纠正或检t重的接nC1

i

CCp(1n

p)ni从而得到误码字率为1pip i

pi(1

p)

或

it

pi(1

p)ni

5-7仍以上例中的分组码A为例。信道平均误码率p=0.01误码字pw解：上例中码长n6（1）A被用作检错码时，它的检错能力=根据pi=pi(1－p)n－i，可求出p0= p1= p2= p3=9.70299×10－7 又∵C60= C1= C2= 63=6 i从而得误码

1C6i

i（2）A被用作纠错码时，它的纠错能力=1，可得误码字率为16wi 1Ci6wii

t2=2，同理可得误码字率为：1Cpipi ii

检约降低为原来68用作纠错码低为原来的6.8分之这种可靠性的提高是以有效性的降低为代价A中只有klog42，而码n6位，编码效率只有三备码与汉明错码，必须增加r个监督r个监取值共有2r码情况建立2式右边的第一项表示n个码元都不发.n生一位错码的情况n种，即C1nn要纠正两位以下的n码元中发生两位错码的情况有C2n位错码与一位错码是完全不同的情况共有(C0＋C1＋C2)种情况。因此码字 督元的个数2

0

＋C 码字中所有≤t则监督元的数目必须满足nn或

0

1＋…＋Cnntnn2r

Ci

nin称式(5-22)为汉明不等式若恰有一种编码使汉明不等式中的等号成立，则称这种码为完备码。在完备码中，较正子的取值恰好与所有≤t重的错误图样有≤3重的随机错误。我们借助计算机，在n≤4096的范围内，除了汉明码和重复码之组为(n,krt2312113),另一组为(n,krt9078122).前者正是上述的(23,12)码，后者为(90,78)码。不过人们(90n还存在满足汉明不等式的以上的讨论仅限于二元域q元内讨论，汉明不等式应改为下式tnqr(q1)iCini人们在三元域内(q3)还找到一种纠多错的完备码，即(11,6)码，它可以纠正≤2位的2r2nk

2k

Ci

2k ntintCni0令此式右端的值的整数部分为M 2 2tM t

Ci

nM为汉明界2k≤M，它表示准用码组的个数不得超M.我们总希2k等于M.但是寻找完备码是很的，人们只五.信道编码定理（香农第二编码定理从分组码纠检能力dmin的关系来看要想提高纠检能力，必须增大dmin，也就是要增加监督码元的数目。似乎要想无错传YCH就要无限增大监督码而使编码效率R无限YCH一个出乎意料的结论只要信息速率不超过

定理5-2香农第二编码定理将熵为H(bit/符号)的信源接至信道容量为C(bit/符号)的有错系统时，则有：H＜C，总存在着无错传输的编码H＞C不存在无错传输的编码方法H＞C（这个定理可以用图5-9来表示（（是严格的证明（对证明感的读者请看本书末所介绍的有关参考文献设信道输入端的熵为H(X)CmaxH(X)H(XP(

/Y

CmaxH(Y)H(Y/XP(又设信源消息的熵H，将消息序列k有2kH个就几乎是全部。再从信道码2kH(X)个码元序列作为码字。适当安排码符HH(X)＜C并建立消息H(Y/X)x1就和2kH(Y/X)个接收向量的y1相对应；同样x2对应y2；…，xiyi；…。如果这些向量的集合y1,y2,…,yi,…不，也就得随着k的增大可使部分的概率趋于零。又因为接收向量总共有2kH(Y)以它所包含的yi2kH(Y)/2kH(Y/X)=2k[H(Y)H(Y/X)]H(Y)－H(Y/X)＜C，这就说明了只要2kH2kC，就可以实现无错编码，相当于图反之若y1,y2,…,yi,…之间有则不这时，在信息kH中，只能传kC的信息量k(H－C)的信息量不能传输，故H(X/Y)为(H－C)5-9（3）区pwenE(R) 其中pw为误码字率；n为码长；E(R)为误是信R＜CE(R)＞0息速R小于C，就能保E(R)0，于是n→∞时pw→0。但在n间是有的纠错编码理论本身正是在为了说明香农第二编码例5-8设有一个随机产生二进制序列的信源和一个平均误码率p0.01的二元对称信道。若直接传送

码00000001101001则误码率显然为0.01.R=k/n=0.5的编码效率进行编码。先k=2分组，然后编出码长为4的(4，2)的分组码。组和对应的码字如表5-6所示。译码码字12个禁用码组别列于码字之收向量落入哪一列就译为哪一列所对应的5-7(4,2码码由译码表可以看出发送的码字在传输5-7可以计算出这种(42)码的误码字率约0.0103，几乎和原来一样。（6，3）此时保持不变。其编、译码表见表5-8由表5-8可知，发送码字的六位码元中任字率降低为0.00136，约为原来信道误码率的七分之一。可见R不变的情况加码长为n可以使误码字率迅速下降组性分组码一.线性分组的定义和性质对于分组码n按前述译码查找工作量从含有2n个向量的译码表里查出接收向量所在的位码表都无法建立据估计整个系里原的个数101402465即使用个原子存贮一个码字，也只能存贮2465个码) 看作是n维向空间Vn(F2)中的一个向那么，分组码的全部码字一定是Vn(F2)的一个看作线性代数中的一种代数结构——线性Vn(F2)F2上的nA是它的一k称A是码长为信息位为k的线性分组码，值得的是Vn(F2)的加法群的子群一是个线性子空间，因此我们说，如果A是A线性码的性质封闭性根据群的性质可知，线性分组AVn(F2)2加法和仍然在A的模22加与模2减是等效的，故将A2A1=A2⊕A3恒等性因为对任意Ai∈A，有Ai⊕0=0⊕Ai=Ai个码字之间的距离必然等于另字的重线性分组码的最小码距等于它的最小码重，即dmin=wmin.这就为我们寻找它的最小码利用性质12，我们可以方便地上节5-8所给出的(6，3)码二.线性分组码的构造原理和生成矩k维子空间的基k个线性无关的向量组成的。设(n，k)线性码A的一组基底向量为g1g2,…gk,用它们构成一个kn的矩阵g1g gG 2

...g g kAi=Mi·G其中Mi=(mk－1，mk－2，…，m0任一信息组这里2乘及模2加都用算术乘和算2乘及2加。反之，g1,g2,…,gk的任意一个线性组合都是A中的码向量G叫做线性码A的一个生成矩阵A都可比其编的存贮量可由原来的2k个码向量减少Gk个向k465时，只要存465个向量就够了。由于A的基底不是唯一以同一性码A，可以有多个生成矩阵。由线性代数的理论可知，F2上的两个秩为k的k×n阶矩阵GG′是同一线性A的两个生成矩阵要条件是存在一个k阶可逆矩阵K，使KG=G′，或者说GG′行等对其另一个。因此，要确定一切码长为n，维数为k的二元线性码，只要定出F2上的一组两两不行等价的秩kk×n阶矩阵即定义单位列单位阵I中的每一个列向量都称为单顺序分别记作I1,I2,…,Ik.即：II1I2Ik定义典型阵如果一个k×n阶矩阵V的前k列恰好构成一个单位阵，则称矩阵V为典型阵，记做Vo.Vo=[Ik,Q定义准典型k×n阶矩阵矩阵V为准典型阵，记Vs.定义非单位列矩阵中未被选作单位所有的非单位列按顺序构成的矩阵记Qs.如果只G进行行初等总能将它化Gs=[l1，l2，…，ln] 其中lii1，2，…，n)Gs中的列向量。假定在n个列向k个单位列：li1,li2, ,lik若用GsM进行编码，即：MA,则有ai1mk－1,ai2mk－2,…,aikm0即码字中的i1,i2,…,ik位码元分别与信息组的第k－1,k－2,…,0位相其余的码mk－1,mk－2,…,m0的的线性组合。因此，我们可以把码字中的i1,i2,…,ik位看如果不仅对G进行了行进行了列置换，那么总能化成典型阵G0 [Ik,Q] 其中Ikk阶单位矩阵，Q是任一k×r阶矩阵(r=n－k).可以看出G0所生成k位就是原来的信息位，后r位则是监督位，称种码为系统码。而典型生G0就是系G经行初等变换和列置换后GGG″不能生成同一能力的是码字中1的个数G先经过行初等变换得到G′，因为它们是行等价的，所以可生成同空间A；而再由G′经过列G″，由于列置换不会改变码向量中1而不会改变码的纠检错能力G″生成的码空间AA″相同的纠检错能力且称GG″互为组合5-9在以前介绍的汉明码的例子

a6

a2a6

a1

a6

a0若用矩阵表示，可

11Q00

00 11 Q的左边补充一k阶单位阵便可得到典型生成矩G0：04 04

00,Q

0 0 1 1任意给信息都可求出它所对应的码字Ai= 对所有的码A 0000001110011010101011000G'00不难验证，由G′所生成的码空间与表5-55两列对换得G″： 1G" 1

0 0 1 1不难验证，由G″生成的码空间A″跟原的最小码距与A的最小码距相等三.线性分组码的监督矩1101110101010101100

a a5 此式还可以简记为

a0a

H·AT=O 或A·HT=

H

0,Aa6a5a4a3a2a1a0,O 我们称H方程的定义可知个码向量都与H的各行H进行一切可能的行初等变换，仍能使式(5-31)Hr的线性组合构成了一个r维的线性子空间A*.A*中的每一个向量都A正交。由对偶空间的定义A*与A互为对偶空看作是一个(n，r)线性码A*A互为对偶码。HA*的生成矩阵。A的生成矩G同时又A*的监督矩阵。=BHTOB一定是码向量。BHT≠OB不是码向量。E，则B=A＋E，代入监督方程S=BHT=(A＋E)·HT=AHT＋EHT(5-已知AHT=O，故有 EHT 式中S为较正子伴随式式可知，S只与错误图样E有关送向A无定理5-3监督矩阵与纠检能力的关系定理A是个线性分组码H是它的一个监督H的任意t列都线性无关，而H有(t＋1)列线A的最小码重等于(t＋1)A是可t重错误的检错码；或者是可以纠正所证：用反证法。设码向量Ai∈A，其重量wt，Ai(an－1an－2…a0).又设A的监督矩阵Hhn－1hn－2…h0]hi为列向量。则AiHT=O.等于0.设它们ai1,ai2,…,ait.ai1hi1＋ai2hi2＋…＋aithit=0此式表明H中有一t的列向量线A中没有重量t的码向量再根据定理条件H(t＋1)列线性相关，A中就有重量为(t＋1)的码向量。A的最小码重wmin=t＋1由线性码的性质可知，A的最小码距dmin=wmin然后直接定理5-即dmin与纠（证毕四.生成矩阵与监督矩阵由线性代数的理论n维向空间中对于其中每个k维子空间A，总存在一个与A*就是(n－k)G的秩k，H的秩为(n－k).因为AA*互为对偶空间A*·AT=O，又G∈A，H∈A*所以：A*·GT=O，A·HT=O，G·HT=根据这些关们对GH，只要知典型阵互求典型矩G0H0的互求设典型生成矩阵为，G0IkQ]则它所对应的典型监督矩阵：H0P,Ir].5-10（53线性码的典型生

G0

00kk

00

,则它的监督 P,

1 1其中

P

rnk53生成矩阵（或监督矩阵如果有可能，一般总是先把它化成典型再利用G0矩阵G）来。

G

11通过行初等变换得到；

00

HH

1 1由于HH0是行等价的也就是所要求的H上面的方法只有当Gk列能够假定Gk列不就把它看作对偶空间A*的监督矩阵要求的HA*的典型阵互求法，可以很快地求出H来。

G

11 G

1

换 100换001100010

0HH

G*

具Gkk列都不能化成单位阵，那么这些方法就要失效5-13设生成矩

G

11Mm2m1m0)，A=(a4a3a2a1a5)，由于MGA，即:(m2m1m0)·G=(a4a3a2a1a0)

式(5-33)＋式(5-35)a4=式(5-35)＋式(5-37)a2=将式(5-34)(5-36)式代入式(5-38)(5-39)式经整理得到两个独立方程

a

a2 它们构成了监督方矩阵

要求的监督虽然解方程组互求法克服了前两种互求法n较大时，这种方法是很繁面介绍一种既简便又通用的互求法——准GH时，其步骤如下（若给定H要求G时，只要将GHPQH,G,Q,P即可）k个单位列的先后顺序不变，但它们可以散布在n列中的任何位置上）由非单位列按顺序构成QsPsQTs按下列规则构成Hs（Hs仍是一个规则1Hs中的单位列按Gs中规则2Hs中的非单位列由Ps的各列求的监督矩H.5-14仍以前面的例子G化为准典型阵

G

1

1

注：Gs1、3、4列为单位列，相当于一Qss s

P

s1 s1s按上述规则构成ss s

02、5列为单位列Gs中的非单位依次填入Ps的三个列向服了典型阵互求法不通用为快速互求法时尽G矩阵k列可Gs,Hs来。0100111001101001111000G 0 0G367列已经是单列了k=4产生一个单位列就可以了又看到第1,5两列都各有两个可以很快化为单位一列。G

G 0101

0 000100110111101010110010

0101

0 000 00后三00

11（2）Gs1367列为单位列24524,5并转置

HH

0 0 如果Gs的单位列恰好k列时，这种首先证明一个引理：K·KT=I.K是列置换所对应的矩阵假定这种两列互换t次，依次设为K1，K2,…KtKK1…Kt对于同一个两列互换进行两次就等于没有换，即：KiKi=I (I=1,2,…,t).容易证Ki是一个对称阵，即：Ki= KKT=(K1…Kt)(K1…Kt)T=Kt·KTt…K1T=K1…Kt-1·KTt-1…K1T=…=GsHs经过相同的列置K可分别得到典型G0H0，即：GsK= ，HsK=H0根据GsHs的构成规则G0=[IkQs]H0=[QTsIr]，注2运算规则下，Qs=Qs再由线性代数的理论可知，G0H0T=O即：(GsK)(HsK)T=GsKKTHsT=O，由引理KKT= GsHsT=O （5-一变换NG=N为可逆∴N－1Gs=N1GsHsT=GHsT=On∴Hs是与 相对应的监督矩阵（证毕由上一节的23表译码，不2nn维向量按一定的规则划分为2k个互不相交的子集D0,D1,…,D2k1,使得每个子集Di仅含一个码字Ai.DiAi一一对应。设发送时，接收向量Bi.Bi位于Di之内，则把它译Ai.误仍Bi位Di则译码是正确它们都是由于发生了最常见的错误而由Ai下面介绍一2nn维向量的一种方2k个码向量置全零码字为最左面的元素A0=(000).在其余2n－2k个向量中一个置于AiE1.然后E2＋AiAi之下(i0，1，…，2k－1).再在余下的向量中任选一个作为E3，置于E2之下，并按上述r=n－k.AA E1 E1 EE EE1

A2AEA标准阵列的两个性质定理性质定理1阵列的同一行中没有相同的证：用反证法设在第l行中有El＋Ai= 设有一个向量出现在第lt行，并假定l＜t，则对于某ij有Et＋Ai=或 Et=码字，则有：EtEl＋As.这意Et在l行中已出现过这与阵列的构成方法。因为按规定Et应该是前面没有用过这个定理说明了阵列中每个向量都不相按可分为2r每一行为一个陪2k性质定理2同一陪集的向量都具有相同陪集首为El＋Ai的伴S=(El＋Ai)HT=ElHT＋AiHT=El即陪集内任一元素的伴随式等于陪集首的用反证法证明定理的第二个结l个陪集和第t个陪集具有相同的伴随式，l＜ElHT=EtHT，或(ElEt)HT=这就是说，(El＋Et)AjEl＋AjEt是第l个陪集中的向量。这与阵列的构成（证毕（随式Syndrome有医并的意思收向量Bi与错误图Ei“并发”在同一个陪集里）选用给定信道下最可能出现的错误图样作陪集首以前曾经证BSC低重为最佳标准阵列5-7和表5-8所给出的利用标准阵列译码需要从2r个伴随式中，再从这个伴随式所在行的2k个向量中找出译成这个码字nk相当大时，这种方80)线性码，220280都是相当大的数线性码译码步骤如下Bi的伴随式：Si=BiHT;找出相应于这个伴随式Ei，并把它作为错误图样：Si=EiHT;A：A=Ai＇就是发送向Ai5-16利用表5-8进行译码。因为这是一种(6，3)码。首先从准用码组中选k=3个线性无关的码字作为生成矩阵。为简尽量找到一个典型生成矩2,3 G

11然后再G求出H，容H

0 0 Bi=

0S0SBHT 0 101110011000

找到与SiEi：∵Si=EiHT，Si=(001)∴Ei=(000001)Ai=Bi＋Ei=(110111)＋(000001)=(110110)Ei为单重错时，HTSiT相同的列恰好与Ei中“1”的位置相对应。若错码不止1SiHTEi中“1”的位置相对应的那些列向量的模2Ei(7,4)码为例，给出它的编译和传输过程示意图（见图5-10，5-11，5-编信息

000000011100110101000101G (7,4)码“2运算（异或）的简记。译

H

00 5-11(7,4)码e6e5e4缓存器缓存器 息 5-12（7，4）码传输过程示意一.循环码原理使我们能利用线性码的代数性质对它进行n较大时，其工作量仍是相当可观的，为易用简单的具有反馈联接的移位寄存器来译的复杂度与码长n成正比为线性复杂度而一般线性码编译的复杂度与n2循环码的定A是一个(nk)线性码。如果A中任字循环移位后，仍是A中的码字，那A是循环码。为了易于用代数理论来讨论循环码的数多项式来表示，称为码多项式。设向量Ai=(an—1,an—1,…,a1a0)，那么它所对应的码多a(x)=an－1xn—1＋an－2xn—2＋…＋a1例5-16下表所给出的线性码就是循5-9(7,3)循环序号信组码多项012345670000010101001010x4＋x3＋x2＋1x5＋x2＋x＋1x5＋x4＋x3＋xx6＋x3＋x2＋xx6＋x4＋x＋1x6＋x5＋x3＋1x6＋x5＋x4＋x2用多项式表示一个码和用向量表示并没有重要的是要赋于这个多项式集合以一定的才能达到建立起循环码的目的呢？我们仍01)，相应的多项式为A1(x)=是字A3=(0111010)，相应的多项式A4(x)=x5＋x4＋x3＋x=x•A1(x)。再左移循环一次得到的又是字A7=(110100码A中的一并且相应的多项式等于A6(x1101001).若按上面x3·A1(x)=x7＋x6＋x5＋x3.但 A6(x)=x3•A1(x)所对应的数字序列为11101它包含了8位码元同时由于多项式x7，越出了多项式集合要使它不越出，可以令x71.这样一来，x3·A8(xx6＋x5＋x3＋1就成立了。照此办x4·A8(x)=x8＋x7＋x6＋x4x6＋x4＋x＋1.它所对应的A31010011).继续下得到（码的全部码字的任一个非零码字所对应的多项式依次乘以xx2,…，从而得到其它的码多项式。只要加上代数结构x71就可以了F2(x7)x7＋1=1，即x7(x7＋1)除,得到的余（73）码的任一非零码多项式乘xii=0,1,…,6然除(x7＋1)得到3）码的其他非零码多项式一般地可以F[x]

来表示所 x次数小于n的多项式的集合。即F[x]

={

xn—

xn—2＋…＋a x

i∈F2;i=0,1,…,n－1 而用A[x]来表示

[x]

中所有的码式集合，即

xA[x]={an－1xn—1＋an－2xn—2＋…＋a0│(an－1an－2…a1a0)∈A 显然，F2[x]xn＋1中的元素与n维向量Vn(F2)中的元素存在着一一对应的关即

)a(x)

xn1

xn2

x

1

同样A[x]中的元素与A中的元素也存在一所以，A[x]F[x

这个多项式 x合所构成的线性空间中的一个子空间如果在集合F2[x]xn＋1中规定了加法和乘法a(x)b(x)= a(x)b(x)= 其中a(x),b(x)∈F[x]

x x则F2[x]xn＋1对于所有规定的加法和x的多项式模(xn＋1)的环。现在我们设A是循环码，a(x)∈A[x]x和a(x)都属于F[x] ，所 xn2=(an－1xn＋an2

x2＋ax)10x10x显然有x⊙a(x)∈A[x].用数学归纳法可推出xi⊙a(x)∈A[x], i=0,1,…,n－1.由于F[x]

中任一元素都是若干xi x系数属于F2的线性组合，又由于A[x]F[x]

的一个线性子空间。所以 xm(x)，都有m(x)⊙a(x)∈A[x]A[x]F[x]

的一个理想 x且A[x]本身就可以由A[x]中次数最低的多即A[x]{m(xg(x)m(x)ng(x)}且 可以证明

g(x)nk那么xk－1g(x),xk－2g(x),…,xg(x),g(x)就是证G(x)={xk－1g(x),xk－2g(x),…,g(x),g(x)先证G(x)中各元素是线性独立的ak－1xk－1g(x)＋ak－2xk－2g(x)＋…＋a1x＋a0g(x)=其中g(x)=grxr＋gr－1xr－1＋…＋g1x＋g0.x的多项式后，其各项0.首先常数项应0，即：a0g00g0≠0，否g(x)=grxr＋gr－1xr－1＋…＋g1x=x( 1＋gr－1x=0g(x)1)的假设相，故只有a0=0。接着应有0a0g1a1g0=a1g0=0，从而a10ak－1=0。这说明G(x)中各元素是线性独立的。次证A[x]中每个元素都可表示为G(x)中如前所 g(x)∈这里 m(x)=mk－1xk－1＋mk－2＋m1x＋m0 (mk－1,mk－1,…,m1,m0∈则m(x)g(x)=m(x)g(x)=mk－1xk－1g(x)＋mk－2xk－2g(x)＋…＋m1xg(x)＋m0g(x)∈A[x]A[x]kmi(i=0,1,…,k－1)的取值是任意的，所以上面的线性组合可A[x]中的所有元素。所以xk－1g(xxk－2g(x…xg(xg(x)确 根据A[x]和A间的一一对应关系这一组所对应kA的一组gr00G

gr1gr0

gr1

00 0 0

000g000g

gr1

g0我们A[x]的生成A的生成多并称A是由它的生成多项式生成的循数最低的一个码多项式g(x)=x4＋x3＋x2＋0G0

0 0 不难验证，由G所生成的码就是上述(g(x)){m(x)g(x)m(x)n3）循反过来说g(x)F2[x]中的一个多项式g(x)|xn＋1代数理论可g(x)F[x]

中所生成的 xAan－1其中ai∈F2 I=0,1,…,n－1那么A是一个码长n，信息位数等ng(x那么g(x)就是这个理想中次数最低的一个多这一点可用反证法来证明。假定有g′(x)＋g(x)=g″(x)≠并 g"(x)g'(x)由于g″(x)(g(x))g″(x)是其中次数更低的多项式g(x)次数最低的假设g(x)n

，那么(g(x))xk－1g(xxk－2g(x),…,xg(x),g(x)k个xi(i=0,1,…,k－1)的线性组合，于是对于任一f(x)∈(g(x))，有f(x)=m(x)g(x)=mk－1xk－1g(x)＋mk－22g(x)＋…＋m1xg(x)＋m0这就是说，任意一个f(x)∈(g(x))，必可表示为(g(x))的一组基底的线性组合，并且(g(x))的维数是k.下面再证A必是一个循环码。(an－1xn－1＋an－2xn－2＋…＋a1那么就x(an－1xn－1＋an－2xn－2＋…＋a1=(an－2xn－1＋…＋a1x2＋a0即(an－2xn－1＋…＋a1x2＋a0x＋an－1)也可表达成(g(x))的一组基底的线性组合因此也是一个码多项式，并且(an－2…a1a0an－1)∈A.故A是个循环码。 为了从认识g(x)|xn＋1这个条件的重要性，下面举一个反例，说明g(xł令g(x)=x4＋x＋1. G

00G所生成的线性码不是循环码。以上我们着重讨论了循环码的生成矩阵A(n,k)循环码，g(x)是它的生成多项式，根据以上证明，(an－1an－2…a1∈A的充分必要条件 g(x)|(an－1an－2xn－2＋…＋a1x＋a0)因为g(x|xn＋1，故可令：h(xg(x1. (h(x)g(x))xn＋1=设a(x)=(an－1xn—1＋an－2xn—2＋…＋a1x＋a0A[x而g(x)|a(x，故可令a(x)=显然 反之， 可 其中axk若g(x) 则h(x)h(x)A的监督多项式h(x)=hkxk＋hk－1xk—1＋…＋h1x＋h0,(h0hk000H

00 0 0

h k k因 grhk=grhk－1＋…＋g1hn－2＋g0hn－1=…grhi－r＋gr－1hi－r＋1＋…＋g1hi－1＋g0hi=…g1h0＋g0h1=g0h0=或简写grhi－r＋gr－1hi－r＋1＋…＋g1hi－1＋g0hi=0 (i=1,2,…, 注意到h(x)也是(xn＋1)的一个因子，所以也可以把它看作某个循环码A′的生成多项 h0h00000 0hhhh0

kk

k

共有n－k行G′与H相比较，可A′与A的对偶码A*是等价的因为将A′中所字都按照由右至左的次序倒写出A*中的码更进一步，若令h(x)~h(x)~

hxh0

hk1x11k~A*.A*A′是等价的，所以有时我们也AA′互为对偶码。5-17(73)循环码的生成多项g(x)=x4＋x3＋x2＋1，那么h(x)=＋1，所以，它的监督矩 0H 0 00

00 n－k411以h(x)为生成多项式的循环码A阵 0G' 0 00

0 0 1 1′倒置之后恰A*(a0a1an－2－1)而以~(x)为生成多项式的循环码A*的生成00G*00

0 0 1 1a，接b，错误图e的b(x)=bn－1xn－1＋bn－2xn－2＋…＋b1e(x)=en－1xn－1＋en－2xn－2＋…＋e1并且 b(x)=整除a(x),g(x)|a(x)，因而b(x)e(x)关于模g(x)同余，即b(x)≡e(x), (modg(x)) 现在我们来证明：接收多项式b(x)的伴随式多项式就是用g(x)去除e(x)所得的余式证a(xb(xe(x)分别为发送向a，收b和错e的多项式。则b(x)=因 (h(x)·a(x))xn＋1=所以(h(x)·b(x))xn＋1=(h(x)·a(x))则有(h(x)·b(xxn＋1h(x)·e(x=(h(x)·Q(x)·g(x))xn＋1=其中h(xk,

nk1这个等式的展开式r后项的系数矩阵为HbT=HeT= 其

hk

00 HH1,H20

k 0 h

0 00

k k

n－k行n－k列 hk

k

k kH2经有限步的行初等变换后可化为单位方阵。设此初等变换对应矩阵为L，用它去LHbT=LHeT=LH2(e′)T=LHH行等价LH仍然A监督矩阵。于b(x)的伴随式为eT= 2…即S=(r－1 －2… （证毕g(x)那么g(x)nk=r. g(x)=grxr＋gr－1xr－1＋…＋g1xgr

gr

g0

0G gr

r

0

0 g r 0那么GA的一个生成gr0G可化为典型G0IkQ其中Qk×r阶矩阵，Ikk阶单位阵。此时码字的k位为信息位r位为监督位。问题是如何由给出的信息位an－1,an－2,…an－k的值，唯ar－1ar－2,…,a0,使(an－1an－2…a1a0∈A根据带余除法，可写成：c(xq(x)·g＋s(x),s(x)0g(x)而且s(x)c(x)g(x)唯一确定。从而有g(x)|[c(x)＋s(x)]因 则多项式[c(x)＋r(x)]的系数序(an－1an－2…a1可见，监督ar－1,ar－2,…,a0可以由带实5-13g(x)grxr＋gr－1x＋g1x＋g0做除式的除法ggr=g…图中共中r个移位寄存器，用方框表示而r 每个寄存器可以取0或1种状态；⊕是模2加法器；○是乘法器；乘法器的设置取决于生成多项式各项系数的n个码元：an－1an－2an－3,…a1a0a0电路r个寄存器的内容就是用g(x)去除a(x)所得的余式s(x)的系数，从左至右依次是sr－1,sr－2,…,s1,s0.另一从第(r＋1)个脉冲开始直到第n这个除法电路左端的输出,－2,…10次项的系数特别，当给定以g(x)为生成多项式的循环码Akan－1,an－2,…,an－k之后，输入端输入n个元素：an－1an－2,…an－k000…0ar－1,ar－2,…,a1,那么(an－1an－2…a1a0)就是A的一个码字例5-18以g(x)=x3＋x＋1为生成多n7A，因为在F2[x]中(x3＋x＋1)|(x7＋1)A确实存它是个74)循环码。A的编码可用下面的图图5- (7,4)循环码g(x)= 当给定信息a6a5a4a33个次a6a5a4a300,0后，寄存器中的内容自左至右依次a2a1,a0，而(a6a5a4a3a2a1a0)就是A的一个码字。上述除法电路虽能用作编，但前r拍只是将信息位输入移位寄k个信息r位间此可采取预先乘xr的k位信息位输入时，图中开K1断，K2,K3通，这样在直接输出信息码元的同时完成了除法运算。然后，K1通，K2,K3断，将移位寄存r个监督码元紧接在信息找码长为n的所有循环码的问题就变为求它的生成多项式g(x)的问题。g(x)|(xn＋1)xn＋1的所有因式即可就需要把xn＋1F2上分解成不可约多项式的上可以查xn＋1的因式分解表多项式a(X)都应被生成多项式g(x)以在接收端可以将接收向量b送入一个以g(x)为除式的除法电路（和发送编中的无错，余式不为零接接收向b除法电缓存

&余式0,输出余式≠0时,输

输重发指图图5- 循环码检错框在接收端为了纠错而采用的译码方法自正的的错误图样必须与特定的余式有一一对应关系。原则上纠错可按下述步骤进求出余式s(x)用生成多项式g(x)除b(x)得到：s(x)=(b(x))g(x)求错误图样e(x)s(x)用查表的方法或通过某种运算便可得到错误图样e(x).求发送多项式a(x)a′(x)=是送码多项式a(x).上述第（（3）步都比较简单。只是e(x)时，要把整个接收码组暂时下组时间中进行纠错。所以，实际的译需要两套除法电路配合一个缓冲寄存(5-17)74g(x)其中的除法电路与图5-14相同了进增加了一个7级缓存器和组合逻它们得到错误图样e(x)，它一方面与缓存器送到D0的输入端，用来消除该错误对余式a(x)输与非7图图5- (7,4)循环码纠错图5-18是一个（7，4）循环码译码器。由两套除法电路交替工作，K1K2K3K4是这两套电路的切换开关。输入输入7输出)上述译码方图5-18(7,4

，此外还捕错译码和大数逻辑译码等方法捕错译码是梅吉特译码的一种变形，也环码下面以定理的形式给出一些关于循环码定理5-4由任何多于一项的生成多项式证：码组中第i位上的单个错码对应于错码多项式xi.要能检测单个错码，只需g(x)多项式能整除xi （证毕最简单的生成多项g(x1＋x定理5-5若生成多项g(x)具有偶数项，则由它产生的编码就能检测所有奇数个错证：当错码有奇数个时，错码多项式e(x)整除e(x)，故能检测所有奇数个错误。令f(x)=(1x)·Q(x)=xaxbxc…将x=1代入上式得：f(1)=(1＋1)·Q(1)=1＋1＋1＋…=有偶数项 （证毕因xm＋1=(x＋1)(xm－1＋xm－2＋…＋1)，何具(xm＋1)形式的多项式都含有(x＋1).从而可推g(x)含有(xm＋1)个错误。(m=1,2,…)定义m是使g(x)xm＋1的最小整数，则称m为多项g(x)定理5-6若码长n不大于生成多项式g(x)mn≤m，则g(x)产生的码能够检测所有的单个和两个错码证：由于g(x)能整除(xm＋1)，它至少有两项，故按定5-4，必能检测出所有单个错若要检测所有两个错码，则要求g(x)不能整除xi＋xj其中ij＜n；假设i＜j，则有：xi＋xj=xi(1＋xj－i)因已假定g(x)不能被x整除（即生成多项式常数项不应为且多于一项的g(x)必定不能整除xi.故要求g(x)不能整除(1＋xj－i)就j－i＜n≤mm所以，g(x)必定不能整除(1＋xj－i).因此能检测两个错码 （证毕定理5-7n不大于g1(x)的指数，则由生成多项g(x)=(x＋1)·g1(x)产生的证5-5可知g(x)中有因子1)，故能检测单个和三个错误。又由定5-6可知，错码多项式(xi＋xj)不能被g1(x)除，故也不能被g(x)整除，所以能检测个错误（证毕个至最末一个之间的码元数目b.例如图样00010110000,b4定理5-8r次多项式产生的任一循环码，能检测所有长度不超过r的突误证b的突发错误可表示为=

xb－2＋…＋1)=xi式中e′(x)为不高于(b－1)次的多项式。g(x) e(x)r1可检测出来g(x)不能有x作为因子，且多于一项的g(x)不能整xi，故只有它能整除e′(x)e(x).但 g(x)).度不超过r的突发错误。 定理5-9长度为b＞r的突发错误中，若b=r＋1，则不能检测部分占1/2(r－1)；若b=r＋1，则不能检测部分1/2r证：设错误图样为e(x)=xie′(x)，其中).－1项，故还应有(b－2)个系01的项xj，0＜j＜b－1，所以共可2b－2种不同的多e′(x).仅当e′(x)有因子g(x)时，此错误才不能被检测，这时e′(xg(x)·Q(xg(x)rQ(x)b－1－r次。r=b－1Q(x)=1.这时仅有一个错误图样测的突发错误总数1/2b－21/2r－1.b－1＞r,Q(x)应含有x0xb－1－rb－2－r个系数01Q(x)有图样所占的比例为2b－2－(n－k)/2b－2=1/2r。定理5-10若由g(x)=(x＋1)·g1(x)产生此码能检测任何两个长度不大于2证：两个长度不大于2的突发错误的组合（1）e(x)=xi＋xj（2）e(x)=(xi＋xi＋1)＋xj（3）e(x)=xi＋(xj＋xj＋1)和(3)由于g(x)中有因子(x＋1)根据定理5-5而(4)可改写为：e(x)=(x＋1)(xi＋xj),被和(4)，为能检测出错误来,(xi＋xj)应不能被g1(x)5-6中已得到证明，所以(1)和(4)这两种错误能被检测。（证毕定理5-11g(xxq＋1)·g1(x)产生的循环码能检测如下两个突发错误的任何组e(x)=如果下列条件满足q＋1错误e1(x的突发长度qg1(x)的指数m的最但由dmin与纠检能力的关系定理易知当码的检错能力t时，其检错能力为[t/2].注:[]表示取整数部分。际的下面的5-10列出了一些有代表性的循截短循环码这就把原(nk)码中信息位删去i位后构成一(n－ik－i)码，0＜i＜k.这个码的最小码距仍不会减小，故很信息kmax是指最大可能的5-10部分循环码的参量和性定理不1所有奇数错5-两个错码：一个长度≤45-4突发；88%5的突发5-94%更长的突5-两个错码；一个长度≤95-9突发;99.6%长为10的突5-发;99.8%更长的突5-5两个长度≤2的突发；任何的突发；93.8%6的突5-5-5-的突发；99.99996%的长23的突发;99.99998%更长突5-5-5-.BCH码BCH码是一种特别重要的Bose-Chaudhuri-Hocguenghem命名的。BCH码的重要性在于它解决了生成多项式mt2m－1BCHt个随机错误（或检测2t个随数，不大于mt.因此，这种码的信息位数k5-11中给出BCH码的参量尔(Fire)码一些特定的循环码常常以研究该码的人命名。例如，定理5-中的码常称为费尔码5-11部分BCH码的参mnktd37411337g1(x)=g3(x)=3g1(x)=457g3(x)=g2(x)(x2＋x＋1)g7(x)=g1(x)=g2(x)=5g3(x)=g2(x)g5(x)=g3(x)g7(x)=g15(x)=g7(x)3g1(x)=g3(x)=2(x)(x6＋x5＋x2＋x＋1)g4(x)=g3(x)(x6＋x3＋1)g5(x)=g4(x)g6(x)=g5(x)(x6＋x5＋x3＋x2＋1)g7(x)=g6(x)(x6＋x4＋x2＋x＋1)g11(x)=g10(x)(x2＋x＋1)g15(x)=g13(x)(x3＋x＋1)g31(x)=g15(x)57495667(Golay)码戈莱码是一种纠正g(x g(x)=.循环(CRC)循环码具有很强情况外，还可检测出与许用码组距离小于CRC码及其生成多项式如下：5-12用CRCCRCx11＋x10＋x8＋x7＋x5＋x4＋x2一.卷积码的编、译码过程卷积码是由伊利亚斯(P.Elias)提出来的。在分组码中每个码字中n个码元仅与本k个信息位有关。而卷积码中，编码后产生n决于这段时间k个信息位，而且还取决于N－1N段时间内的信息。N段时间内的码元数nN称为这种码的约束长度。编码图5-19是一个卷积码的编输出；另一方面，还可以暂存于6级移存器中。每当进入编一个信息位，就立即息位之后发如下图5-20器输出端转换开头的功用即轮流将信息位bi和监督ci5-20编的监督位是由信息位6,3,2,1的21n2N6,nN12.常把卷积码记作(n,k,N).编码效率为R=k/n.bic1234565-19卷积码图图5-20 译码一般说来，卷积码有两类译码法门限译码是一种二进制的择多逻辑译码码破坏了的方程数目在方程组中是否占多数小于方程组中方程个数此方对错码进行5-21中给出了对应于图在译中有一个和图5-19相同的编码的相应监督码元在模2当接收码元无错时，译中重新计算“由图5-21当信息位出现一个码时，仅当它位于信息移存器中6321才使1.时

门限电5-21卷积码门限5-21所示电路连接，假b1以前中各级所寄存的校正子值S可以用下列逻辑 式 0E(b)

E(c)

当c为错码上式经过简单线性变换，可以改写成S1E(b1)E(c14E(b1)E(b4)5 (1)E(b2)

S2

E

这是一组正交于E(b1)的正交校验方每个方均包含一项E(b1)，而所有其他E(bi)和E(ci)整个方程组中至多出现一次因此在所的12个码元中错误不多于2个的条E(b1)=1b1错1所以在图5-21中按式(5-62)4个结果≥3，即当3个以上输入等于“1”时，“器输出端的一级移存器纠正输出码元b1的错b1影响的各级校正子此译除了能纠正两位在约束长束长度和在约束长度中能纠正错误的从上述例子可以看数学理论尚不象循码。由§5-3可知，一个线性码完全由一监督H或生成矩阵G所确定。下面我们例定图5-19在第一个信息位b1进入编之前，各级移存器处于0状态，c1b1c2b2c3b3c4b1c5b1c6

6 6

c7

b3b4b7 上式可以改b1c1b2c2b3c3b1b4b1b2b1

0

b2

用矩阵表示为

b

1 c112 2

b

c

2

1

b7

c7c

HAT0T11001010110000 在卷督矩阵H是一个现H中每两列都与其前（或后两列结0。由于这样半无穷矩阵不便于研究，而且我们只要研究其前6行已能说明n的结构形式如5-22所示H1的最左边n列(n－k)·N行的一个子矩阵，向右的每nnn b1c11c12b2c21c22b3c31c32b4…dj1cj2cc

b

bj1 j j2由此可见k1n3N3，约束长度nN=9.监督方程为11bc 12bc c

或写成矩阵形式为1001000110001010010 1100

0

1

阵为

1001010010011000101001001100000101 1

I

P

I

2

式中I22阶单位阵，Pi——2×1阶矩阵，O——2阶全0方阵。仔细观察可发现它与典型H0=[P,Ir]有 I

O

P

O

I N r式中Irr阶单位阵，rn－kPir×kOr阶全0方阵h=[PNOPN－1OPN－2O…P1Ir]给定了h，则H1或者h不难H1.最后，我们来找卷积码的生成矩阵G，在 b4=[b1b1b1b2(b1＋b2)b2b3(b2b3)(b1＋b3)b4…]12b12

(5-行比上一行向右退n列(现在n＝3).类似式(5-71)，也有截短

I1

Q3 010

Q

2I1 Q1式中I11Qi1×2阶矩阵，iQi=P ，(i= i一般说来，截短生成矩阵具有如下形I

Q

QN G

N1

I

Q1

式中Ikk阶单位方阵Qik(n－k)阶矩阵Ok阶全0方阵g.g=[IkQ1OQ2…OQN同样，如果基本生成矩g已给出，就完全有可能从已知的信息位得到整个编码序一.噪声是指信息系统中导致有用信号失噪声信道的转移概率p(yj/xi)表示当发送xiyj的概率的平错误概率为 pe

p(xi)p(y

/xij

i二.信道编码是对抗信道中加性干扰的的关系来自动检测或纠正传输中所发生的错三.分组码是指新增加的监督元仅与本传输时具有一定的能力把每个k长的信息组n位长的码字(n＞k).这2kn位长码字的全体称为码长为n，信息位为k的分组(nk)监督元个数rn－k.衡量分组码性能的基本参数编码效率：Rk

i0,ai

二元码时wa

i码距d(ab)

1io,ai

二元码时d(a,b) i

.A是码长n的分组的最小码距为dmintt1t2使下列命题dmin≥t＋1时，A是检t码，可以检测所有≤t重的错误；dmin≥2t＋1时，A是纠t码，可以纠正所有≤t重的错误；(t1＋t2)码，可以纠正所有≤t1重错并同测≤(t1＋t2)重错 nnw 1Cinnwi

p)

Ciit1

p)五.若给定BSC（二元对称信道）的平均错码率p，则误码字率为；其中t为该编码的纠检能力，n为码长。六.若要纠正码字中所有t重的错误，则监督元的数r必须满t2r

Cnin汉明不等式中等号成立的纠错码称为完备码 t M2/Cn i M为汉明界。它表示准用码组的个数不M.式中[]表示取整数部分。.信道容量为C的有错系统H＜C，总存