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

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

1、数字通信原理数字通信原理第八章第八章 差错控制编码差错控制编码 (线性分组码部分线性分组码部分)2010 Copyright 2010 Copyright 1 1SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs1 1、差错控制编码的基本原理、差错控制编码的基本原理n 编码编码编码编码：在信息码组上附加一定位数的监督码元，使在信息码组上附加一定位数的监督码元，使其与信息位按某种规则相互关联；其与信息位按某种规则相互关联；n 检错与纠错检错与纠错检错与纠错检错与纠错：若数据在传输过程中发生差错，关联：若数据在传输过程中发生差错，关联关

2、系被破坏，从而可检出和关系被破坏，从而可检出和/或纠正错误或纠正错误第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2 2SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs 2 2、差错控制主要类型差错控制主要类型 检错重发（检错重发（检错重发（检错重发（ARQARQARQARQ）设备较简单；传输序列中冗余量较小；设备较简单；传输序列中冗余量较小；需要有反向信道支持；出错后重传造成延时较大。需要有反向信道支持；出错后重传造成延时较大。前向纠错（前向

3、纠错（前向纠错（前向纠错（FECFECFECFEC）适用于包括没有反向信道的场合；适用于包括没有反向信道的场合；出错时可纠正误码，无需重传，延时小；出错时可纠正误码，无需重传，延时小；传输序列中冗余量较大。传输序列中冗余量较大。混合系统混合系统混合系统混合系统 前向纠错（前向纠错（FECFEC）检错重发（检错重发（ARQARQ）出错较少时出错较少时FECFEC起作用；出错较多时起作用；出错较多时ARQARQ起作用起作用第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 3 3SCUT DT&P LabsSCUT

4、DT&P LabsSCUT DT&P LabsSCUT DT&P Labs 3 3、差错控制编码的分类差错控制编码的分类n n 线性码线性码线性码线性码：信息码与监督码之间的关系为线性关系；：信息码与监督码之间的关系为线性关系；非线性码非线性码非线性码非线性码：信息码与监督码之间的关系为非线性关系。：信息码与监督码之间的关系为非线性关系。n 分组码分组码分组码分组码：信息码与监督码以组为单位建立关系：信息码与监督码以组为单位建立关系；卷积码卷积码卷积码卷积码：监督码与本组和前面码组中的信息码有关。：监督码与本组和前面码组中的信息码有关。n n 系统码系统码系统码系统码：编码后码组中信息码保持原

5、图样顺序不变；编码后码组中信息码保持原图样顺序不变；非系统码非系统码非系统码非系统码：编码后码组中原信息码原图样发生变化。：编码后码组中原信息码原图样发生变化。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 4 4SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs4 4、错误的主要形式错误的主要形式n n 随机错误随机错误随机错误随机错误：误码的位置随机（误码间无关联），随机：误码的位置随机（误码间无关联），随机误码主要由白噪声引起；误码主要由白噪

6、声引起；n 突发错误突发错误突发错误突发错误：误码成串出现，主要由强脉冲及雷电等突：误码成串出现，主要由强脉冲及雷电等突发的强干扰引起；发的强干扰引起；n 混合错误混合错误混合错误混合错误：以上两种误码及产生原因的组合；：以上两种误码及产生原因的组合；第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 5 5SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs5 5、检错与纠错编码的示例检错与纠错编码的示例 三位二进制码的三种编码方法。三位二进码共有三位

7、二进制码的三种编码方法。三位二进码共有8种可能种可能 的组合：的组合：000，001，010，011，100，101，110，111 a.a.若若8 8个码组均用于表示不同的信息，任一位或一位以上的错个码组均用于表示不同的信息，任一位或一位以上的错 误都会变成另一码组，所以无法检错和纠错。误都会变成另一码组，所以无法检错和纠错。b.b.若将若将8 8个码组分成许用和禁用个码组分成许用和禁用(通信过程不会采用通信过程不会采用)两类：两类：许用码组许用码组许用码组许用码组：000000，011011，101101，110110 禁用码组禁用码组禁用码组禁用码组：111111，100100，0100

8、10，001001 因任何一位误码，都会变成禁用码组，所以可检出一位误码。因任何一位误码，都会变成禁用码组，所以可检出一位误码。c.c.若规定若规定 许用码组许用码组许用码组许用码组：000000，111111 禁用码组禁用码组禁用码组禁用码组：001001，010010，011011，100100，101101，110110 每个码组可携带每个码组可携带1 1比特信息，码组具有检测出两位及以下比特信息，码组具有检测出两位及以下 的误码，或纠正一位误码的能力。的误码，或纠正一位误码的能力。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2

9、010 Copyright 6 6SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs6 6、香农信道编码定理、香农信道编码定理 若信道容量为若信道容量为C C，信息传输速率为信息传输速率为R R，如果如果 R C R C，则存在则存在 编码方法，使错误概率编码方法，使错误概率 P PE E e e-nE-nEc c(R(R)其中其中 E EC C(R)(R)称为称为误差指数误差指数误差指数误差指数，n n 为为码组长度。码组长度。码组长度。码组长度。(采用适当的方法采用适当的方法采用适当的方法采用适当的方法增大增大增大增大n n n

10、 n，有利于减小，有利于减小，有利于减小，有利于减小P P P PE E E E)。误差指数误差指数误差指数误差指数特性曲线：特性曲线：信道容量信道容量C C作为曲线的作为曲线的 的参变量（包含了有关的参变量（包含了有关 S/NS/N等因素的影响）等因素的影响）第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 7 7SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs7 7、编码效率和冗余度编码效率和冗余度 假定分组码的长度为假定分组码的长度为n，其中

11、信息位为其中信息位为k，相应的监督相应的监督位为位为nk 编码效率编码效率编码效率编码效率定义为：定义为：冗余度冗余度冗余度冗余度定义为：定义为：通常冗余度越大，码的检错和纠错的能力越强。通常冗余度越大，码的检错和纠错的能力越强。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 8 8SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs8 8、几种常用的检错编码几种常用的检错编码n 奇偶校验码奇偶校验码奇偶校验码奇偶校验码 在信息码组在信息码组a an

12、-1n-1,a,an-2n-2,a,a1 1中加入监督位中加入监督位a a0 0，使编码后码组中使编码后码组中 “1 1”的个数为奇数（的个数为奇数（奇校验奇校验奇校验奇校验）或偶数（）或偶数（偶校验偶校验偶校验偶校验）。）。偶校验偶校验偶校验偶校验：取：取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

13、=a an-1n-1 a an-2 n-2 a a1 1 1 1第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 9 9SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labsn n 奇偶效验码（续）奇偶效验码（续）奇偶效验码（续）奇偶效验码（续）奇偶效验码码组间最小距离奇偶效验码码组间最小距离奇偶效验码码组间最小距离奇偶效验码码组间最小距离d d d dminminminmin2 2 2 2 证明（以偶效验为例）：因为证明（以偶效验为例）：因为 a an

14、-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大于或等于大于或等于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小于或等

15、于小于或等于2 2。综上，综上，d dminmin=2=2 第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 1010SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labsn n 奇偶效验码奇偶效验码奇偶效验码奇偶效验码(续续续续)编码效率编码效率编码效率编码效率为：为：k/nk/nk/(k+1)k/(k+1)；冗员度：；冗员度：1/(k+1)1/(k+1)；k k：信息位：信息位 奇偶效验码的检错能力奇偶效验码的检错能力奇偶效验码的检错能力奇偶效验码的

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

17、ight 2010 Copyright 11 11SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs 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-

18、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行行行行 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 当突发的错误数当突发的错误数小于

19、小于小于小于m m m m个时个时个时个时，每个码组中的误码个数小于，每个码组中的误码个数小于2 2个个 通过奇偶效验可以检出。通过奇偶效验可以检出。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 1212SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs8 8、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码(续续续续)n 水平奇偶效验码水平奇偶效验码水平奇偶效验码水平奇偶效验码（续前）（续前）整个方阵作为一个整个方

20、阵作为一个“码组码组”，长度为原来的，长度为原来的m m倍，可检出不大倍，可检出不大于于 m m个的突发错误个的突发错误;在未增加监督位的条件下，检错能力为原来的在未增加监督位的条件下，检错能力为原来的m m倍，这是倍，这是香农香农香农香农 信道编码定理信道编码定理信道编码定理信道编码定理应用的一个例子。应用的一个例子。编解码所付的编解码所付的代价代价代价代价：缓存空间和延时增大。：缓存空间和延时增大。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 1313SCUT DT&P LabsSCUT DT&P La

21、bsSCUT DT&P LabsSCUT DT&P Labs8 8 8 8、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码(续续续续)n 方阵码（水平垂直奇偶效验码）方阵码（水平垂直奇偶效验码）方阵码（水平垂直奇偶效验码）方阵码（水平垂直奇偶效验码）在水平奇偶监督码的基础上增加列的奇偶效验。在水平奇偶监督码的基础上增加列的奇偶效验。可检出任一行和任一列的所有奇数个错误，及长度不大于可检出任一行和任一列的所有奇数个错误，及长度不大于 行数行数（按列发）或不大于列数按列发）或不大于列数（按行发）的突发错误。按行发）的突发错误。设原来的信息位构成设原来的信息位构成M

22、MN N的矩阵，加上监督位后构成的矩阵，加上监督位后构成 （M M1 1）（N N1 1）的矩阵，编码效率为：的矩阵，编码效率为：第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 1414SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs8 8 8 8、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码、几种常用的检错编码(续续续续)n n 群计数码群计数码群计数码群计数码 计算码组中信息位计算码组中信息位“1 1”的个数，将计算值作为监督位

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

24、P LabsSCUT DT&P LabsSCUT DT&P Labs 9 9、线性分组码、线性分组码n n 基本定义基本定义基本定义基本定义 码重码重码重码重W W W W：码组码组/码字中非零码元的数目；码字中非零码元的数目；码距码距码距码距d d d d（汉明汉明汉明汉明(Hamming)(Hamming)(Hamming)(Hamming)距）距）距）距）：两码组：两码组/码字中对应码元位码字中对应码元位置上取值不同的个数称为码组置上取值不同的个数称为码组/码字间的距离，简称码距；码字间的距离，简称码距；最小码距最小码距最小码距最小码距d d d dminminminmin：准用码组准用

25、码组/码字空间中任两码组间的最小码字空间中任两码组间的最小距离。距离。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 1616SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码的检错能力与码距的关系线性分组码的检错能力与码距的关系线性分组码的检错能力与码距的关系线性分组码的检错能力与码距的关系(1)(1)要在一个码组中检出要在一个码组中检出e e个误码，要求个误码，要求 d dminmin e e1

26、1 即任一码组产生小于等于即任一码组产生小于等于e e个误码时，都不会变成另一准个误码时，都不会变成另一准用码组用码组。图中，图中，C Ci i和和C Cj j是是 两个准用码组两个准用码组第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 1717SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码的纠错能力与码距的关系线性分组码的纠错能力与码距的关系线性分组码的纠错能力与码距的关系线性分组码的纠错能力与

27、码距的关系(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是是 两个准用码组两个准用码组第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 1818SCUT DT&P LabsSCUT DT&P La

28、bsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码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时，不会落入另一码

29、组的纠错范时，不会落入另一码组的纠错范 围内围内第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 1919SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码的基本性质线性分组码的基本性质线性分组码的基本性质线性分组码的基本性质(定理定理定理定理)(1)(1)两许用码组之和（逐位模两许用码组之和（逐位模2 2和）仍为一许用码组和）仍为一许用码组（封闭性）；（封闭性）；(2)(2)码组间的最小距离等于非零码

30、的最小重量。码组间的最小距离等于非零码的最小重量。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2020SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(1)(1)群的概念群的概念群的概念群的概念 若若G是非空集合，在是非空集合，在G中定义了一种代数运算，满足中定义了一种代数运算，满足（a）封闭性，对）封闭性，对 a、b G，恒

31、有，恒有 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构成一个构成一个群群群群。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2121SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码

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

33、t 2222SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(2)(2)矢量空间的概念矢量空间的概念矢量空间的概念矢量空间的概念(续续续续)矢量子空间矢量子空间矢量子空间矢量子空间 矢量空间矢量空间V中的一个子集中的一个子集S，若满足：，若满足：全全0矢量（恒等元矢量（恒等元e）在）在S中；中；S中的任意两个矢量的和（运算中的任意两个矢量的和（运算“”）也在）也在S中中 （封闭性）；（封闭性）；则称则称S为为子空间

34、子空间子空间子空间。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2323SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(3)(3)n n维线性空间维线性空间维线性空间维线性空间 一个由一个由2n个个n维二进制数组组成的集合，定义如下维二进制数组组成的集合，定义如下的加乘运算的加乘运算 则该集合构成一则该集合构成一n维线性空间

35、维线性空间Vn。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2424SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(4)(4)子空间与线性分组码子空间与线性分组码 在在2n个个n维二进制数组中可选择维二进制数组中可选择2k个数组构成个数组构成Vn上上的子空间，子空间上的元素构成线性分组码。的子空间，子空间上的元素构成线性分组

36、码。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2525SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labsn n 线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础线性分组码的数学基础(续续续续)(4)(4)子空间与线性分组码子空间与线性分组码 子空间子空间子空间子空间S S的选择：的选择：的选择：的选择：a a、包含尽可能多的可用码字包含尽可能多的可用码字(组组)，编码效率高，冗余度小；，编码效率高，冗余度小；b、可用码字、可用码字

37、(组组)间的距离尽可能大，使有较大的容错性能。间的距离尽可能大，使有较大的容错性能。线性空间线性空间Vn和和其子空间其子空间S的的形象表示。形象表示。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2626SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码示例线性分组码示例线性分组码示例线性分组码示例 例例1：4 4维线性空间维线性空间维线性空间维线性空间V V4 4及其子空间及其子空间及其子空间及其

38、子空间S S V4的所有元素的所有元素 V4空间的一个子空间空间的一个子空间 容易验证它包含容易验证它包含“0”元素元素(0000),且满足按位求和运算且满足按位求和运算 的封闭性。的封闭性。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2727SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 线性分组码示例线性分组码示例线性分组码示例线性分组码示例 例例2：（6 6，3 3）线性分组码）线性分组码）线性分组

39、码）线性分组码 可以验证：对可以验证：对3位的信息码组采用如下位的信息码组采用如下6为的码字集编码，为的码字集编码，该码字集构成一线性子空间。该码字集构成一线性子空间。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2828SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 生成矩阵生成矩阵生成矩阵生成矩阵G G G G的概念的概念的概念的概念 选择线性空间选择线性空间V V中中k个线性无关个线性无关(独立独立)

40、的的n元组：元组：V1,V2,V3,Vk 以此为基构成所有以此为基构成所有2k个线性组合个线性组合S可以表示为：可以表示为：其中其中mi0或或1。显然，。显然，S是是V的一个子空间。的一个子空间。记记 则有则有 矩阵矩阵G称为称为生成矩阵生成矩阵生成矩阵生成矩阵。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 2929SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码n n 生成矩阵生成矩阵生成矩阵生成矩阵G G G

41、G的概念的概念的概念的概念(续续续续)例：利用矩阵例：利用矩阵G计算（许用）码字，已知生成矩阵计算（许用）码字，已知生成矩阵 编码前的信息码组为编码前的信息码组为110，生成的码字为：，生成的码字为：第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 3030SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监

42、督矩阵和伴随式(校正子校正子校正子校正子)例：具有纠正一位误码的分组码例：具有纠正一位误码的分组码 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 传输过程中如果发生某一位错误，如在传输过程中如果发生某一位错误，如在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

43、1C C0 0 其中：其中：E E3 31 1 定义一组确定误码位置的参量定义一组确定误码位置的参量:校正子校正子/伴随式伴随式 S S1 1S S2 2S S3 3 第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 3131SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式(续续续续)设建立

44、设建立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 3E E6 6 E E4 4 E E3 3 E E0 0 S1S2S3误码位置误码位

45、置S1S2S3误码位置误码位置0010000001101001000001000000101100100000100000010011110000000110001000000 0000000 无误无误第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 3232SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督

46、矩阵和伴随式(续续续续)由此，当出现由此，当出现一位一位误码时，校正子能够确定误码的位置。误码时，校正子能够确定误码的位置。当无误码时，显然有当无误码时，显然有 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

47、 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 上述方程亦称为上述方程亦称为监督方程监督方程监督方程监督方程。(*)(*)由监督方程可以解得，监督位由监督方程可以解得，监督位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

48、C2 2C C1 1C C0 0。构成码：。构成码：C C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0。注意：注意：信息位与监督位间的关系为信息位与监督位间的关系为线性关系线性关系线性关系线性关系。第八章第八章第八章第八章 差错控制编码差错控制编码差错控制编码差错控制编码2010 Copyright 2010 Copyright 3333SCUT DT&P LabsSCUT DT&P LabsSCUT DT&P LabsSCUT DT&P Labs9 9、线性分组码、线性分组码 生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式生成矩阵的构建、监

49、督矩阵和伴随式生成矩阵的构建、监督矩阵和伴随式(续续续续)例（续前）：例（续前）：例（续前）：例（续前）：设信息码组设信息码组C C6 6C C5 5C C4 4C C3 301010101 C C2 2C C6 6 C C5 5 C C4 4 0 0 1 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 发送码字发

50、送码字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 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