1、第 4 章 信 道 编 码 第 4 章 信 道 编 码4.1 4.1 信道编码的基础信道编码的基础 4.2 线性分组码线性分组码 4.3 循环码循环码 4.4 卷积码卷积码 4.5 交织码交织码 4.6 网格编码调制网格编码调制 4.7 Turbo码码 习题习题 第 4 章 信 道 编 码 4.1 信道编码的基础信道编码的基础 4.1.1 4.1.1 信道编码的基本概念信道编码的基本概念在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字通信系统的有效性，即通过各种数据压缩方法尽可能地去除信号中的冗余信息，最大限度地降低传输速率和减少传输频带。信道编码则不同，它是
2、为了提高数字通信系统的可靠性而采取的措施。第 4 章 信 道 编 码 数字信号在传输过程中，由于噪声干扰和信道特性不理想等都会产生误码。为了提高数字通信系统的性能，可采取诸如合理设计基带信号，选择合适的调制解调方式，采用时域均衡和频域均衡，加大发射功率，采取分集接收等各种抗噪声干扰措施，以尽量减小噪声干扰的影响。若采取上述措施仍难以满足要求，则可以采用信道编码技术。信道编码又称差错控制编码或纠错编码，它的基本思想是：按照某种确定的编码规则在待发送的信息码元序列中加入一些多余的码元(监督码元或校验码元)，在接收端利用该规则进行解码，以便发现错误、纠正错误，从而提高信息码元传输的可靠性。第 4 章
3、 信 道 编 码 1.1.信道分类信道分类按照噪声或干扰引起传输差错的变化规律，可以将信道分为以下三类：(1)随机差错信道，恒参高斯白噪声信道是典型的随机信道。在随机信道中，错码是随机出现的，且各个错码的出现是统计独立的。(2)突发差错信道，具有脉冲干扰的信道是典型的突发信道。在突发信道中，错码是相对集中、成串、成群出现的，即在短时间内出现大量错码。(3)混合差错信道，短波信道和对流层散射信道是典型的混合信道。在混合信道中，错码既有随机的又有突发的。第 4 章 信 道 编 码 2.2.差错控制方式差错控制方式常用的差错控制方式主要有以下三种，如图 4-1 所示。(1)检错重发(ARQ)。在发送
4、信息码元序列中加入一些能够发现错误的码元，接收端能够利用这些检错码元发现接收码元序列中的错码，但不能确定错码的准确位置。此时，接收端通过反向信道通知发送端重发，直到接收端确认收到正确信息码元序列为止。检错重发方式的特点是需要使用反向信道，译码设备简单，适合于突发错误或信道干扰严重的情况。但实时性较差，主要应用于计算机数据通信等。第 4 章 信 道 编 码 图 4-1 差错控制方式(a)ARQ;(b)FEC;(c)HEC 编码器缓冲与控制前向信道译码器缓冲与控制反向信道编码器前向信道译码器(a)(b)第 4 章 信 道 编 码 图 4-1 差错控制方式(a)ARQ;(b)FEC;(c)HEC A
5、RQFEC前向信道FECARQ反向信道(c)第 4 章 信 道 编 码(2)前向纠错(FEC)。发送端发送能够纠错的信息码元序列，接收端不仅能发现错码，而且能确定错码的准确位置，并自动纠正错码。前向纠错方式的特点是无需反向信道，延时小，实时性好，但译码设备比较复杂。随着编码理论和大规模集成电路的发展，性能优良的实用编译码方法不断涌现，FEC方式得到了越来越广泛的应用。第 4 章 信 道 编 码(3)混合纠错(HEC)。它是FEC方式和ARQ方式的结合，即发送端发送具有检错和纠错能力的信息码元序列，接收端检查错码情况，如果错码在其纠错能力范围内，则自动纠错；如果错码超过了其纠错能力，但能检测出来
6、，则通过反向信道请求发送端重发。由于HEC方式具有FEC和ARQ的优点，可实现较低的误码率，因而得到了广泛的应用。第 4 章 信 道 编 码 3.3.信道编码分类信道编码分类1)线性码与非线性码根据信息码元与监督码元之间的函数关系，信道编码可分为线性码和非线性码。如果信息码元与监督码元之间的函数关系是线性的，即满足一组线性方程式，则称为线性码;否则，称为非线性码。第 4 章 信 道 编 码 2)分组码与卷积码根据信息码元与监督码元之间的约束方式，信道编码可分为分组码和卷积码。在分组码中，监督码元只与本码组的信息码元有关；在卷积码中，监督码元不仅与本码组的信息码元有关，而且还与前面几个码组的信息
7、码元有关。第 4 章 信 道 编 码 3)检错码与纠错码根据码的用途，信道编码可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；纠错码以纠错为目的，一定能检错。4)系统码与非系统码根据信息码元在编码前后是否保持原来的形式不变，信道编码可以分为系统码和非系统码。若编码前后信息码元保持原样不变，则称为系统码；反之，则称为非系统码。第 4 章 信 道 编 码 4.1.2 信道编码的基本原理信道编码的基本原理1.分组码的结构分组码的结构下面以分组码为例来说明纠错编码的基本原理。分组码一般可用符号(n,k)表示，如图 4-2 所示。其中n为码组长度(简称码长)，即编码后的码元序列每n位为一组；k是
8、信息码元数目;r=nk是码组中的监督码元数目。简而言之，分组码是对每段k位长的信息码元以规定的编码规则增加r个监督码元，组成码长为n的码字。在二进制情况下，共有2k个不同的信息码组，相应地可得到2k个不同的码字，称为许用码组，其余2n2k个码字未被选用，称为禁用码组。第 4 章 信 道 编 码 图 4-2 分组码的结构 an1an2arar1a0时间k个信息位r个监督位码长 n k r第 4 章 信 道 编 码 2.码重与最小码距码重与最小码距在分组码中，将码组内“1”的个数称为码组的汉明重量，简称为码重。例如码组0011011的码重为4。两个等长码组之间对应位取值不同的位数称为这两个码组的汉
9、明(Hamming)距离，简称为码距。例如码组0011011与1110010之间的距离d=5。码组集中任意两个码组之间距离的最小值称为最小距离，用d0表示。最小码距是一个重要的参数，它是衡量码检错、纠错能力的依据。第 4 章 信 道 编 码 3.3.检错和纠错能力检错和纠错能力我们以重复码为例来说明纠错编码的检错与纠错能力。若分组码中监督码元是信息码元的简单重复，则称该分组码为重复码。重复码是一种简单实用的检错码，并具有一定的纠错能力。例如(3,1)重复码，假定000和111是两个许用码组，其余为禁用码组，显然最小码距d0=3，接收端译码时，若出现禁用码组001、010、011、100、101
10、、110，则可检出两个错误，或可纠正一个错误。第 4 章 信 道 编 码 显然，一个分组码的检错和纠错能力取决于最小码距d0的值，分组码的检错和纠错能力与最小码距d0之间有如下关系：(1)为了能检测e个错码，要求最小码距d0 e+1。(2)为了能纠正t个错码，要求最小码距d0 2t+1。(3)为了能纠正t个错码，同时检测e(et)个错码，要求最小码距d0t+e+1。第 4 章 信 道 编 码 4.1.3 4.1.3 纠错编码的信道模型纠错编码的信道模型1.1.随机差错编码信道模型随机差错编码信道模型随机差错编码信道的差错是由高斯白噪声(AWGN)引起的。通常随机差错编码信道可分为二进制对称信道
11、、离散无记忆信道和带限波形信道。1)二进制对称信道(BSC)二进制对称信道模型如图 4-3 所示。它有一个对称二进制输入值集合X=0,1和二进制输出值集合Y=0,1，以及一组表示输入、输出关系的条件概率(转移概率)，若噪声导致差错统计独立且条件概率对称，即 第 4 章 信 道 编 码 P(Y=0/X=1)=P(Y=1/X=0)=PP(Y=1/X=1)=P(Y=0/X=0)=1P(4.1-1)BSC是无记忆的，它的输出仅与对应时刻的输入有关，而与前后输入无关。BSC是研究二进制编码解码最简单、最常用的模型。第 4 章 信 道 编 码 图 4-3 二进制对称信道（BSC）01PP输入1 P1 P0
12、1输出第 4 章 信 道 编 码 2)离散无记忆信道(DMC)离散无记忆信道(DMC)模型如图4-4所示。假设信道的离散输入是q元符号，即输入符号集由q个元素X=x0，x1，xq-1 构成；信道的离散输出是Q元符号，即信道输出符号集由Q个元素Y=y0，y1，yQ-1构成,且信道是无记忆的，则信道模型的输入输出特性可以用一组共qQ个条件概率来描述，即 ijiiiiPxyPxXyYP)/()/(4.1-2)式中，i=0,1,，q-1；j=0，1，Q-1。第 4 章 信 道 编 码 y0y1y2yQ1x0 x1xq1Pij图4-4 离散无记忆信道(DMC)第 4 章 信 道 编 码 条件概率决定了D
13、MC的特征，可以写成矩阵形式P=Pij，其中Pij=P(yj/xi)，P称为信道转移概率矩阵，即 1,11,10,11,111101,00100111110111110010100,)/()/()/()/()/()/()/()/()/(QqqqQQqQqqQQPPPPPPPPPxyPxyPxyPxyPxyPxyPxyPxyPxyPP(4.1-3)第 4 章 信 道 编 码 在信道输入为xi的条件下，由于噪声干扰的存在，信道输出不是一个固定值，而是概率各异的一组值，这种信道称为有扰离散信道。显然输入xi时，各可能输出值yj的概率之和必定为1，即 1)/(10QjijxyPi=0,1,q-1 如果
14、信道转移概率矩阵的每一行中只包含一个“1”，其余元素均为“0”，说明信道无干扰，这种信道称为无扰信道。第 4 章 信 道 编 码 3)离散输入、连续输出信道假设信道输入符号选自一个有限的、离散的输入符号集X=x0，x1，xq-1，而信道输出未经量化，这时的译码器输出可以是实轴上的任意值，即Y=,。定义这样的信道模型称为离散时间无记忆信道，它的特性由离散输入X、连续输出Y以及一组概率密度函数P(Y/X=xi),i=0，1,，q-1来决定。这类信道中最重要的一种是加性高斯白噪声(AWGN)信道，对它而言有 Y=X+G 式中，G是一个零均值、方差为2的高斯随机变量，即 222)-(-e21)/(ix
15、yixyP（4.1-5）第 4 章 信 道 编 码 2.突发差错编码信道模型突发差错编码信道模型 上述三种信道模型都是针对随机差错信道的。对于突发差错信道，有大量的信道模型可供研究。其中，最常用的有记忆突发差错信道模型是双状态一阶马尔可夫链模型，也称为吉尔伯特模型，如图 4-5 所示。吉尔伯特模型有两种状态：G(Good)状态和B(bad)。图 4-5 吉尔伯特模型 GB1 PgbPgbPbg1 Pbg第 4 章 信 道 编 码 在某一时刻，信道处于两种状态之一。当信道处于B状态时，信道以很大的概率Pbe发生错码；当信道处于G状态时，不产生错误(或与Pbe相比可忽略不计)。显然，信道处于B状态
16、意味着有突发差错出现。信道在B和G两种状态之间移动时，在码元周期内，信道从G状态向B状态转移的概率为Pgb，保持在G状态的概率为1 Pgb。同理，信道从B状态向G状态转移概率为Pgb，保持在B状态的概率为1Pbg。因此，吉尔伯特模型的参数是：B状态时的误码率Pbe，状态转移概率Pgb和Pbg。可以证明，吉尔伯特模型代表的编码信道的平均误码率为 bggbgbbeePPPPP（4.1-6）第 4 章 信 道 编 码 4.1.4 信道编码定理信道编码定理 香农有扰离散信道的信道编码定理指出：每个信道都有一定的信道容量C，对于给定的传信率(码率)Rb(RbC)及码长n，总存在一种编译码方法，使得差错概
17、率)(ebeRnEP(4.1-7)式中，E(Rb)为可靠性函数，也称为误差指数，它与C的关系如图 4-6 所示。信道编码定理表明了错误概率与码长n、信道容量C、信息传输速率Rb之间的转换关系。这是纠错编码的理论基础。第 4 章 信 道 编 码 图 4-6 误差指数曲线 ORb1 Rb2C1 C2E(Rb)Rb第 4 章 信 道 编 码 4.1.5 差错控制的原理差错控制的原理 1.原理一原理一由信道编码定理的公式可知，降低差错概率应增大码长n或增大可靠性函数E(Rb)，而要增大E(Rb)就要加大信道容量C或减小码率Rb。从图4-6可以看出：(1)对于相同的码率Rb，信道容量C大者其可靠性函数E
18、(Rb)也大。(2)对于相同的信道容量C，码率Rb减小时可靠性函数E(Rb)增大。由此，我们可采取如下措施来降低差错概率。第 4 章 信 道 编 码 1)增大信道容量C增大信道容量C是提高通信可靠性的基本原理之一。根据信道容量公式，信道容量C与带宽W、信号平均功率S和噪声平均功率N有关，S/N为信号噪声功率比(简称信噪比)。为此，我们可以：(1)扩展频带。例如有线通信从明线(150kHz)、双绞线(100 MHz)、同轴电缆(1 GHz)到光纤(25 THz)，无线通信从中波、短波、超短波到微波、毫米波。(2)加大功率。例如提高发射功率、增大天线增益；采用分集接收、点波束等技术。(3)降低噪声
19、。例如采用低噪声器件、滤波、屏蔽、接地、低温运行等。NS1b1WC第 4 章 信 道 编 码 2)减小码率Rb未编码时，一个二进制码元可携带1比特信息(传信率为1比特/符号)；编码后，n个二进制码元携带k比特信息(传信率为k/n比特/符号)。定义Rb=k/n为二进制分组码的码率(或效率)。对于q进制(n,k)分组码(k个q元符号编成n个q元符号)，其码率Rb=(klbq)/n。由此可知降低码率的方法有：第 4 章 信 道 编 码(1)q,n不变而减小k，这意味着降低信息源速率，每秒少传一些信息。(2)q,k不变而增大n，这意味着提高符号速率(波特率)，占用更大带宽。(3)n,k不变而减小q，这
20、意味着减小信道的输入、输出符号集，在发射信号功率固定时增大信号间的区分度，从而提高可靠性。在一定的通信容量C下减小Rb，等效于拉大C和Rb之差，因此这是用增大信道容量的冗余度来换取可靠性。从20世纪50年代到70年代，主要的纠错编码方法都是以这种冗余度为基础的。第 4 章 信 道 编 码 3)增加码长n如果保持码率Rb不变，增加码长n的同时应增大信息位k，以保持k/n之比不变。在C和Rb固定的情况下增大n，并没有增加信道容量的冗余度，它是利用了随机编码的特点：随着n增大，矢量空间Xn呈指数量级增大，从统计角度而言，码字间距离也将增大，从而提高了可靠性。另外，码长n越大，其实际差错概率就越符合统
21、计规律。第 4 章 信 道 编 码 增大码长n所带来的好处同样需要付出某种代价才能换得，代价就是码长越长，编/解码算法就越复杂，编/解码器就越昂贵。香农早在1948年就已指出增大n的途径，但在20世纪70年代前由于器件水平不允许编/解码器做得太复杂，因此，当时实用的纠错编码主要还是靠牺牲功率和频带利用率来换取可靠性的。进入20世纪80年代后，随着超大规模集成电路(VLSI)的发展，编/解码器可以做得越来越复杂，很多编/解码算法可在数字信号处理专用芯片DSP上实现，因此码长允许设计得很长。目前，通过增大码长来提高可靠性已成为纠错编码的主要途径之一，它实际上是以编/解码设备的复杂度来换取可靠性的。
22、从这个意义上说，设备的复杂性是妨碍数字通信系统性能提高的真正限制因素。第 4 章 信 道 编 码 2.2.原理二原理二1)利用冗余度冗余度就是在信息比特流中插入冗余比特，这些冗余比特与信息比特之间存在着特定的相关性。这样，在传输过程中即使个别信息比特出错，也可以利用其相关性从其他未出错的冗余比特中推测出出错比特的原形，保证了信息比特传输的可靠性。例如，如果用2比特表示四种意义，则无论如何也不能发现差错，因为若有一信息01误成00，则根本无法判断这是传输过程中由01误成00，还是原本发送的就是00。第 4 章 信 道 编 码 但如果用3比特来表示四种意义，则就有可能发现差错，因为3比特的八种组合
23、能表示八种意义，用它代表四种意义尚剩四种冗余组合，如果传输差错使收到的3比特组合落入四种冗余组合，就可判定一定有错码发生。至于加多少冗余比特、加什么样的相关性最好，这正是纠错编码技术要解决的问题，但必须有冗余，这是纠错编码的基本原理。第 4 章 信 道 编 码 为了传输这些冗余比特，必然要动用冗余的资源。这些资源可以是：(1)时间。例如一个比特重发几次，或一段消息重发几次，或根据收端的反馈重发受损信息比特组等。(2)频带。插入冗余比特后传输效率下降，若要保持有用信息的传输速率不变，最直接的方法就是增大符号传送速率(波特率)，结果是占用更大的带宽。例如二进制码(1比特/符号)编成(8，4)分组码
24、后，其符号速率增大一倍，占用带宽也增大一倍。第 4 章 信 道 编 码(3)功率。采用多进制符号，例如用一个八进制ASK符号代替一个四进制ASK符号来传送2比特信息，可腾出位置另传1比特冗余信息。但为了维持信号集各点之间的距离不变，八进制符号的平均功率比四进制时要大，这就是动用冗余的功率资源来传输冗余比特。(4)设备复杂性。增大码长n，例如采用网格编码调制(TCM)，该方法是在功率、带宽受限信道中实施纠错编码的有效方法之一，其代价是算法复杂度增大，需动用计算（设备）资源。第 4 章 信 道 编 码 2)噪声均化噪声均化的基本思想是让差错随机化，设法将危害较大的、较为集中的噪声干扰(称为突发差错
25、)分散开，变为分散的噪声干扰(称为随机差错)，从而使不可恢复的信息损伤达到最小。噪声均化将差错均匀分摊给各码组，从而提高了总体差错控制能力。噪声均化的方法主要有以下三种。第 4 章 信 道 编 码(1)增加码长。例如某BSC信道差错概率Pe=0.01，假如编码后的纠错能力是10%，即在长度为n的码字中，只要差错码元个数少于等于n的10%，就可以通过译码加以纠正。若码长n=10，则码字中有多于一个码元出错时就会产生译码差错，差错概率为 31010ee1027.4)1(101mmmPPmP 如果保持码率Rb不变，将码长n增大到40，则当码字中多于四个码元出错时就会产生译码差错，差错概率为 5404
26、0ee1092.4)1(401mmmPPmP第 4 章 信 道 编 码 从本例可以看到，只要将码长n由10增长到40，译码差错概率就可以降低两个数量级。这是因为：码长越长，每个码字中错码的比例就越接近统计平均值，即噪声均摊到了各个码字上。第 4 章 信 道 编 码(2)卷积。在分组码中，是将信息码元序列分割成k位一组，每组再加入r位监督码元后编成n位码字，即码元之间的相关性仅限于在各个码字内，码字之间是彼此无关的(统计独立的)。卷积码则不然，它在一定约束长度内的若干码字之间加进了相关性，译码时不是根据单个码字，而是一串码字来进行判决。卷积码是将噪声分摊到码字序列而非一个码字上，从而达到噪声均化
27、的目的。第 4 章 信 道 编 码(3)交织(也称为交错)。交织是对付突发差错最有效的措施之一。突发噪声干扰使码流产生集中成串的、不可纠正的差错。交织码的基本思想是：对编码器输出的码流与信道上的符号流做顺序上的变换，将码流转换为随机的、可纠正的差错，即均化突发信道造成的符号流中的突发差错。第 4 章 信 道 编 码 4.1.6 纠错编码系统的性能指标纠错编码系统的性能指标1.编码效率编码效率纠错编码是以降低有效性为代价来提高数字通信系统的可靠性的。对于分组码(n,k)来说，定义编码效率 nkR（4.1-8）式中，n为码长;k为信息码元的个数。第 4 章 信 道 编 码 2.纠错编码的误码性能纠
28、错编码的误码性能对于二进制对称信道(BSC)，假设在随机差错信道中，发送“0”时的差错概率与发送“1”时的差错率均为Pe，且Pe1。可以证明，在码长为n的码组中恰好发生i个错误的概率为 iiniinnPininPPCiPeee)!(!)1()(（4.1-9）则不加纠错时的误码组率为 ininiinninPPCiPP)1()(ee11w（4.1-10）第 4 章 信 道 编 码 如果使用可以纠正t位随机误码的纠错码，则译码后的误码组率降低 inintiinntinPPCiPP)1()(ee11wc（4.1-11）系统误比特率与具体所采用的编译码算法有关。一般来说，可近似地有 inintiinPP
29、iCnP)1(1ee1b（4.1-12）第 4 章 信 道 编 码 例如，码长n=7，Pe=10-3，此时有P7(1)7Pe=71-3，P7(2)21P2e=2.110-5，P7(3)35P3e=3.510-8由此可见，在信道误码率较低的情况下，采用纠错编码，即使只能纠正12个错码，也能使系统误码率下降几个数量级。第 4 章 信 道 编 码 对于高斯白噪声信道(AWGN)，由第3章可知，在数字调制系统中，误比特率Pb与 Eb/n0 和调制方式有关。例如相干解调2PSK无纠错时的误比特率为 0bb2nEQP（4.1-13）式中，Eb为单位比特能量;n0为噪声功率谱密度。第 4 章 信 道 编 码
30、 如果在2PSK调制前先进行(n,k)分组码纠错编码，则由于加入监督码元，在相同码率情况下，信道中需要传输的符号速率增加了k/n倍。因此，误比特率变为 nknEQnEQPc0b0b22（4.1-14）这里，Ec为单位符号能量，它与Eb有如下关系 nknEQnEQPc0b0b22（4.1-15）利用式(4.1-12)、(4.1-13)和(4.1-14)可以求出编译码后误比特率Pb与Eb/n0的关系。第 4 章 信 道 编 码 3.编码增益编码增益在给定误比特率(例如10-5)的条件下，采用纠错编码所节省的信噪比Eb/n0称为编码增益，通常用分贝表示 dB0b0bdBcunEnEG（4.1-16）
31、式中，(Eb/n0)u为未编码时所需的信噪比(dB)；(Eb/n0)c为编码后所需的信噪比(dB)。显然，编码增益越大越好。第 4 章 信 道 编 码 4.1.7 常用的检错码常用的检错码1.奇偶监督码奇偶监督码奇偶监督码又称奇偶校验码，是一种简单的检错码，在计算机数据通信中应用广泛。奇偶监督码的基本思想是在n-1位信息码元的后面附加上一位监督码元，构成(n,n-1)的分组码，监督码元的作用是使得码长为n的码组中“1”的个数是奇数或偶数。码组中“1”的个数是奇数的编码称为奇监督码，码组中“1”的个数是偶数的编码称为偶监督码。第 4 章 信 道 编 码 奇偶监督码的编码规则是：首先将要发送的二进
32、制信息码元进行分组，然后对所有信息码元和监督码元进行模2加，选择正确的监督码元，以保证模2加的结果为0(偶监督码)或1(奇监督码)。假设由n个码元构成的码字为(an-1，an-2，a0)，其中前n1位是信息码元，第n位a0是监督码元，对偶监督码有 00121aaaann（4.1-17）a0可以由下式确定 1210aaaann（4.1-18）第 4 章 信 道 编 码 接收端译码时，按式(4.1-17)将码组中的码元进行模2加，若结果为“0”，则判定为无错码；若结果为“1”，则判定该码组经传输后有奇数个错码。对奇监督码有 10121aaaann（4.1-19）a0可以由下式确定 1210aaaa
33、nn（4.1-20）第 4 章 信 道 编 码 奇偶监督码最小码距为2，无论是奇监督码还是偶监督码，都只能检测出单个或奇数个错码，而不能检测出偶数个错码。奇偶监督码的编码效率为R=(n1)/n。例如，在ASCII码中，通常采用7位二进制码元来表示128种字符。传输时再加上一个奇偶监督位8位码组，接收端根据是否满足式(4.1-17)或式(4.1-19)来判定传输过程中是否发生错误。第 4 章 信 道 编 码 2.行列监督码行列监督码行列监督码是二维奇偶监督码，又称为矩阵码或方阵码。为了改进奇偶监督码不能发现偶数个错误的情况，行列监督码不仅对水平(行)方向的码元，而且对垂直(列)方向的码元实施了奇
34、偶监督，如图4-7(a)所示。具体编码方法是：将要发送的若干信息码元排列成一个方阵，方阵中的每一行为一个码组，在行的最后一位加上一个监督码元ai0(i=1,2，m)，进行奇偶监督；同理，在每列的最后一位也加上一个监督码元ci-1(i=1,2，n)，形成行列监督码。图4-7(b)是(66,50)行列监督的一个码字。第 4 章 信 道 编 码 图 4-7 奇偶监督码(a)编码方法；(b)(66,50)行列监督码 11na12na11a10a21na22na21a20amna1mna2ma1ma0cn1cn2c1c0(a)1 1 0 0 1 0 1 0 0 0 00 1 0 0 0 0 1 1 0
35、1 00 1 1 1 1 0 0 0 0 1 11 0 0 1 1 1 0 0 0 0 01 0 1 0 1 0 1 0 1 0 11 1 0 0 0 1 1 1 1 0 0(b)第 4 章 信 道 编 码 行列监督码不仅具有较强的检错能力，还可用来纠正一些错码。例如，当码组仅在一行中出现奇数个错误时，可以确定错码的位置并加以纠正。行列监督码适合于检测突发错误。由于突发错误常常集中成串出现，随后较长一段时间无差错，因此在一行中出现多个奇数或偶数错码的机会较多，而行列监督码有可能检测偶数个错误。尽管每行中的偶数个错误不能由本行的监督码元检出，但按列的方向可能由本列的监督码元检测出来。由于行列监督
36、码只是对构成矩形四角的错码无法检测，故其检错能力较强。第 4 章 信 道 编 码 3.恒比码恒比码恒比码又称为等比码或等重码。在恒比码中，每个码组中“1”的数目与“0”的数目保持恒定比例，即每个码组都含有相同数目的“1”和“0”。接收端译码时，只要检测码组中“1”或“0”的数目是否与规定的数目相同，就可以判定有无错码。例如，目前我国电传通信中普遍采用五位数字保护电码(3 2码)，即5中取3的恒比码，每个码组的长度为5，其中有三个“1”。准用码组的数目为C35=10，正好表示10个阿位伯数字(09)，如表 4-1 所示。每个汉字可以用四位十进制数来表示。第 4 章 信 道 编 码 表表 4-1
37、5中取中取3的恒比码的恒比码 第 4 章 信 道 编 码 恒比码的最小码距为2，能发现所有奇数个错误，但不能发现所有偶数个错误。实践证明，采用这种恒比码能有效降低汉字电报的差错率。目前国际上通用的ARQ电报通信系统采用3 4码。即7中取3的恒比码，每个码组长度为7，其中有三个“1”，准用码组数为C37=35，35个码组分别表示26个字母和其他符号。恒比码的主要优点是简单、实用，适合传送电报或其他键盘设备产生的字母字符，但不适合传送二进制随机数字序列。第 4 章 信 道 编 码 4.2 线线 性性 分分 组组 码码 4.2.1 线性分组码的基本概念线性分组码的基本概念线性分组码中的分组是指编、译
38、码过程是按分组进行的，一般是按每k个信息码元一组进行编译码；而线性则是指分组码中监督码元按线性方程生成的，即r=n-k个监督码元是由k个信息码元的线性变换产生。例如在(7，4)线性分组码中，信息码元每四位一组进行编码，即输入信息码元长度k=4；编码器输出码组长度n=7，监督码元长度 r=n-k=7-4=3；编码效率R=k/n=4/7。第 4 章 信 道 编 码 从空间的角度看，(n,k)线性分组码中的每一个码字都可以看成n维线性空间中的一个矢量。长度为n的码字共有2n个矢量，构成一个n维线性空间。(n,k)线性分组码中有2k个准用码字(kn)，构成了一个k维线性子空间，即(n,k)线性分组码是
39、n维线性空间中的一个k维线性子空间。纠错编码的任务就是在n维线性空间的2n种可能组合中选择2k个构成一个k维线性子空间。由于该线性子空间在模2加法运算中构成阿贝尔群，因此线性分组码又称为群码。第 4 章 信 道 编 码 4.2.2 4.2.2 线性分组码编码方程与生成矩阵线性分组码编码方程与生成矩阵G G下面以(7，3)二进制线性分组码为例来说明。假设输入信息码组为m=(m0m1m2)，编码器输出码组为C=(c0c1c2c3c4c5c6)，已知输入码与输出码的关系式是c0=m0,c1=m1,c2=m2,c3=m0+m2,c4=m0+m1+m2，c5=m0+m1,c6=m1+m2。因此，可将上述
40、关系式列成如下编码线性方程：第 4 章 信 道 编 码 监督码元信息码元2161052104203221100mmcmmcmmmcmmcmcmcmc（4.2-1）第 4 章 信 道 编 码 可见，输出码组中前三位是信息码元的简单重复，后四位是监督码元，它由前三个信息码元的线性组合构造。写成对应的矩阵形式为 mGmmmcccccccC101110011100100111001)()(2106543210(4.2-2)第 4 章 信 道 编 码 式中，G称为生成矩阵，由G和信息组就可以产生全部码字。G为kn阶矩阵，各行也是线性无关的。生成矩阵也可分为两部分，即G=IkQ(4.2-3)式中，Q为kr
41、阶矩阵；Ik为k阶单位矩阵；G称为典型生成矩阵，非典型生成矩阵经过行列运算可以转化为典型生成矩阵。第 4 章 信 道 编 码 在本例中，七位二进制数有27=128种组合，而三位信息码组只有23=8种组合，一一对应到八个码字。在以上编码过程中，核心的因素是生成矩阵G G，它决定了编码规则，也决定了码字集合。该生成矩阵G G可以看成是由三个行矢量组成的，所有码字是这三个行矢量的线性组合：C=m0(1001110)+m1(0100110)+m2(0011101)分别令信息组m=(m0m1m2)为(000)，(001)，(111)，不难算出各信息组对应的码字，如表 4-2 所示。第 4 章 信 道 编
42、 码 表表 4-2 信息码组与码字对应表信息码组与码字对应表 第 4 章 信 道 编 码 4.2.3 4.2.3 线性分组码的监督方程与监督矩阵线性分组码的监督方程与监督矩阵H H 若将式(4.2-1)编码方程中后四位监督方程改写，可得 000062151042103202121610105210210420203cccccccccccccccmmcccmmccccmmmcccmmc（4.2-4）第 4 章 信 道 编 码 将上述线性方程写成如下矩阵形式 000010001100100011001011100011016543210ccccccc即 TTOHC或 OCHT(4.2-5)第 4
43、章 信 道 编 码 其中，CT是码空间C的转置，OT是O=0000的转置，HT是H的转置。1000010000100001101111100111rIPH（4.2-6）第 4 章 信 道 编 码 H称为监督矩阵。一旦给定H，信息码元和监督码元之间的关系也就确定了。H为rn 阶矩阵，H矩阵每行之间是彼此线性无关的。P为rk(43)阶矩阵，Ir为rr（44）阶单位矩阵。写成H=P Ir形式的矩阵称为典型监督矩阵。由式(4.2-3)和式(4.2-6)可以看出 QT110011110111PQ（4.2-7）其中PT是P的转置。第 4 章 信 道 编 码 根据以上推导可以看出，监督矩阵H H与生成矩阵G
44、 G之间存在一一对应的关系，即)()()()(TTPIQIGIQIPHkkrr（4.2-8）（4.2-9）只要生成矩阵G确定了，监督矩阵H也就确定了；反之亦然。显然，线性分组码可以由生成矩阵G或监督矩阵H完全确定。编码时通常采用生成矩阵G，译码时通常采用监督矩阵H。HCT=OT，说明H矩阵与码字的转置乘积必为零，可以用来作为判定接收码字C是否出错的依据。第 4 章 信 道 编 码 4.2.4 校正子校正子(伴随式伴随式)S与译码与译码 假设发送码组C=(c6c5c4c3c2c1c0)，在传输过程中可能发生误码，接收码组B=(b6b5b4b3b2b1b0)，则发送码组与接收码组之差定义为错误图样
45、E，也称为误差矢量，即E=BC=B+C，其中E=(e6e5e4e3e2e1e0)，且 iiiiicbcbe,0,1i=0,1,6（4.2-10）第 4 章 信 道 编 码 当ei=0时，表示该位接收码元正确；当ei=1时，表示该位接收码元有错。令S=BHT，称为伴随式或校正子。当接收端译码时，用监督矩阵H进行校验，计算校正子S，即TTTTT)(EHEHHCHCEBHS由于CHT=0，因此校正子S只与错误图样E有关，与发送码字C无关。由此可见，校正子S与错误图样之间有确定的线性变换关系。接收端译码器的任务就是从校正子S确定错误图样E，然后从接收到的码字中减去错误图样。图 4-8 给出了译码过程框
46、图。（4.2-11)第 4 章 信 道 编 码 图 4-8 译码过程框图 BHT0ECB否计算E输出BE编码mGm是输出 BC第 4 章 信 道 编 码 如果接收码无误，必有B=C，E=0及EHT=0，S=0；如果信道产生差错而使E0，必有BHT=EHT0，S0。从物理意义看，校正子S并不反映发送的码字是什么，而只反映了信道对码字造成怎样的干扰。在接收端，我们并不知道发送码C究竟是什么，但知道HT和接收码B，从而算出S。译码最重要的任务是从校正子S中找出C的估值C。具体方法是：先算出S，再由S算出E，最后令C=B+E而求出C，即 EBCESBHT（4.2-12）第 4 章 信 道 编 码 问题
47、的关键是从S中找出E，只要E正确，译出的码就是正确的。下面以(5，2)线性分组码来说明如何构造该码的标准阵列译码表和译码。假设(5，2)线性分组码的生成矩阵为 1011011101G其中,n=5,k=2,r=3。由信息组m=(00),(01),(10),(11)，由式(4.2-2)可求得四个准用码字为C0=(00000),C1=(10111),C2=(01101),C3=(11010)。由式(4.2-8)可求得监督矩阵 100100011001111001000110011113hIPH（4.2-13）第 4 章 信 道 编 码 由S=EHT可得 03400001102203404401410
48、011112213314412342002112222332442eeeheheheheheseeheheheheeeseeeheheheheees（4.2-14）由BHT确定S后，对应的E可以有2k(22=4)个解，究竟取哪一个作为差错图样E的解?最简单明了的处理方法是概率译码，即对所有2k个解的重量(差错图样E中1的个数)进行比较，选择重量最小的作为E的估值。由于E=B+C，E重量最小，就是B和C的汉明距离最小。第 4 章 信 道 编 码 显然，在进行概率译码时，每接收一个码字就要解一次线性方程，非常复杂麻烦。但如果nk不太大，我们可以预先把不同校正子S S情况下的所有方程组都预先解出来，
49、将各种情况下的最大概率译码输出列成一个标准阵列译码表。这样，在实际译码时就不必解方程，只要查译码表就可以了。第 4 章 信 道 编 码 校正子S有2n-k=23=8种组合；而错误图样有25=32种，其中：代表无差错的全零错误图样有C05=1种；代表一个差错的错误图样有C15=5种；代表两个差错的错误图样C25=10种。显然，要把八个校正子对应到八个重量最小的错误图样，无疑应先选择：全零错误图样；五种一个差错的错误图样；剩下的两个校正子不得不在10种两个差错的错误图样中选择两个。具体方法是：(1)先将全零错误图样E=(00000)代入式(4.2-14)，可求得对应的S=(000)。第 4 章 信
50、 道 编 码(2)再将五种一个差错的错误图样E=(10000),(01000),(00100),(00010),(00001)代入式(4.2-14)，可求得对应的S=(111),(101),(100),(010),(001)。(3)剩下的两个校正子是(011)和(110)，每个有2种解，对应22个错误图样。对于校正子(011)的22个解(错误图样E)为(00011)，(10100)，(01110)，(11001)，其中(00011)和(10100)具有最小重量，可选择其中之一作为错误图样，例如选择(00011)。同理，校正子(110)所对应的重量最小的错误图样之一是(00110)，如表4-3所
