信息论与编码原理第六章

信息论与编码第6章

信道编码教学目的与要求

深刻理解信道编码的检、纠错原理。熟练掌握建立译码规则的原则和计算错误概率的方法。掌握线性分组码、循环码、卷积码等重要的信道编码的原理与方法。(重点)了解Shnnon信道编码的内容和意义本次课内容

6.1信道编码概念6.1.1信道编码概述6.1.2译码规则6.1.3编码规则6.1.4纠错编码的基本原理6.2线性分组码

6.2.1线性分组码的编码[温旧引新]三大编码:

信源编码、信道编码和加密编码信源编码:

压缩代码长度的编码。信道编码:

为了减少差错而进行的编码。检错原理误码的必然性:

在有噪声和损失存在的信道中,输入符号与接收符号不能一一对应,传输错误和判断错误的情况总会存在。误码的不可预知性:

误码是随机发生的。接收端并不了解是否发生了误码,更不知晓是哪个码元出现错误四种天气状况:

晴、

阴、

雨、

风00011011没有冗余非此即彼错了也不可知000000110110110110115位二进制码元传输2bit的信息,冗余3bit。25=32个码字,许用码字4个,非法码字28个检错--------如何检测有无误码?正误应有别-------许用码字与非法码字原因----------冗余的作用纠错原理

发现错误怎么办?(1)重发反馈方式(ARQ);(2)前向纠错方式(FEC);(3)混合纠错方式(FEC);自动纠错的前提:

不仅知道有错,还应知道是哪个码元出现错误双连码只能检错,不能纠错,因为冗余不够。三连重复码当其中任一码元出错时,还有2位没有错,通过比较就能发现是哪一位错了,从而可以进行纠正。万一三连重复码有两位码元出错时,就会判断失误。表明超出了它的纠错能力。三连重复码的纠错能力是1位,五连重复码的纠错能力是2位,添加的冗余越多,纠错能力就越强,然而传输效率就越低。汉明距离(Hanmingdistance):

定义两个码字相同码位上不同码元的个数叫它们的汉明距离。汉明距离反映了两个码字的差别。•双连重复码的汉明距离d=(00,11)=2;三连重复码的汉明距离d=(000,111)=3;•双连重复码发生1位错的误码是01或10,与许用码字11或00的汉明距离相同,无法判别误码来自谁。•当三连重复码有一位码元出错时,比如000变成001、010或100,误码与000的汉明距离为1,而与111的汉明距离为2,据此就可判定误码来自000;检、纠错原理------添加冗余

冗余的添入，增加了码字总数，给误码留下了空间，就给判断正确与错误提供了可能(检错原理)。更多冗余的添入，拉大了许用码字之间的汉明距离,就有可能区别误码与各个许用码字之间汉明距离的不同,从而判断误码可能的来源(纠错原理)汉明重量与汉明距离

汉明重量(Hammingweight)

定义码字中码元1的个数叫做该码字的汉明重量。

如:W[11010]=3;W[00000]=0;汉明重量与汉明距离的关系:d(u,v)=W[u⊕v] u和v是任意两个码字,⊕代表按位模2加(异或)。u和v码元相同的位模2加为0,不同的位模2加为1,W[u⊕v]就给出了u和v不同位的个数。最小汉明距离一种编码有许多个码字,全部两两比较后,找出最小的汉明距离为d0。

如:C1=00000;C2=01101;C3=10110;C4=11011;

则:d(C1,C2)=3;d(C1,C3)=3;d(C1,C4)=4; d(C2,C3)=4;d(C2,C4)=3;d(C3,C4)=3

因此最小的汉明距离为d0=3线性码的最小汉明距离: d0=Wmin

（最小汉明重量）

检错、纠错能力

检错、纠错能力与最小汉明距离有直接关系设d0为最小汉明距离,e为可检错位数,t为可纠错位数,则: (a)为了发现e个错误码元,要求最小码距d0≥e+1; (b)为了纠正t个错误码元,要求最小码距d0≥2t+1; (c)为了能纠正其中t(t<e)个错误码元的基础上还能发现e个错码元,要求最小码距d0≥e+t+1;如果只检错不纠错,则最多检错位数是e=d0-1。如果只纠错不检错,则最多纠错位数是: t=INT[(d0-1)/2],INT表示取整数如果既纠错又检错,则e和t就不能独立,它们应满足关系式:e+t≤d0-1,而且e必须大于t[例1]已知汉明距离d0=7,分析检、纠错能力。 (1)只检不纠:e=d0-1=6;可检到6位错。 (2)只纠不检:t=(d0-1)/2=3;可纠3位错。 (3)又检又纠:e与t不独立:e+t≤d0-1,且e>t

当t=1时,1<e≤5,1位错已纠,只能检2—5位错。

当t=2时,2<e≤4,2位错已纠,只能检3—4位错。

当t=3时,e无解,3位错已纠,3位以上无能力检信道编码的性能指标

编码效率

设某种编码的码字长n位,其中信息只有k位,r=n–k为冗余位,则该编码的信息率(也叫编码效率):η=k/n

漏检率

把编码检查不出的错误所出现的概率叫做漏检率。差错率

把编码不能自动纠正的错误所出现的概率叫做差错率。[例2]讨论双连重复码的编码效率和漏检率。

编码效率η=k/n=1/2=0.5

假设对称信道,0与1的错误概率均为p,则:

漏检率=2位同时出错的概率=p2

[例3]讨论三连重复码的编码效率和差错率。

编码效率η=k/n=1/3=0.33

差错率=3位同时出错的概率+2位出错1位正确的概率=p3+3p2(1-p)n连重复码n为奇数时：可纠正t＝(n-1)/2位错误当错传概率为p时，差错率＝n位同时出错的概率＋(n-1)位出错1位正确的概率

＋⋯⋯＋(n+1)/2位出错(n-1)/2位正确的概率n为偶数时：可纠正n/2-1位错误，还能发现第n/2位出错漏检率＝n位同时出错的概率＋(n-1)位出错1位正确的概率

＋⋯⋯＋(n/2+1)位出错(n/2-1)位正确的概率它的编码效率很低，只有η＝1/n奇偶校验码n-1个信息位后添加1位“奇偶校验位”，其关系为：编码效率它的编码效率很高，达到：检、纠错能力可查出任何奇数位错误，却不能发现偶数位的错误，也没有纠错能力漏检率（偶校验）（奇校验）n-1位信息位1位监督位双向监督码为了增加奇偶校验码的检错能力，对列再进行奇偶校验，增加一行“竖直奇偶校验位”，进行双向监督，也称方阵码。干扰造成的误码，往往发生在连续的若干个码元上。采用上述双向监督，就把在行中难以发现的错误，在列中发现。信息位监督位110101010010110011111001100001001111列监督000011恒比码从n位二进制自然码中挑出1和0的个数之比恒定的一些码字组成许用码集合五中取三码是从25＝32个二进制自然码中挑出含3个1,2个0的码字，共10个（

），用来表达10个阿拉伯数字；七中取四码则是从27＝128个二进制自然码中选出含4个1,3个0的码字，共35个（

），可用来表达26个英文字母和标点符号。[例4]讨论恒比码的编码效率和漏检率。五中取三码的编码效率η=k/n=log10/5=66.4%七中取四码的编码效率η=k/n=log35/7=73.3%它们可以发现多位错误,却不能发现同时出现0误为1且1误为0的错误,也无纠错能力。小结:

信道编码的原理:检错原理-----添加冗余,克服非此即彼,分辨对错。纠错原理-----添加冗余,拉大码矩,判定错误来源汉明距离与检纠错能力:

检错位数e=d0-1,d0表示汉明距离

纠错位数t=INT[(d0-1)/2],INT表示取整数编码效率

简单的检纠错码: n连重复码、奇偶校验码、恒比码错误概率与纠错能力我们已经有了两种评判信道编码效果的方法:

检、纠错能力与差错控制能力。两种评判方法的比较描述方式检、纠错能力差错控制能力观测点可检纠错的位数漏检率与差错率优点简单、直观科学、本质缺点不严谨计算复杂设:二元对称信道传输单符号的错误概率为:p=0.01,(正确概率为

)三连重复编码,发出的码字为:α0=000,α1=111;各种可能的接收符号为: β0=000,β1=001,β2=010,β3=011, β4=100,β5=101,β6=110,β7=111;三次扩展信道的转移矩阵为:平均错误概率为:与编码前单符号传输相比,差错率由原来的百分之一降低到万分之三。代价是传输效率为原来的三分之一。译码规则编码在发送端进行;误码在信道中发生;发现与纠正错误必须在接收端进行。译码规则是设计人员预先为译码器设计好的译码指令。每当收到一个符号bj;系统都应当为它指定一条译码规则:F(bj)=ai*告诉译码器应当把bj译为哪个ai

;比如三连重复码的译码规则是:

F(000)=0;F(001)=0;F(010)=0;F(100)=0;F(111)=1;F(011)=1;F(110)=1;F(101)=1;[例1]信源发出符号a1,a2,a3;接收端符号为b1,b2,b3;对它可以构造多种译码规则。比如:译码规则A:F(b1)=a1*;F(b2)=a2*;F(b3)=a3*译码规则B:F(b1)=a1*;F(b2)=a3*;F(b3)=a2*

同样的信源信道,选用不同的译码方案,将会得到不同的结果。究竟采用哪个译码规则更好呢?一个很自然的考虑就是按该方案译码后,造成的错误概率应最小译码错误概率译码规则一旦确定,译码器就按指令办事。设译码规则为F(bj)=ai*,当收到一个符号bj时,按译码规则它就被译为ai*。如果信源发出符号恰为ai*,就翻译对了;如果信源发出的是其它符号,译码器按指令仍然会把它译成为ai*,就翻译错了。根据后验概率计算结果可知,翻译对的概率是翻译错的概率是译码错误概率计算公式对于各种接收符号求平均,翻译对的平均概率是:译码错误的平均概率是:利用联合概率公式,上两式可写为:

设信道输入符号集X={a1,a2,…..ar},

输出符号集Y={b1,b2,….bs}。译码规则就是一个译码函数:F(bj)=ai(i=1,…,r;j=1,…,s)

定义在Y上而值域在X中的不同的译码函数共有r×s个设信道的传递矩阵为（其中r=3，s=3）6.1信道编码概念联合概率为

i=1,2,…,r,j=1,2,…,s。联合概率矩阵为6.1信道编码概念最大后验概率准则(最小错误概率准则):

使即在收到bj的条件下,发出的是a*的概率最大,就将bj译为a*,这样就使得pe最小。即在联合概率矩阵中,除去每个F(bj)=a*对应的元素,再对所有剩下的元素求和。6.1信道编码概念说明:(1)求pe的公式适用于所有译码规则。(2)采用最大后验概率准则选择译码规则,一定能使pe达到最小值pemin,而pemin取决于给定信源和信道的统计特性。(3)在信道输入符号等概条件下,pe的公式为

6.1信道编码概念求和是在信道矩阵中除去每列中对应于F(bj)=a*的元,再对其它元素求和。最大似然译码准则:

收到bj后,在信道矩阵的第j列中,译为该列最大那个元素所对应的ai。

当输入符号的先验概率均相等时,两个准则相同。6.1信道编码概念【例6-1】设有单符号离散信道。信道矩阵为求下面译码函数(规则)的pe：A:B:6.1信道编码概念选择A:解:根据最大似然译码准则可选取译码函数A,在输入等概率分布时可使pe最小。=(1/3)(0.2+0.3+0.3+0.3+0.2+0.4)=0.567若选择B:

=(1/3)(0.2+0.3+0.3+0.3+0.2+0.5)=0.600可见

,则pemin=0.567。这意味着在信道的输出端接受100个符号,其中大约有57个符号要发生错误译码。6.1信道编码概念A:B:6.1.2编码规则

设一个二元对称信道的矩阵

按最大似然准则,pemin=0.01=10-2

。

一般系统,pe在10-6--10-9

的范围内。6.1信道编码概念下面研究如何编码以使pe变小。采用重复编码的方法(线性分组码):若发送0，则发000；发送1，则发111。这样，在输入端有两个码字，但在输出端,由于信道干扰作用,各码元之间可能发生错误则有8个可能的输出序列.在接收端有8个可能的序列。6.1信道编码概念此码元n=3重复3次,把错误概率降低了接近两个数量级.这种简单重复编码,若有一位码元出错,译码器能够译出正确的码.因码字

与四个接收序列

对应,

与另四个接收序列对应.若重复次数更多还可进一步降低现N=3如:

N=1时6.1信道编码概念但同时信息传输率也降低了很多

编码后每秒钟传输的信息量

当N=1(无重复)M=2设t=1秒N=3(重复3次)M=2R=1/3N=9R=1/9M输入信息个数,N编码后码字长度上述表明尽管Pe降低很多.但信息传输率也降低了很多6.1信道编码概念根据经验得出如下结论：

(1)不出现错误的概率比出现一个错误的概率大;出现一个错误的概率比出现两个错误的概率大。依此类推。(2)码集dmin越大越好,码集dmin越大pe小;

dmin越小,受干扰后,很容易把码字变成另一个

码字,pe越大。6.1信道编码概念编码原则:

选择M个消息所对应的码字时,应使码字集合的dmin尽可能增大。则只要码长n足够大时,就可以使pe很小,而信息传输率R保持一定。利用汉明距离,极大似然准则可以转化为:当接收到码序列bj后,在输入码字集{ai,i=1,2,…，r}中寻找一个a*,使之与bj的汉明距离最小,即选用译码函数F(bj)=a*,使之满足d(a*,bj)=mind(ai,bj)。6.1信道编码概念定理6-1(香农第二定理)

对任意一个离散无记忆平稳信道,设信道容量为C,则只要信息传输率R<C,则对任意给定的正数,总存在一种分组长度为n的信道编码方案(n足够大),以小于ε的错误概率实现可靠通信。反之,R>C时不可能找到一种编码,使错误概率pe趋于零。6.1信道编码概念6.1.3纠错编码的基本原理数字通信系统模型:信源信源编码器信道编码器调制器信道解调器信源译码器信道译码器信宿噪声源m:二进制序列,信道编码器将m映射到c(码字),r=c⊕e.信道译码器的作用有两个：一是纠错，二是将c*映为m*（m的估算）。6.1信道编码概念

mcerC*介绍几个基本概念：码字c长n位。n=k+r，其中k位是信息位，r位是校验位。(2)长为k的信息组共有2k个,相应的码字有2k个。把这样的码字集合称为(n,k)分组码,码字的分量叫码元。6.1信道编码概念(3)在分组码中,如果校验位与信息位是线性关系,则称为线性分组码。(4)因为码字有2k个,而长为n的序列有2n个,故有2n

-2k个禁用码字。(5)在码字中,信息位所占的比重称为编码效率：R=k/n,表达信道的利用效率。R越大,码的效率越高。例如，n=3时的分组码(3,1)的编码效率:R=1/3。R=1/n是低速码，但可靠性高。6.1信道编码概念对纠错编码的要求：可靠性:

能纠正经常出现的错误。(2)有效性:

在达到要求的错误概率下,所加的校验位最少。(3)成本低：选快速的译码算法，速度高的器件。6.1信道编码概念汉明距离与重量的关系：

(1)汉明距离的度量满足距离公理：Ⅰ.非负性：d(ci,cj)≥0；Ⅱ.对称性：d(ci,cj)＝d(cj,ci)；Ⅲ.三角不等式：d(ci,cj)≤d(ci,c)＋d(c,cj)。(2)一个码字的汉明重量就是一个码字中非零码元的个数,记为W(c)。例如,W(1010101)=4。若c=(c1,c2,…,cn),则W(c)=6.1信道编码概念命题6-1设(n,k)为线性分组码,则它的所有非零码字的重量的最小值wmin,称为最小重量,等于最小距离,即wmin=dmin。这是因为:(1)wmin=W(c0)=d(c0,0)≥dmin,(2)6.1信道编码概念最小距离

的分组码,有能力纠正

注:纠错能力是小于检错能力另：所有码距相等时码的性能最好,各码距相差不大时性能较好。差错概率的上限为

个差错INT[.]表示为取整

t是汉明距离6.1信道编码概念什么是线性分组码?

同时具有分组特性和线性特性的纠错码。

编码器按一定规则,将输入的信息组编成长为n的码字,码字前k位为信息元,后r=n-k个码元为校验元.若各校验元与前k个信息元之间是线性关系,则称这样的码为线性分组码.6.2线性分组码6.2线性分组码6.2.1线性分组码的编码

设码长为n,信息位为k个,消息数2k,信息传输率R=k/n,编码速率为码率。

编码的主要问题是：在一定的编码速率下，如何从已知的k个信息位求得r=n-k个校验位，使得到的码字具有所要求的纠错能力。既，如何建立一个有k个已知数,求n-k个未知数的线性方程组。6.2线性分组码【例6-2】设线性分组码(6,3),按如下规则生成:

其中“+”为模2加,码字c=(c1,c2,c3,c4,c5,c6),所得到的系统码的8个码字如下:6.2线性分组码信息(消息)码字000000000001001101010010011100100110011011110101101011110110101111111000下面给出生成矩阵的概念。生成矩阵主要用来编码,它也可以转化为有译码作用的校验矩阵。6.2线性分组码将上面(6,3)码的方程组改写为:c=(c1,c2,c3,c4,c5,c6)=(m1,m2,m3)=(m1,m2,m3)G矩阵G称为(6,3)码的生成矩阵,若给定信息元011,则码字为:

c=(0,1,1)G=(010011⊕001101)=011110.这就解决了编码问题。6.2线性分组码其中有3阶单位矩阵,这样的G叫校准生成矩阵,它生成系统码。将码字改写为:观看G的结构6.2线性分组码其中，G=(g1,g2,g3)T,gi是G的第i行(i=1,2,3),这样,所有码字的集合是由G的线性无关行向量组g1,g2,g3生成的线性子空间,子空间的维数是3。线性分组码(n,k)的性质:(1)零向量(0,0,…,0)是一个码字。(2)任意两个码字之和仍为码字。(3)任意码字c是G的行向量的线性组合。6.2线性分组码生成矩阵的几个结论。命题6-2行等价的生成矩阵有相同的行空间。设G经初等行变换化为G1,则有可逆矩阵M,使得MG=G1,也有G=M-1G1,于是由此能得到向量组,g1,g2,g3,与向量组h1,h2,h3,可以互相线性表示,从而等价。6.2线性分组码命题6-3设G是某(n,k)码的生成矩阵,G生成系统码→G行等价的行阶梯形的最简形是(Ek,P)的形式。例如,生成矩阵

生成的不是系统码,但它可以经行变换(可交换列)得到G=(Ek,P),G生成系统码,两个矩阵生成的码在性能上等价。6.2线性分组码与生成矩阵同样重要的是校验矩阵。将上面(6,3)码的线性方程组改写为:从而有

或称

为(6,3)码的校验矩阵。或HcT=0,cHT=06.2线性分组码（1）对信息组编出的码字是什么？

（2）设计一个（7，4）分组编码器的原理图（3）若接到一个7位码=（1001101）它是否是正确码字

例一个（7，4）码，生成矩阵为6.2线性分组码

编码所得的码字为

系统码字

（

）（

）

由生成矩阵知

（

）

得解（1）设输入4个信息比特组是()6.2线性分组码又

代入上三式得

则编出的码为

（

）

（2）设计一个（7，4）分组编码器的原理图6.2线性分组码m4m3m2m1ci7ci6ci50001101输入编码器用4级移位寄存器和7-4=3个模2加法器组成,加法器生成校验位后按顺序暂存在另一个长度为7-4的移位寄存器中,先是4位信息位,然后是7-4位校验比特从两个寄存器中移出.（

）

6.2线性分组码（3）判断7位

=（100111）

是否是正确码字

若r是某个码字

必有

反之

不是码字

6.2线性分组码=(0,1,1)说明

与

不正交，

不是码字

6.2线性分组码本课结束上次课内容

6.1信道编码概念6.1.1信道编码概述6.1.2译码规则6.1.3编码规则6.1.4纠错编码的基本原理

6.2线性分组码

6.2.1线性分组码的编码1、线性分组；。复习：3、生成矩阵和校正矩阵作用。通过生成矩阵进行编码,通过校正矩阵检测接收码字是否是正确码.编码器按一定规则,将输入的信息组编成长为n的码字,码字前k位为信息元,后r=n-k个码元为校验元.若各校验元与前k个信息元之间是线性关系,则称这样的码为线性分组码.3定义:两个码字之间,对应位取值不同的个数,称为它们之间的汉明距离.2.汉明距离(译码最小距离译码)本次课内容6.2.2线性分组码的译码6.2.3汉明码6.3循环码6.3.1循环码的定义和结构6.3.2循环码的生成矩阵和校验矩阵6.3.3循环码的编码器6.2.2线性分组码的译码1、讨论校验矩阵与生成矩阵的关系。设线性分组码(n,k)的系统码的生成矩阵为

,n=k+r。校验矩阵H为r×n矩阵,满足:cHT=0或HcT=0.其中c=(c1,c2,c3,c4,c5,c6)为码字,,Q为r×k矩阵。因为G的每行都是码字,故GHT=0或HGT=0,从而有QT+P=0故P=QT

或Q=PT6.2.2线性分组码的译码校验矩阵H的性质:(1)H与生成矩阵G可以相互转化。(2)利用H和式cHT=0判别是否码字。(3)H中列的线性相关性与纠错能力有关系。6.2.2线性分组码的译码如无差错有定义差错图案为判断收码R是否为发码C由在固定的前提下，仅与有关，而与无关。否则

由于模2加与模2减等同，故2、伴随式:发出码字C,接收到向量R,有错误图样E。6.2.2线性分组码的译码另:差错图案是n重矢量,共有2n个可能的组合，而伴随式是n-R重矢量,共有2n-R个可能的组合,所有不同的差错图案可能有相同的伴随式。定义：伴随式

伴随式s并不反映发送的码字是什么,而只是反映信道对码字造成怎样的干扰。6.2.2线性分组码的译码伴随式s的性质:(1)s仅与e有关。(2)s用来判别错误:s=0,无错;s≠0,出错。(3)s不同，则e不同。

接收端虽然不知道发出的c,但知道HT和r,可计算出伴随式

s=rHT

。译码最重要的任务是从s找出c的估计值,方法是:计算出s=rHT

计算e

这里关键是如何从S找出e,只要e正确,译出的码正确。6.2.2线性分组码的译码计算e方法，即译码方法：（1）概率译码:将所有2k个解的汉明重量作比较,选择最轻者作为e的估值。这个估值的汉明距离最小,其译码是最大似然译码。（2）标准阵列译码。2k个码字的集合记为C,2n个r的集合记为R。6.2.2线性分组码的译码译码表的方法:

标准阵列译码表每一行是一个陪集,每陪集的第一个元素(位于第一列)叫陪集首.同一个陪集中的所有元素对应共同的一个伴随式,每一列是一个子集,每个子集的第一个元素叫子集头,同一子集中的所有元素对应同一个码字。6.2.2线性分组码的译码....……..……..

………………..……..

……....……

…………..……..……....此时定理6-3

二元线性分组码(n,k)能纠2r个错误图样(r=n-k)的条件是:纠1个错之内,纠2个错之内,…纠t错之内,若等式成立,伴随式的个数恰好等于可纠的错误图样数,r=n-k个校验元得到了充分利用。6.2.2线性分组码的译码例

某一个(5.2)系统线性码的生成矩阵为

，收码是R=(10101).请先构造该码的标准阵列译码表，然后译出发码估值C解：信息组码（00）,（01）,（10）,（11）（1）构造标准阵列译码表得4个许用码字

由6.2.2线性分组码的译码由

则

伴随式线性方程式

6.2.2线性分组码的译码伴随式有

==8种=差错图案中代表无差错的有一种

代表一个差错有

种

有两个

有

8个伴随式对应到8个最轻的差错图案，首选1个无差错图案，5个1个差错图案，2个差错图案选两个，共8个,故选择不是唯一的.种，(00000)6.2.2线性分组码的译码选择差错图案

代入上面的线性方程组得少(011),(110)6.2.2线性分组码的译码余下的伴随式中,(011)所对应

是(00011),伴随阵（110)对应差错图案（00110）6.2.2线性分组码的译码标准阵列S1=000e1+C1=00000C2=10111C3=01101C4=11010S2=111e2=10000e2+C2=00111e2+C3=1110101010S3=101e3=01000111110010110010S4=100e4=00100100110100111110S5=010e5=00010101010111111000S6=001e6=00001101100110011011S7=011e7=00011101000111011001S8=110e8=00110100010101111100列表如下：6.2.2线性分组码的译码（2）对收码R=(10101),可选择以下三种方法译码。①直接搜索码表，查(10101)所在列的子集头是（10101），译码输出取为（10111）。

S1=000e1+C1=00000C2=10111C3=01101C3=11010S2=111e2=10000e2+C2=00111e2+C3=1110101010S3=101e3=01000111110010110010S4=100e4=00100100110100111110S5=010e5=00010101010111111000S6=001e6=00001101100110011011S7=011e7=00011101000111011001S8=110e8=001101000101011111006.2.2线性分组码的译码②可先求伴随式找到行数，

第5行找到10101，便找到码字10111S1=000e1+C1=00000C2=10111C3=01101C3=11010S2=111e2=10000e2+C2=00111e2+C3=1110101010S3=101e3=01000111110010110010S4=100e4=00100100110100111110S5=010e5=00010101010111111000S6=001e6=00001101100110011011S7=011e7=00011101000111011001S8=110e8=001101000101011111000106.2.2线性分组码的译码③先求

查表

由

该(5.2码)

（最小非零码字的重量）纠错能力

进一步分析，6.2.2线性分组码的译码由此可见,译码阵列中只有前6行具有唯一性,可靠性.，S1=000e1+C1=00000C2=10111C3=01101C3=11010S2=111e2=10000e2+C2=00111e2+C3=1110101010S3=101e3=01000111110010110010S4=100e4=00100100110100111110S5=010e5=00010101010111111000S6=001e6=00001101100110011011S7=011e7=00011101000111011001S8=110e8=00110100010101111100

各含两个1，超出纠错能力，译码不可靠，7.8行中可检错。由6.2.2线性分组码的译码6.2线性分组码汉明提出了信道码的第一个系统编码方法

——汉明码

此方法用模2和对二元分组码码元进行一致性检验，以此发现并确定码字中差错码元的位置。汉明提出的一个重要的概念:

把字母中0.1不仅看作是符号,而且看作是可以运算模2。6.2.3汉明码1.概述+

0101

0110×

0101

0001.

0123401234

0000001234024130314204321模二加法

模二乘法模5运算（mod5）

0123401234

01234123402340134012401236.2.3汉明码对于(n,k)线性分组码，小于或等于t个错误的错误图样共有种，标准阵列中的陪集首共2r(r=n-k)种，用“译码表”译码时，能纠正的错误是各种陪集首。所以，如果性质:陪集首就可包含小于或等于t个错误的全部错误图样。式(6.2-6)称为汉明不等式。它是任何一个(n,k)线性码能纠正小于或等于t个错误所必须满足的条件。(6.2-6)6.2.3汉明码如果成立，称该码是完备码。该码的伴随式,分别与小于或等于t个错误的所有错误图样相对应,这个码的n-k位校验位利用得最充分。6.2.3汉明码由于讨论的是纠正一个错误的线性分组码，必有

n≤2r-1.(6.2-7)即要有纠t=1位错的能力，当校验位数r固定时，码长n不可能无限制地增长，只能在满足式(6.2-7)的约束条件的范围中选取最大的码长6.2.3汉明码

故,在r固定的条件下,保持纠1位错的(n,k)线性分组码可能达到的最高码率.这种码就是(n,k)完备码,它是汉明码,其中

汉明码是校验位r固定时，能纠1位错的所有可能的线性分组码中码率R最高的一种高效码。6.2.3汉明码2.汉明码的定义和性能定义:6.2.3汉明码互不相同且不全为0的列数最大是2r-1列，即H矩阵可用任意次序安排的2r-1列非零向量(r维)组成。用这种校验矩阵H所确定的(n,k)=(2r-1,2r-1-r)线性码,就是纠正单个错误的线性分组码,也称为汉明码。完备码相当于在陪集译码中能将重量小于或等于t个的所有错误图样选为陪集首。可以验证，汉明码是纠正一个错误的完备码。下表是几种汉明码6.2.3汉明码3.汉明码的编码和译码汉明码的编码过程:

由信息位数k→求出纠正1位错的校验距阵H，再由H→求出信息所对应的码字。6.2.3汉明码构造汉明码校验距阵H的方法:(1)由已知k,从汉明不等式的等式中求出r=n-k；(2)在每个中用作为校验位,剩下的位作为信息位。(3)用二进制数字表示2r-1列,得到2r-1列和r行的H；(4)用上一步形成的H根据HcT=0,得出r个校验方程;(5)将已知的信息代入方程组,然后由此求出校验位c2i,从而确定码字。6.2.3汉明码【例6-3】（7,4）汉明码的编码方法：(1)已知k＝4,由2r=1+n=1+k+r=5+r

求出r=3,n=r+k=7(2)建立H,因r=3，故c1,c2,c4为检验位，其余为信息位。6.2.3汉明码则(3)建立方程组，根据HcT=0得个校验方程得到c1=c3+c5+c7C1C2C3C4C5C6C76.2.3汉明码C1C2C3C4C5C6C7可得c2=c3+c6+c7同理可得c4=c5+c6+c76.2.3汉明码(4)编码.将已知的信息位代入方程组，求出校验位。设：信息位c3、c5、c6、c7分别为1011,代入c1=c3+c5+c7=1+0+1=0c2=c3+c6+c7=1+1+1=1c4=c5+c6+c7=0+1+1=0则校验位c1=0,c2=1,c4=0,求得码字为c=0110011注意:调换H各列的位置,不影响码的纠错能力,故H可有其它形式。6.2.3汉明码汉明码的译码方法即伴随式译码,而且可以从伴随式中知道错误位置,因为伴随式正好是错误位的二进制表示。假若接收向量r=0110001,此时伴随式是110正好是6的二进制表示,只要将接收向量的第6位加1,即c=r+e=0110001+0000010=0110011

则可得到正确的码向量。0+0+0+0+0+0+1=16.2.3汉明码6.3循环码6.3.1循环码的定义和结构

循环码是线性分组码的最重要的一个子集。这种编码的编码器和译码器更容易实现。目前实际应用中所使用的线性分组码大都是循环码。6.3循环码定义6-3

设c是线性分组码的任一码字，如果c经循环移位c=(c1,c2,…,cn-1,cn)→c⑴=(c2,c3,…,cn-1cn,c1)后的序列仍然是码字,那么称该线性分组码为循环码。例如,码集是循环码码集不是循环码。6.3循环码现以汉明码为例进一步说明循环码的含义。m码字m码字十进制二进制十进制二进制000000000000810001000101100010001011910011001110200100010110101010101001130011001110111101110110004010001001111211001100010501010101100131101110100160110011000114111011101007011101110101511111111111见下面汉明码表：

6.3循环码为了便于研究循环码的特性，把每一个码字用一个多项式表示。称为码字多项式。对应于码字的码字多项式定义为c循环移位的码字多项式为上式可改写为6.3循环码因二进制运算的加法和减法是等效的,故上式可为（模）注：所谓a(x)≡b(x)（模d(x)是指a(x),b(x)被d(x)整除后有相同的余项。或将c(1)在向左移得该码字多项式（模）6.3循环码定理6-4

在(n,k)循环码中,所有码字多项式都是某个r(r=n-k)次多项式g(x)的倍数,且g(x)是xn+1的因式,从而g(x)是首一的(指多项式最高次项系数为1),对任意信息序列m=(m1,m2,…,mk),定义:对应于m的码字多项式由给出。g(x)称为循环码的生成多项式。是和的离散卷积.6.3循环码【例6-4】(7,4)循环码的生成多项式次数为n-k=3,且必须x7+1是的因式，因为

,该码可以有三个生成多项式,选择并将其与所有m(x)多项式相乘,得到的16个码字多项式作为循环码的码字。m(x)为m1m2m3m40000000100100011010001010110011110001001101010111100110111101111

6.3循环码例

研究一个长度n=7的循环码的构成方法。解：（1）对（x7+1）作因式分解x7+1=(x+1)(x3+x2+1)(x3+x+1)有如下因式：

1次因式1种：(x+1)(x3+x2+1)=x4+x3+x+x3+x2+1(x+1)(x3+x+1)=x4+x3+x2+1(x3+x2+1)(x3+x+1)=x6+x4+x3+x5+x3+x2+x3+x+1=x6+x5+x4+x3+x2+x+1(x+1)3次因式2种：(x3+x2+1)，(x3+x+1)4次因式2种：=x4+x2+x+1(模2加)6次因式1种：(1)对作因式分解,找出其(n-k)次因式;6.3循环码(2)若以(n-k)次因式为生成多项式,可供选取的有：（n-k）=1（n-k）=3（n-k）=4（n-k）=61次因式1种：3次因式2种：4次因式2种：6次因式1种：

既在n=7的情况下可生成1种(7.6),2种(7.4),2种(7.3),1种(7.1)的循环码，若想得到(7.4)的循环码,生成多项式g(x)可选用7-4=3次多项式(x3+x2+1)或(x3+x+1)6.3循环码设信息多项式为=(m3、m2、m1、m0)=(0110),m(x)=m3x3+m2x2+m1x+m0

以g(x)=(x3+x2+1)生成(7.4)码为例,说明得到的确是循环码。对应的信息多项式为=x2+x循环码编码后所得码的多项式为:c(x)=m(x)g(x)==x5+x4+x2+x4+x3+x

=x5+x3+x2+x→(x2+x)(x3+x2+1)(0101110)6.3循环码【例6.3-2】分别写出循环码（7，4）对应于序列0100和1001的码字。得1101001。对0100，得0110100对10016.3循环码上次课内容6.2.2线性分组码的译码6.2.3汉明码6.3循环码6.3.1循环码的定义和结构

1.生成矩阵与校验矩阵之关系设线性分组码(n,k)的系统码的生成矩阵为校验矩阵H为r×n矩阵,满足:cHT=0或HcT=0.C为码字2.伴随式3.循环码设c是线性分组码的任一码字，如果c经循环移位c=(c1,c2,…,cn-1,cn)→c⑴=(c2,c3,…,cn-1cn,c1)后的序列仍然是码字,那么称该线性分组码为循环码。本次课内容

6.3.2循环码的生成矩阵和校验矩阵6.3.3循环码的编码器

6.3.4

循环码的译码器6.4卷积码6.4.1卷积码的基本概念6.4.2卷积码的生成矩阵与生成序列6.4.3卷积码的状态转移图与网格图6.4.4卷积码的译码概述

(n-k)循环码的生成矩阵可以用码空间中任何k个线性无关的码字作为基底来构成,所以不是唯一的,当循环码生成多项式g(x)给定后,最简单的方法是,取g(x)本身加上移位k-1个码字作为k个基底则得矩阵.6.3.2循环码的生成矩阵和校验矩阵6.3循环码g(x)=xn-k+gn-k-1xn-k-1+…..g2x2+g1x+1若循环码生成多项式则生成矩阵为通过这种方法获得的生成矩阵不是系统形式的。注意:6.3循环码例(7.4)循环码的生成多项式为g(x)=x3+x+1（1）该循环码系统形式的生成矩阵；（2）由生成矩阵得到校验矩阵求：6.3循环码则由生成多项式g(x)得

生成多项式为g(x)=x3+x+1(7.4)码6.3循环码解：G=生成矩阵校验矩阵1、由生成多项式g(x)直接生成系统循环码（1）将消息多项式m(x)乘以；（2）将m(x)除以g(x)得到余式r(x)；（3）将r(x)加在m(x)后面。c(x)=xn-km(x)+s(x)6.3循环码6.3.3循环码的编码器生成系统循环码的两种方法步骤：前例(7.4)循环码的生成多项式为g(x)=x3+x+1（1）用生成多项式g(x)

编出消息（1001）的系统循环码字；（2）用带反馈的移存器实现上述运算。求：6.3循环码(1)(m3m2m1m0)=(1001)将消息多项式m(x)乘以xn-k

除以

g(x)=x3+x+1m(x)=m3x3+m2x2+m1x+m0=对应消息多项式得(x3+1)x7-4得商x3-x和余式r(x)=x2+x=x6+x3+x2+x→故码多项式是c(x)=xn-km(x)+s(x)x3+1(1001110)=(x3+1)x3=x6+x36.3循环码（2）循环编码电路实现时的硬件结构图用除法器实现(7，4)循环码编码器

带反馈的移位器构成一个除以g(x)=x3+x+1的除法电路,反馈线的位置与g(x)的项对应.从左到右分别对应1,x,x3,正常做除法时,消息m(x)应从除法器的最左端(对应g(x)常数项1)进入,如消息m(x)右移一位,则应从一次项的位置进入,相当于xm(x)运算后再去做除法。c(x)=xn-km(x)+r(x)

g(x)=x3+x+1

6.3循环码设信息多项式生成多项式则相应的码多项式6.3循环码2、已知信息多项式和生成多项式求码字r级编码器的(乘法)电路图：它由r级线性移位寄存器组成，即r个模2加法器和最多有r+1个模2常数乘法器和r级移位寄存器组成。6.3循环码

开始运算时,r级移位寄存器的内容为全0,被乘多项式m(x)的系数按由高次至低次的顺序进入g(x)乘法电路,工作过程如下：（1)m(x)第一个系数mk-1首先进入电路时,码多项式C(x)的最高次项xn-1的系数mk-1gr就出现在输出端，同时mk-1送入移位寄存器第一级(最左边一级),此时,移位寄存器的内容是mk-100…0。6.3循环码（2)m(x)的第二个系数mk-2送入移位寄存器第一级,并与gr相乘,得到mk-2gr,此时,mk-1由第一级送至第二级,与gr-1相乘,并和mk-2gr相加,再送到输出端,就是C(x)中xn-2的系数,此时,移位寄存器的内容是mk-2mk-10…0。（3)重复上述过程k次后,m(x)的系数已全部送入移位寄存器中,n=k+1次后,移位寄存器传出了C(x)的常数项m0g0,移位寄存器的内容恢复到全0的初始状态。6.3循环码321【例6-7】考虑(7,4)循环汉明码.设m(x)=x3+x，g(x)=x3+x+1对应的码多项式是

C(x)=m(x)g(x)=x6+x3+x2+x其编码器电路如图所示：输出c=1001110输入m=10106.3循环码表6-8展示了编码过程。6.3循环码6.3.4循环码的译码器循环码的译码在原理上与一般线性码的译码极为相似。设与收序列对应的接收多项式为r(x)，则

r(x)=c(x)+e(x)

将r(x)除以生成多项式g(x)可得商q(x)及余式s(x)，即

r(x)=q(x)g(x)+s(x)6.3循环码循环码的所有码字多项式都是g(x)的倍式,故有:

s(x)=r(x)modg(x)=e(x)modg(x)

上式表明s(x)可以表示接收多项式r(x)中有无差错以及差错的图样,所以s(x)也叫作循环码的伴随式。

6.3循环码定理设s(x)是差错多项式e(x)对应的伴随式,s1(x)是e(x)的循环移位xe(x)mod(xn-1)对应的伴随式,则s1(x)=xs(x)modg(x)。

利用这一特征,可以减少译码时需要区别的错误图样的数目。以(7,4)汉明码为例,当作为一般线性码时译码需要区别的错误图样有7种，但当作为循环码时只需识别1种就可以了,因为其余6种都是这一错误图样循环移位所得的结果。6.3循环码在伴随式的基础上循环码的译码原理:⑴按码的生成多项式g(x)或一致检验多项式h(x)

计算接收多项式r(x)的伴随式；⑵按伴随式计算差错多项式e(x)；⑶输出c(x)=r(x)-e(x)

译码的主要运算量或存储量为⑵步，如何减少这一运算量或存储量是代数编码理论研究中的一个重要内容。6.3循环码循环码的一般译码器:(n,k)循环码的一般译码器由三部分组成:⑴一个n位缓冲寄存器；⑵组合逻辑电路;⑶一个r位的伴随式计算电路。这种译码器也称梅吉特（Meggit）通用译码器。它的复杂性由组合逻辑电路决定。如图所示。图6-3循环码的一般译码器(7,4)循环码的完整译码器参见[6]。伴随式计算电路组合逻辑电路n级缓冲寄存器6.3循环码

前面介绍的各种分组码都是将信息序列切割成分组后孤立地进行编译码,分组与分组之间没有任何联系.从信息论的角度看,这样做忽略了各信息分组之间的关系.必然丧失一部分相关信息,且信息序列切割的越碎(码字越短),丧失的信息就越多.若把码长n尽量长,又增加译码的复杂度.能否当码长n有限时,将有限分组的相关性信息添加到码字上,从而等效地增加码长.译码时能否利用前后码字的相关性将前面的编码信息反馈到后面供作译码参考.从而引出了卷积码.

卷积码最早是由埃利斯1955年提出的.6.4卷积码（2）将信息序列切割成长度为k的一个个分组；（3）在某一分组编码时,不仅参看本时刻的分组,而且要参看本时刻以前的m分组。一、卷积码特点：（1）是一个有记忆系统；二、特征参数：m+1:为约束长度;n:为码字长度；K:为分组长度;

m:某时刻前的分组数(记忆长度)。为突出特征参数常把卷积码写成(n,k,m)卷积码。6.4.1卷积码的基本概念6.4.1卷积码的基本概念三、编码原理图

i-m组i-mi-mi-m编码器内有k(m+1)阶移位寄存器,m+1称卷积码的约束长度(段).每次输入k比特信息进入移位寄存器,同时丢弃寄存器最右端的k比特,然后按照一定的规则计算出移位寄存器内的n个线性组合作为编码的结果。书中介绍的卷积码编码器的框图6.4.1卷积码的基本概念

n比特编码输出不仅和最近的k比特输入有关,还与前km阶输入寄存器的km比特信息有关。移位寄存器状态数目是2km.因为每个k比特输入,得到n比特输出,所以卷积码的码率为.6.4.1卷积码的基本概念

注意,进入卷积码编码器的最后m段消息仍是要编码输出的消息,一般的方法是额外输入m段无效的0数据比特,一方面将存储的m段消息编码输出,另一方面保证编码器回到全0的初态。6.4.1卷积码的基本概念

与分组码一样,卷积码也有系统码。系统码中每个子码ci的某一段码元是输入的k个信息元,其余的是n-k个校验元。但,对于非系统码,不能区分子码内哪些是信息元,哪些是校验元。卷积码的纠错能力由自由距离描述。6.4.1卷积码的基本概念

设编码器的初始状态为零(记忆阵列全体为0),随着一个个k比特信息组的输入,编码器源源不断地输出码字(c0.c1.cm.cm+1..)在时刻i=0时，

i=1时，

6.4.2卷积码的生成矩阵与生成序列与分组码一样,可用生成矩阵G(或校验矩阵H)来描述卷积码的编码过程。为卷积码的生成矩阵,由于信息序列本身是半无限的,故生成矩阵是半无限的。

数学表达式：

上式可视一个无限长矩阵序列

写成矩阵形式:与一个有限矩阵序

列的卷积运算*，

这即是卷积码的来历。在时刻i=0时，

i=1时，

mmm时刻i=1信息比特组例：某二进制(3.2.1)卷积编码器如图,若本

=（，）=（01），

上一时刻i=0的信息比特组=(

，

)=

(10),

试用矩阵表示该编码器,并计算输出码字。

用

表示记忆列阵第k行(k=0,1)第m列(m=0,1)对第j个(j=0,1,2)码元的影响.=1，=0，

解：有连线系数否则n×k×（m+1）=3×2×2个系数=1

=0

=1

=1

=1

=1

=0

=1

=1

=1

=0

=0

由(3.2.1)则k行n列2×3系数矩阵=

=

=1

=0

=1

=1

=1

=1

=0

=1

=1

=1

=0

=0