信息论与编码(第6章)

信息理论与编码朱仁祥zhurx@电子与信息工程学院1编码信道：无线通信中的发射机、天线、自由空间、接收机等的全体；有线通信中的如调制解调器、电缆等的全体；Internet网的多个路由器、节点、电缆、底层协议等的全体；计算机的存储器（如磁盘等）的全体。二进制对称信道的模型其中，c=(c0,c1,…,cn-1)；ci∈{0,1}r=(r0,r1,…,rn-1)；ri∈{0,1}编码信道码字c接收向量r编码信道信道编码信道译码接收向量r消息m码字cp(r/c)消息m׳21错误图样⑴当系统无干扰时r=c⑵当系统有干扰时r=c+e其中，e是随机变量,称为信道的错误图样，e=(e0,e1,…,en-1)；ei∈{0,1}；当ei=1，则第i位上有错；反之，无错。例：c=00101101e=01001001

r=01100100有信道的对称性可知p(0/1)=p(1/0)=p（e=1)=p反之，若已知r,e则可求出c，这就是纠错码的原理，如：

e=01001001

r=01100100c=00101101图6.1.4BSC转移概率1－pb00111－pbpbpb图6.1.5BSC编码信道1CER3按功能分检错码纠错码纠删码（发现不可纠正的错误时，可发出指示或删除）按信息码元和监督码元之间的约束方式分分组码卷积码按信息码元和监督码元之间的校验关系分线性码：编码规则可以用线性方程表示；非线性码：编码规则不能用线性方程表示；2、纠错编码的分类信道编码又称为差错控制编码，简称为纠错编码，即在信息序列中按一定的规则附加若干监督码元，以便对信息传输（或存储）起检错与纠错作用，目的在于提高通信（或存储）的可靠性，减低误码率。4分组码：编码的规则仅局限于本码组之内，本码组的监督元仅和本码组的信息元相关。信息码组由k个二进制码元组成，共有2k个不同的信息码组；附加n－k个码元，每个监督元取值与该信息码组的k个码元有关；编码器输出长度n；这2k

个码字的集合称为(n,k)分组码；卷积码：本码组的监督元不仅和本码组的信息元相关，而且还与本码组相邻的前n－1个码组的信息元相关。5按纠正差错的类型分纠正随机错误的码纠正突发错误的码纠正随机/突发错误的码纠同步错误的码按构造码理论分代数码几何码算术码组合码按码字中每个码元的取值分二进制码多进制码按码字之间的关系分循环码非循环码按码字中每个码元的取值分系统码：前k个码元与信息码组一致非系统码：没有系统码的特性6卷积码非线性码线性码纠错码分组码循环码非循环码纠随机错误码纠突发错误码纠随机和突发错误码纠同步错误码76.1Galois域域F是一个元素的集合，在集合上定义了两种运算加和乘，满足下列性质加法：F在加法下封闭，即若a,b。2.满足结合律，即若。3.满足交换律，即a+b=b+a。4.F中含有一个加法恒元0，满足a+0=a。5.集合中每个元素a都有一个加法逆元–a，满足a+(–a)=086.1Galois域乘法：集合F*在乘法下封闭。F*为F除去加法恒元0，记作F*=F-{0}。满足交换律。满足结合律。满足乘加分配律，即(a+b)*c=a*c+b*cF中含有单位元１，对F中任意元素a满足a*1=a。F中任一非零元素a有乘法逆元a–1，满足a*a–1=1。9Galois域例｛０,1｝就构成了最简单的有限域GF(2)+01001110*0100010110⊕01234

001234112340223401334012440123⊙123411234224133314244321模5加法表

模5乘法表

11注1：如果D不是素数，({0,1,…,D-1},(modD)加法,(modD)乘法)不是有限域，只是有限环。注2：有限域GF(D)上的线性代数完全类似于实数域上的线性代数，线性代数的所有内容都在“加法”和“乘法”基础上得到。元素的“加法”负元；非0元的“乘法”逆元；一组向量是否“线性无关”的概念以及所有等价的判别方法；矩阵的“秩”的概念以及所有计算方法；方阵是否“可逆”的所有判别方法；求方阵的“逆阵”的所有算法；关于对称矩阵的所有结论；等等。注3：有限域GF(D)与实数域的区别是：传统的“逼近”、“极限”的概念消失了。12矢量空间与码空间最基本的码是（n,k）分组码，也叫块码，是把信息流切割为k符号一组的独立块后，编成n个码元组成的码字。把码字看成一个n重矢量，n个码元正是n个矢量元素，于是就可以从矢量空间的角度来分析和理解分组码13定义：若线性空间V中的子集Vs也满足线性空间的条件，则称Vs是线性空间V中的一个子空间。定义：能张成（或生成）整个线性空间Vn（F）（或子空间）的一组线性无关的矢量集合称为该线性空间的一个基底，基底中的矢量数目称为该线性空间（或子空间）的维数。（自然基底：矢量元素中包含一个１而其余为０的那组基底，基底不唯一）定义：两个矢量（或数组），若其内积：则称这两个矢量（或数组）互为正交。定义：如果V1，V2是V中两个子空间，且V1中每个矢量都与V2中每个矢量正交，则称V1和V2互为零空间（解空间）或两空间正交，V1•

V2＝0。正交的两个子空间V1，V2互为对偶空间定理：n维线性空间Vn中两个正交子空间V1，V2，若V1是k维子空间，则V2必为（n-k）维子空间。14n维n重空间——以n个(n重)线性无关的矢量作基底，张成的空间S

k维n重空间——从n个(n重)基底中，取出k(k＜n)个矢量作基底，张成的k维n重空间ScSc——S的一个子集(子空间)1001000001100111011110100010010103维3重空间(8个)1001000001100100102维3重空间(4个)0000010011维3重空间(2个)例:15码字空间：q进制(n,k)分组码如果原始信源空间有k个码字，对其进行q元等长码的信道编码，码长为n，信道码字空间的所有码字为qn个，编码器将在这qn个可用码字中选择k个码字分别代表原始信源中的k个码字，信道编码码字空间的这k个码字称为“许用码字”，而另外的qn-k

个码字称为“禁用码字”。为了实现纠错编码，一定有qn>>qk

。这k个许用码字也称为一个码组，或称为码字集合。分组编码的任务:

要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间,其元素就是许用码的码集16信道编码目的：降低错误译码概率PE。对象：信息序列（设码元间彼此无关且等概出现）。方法：在传输的信息码之中按一定规律产生一些附加数字，经信道传输，在传输中若码字出现错误，收端能利用编码规律发现码的内在相关性受到破坏，从而按一定的译码规则自动纠正或发现错误，降低误码率。17实质：在保持一定传输信息速率条件下，通过增加一定的码元多余度，使输出的码字具有特定的相关性，从而使收端易于发现或纠正由于信道噪声而引起的传输错误。

M=qk个k维矢量信息序列禁用码组许用码组码字编码过程n重序列qn个信道编码器MC校验元信息序列码字编码规则qk个18C0C1Ci┋Cj┋C2k-1收端传输模式

Pe～信道传输特征

Pe～译码方法C2k┋Ci’┋C2n-1许用码组禁用码组C0C1┋Ci┋C2k-1许用码组发端不可检出错误传输正确传输可检出错误传输19码元的组成及其它们之间的关系信息码组：数字序列m总是以k个码元为一组传输，称这k个码元的码组为信息码组。例如遥控系统中的每个指令字，计算机中的每个字节。码组/码字：信道编码器按一定的规则对每个信息码组附加一些多余的码元，构成了n个码元的码组。监督码元/监督元：附加的(n－k)

个码元称为该码组的监督码元或监督元。20如用三位二进制编码来代表八个字母

000

A 100 E

001 B

101

F

010 C

110

G011

D 111 H不管哪一位发生错误，都会使传输字母错误如用三位二进制编码来传四个字母

000A 011 B 101 C 110 D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。如用三位二进制编码来传二个字母

000A 111 B 检两个错误，纠正一个错误。大数法则纠错。结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数 －>引入余度。例:21检纠错原理1.目的

(1)检错——r=c？由r来判决所发送的是否为c(2)纠错——r→c，纠正导致r≠c的错误2.模型

(1)冗余编码——n>k(2)编码效率——R=k/n3.几种简单的检纠错码

(1)偶(奇)校验码——检错码①一维偶校验

A.偶校验码字：c=(m0,m1,…,mk-1,p)B.校验位：p=m0+m1+…+mk-1(mod2)C.校验方程：m0+m1+…+mk-1+p=0(mod2)D.C中一定有偶数个“1”,当差错图案E中有奇数个“1”，即

R中有奇数个位有错时，可以通过校验方程是否为0判断有无可能传输差错。cer纠错编码m=(m0,m1,…,mk-1)k位c=(c0,c1,…,cn-1)n位22②二维偶检验——水平垂直校验码，方阵码

(2)重复码——纠错码

如:c0=(00…0),c1=(11…1),R=1/n——低检错n-1位,纠错(n-1)/2位

(3)等比(重)码——检错码设计码字中的非0符号个数恒为常数，即C由全体重量恒等于m的n重向量组成。

5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。如：“5中取3”码，共有10种?H(X)=log210=3.32bit/码组(每码组5位)R=H(X)/n=0.664bit/码符号23分组码信息序列码字M=(mk-1…m0)C=(cn-1…c0){M}f(ּ){C}6.2线性分组码n>k24定义：如果一个（n，k）分组码的编码规则可用线性方程组表示，则称该码为（n，k）线性分组码。表示：(n,k) n:码/帧/组长 R=k/n:码率/编码效率特点线性特性——码组内监督码与信息码间为线性关系分组特性——每码组内的监督码只与本组信息码有关，与其他码组无关。监督码只用来监督本组中的信息位01221

cccccnnL--信息位监督位线性分组码25例.(7,3)线性分组码按以下校验方程求其所有码字？分析：26一、线性分组码的生成矩阵在由(n,k)线性码构成的线性空间Vn

的k维子空间中，一定存在k个线性独立的码字：gk-1,…,g1,g0,。码C中其它任何码字c都可以表为这k个码字的一种线性组合，即6.3线性分组码的生成矩阵和校验矩阵27G中每一行gi=(gi(n-1),…,gi1,gi0)都是一个码字；对每一个信息组m，由矩阵G都可以求得(n,k)线性码对应的码字，因此称矩阵G

为(n,k)线性码的生成矩阵。基底不唯一，生成矩阵也不唯一；不同的基底有可能生成同一码集，但不是同样的码（码集相同但映射方法不同）。(n,k)线性码的每一个码字都是生成矩阵G的行矢量的线性组合，所以它的2k个码字构成了由G的行张成的n维空间的一个k维子空间Vk。281.生成矩阵的标准形式通过行初等变换，将G化为前k列是单位子阵的标准形式，我们称之为生成矩阵的标准形式2.线性系统分组码用生成阵的标准形式产生的码集合称为线性系统分组码。29线性系统分组码：用标准生成矩阵Gk×n

编成的码字，前面k位为信息数字，后面r=n－k位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。系统码：每个码字的前k位（Cn-1Cn-2…Cn-k）与k位信息序列（mk-1…m1m0）依次对应相等，称为信息元，其后（n-k）位根据校验关系得到，添加于信息元之后，称为监督元或校验元。当生成矩阵G确定之后，(n,k)线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。信息码监督码Cn-1Cn-k

Cn-k-1C030

例.把例1中的校验方程改写成编码方程。矩阵形式?生成矩阵31

如果输入码组为M=011,编码器输出码字为:C=MG=？32二、线性分组码的监督矩阵⒈线性分组码的监督矩阵编码就是给已知信息码组按预定规则添加监督码元，以构成码字。在k个信息码元之后附加r(r=n－k)个监督码元，使每个监督元是其中某些信息元的模2和。举例：k=3,r=4，构成(7,3)线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”监督元可按下面方程组计算33一致监督方程/一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。由于一致监督方程是线性的，即监督元和新信源之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。34信息码组(101)，即C6=1,C5=0,C4=1代入监督方程得：C3=0,C2=0,C1=1,C0=1由信息码组(101)编出的码字为(1010011)。其它7个码字如下。35校验方程例.把例1中的校验方程改写成一般方程的形式。为了运算方便，将监督方程写成矩阵形式:36推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定

令上式的系数矩阵为H，码字行阵列为C同样有我们称H为一致监督阵/监督阵。37可以用来检验一个n重矢量是否为码字,若等式成立,必为码字,否则不是码字38⒉监督阵与生成阵的关系由于生成矩阵G的每一行都是一个码字，所以G的每行都满足Hr×nCTn×1=0Tr×1，则有Hr×nGTn×k=0Tr×k

或

Gk×nHTn×r=0k×r线性系统码的监督矩阵与生成矩阵正交。39⒊监督阵的标准形式同样对监督阵的各行进行初等变换，将右边r列化为单位阵即可得到监督阵的标准形式。上例中:40上述等式提供了监督阵与生成阵的互求。即，⒋监督阵与生成阵的转换关系由于系统码的监督阵与生成阵同样彼此正交，所以有：41例：425.(n,k)线性码的对偶码对偶码：对一个(n,k)线性码CI，由于Hr×nGTn×k=0Tr×k，如果以G作监督矩阵，而以H作生成矩阵，可构造另一个码CId，码CId是一个(n,n－k)线性码，称码CId为原码的对偶码。它们的码矢彼此正交，两个子空间是互为零化空间。例如：(7,4)线性码的对偶码是(7,3)码：(7,3)码的监督矩阵H(7,3)是(7,4)码生成矩阵G(7,4)

43

三、线性分组码的编码（n,k）线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n（n>k）的码字。上例编码器的实现44+++m3m2m1m0c6c5c3c4c2c1c0456.4一些特殊的线性分组码46线性码纠错能力与监督元数目的关系：一个可纠t个错误的线性码必须满足

不等式称为汉明限，任何一个纠t码都必须满足。上式中等式成立时的线性码称为完备码。即

伴随式的数目所有错误个数≤t的错误图样的个数完备码相当于在标准阵列中能将所有≤t的错误图样作为陪集首，而＞t的错误图样都不作为陪集首，其校验元得到最充分的利用。故完备码是最佳码47完备码并不多见，有汉明码（t=1,dmin=3）高莱码：（23，12）码（t=3,dmin=7）二进制码（n为奇数、由两个码字组成、满足dmin=n）三进制t=3的（11，6）码48一、汉明码⒈汉明码的特点汉明码是汉明在1950年提出的纠一位码的纠错码。对任意正整数m≥3给定后，即可构造一个(n,k)汉明码。⒉汉明码的参数与m的关系码长：n=2m-1信息位数：k=2m-m-1监督位数：n-k=m，H阵中每列有r个元素，至多可构成2r－1种互不相同的非0列。最小码距：dmin=3监督矩阵任意两列线性无关/H的任两列互不相同；没有全0的列。汉明码的对偶码：(2m-1,m)m的含义：非零m重（m行）作为列，共有n列构成H阵。49⒊汉明码H阵的构成非系统码：将非零m重列按二进制数依次排列。当发生可纠的单个错误时，伴随式为H阵中对应的列，所以伴随式的二进制数值就是错误位置号，有时这种码译码比较方便。线性系统码：将中去掉Im单位阵后剩下的

2m-m-1列作为Q子阵的任意排列。50二、汉明码的编码对于汉明码的编码可先定出m，然后求出相应的H阵（或G阵）最后得出它的编码电路。例：m=3，则n=23-1=7;k=2m-m-1=4;r=n-k=m(7,4)汉明码的H阵，G阵如下。51⒈由H阵得到的编码电路由化为方程组得：

由此得到：并行输出电路

∴串行输出电路

52⒉由G阵得到的编码电路由有：其电路图与H阵产生的电路一样⒊(n,k)线性码的编码原理同(7,4)汉明码的编码原理一样。53二、汉明码——能纠正单个错误的线性分组码汉明码的监督矩阵H的列为所有非零的r维向量组成，一旦r给定，就可以构造出具体的（n，k）汉明码。54例1：构造一个二元的（7，4，3）汉明码。分析：

r=n-k=3,除0以外的所有2r个元素构成矩阵H的列。55消息码字消息码字0000000000010001000011000100011111001100110000100010110101010101010011001100110111011010010001001011100110011001010101010110111010010110011001111101110000011101111001111111111156三、截短汉明码(n,k)－>(n-x,k-x)如(15,11)－>(12,8)

监督矩阵H’是将原H的前3列去掉截短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。57能纠t个错误的(n,k)应满足

取等号时为完备码不同结构的线性码其纠错能力不同，能力和dmin

有关，dmin

越大越好。58如果在汉明码基础上，再加上一位对所有码字进行校验的监督位监督码字由r位增加到r+1位信息位不变码长 码结构dmin=4纠1位错，检测2位错如（8，4），（16，11）四、扩展汉明码59扩展汉明码的监督矩阵60一、译码器的任务设：发送的码字C=(cn

-1，cn

-2，…，c1，c0)，通过有扰信道传输，信道产生的错误图样E=(en-1,en-2，…,e1,e0)。接收端译码器收到的n重码R=(rn

-1,rn-2,…,r1,r0)，其中R=C+E。译码器的任务：根据编码规则和信道特性，对接收码字R作出判决。此判决过程又称为译码。译码器按任务可分为：检错译码和纠错译码。检错译码：输出接收字r，及差错标志。纠错译码：输出纠正的码字（在纠错能力之内）输出接收字及出错标志。（超出纠错能力）

6.5伴随式与标准阵列译码61二、检纠错译码原理⒈

伴随式和错误检测

用监督矩阵编码，当然也用监督矩阵译码。接收到一个接收字R后，校验H

RT=0T是否成立：若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；伴随式/监督子/校验子：S=R

HT或ST=H

RT。

⒉不可检测的错误图样与码矢相同的错误图样是不可检测的错误图样。它在数量上与非零码矢一样多2k-1个（含零码为2k个)62根据上述原理，我们可知：⒊伴随式检错原理设：发送码字C＝(cn－1,cn－2,…,c0)，信道的错误图样为E＝(en－1,en－2,…,e0)，式中：若ei＝0，表示第i位无错，若ei＝1，则表示第i位有错，i＝n－1，n－2，…，0。那么，接收码字

R=(rn－1,rn－2,…,r0)=C＋E

=(cn－1+en－1，cn－2+en－2，…，c0+e0)检错译码基本原理判为无错（可能有错）一定出错63将接收字用监督矩阵进行检验，即求接收码字的伴随式。其中H阵用列来表示，即：所以：ST＝HRT＝H(C＋E)T＝HCT＋HET由于HCT＝

0T，则有：

ST＝HET

所以，64由上面分析得到如下结论：(1)伴随式仅与错误图样有关，只反映信道对码字造成怎样的干扰而与发送的具体码字无关，即伴随式仅由错误图样决定。(2)伴随式是错误的判别式：若S＝0，则判没有出错，（或存在一个不可检测的错误）接收字是一个码字，若S≠0，则判有错。(3)不同的错误图样具有不同的伴随式，它们是一一对应的，二元码伴随式是H阵中与错误码元对应列之和。65例：设(7,3)线性分组码的校验矩阵为试确定以下三种情况时的译码器的输出（1）接收码字R=(1010011)，（2）接收码字R=(1110011)，（3）接收码字R=(0011011)，66解：对于⑴有：传输过程中没有误码，设发送码矢C=1010011，接收码字R＝1010011，R与C相同。但接收端译码器并不知道就是发送的码字,它只能根据接收字R计算伴随式67对于⑵有：，第2位出错，若接收字中有一位错误设发送码矢C=1010011，接收码字=1110011，R与C第2位不相同。68由于sT≠0,译码器判断接收字有错(7,3)码是纠单个错误的码,且sT等于H的第2列,因此判定接收字R的第2位是错的由于接收字R中错误码元数与码的纠错能力相符,所以译码正确69对于⑶有：与中的任一列都不相同，不能确定到底是哪两位出错，不能正确译码。当码元错误多于1个时设发送码矢C=1010011，接收码字=0011011，R与C第1、4位不相同。70由于sT≠0,译码器判断接收字有错由于sT

是第1列与第4列的和，且sT与H的任何一列都不相同,无法判定错误出在哪些位上，只是发现有错。(7,3)码是纠单个错误的码,由于接收字R中错误码元数与码的纠错能力不相符,所以译码错误注意：这里告诉我们一个问题，纠错码的选用要小心，要根据信道条件来确定，如果信道较差，而使用的纠错码能力不够，可能使译码错误反而增加，不仅错误的码元没有纠正，原来正确的码元还被错误的改变。错上加错。71定理：可纠t个错的q元线性分组码满足：三、采用伴随式纠错译码的方法标准阵列法几个概念许用码组：在(n,k)线性码中，与2k个消息码对应的码字称为许用码组。禁用码组：在(n,k)线性码中，除了消息码外的2n-2k个码字72码矢参数发送码矢：取自于2k个码字集合{C}；接收矢量：可以是2n个n重中任一个矢量。译码方法把2n个n重矢量划分为2k个互不相交的子集，使得在每个子集中仅含一个码矢；根据码矢和子集间一一对应关系，若接收矢量Rl

落在子集Dl中，就把Rl

译为子集Dl含有的码字Cl；当接收矢量R与实际发送码矢在同一子集中时，译码就是正确的。标准阵列：是对给定的(n,k)线性码，将2n个n重划分为2k个子集的一种方法。73先将2k个码矢排成一行，作为标准阵列的第一行，并将全0码矢C1=(00…0)放在第一行的最左边的位置上；然后在剩下的(2n－2k)

个n重码中选取一个重量最轻的n重E2放在全0码矢C1下面，再将E2分别和码矢相加，放在对应码矢下面构成阵列第二行;在第二次剩下的n重码中，选取重量最轻的n重E3，放在E2下面，并将E3分别加到第一行各码矢上，得到第三行；直到全部n重用完为止。得到(n,k)线性码的标准阵列。（注意：作为错误图样的Ei不能与表内的其它码字相同）标准阵列的构造方法：74译码规则表子集m0m1m2…m2k-1许用码字C0(陪集首)C1C2C2k-1禁用码组┇┇┇┇75(n，k)线性码的标准阵列76（4，2）码及译码表信息组00100111码字0000100101111110有错码组10000100001000011101101111110011010101101010110077例：已知(6,3)线性分组码的生成阵为求它的标准阵列。解：由生成阵可得该码许用码组的全部码字：消息码线性分组码消息码线性分组码00000000010010011000100110110110101101001001111011010101101111011111100078则它的标准阵列为：00000000110101001101111010011010101111010111100000000100110001001001111110011110101011010011100100001000010000100001000010000010000100111100100100010101110110110110110001000101011101101100001111001111001001110001101001011000111011111011111110010010001010111011011000011000011110100110111110001111101101010100101011011111000111110110010100101101010011101011110011000010100001100001100179有关标准阵列的几个概念：(n，k)线性码的标准阵列有2k列(和码矢数相等)，2n/2k＝2n－k行，且任何两列和两行都没有相同的元素，即列和行都不相交。标准阵列的每一行叫做码的一个陪集，每个陪集的第一个元素叫做陪集首，信道干扰的错误图样是陪集首。2n－k个陪集首称为可纠正的错误图样。定理：(n,k)线性码可纠2n-k个错误图样。这2n－k个可纠的错误图样，包括

0码矢在内，也就是说，把无错的情况也看成一个可纠的错误图样。定理：在标准阵列中，一个陪集的所有2k个n重码字有相同的伴随式，不同陪集的伴随式互不相同。译码原理：收到的n重R落在某一列中，则译码器就译成相应于该列最上面的码字。

80每一列包含2n－k个元素，最上面的是一个码矢，其它元素是陪集首和该码矢之和，例如第j列为若发送码矢为Cj，信道干扰的错误图样是陪集首，则接收矢量R必在Dj

中；若错误图样不是陪集首，则接收矢量R不在Dj

中，则译成其它码字，造成错误译码；当且仅当错误图样为陪集首时，译码才是正确的。可纠正的错误图样：这2n－k个陪集首称为可纠正的错误图样81标准阵列译码=最小距离译码法=最佳译码法陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的n重作陪集首；这样，当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码矢间的距离（等于陪集首）最小；因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；所以标准阵列译码法也是最佳译码法。定理：在标准阵列中，一个陪集的所有2k个n重有相同的伴随式，不同的陪集伴随式互不相同。

82⒊采用伴随式译码的电路以(7，3)码为例，设接收码字R＝(r6,r5,r4,r3,r2,r1,r0)，那么伴随式为：8384码重(weight)一个码字中非0码元符号的个数，称为该码字的重量，又称为汉明重量。记为W(C)。二进制中为一个码组中“1”的数目.最小码重:线性分组码CI中，非0码字重量最小值，叫做码CI的最小重量：Wmin=min{W(V),V∈CI

,V≠0}6.5.2码距、纠错能力、MDC码及重量谱85码距/汉明距离(distance)在线性码中，两个长度相同的码字U、V

之间对应码元位上符号取值不同的个数，称为码字U、V

之间的汉明距离。二进制中为两个码组之间对应位置上1、0不同的位数。最小码距：在码集合中，任两个码字间的距离为最小时，该码距即为码集合的最小码距。记为d0或dmin。例: 10110码重：3 011002距离：3

例：(7,3)码的两个码字U=0011101,V=0100111，它们之间第2、3、4和6位不同。因此，码字U和V的距离为4。线性分组码的一个码字对应于n维线性空间中的一点，码字间的距离即为空间中两对应点的距离。86码集C={000,011,101,110},则码重w(c1)=0,w(c2)=2,w(c3)=2,w(c4)=2,

最小码重wmin(c)=2

码距d(c1;c2)=2,d(c1;c3)=2,d(c1;c4)=2,d(c2;c3)=2,d(c2;c4)=2,d(c3;c4)=2(计算6次)

最小码距dmin=2含2k个码字的码集需计算2k(2k-1)/2个距离后才能找出dmin87定理：（n，k）线性分组码的最小距离等于它的非零码字的最小重量。即：例题中,dmin=min{w(011),w(101),w(110)}=2最小码距与最小重量的关系：求最小距离---求最轻重量问题,含2k个码字的码集仅需计算2k次88

线性分组码的最小距离、检错和纠错能力汉明球：以码字C为中心，半径为t的汉明球是与C的汉明距离≤t的向量全体SC(t)89最小距离与检、纠错能力一般地说，线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。检错能力：如果一个线性码能检出长度≤ℓ个码元的任何错误图样，称码的检错能力为ℓ。纠错能力：如果线性码能纠正长度≤t个码元的任意错误图样，称码的纠错能力为t。90线性码的检纠错能力与最小码距的关系：

最小码距与检错能力的关系：定理：(n,k)线性码能够发现ℓ个错误的充要条件是码的最小距离为

dmin=ℓ+1或ℓ=dmin－1最小码距与纠错能力的关系：定理：(n,k)线性码能纠t个错误的充要条件是码的最小距离为

dmin=2t

+1或t

=(dmin－1)/2最小码距与检、纠错能力的关系：定理：(n,k)线性码能纠t个错误，并能发现ℓ个错误(ℓ>t)的充要条件是码的最小距离为

dmin=t+ℓ+1或t+ℓ=dmin－191最小码距与检错能力的关系：定理：(n,k)线性码能够发现ℓ个错误的充要条件是码的最小距离为

dmin=ℓ+1或ℓ=dmin－192最小码距与纠错能力的关系：定理：(n,k)线性码能纠t个错误的充要条件是码的最小距离为

dmin=2t

+1或t

=(dmin－1)/293最小码距与检、纠错能力的关系：定理：(n,k)线性码能纠t个错误，并能发现ℓ个错误(ℓ>t)的充要条件是码的最小距离为

dmin=t+ℓ+1或t+ℓ=dmin－19495线性码的最小距离与监督阵的关系：定理

1设H为(n,k)

线性码的一致监督阵，若H中任意S列线性无关，而存在S+1列线性相关，则码的最小距离为S+1。即:dmin=S+1(S为监督阵的秩)定理

2若码的最小距离为S+1，则该码的监督阵有

任意S列线性无关，而必存在线性相关的S+1

列推理1(n,k)

线性分组码，

dmin≤n-k+1。当等号成立时,(n,k)

线性分组码称为极大最小距离码。推理2在二元线性码的监督阵H中，如果任一列都不为全零，且任二列都不相等，则该码能纠一个错。例：96总体的、平均的纠错能力取决于码的最小距离，而且与其余码距或者说与码字的重量分布特性有关。当所有码距相等时（重量谱为线谱）码的性能最好，当各码距相差不大时（重量谱为窄谱）码的性能较好。同样的dmin条件下，窄谱的码比宽谱的码更优重量谱可以用重量算子表示：976.6循环码

循环码是线性分组码的一个重要子集.循环码有严密的代数学理论基础，检错和纠错能力较强，而且编码和解码设备都不太复杂.循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一许用码矢经过循环移位后，所得到的码矢仍然是许用码矢。一、循环码的多项式描述

⒈循环码的定义定义：如果(n,k)线性分组码的任意码矢C=(Cn－1,Cn－2,…,C0)的

i次循环移位，所得矢量C(i)=(Cn－1－i

,Cn－2－i,…,C0,Cn－1,…,Cn－i)

仍是一个码矢，则称此线性码为(n,k)循环码。98⒉循环码的多项式描述为了运算的方便，将码矢的各分量作为多项式的系数，设任意n维矢量C=（cn-1,cn-2,….,c1,c0），可以用一个次数不超过n-1的多项式唯一确定。把码矢表示成多项式，称为码多项式。其一般表示式为C(x)=(Cn－1xn－1+Cn－2xn－2+…+C1x

+C0)对于二进制码，码多项式的每个系数不是0就是1。x仅是码元位置的标记。我们并不关心x的取值。码多项式

i次循环移位的表示方法C(x)乘以x(i=1)，再除以(xn+1)，得模运算99上式表明：码矢循环一次的码多项式C(1)(x)是原码多项式C(x)乘以x除以(xn+1)的余式。记作：C(x)的

i

次循环移位C(i)(x)是C(x)乘以xi

除以(xn+1)的余式，即：结论：循环码的码矢的i次循环移位等效于将码多项式乘xi后再取模(xn+1)。100二、循环码的生成多项式和生成矩阵⒈循环码的生成阵在(n，k)循环码的2k个码多项式中，取前k-1位皆为

0的码多项式g(x)

(其次数r＝n-k)，再经k-1次循环移位，共得到k个码多项式：g(x),xg(x),…,xk－1g(x)。这k个码多项式显然是相互独立的，可作为码生成矩阵的k个行，于是得到(n，k)循环码的生成矩阵G(x)为：101码的生成矩阵一旦确定，码就确定了；这就说明：(n,k)循环码可由它的一个(n－k)次码多项式g(x)来确定；所以说g(x)生成了(n,k)循环码，因此称g(x)为码的生成多项式。定理1：(n,k)循环码C(x)中存在唯一的一个非零的，首一的和最低次为r(r=n-k)的码多项式满足：

并且c(x)是码式，当且仅当c(x)是g(x)的倍式定理2：g(x)是(n,k)循环码的生成多项式，当且仅当

g(x)是xn+1的r=n-k次因式。102结论：当求作一个(n,k)循环码时，只要分解多项式(xn+1)，从中取出(n－k)次因式作生成多项式即可。举例：求(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+1103若已知消息矢量，则由求得所有的码字：m2m1m0

由g1(x)产生的码字由g2(x)产生的码字0000000000000000000100101110011101010010111001110100110111001010011110010111001110100101100101111010011101110010100111011111001011010011104⒉循环码的监督阵设g(x)为(n,k)循环码的生成多项式，必为(xn+1)的因式，则有xn+1=h(x)

g(x)，式中h(x)为k次多项式，称为(n,k)循环码的监督多项式。由等式x7+1=h(x)

g(x)两端同次项系数相等得将上面的方程组写成矩阵形式有：105106由此可见，监督矩阵的第一行是码的监督多项式h(x)的系数的反序排列，第二、三、四行是第一行的移位；(n,k)循环码的监督矩阵h0=hk=1107例：已知(7,3)循环码的生成多项式为：g(x)=x4+x2+x+1，求该码的监督多项式及监督阵

解：由x7+1=g(x)h(x)得

h(x)=(x7+1)÷g(x)=x3+x+1,移动方向与g(x)移动方向相反升序排列1086.6.2循环码的编码和译码

一、系统循环码⒈循环码的标准阵定理：令C是一个(n,k)循环码，具有生成多项式g(x)。对i=0,1,…，k-1，，G2,i是长度为n的矢量，它的生成函数是G2,i(x)=xr+i+xr+imodg(x)。则k×n阶矩阵：是码C的一个生成矩阵。类似地，如果H2,j，是长度为r的矢量，它的监督函数是H2,j(x)=xjmodg(x)，则r×n阶矩阵：G,H的标准阵形式109是码C的一个一致校验矩阵。此外，如果矢量m=(mk-1,…,m1,m0)编码为C=mG2，则m(x)与C(x)的关系为：

C(x)=xrm(x)+[xrm(x)]modg(x)并且，如果矢量R=(Rn-1,…,R1,R0)的伴随式计算公式为ST=H2RT，则R(x)与S(x)的关系为：

S(x)=R(x)modg(x)⒉循环码的系统码由上述定理，即可得到循环码产生系统码的方法：C=mG2C(x)=xrm(x)+[xrm(x)]modg(x)将信息码移至最高位，且最低的次数为r次求xrm(x)的余数，且最高次数小于r,应为码字的监督元部分。110例：已知(7,3)循环码的g(x)=x4+x3+x2+1，试求其标准生成阵，一致校验阵及全部码字。解：⑴

由定理G2,i(x)=xr+i+xr+imodg(x)

得：X6+X6modg

X5+X5modgX4+X4modg100111001001110011101X6+X3+X2+X(r=4,i=2)X5+X2+X+1(r=4,i=2)X4+X3+X2+1(r=4,i=0)X6X5X4X3X2X1111⑵h(x)=(x7+1)÷g(x)=x3+x2+1，由定理

H2,j(x)=xjmodg(x)，得：X6modg=X3+X2+X(j=6)

X5modg=X2+X+1(j=5)X4modg=X3+X2+1(j=4)X3(j=3)X2X11110011111011000010000100001X3X2X1转置112⑶求全部码字：由定理得：

C(x)=xrm(x)+[xrm(x)]modg(x)m(x)=X2+X+1X4m(x)=X6+X5+X4[X4m(x)]modg=X2∴C(x)=

X6+X5+X4+X2C={1110100}m(x)=X2+1X4m(x)=X6+X4[X4m(x)]modg=X+1∴C(x)=

X6+X4+X+1C={1010011}消息码C1码C2=mG211111101001110100三行矢模二加10110100111010011000011100110001010011101000000001101001110100101110101001110100111001001110100111000000000111010011101113二、多项式运算电路多项式加法运算多项式乘单项式多项式乘多项式多项式求模g(x)运算(除法电路，即求余数)移位寄存器的级数=除式的次数移位寄存器的反馈抽头，由除式的各项系数定gi(x