第三章线性分组码

1、State Key Laboratory of Integrated Services Networks 第三章第三章 线性分组码线性分组码要求掌握的内容要求掌握的内容线性分组码的定义及性质线性分组码的定义及性质码的一致校验矩阵和生成矩阵码的一致校验矩阵和生成矩阵码的伴随式、标准阵列及译码码的伴随式、标准阵列及译码汉明码及译码汉明码及译码第一节第一节 线性分组码基本概念线性分组码基本概念线性分组码定义线性分组码定义生成矩阵生成矩阵校验矩阵校验矩阵对偶码、系统码和缩短码对偶码、系统码和缩短码编码与译码编码与译码对对 二进制二进制(n, k)码，信息数量（或合法码字数）为码，信息数量（或合法码字数

2、）为2k，可用编码空间的点数为，可用编码空间的点数为2n个。个。任一种任一种2k信息集合到二进制序列集合信息集合到二进制序列集合(2n)的映射都的映射都是一种是一种(n, k)码。因此总共可能的编码方案有码。因此总共可能的编码方案有 种。如，共有种。如，共有1029种种(100,50)码。码。译码运算量：如果直接用最大似然序列译码，对译码运算量：如果直接用最大似然序列译码，对一般性的编码而言，正比于一般性的编码而言，正比于n* 2k ，对，对(100,50)码，码，则为则为1017。几乎是不可能译码的。几乎是不可能译码的。22nk为什么要引入线性码为什么要引入线性码发现或构造好码是信道编码研究

3、的主要问题发现或构造好码是信道编码研究的主要问题编码方案太多，以至全局搜索是不可能的编码方案太多，以至全局搜索是不可能的现实的做法是对编码方案加以一定的约束，在一个子集中现实的做法是对编码方案加以一定的约束，在一个子集中寻找局部最优寻找局部最优这种约束即要能包含尽可能好的码，又要便于分析，便于这种约束即要能包含尽可能好的码，又要便于分析，便于译码译码目前对线性系统的研究远比非线性系统充分目前对线性系统的研究远比非线性系统充分State Key Laboratory of Integrated Services Networks 一、线性一、线性分组码分组码基本概念基本概念(P52-54)2k2

4、n利用线性空间中的子空间作为许用码字的编码利用线性空间中的子空间作为许用码字的编码称线性码称线性码当线性空间为有限维空间时即为线性分组码当线性空间为有限维空间时即为线性分组码GF(q)上的上的n维线性空间维线性空间Vn中的一个中的一个k维子空间维子空间Vn,k称为称为(n,k)线性分组码线性分组码)(min,iknCCwdi性质：性质：n, k, d线性分组码的最小距离等于非线性分组码的最小距离等于非零码字的最小重量零码字的最小重量码的最小距离码的最小距离在大部分情况下，码的最小距离是码设计在大部分情况下，码的最小距离是码设计的首选目标的首选目标它代表了渐近性能它代表了渐近性能大部分分组译码算

5、法的译码能力也限于最小距大部分分组译码算法的译码能力也限于最小距离离线性分组码的特点线性分组码的特点全零序列是许用码字全零序列是许用码字与任一码字的距离谱都相同与任一码字的距离谱都相同只须考虑重量谱只须考虑重量谱自由距就是最小码重量自由距就是最小码重量平均差错概率就是当发全零序列时的条件差错概率：平均差错概率就是当发全零序列时的条件差错概率：Pe= x1P(x1)P(e|x1)= P(e|全零全零)State Key Laboratory of Integrated Services Networks 如何根据如何根据k个信息比特来确定对应的个信息比特来确定对应的n-k个校验比特？个校验比特？

6、利用校验矩阵利用校验矩阵利用生成矩阵利用生成矩阵给定参数给定参数n、k和和dState Key Laboratory of Integrated Services Networks 三、码的生成矩阵三、码的生成矩阵(P56)从线性空间的角度描述分组码从线性空间的角度描述分组码由于由于n,k,d线性分组码是一个线性分组码是一个k维线性空间维线性空间因此，必可找到因此，必可找到k个线性无关的矢量，能张成该线性空间个线性无关的矢量，能张成该线性空间kCCC,21是是k个线性无关的矢量，则对任意个线性无关的矢量，则对任意C，可有：，可有：kkmmmCCCC2211mGCCCkkmmm2121,G称为该

7、分组码的生成矩阵称为该分组码的生成矩阵设设注：注：1)生成矩阵生成矩阵G中的每一行都是一个码字中的每一行都是一个码字2)任意任意k个线性独立的码字都可以作为生成矩个线性独立的码字都可以作为生成矩阵阵3)给定一个给定一个n,k,d线性分组码，其生成矩阵可线性分组码，其生成矩阵可有多个有多个 State Key Laboratory of Integrated Services Networks 四、码的校验矩阵四、码的校验矩阵(P54)从线性方程组的角度描述分组码从线性方程组的角度描述分组码n-k个校验位可用个校验位可用k个已知的信息位表示出来个已知的信息位表示出来个校验位个信息位knknknk

8、knnncccccc02121knknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc, 022, 011, 00, 222, 211, 22, 122, 111, 11000100010001021)(,011, 0, 21, 2, 11, 1ccchhhhhhnnnknknnknknnknknknnkn列行，校验矩阵校验矩阵校验矩阵H与任意一个码字之积为零，因此有与任意一个码字之积为零，因此有0GHT45604561456245631101001111111011ccccccccccccccccExamples1000110

9、010001100101110001101HState Key Laboratory of Integrated Services Networks 五、几个概念五、几个概念(P57-58)对偶码、系统码和缩短码对偶码、系统码和缩短码对系统码对系统码PIGkknTIPH缩短码缩短码 从从n,k,d线性分组码的所有码字中，把前面线性分组码的所有码字中，把前面i位全为零的码字挑选出来构成一个新的子集，该位全为零的码字挑选出来构成一个新的子集，该子集即为子集即为n,k,d的缩短码。的缩短码。问题：最小汉明距离有什么变化？问题：最小汉明距离有什么变化？第二节第二节 线性分组码的译码线性分组码的译码伴随

10、式伴随式汉明码汉明码标准阵列标准阵列State Key Laboratory of Integrated Services Networks 一、伴随式一、伴随式(P59)设发送码字设发送码字021,cccnnC接收序列接收序列021,rrrnnR根据错误图样的概念，根据错误图样的概念，R=C+ETTTEHHECRHS)(S是校验矩阵是校验矩阵H中某几列数据的线性组合中某几列数据的线性组合两个定理两个定理定理定理1：n,k,d线性分组码有最小汉明距离线性分组码有最小汉明距离d的充要条件是，的充要条件是，H矩阵中任意矩阵中任意d-1列线性无关列线性无关定理定理2：n,k,d线性分组码最大可能的最

11、小线性分组码最大可能的最小汉明距离汉明距离d等于等于n-k+1Singleton限限(n, k, d)线性分组码的最大可能的最小距离小于等线性分组码的最大可能的最小距离小于等于于n-k+1, 即即dn-k+1若系统码的最小距离若系统码的最小距离d=n-k+1，则此码为极大最，则此码为极大最小距离可分码，简称小距离可分码，简称MDS码码State Key Laboratory of Integrated Services Networks 二、汉明码二、汉明码参数参数 码长：码长： n=2m-1 信息位长度：信息位长度：k=2m-1-m 最小汉明距离：最小汉明距离：d=3 校验矩阵有校验矩阵有

12、m行，行，2m-1列，取互不相同的列，取互不相同的m重构重构成成汉明码的对偶码是一个汉明码的对偶码是一个2m-1, m, 2m-1码，也称为单纯码或码，也称为单纯码或极长码，也称为最长线性移存器码。极长码，也称为最长线性移存器码。如果用如果用BPSK，并看成，并看成2m进制调制时，是一种自相关性最好的调制方式进制调制时，是一种自相关性最好的调制方式GF(2)上的7,4,3汉明码，001,010,011,100,101,110,111,000。校验矩阵为：Examples:101010111001101111000HState Key Laboratory of Integrated Servi

13、ces Networks 三、标准阵列译码(p63)线性分组码的基本译码步骤线性分组码的基本译码步骤 Step1: 由接收到的序列由接收到的序列R，计算伴随式，计算伴随式S=RHT； Step2: 若若S=0，正确接收；若，正确接收；若S不为零，寻找不为零，寻找错误图样；错误图样； Step3: 由错误图样解出码字由错误图样解出码字C=R-E。标准阵列标准阵列 根据许用码字将禁用码字进行分类，根据许用码字将禁用码字进行分类， 分类的依据是错误图样。分类的依据是错误图样。C1C2kC2CiE2E3knE2C2+E2C2+E3Ci+E3Ci+E222ECk32ECkknkEC22C2+Ci+knE

14、2knE2码字码字禁用码字禁用码字标准阵列译码标准阵列译码(陪集首陪集首)两个概念两个概念 完备译码完备译码:n,k,d线性分组码的所有线性分组码的所有2n-k个伴随式在译码过程中都用来纠正所有个伴随式在译码过程中都用来纠正所有小于等于小于等于t=(d-1)/2个随机错误以及部分个随机错误以及部分大于大于t的错误图样。的错误图样。 限定距离译码限定距离译码：译码时不能达到码的纠：译码时不能达到码的纠错能力错能力第三节第三节 由已知码构造新码的方法由已知码构造新码的方法扩展码扩展码删余码删余码增广码增广码(增信删余码增信删余码)增余删信码增余删信码延长码延长码一、扩展码00111HHn+1,k,

15、d 或或n+1,k,d+1增加一个全校验位增加一个全校验位二、删余码二、删余码在原码基础上删去一个校验元。在原码基础上删去一个校验元。n-1, k三、增广码三、增广码 在原码基础上，增加一个信息元，删去一个校在原码基础上，增加一个信息元，删去一个校验元验元 n,k+1,dGG111ada=mind, n-diaC1CCki2, 2 , 1四、增余删信码四、增余删信码删去一个信息元，增加一个校验元删去一个信息元，增加一个校验元 若若n,k,d码的最小汉明距离码的最小汉明距离d为奇数，则为奇数，则挑选所有偶数重量的码字，即可构成挑选所有偶数重量的码字，即可构成n,k-1,d+1增余删信码增余删信码

16、五、延长码五、延长码对增广码再添加一个全校验位。对增广码再添加一个全校验位。n+1,k+111nkR用多个已知码构造新码用多个已知码构造新码直和直和: n, k1+k2, dmind1, d2笛卡尔积：笛卡尔积：n1+n2, k1+k2, mind1,d2链接链接: n1+n2, k2, dmind1, d2C1, C1+C2构造构造: 2n, k1+k2, min2d1,d2直积：直积：n1n2, k1k2, d1d2第四节第四节 线性码的纠错能力线性码的纠错能力(p79)码的重量分布码的重量分布(p73)普洛特金限普洛特金限(P限限)汉明限汉明限V-G限限 State Key Labora

17、tory of Integrated Services Networks 一、码重量分布一、码重量分布 码的性能不仅由码的最小汉明距离决定，还可码的性能不仅由码的最小汉明距离决定，还可由码的重量分布有关由码的重量分布有关 niiinnxAxAxAAxA010马克威伦马克威伦(MacWilliams)恒等式恒等式()11( )2(1)()n knxxA xxB0( )niiiA xAx0( )niiiB xB x设二进制设二进制n, k线性分组码及其线性分组码及其n, n-k对偶码的对偶码的重量算子分别是重量算子分别是则它们之间有如下关系：则它们之间有如下关系：线性分组码的不可检错误概率线性分组

18、码的不可检错误概率线性码是同距离分布码线性码是同距离分布码若码字等概发送若码字等概发送平均不可检平均不可检 错误概率错误概率211(1)kniniudjieejippA pp1(1)niniudieeipA pp()2(1(1) )nkkudepp译码错误与译码失败概率译码错误与译码失败概率teD译码器正确译码的概率译码器正确译码的概率译码错误概率译码错误概率译码失败概率译码失败概率误码率误码率0(1)tin iwceeinpppi 1(1)nin iweieei tpB pp 1wfwcweppp State Key Laboratory of Integrated Services Networks 普洛特金（普洛特金（P）限）限State Key Laboratory