第六章 纠错编码 4 --线性分组码

1、信息编码理论信道编码定理和方法 之 线性分组码线性分组码线性分组码矢量空间与码空间矢量空间与码空间线性分组码编码线性分组码伴随式与译码码的纠检错能力与MDC码完备码与汉明码分组码的性能极限矢量空间与码空间1212( , ,)-( ,)-,knIi iikCc ccnnnnn分组码： 信息： 位信息 码字： 位码字 码字又可以看成一个 重矢量（ 维线性空间中的一个矢量） 个码元正是 个矢量元素，这样可以从矢量空间的角度来分析和理解分组码。矢量空间定义01,(1),(,),0,1,2,1( , ),;,(),iiiii nijiiijijijFnVvvvvF jnaFaa bFVaaa VVVVV

2、VVVVVVV VVVVV 对于数 域（ ）上 重有序元素的集合 ，若满足条件： 集合 中矢量元素在矢量加运算下构成加群； 集合 中矢量元素与标量的标乘封闭在 中，即 和 分配律、结合律成立，即 和(),()()iiiiiabababa bVFnnnnVVVVV 则称集合 是数域 上的 维矢量空间，也称 维线性空间， 维矢量又称 重，因此码字也叫码矢。矢量空间运算法则01(1)01(1)0011(1)(1)01(1)0011(1)(1)(,),(,),:(,)(,)iiii njjjj nijijiji nj niiii nijijiji nj nvvvvvvaFvvvvvvaavavavvv

3、vvvvVVVVVV V 对于矢量及标量有如下运算法则 矢量加： 标乘： 点积或内积： 以上三者，矢量加和标乘所得结果为矢量，而内积所得结果为标量。矢量空间相关定义和解释121122331212112212,(),0 (),ikkiiikiiiiiiiFaaaaaFFaaaaFaV VVVVVVVVVVV VVV VVVVVVV VV 对于域 上的若干矢量及若满足 ，则称是的线性组合。 对于域 上的若干矢量若满足 ，且 不全 线性组合： 线性相为零 ，则称矢量线 关：性相关。矢量空间相关定义和解释12112212121200,iiiiiiaaaaaaVVVV VVV VVV VV 若时， 才成

4、立，则称矢量线性无关。 若线性相关，则可以通过移项将中任一 矢量表示成其他矢量的线性组合。 若线性无关，则这组矢量中的任何一个 都不能由其他矢量的线性组线性相关：合生成。矢量空间相关定义和解释12,0kssijijnnnnVVV VVVVV VVV如果存在一组线性无关的矢量，这些矢量的线性组合的集合可以构成一个矢量空间，则称这组矢量为这个矢量空间的基底。 维矢量空间应包含 个基底，即 个基底张成了 维矢量空间。若矢量空间 的一个元素子集也能构成一个矢量空间，则称为 的子空间。若两个矢量的点积为零，即 矢量空间的基底： 子空间： 矢量正，则称和正交交：。矢量空间相关定义和解释1212ijnV V

5、VVVVV若某矢量空间中的任意元素与另一个矢量空间中的任意元素正交（=0），称这两个矢量空间正交。若两个矢量空间的基底正交，这两个矢量空间一定正交。若n维矢量空间中的两个子空间和正交，称和为对偶空间，其中一个 矢量空间正交空间是另一个空： 对偶空间： 间的零空间（也称零）。 化空间例3-1 基底及其性质3-1( , ),()(1,0)(0,1)( , )(1,0)(0,1)(-1,0)(0,-1)x yx yRx yxy例 直角坐标系中的任何点都可以用一个二维矢量来表示，其中实数域 ，则可以认为： 两维空间是由两个矢量和 作为基底张成的，空间的任意一矢量 可由这两个基底线性组合而成。 两维空间

6、是由两个矢量和作为基底张成的， 空间的任意一矢量可由这两个基底线性组合而成。 ( , )-(-1,0)-(0,-1)x yxy 例3-1 基底及其性质10(1,0)(0,1)3(1,0)( 1,0) (0,1)(0-1,-1) 基底并非是唯一的。把矢量元素中包含一个，而其余为的那组 基底称为自然基底，如和。自然基底在保持正交的前提下任意缩放或旋转后仍然是基底。由例可知：如 。注意nn引入子空间概念后，维数指线性空间基底的 个数，重数指构成矢量的有序元素的个数，两 任何子空间都包含零矢量，因为它是矢量加法单位元。 维矢量空间的元素可用 重来表示，其维数和重数是 一致的； 矢量空间与其子空间一定具

7、有相同的重数，不同的维 数。维数重数，当维数重数，表者不同明是。子空间。码字与矢量、矢量空间 222 2 -2nkinkknnnnCnnnknnnnVVV码字是 个码元的有序排列，是 维 重矢量空间的元素之一，但是 例如： 位二进制信息有种组合，如果将一个信息组合对应成一个码字，那么总共有个码字；而 重码矢所在的 维 重矢量空间应包含种 重矢量，显然还存矢量空间的元素不一定种 重矢量是不在着码字。是码字。码字与矢量、矢量空间01(1)(,)( , )iiii nknnknncccqn kqqkkqqnnqqCCCCVV线性分组码的码集 一定是的一个子空 为便于区分，码字写作，将码字的集合写作

8、，称为码集。 对于一般 进制分组码，编码前有种信息组合，属于 元域上 维 重矢量空间；编码后有种可能码集 不一定能构成的码字组合，属于 元域上 维 重矢量空间；的通一个子空间，常间。分组码编码任务nkqqknkknn 映射到 分组码的任务： 在种可能的组合中选择其中个构成一个 维 重子空间作为码空间。 确定由 维 重矢量空间维 重矢量空间的 映射方法。 码空间的不同选择方法及信息组与码组的不同映射方 法构成不同的分组码。线性分组码矢量空间与码空间线性分组码编码线性分组码编码线性分组码伴随式与译码码的纠检错能力与MDC码完备码与汉明码分组码的性能极限线性分组码基本概念011-1210-1210(

9、 ,()(),22(.(,)(,)qkknnksymbolncodewordXx xxqqqqkmmm mcccnck把信息流的每 个码元分成一组，通过线性变换，映射成由 个码元组成的码字。码元的值取自字符集时是二进制码，时是 进制元）码位信息元 线性分组可写成： 码字可写：成： 码1121( , )/lnln( , )/lnbqqbbnqNb nn kRk nckMqkqn kRqcNnn 二进制情况下： 个码元符号可携带 比特信息。 进制情况下（， 为正整数）： 个码元符号可携带 比特信息。长度为 的 元 分组码可以映射为长度为的二元分组码。 对于二元分组码： 对于 元分 比特 码元： 码

10、率（编码效率）组码：线性分组码基本概念例3-3 线性分组码生成矩阵2105 4 3 2 1 052413022112100203-3(6,3)()();mm m mCc c c c c ccm cm cm cmmcmmm cmmC例： 二进制线性分组码输入信息组是 编码输出是；已知输入输出码元 之间的关系式是 求:(1)码集 (2)编码时的映射算法;例3-3 线性分组码生成矩阵52413022112100205 4 3 2 1 0210100111()() 010110001011cmcmcmcmmcmmmcmmc c c c c cm m m C = m G解：(1)将关系式写成线性方程，然

11、后写成矩阵形式 例3-3 线性分组码生成矩阵83解(续1）：(1)将信息组2种组合代入矩阵计算，可以得到各个码字。例3-3 线性分组码生成矩阵210(2(2)33(100111)(010110)(001011)mmmGCGCm G解 续 ）： 以上编码过程中，核心因素是矩阵 ，它决定了编码的线性变换规则，也决定了码集 。矩阵可以看成由 个行矢量构成，这 个行矢量线性无关，所有码字都是这三个行矢量的线性组合。 例3-3 线性分组码生成矩阵63-3(2)62648GFn 3由例可知： 二进制码取值于，位二进制数本应有 种组合，而k=3的信息组只有2种组合， 一一对应到码字C，可见码集C只包含了64

12、种组合 中的8种，它是一个子空间。 生成矩阵G的3个行矢量线性无关，作为基底张成 了一个3维6 码集其重的实是码空间，一个子空它是6维6重空间间，只要找到一组的子空合适的基底 。 间 它们的线性组合就可以产生整个码集。线性分组码生成矩阵12101210121 01210,(,),(,)(,)(kkkknnkknmmm mkkkmmm mnkccc cmmm mc mCC线性映射 令是一组个）二进制信息码元，它可以看作是 维 重空间中的一个矢量,也可以看作是1 k的矩阵， 编码后，输出码字长度增加到是 维n重码空间中的矢量。可以写作 编码中最重要的是要研究信息与码字的一一对应映射关系，即121

13、0,)ncc c线性分组码生成矩阵12101(1)2(2)1100-121 01210,0,1,1,1,0jkkjkkjkkjjjijijinnkkjcmmm mcmgmgm gm ggikgimjc cc cmmm mCCCm G对线性分组码：码集 中任意一个码字 的第 个码元都是信息元的线性组合，规则如下： 其中 实际上 表示第 个信息元对第 个码元的影响。 写成矩阵形式：10kknG 式中，它称为是该码的生成矩矩阵行 列的阵gg线性分组码生成矩阵(1)(1)(1)1(1)01(1)11100(1)0100(1)(2)10-11,1,1,0knkknnk nk nii ni niikkgg

14、gggggggggg gikiCmk-110gGgggG 其中 是 中的第 行的行矢量。 按分块矩阵运算法则，可以将 改写成 g-221100kkmmmggg线性分组码生成矩阵2ikGkgkkknnnC由以上推导可知： 任何码字都是生成矩阵 的 个行矢量的线性组合， 每个行矢量 既是基底又是码字。 只要 个行矢量线性无关，就可以作为 个基底张 成一个 维 重矢量空间，它是 维 重空间的一个 子空间，子空间的所有个矢量构成码集 。 不同的生成矩阵产生不同的码，生成矩阵的特点 决定了码字的特点。线性分组码生成矩阵kk由以上推导可知（续1）： 编码涉及 码集 和 映射 两个因素，而构成空间的 基底并

15、非唯一的，所以不同的基底或生成矩阵可能 产生相同的码集；码集相同，映射方法不同时，仍 称为不同的编码，或称为等效编码。 由于子空间是 维的，因此生成矩阵的秩是 。线性分组码生成矩阵,kk由以上推导可知（续2）： 将基底线性组合，挑出其中的 个矢量 只要满足线性 无关的条件，仍可以作为基底张成同一个码空间。反 映到矩阵，等效于通过行运算（行交换、行线性组合） 改变生成矩阵的形式，而不改变码集，只要保证矩阵 的秩仍是 。例如任何生成矩阵都可以通过运算转化成 系统形式（即系统码的生成矩阵）。系统码12011 0( , )kkn kCmmm cc cknkn kkkn 系统码的码字具有如下形式：由系统

16、码的特点可知： 系统码的前 位一定与信息组各比特相同，其余 系统码：把信息原封不动地搬到码字前 位的码。非系统码的生成矩阵可以通过行运算转 位是一致校验位，是 个信息位的线性组合。 ，对应的两个生成矩阵是等效的，生成 的码也是等效的（码集相同，变为系统码 映射不同）。 的生成矩个阵 每, )k 线性码都可以找到一个系统线性码与之等效。系统码(1)(1)(1)1(1)0()1(1)11100(1)0100(1)(1)(1)1(1)01(1)11100(1)0100|1000100001knkkkkn knnk nkn kkkn kn kgggGIPggggggppppppppp 系统码的生成矩阵

17、为系统形式 对偶空间和对偶码-( , )( - )( - )2( , - )( , )n kn kknnnn kn kn n kn kCDD 对偶空间： 与任何一个线性分组码的码空间 相对应，一定存在一个对偶空间 。事实上，码空间基底数 只是 维 重空间的全部 个基底的一部分，由另外个基底所张成的空间，称为对偶空间 。 对偶码： 可以用另外个基底产生一个有个码矢的线性码，称为线性码的对偶码。校验矩阵-( - )( , - )Hn kn knHn n kCDC 码空间 的校验矩阵 ： 将对偶空间 的个基底排列成矩阵，称为码空间 的校验矩阵 ，它是对偶码的生成矩阵，它的每一行都是对偶码的一个码字。

18、 码空间与对偶空间的相互关系( , )n kHCDCDGCDHDCCDCDc 码空间 和对偶空间 的关系和 的对偶是相互的， 是 的生成矩阵， 的校验矩阵； 则是 的生成矩阵， 的校验矩阵。 由于 的基底和 的基底正交，空间 和 也正交，互为零空间，即线性码的任意一个码字 也必定正交于校验矩阵 的任意一个行矢量 1()1 ()()()0Tnnn kn kTk nnn kkn kcHGH0G此式可以用来验证一个n重矢量是否为码字：若等式成立，该n重必为码字， 。 由于生成矩阵 的每一个行矢量都是一个码字，因此有 否则不 是 码字 系统码的校验矩阵Tkn-kGI |PH = -HP |I系统 的校

19、验矩阵 上式中的负号在二进制的情况。码下可省略例3-4 线性分组码编码器10001010100111001011000010114 G =I |P=例3-4 考虑一个(7,4)码，其生成矩阵 求： 对于信息组m=(1011)编出的码字是什么？ 画出它的编码器原理图 若收到一个7位码r=(1001101)，检验它是否是码字；例3-4 线性分组码编码器32106 5 4 3 2 1 06 5 4 33210232112 ()()(1011000);4()()(1011)3m m m mc c c c c c cCc c c cm m m mPcmmmcm4mCC = m GCG =I |P1011

20、11P =110011解： 设信息组，码字 方法一：可由代入计算出 方法二：由可知 为系统码，故前面 位就是信息位，后面 位校验位可由生成矩阵的分块 来求。 21010320032102 1 0000()(1011000)cmmccmmmcCm m m m c c c 码字例3-4 线性分组码编码器1( , )-2-n kkn kkPn k解（续 ）： 一个二进制系统线性分组码的编码器可用级移存器和连接到移存器适当位置的个模 加法器组成。本例先是 位信息比特输出，然后加法器按照规则生成位校验比特输出。例3-4 线性分组码编码器 1001101(011)(000)(4TTn-kn-kTTTTTG

21、 =I |PCH1110100H =-P |I=P |I= 01110101101001r H rr H = 0rr H0rr HHrHr解(续2)：由于 可知 为系统码，则其校验矩阵 为 可由 的结果可以判断 是否为码字。 若 则 是码字； 则 不是码字。 与 不正交，接收到的1001101)不是码字。线性分组码矢量空间与码空间线性分组码编码线性分组码伴随式与译码线性分组码伴随式与译码码的纠检错能力与MDC码完备码与汉明码分组码的性能极限线性分组码伴随式-110111100,)(,),Rnnnee ercrc rcEETTTTTTTTTTER-CERCCRERCEC H = 0R H = C

22、EHC HE HE HR HE HC H = 0R H （是信道干扰的反映，对二进制而言: 利用 则可以检验收码 是否有误。 （） 若接收无误： 若接收有误： 差错图案0TTTTE HHR HER HC由此可知，若保持不变，则 仅与 有关，与发什么码 仅与信道字 无关，说明影响有关。线性分组码伴随式1210-=(,),-22n kn kn knsss sSSn kEnSS TTR HE H 从物理意义上看， 并不反映发送什么码字 只反映 信道对码字造成怎样的干扰。 是一个重矢量，只有种组合； 是 重 矢量 伴，有种可能的组合 同一个伴随式 对应若干随式 个不同的差错图案。S线性分组码的译码过程

23、,TTTTCRHSR HCCR HSSE HECRE 译码思路：在接收端 是未知的，但接收码 和 是已知的，从而可以算出伴随式译码最 重要的任务是如何从伴随式中找出 的估计值 。 1210(1)(1)(1)1(1)012101(1)11100(1)010011 (1)(1)1 (,)(,)n kn kTn knn kn knnnnn knn knn ksss shhheee ehhhhhhsehe h TESE H 通过求解线性方程组来求解 ： （展开为线性方程组） 1)10(1)011 1(1)1 110 1001 0(1)1 01000n knnnne hsehe he hsehe he

24、h 11 (1)(1)1 (1)10(1)011 1(1)1 110 1001 0(1)1 01000110,n knn knn kn knnnnnsehe he hsehe he hsehe he hnee enk E 通过求解线性方程组来求解 ： 以上方程组有 个未知数却只有个方程，因此可知方程组有多解。在有理数或实数域中，少一个方程就可能-( - )22kknn kkTRHSE导致无限多个解；而在二元域中，少一个方程就导致两个解，少两个方程就导致四个解，以此类推，少了个方程导致每个未知数有个解。由确定后，对应的差错图样 可以有种。-12-2221111(1-);2(1-)1(1-)kkn

25、nnBSCpnEpppppppEEEE 由概率译码选择最轻的差错图样 ： 对应的差错图样 可以有种，根据概率译码准则，将所有个解的重量（差错图样 中的个数）做比较，选择最轻的差错图样作为 的解。理论依据： 假设信道差错概率为 ，长度为 的码中错 位，即对应与 中有 个的差错图样，其概率是错 位的概率是依次类推。 -12-2(1-)2nnkpppEE所以在 的个解中选择重量最小的差错图样 时，其译码正确的概率最大。构造标准阵列译码表 上述的概率译码，没接收一个码字就要解一次线性方程，运算量大。 可以预先把S不同取时的输出构成一个码表，接收时只需要查找码表就可以了。培集 定义： 设H是交换群G的一

26、个子群，是G中的任一个元素，用去乘H的所以元素而构成的集合称为H在G中的一个培集。 例：已知C=000,011,101,110是3维矢量空间V（23）的子集，a=100属于V（23），则a+C=100,111，001，010便是C在V（23）中的一个培集。 性质： aH,bH或者重合或者不相交。构造标准阵列译码表StepStepStepjiijC +E 用概率译码确定各伴随式对应的差错图案； 确定标准阵列译码表的第一行和第一列； 在码表的第 行第 列填入-2222kkn kn kStepTSS = E HSEEES 将 的可能取值逐一代入上述由转化的线性方程组中，每个 所对应的 都有个解，取重

27、量最轻的（概率最大）解作为差错图样 的值。 当 的个解中有两个或两个以上的解并列重量最小时，随机选择一个（或由设计者统筹考虑后选一个）。因此尽管伴随式一样，可能会有不 用概率译码确定各伴随式对应的同的译码方案。 有个取值差错图，因此需解；要。案次方程-22222n kknn kkS pRteSCR 由于伴随式 有种可能的取值，码字 有种可能的取值，接收码 有种可能的取值，所以令标准 确阵列译码表有行， 列，设计得当就有能覆盖 的全部取值。定标准阵列译码表的第一行和第一列；000022(000)0(000)kkStERCECEpEEeS第一行： 个位置放置个码字，也可以看成全零差错 图样时的接收

28、 确定标准阵列译码表的第码 标准阵列译码表每一。 第一行对应的一行和行具有相同的差错图样第一列正是全零伴随式所对 应的最轻解。；的2221223n kn kn kn kjnnStepn C第一列： 个位置放置个解取值所对应的最轻解，这些解在列中存放的次序是重量轻者（概率或可靠性大）在 确定标准阵列译码表的先，重者（概率或可靠性小）在后。直至排满行，即满足： 标准阵列译码表每一列具有相同第一行和第的一列。；发送码字-2n kStepjiiijjTjjjjCES = EHECC +EE 表中同一列的和值包含同一个码字做加数；同一行的和值包含同一个差错图样做加数，即对应同一个伴随式； 行数=伴随式的

29、数目 码表每一行是某个与码集 各元素模2运算结果， 因此每一行就是一个陪集，每行含有的共同元素 就称为陪集 在首，码表的第 行第 列每个陪集对应一随。填入个伴式222kkkStepjiijTjjjiiCES = EHCC +CE 表中同一列的和值包含同一个码字做加数；同一行的和值包含同一个差错图样做加数，即对应同一个伴随式； 码表中有列，每列表示同一个码字在不同差错图案 下的变化情况，构成子集，子集各元素所含有的共同 元素称为子集头，码集 中的个码字正好充 在码表的第 行第 列当 个集。入头填子2222222,kn kn kkn kknnnER 两个陪集要么相等，要么不相交，所以如果个陪 集首

30、选择不同的差错图样 ，则个陪集不相交。 总共可以有个陪集，每个陪集有个元素。 如果不存在重复元素（不相交），标准阵列表中设 计的元素总数必定为，正好是接收码 所在的 维 重码空可以间的全部元素值 无一重复，无一 证 遗明： 漏。构造标准阵列译码表-3101113-5(5,2)01101(10101)5,222824(001),(01),(10),(11)4:n kkStekmpnGRCGC = m GCC例 某线性分组码生成矩阵设接收码，请构造标准阵列码表，然后译出发送码估计值 。解：由已知得：；码表行数；列数 分别以信息组及生成矩阵 代入公式可以求得（一个允）构造标准阵列许使用的码字分码别计

31、算码字集合为： 表(00000),(10111),(01101),(11010)1234CCC例3-5 线性分组码译码（构造码表）23(1)(1)23222120(2)(1)13121110(3)(1)030201001101110110111100|10010110012kTn kn knn knn knHPIhhhhhhStehhhhhhhhpHh GI|P解（续 ）： 生成矩阵 校验矩阵 求得校验 矩阵 例3-5 线性分组码译码（构造码表）-322281555210123n kStep S E 解（续 ）： 伴随式的数目 除了代表无差错图案外，代表 个差错的图案有 种，代表 个差错的图案

32、有 种 标准阵 1 个无差错图案； 根据分析来确定 5 个1列码表培集首应包差错图案； 标准 集含:阵列培首 2 个2差错图案；例3-5 线性分组码译码（构造码表）24243232221 2102043214 143 132 121 110 104104043032021 01000430341se he he he he heeese he he he he heese he he he he heeeStepSETS = E HSE解（续 ）： 将 个差错的差错图案与全零差错图案代入以上方程求解与之对应的伴 解的线性方程随式 。组计算即将 和(00000),(00001),(00010),

33、(00100),(01000),(10000)(000),(111),(101),(100),(010),(001)jS代入上述方程组，可计算得： 例3-5 线性分组码译码（构造码表）324281(000),(111),(101),(100),(010),(001)(011)(110),224(011)(00011)(10100)(01110)(11001)5n kStepjSSSSEESE解（续 ）： 伴随式 总共有个，计算得到与 个差错和全零差错对应的 。还剩余两个和每个又对应个差错图案，求解所有的 得到： 解剩 对应的，其中余两个伴有两个并随式 对应的列重量最(110)(00110)jS

34、E轻，只能随机选取其中一个。同理可选得的最轻差错图案之一例3-5 线性分组码译码（构造码表）46Step 构造标准阵列码解（续 ）：表如下：例3-5 线性分组码译码（构造码表）4242225(10101)5()2()(10101)(10111)12(10101)(10(101101)11TMethRECECodMethodCCSRHSRRCC解（续 ）：直接搜索到第 行第 列的码字查得该列 直接搜索标准阵列码表 先求找到 对应行搜索找到该行中某个元（二）接收码）时估子集头为可以推算出发送码估计素顺着该列方向找到子集算发送码为头值推算2(10111)CC出发送码估计值为例3-5 线性分组码译码（

35、构造码表）4442446(10101)(00010)(10101)(00013(101010)(10111)TTTSR HHSEREMethodSRHSECRCRERECC（二）接收码）时估 先求找到对应行的陪集首 解）：发续算送码（例3-5 线性分组码译码（构造码表）min3,(1) 21,7 82101112tINTdmi2n讨论： 码表中只有前6行具有唯一性、可靠性，而第7、8行 是随机选取的最轻重量者，因此不是唯一的，不可靠。 从纠错能力看，d第 、行 错了 个例如：设接收到的码字R=(10100)，根据码表译出的应该 是C，与接收码的汉明距离是 。然而接收码 ，超过了纠错能力 R与全

36、零范围，码字的是不可靠的距离也。是2，也可以译成零码字。例3-5 线性分组码译码（构造码表）线性分组码矢量空间与码空间线性分组码编码线性分组码伴随式与译码码的纠检错能力与码的纠检错能力与MDC码码完备码与汉明码分组码的性能极限基本概念的引入10111C例3-5中，如果接收码字中有1位误码，则译码后该差错可以被纠正；如果有两位出错，则可以检测出差错存在，但未必能被纠正；比如：发送码是(00000)，而接收码为(10100)，根据码表译出的应该是，信道差错而导致了译码差错；如果发生3位误差，接收端可能根本无法察觉误码的存在，比如发送(00000)，接收(01101)，由于(01101)本身也是码字

37、，接收端根本察觉结不出误码。论：任何一种信道编码的纠、检错能力都是有限的，这种限度与码间的距离有关系。基本概念( )(,)(,)()nnwnddw1212121212RRRRRRR RR RRR 汉明重量： 重矢量 中，非零元素的个数称为该 重 矢量的汉明重量，简称重量，用表示。 汉明距离：逐位比较两个 重矢量和的对应各位， 其中取值不同的元素的个数称为与的汉 明距离，用来表示。 显然，有 成立。 最小距离：分组码集中，每mind两两码字之间都存在一定 的距离，其中最小者称为该分组码的最小 距离，用表 示。基本概念 汉明距离基本概念 汉明距离计算最小距离的定理和方法min()22212()(k

38、kkddww11132223C ,CCCCCC = CC理论依据： 如果直接计算最小距离，含个码字的码集需（）计算次距离后才能够找出。由于分组码是群码，具有封闭性，（即满足），则可知 表明只要遍历所有码字重量就可以找到最）小距离。计算最小距离的定理和方法minminmin,0()()()()(22kkddddwwdwiii1312321212CCC,CR ,RR ,RR ,RRRRR 求最小距离问题转化为寻找最轻码字，含个码字 的码集仅需计算次后定理一：线性分组码的最小距离等于码集中非零码字的 最小重量，即 就能够找出。 距离 和重量关系还满足 最小距离表明码集中各码差）的）字异程度，差异越大

39、， 越容易区分，抗干扰能力越强。与最小距离有关的定理minminminmin112ddddttINT 定理二说明，只要发送码字在接收端不被误认为是另 一个码字，定理二：对于任何最小距离为的线性分组码，其检测 随机差错的能力为。定理三：对于任何最小距离为的线性分组码，其纠正 随机差错的能力 为 正确设计的译码器就能察觉出差错的发生。minminminminminminmmiinn();()()()()()()11212221CRdtVCddddddddddddtINTddINTttC,RC,VC,RR,VC,VR,VC,R 设发送码字 时接收的码字为 ，且在差错可纠正范围内，即又设 是码集中不等

40、于 的任意一个其他码字，由于码集的最小距离为又 证明定理三 ： min()()21()()dddtttdtdt R,VC,RC,RR,VCRVRCR 结论：且，说明发送码字 与接收码 字 的距离比任何其他码字 与 的距离都接近，只 要采用最小距离译码，译码输出就是发送码字 ， 即 中的差错能够被正确纠正。计算最小距离的定理和方法-10-1minm210-10-10i-10-10nmin( - ),10( , )nnnnTTTnnnHn knnhhh hhhCChhC hC hn kdddTH C H=H定理四： 线性分组码的最小距离等于的充要条 证明：校验矩阵是的矩阵，其 列 件是 校验矩阵

41、中有列线性无关。可以写成 其中是列矢量。如果要码的最小距离为，-10minminminmin,0101nCCdddd则上式作为系数的码元中至少要有个为非零元素。换句话说，上式至少有项，即个列矢量之和才能线性组合出 ，少列就无法线性组合出 ，也即列必定线性无关。计算最小距离的定理和方法mimnminmiinn( , )-1( - )-1-1,1n knn knn kdn kkddkknnnkd H证明：校验矩阵 是的矩阵，该矩阵的秩最大 不会超过，即定理五： 线性分组码的最小距离必定线性无关的列不会小于等于 超过。 又 结合考虑定 计算最小距离的简便方法：理四 则 定理四和定理五表明，最小距 即

42、 校。离等效于11HH验矩阵中线性无关的列数目再加 ，或者等于矩阵 的秩加。从码空间角度分析检纠错能力-10(,)nCccnnn 检错能力分析 每个码字都可以看作一个 重矢量，与 维空间矢量的某一个点对应。码集的全部码字对应的点可以构成矢量空间的一个子集，子集点只是全部 维空间点的一部分。从码空间角度分析检纠错能力minmin.1nabddb 检错能力分析 传输出错时接收的 重码矢可能出现两种情况： 对应点落到子集外空间的某一点； 对应点仍落到子集内，却对应到该子集的另外一点。 由于子集中任意两点都存在距离，设最小距离为，则 ： （）一个能使空间点位置偏离的差错图案，有可能把接收矢量所对应的空

43、间点从子集内一点偏移到另一点，导致错误地认为是另一个码字，即出现情况 。从码空间角度分析检纠错能力minminmin121dddd 检错能力分析（ ）反之，只有差错图案重量小于，或者说，对应点就不可能从子集一个点对应到另外一个点上，就有可能检测到差错的发生。 从以码的检错能力上分析可以：为 看出从码空间角度分析检纠错能力min( , )2212kkn knttdtINT 纠错能力分析 对于线性分组码个码字对应 维空间中个点。如果以码字为球心，以 为半径做球体，那么使它们之中任意一对球体两两不相交（含不相切）的 的最大值就是从码空间角度分析检纠错能力23min23734323442151CCdt

44、CCtt 联合考虑检、纠错能力例：和之间 则 若选，发生 个错误时会由范围落入范围，无法检测出来，此时检、纠错能力都为 。 若选，发生个错误时可检测，检错；纠错； 若选，检错；纠错；从码空间角度分析检纠错能力min21min23min212313,7,122dccdeedeeCCdCCdtCCCC 联合考虑检、纠错能力结论：同时考虑检错和纠错时，其检错和纠错能力满足 且 进一步讨论：对于线性码来说例如：上图中与之间与之间 若选时，朝方向出现 个错误，则无法纠错； 但若朝方向出现 个错误，则可以纠正回来。从码空间角度分析检纠错能力 进一步讨论结论 最小距离就是最轻码重（或最轻码与全零码 的距离）

45、 纠错能力t只是说明当差错偏移量dt时一定 可以纠正，但并非说明dt时就一定无法纠正。 总体的平均的纠错能力不但与最小距离有关， 而且与码字间的距离（或码字重量分布）有关。码重分布特性：重量谱20120012( )012 nniniinA xAAxA xA xAxnAAAnA重量谱：对码字分布规律的一种描述，不仅是计算各种差错概率的主要依据，也是研究码结构，改善码内部关系从而发现好码的重要工具。可以用重量算子来表示： 含义：码长 的码集中，含重量为的码字个；含重 量为的码字 个；含重量为的码字个； 含重量为的码字个；码重分布特性：重量谱20120( )nniniiA xAAxA xA xAxm

46、in重量谱： 除常数项（全零码）外最低次非零项的次数就是 码集的最小距离d。 正如各符号等概率时熵最大一样，当所有码距相 等（重量谱为线谱）时码的性能最好； 当各码距相差不大（重量谱为窄谱）时码的性能 相对比较好。极大最小距离码（MDC码）min1( , ),1( ,1)MDCdnkn kMDCMDCn knnMDCMDCRS码： 若某种码的最小距离达到了可能取得的 最大值，即，则称该 线性分组码为极大最小距离码（）； 码是给定条件下纠错能力达到极限的最 强码，是我们设计的目标。 目前，在二进制码中，除了将 位信息重复 次 的码外不存在其他的码；但非二进制 的是存在的，比如码。线性分组码矢量空

47、间与码空间线性分组码编码线性分组码伴随式与译码码的纠检错能力与MDC码完备码与汉明码完备码与汉明码分组码的性能极限完备码与汉明码110-(,)( , )( - )2,2Tn kn kn kSEHss sn kn ktt 由 可知，二元线性分组码的伴随式是一个重矢量，有种可能的组合 构成标准阵列译码表则要有个差错图样对应。 由前面线性分组码的译码方法可知，如果码的纠错能力是 ，那么对于任何一个重量小于等于 的差错图案，都应该存在唯一的伴随式组合与之对应，（即伴随式要与差错图样能够一一对应）这样才可能实现真正可靠的纠错。完备码与汉明码ttt 如果某码的伴随式组合数目不多不少恰好和不大于 个差错的图

48、案数目相等，相当于在标准阵列表中能 将所有重量不大于 的差错图案选做陪集首，而没有 一个陪集首的重量大于 ，这时伴随式就能和可纠差 错图案实现一一对应，概率译码原则得到最充分的 体现，校验位得到最合理的利用。完备码与汉明限-0-02012( , )tn kitn kinnnntitnn ki 伴随式组合的数目必须满足的条件称为汉明限， 即 任何纠错能力为 的线性分组码都应满足汉明限。满足方程 的二元线性分组码 称为完备码(perfect code)。 完备码只发现：t=1 汉明限： 完备码的汉：明码；t=3的格雷码； (n,1)分组码；二进制t=2的(11,6,5)格雷码。完备码与汉明限 从n

49、维矢量空间角度考察完备码：汉明码-min-1(1)211(1)21211(1)111213n kn kmmmmmn kqn qnmnkmnknqqnkmkqqtmttdt 令 则有以下关系成立伴随式数量：伴随式数量： 码长： 码长：信息位：信息位：纠错能 汉明码的条件：纠错能力：力的完备码统称纠错能力：汉最小距明码：。离最小距min213 dtq 离：二进制进制汉明码( - )-( , )() 1212121n knn kmn kn kHnnknknHHG 线性分组码校验矩阵，可以看作 个 的列矢量组成。二进制重列矢量的全 部（全零 汉明矢量除外）是个，恰好与列矢量的 数目 相等； 只要排列所

50、有列，通过列置换将矩阵转换成系统 形式码的构造：，就可以得通过校验矩阵来简单构到相应的生造成矩阵 。例3-6 构造汉明码mmnkTTT001 010111例3-6 请构造一个 =3的二元(7,4)汉明码。解： 求校验矩阵H () (7,4)汉明码的校验矩阵大小应该是3 7矩阵，而校验矩阵的列矢量不能为全零（零矢量与任何码元的乘积为零，失去校验的功能。）因此H的7个列矢量正好是除了全零矢量外3重矢量的全部可能组合。将排列起来就是校验矩阵。排列顺序不同，所得的校验矩阵就不同。例3-6 构造汉明码例3-6 请构造一个m=3的二元(7,4)汉明码。解（续）： 由校验矩阵求生成矩阵汉 明 码1220(),1( )(1)(1)(1)1(7,4)(:iinniniiiweight enumerating polynomialzzAiA zAzznzznAA z可以用一个称为重量估值算式 的 的多项式来表达其中 的系数 表示重量为的码字的数目