1、 本章内容 第11章 差错控制编码 基本概念 简单实用码 线性分组码 循环码 卷积码 概 述 为保证运送途中不出现打碎灯泡的情况有效性 可靠性 n 通信中的情况：针对乘性针对加性合理选择调制/解调方法，增大发射功率采用等措施n 差错控制编码u 信道类型信道类型 根据错码的不同分布规律分为：u 差错控制方式：差错控制方式：n 差错控制方式（ARQ）（FEC） 缺点：工作在半双工状态，传输效率较低。u 3 种自动要求重发(ARQ)系统（1 1）停止等待ARQ系统 系统需要双工信道。 （2 2）拉后ARQ系统第第5组组传输速率比第（1 1）种高。（3 3）选择重发ARQ系统uARQ的主要缺点：l码率
2、较高。 用较少的监督码元就能使误码率降到很低；l检错的计算复杂度较低；l检错用的编码方法 和 加性干扰的统计特性基本无关，能适应不同特性的信道。l需双向信道来重发，不适用单向信道和一点到多点的通信系统。l重发使得ARQ系统的传输效率降低。l信道干扰严重时，将发生因反复重发而造成事实上的通信中断。l不适用于要求实时通信的场合，例如电话通信。uARQ的主要优点：与前向纠错（FEC）方法相比uARQ系统的原理方框图纠错编码基本原理 n情形1 1：没有冗余 不能发现错误2：加入冗余 可以发现错误另外4个码组码组码组例例许用码组禁用码组纠正（奇数个错码）例例：ckRn，检错 或 纠错 能力也不同 。n分
3、组码和系统码n= k+r符号：结构 （n，k）l 码长码长 (n)：。l 码重码重(W)：。“ 0 1 1 0 1 1” 的距离例例n 码重和码距 码重为 3l 码距的几何意义：码距的几何意义：10 ed120 td)(teted10（n，k）n最小码距d0 和检纠错能力的关系l 检个错码，要求：l 纠个错码，要求：l 纠 t 个错码,同时检 e个错码，要求： 10 ed120 td)(10teted证明：纠错编码性能 n系统带宽和信噪比的矛盾系统带宽和信噪比的矛盾 右图所示的某种编码性能右图所示的某种编码性能可见：不增大发送功率不增大发送功率, 就能就能 降低误码率约一个半数量级。降低误码率
4、约一个半数量级。A点点B点点例例10-610-510-410-310-210-1编编码码后后 CD A B信噪比信噪比 (dB)2PSK调制调制可见：能节省功率能节省功率 2 dB 称为称为编码增益编码增益D点点10-610-510-410-310-210-1编编码码后后 CD A B信噪比信噪比 (dB)2PSK调制调制C点点设编码设编码前前 系统工作在图中系统工作在图中C点，点， 提高速率后提高速率后由由C点升到点升到E点。点。n传输速率传输速率RB 和和 信噪比信噪比Eb/n0的关系的关系若希望提高若希望提高RB，则必使则必使Eb/n0下降，误码率下降，误码率增大。增大。这时付出的代价仍
5、是带宽增大。这时付出的代价仍是带宽增大。10-610-510-410-310-210-1编编码码后后 CDEAB信噪比信噪比 (dB)0000(1/)bBsssPTPPnnTEnRn但采用纠错编码但采用纠错编码后后，仍可降到仍可降到 D点。点。简单实用编码 11.4.1 奇偶监督码u 适用： u编码规则：只一位监督码元1CknRnnu 码率： 100111 000110 10011根据偶数监督规则：00011例例解解11.4.2 二维奇偶监督码u编码规则：u检测方法：计算接收码组中“1”的数目，可知是否有错。11.4.3 恒比码u适用：用于电报传输系统或其他键盘设备产生的字母和符号。u编码规则
6、：(等重码)例例377!/(3!4!35)C 11.4.4 正反码u编码规则： 设码长n = 10，即信息位 k = 5，监督位 r = 5。例例n监督位数与信息位数相同；监督位数与信息位数相同；n能纠错能纠错。n编码效率低：编码效率低：50%50%。u译码方法： 00000无错信息位中有奇数个“1”，校验码组 = 00000 发送码组为11001 11001u纠检能力：（n, k）线性分组码l线性码：按照一组方程构成的代数码。 即每个码字的监督码元是信息码元的线性组合。n基本概念l代数码：建立在代数学基础上的编码。正反码，效率正反码，效率50%，太低。，太低。纠正纠正1位错，最少增加多少监督
7、位？位错，最少增加多少监督位？构造出以最小多余度代价换取最大抗干构造出以最小多余度代价换取最大抗干扰能力的好码扰能力的好码纠错编码任务：纠错编码任务：汉明码：能纠正汉明码：能纠正1位错，编码效率较高位错，编码效率较高102nnaaaS-监督关系式若 S=0，认为无错（偶监督时）；若 S=1，认为有错 。若要构造具有纠错能力的（n，k）码，则需增加督码元的数目。2121rrnkr 或 当“=”成立时，构造的线性分组码 称为汉明码),(),(rknrr1212校正子校正子n 构造原理只有一位监督元-检错检错汉明码的例例21rn 可以可以其他其他假设假设由表可见由表可见: : 仅当一位错码的位置在a
8、2 、a4、a5 或a6 时， 校正子S1为1；否则S1为 0。16542Saaaa26531Saaaa36430Saaaa654653613204000aaaaaaaaaaaa654621536430aaaaaaaaaaaa(A)移项运算解出监督位(A)654621536430aaaaaaaaaaaa16542Saaaa26531Saaaa36430Saaaa例例接收端译码检错纠错过程以上构造的线性分组码 ，称为汉明码。最小码距：1cknrrRnnn 当 n很大 r很小时，Rc 1。 编码效率：),(),(rknrr1212汉明码特点:21rn d0 = 3 （纠1或检2）r 是不小于3的任
9、意正整数000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaan线性分组码的一般原理uH-监督矩阵 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa65432101110100011010100210110010aaaaaaa （模 ）H A= a6 a5 a4 a3 a2 a1 a00 = 000监督矩阵 或转置转置“T” r n111010011010101011001HMMM
10、= PIr r k阶矩阵r r阶方阵 uH矩阵的性质 H的行数 等于监督位的数目r。H的每行中“1”的位置表示相应码元之间存在的监督关系。(7，4)码r= 3 H的各行应该是线性无关的，否则得不到r个线性无关的监督关系式。若一矩阵能写成典型阵形式 PIr ，则其各行一定是线性无关的。将上面汉明码例子中的监督位公式：改写成矩阵形式：uG-生成矩阵 654621536430aaaaaaaaaaaa或者写成：6251403aaaaaaa111011011011P阵阵6251403aaaaaaa11101101101121065436543a a aa a a aa a a aQ11111010101
11、1式中，Q为一个k r阶矩阵，它为P的转置，即:Q =PT P阵阵Q阵阵 G34560123456aaaaaaaaaaaGA3456aaaa将Q的加上1个k k阶单位方阵，就构成矩阵: 生成矩阵，或者因此，若找到了码的G，则编码的方法就完全确定了。具有IkQ形式的称为由得到的码称为系统码。1000010000111111010100001 011kGQMMMMI I信息位不变，信息位不变，监督位在后。监督位在后。 由它可以产生整个码组，即有: 2106543a a aa a a aQk k n nuG矩阵的性质 G矩阵的各行是线性无关的。GA3456aaaa由式可看出:任一码组A都是G的各行的
12、线性组合。G共有，若它们线性无关，则可以组合出2k种不同的码组A。它恰是有它恰是有k位信息位位信息位 的全部码组。的全部码组。uG和H的关系 1210nnbbb bBL1210nneee eB - AELiiiiiababe当当,10u 校正子与错误图样 设发送码组为一个n列的行矩阵 A， 接收码组的行矩阵 B）1210nnaaa aAL(模2)A= B + E例例E发送接收来进行检测。将 B = A + E代入上式，可得00 00 0EL若, 则 S为0，否则 S 不为 0。译码2) 由S找到错误图样E；3) 由公式 A =B + E得到译码器译出的码组。译码 封闭性A1和A2(A1+A2)
13、证明：若A1和A2是两个码组，则有A1 HT = 0 和 A2 HT = 0，将两式相加，有 A1 HT + A2 HT = (A1 + A2) HT = 0 最小距离（证毕）n线性分组码的性质根据性质 线性分组码计算最小码距，只需找最小码重，无需两两码组比较21r完备性：汉明码中，伴随式的非零形式与错误图样一一对应，且伴完备性：汉明码中，伴随式的非零形式与错误图样一一对应，且伴随式的图样除全随式的图样除全0 0外为外为 个，正好等于码长，最充分利用了监督个，正好等于码长，最充分利用了监督位所提供的信息。位所提供的信息。循 环 码表中的第 2 码组向 右移一位即得到第 5 码组；(7, 3)循
14、环码循环码11.6.1 循环码原理表中的第 6 码组向 右移一位即得到第 3码组 。 注意：注意： 码字（）的多项式可表示为： n码多项式 多项式的系数就是码组中的各码元，x 仅是码元位置标记 。n=7 例例1. 码多项式的按模运算 一般说来，一个整数m可以表示为npnpQnm,（Q 为整数） m p (模n)在模n运算下，有 u 码多项式的按模运算：( )( )( )( )( )F xR xQ xN xN x( )( ) ( )( )F xN x Q xR x或则( )( )( )F xR xN x（模）例例 运算过程：即有 则有44223111xxxxxxxx 余式）（模)()()(1ni
15、xxAxAx因为，A (x)是 A(x) 代表的码组向左循环移位 i 次的结果。u循环码的码多项式则 余式A (x) 也是该编码中的一个许用码组。 例例1256xxxxA)(循环码组，码长n = 7。i = 3时，有）（模)()()(117235358925633xxxxxxxxxxxxxxAx652( )1A xxxx532( )A xxxxx左移 i 位32. 循环码的生成矩阵G 生成矩阵 G可由k 引思：如何寻找这 个线性无关的码组？因此，用这个线性无关的码组可构成该循环码的生成矩阵G ，即)()()()()(xgxxgxgxxgxxkk21G生成多项式生成多项式 g(x)是是xn+1的
16、因式的因式g(x)的性质：的性质： g(x)必有一常数项必有一常数项a01 g(x)的次数为的次数为n-k次，且次，且唯一唯一否则，循环右移1位出现k连0,线性分组码不可能信息位全0，监督位不全为0若2个，由封闭性得两者和为码组，连0个数至少多出2位：a0、an-k 线性分组码不可能后面说明r= n-k = 7-3 =4，001011101011101011100G解2643253242( )( )( )( )1x g xxxxxxxg xxxxxg xxxxG例例码组中唯一一个4次码多项式代表的或此循环码多项式A(x):)()()()()()()()()()(xgaxaxaxgaxxgaxg
17、xaxgxxgxgxaaaxaaaxA452645262456456G(n-k)+(k-1)=n-1(n-k)+(k-1)=n-1A(x) g(x) 11nnkxxAxQxxAx)()()(g(x) A (x) = g(x)A(x) = h(x) g(x)A (x)xkA (xnxkA (x）（模)()()(1nixxAxAx)()()(xAxxAxnk1)()(1xhxxgxkn左端分子和分母都是n次多项式，故Q(x) = 1：将 和 代入上式，化简后得到11nnkxxAxQxxAx)()()(A (x) = g(x)A(x) = h(x) g(x) 求(7, 3)循环码的生成多项式 g(x
18、) 。例例将 (x7+1) 进行因式分解：解：解：nk)()(11113237xxxxxx即有或4327321(1)(1)xxxxxx 4723(111)xxxxxx 11.6.2 循环码的编解码方法1. 1. 循环码的编码循环码的编码 信息码 (an-1 an-2 an-k) 的m(x)=an-1xk-1+an-2 xk-2+ +an-k其最高次数为k-1 循环码的多项式为：121212( )( )( )( )( )kknnnknnnkxg xxg xaaaxaaaxg xg xGA(x)=1212() ( )kknnn kaxaxag xA(x)=m(x)g(x)（1） 乘 （2） xn-
19、k 除以：将信元左移（n k）位，附上（n k）个0，预留给监督码元。( )( )( )()n kxm xQ xg xxr xg得到余式，作为监督码元 即得循环码的码多项式。循环码的编码步骤：（3）作 A = xn-k （n k）+（k-1）（n 1）-（k-1）=r（n 1）最高次数例例2. 2. 循环码的解码循环码的解码目的目的：若能除尽，则无错；若除不尽而有余项，则表示在传输中发生错误。检错检错：纠错纠错：11.6.3 截短循环码n例例：构造一个能够纠正1位错码的(13, 9)码。可由(15, 11)循环码的码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。在发送时不发送这两位
20、“0”。于是发送码组成为(13, 9。 n截短目的：截短目的：在设计纠错编码方案时，若找不到合适的码长n及信息位k 时，把循环码的码长截短以得到符合要求的编码。n截短方法：截短方法：设给定一个(n, k)循环码，它共有 2k种码组，现使其前 i (0 i k)个信息位全为“0”，于是它变成仅有 2k- i 种码组。然后从中删去这 i 位全“0”的信息位，最终得到一个(n i , k i )的线性码。 n截短循环码性能：截短循环码性能：循环码截短前后至少具有的纠错能力，并且编解码方法仍和截短前的方法一样。 11.6.4 BCH码解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要求的条件下
21、寻找到码的生成多项式。n BCH码的重要性: :n BCH码的分类：多个多个u汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码。n BCH码的性能：u 码长n与监督位、纠错个数 t之间的关系： 对于正整数m(m 3)和正整数t 1，且除得尽(2m -1)），则为非本原BCH码。n BCH码的设计：u在工程设计中，一般不需要用计算方法去寻找生成多项式g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查表法找到所需的生成多项式。u教材348/353页的表11-7 给出了码长n 127的二进制本原BCH码生成多项式。n = (2m - 1)
22、n = (2m - 1) BCH码的长度都为奇数。n为得到偶数长度的码，并增大检错能力，在BCH码生成多项式中乘因式(x + 1)，得扩展BCH码(n + 1, k)。n扩展BCH码相当于在原BCH码上增加了一个校验位，因此码距比原BCH码增加1。n扩展BCH码已经不再具有循环性。n例如，广泛实用的扩展戈莱码(24, 12)，其最小码距为8，码率为1/2，能够纠3个错码和检4个错码。它比汉明码的纠错能力强很多。代价：解码更复杂，码率也比汉明码低。不再是循环码。n 扩展BCH码：11.6.5 RS码一类具有很强纠错能力的多进制BCH码。 由里德和索洛蒙(Reed Solomon)提出。 一个能够
23、纠t个错误符号的m进制的RS码有如下参数：d0 = 2t + 1个 符号， 或 q（ 2t + 1）比特n = m 1 = 2q 1个符号，r = n-k= 2t个符号， 或 2tq比特k 个符号， 或 kq个比特参数参数或 q(2q 1)个比特能够纠正t个m进制错码，即能纠正码组中t个不超过q位连续的错码，特别适用于存在的信道，例如，移动通信网等中。它是多进制纠错编码，特别适合用于的场合。RS码的生成多项式： g(x) = (x + )(x +2) (x +2t)式中， 是伽罗华域GF(2q )中的本原元素。应用应用卷 积 码n非分组码概念：u 分组码: 每个码组中的监督码仅与本码组中的k个
24、有约束关系。u 非分组码:即一个码组中的监督着N个信息段。u 卷积码的符号: (n, k, N)- 编码nN- 编码，。u 卷积码的码率: R=k/ n(n, 1, N) 简单, 常用N或nN也反映了卷积码编码器的复杂度。 将k比特信息段编成n比特码组一般，一般，k，n较小，较小，N较大；较大；随着随着N增大，误码率呈指数下降；增大，误码率呈指数下降；更适用于前向纠错，性能优于分组码，运算简单。更适用于前向纠错，性能优于分组码，运算简单。GSM（2,1,5）IS-95 （2,1,9）CDMA2000（2,1,9)11.7.1 卷积码的基本原理n编码器原理方框图k(N-1)共有N移存器，每段k
25、212iiiiiiiiibbbebbdbc 如图所示的(n, k, N) = (3, 1, 3)卷积码编码器。例例共有移存器，每段1 每次输入1b，输出 3b ：-移存器初始是全零状态，当输入信息序列 ：编码器输出序列：212iiiiiiiiibbbebbdbc结果为形式。ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt输入输出信息位bi的监督位和各信息位之间的约束关系如下图中虚线所示：（编码N=3，nN=33 =9） 212iiiiiiiiibbbebbdbcn卷积码的表述方法：11.7.2 卷积码的代数表述212iiiiiiiiibbbebbdbc上式：表
26、示的卷积码也是一种线性码。 可完全由 H 或 G 所确定。监督矩阵生成矩阵n分类：代数解码： 利用编码本身的代数结构进行解码，不考虑信道的统计特性。概率解码（最大似然解码）： 基于信道的统计特性和卷积码的特点进行计算。11.7.3 卷积码的解码 如：大数逻辑解码（门限解码），适用 nN 较短的卷积码。 序贯解码: 适用无记忆信道当码的 nN 较短时，效率更高、速度更快2 卷积码的几何表述卷积码的几何表述 维特比解码算法的基础维特比解码算法的基础1）码树图以前面 (3, 1, 3) 卷积码为例：(n, k, N) 113123iiicMdMMeMMM (3, 1, 3) 码树图：观察观察1 11
27、13123iiicMdMMeMMM规定规定 若信息位编码输出 111 110 010 100 (3, 1, 3) 码树图：观察观察2 2M1M2M3110011101100M3M20111100100状态状态11011 1 0 1 (3, 1, 3) 码树图：观察观察3 3若信息位编码输出 111 110 010 1000 010101 11 10 0不实用基础2）状态图由(3, 1, 3)编码器结构可知： 一状态 a只能转到下一状态a或b；一状态b只能转到下一状态c或d， 等等。按照 表中的规律 画出的状态图： 由表看出：abcd000111101110010011100001abcd000
28、111101110010011100001利用状态图可方便地从输入序列得到输出序列。例如： 输入信息位 编码输出 111 110 010 100111110010100第4时隙后完全是第3时隙的重复，因（3,1,3）码约束长度为3。3）网格图5个时隙abcd000111101110010011100001当输入信息位为11010时，在网格图中的编码路径：这时的输出编码序列：111 110 010 100 011。基于上面的和，讨论维特比解码算法。3 维特比解码算法维特比解码算法 仍用上面(3, 1, 3)卷积码的例子来说明维特比算法的原理。例例设发送信息位为1101，为了使图中移存器的信息位全
29、部移出，在信息位后面加入3个“0”，故编码后的发送序列为 111 110 010 100 001 011 000设接收序列为 111 010 010 110 001 011 000比较网格图中的这8条路径接收序列之间的汉明距离。 (n, k, N) 第1步，由出发点状态 a经 3级 路径后到达状态 a的中：上面一条为“000 000 000”，它和接收序列“111 010 010”的汉明距离=5下面一条为“111 001 011”，它和接收序列 的汉明距离=3同样，由出发点a经过3级路径后到达状态b、c和d的路径分别都有，故总共有8条路径。 下表中列出了这8条路径和其汉明距离。比较到达每个状态
30、的路径的汉明距离作，将距离小的一条路径保留，称为。两条路径的汉明距离相同，可任意保存一条。就剩下4条路径： 2, 4, 6，8第2步abcd011010010101001abcd111100100110110按照表中的幸存路径画出的网格图示于下图中： 上例卷积码的约束度 N = 3，需要存储和计算 8 条路径的参量。 故维特比解码算法适合约束度较小（N 10）的编码。 对于约束度大的卷积码，可以采用其他解码算法。 由此可见，维特比解码算法的复杂度 随N按指数形 式 2N增长。交织编码主要用来纠正突发差错，即使突发差错分散成为随机差错而得到纠正。交织编码不增加监督元，交织编码前后，码速率不变， 不影响有效性。常与其它纠正随机差错的编码(如卷积码或其它分组码)结合使用，既能纠正随机差错又能纠正突发差错。在移动信道中数字信号传输常出现成串的突发差错，数字化移动通信中经常使用交织编码技术。交织编码交织编码第一个码字： c11c12c13c14c15c16c17， 第二个码字： c21c22c27 ， ， 第m个码字： cm1cm2 cm7。交织方法将每个码字按行按行存入存储器：一般在交织之前， 先进行分组码编码， 如采用(7，3)码
