《《纠错码的基本概念》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《纠错码的基本概念》PPT课件.ppt（76页珍藏版）》请在三一办公上搜索。
1、1,现代编码技术刘原华,2,课程性质：学位课课程课时：48（3学分）考试形式：闭卷（平时成绩30%、试卷成绩70%）参考书目：纠错码-原理与应用 王新梅等无线通信调制与编码 王军选等其它编码类书籍,3,课程内容什么是编码为什么要编码编码的应用教学安排编码基础（3学时）代数基础（3学时）线性分组码（15学时）卷积码以及应用（15学时）Turbo码以及应用（3学时）LDPC编码（6学时）,4,第一章 纠错码的基本概念,1.1 数字通信系统的组成及信道模型 1.2 差错控制系统和纠错码分类 1.3 最大似然译码和纠错码的基本概念 1.4 信道编码定理,5,1.1 数字通信系统的组成及信道模型,一、数
2、字通信系统的组成 通信的目的是要把对方不知道的消息及时可靠地(有时还须秘密地)传送给对方。如何较合理地解决可靠性与速度这一对矛盾，是正确设计一个通信系统关键问题之一。通信理论本身(包括纠错码)也正是在解决这对矛盾中不断发展起来的。,6,图 1-1 数字通信系统模型,7,信源：产生消息和消息序列的来源。消息可以是离散的，也可以是连续的（数据、文字、语言、图像），通常信源的消息序列是随机发生的，因此要用随机变量来描述。信源编码器：将信源的输出进行适当的变换，转换成为二进制(多进制)形式的信息序列，以提高信息传输的有效性。信道编码器：对信源编码器的输出进行变换，用增加多余度的方法提高信道的抗干扰能力
3、，以提高信息传输的可靠性。调制器：将信道编码器输出的数字序列变换为振幅、频率或相位受到调制控制的形式，以适合在信道中进行较长距离的传输。,8,信道：信号由发送端传输到接收端的媒介。典型的传输信道有明线、电缆、高频无线信道、微波通道和光纤通道等；典型的存储媒介有磁芯、磁鼓、磁盘、磁带等。噪声源：对传输信道或存储媒介构成干扰的来源的总称。干扰和噪声往往具有随机性，所以信道的特征也可以用概率空间来描述；而噪声源的统计特性又是划分信道的依据：加性干扰，它是由外界原因产生的随机干扰，它与信道中传送的信号的统计特性无关，因而信道的输出是输入和干扰的叠加乘性干扰：信道的输出信号可看成输入信号和一个时变参量相
4、乘的结果,9,解调器：从载波中提取信号，变成二进制(或多进制)信息序列，是调制的逆过程。信道译码器：利用信道编码时所提供的多余度，检查或纠正数字序列中的错误。信源译码器：把经过信道译码器核对过的信息序列恢复成原来的消息。信宿：消息传送的对象（人或机器）,10,编码信道,等效离散信源,等效信宿,信道编码器,信道译码器,我们关心的是图中的信道编、译码器即纠错编、译码器两个方框，为了研究方便，将上述模型再进一步简化。,11,图 1-2 数字通信系统简化模型,12,二、信道模型 现在以图1-2的模型来讨论二进制数字序列通过该系统时所发生的情况。设从信源送出字母A，它的二进制序列为11000，以基带信号
5、传送，经发射机调制后，送往信道的已调信号如图 1-3所示。由于信道的干扰，从信道输出端的信号产生了失真，如图 1-4所示。对第三个码元来说，由于失真严重而难于判决。这时有以下三种判决方法：一是勉强作出是0还是1的判决，即所谓硬判决；另一种是对该码元暂且不作判决，而输出一个未知或待定的信号“x”，称其为删除符号；第三种方法是输出一种有关该码元的信息，例如关于0和1的后验概率或似然函数，这种作法称为软判决。,13,图 1 3 11000发送的已调信号波形,图 1-4 接收端收到的失真信号波形,14,在二进制硬判决情况下，信道可用图 1-5所示的简单模型表示。图中，p01和p10分别是0错成1和1错
6、成0的概率，称信道转移概率。该信道的信道转移概率矩阵可用,描述。如果p01=p10=pe，则称这种信道为二进制对称信道，简称BSC。否则，称为不对称信道。若p01或p10等于零，则称为Z信道。通常BSC是一种无记忆信道，所以也称随机信道，它说明数据序列中出现的错误彼此无关。,15,如果信道的输入是二进制符号，而输出是离散的q(qpm2)进制符号，如图 1-6所示，且p(i0)p(q-1-i1)，i0，1，q-1，则这种信道称为离散无记忆信道(DMC)，显然BSC是DMC的一种特殊情况。DMC的信道转移概率矩阵,16,图 1 5 二进制信道,17,图 1-6 DMC信道,18,在作删除判决情况下
7、，信道可用图 1-7所示的模型表示，称为BEC，一般它也是对称信道。图中，pe为信道的转移概率，q为删除概率，在有删除处理情况下，信道的转移概率pe一般很小，可忽略，因此把图1-7所示的模型用图 1-8代替，称为二进制纯删除信道。以后所说的BEC都是指这种信道。应当指出，当码元作删除处理时，它在序列中的位置是已知的，仅不知其值是0还是1，故对这种BEC信道的纠错要比BSC信道容易。,19,图 1-7 二进制删除信道,20,图 1-8 二进制纯删除,21,上述三种信道模型只是为了讨论问题方便而简化成理想的情况，它们表达了某些实际信道传送信号的主要特征。但有很多实际信道如高频、散射、有线等信道，由
8、于各种干扰所造成的错误，往往不是单个地而是成群成串地出现的，表现为错误之间的相关性。产生这种错误的信道称有记忆信道或突发信道。作为检错与纠错用的抗干扰码，必须针对这几类信道，设计能纠正随机错误或纠正突发错误的码，或者设计既能纠正随机错误又能纠正突发错误的码。,22,由于目前在信道中传输或计算机内部运算的数据序列，大部分是二进制数字序列，因此以后主要讨论二进制数字通信中的纠错码。二进制情况下，序列之间0、1两个符号按下列规则进行运算：,0 1,0 0 11 1 0,模2相加,模2相乘,为了简便，今后用+和表示模2相加和相乘。在模2情况下，加和减是一回事。,23,三、错误图样设发送的码序列是C：(
9、cn-1，cn-2，c1，c0)，到达接收端的序列为R：(rn-1，rn-2，r1，r0)。由于信道中存在干扰，R序列中产生了错误。如果把干扰也用二进制序列E：(en-1，en-2，e1，e0)表示，则相应有错误的各位ei取值为1，无错的各位取值为0，而R就是C与E序列模2相加的结果，我们称E为信道的错误图样或干扰矢量。例如，发送序列C：(1111100000)，收到的序列R：(1001010000)，第二、三、五、六位产生了错误，因此信道的错误图样E的二、三、五、六位取值为1，其它各位取值为0，即E：(0110110000)。用式子可表示成：,24,即RC+E，或E=R-C。,若C序列长为n
10、，则信道中可能产生的错误图样E共有2n种。若为突发信道，则在错误图样E中，第一个1与最后一个1之间的长度称为突发长度，其图样称为突发图样。在该例中，突发图样是(11011)，突发长度为5。,25,1.2 差错控制系统和纠错码分类,(1)重传反馈方式(ARQ)。如图1-9所示。,图 1-9 ARQ通信系统,26,应用ARQ方式必须有一反馈信道，一般较适用于一个用户对一个用户（点对点)的通信。缺点：控制电路比较复杂；连贯性和实时性较差。优点：编译码设备比较简单；纠错能力极强，能获得极低的误码率；信道适应性很强。,27,(2)前向纠错方式(FEC)。如图 1-2所示。,28,优点：不需要反馈信道，能
11、进行一个用户对多个用户的同播通信，译码实时性较好，控制电路比ARQ的简单。缺点：译码设备比较复杂；对信道的适应性较差；编码效率很低。但由于这种方式能同播，特别适用于军用通信，并且随着编码理论的发展和大规模集成电路成本的不断降低，译码设备有可能做得越来越简单，成本越来越低，因而在实际的数字通信中逐渐得到广泛应用。,29,(3)混合纠错方式(HEC)。这种方式是发送端发送的码不仅能够被检测出错误，而且还具有一定的纠错能力。接收端收到码序列以后，首先检验错误情况，如果在纠错码的纠错能力以内，则自动进行纠错。如果错误很多，超过了码的纠错能力，但能检测出来，则接收端通过反馈信道，要求发端重新传送有错的消
12、息。这种方式在一定程度上避免了FEC方式要求用复杂的译码设备和ARQ方式信息连贯性差的缺点，并能达到较低的误码率，因此在实际中的应用越来越广。,30,除了上述三种主要方式以外，还有所谓狭义信息反馈系统(IRQ)。这种方式是接收端把收到的消息原封不动地通过反馈信道送回发送端，发送端比较发送的与反馈回来的消息，从而发现错误，并且把传错的消息再次传送，最后达到使对方正确接收消息的目的。为了便于比较，我们把上述几种方式用图 1-10所示的框图表示。图中，有斜线的方框表示在该端检出错误。,31,图 1-10 差错控制的基本方式,32,二、纠错码的分类 上述各种差错控制系统中所用到的码，不外乎是能在译码器
13、自动发现错误的检错码，或者不仅能发现错误而且能自动纠正错误的纠错码，或者能纠正删除错误的纠删码。但这三类码之间没有明显区分，以后将看到，任何一类码，按照译码方法不同，均可作为检错码、纠错码或纠删码来使用。除了上述的划分方法以外，通常还按以下方式对纠错码进行分类：,33,(1)按照对信息元处理方法的不同，分为分组码与卷积码两大类。分组码是把信源输出的信息序列，以k个码元划分为一段，通过编码器把这段k个信息元按一定规则产生r个校验(监督)元，输出长为nk+r的一个码组。因此每一码组的校验元仅与本组的信息元有关，而与别组无关。分组码用(n，k)表示，n表示码长，k表示信息位。卷积码是把信源输出的信息
14、序列，以k0个(k0通常小于k)码元分为一段，通过编码器输出长为n0(k0)一段的码段。但是该码段的n0-k0个校验元不仅与本组的信息元有关，而且也与其前m段的信息元有关，称m为编码存贮。因此卷积码用(n0，k0，m)表示。,34,(2)根据校验元与信息元之间的关系分为线性码与非线性码。若校验元与信息元之间的关系是线性关系(满足线性叠加原理)，则称为线性码；否则，称为非线性码。由于非线性码的分析比较困难，实现较为复杂，故今后我们仅讨论线性码。(3)按照纠正错误的类型可分为纠正随机(独立)错误的码、纠正突发错误的码和纠正同步错误的码，以及既能纠正随机错误又能纠正突发错误的码。,35,(4)按照每
15、个码元取值来分，可分为二进制码与q进制码(q=pm，p为素数，m为正整数)。(5)按照对每个信息元保护能力是否相等可分为等保护纠错码与不等保护(UEP)纠错码。除非特别说明，今后讨论的纠错码均指等保护能力的码。此外，在分组码中按照码的结构特点，又可分为循环码与非循环码。为了清楚起见，我们把上述分类用图 1-11表示。,36,图 1-11 纠错码分类,37,1.3 最大似然译码和纠错码的基本概念,一、基本定义 利用纠错码进行差错控制的数字通信系统如图 1-12所示，由此可如下定义分组码。定义1.3.1 分组码是对每段k位长的信息组，以一定规则增加r=n-k个校验元，组成长为n的序列：(cn-1，
16、cn-2，c1，c0)，称这个序列为码字(码组、码矢)。在二进制情况下，信息组总共有2k(q进制为qk)个，因此通过编码器后，相应的码字也有2k个，称这2k个码字集合为(n，k)分组码。,38,图 1-12 利用分组码的数字通信模型,39,n长序列的可能排列总共有2n种(每一n长序列称为n重)，而(n，k)分组码的码字集合只有2k种。所以，分组码的编码问题就是定出一套规则，以便从2n个n重中选出2k个码字，不同的选取规则就得到不同的码。我们称被选取的2k个n重为许用码组，其余的2n-2k个为禁用码组。称Rkn为码率，表示(n，k)分组码中，信息位在码字中所占的比重。R是衡量分组码有效性的一个基
17、本参数。,40,图 1-13是一个(2,1,2)卷积码编码器。若输入的信息序列以k01个码元分段输入，则输出以n02个码元为一段输出，如输入的信息序列M(1 1 0 1 0 0)，输出的码序列为C(11，10，10，00，01，11，00，)。可知随着信息元的不断输入，输出的是一个半无限长的码序列，由此可如下定义卷积码。,图 1-13 一个(2，1，2)卷积码编码器,41,定义(n0，k0，m)卷积码是对每段k0长的信息组以一定的规则增加r0n0-k0个校验元，组成长为n0的码段。n0-k0个校验元不仅与本段的信息元有关，且与前m段的信息元有关，当信息元不断输入时，输出的码序列是一个半无限长序
18、列。(n0，k0，m)卷积码的码率Rk0 n0。与分组码的码长n相对应，在卷积码中称ncn0(m+1)为编码约束长度，说明k0个信息元从输入编码器到离开时在码序列中影响的码元数目，如图 1-13中(2，1，2)卷积码的nc 6。,42,二、最大似然译码 由图1-2可知，信道输出的R是一个二(或q)进制序列，而译码器的输出是一个信息序列M的估值序列。译码器的基本任务就是根据一套译码规则，由接收序列R给出与发送的信息序列M最接近(最好是相同)的估值序列。由于M与码字C之间存在一一对应关系，所以这等价于译码器根据R产生一个C的估值序列。显然，当且仅当CC时，M，这时译码器正确译码。,43,如果译码器
19、输出的 C，则译码器产生了错误译码。之所以产生错误译码是由于：信道干扰很严重，超过了码本身的纠错能力；其次，由于译码设备的故障(这点本书不予讨论)。当给定接收序列R时，译码器的条件译码错误概率定义为,所以译码器的错误译码概率,44,P(R)是接收R的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则是使,因此，如果译码器对输入的R，能在2k个码字中选择一个使 最大的码字Ci作为C的估值序列，则这种译码规则一定使译码器输出错误概率最小，称这种译码规则为最大后验概率译码。,（）,45,由贝叶斯公式,可知，若发端发送每个码字的概率P(Ci)均相同，且由于P(R)与译码方法无关，所以,对DMC而
20、言,（）,（）,这里码字Ci(ci1，ci2，cin)，i1，2，2k。,46,一个译码器的译码规则若能在2k个码字C中选择某一个Ci使式(1.3.2)成为最大，则这种译码规则称为最大似然译码(MLD)，P(R|C)称为似然函数，相应的译码器称为最大似然译码器。由于logbx与x是单调关系，因此式(1.3.2)与式(1.3.3)可写成,称logbP(R|C)为对数似然函数或似然函数。对于DMC信道，MLD是使译码错误概率最小的一种最佳译码准则或方法，但此时要求发端发送每一码字的概率P(Ci)(i1，2，,2k)均相等，否则MLD不是最佳的。在以后的讨论中，都认为P(Ci)均近似相等。,47,三
21、、汉明(Hamming)距离与重量 定义1.3.3 两个n重x、y之间，对应位取值不同的个数，称为它们之间的汉明距离，用d(x，y)表示。例如，若x:(10101)，y:(01111)，则d(x，y)3。定义 n重x中非零码元的个数，称为它的汉明重量，简称重量，用w(x)表示。例如，若x:(10101)，则w(x)3。若y:(01111)，则w(y)4，等等。,48,定义(n，k)分组码中，任两个码字之间距离的最小值，称为该分组码的最小汉明距离d0，简称最小距离 例如(3,2)码，n3，k2，共有224个码字：000，011，101，110，显然d02。d0是(n，k)分组码的另一个重要参数。
22、它表明了分组码抗干扰能力的大小。以后将看到：d0越大，码的抗干扰能力越强，在同样译码方法下它的译码错误概率越小。由上可知，R和d0是(n，k)分组码的两个最重要参数。纠错编码的基本任务之一就是构造出R一定、d0尽可能大的码，或d0一定、R尽可能高的码。下面用几个具体例子说明码的R、d0以及译码错误概率之间的关系。,49,例1.1 重复码 重复码是k1的(n，1)码，它的编码规则是(n-1)个校验元是信息元的重复，设信息元为cn-1，则校验元cicn-1(i=0，1，2，n-2)。由于k1，相应的许用码字只有2k2个(000)和(111)。设它们通过BSC传输，信道的转移概率为pe。通常情况下，
23、pe0.5，因此在传输中没有错误的可能性比出现一个错误的可能性大，出现一个错误的可能性比出现两个错误的大，等等。也就是说信道错误图样E中，出现重量最轻的图样可能性最大。,50,P(w(E)0)P(w(E)1)P(w(E)2),或,由ER-C及式(1.3.2)可知，MLD译码器寻求与R的汉明距离最小的码字Ci，为最可能发送的码字而接收，这就是最小汉明距离译码。在重复码情况下这种译码方案就是根据收到序列中0和1的多少，来判断信息组是0还是1。若接收序列中1的个数大于n2，则判为1；否则，判为0。这种译码方案就是大数准则译码。,51,当n是奇数时，按照这种大数准则译码方法，译码器总可以很快地作出是0
24、还是1的判决。当n是偶数时可能出现以下情况，即接收序列中“1”的个数和“0”的个数刚好相等，此时若按大数准则无法作出判断，造成译码失败，这种译码称为不完备译码。而n为奇数情况下的译码(即译码器一定作出是哪一个信息组的判决)称为完备译码。译码失败只表明译码器无法给出明确判断，但并不等于译码错误，而仅表明接收序列中存在有错误。此时，如果我们与ARQ系统相结合，则可以利用此信息要求对方重发该组信息，直到译码器作出明确判决为止。下面几个具体例子说明重复码的抗干扰能力。,52,(1)(1，1)码。这种码n1，k1，d1，R1，显然无任何抗干扰能力。设BSC中的pe0.1，则这种码的误码率仍为0.1。(2
25、)(2，1)重复码。该重复码的两个许用码字是(00)和(11)，d02，R12。若用不完备译码(并与ARQ结合)则译码错误概率为p2e10-2。也就是说只有当(00)错成(11)或(11)错成(00)时，才造成译码错误。而(01)和(10)不是许用码字，不会造成译码错误。因此，这个码能发现传输中的一个错误，但不能自动纠正。,53,(3)(3，1)重复码。显然，它的两个码字是(000)和(111)，d03，R13。设发的是(000)，若收到的是(001)或(010)或(100)，则根据大数译码准则正确地判为(000)，信息组为0。若收到的是(011)，(101)，(110)，(111)中之一，则
26、造成译码错误，错判为信息组是1。因此，该码若用完备译码能纠正序列中的一个错误，此时译码错误概率p1-Q1-(1-pe)3+3pe(1-pe)2=2.810-2也就是误码率由0.1减至2.810-2。若该码不用作纠错，而采用不完备译码用作检错，则可以发现两个错误，与ARQ系统结合后，译码错误概率减至p3e10-3。,54,(4)(4，1)重复码。显然，该码的d04，R14。由于n是偶数，故只能采取不完备译码。它的纠错能力如下：能纠正一个错误同时发现两个错误。若发送的是(0000)，则错一个时，根据大数准则可正确判断发送的是0信息组。若错两个变成(0011)，(1100)，(1010)，(0101
27、)，(1001)，(0110)之一时，则译码器无法作出判决，而指出发生了两个错误。仅在变成(1110)，(0111)，(1011)，(1101)和(1111)时，译码器才作出错误译码。因此，这时的译码错误概率,55,若仅用来检错，则可检测ed0-13个错误。显然，若发送的是(0000)，则仅在变成(1111)时，才产生错误译码，而其它情况均能正确译码或发现错误。因此，此时的译码错误概率pp4e10-4。,56,(5)(5，1)重复码。(5，1)码的d05，R15。它的纠错能力如下：能纠正两个随机错误，这时的译码错误概率,因此，传送信息组0、1的错误概率从0.1降至千分之七，约降低了两个量级。,
28、57,若仅用来检错，则能发现ed0-14个错误。若与ARQ系统结合进行纠错，则译码错误概率大约为pp5e10-5。由上面有关重复码的一系列例子可以看到：(1)随着码长n的增加，重复码的d0n越来越大，抗干扰能力越来越强，误码率也越来越小，但码率R1n却越来越低。(2)在用同样的(n，k)码下，应用非完备译码并与ARQ系统相结合，译码器所给出的误码率比完备译码所产生的要低得多。通过上面这些例子还可看出，(n，k)分组码的最小距离d0(今后简称d)与纠错能力有如下关系。,58,定理1.3.1 任一(n，k)分组码，若要在码字内：(1)检测e个随机错误，则要求码的最小距离de+1；(2)纠正t个随机
29、错误，则要求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，故C1C2，因此译码器不会将C1错判成C2，检测到e=d-1个错误。,59,图 1-14 纠错码纠错能力的几何解释,60,(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)所
30、示，所以译码器可以根据它们之间的距离的大小正确译码，从而纠正t个错误。(3)这里所指的同时，是当错误个数t时，该码能纠正t个错；当错误个数大于t而小于e时，则码能发现e个错误。由(1)和(2)的证明可直接得到结论(3)，请自行证明。由此定理可知，一个距离为d的分组码，至多能纠正t(d-1)2(x是x的整数部分)个错误。该定理确定了码的纠错能力与它的距离之间的关系，是纠错码理论中最基本的定理之一。,61,例1.2 奇偶校验(监督)码 奇偶校验码是只有一个校验元的(n，n-1)分组码。设给定kn-1位的二进制信息码组为:mk-1，mk-2，m1，m0，则按如下规则完成码中一个码字(cn-1，cn-
31、2，c1，c0)的编码：cn-1mk-1，cn-2mk-2，c2m1，c1m0，而一个校验元c0mk-1+mk-2+m1+m0或 cn-1+cn-2+c1+c00(1.3.5)该式保证每个码字中“1”的个数为偶数，所以称这种校验关系为奇偶校验。由于分组码中的每一个码字均按同一规则构成，故称这种分组码为一致校验码。显然，码中的码字数目M2k2n-1。,62,(1)(2，1)奇偶校验码。此码的n=2，k1，按c1+c00求出校验元c0=c1，所以两个许用码组是00和11，此时d2，R1/2，能发现一个错误。若在pe0.1的BSC中传送，则利用不完备译码并与ARQ相结合，可使误码率大约减至p10-2
32、。(2)(3，2)码。此码有224个信息组，由式(1.3.5)求得校验元，得到相应的4个码字为：000，011，101，110。由此看出，这4个信息组就是在8个二进制三重中，把重量为偶数的4个三重挑选为许用码字，重量为奇数的其它4个为禁用码组。显然，该码的d2，。译码误码率大约为,63,(3)(4，3)码。该码的8个码字是按照式(1.3.5)的要求，在16个二进制四重中挑选出来的，其重量均为偶数。该码的d2，R34。其译码误码率约为 由上看出，(n，n-1)奇偶校验码。当它的n时，R1，但d2，dn0，译码误码率ppe，接近未编码时的情况。即随着码长的增加，抗干扰能力接近于零。上述(n，1)和
33、(n，n-1)码，随着码长n的增加，前者R0，后者抗干扰能力接近于零，或dn0，都不理想。那么是否存在有一种码，随着n的增加。其纠错能力和传信率都保持一定呢？换言之，在R一定时，随着n，dn0，从而使p0的码是否存在？1949年香农(Shannon)的信道编码定理对此作了肯定的回答。,64,1.4 信道编码定理,信道编码定理 每个信道具有确定的信道容量C，对任何小于C的码率R，存在有速率为R码长为n的分组码及(n0，k0，m)卷积码，若用最大似然译码，则随着码长的增加其译码错误概率p可任意小，即,和,(1.4.1),65,式中，Ab和Ac为大于0的系数，Eb(R)和Ec(R)为正实函数，称为误
34、差指数，它与R、C的关系如图1-15所示。,图 1-15 信道容量C、码长n和错误概率p之间的转换关系,66,由式(1.4.1)和图 1-15可看出，为了满足一定误码率p的要求，可用以下两类方法实现。一是增加信道容量C，从而使E(R)增加。由C的表示式可知，增加C的方法可以采用如加大系统带宽或增加信噪比的方法来达到，是通信设计工作者经常采用的传统方法。,67,另一种方法是在R一定下，增加分组码长n，可使p随n的增加而呈指数下降。但由于码长n的增加，当R保持一定时，可能发送的码字数2k指数增加，从而增加了译码设备的复杂性。这种方法就是信道编码定理所指出减少误码率的另一方向，它为通信设计工作者提供
35、了一条新的途径。下面通过几个具体例子说明R保持一定时，随着n的增加，可使p下降。,68,例1.3 设有一个随机产生二进制序列的信源和一个转移概率pe0.1的BSC。如果不编码，则传送消息的误码率仍为0.1。现以R12的码率进行编码，考察一下编码效果。首先，按k2分组，则编出码的长度n4，构成一个(4，2)分组码。编码规则如下：设两个信息元为c3、c2，两个校验元为c1、c0，则c1 c2 c0 c3+c2 编出的4个许用码组为:(0000)，(1001)，(0111)，(1110)。其余12个四重为禁用码组。译码按表1-1所示的译码表进行。,69,表1-1(4，2)码译码表,70,由译码表可知
36、，若发送码字在传送过程中前三位的任一位发生错误，接收的四重必位于该码字所在列中，因而正确译码。因此正确译码概率,码字的错误译码概率,由此可得译码后的误码率,可以看到，编码使误码率由0.1下降到0.063。,71,如果保持传信率R12不变，把信息组的长度k加大到3，构成一个(6，3)码。设信息组为c5、c4、c3，相应地3个校验元为c2、c1、c0，按下述校验规则求校验元：,c2c3+c4c1=c3+c5c0=c4+c5,得到8个码字及其译码表，如表1-2所示。由该译码表知，发送码字的六位码元中，任一位出现错误均可纠正。第一位和第四位同时出现错误时也能正确译码。,72,表1-2(6，3)码编译码
37、表,73,相应的信息元误码率,由此可见，随着n的增加，在保持R1/2不变时，可使误码率越来越小，这正是信道编码定理指出的结果。但也必须看到，随着n的增加，其译码设备的复杂性成指数增加。我们研究纠错编码的意义就在于：保持一定的信息传输效率条件下，通过编译码来降低误码率以实现可靠通信，并且要求译码器尽可能简单。,三位信息组完全正确译出的概率为,74,应用纠错码后，若仍要求传输信息的速率不变，则必然使信道的带宽W增加。设原来的信息传输速率为600bits，如用R12码，则要求信道传输速率为1 200 bits，一般要求信道带宽增加一倍(通常增加(n-k)k倍)。因此，纠错码主要应用于功率受限而带宽不
38、太受限的信道中。,75,在极限情况n时，要求带宽W。根据计算，此时只要求信噪比EbN0-1.6dB，就可实现高斯白噪声信道下的无误传输。这就是带宽无限高斯白噪声信道的极限传输能力，称为Shannon限。图 1-16给出了未编码的PSK与应用各类纠错码后，误码率与信噪比之间的关系曲线。由此图看到：应用R1/2的(24，12)分组码后，在误码率为10-5时比未编码的大约可节省3 dB的功率(称编码增益)；而用R1/2，约束度N为8的卷积码软判决维特比(Viterbi)译码，在误码率为10-5时，大约可节省5dB的功率。一般情况下，应用纠错码后，大约能得到从零点几到几个dB程度不等的编码增益。,76,图 1-16 各种码的性能比较,
