第8章 差错控制技术课件.ppt

第第8 8章章 差错控制技术差错控制技术8.1 8.1 差错控制的常用方法差错控制的常用方法8.2 8.2 纠错编码纠错编码8.3 8.3 常用的简单编码常用的简单编码8.4 8.4 线性分组码线性分组码8.5 8.5 循环码循环码8.68.6 m序列序列8.1 8.1 差错控制的常用方法差错控制的常用方法 自动请求重发（自动请求重发（ARQ） 停发等待重发停发等待重发 返回重发返回重发 选择重发选择重发 前向纠错（前向纠错（FEC） 混合纠错（混合纠错（HEC） 反馈检验（反馈检验（IRQ）自动请求重发自动请求重发 应答信号 信息码 能够发现错误的码 信息码 发送端 接收端 图 8-1 自动请求重发 ARQ 示意图 图8-2 停止等待重发ARQ系统 接收数据 ACK ACK NAK ACK ACK NAK ACK 1 2 3 3 4 5 5 t 发送数据 1 2 3 3 4 5 5 6 t 有错码组 有错码组 优点：译码设备简单，对突发错误和信道干扰较优点：译码设备简单，对突发错误和信道干扰较严重时比较有效。严重时比较有效。 缺点：需要反馈信道，实时性差。缺点：需要反馈信道，实时性差。 图8-3 返回重发ARQ系统 2 1 4 3 6 5 7 9 8 接收数据 有错码组 有错码组 9 10 11 10 11 12 5 7 6 ACK1 NAK5 NAK9 ACK5 5 7 6 9 5 2 1 4 3 6 7 9 8 发送数据 10 11 10 11 12 重发码组 重发码组 图8-4 选择重发ARQ系统 9 接收数据 有错码组 有错码组 2 1 4 3 6 5 7 5 9 8 10 11 13 14 12 发送数据 9 9 5 8 5 2 1 4 3 6 7 10 11 13 14 12 重发码组 重发码组 NAK9 ACK1 NAK5 ACK5 ACK9 前向纠错前向纠错 优点：使用纠错码和单向信道，发送端无优点：使用纠错码和单向信道，发送端无需设置缓冲器。需设置缓冲器。 缺点：设备复杂、成本高。缺点：设备复杂、成本高。混合纠错混合纠错 特点：实时性和译码复杂性方面是前向纠错和检特点：实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，可达到较低的误码率，较适错重发方式的折衷，可达到较低的误码率，较适合于环路延迟大的高速数据传输系统。合于环路延迟大的高速数据传输系统。 应答信号 信息码 能够发现并纠正错误的码 信息码 发送端 接收端 图 8-6 混合纠错 HEC 示意图 反馈校验反馈校验 优点：设备简单，可以纠正任何错误优点：设备简单，可以纠正任何错误 缺点：会引入较大的时延。缺点：会引入较大的时延。 原码返回，在发送端比较 信息码 发送信息码 信息码 发送端 接收端 图 8-7 反馈检测 IRQ 示意图 8举例：有一种由举例：有一种由3个二进制码元构成的编码，它共有个二进制码元构成的编码，它共有23 = 8种种 不同不同的可能码组：的可能码组：000 晴晴 001 云云 010 阴阴 011 雨雨100 雪雪 101 霜霜 110 雾雾 111 雹雹 这时，这时，若一个码组中发生错码，则将收到错误信息若一个码组中发生错码，则将收到错误信息。 若在此若在此8种码组中仅允许使用种码组中仅允许使用4种来传送天气，例如：令种来传送天气，例如：令000 晴晴 011 云云 101 阴阴 110 雨雨 为为许用码组许用码组，其他，其他4种不允许使用，称为种不允许使用，称为禁用码组禁用码组。 这时，接收端有可能发现（检测到）码组中的一个错码。这时，接收端有可能发现（检测到）码组中的一个错码。 这种编码只能检测错码，不能纠正错码。这种编码只能检测错码，不能纠正错码。 若规定只许用两个码组：例如若规定只许用两个码组：例如000 晴晴 111 雨雨就能检测两个以下错码，或纠正一个错码。就能检测两个以下错码，或纠正一个错码。 纠错编码的基本原理纠错编码的基本原理9分组码概念分组码概念 分组码分组码 信息位信息位 监督位监督位 分组码符号：分组码符号：(n, k) 其中，其中，n 码组总长度，码组总长度， k 信息码元数目。信息码元数目。 r = n k 监督码元数目。监督码元数目。右表中的码组为右表中的码组为(3, 2)码。码。 分组码的一般结构：分组码的一般结构： 分组码的参数：分组码的参数： 码重：码组内码重：码组内“1”的个数的个数 码距：两码组中对应位取值不同的位数，又称汉明距离码距：两码组中对应位取值不同的位数，又称汉明距离 最小码距最小码距(d0) ：各码组间的最小距离：各码组间的最小距离信息位信息位监督位监督位晴晴000云云011阴阴101雨雨110k个信息位个信息位r个监督位个监督位an-1an-2.arar-1an-2.a0t码长码长 n = k + r分组码的结构分组码的结构 码距的几何意义：以码距的几何意义：以n = 3的编码为例的编码为例 一般而言，码距是一般而言，码距是 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)a2a0a1码距与纠检错能力的关系码距与纠检错能力的关系 为了检测为了检测t个随机错误，则要求码组的最小个随机错误，则要求码组的最小距离距为距离距为 01de码距与纠检错能力的关系码距与纠检错能力的关系 为了纠正为了纠正t个随机错误，个随机错误， 则要求码组的最小则要求码组的最小距离为距离为021dt B t A 汉明距离 0 1 2 3 4 5 t d0 8-10 码距等于5的两个码组 码距与纠检错能力的关系码距与纠检错能力的关系 纠正纠正t个随机错码，同时检测个随机错码，同时检测e个随机错误，个随机错误，则要求码组的最小距离为则要求码组的最小距离为01dte(e t) A B 1 t t 汉明距离 e 图8-11 码距等于(e+t+1)的两个码组 14常用的简单编码常用的简单编码 奇偶校验码奇偶校验码 群计数码群计数码 恒比码恒比码 正反码正反码线性分组码线性分组码 代数码代数码 利用代数关系式产生监督位的编码利用代数关系式产生监督位的编码 线性分组码线性分组码 代数码的一种，其监督位和信息位的代数码的一种，其监督位和信息位的关系关系由线性代数方程决定由线性代数方程决定 汉明码汉明码 一种能够纠正一个错码的一种能够纠正一个错码的线性分组码线性分组码 校正子：校正子：在偶数监督码中，计算在偶数监督码中，计算实际上就是计算实际上就是计算并检验并检验S是否等于是否等于0。S称为校正子称为校正子 监督关系式：监督关系式：1200nnaaa120nnSaaa120nnSaaa 纠错基本原理纠错基本原理 中，中，S只有两种取值只有两种取值，故只能表示，故只能表示有错有错和和无错无错，而不能进一步指明错码的位置。，而不能进一步指明错码的位置。 若此码组长度增加一位，则能增加一个监督关系式。这若此码组长度增加一位，则能增加一个监督关系式。这样，就能得到两个校正子。两个校正子的可能取值有样，就能得到两个校正子。两个校正子的可能取值有4种组合，即种组合，即00，01，10，11，故能表示，故能表示4种不同的信息。种不同的信息。若用其中若用其中一种组合表示无错码一种组合表示无错码，则还有，则还有其他其他3种组合可种组合可以用于指明一个错码的以用于指明一个错码的3种不同位置种不同位置。 从而可以有纠错从而可以有纠错能力。能力。 一般而言，若有一般而言，若有 r 个监督关系式，则个监督关系式，则 r 个校正子可以指个校正子可以指明一个错码的明一个错码的 (2r 1) 个不同位置。个不同位置。 当校正子可以指明的错码位置数目等于或大于码组长度当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要时，才能够纠正码组中任何一个位置上的错码，即要求求021aaaSnn1212rknrr或 汉明码汉明码 例：要求设计一个能够纠正例：要求设计一个能够纠正1个错码的分组码个错码的分组码(n, k)，给定，给定的码组中有的码组中有4个信息位，即个信息位，即k = 4。 由由这时要求监督位数这时要求监督位数r 3。若取。若取r = 3，则，则n = k + r = 7。现在用。现在用a6 a5 a4 a3 a2 a1 a0表示这表示这7个码元，用个码元，用S1 S2 S3表示校正子，则这表示校正子，则这3个校个校正子恰好能够指明正子恰好能够指明23 1 = 7个错码的位置。个错码的位置。 若规定校正子和错码位置的关系如下表，则仅当在若规定校正子和错码位置的关系如下表，则仅当在a6 a5 a4 a2位置位置上有错码时，校正子上有错码时，校正子S1的值才等于的值才等于1；否则；否则S1的值为零。这就意味的值为零。这就意味着着a6 a5 a4 a2四个码元构成偶数监督关系：四个码元构成偶数监督关系： 同理，有同理，有1212rknrr或24561aaaaS13562aaaaS03463aaaaS19 在编码时，信息位在编码时，信息位a6 a5 a4 a3的值决定于输入信号，它们是随机的。的值决定于输入信号，它们是随机的。监督位监督位a2 a1 a0是按监督关系确定的，应该保证上列是按监督关系确定的，应该保证上列3式中的校正式中的校正子等于子等于0，即有，即有给定信息位后，为了给定信息位后，为了计算监督位，上式可计算监督位，上式可以改写为以改写为按照上式计算结果为按照上式计算结果为000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa20 在接收端解码时，对于每个接收码组，先按式在接收端解码时，对于每个接收码组，先按式计算出校正子计算出校正子S1，S2和和S3，然后按照表，然后按照表判断错码的位置。判断错码的位置。 例：若接收码组为例：若接收码组为0000011，则按上三式计算得到：，则按上三式计算得到：S1 = 0，S2 = 1，S3 = 1。这样，由上表可知，错码位置在。这样，由上表可知，错码位置在a3。24561aaaaS13562aaaaS03463aaaaS 上例中的汉明码是上例中的汉明码是(7, 4)码，其最小码距码，其最小码距d0 = 3。 由式由式 可知，此码能够检测可知，此码能够检测2个错码，或纠正个错码，或纠正1个错码。个错码。 汉明码的码率：汉明码的码率：当当r (或或n)很大时，上式趋近于很大时，上式趋近于1。所以汉明码是。所以汉明码是一种高效编码。一种高效编码。10 ed120 td1212rrrnk 分组码的一般原理分组码的一般原理 线性分组码的监督位和信息位的关系线性分组码的监督位和信息位的关系 可以改写为可以改写为上式中，已经将上式中，已经将“ ”简写成简写成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa 监督矩阵监督矩阵上式可以写成矩阵形式：上式可以写成矩阵形式： （模（模2） 将上式简写为将上式简写为HAT = 0T 或或AHT = 0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa0001011001110101011101000123456aaaaaaa24 HAT = 0T 式中，式中， 称为监督矩阵称为监督矩阵 监督矩阵的性质监督矩阵的性质 监督矩阵监督矩阵H确定码组中的信息位和监督位的关系。确定码组中的信息位和监督位的关系。 H 的行数就是监督关系式的数目，即监督位数的行数就是监督关系式的数目，即监督位数 r 。 H 的每行中的每行中“1”的位置表示相应的码元参与监督关系。的位置表示相应的码元参与监督关系。 H 可以分成两部分，例如可以分成两部分，例如 典型监督矩阵典型监督矩阵 式中，式中，P 为为r k阶矩阵，阶矩阵，Ir为为 r r 阶单位方阵阶单位方阵。 101100111010101110100HrPIH001101101011011001110A = a6 a5 a4 a3 a2 a1 a0 0 = 000 H 矩阵的各行应该是线性无关的，否则将得不到矩阵的各行应该是线性无关的，否则将得不到 r 个线性无个线性无关的监督关系式。关的监督关系式。 若一个矩阵能写成典型阵形式若一个矩阵能写成典型阵形式P Ir，则其各行一定是线性，则其各行一定是线性无关的。无关的。 生成矩阵生成矩阵 例：例： 可以写为可以写为上式两端分别转置后，可以变成上式两端分别转置后，可以变成式中，式中，Q为为k r 阶矩阵，是阶矩阵，是P的转置，即的转置，即 Q = PT3456012101111011110aaaaaaa346035614562aaaaaaaaaaaaQ34563456012011101110111aaaaaaaaaaa将将Q的左边加上一个的左边加上一个k阶单位方阵，称为生成矩阵：阶单位方阵，称为生成矩阵： 生成矩阵生成矩阵 G称为生成矩阵，因为可以用它产生整个码组称为生成矩阵，因为可以用它产生整个码组A，即有，即有 生成矩阵的性质生成矩阵的性质 具有具有IkQ形式的生成矩阵称为典型生成矩阵。形式的生成矩阵称为典型生成矩阵。 由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位的位置不变，监督位中，信息位的位置不变，监督位附加于其后。这种形式的码组称为系统码。附加于其后。这种形式的码组称为系统码。 矩阵矩阵G的各行也必须是线性无关的。的各行也必须是线性无关的。 如果已有如果已有k个线性无关的码组，则可以将其用来作为生成矩阵个线性无关的码组，则可以将其用来作为生成矩阵G，并由它生成其余码组。，并由它生成其余码组。0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaA 错误图样错误图样设：发送码组设：发送码组A是一个是一个n列的行矩阵：列的行矩阵：接收码组是一个接收码组是一个n列的行矩阵列的行矩阵B： 令接收码组和发送码组之差为令接收码组和发送码组之差为E就是错码的行矩阵就是错码的行矩阵 -称为错误图样称为错误图样 式中，式中， (i = 0, 1, , n-1)若若ei = 0，表示该码元未错；若，表示该码元未错；若ei = 1，表示该码元为错码，表示该码元为错码 0121aaaaAnn0121bbbbBnnB A = E (模模2)0121eeeeEnniiiiiababe当当, 1, 0 校正子矩阵校正子矩阵 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的位置进行计算。若接收码组中无错码，则的位置进行计算。若接收码组中无错码，则B = A。代入后，。代入后，该式仍成立，即有该式仍成立，即有BH T = 0只有当错码未超出检测能力时，上式才不成立。只有当错码未超出检测能力时，上式才不成立。 假设，这时该式的右端等于假设，这时该式的右端等于S，即有，即有BH T = S将将B = A + E 代入上式，得到代入上式，得到:S = (A + E) H T = AH T + EH TS = (A + E) H T = AH T + EH T上式右端第一项等于上式右端第一项等于0，所以，所以 S = EH T 校正子矩阵校正子矩阵当当H 确定后，上式中确定后，上式中S只与只与E 有关，而与有关，而与A 无关。无关。 这意味着，这意味着，S 和错码和错码E 之间有确定的线性变换关系。之间有确定的线性变换关系。 若若S 和和E 有一一对应关系，则有一一对应关系，则S 将能代表错码位置。将能代表错码位置。 线性码的封闭性：若线性码的封闭性：若A1和和A2是一种线性码中的两个码组，则是一种线性码中的两个码组，则(A1+A2)仍是其中一个码组。仍是其中一个码组。 证证若若A1和和A2是两个码组，则有：是两个码组，则有：A1HT = 0, A2HT = 0 将上两式相加，得出将上两式相加，得出A1HT + A2HT = (A1 + A2 ) HT = 0 所以所以(A1 + A2)也是一个码组。也是一个码组。 由于线性码具有封闭性，所以两个码组由于线性码具有封闭性，所以两个码组(A1和和A2)之间的之间的距离（即对应位不同的数目）必定是另一个码组距离（即对应位不同的数目）必定是另一个码组(A1 + A2)的重的重量（即量（即“1”的数目）。因此，码的最小距离就是码的最小重的数目）。因此，码的最小距离就是码的最小重量（除全量（除全“0”码组外）。码组外）。循环码循环码 循环性是指任一码组循环一位后仍然是该编码中的一个码组。循环性是指任一码组循环一位后仍然是该编码中的一个码组。 例：一种例：一种(7, 3)循环码的全部码组如下循环码的全部码组如下 表中第表中第2码组向右移一位即得到第码组向右移一位即得到第5码组；第码组；第5码组码组向右移一位即得到第向右移一位即得到第7码组。码组。 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)(axaxaxaxTnnnn11010011)(25623456xxxxxxxxxxT循环码的运算循环码的运算 整数的按模运算整数的按模运算在整数运算中，有模在整数运算中，有模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, 码多项式的按模运算码多项式的按模运算 若任意一个多项式若任意一个多项式F(x)被一个被一个n次多项式次多项式N(x)除，得到商除，得到商式式Q(x)和一个次数小于和一个次数小于n的余式的余式R(x)，即，即则在按模则在按模N(x)运算下，有运算下，有这时，码多项式系数仍按模这时，码多项式系数仍按模2运算。运算。 例例1：x3被被(x3 + 1)除，得到余项除，得到余项1，即，即 例例2：因为因为 xx3 + 1 x4 +x2 + 1 x4 +x x2 +x +1 在模在模2运算中加法和减法一样。运算中加法和减法一样。)()()()(xRxQxNxF）（模)()()(xNxRxF）（模) 1(133xx）（模) 1(113224xxxxx 循环码的数学表示法循环码的数学表示法 在循环码中，设在循环码中，设T(x)是一个长度为是一个长度为n的码组，若的码组，若则则T (x)也是该编码中的一个码组。也是该编码中的一个码组。 证证 设一循环码为设一循环码为 则有则有 上式中的上式中的T (x) 正是码组正是码组T (x)向左循环移位向左循环移位 i 次的结果。次的结果。例：例： 一循环码为一循环码为1100101，即，即 若给定若给定 i = 3，则有，则有 上式对应的码组为上式对应的码组为0101110，它正是，它正是T(x)向左移向左移3位的结果。位的结果。结论：一个长为结论：一个长为n的循环码必定为按模的循环码必定为按模(xn + 1)运算的一个余式。运算的一个余式。 ）（模) 1()()(nixxTxTx012211)(axaxaxaxTnnnn)()(1102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni1)(256xxxxT）（模) 1()(723535893xxxxxxxxxxTx 循环码的生成循环码的生成 有了生成矩阵有了生成矩阵G，就可以由，就可以由k个信息位得出整个码组：个信息位得出整个码组：例：例：式中，式中，生成矩阵生成矩阵G的每一行都是一个码组。的每一行都是一个码组。 因此，若能找到因此，若能找到 k 个已知的码组，就能构成矩阵个已知的码组，就能构成矩阵G。如。如前所述，这前所述，这k个已知码组必须是线性不相关的。个已知码组必须是线性不相关的。 在循环码中，一个在循环码中，一个(n, k)码有码有2k个不同的码组。若用个不同的码组。若用g(x)表示其中前表示其中前(k-1)位皆为位皆为“0”的码组，则的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这都是码组，而且这k个码组是线性个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵无关的。因此它们可以用来构成此循环码的生成矩阵G。G34560123456aaaaaaaaaaaA0110001101001011001001111000QGkI I 在循环码中除全在循环码中除全“0”码组外，再没有连续码组外，再没有连续k位均为位均为“0”的的码组。否则，在经过若干次循环移位后将得到码组。否则，在经过若干次循环移位后将得到k位信息位位信息位全为全为“0”，但监督位不全为，但监督位不全为“0”的一个码组。这在线性码的一个码组。这在线性码中显然是不可能的。中显然是不可能的。 因此，因此，g(x)必须是一个常数项不为必须是一个常数项不为“0”的的(n - k)次多项式，次多项式，而且这个而且这个g(x)还是这种还是这种(n, k)码中次数为码中次数为(n k)的唯一一个的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续，即连续“0”的个数多于的个数多于(k 1)。显然，这是与前面的。显然，这是与前面的结论矛盾的。结论矛盾的。 我们称这唯一的我们称这唯一的(n k)次多项式次多项式g(x)为码的生成多项式。为码的生成多项式。一旦确定了一旦确定了g(x)，则整个，则整个(n, k)循环码就被确定了。循环码就被确定了。 因此，循环码的生成矩阵因此，循环码的生成矩阵G可以写成可以写成 例：例：上表中的编码为上表中的编码为(7, 3)循环码，循环码，n = 7, k = 3, n k = 4，其中唯一的一个其中唯一的一个(n k) = 4次码多项式代表的码组是第二次码多项式代表的码组是第二码组码组0010111，与它对应的码多项式，即生成多项式，为，与它对应的码多项式，即生成多项式，为g(x) = x4 + x2 + x + 1。 )()()()()(21xgxxgxgxxgxxkkG g(x) = x4 + x2 + x + 1 即即 “1 0 1 1 1”将此将此g(x)代入上矩阵，得到代入上矩阵，得到 或或上式不符合上式不符合G = IkQ形式，所以它不是典型生成矩阵。但它经过线性形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。变换后，不难化成典型阵。此循环码组的多项式表示式此循环码组的多项式表示式T(x)： 上式表明，所有码多项式上式表明，所有码多项式T(x)都能够被都能够被g(x)整除，而且任意一个次整除，而且任意一个次数不大于数不大于(k 1)的多项式乘的多项式乘g(x)都是码多项式。都是码多项式。 )()()()(2xgxxgxgxxG001011101011101011100)(xG)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG 寻求码生成多项式寻求码生成多项式 因为任意一个循环码因为任意一个循环码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) = 1。因此，上。因此，上式可以写成式可以写成）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk将将 T(x) = h(x) g(x) 和和 T (x) = g(x) 代入代入化简后，得到化简后，得到上式表明，生成多项式上式表明，生成多项式g(x)应该是应该是(xn + 1)的一个因子。的一个因子。例：例：(x7 + 1)可以分解为可以分解为为了求出为了求出(7, 3)循环码的生成多项式循环码的生成多项式 g(x)，需要从上式中找到一，需要从上式中找到一个个(n k) = 4次的因子。这样的因子有两个，即次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。以上两式都可以作为生成多项式。 选用的生成多项式不同，产生出的循环码码组也不同。选用的生成多项式不同，产生出的循环码码组也不同。 )() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx 循环码的编码方法循环码的编码方法用用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，则有，则有 上式是用码多项式表示的运算。它和下式等效：上式是用码多项式表示的运算。它和下式等效：编出的码组编出的码组T(x)为：为：T(x) = xn-k m(x) +r(x)在上例中，在上例中，T(x) = 1100000 + 101 = 1100101 )()()()()(xgxrxQxgxmxkn11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn10111101111101111100000 循环码的解码方法循环码的解码方法在检错时：当接收码组没有错码时，接收码组在检错时：当接收码组没有错码时，接收码组R(x)必定能被必定能被g(x)整除，整除，即下式即下式中余项中余项r(x)应为零；否则，有误码。应为零；否则，有误码。当接收码组中的错码数量过多，超出了编码的检错能力时，有错码当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被的接收码组也可能被g(x)整除。这时，错码就不能检出了。整除。这时，错码就不能检出了。 在纠错时：在纠错时：用生成多项式用生成多项式g(x)除接收码组除接收码组R(x)，得出余式，得出余式r(x)。按照余式按照余式r(x)，用查表的方法或计算方法得出错误图样，用查表的方法或计算方法得出错误图样E(x)。从从R(x)中减去中减去E(x)，便得到已经纠正错码的原发送码组，便得到已经纠正错码的原发送码组T(x)。)(/)()()(/)(xgxrxQxgxR截短循环码截短循环码 截短目的：截短目的： 在设计时，通常信息位数在设计时，通常信息位数k、码长、码长n和纠错能力都是预先给定的。但和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。故采用截短码长截短，是，并不一定有恰好满足这些条件的循环码存在。故采用截短码长截短，得出满足要求的编码。得出满足要求的编码。 截短方法：截短方法： 设给定一个设给定一个(n, k)循环码，它共有循环码，它共有2k种码组，现使其前种码组，现使其前i (0 i k)个信息位全为个信息位全为“0”，于是它变成仅有，于是它变成仅有2k-i种码组。然后从中删去这种码组。然后从中删去这 i 位全位全“0”的信息位，最终得到一个的信息位，最终得到一个 (n i，k i)的线性码。将这种码称的线性码。将这种码称为截短循环码。为截短循环码。 截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环码的编解码方法仍和截短前的方法一样。码的编解码方法仍和截短前的方法一样。 例：要求构造一个能够纠正例：要求构造一个能够纠正1位错码的位错码的(13, 9)码。码。 这时可以由这时可以由(15, 11)循环码的循环码的11种码组中选出前两信息位均为种码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。然后在发送时不发送这两位的码组，构成一个新的码组集合。然后在发送时不发送这两位“0”。于。于是发送码组成为是发送码组成为(13, 9)截短循环码。截短循环码。 几种二进制分组码的性能比较几种二进制分组码的性能比较 RS码码 RS码：是码：是q进制进制BCH码的一个特殊子类，并且具有很强的纠码的一个特殊子类，并且具有很强的纠错能力。错能力。 RS码的参数：码长码的参数：码长n = q 1，监督位数目，监督位数目r = 2t，其中，其中t是能是能够纠正的错码数目；其生成多项式为够纠正的错码数目；其生成多项式为g(x) = (x + )(x + 2) (x + 2t)式中，式中， 为伽罗华域为伽罗华域GF(2m)中的本原元。中的本原元。 RS码的主要优点：码的主要优点： 它是多进制纠错编码，所以特别适合用于多进制调制的场它是多进制纠错编码，所以特别适合用于多进制调制的场合；合； 它能够纠正它能够纠正t个个q位二进制错码，即能够纠正不超过位二进制错码，即能够纠正不超过q个连个连续的二进制错码，所以适合在衰落信道中纠正突发性错码。续的二进制错码，所以适合在衰落信道中纠正突发性错码。 卷积码卷积码 卷积码的特点：卷积码的特点： 监督码元不仅和当前的监督码元不仅和当前的k比特信息段有关，而且还同前面比特信息段有关，而且还同前面m = (N 1)个信息段有关。个信息段有关。 将将N称为码组的约束长度。称为码组的约束长度。 将卷积码记作将卷积码记作(n, k, m)，其码率为，其码率为k/n。 卷积码的编码卷积码的编码 一般原理方框图一般原理方框图 卷积码编码器的实例方框图：卷积码编码器的实例方框图：(n, k, m) =（3, 1, 2） 每当输入每当输入1比特时，此编码器输出比特时，此编码器输出3比特比特c1c2 c3： 编码器的工作状态编码器的工作状态 321331211bbbcbbcbcm序列序列 m序列是最长线性反馈移位寄存器序列序列是最长线性反馈移位寄存器序列 移位脉冲节拍 第1级输出 第2级输出 第3级输出 反馈值 0 0 0 1 1 1 1 0 0 1 2 1 1 0 1 3 1 1 1 0 4 0 1 1 1 5 1 0 1 0 6 0 1 0 0 7 0 0 1 1 8 1 0 0 1 9 1 1 0 1 10 1 1 1 0 11 0 1 1 1 12 1 0 1 0 13 0 1 0 0 14 0 0 1 1 n级线性反馈移位寄存器级线性反馈移位寄存器 D1 D2 Dn-1 Dn cn=1 cn-1 c2 c1 1na 2na 1a 0a 图 8-13 n 级线性反馈移位寄存器 na 1122330nnnnnac ac ac ac aLniiinnxcxcxccxf010.)(特征多项式特征多项式常用的本原多项式常用的本原多项式 n 本原多项式 n 本原多项式 代数式 8进制表示 代数式 8进制表示 2 21xx 7 8 84321xxxx 435 3 31xx 13 9 941xx 1021 4 41xx 23 10 1031xx 2011 5 521xx 45 11 1121xx 4005 6 61xx 103 12 12641xxxx 10123 7 731xx 211 13 13431xxxx 20033 扰码与解扰扰码与解扰例例8-5 设设m序列发生器的本原多项式为：序列发生器的本原多项式为： ，由该，由该m序列发生器构成的扰码和解扰器。序列发生器构成的扰码和解扰器。 1.画出扰码器和解扰器的方框图画出扰码器和解扰器的方框图 2.若输入信号为若输入信号为“11101001010”，求扰码器的输出序列。，求扰码器的输出序列。53( )1f xxx