最新差错控制编码PPT课件.ppt

《最新差错控制编码PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新差错控制编码PPT课件.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、差错控制编码差错控制编码8.1 差错控制编码的基本概念差错控制编码的基本概念数字通信中，根据不同的目的，编码可分为数字通信中，根据不同的目的，编码可分为信源编码信源编码和和信道编码信道编码。信源编码是为了提高数字通信的有效性，以及为了使模信源编码是为了提高数字通信的有效性，以及为了使模拟信号数字化而采取的编码。拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。采取的编码。数字信号在传输的过程中，加性噪声、码间串扰等都会数字信号在传输的过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发

2、射产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。解调方法等。此外，还可以采用信道编码技术。2022/11/228.1.2 差错控制编码的分类差错控制编码的分类根据信息元和监督元的函数关系，可分为根据信息元和监督元的函数关系，可分为线性码线性码和和非非线性码线性码。如果函数关系是线性的，即满足一组线性方。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。程式，则称为线性码，否则为非线性码。根据上述关系涉及的范围，可分为根据上述关系涉及

3、的范围，可分为分组码分组码和和卷积码卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。的信息元有关。根据码的用途，可分为根据码的用途，可分为检错码检错码和和纠错码纠错码。检错码以检。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。一定能检错。2022/11/298.1.3 几种简单的检错码几种简单的检错码(1)奇偶监督码奇偶监督码设码字A=an-1,an-2,a1,a0，对偶

4、监督码有：an-1 an-2 a1 a0=0 奇监督码情况相似，只是码组中“1”的数目为奇数，即 满足条件：an-1 an-2 a1 a0=1 而检错能力与偶监督码相同。2022/11/210奇偶监督码奇偶监督码编码方法：把信息码元分组，在每组信息码元编码方法：把信息码元分组，在每组信息码元 的后面附加一位监督码元，使得的后面附加一位监督码元，使得 码组中码组中1的数目为奇数或偶数即可的数目为奇数或偶数即可 编码规则：码组长度编码规则：码组长度n；信息位；信息位n-1 特点：是一种能发现奇数个差错的分组码；特点：是一种能发现奇数个差错的分组码；n 较大，即编码码组较长时，编码效率较大，即编码码

5、组较长时，编码效率 接近于接近于1;（n-1）/n 信息码元比信息码元比 码组码元码组码元 适用于检测随机的零星错码适用于检测随机的零星错码加性白噪声造加性白噪声造 成的成的2022/11/2118.1.3 几种简单的检错码几种简单的检错码(2)二维奇偶监督码二维奇偶监督码(6,11)行列监督码 2022/11/212二维奇偶监督码二维奇偶监督码 编码方法：把码元排成方阵，按行列进行奇偶校验编码方法：把码元排成方阵，按行列进行奇偶校验 分别附加一位监督码元分别附加一位监督码元 特点：不仅可检测每行（每列）中奇数个错误，而且特点：不仅可检测每行（每列）中奇数个错误，而且 可通过水平监督和垂直监督

6、来确定错码的位置可通过水平监督和垂直监督来确定错码的位置 纠正仅一行（一列）出现的奇数个错误纠正仅一行（一列）出现的奇数个错误 通过水平监督和垂直监督的关系可以发现单行中出现通过水平监督和垂直监督的关系可以发现单行中出现 的偶数个错误；但不能发现构成矩形的的偶数个错误；但不能发现构成矩形的4个错误码元个错误码元 适用于突发差错适用于突发差错由突发干扰（突发脉冲，如：由突发干扰（突发脉冲，如：闪电，电火花等）在短时间内错码成串出现，在某闪电，电火花等）在短时间内错码成串出现，在某 一行中出现多个错码一行中出现多个错码2022/11/2138.1.3 几种简单的检错码几种简单的检错码(3)重复码重

7、复码 在每位信息码元之后，用简单重复多次的方法编码。在每位信息码元之后，用简单重复多次的方法编码。例：重复两次时，用例：重复两次时，用111传输传输1码，用码，用000传输传输0码码 编码方法：每位信息码元简单重复多次；编码方法：每位信息码元简单重复多次；收端收端 译码采用多数表决法；译码采用多数表决法；例：重复例：重复2 2次次特点：纠正特点：纠正1 1个错，检出个错，检出2 2个错个错2022/11/2148.1.3 几种简单的检错码几种简单的检错码(4)恒比码恒比码码字中码字中 1 1 的数目与的数目与 0 0 的数目保持的数目保持恒定比例的码称为恒比码恒定比例的码称为恒比码。这种码在检

8、测时，只要计算接收码这种码在检测时，只要计算接收码元中元中 1 1 的数目是否正确，的数目是否正确，就知道有无错误。就知道有无错误。2022/11/215恒比码恒比码例：例：5中取中取3恒比码恒比码用于电报电码用于电报电码 每个码组长度为每个码组长度为5，共有，共有25=32种不同的码组，种不同的码组，其中有其中有3个个1的码组为可用码组，共有的码组为可用码组，共有10种种 表示表示10个阿拉伯数字，用它拼成汉字（每个阿拉伯数字，用它拼成汉字（每4阿拉阿拉 伯数字组成伯数字组成1个汉字电码）；其余的个汉字电码）；其余的22个为禁用个为禁用 码组。码组。特点：简单；除了特点：简单；除了1错为错为

9、0与与0错为错为1成对出现（对换成对出现（对换 性）差错不能检测外，其它任何奇数个或偶数性）差错不能检测外，其它任何奇数个或偶数 个错码都可以被检测出来。个错码都可以被检测出来。只适用于传输种类较少且有固定代码的字符，而不适只适用于传输种类较少且有固定代码的字符，而不适用于表示由信源来的二进制随机，数字序列。用于表示由信源来的二进制随机，数字序列。2022/11/2168.1.3 几种简单的检错码几种简单的检错码(4)ISBN国际统一图书编号国际统一图书编号例例 ISBN 04710297772022/11/2178.1.4 检错和纠错的基本原理检错和纠错的基本原理如用三位二进制编码来代表八个

10、字母如用三位二进制编码来代表八个字母000 A000 A100100E E001 001 B B101101F F010010C C110110G G011011D D111111H H不管哪一位发生错误，都会使传输字母错误不管哪一位发生错误，都会使传输字母错误如用三位字母传四个字母如用三位字母传四个字母000 A000 A011011B B101 101 C C110110D D发生一位错误，准用码字将变成禁用码字，接收端就能知道发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错出错，但是不能纠错。如果进一步将许用码组限制为两种如果进一步将许用码组限制为两种000 A 1

11、11 B000 A 111 B检错和纠错能力是用信息量的冗余度来换取的。检错和纠错能力是用信息量的冗余度来换取的。2022/11/218检错和纠错的基本原理检错和纠错的基本原理检错和纠错能力是用信息量的冗余度换取的检错和纠错能力是用信息量的冗余度换取的与码组之间的差别有关；不同的编码方法和与码组之间的差别有关；不同的编码方法和形式，检错和纠错能力不同。形式，检错和纠错能力不同。例：例：n=3，共有，共有8种组合，都用于传输消息，种组合，都用于传输消息，在传输过程中若发生一个误码，则一种码组就在传输过程中若发生一个误码，则一种码组就会错误地变成另一种码组，但接收端却不能发会错误地变成另一种码组，

12、但接收端却不能发现错误，因为任何一个码组都是许用码组。现错误，因为任何一个码组都是许用码组。2022/11/219 在差错控制编码中，定义码组中非零码元的数目为码字的在差错控制编码中，定义码组中非零码元的数目为码字的汉明汉明(Hamming)(Hamming)重量重量，简称简称码重码重。例如，码字。例如，码字 1011010110，码重，码重w w=3=3。定义两个等长码组之间相应位取值不同的数目为这两个码组的定义两个等长码组之间相应位取值不同的数目为这两个码组的汉汉明明(Hamming)(Hamming)距离距离，简称简称码距码距。例如。例如 11000 11000 与与 100111001

13、1之间的距离之间的距离d=3d=3。码组集中任意两个码字之间距离的最小值称为码组集中任意两个码字之间距离的最小值称为码的最小距离码的最小距离，用，用d dminmin表示。最小码距是码的一个重要参数，表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能它是衡量码检错、纠错能力的依据。力的依据。2022/11/220最小码距与检错纠错能力的关系最小码距与检错纠错能力的关系 码组内的距离反映了码组之间的差别，码组内的距离反映了码组之间的差别，最小距离越大，说明两个码组间的最小最小距离越大，说明两个码组间的最小差别越大，或者说其中一个码组错为另差别越大，或者说其中一个码组错为另一个码组的可能性就

14、越小，那么其检错一个码组的可能性就越小，那么其检错和纠错能力也就越强，因此可以说最小和纠错能力也就越强，因此可以说最小码距是衡量一种纠错编码的检错，纠错码距是衡量一种纠错编码的检错，纠错能力大小的标准。能力大小的标准。2022/11/221 码码的的最最小小距距离离直直接接关关系系着着码码的的检检错错和和纠纠错错能能力力；任任一一(n,kn,k)分组码，若要在码字内分组码，若要在码字内:(1)(1)检检测测e e个个随随机机错错误误，则则要要求求码码的的最最小小距距离离d dminmine e+1;+1;(2)(2)纠纠正正t t个个随随机机错错误误，则则要要求求码码的的最最小小距距离离d d

15、minmin22t t+1;+1;(3)(3)纠纠正正t t个个同同时时检检测测e e(t t)个个随随机机错错误误，则则要要求求码的最小距离码的最小距离d dminmint t+e e+1+1。t1eAB2022/11/222 用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:Rc=k/n其中,k是信息元的个数，n为码长。对纠错码的基本要求是:检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。编码效率编码效率2022/11/2238.2 线性分组码线性分组码线性分组码

16、的构成线性分组码的构成 将信息序列划分为等长将信息序列划分为等长(k位位)的序列段的序列段 共有共有2k个不同的序列段，在每一信息个不同的序列段，在每一信息 段之后，附加段之后，附加m位监督元，构成长度位监督元，构成长度 n=k+m的分组码的分组码(n，k)监督元与信息码元为线性关系监督元与信息码元为线性关系2022/11/224例例 信息元长度信息元长度k=3共有共有2k=8个不同的信息组个不同的信息组 每组信息组加每组信息组加4个监督元，构成一个长度为个监督元，构成一个长度为7 的的(7，3)线性分组码。线性分组码。设：设：每组信息元为每组信息元为C1C2C3监督元为监督元为C4 C5 C

17、6C7 根据下列线性方程组求监督元根据下列线性方程组求监督元 C4=C1+C3 C5=C1+C2+C3 C6=C1+C2 C7=C2+C32022/11/225例例(7，3)码有码有8个信息组，信息组按上方程组求得每个个信息组，信息组按上方程组求得每个 信息组的信息组的4个监督元，得到个监督元，得到(7，3)码的所有码的所有8个码字个码字 信息组信息组 码元码元 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1

18、 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0重要特性，线性码有封闭性重要特性，线性码有封闭性 2022/11/2268.2 线性分组码线性分组码设分组码由设分组码由n n位码组构成，记为位码组构成，记为c c1 1，c c2 2，c cn n，信息码组由，信息码组由k k位码位码组成，记为组成，记为d d1 1，d d2 2，d dk k。则该分组码记为（。则该分组码记为（n n，k k）码。）码。码组和信息码组可用行矩阵码组和信息码组可用行矩阵C C和和D D表示表示若为线性分组码，若为线性分组码，C C中的中的n n个元素都是由个元素都是由D D中的

19、中的k k个元素经线性组合个元素经线性组合形成的。可用一联立方程表示为形成的。可用一联立方程表示为2022/11/227将码组将码组C写成矩阵形式写成矩阵形式矩阵矩阵G称为生成矩阵，它是一个称为生成矩阵，它是一个kn的矩阵的矩阵2022/11/228生成矩阵生成矩阵G2022/11/229生成矩阵生成矩阵GIk 单位矩阵，单位矩阵，k行行k列列(k x k阶阶)P矩阵，矩阵，k行行m列列(k x m阶阶)编码前编码前k位，编码后有位，编码后有n位，位，2n 2k；选择选择P矩阵，可得到有较强检错纠错能力，实现矩阵，可得到有较强检错纠错能力，实现 方法尽可能简单，编码效率又高的线性分组码方法尽可

20、能简单，编码效率又高的线性分组码由于线性码具有封闭性，故任何二个码组之间的距离由于线性码具有封闭性，故任何二个码组之间的距离必须与某一个码组中必须与某一个码组中“1”的个数相等，而码组中非零的个数相等，而码组中非零码元的数目码元的数目“1”的个数为码组的重量（码重）所以线的个数为码组的重量（码重）所以线性码任意二个码字之间的距离必须等于码中某一个码性码任意二个码字之间的距离必须等于码中某一个码字的重量字的重量线性码最小码距正好等于非零码的最小线性码最小码距正好等于非零码的最小码重码重估算线性码的差错控制能力：估算线性码的差错控制能力：求最小码距求最小码距最小码重最小码重2022/11/230例

21、例 已知（已知（6，3）码的生成距阵，求：编码码组）码的生成距阵，求：编码码组2022/11/231监督矩阵监督矩阵H校验矩阵或监督矩阵校验矩阵或监督矩阵H H：m x n m x n 阶阶P PT T:m m行行k k列列 k+m=nk+m=n列列2022/11/232伴随式（校正子）伴随式（校正子）S 设设发发送送码码组组C=C=c cn n-1-1,c cn n-2-2,c c1 1,c c0 0，在在传传输输过过程程中中可可能能 发发生生误误码码。接接收收码码组组R R=r rn n-1-1,r rn n-2-2,r r1 1,r r0 0，则则收收发发码码组组之之差定义为错误图样差定

22、义为错误图样E E，也称为误差矢量，也称为误差矢量，即即 E E=RC=RC=en-1,en-2,e1,e0，且且 当ri=ci 当rici 令令 S=RHT，称为称为伴随式伴随式或或校正子校正子 S=RHS=RHT T=CH=CHT T EHEHT T=EH=EHT T S S只与错误图形有关，与发送的码组只与错误图形有关，与发送的码组C C无关无关 H HT T：n x m n x m 阶；阶；E E：1x n 1x n 阶；阶；S S：1x m 1x m 阶；阶；S=sS=s1 1 s s2 2 s sm m 解得误差矢量解得误差矢量E E，求得纠错后的码组求得纠错后的码组 C=R C=

23、R E E2022/11/233检错与纠错检错与纠错检错：当码组出现错误检错：当码组出现错误S为非零矢量为非零矢量纠错：纠错：S=RHT=CHT EHT=EHT S与与E之间有着确定的线性关系之间有着确定的线性关系由由H矩阵矩阵 确定（也就是与确定（也就是与G（P）矩阵有关）矩阵有关）S=s1 s2 sm 共有共有2m种不同的形式，除全种不同的形式，除全 0外，可代表外，可代表2m-1种有错误的图形种有错误的图形 信息码组有信息码组有2k个错误图形，有多种不同的形式个错误图形，有多种不同的形式可能有可能有2k种解答；为了选择正确的结果，要使种解答；为了选择正确的结果，要使用最大似然比准则，选择

24、与用最大似然比准则，选择与R最相似的最相似的C（与（与R距距离最小的码组离最小的码组E是是1码最小的矢量）码最小的矢量）。2022/11/234例：（例：（6，3）码）码2022/11/235S与与E对照表对照表 E S 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 （6，3）码具有纠码具有纠1位错的能力位错的能力发生发生1 1个错误的情况：个错误的情况：

25、S S是是H HT T的第的第i i行，说明行，说明R R中第中第i i位位 产生了错误，可以把它纠正产生了错误，可以把它纠正发生发生2个错误的情况：个错误的情况：除除S=111对应第对应第1，5位有错位有错 其它的双错不能得到纠正其它的双错不能得到纠正 例：例：接收码组接收码组R111011 2022/11/236查表法译码器的原理查表法译码器的原理S=RHT=CHT EHT=EHT算出伴随式算出伴随式S与最小码重的差错与最小码重的差错矢量矢量E的对照表，提供译码使用的对照表，提供译码使用2022/11/237汉明码汉明码按上述方法构造的能纠正单个错误的线性分组码称为按上述方法构造的能纠正单

26、个错误的线性分组码称为 汉明码。汉明码。对于线性分组码，为了指示所有单错位置和无错的情况，对于线性分组码，为了指示所有单错位置和无错的情况，必须满足不等式必须满足不等式汉明码具有以下特点：汉明码具有以下特点：汉明码的编码效率汉明码的编码效率2022/11/238汉明界汉明界如果码组有纠如果码组有纠t个差错的能力，则应能指出无错、单错到个差错的能力，则应能指出无错、单错到t个差错所个差错所有可能的情况，校验位数有可能的情况，校验位数m应满足不等式：应满足不等式：汉明界，是纠正t个差错的一个必要条件2022/11/2398.3 循环码循环码特点特点线性分组码循环性任一许用码字经过循环移位后，得到的

27、码组仍为一个许用码组如 是循环码的一许用码组 则 也是一许用码组 移位i次得到 也是许用码组2022/11/2408.3.1 循环码的特点及表达循环码的特点及表达码多项式表示码多项式表示以此类推，码组以此类推，码组C移位移位i i次，相应的码多项式次，相应的码多项式c c(i)(i)(x)(x)是是x xi ic(x)c(x)除以除以（x xn n+1)+1)后的余式。后的余式。在模在模（x xn n+1)+1)意义下，若意义下，若c(x)c(x)是码多项式，则是码多项式，则x xi ic(x)c(x)都都是码多项式。是码多项式。2022/11/241循环码的编码过程循环码的编码过程一个一个k

28、位的信息码组位的信息码组 可用信息多可用信息多项式表示项式表示假设码组多项式可表示为假设码组多项式可表示为如果如果(n n+1)+1)是是g(g()的倍式的倍式 C C（1 1）()=)=d(d()g()g()+aC)+aC1 1g(g()=d(d()+aC)+aC1 1g(g()=d)=d1()g()g()d d1 1()对应某个信息码组对应某个信息码组2022/11/242生成多项式生成多项式g()(n+1)是是g()的倍式，且的倍式，且g()为为n-k次多次多项式，所以对项式，所以对(n+1)进行因式分解，便进行因式分解，便可得到相应的可得到相应的g()。对对(n+1)进行因式进行因式分

29、解可由计算机完成，有表格给出。分解可由计算机完成，有表格给出。由信息多项式求解码多项式由信息多项式求解码多项式 C()=d()g()n-1次次 k-1次次 n-k次次2022/11/243例例(7，4)n=7k=4 m=n-k=3 g()应为应为(7+1)的的3次因式次因式+1=(+1)(+1)(+1)g1()=(+1)g2()=(+1)D=1010 d()=(+)C1()=d()g1()=(+)(+1)=+C1=1001110C2()=d()g2()=(+)(+1)=+C=1110010注：注：1.不同的生成多项式得到不同的码组不同的生成多项式得到不同的码组 2.由此编码法得到的不是系统码（

30、前由此编码法得到的不是系统码（前4位不是位不是D=1010）2022/11/244非系统码非系统码系统码系统码系统码用多项式表示为系统码用多项式表示为 k-1次次 m-1次次 由式（由式（831）码组多项式表示为）码组多项式表示为综合两式有综合两式有2022/11/245例例(7，4)n=7k=4 m=n-k=3 g()应为应为(7+1)的的3次因式次因式+1=(+1)(+1)(+1)g1()=(+1)g2()=(+1)D=1010 d()=(+)-4 d()=(+)=+4 R1()=-4 d()/g1()=(+1)C1()=-4 d()+R1()=+4+1 C1=1010011-4 d()=

31、(+)=+4 R2()=-4 d()/g2()=1 C2()=-4 d()+R2()=+4+1 C2=1010001注：注：不同的生成多项式得到不同的系统循环码不同的生成多项式得到不同的系统循环码2022/11/2468.3.2 循环码的编码和译码循环码的编码和译码原理：按系统码的生成方式原理：按系统码的生成方式以以(7,4)码为例码为例 2022/11/247循环码的译码器循环码的译码器发送码组多项式发送码组多项式c(x)是生成多项式是生成多项式g(x)的倍式。如果经信道传输的倍式。如果经信道传输后发生错误，接收码组多项式后发生错误，接收码组多项式r(x)不再是不再是g(x)的倍式的倍式接收码组表示为接收码组表示为由由s()确定确定e()同样使用最同样使用最大似然比准则，对应最小码重大似然比准则，对应最小码重的差错多项式，列出译码表，的差错多项式，列出译码表，由由s()对照译码表确定对照译码表确定e()译码三步译码三步伴随式S的计算由S得到错误图样纠正2022/11/248