数字通信原理8差错控制编码.ppt

《数字通信原理8差错控制编码.ppt》由会员分享，可在线阅读，更多相关《数字通信原理8差错控制编码.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数字通信原理数字通信原理第八章第八章 差错控制编码差错控制编码 (线性分组码部分线性分组码部分)1 11 1、差错控制编码的基本原理、差错控制编码的基本原理n 编码编码编码编码：在信息码组上附加一定位数的监督码元，使在信息码组上附加一定位数的监督码元，使其与信息位按某种规则相互关联；其与信息位按某种规则相互关联；n 检错与纠错检错与纠错检错与纠错检错与纠错：若数据在传输过程中发生差错，关联：若数据在传输过程中发生差错，关联关系被破坏，从而可检出和关系被破坏，从而可检出和/或纠正错误或纠正错误第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2 2 2 2、差错控制主要类

2、型差错控制主要类型 检错重发（检错重发（检错重发（检错重发（ARQARQARQARQ）设备较简单；传输序列中冗余量较小；设备较简单；传输序列中冗余量较小；需要有反向信道支持；出错后重传造成延时较大。需要有反向信道支持；出错后重传造成延时较大。前向纠错（前向纠错（前向纠错（前向纠错（FECFECFECFEC）适用于包括没有反向信道的场合；适用于包括没有反向信道的场合；出错时可纠正误码，无需重传，延时小；出错时可纠正误码，无需重传，延时小；传输序列中冗余量较大。传输序列中冗余量较大。混合系统混合系统混合系统混合系统 前向纠错（前向纠错（FECFEC）检错重发（检错重发（ARQARQ）出错较少时出错

3、较少时FECFEC起作用；出错较多时起作用；出错较多时ARQARQ起作用起作用第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码3 3 3 3、差错控制编码的分类、差错控制编码的分类n n 线性码线性码线性码线性码：信息码与监督码之间的关系为线性关系；：信息码与监督码之间的关系为线性关系；非线性码非线性码非线性码非线性码：信息码与监督码之间的关系为非线性关系。：信息码与监督码之间的关系为非线性关系。n 分组码分组码分组码分组码：信息码与监督码以组为单位建立关系：信息码与监督码以组为单位建立关系；卷积码卷积码卷积码卷积码：监督码与本组和前面码组中的信息码有关。：监督码与本

4、组和前面码组中的信息码有关。n n 系统码系统码系统码系统码：编码后码组中信息码保持原图样顺序不变；编码后码组中信息码保持原图样顺序不变；非系统码非系统码非系统码非系统码：编码后码组中原信息码原图样发生变化。：编码后码组中原信息码原图样发生变化。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码4 44 4、错误的主要形式、错误的主要形式n n 随机错误随机错误随机错误随机错误：误码的位置随机（误码间无关联），随机：误码的位置随机（误码间无关联），随机误码主要由白噪声引起；误码主要由白噪声引起；n 突发错误突发错误突发错误突发错误：误码成串出现，主要由强脉冲及雷电等突：

5、误码成串出现，主要由强脉冲及雷电等突发的强干扰引起；发的强干扰引起；n 混合错误混合错误混合错误混合错误：以上两种误码及产生原因的组合；：以上两种误码及产生原因的组合；第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码5 55 5、检错与纠错编码的示例、检错与纠错编码的示例 三位二进制码的三种编码方法。三位二进码共有三位二进制码的三种编码方法。三位二进码共有8种可能种可能 的组合：的组合：000，001，010，011，100，101，110，111 a.a.若若8 8个码组均用于表示不同的信息，任一位或一位以上的错个码组均用于表示不同的信息，任一位或一位以上的错 误都

6、会变成另一码组，所以无法检错和纠错。误都会变成另一码组，所以无法检错和纠错。b.b.若将若将8 8个码组分成许用和禁用个码组分成许用和禁用(通信过程不会采用通信过程不会采用)两类：两类：许用码组许用码组许用码组许用码组：000000，011011，101101，110110 禁用码组禁用码组禁用码组禁用码组：111111，100100，010010，001001 因任何一位误码，都会变成禁用码组，所以可检出一位误码。因任何一位误码，都会变成禁用码组，所以可检出一位误码。c.c.若规定若规定 许用码组许用码组许用码组许用码组：000000，111111 禁用码组禁用码组禁用码组禁用码组：0010

7、01，010010，011011，100100，101101，110110 每个码组可携带每个码组可携带1 1比特信息，码组具有检测出两位及以下比特信息，码组具有检测出两位及以下 的误码，或纠正一位误码的能力。的误码，或纠正一位误码的能力。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码6 66 6、香农信道编码定理、香农信道编码定理 若信道容量为若信道容量为C C，信息传输速率为信息传输速率为R R，如果如果 R C R C，则存在则存在 编码方法，使错误概率编码方法，使错误概率 P PE E e e-nE-nEc c(R)(R)其中其中 E EC C(R)(R)称

8、为称为误差指数误差指数误差指数误差指数，n n 为为码组长度。码组长度。码组长度。码组长度。(采用适当的方法采用适当的方法采用适当的方法采用适当的方法增大增大增大增大n n n n，有利于减小，有利于减小，有利于减小，有利于减小P P P PE E E E)。误差指数误差指数误差指数误差指数特性曲线：特性曲线：信道容量信道容量C C作为曲线的作为曲线的 的参变量（包含了有关的参变量（包含了有关 S/NS/N等因素的影响）等因素的影响）第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码7 77 7、编码效率和冗余度编码效率和冗余度 假定分组码的长度为假定分组码的长度为n，

9、其中信息位为其中信息位为k，相应的监督相应的监督位为位为nk 编码效率编码效率编码效率编码效率定义为：定义为：冗余度冗余度冗余度冗余度定义为：定义为：通常冗余度越大，码的检错和纠错的能力越强。通常冗余度越大，码的检错和纠错的能力越强。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码8 88 8、几种常用的检错编码几种常用的检错编码n 奇偶校验码奇偶校验码奇偶校验码奇偶校验码 在信息码组在信息码组a an-1n-1,a,an-2n-2,a,a1 1中加入监督位中加入监督位a a0 0，使编码后码组中使编码后码组中 “1”“1”的个数为奇数（的个数为奇数（奇校验奇校验奇校

10、验奇校验）或偶数（）或偶数（偶校验偶校验偶校验偶校验）。）。偶校验偶校验偶校验偶校验：取：取a a0 0，使下式成立使下式成立 a an-1n-1 a an-2 n-2 a a1 1 a a0 0 0 0 a a0 0=a an-1n-1 a an-2 n-2 a a1 1 奇校验奇校验奇校验奇校验：取：取a a0 0，使下式成立使下式成立 a an-1n-1 a an-2 n-2 a a1 1 a a0 0 1 1 a a0 0=a an-1n-1 a an-2 n-2 a a1 1 1 1第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码9 9n n 奇偶效验码（续

11、）奇偶效验码（续）奇偶效验码（续）奇偶效验码（续）奇偶效验码码组间最小距离奇偶效验码码组间最小距离奇偶效验码码组间最小距离奇偶效验码码组间最小距离d d d dminminminmin2 2 2 2 证明（以偶效验为例）：因为证明（以偶效验为例）：因为 a an-1n-1 a an-2 n-2 a a1 1 a a0 0 0 0 所以当码组中任一位所以当码组中任一位a aj j发生错误时发生错误时:a aj j /a aj j;a an-1n-1 a an-2 n-2 /a aj j a a1 1 a a0 0 1 1 至少可检出一位误码，故至少可检出一位误码，故d dminmin大于或等于大

12、于或等于2 2。当有两位当有两位a ai i，a aj j发生误码时发生误码时 a an-1n-1 a an-2 n-2 /a aj j/s sj j a a1 1 a a0 0 0 0 所以不能检出两位误码，所以不能检出两位误码，故故d dminmin小于或等于小于或等于2 2。综上，综上，d dminmin=2=2 第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码1010n n 奇偶效验码奇偶效验码奇偶效验码奇偶效验码(续续续续)编码效率编码效率编码效率编码效率为：为：k/nk/nk/(k+1)k/(k+1)；冗员度：；冗员度：1/(k+1)1/(k+1)；k k

13、：信息位：信息位 奇偶效验码的检错能力奇偶效验码的检错能力奇偶效验码的检错能力奇偶效验码的检错能力：奇偶效验码能够检测出所有奇数个位数的错误；奇偶效验码能够检测出所有奇数个位数的错误；奇偶效验码不能检测出所有的偶数个位数的错误。奇偶效验码不能检测出所有的偶数个位数的错误。一般地，若信道接收一个错误比特的概率为一般地，若信道接收一个错误比特的概率为p p，则则n n个比特长个比特长 的码组发生的码组发生j j个比特错误的概率为：个比特错误的概率为：其中其中 奇偶效验码奇偶效验码奇偶效验码奇偶效验码不不不不能检出的错误的概率为：能检出的错误的概率为：能检出的错误的概率为：能检出的错误的概率为：第八

14、章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码11 11 8 8 8 8、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码(续续续续)n 水平奇偶效验码水平奇偶效验码水平奇偶效验码水平奇偶效验码 m m m m个码组个码组个码组个码组分别以各自码组为单位作奇效验或偶效验，然后以各分别以各自码组为单位作奇效验或偶效验，然后以各 码组的最高位、次高位，码组的最高位、次高位，依次发送：依次发送：a a a an-1 n-1 n-1 n-1 a a a an-2 n-2 n-2 n-2 a a a a1 1 1 1 a a a a0 0 0 0 a

15、 a a an-1 n-1 n-1 n-1 a a a an-2 n-2 n-2 n-2 a a a a1 1 1 1 a a a a0 0 0 0 共共共共m m m m行行行行 a a a an-1 n-1 n-1 n-1 a a a an-2 n-2 n-2 n-2 a a a a1 1 1 1 a a a a0 0 0 0 a a a an-1 n-1 n-1 n-1 a a a an-2 n-2 n-2 n-2 a a a a1 1 1 1 a a a a0 0 0 0 当突发的错误数当突发的错误数小于小于小于小于m m m m个时个时个时个时，每个码组中的误码个数小于，每个码组中的

16、误码个数小于2 2个个 通过奇偶效验可以检出。通过奇偶效验可以检出。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码12128 8、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码(续续续续)n 水平奇偶效验码水平奇偶效验码水平奇偶效验码水平奇偶效验码（续前）（续前）整个方阵作为一个整个方阵作为一个“码组码组”，长度为原来的，长度为原来的m m倍，可检出不大倍，可检出不大于于 m m个的突发错误个的突发错误;在未增加监督位的条件下，检错能力为原来的在未增加监督位的条件下，检错能力为原来的m m倍，这是倍，这是香农香农香农香农 信道编码定理

17、信道编码定理信道编码定理信道编码定理应用的一个例子。应用的一个例子。编解码所付的编解码所付的代价代价代价代价：缓存空间和延时增大。：缓存空间和延时增大。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码13138 8 8 8、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码(续续续续)n 方阵码（水平垂直奇偶效验码）方阵码（水平垂直奇偶效验码）方阵码（水平垂直奇偶效验码）方阵码（水平垂直奇偶效验码）在水平奇偶监督码的基础上增加列的奇偶效验。在水平奇偶监督码的基础上增加列的奇偶效验。可检出任一行和任一列的所有奇数个错误，及长度不大于可检出任一

18、行和任一列的所有奇数个错误，及长度不大于 行数行数（按列发）或不大于列数按列发）或不大于列数（按行发）的突发错误。按行发）的突发错误。设原来的信息位构成设原来的信息位构成MNMN的矩阵，加上监督位后构成的矩阵，加上监督位后构成 （M M1 1）（N N1 1）的矩阵，编码效率为：的矩阵，编码效率为：第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码14148 8 8 8、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码(续续续续)n n 群计数码群计数码群计数码群计数码 计算码组中信息位计算码组中信息位“1”“1”的个数，将计算值作为监督位

19、，可检的个数，将计算值作为监督位，可检出出 除除“0”“0”变变“1”“1”，“1”“1”变变“0”“0”成对出现之外的所有错误。成对出现之外的所有错误。n n 恒比码恒比码恒比码恒比码 从某确定长度的码组中挑选出那些从某确定长度的码组中挑选出那些“1”“1”和和“0”“0”的比例为恒的比例为恒定值定值 的码组作为许用码组，当收到违反恒比特性的码组即可判为的码组作为许用码组，当收到违反恒比特性的码组即可判为 误码。误码。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码1515 9 9、线性分组码、线性分组码n n 基本定义基本定义基本定义基本定义 码重码重码重码重W

20、W W W：码组码组/码字中非零码元的数目；码字中非零码元的数目；码距码距码距码距d d d d（汉明汉明汉明汉明(Hamming)(Hamming)(Hamming)(Hamming)距）距）距）距）：两码组：两码组/码字中对应码元位码字中对应码元位置上取值不同的个数称为码组置上取值不同的个数称为码组/码字间的距离，简称码距；码字间的距离，简称码距；最小码距最小码距最小码距最小码距d d d dminminminmin：准用码组准用码组/码字空间中任两码组间的最小码字空间中任两码组间的最小距离。距离。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码16169 9、线

21、性分组码、线性分组码n n 线性分组码的检错能力与码距的关系线性分组码的检错能力与码距的关系线性分组码的检错能力与码距的关系线性分组码的检错能力与码距的关系(1)(1)要在一个码组中检出要在一个码组中检出e e个误码，要求个误码，要求 d dminmin e e1 1 即任一码组产生小于等于即任一码组产生小于等于e e个误码时，都不会变成另一准个误码时，都不会变成另一准用码组用码组。图中，图中，C Ci i和和C Cj j是是 两个准用码组两个准用码组第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码17179 9、线性分组码、线性分组码n n 线性分组码的纠错能力与码

22、距的关系线性分组码的纠错能力与码距的关系线性分组码的纠错能力与码距的关系线性分组码的纠错能力与码距的关系(2)(2)要在一个码组中能纠正要在一个码组中能纠正t t个误码，要求个误码，要求 d d d dminminminmin 2t 2t 2t 2t1 1 1 1 将以将以t t为半径的为半径的“球球”内所有的禁用码组均判为球心中的准内所有的禁用码组均判为球心中的准用用 码组，可纠正码组，可纠正t t个以内的错误个以内的错误。图中，图中，C Ci i和和C Cj j是是 两个准用码组两个准用码组第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码18189 9、线性分组码

23、、线性分组码n n 线性分组码的检错纠错能力与码距的关系线性分组码的检错纠错能力与码距的关系线性分组码的检错纠错能力与码距的关系线性分组码的检错纠错能力与码距的关系 (3)(3)要在一个码组中能纠正要在一个码组中能纠正t t个误码，同时检出个误码，同时检出e(e e(e t t)个误码，要求个误码，要求 d d d dminminminmin e e e et t t t1 1 1 1 当误码数小于等于当误码数小于等于t t时，可纠正；时，可纠正；当误码数大于当误码数大于t t小于等于小于等于e e时，不会落入另一码组的纠错范时，不会落入另一码组的纠错范 围内围内第八章第八章第八章第八章 差错

24、控制编码差错控制编码差错控制编码差错控制编码19199 9、线性分组码、线性分组码n n 线性分组码的基本性质线性分组码的基本性质线性分组码的基本性质线性分组码的基本性质(定理定理定理定理)(1)(1)两许用码组之和（逐位模两许用码组之和（逐位模2 2和）仍为一许用码组和）仍为一许用码组（封闭性）；（封闭性）；(2)(2)码组间的最小距离等于非零码的最小重量。码组间的最小距离等于非零码的最小重量。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码20209 9、线性分组码、线性分组码n n 线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础

25、(1)(1)群的概念群的概念群的概念群的概念 若若G是非空集合，在是非空集合，在G中定义了一种代数运算，满足中定义了一种代数运算，满足（a）封闭性，对）封闭性，对 a、b G，恒有，恒有 ab G（b）结合律，对）结合律，对 a、b、c G，恒有，恒有 （ab）c a（bc）（c）有恒等元）有恒等元e存在，对存在，对 a G，有，有 e G，使，使 aeeaa（d）对）对 a G，有逆元，有逆元 a-1 G，使使 aa-1 a-1ae 则称则称G构成一个构成一个群群群群。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码21219 9、线性分组码、线性分组码n n 线性

26、分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(2)(2)矢量空间的概念矢量空间的概念矢量空间的概念矢量空间的概念 在群在群G中，若中，若 a、b G，恒有，恒有 abba，则，则称称G为为交换群交换群交换群交换群或或阿贝尔群阿贝尔群阿贝尔群阿贝尔群。在阿贝尔群在阿贝尔群G中定义中定义F域上的数乘、且分配率成立，域上的数乘、且分配率成立，a、b G，A F，有，有 A（ab）AaAb则称该群为则称该群为矢量空间矢量空间矢量空间矢量空间V V。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码22229 9、线性分组码、线性分组码n n 线性

27、分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(2)(2)矢量空间的概念矢量空间的概念矢量空间的概念矢量空间的概念(续续续续)矢量子空间矢量子空间矢量子空间矢量子空间 矢量空间矢量空间V中的一个子集中的一个子集S，若满足：，若满足：全全0矢量（恒等元矢量（恒等元e）在）在S中；中；S中的任意两个矢量的和（运算中的任意两个矢量的和（运算“”）也在）也在S中中 （封闭性）；（封闭性）；则称则称S为为子空间子空间子空间子空间。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码23239 9、线性分组码、线性分组码n n 线性分组码的数学基础线性分

28、组码的数学基础线性分组码的数学基础线性分组码的数学基础(3)(3)n n维线性空间维线性空间维线性空间维线性空间 一个由一个由2n个个n维二进制数组组成的集合，定义如下维二进制数组组成的集合，定义如下的加乘运算的加乘运算 则该集合构成一则该集合构成一n维线性空间维线性空间Vn。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码24249 9、线性分组码、线性分组码n n 线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(4)(4)子空间与线性分组码子空间与线性分组码 在在2n个个n维二进制数组中可选择维二进制数组中可选择2k个数组构成个数

29、组构成Vn上上的子空间，子空间上的元素构成线性分组码。的子空间，子空间上的元素构成线性分组码。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2525n n 线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(续续续续)(4)(4)子空间与线性分组码子空间与线性分组码 子空间子空间子空间子空间S S的选择：的选择：的选择：的选择：a a、包含尽可能多的可用码字包含尽可能多的可用码字(组组)，编码效率高，冗余度小；，编码效率高，冗余度小；b、可用码字、可用码字(组组)间的距离尽可能大，使有较大的容错性能。间的距离尽可能大，使有较大的容错性能

30、。线性空间线性空间Vn和和其子空间其子空间S的的形象表示。形象表示。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码26269 9、线性分组码、线性分组码n n 线性分组码示例线性分组码示例线性分组码示例线性分组码示例 例例1：4 4维线性空间维线性空间维线性空间维线性空间V V4 4及其子空间及其子空间及其子空间及其子空间S S V4的所有元素的所有元素 V4空间的一个子空间空间的一个子空间 容易验证它包含容易验证它包含“0”元素元素(0000),且满足按位求和运算且满足按位求和运算 的封闭性。的封闭性。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码

31、差错控制编码27279 9、线性分组码、线性分组码n n 线性分组码示例线性分组码示例线性分组码示例线性分组码示例 例例2：（6 6，3 3）线性分组码）线性分组码）线性分组码）线性分组码 可以验证：对可以验证：对3位的信息码组采用如下位的信息码组采用如下6为的码字集编码，为的码字集编码，该码字集构成一线性子空间。该码字集构成一线性子空间。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码28289 9、线性分组码、线性分组码n n 生成矩阵生成矩阵生成矩阵生成矩阵G G G G的概念的概念的概念的概念 选择线性空间选择线性空间V V中中k个线性无关个线性无关(独立独立

32、)的的n元组：元组：V1,V2,V3,Vk 以此为基构成所有以此为基构成所有2k个线性组合个线性组合S可以表示为：可以表示为：其中其中mi0或或1。显然，。显然，S是是V的一个子空间。的一个子空间。记记 则有则有 矩阵矩阵G称为称为生成矩阵生成矩阵生成矩阵生成矩阵。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码29299 9、线性分组码、线性分组码n n 生成矩阵生成矩阵生成矩阵生成矩阵G G G G的概念的概念的概念的概念(续续续续)例：利用矩阵例：利用矩阵G计算（许用）码字，已知生成矩阵计算（许用）码字，已知生成矩阵 编码前的信息码组为编码前的信息码组为110，

33、生成的码字为：，生成的码字为：第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码30309 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式(校正子校正子校正子校正子)例：具有纠正一位误码的分组码例：具有纠正一位误码的分组码 C C6 6C C5 5C C4 4C C3 3 C C2 2C C1 1C C0 0 n=7,k=4,n=7,k=4,信息位信息位 监督位监督位 r=nr=nk k3 3 传输过程中如果发生某一位错误，如在传输过程中如果发生某一位错误，如在

34、C C3 3位置出错，位置出错，则相当于则相当于 C C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0000E000E3 3000=C000=C6 6C C5 5C C4 4(C(C3 3 E E3 3)C)C2 2C C1 1C C0 0 其中：其中：E E3 31 1 定义一组确定误码位置的参量定义一组确定误码位置的参量:校正子校正子/伴随式伴随式 S S1 1S S2 2S S3 3 第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码31319 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴

35、随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式(续续续续)设建立设建立1 1 1 1位误码位误码位误码位误码与校正子的对应关系如下（亦可建立其它关系）与校正子的对应关系如下（亦可建立其它关系）由表格关系，校正子与误码由表格关系，校正子与误码E Ei i的关系，如表中的的关系，如表中的S S1 1，当，当 E E2 2、E E4 4、E E5 5、E E6 6中有一个为中有一个为1 1时，时，S S1 11 1；S S1 1E E6 6 E E5 5 E E4 4 E E2 2 同理可得，同理可得，S S2 2E E6 6 E E5 5 E E3 3 E E1 1 S S3

36、 3E E6 6 E E4 4 E E3 3 E E0 0 S1S2S3误码位置误码位置S1S2S3误码位置误码位置0010000001101001000001000000101100100000100000010011110000000110001000000 0000000 无误无误第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码32329、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式(续续续续)由此，当出现由此，当出现一位一位误码时，校正子能够确定误码的位

37、置。误码时，校正子能够确定误码的位置。当无误码时，显然有当无误码时，显然有 S S1 1E E6 6 E E5 5 E E4 4 E E2 20 0 S S2 2 E E6 6 E E5 5 E E3 3 E E1 10 0 S S3 3E E6 6 E E4 4 E E3 3 E E0 00 0 编码时编码时,通过选择监督位通过选择监督位C C0 0C C1 1C C2 2的取值来保证正常情况下：的取值来保证正常情况下：S S1 1C C6 6 C C5 5 C C4 4 C C2 20 0 S S2 2C C6 6 C C5 5 C C3 3 C C1 10 0 S S3 3C C6 6

38、C C4 4 C C3 3 C C0 00 0 上述方程亦称为上述方程亦称为监督方程监督方程监督方程监督方程。(*)(*)由监督方程可以解得，监督位由监督方程可以解得，监督位C C0 0C C1 1C C2 2的取值分别为：的取值分别为：C C0 0 C C6 6 C C4 4 C C3 3 C C1 1C C6 6 C C5 5 C C3 3 C C2 2C C6 6 C C5 5 C C4 4 给出一组信息码给出一组信息码C C6 6C C5 5C C4 4C C3 3，可计算出监督位，可计算出监督位C C2 2C C1 1C C0 0。构成码：。构成码：C C6 6C C5 5C C4

39、4C C3 3C C2 2C C1 1C C0 0。注意：注意：信息位与监督位间的关系为信息位与监督位间的关系为线性关系线性关系线性关系线性关系。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码33339 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式(续续续续)例（续前）：例（续前）：例（续前）：例（续前）：设信息码组设信息码组C C6 6C C5 5C C4 4C C3 301010101 C C2 2C C6 6 C C5 5 C C4 4 0 0 1

40、1 0 01 1 C C1 1C C6 6 C C5 5 C C3 3 0 0 1 1 1 10 0 C C0 0C C6 6 C C4 4 C C3 3 0 0 0 0 1 11 1 构成发送码字：构成发送码字：C C6 6C C5 5C C4 4C C3 3 C C2 2C C1 1C C0 0 01011010101101 发送码字发送码字0101110101011101，若接收时有一位，如，若接收时有一位，如C C5 5，出错：，出错：C C6 6(C(C5 5 E E5 5)C)C4 4C C3 3 C C2 2C C1 1C C0 00 00 00110101101 S S1 1C

41、 C6 6(C(C5 5 E E5 5)C C4 4 C C2 20 0 0 0 0 0 1 11 1(C(C6 6 C C5 5 C C4 4 C C2 2)E E5 5 S S2 2C C6 6(C(C5 5 E E5 5)C C3 3 C C1 10 0 0 0 1 1 0 01 1(C(C6 6 C C5 5 C C3 3 C C1 1)E E5 5 S S3 3C C6 6 C C4 4 C C3 3 C C0 0 0 0 0 0 0 0 0 00 0(C(C6 6 C C4 4 C C3 3 C C0 0)根据校正子根据校正子 S S1 1 S S2 2 S S3 3110110，

42、由表，可判断误码发生在，由表，可判断误码发生在C C5 5第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码3434 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式 前述的前述的监督方程监督方程监督方程监督方程可用矩阵形式表示可用矩阵形式表示 其一般形式为：其一般形式为：u un-1n-1u un-2n-2uu1 1u u0 0是发送码字是发送码字/码组，矩阵码组，矩阵H H称为称为监督矩阵监督矩阵监督矩阵监督矩阵。第八章第八章第八章第八章 差错控制编码差错控制

43、编码差错控制编码差错控制编码35359、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式(续续续续)对上例，观察对上例，观察P37P37（*）式（监督方程），有：）式（监督方程），有：S S1 1C C6 6 C C5 5 C C4 4 C C2 20 0S S2 2C C6 6 C C5 5 C C3 3 C C1 10 0 S S3 3C C6 6 C C4 4 C C3 3 C C0 00 0 方程组的矩阵表示形式为：方程组的矩阵表示形式为：第八章第八章第八章第八章 差错控制编码差错控

44、制编码差错控制编码差错控制编码36369 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式 其中，监督矩阵其中，监督矩阵H H为：为：校正子与误码的位置的关系校正子与误码的位置的关系 由由H H的列向量反映的列向量反映 监督矩阵的性质监督矩阵的性质监督矩阵的性质监督矩阵的性质：（a a）H H由码元间的监督关系唯一确定；由码元间的监督关系唯一确定；（b b）H H的行向量相互独立，当采用系统码结构时，具有形式的行向量相互独立，当采用系统码结构时，具有形式 ，其中，其中I Ir r是是rr

45、rr（r rn-kn-k）单位阵。）单位阵。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码37379 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式 在上例中，监督位的产生可表示为在上例中，监督位的产生可表示为 一般地，对于线性分组码一般地，对于线性分组码(n(n，k)k)，上述关系可表示为，上述关系可表示为 其中监督位其中监督位 r rn nk k：第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码38389 9、线性分组码、线性分

46、组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式 监督位矩阵的转置表达式为：监督位矩阵的转置表达式为：若将信息位排列在码组的前半部，监督排列在码组的后半部，若将信息位排列在码组的前半部，监督排列在码组的后半部，则有：则有：生成矩阵生成矩阵生成矩阵生成矩阵可定义为：可定义为：其中其中I Ik k是是kkkk的单位阵。系统码形式的发送码组可按下式产生的单位阵。系统码形式的发送码组可按下式产生第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码39399 9、线性分组码、线性分组码 生成矩阵的

47、构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式 生成矩阵生成矩阵G G与监督矩阵与监督矩阵H H之间的关系之间的关系 监督位矩阵监督位矩阵监督位矩阵监督位矩阵可表示为：可表示为：生成矩阵生成矩阵生成矩阵生成矩阵可表示为：可表示为：其中其中I Ik k是是kkkk的单位阵，的单位阵，I In-kn-k是是(n-k)(n-kn-k)(n-k)的单位阵的单位阵 由此得由此得 上述关系说明：生成矩阵的每一行都是一个有效的码字。上述关系说明：生成矩阵的每一行都是一个有效的码字。第八章第八章第八章第八章 差错控制编码差错控制编码差错控

48、制编码差错控制编码40409 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式 伴随式伴随式(校正子校正子)的定义的定义 设设 发送码字为发送码字为 接收码字为接收码字为 错误图样为错误图样为 则一般地，有则一般地，有 接收码字接收码字r r的的伴随式伴随式伴随式伴随式(校正子校正子)定义为定义为第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码41419 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、

49、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式 由前面分析，有由前面分析，有 其中其中H H的第的第i i列对应第列对应第i i位位单个错误单个错误单个错误单个错误时的伴随式时的伴随式/校正子校正子 伴随式只与错误图样和监督矩阵有关伴随式只与错误图样和监督矩阵有关伴随式只与错误图样和监督矩阵有关伴随式只与错误图样和监督矩阵有关，与发送的码字无关。，与发送的码字无关。上式中上式中e e是是1n1n的矩阵，而的矩阵，而H H是是rnrn的矩阵，所得结果的矩阵，所得结果 S S是二进制数的是二进制数的1r1r的矩阵（向量），所有可能组合的个数为的矩阵（向量），所有可能组合的个数为 若用伴随式的不同

50、组合表征不同的错误，则最多能够表若用伴随式的不同组合表征不同的错误，则最多能够表 征（纠正）征（纠正）2 2r r2 2n-kn-k个错误。个错误。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码42429 9、线性分组码、线性分组码 线性分组码的许用码字与可纠正的错误图样线性分组码的许用码字与可纠正的错误图样 对于线性分组码（对于线性分组码（n n，k k）所有许用码字和可纠正）所有许用码字和可纠正 的错误图样及组合可表示为一标准阵：的错误图样及组合可表示为一标准阵：其中其中U U1 1是许用码字集中的全是许用码字集中的全0 0码字。码字。第一行第一行第一行第一行为