第3章信道编码 (2)
3.1差错控制方式 (2)
3.2信道编码 (3)
3.2.1 差错控制编码的基本原理 (3)
3.2.2 差错控制编码的分类 (4)
3.2.3 差错控制编码的基本概念 (5)
3.3常见的几种检错码 (7)
3.3.1 奇偶校验码 (7)
3.3.2 水平奇偶校验码 (8)
3.3.3 水平垂直奇偶校验码 (9)
3.3.4 恒比码 (9)
3.3.5群计数码 (10)
3.4线性分组码 (11)
3.4.1 基本概念 (11)
3.4.2 线性分组码的编码 (12)
3.4.3 线性分组码的译码 (16)
3.5循环码 (18)
3.5.1 基本概念 (18)
3.5.2 循环码的编码 (25)
3.5.3 循环码的译码 (27)
3.5.4 常见的几种循环码 (29)
3.6BCH码 (30)
3.7RS码 (33)
3.7.1 RS码的编码 (34)
3.7.2 RS码的译码 (35)
3.8卷积码 (36)
3.8.1 基本概念 (36)
3.8.2 卷积码的图解表示 (38)
3.8.3 卷积码的译码 (40)
3.9几种新的编码方法 (42)
3.9.1 网格编码调制（TCM） (42)
3.9.2 TURBO码 (47)
8.9.3LDPC码 (49)
3.9.4喷泉码 (51)
本章小结 (56)
习题 (57)
第3章信道编码
在数字通信系统中，干扰会使信号产生变形，致使接收端产生误码，这将严重影响数字通信系统的可靠性。为了提高数字通信系统的可靠性，除了可采用均衡技术来消除乘性干扰引起的码间串扰外，还可以通过对所传数字信息进行特殊的处理（即信道编码）对误码进行检错和纠错，进一步降低误码率，以满足通信的传输要求。因此，信道编码是提高数字通信系统可靠性的有效措施之一，能提高传输质量1~2个数量级。信道编码的目的就是通过加入冗余码来减小误码，进而提高数字通信的可靠性。
香农第二定理指出：对于一个给定的有扰信道，若该信道容量为C，则只要信道中的信息传输速率R小于C，就一定存在一种编码方式，使编码后的误码率随着码长n的增加而按指数下降到任意小的值。或者说只要R C
，就存在传输速率为R的纠错码。该定理虽然没有明确指出如何对数据信息进行纠错编码，也没有给出这种具有纠错能力通信系统的具体实现方法，但它奠定了信道编码的理论基础，并为人们从理论上指出了信道编码的努力方向。信道编码的基本思想就是在数字信号序列中加入一些冗余码元，这些冗余码元不含有通信信息，但与信号序列中的信息码元有着某种制约关系，这种关系在一定程度上可以帮助人们发现或纠正在信息序列中出现的错误（也就是误码），从而起到降低误码率的作用。
本章主要分析差错控制编码的基本方法和纠错编码的基本原理，以及常用检错码、线性分组码和卷积码的构造原理等。
3.1 差错控制方式
目前常见的差错控制方式主要有：前向纠错（FEC）、检错重发（ARQ）、混合纠错（HEC）、信息反馈（IF）和检错删除（deletion）等。几种差错控制方式的原理如图3-1所示。
（1）前向纠错(FEC)：发端除了发送信息码元外，还发送加入的差错控制码元。接收端根据接收到的这些码组后，并利用加入的差错控制码元不但能够发现错码，而且还能自动纠正这些错码。如图3-1（a）所示。前向纠错方式只要求单向信道，因此特别适合于只能提供单向信道的场合，同时也适合一点发送多点接收的广播方式。因为不需要对发信端反馈信息，所以接收信号的延时小、实时性好。这种纠错系统的缺点是设备复杂、成本高，且纠错能力愈强，编译码设备就愈复杂。
（2）检错重发(ARQ)：发端将信息码编成能够检错的码组发送到信道，收端接收到一个码组后进行检验，并将检验结果通过反向信道反馈给发端。发端根据收到的应答信号重新发送有错误的码元，直到接收端能够正确接收为止。如图3-1（b）所示。其优点是译码设备不会太复杂，对突发错误特别有效，但需要双向信道。
（3）混合纠错（HFC）：混合纠错方式是前向纠错方式和检错重发方式的结合。如图3―1（c）所示。其内层采用FEC方式，纠正部分差错；外层采用ARQ方式，重传那些虽已检出但未纠正的差错。混合纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，较适合于环路延迟大的高速数据传输系统。
（4）信息反馈（IF）：前三种方式都是在收端识别有无错码，而信息反馈是接收端接收到的消息原封不动的发回发端，由发端将反馈信息和原发送信息进行比较。当发现错误时进行重发。如图3-1（d）所示。该方法的优点是原理和设备简单，且无须纠检错编译码系统。缺点是需要双向信道，而且传输效率较低，实时性较差。
发送端接收端
（a）前向纠错（FEC）示意图
发送端接收端
（b）检错重发（ARQ）示意图
发送端接收端
（c）混合纠错（HEC
）示意图
图3-1 差错控制的工作方式
（5）检错删除（deletion）：它和检错重发的区别在于，当接收端发现错误时，立即将其删除，不要求重发。这种方法只适用于少数特定系统中，在那里发送的码元中有大量多余度，删除部分接收码后不影响其应用。
3.2 信道编码
3.2.1 差错控制编码的基本原理
信道编码就是在信息码序列中加入冗余码（即监督码元），接收端利用监督码与信息码之间的某种特殊关系加以校验，以实现检错和纠错功能。下面我们以重复码为例详细介绍检错和纠错的基本原理。
假设要发送一组具有两种状态的数据信息（比如，A和B）。我们首先要用二进制码对数据信息进行编码，显然，用1位二进制码就可完成。编码表如表3―1所示。
假设不经信道编码，在信道中直接传输按表中编码规则得到的0、1数字序列，则在理想情况下，收信端收到“0”就认为是A，收到“1”就是B，如此可完全了解发端传过来的信息。而在实际通信中由于干扰（噪声）的影响，会使信息码元发生错误从而出现误码（比如码元“0”变成“1”、或“1”变成“0”）。从上表可见，任何一组码只要发生错误，都会使该码组变成另外一组信息码，从而引起信息传输错误。因此，这种编码不具备检错和纠错的能力。
表3-1 编码表
(1,1)码(2,1)码(3,1)码(4,1)码
A B检错
个数
纠错
个数0100 0 0 1 111 0 00
0 000
1 11
1 111
21
31
重复码信息位监督位信息位监督位
当增加1位冗余码，即采用重复码（2，1）。其中，码长为2位，信息位为1位。如用“00”表示A，用“11”表示B。当传输过程中发生1位错误时，码字就会变为“10”或“01”。当接收端接收到“10”或“01”时，只能检测到错误，而不能自动纠正错误。这是因为存在着不准使用的码字“10”和“01”的缘故，即存在禁用码组。相对于禁用码组而言，把允许使用的码组称为许用码组。这表明在信息码元后面附加一位监督码元后，当只发生一位错码时，码字具有检错能力。但由于不能判决是哪一位发生了错码，所以没有纠错能力。
当增加2位冗余码，即采用重复码（3，1）。如用“000”表示A，用“111”表示B。此时的禁用码组为“100”、“010”、“001”、“011”、“101”和“110”。当传输过程中发生1位错误时，码字就会变为“100”、“010”、“001”、“011”、“101”或“110”。例如，当接收端收到“100”时，收端就会按照“大数法则”自动恢复为“000”，认为信息发生了1位错码。此时接收端不仅能检测到1位错误，而且还能自动纠正该错误。但是当出现2位错误时，例如，“000”会错成“100”、“010”或“001”，当接收端收到这三种码时，就会认为信息有错，但不知是那位错了，此时只能检测到2位错。如果在传输过程中发生了3位错，接收端收到的是许用码组，此时不再具有检错能力。因此，这时的信道编码具有检出两位错和两位以下错码的能力，或者具有纠正一位错码的能力。
当增加3位冗余码，即采用重复码（4，1）。如用“0000”表示A，用“1111”表示B。此时接收端能纠正1位错误，用于检错时能检测3位错误。
由此可见，增加冗余码的个数就能增加纠检错能力。
3.2.2 差错控制编码的分类
根据编码方式和不同的衡量标准，差错控制编码有多种形式和类别。下面我们简单地介绍几种主要分类。
(1)根据编码功能可分为检错码、纠错码和纠删码三种类型，只能完成检错功能的码叫检错码；具有纠错能力的码叫纠错码；而纠删码既可检错也可纠错。
(2)按照信息码元和附加的监督码元之间的检验关系可以分为线性码和非线性码。若信息码元与监督码元之间的关系为线性关系，即监督码元是信息码元的线性组合，则称为线性码。反之，若两者不存在线性关系，则称为非线性码。
(3)按照信息码元和监督码元之间的约束方式可分为分组码和卷积码。在分组码中，编码前先把信息序列分为k位一组，然后用一定规则附加m位监督码元，形成n k m
=+
位的码组。监督码元仅与本码组的信息码元有关，而与其它码组的信息码元无关。但在卷积码中，码组中的监督码元不但与本组信息码元有关，而且与前面码组的信息码元也有约束关系，就像链条那样一环扣—环；所以卷积码又称连环码或链码。
(4)系统码与非系统码。在线性分组码中所有码组的k位信息码元在编码前后保持原
来形式的码叫系统码，反之就是非系统码。系统码与非系统码在性能上大致相同，而且系统码的编、译码都相对比较简单，因此得到广泛应用。
(5)纠正随机错误码和纠正突发错误码。顾名思义，前者用于纠正因信道中出现的随机独立干扰引起的误码，后者主要对付信道中出现的突发错误。
从上述分类中可以看到，一种编码可以具有多样性，本章主要介绍纠正随机错误的二进制线性分组码。
3.2.3 差错控制编码的基本概念
1、码长、码重、码距和编码效率
码组又称码字或码矢。码组中编码的总位数称为码组的长度，简称为码长。如，码组 “11001”的码长为5，码组 “110001”的码长为6。
码组中非“0”元的数目（即“1”码元的个数）称为码组的重量，简称码重。常用W 表示。如，码组 “11001”的码重为3W =，码组 “110001”的码重也为3W =。它反映一个码组中“0”和“1”的“比重”。
所谓码元距离就是两个等长码组之间对应码位上码元不同的个数，简称码距（也称汉明距）。码距反映的是码组之间的差异程度，比如，00和01两组码的码距为1；011和100的码距为3。那么，多个码组之间相互比较，可能会有不同的码距，其中的最小值被称为最小码距（用0d 表示）。它是衡量编码纠/检错能力的重要依据。比如，000、001、110三个码组相比较，码距有1和2两个值，则最小码距为01d =。
n k r
=+码长个信息位
个监督位k
r 1n a -2n a -r a 1r a -0a ......
3-2 分组码的结构图 在一个码长为n 的编码序列中，信息位为k 位，它表示所传递的信息；监督位为r 位，它表示增加的冗余位。分组码一般可表示为(,)n k ，其中，r n k =-。具体形式如图3-2所示。图中前k 位12(,,
,)n n r a a a --为信息位，后面r 位120(,,,)r r a a a --为监督位。则其
编码效率c R 可定义为
c k
R n = （3.1） 而其监督元个数r 和信息元个数k 之比定义为冗余度。因为k n <，所以，1c R <。显然，编码的冗余度越大，编码效率越低。也就是说，通信系统可靠性的提高是以降低有效性（即编码效率）来换取的。差错控制编码的关键之一就是寻找一种好的编码方法，即在一定的差错控制能力的要求下，使得编码效率尽可能的高，同时译码方法尽可能的简单。
2、抗干扰能力与最小码距的关系
最小码距0d 与纠/检错能力间有着密切的关系，它们之间的关系为：
(a)(b)
(c)
图3-3 码距与检错和纠错能力间的关系 （1）检测e 个随机错误，要求最小码距0d 为：
01d e ≥+ （3.2）
可用几何图形简要证明（3.2）式。设一个码组A 位于O 点。若码组A 中发生一个错码，则可认为A 的位置将移动至以O 点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。若码组A 中发生两位错码，则其位置不会超出以O 点为圆心，以2为半径的圆。依此类推，若码组A 中发生e 位错码，则其位置不会超出以O 点为圆心，以e 为半径的圆。如图3-3（a ）所示，若要检测e 位错码，则最小码距0d 至少应不小于1e +，即01d e ≥+。因为01d e =+时，码组集合中的其它码字均在以A 为圆心、以e 为半径的圆外，所以就能和错码区别开。
（2）在一个码组内要想纠正t 位误码，要求最小码距0d 为
021d t ≥+ （3.3）
此式可以用图3-3（b ）来说明。图中码组A 和B 间的距离为0d 。码组A 或B 若发生不多于t 位错码时，则其位置均不会超出以t 为半径，以原位置为圆心的圆。只要这两圆不相交，则就不会发生混淆，码字落在那个圆内就可判为对应码字，所以它能够纠正
错码。此时，两圆不相交的最小距离为21t +，故最小码距0d 应大于等于21t +，即021d t ≥+。
（3）在一个码组内要想纠正t 位误码，同时检测出e 位误码（e t ≥）,要求最小码距0d 为
01d t e ≥++
（3.4） 在这种情况下，若接收码组与某一许用码组间的距离在纠错能力t 范围内，则将按纠错方式工作；若与任何许用码组间的距离都超过t ，则按检错方式工作。可用图3-3（c ）来说明。若设检错能力为e ，则当码组A 中存在e 个错码时，该码组与任一许用码组的距离至少应有1t +，否则将进入许用码组B 的纠错能力范围内，而被纠为B 。
综上所述，要提高编码的纠、检错能力，不能仅靠简单地增加监督码元位数（即冗余度），更重要的是要加大最小码距（即码组之间的差异程度），而最小码距的大小与编码的冗余度是有关的，最小码距增大，码元的冗余度就增大。但当码元的冗余度增大时，最小码距不一定增大。因此，一种编码方式具有检错和纠错能力的必要条件是信息编码必须有冗余，而充分条件是码元之间要有一定的码距。另外，检错要求的冗余度比纠错要低。
信道编码中两个最主要的参数是最小码距0d 与编码效率c R 。一般说来，这两个参数是相互矛盾的，编码的检、纠错能力越强，最小码距0d 就越大，而编码效率c R 就越小。所以，纠错编码的任务就是构造出编码效率c R 一定时，最小码距0d 尽可能大的码；或最小码距0d 一定时，而编码效率c R 尽可能大的码。
3.3 常见的几种检错码
3.3.1 奇偶校验码
奇偶校验码是数据通信中最常见的一种简单检错码，它分为奇数校验码和偶数校验码。虽然有两种编码方式，但其编码原理是相同的。其编码规则是：把信息码先分组，形成多个许用码组，在每一个许用码组最后（最低位）加上一位监督码元即可。加上监督码元后使该码组中1的数目为奇数的编码称为奇校验码，为偶数的编码称为偶校验码。根据编码分类，可知奇偶校验码属于一种检错、线性、分组系统码。
奇偶校验码的监督关系可以用以下公式进行表述。假设一个码组的长度为n (在计算机通信中，常为一个字节)，表示为120(,,,)n n A a a a --=，其中前1n -位是信息码，最后一位0a 为校验位（或监督位），那么，对于偶校验码必须保证
12300n n n a a a a ---⊕⊕⊕⊕= （3.5）
校验码元（或监督码元）0a 的取值（0或1）可由下式决定：
01231n n n a a a a a ---=⊕⊕⊕⊕ （3.6）
对于奇校验码而言，要求必须保证
12301n n n a a a a ---⊕⊕⊕⊕= （3.7）
校验码元0a 的取值（0或1）可由下式决定：
012311n n n a a a a a ---=⊕⊕⊕⊕⊕ （3.8）
根据奇偶校验的规则我们可以看到，当码组中的误码为偶数时，校验失效。比如有两位发生错误，会有这样几种情况：00变成11、11变成00、01变成10、10变成01，可见无论哪种情况出现都不会改变码组的奇偶性，偶校验码中1的个数仍为偶数，奇校验码中1的个数仍为奇数。
下面我们讨论奇偶校检码的码距问题。假设两个码组同为奇数（或偶数）码组，如果两组码只有1位不同，则它们的奇偶性就不同，这与假设相矛盾；如果两组码有2位不同，则它们的奇偶性不变。换句话说，构造不出码距为1的奇偶校检码，所以奇偶校验码的最小码距为2。因此，简单的奇偶校验码只能检测出单个或奇数个位发生错误的码组。其检错能力低，但编码效率1n n c R -=会随着n 的增加而增加。因奇偶校验码编码方式较为简单，所以在计算机通信中得到了较为广泛的应用。例如在传递标准ASCII 码时，通常采用7比特码元128种字符，在传输时再加1位奇偶校验位，成为8位码组，收端根据是否满足奇偶校验的条件来判断传输过程是否发生错误。
3.3.2 水平奇偶校验码
表3-2 水平奇偶校验码 0 1 0 1 1 0 1 1 0 0
0 1 0 1 0 1 0 0 1 0
0 0 1 1 0 0 0 0 1 1
1 1 0 0 0 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1
0 0 0 1 0 0 1 1 1 1
1 1 1 0 1 1 0 0 0 0信 息 码 元
监 督 码 元1001011
奇偶校验码检错能力低且不能检测突发错误，为了克服这个缺点，对奇偶校验码进行改进，得到了水平奇偶监督码。其基本原理是先将经过简单奇偶校验编码的码组按行排列成方阵，每一行是一个码组，若有n 个码组则方阵就有n 行。比如，有经过奇偶校验编码的7个码组010********、010********、00110000110、11000111001、00111111110、00010011111、11101100001排成方阵共有7行（见表3―2）。传输时发端按列进行传输，
即000100111010010010101…1001011。收端按列接收后再按行还原成发端的方阵，然后按行进行奇偶校验，则纠错情况就会发生变化。观察该表可见，因为是逐列发送，在一列中不管出现几个误码（偶数个或奇数个），对应在每一行都只是一位误码，所以都可以通过水平奇偶校验检验出来；但对于每一行（一个码组）而言仍然只能检出所有奇数个错误。与简单奇偶校验编码相比，它除了具备奇偶校验码的检错能力外，还可以检出所有长度小于行数（码组数）的突发错误。
3.3.3 水平垂直奇偶校验码
在上述水平奇偶校验编码的基础上，若再加上垂直奇偶校验编码就构成水平垂直奇偶校验码。比如对表3―2的7个码组再加上一行就构成水平垂直奇偶校验码，如表3―3所示。 水平垂直奇偶校验码在发送时仍按列发送，收端顺序接收后仍还原成表3-3的方阵形式。这种码既可以逐行传输，也可以逐列传输。水平垂直奇偶校验码比简单奇偶校验码多了个列校验，因此，其检错能力有所提高。除了检出行中的所有奇数个误码及长度不大于行数的突发性错误外，还可检出列中的所有奇数个误码及长度不大于列数的突发性错误。同时还能检出码组中大多数出现偶数个错误的情况，比如，在码组1中，头两位发生错误，从01变成10，则第1列的1就变成3个，第2列的1也变成3个，而两列的校验码元都是0，所以可以查出这两列有错误。也就是说，码组中出现了2位（偶数位）误码，但具体是哪一个码组（那一行）出现误码还无法判断。
表3-3 水平垂直奇偶校验码 0 1 0 1 1 0 1 1 0 0
0 1 0 1 0 1 0 0 1 0
0 0 1 1 0 0 0 0 1 1
1 1 0 0 0 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1
0 0 0 1 0 0 1 1 1 1
1 1 1 0 1 1 0 0 0 0
信 息 码 元
监 督 码 元10010110 0 1 1 1 0 0 0 0 10
3.3.4 恒比码
恒比码是码组中1的数目与0 的数目保持恒定比例的一种码。由于恒比码中每个码组均含有相同数目的1和0，因此恒比码又称为等重码或定1码。这种码通过计算接收码组中“1”的数目是否正确，就可检测出有无错误。表3-4是我国邮电部门在国内通信中采用的五单位数字保护电码，它是一种五中取三的恒比码，也称作为3:2恒比码。
每个码组的长度为5，其中“1”的个数为3，每个许用码组中“1”和“0”个数的比值恒为3/2。许用码组的个数就是5中取3的组合数，即3542510C ?==，正好可以表示10个阿拉伯数字。实践证明，采用这种码后，我国汉字电报的差错概率大为降低。不难看出这种码的最小码距是2，它能够检出码组中所有奇数个错误和部分偶数个错误。该码也是非线性分组码，但不是系统码，其主要优点是简单，适用于对电传机或其它键盘设备产生的字母和符号进行编码。
表3-4 3:2恒比码 数 字码 字 0 0 1 1 0 1
1 0 1 0 1 1
2 1 1 0 0 1
3 1 0 1 1 0
4 1 1 0 1 0
5 0 0 1 1 1
6 1 0 1 0 1
7 1 1 1 0 0
8 0 1 1 1 0
9 1 0 0 1 1
数 字码 字
另外，目前国际上的ARQ 电报通信系统中采用的3:4码也是一种恒比码，又称为“7”
中取“3”码。它的码组数量为3765327
35C ???==，代表26个英文字母和其它符号。实践证明，这种码使通信的误码率保持在610-以下。
3.3.5群计数码
在奇偶校验码中，我们通过添加监督位将码组的码重配成奇数或偶数。而群计数码就是先将信息码元分组后，计算出信息码组的码重（即码组中“1”的个数），然后用二进制计数法表示并作为监督码元添加到信息码组的后面。比如表3-3中的7个信息码组变成群计数码后的形式见表3-5。收端只要检测监督码元所表示的“1”的个数与信息码元中“1”的个数是否相同来判断错误与否。
表3-5 群计数码 0 1 0 1 1 0 1 1 0 0
0 1 0 1 0 1 0 0 1 0
0 0 1 1 0 0 0 0 1 1
1 1 0 0 0 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1
0 0 0 1 0 0 1 1 1 1
1 1 1 0 1 1 0 0 0 0
信 息 码 元
监 督 码 元0 1 0 10 1 0 00 1 0 00 1 0 11 0 0 00 1 0 10 1 0 1
这种码属于非线性分组系统码，检错能力很强，除了能检出码组中奇数个错误之外，还能检出偶数个1变0或0变1的错误，但对1变0和0变1成对出现的误码无能为力。可以验证，除了无法检出1变0和0变1成对出现的误码外，这种码可以检出其它所有形式的错误。
3.4 线性分组码
在计算机通信中，信源输出的是由“0”和“1”组成的二进制序列，在分组码中，该二元信息序列被分成码元个数固定的一组组信息，每组信息的码元由k 位二进制码元组成，则共有2k 个不同的组合，即不同的信息。信道编码器就是要对这2k 个不同的信息用2k 个不同的码组（或码字）表示，2k 个码组的位数是一样的。假设为n ，且n >k ，则这2k 个码组的集合就被称作为分组码。简单地说，将信息码进行分组，然后为每组信息码附加若干位监督码元的编码方法得到的码集合称为分组码。为讨论方便，我们把由k 位二进制码元构成2k 个信息码组用矩阵D 表示，则由n 位二进制码元组成的分组码中就必须有2k 个不同的码组才能代表2k 个信息，把这2k 个不同的码组用矩阵C 表示，则D 和C 必须一一对应。因为n >k ，所以，在一个n 位码组中，有n -k 个不代表信息的码元，这些码元被称为监督码元或校验码元。显然，如果上述分组码每个码组之间没有关系的话（彼此独立），则对于大的k 值或n 值（信息码或分组码的码长很大），编码设备会极为复杂，因为编码设备必须储存2k 个码长为n 的码组。因此，我们需要构造码组之间有某种关系的分组码，以降低编码的复杂性，线性分组码就是满足这一条件的一种分组码。
3.4.1 基本概念
所谓线性分组码就是一种长度为n ，其中2k 个许用码组（代表信息的码组）中的任意两个码组的模2和仍为一个许用码组的分组码。或者说，可用线性方程组表述码规律性的分组码。这种长度为n ，有2k 个码组的线性分组码我们称为线性（n ，k ）码（或（n ，k ）线性码）。分组码中的每个码组可用向量来表示，即120(,,,)n n A a a a --=，其中前k 位为信息位，后r 位为监督位。其结构如图3-2所示。
线性分组码是一种群码，对于模2加运算具有以下性质：
（1）满足封闭性：即任意两个许用码组之和仍为一许用码组，这种性质也成为自闭率；
（2）有零元：所有信息元和监督元均为零的码组，称为零码，即[]000
0A =。
任一码组与零码相运算其值不变，即，0i i A A A =⊕
（3）有负元：线性分组码中的任一码组即是它自身的负元，即i i i A A A =⊕。
（4）满足结合律：即123123()()A A A A A A ⊕⊕=⊕⊕。
（5）满足交换律：1221A A A A ⊕=⊕。
（6）线性分组码的最小码距等于非零码的最小码重，即
0[,]
min ()i i A n k d W A ∈= （3.9） 在线性分组码还具有以下特点：
（1）01212(,)()()d A A W A W A ≤+；
（2）012023013(,)(,)(,)d A A d A A d A A +≥；
（3）码字的重量或全部为偶数，或奇数重量的码字数等于偶数重量的码字数。
3.4.2 线性分组码的编码
对于线性分组码而言，信息元与监督元之间的关系可以用一组线性方程来表示。设线性分组码的码字为120(,,,)n n A a a a --=，其中前k 位为信息位，后r 位为监督位。下面以（7，3）码为例来描述线性分组码的编码原理。
在（7，3）线性分组码中，码长7n =，信息元的个数3k =，则监督元的个数4r =。（7，3）码的每一个码组可写成6543210(,,,,,,)A a a a a a a a =，其中654,,a a a 为信息位，3210,,,a a a a 为监督位。它们之间的监督关系可用线性方程组描述为：
3654264154
065
a a a a a a a a a a a a a =⊕⊕??=⊕??=⊕??=⊕? （3.10） 表3-6 （7，3）线性分组码 信息元监督元序 号
0 000 00001 001 11012 010 01113 011 1010 4 100 1110
5 101 0011
6 110 1001
7 111 0100码 元
信息元监督元
序 号码 元
因为信息元个数3k =，所以只有8种许用码组。可由监督方程（3.10）写出许用码
组，如表3-6所示。
1 生成矩阵
对（3.10）式进行改写，各位码元与信息位654,,a a a 之间的关系为：
665
54436542
641540
65a a a a a a a a a a a a a a a a a a a =??=??=?=⊕⊕??=⊕?=⊕??=⊕? （3.11）
将式（3.11）用矩阵表示
65463524101000100011
111010
11110a a a a a a a a a a ????????????????????????=?????????????????????????????
?? （3.12） 或 [][]6
543210654100110101010110011110a a a a a a a a a a ????=??????? （3.13） 记[]6543210A a a a a a a a =，[]6
54M a a a =， []31001
1010101
0110011110G I Q ????==??????
（3.14）
则式（3.12）和（3.13）分别可简记为
T T T A G M =? （3.15）
A M G =? （3.16）
其中，G 称为生成矩阵，是一个37?阶的矩阵。G 的行数是信息元的个数，列数是码长。3I 为33?阶的单位方阵，其行数是信息元的个数；Q 为34?阶的矩阵，其行数是信息元的个数，列数是元的个数。根据（3.16）式，由信息位和生成矩阵G 就可以产生全部码组。
可将其理论推广到任意线性分组码。对于一个(,)n k 线性分组码而言，生成矩阵G 是
一个k n ?阶的矩阵，也可分为两部分，即
[]k
G I Q = （3.17）
其中， 111212122212
r r k k kr q q q q q q Q q q q ??
????=?????? （3.18） Q 是一个k r ?阶矩阵；k I 为k 阶单位方阵。把具有[]k I Q 形式的生成矩阵称为典型生成矩阵。非典型形式的生成矩阵经过运算一定能化为典型矩阵。
（n ，k ）线性分组码完全由生成矩阵G 的k 行元素决定，即任意一个分组码码组都是G 的线性组合。而（n ，k ）线性码中的任何k 个线性无关的码组都可用来构成生成矩阵，所以，生成矩阵G 的各行都线性无关。如果各行之间是线性相关的，就不可能由G 生成2k 个不同的码组了。其实，G 的各行本身就是一个码组。如果已有k 个线性无关的码组，则可用其直接构成G 矩阵，并由此生成其余码组。
综上所述，由于可以用一个k ×n 阶矩阵G 生成2k 个不同的码组，因此，编码器只需储存G 矩阵的k 行元素（而不是一般分组码的2k 码组），就可根据信息向量构造出相应的一个分组码码组（或根据信息码矩阵构造出相应的一个分组码矩阵），从而降低了编码的复杂性，并提高了编码效率。
2 监督矩阵
将方程（3.10）式移项，可得到四个相互独立的监督方程组：
654364254165
00000a a a a a a a a a a a a a ⊕⊕⊕=??⊕⊕=??⊕⊕=??⊕⊕=? （3.19） 将式（3.19）可用矩阵表示为
6543210111100001010100001100100110000
10T a a a a O a a a ????
???????????????????==???????????????????????? （3.20） 或
[][]654321011011011111000001
00001000
0100001a a a a a a a O ???????????==????????????
（3.21） 记[]6543210A a a a a a a a =，[]0000O =，T O 为O 的转置，
[]41111000101010001100101100001H P I ??????==?????
? （3.22）
则式（3.20）可简记为
T T H A O ?= （3.23）
或
T A H O ?= （3.24）
其中，T H 表示H 的转置。H 被称为监督矩阵，或校验矩阵。只要监督矩阵H 给定，编码时监督位和信息位的关系就完全确定了。由（3.22）式可看出，H 的行数就是监督关系式的数目，它等于监督位（监督元）的数目4，列数是码长7。监督矩阵H 的每行中“1”的位置表示相应码元之间存在的监督关系。例如，H 的第一行1111000表示监督位3a 是由信息位654a a a 之和决定的。式（3.22）中的H 矩阵可以分成P 和4I 两部分。其中，P 是一个43?阶矩阵； 4I 为4阶单位方阵；3表示信息位（信息元）个数，4表示监督位（监督元）个数。（3.24）式说明线性分组码中任一码组与校验矩阵H 的转置相乘，其结果为r 位全零向量，因此，用校验矩阵检查二元序列是不是给定分组码中的码组非常方便，“校验”之名由此而来。
可将其理论推广到任意线性分组码。对于一个(,)n k 线性分组码而言，监督矩阵H 是一个r n ?阶的矩阵，也可分为两部分，即
[]r H P I = （3.25）
其中，
1112121
2221
2k k r r rk p p p p q p P p p p ??????=?????? （3.26）
P 是一个r k ?阶矩阵；r I 为r 阶单位方阵。把具有[]r P I 形式的监督矩阵称为典型监督矩阵。根据典型监督矩阵和信息码元很容易算出各监督码元。非典型形式的监督矩阵经过运算一定能化为典型矩阵。
由代数理论可知，监督矩阵H 的各行应该是线性无关的，否则将得不到r 个线性无关的监督关系式，也得不到r 个独立的监督位。若一矩阵能写成典型阵形式[]r P I ，那么其各行一定是线性无关的。
3 监督矩阵和生成矩阵间的关系
由上面的推导可知，生成矩阵G 与监督矩阵H 之间有一一对应关系。由于G 的每一行都是码字，因此它必然满足公式（3.23），即
T T H A O ?=
所以，
[][][]T k
n k k n k T T k n k T T
I P I I Q P I Q PI I Q P Q O ---???=?????
??=⊕????=⊕??
= （3.27）
其中，O 为k r ?阶零矩阵；⊕为模2加。只有当T P Q =时，式（3.27）才为零。因此，生成矩阵可以写成
[]T k k G I Q I P ??==?? （3.28）
[]T n k n k H P I Q I --??==?
? （3.29） 由此可见，只要知道生成矩阵G ，就可以得到监督矩阵H ，反之也亦然。所以线性分组码由生成矩阵或监督矩阵来完全确定。
3.4.3 线性分组码的译码
由前面的讨论可以看出，若某一码字为许用码组，则必然满足式（3.24）。利用这一关系，接收端就可以用接收到的码组和事先与发端约定好的监督矩阵相乘，看是否为零。若满足条件，则认为接收正确；反之，则认为传输过程中发生了错误，进而设法确定错误的数目和位置。
假设发送码组为120(,,,)n n A a a a --=，接收码组为120(,,,)n n B b b b --=。由于发送码组在传输的过程中会受到干扰，致使接收码组与发送码组不一定相同。因此，定义发送码组和接收码组之差为
(2)B A E -=模和 （3.30）
E 是传输中产生的错码行矩阵，即
[]12
0E e e e = （3.31）
其中， 01i i i i i
b a e b a =?=?≠?当当 （3.32） 若0i e =，表示该位接收码元无误；若1i e =，则表示该位接收码元有误。E 是一个由“1”和“0”组成的行矩阵，它反映误码状况，被称为错误图样。例如，若发送码组[]1001101A =，接收码组[]1001001B =，显然B 中有一个错误。由（3.30）可得错误图样为[]0000100E =。可见，E 的码重就是误码的个数，因此E 的码重越小越好。另外，式（3.30）也可以改写为
B A E =⊕ （3.33）
当接收端接收到码组B 时，可用监督矩阵H 进行校验，即将接收码组B 代入式（3.24）进行验证。若接收码组中无错码，即E O =，则B A E A =⊕=。即把B 代入式（3.24）后该式仍然成立，则有
T B H O ?= （3.34）
当接收码组有误时，即E O ≠，则B A E =⊕。即把B 代入式（3.24）后该式不成立，则有T B H O ?≠。我们定义
T B H S ?= （3.35）
将B A E =⊕代入式（3.35）中，可得
()T
T
T T
T S B H A E H A H E H E H =?=⊕?=?⊕?=? （3.36）
其中，S 是一个r 维的行向量，被称为校正子，或伴随式。式（3.36）标明伴随式S 与错误图样E 之间有确定的线性变换关系，而与发送码组A 无关。所以，可以采用伴随式S 来判断传输中是否发生了错误。若伴随式S 与错误图样E 之间一一对应，则伴随式S 将能代表错码发生的位置。例如，[]1001101A =，[]1001001B =，则[]0000100E =，把（3.22）式的H 代入（3.35）式，可得[]0100S =。
为了进一步分析码组中不同码元发生一位错码的情况，仍以表3-6中的（7，3）线性分组码为例，来描述伴随式与错误图样之间的对应关系。如表3-7所示。
从表3-7可以看出：发生一位错误时，T S 与监督矩阵H 的列一一对应。如0b 发生错误，则T S 与监督矩阵H 的最后一列相同；1b 发生错误，则T S 与监督矩阵H 的倒数第二列相同，以此类推。故接收端可以根据这种关系纠正一位错误。对于(,)n k 线性分组
码，S 有2r 中不同的形式，可代表21r -种错误图样。为了指明单个错误的位置，必须要求：
表3-7 伴随式与错误图样的对应关系 1 0000001 00010
b 编 号 错码位置E S
2 0000010 0010
3 0000100 0100
4 0001000 1000
5 0010000 1110
6 0100000 1011
7 1000000 11011b 2
b 3b 4
b 5
b 6b
21r n -≥ （3.37）
注意：若传输过程中错码的位置不止一位时，S 可能与表3-7中所列的任意一种都不同，这时系统只能检错而不能纠错，并根据不同系统的要求将该码组丢弃或重发。此时，S 也有可能正好与发生一位错误时的某种伴随式相同，这样经纠错后反而“越纠越错”。在传输过程中，发送码组的某几位发生错误后成为另一许用码组，这种情况接收端无法检测，称这种为不可检测的错误。不过从统计学的观点来看，这种情况出现的概率要小得多，可忽略。
从以上分析可以得到线性分组码的译码过程为：
（1）根据接收码组B 计算其伴随式S ；
（2）根据伴随式S 找出对应的错误图样E ，并确定误码位置；
（3）根据错误图样E 和A B E =⊕得到正确的码组A 。
3.5 循环码
循环码是线性分组码的一个重要分支。循环码有许多特殊的代数性质，基于这些性质，循环码有较强的纠错能力（即它既能纠正独立的随机错误又能纠正突出错误），而且其编码和译码电路很容易用移位寄存器实现，因而在FEC 系统中得到了广泛的应用。
3.5.1 基本概念
循环码可定义为：对于一个（n ，k ）线性分组码，若其中的任一码组向左或向右循环移动任意位后仍是码组集合中的一个码组，则称其为循环码。循环码是一种分组码，前k 位为信息码元，后r 位为监督码元。它除了具有线性分组码的性质之外，还具有一个独特的性质即循环性。所谓循环性，是指任一许用码组经过循环移位后所得到的码组仍为一许用码组。
若120(,,
,)n n A a a a --=是循环码中的一个许用码组，对它左循环移位一次，得到1201(,
,,)n n A a a a --=也是一个许用码组，移位i 次得到1201(,,
,,,)i i i n i A a a a a a ++-=还是许
用码组。不论右移或左移，移位位数多少，其结果均为循环码组。以（7，3）循环码和（6，3）循环码为例，其全部码组见表3-8。
表3-8 （7，3）循环码和（6，3）循环码的全部码组 编 号1 0 0 0 0 0 0 0 0 0 0 0 0 0
（7，3）循环码（6，3）循环码
8 1 1 1 0 1 0 0 1 1 1 1 1 17 1 1 0 1 0 0 1 1 1 0 1 1 0
6 1 0 1 0 0 1 1 1 0 1 1 0 1
5 1 0 0 1 1 1 0 1 0 0 1 0 0
4 0 1 1 1 0 1 0 0 1 1 0 1 1
3 0 1 0 0 1 1 1 0 1 0 0 1 0
2 0 0 1 1 1 0 1 0 0 1 0 0 1
由表3-8可看出：（7，3）循环码有两个循环圈，如图3-4（a ）所示。其中，编号为1的全零码组自成循环圈，其码重为0W =；另一个是剩余码组组成的循环圈，其码重为4W =。（6，3）循环码的循环圈有四个，如图3-4（b ）所示。（6，3）循环码构成了码重分别为0、2、4和
6的循环圈。由图3-4可得，同一循环圈上的码字具有相同的码重。
左移图3-4
（a ） （7，3）循环码的循环圈
左移左移图3-4 (b) （6，3）循环码的循环圈
为了便于用代数理论分析循环码，可以将循环码的码字用代数多项式来表示，把这
个表示码字的代数多项式称为码多项式。把码长n 的码组120(,,
,)n n A a a a --=可表示为 121210()n n n n T x a x a x a x a ----=++++ （3.38）
例如，若码字为1110100，则其对应的码多项式为
654326542()1110100
T x x x x x x x x x x x =?+?+?+?+?+?+=+++ （3.39）
在码多项式中，变量x 称为元素，其幂次对应元素的位置，它的系数即为元素的取值（我们不关心x 本身的取值），系数之间的加法和乘法仍服从模2规则。如式（3.39）中 1仅表示码元出现在6a 、5a 、4a 和2a 位上，其余均为0。
1 码多项式的按模运算
下面我们来介绍多项式的按模运算。如果一个多项式()F x 被另一个n 次多项式()N x
除，得到一个商式()Q x 和一个次数小于n 的余式()R x ，即
()()()()F x N x Q x R x =+ （3.40）
可记作为：
()()[mod ()]F x R x N x ≡ （3.41）
则称作为在模()N x 运算下，()()F x R x ≡。
例如 ，51x +被31x +除时，由于2
52
311x x x x +=++，所以 5231[mod(1)]x x x +≡+
注意：在模2计算中，系数只能为“0”或“1”，故在多项式的余式中是1x +，而不是1x -+。
将式(3.38)乘以x ，再除以(1)n x +，则可得：
122231011()11
n n n n n n n n a x a x a x a x a xT x a x x ------+++++=+++ （3.42） 式（3.42）表明：码多项式()T x 乘以x 再除以(1)n x +所得余式就是码组左循环一次的码多项式。由此可知，循环码左循环移位i 次后的码多项式就是将()i x T x 按模(1)n x +做运算后所得的余式。
2 循环码的生成多项式和生成矩阵
我们在前面已经讲过，循环码属于线性分组码，它除了具有循环特性外，还具有线
摘要 本文首先介绍了电子设计自动化（EDA）技术的主要特征、现状和前景，并就课题的研究方向做了有关论述；进一步研究了EDA技术的发展对电路设计方法的影响，深入探讨了用VHDL语言和复杂系统可编程逻辑器件(CPLD)开发的基本方法，作为应用对象，进一步研制、开发了循环冗余差错校验编码(CRC)、RS(255,239)编码和MD5编码。通过对前两种编码各个模块的设计，完整阐述了对前两种编码软件部分的设计；又通过硬件的测试，完善，修改，最终完成了各自独立的编码程序。基于VHDL语言，利用FPGA器件开发的差错控制编码系统，采用了自顶向下的设计方法，系统的顶层设计和底层设计采用原理图输入描述和VHDL语言进行设计，选用当前应用最广泛的EDA软件QUARTUS II作为开发平台，所有程序全部通过了该平台的编译和功能仿真测试，得出了实际的仿真波形，最后，对设计调试过程中出现的问题进行了分析、研究、解决。我还对上述这些各种编码的异同点进行了总结，对MD5编码进行了算法分析，从而对这些编码进行研究。 关键词： 循环冗余差错校验编码 FPGA QUARTUS II VHDL语言 RS编码 MD5
Abstract This text first introduction electronics design automation(EDA) technique of main characteristic, present condition and foreground, and topic of research the direction did relevant discuss;Further research EDA technique of development to electric circuit design method of influence, thorough study use VHDL language and complications system programmable logic spare part(CPLD) development of basic method, Be application object, further develop, development circulation redundancy mistake the school check code(CRC), RS(255,239) code and MD5 code.Pass to two kinds of ex- code each mold piece of one by one introduction, integrity elaborate to two kinds of ex- code software part of design;The test passed hardware again, perfect, modification, end completion independence of respectively code procedure.According to the VHDL language, application FPGA spare part development of mistake control code system, adoption from crest get down of design method, the crest of the system layer design and first floor design adoption principle diagram importation description and the VHDL language carry on design, choose to use current application most extensive of EDA software QUARTUS II Be development terrace, all all of the procedures passed that edit and translate of terrace and function to imitate true test, give actual of imitate true wave form, end, to design adjust to try to appear in the process of the problem carried on analysis, research, solve.I return various to these code of different and similar point carried on summary, to MD5 code carried on calculate way analysis, thus to these code carry on research. Keywords: Cyclic Redundancy Check Field Programmable Gate Array QUARTUS II VHDL language RS code Message-Digest Algorithm 5
第五章 差错控制与信道编码
内容简介
学习要求
学习目录
结束放映
作者：蒋占军
内容简介
——差错控制就是通过某种方法，发现并纠正数据传输中出现的 错误。差错控制技术是提高数据传输可靠性的重要手段之一，现 代数据通信中使用的差错控制方式大都是基于信道编码技术来实 现的，本章对差错控制的基本概念以及常用的信道编码方案作了 比较详细的理论述。
返回
结束
学习要求
1. 理解差错控制的基本概念及其原理等； 2. 掌握信道编码的基本原理； 3. 了解常用检错码的特性； 4. 掌握线性分组码的一般特性； 5. 掌握汉明码以及循环码的编译码及其实现原理； 6. 了解卷积码的基本概念。
返回
结束
学习目录
5.1 概述 5.2 常用的简单信道编码 5.3 线性分组码 5.4 卷积码
返回
结束
5.1 概 述
本节内容提要：
——差错控制是数据通信系统中提高传输可靠性，降低系统传输误 码率的有效措施 。本节将介绍差错控制和信道编码的基本原理、 差错控制的实现方式等内容。 5.1.1 差错控制 5.1.2 信道编码 5.1.3 基于信道编码的差错控制方式
上一页
下一页
5.1.1 差错控制
差错控制 ——通过某种方法，发现并纠正传输中出现的错误。 香农信道编码定理 ——在具有确定信道容量的有扰信道中，若以低于信道容量的速率传输 数据，则存在某种编码方案，可以使传输的误码率足够小。 基于信道编码的差错控制 ——在发送端根据一定的规则，在数据序列中按照一定的规则附加一 些监督信息，接收端根据监督信息进行检错或者纠错。
上一页
下一页
第九章差错控制编码 9.1引言 一、信源编码与信道编码 数字通信中，根据不同的目的，编码分为信源编码与信道编码二大类。 信源编码~ 提高数字信号的有效性，如，PCM编码，M 编码，图象数据压缩编码等。 信道编码~ 提高传输的可靠性，又称抗干扰编码，纠错编码。 由于数字通信传输过程中，受到干扰，乘性干扰引起的码间干扰，可用均衡办法解决。 加性干扰解决的办法有：选择调制解码，提高发射功率。 如果上述措施难以满足要求，则要考虑本章讨论的信道编码技术，对误码（可能或已经出现）进行差错控制。 从差错控制角度看：信道分三类：（信道编码技术） ①随机信道：由加性白噪声引起的误码，错码是随机的，错码间统计独立。 ②突发信道：错码成串，由脉冲噪声干扰引起。 ③混合信道：既存在随机错误，又存在突发错码，那一种都不能忽略不计的信道。 信道编码（差错控制编码）是使不带规律性的原始数字信号，带上规律性（或加强规律性，或规律性不强）的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进而纠错。 需要说明的是信道编码是用增加数码，增加冗余来提高抗干扰能力。二：差错控制的工作方式 (1) 检错重发 (2) 前向纠错，不要反向信道 (3) 反馈校验法，双向信道 这三种差错控制的工作方式见下图所示： 检错重发 前向纠错 反馈校验法 检错误 判决信号 纠错码 信息信号 发 发 收 信息信号 152
153 9.2 纠错编码的基本原理 举例说明纠错编码的基本原理。 用三位二进制编码表示8种不同天气。 ???????? ?????雹 雾霜雪雨阴云 晴1 11 011101001 110010100000???→?种 许使用种中只准 48码组许用码组，其它为禁用雨阴云晴 0 11101110000 ??? ? ??? 许用码组中，只要错一位（不管哪位错），就是禁用码组，故这种编码能 发现任何一位出错，但不能发现的二位出错，二位出错后又产生许用码。 上述这种编码只能检测错误，不能纠正错误。 因为晴雨阴错一位，都变成1 0 0。 要想纠错，可以把8种组合（3位编码）中，只取2种为许用码，其它6种为禁用码。 例如： 0 0 0 晴 1 1 1 雨 这时，接收端能检测两个以下的错误，或者能纠正一个错码。 例：收到禁用码组1 0 0时，如认为只有一位错，则可判断此错码发生在第1位，从而纠正为0 0 0（晴），因为1 1 1（雨）发生任何一个错误都不会变成1 0 0。 若上述接收码组种的错码数认为不超过二个，则存在两种可能性： 位错） （位错）（21111000/变成（1 1 1）或（1 0 0）， 因为只能检出错误，但不能纠正。 一：分组码，码重，码距 （见樊书P282 表9-1） 将码组分段：分成信息位段和监督位段，称为分组码，记为（n, k ） n ~ 编码组的总位数，简称码长（码组的长度） k ~ 每组二进制信息码元数目，（信息位段） r k n =- ~ 监督码元数目，（监督位段）（见樊书P282，图9-2） 一组码共计8种
第九章差错控制编码（信道编码） 9.1引言 一、信源编码与信道编码 数字通信中，根据不同的目的，编码分为信源编码与信道编码二大类。 信源编码~ 提高数字信号的有效性，如，PCM编码，M 编码，图象数据压缩编码等。 信道编码~ 提高传输的可靠性，又称抗干扰编码，纠错编码。 由于数字通信传输过程中，受到干扰，乘性干扰引起的码间干扰，可用均衡办法解决。 加性干扰解决的办法有：选择调制解码，提高发射功率。 如果上述措施难以满足要求，则要考虑本章讨论的信道编码技术，对误码（可能或已经出现）进行差错控制。 从差错控制角度看：信道分三类：（信道编码技术） ①随机信道：由加性白噪声引起的误码，错码是随机的，错码间统计独立。 ②突发信道：错码成串，由脉冲噪声干扰引起。 ③混合信道：既存在随机错误，又存在突发错码，那一种都不能忽略不计的信道。 信道编码（差错控制编码）是使不带规律性的原始数字信号，带上规律性（或加强规律性，或规律性不强）的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进而纠错。 需要说明的是信道编码是用增加数码，增加冗余来提高抗干扰能力。二：差错控制的工作方式 (1) 检错重发 (2) 前向纠错，不要反向信道 (3) 反馈校验法，双向信道 这三种差错控制的工作方式见下图所示： 检错重发 前向纠错 反馈校验法 检错误 判决信号 纠错码 信息信号 发 发 收 信息信号
9.2 纠错编码的基本原理 举例说明纠错编码的基本原理。 用三位二进制编码表示8种不同天气。 ???????? ?????雹 雾 霜 雪 雨阴 云 晴111 0111 01001 11001010 0000???→ ?种 许使用种中只准 48码组许用码组，其它为禁用雨阴云晴 011101110000??? ? ??? 许用码组中，只要错一位（不管哪位错），就是禁用码组，故这种编码能发现任何一位出错，但不能发现的二位出错，二位出错后又产生许用码。 上述这种编码只能检测错误，不能纠正错误。 因为晴雨阴错一位，都变成1 0 0。 要想纠错，可以把8种组合（3位编码）中，只取2种为许用码，其它6种为禁用码。 例如： 0 0 0 晴 1 1 1 雨 这时，接收端能检测两个以下的错误，或者能纠正一个错码。 例：收到禁用码组1 0 0时，如认为只有一位错，则可判断此错码发生在第1位，从而纠正为0 0 0（晴），因为1 1 1（雨）发生任何一个错误都不会变成1 0 0。 若上述接收码组种的错码数认为不超过二个，则存在两种可能性： 位错） （位错）（21111000/变成100 因为只能检出错误，但不能纠正。 一：分组码，码重，码距 （见樊书P282 表9-1） 将码组分段：分成信息位段和监督位段，称为分组码，记为（n, k ） n ~ 编码组的总位数，简称码长（码组的长度） k ~ 每组二进制信息码元数目，（信息位段） r k n =- ~ 监督码元数目，（监督位段）（见樊书P282，图9-2） 一组码共计8种
差错控制编码的SIMULINK建模与仿真一．线性分组码编码系统建模 Reed-Solomon码编码系统框图： 信源模块的系统框图： 信宿模块的系统框图： 1.循环冗余码编码系统建模与仿真 CRC-16编码系统框图：
信源模块的系统框图： 信宿模块的系统框图： 信号比较模块系统款图： M文件如下： x=[0.00001 0.0001 0.001 0.005 0.01 0.02 0.03 0.04 0.05 0.1 0.2 0.3 0.4 0.5]; y=x; ProtectedData=48; FrameInterval=0.010; BitPeriod=FrameInterval/ProtectedData;
ProtectedDataWithCRC=ProtectedData+16; FrameLength=480; SimulationTime=1000; TotalFrameNumber=SimulationTime/FrameInterval; for i=1:length(x) ChannelErrorRate=x(i); sim('project_2'); y(i)=MissedFrameNumber(length(MissedFrameNumber))/TotalFrameNumber; end loglog(x,y); 仿真结果：没有达到预想的结果，还有待改进。 二．卷积码编码系统建模与仿真： 1）卷积码编码系统在二进制对称信道中的性能 系统框图： M文件如下： x=[0.01 0.02 0.03 0.04 0.05 0.1 0.15 0.2 0.25 0.3 0.4 0.5];%x表示二进制对称信道的误比特率的各个取值 y=x;%y表示卷积编码信号的误码率，它的长度与x的长度相等 for i=1:length(x)%对x中的每个元素依次执行仿真
2.差错控制编码 2.1. 引言 什么是差错控制编码（纠错编码、信道编码）？ 为什么要引入差错控制编码？ 差错控制编码的3种方式？ 本章主要讲述：前向纠错编码（FEC）、常用的简单编码、线性分组码（汉明码、循环码）、简单介绍RS码*、BCH码*、FIRE码*、交织码，卷积码极其译码、TCM编码*。 一、什么是差错控制编码及为什么引入差错控制编码？ 在实际信道上传输数字信号时，由于信道传输特性不理想及加性噪声的影响，接收 端所收到的数字信号不可避免地会发生错误。为了在已知信噪比情况下达到一定的 误比特率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域、频域 均衡，使误比特率尽可能降低。但若误比特率仍不能满足要求，则必须采用信道编 码（即差错控制编码），将误比特率进一步降低，以满足系统指标要求。 随着差错控制编码理论的完善和数字电路技术的发展，信道编码已经成功地应用于 各种通信系统中，并且在计算机、磁记录与存储中也得到日益广泛的应用。 差错控制编码的基本思路：在发送端将被传输的信息附上一些监督码元，这些多余 的码元与信息码元之间以某种确定的规则相互关联（约束）。接收端按照既定的规 则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码 元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。 研究各种编码和译码方法是差错控制编码所要解决的问题。 二、差错控制的三种方式 1、检错重发（ARQ） 检错重发：在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向 信道要求发送端重新发送，直到接收端检查无误为止。 ARQ系统具有各种不同的重发机制：如可以停发等候重发、X.25协议的滑动窗 口选择重发等。 ARQ系统需要反馈信道，效率较低，但是能达到很好的性能。 2、前向纠错 前向纠错（FEC）：发送端发送能纠正错误的编码，在接收端根据接收到的码和 编码规则，能自动纠正传输中的错误。 不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂。
差错控制编码技术的应用 摘要：随着网络技术的发展,网络中数据交换量迅速增加,大量的数据需要通过网络进行交 换。在数据的传输过程中,由于种种原因,数据并不能保证100%的准确传输,数据传输的高准确率与高效率中间存在着比较难调和的矛盾。为了解决这个问题,便出现了通信中的差错控制技术,即通过将传送数据进行编码发送的方法来进行检错和纠正。 引言：无线应用的飞跃发展和广阔的应用前景，使得人们不得不把更多的目光投向无线网 络的通信。由于无线环境与有线环境相比，具有误码率高、时延长、带宽窄、信道不对称以及频繁的移动等特性，使无线网络中的通信质量难于保证。这样，怎样改善无线网络中的通信性能也自然成了目前乃至以后较长时期网络领域的重要研究课题。 一、差错控制编码技术的概念 信道干扰源可分为无源干扰和有源干扰。前者引起的差错是一种随机差错，即某个码元的出错具有独立性，与前后码元无关。而后者是由短暂原因如突然施加干扰源引起的，差错是成群的，其差错持续时间称为突发错的长度在信息传输中，二者均有可能被引入。根据具体情况而选定合适的差错控制编码可以发现并纠正这些错误。 1．1差错控制的基本方式 (1)反馈纠错 反馈纠错是在信源端采用能发现一定程度传输差错的简单编码方法对所传信息进行编码(加入少量监督码元)，在信宿端根据编码规则对收到的编码信号进行检查，一旦检测出误码，即向信源端发出信号要求重发。信源端收到信号后，立即重发已发生传输差错的那部分信息，直到正确收到为止。这种方法只能发现接收码元中的一个或一些错误，但无法确定误码的准确位置，较适合于双向数据通信，要求信源端有数据存储装置。 (2)前向纠错 前向纠错是信源端采用在解码时能纠正一定程度传输差错的较复杂的编码方法，使信宿端在收到码元后不仅能发现错码，还能够纠正错码。采用前向纠错方式时，不需要反馈信道，也无需反复重发而延误传输时间，对实时传输有利。但是纠错装置比较复杂。此方法可用于没有反馈通道的单向数字信号的传输。 (3)混合纠错 混合纠错即在接收端自动纠正少量差错，当误码严重超出其自行纠正能力时，就向信源端发出询问信号，要求重发，是反馈纠错和前向纠错的混合形式。 1．2差错控制编码的分类 差错控制编码按照差错控制的不同方式，可分为检错码、纠错码和纠删码等；按照误码产生的原因不同，可分为纠正随机错误码与纠正突发性错误码；按照信息码元与附加的监督码元之间的检验关系，可分为线性码与非线性码；按照信息码元与附加监督码元之间的约束方式不同，可以分为分组码与卷积码；按照信息码元在编码之后是否保持原来的形式不变，可分为系统码与非系统码。在实际运用中往往是多种方式的编码方式混合，如线性分组码就是信息码元与附加的监督码元之间的检验关系为线性，约束方式为分组形式。
8－1 某码字的集合为 00000000 1000111 0101011 0011101 1101100 1011010 0110110 1110001 求：（1）该码字集合的最小汉明距离；（2）根据最小汉明距离确定其检错和纠错能力。 解： （1）通过两两比较每个码字，可知该码字集的最小汉明距离为4； （2）因为检错能力与最小码距的关系为：1min +=e d ，所以检错能力为 3141min =-=-=d e 又因为纠错能力与最小码距的关系为：12min +=t d ，所以纠错能力为 5.12 1 421min =-=-= d t 取整后可得，纠错能力为1=t 。 8－2 已知二进制对称信道的差错率为2 10-=P 。（1）（5，1）重复码通过此信道传输，不可纠正错误的出现概率是多少？（2）（4，3）偶校验码通过此信道传输，不可检出错误的出现概率是多少？ 解： （1）当（5，1）重复码发生3个或3个以上的错误时不可纠正，此时不可纠正的错误出现的概率为 ( )()()60 5 551 4452 3351085.9111-?≈-+-+-=P P C P P C P P C P e （2）当（4，3）偶校验码发生偶数个错误时这些错误不可检出，这些错误出现的概率 为 ( )()40 4 442 2241088.511-?≈-+-=P P C P P C P e 8－3 等重码是一种所有码字具有相同汉明重量的码，请分析等重码是否线性码？ 解： 因为该码字集中所有的码字均有相同的码重，因此全零码字不包括在内，而线性码在输入信息位均为零时，输出也全为零，因此一定包含全零码。因此等重码不是线性码。 8－4 对于一个码长为15，可纠正2个随机错误的线性分组码，需要多少个不同的校正子？至少需要多少位监督码元？ 解：对于一个码长为15的线性码，1个及2个随机错误的图样数为 120215115=+C C
第9章 差错控制编码习题解答 9-1 （1） 写出),(k n 循环码的码多项式的一般表达式； （2） 已知)3,7(循环码的生成多项式为1)(24+++=x x x x g ，若)(x m 分别为2x 和1， 求循环码的码字。 解： : ,1)()()(:,,)(1)(:,4,3,)3,7()2()(),()1(36 242 24012211过程如下的余式为得根据编码规则若信息码生成多项式循环码式为系统码码字的一般表达++÷===+++===++++=----x x x g x m x x x x x m x x x m x x x x g r k a x a x a x a x A k n r r n n n n x x x x x x x 1001011 1 1011 11 1 10123456233242342 3466 24=++++++++++++++++a a a a a a a x x x x x x x x x x x x 最后得系统码码字为对应码为得余多项式为 x x x x x x 0010111 1 0111 111 1012345622244 24=++++++++++a a a a a a a x x x x x x x 最后得系统码码字为对应码为得余多项式: ,1)()()(:,1)(24 过程如下的余式为则有若信息码++÷==x x x g x m x m x x m r r 9-2 （5,1）重复码若用于检错，能检测几位错？若用于纠错，能纠正几位错？，若同时用 于检错与纠错，情况又如何？
. 31,2,4,5)1,5(:1,)(,)2(1 2,)2(1,)1(0000位错位错和检并同时能纠位错纠位错故能检重复码由上述公式得则要求随机错误个同时检测个纠则要求个随机错误纠则要求个随机错误检测=++≥>+≥+≥d e t d t e e t t d t e d e 9-3 已知八个码字分别为000000、001110、010101、011011、100011、101101、110110、 111000，试求其最小码距0d 。 解： . 3,1,1,0:.,,,.:. ,,:111000 110110, 101101, 100011,011011, ,010101 ,001110 ,00000080=d 故得的个数为最小汉明距离该码中少的码的个数为最找出码外除全具体方法是是类似的性这和实数运算具有封闭属于该码组中的一个码仍然算的结果码组中任意两组异或运闭性是指所谓封性来判断利用码组是否具有封闭方法二码组大时较麻烦这种方法在可得最小汉明距离两两比较方法一个码组为 已知 9-4 上题所给的码组若用于检错，能检测几位错？用于纠错，能纠正几位错？，若同时用 于检错与纠错，情况又如何？ 解： ). 3?(,2,1:1 ,)(,)3(12,)2(1,)1(: .30000条不满足第为什么同时用于纠错和检错但不能位错检位错能纠由上述公式得要求则随机错误个同时检测个纠则要求个随机错误纠则要求个随机错误检测利用公式得++≥>+≥+≥=e t d t e e t t d t e d e d 9-5 汉明码（7,4）循环码的1)(3++=x x x g ，若输入信息组0111，试设计该码的编码电路， 并求出对应的输出码字。
差错控制概述 1. 差错的概念 所谓差错，就是在通信接收端收到的数据与发送端实际发出的 数据出现不一致的现象。 2. 差错类型 通信信道的噪声分为热噪声和冲击噪声两种。由这两种噪声分 别产生两种类型的差错，随机差错和突发差错。 热噪声是由传输介质导体的电子热运动产生的，它的特点是： 时刻存在，幅度较小且强度与频率无关，但频谱很宽，是一类随机 噪声。由热噪声引起的差错称随机差错。此类差错的特点是：差错 是孤立的，在计算机网络应用中是极个别的。 与热噪声相比，冲击噪声幅度较大，是引起传输差错的主要原 因。冲击噪声的持续时间要比数据传输中的每比特发送时间要长， 因而冲击噪声会引起相邻多个数据位出错。冲击噪声引起的传输差 错称为突发差错。常见的突发错是由冲击噪声（如电源开关的跳火、 外界强电磁场的变换等）引起，它的特点是：差错呈突发状，影响 一批连续的bit（突发长度）。计算机网络中的差错主要是突发差错。 通信过程中产生的传输差错，是由随机差错和突发差错共同构 成的。 3. 误码率 数据传输过程中可用误码率Pe来衡量信道数据传输的质量，误码率是指二进制码元在数据传输系统中出现差错的概率，可用下式表达： 4. 差错控制 差错控制是指在数据通信过程中能发现或纠正差错，将差错限 制在尽可能小的允许范围内。
差错检测是通过差错控制编码来实现的；而差错纠正是通过差错控制方法来实现的。 差错控制编码 差错控制编码的原理是：发送方对准备传输的数据进行抗干扰编码，即按某种算法附加上一定的冗余位，构成一个码字后再发送。接收方收到数据后进行校验，即检查信息位和附加的冗余位之间的关系，以检查传输过程中是否有差错发生。差错控制编码分检错码和纠错码两种，检错码是能自动发现差错的编码，纠错码是不仅能发现差错而且能自动纠正差错的编码。 衡量编码性能好坏的一个重要参数是编码效率R： 其中，n表示码字的位长，k表示数据信息的位长，r表示冗余位的位长。 计算机网络中常用的差错控制编码是奇偶校验码和循环冗余码。 1. 奇偶校验码 奇偶校验码是一种最简单的检错码。 原理：通过增加冗余位来使得码字中"1"的个数保持为奇数（奇校验）或偶数（偶校验）。例如，偶校验：110101000，011011011在实际使用时，奇偶校验可分为以下三种方式。 (1) 垂直奇偶校验 原理：将要发送的整个数据分为定长p位的q段，每段的后面按"1"的个数为奇数或偶数的规律加上一位奇偶位： 编码效率：R = P/（P+1） 检错能力：能检出每列中的所有奇数个错，但检不出偶数个错。对突发错，漏检率约为50%
差错控制编码仿真 一、实验目的 掌握差错控制编码的实现技术以及仿真方法 二、实验内容 1、设计一个（7,4）汉明码编译码仿真模型 2、观察经过并串转换后的(7,4)汉明码输出波形图 三、实验原理 1、线性分组码的基本概念： 线性分组码（n，k）中许用码字（组）为2k个。定义线性分组码的加法为模2和，乘法为二进制乘法。即1+1=0、1+0=1、0+1=1、0+0=0； 1×1=1、1×0=0、0×0=0、0×1=0。且码字与码字 的运算在各个相应比特位上符合上述二进制加法运算规则。 线性分组码具有如下性质（n，k）的性质： 1）封闭性。任意两个码组的和还是许用的码组。 2）码的最小距离等于非零码的最小码重。 对于码组长度为n、信息码元为k位、监督码元为r＝n－k位的分组码，常记作（n，k）码，如果满足2r－1≥n，则有可能构造出纠正一 位或一位以上错误的线性码。 下面我们通过（7，4）分组码的例子来说明如何具体构造这种线性码。设分组码（n，k）中，k = 4，为能纠正一位误码，要求r≥3。现取 r＝3，则n＝k＋r＝7。我们用a0ala2a3a4a5a6表示这7个码元，用S1、 S2、S3表示由三个监督方程式计算得到的校正子，并假设三位S1、S2、 S3校正子码组与误码位置的对应关系如下表12.2所示。 （7，4）码校正子与误码位置
S1＝0。因此有S1＝a6⊕a5⊕a4⊕a2，同理有S2＝a6⊕a5⊕a3⊕a1和S3＝a6⊕a4⊕a3⊕a0。在编码时a6、a5、a4、a3为信息码元，a2、a1、a0为监督码元。则监督码元可由以下监督方程唯一确定 即 由上面方程可得到表12.3所示的16个许用码组。在接收端收到每个码组后，计算出S1、S2、S3，如果不全为0，则表示存在错误，可以由表12.2确定错误位置并予以纠正。例如收到码组为0000011，可算出S1S2S3=011,由表12.2可知在a3上有一误码。通过观察可以看出，上述（7，4）码的最小码距为dmin＝3，它能纠正一个误码或检测两个误码。如果超出纠错能力则反而会因“乱纠”出现新的误码。 （7，4）许用码组 有以下一些特点：码长n＝2m－1，最小码距为d＝3，信息码长k＝2n －m－1，纠错能力t＝1，监督码长r＝n－k＝m。这里m为≥2的正整数。给定m后，就可构造出汉明码（n，k）。 1、（7，4）汉明码的编译码仿真：
差错控制编码的设计与仿真 学生：陈琪，长江大学文理学院 指导教师：黄金平，长江大学电信学院 一、题目来源 来源于通信过程中所遇到的实际的问题 二、研究目的和意义 通信系统必须具备发现(即检测)差错的能力，并采取措施纠正之，使差错控制在所能允许的尽可能小的范围内，这就是差错控制过程，也是数据链路层的主要功能之一。 接收方通过对差错编码(奇偶校验码或CRC码)的检查，可以判定一帧在传输过程中是否发生了差错。一旦发现差错，一般可以采用反馈重发的方法来纠正。这就要求接受方收完一帧后，向发送方反柜一个接收是否正确的信息，使发送方据此做出是否需要重新发送的决定。发送方仅当收到接收方以正确接收的反馈信号后才能认为该帧已经正确发送完毕，否则需要重发直至正确为止。 物理信道的突发噪声可能完全“淹没”一帧，即使得整个数据帧或反馈信息帧丢失，这将导致发送方永远收不到接受方发来的信息，从而使传输过程停滞。为了避免出现这种情况，通常引入计时器(Timer)来限定接收方发回方反柜消息的时间间隔，当发送方发送一帧的同时也启动计时器，若在限定时间间隔内未能收到接收方的反柜信息，即计时器超时(Timeout)，则可认为传出的帧以出错或丢失，就要重新发送。由于同一帧数据可能被重复发送多次，就可能引起接收方多次收到同一帧并将其递交给网络层的危险。为了防止防止发生这种危险，可以采用对发送的帧编号的方法，即赋予每帧一个序号，从而使接收方能从该序号来区分是新发送来的帧还是已经接受但又重发来的帧，以此来确定要不要将接收到的帧递交给网络层。数据链路层通过使用计数器和序号来保证每帧最终都能被正确地递交给目标网络层一次。
实训18数据通信编码与差错控制技术 【实训内容】 ◎网络传输速度测试 ◎校验码 .1准备知识 互联网的最吸引的人的地方在于能提供一个信息交互的平台。而信息的载体是数据，那么信息交互的实质是数据如何在互联网的节点（设备）上进行交换；而这必须依赖于互联网上如何对数据进行编码。这就类似于联合国开会，会议的目的是为了交换意见，类似数据交换；而面对全世界这么多不同国家的语言，必须选择一种统一的语言进行交流，这就类似于对数据进行统一编码。 .1.1通信编码 1．通信的模型 一个数据通信系统由三大部分组成、即信源系统（发送端）、传输系统（传输网络）和目的系统（接收端）。在数据通信系统中，产生和发送信息的一端叫信源，接受信息的一端叫信宿。信源与信宿之间通过通信设备和传输介质进行通信。 2．模拟数据、数字数据 模拟数据是由传感器采集得到的连续变化的值，例如温度、压力，以及目前在电话、无线电和电视广播中的声音和图像。数字数据则是模拟数据经量化后得到的离散的值，例如在计算机中用二进制代码表示的字符、图形、音频与视频数据。 信源发出的可以是模拟数据，也可以是数字数据；而信道又可分为模拟信道和数字信道，所以两种信号在两种信道上面传输有以下4种可能的关系： ①数字数据在数字信号传输。例如：100BASE-T以太网。 ②数字数据在模拟信号传输。例如：使用ADSL MODEL上网。
③模拟数据在数字信号传输。例如：数字电视传输系统。 ④模拟数据在模拟信号传输。例如：收音机和早期的电话传输系统。 3．数字信号编码 在计算机网络中，信源和信宿发出和接受的数据，都是数字信号；而在信道的传输过程中，可以使用数字信号或者模拟信号两种表达方式，也就是上面所提到的①、②两种方式。 因此，根据通信过程中信号的表达方式不同，分为基带传输和频带传输，统称为数据通信。 1)基带传输 由计算机、终端等直接发出的二进制信号的典型的矩形电脉冲信号，其频谱包含直流（零频）、低频和高频（从直流一直到无限高的频率）等多种成分。因此，数字信号的频带非常宽，但是，其主要能量集中在低频段，那么把直流开始到能量集中的一段频率范围称为基本频带，简称基带，为此数字信号也被称为数字基带信号，简称为基带信号。如果在数据通信中，直接传输基带信号，则该信号几乎占用整个频带。在大多数局域网中，尤其是在传输距离不远的有线情况下，大都采用了基带传输方式。特点如下：优点：速率高、误码率低。 缺点：占用的频带，不利于远程。 2)频带传输和宽带传输 频带传输：是用电话线和电话交换网作为传输信道时采用的传输技术。频带传输中的信道带宽为3100Hz。在采用频带传输方式时，在发送端和接受端都要安排调制解调器。 宽带传输：通常是采用75?的有线电视（CATV）的同轴电缆或光缆作为传输介质时的传输技术。宽带传输中的信道带宽为300M Hz。因为宽带同轴电缆是用来传输电视信号的，所以传输数字信号时，需要利用电缆调制（Cable Mondem）把数字信号变成频率为几十到几百兆赫兹（M Hz）的模拟信号。远程通讯一般都是采用频带传输和宽带传输。特点如下：优点：可以利用现有的大量模拟信道（电话交换网）通信，价格便宜，容易实现。 缺点：速率低，误码率高。 4．基带传输与数字信号编码 在基带传输中，用不同的电压极性或者电平信号对数字数据0和1进行编码（反之为解码），但在基带传输的编码过程中，需要解决基带信号的编码问题和接收双方之间的同步问题，常采用以下3种编码方法。