2.差错控制编码2.1. 引言什么是差错控制编码（纠错编码、信道编码）？为什么要引入差错控制编码？差错控制编码的3种方式？本章主要讲述：前向纠错编码（FEC）、常用的简单编码、线性分组码（汉明码、循环码）、简单介绍RS码*、BCH码*、FIRE码*、交织码，卷积码极其译码、TCM编码*。
一、什么是差错控制编码及为什么引入差错控制编码？在实际信道上传输数字信号时，由于信道传输特性不理想及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误。
为了在已知信噪比情况下达到一定的误比特率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域、频域均衡，使误比特率尽可能降低。
但若误比特率仍不能满足要求，则必须采用信道编码（即差错控制编码），将误比特率进一步降低，以满足系统指标要求。
随着差错控制编码理论的完善和数字电路技术的发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与存储中也得到日益广泛的应用。
差错控制编码的基本思路：在发送端将被传输的信息附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联（约束）。
接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。
研究各种编码和译码方法是差错控制编码所要解决的问题。
二、差错控制的三种方式1、检错重发（ARQ）检错重发：在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道要求发送端重新发送，直到接收端检查无误为止。
ARQ系统具有各种不同的重发机制：如可以停发等候重发、X.25协议的滑动窗口选择重发等。
ARQ系统需要反馈信道，效率较低，但是能达到很好的性能。
2、前向纠错前向纠错（FEC）：发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动纠正传输中的错误。
不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂。
3、混合方式结合前向纠错和ARQ 的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。
它是一种折中的方案。
三、信道发生差错的几种模式1、随机差错：差错的出现是随机的，一般而言差错出现的位置是随机分布的。
这种情况一般是由信道的加性随机噪声引起的。
一般将这种信道称为随机信道。
2、突发差错：差错的出现是一连串出现的。
这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等。
这样的信道我们称之为突发信道。
3、混合差错：既有突发错误又有随机差错的情况。
这种信道称之为混合信道。
四、差错控制编码的基本原理我们以差错重发编码来简单地阐述差错编码在相同的信噪比情况下为什么会获得更好的系统性能？例1，假设我们发送的信息0、1（等概），采用2PSK 方式，我们知道最佳接收的系统误比特率为⎪⎪⎭⎫ ⎝⎛=021N E erfc P s e ，现在假设310-=e P （即平均接收1000个中错一个）。
如果我们将信息0编码成00，信息1编码成11，还是采用刚才的系统，则在接收端：如果发送00，收到01、10，我们知道发生了差错，要求发送端重新传输，直到传送正确为止，因此只有当收到11时，我们才错误地认为当前发送的是1。
因此在这种情况下发生译码错误的概率是221e P ； 同理，如果发送的是11，只有收到00时才可能发生错误译码，因此在这种情况下发生译码错误的概率是221e P 。
所以采用00、11编码的系统误比特率为2e P 。
问题：采用000、111编码的ARQ 系统误比特率是多少？采用0000、1111编码的ARQ 系统误比特率是多少？例2，如例1，如果0、1采用00000、11111编码，在接收端我们用如下的译码方法，每收到5个比特译码一次，采用大数判决，即5个比特中0的个数大于1的个数则译码成0，反之译码成1；不采用ARQ 方式。
那么，我们看到这种编码方式就变成了纠错编码。
由于传输错误当接收端收到11000，10100，10010，10001，01100，01010，01001，00110，00101，00011中的任何一种时，都可以自动纠正成00000。
问题：请计算在这种情况下的系统性能。
例3，我们知道，2PSK 系统中误比特率与0/N E s 有关，上述例1，例2的编码方式叫重复码。
我们看到，重复码中我们假设传输时每个符号的0/N E s 相等，因此才得到以上的性能分析对比。
但是如果我们以0/N E b 的指标进行比较，则我们看到例1的002N E N E s b = 例2的005N E N E s b = 如果要求系统的比较在0/N E b 相同的情况下进行比较，则我们可以看到这3种系统是等价的。
（即没有获得相应的编码增益）221)(x e x x erfc -≈π，x>>1 2PSK 系统：()0/21N E erfc P b e ==00/21N E b b e N E -π 2重复码：20]221[⎪⎪⎭⎫ ⎝⎛=N E erfc P b e =00/21N E b b e N E -π 实际上，我们知道系统的性能与0/N E s 直接相关，在n 重复码中我们用了n s E 的能量来传输一个比特，从每个比特能量的角度来看重复码没有得到好处。
五、差错控制编码的分类根据差错控制编码的功能不同分为：检错码、纠错码、纠删码（兼检错、纠错） 根据信息位和校验位的关系分为：线性码和非线性码根据信息码元和监督码元的约束关系分为：分组码和卷积码。
分组码：将k 个信息比特编成n 个比特的码字，共有k 2个码字。
所有k 2个码字组成一个分组码。
传输时前后码字之间毫无关系。
卷积码：也是将k 个信息比特编成n 个比特，但是前后的N 个码字之间是相互关联。
编码速率=n k =个比特的码字编成个信息比特n k =平均每个码字所携带的信息比特率。
六、编码信道及仙农编码定理所谓的编码信道就是将调制解调包在信道内的一种模型上的等效。
即由上图，如果我们研究的是编码和译码，我们完全可以将调制、解调与信道合起来等效成一个等效的信道，这种信道就称之为编码信道。
编码信道根据调制解调的不同输入和输出具有不同的类型：1、离散无记忆对称二进制输入二进制输出信道（BSC ）信道这种情况相应于2进制调制解调+判决，可以用如下的模型来表示：2、离散无记忆二进制输入多进制输出信道这种情况对应于2进制输入，量化后输出的情况，即所谓的软译码。
3、离散无记忆多进制输入多进制输出这种情况对应于多进制输入、量化后输出。
4、离散无记忆二进制输入连续输出这种情况对应于二进制输入，模拟输出（未判决、未量化）。
仙农有扰离散信道的编码定理：对于一个给定的有扰信道，若信道的容量为C ，只要发送端以低于C 的速率R 发送信息（R 为编码器的输入二进制码元速率），则一定存在一种编码方法，使编码错误概率P 随着码长n 的增加，按指数下降到任意小的值，表示为)(R nE e P -≤，这里)(R E 称为误差指数。
这条定理告诉我们：1、在码长及发送信息速率一定的情况下，为减小P ，可以增大信道容量。
2、在信道容量及发送信息速率一定的情况下，增加码长，可以使错误概率指数下降。
从实际的角度看，这时设备复杂性和译码延时也随之增加。
2.2. 纠错编码的基本原理前面我们说到：分组码将k 个比特编成n 个比特一组的码字（码组）（Code words ）， 经常将分组码记为（n ，k ）码。
由于输入有k 2种组合，因此（n ，k ）码应该有k 2个 码字。
一、码重、码距码重：码字中1的个数。
如码字11000的码重为2。
码距：码字C1与码字C2之间不同的比特数（又称为汉明距）。
二、最小码距最小码距：是码的一种属性，如（n ，k ）码中任何两个码字C1、C2之间的距的最小值，用min d 表示。
三、码的最小码距决定了码的纠错、检错性能1、为了检测e 个错误，要求最小码距min d 1+≥e2、为了纠正t 个错误，要求最小码距12min +≥t d3、为了纠正t 个错误，同时检测e 个错误，要求最小码距1min ++≥e t d （)t e > 图示说明：2.3. 常用的简单编码让我们简单介绍几种常用的简单编码：一、奇偶监督码（奇偶校验）这是一种最简单的检错码，在计算机数据传输中得到广泛应用。
假设奇偶监督码的码字表示为：),...,,(021a a a n n --则偶校验码：0...021=⊕⊕⊕--a a a n n （即偶数个1）奇校验码：1...021=⊕⊕⊕--a a a n n （即奇数个1）可见这种码的最小码距为2，只能检1个错。
二、二维奇偶监督码为了提高奇偶校验码对突发错误的检测能力，可以考虑用二维奇偶校验码。
将若干奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行。
传输时按照列顺序进行传输，在接收端又按照行的顺序检验是否差错。
由于突发错误是成串发生的，经过这样的传输后错误被分散了。
（实际上这种方法是交织编码+奇偶校验）。
在移动通信中，由于信道的衰落经常造成突发错误，因此经常在进入信道传输前，先将输入的信息比特交织，将突发错误尽可能分散成随机错误，然后用其它编码方式来纠正随机的错误。
m m n m n n n n n c c c a a a a a a 021202221101211.....................------三、恒比码每个码组中的1的个数都是一样的。
我国电传机传输汉字时每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示。
由于阿拉伯数字只有10个，因此从32中可能的码字中挑出53C =10个恒比码的译码可以采用查表方法，检错时检查1的个数是否为3。
恒比码一般用在电传、电报。
四、ISBN 国际统一图书编号我们简单介绍一下编码的应用。
在国际图书的发行中，经常用编码的方式来防止书号在通信过程中发生错误。
如《通信原理》的书号是ISBN 7-118-01429-X其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”表示书名编号，最后一位“X ”表示校验位（它是罗马数字10的表示）。
这里所采用的校验方式如下所示：7 1 1 8 0 4 2 9 X=107 8 9 17 17 21 23 32 427 15 24 41 58 79 102 134 176 176(模11)=0。
2.4. 线性分组码2.4.1. 线性分组码的基本概念一、线性分组码的性质（n ，k ）（n ，k ）中许用码字（组）为2^k 个。
定义线性分组码的加法为模2加，乘法为二进制乘法。
即1+1=0、1+0=1、0+1=1、0+0=01x1 = 1, 1x 0 =0, 0x0 =0, 0x1 =0且码字),...,(021i n i n i i c c c C --=与码字),...,(021j j n j n j c c c C --=的运算是各个相应比特位上符合上述二进制加法运算规则。
