1、第九章 差错控制编码2023年2月8日2基本内容基本内容 引言引言 纠错编码原理纠错编码原理 常用简单编码常用简单编码 线性分组码线性分组码 循环码循环码2023年2月8日39.1 引言引言随机信道：错码出现是随机的，错码之间统计独立。随机信道：错码出现是随机的，错码之间统计独立。突发信道：错码成串集中出现，（脉冲干扰）。突发信道：错码成串集中出现，（脉冲干扰）。混合信道：既存在随机错码，又存在突发错码。混合信道：既存在随机错码，又存在突发错码。码间干扰可以用均衡的办法来纠正码间干扰可以用均衡的办法来纠正,但不可能很但不可能很彻底；至于加性干扰则是不可避免的；彻底；至于加性干扰则是不可避免的；
2、当误码不可避免时，可以考虑差错控制编码；当误码不可避免时，可以考虑差错控制编码；根据错码分布规律的不同，将信道分为三类：根据错码分布规律的不同，将信道分为三类：2023年2月8日49.1 引言引言差错控制方法：差错控制方法：检错重发检错重发(ARQ)；前向纠错前向纠错(FEC)；反馈校验法反馈校验法；混合纠错混合纠错(HEC)；差错删除法；差错删除法；差错控制编码：差错控制编码：在信息码中加入监督码；在信息码中加入监督码；以降低信息传输速率为代价来换取传输以降低信息传输速率为代价来换取传输可靠性的提高。可靠性的提高。多余度：增加的码元数目除以总码元数多余度：增加的码元数目除以总码元数目；目；2
3、023年2月8日59.2 纠错编码的基本原理纠错编码的基本原理分组码：分组码：每组信息码附加若干监督码的编每组信息码附加若干监督码的编码集合。在分组码中，监督码元仅监督本码集合。在分组码中，监督码元仅监督本码组中的信息码元。用码组中的信息码元。用(n，k)表示表示。an-1an-2arar-1a0krn码重：码重：码组中非零码元的数目。码组中非零码元的数目。码距：码距：两码组中对应码位上具有不同二进制码两码组中对应码位上具有不同二进制码元的位数。元的位数。2023年2月8日6最小码距的有关结论：最小码距的有关结论：在一个码组内检测在一个码组内检测e个误码，要求最小码距个误码，要求最小码距1mi
4、ned在一个码组内纠正在一个码组内纠正t个误码，要求最小码距个误码，要求最小码距12min td在一个码组内纠正在一个码组内纠正t个误码，同时检测个误码，同时检测e个误码个误码(et)，要求最小码距要求最小码距1minetd2023年2月8日7差错编码的效果差错编码的效果假设随机信道发送假设随机信道发送0时的错误概率和发送时的错误概率和发送1时的时的错误概率相等，均为错误概率相等，均为p1，则在码长为，则在码长为N的码的码组中发生组中发生r个错误的概率为：个错误的概率为：rnrrnnppCrP)1()(当当n=7，p=0.001，有：有：875737105.3)3(101.2)2(,107)1
5、(ppp2023年2月8日89.3 常用的简单编码常用的简单编码奇偶监督码：奇偶监督码：偶校验：偶校验：奇校验：奇校验：0021aaann1021aaann特点：特点：奇偶校验只能发现单个或奇数个错码，而奇偶校验只能发现单个或奇数个错码，而不能检测出偶数个错码。所以检错能力不高，奇不能检测出偶数个错码。所以检错能力不高，奇偶校验的最小码距偶校验的最小码距dmin=2。适应于检测随机错误适应于检测随机错误。2023年2月8日9二维奇偶监督码（水平垂直奇偶监督位）：二维奇偶监督码（水平垂直奇偶监督位）：012102010121212221111211ccccaaaaaaaaaaaannmmmnmn
6、nnnn特点：特点：可能检测出偶数个错码。有些偶数错码不可可能检测出偶数个错码。有些偶数错码不可能检测出，如构成矩形的能检测出，如构成矩形的4个错码。个错码。适应于检测突发错码适应于检测突发错码。2023年2月8日10恒比码：恒比码：定义：从某确定码长的码组中排选那些定义：从某确定码长的码组中排选那些“1”和和“0”的比例为恒定值的码组作为许用码组。的比例为恒定值的码组作为许用码组。7中取中取3 5中取中取3 特点：特点：能发现所有单个错误和奇数个错误。能发现所有单个错误和奇数个错误。正反码：正反码：是一种简单的能够纠正错误的编是一种简单的能够纠正错误的编码。其中的监督位数目码。其中的监督位数
7、目=信息位数目。监信息位数目。监督码元与信息码元相同或者相反，由信息督码元与信息码元相同或者相反，由信息码中码中“1”的个数而定。的个数而定。2023年2月8日11（1）当信息位中有奇数个）当信息位中有奇数个“1”时，监督码为正码。时，监督码为正码。（2）当信息位中有偶数个）当信息位中有偶数个“1”时，监督码为反码。时，监督码为反码。（1）信息位）信息位+监督位监督位=合成码组（产生校验码组）。合成码组（产生校验码组）。（2）接收码组的信息位中有奇数个）接收码组的信息位中有奇数个“1”，则合成，则合成码组码组=校验码组；接收码组的信息位中有偶数个校验码组；接收码组的信息位中有偶数个“1”，则合
8、成码组的反码，则合成码组的反码=校验码组；校验码组；（3）观察校验码组中）观察校验码组中“1”的个数，可知错码情况。的个数，可知错码情况。接收端译码方法：接收端译码方法：2023年2月8日12正反码举例正反码举例1100111001 正确正确1000111001 左边第二位为错码左边第二位为错码1100101001 监督位中第一位为错码监督位中第一位为错码1001111001 错码多于一个错码多于一个特点：这种长度为特点：这种长度为10的正反码具有纠正的正反码具有纠正一位错码的能力，并能检测全部两位以一位错码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。下的错码和大部分两位以上的错
9、码。2023年2月8日139.4 线性分组码线性分组码定义定义：信息码元与监督码元由线性方程联系起来。：信息码元与监督码元由线性方程联系起来。性质性质：（1）封闭性：任意两许用码组之和仍为一许用码组；）封闭性：任意两许用码组之和仍为一许用码组；（2）最小码距）最小码距=非零码的最小重量。非零码的最小重量。一、简单线性分组码（奇偶监督码）一、简单线性分组码（奇偶监督码）021aaann偶数监督码：021 aaasnn在接收端计算：，则有错。，则无错；若若10ss2023年2月8日14监督码元的位数要求监督码元的位数要求关于校正子关于校正子S,如果只有一位，则只能用来判断如果只有一位，则只能用来判
10、断对或者错，无法纠正；对或者错，无法纠正；如果有两位校正子，则有四种组合，除了一种如果有两位校正子，则有四种组合，除了一种表示没有错误之外，还有三种可以表示以为错表示没有错误之外，还有三种可以表示以为错误的三个可能位置。误的三个可能位置。因此，假设码长为因此，假设码长为n，监督位数为，监督位数为r，则可以纠，则可以纠正一位错码时，必须满足：正一位错码时，必须满足：1212rknrr或者2023年2月8日15二、（二、（7，4）线性分组码（奇偶监督码）线性分组码（奇偶监督码）0a错码位置错码位置321sss错码位置错码位置0010101000111a2a3a1011101110004a5a6a无
11、错无错321sss0346313562245616542116542,0;1,aaaasaaaasaaaasaaaassaaaa构成偶位监督关系。即否则时，校正子在可见，仅当一错码位置2023年2月8日16000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa 给定信息位，可直接按上式计算出监督位（给定信息位，可直接按上式计算出监督位（P289表表9-5）。）。根据监督位可判断错码情况。如：收到码组为根据监督位可判断错码情况。如：收到码组为0000011；因为；因为s1s2s3=011，故故a3位有错码。位有错码。（7，4）汉明码的最小码距）汉明
12、码的最小码距d0=3，所以能纠正一位错码或所以能纠正一位错码或检测两个错码。汉明码是一种高效码。检测两个错码。汉明码是一种高效码。nrrrnkrrr112112122023年2月8日17三、监督矩阵三、监督矩阵分组码的监督方程分组码的监督方程矩阵形式矩阵形式000034613562456aaaaaaaaaaaa0001001101010101100101110123456Taaaaaaa00TTTHAAH或者记为：2023年2月8日18100110101010110010111rIPH监督矩阵：典型形式监督矩阵。阶单位方阵。：阶矩阵；：HrrIkrPr 由典型形式监督矩阵及信息码元很容易算出各
13、监由典型形式监督矩阵及信息码元很容易算出各监督码元。即用信息位的行矩阵乘督码元。即用信息位的行矩阵乘Q矩阵得到监督位。矩阵得到监督位。TPQ 2023年2月8日19四、生成矩阵四、生成矩阵3456012110110110111aaaaaaa Qaaaaaaaaaaa34563456012110101011111或TPQrkQ 阶矩阵；：2023年2月8日201101000101010001100101110001QIGk生成矩阵：Gaaaaaaaaaaa34560123456个码组，即由生成矩阵可以产生整典型生成矩阵典型生成矩阵：具有：具有IkQ形式的生成矩阵。形式的生成矩阵。系统码系统码：信
14、息位不变，监督位附加于其后的纠错编码。：信息位不变，监督位附加于其后的纠错编码。2023年2月8日21G矩阵性质矩阵性质与与H矩阵类似，要求矩阵类似，要求G矩阵的各行是线性矩阵的各行是线性无关的。无关的。G矩阵的各行本身就是一个码组。因此，矩阵的各行本身就是一个码组。因此，如果已有如果已有k个线性无关的码组，则可以用个线性无关的码组，则可以用其作为生成矩阵其作为生成矩阵G，并由它生成其余的码，并由它生成其余的码组。组。2023年2月8日22五、校正子五、校正子021021021eeeABEbbbBaaaAnnnnnn，则收发码组之差为：，接收码组为设发送码组为iiiiiiabieabie位有错
15、表示位无错表示10TTTTTHEHEHAHEAHBS)(校正子2023年2月8日23线性码的性质线性码的性质封闭性：任意一种线性码中的任意两个封闭性：任意一种线性码中的任意两个码组之和仍为这种码组之中的一个码组。码组之和仍为这种码组之中的一个码组。因此，两个码组之间的距离必是另一码因此，两个码组之间的距离必是另一码组的重量。组的重量。线性码又称为群码。线性码又称为群码。2023年2月8日24六、汉明码：六、汉明码：(纠正单个错误的线性分组码纠正单个错误的线性分组码)特点：特点：码长：码长：最小码距：最小码距：d=3 信息码位：信息码位：纠错能力：纠错能力：t=1 监督码位：监督码位：r=n-k
16、给定给定r，即可构造出具体的汉明码即可构造出具体的汉明码(n，k)。12 rn12rkr2023年2月8日259.5 循环码循环码一、循环码的特点：一、循环码的特点：（1）封闭性：任意两许用码组之和仍为一许用码组；）封闭性：任意两许用码组之和仍为一许用码组；（2）循环性：循环码中任意许用码组经循环移位后得）循环性：循环码中任意许用码组经循环移位后得到的码组仍为一许用码组。不论左移或右移，移位位到的码组仍为一许用码组。不论左移或右移，移位位数多少，其结果均为循环码组。数多少，其结果均为循环码组。二、循环码的原理：二、循环码的原理：1 多项式按模运算多项式按模运算PnmnPQnmmod)(2023
17、年2月8日26)(mod()()()()()()(xNxRxFxRxQxNxF则可写成：对于多项式：注意注意：码多项式系数按模：码多项式系数按模2运算，即只取运算，即只取0、1；模；模2运算中，运算中，加法代替减法。加法代替减法。结论结论：一个长为：一个长为n的循环码，它必为按模的循环码，它必为按模 运算的一运算的一个余式。个余式。)1(nx.)1()()(码组运算下，也是一个许用在按模是许用码组，则在循环码中，若nixxTxxT2023年2月8日272 循环码的生成矩阵循环码的生成矩阵nkkkxgxxgxgxxgxxG)()()()()(21 首先找到码生成多项式首先找到码生成多项式g(x)
18、：g(x)是唯一一个是唯一一个(n-k)次多项式；次多项式；g(x)的常数项不为零；的常数项不为零；g(x)是是xn+1的一个因式。的一个因式。2023年2月8日28生成矩阵生成矩阵G的性质的性质这个时候的这个时候的G往往不是典型的，但是可以通过线往往不是典型的，但是可以通过线性变换化为典型的。性变换化为典型的。此时：此时：)().(,.,)(2111xgaxaxaGaaaxTrknknrnn可见，所有码多项式可见，所有码多项式T(xT(x)都可被都可被g g（x x）整除，）整除，而且任一次数不大于（而且任一次数不大于（k-1k-1）的多项式乘以）的多项式乘以g g（x x）都是码多项式。）
19、都是码多项式。2023年2月8日293 如何寻找任意如何寻找任意(n，k)循环码的生成多项式。循环码的生成多项式。)()()()()(xgxTxgxhxT1)()(1)(nnkxxTxQxxTx)()1()(1)(xTxxTxxQnk)()(1xhxxgxkn结论结论：生成多项式：生成多项式g(x)是是xn+1的一个的一个(n-k)次因式。次因式。2023年2月8日30三、循环码编、解码方法：三、循环码编、解码方法：；乘用)()1(xmxkn)()()()()()()()()()2(xgxrxQxgxmxxrxQxmxxgknkn；，得除用。编出码组)()3(xT)()()(xrxmxxTkn
20、D1D2+D3+输入校验位码字输出编码：编码：2023年2月8日31译码比编码复杂译码比编码复杂译码三步译码三步校正子s的计算由s得到错误图样纠正发送码组发送码组 接收码组接收码组误差码组误差码组 校正子只与校正子只与 E 有关，译码的根本在于计算校正子有关，译码的根本在于计算校正子021aaaAnn021bbbBnnEABEABTTTTT)(EHEHAHHEAHBS2023年2月8日32校正子校正子S的计算的计算生成多项式生成多项式 g(x)去除接收码字去除接收码字B(x)(Mod)()(xgxBxS2023年2月8日33四、缩短循环码：四、缩短循环码：(n,k)(n-i,k-i)如如(15
21、,11)(12,8)监督矩阵监督矩阵 Hi 是将原是将原 H 的前的前 3 列列 去掉去掉缩短汉明码的最小码距至少和原来码的码距相缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。同，因为监督位没有变。2023年2月8日34BCH 码码定义定义:一类能纠正多个随机错误的循环码。分为本原一类能纠正多个随机错误的循环码。分为本原BCH码码和非本原和非本原BCH码。码。),(),(),(LCM)(1231xmxmxmxgt生成多项式的本原多项式。含有最高次数为中不项式的一个因子，其生成多是的码长码原次的本原多项式；非本含有最高次数为中，其生成多项式码的码长为本原mxgnBCHmxgBCH
22、mm)(12)(122023年2月8日35纠正纠正 3 个错误，码长为个错误，码长为15的的BCH码码解：解：n=15,m=5 查表查表9-8得，得，2467 这是这是(15,5)码。码。1)(245810 xxxxxxxg2023年2月8日36表表99中最重要的中最重要的BCH码是码是(23,12)，称为格，称为格雷码，码间为雷码，码间为7，能纠正，能纠正3个错误。个错误。生成多项式生成多项式在实际通信系统中，所要求的在实际通信系统中，所要求的n、k并不是码表并不是码表中所推荐的值，在这时我们可以采用缩短或扩中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号展的
23、方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。验位来减少码组长度。1)(567911DDDDDDDg重要的重要的BCHBCH码码 (23,12)2023年2月8日37里德里德-索洛蒙码（索洛蒙码（RS）RS码的生成多项式为：码的生成多项式为：中的本原元为伽罗华域其中)2().()()(22mtGFxxxxgRS码的应用：码的应用：第一，由于采用了第一，由于采用了q进制，所以它是多进制调制进制，所以它是多进制调制时的自然和方便的编码手段时的自然和方便的编码手段第二，第二，RS码也被应用在计算机存储系统中，以码也被应用在计算机存储系统中，以克服系统中存在的差错串。克服系统中存在的差错串。
