数字通信技术第10章

1、1信道编码：信道编码：p目的：提高信号传输的可靠性。目的：提高信号传输的可靠性。p方法：增加多余比特，以发现或纠正错误。方法：增加多余比特，以发现或纠正错误。 差错控制差错控制：包括信道编码在内的一切纠正错误手段。：包括信道编码在内的一切纠正错误手段。产生错码的原因：产生错码的原因：p乘性干扰引起的码间串扰乘性干扰引起的码间串扰p加性干扰引起的信噪比降低加性干扰引起的信噪比降低 信道分类：按照加性干扰造成错码的统计特性不同划分信道分类：按照加性干扰造成错码的统计特性不同划分p随机信道：错码随机出现，例如由白噪声引起的错码随机信道：错码随机出现，例如由白噪声引起的错码 p突发信道：错码相对集中出

2、现，例如由脉冲干扰引起的错突发信道：错码相对集中出现，例如由脉冲干扰引起的错码。码。 p混合信道：既存在随机错码又存在突发错码混合信道：既存在随机错码又存在突发错码 2差错控制技术的种类差错控制技术的种类：p检错重发检错重发：u能发现错码，但是不能确定错码的位置。能发现错码，但是不能确定错码的位置。u通信系统需要有双向信道。通信系统需要有双向信道。 p前向纠错前向纠错(FEC)：利用加入的差错控制码元，不但能够发：利用加入的差错控制码元，不但能够发现错码，还能纠正错码。现错码，还能纠正错码。p 反馈校验反馈校验：u将收到的码元转发回发送端，将它和原发送码元比较。将收到的码元转发回发送端，将它和

3、原发送码元比较。u缺点：需要双向信道，传输效率也较低。缺点：需要双向信道，传输效率也较低。p检错删除检错删除：u在接收端发现错码后，立即将其删除。在接收端发现错码后，立即将其删除。u适用在发送码元中有大量多余度，删除部分接收码元不适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。影响应用之处。 3p监督码元监督码元：上述：上述4种技术中除第种技术中除第3种外，都是在接收端种外，都是在接收端识别有无错码。所以识别有无错码。所以在发送端需要在信息码元序列中在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元增加一些差错控制码元，它们称为监督码元。p不同的编码方法，有不同的

4、检错或纠错能力。不同的编码方法，有不同的检错或纠错能力。p多余度多余度：就是：就是指增加的监督码元多少指增加的监督码元多少。例如例如，若编码，若编码序列中序列中平均每两个信息码元就添加一个监督码元平均每两个信息码元就添加一个监督码元，则，则这种编码的这种编码的多余度为多余度为1/3。p编码效率编码效率(简称码率简称码率) ：设编码序列中：设编码序列中信息码元数量为信息码元数量为k，总码元数量为总码元数量为n，则比值，则比值k/n 就是编码效率就是编码效率。p冗余度冗余度：监督码元数监督码元数(n-k) 和信息码元数和信息码元数 k 之比之比。p理论上，差错控制以降低信息传输速率为代价换取提理论

5、上，差错控制以降低信息传输速率为代价换取提高传输可靠性。高传输可靠性。4编码序列的参数编码序列的参数un 编码序列中总码元数量编码序列中总码元数量uk 编码序列中信息码元数量编码序列中信息码元数量ur 编码序列中差错控制码元数量编码序列中差错控制码元数量 （差错控制码元，以后称为监督码元或监督位（差错控制码元，以后称为监督码元或监督位 ）uk/n 码率（编码效率）码率（编码效率）u(n - k) / k = r / k 冗余度冗余度ur / n 多余度多余度5自动要求重发自动要求重发(ARQ)系统（系统（Automatic Repeate Quest）p停止等待停止等待ARQ系统系统 停止等待

6、ARQ系统接收数据ACKACKNAKACKACKNAKACK1233455t发送数据12334556t有错码组有错码组u数据按分组发送。每发送一组数据后发送端等待接收端数据按分组发送。每发送一组数据后发送端等待接收端的确认的确认(ACK)答复，然后再发送下一组数据。答复，然后再发送下一组数据。u图中的第图中的第3组接收数据有误，接收端发回一个否认组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第答复。这时，发送端将重发第3组数据。组数据。u特点：特点：工作在半双工状态，时间没有得到充分利用，传工作在半双工状态，时间没有得到充分利用，传输效率较低。输效率较低。6p 拉后拉后A

7、RQ系统系统拉后ARQ系统214365798接收数据有错码组有错码组910 1110 11 12576ACK1NAK5NAK9ACK55769521436798发送数据10 1110 11 12重发码组重发码组u发送端连续发送数据组，接收端对于每个接收到的数据发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认组都发回确认(ACK)或否认或否认(NAK)答复。答复。u例如，图中第例如，图中第5组接收数据有误，则在发送端收到第组接收数据有误，则在发送端收到第5组接组接收的否认答复后，从第收的否认答复后，从第5组开始重发数据组。组开始重发数据组。u在这种系统中在这种系统中需要对发送的数据组

8、和答复进行编号，以需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。便识别。显然，这种系统需要双工信道。7p 选择重发选择重发ARQ系统系统选择重发ARQ系统9接收数据有错码组有错码组214365759810 11131412发送数据9958521436710 1113 1412重发码组重发码组NAK9ACK1NAK5ACK5ACK9u它只重发出错的数据组，因此进一步提高了传输效率它只重发出错的数据组，因此进一步提高了传输效率8 ARQ的主要特点：与前向纠错比较的主要特点：与前向纠错比较p优点优点u监督码元较少，即码率较高监督码元较少，即码率较高u检错的计算复杂度较低检错

9、的计算复杂度较低u能适应不同特性的信道能适应不同特性的信道p缺点缺点u需要双向信道需要双向信道u不适用于一点到多点的通信系统或广播系统不适用于一点到多点的通信系统或广播系统u传输效率降低，可能因反复重发而造成事实上的通传输效率降低，可能因反复重发而造成事实上的通信中断信中断u在要求实时通信的场合，例如电话通信，往往不允在要求实时通信的场合，例如电话通信，往往不允许使用许使用ARQ法法9ARQ系统的原理方框图系统的原理方框图p在发送端，输入的信息码元在编码器中被分组编码（加入在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器中。监督码元）后，除了立

10、即发送外，还暂存于缓冲存储器中。若接收端解码器检出错码，则由解码器控制产生一个重发若接收端解码器检出错码，则由解码器控制产生一个重发指令。此指令经过反向信道送到发送端。由发送端重发控指令。此指令经过反向信道送到发送端。由发送端重发控制器控制缓冲存储器重发一次。制器控制缓冲存储器重发一次。p接收端仅当解码器认为接收信息码元正确时，才将信息码接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。元送给收信者，否则在输出缓冲存储器中删除接收码元。p当解码器未发现错码时，经过反向信道发出不需重发指令。当解码器未发现错码时，经过反向信道发出不需重发指令。发送

11、端收到此指令后，即继续发送后一码组，发送端的缓发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。冲存储器中的内容也随之更新。10分组码举例分组码举例p设：有一种由设：有一种由3位二进制码元构成的编码，它共有位二进制码元构成的编码，它共有23 = 8种种不同的可能码组，可以表示不同的可能码组，可以表示8种不同天气：种不同天气：000 晴晴 011 云云 101 阴阴 110 雨雨100 雪雪 001 霜霜 010 雾雾 111 雹雹 其中，若一个码组中发生错码，则将变成另一个信息码组。其中，若一个码组中发生错码，则将变成另一个信息码组。这时，接收端将无法发现错误。这时

12、，接收端将无法发现错误。 p若在此若在此8种码组中仅允许使用种码组中仅允许使用4种来传送天气，例如：种来传送天气，例如：000 晴晴 011 云云 101 阴阴 110 雨雨 为为许用码组许用码组，其他，其他4种不允许使用，称为种不允许使用，称为禁用码组禁用码组。 这时，接收端有可能发现（检测到）码组中的一个错码。这时，接收端有可能发现（检测到）码组中的一个错码。 例例: “000”（晴）中错了一位，变成（晴）中错了一位，变成“100”或或“010”或或“001” 这种编码只能检测错码，不能纠正错码这种编码只能检测错码，不能纠正错码。 p若规定只允许用两个码组：例如若规定只允许用两个码组：例如

13、000 晴晴 111 雨雨就能检测两个以下错码，或纠正一个错码。就能检测两个以下错码，或纠正一个错码。 11分组码概念分组码概念p 将信息码分组，为每组信息码附加若干监督码的编码将信息码分组，为每组信息码附加若干监督码的编码称为称为分组码。分组码。即即 分组码分组码 信息位信息位 监督位监督位 在分组码中，监督码元仅监督本码组中的信息码元。在分组码中，监督码元仅监督本码组中的信息码元。p 分组码符号：分组码符号：(n, k)其中，其中，n 码组总长度，码组总长度， k 信息码元数目。信息码元数目。 r = n k 监督码元数目。监督码元数目。下表中的码组为下表中的码组为(3, 2)码。码。信息

14、位监督位晴000云011阴101雨11012p 分组码的一般结构：分组码的一般结构：p 分组码的参数：分组码的参数：u码重：码组内码重：码组内“1”的个数。例：的个数。例： “101”的码重是的码重是2u码距：两码组中对应位取值不同的位数，又称汉明距离。码距：两码组中对应位取值不同的位数，又称汉明距离。 例：例： “000”晴，晴，“011”云，云，“101”阴，阴，“110”雨，雨， 4个码组之间，任意两个的距离均为个码组之间，任意两个的距离均为2 u最小码距最小码距(d0) ：各码组间的最小距离。：各码组间的最小距离。k个信息位r个监督位an-1an-2.arar-1an-2.a0t码长

15、n = k + r分组码的结构13p码距的几何意义：以码距的几何意义：以n = 3的编码为例的编码为例 u每个码组的每个码组的3个码元值个码元值(a1, a2, a3)就是此立方体各顶点的坐就是此立方体各顶点的坐标。码距是对应于图中各顶点之间沿立方体各边行走的几标。码距是对应于图中各顶点之间沿立方体各边行走的几何距离。何距离。例：例：“000”晴，晴，“011”云，云，“101”阴，阴，“110”雨，雨， 4个码组之间，任意两个的距离均为个码组之间，任意两个的距离均为2u一般而言，码距是一般而言，码距是 n 维空间中单位正多面体顶点之间的汉维空间中单位正多面体顶点之间的汉明距离。明距离。(0,

16、0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a114码距和检纠错能力的关系码距和检纠错能力的关系一种编码的纠检错能力：决定于最小码距一种编码的纠检错能力：决定于最小码距d0的值。的值。p为了能检测为了能检测e个错码，要求个错码，要求 最小码距为最小码距为p为了能纠正为了能纠正 t 个错个错 码，要求最小码距码，要求最小码距 10 ed0123BA汉明距离ed0码距等于3的两个码组120 tdBtA汉明距离012345td0码距等于5的两个码组15p为了能纠正为了能纠正t个错码，同时检测个错码，同时检测e个错码，要求最小码距个

17、错码，要求最小码距纠检结合工作方式：纠检结合工作方式：n当错码数量少时，系统按前向纠错方式工作，以节当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；省重发时间，提高传输效率；n当错码数量多时，系统按反馈重发的纠错方式工作，当错码数量多时，系统按反馈重发的纠错方式工作，以降低系统的总误码率。以降低系统的总误码率。 AB1tt汉明距离e码距等于(e+t+1)的两个码组)(10teted1610.3.1 误码率性能和带宽的关系误码率性能和带宽的关系 采用编码降低误码率采用编码降低误码率所付出的代价是带宽的增大所付出的代价是带宽的增大。10-610-510-410-310-210

18、-1编码后Eb/n0 (dB)编码和误码率关系PeCDEAB2PSKA与与B点：相同的接收信噪比下点：相同的接收信噪比下误码率降低约一个半数量级。误码率降低约一个半数量级。1710.3.2 功率和带宽的关系功率和带宽的关系采用编码以节省功率，并保持采用编码以节省功率，并保持误码率不变，付出的代价也是误码率不变，付出的代价也是带宽增大。带宽增大。 10-610-510-410-310-210-1编码后Eb/n0 (dB)编码和误码率关系PeCDEAB2PSKC与与D点：相同的误码率下，点：相同的误码率下，编码后输入信噪比可降低约编码后输入信噪比可降低约2dB，即可以节省功率，即可以节省功率2dB

19、。通常称这通常称这2 dB为为编码增益。编码增益。1810.3.3 传输速率和带宽的关系传输速率和带宽的关系对于给定的传输系统，其传输速率和对于给定的传输系统，其传输速率和Eb/n0的关系：的关系：式中，式中，RB 码元速率。码元速率。 提高传输速率，采用编提高传输速率，采用编码以保持误码率不变；付出码以保持误码率不变；付出的代价仍是带宽增大的代价仍是带宽增大。BsssbRnP)T/(nPnTPnE0000110-610-510-410-310-210-1编码后Eb/n0 (dB)编码和误码率关系PeCDEAB2PSK提高码元速率后由提高码元速率后由C点升到点升到E点（信噪比下降，误码率点（信

20、噪比下降，误码率增大），用纠错编码后，将增大），用纠错编码后，将误码率降到误码率降到D点。这时付出点。这时付出的代价仍是带宽增大的代价仍是带宽增大1910.3.4 编码增益编码增益定义：在保持误码率恒定条件下，采用纠错编码所节省的信定义：在保持误码率恒定条件下，采用纠错编码所节省的信 噪比噪比Eb/n0称为编码增益：称为编码增益： 式中，式中，(Eb/n0)u 未编码时的信噪比未编码时的信噪比(dB)； (Eb/n0)c 编码后所需的信噪比编码后所需的信噪比(dB)。)(/00dBnEnEGcbubdB2010.4.1 一维奇偶监督码一维奇偶监督码奇偶监督码奇偶监督码 分为奇数监督码和偶数监督

21、码两类。分为奇数监督码和偶数监督码两类。在奇偶监督码中，监督位只有在奇偶监督码中，监督位只有1位，故码率等于位，故码率等于k/(k+1)。偶数监督码中，此监督位使码组中偶数监督码中，此监督位使码组中“1”的个数为偶数的个数为偶数：式中，式中，a0为监督位，其他位为信息位。为监督位，其他位为信息位。奇数监督码中，此监督位使码组中奇数监督码中，此监督位使码组中“1”的个数为奇数：的个数为奇数：0021aaann1021aaann21检错能力检错能力 能够检测奇数个错码。能够检测奇数个错码。 n设：码组长度为设：码组长度为n， 码组中各个错码的发生是独立的和等概率的，码组中各个错码的发生是独立的和等

22、概率的， 则在一个码组中出现则在一个码组中出现 j 个错码的概率为个错码的概率为 式中，式中， 为在为在n个码元中有个码元中有j个错码的组合数。个错码的组合数。n奇偶监督码不能检测码组中出现的偶数个错码奇偶监督码不能检测码组中出现的偶数个错码，所以在一，所以在一个码组中有错码而不能检测的概率等于个码组中有错码而不能检测的概率等于: 当当n为偶数时为偶数时 当当n为奇数时为奇数时 jnjnj)p(pC)n, j(P1)!( !jnjnCnj2/1222)1 (njjnjnjuppCP2/ )1(1222)1 (njjnjnjuppCP22例：例：右表中的编码是偶数监督码。右表中的编码是偶数监督码

23、。 设信道的误码率为设信道的误码率为10-4，错码，错码 的出现是独立的。试计算其不的出现是独立的。试计算其不 能检测的误码率。能检测的误码率。将给定条件代入式将给定条件代入式计算得出计算得出由计算结果可见，此编码可以将误码率从由计算结果可见，此编码可以将误码率从10-4降低到降低到10-8量量级。效果非常明显。级。效果非常明显。信息位监督位晴0000云0101阴1001雨11002/1222)1 (njjnjnjuppCP8244324220444224221242421066612616111pppppp)p(p)p(pC)p(pC)p(pCPjjjju2311na12na11a10a21

24、na22na21a20amna1mna2ma1ma01nc2nc1c0c10.4.2 二维奇偶监督码二维奇偶监督码n码率等于码率等于n有可能检测偶数个错码有可能检测偶数个错码n适合检测突发错码适合检测突发错码 n能够纠正部分错码。能够纠正部分错码。 例如：例如： 一行中有奇数个错码一行中有奇数个错码nmnmnk)1()1(只对构成矩形四角的错码无法检测。只对构成矩形四角的错码无法检测。24基本概念基本概念n代数码代数码 利用利用代数关系代数关系式产生监督位的编码式产生监督位的编码(不一定线性不一定线性)n线性分组码线性分组码 代数码的一种，其监督位和信息位的关系代数码的一种，其监督位和信息位的

25、关系 由由线性代数方程线性代数方程决定决定n汉明码汉明码 一种能够纠正一个错码的线性分组码一种能够纠正一个错码的线性分组码n校正子：校正子：在偶数监督码中，计算在偶数监督码中，计算实际上就是计算实际上就是计算并检验并检验S是否等于是否等于0。 S称为校正子称为校正子。n监督关系式：监督关系式：0021aaann021aaaSnn021aaaSnn25纠错基本原理纠错基本原理n 中，中，S只有两种取值，故只能表示只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。有错和无错，而不能进一步指明错码的位置。 n若此若此码组长度增加一位码组长度增加一位，则能增加一个监督关系式。这样，则能增

26、加一个监督关系式。这样，就能就能得到两个校正子得到两个校正子。两个校正子的可能取值有。两个校正子的可能取值有4种组合，种组合，即即00，01，10，11，故，故能表示能表示4种不同的信息种不同的信息。若用其中。若用其中一一种组合表示无错码种组合表示无错码，则还有，则还有其它其它3种种组合组合可以用于可以用于指明一个指明一个错码的错码的3种不同位置。种不同位置。 从而可以有从而可以有纠错纠错能力。能力。n一般而言，一般而言，若有若有 r 个监督关系式，则个监督关系式，则 r 个校正子可以指明个校正子可以指明一个错码的一个错码的 (2r 1) 个不同位置。个不同位置。 n当校正子可以指明的错码位置

27、数目等于或大于码组长度当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够时，才能够纠正码组中任何一个位置上的错码纠正码组中任何一个位置上的错码，即，即要求要求021aaaSnn1212rknrr或26汉明码汉明码n例例：要求设计一个能够纠正：要求设计一个能够纠正1个错码的分组码个错码的分组码(n, k)，给定，给定的码组中有的码组中有4个信息位，即个信息位，即k = 4。 p由由要求监督位数要求监督位数r 3。若取。若取r = 3，则，则n = k + r = 7。现在用。现在用a6 a5 a4 a3 a2 a1 a0表示这表示这7个码元，用个码元，用S1 S2 S3表示校正子，表示

28、校正子，则这则这3个校正子恰好能够指明个校正子恰好能够指明23 1 = 7个错码的位置。个错码的位置。p若规定校正子和错码位置的关系如下表，则仅当在若规定校正子和错码位置的关系如下表，则仅当在a6 a5 a4 a2位置上有错码时，校正子位置上有错码时，校正子S1的值才等于的值才等于1；否则；否则S1的值为零。这就意味着的值为零。这就意味着a6 a5 a4 a2四个码元构成偶数监督四个码元构成偶数监督关系：关系：p同理，有同理，有S1 S2 S3错码位置S1 S2 S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码1212rknrr或24561aaaa

29、S13562aaaaS03463aaaaS27p在编码时，信息位在编码时，信息位a6 a5 a4 a3的值由输入信号决定，它们的值由输入信号决定，它们是随机的。监督位是随机的。监督位a2 a1 a0是按监督关系确定的，应该保是按监督关系确定的，应该保证上列证上列3式中的式中的校正子等于校正子等于0，即有，即有给定信息位后，为了给定信息位后，为了计算监督位计算监督位，上式可，上式可以改写为以改写为按照上式计算结果如按照上式计算结果如 右表所示右表所示000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa信息位a6 a5 a4 a3监督位a2 a1

30、a0信息位a6 a5 a4 a3监督位a2 a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111128p在接收端解码时，对于每个接收码组，先按式在接收端解码时，对于每个接收码组，先按式计算出校正子计算出校正子S1，S2和和S3，然后按照表，然后按照表判断错码的位置。判断错码的位置。 例：若接收码组为例：若接收码组为0000011，则按上三式计算得到：，则按上三式计算得到：S1 = 0，S2 = 1，S3 = 1。这样

31、，由上表可知，错码位置在。这样，由上表可知，错码位置在a3。正确的码组是正确的码组是000101124561aaaaS13562aaaaS03463aaaaSS1 S2 S3错码位置S1 S2 S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码29p上例中的汉明码是上例中的汉明码是(7, 4)码，其最小码距码，其最小码距d0 = 3。 由式由式 可知，此码能够检测可知，此码能够检测2个错码，或纠正个错码，或纠正1个错码。个错码。n汉明码的码率：汉明码的码率：当当r (或或n)很大时，上式趋近于很大时，上式趋近于1。所以汉明码是一种高效编。所以汉明码是

32、一种高效编码。码。10 ed120 td1212rrrnk30分组码的一般原理分组码的一般原理n线性分组码的监督位和信息位的关系线性分组码的监督位和信息位的关系 可以改写为可以改写为上式中，已经将上式中，已经将“ ”简写成简写成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa31n监督矩阵监督矩阵上式可以写成矩阵形式：上式可以写成矩阵形式： （模（模2） 将上式简写为将上式简写为HAT = 0T 或或AHT = 001001101001010110

33、0010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa0001011001110101011101000123456aaaaaaa32 HAT = 0T 式中，式中， 称为称为监督矩阵监督矩阵 n监督矩阵的性质监督矩阵的性质p监督矩阵监督矩阵H确定码组中的信息位和监督位的关系。确定码组中的信息位和监督位的关系。pH 的行数就是监督关系式的数目，即监督位数的行数就是监督关系式的数目，即监督位数 r 。pH 的每行中的每行中“1”的位置表示相应的码元参与监督关系。的位置表示相应的码元参与监督关系。p H 可以分成两部分，例如可以分成两部分，例如 典型监督

34、矩阵典型监督矩阵 式中，式中，P 为为r k阶矩阵，阶矩阵，Ir为为 r r 阶单位方阵。阶单位方阵。 101100111010101110100HrPIH001101101011011001110A = a6 a5 a4 a3 a2 a1 a0 0 = 00033pH 矩阵的各行应该是线性无关的，否则将得不到矩阵的各行应该是线性无关的，否则将得不到 r 个线个线性无关的监督关系式。性无关的监督关系式。p若一个矩阵能写成典型阵形式若一个矩阵能写成典型阵形式P Ir，则其各行一定是，则其各行一定是线性无关的。线性无关的。n生成矩阵生成矩阵p例：例： 可以写为可以写为上式两端分别转置后，可以变成上

35、式两端分别转置后，可以变成式中，式中，Q为为k r 阶矩阵，是阶矩阵，是P的转置，即的转置，即 Q = PT3456012101111011110aaaaaaa346035614562aaaaaaaaaaaaQ34563456012011101110111aaaaaaaaaaa34将将Q的左边加上一个的左边加上一个k阶单位方阵，称为生成矩阵：阶单位方阵，称为生成矩阵： 生成矩阵生成矩阵 G称为生成矩阵，因为可以用它产生整个码组称为生成矩阵，因为可以用它产生整个码组A，即有，即有p生成矩阵的性质生成矩阵的性质n具有IkQ形式的生成矩阵称为典型生成矩阵典型生成矩阵。n由典型生成矩阵得出的码组A中，

36、信息位的位置不变，监督位附加于其后。这种形式的码组称为系统系统码码。 n矩阵G的各行也必须是线性无关的。n如果已有k个线性无关的码组，则可以将其用来作为生成矩阵G，并由它生成其余码组。0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaA35n错误图样错误图样设：发送码组设：发送码组A是一个是一个n列的行矩阵：列的行矩阵：接收码组是一个接收码组是一个n列的行矩阵列的行矩阵B： 令接收码组和发送码组之差为令接收码组和发送码组之差为E就是错码的行矩阵就是错码的行矩阵 称为错误图样称为错误图样 式中，式中， (i = 0, 1, , n-

37、1)若若ei = 0，表示该码元未错；若，表示该码元未错；若ei = 1，表示该码元为错码。，表示该码元为错码。 0121aaaaAnn0121bbbbBnnB A = E (模2)0121eeeeEnniiiiiababe当当, 1, 036n校正子矩阵校正子矩阵 B A = E 可以改写成可以改写成 B = A + E上式表示发送码组上式表示发送码组A与错码矩阵与错码矩阵E之和等于接收码组之和等于接收码组B。 例如，例如， 若发送码组若发送码组A = 1 0 0 0 1 1 1， 错码矩阵错码矩阵E = 0 0 0 0 1 0 0， 则则 接收码组接收码组B = 1 0 0 0 0 1 1

38、。 在在接收端解码时接收端解码时，将接收码组，将接收码组B代入式代入式AHT = 0中中A的位置进行计算。若接收码组中无错码，则的位置进行计算。若接收码组中无错码，则B = A。代。代入后，该式仍成立，即有入后，该式仍成立，即有BH T = 0 （无错）（无错）只有当错码未超出检测能力时，上式才不成立。只有当错码未超出检测能力时，上式才不成立。 假设，这时该式的右端等于假设，这时该式的右端等于S，即有，即有BH T = S将将B = A + E 代入上式，得到代入上式，得到:S = (A + E) H T = AH T + EH T37S = (A + E) H T = AH T + EH T

39、上式右端第一项等于上式右端第一项等于0，所以，所以 S = EH T 校正子矩阵校正子矩阵当当H 确定后，上式中确定后，上式中S只与只与E 有关，而与有关，而与A 无关。无关。 这意味着，这意味着，S 和错码和错码E 之间有确定的线性变换关系。之间有确定的线性变换关系。 若若S 和和E 有一一对应关系，有一一对应关系，则则S 将能代表错码位置将能代表错码位置。例：例：38n线性码的封闭性：线性码的封闭性：若若A1和和A2是一种线性编码中的两个码组，是一种线性编码中的两个码组，则则(A1+A2)仍是其中一个码组仍是其中一个码组。 证若证若A1和和A2是两个码组，则有：是两个码组，则有：A1HT

40、= 0, A2HT = 0 将上两式相加，得出将上两式相加，得出A1HT + A2HT = (A1 + A2 ) HT = 0 所以所以(A1 + A2)也是一个码组。也是一个码组。 由于线性码具有封闭性，所以由于线性码具有封闭性，所以两个码组两个码组(A1和和A2)之间之间的距离（即对应位不同的数目）必定是另一个码组的距离（即对应位不同的数目）必定是另一个码组(A1 + A2)的重量（即的重量（即“1”的数目）。的数目）。因此，因此，码的最小距离就是码的码的最小距离就是码的最小重量最小重量（除全（除全“0”码组外）。码组外）。3910.6.1 循环码的概念：循环码的概念： 循环性是指任一码组

41、循环一位后仍然是该编码中的一个码组。循环性是指任一码组循环一位后仍然是该编码中的一个码组。例：一种例：一种(7, 3)循环码的全部码组如下循环码的全部码组如下 表中第表中第2码组向右移一位即得到第码组向右移一位即得到第5码组；第码组；第5码组向右移码组向右移一位即得到第一位即得到第7码组。码组。 码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111610111003010111071100101401110018111001040一般情况一般情况 若若(an-1 an-2 a0)是循环码的一个码组，则循

42、环移位后的码是循环码的一个码组，则循环移位后的码组：组： (an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2) (a0 an-1 a2 a1) 仍然是该编码中的码组。仍然是该编码中的码组。多项式表示法多项式表示法一个长度为一个长度为n的码组的码组(an-1 an-2 a0)可以表示成可以表示成 上式中上式中x 的值没有任何意义，仅用它的幂代表码元的位置。的值没有任何意义，仅用它的幂代表码元的位置。例例：码组：码组1 1 0 0 1 0 1可以表示为可以表示为 012211)(axaxaxaxTnnnn11010011)(25623456xxxxxxxxxxT4110

43、.6.2 循环码的运算循环码的运算 整数的按模运算整数的按模运算在整数运算中，有模在整数运算中，有模n运算。例如，在模运算。例如，在模2运算中，有运算中，有1 + 1 = 2 0 (模模2)， 1 + 2 = 3 1 (模模2)， 2 3 = 6 0 (模模2) 等等。等等。 一般说来，若一个一般说来，若一个整数整数m可以表示为可以表示为式中，式中，Q为整数，则为整数，则在模在模n运算下，有运算下，有m p (模模n) 所以，在模所以，在模n运算下，一个整数运算下，一个整数m等于它被等于它被n除得的余数。除得的余数。npnpQnm,42码多项式的按模运算码多项式的按模运算 若任意一个多项式若任

44、意一个多项式F(x)被一个被一个n次多项式次多项式N(x)除，得到商除，得到商式式Q(x)和一个次数小于和一个次数小于n的余式的余式R(x)，即，即则在按模则在按模N(x)运算下，有运算下，有这时，这时，码多项式系数仍按模码多项式系数仍按模2运算运算。 例例1：x3被被(x3 + 1)除，得到余项除，得到余项1，即，即 例例2：因为因为xx3 + 1 x4 +x2 + 1x4 + x x2 +x +1 在模在模2运算中加法和减法一样。运算中加法和减法一样。)()()()(xRxQxNxF）（模)()()(xNxRxF）（模)x(x1 133）（模) 1(113224xxxxx43循环码的数学表

45、示法循环码的数学表示法 在循环码中，设在循环码中，设T(x)是一个长度为是一个长度为n的码组，若的码组，若则则T (x)也是该编码中的一个码组。也是该编码中的一个码组。 证证 设一循环码为设一循环码为 （略）（略） 则有则有 上式中的上式中的T (x) 正是码组正是码组T (x)向左循环移位向左循环移位 i 次的结果。次的结果。例例： 一循环码为一循环码为1100101，即，即 若给定若给定 i = 3，则有，则有 上式对应的码组为上式对应的码组为0101110，它正是，它正是T(x)向左移向左移3位的结果。位的结果。结论：一个长为结论：一个长为n的循环码必定为按模的循环码必定为按模(xn +

46、 1)运算的一个余式运算的一个余式。 ）（模) 1()()(nixxTxTx012211)(axaxaxaxTnnnn)()(1102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni1)(256xxxxT）（模)x(xxxxxxxx)x(Tx172353589344循环码的生成循环码的生成 n有了生成矩阵有了生成矩阵G，就可以由，就可以由k个信息位得出整个码组：个信息位得出整个码组：例：例：式中，式中，生成矩阵生成矩阵G的每一行都是一个码组。的每一行都是一个码组。n因此，若能找到因此，若能找到 k 个已知的码组，就能构成矩阵

47、个已知的码组，就能构成矩阵G。如前。如前所述，这所述，这k个已知码组必须是线性不相关的。个已知码组必须是线性不相关的。n在循环码中，一个在循环码中，一个(n, k)码有码有2k个不同的码组。若个不同的码组。若用用g(x)表表示其中前示其中前(k-1)位皆为位皆为“0”的码组，则的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这都是码组，而且这k个码组是线性无关的。个码组是线性无关的。因因此它们可以用来构成此循环码的生成矩阵此它们可以用来构成此循环码的生成矩阵G。G34560123456aaaaaaaaaaaA01100011010010110010011110

48、00QGkI I45n在循环码中在循环码中除全除全“0”码组外，再没有连续码组外，再没有连续k位均为位均为“0”的码的码组组。否则，在经过若干次循环移位后将得到。否则，在经过若干次循环移位后将得到k位信息位全为位信息位全为“0”，但监督位不全为，但监督位不全为“0”的一个码组。这在线性码中显的一个码组。这在线性码中显然是不可能的。然是不可能的。n因此，因此，g(x)必须是一个常数项不为必须是一个常数项不为“0”的的(n - k)次多项式次多项式，而且这个而且这个g(x)还是这种还是这种(n, k)码中码中次数为次数为(n k)的唯一一个的唯一一个多项式。多项式。因为如果有两个，则由码的封闭性，

49、把这两个相因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续，即连续“0”的个数多于的个数多于(k 1)。显然，这是与前面的结。显然，这是与前面的结论矛盾的。论矛盾的。n我们我们称这唯一的称这唯一的(n k)次多项式次多项式g(x)为码的生成多项式为码的生成多项式。一。一旦确定了旦确定了g(x)，则整个，则整个(n, k)循环码就被确定了。循环码就被确定了。46n因此，因此，循环码的生成矩阵循环码的生成矩阵G可以写成可以写成n例：例：上表中的编码为上表中的编码为(7, 3)循环码，循环码，n

50、= 7, k = 3, n k = 4，其中唯一的一个其中唯一的一个(n k) = 4次码多项式代表的码组是第二码次码多项式代表的码组是第二码组组0010111，与它对应的码多项式，即生成多项式，为，与它对应的码多项式，即生成多项式，为g(x) = x4 + x2 + x + 1。 )()()()()(21xgxxgxgxxgxxkkG码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111610111003010111071100101401110018111001047g(x) = x4 + x2 +

51、x + 1 即即 “1 0 1 1 1”将此将此g(x)代入前面的矩阵，得到代入前面的矩阵，得到 或或上式不符合上式不符合G = IkQ形式，所以它不是典型生成矩阵。但形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。它经过线性变换后，不难化成典型阵。此此循环码组的多项式循环码组的多项式表示式表示式T(x)： 上式表明，上式表明，所有码多项式所有码多项式T(x)都能够被都能够被g(x)整除整除，而且，而且任意一个次数不大于任意一个次数不大于(k 1)的多项式乘的多项式乘g(x)都是码多项式。都是码多项式。 )()()()(2xgxxgxgxxG00101110101110101

52、1100)(xG)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG48寻求寻求码生成多项式码生成多项式 因为任意一个循环码因为任意一个循环码T(x)都是都是g(x)的倍式，故它可以写成的倍式，故它可以写成T(x) = h(x) g(x)而生成多项式而生成多项式g(x)本身也是一个码组，即有本身也是一个码组，即有 T (x) = g(x)由于码组由于码组T (x)是一个是一个(n k)次多项式，故次多项式，故xk T (x)是一个是一个n次次多项式。由多项式。由可知，可知，xk T (x)在模在模(xn

53、+ 1)运算下也是一个码组，所以有运算下也是一个码组，所以有上式左端分子和分母都是上式左端分子和分母都是n次多项式，故相除的商式次多项式，故相除的商式Q(x) = 1。因此，上式可以写成因此，上式可以写成）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk49将将 T(x) = h(x) g(x) 和和 T (x) = g(x) 代入代入化简后，得到化简后，得到上式表明，上式表明，生成多项式生成多项式g(x)应该是应该是(xn + 1)的一个因子的一个因子。例例：(x7 + 1)可以分解为可以分解为为了求出为了求出(7, 3)循环码的生

54、成多项式循环码的生成多项式 g(x)，需要从上式，需要从上式中找到一个中找到一个(n k) = 4次的因子。这样的因子有两个，即次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。以上两式都可以作为生成多项式。 选用的生成多项式不同，产生出的循环码码组也不同。选用的生成多项式不同，产生出的循环码码组也不同。 )() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx5010.6.3 循环码的编码方法循环码的编码方法用用xn-k乘乘m(x)。这一运算实际上是在信息码后附加上。

55、这一运算实际上是在信息码后附加上(n k)个个“0”。例如，信息码为。例如，信息码为110，它写成多项式为，它写成多项式为m(x) = x2 + x。当当n k = 7 3 =4时，时，xn-k m(x) = x4 (x2 +x) = x6 +x5，它表示，它表示码组码组1100000。用用g(x)除除xn-k m(x)，得到商，得到商Q(x)和余式和余式r(x)，即有，即有例：若选定例：若选定g(x) = x4 + x2 + x + 1，则有，则有 上式是用码多项式表示的运算。它和下式等效：上式是用码多项式表示的运算。它和下式等效：编出的码组编出的码组T(x)为：为：T(x) = xn-k

56、m(x) +r(x)在上例中，在上例中，T(x) = 1100000 + 101 = 1100101 )()()()()(xgxrxQxgxmxkn11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn101111011111011111000005110.6.4 循环码的解码方法循环码的解码方法在检错时：当在检错时：当接收码组没有错码时接收码组没有错码时，接收码组，接收码组R(x)必定能被必定能被g(x)整除，即下式整除，即下式中中余项余项r(x)应为零应为零；否则，有误码否则，有误码。n当接收码组中的错码数量过多，超出了编码的检错能力当接收码组中的错码数量过多，超出了编

57、码的检错能力时，有错码的接收码组也可能被时，有错码的接收码组也可能被g(x)整除。这时，错码就整除。这时，错码就不能检出了。不能检出了。 在纠错时：在纠错时：n用生成多项式用生成多项式g(x)除接收码组除接收码组R(x)，得出余式，得出余式r(x)。n按照余式按照余式r(x)，用查表的方法或计算方法得出错误图样用查表的方法或计算方法得出错误图样E(x)。n从从R(x)中减去中减去E(x)，便得到已经纠正错码的原发送码组，便得到已经纠正错码的原发送码组T(x)。)(/)()()(/)(xgxrxQxgxR5210.6.5 截短循环码截短循环码截短目的：截短目的： 在设计时，通常信息位数在设计时，

58、通常信息位数k、码长、码长n和纠错能力都是预先和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。给定的。但是，并不一定有恰好满足这些条件的循环码存在。故采用截短码长，得出满足要求的编码。故采用截短码长，得出满足要求的编码。截短方法截短方法： 一个给定的一个给定的(n, k)循环码，共有循环码，共有2k种码组，将其中前种码组，将其中前i (0 i k) 个信息位全为个信息位全为“0”的码组取出，它变成仅有的码组取出，它变成仅有2k-i种码组。种码组。然后删去这然后删去这 i 位全位全“0”的信息位，最终得到一个的信息位，最终得到一个 (n i，k i)的线性码。将这种码称为

59、截短循环码。的线性码。将这种码称为截短循环码。 截短循环码与截短前的循环码至少具有相同的纠错能力，并截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环码的编解码方法仍和截短前的方法一样。且截短循环码的编解码方法仍和截短前的方法一样。 例：要求构造一个能够纠正例：要求构造一个能够纠正1位错码的位错码的(13, 9)码。码。 这时可以由这时可以由(15, 11)循环码的循环码的211种码组中选出前两个信息种码组中选出前两个信息位均为位均为“0”的码组，构成一个新的码组集合。然后在发送时的码组，构成一个新的码组集合。然后在发送时不发送这两位不发送这两位“0”。于是发送码组成为。于是发送码

60、组成为(13, 9)截短循环码。截短循环码。 5310.6.6 BCH码码BCH码是能够纠正多个随机错码的循环码。码是能够纠正多个随机错码的循环码。 BCH码分为两类：本原码分为两类：本原BCH码和非本原码和非本原BCH码。码。 n本原本原BCH码：码长码：码长n = 2m 1 (m 3，任意正整数，任意正整数)，它的生，它的生成多项式成多项式g(x)中含有最高次数为中含有最高次数为m次的本原多项式；次的本原多项式；n非本原非本原BCH码：码长码：码长n是是(2m 1)的一个因子，它的生成多的一个因子，它的生成多项式项式g(x)中不含有最高次数为中不含有最高次数为m的本原多项式。的本原多项式。