第1章 纠错码的基本概念

1、第一章 纠错码的基本概念 第一章 纠错码的基本概念 1.1 数字通信系统的组成及信道模型数字通信系统的组成及信道模型 1.2 差错控制系统和纠错码分类差错控制系统和纠错码分类 1.3 最大似然译码和纠错码的基本概念最大似然译码和纠错码的基本概念 1.4 信道编码定理信道编码定理 第一章 纠错码的基本概念 1.1 数字通信系统的组成及信道模型数字通信系统的组成及信道模型 一、一、 数字通信系统的组成数字通信系统的组成 通信的目的：把对方不知道的消息及时、可靠地（有时还需秘密地）传送给对方 在数字通信系统中可靠与快速往往是一对矛盾 若要求快速，则必然使得每个数据码元所占的时间缩短、波形变窄、能量减

2、少，从而在受到干扰后产生错误的可能性增加，传送消息的可靠性减低。 若要求可靠， 则使得传送消息的速率变慢 因此，如何较合理地解决可靠性与速度这一对矛盾， 是正确设计一个通信系统关键问题之一。 通信理论本身(包括纠错码)也正是在解决这对矛盾中不断发展起来的。 第一章 纠错码的基本概念 图 1 - 1 数字通信系统模型第一章 纠错码的基本概念 信源编码器：把信源发出的消息转换成为二进制(或多进制)形式的信息序列，并且为了使传输有效，还去掉了一些与传输信息无关的多余度（信源编码越短越好）。信道编码器（纠错编码器）：为了抗击传输过程中的各种干扰，人为地增加多余度，使其具有自动检错或纠错能力。发射机(调

3、制器)：把纠错码送出的信息序列通过调制器变换成适合于信道传输的信号。解调器：信号变为二进制(或多进制)信息序列。信道译码器（纠错译码器）：纠正由于信道干扰而使信息序列中发生的错误。信源译码器：恢复成原来的消息送给用户。 第一章 纠错码的基本概念 我们关心的是信道编、译码器即纠错编、译码器上述模型可进一步简化为图1-2模型： 信源指原来的信源和信源编码器， 其输出是二(多)进制信息序列。 信道包括发射机、实际信道和接收机在内的广义信道(又称编码信道)， 它的输入是二(多)进制数字序列，输出一般也是二(多)进制数字序列。 信宿可以是人或计算机。 第一章 纠错码的基本概念 二、二、 信道模型信道模型

4、 现在以简化模型来讨论二进制数字序列通过该系统时所发生的情况。设从信源送出字母A，它的二进制序列为11000， 以基带信号传送， 经发射机调制后，送往信道的已调信号如图1-3所示。由于信道的干扰， 从信道输出端的信号产生了失真， 如图1-4所示。第一章 纠错码的基本概念 这些失真信号送入接收机进行判决时， 由于第一、 二、 四、 五码元的波形失真不大， 容易正确地判为1、1和0、 0； 但对第三个码元来说，由于失真严重而难于判决。这时有以下三种判决方法： 硬判决：一是勉强作出是0还是1的判决 删除符号：对该码元暂且不作判决，而输出一个未知或待定的信号“x”，称其为删除符号 软判决：第三种方法是

5、输出一种有关该码元的信息，例如关于0和1的后验概率或似然函数 当然软判决的性能较好，但实现起来较复杂。第一章 纠错码的基本概念 在二进制硬判决情况下，信道可用图1-5所示的简单模型表示。图中，p01和p10分别是0错成1和1错成0的概率， 称信道转移概率。该信道的信道转移概率矩阵可用 101001011110010011ppppppppP描述。如果p01=p10=pe，则称这种信道为二进制对称信道二进制对称信道，简称BSC。否则，称为不对称信道不对称信道。若p01或p10等于零，则称为Z信信道道。通常BSC是一种无记忆信道无记忆信道，所以也称随机信道随机信道， 它说明数据序列中出现的错误彼此无

6、关。 第一章 纠错码的基本概念 如果信道的输入是二进制符号，而输出是离散的q(qpm2)进制符号，如图1-6所示，且p(i0)p(q-1-i1)，i0， 1， q-1，则这种信道称为离散无记忆信道(DMC)，显然BSC是DMC的一种特殊情况。 DMC的信道转移概率矩阵 ) 1 |1() 1 |1 () 1 |0()0|1()0|1 ()0|0(qpppqpppP第一章 纠错码的基本概念 在作删除判决情况下，信道可用图1-7所示的模型表示， 称为二进制删除信道，简称BEC，一般它也是对称信道。图中， pe为信道的转移概率，q为删除概率。第一章 纠错码的基本概念 在有删除处理情况下， 信道的转移概

7、率pe一般很小，可忽略，因此把图1-7所示的模型用图1-8代替，称为二进制纯删除信道。以后所说的BEC都是指这种信道。应当指出，当码元作删除处理时，它在序列中的位置是已知的，仅不知其值是0还是1，故对这种BEC信道的纠错要比BSC信道容易。 第一章 纠错码的基本概念 上述三种信道模型只是为了讨论问题方便而简化成理想的情况，它们表达了某些实际信道传送信号的主要特征。例如， 卫星信道或深空信道，可近似看成是BSC。但有很多实际信道如高频、散射、有线等信道， 由于各种干扰所造成的错误， 往往不是单个地而是成群成串地出现的， 也就是一个错误的出现，往往引起其前后码元的错误(突发错误)， 表现为错误之间

8、的相关性。产生这种错误的信道称有记忆信道或突发信道。 在计算机存贮系统中，磁带的缺陷或读写头接触不良所引起的错误，也属于这种类型。第一章 纠错码的基本概念 但由于实际信道干扰的复杂性，所引起的错误往往不是单纯的一种，而是两种错误形式并存，只不过有的信道以某种错误形式为主罢了。像这种随机错误与突发错误并存的信道，称为组合信道或复合信道。 作为检错与纠错用的抗干扰码，必须针对这几类信道， 设计能纠正随机错误或纠正突发错误的码，或者设计既能纠正随机错误又能纠正突发错误的码。第一章 纠错码的基本概念 由于目前在信道中传输或计算机内部运算的数据序列， 大部分是二进制数字序列， 因此以后主要讨论二进制数字

9、通信中的纠错码，当然这些纠错码往往可以推广到q(素数或素数的幂)进制情况，这将在以后具体讨论时予以说明。 二进制情况下， 序列之间0、1两个符号按下列规则进行运算： +0 1 0 0 11 1 0模2相加 模2相乘 0 1 0 0 01 0 1 为了简便，今后用+和表示模2相加和相乘。 在模2情况下， 加和减是一回事。 第一章 纠错码的基本概念 三、三、 错误图样错误图样设发送的是n个码元长的序列C：(cn-1，cn-2，c1，c0)， 通过信道传输到达接收端(纠错码译码器输入端)的序列为R：(rn-1， rn-2，r1，r0)。由于信道中存在干扰，R序列中的某些码元可能与C序列中对应码元的值

10、不同，也就是说产生了错误。把信道中的干扰也用二进制序列E：(en-1，en-2，e1，e0)表示，则相应有错误的各位ei取值为1，无错的各位取值为0，而R就是C与E序列模2相加的结果，我们称E为信道的错误图样或干扰矢量。 例如，发送序列C：(1111100000)， 收到的序列R： (1001010000)，第二、三、五、六位产生了错误， 因此信道的错误图样E的二、 三、 五、 六位取值为1，其它各位取值为0， 即E： (0110110000)。 用式子可表示成： 第一章 纠错码的基本概念 发送序列C: 1111100000 错误图样E： 0110110000 接收序列R： 100101000

11、0 +即RC+E， 或E=R-C。 信道干扰所造成的错误可在序列中的任一位出现，且也可以在n长序列中同时出现一位、二位，甚至n位错误。因此，若发送的C序列长为n， 则信道中可能产生的错误图样E共有2n种。 若为突发信道，则在错误图样E中，第一个1与最后一个1之间的长度称为突发长度，其图样称为突发图样。在该例中，突发图样是(11011)， 突发长度为5。 第一章 纠错码的基本概念 1.2 差错控制系统和纠错码分类差错控制系统和纠错码分类 (1) 重传反馈方式(ARQ)。 应用ARQ方式纠错的通信系统如图 1 - 9所示。 发送端发出能够发现(检测)错误的码， 接收端收到通过信道传来的码后，在译码

12、器根据该码的编码规则，判决收到的码序列中有无错误产生，并通过反馈信道把判决结果用判决信号告诉发端。发端根据这些判决信号， 把接收端认为有错的消息再次传送，直到接收端认为正确接收为止。 第一章 纠错码的基本概念 图 1 - 9 ARQ通信系统 第一章 纠错码的基本概念 从上可知，应用ARQ方式必须有一反馈信道，一般较适用于一个用户对一个用户（点对点)的通信，且要求信源能够控制，系统收发两端必须互相配合、 密切协作，因此这种方式的控制电路比较复杂。由于反馈重发的次数与信道干扰情况有关，若信道干扰很频繁，则系统经常处于重发消息的状态， 因此这种方式传送消息的连贯性和实时性较差。该方式的优点是： 编译

13、码设备比较简单；在一定的多余度码元下，检错码的检错能力比纠错码的纠错能力要高得多，因而整个系统的纠错能力极强， 能获得极低的误码率；由于检错码的检错能力与信道干扰的变化基本无关，因此这种系统的适应性很强，特别适应于短波、散射、有线等干扰情况特别复杂的信道中。 第一章 纠错码的基本概念 (2) 前向纠错方式(FEC)。发送端发送能够被纠错的码，接收端收到这些码后，通过纠错译码器不仅能自动地发现错误， 而且能自动地纠正接收码字传输中的错误。优点：是不需要反馈信道，能进行一个用户对多个用户的同播通信，译码实时性较好，控制电路比ARQ的简单。缺点：是译码设备比较复杂，所选用的纠错码必须与信道的干扰情况

14、相匹配，因而对信道的适应性较差。为了要获得比较低的误码率，往往必须以最坏的信道条件来设计纠错码，故所需的多余度码元比检错码要多得多，从而使编码效率很低。但由于这种方式能同播， 特别适用于军用通信，并且随着编码理论的发展和编译码设备所需的大规模集成电路成本的不断降低，译码设备有可能做得越来越简单，成本越来越低，因而在实际的数字通信中逐渐得到广泛应用。 第一章 纠错码的基本概念 (3) 混合纠错方式(HEC)。这种方式是发送端发送的码不仅能够被检测出错误，而且还具有一定的纠错能力。接收端收到码序列以后，首先检验错误情况，如果在纠错码的纠错能力以内，则自动进行纠错。如果错误很多，超过了码的纠错能力，

15、 但能检测出来，则接收端通过反馈信道，要求发端重新传送有错的消息。 这种方式在一定程度上避免了FEC方式要求用复杂的译码设备和ARQ方式信息连贯性差的缺点，并能达到较低的误码率， 因此在实际中的应用越来越广。 第一章 纠错码的基本概念 除了上述三种主要方式以外， 还有所谓狭义信息反馈系统(IRQ)。 这种方式是接收端把收到的消息原封不动地通过反馈信道送回发送端，发送端比较发送的与反馈回来的消息，从而发现错误，并且把传错的消息再次传送，最后达到使对方正确接收消息的目的。 为了便于比较，我们把上述几种方式用图 1 - 10所示的框图表示。图中，有斜线的方框表示在该端检出错误。在实际系统设计中，如何

16、根据实际情况选择哪种差错控制方式是一个比较复杂的问题，这里不再讨论。 第一章 纠错码的基本概念 图图 1 - 10 差错控制的基本方式差错控制的基本方式 第一章 纠错码的基本概念 二、二、 纠错码的分类纠错码的分类 上述各种差错控制系统中所用到的码，不外乎是能在译码器自动发现错误的检错码，或者不仅能发现错误而且能自动纠正错误的纠错码，或者能纠正删除错误的纠删码。但这三类码之间没有明显区分，以后将看到，任何一类码，按照译码方法不同， 均可作为检错码、 纠错码或纠删码来使用。 除了上述的划分方法以外， 通常还按以下方式对纠错码进行分类： 第一章 纠错码的基本概念 (1) 按照对信息元处理方法的不同

17、， 分为分组码与卷积码两大类。 分组码分组码是把信源输出的信息序列，以k个码元划分为一段， 通过编码器把这段k个信息元按一定规则产生r个校验(监督)元， 输出长为nk+r的一个码组。因此每一码组的校验元仅与本组的信息元有关，而与别组无关。分组码用(n，k)表示，n表示码长，k表示信息位。 卷积码卷积码是把信源输出的信息序列，以k0个(k0通常小于k)码元分为一段，通过编码器输出长为n0(k0)一段的码段。 但是该码段的n0-k0个校验元不仅与本组的信息元有关，而且也与其前m段的信息元有关，称m为编码存贮。因此卷积码用(n0，k0，m)表示。 第一章 纠错码的基本概念 (2) 根据校验元与信息元

18、之间的关系分为线性码与非线性码。 若校验元与信息元之间的关系是线性关系(满足线性叠加原理)， 则称为线性码; 否则，称为非线性码。 由于非线性码的分析比较困难， 实现较为复杂， 故今后我们仅讨论线性码。 (3) 按照纠正错误的类型可分为纠正随机(独立)错误的码、 纠正突发错误的码和纠正同步错误的码，以及既能纠正随机错误又能纠正突发错误的码。 第一章 纠错码的基本概念 (4) 按照每个码元取值来分， 可分为二进制码与q进制码(q=pm，p为素数，m为正整数)。 (5) 按照对每个信息元保护能力是否相等可分为等保护纠错码与不等保护(UEP)纠错码。除非特别说明，今后讨论的纠错码均指等保护能力的码。

19、此外，在分组码中按照码的结构特点， 又可分为循环码与非循环码。为了清楚起见，我们把上述分类用图 1 - 11表示。 第一章 纠错码的基本概念 图 1 - 11 纠错码分类 第一章 纠错码的基本概念 1.3 最大似然译码和纠错码的基本概念最大似然译码和纠错码的基本概念 一、一、 基本定义基本定义 利用纠错码进行差错控制的数字通信系统如图 1 - 12所示， 由此可如下定义分组码。 定义定义1.3.1 分组码是对每段k位长的信息组，以一定规则增加r=n-k个校验元，组成长为n的序列：(cn-1，cn-2，c1，c0)，称这个序列为码字(码组、码矢)。在二进制情况下，信息组总共有2k(q进制为qk)

20、个，因此通过编码器后，相应的码字也有2k个，称这2k个码字集合为(n，k)分组码。 第一章 纠错码的基本概念 图 1 - 12 利用分组码的数字通信模型第一章 纠错码的基本概念 n长序列的可能排列总共有2n种(每一n长序列称为n重)，而(n，k)分组码的码字集合只有2k种。所以，分组码的编码问题就是定出一套规则，以便从2n个n重中选出2k个码字，不同的选取规则就得到不同的码。我们称被选取的2k个n重为许用码组， 其余的2n-2k个为禁用码组。 称Rkn为码率，表示(n，k)分组码中，信息位在码字中所占的比重。R是衡量分组码有效性的一个基本参数。 第一章 纠错码的基本概念 图 1 - 13是一个

21、(2, 1, 2)卷积码编码器。若输入的信息序列以k01个码元分段输入，则输出以n02个码元为一段输出， 如输入的信息序列M(1 1 0 1 0 0)，输出的码序列为C(11， 10，10， 00， 01， 11， 00， )。可知随着信息元的不断输入，输出的是一个半无限长的码序列，由此可如下定义卷积码。 第一章 纠错码的基本概念 定义定义1.3.2 (n0，k0，m)卷积码是对每段k0长的信息组以一定的规则增加r0n0-k0个校验元，组成长为n0的码段。 n0-k0个校验元不仅与本段的信息元有关，且与前m段的信息元有关，当信息元不断输入时，输出的码序列是一个半无限长序列。 (n0，k0，m)

22、卷积码的码率Rk0 n0 。与分组码的码长n相对应，在卷积码中称ncn0(m+1)为编码约束长度，说明k0个信息元从输入编码器到离开时在码序列中影响的码元数目，如图 1 - 13中(2，1，2)卷积码的nc 6。 第一章 纠错码的基本概念 二、二、 最大似然译码最大似然译码 由图1-2可知，信道输出的R是一个二(或q)进制序列，而译码器的输出是一个信息序列M的估值序列 。 译码器的基本任务就是根据一套译码规则，由接收序列R给出与发送的信息序列M最接近(最好是相同)的估值序列 。由于M与码字C之间存在一一对应关系，所以这等价于译码器根据R产生一个C的估值序列 。显然，当且仅当 C时， M，这时译

23、码器正确译码。 MMCMC第一章 纠错码的基本概念 如果译码器输出的 C，则译码器产生了错误译码。之所以产生错误译码是由于：信道干扰很严重， 超过了码本身的纠错能力；其次，由于译码设备的故障(这点本书不予讨论)。当给定接收序列R时，译码器的条件译码错误概率定义为 C)|()|(RCCPREP所以译码器的错误译码概率 RERPREPP)()|(第一章 纠错码的基本概念 P(R)是接收R的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则是使 )|(max)|(min)|(min)|(minminRCCPRCCPRCCPREPPRRE因此，如果译码器对输入的R，能在2k个码字中选择一个使 最

24、大的码字Ci作为C的估值序列 ，则这种译码规则一定使译码器输出错误概率最小，称这种译码规则为最大后验概率译码。 )2 , 2 , 1)(|(kiiRCCPC（1.3.1）第一章 纠错码的基本概念 由贝叶斯公式 )()|()()|(RPCRPCPRCPiii可知，若发端发送每个码字的概率P(Ci)均相同，且由于P(R)与译码方法无关，所以 kkiiiiCRPRCP2, , 2, 12, , 2, 1)|(max)|(max对DMC而言njijiicrPCRP1)|()|(（1.3.2）（1.3.3）这里码字Ci(ci1，ci2，cin)，i1，2， ，2k。 第一章 纠错码的基本概念 一个译码器

25、的译码规则若能在2k个码字C中选择某一个Ci使式(1.3.2)成为最大，则这种译码规则称为最大似然译码(MLD)，P(RC)称为似然函数，相应的译码器称为最大似然译码器。由于logbx与x是单调关系，因此式(1.3.2)与式(1.3.3)可写成 njijibiibicrpCRPkk12, 2, 12, 2, 1)|(logmax)|(logmax称logb P(RC)为对数似然函数或似然函数。对于DMC信道， MLD是使译码错误概率最小的一种最佳译码准则或方法，但此时要求发端发送每一码字的概率P(Ci)(i1，2，,2k)均相等，否则MLD不是最佳的。 在以后的讨论中，都认为P(Ci)均近似相

26、等。 第一章 纠错码的基本概念 三、三、 汉明汉明(Hamming)距离与重量距离与重量 定义1.3.3 两个n重x、y之间，对应位取值不同的个数，称为它们之间的汉明距离，用d(x，y)表示。 例如，若x:(10101)，y： (01111)，则d(x，y)3 。 定义定义1.3.4 n重x中非零码元的个数，称为它的汉明重量， 简称重量，用w(x)表示。 例如，若x： (10101)，则w(x)3。若y： (01111)，则w(y)4，等等。 第一章 纠错码的基本概念 定义定义 1.3.5 (n，k)分组码中，任两个码字之间距离的最小值， 称为该分组码的最小汉明距离d0，简称最小距离 例如(3

27、,2)码，n3，k2，共有224个码字：000，011， 101，110，显然d02。 d0是(n，k)分组码的另一个重要参数。它表明了分组码抗干扰能力的大小。以后将看到： d0越大，码的抗干扰能力越强， 在同样译码方法下它的译码错误概率越小。由上可知，R和d0是(n，k)分组码的两个最重要参数。纠错编码的基本任务之一就是构造出R一定、 d0尽可能大的码，或d0一定、R尽可能高的码。 下面用几个具体例子说明码的R、d0以及译码错误概率之间的关系。 0,( , )min ( , )x yn kdd x y第一章 纠错码的基本概念 例例1.1 重复码 重复码是k1的(n，1)码，它的编码规则(即在

28、2n个n重中挑选2k21 个码字的规则)是(n-1)个校验元是信息元的重复，设信息元为cn-1，则校验元cicn-1(i=0，1，2，n-2)。 由于信息组只有2k2组：0和1，因此相应的许用码字只有两个(000)和(111)。设它们通过BSC传输，信道的转移概率为pe。 通常情况下，pe0.5，因此在传输中没有错误的可能性比出现一个错误的可能性大，出现一个错误的可能性比出现两个错误的大，等等。也就是说信道错误图样E中，出现重量最轻的图样可能性最大。 第一章 纠错码的基本概念 P(w(E)0)P(w(E)1)P(w(E)2)或 221)1 ()1 ()1 (neeneeneppppp 由ER-

29、C及式(1.3.2)可知，MLD译码器寻求可能出现的错误图样，就是由接收到的R在2k个码字集中，寻求与R的汉明距离最小的码字Ci，为最可能发送的码字而接收，这就是最小汉明距离译码(或称最近临区译码)。(试证明：在DMC中，最小汉明距离译码就是MLD。)在重复码情况下这种译码方案就是根据收到序列中0和1的多少，来判断信息组是0还是1。若接收序列中1的个数大于n2，则判为1；否则，判为0。这种译码方案就是大数准则译码。 第一章 纠错码的基本概念 当n是奇数时，按照这种大数准则译码方法，译码器总可以很快地作出是0还是1的判决。当n是偶数时可能出现以下情况， 即接收序列中“1”的个数和“0”的个数刚好

30、相等，此时若按大数准则无法作出判断，造成译码失败，这种译码称为不完备译码。 而n为奇数情况下的译码(即译码器一定作出是哪一个信息组的判决)称为完备译码。 译码失败只表明译码器无法给出明确判断， 但并不等于译码错误，而仅表明接收序列中存在有错误。此时， 如果我们与ARQ系统相结合，则可以利用此信息要求对方重发该组信息，直到译码器作出明确判决为止。 下面几个具体例子说明重复码的抗干扰能力。 第一章 纠错码的基本概念 (1) (1，1)码。这种码n1，k1，d1，R1，显然无任何抗干扰能力。设BSC中的pe0.1，则这种码的误码率仍为0.1。 (2) (2，1)重复码。该重复码的两个许用码字是(00

31、)和(11)， d02，R12。若用不完备译码(并与ARQ结合)则译码错误概率为p2e10-2。也就是说只有当(00)错成(11)或(11)错成(00)时， 才造成译码错误。 而(01)和(10)不是许用码字，不会造成译码错误。因此，这个码能发现传输中的一个错误，但不能自动纠正。 第一章 纠错码的基本概念 (3) (3，1)重复码。显然，它的两个码字是(000)和(111)，d03，R13。设发的是(000)，若收到的是(001)或(010)或(100)， 则根据大数译码准则正确地判为(000)，信息组为0。若收到的是(011)，(101)，(110)，(111)中之一，则造成译码错误， 错判

32、为信息组是1。因此，该码若用完备译码能纠正序列中的一个错误， 此时译码错误概率p1-Q1-(1-pe)3+3pe(1- pe)2=2.810-2也就是误码率由0.1减至2.810-2。 若该码不用作纠错，而采用不完备译码用作检错， 则可以发现两个错误，与ARQ系统结合后，译码错误概率减至p3e10-3。 第一章 纠错码的基本概念 (4) (4，1)重复码。显然，该码的d04，R14。由于n是偶数，故只能采取不完备译码。它的纠错能力如下： 能纠正一个错误同时发现两个错误。 若发送的是(0000)， 则错一个时，根据大数准则可正确判断发送的是0信息组。 若错两个变成(0011)，(1100)，(1

33、010)， (0101)， (1001)， (0110)之一时， 则译码器无法作出判决，而指出发生了两个错误。 仅在变成(1110)， (0111)， (1011)， (1101)和(1111)时， 译码器才作出错误译码。 因此， 这时的译码错误概率 434106 . 3)1 (4eeepppp第一章 纠错码的基本概念 若仅用来检错，则可检测ed0-13个错误。显然，若发送的是(0000)， 则仅在变成(1111)时，才产生错误译码，而其它情况均能正确译码或发现错误。因此，此时的译码错误概率pp4e10-4。 第一章 纠错码的基本概念 (5) (5，1)重复码。(5，1)码的d05，R15。它

34、的纠错能力如下： 能纠正两个随机错误， 这时的译码错误概率 33245107993. 01)1 (25)1 (15)1(1eeeeepppppp 因此，传送信息组0、1的错误概率从0.1降至千分之七， 约降低了两个量级。 第一章 纠错码的基本概念 若仅用来检错，则能发现ed0-14个错误。若与ARQ系统结合进行纠错，则译码错误概率大约为pp5e10-5。 由上面有关重复码的一系列例子可以看到： (1) 随着码长n的增加，重复码的d0n越来越大，抗干扰能力越来越强，即dn1，误码率也越来越小，但码率R1n却越来越低，并随着n的增加而趋近于零。 (2) 在用同样的(n，k)码下，应用非完备译码并与

35、ARQ系统相结合，译码器所给出的误码率比完备译码所产生的要低得多。 通过上面这些例子还可看出，(n，k)分组码的最小距离d0(今后简称d)与纠错能力有如下关系。 第一章 纠错码的基本概念 定理定理1.3.1 任一(n，k)分组码，若要在码字内： (1) 检测e个随机错误， 则要求码的最小距离de+1； (2) 纠正t个随机错误，则要求d2t+1; (3) 纠正t个随机错误，同时检测e(t)个错误，则要求dt+e+1。 (4) 纠正t个错误和个删除，则要求d2t+1。 证明(1)由图1-14(a)可知，若C1发生了e个错误变为C1， 则d(C1， C1)e，设ed-1，则d(C1 ，C2)1，故

36、C1 C2，因此译码器不会将C1错判成C2，检测到e=d-1个错误。 第一章 纠错码的基本概念 图 1 - 14 纠错码纠错能力的几何解释 第一章 纠错码的基本概念 (2) 设C1与C2是(n，k)码中任两码字距离之最小者，且为2t+1。 则C1错了t个错误以后变成C1，它们之间的距离d(C1，C1)=t， 但d(C1，C2)t+1。d(C1，C2)d(C1，C1)，如图 1-14(b)所示，所以译码器可以根据它们之间的距离的大小正确译码， 从而纠正t个错误。 (3) 这里所指的同时，是当错误个数t时，该码能纠正t个错；当错误个数大于t而小于e时，则码能发现e个错误。 由(1)和(2)的证明可

37、直接得到结论(3)， 请读者自行证明。 由此定理可知，一个距离为d的分组码，至多能纠正t(d-1)2(x是x的整数部分)个错误。该定理确定了码的纠错能力与它的距离之间的关系，是纠错码理论中最基本的定理之一。 第一章 纠错码的基本概念 例例1.2 奇偶校验(监督)码 奇偶校验码是只有一个校验元的(n， n-1)分组码。 设给定kn-1位的二进制信息码组为:mk-1，mk-2，m1，m0，则按如下规则完成码中一个码字(cn-1，cn-2，c1，c0)的编码：cn-1mk-1，cn-2mk-2，c2m1，c1m0，而一个校验元c0mk-1+mk-2+m1+m0或mk-1+mk-2+m1+m0 +c0

38、0cn-1+cn-2+c1+c00 (1.3.5)该式保证每个码字中“1”的个数为偶数，所以称这种校验关系为奇偶校验。由于分组码中的每一个码字均按同一规则构成，故称这种分组码为一致校验码。显然，码中的码字数目M2k2n-1。 第一章 纠错码的基本概念 (1) (2，1)奇偶校验码。此码的n=2，k1，按c1+c00求出校验元c0=c1，所以两个许用码组是00和11，此时d2，R12，能发现一个错误。若在pe0.1的BSC中传送，则利用不完备译码并与ARQ相结合，可使误码率大约减至p10-2。 (2) (3，2)码。此码有224个信息组，由式(1.3.5)求得校验元，得到相应的4个码字为：000

39、， 011，101，110。由此看出， 这4个信息组就是在8个二进制三重中，把重量为偶数的4个三重挑选为许用码字，重量为奇数的其它4个为禁用码组。显然，该码的d2，也只能发现码元中的一个错误。译码误码率大约为 32R22107 . 2)1 (23eepPp第一章 纠错码的基本概念 (3) (4，3)码。该码的8个码字是按照式(1.3.5)的要求，在16个二进制四重中挑选出来的，其重量均为偶数。该码的d2， R34，故只能检测码字中的一位错误。其译码误码率约为 。 由上看出，(n，n-1)奇偶校验码。当它的n时，R1，但d2，dn0，译码误码率ppe，接近未编码时的情况。 即随着码长的增加，抗干

40、扰能力接近于零。 上述(n，1)和(n，n-1)码，随着码长n的增加，前者R0， 后者抗干扰能力接近于零，或dn0，都不理想。那么是否存在有一种码，随着n的增加。其纠错能力和传信率都保持一定呢？换言之，在R一定时，随着n，dn0，从而使p0的码是否存在？1949年香农(Shannon)的信道编码定理对此作了肯定的回答。 2432105)1 (24eeepppp第一章 纠错码的基本概念 1.4 信道编码定理信道编码定理 信道编码定理 每个信道具有确定的信道容量C，对任何小于C的码率R，存在有速率为R码长为n的分组码及(n0，k0，m)卷积码，若用最大似然译码，则随着码长的增加其译码错误概率p可任

41、意小， 即 )(RnEbbeAp和 )()()1(0REncREnmcccceAeAp(1.4.1) 第一章 纠错码的基本概念 式中，Ab和Ac为大于0的系数，Eb(R)和Ec(R)为正实函数，称为误差指数，它与R、C的关系如图1 - 15所示。图中，C1、C2为信道容量，且C1C2。由信息论的基本知识可知，在高斯白噪声信道时， 信道容量 )/(1log02sbitWNPWCS式中，W是信道所能提供的带宽，PSEST是信号功率，ES是信号能量，T是分组码信号的持续时间即信号宽度，PSW是单位频带的信号功率，N0是单位频带的噪声功率， PS (WN0)是信噪比。 第一章 纠错码的基本概念 由式(

42、1.4.1)和图 1-15可看出，信道容量C、码长n和错误概率p之间的转换关系。为了满足一定误码率p的要求，可用以下两类方法实现。 一是增加信道容量C，从而使E(R)增加。由C的表示式(1.4.2)可知，增加C的方法可以采用如加大系统带宽或增加信噪比的方法来达到。例如，采用调频、调相等宽带调制方法； 增加发射机的功率；应用高增益天线；采用分集接收及低噪声器件等方法。这些措施是从根本上改善信道、增加信道容量、减少误码率的方法， 是通信设计工作者经常采用的传统方法。 第一章 纠错码的基本概念 图 1-15 信道容量C、码长n和错误概率p之间的转换关系第一章 纠错码的基本概念 另一种方法是在R一定下，增加分组码长n(也就是增加分组信号持续时间T)，可使p随n的增加而呈指数下降。 但由于码长n的增加，当R保持一定时，可能发送的码字数2k指数增加， 从而增加了译码设备的复杂性。这种方法就是信道编码定理所指出减少误码率的另一方向，它为通信设计工作者提供了一条新的途径。下面通过几个具体例子说明R保持一定时，随着n的增加，可使p下降。 第一章 纠错码的基本概念 例例1.3 设有一个随机产生二进制序列的信源和一个转移概率pe0.1的BSC。如果不编码，则传送