线性分组码课件

1、关于线性分组码1第一张，PPT共五十页，创作于2022年6月2设传输一比特字符x=0或1 若传输过程中出现差错,不能被发现引例第二张，PPT共五十页，创作于2022年6月3引例0后附加字符0，1后附加1；即只有00和11被接受，且00视为0，11视为1；故： 如果有一位错误发生，可以被检出！第三张，PPT共五十页，创作于2022年6月4如果通信过程中发现差错，可以通过要求对方重新发送来获得正确的信息，即所谓的“数量换质量”. 但是这在实时信息采集系统中可能是有困难的，因为信息源已经发生变化；即使是在发方保留原信息样本的情况下，也只有在差错率很低的条件下是比较可行的. 因为如果通信条件比较恶劣，

2、差错出现频繁，以至多次重发仍然得不到一份正确的信息. 这时，仅有“检错”手段，已无能为力！引例第四张，PPT共五十页，创作于2022年6月5引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.第五张，PPT共五十页，创作于2022年6月6引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.纠错码信息位校验位第六张，PPT共五十页，创作于2022年6月7线性分组码的基本概念分组码分组码是把信

3、源输出的信息序列，以k个信息位分为一段，通过编码器把这段信息位按一定规则f 产生r个校验位，输出长为n=k+r的一个码字，所得码字的全体.称之为（n， k ）分组码 ！ n表示码长， k表示信息位个数. 第七张，PPT共五十页，创作于2022年6月8引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.(3,1)分组码信息位校验位第八张，PPT共五十页，创作于2022年6月9（n， k ）分组码若校验位与信息位之间的关系是线性的，即上述编码规则是线性的，称之为（n， k ）线性分组码！ 第九张

4、，PPT共五十页，创作于2022年6月10一、二元域GF(2)设0,1为一个二元集，在其上定义模2的加法和乘法运算加法：乘法： 可见二元集0,1对上述定义的加法及乘法运算封闭，并满足一个“域”所要求的交换律、结合律、分配律等运算规则，因此0,1对所规定的加法和乘法运算构成一个域，称为二元域，记作GF(2).第十张，PPT共五十页，创作于2022年6月11注 第十一张，PPT共五十页，创作于2022年6月12称码为(n, k)码.二、线性分组码的定义及表示第十二张，PPT共五十页，创作于2022年6月13若设码字 ，则即校验位是由信息位线性组合得到.第十三张，PPT共五十页，创作于2022年6月

5、14可见，码字的三个校验元都由其前两位线性组合得到，即可由线性方程组求得； 信息位k=2码字数M=4第十四张，PPT共五十页，创作于2022年6月15线性编码第十五张，PPT共五十页，创作于2022年6月16例题1：下面是某个（n，k）线性二元码的全部码字x16=000000 x26=100011 x36=010101 x46=001111x56=110110 x66=101100 x76=011010 x86=111001求n、k的值；n=6;M=2k k=3.解：第十六张，PPT共五十页，创作于2022年6月17例2、（5，2）线性二元码的全部码字设码字 ， 可得第十七张，PPT共五十页，

6、创作于2022年6月18改写为用矩阵可表示成： 校验矩阵 与任一码字的乘积为0 第十八张，PPT共五十页，创作于2022年6月19线性分组码的特性 2k个码字完全可由其中一组k 个独立的码字组合而成； 生成矩阵从线性分组码（n，k）中任取 k 个线性无关的码字，以行的形式写成矩阵G，则称为该线性分组码的生成矩阵. 第十九张，PPT共五十页，创作于2022年6月20例题3：下面是一个（6，3）线性二元码的全部码字构造它的一个生成矩阵.解：由k=3 个线性独立的码字组成：第二十张，PPT共五十页，创作于2022年6月21例题3：下面是一个（6，3）线性二元码的全部码字验证：第二十一张，PPT共五十

7、页，创作于2022年6月22说明第二十二张，PPT共五十页，创作于2022年6月23 一个线性子空间可以有不同的但相互等价的基，亦即不同的G可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。第二十三张，PPT共五十页，创作于2022年6月24例4 矩阵为一个(7, 3) 码.第二十四张，PPT共五十页，创作于2022年6月25系统码 若（n , k）线性分组码的生成矩阵形如 G=(Ik A)其中Ik是k阶单位阵，A为 阶子阵，则称这类码为系统码.特点：校验矩阵为H=( AT I(n-k) ) .三、系统编码与校验矩阵第二十五张，PPT共五十页，创作于2022年6月26例题3：下面是一个（6

8、，3）线性二元码的全部码字它的一个生成矩阵请写出它的校验矩阵H.第二十六张，PPT共五十页，创作于2022年6月27第二十七张，PPT共五十页，创作于2022年6月28注：系统码的码字的前k个码元就是它所载荷的数字消息，故系统码的前k为称为信息位，后n-k位称为校验位.第二十八张，PPT共五十页，创作于2022年6月29校验矩阵即结论：第二十九张，PPT共五十页，创作于2022年6月30汉明距离： 指（n,k）分组码中两个码字xn 、 yn对应位取值不同的个数；记为d（xn ，yn）. 例： 第三十张，PPT共五十页，创作于2022年6月31汉明距离： 指（n,k）分组码中两个码字xn 、 y

9、n对应位取值不同的个数；记为d（xn ， yn）. 例： 第三十一张，PPT共五十页，创作于2022年6月32线性分组码的最小距离： 称（n,k）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离d. （5,2）线性分组码全部码字：最小距离d=3. 汉明重量第三十二张，PPT共五十页，创作于2022年6月33汉明(Hamming)码汉明码是一类能纠正一位差错的线性分组码，其参数为：码长： 信息位长： 校验位长： 最小码距： 汉明码 H 矩阵的构造方式：按 m 位的 2 进制数的自然顺序从左到右排列(不包括全 0 列)，当发生可纠的单个差错时，伴随式为 H 矩阵中对应的列，译码比较方便将上

10、述非标准形式的 H 矩阵通过列初等置换变成标准形式的校验矩阵，纠错能力保持不变例：构造一个 的 2 元汉明码由于 故构造的汉明码为 线性分组码汉明码的编码效率是很高的， 第三十三张，PPT共五十页，创作于2022年6月34设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？习题课（补充）第三十四张，PPT共五十页，创作于2022年6月35解：设码字C=(c5c4c3c2c1c0)，有习题课故得所以n=6，k=3，为(6,3)分组码共有码字2k=8个第三十五张，PPT共五十页，创作于2022年6月36设一分组码具有一致校验矩阵：求

11、这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？习题课（补充）第三十六张，PPT共五十页，创作于2022年6月37习题课由上式可得取一组线性无关的基础解系，得到生成矩阵第三十七张，PPT共五十页，创作于2022年6月38设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？习题课（补充）第三十八张，PPT共五十页，创作于2022年6月39习题课由可知，向量101010不是码字第三十九张，PPT共五十页，创作于2022年6月40说明第四十张，PPT共五十页，创作于2022年6月41 一个线性子

12、空间可以有不同的但相互等价的基，亦即不同的G可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。第四十一张，PPT共五十页，创作于2022年6月42例2 设码的生成矩阵为则共有两个码字，为一个(5, 1) 码.第四十二张，PPT共五十页，创作于2022年6月43系统码消息G1 码字G2 码字000000 000000 000001111 000001 101010110 101010 011011001 101011 110100101 011100 110101010 011101 011110011 110110 101 111100 110111 000生成矩阵 G 的选择不是惟一的；

13、如下面的G1 和 G2 都可作为同一个 (6, 3) 码的生成矩阵，所对应的码字如右表所示：系统码的编码器仅需存储 k (n - k) 个数字(非系统码要存储 k n 个数字)，译码时仅需对前 k 个信息位纠错即可恢复信息；可见系统码的编码和译码比较简单，而性能与非系统码一样，所以系统码得到了十分广泛的应用虽然二者用了不同形式的生成矩阵，却都是 (6, 3) 线性分组码，因此它们的检错和纠错能力是一样的，但是 G2 生成的码，其前 k 位与消息码完全相同，这种码称为系统码，其生成矩阵和一致校验矩阵分别记为 Gs , Hs第四十三张，PPT共五十页，创作于2022年6月44线性分组码的生成矩阵和

14、校验矩阵的关系由于 G 的每一行都是一个码字，所以 G 的每一行 c i 都满足：从而有： 在码字集合不变的前提下，给定任何一个线性分组码，通过其生成矩阵 G 实施行初等变换，均可以转换为某个系统码当且仅当线性分组码一致校验矩阵 H 中任意 d - 1 个列线性无关而某 d 列线性相关时，线性分组码的最小码距为 dmin = d第四十四张，PPT共五十页，创作于2022年6月45汉明(Hamming)码汉明码是一类能纠正一位差错的线性分组码，其参数为：码长： 信息位长： 校验位长： 最小码距： 汉明码 H 矩阵的构造方式：按 m 位的 2 进制数的自然顺序从左到右排列(不包括全 0 列)，当发

15、生可纠的单个差错时，伴随式为 H 矩阵中对应的列，译码比较方便将上述非标准形式的 H 矩阵通过列初等置换变成标准形式的校验矩阵，纠错能力保持不变例：构造一个 的 2 元汉明码由于 故构造的汉明码为 线性分组码汉明码的编码效率是很高的， 第四十五张，PPT共五十页，创作于2022年6月46线性分组码的描述设信息分组长度为 ，在每一信息组后加上 4 个校验码元，构成 线性分组码设该码的码字为 ，其中 为信息码元， 为校验码元， ；信息码元和校验码元可按下面方程组计算：消息码字消息码字000000 0000100100 1110001001 1101101101 0011010101 0111110

16、110 1001011011 1010111111 0100利用上式每给出一个 4 位的信息组，就可编出一个码字，结果如表所示 模 2 加第四十六张，PPT共五十页，创作于2022年6月476.2.1线性分组码的描述 分组码的编码包括两个基本步骤首先将信源的输出序列分为 k 位一组的信息组然后信道编码器根据一定的编码规则将 k 位信息组变换成n 个码元的码字信息组和码字用矩阵表示如下：信息组： k 位信息 码字： n 个码元 k 位信息位r = n - k 位校验位通常对编码器附加一个线性约束条件，使得码字的校验位与信息位之间呈线性关系，这种码称为 (n, k ) 线性分组码采用线性分组码进行

17、信道编码，就是给已知信息组按预定规则添加校验码元以构成码字。在 k 个信息元之后附加 r = n - k 个校验码元，使每个校验码元是其中某些信息码元的和第四十七张，PPT共五十页，创作于2022年6月48线性分组码的生成矩阵和一致校验矩阵在 (n, k ) 线性分组码中，编码器输出的码字可以由如下方程组来决定：如设：则方程组的矩阵表示为：c = mG所有满足上式码字(n 维向量)的全体构成 (n, k) 线性分组码 C生成矩阵生成矩阵 G 是一个 k 行 n 列(n k)秩为 k 的矩阵，它 建立了消息向量与码字的一一对应关系，它起着编码器的变换作用G 的每一行都是一个码字，分别是 k 维消息向量组 1000, 01000, , 00010, 00001 所对应的码字m 是任意 k 维消息向量运算：模 2 加、模 2 乘第