1、第10章信道编辑原理10.1 概述 10.2 检错码 10.3 线性分组码 10.4 卷积码 10.5 复合编码 10.6 m序列 思考题 习题 第第10章章 信道编码原理信道编码原理 第10章信道编辑原理10.1 概概 述述10.1.1 信源编码与信道编码信源编码与信道编码数字通信中，根据不同的目的，可将编码分为信源编码和信道编码两大类。为了提高数字信号的有效性而采取的编码称为信源编码，又称有效编码；为了提高数字通信的可靠性而采取的编码称为信道编码(或者可靠编码)，又称抗干扰编码，这是本章要讨论的内容。第10章信道编辑原理数字通信要求传输过程中所造成的码元差错足够低。引起传输差错的根本原因是
2、信道内存在噪声以及信道传输特性不理想所造成的码间串扰。通常，由于信道线性畸变所造成的码间串扰可以通过均衡的办法来消除,因此，常常只把信道中的噪声作为造成传输差错的根本原因。为了提高数字通信系统的抗噪声性能，可以采取增大发射功率、降低接收设备本身的噪声、选择好的调制制度和解调方式、加强天线的方向性等措施。但是,这些措施只能将差错减小到一定程度,要进一步提高通信的可靠性，就需要采用信道编码技术，对可能或者已经出现的差错进行控制。第10章信道编辑原理 信道编码是使不带规律性或者规律性不强的原始数字信号变换为带上规律性或者加强了规律性的数字信号，信道译码器则利用这些规律性来鉴别是否发生了错误，进而纠正
3、错误。信道编码分为纠错编码和正交编码两大类。纠错码的规律性体现在各码组的码元之间，而正交码的规律性体现在各码组之间的正交性。这两类码有密切的联系，有些正交码就是纠错码。第10章信道编辑原理 原始数字信号是分组传输的，例如每k个二进制码元为一组，称为信息组，经信道编码后转换为每n个码元一组的码字(码组)，nk。可见，信道编码是采用增加数码，利用“多余”码来提高抗干扰能力的，亦即以降低信息传输速率为代价来减少错误，或者说是通过采用削弱有效性来增强可靠性。第10章信道编辑原理10.1.2 纠错码的分类纠错码的分类 (1)根据纠错码各码组的码元与信息元之间的函数关系，纠错码可分为线性码和非线性码。如果
4、函数关系是线性的，则称为线性码，否则称为非线性码。(2)根据上述关系涉及的范围，纠错码可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关，卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关，卷积码又称连环码。线性分组码中，把具有循环移位特性的码称为循环码，否则称非循环码。第10章信道编辑原理(3)根据纠错码组中信息元是否隐蔽，纠错码可分为系统码和非系统码。如果信息元能从码组中截然分离出来(通常K个信息元与原始数字信号一致，且位于码组的前K位)，则称为系统码或组织码，否则称为非系统码或非组织码。(4)根据码的用途,纠错码可分为检错码和纠错码。前者以检测(发现)错误为目的，
5、后者以纠正错误为目的。纠错码一定能检错，检错码不一定能纠错。平常所说的纠错码是两者的统称。第10章信道编辑原理(5)根据纠(检)错码的类型区分，纠错码可分为纠(检)随机错码、纠(检)突发错码及既能纠(检)随机错又能纠(检)突发错的码。(6)根据码元取值的进制，纠错码可分为二进制码和多进制码。本章主要介绍二进制纠错码。第10章信道编辑原理10.1.3 差错控制的工作方式差错控制的工作方式差错控制的基本工作方式有4种，如图10.1所示。图中有斜线的方框图表示在该端检出错误。第10章信道编辑原理图10.1 差错控制的基本工作方式第10章信道编辑原理前向纠错(FEC，Forward Error Cor
6、rection)：又称自动纠错，发端发送纠错码，收端译码器自动发现并纠正错误。其特点是能单向连续传输，实时性好，但是译码电路比较复杂。检错重发(ARQ,Auto Repeat-reQuest):又称反馈重发、自动重传请求或者判决反馈，发端发出检错码，通过正向信道送到收端，收端译码器判决码组中有无错误出现，再把判决信号通过反馈信道送回发端，发端根据判决信号将收端认为有错的消息重发到收端，直到正确接收为止。其特点是需要反馈信道，但是译码设备简单，对突发错误特别有效。第10章信道编辑原理信息反馈(IF，Information Feedback)：又称反馈检验，收端把收到的消息原封不动地通过反馈信道送
7、回发端，发端把反馈回来的信息与原发送信息进行比较，从而发现错误，并把二者不一致的部分重发到收端。其特点是没有纠(检)错编码，电路较简单，但是需要反馈信道并且传输速率较低。第10章信道编辑原理 混合纠错(HEC，Hybrid Error Correction)：是FEC与ARQ的混合，发端发出便于检错和纠错的码，通过正向信道送到收端，收端对错误能纠正的就自动纠正，纠正不了时自动发出判决信号并送回发端，发端把收端认为有错并且无法纠正的消息重发到收端，以达到正确传输。这种方式具有 FEC与ARQ的特点，能充分发挥码的纠错和检错性能，在较差的信道中仍然可以收到好的效果，缺点是需要反馈信道以及复杂的译码
8、设备。第10章信道编辑原理 以上4种工作方式在数字通信系统中都得到了广泛的应用。例如,在高速防空系统中常采用前向纠错方式，在国际间的数字通信系统中往往采用检错重发的方式或者信息反馈的方式，而在复杂的短波信道与散射信道中则常采用混合纠错的方式。第10章信道编辑原理10.1.4 纠错码的基本概念纠错码的基本概念1 码长、码重和码距码长、码重和码距 码组(码字或码矢)中码元的数目称为码组的长度，简称码长。码组中非0位的数目称为码组的重量，简称码重。对于二进制码而言，码重W就是码组中1的数目，例如码组11010，码长n=5，码重W=3。第10章信道编辑原理两个等长码组之间对应位不同的数目称为这两个码组
9、的汉明距离，简称码距,例如码组11000与10011的距离d=3。而码组集合中全体码组之间距离的最小数值d0称为码的最小距离。由于两个码组模二相加，其不同的对应位必为1，而相同的对应位必为0，因此两个码组模二相加得到的新码组的重量就是这两个码组之间的距离。码的最小距离是衡量该码纠错能力的依据，是重要的参数。第10章信道编辑原理2 为什么纠错码能够检错或者纠错为什么纠错码能够检错或者纠错 现在以二进制码组为例说明纠错码检错和纠错的基本原理。分组码对数字序列是分段处理的，设每一段由k个码元组成，称做长度为k的信息组，又称k重。由于每个码元有0或1两个值，因此共有2k个不同的k重。每段长k的信息组，
10、以一定的规则增加r个称为监督元的多余度码元，来监督这k个信息元，这样就组成长为n=k+r的码组，又称n重，共得到2k个不同的n重。这2k个n重分别代表2k个不同的信息组，称为许用码组。长n的数字序列共有2n种可能的组合，其中2n-2k个n重未被选用，称为禁用码组。上述2k 个不同的长n的许用码组的集合称为分组码。分组码能够检错或者纠错的原因是每个n重中有多余度码元，或者说2n个n重中有禁用码组。举例说明如下：第10章信道编辑原理 设发送端发送A和B两个消息，分别用一位码元(k=1)表示，1代表A，0代表B。如果这两个信息组在传输中产生了错误，0错成了1或者1错成了0，则接收端不能发现这种错误，
11、更谈不上纠正错误,此时收到的消息就不可靠。如果每个一位长的信息组中添加上一个监督元(r=1)，其规则是与信息元重复，则这样编出的两个长为n=2的码组是11(代表A)和00(代表B)。11、00是许用码组，这两个码字组成一个(2，1)分组码，其特点是各码字的码元是重复的，因此又称为重复码。01、10是禁用码组。设发送11经信道传输错了一位，变成01或10，收端译码器根据重复码的规则，能发现有一位错误，但是不能指明错在哪一位，亦即不 第10章信道编辑原理能作出发送的消息是A(“11”)还是B(“00”)的判决。如果信道干扰严重，使发送码字的两位都产生错误，从而使11错成了00，则收端译码器根据重复
12、码的规则检验，不认为有错，并且判决为消息B，造成了错判。这种码距为2的(2，1)重复码能发现1个码元的错误，不能发现2个码元的错误(以下简称1个错误、2个错误、)，也不能纠正错误。如果仍然按照重复码的规则，再加一个监督元，则得到(3，1)重复码，它的两个码字为111和000，码距为3；其余6个码组(001，010，100，110，101，011)为禁用码组。设发送111(代表消息A)，译码器收到的3重为110，根据重复码的规则，发现有错，并且当采用最大似然法译码时，把与 第10章信道编辑原理发送码字最相似的码组认为是发送码组。110与111只有一位不同，而与000有两位不同，因此判决为111。
13、事实上，一般情况下错1位的可能性比错2位的可能性大得多，从统计的观点看，这样判决是正确的。因此，这种(3，1)码能纠正一个错误，但不能纠正两个错误，因为如果发送111，收到100，根据译码规则将译为000，这就判错了。类似于前面的分析，如果用这种码来检错，则可以发现两个错误，但是不能发现3个错误。如果按照重复码的规则编成(4，1)码，则长度为4的码组共有16个，其中1111和0000为许用码组，分别代表消息A和B，其余14个码组为禁用码组。类似的方法可以证明，这种码距为4的(4，1)码能够纠正一个错误，同时发现两个错误，如果仅作检错用，则可以发现3个错误。第10章信道编辑原理上述例子表明，纠错
14、码的抗干扰能力完全取决于许用码组之间的距离。码的最小距离 d0越大，说明码字间的最小差别越大，抗干扰能力就越强，即受较强的干扰时仍然可以不造成许用码组之间的混淆。纠错码的纠错效果与信道误码率有密切的关系：信道误码率越低，纠错效果越显著，反之不显著，信道误码率很大时甚至会出现“越纠越错”的现象。第10章信道编辑原理 香农编码定理告诉我们，只要信息传输速率不大于信道容量，在理论上存在一种方法，使得通过信道传输的数码的差错概率为任意小。香农编码定理没有给出具体的编码方法，但是它指明了研究的方向。第10章信道编辑原理3 分组码的纠分组码的纠(检检)错能力与最小码距的关系错能力与最小码距的关系 任一(n
15、，k)分组码，如果要在码字内：(1)检测e个随机错误，则要求码的最小距离d0e+1 (10.1)(2)纠正t个随机错误，则要求码的最小距离 d02t+1 (10.2)(3)纠正t个同时检测e(t)个随机错误，则要求码的最小距离d0t+e+1 (10.3)第10章信道编辑原理 下面利用几何图形进行简要证明。设A1、A2是分组码中相距d0的两个码字，分别位于A1及A2两点。由图10.2(a)可见，如果A1发生e个错误，则位置将移动e，至以A1为圆心、e为半径的圆上某点，考虑造成使A1、A2两码组最难分辨的情况是移至点。如果译码器不将 错判成A2，则必须使与A2之间的距离d(，A2)1，因此检测e个
16、错误的条件是d0e+1。第10章信道编辑原理图10.2 纠(检)错能力的几何解释第10章信道编辑原理由图10.2(b)可见，如果A1发生t个错误，则位置移至，d(A1，)=t。如果译码器能把正确判成A1，则必须要求d(A1，)t)个错误，则位置分别移至及，为了保证纠正t个同时检测e个错误，必须要求d(，)1，即d0t+e+1。这里说的“同时”是指在译码过程中,如果错误个数小于等于t，则能纠正；如果错误个数大于t 且小于等于e(et)，则能检测这些错误，但是不能纠正，或者说能检测t+e个错误，其中t个错误可以纠正。第10章信道编辑原理4 对纠错编码的基本要求对纠错编码的基本要求 以上讨论说明，码
17、的最小距离d0越大，码的纠(检)错的能力越强。但是，随着多余码元的增多，信息传输速率降低越多。通常用R=k/n来表示码字中信息元所占的比例，称为编码效率，简称码率。它是衡量码性能的又一个重要参数。码率越高，传信率就越高，但是此时纠错能力要降低，R=1时就没有纠错能力了。可见，码率与纠错能力之间是有矛盾的。第10章信道编辑原理对纠错编码的基本要求是：纠错和检错能力尽量强；编码效率尽量高；码长尽量短；编码规律尽量简单。实际应用中应根据具体指标要求，保证有一定的纠检错误的能力和编码效率，要易于实现，节省费用。第10章信道编辑原理10.2 检检 错错 码码10.2.1 奇偶监督码奇偶监督码1 意义及特
18、点意义及特点 奇偶监督码是奇监督码和偶监督码的统称，是一种最基本的检错码。在n-1个信息元后面附加一个监督元，使得长度为n的码字中1的个数保持为奇数或者偶数的码称为奇偶监督码。或者说,奇偶监督码是r=1、W为奇数或偶数的系统分组码。常用的奇偶监督码的码重W为偶数。设码字A=an-1，an-2，a1，a0满足an-1+an-2+a1+a0=0 (10.4)式中:a0为监督元；“+”为模二加(以后也这样表示，请读者注意)。由于这种码的每一个码字均按同一规则构成，因此又称为一致监督码。式(10.4)称为一致监督方程或监督方程。第10章信道编辑原理 利用式(10.4)，由信息元即可求出监督元。另外，如
19、果发生单个或者奇数个错误，就会破坏这个关系式，因此，通过该式能检测码字中是否发生了奇数个错误。以码长n=5为例，列出全部偶监督码字如表10.1所示。从表中可以看出，该码的最小码距为2，这是能检测单个错误所要求的最小d0值。人们常把注意力集中在检(纠)单个错误上，这是因为码字中发生单个错误的概率比发生两个、多个错误的概率要大得多。设码字中各码元的错误互相独立，误码率为10-4，则n=5的码字只错一位的概率为第10章信道编辑原理错两位的概率为错3、4、5位的概率分别为10-11、510-16、10-20。由此可见，要检(纠)错误，首先要解决单个错误，这样才抓住了主要矛盾。一般情况下用上述偶监督码来
20、检出奇数个错误，检错效果是令人满意的。奇偶监督码不能发现偶数个错误。奇偶监督码的编码效率很高，R=(n-1)/n，随着n的增大而趋近于1。第10章信道编辑原理第10章信道编辑原理2编码电路和检错电路编码电路和检错电路 奇偶监督码的编码可以用数字软件实现，也可以用编码电路(硬件)实现。图10.3是码长为5的偶监督码编码器。4位长的信息组，串行送入4级移位寄存器(输入定时缓冲器)，一旦存满，立即输送给输出定时缓冲器前4级，同时经模2运算得到监督元，存入输出缓冲器末级。编码完成后即可输出码字。第10章信道编辑原理图10.3 偶监督码编码器第10章信道编辑原理接收端的检错电路如图10.4所示。当一个接
21、收码组B完全进入5级移存器内时，开关S立即接通，从而取得检错信号M=b4+b3+b2+b1+b0。如果接收码组B无错，B=A，则 M=0；如果接收码组B有奇数个错误，则M=1。第10章信道编辑原理图10.4 偶监督码的检错电路第10章信道编辑原理行列监督码又称为水平垂直一致监督码、二维奇偶监督码或者矩阵码。它同时对水平(行)方向的码元和垂直(列)方向的码元实施奇偶监督。一般Lm个信息元，附加L+m+1个监督元，由L+1行、m+1列组成一个(Lm+L+m+1，Lm)行列监督码的码字。图10.5是(66，50)行列监督码的一个码字(L=5，m=10)，它的各行和各列对1的数目都实行偶数监督。可以逐
22、行传输，也可以逐列传输。译码时分别检查各行、各列的监督关系，判断是否有错。第10章信道编辑原理图10.5 行列监督码第10章信道编辑原理这种码具有较强的检测随机错误的能力，能发现所有1、2、3及其它奇数个错误，也能发现大部分偶数个错误，但是分布在矩形的四个顶点这类偶数个错误则例外。这种码适于检测突发错误。逐行传输时，能检测长度bm+1的突发错误；逐列传输时，能检测长度bL+1的突发错误。这种码还可以纠正单个错误以及仅在一行中的奇数个错误，因为这些错误的位置是可以由行、列监督而确定的。第10章信道编辑原理10.2.3 恒比码恒比码恒比码又称为等重码或者定1码，这种码的码字中1和0的位数保持恒定的
23、比例。由于每个码字的长度是相同的，因此，如果1、0恒比，则码字必等重。第10章信道编辑原理如果码长为n，码重为W，则此码的码字个数为，禁用码字数为。该码的检错能力较强，除对换差错(1和0成对地出错)不能发现外，其他各种错误均能发现。目前我国电传通信中普遍采用32码，该码共有个许用码字，用来传送10个阿拉伯数字，如表10.2所示。这种码又称为5中取3数字保护码。因为每个汉字是以4位十进制数来代表的，所以提高十进制数字传输的可靠性，就等于提高汉字传输的可靠性。实践证明，采用这种码后，我国汉字电报的差错率大为降低。第10章信道编辑原理第10章信道编辑原理 目前国际上通用的ARQ电报通信系统中，采用3
24、4码,即7中取3码，这种码共有个许用码字，93个禁用码字。35个许用码字用来代表不同的字母和符号。实践证明，应用这种码后，使国际电报通信的误码率保持在10-6以下。第10章信道编辑原理10.3 线线 性性 分分 组组 码码10.3.1 基本概念基本概念可以用线性方程组表述码的规律性的分组码称为线性分组码。奇偶监督码是一种线性分组码，因为它满足线性方程式(10.4)。现在以(7，3)分组码为例来说明线性分组码的意义及特点。设该码的码字为A=a6，a5，a4，a3，a2，a1，a0，其中前3位是信息元，后4位是监督元，可以用下列线性方程组来表述这种线性分组码，产生4个监督元：第10章信道编辑原理显
25、然,上述方程中各方程是线性无关的。对上式进行运算，可以得到(7，3)线性分组码的8个码字，如表10.3所示。我们可以把(n，k)线性分组码的每一个码字看成是一个n维线性空间中的一个矢量。长度为n的码组共有2n个，组成一个n维线性空间，(n，k)线性分组码共有2k个码字(kn)，构成了一个k维的线性子空间。因此，(n，k)线性分组码是n维线性空间的一个k维子空间，这是线性分组码的另一个定义。由于该线性子空间在模二加法运算中构成阿贝尔群，因此线性分组码又称为群码。第10章信道编辑原理第10章信道编辑原理某种集合称为群，此集合中的元素(在此为任一码组)对于某种运算(在此为模二加法)必须满足下列4个条
26、件：(1)封闭性(自闭律)。集合中的任意两个元素经此运算后得到的仍为该集合中的元素。例如A1+A2=A3，A6+A7=A1等(A1、A2、分别是表10.3中序号为1、2、的码字)。(2)有零元(乘法运算为单位元)。如上例中A0即是零元，A0+Ai=Ai i=0，1,，7第10章信道编辑原理(3)有负元(乘法运算为逆元)。线性分组码中任一码组即是它自身的负元,Ai+Ai=A0 i=0，1，7 (4)结合律成立。例如，(A2+A3)+A4=A2+(A3+A4)。如果除满足上述4个条件外，又满足交换律，则称为交换群或者阿贝尔群。由于线性分组码是满足交换律的，如A1+A2=A2+A1等，因此，线性分组
27、码对于模二加法运算构成交换群。第10章信道编辑原理(n，k)线性分组码的封闭性表明，码组集合中的任意两个码组模二相加所得的码组，一定在该码组集中。又由于两个码组模二和所得的码组的重量等于这两个码组的距离，因此(n，k)线性分组码中两个码组之间的距离一定等于该分组码中某一非全0码组的重量。所以，线性分组码的最小距离必等于码中非全0码字的最小重量。设A0为全0码矢，则有d0=Wmin(Ai)Ai(n，k)，i0 (10.6)第10章信道编辑原理上述重要特点告诉我们，如何去查找一个线性分组码的最小距离，进而明确该码的纠(检)错能力。除此之外，线性分组码还有以下特点：(1)d(A1，A2)W(A1)+
28、W(A2)；(2)d(A1，A2)+d(A2，A3)d(A1，A3)；(3)码字的重量或者全部为偶数，或者奇数重量的码字数等于偶数重量的码字数。第10章信道编辑原理10.3.2 汉明码汉明码 汉明码是一种高码率的纠单个错误的线性分组码，其特点是d0=3，码长n与监督元个数r满足关系式n=2r-1。现以r=3、n=7的(7，4)汉明码为例来说明(n，k)线性分组码编码和译码的理论依据。1 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 设(7，4)汉明码的码字A=a6，a5，a4，a3，a2，a1，a0，它有3个监督元，可以建立3个互相独立的监督关系式(10.7)第10章信道编辑原理写成矩阵形式为简记
29、为HAT=OT 第10章信道编辑原理或者AHT=O (10.9)其中AT是A的转置，OT是O=0 0 0的转置，HT是H的转置。(10.10)第10章信道编辑原理称为(7，4)汉明码的监督矩阵。(n，k)线性分组码的监督矩阵H由r行n列组成，这r行是线性无关的。系统码的监督矩阵可写成如下形式：H=PIr (10.11)称为典型监督矩阵，Ir为rr的单位矩阵，P是rk的矩阵。对式(10.10)，有第10章信道编辑原理如果信息元已知，则通过P矩阵可以求得监督元。将式(10.7)变换成(10.12)即满足第10章信道编辑原理或者 (10.13)第10章信道编辑原理只要将PT矩阵扩展一下，在其左边加上
30、44的单位矩阵，即可由已知的信息元求得码组A，即(10.14)其中。设信息组M=a6，a5，a4，a3，则式(10.14)可以写成A=MG (10.15)第10章信道编辑原理G称为生成矩阵。由生成矩阵及信息组就可以产生出全部码字。G由k行n列组成，每一行是一个码字，k行线性无关。系统码的生成矩阵可以写成：G=IkPT(10.16)称为典型生成矩阵。利用式(10.14)产生的全部(7，4)码的码字如表10.4所示。第10章信道编辑原理第10章信道编辑原理2 伴随式伴随式(校正子校正子)设发送码组A=an-1，an-2，a1，a0，接收码组B=bn-1，bn-2，b1，b0，错误图样(误差矢量)为
31、E=en-1，en-2，e1，e0E=B-A=B+A第10章信道编辑原理E矩阵中哪位出现1，就表示接收码组B中相应的码元错了。接收端利用监督矩阵来检测接收码组B中的错误。令S=BHT，称为伴随式或者校正子，则S=BHT=(A+E)HT=AHT+EHT=EHT (10.17)由于E为1n矩阵，HT为nr矩阵，因此S为1r矩阵，即r列的行矩阵S=Sr-1，Sr-2，S1，S0(10.18)第10章信道编辑原理由式(10.17)可知，S与E之间有确定的线性变换关系，即S能代表B中错误的情况，B无错则S=0，B有错则S0(非全0矩阵)。S有2r种不同的形式，可以代表2r-1种错误图样。为了用伴随式指明
32、单个错误的位置以便纠正，要求2r-1n (10.19)第10章信道编辑原理 对于(7，4)汉明码，n=7，r=3，n=2r-1，即对式(10.19)取等号。这就表明用来纠正单个错误时，汉明码所用的监督码元位数最少。与码长相同的其他纠单个错误的码比较，其码率最高。上述(7，4)汉明码的伴随式S与错误图样E的对应关系可以由式(10.17)求得，如表10.5所示。在接收端的译码器中有专门的伴随式计算电路，可实现检错和纠错。第10章信道编辑原理第10章信道编辑原理10.3.3 循环码循环码 循环码是一类重要的线性分组码，它的构造便于运用代数理论来研究。其编译码电路比较简单，因此应用十分广泛。1 循环码
33、的意义及特点循环码的意义及特点 如果线性分组码的任一码组循环移位所得的码组仍在该码组集合中，则此线性分组码称为循环码。很明显，(n，1)重复码是一个循环码。表10.6中的(7，3)码及表10.7中的(6，3)码也都是循环码，其循环特性分别如图10.6及图10.7所示。循环圈上的数字为码字的序号。由图可见，同一循环圈上的各码组重量是相等的。全0、全1码组分别自成循环圈。循环码的循环圈数目2。第10章信道编辑原理第10章信道编辑原理第10章信道编辑原理图10.6 (7，3)循环码的循环圈 第10章信道编辑原理图10.7 (6，3)循环码的循环圈第10章信道编辑原理 人们常用代数多项式来表示循环码的
34、码字，称为码多项式。(n，k)循环码的码多项式按降幂顺序排列为 A(x)=an-1xn-1+an-2xn-2+a1x+a0 (10.20)码组中各位码元的数值是其码多项式中相应各项的系数值(0或1)。例如,表10.6中第4号码字可以用多项式A4(x)=x6+x3+x2+x表示。第10章信道编辑原理2 生成多项式及生成矩阵生成多项式及生成矩阵循环码中次数最低的多项式(全0码字除外)称为生成多项式g(x)。可以证明，g(x)是常数项为1的r=n-k次多项式，是xn+1的一个因式。循环码的码多项式都是g(x)的倍式。用多项式来表示生成矩阵的各行，则生成矩阵可以写成(10.21)其中 g(x)=xr+
35、gr-1xr-1+g1x+1 (10.22)第10章信道编辑原理例如表10.6中(7，3)循环码，n=7，k=3，r=4，其生成多项式及生成矩阵分别为即第10章信道编辑原理生成矩阵中的3行都是表10.6中的码字，并且是线性无关的。表10.6中的所有码字用多项式表示时，均是g(x)的倍式。g(x)可由x7+1分解因式(系数按模二运算)得到x7+1=(x4+x3+x2+1)(x3+x2+1)。设信息组M=mk-1，mk-2，m1，m0，则(n，k)循环码的所有码字由下式生成：A(x)=MG(x)=(mk-1xk-1+mk-2xk-2+m1x+m0)g(x)=m(x)g(x)(10.23)第10章信
36、道编辑原理其中m(x)为信息组多项式，其最高次数为k-1。由上式可见，知道m(x)及g(x)就可以生成全部码字。但是，由式(10.23)直接产生的码字并非系统码。由于(n，k)循环码的所有码多项式都是g(x)的倍式，最高次数为n-1，因此系统循环码的码多项式可以表示为A(x)=xn-km(x)+xn-km(x)(10.24)其中，前一部分代表信息组；后一部分用 表示，是xn-km(x)被g(x)除得的余式，代表监督组。第10章信道编辑原理3 监督多项式及监督矩阵监督多项式及监督矩阵 由于(n，k)循环码中的g(x)是xn+1的因式，因此可以令 (10.25)由于g(x)是常数项为1的r次多项式
37、，因此h(x)必是常数项为1的k次多项式。h(x)称为监督多项式。与式(10.21)所表示的G(x)相对应，监督矩阵可以表示为(10.26)第10章信道编辑原理其中h*(x)=xk+h1xk-1+h2xk-2+hk-1x+1 (10.27)是h(x)的逆多项式。例如表10.6中的(7，3)循环码：g(x)=x4+x3+x2+1则 h*(x)=x3+x+1 第10章信道编辑原理于是即第10章信道编辑原理4 编码电路编码电路根据式(10.24)，利用多项式除法电路求xn-km(x)除以g(x)的余式，即可产生(n，k)系统循环码。当g(x)=x4+x3+x2+1时，(7，3)循环码的编码器如图10
38、.8所示。D0D1D2D3是4级移存器，反馈线的连接与g(x)的非0系数相对应。首先，4级移存器清零，3位信息元输入时，门1断开，门2接通，直接输出信息元。第3次移位脉冲来时,将除法电路运算所得的余数存入4级移存器中。第47次移位时，门2断开，门1接通，输出监督元(即余数)。当一个码字输出完毕后,就将移存器清零，等待下一组信息数字送入后重新编码。设输入的信息组为110，图10.8中各器件及端点状态变化情况如表10.8所示。该编码器编出的全部码字如表10.6所示。第10章信道编辑原理图10.8 (7，3)循环码编码器第10章信道编辑原理第10章信道编辑原理5 译码电路译码电路设接收码组、错误图样
39、及伴随式的多项式分别为B(x)=bn-1xn-1+bn-2xn-2+b1x+b0E(x)=en-1xn-1+en-2xn-2+e1x+e0S(x)=Sr-1xr-1+Sr-2xr-2+S1x+S0第10章信道编辑原理 可以证明S(x)=BHT(x)=B(x)=E(x)(10.28)即B(x)或E(x)除以g(x)所得的余式就是S(x)。用于检错时，根据S(x)是否为零来判决接收码组B是否有错，S(x)=0时,表明B无错，S(x)0时,表明B有错。用于纠错时，需要根据不同的非零S(x)来指明不同的错误位置，从而纠正错误。伴随式S(x)的计算由 g(x)除法电路来实现。利用式(10.28)可以求得
40、(7，3)循环码单个错误的错型多项式 E(x)与伴随式S(x)的对应关系，如表10.9所示。第10章信道编辑原理第10章信道编辑原理针对接收码组中单个错误出现在首位的错误图样及相应的伴随式来设计组合逻辑电路，以实现纠错。由于循环码的伴随式也具有循环移位特性，因此利用移存器的循环移位就可以纠正任何一位上的单个错误。为了在g(x)除法电路的移存器中存放如表10.9所示的与E(x)对应的伴随式，接收码组必须从除法电路的第一级移存器输入。第10章信道编辑原理上述(7,3)循环码的译码电路如图10.9所示。接收到的B(x)(高次项在前，低次项在后)一方面送入7级缓冲移位寄存器，一方面送入g(x)除法电路
41、计算伴随式。第7次移位时，7个码元一组的码组全部送入缓存器，B(x)中首位b6输出，同时g(x)除法电路也得到了伴随式S(x)(共4项，由低次到高次分别存于D0、D1、D2、D3中)，如果首位b6有错，则D0D1D2D3的状态必为0111。经与门输出1(纠错信号)，即可纠正b6的错误，该纠错信号同时也送到S(x)计算电路去清零，如图中虚线所示。此纠错译码过程如表10.10所示。其他位上错误的纠正过程读者可自行画出。第10章信道编辑原理图10.9 (7，3)循环码译码器之一第10章信道编辑原理第10章信道编辑原理为使译码连续不断地进行，在译码器中需要采用两套g(x)除法电路。采用像编码器中的变形
42、除法电路进行译码也是可以的，但是逻辑控制电路有所不同，如图10.10所示，其译码过程供读者自己研究。第10章信道编辑原理图10.10 (7，3)循环码译码器之二第10章信道编辑原理10.3.4 BCH码码BCH码是循环码的一个子集，它是以三个发明者的名字Bose、Chaudhuri和Hocquenghem命名的，一般用于纠正t个错误。BCH码的设计因具有良好的通用性并且有高效的译码算法而受到高度重视。对于任意码长m2，纠错数目为t的编码，都存在满足下列参数的BCH码：n=2m-1，n-kmt，dmin=2t+1。由于m和t可以自由选择，因此在码长和码率的设计上有很大的选择余地。BCH码已经过了
43、详细的推导，并且有了码长为7255的BCH码生成多项式的系数表，有兴趣的读者可以查阅相关文献。第10章信道编辑原理10.3.5 里德里德-索洛蒙码索洛蒙码里德-索洛蒙(R-S，Reed-Solomon)码是BCH码的子集，因此也属于循环码。它是一种非二进制码，即码字c=(c1，c2,，cn)中的任意元素ci是一个q进制数，q=2k，这时每个q进制字符包含k比特信息。在(N，K)R-S码中，长度为K的q进制码元将映射为长度为N的q进制码元，然后在信道上传送，如图10.11所示。第10章信道编辑原理图10.11 R-S码编码器第10章信道编辑原理R-S码是按照下列条件定义的BCH码：N=q-1=2
44、k-1(k=2，3，)，dmin=N-K+1，码率Rc=K/N。R-S码能够纠正t=(dmin-1)/2个码元错误。里德-索洛蒙码具有优越的距离特性，特别适于与q进制调制联合使用。R-S码还能够有效地纠正突发错误，因为突发错误在R-S码中表现为少量几个码元错误，因而易于纠正。在二进制编码中，同样的突发错误会导致许多比特的错误，因而不容易纠正。R-S码还可以与二进制编码进行连接，以获得更强的纠错能力。与R-S码连接的二进制编码可以是分组码或者卷积码。第10章信道编辑原理 图10.12 m=4的(28，16)交错码第10章信道编辑原理10.3.6 交错码交错码交错码又称交织码，是一种能纠正突发错误
45、的码。它是利用纠随机错误的码，以交错的方法来构造码本的。把纠随机错误的(n，k)线性分组码的m个码字，排成m行的一个码阵，该码阵称为交错码阵。一个交错码阵就是交错码的一个码字。交错码阵中的每一行称为交错码的子码或行码，行数m称为交错度。图10.12所示的是(28，16)交错码的一个码字，其行码是能纠单个随机错误的(7，4)线性分组码，交错度m=4。传输时按列的次序进行，因此送往信道的交错码的一个码字为a61 a62 a63 a64 a51 a52 a01 a02 a03 a04。第10章信道编辑原理 图10.12 m=4的(28，16)交错码第10章信道编辑原理在传输过程中如果发生长度b4的单
46、个突发错误，那么无论从哪一位开始，至多只影响图10.12码阵中每一行的一个码元。接收端把收到的交错码的码字再排成如图10.12所示的码阵，然后逐行分别译码，由于每一行码能纠正一个错误，因此4行译完后，就可把b4 的突发错误纠正过来。第10章信道编辑原理如果要纠正较长的突发错误，则可以把码阵中的行数增加，即增大交错度(交织度)。一般，一个(n，k)码能纠正t个随机错误，按照上述方法交错，交错度为m时即可得到一个(nm，km)交错码,该交错码能纠正长度bmt的单个突发错误。可以证明，如果(n，k)是一个循环码，它的生成多项式为g(x)，那么(nm，km)交错码也是一个循环码，其生成多项式为 g(x
47、m)，且码率与其行码相同。第10章信道编辑原理10.4 卷卷 积积 码码卷积码的规律性与分组码有明显的区别。(n，k)线性分组码的规律性完全局限在各码组之内,每个码组的n个码元完全由本组的k个信息元确定。或者说，各码组中的监督元只对本组的信息元起监督作用。卷积码则不同，每个(n，k)码段(也称子码，通常较短)内的 n个码元不仅与该码段内的信息元有关，而且与前面m段内的信息元有关。或者说，各码段内的监督元不仅对本码段而且对前面m段内的信息元起监督作用。卷积码序列的每一码段与前后有关码段互相关联，一环扣一环，因此又称为连环码。这种码能用卷积运算的线性方程组描述。第10章信道编辑原理分组码各码组彼此
48、独立地进行编码和译码。卷积码则不然，无论编码还是译码，各子码都不能独立地进行。卷积码子码间的约束关系如图10.13所示。图中A1，A2,表示卷积码序列中的各个子码，均是(n，k)线性分组码，各子码之间的约束范围如图中虚线方框所示。通常称m为编码存储，它反映了输入信息元在编码器中需要存储的时间长短；称N=m+1为编码约束度，它是相互约束的码段个数；称nN为编码约束长度，它是相互约束的码元个数。卷积码常用子码长度、子码中的信息元个数及编码存储三个参数表示，记为(n，k，m)，或用约束度及子码符号表示，记为N(n，k)，也可用约束长度内的分组码形式表示，记为(nN，kN)。如果卷积码的各子码是系统码
49、，则称该卷积码为系统卷积码，否则为非系统卷积码。很明显，假如m=0，N=1，那么卷积码就是(n，k)分组码了。第10章信道编辑原理图10.13 卷积码子码间的约束关系第10章信道编辑原理图10.14是一个(3，1，2)系统卷积码的编码器。由三级移位寄存器、两个模二加法器及开关电路组成。编码前，各级移存器清零，信息元按a1 a2 a3 aj-2 aj-1 aj 的顺序输入编码器。每输入一个信息元aj，开关S依次接到aj、aj1、aj2各端点一次，编出一个子码ajaj1aj2(n=3，k=1)，其中两个监督元由下式确定：(10.29)编码器编出的任一子码均与前面两段信息元有关，因此编码存储m=2，
50、编码约束度N=m+1=3，约束长度Nn=9。第10章信道编辑原理图10.14 (3，1，2)卷积码编码器及输入输出关系第10章信道编辑原理10.5 复合编码复合编码分组码和卷积码的性能都与其距离特性有关。为了设计一个达到给定码率并且具有较好距离特性的分组码或者卷积码，只有增加码字的分组长度n或者卷积码的约束长度，这将导致译码器复杂度增加。第10章信道编辑原理为了在增加码字的有效分组长度或约束长度的同时，限制设备复杂度的增加，人们提出了许多方案，其中大多数方法都是通过合成简单编码而得到复杂编码，合成码的译码方法也是基于前面讨论的简单编码。如果采用复杂的最佳译码算法，则通常也能获得满意的效果。下面
