通信原理--第十章

1、1信道编码：信道编码：n目的：提高信号传输的可靠性。目的：提高信号传输的可靠性。n方法：方法：增加多余比特，以发现或纠正错误。增加多余比特，以发现或纠正错误。 产生错码的原因：产生错码的原因：n乘性干扰引起的码间串扰乘性干扰引起的码间串扰n加性干扰引起的信噪比降低加性干扰引起的信噪比降低 错码分类：错码分类：n随机错误：错码随机出现，例如由白噪声引起的错码随机错误：错码随机出现，例如由白噪声引起的错码 n突发错误：错码相对集中地出现，例如由脉冲干扰引起的突发错误：错码相对集中地出现，例如由脉冲干扰引起的错码。错码。 2差错控制差错控制n一切纠正错误手段一切纠正错误手段差错控制技术的种类：差错控

2、制技术的种类：n检错检错重发：重发：p发现错码，但是不能纠正错码。要求发送端重新发送。发现错码，但是不能纠正错码。要求发送端重新发送。 n前向前向纠错纠错(FEC)：p利用加入的差错控制码元，不但能够发现错码，还能纠利用加入的差错控制码元，不但能够发现错码，还能纠正错码。正错码。n 反馈校验：反馈校验：p将收到的码元转发回发送端，将它和原发送码元比较。将收到的码元转发回发送端，将它和原发送码元比较。n检错删除：检错删除：p在接收端发现错码后，立即将其删除。在接收端发现错码后，立即将其删除。3自动要求重发自动要求重发(ARQ)系统系统-检错重发机制检错重发机制n停止等待停止等待ARQn拉后拉后A

3、RQ 停止等待停止等待ARQ系统系统接收数据接收数据ACKACKNAKACKACKNAKACK1233455t发送数据发送数据12334556t有错码组有错码组有错码组有错码组拉后拉后ARQ系统系统214365798接收数据接收数据有错码组有错码组有错码组有错码组910 1110 11 12576ACK1NAK5NAK9ACK55769521436798发送数据发送数据10 1110 11 12重发码组重发码组重发码组重发码组4n选择重发选择重发ARQ系统系统 选择重发选择重发ARQ系统系统9接收数据接收数据有错码组有错码组有错码组有错码组214365759810 11131412发送数据发送

4、数据9958521436710 1113 1412重发码组重发码组重发码组重发码组NAK9ACK1NAK5ACK5ACK95举例举例n3个二进制码，可表示个二进制码，可表示23 = 8种信息：种信息：000 晴晴 001 云云 010 阴阴 011 雨雨100 雪雪 101 霜霜 110 雾雾 111 雹雹 这时，若传送过程中发生错码，将无从判断对错。这时，若传送过程中发生错码，将无从判断对错。 n若仅允许使用其中若仅允许使用其中4种（种（许用码组许用码组）：）：000 晴晴 011 雨雨 101 霜霜 110 雾雾 这时，接收端可发现（检测到）码组中的一个错码。这时，接收端可发现（检测到）码

5、组中的一个错码。p但只能检测错码，不能纠正错码。但只能检测错码，不能纠正错码。 n若规定只许用两个码组：若规定只许用两个码组：000 晴晴 111 雹雹就能检测两个以下错码，或纠正一个错码。就能检测两个以下错码，或纠正一个错码。 6n码距码距p两码组中两码组中对应位取值不同对应位取值不同的位数，又称汉明距离的位数，又称汉明距离 p最小码距最小码距(d0) ：各码组间的最小距离：各码组间的最小距离n码距的几何意义：以码距的几何意义：以n = 3的编码为例的编码为例 p码距是码距是 n 维空间中单位正多面体顶点之间的汉明距离。维空间中单位正多面体顶点之间的汉明距离。p前例的码距分析前例的码距分析(

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

7、距个错码，要求最小码距纠检结合：纠检结合：n纠错需要更多的冗余度。纠错需要更多的冗余度。n当错码数量少时，系统按前向纠错方式工作，以节省重发当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；时间，提高传输效率；n当错码数量多时，系统按反馈重发的纠错方式工作，以降当错码数量多时，系统按反馈重发的纠错方式工作，以降低系统的总误码率。低系统的总误码率。 AB1tt汉明距离汉明距离e码距等于码距等于(e+t+1)的两个码组的两个码组)(10teted9分组码分组码n分组码分组码 信息位信息位 监督位监督位n分组码符号：分组码符号：(n, k) 其中，其中，n 码组总长度，码组总长度

8、， k 信息码元数目。信息码元数目。 r = n k 监督码元数目。监督码元数目。nk/n 码率码率n(n - k) / k = r / k 冗余度冗余度n一般结构：一般结构：p码重：码组内码重：码组内“1”的个数的个数信息位信息位监督位监督位晴晴000云云011阴阴101雨雨110k个信息位个信息位r个监督位个监督位an-1an-2.arar-1an-2.a0t码长码长 n = k + r1010.3.1 误码率和带宽的关系误码率和带宽的关系在不增加发送功率的前提下，采用在不增加发送功率的前提下，采用编码降低了误码率，编码降低了误码率，所付出的代价是带宽的增大。所付出的代价是带宽的增大。 有

9、效性换取可靠性有效性换取可靠性10-610-510-410-310-210-1编码后编码后Eb/n0 (dB)编码和误码率关系编码和误码率关系Pe CDE A B2PSK1110.3.2 功率和带宽的关系功率和带宽的关系若误码率不变（可靠性要求不变），若误码率不变（可靠性要求不变），采用编码，可以节省发送功率，采用编码，可以节省发送功率，并付出的代价也是带宽增大。并付出的代价也是带宽增大。 10-610-510-410-310-210-1编码后编码后Eb/n0 (dB)编码和误码率关系编码和误码率关系Pe CDE A B2PSK1210.3.3 传输速率和带宽的关系传输速率和带宽的关系每比特的

10、能量和噪声单边功率谱密度每比特的能量和噪声单边功率谱密度比（比（144页）页）式中，式中，RB 码元速率。码元速率。 1、提高传输速率，会降低信噪比，、提高传输速率，会降低信噪比，造成误码率增大造成误码率增大 2、可采用编码以保持误码率不变；、可采用编码以保持误码率不变；付出的代价仍是带宽增大。付出的代价仍是带宽增大。BsssbRnPTnPnTPnE0000)/1 (10-610-510-410-310-210-1编码后编码后Eb/n0 (dB)编码和误码率关系编码和误码率关系Pe CDE A B2PSK1310.3.4 编码增益编码增益定义：在保持误码率恒定条件下，采用纠错编码所节省的信定义

11、：在保持误码率恒定条件下，采用纠错编码所节省的信 噪比噪比Eb/n0称为编码增益：称为编码增益： 式中，式中，(Eb/n0)u 未编码时的信噪比未编码时的信噪比(dB)； (Eb/n0)c 编码后所需的信噪比编码后所需的信噪比(dB)。)(/00dBnEnEGcbubdB14式中，式中，a0为监督位，其他位为信息位。为监督位，其他位为信息位。10.4.1 一维奇偶监督码一维奇偶监督码监督位只有监督位只有1位，故码率等于位，故码率等于k/(k+1)。只能检错只能检错但但只能检测奇数个错码只能检测奇数个错码。0021aaann1021aaann1511na12na11a10a21na22na21a

12、20amna1mna2ma1ma01nc2nc1c0c10.4.2 二维奇偶监督码二维奇偶监督码 每行都是一个包含监督位的码组每行都是一个包含监督位的码组此外，对每一列也加入监督位此外，对每一列也加入监督位n码率等于码率等于n有可能检测偶数个错码有可能检测偶数个错码n能够纠正部分错码能够纠正部分错码 n适合检测突发错码适合检测突发错码 nmnmnk)1()1(16基本概念基本概念n监督位和信息位的关系由线性代数方程决定监督位和信息位的关系由线性代数方程决定n校正子校正子：在偶数监督码中，计算在偶数监督码中，计算实际上就是计算实际上就是计算并检验并检验S是否等于是否等于0。S称为校正子。称为校正

13、子。n监督关系式监督关系式：-接收端去检验的那个代数式接收端去检验的那个代数式0021aaann021aaaSnn021aaaSnn17纠错基本原理纠错基本原理n 若若S只有一位（两种取值），则只能表示有错或无错。而只有一位（两种取值），则只能表示有错或无错。而不能进一步指明错码的位置。因此只能不能进一步指明错码的位置。因此只能检错检错。 n若若S有两位，则取值有有两位，则取值有4种组合：其中一种表示无错码，另种组合：其中一种表示无错码，另外外3种则可指明一个错码的种则可指明一个错码的3种不同位置，因而可以种不同位置，因而可以纠错纠错。n增加增加S的位数，意味着增加的位数，意味着增加监督关系式

14、监督关系式的个数。的个数。n一般而言，若有一般而言，若有 r 个监督关系式，则个监督关系式，则 r 个校正子可以指明个校正子可以指明一个错码的一个错码的 (2r 1) 个不同位置。个不同位置。 n当校正子可以指明的错码位置数目等于或大于码组长度当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即时，才能够纠正码组中任何一个位置上的错码，即1212rknrr或18汉明码汉明码n例：要求能够纠正例：要求能够纠正1个错码，分组码个错码，分组码(n, k)中中k = 4。 p由由可得出监督位数可得出监督位数r 3，则，则n = k + r = 7。 S1 S2

15、 S3表示表示3个校正子，能指出个校正子，能指出23 1 = 7个错码的位置。个错码的位置。p校正子和错码位置的关系如表校正子和错码位置的关系如表p则可得到：则可得到：S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错码无错码1212rknrr或24561aaaaS13562aaaaS03463aaaaS19n利用监督关系式推导监督位的值利用监督关系式推导监督位的值p满足校正子等于满足校正子等于0p得到监督位与信息位得到监督位与信息位 的线性关系的线性关系000034613562456aaaaaaaa

16、aaaa346035614562aaaaaaaaaaaa信息信息位位a6 a5 a4 a3监督监督位位a2 a1 a0信息信息位位a6 a5 a4 a3监督监督位位a2 a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111120n接收端接收端p利用收到的码组，计算校正子利用收到的码组，计算校正子p根据关系表确定错码位置根据关系表确定错码位置例：若接收码组为例：若接收码组为0000011 按三式计算得到：按三式计算得到

17、：S1 = 0，S2 = 1，S3 = 1。按照表按照表可知：错码位置在可知：错码位置在a3。纠正为：。纠正为：0001011。24561aaaaS13562aaaaS03463aaaaSS1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错码无错码21p上例中的汉明码是上例中的汉明码是(7, 4)码，其最小码距码，其最小码距d0 = 3。p由式由式p可知，此码能够检测可知，此码能够检测2个错码，或纠正个错码，或纠正1个错码。个错码。n汉明码的码率：汉明码的码率：当当r (或或n)很大时，上式趋近于很大时

18、，上式趋近于1。所以汉明码是一种高效编。所以汉明码是一种高效编码。码。10 ed120 td1212rrrnk22分组码的一般原理分组码的一般原理n线性分组码的监督位和信息位的关系线性分组码的监督位和信息位的关系 可以改写为可以改写为上式中，已经将上式中，已经将“ ”简写成简写成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa23n监督矩阵监督矩阵上式可以写成矩阵形式：上式可以写成矩阵形式： （模（模2） 将上式简写为将上式简写为HAT = 0T

19、或或AHT = 0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa0001011001110101011101000123456aaaaaaa24 HAT = 0T 式中，式中， 称为监督矩阵称为监督矩阵 n监督矩阵的性质监督矩阵的性质p监督矩阵监督矩阵H确定码组中的信息位和监督位的关系。确定码组中的信息位和监督位的关系。pH 的行数就是监督关系式的数目，即监督位数的行数就是监督关系式的数目，即监督位数 r 。pH 的每行中的每行中“1”的位置表示相应的码元参与监督关系。的位置表示相应的码元参与监督关系。p H

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

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

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

23、误图样 式中，式中， (i = 0, 1, , n-1)若若ei = 0，表示该码元未错；若，表示该码元未错；若ei = 1，表示该码元为错码。，表示该码元为错码。 0121aaaaAnn0121bbbbBnnB A = E (模2)0121eeeeEnniiiiiababe当当, 1, 028n校正子矩阵校正子矩阵 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， 则则

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

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

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

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

28、情况 若若(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)(axaxaxaxTnnnn11

29、010011)(25623456xxxxxxxxxxT3210.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,

30、33码多项式的按模运算码多项式的按模运算 若任意一个多项式若任意一个多项式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）（模) 1(

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

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

33、，若能找到因此，若能找到 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。G34560123456aaaaaaaaaa

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

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

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

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

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

39、 (x)是一个是一个n次次多项式。由多项式。由可知，可知，xk T (x)在模在模(xn + 1)运算下也是一个码组，所以有运算下也是一个码组，所以有上式左端分子和分母都是上式左端分子和分母都是n次多项式，故相除的商式次多项式，故相除的商式Q(x) = 1。因此，上式可以写成因此，上式可以写成）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk40将将 T(x) = h(x) g(x) 和和 T (x) = g(x) 代入代入化简后，得到化简后，得到上式表明，生成多项式上式表明，生成多项式g(x)应该是应该是(xn + 1)的一个因子。

40、的一个因子。例：例：(x7 + 1)可以分解为可以分解为为了求出为了求出(7, 3)循环码的生成多项式循环码的生成多项式 g(x)，需要从上式，需要从上式中找到一个中找到一个(n k) = 4次的因子。这样的因子有两个，即次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。以上两式都可以作为生成多项式。 选用的生成多项式不同，产生出的循环码码组也不同。选用的生成多项式不同，产生出的循环码码组也不同。 )() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx4110.6.3

41、 循环码的编码方法循环码的编码方法用用xn-k乘乘m(x)。这一运算实际上是在信息码后附加上。这一运算实际上是在信息码后附加上(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，则有，则有 上式是用码多项式表示的运算。它和下式等效：上式是用

42、码多项式表示的运算。它和下式等效：编出的码组编出的码组T(x)为：为：T(x) = xn-k m(x) +r(x)在上例中，在上例中，T(x) = 1100000 + 101 = 1100101 )()()()()(xgxrxQxgxmxkn11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn101111011111011111000004210.6.4 循环码的解码方法循环码的解码方法在检错时：当接收码组没有错码时，接收码组在检错时：当接收码组没有错码时，接收码组R(x)必定能被必定能被g(x)整除，即下式整除，即下式中余项中余项r(x)应为零；否则，有误码。应为零；否

43、则，有误码。n当接收码组中的错码数量过多，超出了编码的检错能力当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被时，有错码的接收码组也可能被g(x)整除。这时，错码就整除。这时，错码就不能检出了。不能检出了。 在纠错时：在纠错时：n用生成多项式用生成多项式g(x)除接收码组除接收码组R(x)，得出余式，得出余式r(x)。n按照余式按照余式r(x)，用查表的方法或计算方法得出错误图样，用查表的方法或计算方法得出错误图样E(x)。n从从R(x)中减去中减去E(x)，便得到已经纠正错码的原发送码组，便得到已经纠正错码的原发送码组T(x)。)(/)()()(/)(xgxrxQ

44、xgxR)(/ )()()(/ )(xgxrxQxgxR4310.6.5 截短循环码截短循环码截短目的：截短目的： 在设计时，通常信息位数在设计时，通常信息位数k、码长、码长n和纠错能力都是预先和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。给定的。但是，并不一定有恰好满足这些条件的循环码存在。故采用截短码长截短，得出满足要求的编码。故采用截短码长截短，得出满足要求的编码。截短方法：截短方法： 设给定一个设给定一个(n, k)循环码，它共有循环码，它共有2k种码组，现使其前种码组，现使其前i (0 i k)个信息位全为个信息位全为“0”，于是它变成仅有，于是它变成仅有2

45、k-i种码组。然后种码组。然后从中删去这从中删去这 i 位全位全“0”的信息位，最终得到一个的信息位，最终得到一个 (n i，k i)的线性码。将这种码称为截短循环码。的线性码。将这种码称为截短循环码。 截短循环码与截短前的循环码至少具有相同的纠错能力，并截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环码的编解码方法仍和截短前的方法一样。且截短循环码的编解码方法仍和截短前的方法一样。 例：要求构造一个能够纠正例：要求构造一个能够纠正1位错码的位错码的(13, 9)码。码。 这时可以由这时可以由(15, 11)循环码的循环码的11种码组中选出前两信息位种码组中选出前两信息位均为均为

46、“0”的码组，构成一个新的码组集合。然后在发送时不的码组，构成一个新的码组集合。然后在发送时不发送这两位发送这两位“0”。于是发送码组成为。于是发送码组成为(13, 9)截短循环码。截短循环码。 4410.6.6 BCH码码BCH码是能够纠正多个随机错码的循环码。码是能够纠正多个随机错码的循环码。 BCH码分为两类：本原码分为两类：本原BCH码和非本原码和非本原BCH码。码。 n本原本原BCH码：码长码：码长n = 2m 1 (m 3，任意正整数，任意正整数)，它的生，它的生成多项式成多项式g(x)中含有最高次数为中含有最高次数为m次的本原多项式；次的本原多项式；n非本原非本原BCH码：码长码

47、：码长n是是(2m 1)的一个因子，它的生成多的一个因子，它的生成多项式项式g(x)中不含有最高次数为中不含有最高次数为m的本原多项式。的本原多项式。BCH码的工程设计：可以用查表法找到所需的生成多项式。码的工程设计：可以用查表法找到所需的生成多项式。例：二进制非本原例：二进制非本原BCH码的生成多项式系数码的生成多项式系数 表中表中g(x)是用是用8进制数字表示的；进制数字表示的；t 为纠错能力。为纠错能力。nktg(x)nktg(x)1721233341912122221223247271663534351456647133476565732453404652444307335710761

48、354300067171777353745常用常用BCH码：码：n戈莱戈莱(Golay)码：码： (23, 12)非本原非本原BCH码，它能纠正码，它能纠正3个随机个随机错码，并且容易解码错码，并且容易解码 。n扩展扩展BCH码码(n + 1, k) ：pBCH码的长度为奇数。在应用中，为了得到偶数长度码的长度为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在的码，并增大检错能力，可以在BCH码生成多项式中码生成多项式中乘上一个因式乘上一个因式(x + 1)，从而得到扩展，从而得到扩展BCH码码(n + 1, k)。 p扩展扩展BCH码已经不再具有循环性。码已经不再具有循环性。 n

49、扩展戈莱码扩展戈莱码(24, 12)：其最小码距为：其最小码距为8，码率为，码率为1/2，能够纠，能够纠正正3个错码和检测个错码和检测4个错码。个错码。 46几种二进制分组码的性能比较几种二进制分组码的性能比较 2PSK汉明码汉明码(7, 4) t=1 汉明码汉明码(31, 26) t=1扩展戈莱码扩展戈莱码(24, 12) t=3BCH码码(127, 64) t=10Eb / n0 (dB)Pe4710.6.7 RS码码RS码：是码：是q进制进制BCH码的一个特殊子类，并且具有很强的纠码的一个特殊子类，并且具有很强的纠错能力。错能力。RS码的参数：码长码的参数：码长n = q 1，监督位数目

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

51、卷积码卷积码卷积码的特点：卷积码的特点：n监督码元不仅和当前的监督码元不仅和当前的k比特信息段有关，而且还同前面比特信息段有关，而且还同前面m = (N 1)个信息段有关。个信息段有关。n将将N称为码组的约束度。称为码组的约束度。n将卷积码记作将卷积码记作(n, k, m)，其码率为，其码率为k/n。49卷积码的编码卷积码的编码n一般原理方框图一般原理方框图编码输出编码输出每次输入每次输入k比特比特1k1k1k1k 1 k2k3kNk 12nNk级级移存器移存器n个模个模2加法器加法器每输入每输入k比特比特旋转旋转1周周50n卷积码编码器的实例方框图：卷积码编码器的实例方框图：(n, k, m

52、) =（3, 1, 2）p每当输入每当输入1比特时，此编码器输出比特时，此编码器输出3比特比特c1c2 c3：p编码器的工作状态编码器的工作状态 123b3b1输入输入b2编码输出编码输出c2c1c3321331211bbbcbbcbcb11101000b3b200011110011000c1c2 c3111110010100001011000状态状态abdcbca5110.7.2 卷积码的解码卷积码的解码码树搜索法：码树搜索法：(3, 1, 2)卷积码的码树图卷积码的码树图此法不实用：因为随信息位增多，分支数目按指数规律增长此法不实用：因为随信息位增多，分支数目按指数规律增长00011100

53、1110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110c1c2c3信息位信息位 1 1 0 1ba起点起点信息位信息位000111c1c2c3abcdabcdabcdabcd上上半半部部下下半半部部10a状态状态 b3b2 a 0 0 b 0 1 c 1 0 d 1 1abcdabcdcdab01100152状态图和网格图状态图和网格图n移存器状态和输入输出码元的关系移存器状态和输入输出码元的关系n状态图状态图前一状态前一状态b3 b2当前输入当前输入 b1输出输出c1c2

54、c3下一状态下一状态b3 b2a (00)01000111a (00)b (01)b (01)01001110c (10)d (11)c (10)01011100a (00)b (01)d (11)01010101c (10)d (11)321331211bbbcbbcbc123b3b1输入输入b2编码输出编码输出c2c1c3abcd00011110111001001110000153n(3, 1, 2)卷积码网格图卷积码网格图n网格图中的编码路径举例网格图中的编码路径举例p输入信息位为输入信息位为1101时时p输出编码序列是：输出编码序列是：111 110 010 100 011 11011

55、0110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100abcd000111101110010011100001abcdabcd11001000111110054维特比算法维特比算法n基本原理：将接收到的序列和所有可能的发送序列作比较，基本原理：将接收到的序列和所有可能的发送序列作比较，选择其中汉明距离最小的序列当作是现在的发送序列选择其中汉明距离最小的序列当作是现在的发送序列n例：设卷积码为例：设卷积码为(n, k, m) = (3, 1, 2)码码p 现在的发送

56、信息位为现在的发送信息位为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，所以首先需考察，所以首先需考察3个信息段，即考察个信息段，即考察3n 9比特，比特，即接收序列前即接收序列前9位位“111

57、010 010”。 55n解码第解码第1步步p由网格图可见，沿路径每一级有由网格图可见，沿路径每一级有4种状态种状态a, b, c和和d。每。每种状态只有两条路径可以到达。故种状态只有两条路径可以到达。故4种状态共有种状态共有8条到达条到达路径。路径。p比较网格图中的这比较网格图中的这8条路径和接收序列之间的汉明距离。条路径和接收序列之间的汉明距离。例如，由出发点状态例如，由出发点状态a经过经过3级路径后到达状态级路径后到达状态a的两条的两条路径中上面一条为路径中上面一条为“000 000 000”。它和接收序列。它和接收序列“111 010 010”的汉明距离等于的汉明距离等于5；下面一条为

58、；下面一条为“111 001 011”,它和接收序列的汉明距离等于它和接收序列的汉明距离等于3。 110110110110011011011010010010101101101001001001001abcdabcd00000000000000011111111111111110010010056p将这将这8个比较结果列表如下：个比较结果列表如下：p比较到达每个状态的两条路径的汉明距离，将距离小的比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就剩下一条路径保留，称为幸存路径。这样，就剩下4条路径条路径了，即表中第了，即表中第2, 4, 6和和8条路径。条路径

59、。 序序号号路径路径对应序列对应序列汉明距离汉明距离幸存否？幸存否？1aaaa000 000 0005否否2abca111 001 0113是是3aaab000 000 1116否否4abcb111 001 1004是是5aabc000 111 0017否否6abdc111 110 0101是是7aabd000 111 1106否否8abdd111 110 1014是是57n解码第解码第2步：继续考察接收序列中的后继步：继续考察接收序列中的后继3个比特个比特“110” p计算计算4条幸存路径上增加条幸存路径上增加1级后的级后的8条可能路径的汉明距条可能路径的汉明距离。计算结果列于下表中。离。计

60、算结果列于下表中。 p表中总距离最小为表中总距离最小为2，其路径是，其路径是abdc+b，相应序列为，相应序列为111 110 010 100。它和发送序列相同，故对应发送信息。它和发送序列相同，故对应发送信息位位1101。 序号序号路径路径原幸存路径的原幸存路径的距离距离新增新增路径段路径段新增距离新增距离总距离总距离幸存否？幸存否？1abca+a3aa25否否2abdc+a1ca23是是3abca+b3ab14否否4abdc+b1cb12是是5abcb+c4bc37否否6abdd+c4dc15是是7abcb+d4bd04是是8abdd+d4dd26否否58p按照上表中的幸存路径画出的网格图