第11-差错控制编码课件

第第1111章章 差错控制编码差错控制编码通信原理2024/7/121本章内容目的要求本章内容目的要求教学要求教学要求:了解差错控制编码的基本方法和基本原理，掌握线性分组码的一般构造原理及汉明码、循环码、卷积码的概念。理解序列的产生原理、性质及数字加密的概念。内容提要内容提要:差错控制的基本方式及信道编码的概念；检错码；线性分组码；卷积码；m序列；数字加密基本方法介绍。重点重点：汉明码的生成矩阵、监督矩阵的计算；循环码的生成矩阵、监督矩阵的计算。难点：难点：卷积码的原理。第第1111章章 差错控制编码差错控制编码通信原理2024/7/12211.1 概述概述 11.1.1 信道编码信道编码 信元编码：信元编码：为了提高数字信号传输的为了提高数字信号传输的有效性有效性而采取的编码。而采取的编码。信道编码：信道编码：为了提高数字通信的为了提高数字通信的可靠可靠性性而采取的编码。而采取的编码。信道编码方法：信道编码方法：在信息序列上附加上在信息序列上附加上一些监督码元，发现和纠正错误。一些监督码元，发现和纠正错误。第第1111章章 差错控制编码差错控制编码通信原理2024/7/123 11.1.2 差错控制方式差错控制方式 第第1111章章 差错控制编码差错控制编码通信原理2024/7/124 1、检错重发方式：、检错重发方式：检错重发（检错重发（ARQ）的优点主要表现在：）的优点主要表现在：（1）只需要少量的冗余码，就可以得到）只需要少量的冗余码，就可以得到极低的输出误码率；极低的输出误码率；（2）有一定的自适应能力；有一定的自适应能力；某些不足主要表现在：某些不足主要表现在：（1）需要反向信道，故不能用于单向传需要反向信道，故不能用于单向传输系统，并且实现重发控制比较复杂；输系统，并且实现重发控制比较复杂；（2）通信效率低，）通信效率低，不适合严格实时传输不适合严格实时传输系统。系统。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1252、前向纠错、前向纠错 发送端经信道编码后可以发出具有纠错发送端经信道编码后可以发出具有纠错能力的码字；接收端译码后不仅可以发现错能力的码字；接收端译码后不仅可以发现错误码，而且可以判断错误码的位置并予以自误码，而且可以判断错误码的位置并予以自动纠正。动纠正。3、混合纠错方式、混合纠错方式 混合纠错方式是前向纠错方式和检错重混合纠错方式是前向纠错方式和检错重发方式的结合。发方式的结合。第第1111章章 差错控制编码差错控制编码通信原理2024/7/126 11.1.3 纠错编码的分类纠错编码的分类 （1）按照信道编码的不同功能，可以将它分）按照信道编码的不同功能，可以将它分为检错码和纠错码。为检错码和纠错码。（2）按照信息码元和监督码元之间的检验关按照信息码元和监督码元之间的检验关系，可以将它分为线性和非线性码。系，可以将它分为线性和非线性码。（3）按照信息码元和监督码元之间的约束方按照信息码元和监督码元之间的约束方式不同，可以将它分为分组码和卷积码。式不同，可以将它分为分组码和卷积码。（4）按照信息码元在编码后是否保持原来的按照信息码元在编码后是否保持原来的形式，可以将它分为系统码和非系统码。形式，可以将它分为系统码和非系统码。第第1111章章 差错控制编码差错控制编码通信原理2024/7/127 （5）按照纠正错误的类型不同，可以将按照纠正错误的类型不同，可以将它分为纠正随机错误码和纠正突发错误码它分为纠正随机错误码和纠正突发错误码。随着数字通信系统的发展，可以将信道随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是编码器和调制器统一起来综合设计，这就是所谓的网格编码调制。所谓的网格编码调制。11.1.4 纠错编码的基本原理纠错编码的基本原理 1、分组码、分组码 表示为表示为（n，k）,n表示码组的长度；表示码组的长度；k信息的长度；信息的长度；r=n-k表示监督位长度。表示监督位长度。几个概念：几个概念：第第1111章章 差错控制编码差错控制编码通信原理2024/7/128 码长：码长：码字中码元的数目；码字中码元的数目；码重：码重：码字中非码字中非0数字的数目；数字的数目；码码距距：两两个个等等长长码码字字之之间间对对应应位位不不同同的的数目，有时也称作这两个码字的汉明距离。数目，有时也称作这两个码字的汉明距离。最最小小码码距距：在在码码字字集集合合中中全全体体码码字字之之间间距离的最小数值。距离的最小数值。纠纠错错码码的的抗抗干干扰扰能能力力完完全全取取决决于于许许用用码码字字之之间间的的距距离离，码码的的最最小小距距离离越越大大，说说明明码码字间的最小差别越大，抗干扰能力就越强。字间的最小差别越大，抗干扰能力就越强。第第1111章章 差错控制编码差错控制编码通信原理2024/7/129 分组码的分组码的最小汉明距离为最小汉明距离为d0 2、检错和纠错能力、检错和纠错能力 （1）当码字用于检测错误时，如果要）当码字用于检测错误时，如果要检检测测e个错误个错误，则，则 d0 e+1；（2）当码字用于纠正错误时，如果要当码字用于纠正错误时，如果要纠纠正正t个错误个错误，则，则 d0 2t+1；（3）若码字用于纠若码字用于纠t个错误，同时检个错误，同时检e个个错误时（错误时（e t），则），则 d0 t+e+1。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1210编码效率编码效率Rc可以用下式表示：可以用下式表示：第第1111章章 差错控制编码差错控制编码通信原理2024/7/121111.2 常用的几种简单分组码常用的几种简单分组码 11.2.1 奇偶监督码奇偶监督码 可以表示成为（可以表示成为（n，n-1）。如果是）。如果是奇奇监督码监督码，在附加上一个监督元以后，码长，在附加上一个监督元以后，码长为为n的码字中的码字中“1”的个数为奇数个；如果的个数为奇数个；如果是是偶监督码偶监督码，在附加上一个监督元以后，在附加上一个监督元以后，码长为码长为n的码字中的码字中“1”的个数为偶数个。的个数为偶数个。an-1+an-2+a1+a0=0 第第1111章章 差错控制编码差错控制编码通信原理2024/7/1212 奇偶监督码的编码可以用软件实现，也奇偶监督码的编码可以用软件实现，也可用硬件电路实现。可用硬件电路实现。如果码组如果码组B无错，无错，BA，则，则M0；如果；如果码组码组B有单个（或奇数个）错误，则有单个（或奇数个）错误，则M1。编码效率编码效率:R=(n-1)/n第第1111章章 差错控制编码差错控制编码通信原理2024/7/1213 11.2.2 行列监督码行列监督码 行列监督码又称水平垂直一致监督码或行列监督码又称水平垂直一致监督码或二维奇偶监督码，有时还被称为矩阵码。二维奇偶监督码，有时还被称为矩阵码。1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 0 0 0 0 11 0 0 1 1 1 0 0 0 01 0 1 0 1 0 1 0 1 000101 1 1 0 0 0 1 1 1 1 0 0第第1111章章 差错控制编码差错控制编码通信原理2024/7/1214 二维奇偶监督码适于检测突发错码。二二维奇偶监督码适于检测突发错码。二维奇偶监督码不仅可用来检错，还可用来纠维奇偶监督码不仅可用来检错，还可用来纠正一些错码。正一些错码。11.2.3 恒比码恒比码 恒比码又称等重码，该码的码字中恒比码又称等重码，该码的码字中1和和0的位数保持恒定的比例。具体情况见表的位数保持恒定的比例。具体情况见表11.2.1。目前我国电传通信中普遍采用目前我国电传通信中普遍采用3：2码，码，国际上通用的国际上通用的ARQ电报通信系统中，采用电报通信系统中，采用3：4码即码即7中取中取3码。码。第第1111章章 差错控制编码差错控制编码通信原理2024/7/121511.3 线性分组码线性分组码 11.3.1 基本概念基本概念 分组码是一组固定长度的码组，可表分组码是一组固定长度的码组，可表示为（示为（n,k），通常它用于前向纠错。在），通常它用于前向纠错。在编码时，编码时，k个信息位被编为个信息位被编为n位码组长度，位码组长度，而而n-k个监督位的作用就是实现检错与纠错。个监督位的作用就是实现检错与纠错。这样，一个这样，一个k比特信息的线性分组码可比特信息的线性分组码可以映射到一个长度为以映射到一个长度为n码组上。码组上。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1216 线性分组码的主要性质如下：线性分组码的主要性质如下：（1）任意两许用码之和仍为一许用码，）任意两许用码之和仍为一许用码，也就是说，线性分组码具有封闭性；也就是说，线性分组码具有封闭性；（2）码组间的最小码距等于非零码的最码组间的最小码距等于非零码的最小码重。小码重。对对偶偶校校验验时时的的监监督督关关系系。在在接接收收端端解解码码时，实际上就是在计算：时，实际上就是在计算：S=bn-1+bn-2+b1+b0 若若S0，则无错；若，则无错；若S1就认为有错。就认为有错。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1217 以（以（7，4）码为例进行分析，可以设码）码为例进行分析，可以设码字字A=a6,a5,a4,a3 a2,a1,a0，其中，其中 a6,a5,a4,a3 为信息位，为信息位，a2,a1,a0 为监督位，为监督位，进而得到进而得到下下面的方程组形式：面的方程组形式：不难看出，上述（不难看出，上述（7，4）码的最小码距）码的最小码距dmin3。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1218 11.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 将（将（7，4）码的三个监督方程式可以重）码的三个监督方程式可以重新改写为如下形式：新改写为如下形式：上式可以记作：上式可以记作：HAT=0T或或AHT=0，其中，其中 第第1111章章 差错控制编码差错控制编码通信原理2024/7/1219也可以用矩阵形式来表示：也可以用矩阵形式来表示：或表示成为：或表示成为：这这时时Q=PT，如如果果在在Q矩矩阵阵的的左左边边在在加加上上一一个个kk的单位矩阵，就形成了一个新矩阵的单位矩阵，就形成了一个新矩阵G：第第1111章章 差错控制编码差错控制编码通信原理2024/7/1220 这这里里G称称为为生生成成矩矩阵阵，利利用用它它可可以以产产生生整整个码组：个码组：11.3.3 校验子校验子S 设发送组码设发送组码A，在传输过程中有可能出现，在传输过程中有可能出现误码，这时接收到的码组为误码，这时接收到的码组为B。则收发码组之。则收发码组之差为：差为：第第1111章章 差错控制编码差错控制编码通信原理2024/7/1221其中：其中：则接收端利用接收到的码组则接收端利用接收到的码组B计算校正子：计算校正子：S=BHT=(A+E)HT=AHT+EHT=EHT 因此，校正子仅与因此，校正子仅与E有关，即错误图样与校有关，即错误图样与校正子之间有确定的关系。正子之间有确定的关系。汉明码就是一个线性分组码。有以下特点：汉明码就是一个线性分组码。有以下特点：（1）最小码距）最小码距dmin3，可纠正一位错误；，可纠正一位错误；（2）码长码长n与监督元个数与监督元个数r之间满足之间满足第第1111章章 差错控制编码差错控制编码通信原理2024/7/122211.4 循环码循环码 循环码是线性分组码的一个重要子集，是目循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码，它有许多特殊的代数前研究得最成熟的一类码，它有许多特殊的代数性质。性质。特点：特点：循环码中任一许用码组经过循环移位循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。后，所得到的码组仍然是许用码组。描述：描述：许用循环码许用循环码A=(an-1 an-2 a1 a0)，可以可以将它的码多项式表示为：将它的码多项式表示为：第第1111章章 差错控制编码差错控制编码通信原理2024/7/1223若一个整数若一个整数m可以表示为可以表示为:则则在在模模n运运算算下下，有有mp（模模n），同同样样对于多项式而言：对于多项式而言：则可以写为：则可以写为：F(x)R(x)（模（模N(x)）。）。在在循循环环码码中中，若若A(x)是是一一个个长长为为n的的许许用用码码组组，则则在在按按模模 运运算算下下，亦亦是是一一个个许许用用码组。码组。第第1111章章 差错控制编码差错控制编码通信原理2024/7/122411.4.1 生成多项式及生成矩阵生成多项式及生成矩阵 循环码中次数最低的码多项式称为生成循环码中次数最低的码多项式称为生成多项式，用多项式，用g(x)表示。可以证明生成多项式表示。可以证明生成多项式g(x)具有以下特性：具有以下特性：（1）g(x)是一个常数项为是一个常数项为1的的 次次多项式；多项式；（2）g(x)是是 的一个因式；的一个因式；（3）该循环码中其它码多项式都是该循环码中其它码多项式都是g(x)的倍式。的倍式。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1225 为了保证构成的生成矩阵为了保证构成的生成矩阵G的各行线性的各行线性不相关，通常用不相关，通常用g(x)来构造生成矩阵，来构造生成矩阵，显然，上式不符合显然，上式不符合 形式，所以形式，所以此生成矩阵不是典型形式。此生成矩阵不是典型形式。因此，一旦生成多项因此，一旦生成多项式式g(x)确定以后，该循环确定以后，该循环码的生成矩阵就可以确定。码的生成矩阵就可以确定。第第1111章章 差错控制编码差错控制编码通信原理2024/7/122611.4.2 监督多项式及监督矩阵监督多项式及监督矩阵 利用循环码的特点来确定监督矩阵利用循环码的特点来确定监督矩阵H：由于（由于（n,k）循环码中）循环码中g(x)是是xn+1的因式，的因式，因此可令：因此可令：监督矩阵表示为：监督矩阵表示为：其中：其中：第第1111章章 差错控制编码差错控制编码通信原理2024/7/1227 11.4.3 编码方法和电路编码方法和电路 1、编码过程、编码过程 首先需要根据给定循环码的参数确定生首先需要根据给定循环码的参数确定生成多项式成多项式g(x)，然后，利用循环码的编码特然后，利用循环码的编码特点，即所有循环码多项式点，即所有循环码多项式A(x)都可以被都可以被g(x)整整除，来定义生成多项式除，来定义生成多项式A(x)。下面就将以上。下面就将以上各步处理加以解释：各步处理加以解释：（1）用用xn-k乘乘m(x)。这一运算实际上是。这一运算实际上是把信息码后附加上（把信息码后附加上（n-k）个）个“0”。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1228 （2）求求R(x)。由于循环码多项式。由于循环码多项式A(x)都都可以被可以被g(x)整除，也就是：整除，也就是：上式也等效于：上式也等效于：这样我们就得到了这样我们就得到了R(x)。（3）编码输出系统循环码多项式编码输出系统循环码多项式A(x)为：为：第第1111章章 差错控制编码差错控制编码通信原理2024/7/1229 上述三步编码过程，在硬件实现时，可上述三步编码过程，在硬件实现时，可以利用除法电路来实现。以利用除法电路来实现。11.4.4 译码方法和电路译码方法和电路 循环码的译码可以分三步进行：循环码的译码可以分三步进行：（1）由接收到的码多项式）由接收到的码多项式B(x)计算校正计算校正子（伴随式）多项式子（伴随式）多项式S(x)；第第1111章章 差错控制编码差错控制编码通信原理2024/7/1230 （2）由校正子由校正子S(x)确定错误图样确定错误图样E(x)；（3）将错误图样将错误图样E(x)与与B(x)相加，纠正相加，纠正错误。错误。第第1111章章 差错控制编码差错控制编码通信原理2024/7/123111.4.5 BCH码码 特点：特点：它的生成多项式它的生成多项式g(x)与最小码距与最小码距之间有密切的关系，可以根据所要求的纠之间有密切的关系，可以根据所要求的纠错能力错能力t，很容易地构造出，很容易地构造出BCH码。码。相关知识：本原多项式的定义：相关知识：本原多项式的定义：(1)f(t)为既约多项式；为既约多项式；(2)f(t)是是(xp+1)因子，因子，p=2n-1 (3)f(t)不是不是(xq+1)的因子，的因子，pq第第1111章章 差错控制编码差错控制编码通信原理2024/7/123211.5 纠正和检测突发错误分组码纠正和检测突发错误分组码11.5.1 交错码交错码11.5.2 Fire码码11.5.3 RS码码第第1111章章 差错控制编码差错控制编码通信原理2024/7/123311.6 卷积码卷积码 卷积码中编码后的卷积码中编码后的n个码元不仅与当前个码元不仅与当前段的段的k个信息有关，而且也与前面（个信息有关，而且也与前面（N-1）段的信息有关，编码过程中相互关联的码段的信息有关，编码过程中相互关联的码元为元为nN个。因此，这个。因此，这N段时间内的码元数段时间内的码元数目目nN通常被称为这种码的约束长度。通常被称为这种码的约束长度。由于与前面由于与前面m段规定时间内的信息位段规定时间内的信息位有关，这里的有关，这里的mN-1通常用（通常用（n，k，m）表示卷积码表示卷积码。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1234 例如：例如：卷积码的卷积码的n=2，k=1，m=2，因，因此，它的约束长度此，它的约束长度nN=n(m+1)=23=6。第第1111章章 差错控制编码差错控制编码通信原理2024/7/1235 假如输入的信息为假如输入的信息为D=11010，为了使信，为了使信息息D全部通过移位寄存器，还必须在信息位后全部通过移位寄存器，还必须在信息位后面加面加3个零。表列出了对信息个零。表列出了对信息D进行卷积编码时进行卷积编码时的状态。的状态。描述卷积码的方法：图解表示和解析表示。描述卷积码的方法：图解表示和解析表示。卷积码的译码方法可分为代数译码和概率卷积码的译码方法可分为代数译码和概率译码两大类。译码两大类。