第八章-差错控制编码.ppt

1、数字编码的两种类型：,8.1 引言,一、差错控制编码的目的,二、传输中产生误码的原因,1、随机起伏噪声：误码随机、统计独立（高斯白噪声）,2、突发干扰：误码集中出现（脉冲干扰、衰落）,3、混合干扰：既有随机误码又有突发误码。,三、解决途径,5、采用信道编码（差错控制编码）,1、合理设计基带信号传输码型，2、合理选择调制、解调方式， 3、加大发送功率，4、采用频域、时域均衡。,1、检错重发法ARQ (Automatic Repeat Request) ：,四、差错控制方法,2、前向纠错法FEC (Forword ErrorCorrection),3、反馈校验法,4、混合纠错法HEC (Hybri

2、d ErrorCorrection),图1 自动请求ARQ方框图,一、差错控制编码的基本概念：,1、几个名词解释：,码距：两个码字对应位上数字不同的个数；（汉明距离） 例如 11000 与 10011之间的距离d=3,最小码距 ：码组集中各码距的最小值。,码字：由若干个码元组成的序列。例：1011001称为一个码字 。,结论：线性分组码中，最小码距等于最小码重,8.2 差错控制编码的基本原理,码组：由多个码字构成的集合。例：00,01,10,11。,码重/汉明重量：码字中“1”的个数；例：码字 10110，码重w=3。,2、 差错控制编码的基本原理,（1）举例：发短信、天气预报,（3）基本原理

3、：k位信息码+r位监督码n位编码。,（4）编码效率：k/n=1-r/n。 若2个信息码元中加1个监督码元，编码效率2/3。,（2）基本思想：在发送信息时，加入某种关联性某种约束关系。,8.2 差错控制编码的基本原理,接收端不能检错，也不能纠错。,返回,（3）、基本原理：,0 0（晴）0 1（云）1 0（阴）1 1（雨）,信息码加若干监督码的编码集合，用 表示。,：信息码元的数目， ：码组的总位数,表示监督码元的数目,其结构为：信息码+监督码,返回,二、最小码距d0与纠错能力的关系：,8.2 差错控制编码的基本原理,1、重复码：用来发送天气预报 举例： 结论：纠错能力与码的位数有关。怎么样的关系

4、呢？,(1) 检测e个随机错误，则要求码的最小距离d0e+1; (2) 纠正t个随机错误， 则要求码的最小距离d02t+1; (3) 纠正t个同时检测e个随机错误，则要求码的最小距离d0t+e+1， (et)。,2、最小码距d0与纠错能力的关系：,三、差错控制编码的分类：,从用途、监督关系、码字结构、信息处理等方面分类,接收端不能检错，也不能纠错。,3、若用3位码表示2种信息， 000（晴） 111（雨）,接收端此时有可能发现一个错码并能纠正它， 或发现二个以下错码不能纠正，不能发现三个错误。,返回,8.3 常用的简单编码,1、奇偶监督码,奇偶监督码可分为奇数监督码和偶数监督码，两者的原理相同

5、。,它能检测奇数个错码，无纠错能力。,（2）奇数监督码：监督位也只有一位，使得码组中“1”的个数为奇数，即满足,它也能检测奇数个错码，无纠错能力。,编码效率：(n-1)/n,应用：适用于一般随机错误的检测,2、二维奇偶监督码,1）原理：,2）举例：,3）检错能力：,4）编码效率：,5）特点：适合检测突发误码。,3、恒比码,码组中“1”（或“0”）的个数相同。也即它们的比保持恒定。,接收端计算码组中“1”的个数即可知道有无误码。,优点：适合用来传输电传机或键盘设备产生的信息。,举例：5取3恒比码我国电传机，7取3恒比码国际电传电报,2）举例：4行7列信息组的水平垂直偶校验码为：,发往线路顺序：

6、01110010|00101011|01010110|10101010|10100101 第1字符 第2字符 第3字符第4字符 偶校验字符,返回,4、正反码（能纠正一位错码）,1）、编码规则：监督位数与信息位数相同。,“1”的个数决定监督码元是否与信息码元相同或相反。,举例：,电报通信 （10 5),若有奇数个“1”，则监督码元与信息码元相同,若有偶数个“1”，则监督码元与信息码元相反,2）、解码原理：,若收到码字的信息位有奇数个“1”，合成码字就是校验码字,若收到码字的信息位有偶数个“1”，合成码字的反码是校验码字,3）、由校验码字来检错纠错：,8.4 线性分组码,一、什么是线性分组码？,（

7、1）封闭性：任何两个许用码字之和，仍为一许用码字。,2、两个重要性质,分组码:先给信息码分组，然后给每组信息码附加若干监督码的编码。,1、基本概念,代数码:建立在代数学基础上的编码。,线性码:信息位与监督位由线性代数方程组联系在一起。是代数码,线性分组码:信息码分组后，定长信息码与监督码由线性代数方程组联系在一起而形成的编码。如汉明码、循环码等。,（2）最小码距最小码重（全“0”码除外）,3、编码效率,二、线性分组码的编码原理,3）若有r位监督位，可以指示错码 个不同位置,1、一般原理,结论：码长 n,信息位 k,监督位为 r=n-k，若它能指示n个错码位置,则：,（或 ）,举例：（7 4）汉

8、明码 r=3 可以指示7个错码位置,1） （7 4）应该有3个校正因子，8种组合，7个错码位置,那么：,3）正确的监督关系为：,4）可得16个许用码字 P222 表8-7,5）汉明码还可纠错 例8-4-1,二、线性分组码的编码原理,2、监督方程与监督矩阵H,3、生成方程与生成矩阵G,结论：典型阵H的各行一定是线性无关的，非典型阵可以经线性变换后化成典型阵。根据AHT=0，用于接收端检、纠错,典型阵,典型阵,二、线性分组码的编码原理,4、监督矩阵H与生成矩阵G的关系,结论：生成矩阵的每一行都是码字，利用生成矩阵G可以产生整个码组，即,三、线性分组码的译码原理,2、校正子S,1、错误图样E,3、结

9、论,接收码元中只错一位时，计算出的校正子S总是和典型阵H的某一列相同，可判断错误发生在哪个码元。（纠单个错）,例8-4-2 P225,8.5 循环码,1、定义：是常用的线性分组码，其检、纠错能力强，编译码设备不复杂的码。有严密的代数理论基础，以生成多项式作为收发双方的约束关系。由于码组内任一码字经循环移位后仍为该码组中的一个码字，所以称为循环码。,1）封闭性,3、码字多项式,来表示,码字与码字多项式有一一对应关系,表示方法：,一、 循环码的基本概念,2、特点：,3）循环性：任一许用码组经循环移位后仍为一许用码组。,2）最小码距等于最小码重（全“0”码除外）,举例：,循环性：若T(x)是长为n的

10、许用码字多项式，则,4、生成多项式,是一个能整除xn+1且常数项为1的r（r=n-k)次多项式，是(n,k)循环码集合中（除全“0”码外）幂次最低的多项式，它有唯一性，由生成多项式可以产生循环码的全部码字。,5、生成矩阵多项式G(x)、生成矩阵G,由生成矩阵可以得到所有的循环码字,(n,k)循环码中前（k-1)位都是0，那么 ,都是码字多项式，且线性无关。把这些多项式写成矩阵的形式，即,把系数写成矩阵形式,生成矩阵G (若非典型阵),典型阵G,线性变换,二、循环码的编码,1）用 乘 。相当于在信息码元后面加 个0；,2）用 除 ，得到商Q（x)和余式r(x),3）编出的码组为,1100000+

11、101=1100101,1、编码步骤,并发送,4）举例：已知（7，3）循环码，m(x)=x2+x，g(x)=x4+x2+x+1，求经CRC编码后的发送码字,2、编码电路的实现,软件有延时，但成本低,硬件实时性强，但有设备成本,编码电路,三、循环码的译码,收到码多项式R(x)，用g(x)做除法，,若r(x) 0，则无错，否则有错。,1、译码原理,举例：P228 例8-5-2,2、译码电路的实现,软件有延时，但成本低,硬件实时性强，但有设备成本,由r(x) 找错误图样，最后纠错。即：,四、循环码的检查能力,（1）可检测出所有奇数位错； （2）可检测出所有双比特错； （3）可检测出所有小于、等于校验

12、位长度的突发错。 结论：是一种检纠错能力和编码效率达到最佳折中的编码。在数据通信和计算机网络中得到了广泛应用。,五、几种常用的CRC校验码生成多项式：,8.6 其它差错控制编码简介,8.6.1 BCH码,1、何为BCH码？,BCH码是由博斯（Bose）、查德胡里（Chaudhuri）和霍昆格姆（Hocquenghem）名字的开头字母命名的，有严密的代数理论，纠多个随机错的CRC码。根据所要求的纠错能力t，可求生成多项式g(x)，很容易构造出BCH码，译码也易实现。,2、BCH码分类,本原BCH码：码长为 ，m为正整数；它的生成多项式由若干m阶或以m阶的因子为最高阶的多项式相乘而构成。,非本原B

13、CH码：码长是 的一个因子；它的生成多项式中不含有最高次数为m的本原多项式。,8.6.2 卷积码,1、问题的提出：,分组码是把k个信息比特的序列编成n个比特的码字，每个码字的n-k个校验位仅与本码组的k个信息位有关，而与其他码字无关。为了达到一定的纠错能力和编码效率，分组码的码字长度一般都比较大。 是否有既要求n、k较小，又要求纠错能力较强的编码呢？ 答案是肯定的，那就是我们要介绍的卷积码。,2、特点：卷积码是非分组码,8.6.2 卷积码,3、卷积码的定义：,卷积码：也称连环码，是一种非线性分组码，它也是将k个信息比特编成n个比特，但k和n通常很小，特别适合以串行形式进行传输，时延小。卷积码编码后的n个码元不仅与当前段的k个信息位有关，还与前面的N-1段信息位有关，整个编码过程可以看成是输入信息序列与编码器的卷积，因此称为卷积码。,通常把卷积码记为：（n，k，N），N1，n表示总码字的长度，k表示信息位的个数，N就是寄存器的个数，通常将N称为约束长度（以组为单位）