分组码

第八章线性分组码第八章线性分组码内容提要目前，几乎所有得到实际应用的纠错码都是线性的。本章首先介绍有关纠错码的基本概念，然后重点论述线性分组码的定义及其编译码理论。在此基础上，介绍了一种典型的线性分组码：汉明码。8.1纠错码的基本概念8.1.1信道纠错编码l信源编码的目的是压缩冗余度，提高信息的传输速率。l信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术——纠错编码技术。这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。8.1.2差错控制系统模型及分类为了方便研究，将信息传输系统模型简化成图8.1所示的简化模型图8.1简化的信息传输系统模型模型突出了以控制差错为目的的纠错码编码器和译码器，因此也称为差错控制系统。在差错控制系统中使用的码按其纠错能力的不同可分为两种：检错码和纠错码。能发现错误但不能纠正错误的码称为检错码；不仅能发现错误而且还能纠正错误的码称为纠错码。（１）前向纠错(FEC)方式：FEC(ForwardErrorControl)方式是发端发送有纠错能力的码（纠错码），接收端收到这些码后，通过纠错译码器自动地纠正传输中的错误。差错控制系统大致可分为前向纠错、重传反馈和混合纠错等三种方式。l优点是不需要反馈信道；能进行一个用户对多个用户的同时通信，特别适合于移动通信；译码实时性较好，控制电路也比较简单。l缺点是译码设备较复杂；编码效率较低。（２）重传反馈(ARQ)方式:ARQ(AutomaticRepeatRequest)方式是：发端发出能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。l优点是译码设备简单，在多余度一定的情况下，码的检错能力比纠错能力要高得多，因而整个系统能获得极低的误码率。l应用ARQ方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时性也较差。（３）混合纠错(HEC)方式：HEC(HybridErrorControl)方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了FEC方式译码设备复杂和ARQ方式信息连贯性差的缺点。在设计差错控制系统时，选择何种实现方式，应综合考虑各方面的因素。主要有：⑴满足用户对误码率的要求；⑵有尽可能高的信息传输速率；(4)可接受的成本。⑶有尽可能简单的编译码算法且易于实现；8.1.3纠错码的分类常用的纠错码按其码字结构形式和对信息序列处理方式的不同可分成两大类：分组码和卷积码。分组码是把信息序列以每k个码元分组，编码器将每个信息组按一定规律产生r个多余的码元（称为校验元），形成一个长为n=k+r的码字。卷积码是把信息序列以每k个分组，通过编码器输出长为n（nk）的一个子码。但是该子码的n－k个校验元不仅与本子码的信息元有关，而且也与其前m个子码的信息元有关。8.1.4差错类型讨论码字序列c通过离散信道时发生的情况，信道分为无记忆信道和有记忆信道。l在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一个差错的出现与其前后是否有错无关,如图8.2。在无记忆信道中，错误是随机产生的，因此被称作随机错误，无记忆信道也被称为随机信道（randomchannel）。图8.2二进制对称信道l有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、成串地出现，表现出错误之间有相关性。图8.3就是这种信道的一个模型。图8.3有记忆信道模型就实际信道而言，由于其干扰的复杂性，往往是两种错误并存。随机错误与突发错误并存的信道，称为组合信道或复合信道。表8.1给出了一个（7，3）线性分组码的例子。该例子中，信息组为（c6c5c4），码字为（c6c5c4c3c2c1c0）。当已知信息组时，按以下规则得到四个校验元：（8－3）这组方程称为校验方程。8.2线性分组码的编码8.2.1生成矩阵4505614562463ccccccccccccc信息组码字00000000000010011101010010011101101110101001001110101101001111011010011111110100表8.1（7，3）线性分组码（7，3）线性分组码有23＝８个许用码字或合法码字，另有27－23个禁用码字。发方发送的是许用码字，若收方收到的是禁用码字，则说明传输中发生了错误。为了深化对线性分组码的理论分析，与线性空间联系起来。将（n，k）线性分组码的定义如下：定义8.12k个n重的集合C称为线性分组码，当且仅当它是n维线性空间Vn中的一个k维子空间。（n，k）线性分组码的2k个码字组成了n维线性空间Vn的一个k维子空间，因此这2k个码字完全可由k个线性无关的矢量所组成的基底所张成。设此k个矢量为c1，c2，…，ck:c1＝（g1,n-1，g1,n-2，…，g1,0）c2＝（g2,n-1，g2,n-2，…，g2.0）ck＝（gk,n-1，gk,n-2，…，gk,0）（n，k）码中的任一码字ci，均可由这组基底的线性组合生成：(8－5)0,2,1,0,22,21,20,12,11,121knknknnnnknnniigggggggggmmmGmc定义8.2若信息组以不变的形式，在码字的任意k位中出现的码，称为系统码；否则，称为非系统码。写成矩阵形式：(8－4)0,2,1,0,22,21,20,12,11,1knknknnnngggggggggk21cccG8.2.2校验矩阵表8.1所示（7，3）线性分组码的四个校验元是由(8－3)式所示的线性方程组决定的。把(8－3)式移项：上式写成矩阵形式得00000451562456346ccccccccccccc000010001100100011001011100011010123456ccccccc这里的四行七列矩阵称为（7，3）码的一致校验矩阵，简称校验矩阵，用H表示：1000110010001100101110001101H由H矩阵得到的（n，k）线性分组码的每一码字ci，（i＝1，2，…，2k），都必须满足由H矩阵各行所确定的线性方程组，即ci·HT＝0(8－8)或H·ciT＝0T(8－9)又，（n，k）线性分组码的生成矩阵G中的每一行及其线性组合都是（n，k）码的码字，所以有G·HT＝0(8－10)或H·GT＝0T(8－11)8.2.3编码的实现设码的G矩阵为0,2,1,0,22,21,20,12,11,1kknkknkknknknknkpppppppppIG当信息组m＝（mn-1mn-2…mn-k）时，相应的码字c是c＝m·G＝（cn-1cn-2…c1c0）cj＝mn-1p1,j+mn-2p2,j+…+mn-kpk,j0jn－kcj＝mjn－kjn－1其中图8.4（n，k）线性分组码编码电路编码实现电路如图8.4所示。电路由移位寄存器、模二加法器和模二乘法器组成根据图8.4的电路，可画出（7，3）线性分组码的编码器电路，如图8.5。图8.5（7,3）线性分组码编码电路8.3伴随式与译码8.3.1码的距离和重量定义8.5一个码的最小距离dmin定义为(8－13)),(,,),,(minminknjiddjijicccc定义8.4码字中非零码元的个数，称为该码字的汉明重量，简称重量，用w（c）表示。定义8.3两个码字之间，对应位取值不同的个数，称为它们之间的汉明距离，简称距离，用d（c1，c2）表示。码的距离和重量满足以下不等d（c1，c2）d（c1，c3）＋d（c3，c2）(8－14)w（c1＋c2）w（c1）＋w（c2）(8－15)定理8.1线性分组码的最小距离等于其非零码字的最小重量。根据定理，要得到码的最小距离，只要检查2k－1个非零码字的重量即可。事实上，两个码字之间的距离表示了它们之间差别的大小。因此，一个线性分组码的最小距离是衡量码抗干扰能力的重要参数。码的最小距离愈大，其抗干扰能力愈强。8.3.2线性码的纠检错能力以上定理是纠错码理论中最重要的基本定理之一，它说明了一个距离为d的线性分组码，既可用来纠正个错误，又可用来检测ed－1个错误。21dt定理8.2对于任一个（n，k）线性分组码，若要在码字内⑴检测e个错误，则要求码的最小距离de＋1；⑵纠正t个错误，则要求码的最小距离d2t＋1；⑶纠正t个错误同时检测e（t）个错误，则要求dt＋e＋1。定理8.3（n，k）线性分组码有最小距离为d的充要条件，是H矩阵中任意d－1列线性无关。推论8.1（n，k）线性分组码的最大的，可能的最小距离等于n－k＋1。由此定理可知，所有列相同，但排列位置不同的各种H矩阵所对应的不同（n，k）线性分组码，都有相同的最小距离，即它们在纠错能力和码率上是完全等价的。8.3.3陪集分解与伴随式由于信道中噪声的影响，y序列中的某些码元可能与c序列中对应码元的值不同，有y＝c＋e(8－16)称e为信道的错误图样。（n，k）码的任一码字，均满足(8－8)式或(8－9)式，因此，可以将接收码字y用二式中之任一式进行检验：(8－17)TTTTTHHHHHeececy)(令s=y.HT=e.HT(8－18)称为接收序列的伴随式或校正子。当s≠0时，译码器要做的就是如何从伴随式s中找到错误图样，从而译出发送的码字。8.3.4标准阵列与译码表（n，k）码的2k个码字是n维线性空间Vn中的一个k维子空间。将Vn中的全部n重划分成若干个陪集，具体做法可通过建造码的标准阵列来实现（如表8.3）：l第三行是再从其余的n重中选择一个e3作为首位元素,同理将e3＋ci置于ci的下面完成第三行；……依此类推，一直到将全部n重用完为止。l在余下的2n－2k个n重中，选择一个n重e2作为第二行的首位元素，于是第二行的元素是e2和每个码字ci（i＝1，2，…，2k）相加；l先把子群中的全部2k个码字c1，c2，…，置于表的第一行；许用码字e1＝c1（陪集首）c2c3…禁用码字e2e3e2＋c2e3＋c2＋c2e2＋c3e3＋c3＋c3e2＋e3＋＋kne2kne2kne2kc2kc2kc2kc2kne2表8.3线性分组码的标准阵列表8.3称作（n，k）线性分组码的标准阵列，这是一个2n－k行、2k列的阵列。表中每列元素组成一个子集。表中每一行称为一个陪集，每一行的首位元素ej（j＝1，2，…，2n-k）称作陪集首。⑶对于同一列的各子集来说，其中2n-k个n重的错误图样虽然不同，但全都对应于同一个许用码字。k221,,,φφφ利用标准阵列的性质可以进行译码：当输入译码器的接收序列为y，查表确定y落在标准阵列的第j行第i列，译码器就判定发送码字是第i列（即子集）所对应的许用码字ci，错误图样就是第j行所在陪集的陪集首ej。iφ标准阵列具有以下性质：⑴如果把陪集首看成是错误图样，则每一个陪集中各n重具有相同的错误图样；⑵每一个陪集中的2k个n重都有相同的伴随式，而不同的陪集具有不同的伴随式；译码正确的概率大小与陪集首的