第6章信道编码-Qtech

第6章信道编码信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号 －－线路编码如何避免少量差错信号对信息内容的影响 －－纠错编码1本章内容有扰离散信道的编码定理纠错编译码的基本原理与分析方法线性分组码卷积码26.1 有扰离散信道的编码定理差错和差错控制系统分类矢量空间与码空间随机编码信道编码定理3差错类型差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示；差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示；对于二进制传输系统，符号差错等效于比特差错；对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。4差错图样（errorpattern）为了定量地描述信号的差错，定义收、发码之“差”为： 差错图样E＝发码C－收码R

（模M）例：8进制(M=8)码元， 若发码 C=（0,2,5,4,7,5,2） 收码变为 R=（0,1,5,4,7,5,4） 差错图样 E=C－R=（0,1,0,0,0,0,6）（模8）5差错图样（errorpattern）二进制码：E=CR或

C=RE

，差错图样中的“１”既是符号差错也是比特差错，差错的个数叫汉明距离。6差错图样类型随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。7纠错码分类从功能角度：检错码、纠错码对信息序列的处理方法：分组码、卷积码码元与原始信息位的关系：线性码、非线性码差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码、几何码、算术码、组合码等8差错控制系统分类前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力96.1.2矢量空间与码空间基本的纠错码为（n,k）分组码（块码）每块为k个符号由n个码元组成码字码字可视为n重矢量（n个矢量元素）106.1.2矢量空间与码空间F表示码元所在的数域(对于二进制码，F代表二元域{0,1})设n重有序元素的集合V={Vi

},若满足条件：V中矢量元素在矢量加运算下构成加群；V中矢量元素与数域F元素的标乘封闭在V中；分配律、结合律成立，则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。11矢量空间中矢量的关系

对于域F上的若干矢量线性组合：

线性相关：

其中任一矢量可表示为其它矢量的线性组合线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替.。12矢量空间与基底一组线性无关的矢量，其线性组合的集合就构成了一个矢量空间V，这组矢量就是这个矢量空间的基底。n维矢量空间应包含n个基底基底不是唯一的，例：线性无关的两个矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可张成同一个两维空间。13二元域GF(2)上三重矢量空间以（100）为基底可张成一维三重子空间V1，含21=2个元素，即以(010)(001)为基底可张成二维三重子空间V2，含22=4个元素，即以(100)(010)(001)为基底可张成三维三重空间V,含23=8个元素，V1和V2都是V的子空间。14概念重数构成矢量的有序元素的个数维数构成矢量空间的基底的个数15矢量空间每个矢量空间或子空间中必然包含零矢量两个矢量正交：V1V2＝0两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交正交的两个子空间V1、V2互为对偶空间

(DualSpace)，其中一个空间是另一个空间的零空间（nullspace，也称零化空间）。16码空间

17

消息k长 (n,k)码字n长

qk

种分组编码器qn种

k维k重矢量n维n重矢量

通常qn>>qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。分组编码的任务选择一个ｋ维n重子空间作为码空间。确定由k维k重信息空间到ｋ维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。186.1.3随机编码编码的分析设计途径：1.数学解析途径，即将代数、几何、数论等理论运用到编解码，如分组码，卷积码。2.运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。196.1.3随机编码对于一个(N,K)分组编码器对K个q进制组成的消息组m=(m0,m1,…,mk-1)编码；生成N个q进制符号组成的码字c=(c0,c1,…cN-1)；在(N,K)分组编码器中随机选定的码集有qNM种一个消息组的编码有qN种选择（N个码元，q进制）qK个消息组共有种选择令M=qK，可得上式206.1.3随机编码在(N,K)分组编码器中随机选定的码集有qNM个第m个码集(记作{c}m)被随机选中的概率是设与这种选择相对应的条件差错概率是Pe({c}m)全部码集的平均差错概率是216.1.3随机编码必定存在某些码集某些码集若，就必然存在一批码集即差错概率趋于零的好码一定存在；226.1.3随机编码码集点数M=qK占N维矢量空间总点数qN的比例是 F=qK/qN

=q-(N-K)

当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字之间的平均距离将变大，平均差错概率将变小。当F0即(N-K)时，能否让平均差错概率？

Gallager在1965年推导了的上边界，并证明这个上边界是按指数规律收敛的。236.1.4信道编码定理E(R)为可靠性函数，也叫误差指数；码率：R=(lbM)

/N

M是可能的信息组合数，M=qKN是每码字的码元数，R表示每码元携带的信息量，单位是比特每符号（bit/symbol）246.1.4信道编码定理R在[0,R0]区间时：E(R)~R曲线是斜率为-1（-45）的直线，E(R)反比于R；而当R=C（信道容量）时：E(R)=0，即可靠性为零。25

E(R)

C

R0R0-45

E(R)和R的关系曲线6.1.4信道编码定理正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R>C，就不可能有任何一种编码能使差错概率任意小。266.2纠错编译码的基本原理与分析内容：纠错编码的基本思路译码方法－最优译码与最大似然译码276.2.1纠错编码的基本思路R不变，信道容量大者其可靠性函数E(R)也大；C不变，码率减小时其可靠性函数E(R)增大。28E(R) R0R1<R2C1

<C2

增大E(R)的途径信道编码定理6.2.1纠错编码的基本思路增大信道容量C

扩展带宽：开发新的宽带媒体加大功率：提高发送功率、提高天线增益降低噪声：采用低噪声器件减小码率R

（R=(lbM)

/N

）Q、N不变而减小K

Q、K不变而增大NN、K不变而减小Q增大码长N296.2.1纠错编码的基本思路另一种思路是从概念上分析纠错编码的基本原理，可以把纠错能力的获取归结为两条：一条是利用冗余度，另一条是噪声均化（随机化、概率化）30冗余度就是在信息流中插入冗余比特。例：3bit表示4种意义。为了传输这些冗余位，必然动用冗余的资源。这些资源可以是：时间、频带、功率、设备复杂度噪声均化就是让差错随机化，就是设法将危害较大的、较为集中的噪声干扰分摊开来。1、增加码长N例：设某BSC信道误码率Pe=0.01，假如编码后的纠错能力是10%。先设码长N=10，码字中多于1位误码时就会产生译码差错，差错概率为：6.2.1纠错编码的基本思路31如果保持码率不变，将码长增加到N=40，那么当码字中多于4位误码时，会产生译码差错，差错的概率为卷积：卷积码在一定约束长度内的若干码字之间加进了相关性，译码时不是根据单个码字，而是一串码字，这样就可以将噪声分摊到码字序列而不是一个码字上。交错：交错是对付突发差错的有效措施。6.2.2最优译码与最大似然译码译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。译码算法的已知条件是：实际接收到的码字序列{r},r=(r1,r2,…,rN)发端所采用的编码算法和该算法产生的码集XN，满足信道模型及信道参数。326.2.2最优译码与最大似然译码最佳译码，也叫最大后验概率译码(MAP:Maximumaposteriori)已知r的条件下找出可能性最大的发码作为译码估值通过经验与归纳推测发码的方法实现困难33

消息组mi

码字ci

接收码r

估值

消息编码器信道译码消息还原6.2.2最优译码与最大似然译码最大似然译码(MLD:MaximumLikelihoodDecoding)已知r的条件下使先验概率最大的译码算法346.2.2最优译码与最大似然译码如果构成码集的2K个码字以相同概率发送，满足P(ci)=1/2K

，i=1,2,…,2K

P(r)对于任何r都有相同的值，满足P(r)=1/2K

则P(ci/r)最大等效于P(r/ci)的最大，在此前提下最佳译码等效于最大似然译码。356.2.2最优译码与最大似然译码对于无记忆信道，

例：BSC信道的最大似然译码可以简化为最小汉明距离译码。汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概率，汉明距离译码也就是最佳译码。

36376.3线性分组码码集C能否构成n维n重矢量空间的一个k维n重子空间？如何寻找最佳的码空间？qk个信息元组以什么算法一一对应映射到码空间。码率－－编码效率：Rc

=k/n

（二进制）；

Rc

=k*lbq/n(q进制)38

消息m (n,k)码字c

m=(mk-1,…,m1,m0)

分组编码器c=(cn-1,…,c1,c0)

qk<qn6.3.1

生成矩阵和校验矩阵c＝mG1×n1×k

k×n

码字消息生成矩阵

G＝[gk-1…g1g0]T，有k个(1×n)行矢量，如何选择呢？

39线性分组码的形成c=

mk-1

gk-1+…+

m1

g1+m0g0

码空间的所有元素（即码字）都可以写成k个基底的线性组合；由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。当信息元确定后，码字仅由G矩阵决定，因此称这k×n矩阵G为该(n,k)线性分组码的生成矩阵。

40生成矩阵G(k×n)的特点想要保证(n,k)线性分组码能够构成k维n重子空间，G的k个行矢量gk-1,…,g1,g0必须是线性无关的，只有这样才符合作为基底的条件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。41系统形式的生成矩阵(n,k)码的任何生成矩阵都可以通过行运算（以及列置换）简化成“系统形式”。G=[Ik

P]=Ik是k×k单位矩阵，P是k×(n-k)矩阵。42生成的码字C前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的（n,k）码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。43空间构成n维n重空间有相互正交的n个基底选择k个基底构成码空间C选择另外的(n-k)个基底构成空间DC和H是对偶的

CDT＝0,GHT=044

n维n重空间V

k维k重k维n重n-k维信息组码空间n重对偶

空间mC空间D

GH对偶空间与(n,k)分组线性码的码空间C相对应，必然存在一个对偶空间D：码空间基底数为k,找出另外n-k个基底，可找到对偶空间；用n-k个基底生成的(n,n-k)分组线性码，称为(n,k)分组线性码的对偶码。45校验矩阵将H空间的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为校验矩阵H。用来校验接收到的码字是否是正确的；cHT=0(任意码字正交与H的任意行矢量)G是(n,k)码的生成矩阵，H是它的校验矩阵；H是(n,n-k)对偶码的生成矩阵，它的每一行是一个基底。G则是它的校验矩阵。（对偶是相互的）GHT=0，H＝[－

PTIn-k]，二进制时，负号可省略。46例6-2 (6,3)线性分组码，其生成矩阵是

G=求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r=[100110],检验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。

47111010①110001②011101③例6-2码集与映射关系（1）

c=

mk-1

gk-1+…+

m1

g1+m0g0

48信息码字系统码字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 111010111010①110001②011101③例6-2计算系统码码集（2）

将G改写成=[Ik

P]形式：49111010①110001②011101③原①③行相加作为第1行；原①②③行相加作为第2行；原①②行相加作为第3行；得到矩阵：100111①010110②001011③例6-2计算系统码码集（2）

c=

mk-1

gk-1+…+

m1

g1+m0g0

，结果如下：50信息码字系统码字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 111010100111①010110②001011③码集未变，但映射关系变了！例6-2计算校验矩阵H（3）

51100|111010|110001|011G==[I3|P],H=[PT|In-k]=110|100111|010101|001不同的3个基底分别构成了码空间和对偶码空间；若收码r=[100110]，rHT=[100110]=[001]≠0,不是码字。

例6-2编码器电原理图（4）：52C=(c5,c4,c3,c2,c1,c0=(m2,m1,m0,c2,c1,c0)=m2[100111]+m1[010110]+m0[001011],求解得到：C5=m2C4=m1C3=m0c2=m2+m1C1=m2+m1+m0C0=m2+m0100|111010|110001|011例6-2编码器电原理图（4）：53m0

m1

m2

输入 输出

c0

c1

c26.3.2伴随式与标准阵列译码mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)

(n,k)信道定义差错图案EE＝(en－1,…,e1,e0)＝R－C

＝(rn-1－cn-1,…,r1－c1,r0－c0)二进制码中模2加与模2减是等同的，因此有 E=R＋C及 R=C＋E 54伴随式S的定义因为CHT=0（码字与校验矩阵的正交性）所以RHT＝(C＋E)HT＝CHT＋EHT=EHT如果收码无误：必有R＝C即E＝0，则EHT=0RHT=0。如果收码有误：即E0，则RHT=EHT0。在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义伴随式S

S=(sn-k-1,…,s1,s0)=RHT=EHT

55

伴随式S的意义从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图案可能有相同的伴随式。接收端收到R后，因为已知HT，可求出S＝RHT；如果能知道对应的E，则通过C=R＋E而求得C。

56RHT=S ?C=R＋ERSEC

只要E正确，译出的码也就是正确的。

差错图案E的求解(1)可以通过解线性方程求解E：

S=(sn-k-1,…,s1,s0)=EHT

=(en-1,…e1,e0)得到线性方程组：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h0057差错图案E的求解(2)上述方程组中有n个未知数en－1,…e1,e0

，却只有n-k个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-(n-k)=k个方程导致每个未知数有2k个解。因此，由上述方程组解出的E可以有2k个解。到底取哪一个作为附加在收码R上的差错图案E的估值呢？概率译码：把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。5859依据：若BSC信道的差错概率是p，则长度n的码中错误概率：

0个错1个错2个错…n个错

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

由于p<<1,>>>>>>…>>

出错越少的情况，发生概率越大，E的重量越轻。所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。标准阵列译码表

上述的概率译码，如每接收一个码R就要解一次线性方程，太麻烦！伴随式S的数目是有限的2n-k个，如果n-k不太大，可以预先把不同S下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做标准阵列译码表。60标准阵列译码表的构成表中所列码字是接收到的码字R；将没有任何差错时的收码R放在第一行，收码等于发码R=C(CCi,i=0,1,…2k-1),差错图案为全零E0=(0,0…0)，伴随式为全零S0=(0,0…0)。由于有2k个码字，码表有2k列。在第2到第n+1的n行中差错图案的所有重量为1(共n个)。61如果总行数(1+n+)仍然小于2n-k，再列出带有3个差错的图案，以此类推，直到放满2n-k行，每行一个Ej,对应一个不同的伴随式Sj。这样，表的行数2n-k正好等于伴随式的数目。如果(1+n)<2n-k，再在下面行写出全部带有2个差错的图案(共个)。62S0E0S1E1

SjEj

E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1

E1+CiEj+C0=EjEj+C1Ej+Ci

标准阵列译码表在码表的第j行、第i列填入Ci+Ej：E1+C1

陪集和子集译码表中有2n-k行，每行是一个陪集，每陪集的第一个元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式S0所对应的全零差错图案E0(无差错)，而第j行陪集的陪集首是伴随式Sj所对应的重量最小的差错图案Ej(C0=0,Rj=Ej)。译码表中有2k列，每列是一个子集，每子集的第一个元素(位于第一行)叫子集头。同一子集（同一列）中的所有元素对应同一个码字，第一列子集的子集头是全零码字C0，而第i列子集的子集头是码字Ci(E0=0,Ri=Ci)。6364例

6-3

一个(5,2)系统线性码的生成矩阵是G=设收码R=(10101)，构造标准阵列译码表，译出发码的估值解：(1)构造标准阵列译码表。分别以信息组m=(00)、(01)、(10)、(11)及已知的G求得4个许用码字为（c=

mk-1

gk-1+…+

m1

g1+m0g0=mG)C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校验矩阵：

H=[PTI3]=列出方程组：S=EHT65伴随式有2n-k＝23＝8种组合，差错图案中代表无差错的有一种，代表一个差错的图案有种，已有6种。代表两个差错的图案有种。只需挑选其中的两个就可凑足8种组合。挑选方法可有若干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，解得对应的Sj分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，(011)所对应的差错图案是2k个即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最轻，任选其中一个如(00011)。同样可得伴随式(110)所对应的最轻差错图案之一是(00110)。例6-3译码表的构成66S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例6-3标准阵列译码表（第j行、第i列填入Ci+Ej）例6-3将接收码R＝10101译码

可选以下三种方法之一译码：直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。先求伴随式RHT=(10101)HT=(010)=S4，确定S4所在行，再沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找出码字(10111)。先求出伴随式RHT=(010)=S4并确定S4所对应的陪集首（差错图案）E4=(00010)，再将陪集首与收码相加得到码字C=R+E4=(10101)+(00010)=(10111)。上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。6768

对上例作进一步分析，还可以看到，该(5,2)码的dmin=3,纠错能力是t=INT[(3-1)/2]=1。因此，译码阵列中只有前6行具有唯一性、可靠性，真正体现了最大似然译码准则，而第7、8行的差错图案(00011)和(00110)中包含两个“1”，已超出了t=1的纠错能力，译码已不可靠。比如，当收码R＝(10100)时，根据码表译出的码字是(10111)，与收码R的汉明距离是2，然而收码R与全零码字(00000)的汉明距离也是2，为什么不能译成(00000)呢？事实上，码表的第7、8行本身就不是唯一的。注意在码表计算过程中，伴随式(011)所对应的4个差错图案中有两个并列重量最轻，如果当时选的不是(00011)而是(10100)，那么码表第7行就不是现在这样了。对例6-3的分析6.3.3码距、纠错能力、MDC码及重量谱N重码矢c=(cn-1,cn-2,…c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集；发码一定在这个子集里，传输无误时的收码也一定位于该子集；当出现差错时，接收的N重矢量:对应到子集外空间某一点；对应到该子集，却对应到该子集的另一点上；696.3.3码距、纠错能力、MDC码及重量谱码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmin；dmin表明各码字差异程度，差异越大，抗干扰能力越强；这里dmin=3，纠错能力是1，检错能力是270td=7dmin=3d=5C1C2C3C4C56.3.3码距、纠错能力、MDC码及重量谱定理6.1

任何最小距离dmin的线性分组码，其检错能力为（dmin-1）,纠错能力t为71定理6.2线性分组码的最小距离等于码集中非零码字的最小重量

dmin=min{w(Ci)} CiC及Ci

0 6.3.3码距、纠错能力、MDC码及重量谱定理6.3(n,k)线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。定理6.4(n,k)线性分组码的最小距离必定小于等于(n-k+1) dmin

(n-k+1) 726.3.3码距、纠错能力、MDC码及重量谱例：

H＝(7，4)线性码各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k+1＝4。736.3.3码距、纠错能力、MDC码及重量谱（n,k）线性码最小距离dmin的上边界是n-k+1。如果我们设计的（n,k）线性码的dmin达到了n-k+1，就是达到了设计性能的极点。因此，dmin＝n-k+1的码称为极大最小距离码

(MDC–MaximizedminimumDistanceCode)。总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关。746.3.4 完备码(Perfectcode)任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件75上式称作汉明限，任何一个纠t码都应满足上述条件。6.3.4 完备码

某二元(n,k)线性分组码能使等式76成立，即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。这样的二元(n,k)线性分组码称为完备码。

汉明码(HammingCode)汉明码不是指一个码，而是代表一类码。汉明码的纠错能力t=1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整数。当m＝3、4、5、6、7、8…时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。汉明码是完备码，因为它满足下述等式：77高莱（Golay）码是二进制（23，12）线性码，其最小距离dmin＝7，纠错能力t=3。是完备码，因为满足等式

223-12=2048=78在(23,12)码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码，其最小距离dmin＝8。

6.3.5循环码循环码是线性码的一个子类；满足下列循环移位特性：码集C中任何一个码字的循环移位仍是码字。79循环码的多项式描述一般(n,k)线性分组码的k个基底之间不存在规则的联系，因此需用k个基底组成生成矩阵来表示一个码的特征。而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就足以表示一个码的特征。既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了。80循环码的多项式定义把码字C＝[cn-1cn-2

…c1c0]与一个不大于n-1次的码多项式C(x)对应起来。码多项式C(x)定义为：

C(x)=cn-1xn-1+cn-2xn-2

+…+c1x+c0

对于二进制码，ci{0,1},i=0,…，n-1。81循环码的循环移位循环移一位：(cn-1cn-2

…c1c0)(cn-2

…c1c0cn-1)循环移一位：C0(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0

C1(x)=

cn-2xn-1+cn-3xn-2+…+c0x+cn-1比较循环移位的前后，可用如下的多项式运算来表达循环移位

移1位： C1(x)=xC0(x) mod(xn

+1)

移2位： C2(x)=xC1(x)=x2C0(x) mod(xn

+1)

移n-1位：Cn-1(x)=xCn-2(x)=xn-1C0(x) mod(xn

+1)82码字的组成根据码空间的封闭性，码字的线性组合仍是码字。C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x)=(a0+a1x

+a2x2+…+an-1xn-1)C0(x)=A(x)C0(x) mod(xn

+1) 其中C0(x)是一个码多项式，而A(x)是次数不大于n-1的任意多项式。对于二进制码，ai{0,1},i=0,…，n-1。83生成多项式

C(x)=m(x)g(x)

码多信息生成项式多项式多项式生成多项式不是唯一的；g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1

是(n-k)次的首一码多项式，即(n-k)次项的系数为1。g(x)一定是(xn+1)的因子。84校验多项式多项式xn+1可因式分解为xn+1＝g(x)h(x)的形式；如果g(x)代表(n，k)循环码的生成多项式，则h(x)代表该循环码的一致校验多项式，其阶次为k。h(x)的校验作用表现在：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码字与h(x)的乘积必不为0。

C(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1)=0mod(xn+1)85例6.5

研究一个长度n=7的循环码的构成方法(1) 对(x7+1)作分解，找出n-k次因式。

x7+1＝(x+1)(x3+x2+1)(x3+x+1)，

n-k因式g(x)对偶式h(x) 循环码

1(x+1) (x3+x2+1)(x3+x+1) (7,6)3(x3+x2+1)(x+1)(x3+x+1) (7,4)3(x3+x+1)(x+1)(x3+x2+1) (7,4)4(x+1)(x3+x2+1)(x3+x+1) (7,3)

4(x+1)(x3+x+1)(x3+x2+1) (7,3)6(x3+x2+1)(x3+x+1)

(x+1) (7,1)86例6.5

研究一个长度n=7的循环码的构成方法若构成(7,3)循环码： 选g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，则C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。当输入信息m=(011)时，m(x)=(x+1)，C(x)=(x+

1)(x4＋x3＋x2＋1)=x5+x2+x1+

1， 对应码矢C=(0100111)。87例6.5

研究一个长度n=7的循环码的构成方法信息矢量m(m2m1m0)码矢C(c6c5c4c3c2c1c0)0000010100111001011101110000000001110101110100100111111010011010011001110101001188作业89复习并掌握课堂上讲概念的例题！系统循环码码字的前k位原封不动照搬信息位而后面(n－k)位为校验位：C(x)=xn-km(x)+r(x)产生系统循环码的方法：将信息多项式m(x)预乘xn-k；将xn-km(x)除以g(x)，得余式r(x)；得系统循环码的码多项式：C(x)=xn-km(x)

+r(x)。9091例6.6

(7,3)循环码生成多项式是g(x)=x4+x3+x2+1，用式(6-3-35)产生系统循环码。解：先以输入信息m=(011)即m(x)=(x+1)为例，①.xn-km(x)=x4(x+1)=x5+x4

②.(x5+x4)除以(x4+x3+x2+

1)，得余式(x3+x)③.C(x)=xn-km(x)

+r(x)＝(x5+x4)+(x3+x),对应码矢(0111010)。依次将(000)…(111)代入，可得全部码矢如表6-6。此表与表6-5对比，可见码集未变而映射规则变了，表6-6满足系统循环码要求。

扩展码

如果给每个码字添加一位奇偶校验位c校，构成（n＋1，k）线性码，称为扩展码。

[cn-1,…,c1,c0] [cn-1,…,c1,c0,c校] c

n－1…c1c0

c

校＝0在二进制偶校验时：原来码字中1的个数为偶数，则添加校验位0；原来码字中1的个数为奇数，则添加校验位1。如果某码原来的最小重量dmin是奇数，则新的最小距离变为dmin+1，检错能力增1。

校验矩阵He＝92

H缩短码

把第一位为1的所有码字舍去，剩下另一半第一位为0的码字舍去它们的第一位后组成一个新的(n－1，k－1)码，称为缩短码。码长n－1和信息位长度k－1均缩短了。(n－1，k－1)缩短码共包含2k2=2k-1个码字。由于原先保留的均是第一位为0的码，舍去它们的第一位不会改变码的最小重量，因此缩短码与原码具有同样的dmin。称为（n-1,k-1,dmin）缩短码。9394例：(7,4)码的生成矩阵为

4×7m3m2m1m0ci2ci1ci000000000001011001011000111010100111010110001100010111010Ci＝mG

＝[m3m2m1m0]

码字中的c6去掉，c6是信息位m与G的第一列相乘结果，所以G的第一列应去掉；m3去掉，而m3是与G的第一行相乘，所以G的第一行也去掉。95得到新的生成矩阵为G’＝

3×6原来的校验矩阵H为H＝

3×7校验时，计算rHT，因r的第一位已没有，故HT的第一行应去掉，即H的第一列去掉。得到新的校验矩阵H’为

H’＝dmin不变，为3。

3×6循环冗余校验(CRC)码信息位k和码长n可变，校验位长度n-k固定，符合(n-i,k-i)缩短循环码的特点。以一个选定的(n,k)循环码为基础，改变i值，得出任意信息长度的码字，而纠检错能力保持不变。循环冗余校验码（(CRC-CyclicRedundancyCheck)）是系统的缩短循环码。9697例6－10

某CRC码的生成多项式g(x)=x4+x+1。如果想发送一串信息110001…的前6位并加上CRC校验，发码应如何安排？收码又如何检验？解：本题信息多项式m(x)=x5+x4+1,即k=6，因此n=10，deg[g(x)]=4=n-k

。将xn-km(x)除以g(x),得余式

r(x)=xn-km(x)modg(x)=x4(x5+x4+1)modg(x)=(x9+x8+x4)modg(x)=x3+x2

于是发码C(x)=xn-km(x)+r(x)=x9+x8+x4

+x3+x2，对应的码字是(1100011100)。接收端的CRC校验实际上就是做除法。如果收码无误，R(x)除以g(x)应得余式0；反之，如果余式不等于零就说明一定有差错。6.4卷积码卷积码的产生分组码以孤立码块为单位编译码信息流割裂为孤立块后丧失了分组间的相关信息分组码长n越大越好，但译码运算量随n指数上升本节内容卷积码的基本概念和描述方法卷积码的最大似然译码维特比算法卷积码的性能限与距离特点98996.4.1卷积码的基本概念和描述方法将信息序列分隔成长度k的一个个分组某一时刻的编码输出不仅取决于本时刻的分组，而且取决于本时刻以前的L个分组。称L＋1为约束长度最重要的三个参数(n,k,L)100(n,k,L)卷积编码示意

第i分组第i-1分组第i-2分组……第i-L分组

m0im1i…mk-1im0i-1…mk-1i-1m0i-2…mk-1i-2………m0i-Lm1i-L…mk-1i-L输入

…… …………

卷积编码器（线性组合器）

c0ic1i…cn-2icn-1i

编码输出Ci101mk-1i-2mk-1i-2mk-1i-2…mk-1i-Lm0im0i-1m0i-2…m0i-Lm1im1i-1m1i-2…m1i-L102串并变换线性组合器…………串并变换C0iC1iCn-2iCn-1i编码输出

例6-11二进制(3,2,1)卷积编码器103

c0i信号入

m

c1iCi

编码输出

c2im0im0i-1m1im1i-1本时刻m0=(m00,m10)=(01),上一时刻m1=(m01,m11)=(10)gknl表示记忆阵列第k行(k=0,1)第l列(l=0,1)对第n个(n=0,1,2)码元的影响,共N×K×(L+1)=

3×2×2个系数：

g000=1,g001=1,g010=0,g011=1,g020=1,g021=1,g100=0,g101=1,g110=1,g111=0,g120=1,g121=0。用矩阵表示104本时刻编码输出：

C0=(c00,c10,c20)=m0G0+m1G1=(01)+(10)=(011)+(111)=(100)105卷积码名称的由来设编码器的初始状态为零（记忆阵列全体清0），随着时刻i的递推和k比特信息组(m0,m1,…,mL,mL+1,…)源源不断地输入，码字(C0,C1,…,CL,CL+1,…)源源不断地输出。在时刻i=0时，C0

=m0G0 i=1时，C1=m1G0+m0G1

i=L

时，CL=mLG0+mL-1G1…m0GLi=L+1时，CL+1=mL+1G0+mLG1…m1GL

于是任何时刻i的输出码字：Ci=mi-lGl

106多项式表示G(D)=G0+G1D+…+GLDL=gkn(D)=gkn0+gkn1D+gkn2D2+…+gknLDL=gknlDl例6-11中

107例6－12

二元(3,1,2)卷积码的转移函数矩阵G(D)=(1,1+D,1+D+D2)，根据转移函数矩阵，

g00(D)=g000+g001D+g002D2=1

g01(D)=g010+g011D+g012D2=1＋D

g02(D)=g020+g021D+g022D2=1+D+D2得 g000=1,g001=0,g002=0, g010=1,g011=1,g012=0, g020=1,g021=1,g022=1。

108

c0i

信号入

m

c1i

输出Ci

c2im0im0i-1m0i-2例6-13同例6-12的（3，1，2）卷积码，转移函数矩阵G(D)=(1,1+D,1+D+D2)试用状态流图来描述该码。假如输入信息序列是10110，而输出码字是什么？状态m0i-1m0i-2S000S101S210S311m0i=0m0i=1S0000111S1001110S2011100S3010101109m0i=0m0i=1S0S0S2S1S0S2S2S1S3S3S1S3编码器状态的定义不同状态与输入时编出的码字不同状态Si与输入时的下一状态Si+1图6-20(3,1,2)卷积码状态流图假如输入信息序列 是10110…，

S0

1/111S2

0/011S11/110S2

1/100S30/010S1……

1100/000S01/1110/0011/110S2S10/0111/1000/010S3