第七章 线性分组码

第七章线性分组码1第1页，课件共61页，创作于2023年2月内容提要

目前，几乎所有得到实际应用的纠错码都是线性的。本章首先介绍有关纠错码的基本概念，然后重点论述线性分组码的定义及其编译码理论。在此基础上，介绍了一种典型的线性分组码：汉明码。掌握内容：线性分组码的概念，生成矩阵，校验矩阵，最小距离，伴随式，标准阵列等。2第2页，课件共61页，创作于2023年2月§7.1纠错编码的基本概念一．信道纠错编码

近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者面临的重要课题。香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术——纠错编码技术。这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。信源编码的目的是压缩冗余度，提高信息的传输速率。信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。3第3页，课件共61页，创作于2023年2月二．差错控制系统模型及分类

1．差错控制系统模型模型突出了以控制差错为目的的纠错码编、译码器，因此也称为差错控制系统。2．差错控制系统的分类按其纠错能力的不同可分为两种：检错码和纠错码。

⑴检错码：能发现错误但不能纠正错误的码；⑵纠错码：不仅能发现错误而且还能纠正错误的码。

4第4页，课件共61页，创作于2023年2月按差错控制系统类型，可分为前向纠错、重传反馈和混合纠错等三种方式。

⑴前向纠错(FEC)方式：FEC(ForwardErrorControl)方式是发端发送有纠错能力的码（纠错码），接收端收到这些码后，通过纠错译码器自动地纠正传输中的错误。

优点：是不需要反馈信道；能进行一个用户对多个用户的同时通信，特别适合于移动通信；译码实时性较好，控制电路也比较简单。缺点：是译码设备较复杂；编码效率较低。⑵重传反馈(ARQ)方式:ARQ(AutomaticRepeatRequest)方式是：发端发出能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。5第5页，课件共61页，创作于2023年2月优点：译码设备简单，在多余度一定的情况下，码的检错能力比纠错能力要高得多，因而整个系统能获得极低的误码率。缺点：应用ARQ方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时性也较差。⑶混合纠错(HEC)方式：

HEC(HybridErrorControl)方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了FEC方式译码设备复杂和ARQ方式信息连贯性差的缺点。

6第6页，课件共61页，创作于2023年2月

在设计差错控制系统时，选择何种实现方式，应综合考虑各方面的因素。主要有：⑴满足用户对误码率的要求；⑵有尽可能高的信息传输速率；⑶有尽可能简单的编译码算法且易于实现；(4)可接受的成本。三．纠错码的分类

常用的纠错码按其码字结构形式和对信息序列处理方式的不同可分成两大类：分组码和卷积码。

7第7页，课件共61页，创作于2023年2月分组码：把信息序列以每k个码元分组，编码器将每个信息组按一定规律产生r个多余的码元（称为校验元），形成一个长为n=k+r的码字。对于k个码元分组，共有2k个不同的信息组，编码器输出长n的2k个码字，这2k个长为n的码字构成的集合称为一个（n，k）分组码。n：码长；k：信息位的数目；R=k/n：分组码码率。

卷积码：把信息序列以每k个分组，通过编码器输出长为n（n

k）的一个子码。但是该子码的n－k个校验元不仅与本子码的信息元有关，而且也与其前m个子码的信息元有关。8第8页，课件共61页，创作于2023年2月四．差错类型

讨论码字序列通过离散信道时发生的情况，信道分为无记忆信道和有记忆信道。在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一个差错的出现与其前后是否有错无关，如图所示。在无记忆信道中，错误是随机产生的，因此被称作随机错误，无记忆信道也被称为随机信道（randomchannel）。

9第9页，课件共61页，创作于2023年2月有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、成串地出现，表现出错误之间有相关性，称为突发错误。下图就是这种信道的一个模型。

就实际信道而言，由于其干扰的复杂性，往往是两种错误并存。随机错误与突发错误并存的信道，称为组合信道或复合信道。

10第10页，课件共61页，创作于2023年2月§7.2分组码及检、纠错能力的获得

一．分组码定义

设消息或数据以二进制形式表示，并以F2={0,1}表示这个二元集。消息集：

序列个数：2k

设长为n的二元码元序列集为：

序列个数：2n≥2k

设消息集是长为k的二元消息序列集，表示如下：11第11页，课件共61页，创作于2023年2月1．分组编码：在长为n的二元序列集中选出与消息序列数2k相同数目的码元序列，并使两者一一对应。

几个概念：码字：对应于消息的长n的2k个码元序列，用表示。选出的2k个码元序列称为许用码组，另外的2n-2k个为禁用码组。

码：所有码字的集合，用C表示。

字：所有长为n的二元序列。

消息：长为k的二元码元序列，用表示。

12第12页，课件共61页，创作于2023年2月2．消息与码字的映射关系（函数关系）

线性分组码：与呈线性关系（fi为线性函数）

非线性分组码：与呈线性关系（fi为线性函数）

对于消息为k位，码长为n的线性分组码称（n，k）线性分组码。

13第13页，课件共61页，创作于2023年2月【例】一个原始数字消息u0

编码规则：

k=1，故为（n，1）码，称（n，1）重复码。码率：R=1/n

【例】编码规则

构成一个（n，n-1）线性分组码：R=(n-1)/n

（加法为模2加）

14第14页，课件共61页，创作于2023年2月由最后一个方程：

（奇）偶校验码：码字中1的个数为偶数。

在接收到一个字中1的个数不是偶数时，就可以确定接收的不是码字。这种码能检出奇数个错误，但不能发现偶数个错误。比较上面两例编码方案：①重复码：R=1/n，编码效率最低，检纠错能力最高。②奇偶校验码：R=(n-1)/n，编码效率最高，检纠错能力最低。（两个极端）

3．纠错编码理论的中心任务：在重复码和奇偶校验码之间寻找一些性能良好的码，使编码效率和检、纠错能力得到统一。

15第15页，课件共61页，创作于2023年2月二．分组码检、纠错能力的获得【例】（2，1）重复码（2，1）重复码可以检出一个错误，但错误不能纠正。

16第16页，课件共61页，创作于2023年2月（3，1）重复码

（3，1）重复码可以检出最多不超过两个错误，能纠正一个错误，但不能检出3个错误。

17第17页，课件共61页，创作于2023年2月三．错误图样对应着n为码字，长为n的二元序列

当ei=1时，表明码字中第i位ci发生错误；当ei=0时，表明码字中第i位ci没有错误。

称为错误图样。

中“1”的个数表示产生错误的个数，称错误图样的错误重数（t）。

设为码字在传输过程中发生错误而得到的接收字，则

18第18页，课件共61页，创作于2023年2月【例】（2，1）重复码

（3，1）重复码19第19页，课件共61页，创作于2023年2月§7.3汉明距离和分组码的检、纠错能力

一．汉明距离1．定义：设是集合Vn（F2）（n维向量空间）中的任意两个字，令

ai，bi取自G(F2)(0，1)

规定表示字的各对应码元之间不相同的个数，则

称为之间的汉明距离，简称距离。

20第20页，课件共61页，创作于2023年2月例如：

说明：

①收到接收字后，通过计算与各码字之间的汉明距离，如与某一码字的汉明距离最小，则与码字最像，译码器将译成。②极大似然译码基础：收到的字是从一个码字经错传尽可能少的位而来的可能性较从一个码字经错传较多的位而来的可能性要大。故通过判断汉明距离来译码，符合极大似然译码规则。如：pe＝10-5，则错一位的概率：pe＝10-5，错两位的概率：pe＝10-1021第21页，课件共61页，创作于2023年2月【例】有码字

如接收字：

判断该接收字最有可能的码字。

2．汉明距离的性质①自反性：

②对称性：

③三角不等式：

22第22页，课件共61页，创作于2023年2月二．分组码的检、纠错能力与最小汉明距离之间的关系1．码的最小距离码C中不同码字之间距离的最小值称码C的最小距离。

dmin是衡量码的检、纠错能力的一个重要的参数。2．码的检、纠错能力与dmin的关系①若dmin≥t+1，则码C可以检出所有不多于t重的错误；

23第23页，课件共61页，创作于2023年2月②若dmin≥2t+1，则码C可以纠正所有不多于t重的错误；

③若dmin≥2t1

+t2+1，则码C可以纠正所有不多于t1重的错误，并能检出所有的从（t1+1）到（t1+t2）重的错误。

24第24页，课件共61页，创作于2023年2月§7.4线性分组码及其矩阵描述

一．基本概念1．线性空间定义：如果域F上的n重元素集合V满足下述条件时，

①V关于加法构成阿贝尔群；

②对V中任何元素和F中的任何元素a，，称V中元素为矢量（向量），F中元素a称纯量（标量），称乘a运算为数乘。

③分配律成立：④若

有

则称V是域F上的一个n维线性空间（矢量空间），表示为：Vn（F）

25第25页，课件共61页，创作于2023年2月2．子空间

线性空间Vn(F)中矢量的所有线性组合所构成的集合S是Vn(F)的子空间。

3．线性相关和线性无关设是线性空间Vn(F)中的一组非全零矢量，当且仅当存在有一组不全为零的纯量，使

成立时，称这组矢量线性相关，否则，称这组矢量线性无关（线性独立）。

即：若

线性无关，若等式成立，必有

26第26页，课件共61页，创作于2023年2月如：（1）

则

故线性无关。

（2）

故线性无关。

则

线性相关的充要条件：在线性空间中，对于矢量存在着一个矢量，它可以表示为其余矢量的线性组合。27第27页，课件共61页，创作于2023年2月4．矢量空间（线性空间）的基底如果存在一组线性无关的矢量，这些矢量的线性组合的集合可以构成一个矢量空间，则称这组矢量为这个矢量空间的基底。

n维矢量空间包含n个基底，也可以说，n个基底“张成”n维矢量空间。如果是n维矢量空间Vn(F)中k个线性无关的矢量，则这些矢量线性组合的集合可构成Vn(F)的一个子空间，这k个矢量为子空间的基底。

结论：（n，k）线性分组码可由k个线性独立的码字组成的基底张成。

码矢量：由（n，k）线性分组码的每个码字构成的矢量（码字）字矢量：n维线性空间任一个字构成的矢量。28第28页，课件共61页，创作于2023年2月二．线性分组码的矩阵描述1．定义：（线性分组码的模型）设Vn(F2)是定义在F2上的一个n维的矢量空间，而C是它的一个k维的子空间，则称C是码长为n，消息位为k的线性分组码或（n，k）线性分组码。【例】（6，3）分组码C

编码规则：

用矩阵表示：

组成矩阵的三个6维的行矢量是线性无关的，它构成了V6(F2)上的一个3维子空间，故C是（6，3）线性分组码。29第29页，课件共61页，创作于2023年2月2．线性分组码的矩阵描述：设

是（n，k）线性分组码中k个线性无关的非零码字，

则（n，k）线性分组码2k个码字中的任一码字可表示为用矩阵表示：：长为k的序列，构成2k个不同的消息。

生成矩阵

30第30页，课件共61页，创作于2023年2月【例】（7，3）线性分组码，k=3，2k=8（消息）则：

如：

31第31页，课件共61页，创作于2023年2月3．系统码：信息位以不变的形式在码组中出现的码称为系统码（出现的位置一般在前面）。如：前例（7，3）线性分组码一般性结论：（1）每一个线性分组码都有一个与之等价的系统码存在；（2）（n，k）线性分组码系统码的生成矩阵是一个k×k的单位阵[Ik]和一个k×(n-k)矩阵[Pk×n-k]组合而成的。（3）与非系统码相比，系统码编码过程及所需设备可以简化。32第32页，课件共61页，创作于2023年2月4．生成矩阵的性质（1）如果G是一个生成矩阵，那么与G行等价的任一矩阵也是生成矩阵。

初等行变换：任意两行交换；将任一行加到另一行；将任一行同乘一个数。

【例】（6，3）线性分组码对G作初等行变换：33第33页，课件共61页，创作于2023年2月（2）每个线性分组码都有唯一的梯形生成矩阵（3）一个矢量空间的基底不止一个，G不唯一，各个G编出的码相同，但各消息对应的码字不同。

三．线性分组码的校验矩阵1．校验矩阵【例】（6，3）线性分组码在码字中c0、c1、c2是信息位，c3、c4、c5是冗余位（校验位）

34第34页，课件共61页，创作于2023年2月由校验位方程得：用矩阵表示即

（H为n－k行n列的矩阵）

35第35页，课件共61页，创作于2023年2月【例】（1）（n，1）重复码，k＝1

（2）（n，n-1）奇偶校验码

36第36页，课件共61页，创作于2023年2月结论：一般的（n，k）线性分组码C总可以从该码的编码规则中选出（n-k）个独立校验位方程，如将它们写成齐次线性方程的形式，则它们可以用矩阵表示为：

简记为：

（H(n－k)×n为线性分组码的校验矩阵）。

说明：（1）矩阵H的n-k个行矢量是线性独立的，它们组成了Vn（F2）上的一个n-k维的子空间。（2）

H的行空间与G的行空间是相互正交的（对偶的）。

37第37页，课件共61页，创作于2023年2月2．对偶码生成矩阵G的k行矢量组成Vn(F2)的k维子空间（码字空间C）；校验矩阵H的n-k个行矢量组成Vn(F2)的n-k维的子空间(C的对偶子空间C⊥)。

对偶码定义：C⊥是Vn（F2）的一个子空间，它的维数维n-k，因此可以把C⊥看作是一个二元（n，n-k）线性分组码，并把它称为C的对偶码。

结论：设C是（n，k）线性分组码，其生成矩阵维G，那么码C的对偶码C⊥的生成矩阵H就是码C的校验矩阵。3．线性分组码的译码问题由于生成矩阵和校验矩阵的行空间是对偶的，因此我们可以利用这种对偶特性来判断接收到的任一矢量是否为码矢量，这在原则上提供了一种解决线性分组码的译码问题的途径。

的充要条件是：

即：

38第38页，课件共61页，创作于2023年2月4．生成矩阵G与校验矩阵H的梯形矩阵的关系（1）每个线性分组码的生成矩阵存在唯一的k×n的梯形矩阵；（2）每个线性分组码的校验矩阵存在唯一的(n-k)×n的梯形矩阵；（3）如G有[Ik

P]的形式，则H有[PT

In-k]的形式（条件：在F2中）。

【例】

39第39页，课件共61页，创作于2023年2月§7.5线性分组码的检、纠错能力

一．码字重量1．定义

设，令为码字中不为零码元的个数，即

称为码字的汉明重量，简称重量。

2．最小重量：码C中非零码字重量的最小值

40第40页，课件共61页，创作于2023年2月3．任一码字的重量都可以看作是该码字与0码字之间的汉明距离

4．定理：任一线性分组码的最小距离等于它的最小重量。

证明：

由于C是线性码，故，即线性分组码中任意两个码矢量间的距离等于另一个码矢的重量，即

故

41第41页，课件共61页，创作于2023年2月二．线性分组码的检、纠错能力与H矩阵的关系定理：设C是线性分组码，H是它的校验矩阵，那么码C的最小重量就等于H中线性相关的最小列数。因此，如果H中的2t个和小于2t个列的任一子集都线性无关，而H中有2t+1个列线性相关，那么码C就是纠正t个错误的纠错码，或能检出2t个错误的检错码。【例】（7，4）线性分组码

线性相关的最小列数为3

故：wmin(C)=3

推论：如果H的任意小于等于t个列的线性组合都不相同，那么wmin(C)≥2t+1，即C是能纠正重数小于等于t的纠错码。42第42页，课件共61页，创作于2023年2月§7.6群及其性质

一．群的概念定义：设G是非空集合，在G中规定一种运算“*”，，即运算*在G中是封闭的。

同时要求：（2）

，对一切的

，使a*e=a，e为恒元；

（1）

，有

结合律；

（3）

，有a*a-1=e，存在逆元a-1。

，若以上条件均满足，称G对于“*”运算是一个群。交换群（阿贝尔群）：a*b=b*a(满足交换律)加法群：运算“*”为加法运算。e：零元素乘法群：运算“*”为乘法运算。e：单位元有限群：G中只含有有限个元，元的个数称群的阶。

43第43页，课件共61页，创作于2023年2月二．子群和陪集展开1．子群：设G是一个群，而G0是G的一个非空子集，若G0在G规定的运算下满足群的条件，则G0是G的子群。

2．群按子群展开（陪集展开）设加群G的子群

展开步骤：

（1）把H的元依次排在第一行；（2）取不属于H的G中的任一元，记为g1，将它与H中的元依次相加，结果记为，并依次排在第二行；

（3）再取不属于H又不属于g1+H的G中的任一元g2，将它与H中的元依次相加，结果记为，并依次排在第三行；

（4）按步骤继续下去，直到排完G中所有的元。

44第44页，课件共61页，创作于2023年2月Hh1=eh2...hrg1+Hg1g1+h2...g1+hrg2+Hg2g2+h2...g2+hr...gn+Hgngn+h2...gn+hr把叫做H的一个陪集。而g称为该陪集的一个代表元或陪集首（e，g1，g2，...，gn）。45第45页，课件共61页，创作于2023年2月【例】V4（F2）的模2加群：子群H={0000，0101，1110，1011}，陪集展开。H00000101111010110110＋H01100011100011011111＋H11111010000101000010＋H0010011111001001结论：（1）G的每一个仅在子群H的一个陪集中（2）设G是个交换群，H是它的一个子群，那么G可以唯一地表示为H的一些两两没有公共元的陪集的并。

46第46页，课件共61页，创作于2023年2月§7.7线性码的伴随式译码和标准阵列一．群码1．定义：所有构成群的码称为群码。

2．定理：二元分组码对于码字的模2加法成群的充要条件：码是线性的。

二．伴随式1．伴随式（校验子）对任一错误图样，接受字可表示为：

由于

是码字，

，故

称为接收字的伴随式或校验子，它是一个n-k维的行矢量。47第47页，课件共61页，创作于2023年2月2．定理：任意两个长n的二元矢量，如果对群码C的校验矩阵有相同的伴随式，即，那么属同一个陪集（有相同的陪集首）。三．标准阵列：在全部长为n的二元序列按线性码C的陪集展开中，陪集首可以用该陪集中的任意序列担任，而不会改变此陪集的元，只是他们的排列次序有所变动。

标准阵列：全体长n的二元序列按线性码C的以陪集中最小重量的字作为陪集首的陪集展开就称为C的标准阵列。

48第48页，课件共61页，创作于2023年2月【例】（4，2）线性码C={0000，0101，1110，1011}，其标准阵列为

码字伴随式0000010111101011100010011111001001010100000110101111111000110101100011其校验矩阵为

，计算其伴随式，如表。

说明：对于（4，2）线性码，码字的最小重量为2，可以纠正一个错误，实际上按标准阵列展开的陪集为码字错误图样为陪集首的接收字，由于可以纠正一个错误，因此译码时对单个错误可以正确译码。49第49页，课件共61页，创作于2023年2月四．伴随式译码

1．标准阵列法：

按标准阵列的陪集展开实际上就构成了线性码的译码表，因此完全可以通过标准阵列来译码。其中，陪集首就是线性码可以纠错的错误图样。2．伴随式译码（1）原理：对于码C的同一陪集，有相同的伴随式和陪集首(错误图样），因此，只要知道伴随式与陪集首的对应关系，通过计算接收字的伴随式，就可以知道错误图样，从而进行译码。

（2）方法：计算接收字的伴随式：；根据算得得伴随式找到对应的陪集首（错误图样）；根据错误图样译码并输出码字：

（3）优点：不用记住整张译码表（标准阵列），只需记住伴随式与陪集首相对应的表。

50第50页，课件共61页，创作于2023年2月【例】（7，3）线性分组码

能检出3重错误，纠正1重错误。

51第51页，课件共61页，创作于2023年2月如：（一个错）如两个错：

，但无伴随式与之对应，不能纠正。

52第52页，课件共61页，创作于2023年2月§7.7汉明码

一．基本概念汉明码：一类能纠单个错误的纠错码。

二．纠单个错误的线性分组码【例】（7，4）线性码

53第53页，课件共61页，创作于2023年2月（1）H中列为非全零元素；

（2）H中任意两列都不相同，但存在相加等于0的三个列的子集。

H中线性相关的最小列数为3，故，该码是纠单个错误的码。定理：C是一个线性分组码，H是校验矩阵，C是可以纠单个错误的纠错码的充要条件：（1）H中没有元素全为0的列矢量；（