通信原理第9章--差错控制编码课件优秀PPT.ppt

第一节第一节 概述概述一、差错限制编码的作用一、差错限制编码的作用 在在数数字字通通信信中中，依依据据不不同同的的目目的的，编编码码可可分分为为信信源源编编码码和和信信道道编编码码。信信源源编编码码是是为为了了提提高高数数字字通通信信的的有有效效性性以以及及使使模模拟拟信信号号数数字字化化而而实实行行的的编编码码技技术术。信信道道编编码码是是为为了了降降低低误误码码率率，提高数字通信的牢靠性而实行的编码。提高数字通信的牢靠性而实行的编码。数字信号在传输过程中，加性噪声、码间串扰等都可能引起误码。为数字信号在传输过程中，加性噪声、码间串扰等都可能引起误码。为了提高系统的抗干扰性能，可以加大发送功率，降低接收设备本身的噪声，了提高系统的抗干扰性能，可以加大发送功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以接受信道编码技术。正如以及合理选择调制、解调方法等。此外，还可以接受信道编码技术。正如第一章在通信系统模型中所述，信源编码是降低信源的冗余度；而信道编第一章在通信系统模型中所述，信源编码是降低信源的冗余度；而信道编码按确定的规则人为引入冗余度。具体地讲，信道编码就是在发送端的信码按确定的规则人为引入冗余度。具体地讲，信道编码就是在发送端的信息码元序列中，以某种确定的编码规则，加入监督码元，在接收端再利用息码元序列中，以某种确定的编码规则，加入监督码元，在接收端再利用该规则进行检查识别，从而发觉错误、订正错误。该规则进行检查识别，从而发觉错误、订正错误。二进制数字信号在传输中发生的错误，主要有两种类型：随二进制数字信号在传输中发生的错误，主要有两种类型：随机错误和突发错误。随机错误的特点是码元间的错误相互独立，即机错误和突发错误。随机错误的特点是码元间的错误相互独立，即每个码元的错误概率与它前后码元的错误与否是无关的。突发错误每个码元的错误概率与它前后码元的错误与否是无关的。突发错误则不然，一个码元的错误往往影响前后码元的错误概率。或者说，则不然，一个码元的错误往往影响前后码元的错误概率。或者说，一个码元产生错误，则后面几个码元都可能发生错误。在实际信道一个码元产生错误，则后面几个码元都可能发生错误。在实际信道中，上述两种错误形式往往兼而有之。移动通信的传输信道属于变中，上述两种错误形式往往兼而有之。移动通信的传输信道属于变参信道，它不仅会引起随机错误，而更重要的是造成突发错误。参信道，它不仅会引起随机错误，而更重要的是造成突发错误。能发觉错误的编码叫检错码；能订正错误的编码叫纠错码。一般能发觉错误的编码叫检错码；能订正错误的编码叫纠错码。一般说来，纠错码确定能检错。反过来，检错码不确定能纠错。或者说，说来，纠错码确定能检错。反过来，检错码不确定能纠错。或者说，同一个码，检错实力比纠错实力强。同一个码，检错实力比纠错实力强。二、差错限制方式二、差错限制方式 在数字通信系统中，利用纠错码或检错码进行差在数字通信系统中，利用纠错码或检错码进行差错限制的方式有错限制的方式有3 3种：检错重发、前向纠错和混合纠错，种：检错重发、前向纠错和混合纠错，它们的系统构成如图它们的系统构成如图9-19-1所示，图中有斜线的方框图表所示，图中有斜线的方框图表示在该端检出错误。示在该端检出错误。1 1检错限制方式检错限制方式 检错重发又称自动恳求重传方式，记作检错重发又称自动恳求重传方式，记作ARQ(Automatic Repeat Request)ARQ(Automatic Repeat Request)。发送端发出。发送端发出能够发觉（检测）错误的码，接收端收到通过信能够发觉（检测）错误的码，接收端收到通过信道传来的码后，在译码器依据该码的编码规则，道传来的码后，在译码器依据该码的编码规则，判决收到的码序列中有无错误产生，假如发觉错判决收到的码序列中有无错误产生，假如发觉错误，则通过反向信道把这一判决结果反馈给发端。误，则通过反向信道把这一判决结果反馈给发端。然后，发端依据这些判决信号，把接收端认为有然后，发端依据这些判决信号，把接收端认为有错误的信息再次传送，直到接收端认为正确接收错误的信息再次传送，直到接收端认为正确接收为止。为止。从上可知，应用从上可知，应用ARQARQ方式必需有一反馈信道，一般方式必需有一反馈信道，一般较适用于一个用户对一个用户（点对点）的通信，且要较适用于一个用户对一个用户（点对点）的通信，且要求信源能够限制，系统收发两端必需相互协作、亲密协求信源能够限制，系统收发两端必需相互协作、亲密协作。由于反馈重发的次数与信道干扰状况有关，若信道作。由于反馈重发的次数与信道干扰状况有关，若信道干扰很频繁，则系统常常处于重发消息的状态，因此这干扰很频繁，则系统常常处于重发消息的状态，因此这种方式传送消息的连贯性和实时性较差。该方式的优点种方式传送消息的连贯性和实时性较差。该方式的优点是：编译码设备简洁；在确定的多余度码元下，检错码是：编译码设备简洁；在确定的多余度码元下，检错码的检错实力比纠错码的纠错实力要高得多，因此这种系的检错实力比纠错码的纠错实力要高得多，因此这种系统的适应性很强，特殊适应于短波、散射、有线等干扰统的适应性很强，特殊适应于短波、散射、有线等干扰状况特殊困难的信道中。状况特殊困难的信道中。2 2前向纠错方式前向纠错方式 前向纠错方式记作前向纠错方式记作FECFEC（Forword Forword Error-Correction)Error-Correction)。发送端发送能够被纠错的码，。发送端发送能够被纠错的码，接收端收到这些码后，通过纠错译码器不仅能够自动接收端收到这些码后，通过纠错译码器不仅能够自动地发觉错误，而且能自动地订正接受码字传输中的错地发觉错误，而且能自动地订正接受码字传输中的错误。这种方式的优点是不须要反馈信道，能进行一个误。这种方式的优点是不须要反馈信道，能进行一个用户对多个用户的同播通信，译码实时性较好。其缺用户对多个用户的同播通信，译码实时性较好。其缺点是译码设备比较困难，所选用的纠错码必需与信道点是译码设备比较困难，所选用的纠错码必需与信道的干扰状况相匹配，因此对信道的适应性较差。编码的干扰状况相匹配，因此对信道的适应性较差。编码效率低。但由于这种方式能同播，特殊适用于军用通效率低。但由于这种方式能同播，特殊适用于军用通信。信。3 3混合纠错方式混合纠错方式 混合纠错方式记作混合纠错方式记作HEC(Hybrid Error HEC(Hybrid Error-Correction)-Correction)是是FECFEC和和ARQARQ方式的结合，这种方式方式的结合，这种方式是发送端发送的码不仅能够被检测出错误，而且是发送端发送的码不仅能够被检测出错误，而且还具有确定的纠错实力。接收端收到码后，首先还具有确定的纠错实力。接收端收到码后，首先检查差错状况，假如在纠错码的纠错实力范围以检查差错状况，假如在纠错码的纠错实力范围以内，则自动纠错，假如错误过多，超过了码的纠内，则自动纠错，假如错误过多，超过了码的纠错实力，但能检测出来，则接收端通过反馈信道，错实力，但能检测出来，则接收端通过反馈信道，要求发端重新传送有错的消息。这种方式具有自要求发端重新传送有错的消息。这种方式具有自动纠错和检错重发的优点，并可达到较低的误码动纠错和检错重发的优点，并可达到较低的误码率。因此，在实际中的应用越来越广。率。因此，在实际中的应用越来越广。在移动通信系统中，几乎都接受前向纠错的差错限在移动通信系统中，几乎都接受前向纠错的差错限制方式。制方式。除了上述三种主要方式以外，还有所谓狭义信息反馈除了上述三种主要方式以外，还有所谓狭义信息反馈系统（系统（IRQInformation Repeat RequestIRQInformation Repeat Request）。这种方式）。这种方式是接收端把收到的消息原封不动地通过反馈信道送回发是接收端把收到的消息原封不动地通过反馈信道送回发送端，发送端比较发送的与反馈回来的消息，从而发觉送端，发送端比较发送的与反馈回来的消息，从而发觉错误，并且把传错部分对应的原消息再次传送，最终达错误，并且把传错部分对应的原消息再次传送，最终达到使对方正确接收消息的目的。到使对方正确接收消息的目的。三、纠错码的分类三、纠错码的分类 .线性码与非线性码线性码与非线性码 依据纠错码各码组信息和监督元的函数关依据纠错码各码组信息和监督元的函数关系，可分为线性码和非线性码。假如函数关系系，可分为线性码和非线性码。假如函数关系是线性的，即满足一组线性方程式，则称为线是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。线性码集合中的全部性码，否则为非线性码。线性码集合中的全部码字在加法和乘法运算时是封闭的，而非线性码字在加法和乘法运算时是封闭的，而非线性码则不封闭。换言之，线性码事实上就是码则不封闭。换言之，线性码事实上就是n维线维线性空间的一个性空间的一个k（kn）维子空间。目前大量运）维子空间。目前大量运用的均为线性码。用的均为线性码。分组码与卷积码分组码与卷积码 依据码组中监督码元与信息码元相互关联的长度，可分依据码组中监督码元与信息码元相互关联的长度，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。干组的信息元有关。分组码把信息序列以分组码把信息序列以k个码元分组，通过编码器将每组的个码元分组，通过编码器将每组的k元信息按确定规律产生元信息按确定规律产生r个多余码元（称为校验元或监督元）个多余码元（称为校验元或监督元）输出长为输出长为n=k+r的一个码字（码组）。因此，每一码组的的一个码字（码组）。因此，每一码组的r个个校验元仅与本组的信息元有关而与别组无关。分组码用校验元仅与本组的信息元有关而与别组无关。分组码用(n，k)表示，表示，n为码长，为码长，k表示信息位数目。表示信息位数目。卷积码将信息序列以卷积码将信息序列以k0个码元分段，通过编码器输出长为个码元分段，通过编码器输出长为n0的一段码组。但是该码的的一段码组。但是该码的n0-k0个校验元不仅与本段的信个校验元不仅与本段的信息源有关，而且也与其前息源有关，而且也与其前m段的信息源有关，故卷积码用段的信息源有关，故卷积码用（n0，k0，m0）表示。）表示。检错码和纠错码检错码和纠错码 依据码的用途，可分为检错码和纠错码。检依据码的用途，可分为检错码和纠错码。检错码以检错为目的，不确定能纠错；而纠错码以错码以检错为目的，不确定能纠错；而纠错码以纠错为目的，确定能检错。纠错为目的，确定能检错。另外，在分组码中依据码的结构特点，可以分另外，在分组码中依据码的结构特点，可以分为循环码和非循环码；依据纠（检）错误的类型为循环码和非循环码；依据纠（检）错误的类型来分，可以分为订正随机错误的码、订正突发错来分，可以分为订正随机错误的码、订正突发错误的码和订正同步错误的码；依据码元取值的进误的码和订正同步错误的码；依据码元取值的进制来分，可分为二进制码和多进制码；等等，这制来分，可分为二进制码和多进制码；等等，这里不一一赘述。里不一一赘述。四、纠错编码的基本原理四、纠错编码的基本原理下面以分组码为例来说明纠错码检错和纠错的基本下面以分组码为例来说明纠错码检错和纠错的基本原理。原理。1分组码分组码 分组码一般可用（分组码一般可用（n，k）表示。其中，）表示。其中，k是每是每个码组二进制信息码元的数目，个码组二进制信息码元的数目，n是编码组的码元是编码组的码元总位数，又称为码组长度，简称码长。总位数，又称为码组长度，简称码长。n-k=r为每为每个码组中的监督码元数目。简洁地说，分组码是对个码组中的监督码元数目。简洁地说，分组码是对每段每段k位长的信息组以确定的规则增加位长的信息组以确定的规则增加r个监督元，个监督元，组成长为组成长为n的码字。在二进制状况下，共有的码字。在二进制状况下，共有2k个不个不同的信息组，相应地可得到同的信息组，相应地可得到2k个不同的码字，称为个不同的码字，称为许用码组。其余许用码组。其余2n-2k个码未被选用，称为禁用码个码未被选用，称为禁用码组。组。两个等长码组之间相应位取值不同的数目两个等长码组之间相应位取值不同的数目称为这两个码组的汉明（称为这两个码组的汉明（HammingHamming）距离，简）距离，简称码距。例如称码距。例如1100011000与与1001110011之间的距离之间的距离d=3d=3。码组集合中随意两个码字之间距离的最小值称码组集合中随意两个码字之间距离的最小值称为码的最小距离，用为码的最小距离，用d0d0表示。最小码距是码的表示。最小码距是码的一个重要参数，它是衡量码检错、纠错实力的一个重要参数，它是衡量码检错、纠错实力的依据。在分组码中，非零码元的数目称为码字依据。在分组码中，非零码元的数目称为码字的汉明重量，简称码重。例如，码字的汉明重量，简称码重。例如，码字1011010110，码重码重w=3w=3。2检错和纠错实力检错和纠错实力 我们以重复码为例，说明为什么纠错码能我们以重复码为例，说明为什么纠错码能够检错或纠错。够检错或纠错。若分组码码字中的监督元在信息元之后，而若分组码码字中的监督元在信息元之后，而且是信息元的简洁重复，则称该分组码为重复且是信息元的简洁重复，则称该分组码为重复码。它是一种简洁好用的检错码，并有确定的码。它是一种简洁好用的检错码，并有确定的纠错实力。例如（纠错实力。例如（2，1）重复码，两个许用码）重复码，两个许用码组是组是00与与11，d0=2，收端译码，出现，收端译码，出现01、10禁禁用码组时，可以发觉传输中的一位错误。假如用码组时，可以发觉传输中的一位错误。假如是（是（3，1）重复码，两个许用码为）重复码，两个许用码为000、111，d0=3；当收端出现两个或三个；当收端出现两个或三个1时，判为时，判为1，否，否则判为则判为0。此时，可以订正一个错误，或者该。此时，可以订正一个错误，或者该码可以检出两个错误。码可以检出两个错误。从上面的例子中，可以看出：码的最小距离从上面的例子中，可以看出：码的最小距离d0d0干脆关干脆关系着码的检错和纠错实力；任一（系着码的检错和纠错实力；任一（n n，k k）分组码，）分组码，若要在码字内检测若要在码字内检测e e个随机错误，则要求码的最小距离：个随机错误，则要求码的最小距离：d0 e+1 d0 e+1要订正要订正t t个随机错误，则要求码的最小距离：个随机错误，则要求码的最小距离：d02t+1 d02t+1要订正要订正t t个错误同时检测个错误同时检测e e个错误（个错误（etet），则要求码的最小），则要求码的最小距离：距离：d0t+e+1 d0t+e+13 3编码效率编码效率 接受差错限制编码是提高了通信系统接受差错限制编码是提高了通信系统的牢靠性，但是以降低有效性为代价换来的。的牢靠性，但是以降低有效性为代价换来的。通常定义编码效率通常定义编码效率R R 来衡量有效性：来衡量有效性：R=k/n R=k/n 其中，其中，k k 是一个码组中信息元的个数，是一个码组中信息元的个数，n n 为码长。为码长。对纠错码的基本要求是：检错和纠错实力对纠错码的基本要求是：检错和纠错实力尽量强；编码效率尽量高；编码规律尽量简洁。尽量强；编码效率尽量高；编码规律尽量简洁。实际中要依据具体指标要求，保证有确定纠、实际中要依据具体指标要求，保证有确定纠、检错实力和编码效率，并且易于实现。检错实力和编码效率，并且易于实现。其次节常用的几种简洁分组码其次节常用的几种简洁分组码 纠错编码的种类很多，较早出现的、纠错编码的种类很多，较早出现的、应用较多的大多属于分组码。本节仅介绍其中应用较多的大多属于分组码。本节仅介绍其中一些较为常用的简洁编码。一些较为常用的简洁编码。一、奇偶监督码一、奇偶监督码 奇偶监督码是在原信息码后面附加一个奇偶监督码是在原信息码后面附加一个监督元，使得码组中监督元，使得码组中“1”“1”的个数是奇数或偶数。的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶或者说，它是含一个监督元，码重为奇数或偶数的（数的（n n，n-1n-1）系统分组码。奇偶监督码又分）系统分组码。奇偶监督码又分为奇监督码和偶监督码。为奇监督码和偶监督码。设码字设码字A=an-1，an-2，a1，a0，对偶监督码有，对偶监督码有 (9-1)式中式中an-1，an-2，a1为信息元，为信息元，a0为监督元。由于该码的每一个码为监督元。由于该码的每一个码字均按同一规则构成式（字均按同一规则构成式（9-1），故又称为一样监督码。接收端译码时，），故又称为一样监督码。接收端译码时，按式（按式（9-1）将码组中的码元模二相加，若结果为）将码组中的码元模二相加，若结果为“0”就认为无错（包就认为无错（包括有偶数个错误）；结果为括有偶数个错误）；结果为“1”，就可断定该码组经传输后有奇数个，就可断定该码组经传输后有奇数个错误。错误。奇监督码状况相像，只是码组中奇监督码状况相像，只是码组中“1”的数目为奇数，即满足条件的数目为奇数，即满足条件 而检错实力与偶监督码相同。奇偶监督码的编码效率为而检错实力与偶监督码相同。奇偶监督码的编码效率为R=（n-1）/n，奇偶校验码的编码率是最高的。，奇偶校验码的编码率是最高的。二维奇偶监督码把上述奇偶监督码的若干码组排列成矩阵，每一二维奇偶监督码把上述奇偶监督码的若干码组排列成矩阵，每一码组写成一行，然后再按列的方向增加其次维监督位，设码组写成一行，然后再按列的方向增加其次维监督位，设a01 a02 a0m为为m行奇偶监督位；行奇偶监督位；cn-1 cn-2 c0为按列进行其为按列进行其次次编码所增加的监督位，它们构成了一监督位行。由此组成的二维奇次次编码所增加的监督位，它们构成了一监督位行。由此组成的二维奇偶监督码阵如下：偶监督码阵如下：二、二维奇偶监督码二、二维奇偶监督码an-11 an-11a11 a01an-12 an-12a12 a02 an-1m an-1m a1m a0mcn-1 cn-2 c1 c0 这种码有可能检测偶数个错误。因为这种码有可能检测偶数个错误。因为每行的监督位虽然不能用于检测本行中的每行的监督位虽然不能用于检测本行中的偶数个错误，但按列的方向有可能由偶数个错误，但按列的方向有可能由cn-1、cn-2、c0等监督位检测出来。有等监督位检测出来。有一些偶数错码不行能检测出，例如，构成一些偶数错码不行能检测出，例如，构成矩形的四个错码就检测不出来矩形的四个错码就检测不出来,比如阵列中比如阵列中的的an-22,a12,an-2m,a1m。这种二维奇偶监督码适于检测突发错这种二维奇偶监督码适于检测突发错误。前述的一维奇偶监督码一般只适于检误。前述的一维奇偶监督码一般只适于检测随机错误。二维奇偶监督码不仅可用来测随机错误。二维奇偶监督码不仅可用来检错，还可以用于纠错。例如，当码组中检错，还可以用于纠错。例如，当码组中仅在一行中有奇数个错误时，则能够确定仅在一行中有奇数个错误时，则能够确定错码的位置，从而订正它。错码的位置，从而订正它。an-11 an-11a11 a01an-12 an-12a12 a02 an-1m an-1m a1m a0mcn-1 cn-2 c1 c0三、恒比码三、恒比码 码字中码字中1 1的数目与的数目与0 0的数目保持恒定比例的码的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相称为恒比码。由于恒比码中，每个码组均含有相同数目的同数目的1 1和和0 0，因此恒比码又称等重码，定，因此恒比码又称等重码，定1 1码。码。这种码在检测时，通过计算接收码元中这种码在检测时，通过计算接收码元中1 1的数目是的数目是否正确，就知道有无错误。否正确，就知道有无错误。目前我国电传通信中普遍接受目前我国电传通信中普遍接受3 3：2 2码，又称码，又称“5“5中取中取3”3”的恒比的恒比码，即每个码组长度为码，即每个码组长度为5 5，其中，其中3 3个个“1”“1”。这时可能编成的不同码组。这时可能编成的不同码组数目等于从数目等于从5 5中取中取3 3的组合数的组合数1010，这，这1010个许用码组恰好可表示个许用码组恰好可表示1010个阿拉个阿拉伯数字，如表伯数字，如表7-17-1所示。而每个汉字又是以四位十进制数来代表的。所示。而每个汉字又是以四位十进制数来代表的。实践证明，接受这种码后，我国汉字电报的差错率大为降低。实践证明，接受这种码后，我国汉字电报的差错率大为降低。目前国际上通用的目前国际上通用的ARQARQ电报通信系统中，接受电报通信系统中，接受3 3：4 4码，即码，即“7“7中取中取3”3”的恒比码。的恒比码。100119011108111007101016001115110104101103110012010111011010码字数字表表9-1 39-1 3：2 2恆比码恆比码第三节线性分组码第三节线性分组码一、基本概念一、基本概念 线性分组码在全部可能的分组码（线性分组码在全部可能的分组码（Block Code）中只占很少的一部分，然而，它却几乎是惟）中只占很少的一部分，然而，它却几乎是惟一具有实际价值的分组码。线性分组码是全部纠错一具有实际价值的分组码。线性分组码是全部纠错编码中最基本最简洁探讨的一类码，它概念清晰，编码中最基本最简洁探讨的一类码，它概念清晰，易于理解，而且能便利地反映出各类编码中广为运易于理解，而且能便利地反映出各类编码中广为运用的一些基本参数和名称，因此，线性分组码就成用的一些基本参数和名称，因此，线性分组码就成了探讨其他各类码的基础。了探讨其他各类码的基础。在（在（n，k）分组码中，若每一个监督元都是码组）分组码中，若每一个监督元都是码组中某些信息元按模中某些信息元按模2和得到的，即监督元是信息元和得到的，即监督元是信息元按线性关系相加而得到的，则称线性分组码。或者按线性关系相加而得到的，则称线性分组码。或者说，可用线性方程组表述码规律性的分组码称为线说，可用线性方程组表述码规律性的分组码称为线性分组码。线性分组码是一类重要的纠错码，应用性分组码。线性分组码是一类重要的纠错码，应用很广泛。很广泛。对于偶监督码，运用了一位监督位a0，设码字A=an-1，an-2，a1，a0，有 在接收端解码时，事实上就是计算上式S的结果，若结果为1，则认为有错，结果为0，则认为无错。式中，S称为校正子，取值只有两种，故只能代表有错和无错两种信息，若增加一位监督位，则能增加一个类似于上式的监督关系式。则有两个校正子，它们有4中可能值组合，故能表示4种不同信息，则除了表示有无错信息外，还能有其余可能值来表示错误的位置信息。同理，r个监督位能只是一位错码的2r-1个可能位置。现以（现以（7，4）分组码为例来说明线性分组码的特点。）分组码为例来说明线性分组码的特点。设其码字为设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前，其中前4位是信位是信息元，后息元，后3位是监督元，可用下列线性方程组来描述该分位是监督元，可用下列线性方程组来描述该分组码，产生监督元。组码，产生监督元。明显，这明显，这3 3个方程是线性无关的。经计算可得（个方程是线性无关的。经计算可得（7 7，4 4）码的全部）码的全部码字，如表码字，如表9292所示。所示。（9-7）1 1 11 1 1 1150 0 00 1 1 171 0 01 1 1 0140 1 10 1 1 060 1 01 1 0 1131 0 10 1 0 150 0 11 1 0 0121 1 00 1 0 040 0 11 0 1 1111 1 00 0 1 130 1 01 0 1 0101 0 10 0 1 021 0 01 0 0 190 1 10 0 0 111 1 11 0 0 080 0 00 0 0 00监督元监督元信息元信息元监督元监督元信息元信息元码字码字序序号号码字码字序序号号表表9 92 2（7 7，4 4）码的码字表）码的码字表不难看出，上述（不难看出，上述（7 7，4 4）线性分组码的最小码距）线性分组码的最小码距d0=3d0=3，它能订正一个错误或检测两个错误。它能订正一个错误或检测两个错误。二、监督矩阵和生成矩阵二、监督矩阵和生成矩阵式（式（9-79-7）所述（）所述（7 7，4 4）码的）码的3 3个监督方程式可以改写为个监督方程式可以改写为这组线性方程可用矩阵形式表示为这组线性方程可用矩阵形式表示为并简记为并简记为其中，其中，A是是A的转置，的转置，是是O=000的转置，的转置，是是H 的转置。的转置。（9-11）H 称为监督矩阵，一旦称为监督矩阵，一旦H 给定，信息位和监督给定，信息位和监督位之间的关系也就确定了，位之间的关系也就确定了，H 为为 rn 阶矩阵，阶矩阵，H 矩矩阵每行之间是彼此线性无关的。式（阵每行之间是彼此线性无关的。式（9-119-11）所示的）所示的H 矩阵可分成两部分。矩阵可分成两部分。（9-10）HATT 或或 AH（9-12）其中，其中，P为为rk 阶矩阵，阶矩阵，Ir为为rr 阶单位矩阵，可以写成阶单位矩阵，可以写成H=P Ir形式的监督矩阵称为典型监督矩阵。形式的监督矩阵称为典型监督矩阵。HAT=OT 说明说明H 矩阵与码字的转置乘积必为零，可以矩阵与码字的转置乘积必为零，可以接受来作为推断接收码字接受来作为推断接收码字A是否出错的依据。是否出错的依据。=P Ir 若把（若把（9-79-7）补充为下列方程）补充为下列方程（9-13）并改写为矩阵形式并改写为矩阵形式（9-14）即即（9-15）两边求转置，得两边求转置，得其中其中（9-16）称为生成矩阵，由称为生成矩阵，由G 和信息码组和信息码组 就可以产生全就可以产生全部码字。部码字。G为为kr阶矩阵，各行也是线性无关的。阶矩阵，各行也是线性无关的。生成矩阵也可以分两部分，即生成矩阵也可以分两部分，即(9-17)其中其中（9-18）Q为为kr 阶矩阵，阶矩阵，Ik 为为k阶单位阵，可以写成式（阶单位阵，可以写成式（9-17）形式的）形式的G 矩阵，称为典型生成矩阵。非典型形矩阵，称为典型生成矩阵。非典型形式的生成矩阵经过简洁的行运算也确定可以化为典式的生成矩阵经过简洁的行运算也确定可以化为典型生成矩阵形式。型生成矩阵形式。G=Ik Q 三、伴随式（校正子）三、伴随式（校正子）S 设发送码组设发送码组 ，在传输过程中可能发，在传输过程中可能发生误码。接收码组生误码。接收码组B=bn-1，bn-2b1，b0，则收发码组，则收发码组之差定义为错误图样之差定义为错误图样E，也称为误差矢量，即，也称为误差矢量，即 E=B-A （9-19）其中其中，且且（9-20）式（式（9-19）也可写作）也可写作 B=A+E （9-21）令令S=BH T，S 称为伴随式或校正子，利用称为伴随式或校正子，利用AH T=0，得，得 （9-22）由此可见，伴随式由此可见，伴随式S与错误图样与错误图样E之间有确定的线之间有确定的线性变换关系。接收端译码器的任务就是从伴随式确定性变换关系。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。上错误图样，然后从接收到的码字中减去错误图样。上述（述（7，4）线性分组码的伴随式与错误图样的对应关）线性分组码的伴随式与错误图样的对应关系如表系如表9-3所示。所示。S=BH T=（A+E）H T=EH T 0 0 00 0 10 1 01 0 00 1 1 1 0 11 1 01 1 10 0 0 0 0 0 00 0 0 0 0 0 10 0 0 0 0 1 00 0 0 0 1 0 00 0 0 1 0 0 00 0 1 0 0 0 00 1 0 0 0 0 01 0 0 0 0 0 0 /b0b1b2b3b4b5b601234567s2 s1 s0e6 e5 e4 e3 e2 e1 e0SE错误码位序号表表9-3 9-3（7 7，4 4）码）码S S与与E E的对应关系的对应关系从表从表9-3中可以看出，伴随式中可以看出，伴随式S的的2r形式分别代表形式分别代表A码无码无错和错和2r-1种有错的图样。种有错的图样。汉明码是汉明（汉明码是汉明（HammingHamming）于）于19491949年提出的能够订正单个随机错年提出的能够订正单个随机错误的线性分组码。误的线性分组码。它有如下参数：它有如下参数：码长：码长：n=2r-1n=2r-1 信息位：信息位：k=2r-1-rk=2r-1-r 监督位：监督位：n-k=r,rn-k=r,r是不小于是不小于3 3的随意正整数。的随意正整数。最小距离：最小距离：d0=3d0=3上述的（上述的（7 7，4 4）线性分组码就是一个汉明码。）线性分组码就是一个汉明码。汉明码的码率为汉明码的码率为 R=k/n=(n-r)/n=1-r/n R=k/n=(n-r)/n=1-r/n (9-23(9-23）若码长若码长n很长，则很长，则R接近接近1，所以汉明码是一类高效码。，所以汉明码是一类高效码。第四节第四节 循环码循环码 循环码（循环码（Cyclic CodeCyclic Code）是一类重要）是一类重要的线性分组码，它除了具有线性码的一般性质的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码许用码组集合中外，还具有循环性，即循环码许用码组集合中任一码字循环移位所得的码字仍为该码组集合任一码字循环移位所得的码字仍为该码组集合中的一个码字。循环码的两个最引人注目的特中的一个码字。循环码的两个最引人注目的特点是：点是：可以用反馈线性移位寄存器很简洁地实现其可以用反馈线性移位寄存器很简洁地实现其编码和伴随式计算编码和伴随式计算 由于循环码有很多固有的代数结构，从而可由于循环码有很多固有的代数结构，从而可以找到各种简洁好用的译码方法。以找到各种简洁好用的译码方法。目前发觉的很多线性分组码都与循环码亲密相关。由于循环码具有目前发觉的很多线性分组码都与循环码亲密相关。由于循环码具有众多的良好性质，所以它在理论和好用中都是特别重要的。表众多的良好性质，所以它在理论和好用中都是特别重要的。表9-4中给出中给出一种（一种（7，3）循环码全部码字。）循环码全部码字。在代数理论中，为了便于计算，常用码多项式表示码字。（在代数理论中，为了便于计算，常用码多项式表示码字。（n，k）循环码的码字，其码多项式（以降幂依次排列）为循环码的码字，其码多项式（以降幂依次排列）为(9-24)如表如表9-49-4中第中第4 4号码字可用多项式号码字可用多项式 表示。表示。0 0 0 0 0 0 00 0 1 1 1 0 10 1 0 0 1 1 10 1 1 1 0 1 01 0 0 1 1 1 01 0 1 0 0 1 11 1 0 1 0 0 11 1 1 0 1 0 001234567 码 字序号表表9-4 9-4（7 7，3)3)循环码循环码T(x)=an-1xn-1+a n-2xn-2+?+a1x+a0 T4(x)=x6+x3+x2+x T7(x)=x6+x5+x2+1 第第7 7号码字可用多项式号码字可用多项式 表示。表示。一、生成多项式及生成矩阵一、生成多项式及生成矩阵 假如一种码的全部码多项式都是多项式假如一种码的全部码多项式都是多项式g g(x)(x)的倍式，则称的倍式，则称g(x)g(x)为该码的生成多项式。为该码的生成多项式。在在(n(n，k)k)循环码中，随意码多项式循环码中，随意码多项式A(x)A(x)都是都是最低次码多项式的倍式。如表最低次码多项式的倍式。如表9-49-4的（的（7 7，3 3）循）循环码中，环码中，（9-25）其它码多项式都是其它码多项式都是g(x)倍式，即倍式，即 g(x)=T1(x)=x4+x3+x2+1 T0(x)=0g(x)T2(x)=(x+1)g(x)T3(x)=xg(x)T7(x)=x2g(x)0 0 0 0 0 0 00 0 1 1 1 0 10 1 0 0 1 1 10 1 1 1 0 1 01 0 0 1 1 1 01 0 1 0 0 1 11 1 0 1 0 0 11 1 1 0 1 0 001234567 码 字序号因此，循环码中次数最低的多项式（全因此，循环码中次数最低的多项式（全0 0码字除码字除外）就是生成多项式外）就是生成多项式g(x)。可以证明，。可以证明，g(x)是是常数项为常数项为1 1的的r=n-k次多项式，是次多项式，是 xn+1 的因式。的因式。循环码的生成矩阵常用多项式的形式来表示，即循环码的生成矩阵常用多项式的形式来表示，即其中其中 （9-26）(9-27)g(x)=xr+gr-1xr-1+g1x+1 例如（例如（7，3）循环码，）循环码，n=7，k=3，r=4，其生成，其生成多项式及生成矩阵分别为多项式及生成矩阵分别为即即 g(x)=T1(x)=x4+x3+x2+1二、监督多项式及监督矩阵二、监督多项式及监督矩阵为了便于对循环编译码，通常还定义监督多项式，令为了便于对循环编译码，通常还定义监督多项式，令其中，其中，g(x)是常数项为是常数项为1 1的的r次多项式，即生成多项式；次多项式，即生成多项式；h(x)是常数项为是常数项为1 1的的k次多项式，称为监督多项式。次多项式，称为监督多项式。同理可得监督矩阵同理可得监督矩阵H H（9-29）（9-28）其中其中称为称为h(x)的逆多项式。的逆多项式。（9-30）例如（例如（7 7，3 3）循环码）循环码，则则g(x)=x4+x3+x2+1 三、编码方法和电路三、编码方法和电路 在编码时，首先要依据给定的在编码时，首先要依据给定的(n，k)值选值选定生成多项定生成多项g(x)，即应在，即应在xn+1的因式中选一个的因式中选一个r=n-k次多项式作为次多项式作为g(x)。设编码前的信息多项式。设编码前的信息多项式m(x)为为（9-31）m(x)的最高幂次为的最高幂次为k-1。循环码中的全部码多项式都可。循环码中的全部码多项式都可被被g(x)整除，依据这条原则，就可以对给定的信息进行编码。整除，依据这条原则，就可以对给定的信息进行编码。用用xr（即（即xn-k）乘）乘m(x)，得到，得到xrm(x)的次数小于的次数小于n。用用g(x)去除去除 x rm(x)，得到余式，得到余式R(x)，R(x)的次数必小于的次数必小于g(x)的次的次数，即小于数，即小于(n-k)。将此余式加于信息位之后作为监督位，即。将此余式加于信息位之后作为监督位，即将将R(x)与与xr.m(x)相加，得到的多项式必为一码多项式，因为相加，得到的多项式必为一码多项式，因为它必能被它必能被g(x)整除，且商的次数不大于整除，且商的次数不大于(k-1)。m(x)=a1+a2x+a3x2+akxk-1 因此循环码的码多项式可表示为因此循环码的码多项式可表示为（9-32）其中其中xrm(x)代表信息位，代表信息位，R(x)是是xrm(x)与与g(x)相除得到的余式，代表监督位。相除得到的余式，代表监督位。编码电路的主体是生成多项式构成的除法电路，再加上编码电路的主体是生成多项式构成的除法电路，再加上适当的限制电路组成。适当的限制电路组成。g(x)=x4+x3+x2+1g(x)=x4+x3+x2+1时，（时，（7 7，3 3）循环码的编码电路如图循环码的编码电路如图9-29-2所示。所示。图图9-2 9-2 （7 7，3 3）循环码的编码电路）循环码的编码电路T(x)=xrm(x)+R(x)g(x)的次数等于移位寄存器的级数；的次数等于移位寄存器的级数；g(x)的的x0、x1、x2、xr 的非零系数对应移位寄存的反馈抽头。首的非零系数对应移位寄存的反馈抽头。首先，移位寄存器清零，先，移位寄存器清零，3位信息元输入时，门位信