1、第12章差错控制编码 第12章 差错控制编码 12.1 概述概述 12.2 差错控制编码的基本原理差错控制编码的基本原理 12.3 常用的简单编码常用的简单编码 12.4 线性分组码线性分组码 12.5 循环码循环码 12.6 卷积码卷积码 第12章差错控制编码 12.1概述概述 数据在网络中传输时,由于信道噪声及信道传输特性不理想等因素的影响,接收端所收到的数据不可避免地会发生错误。通常,传输中报文数据的部分内容出错的情况可能比整个报文内容完整无缺地到达目的地的情况要多得多。因此,一个可靠的数据传输系统必须具有检测或纠正这种错误的机制。通过编码来实现对传输中出现的错误进行检测或纠正的方法称为
2、差错控制编码。差错控制编码的基本(实现)方法是在发送端将被传输的数据信息(信息码)中增加一些多余的比特(监督码),使原来彼此相互独立没有关联的信息码与监督码经过某种变换后产生某种规律性或相关性。第12章差错控制编码 接收端按照一定的规则对信息码与监督码之间的相互关系进行校验,一旦传输发生差错,则信息码与监督码的关系就受到破坏,从而接收端可以发现以至纠正传输中产生的错误。通过差错控制编码这一环节,使系统具有一定的检错或纠错能力,可减少接收信息中的错误,提高系统的抗干扰能力。在OSI模型中,检测错误或纠正错误可以在数据链路层实现,也可以在传输层实现。第12章差错控制编码 所谓检测错误(简称检错),
3、是指接收端仅对接收到的信息进行正确或错误判断,而不对错误进行纠正。所谓纠正错误(简称纠错),是指接收端不仅能对接收到的信息进行正确或错误判断,而且能对错误进行纠正。由于信道噪声及信道传输特性的不同,造成错误的统计特性也不同。传输信道中常见的错误有以下三种:(1)随机错误。这种错误是随机出现的,通常不是成片地出现错误,并且各个错误的出现是统计独立的。这种情况一般是由信道的加性随机噪声引起的。因此,一般将具有此特性的信道称为随机信道。第12章差错控制编码(2)突发错误。这种错误是相对集中出现的,即在短时间段内有很多错误出现。这种情况如移动通信中信号在某一段时间内发生衰落,造成一串错误;汽车发动时电
4、火花干扰造成的错误;光盘上的一条划痕等等。这样的信道我们称之为突发信道。(3)混合错误。这种错误是指既有突发错误又有随机差错的情况。这种信道称之为混合信道。第12章差错控制编码 1.检错重发方式检错重发方式检错重发又称反馈纠错。发送端在被传输的数据信息中增加一些监督码编成码组,使其具有一定的检错能力。接收端对接收到的码组按一定的规则进行有无错误的判断,并将判断结果通过反馈信道送回发送端。发送端根据应答信号内容来决定是重新发送原来数据信息还是发送新数据信息。以此往复,直至将数据信息正确接收完为止。第12章差错控制编码 检错重发方式有如下6个特点:(1)编译码简单,容易实现;(2)编码效率高,只需
5、要少量的冗余码就能获得极低的输出误码率;(3)所使用的检错码与传输出错的统计特性无关,对各种信道的不同错误特性有一定的适应能力;(4)通信系统必须要有反馈信道,因而不能用于单向传输系统和一点对多点的同播系统;(5)由于检错重发的随机性,接收端送给用户的正确数据信息也是随机到达的,因此不适合实时数据传输;(6)当信道干扰增大时,数据传输中错误增多,这将导致系统通信效率降低。第12章差错控制编码 检错重发系统称为自动要求重发ARQ(Automatic RepeatreQuest)系统。图12-1是检错重发差错控制系统的组成框图。检错重发系统有三种主要工作方式:发送等候(SWARQ)工作方式、连续工
6、作方式和混合工作方式。连续工作方式又可分为退N或往返重发N方式(GBNARQ)和选择性重发方式(SNARQ)。第12章差错控制编码 图12-1检错重发差错控制系统的组成 第12章差错控制编码 发送等候(SWARQ)工作方式是一种简单的检错重发方式,其工作过程如图12-2所示。图中1,2,3,是发送的数据组;ACK是接收数据没有错误的应答信号,请求发送端发送新数据组;NAK是接收数据中出现错误的应答信号,请求发送端重新发送前一数据组。由图12-2可以看出,发送端每发送完一个数据组都要等待接收应答信号。若应答信号是ACK,则发送新数据组;若应答信号是NAK,则重新发送前一数据组。这种检错重发方式简
7、单、易于实现,并且误码率可以做得很低,适用于半双工通信及数据网之间的通信。第12章差错控制编码 图12-2发送等候方式工作过程 第12章差错控制编码 2.前向纠错方式前向纠错方式(FEC)前向纠错方式(ForwardErrorCorrection,FEC)数据通信系统原理如图12-3所示,由发送数据终端、纠错码编码器、数据信道、纠错码译码器、接收数据终端等部分组成。发送端在被传输的数据信息中增加一些监督码编成码组,使其具有一定的纠错能力。接收端对接收到的码组按一定的规则进行译码,判断接收到的码组有无错误。若无错误,则译码器直接将数据信息送给接收数据终端;若有错误并且错误在纠错能力之内,则译码器
8、对错误进行纠正后再将数据信息送给接收数据终端。第12章差错控制编码 图12-3前向纠错数据通信系统原理 第12章差错控制编码 前向纠错方式有如下4个主要特点:(1)通信系统不需要反馈信道,能用于单向通信系统,因而也适用于一点对多点的同播系统;(2)译码延迟固定,适用于实时传输系统;(3)纠错能力与所加的冗余码多少有关,为了得到较强的纠错能力所需要的冗余码较多,因而编码效率较低;(4)当传输中产生的错误超过码的纠错能力时,带有错误的数据信息有可能送给用户,从而造成用户接收到有错的数据信息。第12章差错控制编码 3.混合差错控制方式混合差错控制方式(HEC)混合差错控制方式(HybridError
9、Correction,HEC)是前向纠错与检错重发两种差错控制方式的结合。发送端进行同时具有自动纠错和检错能力的编码,接收端收到码组后,首先进行错误情况判断,如果出现的错误在该编码的纠错能力之内,则自动对错误进行纠正。如果信道干扰严重,出现的错误超过了该编码的纠正错误能力,但是在检测错误能力之内,则经过反馈信道请求发送端重新发送这组数据。如果信道干扰非常严重,出现的错误不仅超过了该编码的纠正错误能力,而且超过了该编码的检测错误能力,对这种严重的错误,这种差错控制方式将失去作用,译码器会将有错误的数据送给数据终端,从而产生接收数据出错。混合差错控制方式的原理如图12-4所示。发送端的差错控制编码
10、应同时具有检测错误和纠正错误的能力。第12章差错控制编码 图12-4混合差错控制方式原理图 第12章差错控制编码 混合差错控制方式有以下4个主要特点:(1)同时具有检测错误和纠正错误的能力。(2)克服了检错重发方式数据连贯性差、通过率随信道错误率的增加而迅速降低的严重缺点。(3)避免了前向纠错方式为了得到低的错误率,使得编码效率低、需要很复杂的译码器及不能适应信道错误变化的缺点。(4)需要双向信道。因此,在数据交换网和计算机通信网中,常常采用混合差错控制方式。但是,如果在通信系统中没有反馈信道可用或因某种原因不可能重传时,前向纠错方式就是唯一的选择了。随着数字通信技术的发展,各种误码控制编码方
11、案相继推出。这些方案建立在不同的数学模型基础上,并具有不同的检错与纠错特性。图12-5给出了纠错码的各种类型。第12章差错控制编码 图12-5纠错码的各种类型 第12章差错控制编码 12.2差错控制编码的基本原理差错控制编码的基本原理 12.2.1纠错编码的基本原理纠错编码的基本原理差错控制编码也称纠错编码,其基本原理是在信息码元序列中加入一定的监督码元,使编成的码组具有一定的检测错误和纠正错误的能力,纠错编码包括检错编码和纠错编码。不同的编码方法有不同的检错和纠错能力。一般来说,付出的代价越大,检(纠)错的能力就越强。这里所说的代价,就是指增加的监督码元的多少。例如,若编码序列中,平均每两个
12、信息码元就有一个监督码元,则这种编码的冗余度为1/3。换一种说法,这种编码的编码速率为2/3。第12章差错控制编码 下面以一个简单的例子来阐述差错编码在相同的信噪比情况下为什么会获得更小的误码率性能。假设我们发送一个开关的断开和闭合两种状态,用二进制码元的“0”表示开关处于“断开”状态,用二进制码元的“1”表示开关处于“闭合”状态。这时,若码元在传输过程中出现错误,将“0”码元接收为“1”码元,或将“1”码元接收为“0”码元,则因为接收端无法发现错码,而将收到错误信息。第12章差错控制编码 如果将开关的“断开”和“闭合”两种状态信息用2个二进制码元表示,即进行2个二进制码元编码,共有4种编码:
13、“00”、“01”、“10”和“11”。选择其中的“00”表示开关处于“断开”状态,“11”表示开关处于“闭合”状态。另外还有两种编码“01”和“10”没有选用,称为禁用码组。若发送端发送的是“00”编码,如果码组在传输过程中出现1个错误,则接收到的码组可能是“01”或“10”。由于“01”和“10”两种编码是禁用码组,因此我们可以判定接收到的码组出现了错误。同样,若发送端发送的是“11”编码,如果码组在传输过程中出现1个错误,则接收到的码组也可能是“01”或“10”,我们也可以判定接收到的码组出现了错误,从而实现了检测错误。通过这种简单的重复编码就可以实现对码组中一个错误的检测。但是这种编码
14、不能实现对两个或两个以上的错码进行检测,也不能纠正错码。第12章差错控制编码 如果采用更多个二进制码元编码来表示开关的“断开”和“闭合”两种状态则情况会如何？例如采用3个二进制码元编码共有8种编码:“000”、“001”、“010”、“011”、“100”、“101”、“110”和“111”。选择其中的“000”表示开关处于“断开”状态,“111”表示开关处于“闭合”状态。另外6种编码“001”、“010”、“011”、“100”、“101”和“110”为禁用码组。在接收端我们用如下的译码方法,每收到3个比特译码一次,采用大数判决,即3个比特中0的个数大于1的个数则译码成0,反之译码成1。若发
15、送端发送的是“000”编码,如果码组在传输过程中出现1个错误,则接收到的码组可能是“001”、“010”或“100”。第12章差错控制编码 由于这三种编码是禁用码组,因此我们可以判定接收到的码组出现了错误。更进一步,由于接收到的码组“001”、“010”或“100”中0的个数大于1的个数,根据大数判决规则译码,则译码器译成“000”码输出,纠正了传输中出现的1个错码。同样,若发送端发送“111”编码,如果码组在传输过程中出现1个错误,接收端根据大数判决规则译码,则译码器译成“111”码输出,也纠正了传输中出现的1个错码。可见,这种纠错编码方法能够纠正1个错码。第12章差错控制编码 从这个简单例
16、子可以看到:当发送的信息编码中没有冗余码时,接收端译码器不能检测和纠正错码;当在发送的信息编码中加入1个冗余码时,接收端译码器能够检测出1个错码,但是不能纠正错码;当在发送的信息编码中加入2个冗余码时,接收端译码器能够检测出2个或1个错码,或纠正1个错码。检测或纠正错码能力的增强是通过增加发送编码中冗余码而得到的。第12章差错控制编码 纠错编码的基本原理是:为了使信源信息具有检错和纠错能力,应当按一定的规则在信息码中增加一些冗余码(又称监督码),使这些冗余码与被传送信息码之间建立一定的关系,发送端完成这个任务的过程就称为差错控制编码(或纠错编码);在接收端,根据信息码与监督码的特定关系,实现检
17、错或纠错,输出原信息码,完成这个任务的过程就称差错控制译码(或纠错译码)。另外,无论检错和纠错,都有一定的识别范围。差错控制编码原则上是以降低信息传输速率来换取信息传递的可靠性的提高。我们研究误码控制编码的目的,正是为了寻求较好的编码方式,在尽可能少的增加冗余码的情况下来实现尽可能强的检错和纠错能力。第12章差错控制编码 12.2.2纠错编码的基本概念纠错编码的基本概念1.信息码元与监督码元信息码元与监督码元信息码元又称信息位,这是指由发送端信源发送的信息数据比特,通常以mi表示。由信息码元组成的信息码组为M=(mk-1,mk-2,m0)(12.2-1)其中,k为信息码组中信息码元的个数。在二
18、进制码情况下,每个信息码元mi的取值只有0或1两种状态,所以总的信息码组数共有2k个。监督码元又称监督位,这是为了检测或纠正错码而在信息码组中加入的冗余码。监督码元的个数通常以r表示。第12章差错控制编码 2.分组码分组码在纠错编码时,将r个监督码元附加在由k个信息码元组成的信息码组上,构成一个就有纠错功能的独立码组,并且监督码元仅与本码组中的信息码组有关,这种按组进行编码的方法称为分组码。分组码通常用符号(n,k)表示,其中,n表示分组码码组长度;k表示信息码元个数;r=n-k,表示监督码元个数。在二进制编码中,通常分组码都是k个信息码元在前,r个监督码元附加在k个信息码元之后,其结构如图1
19、2-6所示。第12章差错控制编码 图12-6分组码结构图 第12章差错控制编码 通常把信息码元个数k与码组长度n之比称为纠错编码的编码效率或编码速率,表示为(12.2-2)编码效率是衡量纠错码性能的一个重要指标,一般情况下,监督位越多,检纠错能力越强,但相应的编码效率也随之降低。第12章差错控制编码 3.许用码组与禁用码组许用码组与禁用码组在二进制编码中,若分组码码组长度为n,则总的码组数应为2n=2k+r个。其中被传送的码组有2k个,通常称为许用码组;其余的2n-2k个码组不传送,称为禁用码组。发送端纠错编码的任务正是寻求某种规则从总码组数2n中选出2k个许用码组,而接收端译码的任务则是利用
20、相应的规则来判断收到的码字是否符合许用码组,对错误进行检测和纠正。第12章差错控制编码 4.码重、码距与最小码距码重、码距与最小码距码组的重量(简称码重)是指码组中非零元素的个数。对于二进制编码,码重就是码组中1的个数。例如:000码组的重量是0,101码组的重量是2。码组的距离(简称码距)是指两个码组ci、cj之间不同比特的个数,数学表示为(模q)（12.2-3）第12章差错控制编码 最小码距是指在一个码组集合中,任意两个码组之间距离的最小值,以字母d0表示,(模q)(12.2-4)最小码距也称最小汉明距离。例如:000、101与111三个码组之间的最小码距d0=1。第12章差错控制编码 5
21、.最小码距最小码距d0与纠错能力的关系与纠错能力的关系纠错编码理论的研究结果表明,最小码距d0与检、纠错能力之间满足下列关系:(1)若码组用于检测e个错误时,则放大码距:(12.2-5)(2)若码组用于纠正t个错误时,则放大码距:(12.2-6)(3)若码组用于纠正t个错误,同时检测e个错误时,则放大码距:(12.2-7)第12章差错控制编码 一种编码的最小码距d0与检错和纠错能力的关系如图12-7所示。图12-7最小码距与检错和纠错能力的关系 第12章差错控制编码 6.编码增益编码增益差错控制编码使数据通信系统具有一定的纠错能力,这种能力可以用编码增益来衡量。在保持误码率不变的情况下,采用纠
22、错编码所节省的信噪比Eb/n0称为编码增益,用分贝形式表示如下:(12.2-8)第12章差错控制编码 编码增益也反映了译码后数据信息的误码率与译码前数据信息在信道传输中的误码率相比较时所得到的改进量。不同的纠错编码具有不同的编码增益,它和编码方式、译码方式及信道误码率pe等因素有关。译码后的误码率pB可以近似表示为(12.2-9)第12章差错控制编码 12.3常用的简单编码常用的简单编码 1.奇偶监督码奇偶监督码奇偶监督码是一种用于检测错误的简单编码,分为奇监督码和偶监督码两种。编码时只需要在信源输出的信息码的后面添加一位监督码元(又称校验码元),使得码组中“1”的个数是奇数个或偶数个。例如,
23、若信源送出的信息码是1001101,信息码中有4个“1”,经过编码器输出码组为10011011,在信息码后加了1个监督码“1”,使该码组中“1”的个数为奇数个,这种编码方法是奇监督码。若信息码1001101经过编码器后输出码组为10011010,在信息码后加了1个监督码“0”,使该码组中“1”的个数为偶数个,这种编码方法是偶监督码。第12章差错控制编码 设码组为,则奇监督码满足如下关系式:(12.3-1)偶监督码满足:(12.3-2)式中,是信息位;a0是监督位。第12章差错控制编码 奇偶监督码的译码方法也很简单。若对于偶监督码,在接收端只需对接收到的码组按式(12.3-2)进行验证。若计算结
24、果为“0”,则认为接收到的码组是正确的,若计算结果为“1”,则接收到的码组是错误的。奇偶监督码检测错误的能力有限,它只能检测出所有奇数个错码,不能检测出偶数个错码。另外,该码组的最小码距d0=2,故没有纠正错码的能力。由于在奇偶监督码中,无论信息位有多少位,监督位只有一位,因此编码效率很高。奇偶监督码组长度为n,信息位长度为n-1,所以编码效率为(12.3-3)第12章差错控制编码 2.二维奇偶监督码二维奇偶监督码为了提高奇偶监督码检测错误的能力,可以采用二维奇偶监督码,二维奇偶监督码也称为方阵码。该码的构造方法是先将信息码排列成m1行乘n1列矩阵,在每一行最后加上一位奇偶监督码a10a20a
25、0m1,然后再在每一列最后加上一位奇偶监督码cn1cn2c1c0,构成二维奇偶监督关系。二维奇偶监督码结构如图12-8所示。与一维奇偶监督码相比,二维奇偶监督码增加了列监督码,因此编码效率有所降低,图12-8所示的二维奇偶监督码编码效率为(12.3-4)第12章差错控制编码 图 12-8 二维奇偶监督码结构第12章差错控制编码 二维奇偶监督码发送时可以按行的顺序发送,先发送第一行a1n-1a1n-2a11a10,再发送第二行a2n-1a2n-2a21a20,最后发送监督码cn-1cn-2c1c0。当然也可以按列的顺序发送。二维奇偶监督码有较强的检测错误能力,它可以检测出所有奇数个错码,并且可以
26、检测出有些偶数个错码。这种码还适合检测突发错码,能检测出所有错误长度不大于n+1的突发错误,以及其他大量的错误图样突发。该码除了具有检测错误的能力外,还具有一定的纠正错误的能力。例如发送的二维奇偶监督码如图12-9(a)所示,接收到的码组如图12-9(b)所示。第12章差错控制编码 图 12-9 二维奇偶监督码检错、纠错原理(a)发送码;(b)接收码第12章差错控制编码 3.循环冗余校验循环冗余校验(CRC)循环冗余校验的英文全称为Cyclic Redundancy Check,它是一类重要的线性分组码,编码和解码方法简单,检错能力强,在数据通信领域广泛地用于实现差错控制。利用CRC进行检错的
27、过程可简单描述为:在发送端根据要传送的k位二进制信息码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在原始信息码后边,构成一个新的二进制码序列数，共k+r位,然后发送出去。在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以确定接收的数据中是否出错。第12章差错控制编码 CRC校验采用多项式编码方法,被处理的信息序列可以看做是一个n阶的二进制多项式,标准形式如下:(12.3-5)第12章差错控制编码 第12章差错控制编码(3)用xrm(x)以模2的方式加上r(x),得到二进制多项式(模2)T(x)就是包含了CRC校验码的待发送数据序列。为了更清楚地了解CRC校验码的编码原理
28、,下面用一个简单的例子来说明CRC的编码过程。设信息码为1100,生成多项式为1011,即m(x)=x3+x2,g(x)=x3+x+1,计算CRC的编码过程为 即r(x)=x,注意到g(x)的最高幂次r=3,得出CRC为010。第12章差错控制编码 由此可产生待发送的二进制码为1100000+010=1100010,其对应的二进制多项式为 从CRC的编码规则可以看出,CRC编码实际上是将待发送的k位信息码的二进制多项式m(x)转换成了可以被生成多项式g(x)除尽的k+r位二进制多项式T(x)。所以解码时可以用接收到的数据多项式去除生成多项式g(x),如果余数为零,则表示接收数据中没有错误;如果
29、余数不为零,则接收数据中肯定存在错误。同时,T(x)可以看做是由m(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位校验,得到的就是原始信息。第12章差错控制编码 多项式除法可用除法电路来实现。除法电路的主体由一组移位寄存器和模2加法器组成。CRC-ITU标准的CRC校验码生成多项式g(x)=x16+x12+x5+1,除法电路原理如图12-10所示,它由16级移位寄存器和3个模2加法器组成(编码器、解码器结构相同)。编码、解码前将各寄存器初始化为“1”,信息位随着时钟移入。当信息位全部输入后,从寄存器组输出CRC结果。第12章差错控制编码 图12-10CRC-ITU标准的
30、除法电路原理 第12章差错控制编码 表12-1列出了一些常见的CRC标准。CRC-16用于IBM的同步数据链路控制规程SDLC的帧校验序列FCS;CRC-ITU用于ITU推荐的高级数据链路控制规程HDLC的帧校验序列FCS等。一般情况下,r阶生成多项式产生的CRC码可检测出所有的奇数位错误和突发长度小于等于r的突发错误,以及(1-2-(r-1)%的突发长度为r+1的突发错误和(1-2-r)%的突发长度大于r+1的突发错误。所以CRC生成多项式的阶数越高,则误判的概率就越小。例如对CRC-16的情况,能检测出所有突发长度小于等于16的突发错误,以及99.997%的突发长度为17的突发错误和99.
31、998%的突发长度大于17的突发错误。而CRC-32的误判概率是CRC-16的1/105。可以看出CRC码的检错能力还是很强的。第12章差错控制编码 第12章差错控制编码 12.4线性分组码线性分组码 12.4.1线性分组码原理线性分组码原理线性分组码是一种定义在Galois域(记作GF(q)上的代数码,在数据通信系统中,由于编码经常是二进制形式,因而使用最广泛的是二进制域GF(2)。在二进制编码中,每个码元取值是“0”或“1”两种状态,其基本运算规则如表12-2所示。第12章差错控制编码 第12章差错控制编码 我们假设信源输出是二进制“0”或“1”序列。在线性分组码中,二进制信息序列被分成长
32、度为k的信息组,共有2k个。在长度为k的信息码后添加长度为r的监督码,编成长度为n=k+r的分组码。长度为n的所有二进制组共有2n个,线性分组码就是以一定的规则从2n个组中选出其中2k个用做码组,这2k个码组构成了一个(n,k)分组码。我们通常称这2k个码组为许用码组,而其余2n-2k个码组为禁用码组。如果一个(n,k)分组码的信息码和监督码之间的关系为线性的,则称该分组码为线性分组码,否则称为非线性码。第12章差错控制编码 第12章差错控制编码 第12章差错控制编码 根据表12-3的规定可见,仅当有一个错码且位置在a2、a4、a5或a6时,校正子S1为1,否则S1为0。这就意味着a2、a4、
33、a5和a6四个码元构成偶数监督关系,即(12.4-1)同理可得,a1、a3、a5和a6四个码元构成偶数监督关系为(12.4-2)以及a0、a3、a4和a6四个码元构成偶数监督关系为(12.4-3)在编码时,a3、a4、a5和a6为信息码,是二进制随机序列,a0、a1、a2为监督码,应根据信息码的取值按监督关系式决定,即监督码应使校正子S1、S2、S3为零,即 第12章差错控制编码(12.4-4)上式即是(7,4)线性分组码的信息码和监督码所满足的监督方程。对式(12.4-4)进行求解可以得到监督码满足下列关系:(12.4-5)给定信息码a3、a4、a5和a6即可按式(12.4-5)计算出监督码
34、a0、a1、a2。根据式(12.4-5)构成的(7,4)线性分组码编码器原理图如图12-11所示。第12章差错控制编码 图12-11(7,4)线性分组码编码器原理图 第12章差错控制编码 对于(7,4)线性分组码,其信息码长度k=4,共有24=16个信息组,编出的16个码组如表12-4所示。第12章差错控制编码 接收端收到每个码组后,先按式(12.4-1)、(12.4-2)和(12.4-3)计算出校正子S1、S2和S3,再按表12-3判断错误情况。根据此译码过程构造的译码器如图12-12所示。图12-12(7,4)线性分组码译码器原理图 第12章差错控制编码 12.4.2监督矩阵与生成矩阵监督
35、矩阵与生成矩阵在线性码分组码中信息码和监督码满足一组线性方程,或者说信息码和监督码之间有某种线性变换关系。下面仍以(7,4)线性分组码为例,讨论线性分组码的一般原理。将(7,4)线性分组码的监督方程式(12.4-4)写成标准的方程形式(12.4-6)第12章差错控制编码 式中的“+”号是指模2加,这个方程组叫做码组的一致监督方程或一致校验方程。将(12.4-6)式表示成矩阵形式(12.4-7)式(12.4-7)用矩阵符号简写为(12.4-8)第12章差错控制编码 式中 第12章差错控制编码 我们将矩阵H称为(7,4)线性分组码的监督矩阵或校验矩阵,AT和HT分别为矩阵A和监督矩阵H的转置。只要
36、监督矩阵H给定,码组中信息码和监督码之间的关系也就完全确定了。由监督矩阵H可以看出,H矩阵是一个3行乘7列矩阵,即H矩阵的行数等于监督码长度r,其列数等于码组长度n。对于本例的(7,4)线性分组码,其监督矩阵H可以分成两部分(12.4-9)第12章差错控制编码 式中,P是34阶矩阵,I3是33阶单位方阵。我们将具有PIr形式的H矩阵称为典型监督矩阵。当监督矩阵H不是典型阵时,可以对它进行变换,将其化为典型监督矩阵。由典型监督矩阵构成的码组称为系统码,非典型监督矩阵构成的码组是非系统码。系统码的特点是信息位不变,监督位直接附加于其后。(12.4-10)第12章差错控制编码 其中,监督矩阵H是一个
37、rn阶矩阵,P是一个rk阶矩阵,Ir是一个rr阶单位方阵。由代数理论可知,监督矩阵H的各行之间是线性无关的。同样,将(7,4)线性分组码的监督码生成方程式(12.4-5)写成标准的方程形式(12.4-11)第12章差错控制编码 其矩阵表示形式为(12.4-12)或者(12.4-13)式中,Q是一个43阶矩阵,其行数等于码组中信息码长度k,其列数等于监督码长度r。第12章差错控制编码 将Q矩阵与(12.4-9)式中的P矩阵相比较可以看出,Q矩阵是P矩阵的转置,即(12.4-14)将Q矩阵的左边加上一个44阶单位方阵I4构成G矩阵,即(12.4-15)第12章差错控制编码 式中,G矩阵是一个47阶
38、矩阵,其行数等于码组中信息码长度k,其列数等于码组长度n。显然,由G矩阵可以生成(7,4)线性分组码的所有码组,因此称G矩阵为(7,4)线性分组码的生成矩阵。如果得到生成矩阵G也就完全确定了该码的编码方法。假设(7,4)线性分组码的信息码为a3、a4、a5和a6,则按下式可以生成对应的码组:(12.4-16)与监督矩阵H类似,生成矩阵G的每一行都是一个码组,并且各行之间也是线性无关的。如果生成矩阵G具有IkQ的形式,则称G为典型生成矩阵,由典型生成矩阵生成的码组是系统码。第12章差错控制编码 二进制(n,k)系统码典型生成矩阵G的一般形式为(12.4-17)其中,生成矩阵G是一个kn阶矩阵,Q
39、是一个kr阶矩阵,Ik是一个kk阶单位方阵。对式(12.4-16)进行修改,我们可以得到产生码组的一般表示形式(12.4-18)第12章差错控制编码 另外,由Q矩阵与P矩阵互为转置的关系可知,只要得到了监督矩阵H则生成矩阵G也就确定了。反之亦然。(n,k)线性分组码具有如下的性质:(1)封闭性。任意两个码组的和还是许用的码组。(2)码的最小距离等于非零码的最小码重。第12章差错控制编码 12.4.3伴随式与错误图样伴随式与错误图样在发送端,给定信息码由式(12.4-18)即可生成对应的码组,设发送端产生的码组为(12.4-19)该码组通过信道传输到达接收端。设接收端收到的码组为(12.4-20
40、)由于信道的失真和干扰的影响,接收到的码组R通常情况与发送的码组A不一定相同,定义错误矩阵E为接收码组与发送码组之差,即(模2)(12.4-21)第12章差错控制编码 式中 由ei可以看出,当ei=0时,接收的码元等于发送的码元,表示接收码组中该位码元正确;当ei=1时,接收的码元不等于发送的码元,表示接收码组中该位码元错误。因此,错误矩阵E反映了接收码组的出错情况,错误矩阵有时也称为错误图样。在接收端,若能求出错误图样E就能正确恢复出发送的码组A,即(模2)(12.4-22)例如,接收的码组R=1000101,错误图样E=0000010,则发送的码组A=R+E=1000111。第12章差错控
41、制编码 根据线性分组码的编码原理,每个码组应满足式(12.4-8),即 因此,当我们接收到R后用式(12.4-8)进行验证,若等于0则认为接收到的是码组,若不等于0,则认为接收到的不是码组,从而产生了错码。我们定义(12.4-23)则称S为伴随式或校正子。将式(12.4-22)代入式(12.4-23)可得 第12章差错控制编码 第12章差错控制编码 12.4.4汉明码汉明码汉明码是汉明(Hamming)于1949年提出的一种纠正一个随机错误的线性分组码,它有如下参数:(1)码组长度n=2r1;(2)信息码长度k=2r1r;(3)监督码长度r=nk,r是不小于3的任意正整数;(4)最小码距d0=
42、3;(5)能够纠正1个随机错误或检测2个随机错误。第12章差错控制编码 汉明码的监督矩阵H具有特殊的性质,使得能以相对简单的方法来描述该码。对于二进制汉明码,其n=2r-1列包含由r=n-k个二进制码元组成的列矢量的所有可能的组合(全零矢量除外)。例如前面例子所讨论的(7,4)线性分组码就是码组长度为7的汉明码,其监督矩阵由(001)、(010)、(100)、(011)、(101)、(110)和(111)组成。汉明码的编码效率为 若码长n很长,则编码效率R接近1,因此汉明码的编码效率较高。第12章差错控制编码 12.5循环码循环码 12.5.1循环码的基本原理循环码的基本原理循环码是线性分组码
43、的一个重要子集,是目前研究得比较成熟的一类码。循环码具有许多特殊的代数性质,这些性质有助于按照要求的纠错能力系统地构造这类码。目前发现的大部分线性码与循环码有密切关系。循环码还有易于实现的特点,很容易用带反馈的移位寄存器实现其硬件。正是由于循环码具有码的代数结构清晰、性能较好、编译码简单和易于实现的特点,因此在数据通信和计算机纠错系统中得到广泛应用。循环码具有较强的检错和纠错能力,它不仅可以用于纠正独立的随机错误,而且也可以用于纠正突发错误。第12章差错控制编码 第12章差错控制编码 第12章差错控制编码 循环码是线性分组码,除了具有线性分组码的性质外还具有以下重要性质:(1)封闭性(线性性)
44、。任何许用码组的线性和还是许用码组。由此性质可知:线性码都包含全零码,且最小码距就是最小码重(除全0码)。(2)循环性。任何许用的码组循环移位后的码组还是许用码组。为了便于用代数来研究循环码,我们把长度为n的码组用n-1次多项式表示,将码组中各码元当作是一个多项式的系数。若码组为(an-1an-2a1a0),则相应的多项式表示为(12.5-1)第12章差错控制编码 多项式A(x)称为码多项式。例如表12-5中的第7个码组A=(1100101),则相应的多项式表示为 由码多项式可以看出,对于二进制码组,多项式的每个系数不是0就是1,x仅是码元位置的标志。码多项式的运算是采用按模运算法则,若一任意
45、多项式M(x)被一个n次多项式N(x)除,得到商式Q(x)和一个次数小于n的余式R(x),也就是(12.5-2)第12章差错控制编码 可以写为(模N(x)(12.5-3)第12章差错控制编码 所以 取模x5+1后可得(模x5+1)在循环码中,若A(x)是一个长为n的许用码组,则xiA(x)在按模xn+1运算下,亦是一个许用码组。也就是假如xiA(x)A(x)(模xn+1),可以证明A(x)亦是一个许用码组,并且A(x)正是A(x)代表的码组向左循环移位i次的结果。例如表12-5所示的(7,3)循环码中的第3个码组乘以x3,则有第12章差错控制编码(模x7+1)其对应的码组为A=(1110010
46、),它正是表12-5中第8个码组。通过上述分析可以得到,若A(x)是(n,k)循环码的一个码组,则它的循环移位xA(x),x2A(x),以及循环移位的线性组合均是该循环码的码组,且这些码多项式都是模xn+1的一个余式。第12章差错控制编码 第12章差错控制编码(12.5-4)式中,g(x)称为循环码的生成多项式。可以证明,生成多项式g(x)是2k个码组集合中唯一的一个次数为n-k次多项式。当给出k个信息码(an-1an-2an-k),则可以根据公式(12.5-5)求出码多项式A(x)。第12章差错控制编码 例如,对于上例的(7,3)循环码,由表12-5可以看出,前面k-1=2位都是0的码组是(
47、0010111),该码组对应的生成多项式g(x)=x4+x2+x+1,则生成矩阵G的多项式表示为 相应的生成矩阵G为 第12章差错控制编码 可以看出该生成矩阵G不是典型生成矩阵,将生成矩阵中的第3行加到第1行可得典型生成矩阵为 当信息码为(110)时,编出的系统码码组为 第12章差错控制编码 通过以上对循环码的讨论可以看出,寻找循环码的生成多项式是循环码编码的关键。研究表明循环码生成多项式有如下重要性质:循环码生成多项g(x)是xn+1的一个n-k=r次因式。该性质为我们提供了一种寻找循环码生成多项式的方法。例如对于(7,3)循环码,其生成多项式g(x)应是x7+1的7-3=4次因式。对x7+
48、1进行因式分解有 第12章差错控制编码 第12章差错控制编码 12.5.3循环码的编码和译码方法循环码的编码和译码方法1.循环码的编码循环码的编码由式(12.5-5)可以看出,用信息码多项式m(x)乘以生成多项式g(x)就得到一个码多项式。但是用这种相乘的方法产生的循环码不是系统码。为了得到系统循环码的编码方法,我们可以采用除法方法。编码过程可分为三个步骤:(1)设m(x)为信息码多项式,用xn-k乘信息码多项式m(x),则xn-km(x)的次数小于n;(2)用g(x)除xn-km(x),即(12.5-6)其中,r(x)是余式,其次数小于n-k;第12章差错控制编码(3)将余式r(x)加到xn
49、-km(x)之后,即xn-km(x)+r(x),它能被g(x)整除,令A(x)=xn-km(x)+r(x),则A(x)就是循环码的码多项式。从编码的步骤看,编码的核心是如何确定余式r(x),找到r(x)后可直接将r(x)所代表的编码附加到信息码之后,完成编码。实际上,r(x)所代表的编码可以理解为监督码,得到r(x)可以采用除法电路。例如,对于生成多项式g(x)=x4+x2+x+1的(7,3)循环码,设信息码多项式m(x)=x2+1,则xn-km(x)=x4(x2+1)=x6+x4。用g(x)除xn-km(x),即第12章差错控制编码 编出码组的码多项式为 对应的码组为 它是表12-5所示(7
50、,3)循环码中的第6个码组。第12章差错控制编码 上述循环码的编码过程可以用由移位寄存器和模2加法器组成的g(x)除法电路实现。对于生成多项式g(x)=x4+x2+x+1的(7,3)循环码的编码器如图12-13所示。图中有一个四级移位寄存器,分别用D1、D2、D3和D4表示。另外还有一个双刀双掷开关S。编码器工作过程如下:第第1步步开关S向下,输入的k位信息码m0,m1,mk-1一方面送入除法器进行运算,同时直接输出。一旦k位信息码全部送入除法器,在n-k=4级移位寄存器中的数据就是除法余项(它就是信息码的监督码)。第12章差错控制编码 第2步开关S向上,断开反馈输入,同时移位寄存器连接到输出
