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

第二十四讲第六节线性分组码1第一页，共四十七页，编辑于2023年，星期一设传输一比特字符x=0或1

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

n表示码长，k表示信息位个数.7第七页，共四十七页，编辑于2023年，星期一引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.(3,1)分组码信息位校验位8第八页，共四十七页，编辑于2023年，星期一（n，k）分组码若校验位与信息位之间的关系是线性的，即上述编码规则是线性的，称之为（n，k）线性分组码！

9第九页，共四十七页，编辑于2023年，星期一一、二元域——GF(2)设{0,1}为一个二元集，在其上定义模2的加法和乘法运算加法：乘法：

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

18第十八页，共四十七页，编辑于2023年，星期一线性分组码的特性

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

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

k

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

19第十九页，共四十七页，编辑于2023年，星期一例题3：下面是一个（6，3）线性二元码的全部码字构造它的一个生成矩阵.解：由k=3个线性独立的码字组成：20第二十页，共四十七页，编辑于2023年，星期一例题3：下面是一个（6，3）线性二元码的全部码字验证：21第二十一页，共四十七页，编辑于2023年，星期一说明22第二十二页，共四十七页，编辑于2023年，星期一

一个线性子空间可以有不同的但相互等价的基，亦即不同的G可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。23第二十三页，共四十七页，编辑于2023年，星期一例4矩阵为一个(7,3)码.24第二十四页，共四十七页，编辑于2023年，星期一系统码

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

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

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

例：

30第三十页，共四十七页，编辑于2023年，星期一汉明距离：指（n,k）分组码中两个码字xn、

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

yn）.

例：

31第三十一页，共四十七页，编辑于2023年，星期一线性分组码的最小距离：称（n,k）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离d.

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

汉明重量32第三十二页，共四十七页，编辑于2023年，星期一汉明(Hamming)码汉明码是一类能纠正一位差错的线性分组码，其参数为：码长：信息位长：

校验位长：最小码距：

汉明码H

矩阵的构造方式：按

m

位的

2

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

0

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

H

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

H

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

2

元汉明码由于故构造的汉明码为线性分组码汉明码的编码效率是很高的，33第三十三页，共四十七页，编辑于2023年，星期一设一分组码具有一致校验矩阵：①求这个分组码n=？k=？，共有多少个码字？②此分组码的生成矩阵；③向量101010是否是码字？习题课（补充）34第三十四页，共四十七页，编辑于2023年，星期一解：①设码字C=(c5c4c3c2c1c0)，有习题课故得所以n=6，k=3，为(6,3)分组码．共有码字2k=8个35第三十五页，共四十七页，编辑于2023年，星期一设一分组码具有一致校验矩阵：①求这个分组码n=？k=？，共有多少个码字？②此分组码的生成矩阵；③向量101010是否是码字？习题课（补充）36第三十六页，共四十七页，编辑于2023年，星期一习题课②由上式可得取一组线性无关的基础解系，得到生成矩阵37第三十七页，共四十七页，编辑于2023年，星期一设一分组码具有一致校验矩阵：①求这个分组码n=？k=？，共有多少个码字？②此分组码的生成矩阵；③向量101010是否是码字？习题课（补充）38第三十八页，共四十七页，编辑于2023年，星期一习题课③由可知，向量101010不是码字．39第三十九页，共四十七页，编辑于2023年，星期一说明40第四十页，共四十七页，编辑于2023年，星期一

一个线性子空间可以有不同的但相互等价的基，亦即不同的G可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。41第四十一页，共四十七页，编辑于2023年，星期一例2设码的生成矩阵为则共有两个码字，为一个(5,1)码.42第四十二页，共四十七页，编辑于2023年，星期一系统码消息G1码字G2码字000000000000000001111000001101010110101010011011001101011110100101011100110101010011101011110011110110101111100110111000生成矩阵

G

的选择不是惟一的；如下面的G1

和G2

都可作为同一个(6,3)码的生成矩阵，所对应的码字如右表所示：系统码的编码器仅需存储k

(n

-

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

n

个数字)，译码时仅需对前k

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

(6,

3)

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

G2

生成的码，其前

k

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

Gs

,Hs43第四十三页，共四十七页，编辑于2023年，星期一线性分组码的生成矩阵

和校验矩阵的关系由于G

的每一行都是一个码字，所以G

的每一行c

i

都满足：

从而有：

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

d

-

1

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

dmin

=

d44第四十四页，共四十七页，编辑于2023年，星期一汉明(Hamming)码汉明码是一类能纠正一位差错的线性分组码，其参数为：码长：信息位长：

校验位长：最小码距：

汉明码H

矩阵的构造方式：按

m

位的

2

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

0

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

H

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

H

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

2

元汉明码由于故构造的汉明码为线性分组码汉明码的编码效率是很高的，45第四十五页，共四十七页，编辑于2023年，星期一线性分组码的描述设信息分组长度为

，在每一信息组后加上

4

个校验码元，构成线性分组码

设该码的码字为，其中为信息码元，

为校验码元，

；信息码元和校验码元可按下面方程组计算：消息码字消息码字00000