第九章差错控制编码课件

第九章 差错控制编码2024/7/131基本内容基本内容 引言引言 纠错编码原理纠错编码原理 常用简单编码常用简单编码 线性分组码线性分组码 循环码循环码2024/7/1329.1 引言引言随机信道：错码出现是随机的，错码之间统计独立。随机信道：错码出现是随机的，错码之间统计独立。突发信道：错码成串集中出现，（脉冲干扰）。突发信道：错码成串集中出现，（脉冲干扰）。混合信道：既存在随机错码，又存在突发错码。混合信道：既存在随机错码，又存在突发错码。码间干扰可以用均衡的办法来纠正码间干扰可以用均衡的办法来纠正,但不可能很但不可能很彻底；至于加性干扰则是不可避免的；彻底；至于加性干扰则是不可避免的；当误码不可避免时，可以考虑差错控制编码；当误码不可避免时，可以考虑差错控制编码；根据错码分布规律的不同，将信道分为三类：根据错码分布规律的不同，将信道分为三类：2024/7/1339.1 引言引言差错控制方法：差错控制方法：检错重发检错重发(ARQ)；前向纠错前向纠错(FEC)；反馈校验法反馈校验法；混合纠错混合纠错(HEC)；差错删除法；差错删除法；差错控制编码：差错控制编码：在信息码中加入监督码；在信息码中加入监督码；以降低信息传输速率为代价来换取传输以降低信息传输速率为代价来换取传输可靠性的提高。可靠性的提高。多余度：增加的码元数目除以总码元数多余度：增加的码元数目除以总码元数目；目；2024/7/1349.2 纠错编码的基本原理纠错编码的基本原理分组码：分组码：每组信息码附加若干监督码的编每组信息码附加若干监督码的编码集合。在分组码中，监督码元仅监督本码集合。在分组码中，监督码元仅监督本码组中的信息码元。用码组中的信息码元。用(n，k)表示表示。an-1an-2arar-1a0krn码重：码重：码组中非零码元的数目。码组中非零码元的数目。码距：码距：两码组中对应码位上具有不同二进制码元两码组中对应码位上具有不同二进制码元的位数。的位数。2024/7/135最小码距的有关结论：最小码距的有关结论：在一个码组内检测在一个码组内检测e个误码，要求最小码距个误码，要求最小码距在一个码组内纠正在一个码组内纠正t个误码，要求最小码距个误码，要求最小码距在一个码组内纠正在一个码组内纠正t个误码，同时检测个误码，同时检测e个误码个误码(et)，要求最小码距要求最小码距2024/7/136差错编码的效果差错编码的效果假设随机信道发送假设随机信道发送0时的错误概率和发送时的错误概率和发送1时的时的错误概率相等，均为错误概率相等，均为p1，则在码长为，则在码长为N的码的码组中发生组中发生r个错误的概率为：个错误的概率为：当当n=7，p=0.001，有：有：2024/7/1379.3 常用的简单编码常用的简单编码奇偶监督码：奇偶监督码：偶校验：偶校验：奇校验：奇校验：特点：特点：奇偶校验只能发现单个或奇数个错码，而奇偶校验只能发现单个或奇数个错码，而不能检测出偶数个错码。所以检错能力不高，奇不能检测出偶数个错码。所以检错能力不高，奇偶校验的最小码距偶校验的最小码距dmin=2。适应于检测随机错误适应于检测随机错误。2024/7/138二维奇偶监督码（水平垂直奇偶监督位）：二维奇偶监督码（水平垂直奇偶监督位）：特点：特点：可能检测出偶数个错码。有些偶数错码不可可能检测出偶数个错码。有些偶数错码不可能检测出，如构成矩形的能检测出，如构成矩形的4个错码。个错码。适应于检测突发错码适应于检测突发错码。2024/7/139恒比码：恒比码：定义：从某确定码长的码组中排选那些定义：从某确定码长的码组中排选那些“1”和和“0”的比例为恒定值的码组作为许用码组。的比例为恒定值的码组作为许用码组。7中取中取3 5中取中取3 特点：特点：能发现所有单个错误和奇数个错误。能发现所有单个错误和奇数个错误。正反码：正反码：是一种简单的能够纠正错误的编是一种简单的能够纠正错误的编码。其中的监督位数目码。其中的监督位数目=信息位数目。监信息位数目。监督码元与信息码元相同或者相反，由信息督码元与信息码元相同或者相反，由信息码中码中“1”的个数而定。的个数而定。2024/7/1310（1）当信息位中有奇数个）当信息位中有奇数个“1”时，监督码为正码。时，监督码为正码。（2）当信息位中有偶数个）当信息位中有偶数个“1”时，监督码为反码。时，监督码为反码。（1）信息位）信息位+监督位监督位=合成码组（产生校验码组）。合成码组（产生校验码组）。（2）接收码组的信息位中有奇数个）接收码组的信息位中有奇数个“1”，则合成，则合成码组码组=校验码组；接收码组的信息位中有偶数个校验码组；接收码组的信息位中有偶数个“1”，则合成码组的反码，则合成码组的反码=校验码组；校验码组；（3）观察校验码组中）观察校验码组中“1”的个数，可知错码情况。的个数，可知错码情况。接收端译码方法：接收端译码方法：2024/7/1311正反码举例正反码举例1100111001 正确正确1000111001 左边第二位为错码左边第二位为错码1100101001 监督位中第一位为错码监督位中第一位为错码1001111001 错码多于一个错码多于一个特点：这种长度为特点：这种长度为10的正反码具有纠正的正反码具有纠正一位错码的能力，并能检测全部两位以一位错码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。下的错码和大部分两位以上的错码。2024/7/13129.4 线性分组码线性分组码定义定义：信息码元与监督码元由线性方程联系起来。：信息码元与监督码元由线性方程联系起来。性质性质：（1）封闭性：任意两许用码组之和仍为一许用码组；）封闭性：任意两许用码组之和仍为一许用码组；（2）最小码距）最小码距=非零码的最小重量。非零码的最小重量。一、简单线性分组码（奇偶监督码）一、简单线性分组码（奇偶监督码）2024/7/1313监督码元的位数要求监督码元的位数要求关于校正子关于校正子S,如果只有一位，则只能用来判断对如果只有一位，则只能用来判断对或者错，无法纠正；或者错，无法纠正；如果有两位校正子，则有四种组合，除了一种表如果有两位校正子，则有四种组合，除了一种表示没有错误之外，还有三种可以表示以为错误的示没有错误之外，还有三种可以表示以为错误的三个可能位置。三个可能位置。因此，假设码长为因此，假设码长为n，监督位数为，监督位数为r，则可以纠，则可以纠正一位错码时，必须满足：正一位错码时，必须满足：2024/7/1314二、（二、（7，4）线性分组码（奇偶监督码）线性分组码（奇偶监督码）错码位置错码位置错码位置错码位置001010100011101110111000无错无错2024/7/1315 给定信息位，可直接按上式计算出监督位（给定信息位，可直接按上式计算出监督位（P289表表9-5）。）。根据监督位可判断错码情况。如：收到码组为根据监督位可判断错码情况。如：收到码组为0000011；因为；因为s1s2s3=011，故故a3位有错码。位有错码。（7，4）汉明码的最小码距）汉明码的最小码距d0=3，所以能纠正一位错码或所以能纠正一位错码或检测两个错码。汉明码是一种高效码。检测两个错码。汉明码是一种高效码。2024/7/1316三、监督矩阵三、监督矩阵分组码的监督方程分组码的监督方程矩阵形式矩阵形式2024/7/1317 由典型形式监督矩阵及信息码元很容易算出各监督由典型形式监督矩阵及信息码元很容易算出各监督码元。即用信息位的行矩阵乘码元。即用信息位的行矩阵乘Q矩阵得到监督位。矩阵得到监督位。2024/7/1318四、生成矩阵四、生成矩阵2024/7/1319典型生成矩阵典型生成矩阵：具有：具有IkQ形式的生成矩阵。形式的生成矩阵。系统码系统码：信息位不变，监督位附加于其后的纠错编码。：信息位不变，监督位附加于其后的纠错编码。2024/7/1320G矩阵性质矩阵性质与与H矩阵类似，要求矩阵类似，要求G矩阵的各行是线性矩阵的各行是线性无关的。无关的。G矩阵的各行本身就是一个码组。因此，矩阵的各行本身就是一个码组。因此，如果已有如果已有k个线性无关的码组，则可以用个线性无关的码组，则可以用其作为生成矩阵其作为生成矩阵G，并由它生成其余的码，并由它生成其余的码组。组。2024/7/1321五、校正子五、校正子2024/7/1322线性码的性质线性码的性质封闭性：任意一种线性码中的任意两个封闭性：任意一种线性码中的任意两个码组之和仍为这种码组之中的一个码组。码组之和仍为这种码组之中的一个码组。因此，两个码组之间的距离必是另一码因此，两个码组之间的距离必是另一码组的重量。组的重量。线性码又称为群码。线性码又称为群码。2024/7/1323六、汉明码：六、汉明码：(纠正单个错误的线性分组码纠正单个错误的线性分组码)特点：特点：码长：码长：最小码距：最小码距：d=3 信息码位：信息码位：纠错能力：纠错能力：t=1 监督码位：监督码位：r=n-k给定给定r，即可构造出具体的汉明码即可构造出具体的汉明码(n，k)。2024/7/13249.5 循环码循环码一、循环码的特点：一、循环码的特点：（1）封闭性：任意两许用码组之和仍为一许用码组；）封闭性：任意两许用码组之和仍为一许用码组；（2）循环性：循环码中任意许用码组经循环移位后得）循环性：循环码中任意许用码组经循环移位后得到的码组仍为一许用码组。不论左移或右移，移位位到的码组仍为一许用码组。不论左移或右移，移位位数多少，其结果均为循环码组。数多少，其结果均为循环码组。二、循环码的原理：二、循环码的原理：1 多项式按模运算多项式按模运算2024/7/1325注意注意：码多项式系数按模：码多项式系数按模2运算，即只取运算，即只取0、1；模；模2运算中，运算中，加法代替减法。加法代替减法。结论结论：一个长为：一个长为n的循环码，它必为按模的循环码，它必为按模 运算的一运算的一个余式。个余式。2024/7/13262 循环码的生成矩阵循环码的生成矩阵 首先找到码生成多项式首先找到码生成多项式g(x)：g(x)是唯一一个是唯一一个(n-k)次多项式；次多项式；g(x)的常数项不为零；的常数项不为零；g(x)是是xn+1的一个因式。的一个因式。2024/7/1327生成矩阵生成矩阵G的性质的性质这个时候的这个时候的G往往不是典型的，但是可以通过线往往不是典型的，但是可以通过线性变换化为典型的。性变换化为典型的。此时：此时：可见，所有码多项式可见，所有码多项式T(x)T(x)都可被都可被g g（x x）整除，）整除，而且任一次数不大于（而且任一次数不大于（k-1k-1）的多项式乘以）的多项式乘以g g（x x）都是码多项式。）都是码多项式。2024/7/13283 如何寻找任意如何寻找任意(n，k)循环码的生成多项式。循环码的生成多项式。结论结论：生成多项式：生成多项式g(x)是是xn+1的一个的一个(n-k)次因式。次因式。2024/7/1329三、循环码编、解码方法：三、循环码编、解码方法：编码：编码：2024/7/1330译码比编码复杂译码比编码复杂译码三步译码三步校正子s的计算由s得到错误图样纠正发送码组发送码组 接收码组接收码组误差码组误差码组校正子只与校正子只与 E 有关，译码的根本在于计算校正子有关，译码的根本在于计算校正子2024/7/1331校正子校正子S的计算的计算生成多项式生成多项式 g(x)去除接收码字去除接收码字B(x)2024/7/1332四、缩短循环码：四、缩短循环码：(n,k)(n-i,k-i)如如(15,11)(12,8)监督矩阵监督矩阵 Hi 是将原是将原 H 的前的前 3 列列 去掉去掉缩短汉明码的最小码距至少和原来码的码距相缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。同，因为监督位没有变。2024/7/1333BCH 码码定义定义:一类能纠正多个随机错误的循环码。分为本原一类能纠正多个随机错误的循环码。分为本原BCH码码和非本原和非本原BCH码。码。2024/7/1334纠正纠正 3 个错误，码长为个错误，码长为15的的BCH码码解：解：n=15,m=5 查表查表9-8得，得，2467 这是这是(15,5)码。码。2024/7/1335表表99中最重要的中最重要的BCH码是码是(23,12)，称为格，称为格雷码，码间为雷码，码间为7，能纠正，能纠正3个错误。个错误。生成多项式生成多项式在实际通信系统中，所要求的在实际通信系统中，所要求的n、k并不是码表并不是码表中所推荐的值，在这时我们可以采用缩短或扩中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。验位来减少码组长度。重要的重要的BCHBCH码码 (23,12)2024/7/133637写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits谢谢大家荣幸这一路，与你同行ItS An Honor To Walk With You All The Way讲师：XXXXXX XX年XX月XX日