第八章线性分组码课件

第八章 线性分组码第八章 1第八章第八章 线性分组码线性分组码内容提要内容提要目前，几乎所有得到实际应用的纠错码都是线目前，几乎所有得到实际应用的纠错码都是线性的。本章首先介绍有关纠错码的基本概念，性的。本章首先介绍有关纠错码的基本概念，然后重点论述线性分组码的定义及其编译码理然后重点论述线性分组码的定义及其编译码理论。在此基础上，介绍了一种典型的线性分组论。在此基础上，介绍了一种典型的线性分组码：汉明码。码：汉明码。第八章 线性分组码内容提要28.1 8.1 纠错码的基本概念的基本概念 8.1.1 信道纠错编码信道纠错编码 l l信源编码的目的是压缩冗余度，提高信息的传输速率。信源编码的目的是压缩冗余度，提高信息的传输速率。l l信道编码的目的是提高信息传输时的抗干扰能力以增信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。加信息传输的可靠性。香香农农第第二二定定理理指指出出，当当信信息息传传输输速速率率低低于于信信道道容容量量时时，通通过过某某种种编编译译码码方方法法，就就能能使使错错误误概概率率为为任任意意小小。目目前前已已有有了了许许多多有有效效的的编编译译码码方方法法，并并形形成成了了一一门门新新的的技术技术纠错编码技术。纠错编码技术。纠纠错错编编码码即即信信道道编编码码，与与信信源源编编码码一一样样都都是是一一种种编码，但两者的作用是完全不同的。编码，但两者的作用是完全不同的。8.1 纠错码的基本概念 8.1.1 信道纠错编码 l信38.1.2 差错控制系统模型及分类差错控制系统模型及分类 信息传输系统模型简化成图信息传输系统模型简化成图8.1所示的简化模型所示的简化模型图图8.1 8.1 简化的信息传输系统模型简化的信息传输系统模型 模模型型突突出出了了以以控控制制差差错错为为目目的的的的纠纠错错码码编编码码器器和和译译码码器器，因此也称为差错控制系统。因此也称为差错控制系统。8.1.2 差错控制系统模型及分类 信息传输系统模型简化成图4在在差差错错控控制制系系统统中中使使用用的的码码按按其其纠纠错错能能力力的的不不同同可可分分为为两两种：种：检错码检错码和和纠错码纠错码。能发现错误但不能纠能发现错误但不能纠正错误的码称为检错码正错误的码称为检错码；不仅能发不仅能发现错误而且还现错误而且还能纠正错误的能纠正错误的码称为纠错码。码称为纠错码。在差错控制系统中使用的码按其纠错能力的不同可分为两种：检错码5（）前向纠错（）前向纠错(FEC)方式方式：FEC(Forward Error Control)方式是发端发送有纠错方式是发端发送有纠错能力的码（纠错码），接收端收到这些码后，通过纠错译能力的码（纠错码），接收端收到这些码后，通过纠错译码器自动地纠正传输中的错误。码器自动地纠正传输中的错误。差差错错控控制制系系统统大大致致可可分分为为前前向向纠纠错错、重重传传反反馈馈和和混混合合纠纠错错等三种方式。等三种方式。l l优点优点:是不需要反馈是不需要反馈信道；能进行一个用信道；能进行一个用户对多个用户的同时户对多个用户的同时通信，特别适合于移通信，特别适合于移动通信；译码实时性动通信；译码实时性较好，控制电路也比较好，控制电路也比较简单。较简单。l l缺点是译码设缺点是译码设备较复杂；编码备较复杂；编码效率较低。效率较低。（）前向纠错(FEC)方式：FEC(Fo6（）重传反馈（）重传反馈(ARQ)方式方式:ARQ(Automatic Repeat Request)方式是：发端发出方式是：发端发出能够发现错误的码（检错码），收端译码器收到后，判断能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道把捡测结果告诉在传输中有无错误产生，并通过反馈信道把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。为正确接收为止。l l优点是译码设备简单，优点是译码设备简单，在多余度一定的情况下，在多余度一定的情况下，码的检错能力比纠错能码的检错能力比纠错能力要高得多，因而整个力要高得多，因而整个系统能获得极低的误码系统能获得极低的误码率。率。l l应用应用ARQ方式必须有一条从收端至发端的反馈信道。并要求信方式必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时性也较差。控制电路比较复杂，传输信息的连贯性和实时性也较差。（）重传反馈(ARQ)方式:ARQ(A7（）混合纠错（）混合纠错(HEC)方式：方式：HEC(Hybrid Error Control)方式是上述两种方式的方式是上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内，则自动进端译码时若发现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能力，但能检测出来，行纠错；若错误个数超过了码的纠错能力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避则通过反馈信道告知发方重发。这种方式在一定程度上避免了免了 FEC方式译码设备复杂和方式译码设备复杂和 ARQ方式信息连贯性差的方式信息连贯性差的缺点。缺点。（）混合纠错(HEC)方式：HEC(Hy8在在设设计计差差错错控控制制系系统统时时，选选择择何何种种实实现现方方式式，应应综综合合考考虑各方面的因素。主要有：虑各方面的因素。主要有：满足用户对误码率的要求；满足用户对误码率的要求；有尽可能高的信息传输速率；有尽可能高的信息传输速率；(4)可接受的成本。可接受的成本。有尽可能简单的编译码算法且易于实现；有尽可能简单的编译码算法且易于实现；在设计差错控制系统时，选择何种实现方式，应综合考虑各方面的因98.1.3 纠错码的分类纠错码的分类 常用的纠错码按其码字结构形式和对信息序列处理方式常用的纠错码按其码字结构形式和对信息序列处理方式的不同可分成两大类：的不同可分成两大类：分组码分组码和和卷积码卷积码。分组码是把信息序列以每分组码是把信息序列以每k个码元分组，编码器将每个信息组个码元分组，编码器将每个信息组按一定规律产生按一定规律产生r个多余的码元（称为校验元），形成一个长个多余的码元（称为校验元），形成一个长为为n=k+r 的码字。的码字。卷积码是把信息序列以每卷积码是把信息序列以每k个分组，通过编码器输出长为个分组，通过编码器输出长为n（n k）的一个子码。但是该子码的的一个子码。但是该子码的nk个校验元不仅与本子码的信息个校验元不仅与本子码的信息元有关，而且也与其前元有关，而且也与其前m个子码的信息元有关。个子码的信息元有关。8.1.3 纠错码的分类 常用的纠错码按其码字结构形式108.1.4 差错类型差错类型 讨论码字序列讨论码字序列c通过离散信道时发生的情况，信道分为无记忆信通过离散信道时发生的情况，信道分为无记忆信道和有记忆信道。道和有记忆信道。l l在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一个差错的出现与其前后是否有错无关个差错的出现与其前后是否有错无关,如图如图8.2。在无记忆信道中，在无记忆信道中，错误是错误是随机随机产生的，因此被称作随机错误，产生的，因此被称作随机错误，无记忆信道也被称为随无记忆信道也被称为随机信道机信道（random channel）。图图8.2 8.2 二进制对称信道二进制对称信道 8.1.4 差错类型 讨论码字序列c通过离散信道时发生11 l l有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、成串地出现，表现出错误之间有相关性。图群、成串地出现，表现出错误之间有相关性。图8.3就是这种信道的就是这种信道的一个模型。一个模型。图图8.3 8.3 有记忆信道模型有记忆信道模型 就实际信道而言，由于其干扰的复杂性，往往是两种错误就实际信道而言，由于其干扰的复杂性，往往是两种错误并存。随机错误与突发错误并存的信道，称为并存。随机错误与突发错误并存的信道，称为组合信道或复组合信道或复合信道合信道。l有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成12 表表8.1给给出出了了一一个个（7，3）线线性性分分组组码码的的例例子子。该该例例子子中中，信信息息组组为为（c6 c5 c4），码码字字为为（c6 c5 c4 c3 c2 c1 c0）。）。当已知信息组时，按以下规则得到四个校验元：当已知信息组时，按以下规则得到四个校验元：（83）这组方程称为校验方程。这组方程称为校验方程。8.2 8.2 线性分性分组码的的编码 8.2.1 生成矩阵生成矩阵 表8.1给出了一个（7，3）线性分组码的例子。该例13信息组信息组 码码 字字 0000 0 0 0 0 0 0 0010 0 1 1 1 0 1 0100 1 0 0 1 1 1 0110 1 1 1 0 1 0 1001 0 0 1 1 1 0 1011 0 1 0 0 1 1 1101 1 0 1 0 0 1 1111 1 1 0 1 0 0 表表8.1（7，3）线性分组码）线性分组码（7，3）线线性性分分组组码码有有23个个许许用用码码字字或或合合法法码码字字，另另有有2723个个禁禁用用码码字字。发发方方发发送送的的是是许许用用码码字字，若若收收方方收收到到的的是禁用码字，则说明传输中发生了错误。是禁用码字，则说明传输中发生了错误。信息组 码 字 0000 0 0 0 0 0 0 0014 为了深化对线性分组码的理论分析，与线性空间联系起为了深化对线性分组码的理论分析，与线性空间联系起来。来。将（将（n，k）线性分组码的定义如下：线性分组码的定义如下：定义定义8.1 2k个个n重的集合重的集合C称为线性分组码，当且仅当它是称为线性分组码，当且仅当它是n维线性空间维线性空间Vn中的一个中的一个k 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）为了深化对线性分组码的理论分析，与线性空间联系起来。15（n，k）码中的任一码字码中的任一码字ci，均可由这组基底的线性组合生成：均可由这组基底的线性组合生成：(8 (85)5)写成矩阵形式：写成矩阵形式：(8 (84)4)（n，k）码中的任一码字ci，均可由这组基底的线性组合生成：16信息组信息组 码码 字字 0000 0 0 0 0 0 0 0010 0 1 1 1 0 1 0100 1 0 0 1 1 1 0110 1 1 1 0 1 0 1001 0 0 1 1 1 0 1011 0 1 0 0 1 1 1101 1 0 1 0 0 1 1111 1 1 0 1 0 0 表表8.1（7，3）线性分组码）线性分组码 定义定义8.2 若信息组以不变的形式，在码字的任意若信息组以不变的形式，在码字的任意k位中出现位中出现的码，称为系统码；否则，称为非系统码。的码，称为系统码；否则，称为非系统码。信息组 码 字 0000 0 0 0 0 0 0 0017说明：说明：常见系统码有两种形式：常见系统码有两种形式：（1 1）、信息组排在码字的最左边）、信息组排在码字的最左边k k位；（本教材采用）位；（本教材采用）（2 2）、）、信息组排在码字的最右边信息组排在码字的最右边k位；位；一个系统码的生成矩阵一个系统码的生成矩阵G，其左边，其左边k行行k列应是一个列应是一个k阶单位方阵阶单位方阵Ik 因此生产矩阵因此生产矩阵G表示为：表示为：其中，其中，P是一个是一个 阶矩阵。阶矩阵。Q为为kr阶矩阵阶矩阵,Ik为为k阶单位阵，称为阶单位阵，称为典型生成矩阵典型生成矩阵。说明：常见系统码有两种形式：一个系统码的生成矩188.2.2 校验矩阵校验矩阵 表表8.1所所示示（7，3）线线性性分分组组码码的的四四个个校校验验元元是是由由(83)式式所所示示的的线线性方程组决定的。把性方程组决定的。把(8(83)3)式移项：式移项：上式写成矩阵形式得上式写成矩阵形式得8.2.2 校验矩阵 表8.1所示（7，3）线性分组码的四个19这里的四行七列矩阵称为（这里的四行七列矩阵称为（7，3）码的一致校验矩阵，简称）码的一致校验矩阵，简称校验矩阵校验矩阵，用，用H表示：表示：由由H矩矩阵阵得得到到的的（n，k）线线性性分分组组码码的的每每一一码码字字ci，（i i1 1，2 2，2k），都都必必须须满满足足由由H矩矩阵阵各各行行所所确确定定的的线线性方程组，即性方程组，即 c ci iH H T T0 0 (8(88)8)或或 H Hc ci iT T0 0T T (8(89)9)又又，（n n，k k）线线性性分分组组码码的的生生成成矩矩阵阵G G中中的的每每一一行行及及其其线线性性组组合都是（合都是（n n，k k）码的码字，所以有码的码字，所以有 GH GH T T0 0 (8 (810)10)或或 HG T0T (8 (811)11)这里的四行七列矩阵称为（7，3）码的一致校验矩阵，简称校验矩20系统码的校验矩阵系统码的校验矩阵H H具有以下形式：即具有以下形式：即 一个系统码的校验矩阵一个系统码的校验矩阵H，其右边，其右边r行行r列应是一个列应是一个r阶单位方阵阶单位方阵Ir，而而PT是一个是一个 阶矩阵阶矩阵：系统码的校验矩阵H具有以下形式：即 一个系统码218.2.3 编码的实现编码的实现 设码的设码的G矩阵为矩阵为当信息组当信息组m（mn-1mn-2 mn-k）时，相应的码字时，相应的码字c是是 c mG（cn-1 cn-2 c1 c0）cj mn-1 p1,j+mn-2 p2,j+mn-k pk,j 0 j nk cjmj nk j n1 其中其中8.2.3 编码的实现 设码的G矩阵为当信息组m（mn-22图8.4 （n，k）线性分组码编码电路 图8.4 （n，k）线性分组码编码电路 23编编码码实实现现电电路路如如图图8.4所所示示。电电路路由由移移位位寄寄存存器器、模模二二加加法法器器和和模模二二乘乘法法器器组组成成根根据据图图8.4的的电电路路，可可画画出出（7，3）线线性性分分组组码码的的编编码码器电路，如图器电路，如图8.5。图图8.5 8.5 （7,37,3）线性分组码编码电路）线性分组码编码电路 编码实现电路如图8.4所示。电路由移位寄存器、模二加法器和模248.3 8.3 伴随式与伴随式与译码 8.3.1 码的距离和重量码的距离和重量 定义定义8.5 一个码的最小距离一个码的最小距离dmin定义为定义为 (8 (813)13)定义定义8.4 码字中码字中非零码元的个数，非零码元的个数，称为该码字的汉明称为该码字的汉明重量，简称重量，重量，简称重量，用用w（c）表示。表示。定义定义8.3 两个两个码字码字之间，对应位取值之间，对应位取值不同的个数，称为不同的个数，称为它们之间的它们之间的汉明汉明距距离，简称距离，用离，简称距离，用d d（c1，c 2）表示。表示。8.3 伴随式与译码 8.3.1 码的距离和重量 定义8.525码的距离和重量满足以下不等码的距离和重量满足以下不等 d d（c 1，c 2）d d（c 1 1，c 3 3）d d（c 3 3，c 2 2）(8 (814)14)w（c 1 1c 2 2）w（c 1 1）w（c 2 2）(8 (815)15)定理定理8.1 线性分组码的最小距离等于其非零码字的最小重线性分组码的最小距离等于其非零码字的最小重量。量。根据定理，要得到码的最小距离，只要检查根据定理，要得到码的最小距离，只要检查2k1个非零个非零码字的重量即可。码字的重量即可。当当 当生成矩阵给定时，当生成矩阵给定时，线性分组码有如下性质线性分组码有如下性质：（1 1）零向量；）零向量；（2 2）任意两码字的和仍是一个码字；）任意两码字的和仍是一个码字；（3 3）任意码字）任意码字 是是 的行向量的行向量 的线性组合；的线性组合；（4 4）线性分组码的最小距离等于最小非零码字重量。）线性分组码的最小距离等于最小非零码字重量。码的距离和重量满足以下不等 定理8.1 线性分组码的最小26信息组信息组 码码 字字 0000 0 0 0 0 0 0 0010 0 1 1 1 0 1 0100 1 0 0 1 1 1 0110 1 1 1 0 1 0 1001 0 0 1 1 1 0 1011 0 1 0 0 1 1 1101 1 0 1 0 0 1 1111 1 1 0 1 0 0 表表8.1（7，3）线性分组码）线性分组码 事事实实上上，两两个个码码字字之之间间的的距距离离表表示示了了它它们们之之间间差差别别的的大大小小。因因此此，一一个个线线性性分分组组码码的的最最小小距距离离是是衡衡量量码码抗抗干干扰扰能能力力的的重要参数。码的最小距离愈大，其抗干扰能力愈强。重要参数。码的最小距离愈大，其抗干扰能力愈强。信息组 码 字 0000 0 0 0 0 0 0 00278.3.2 线性码的纠检错能力线性码的纠检错能力 该定理是纠错码理论中最重要的基本定理之一，它说该定理是纠错码理论中最重要的基本定理之一，它说明了一个距离为明了一个距离为d的线性分组码，既可用来纠正的线性分组码，既可用来纠正个错误，又可用来检测个错误，又可用来检测e d1个错误。个错误。定定理理8.2 对对于于任任一一个个（n，k）线线性性分分组组码码，若若要要在在码码字字内内 检测检测e个错误，则要求码的最小距离个错误，则要求码的最小距离d e1；纠正纠正t个错误，则要求码的最小距离个错误，则要求码的最小距离d 2t1；纠正纠正t个错误同时检测个错误同时检测e（t）个错误，则要求个错误，则要求d te1。8.3.2 线性码的纠检错能力 该定理是纠错码理论中28 定理定理8.3 （n，k）线性分组码有最小距离为线性分组码有最小距离为d的充的充要条件，是要条件，是H矩阵中任意矩阵中任意d1列线性无关。列线性无关。推论推论8.4 （n，k）线性分组码的最大的，可能线性分组码的最大的，可能的最小距离等于的最小距离等于n k1。由此定理可知，所有列相同，但排列位置不同的各种由此定理可知，所有列相同，但排列位置不同的各种H矩阵所对应的不同（矩阵所对应的不同（n，k）线性分组码，都有相同的最线性分组码，都有相同的最小距离，即它们在纠错能力和码率上是完全等价的。小距离，即它们在纠错能力和码率上是完全等价的。定理8.3（n，k）线性分组码有最小距离为d的充要条件，298.3.3 伴随式伴随式 由于信道中噪声的影响，由于信道中噪声的影响，y序列中的某些码元可能与序列中的某些码元可能与c序列序列中对应码元的值不同，有中对应码元的值不同，有 yce (8(816)16)称称e为信道的为信道的错误图样错误图样。（n，k）码码的的任任一一码码字字，均均满满足足(88)式式或或(89)式式，因此，可以将接收码字因此，可以将接收码字y用二式中之任一式进行检验：用二式中之任一式进行检验：(8(817)17)令令 s s=y y.H H T T=e e.H H T T (8 (818)18)称称为接收序列的接收序列的伴随式伴随式或校正子。或校正子。当当s 0时时，译译码码器器要要做做的的就就是是如如何何从从伴伴随随式式s中中找找到到错错误误图样，从而译出发送的码字。图样，从而译出发送的码字。8.3.3 伴随式 由于信道中噪声的影响，y序列中的某些码元30得到（得到（n，k）线性分组码的译码步骤如下：线性分组码的译码步骤如下：若若s=0，则认为收到的则认为收到的y没有错误；否则认为没有错误；否则认为有错，并查译码表，由有错，并查译码表，由s找出错误图样找出错误图样 ；由接收到的由接收到的y计算伴随式计算伴随式 ；由和由和y计算计算 ，就作为纠错后的判决码就作为纠错后的判决码字输出。字输出。8.3.4 线性分组码的译码线性分组码的译码 得到（n，k）线性分组码的译码步骤如下：若s=0，则318.4 8.4 汉明明码 8.4.1 汉明码的构造汉明码的构造 定义定义8.6若若H矩阵的列是由非全零且互不相矩阵的列是由非全零且互不相同的所有二进制同的所有二进制r重组成，则由此得到的线性重组成，则由此得到的线性分组码，称为分组码，称为GF(2)上的（上的（2r1，2r1r）汉明码。汉明码。8.4 汉明码 8.4.1 汉明码的构造 定义8.328.4.2 汉明限与完备码汉明限与完备码 一一个个二二进进制制（n，k）线线性性分分组组码码，若若要要纠纠正正t个个错错误误，则则应应使使小小于于或或等等于于t个个错错误误所所组组成成的的所所有有错错误误图图样样，都都必必须须有有不不同的伴随式与之对应，即以下不等式成立：同的伴随式与之对应，即以下不等式成立：(8 (820)20)式式(820)称为称为汉明限汉明限。如果某一（如果某一（n，k）线性分组码能使线性分组码能使(8(820)20)式等号成立，式等号成立，即错误图样总数正好等于伴随式数目，则称这种码为即错误图样总数正好等于伴随式数目，则称这种码为完备码完备码。如果一个（如果一个（n，k）线性分组码，除了能将重量小于等于线性分组码，除了能将重量小于等于t的所有错误图样作为陪集首外，还有部分（但不是全部）的所有错误图样作为陪集首外，还有部分（但不是全部）重量大于重量大于t的错误图样作为陪集首，则称这种码为的错误图样作为陪集首，则称这种码为准完备码准完备码。8.4.2 汉明限与完备码 一个二进制（n，k）线性33本章的主要内容是：本章的主要内容是：本本 章章 小小 结结l l（3）线性分组码的检纠错能力：汉明距离和汉明重量，）线性分组码的检纠错能力：汉明距离和汉明重量，码的最小距离，码的最小距离与检纠错能力的关系，距离码的最小距离，码的最小距离与检纠错能力的关系，距离为为d的线性分组码的构造，的线性分组码的构造，MDSMDS码。码。l l（2）线性分组码的编码：线性分组码的定义，生成矩阵）线性分组码的编码：线性分组码的定义，生成矩阵和校验阵的构成，系统码的生成矩阵和校验矩阵，对偶码，和校验阵的构成，系统码的生成矩阵和校验矩阵，对偶码，编码实现电路。编码实现电路。l l（1）纠错码的基本概念：信道纠错编码及其目的，差错）纠错码的基本概念：信道纠错编码及其目的，差错控制系统的三种实现方式，检错码与纠错码，分组码与卷控制系统的三种实现方式，检错码与纠错码，分组码与卷积码，随机错误与突发错误。积码，随机错误与突发错误。本章的主要内容是：本 章 小 结l（3）线性分组码的检34l l（5）汉明码：汉明码的定义，构造一个汉明码，汉明限，）汉明码：汉明码的定义，构造一个汉明码，汉明限，完备码与准完备码。完备码与准完备码。l l（4）伴随式与译码：错误图样，接收序列的伴随式，）伴随式与译码：错误图样，接收序列的伴随式，码的标准阵列的构成，选择陪集首，将标准阵列简化为译码的标准阵列的构成，选择陪集首，将标准阵列简化为译码表，线性分组码的译码步骤。码表，线性分组码的译码步骤。l（5）汉明码：汉明码的定义，构造一个汉明码，汉明限，l（435第八章线性分组码课件36