第二十四讲第六节线性分组码

（优选）第二十四讲第六节线性分组码现在是1页\一共有45页\编辑于星期四1引例0后附加字符0，1后附加1；即只有00和11被接受，且00视为0，11视为1；故：如果有一位错误发生，可以被检出！现在是2页\一共有45页\编辑于星期四2如果通信过程中发现差错，可以通过要求对方重新发送来获得正确的信息，即所谓的“数量换质量”.但是这在实时信息采集系统中可能是有困难的，因为信息源已经发生变化；即使是在发方保留原信息样本的情况下，也只有在差错率很低的条件下是比较可行的.因为如果通信条件比较恶劣，差错出现频繁，以至多次重发仍然得不到一份正确的信息.这时，仅有“检错”手段，已无能为力！引例现在是3页\一共有45页\编辑于星期四3引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.现在是4页\一共有45页\编辑于星期四4引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.纠错码信息位校验位现在是5页\一共有45页\编辑于星期四5线性分组码的基本概念分组码分组码是把信源输出的信息序列，以k个信息位分为一段，通过编码器把这段信息位按一定规则f产生r个校验位，输出长为n=k+r的一个码字，所得码字的全体.称之为（n，k）分组码！n表示码长，k表示信息位个数.现在是6页\一共有45页\编辑于星期四6引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.(3,1)分组码信息位校验位现在是7页\一共有45页\编辑于星期四7（n，k）分组码若校验位与信息位之间的关系是线性的，即上述编码规则是线性的，称之为（n，k）线性分组码！

现在是8页\一共有45页\编辑于星期四8一、二元域——GF(2)设{0,1}为一个二元集，在其上定义模2的加法和乘法运算加法：乘法：可见二元集{0,1}对上述定义的加法及乘法运算封闭，并满足一个“域”所要求的交换律、结合律、分配律等运算规则，因此{0,1}对所规定的加法和乘法运算构成一个域，称为二元域，记作GF(2).现在是9页\一共有45页\编辑于星期四9注现在是10页\一共有45页\编辑于星期四10称码为(n,k)码.二、线性分组码的定义及表示现在是11页\一共有45页\编辑于星期四11若设码字，则即校验位是由信息位线性组合得到.现在是12页\一共有45页\编辑于星期四12可见，码字的三个校验元都由其前两位线性组合得到，即可由线性方程组求得；信息位k=2码字数M=4现在是13页\一共有45页\编辑于星期四13线性编码现在是14页\一共有45页\编辑于星期四14例题1：下面是某个（n，k）线性二元码的全部码字x16=000000x26=100011x36=010101x46=001111x56=110110x66=101100x76=011010x86=111001求n、k的值；n=6;M=2kk=3.解：现在是15页\一共有45页\编辑于星期四15例2、（5，2）线性二元码的全部码字设码字，可得现在是16页\一共有45页\编辑于星期四16改写为用矩阵可表示成：校验矩阵与任一码字的乘积为0

现在是17页\一共有45页\编辑于星期四17线性分组码的特性

2k个码字完全可由其中一组k个独立的码字组合而成；

生成矩阵从线性分组码（n，k）中任取

k

个线性无关的码字，以行的形式写成矩阵G，则称为该线性分组码的生成矩阵.

现在是18页\一共有45页\编辑于星期四18例题3：下面是一个（6，3）线性二元码的全部码字构造它的一个生成矩阵.解：由k=3个线性独立的码字组成：现在是19页\一共有45页\编辑于星期四19例题3：下面是一个（6，3）线性二元码的全部码字验证：现在是20页\一共有45页\编辑于星期四20说明现在是21页\一共有45页\编辑于星期四21一个线性子空间可以有不同的但相互等价的基，亦即不同的G可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。现在是22页\一共有45页\编辑于星期四22例4矩阵为一个(7,3)码.现在是23页\一共有45页\编辑于星期四23系统码

若（n,k）线性分组码的生成矩阵形如

G=(IkA)其中Ik是k阶单位阵，A为阶子阵，则称这类码为系统码.特点：校验矩阵为H=(ATI(n-k)).三、系统编码与校验矩阵现在是24页\一共有45页\编辑于星期四24例题3：下面是一个（6，3）线性二元码的全部码字它的一个生成矩阵请写出它的校验矩阵H.现在是25页\一共有45页\编辑于星期四25现在是26页\一共有45页\编辑于星期四26注：系统码的码字的前k个码元就是它所载荷的数字消息，故系统码的前k为称为信息位，后n-k位称为校验位.现在是27页\一共有45页\编辑于星期四27校验矩阵即结论：现在是28页\一共有45页\编辑于星期四28汉明距离：指（n,k）分组码中两个码字xn、

yn对应位取值不同的个数；记为d（xn，yn）.

例：

现在是29页\一共有45页\编辑于星期四29汉明距离：指（n,k）分组码中两个码字xn、

yn对应位取值不同的个数；记为d（xn，

yn）.

例：

现在是30页\一共有45页\编辑于星期四30线性分组码的最小距离：称（n,k）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离d.

（5,2）线性分组码全部码字：最小距离d=3.

汉明重量现在是31页\一共有45页\编辑于星期四31汉明(Hamming)码汉明码是一类能纠正一位差错的线性分组码，其参数为：码长：信息位长：

校验位长：最小码距：

汉明码H

矩阵的构造方式：按

m

位的

2

进制数的自然顺序从左到右排列(不包括全

0

列)，当发生可纠的单个差错时，伴随式为

H

矩阵中对应的列，译码比较方便将上述非标准形式的

H

矩阵通过列初等置换变成标准形式的校验矩阵，纠错能力保持不变例：构造一个的

2

元汉明码由于故构造的汉明码为线性分组码汉明码的编码效率是很高的，现在是32页\一共有45页\编辑于星期四32设一分组码具有一致校验矩阵：①求这个分组码n=？k=？，共有多少个码字？②此分组码的生成矩阵；③向量101010是否是码字？习题课（补充）现在是33页\一共有45页\编辑于星期四33解：①设码字C=(c5c4c3c2c1c0)，有习题课故得所以n=6，k=3，为(6,3)分组码．共有码字2k=8个现在是34页\一共有45页\编辑于星期四34设一分组码具有一致校验矩阵：①求这个分组码n=？k=？，共有多少个码字？②此分组码的生成矩阵；③向量101010是否是码字？习题课（补充）现在是35页\一共有45页\编辑于星期四35习题课②由上式可得取一组线性无关的基础解系，得到生成矩阵现在是36页\一共有45页\编辑于星期四36设一分组码具有一致校验矩阵：①求这个分组码n=？k=？，共有多少个码字？②此分组码的生成矩阵；③向量101010是否是码字？习题课（补充）现在是37页\一共有45页\编辑于星期四37习题课③由可知，向量101010不是码字．现在是38页\一共有45页\编辑于星期四38说明现在是39页\一共有45页\编辑于星期四39一个线性子空间可以有不同的但相互等价的基，亦即不同的G可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。现在是40页\一共有45页\编辑于星期四40例2设码的生成矩阵为则共有两个码字，为一个(5,1)码.现在是41页\一共有45页\编辑于星期四41系统码消息G1码字G2码字000000000000000001111000001101010110101010011011001101011110100101011100110101010011101011110011110110101111100110111000生成矩阵

G

的选择不是惟一的；如下面的G1和G2都可作为同一个(6,3)码的生成矩阵，所对应的码字如右表所示：系统码的编码器仅需存储k

(n

-

k)个数字(非系统码要存储k

n个数字)，译码时仅需对前k个信息位纠错即可恢复信息；可见系统码的编码和译码比较简单，而性能与非系统码一样，所以系统码得到了十分广泛的应用虽然二者用了不同形式的生成矩阵，却都是

(6,

3)

线性分组码，因此它们的检错和纠错能力是一样的，但是

G2

生成的码，其前

k位与消息码完全相同，这种码称为系统码，其生成矩阵和一致校验矩阵分别记为

Gs

,Hs现在是42页\一共有45页\编辑于星期四42线性分组码的生成矩阵

和校验矩阵的关系由于G的每一行都是一个码字，所以G的每一行c

i

都满足： 从而有：

在码字集合不变的前提下，给定任何一个线性分组码，通过其生成矩阵G实施行初等变换，均可以转换为某个系统码当且仅当线性分组码一致校验矩阵H中任意

d

-

1

个列线性无关而某d列线性相关时，线性分组码的最小码距为

dmin

=

d现在是43页\一共有45页\编辑于星期四43汉明(Hamming)码汉明码是一类能纠正一位差错的线性分组码，其参数为：码长：信息位长：

校验位长：最小码距：

汉明码H

矩阵的构造方式：按

m

位的

2

进制数的自然顺序从左到右排列(不包括全

0

列)，当发生可纠的单个差错时，伴随式为

H

矩阵中对应的列，译码比较方便将上述非标准形式的

H

矩阵通过列初等置换变成标准形式的校验矩阵，纠错能力保持不变例：构造一个的

2

元汉明码由于故构造的汉明码为线性分组码汉明码的编码效率是很高的，现在是44页\一共有45页\编辑于星期四44线性分组码的描述设信息分组长度为

，在每一信息组后加上

4

个校验码元，构成线性分组码 设该码的码字为