通信原理教程10

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

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

3、：需要双向信道，传输效率也较低。n检错删除：检错删除：p在接收端发现错码后，立即将其删除。在接收端发现错码后，立即将其删除。p适用在发送码元中有大量多余度，删除部分接收码元不适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。影响应用之处。 2编码序列的参数编码序列的参数nn 编码序列中总码元数量编码序列中总码元数量nk 编码序列中信息码元数量编码序列中信息码元数量nr 编码序列中差错控制码元数量编码序列中差错控制码元数量 （差错控制码元，以后称为监督码元或监督位（差错控制码元，以后称为监督码元或监督位 ）nk/n 码率码率n(n - k) / k = r / k 冗余度冗余度3自动

4、要求重发自动要求重发(ARQ)系统系统n停止等待停止等待ARQ系统系统 n拉后拉后ARQ系统系统 停止等待ARQ系统接收数据ACKACKNAKACKACKNAKACK1233455t发送数据12334556t有错码组有错码组拉后ARQ系统214365798接收数据有错码组有错码组910 1110 11 12576ACK1NAK5NAK9ACK55769521436798发送数据10 1110 11 12重发码组重发码组4n选择重发选择重发ARQ系统系统 nARQ和前向纠错比较：和前向纠错比较：p优点优点n监督码元较少，即码率较高 n检错的计算复杂度较低n能适应不同特性的信道 p缺点缺点n需要双

5、向信道。n不适用于一点到多点的通信系统或广播系统。n传输效率降低，可能因反复重发而造成事实上的通信中断。 选择重发ARQ系统9接收数据有错码组有错码组214365759810 11131412发送数据9958521436710 1113 1412重发码组重发码组NAK9ACK1NAK5ACK5ACK95分组码举例分组码举例n设：有一种由设：有一种由3个二进制码元构成的编码，它共有个二进制码元构成的编码，它共有23 = 8种种不同的可能码组：不同的可能码组：000 晴晴 001 云云 010 阴阴 011 雨雨100 雪雪 101 霜霜 110 雾雾 111 雹雹 这时，若一个码组中发生错码，则

6、将收到错误信息。这时，若一个码组中发生错码，则将收到错误信息。 n若在此若在此8种码组中仅允许使用种码组中仅允许使用4种来传送天气，例如：令种来传送天气，例如：令000 晴晴 011 云云 101 阴阴 110 雨雨 为为许用码组许用码组，其他，其他4种不允许使用，称为种不允许使用，称为禁用码组禁用码组。 这时，接收端有可能发现（检测到）码组中的一个错码。这时，接收端有可能发现（检测到）码组中的一个错码。p这种编码只能检测错码，不能纠正错码。这种编码只能检测错码，不能纠正错码。 n若规定只许用两个码组：例如若规定只许用两个码组：例如000 晴晴 111 雨雨就能检测两个以下错码，或纠正一个错码

7、。就能检测两个以下错码，或纠正一个错码。 6分组码概念分组码概念n分组码分组码 信息位信息位 监督位监督位n分组码符号：分组码符号：(n, k) 其中，其中，n 码组总长度，码组总长度， k 信息码元数目。信息码元数目。 r = n k 监督码元数目。监督码元数目。右表中的码组为右表中的码组为(3, 2)码。码。 n分组码的一般结构：分组码的一般结构：n分组码的参数：分组码的参数：p码重：码组内码重：码组内“1”的个数的个数p码距：两码组中对应位取值不同的位数，又称汉明距离码距：两码组中对应位取值不同的位数，又称汉明距离 p最小码距最小码距(d0) ：各码组间的最小距离：各码组间的最小距离k个

8、信息位r个监督位an-1an-2.arar-1an-2.a0t码长 n = k + r分组码的结构7n码距的几何意义：以码距的几何意义：以n = 3的编码为例的编码为例 n一般而言，码距是一般而言，码距是 n 维空间中单位正多面体顶点之间的汉维空间中单位正多面体顶点之间的汉明距离。明距离。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a18n一种编码的纠检错能力：决定于最小码距一种编码的纠检错能力：决定于最小码距d0的值。的值。 p为了能检测为了能检测e个错码，要求最小码距个错码，要求最小码距p为了能纠正为了能纠正 t

9、个错码，要求最小码距个错码，要求最小码距 10 ed0123BA汉明距离ed0码距等于3的两个码组120 tdBtA汉明距离012345td0码距等于5的两个码组9p为了能纠正为了能纠正t个错码，同时检测个错码，同时检测e个错码，要求最小码距个错码，要求最小码距纠检结合工作方式：纠检结合工作方式：n当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；n当错码数量多时，系统按反馈重发的纠错方式工作，以降低系统的总误码率。 AB1tt汉明距离e码距等于(e+t+1)的两个码组)(10teted1010.3.1 误码率性能和带宽的关系误码率性能和带宽的关系 采用编码降低误码率采用编

10、码降低误码率所付出的代价是带宽的增大。所付出的代价是带宽的增大。10-610-510-410-310-210-1编码后Eb/n0 (dB)编码和误码率关系PeCDEAB2PSK1110.3.2 功率和带宽的关系功率和带宽的关系采用编码以采用编码以节省功率，并保持节省功率，并保持误码率不变，付出的代价也是误码率不变，付出的代价也是带宽带宽增大增大。 10-610-510-410-310-210-1编码后Eb/n0 (dB)编码和误码率关系PeCDEAB2PSK12对于给定的传输系统，其传输速率和对于给定的传输系统，其传输速率和Eb/n0的关系：的关系：式中，式中，RB 码元速率。码元速率。 提高

11、传输速率，采用编提高传输速率，采用编码以保持误码率不变；付出码以保持误码率不变；付出的代价仍是带宽增大。的代价仍是带宽增大。BsssbRnPTnPnTPnE0000)/1 (10-610-510-410-310-210-1编码后Eb/n0 (dB)编码和误码率关系PeCDEAB2PSK1310.3.4 编码增益编码增益定义：在保持误码率恒定条件下，采用纠错编码所节省的信定义：在保持误码率恒定条件下，采用纠错编码所节省的信 噪比噪比Eb/n0称为编码增益：称为编码增益： 式中，式中，(Eb/n0)u 未编码时的信噪比未编码时的信噪比(dB)； (Eb/n0)c 编码后所需的信噪比编码后所需的信噪

12、比(dB)。)(/00dBnEnEGcbubdB14奇偶监督码奇偶监督码 分为奇数监督码和偶数监督码两类。分为奇数监督码和偶数监督码两类。在奇偶监督码中，监督位只有在奇偶监督码中，监督位只有1位，故码率等于位，故码率等于k/(k+1)。偶数监督码中，此监督位使码组中偶数监督码中，此监督位使码组中“1”的个数为偶数：的个数为偶数：式中，式中，a0为监督位，其他位为信息位。为监督位，其他位为信息位。奇数监督码中，此监督位使码组中奇数监督码中，此监督位使码组中“1”的个数为奇数：的个数为奇数：0021aaann1021aaann15检错能力检错能力 能够检测奇数个错码。能够检测奇数个错码。 n设：码

13、组长度为设：码组长度为n， 码组中各个错码的发生是独立的和等概率的，码组中各个错码的发生是独立的和等概率的， 则在一个码组中出现则在一个码组中出现 j 个错码的概率为个错码的概率为 式中，式中， 为在为在n个码元中有个码元中有j个错码的组合数。个错码的组合数。n奇偶监督码不能检测码组中出现的偶数个错码，所以在一奇偶监督码不能检测码组中出现的偶数个错码，所以在一个码组中有错码而不能检测的概率等于个码组中有错码而不能检测的概率等于: 当当n为偶数时为偶数时 当当n为奇数时为奇数时 jnjnjppCnjP)1 (),()!( !jnjnCnj2/1222)1 (njjnjnjuppCP2/ )1(1

14、222)1 (njjnjnjuppCP16n例例 右表中的编码是偶数监督码。右表中的编码是偶数监督码。设信道的误码率为设信道的误码率为10-4，错码的出，错码的出现是独立的。试计算其不能检测现是独立的。试计算其不能检测的误码率。的误码率。将给定条件代入式将给定条件代入式计算得出计算得出由计算结果可见，此编码可以将误码率从由计算结果可见，此编码可以将误码率从10-4降低到降低到10-8量量级。效果非常明显。级。效果非常明显。2/1222)1 (njjnjnjuppCP82443242204442242212424210666126)1 (6)1 ()1 ()1 (ppppppppppCppCpp

15、CPjjjju1711na12na11a10a21na22na21a20amna1mna2ma1ma01nc2nc1c0c10.4.2 二维奇偶监督码二维奇偶监督码n码率等于码率等于n有可能检测偶数个错码有可能检测偶数个错码n适合检测突发错码适合检测突发错码 n能够纠正部分错码能够纠正部分错码 nmnmnk)1()1(18基本概念基本概念n代数码代数码 利用代数关系式产生监督位的编码利用代数关系式产生监督位的编码n线性分组码线性分组码 代数码的一种，其代数码的一种，其 监督位和信息位的关系由线性代数方程决定监督位和信息位的关系由线性代数方程决定n汉明码汉明码 一种能够纠正一个错码的线性分组码一

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

17、校正子的可能取值有4种组合，种组合，即即00，01，10，11，故能表示，故能表示4种不同的信息。若用其中一种不同的信息。若用其中一种组合表示无错码，则还有其他种组合表示无错码，则还有其他3种组合可以用于指明一个种组合可以用于指明一个错码的错码的3种不同位置。种不同位置。 从而可以有纠错能力。从而可以有纠错能力。n一般而言，若有一般而言，若有 r 个监督关系式，则个监督关系式，则 r 个校正子可以指明个校正子可以指明一个错码的一个错码的 (2r 1) 个不同位置。个不同位置。 n当校正子可以指明的错码位置数目等于或大于码组长度当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组

18、中任何一个位置上的错码，即要求时，才能够纠正码组中任何一个位置上的错码，即要求021aaaSnn1212rknrr或20汉明码汉明码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表示校表示校正子，则这正子，则这3个校正子恰好能够指明个校正子恰好能够指明23 1 = 7个错码的

19、个错码的位置。位置。p若规定校正子和错码位置的关系如下表，则仅当在若规定校正子和错码位置的关系如下表，则仅当在a6 a5 a4 a2位置上有错码时，校正子位置上有错码时，校正子S1的值才等于的值才等于1；否则；否则S1的值为零。这就意味着的值为零。这就意味着a6 a5 a4 a2四个码元构成偶数监督四个码元构成偶数监督关系：关系：p同理，有同理，有1212rknrr或24561aaaaS13562aaaaS03463aaaaS21p在编码时，信息位在编码时，信息位a6 a5 a4 a3的值决定于输入信号，它们的值决定于输入信号，它们是随机的。监督位是随机的。监督位a2 a1 a0是按监督关系确

20、定的，应该保是按监督关系确定的，应该保证上列证上列3式中的校正子等于式中的校正子等于0，即有，即有给定信息位后，为了给定信息位后，为了计算监督位，上式可计算监督位，上式可以改写为以改写为按照上式计算结果为按照上式计算结果为000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa22p在接收端解码时，对于每个接收码组，先按式在接收端解码时，对于每个接收码组，先按式计算出校正子计算出校正子S1，S2和和S3，然后按照表，然后按照表判断错码的位置。判断错码的位置。 例：若接收码组为例：若接收码组为0000011，则按上三式计算得到：，则按上三式计算得到：

21、S1 = 0，S2 = 1，S3 = 1。这样，由上表可知，错码位置在。这样，由上表可知，错码位置在a3。24561aaaaS13562aaaaS03463aaaaS23p上例中的汉明码是上例中的汉明码是(7, 4)码，其最小码距码，其最小码距d0 = 3。p由式由式p可知，此码能够检测可知，此码能够检测2个错码，或纠正个错码，或纠正1个错码。个错码。n汉明码的码率：汉明码的码率：当当r (或或n)很大时，上式趋近于很大时，上式趋近于1。所以汉明码是一种高效编。所以汉明码是一种高效编码。码。10 ed120 td1212rrrnk24分组码的一般原理分组码的一般原理n线性分组码的监督位和信息位

22、的关系线性分组码的监督位和信息位的关系 可以改写为可以改写为上式中，已经将上式中，已经将“ ”简写成简写成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa25n监督矩阵监督矩阵上式可以写成矩阵形式：上式可以写成矩阵形式： （模（模2） 将上式简写为将上式简写为HAT = 0T 或或AHT = 0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa000101100111

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

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

25、101111011110aaaaaaa346035614562aaaaaaaaaaaaQ34563456012011101110111aaaaaaaaaaa28将将Q的左边加上一个的左边加上一个k阶单位方阵，称为生成矩阵：阶单位方阵，称为生成矩阵： 生成矩阵生成矩阵 G称为生成矩阵，因为可以用它产生整个码组称为生成矩阵，因为可以用它产生整个码组A，即有，即有p生成矩阵的性质生成矩阵的性质n具有IkQ形式的生成矩阵称为典型生成矩阵典型生成矩阵。n由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码组称为系统系统码码。 n矩阵G的各行也必须是线性无关的。n如果已有k个线性

26、无关的码组，则可以将其用来作为生成矩阵G，并由它生成其余码组。0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaA29n错误图样错误图样设：发送码组设：发送码组A是一个是一个n列的行矩阵：列的行矩阵：接收码组是一个接收码组是一个n列的行矩阵列的行矩阵B： 令接收码组和发送码组之差为令接收码组和发送码组之差为E就是错码的行矩阵就是错码的行矩阵 称为错误图样称为错误图样 式中，式中， (i = 0, 1, , n-1)若若ei = 0，表示该码元未错；若，表示该码元未错；若ei = 1，表示该码元为错码。，表示该码元为错码。 0121

27、aaaaAnn0121bbbbBnnB A = E (模2)0121eeeeEnniiiiiababe当当, 1, 030n校正子矩阵校正子矩阵 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。 在接收端解码时，将接收码组在接收端解码时，将接收码组B代入式代入式AHT = 0中中A的位置进行计算。若接收码组中无错

28、码，则的位置进行计算。若接收码组中无错码，则B = A。代。代入后，该式仍成立，即有入后，该式仍成立，即有BH T = 0只有当错码未超出检测能力时，上式才不成立。只有当错码未超出检测能力时，上式才不成立。 假设，这时该式的右端等于假设，这时该式的右端等于S，即有，即有BH T = S将将B = A + E 代入上式，得到代入上式，得到:S = (A + E) H T = AH T + EH T31S = (A + E) H T = AH T + EH T上式右端第一项等于上式右端第一项等于0，所以，所以 S = EH T 校正子矩阵校正子矩阵当当H 确定后，上式中确定后，上式中S只与只与E

29、有关，而与有关，而与A 无关。无关。 这意味着，这意味着，S 和错码和错码E 之间有确定的线性变换关系。之间有确定的线性变换关系。 若若S 和和E 有一一对应关系，则有一一对应关系，则S 将能代表错码位置。将能代表错码位置。n线性码的封闭性：若线性码的封闭性：若A1和和A2是一种线性码中的两个码组，是一种线性码中的两个码组，则则(A1+A2)仍是其中一个码组。仍是其中一个码组。 证证若若A1和和A2是两个码组，则有：是两个码组，则有：A1HT = 0, A2HT = 0 将上两式相加，得出将上两式相加，得出A1HT + A2HT = (A1 + A2 ) HT = 0 所以所以(A1 + A2

30、)也是一个码组。也是一个码组。 由于线性码具有封闭性，所以两个码组由于线性码具有封闭性，所以两个码组(A1和和A2)之间之间的距离（即对应位不同的数目）必定是另一个码组的距离（即对应位不同的数目）必定是另一个码组(A1 + A2)的重量（即的重量（即“1”的数目）。因此，码的最小距离就是码的的数目）。因此，码的最小距离就是码的最小重量（除全最小重量（除全“0”码组外）。码组外）。32例：一种例：一种(7, 3)循环码的全部码组如下循环码的全部码组如下 表中第表中第2码组向右移一位即得到第码组向右移一位即得到第5码组；第码组；第5码组向右移码组向右移一位即得到第一位即得到第7码组。码组。 33一

31、般情况一般情况 若若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码是循环码的一个码组，则循环移位后的码组：组： (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)(axaxaxaxTn

32、nnn11010011)(25623456xxxxxxxxxxT3410.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除得的余数。除得的余数。npn

33、pQnm,35码多项式的按模运算码多项式的按模运算 若任意一个多项式若任意一个多项式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）（

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

35、结论：一个长为n的循环码必定为按模的循环码必定为按模(xn + 1)运算的一个余式。运算的一个余式。 ）（模) 1()()(nixxTxTx012211)(axaxaxaxTnnnn)()(1102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni1)(256xxxxT）（模) 1()(723535893xxxxxxxxxxTx37循环码的生成循环码的生成 n有了生成矩阵有了生成矩阵G，就可以由，就可以由k个信息位得出整个码组：个信息位得出整个码组：例：例：式中，式中，生成矩阵生成矩阵G的每一行都是一个码组。的每一行都是一个码

36、组。n因此，若能找到因此，若能找到 k 个已知的码组，就能构成矩阵个已知的码组，就能构成矩阵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。G34560123456aaaaa

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

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

39、例：例：上表中的编码为上表中的编码为(7, 3)循环码，循环码，n = 7, k = 3, n k = 4，其中唯一的一个其中唯一的一个(n k) = 4次码多项式代表的码组是第二码次码多项式代表的码组是第二码组组0010111，与它对应的码多项式，即生成多项式，为，与它对应的码多项式，即生成多项式，为g(x) = x4 + x2 + x + 1。 )()()()()(21xgxxgxgxxgxxkkG40g(x) = x4 + x2 + x + 1 即即 “1 0 1 1 1”将此将此g(x)代入上矩阵，得到代入上矩阵，得到 或或上式不符合上式不符合G = IkQ形式，所以它不是典型生成矩阵

40、。但形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。它经过线性变换后，不难化成典型阵。此循环码组的多项式表示式此循环码组的多项式表示式T(x)： 上式表明，所有码多项式上式表明，所有码多项式T(x)都能够被都能够被g(x)整除，而且整除，而且任意一个次数不大于任意一个次数不大于(k 1)的多项式乘的多项式乘g(x)都是码多项式。都是码多项式。 )()()()(2xgxxgxgxxG001011101011101011100)(xG)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG41寻

41、求码生成多项式寻求码生成多项式 因为任意一个循环码因为任意一个循环码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 + 1)运算下也是一个码组，所以有运算下也是一个码组，所以有上式左端分子和分母都是上式左端分子和分母都是n次多项式，故相除的商式次多项式，故相除的商式Q(x) =

42、1。因此，上式可以写成因此，上式可以写成）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk42将将 T(x) = h(x) g(x) 和和 T (x) = g(x) 代入代入化简后，得到化简后，得到上式表明，生成多项式上式表明，生成多项式g(x)应该是应该是(xn + 1)的一个因子。的一个因子。例：例：(x7 + 1)可以分解为可以分解为为了求出为了求出(7, 3)循环码的生成多项式循环码的生成多项式 g(x)，需要从上式，需要从上式中找到一个中找到一个(n k) = 4次的因子。这样的因子有两个，即次的因子。这样的因子有两个，即以

43、上两式都可以作为生成多项式。以上两式都可以作为生成多项式。 选用的生成多项式不同，产生出的循环码码组也不同。选用的生成多项式不同，产生出的循环码码组也不同。 )() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx4310.6.3 循环码的编码方法循环码的编码方法用用xn-k乘乘m(x)。这一运算实际上是在信息码后附加上。这一运算实际上是在信息码后附加上(n k)个个“0”。例如，信息码为。例如，信息码为110，它写成多项式为，它写成多项式为m(x) = x2 + x。当当n k

44、 = 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 m(x) +r(x)在上例中，在上例中，T(x) = 1100000 + 101 = 1100101 )()()()()(xgxrxQxgxmxkn11) 1(

45、1)()(24222456xxxxxxxxxxxxgxmxkn1011110111110111110000044在检错时：当接收码组没有错码时，接收码组在检错时：当接收码组没有错码时，接收码组R(x)必定能被必定能被g(x)整除，即下式整除，即下式中余项中余项r(x)应为零；否则，有误码。应为零；否则，有误码。n当接收码组中的错码数量过多，超出了编码的检错能力当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被时，有错码的接收码组也可能被g(x)整除。这时，错码就整除。这时，错码就不能检出了。不能检出了。 在纠错时：在纠错时：n用生成多项式用生成多项式g(x)除接收码组

46、除接收码组R(x)，得出余式，得出余式r(x)。n按照余式按照余式r(x)，用查表的方法或计算方法得出错误图样，用查表的方法或计算方法得出错误图样E(x)。n从从R(x)中减去中减去E(x)，便得到已经纠正错码的原发送码组，便得到已经纠正错码的原发送码组T(x)。)(/)()()(/)(xgxrxQxgxR)(/ )()()(/ )(xgxrxQxgxR4510.6.5 截短循环码截短循环码截短目的：截短目的： 在设计时，通常信息位数在设计时，通常信息位数k、码长、码长n和纠错能力都是预先和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。给定的。但是，并不一定有恰好满足这

47、些条件的循环码存在。故采用截短码长截短，得出满足要求的编码。故采用截短码长截短，得出满足要求的编码。截短方法：截短方法： 设给定一个设给定一个(n, k)循环码，它共有循环码，它共有2k种码组，现使其前种码组，现使其前i (0 i k)个信息位全为个信息位全为“0”，于是它变成仅有，于是它变成仅有2k-i种码组。然后种码组。然后从中删去这从中删去这 i 位全位全“0”的信息位，最终得到一个的信息位，最终得到一个 (n i，k i)的线性码。将这种码称为截短循环码。的线性码。将这种码称为截短循环码。 截短循环码与截短前的循环码至少具有相同的纠错能力，并截短循环码与截短前的循环码至少具有相同的纠错

48、能力，并且截短循环码的编解码方法仍和截短前的方法一样。且截短循环码的编解码方法仍和截短前的方法一样。 例：要求构造一个能够纠正例：要求构造一个能够纠正1位错码的位错码的(13, 9)码。码。 这时可以由这时可以由(15, 11)循环码的循环码的11种码组中选出前两信息位种码组中选出前两信息位均为均为“0”的码组，构成一个新的码组集合。然后在发送时不的码组，构成一个新的码组集合。然后在发送时不发送这两位发送这两位“0”。于是发送码组成为。于是发送码组成为(13, 9)截短循环码。截短循环码。 4610.6.6 BCH码码BCH码是能够纠正多个随机错码的循环码。码是能够纠正多个随机错码的循环码。

49、BCH码分为两类：本原码分为两类：本原BCH码和非本原码和非本原BCH码。码。 n本原本原BCH码：码长码：码长n = 2m 1 (m 3，任意正整数，任意正整数)，它的生，它的生成多项式成多项式g(x)中含有最高次数为中含有最高次数为m次的本原多项式；次的本原多项式；n非本原非本原BCH码：码长码：码长n是是(2m 1)的一个因子，它的生成多的一个因子，它的生成多项式项式g(x)中不含有最高次数为中不含有最高次数为m的本原多项式。的本原多项式。BCH码的工程设计：可以用查表法找到所需的生成多项式。码的工程设计：可以用查表法找到所需的生成多项式。例：二进制非本原例：二进制非本原BCH码的生成多

50、项式系数码的生成多项式系数 表中表中g(x)是用是用8进制数字表示的；进制数字表示的；t 为纠错能力。为纠错能力。47常用常用BCH码：码：n戈莱戈莱(Golay)码：码： (23, 12)非本原非本原BCH码，它能纠正码，它能纠正3个随机个随机错码，并且容易解码错码，并且容易解码 。n扩展扩展BCH码码(n + 1, k) ：pBCH码的长度为奇数。在应用中，为了得到偶数长度码的长度为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在的码，并增大检错能力，可以在BCH码生成多项式中码生成多项式中乘上一个因式乘上一个因式(x + 1)，从而得到扩展，从而得到扩展BCH码码(n + 1

51、, k)。 p扩展扩展BCH码已经不再具有循环性。码已经不再具有循环性。 n扩展戈莱码扩展戈莱码(24, 12)：其最小码距为：其最小码距为8，码率为，码率为1/2，能够纠，能够纠正正3个错码和检测个错码和检测4个错码。个错码。 48几种二进制分组码的性能比较几种二进制分组码的性能比较 2PSK汉明码(7, 4) t=1 汉明码(31, 26) t=1扩展戈莱码(24, 12) t=3BCH码(127, 64) t=10Eb / n0 (dB)Pe4910.6.7 RS码码RS码：是码：是q进制进制BCH码的一个特殊子类，并且具有很强的纠码的一个特殊子类，并且具有很强的纠错能力。错能力。RS码

52、的参数：码长码的参数：码长n = q 1，监督位数目，监督位数目r = 2t，其中，其中t是能够是能够纠正的错码数目；其生成多项式为纠正的错码数目；其生成多项式为g(x) = (x + )(x + 2) (x + 2t)式中，式中， 为伽罗华域为伽罗华域GF(2m)中的本原元。中的本原元。 RS码的主要优点：码的主要优点：n它是多进制纠错编码，所以特别适合用于多进制调制的场它是多进制纠错编码，所以特别适合用于多进制调制的场合；合；n它能够纠正它能够纠正t个个q位二进制错码，即能够纠正不超过位二进制错码，即能够纠正不超过q个连续个连续的二进制错码，所以适合在衰落信道中纠正突发性错码。的二进制错码

53、，所以适合在衰落信道中纠正突发性错码。5010.7 卷积码卷积码卷积码的特点：卷积码的特点：n监督码元不仅和当前的监督码元不仅和当前的k比特信息段有关，而且还同前面比特信息段有关，而且还同前面m = (N 1)个信息段有关。个信息段有关。n将将N称为码组的约束长度。称为码组的约束长度。n将卷积码记作将卷积码记作(n, k, m)，其码率为，其码率为k/n。51卷积码的编码卷积码的编码n一般原理方框图一般原理方框图编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周52n卷积码编码器的实例方框图：卷积码编码器的实例方框图：(n, k,

54、m) =（3, 1, 2）p每当输入每当输入1比特时，此编码器输出比特时，此编码器输出3比特比特c1c2 c3：p编码器的工作状态编码器的工作状态 123b3b1输入b2编码输出c2c1c3321331211bbbcbbcbc53000111001110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110c1c2c3信息位 1 1 0 1ba起点信息位000111c1c2c3abcdabcdabcdabcd上半部下半部10a状态 b3b2 a 0 0 b 0 1 c 1 0 d

55、1 1abcdabcdcdab01100110.7.2 卷积码的解码卷积码的解码码树搜索法：码树搜索法：(3, 1, 2)卷积码的码树图卷积码的码树图此法不实用：因为随信息位增多，分支数目按指数规律增长此法不实用：因为随信息位增多，分支数目按指数规律增长54状态图和网格图状态图和网格图n移存器状态和输入输出码元的关系移存器状态和输入输出码元的关系n状态图状态图321331211bbbcbbcbc123b3b1输入b2编码输出c2c1c3abcd00011110111001001110000155n(3, 1, 2)卷积码网格图卷积码网格图n网格图中的编码路径举例网格图中的编码路径举例p输入信息

56、位为输入信息位为1101时时p输出编码序列是：输出编码序列是：111 110 010 100 011 110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100abcd000111101110010011100001abcdabcd11001000111110056维特比算法维特比算法n基本原理：将接收到的序列和所有可能的发送序列作比较，基本原理：将接收到的序列和所有可能的发送序列作比较，选择其中汉明距离最小的序列当作是现在的发送序列选择其中汉明距离最小的序

57、列当作是现在的发送序列n例：设卷积码为例：设卷积码为(n, k, m) = (3, 1, 2)码码p 现在的发送信息位为现在的发送信息位为1101p为了使移存器中的信息位全部移出，在信息位后面加入为了使移存器中的信息位全部移出，在信息位后面加入了了3个个“0”，即，即1101000p编码后的发送序列：编码后的发送序列：111 110 010 100 001 011 000p接收序列：接收序列：111 010 010 110 001 011 000 (红色为错码)n由于这是一个由于这是一个 (3, 1, 2)卷积码，发送序列的约束长度为卷积码，发送序列的约束长度为N = m + 1 3，所以首先

58、需考察，所以首先需考察3个信息段，即考察个信息段，即考察3n 9比比特，即接收序列前特，即接收序列前9位位“111 010 010”。 57n解码第解码第1步步p由网格图可见，沿路径每一级有由网格图可见，沿路径每一级有4种状态种状态a, b, c和和d。每。每种状态只有两条路径可以到达。故种状态只有两条路径可以到达。故4种状态共有种状态共有8条到达条到达路径。路径。p比较网格图中的这比较网格图中的这8条路径和接收序列之间的汉明距离。条路径和接收序列之间的汉明距离。例如，由出发点状态例如，由出发点状态a经过经过3级路径后到达状态级路径后到达状态a的两条的两条路径中上面一条为路径中上面一条为“00

59、0 000 000”。它和接收序列。它和接收序列“111 010 010”的汉明距离等于的汉明距离等于5；下面一条为；下面一条为“111 001 011”,它和接收序列的汉明距离等于它和接收序列的汉明距离等于3。 110110110110011011011010010010101101101001001001001abcdabcd00000000000000011111111111111110010010058p将这将这8个比较结果列表如下：个比较结果列表如下：p比较到达每个状态的两条路径的汉明距离，将距离小的比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就

60、剩下一条路径保留，称为幸存路径。这样，就剩下4条路径条路径了，即表中第了，即表中第2, 4, 6和和8条路径。条路径。 59n解码第解码第2步：继续考察接收序列中的后继步：继续考察接收序列中的后继3个比特个比特“110” p计算计算4条幸存路径上增加条幸存路径上增加1级后的级后的8条可能路径的汉明距条可能路径的汉明距离。计算结果列于下表中。离。计算结果列于下表中。 p表中总距离最小为表中总距离最小为2，其路径是，其路径是abdc+b，相应序列为，相应序列为111 110 010 100。它和发送序列相同，故对应发送信息。它和发送序列相同，故对应发送信息位位1101。 序号路径原幸存路径的距离新