线性分组码精选PPT.ppt

《线性分组码精选PPT.ppt》由会员分享，可在线阅读，更多相关《线性分组码精选PPT.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、分组码！第9页，讲稿共50张，创作于星期二10一、二元域一、二元域GF(2)设设0,1为一个二元集，在其上定义模为一个二元集，在其上定义模2的加法和乘法运算的加法和乘法运算加法：加法：乘法：乘法：可见二元集可见二元集0,1对上述定义的加法及乘法运算封闭，并满足一个对上述定义的加法及乘法运算封闭，并满足一个“域域”所要求的交换律、结合律、分配律等运算规则，因此所要求的交换律、结合律、分配律等运算规则，因此0,1对所对所规定的加法和乘法运算构成一个域，称为二元域，记作规定的加法和乘法运算构成一个域，称为二元域，记作GF(2).第10页，讲稿共50张，创作于星期二11注注 第11页，讲稿共50张，创

5、作于星期二12称码为称码为(n,k)码码.二、线性分组码的定义及表示二、线性分组码的定义及表示第12页，讲稿共50张，创作于星期二13若设码字若设码字 ，则即校验位是由信息位线性组合得到即校验位是由信息位线性组合得到.第13页，讲稿共50张，创作于星期二14可见，码字的三个校验元都由其前两位线性组合得到，即可由线性方程组求得；信息位k=2码字数M=4第14页，讲稿共50张，创作于星期二15线性编码线性编码第15页，讲稿共50张，创作于星期二16例题例题1：下面是某个下面是某个（n，k）线性二元码的全部码字线性二元码的全部码字x16=000000 x26=100011 x36=010101 x4

6、6=001111x56=110110 x66=101100 x76=011010 x86=111001求求n、k的值；的值；n=6;M=2k k=3.解：第16页，讲稿共50张，创作于星期二17例2、（5，2）线性二元码的全部码字设码字 ，可得第17页，讲稿共50张，创作于星期二18改写为用矩阵可表示成：校验矩校验矩阵阵 与任一码字的乘积为0 第18页，讲稿共50张，创作于星期二194线性分组码的特性线性分组码的特性 2k个码字完全可由其中一组k 个独立的码字组合而成；4生成矩阵生成矩阵从线性分组码（n，k）中任取 k 个线性无关的码字，以行的形式写成矩阵G，则称为该线性分组码的线性分组码的生

7、成矩阵生成矩阵.第19页，讲稿共50张，创作于星期二20例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字构造它的一个生成矩阵构造它的一个生成矩阵.解解：由：由k=3 个线性独立的码字组成：个线性独立的码字组成：第20页，讲稿共50张，创作于星期二21例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字验证：验证：第21页，讲稿共50张，创作于星期二22说明说明第22页，讲稿共50张，创作于星期二23 一个线性子空间可以有不同的但相互等价的基，亦即不同的一个线性子空间可以有不同的但相互等价的基，亦即不同的G可以产生相同的线性

8、码，所以一个线性码的生成矩阵不唯一。可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。第23页，讲稿共50张，创作于星期二24例例4 4 矩阵矩阵为一个为一个(7,3)码码.第24页，讲稿共50张，创作于星期二25系统码系统码 若若（n,k）线性分组码的生成矩阵形如线性分组码的生成矩阵形如 G=(Ik A)其中其中Ik是是k阶单位阵，阶单位阵，A为为 阶子阵，阶子阵，则称这类码为系统码则称这类码为系统码.特点：校验矩阵为特点：校验矩阵为H=(AT I(n-k).三、系统编码与校验矩阵三、系统编码与校验矩阵第25页，讲稿共50张，创作于星期二26例题例题3：下面是一个（下面是一个（6，3）线

9、性二元码的全部码字）线性二元码的全部码字它的一个生成矩阵它的一个生成矩阵请写出它的校验矩阵请写出它的校验矩阵H.第26页，讲稿共50张，创作于星期二27第27页，讲稿共50张，创作于星期二28注：系统码的码字的前注：系统码的码字的前k个码元就是它所载荷的数字消息，故系个码元就是它所载荷的数字消息，故系统码的前统码的前k为称为信息位，后为称为信息位，后n-k位称为校验位位称为校验位.第28页，讲稿共50张，创作于星期二29校验矩阵校验矩阵即即结论：结论：第29页，讲稿共50张，创作于星期二30汉明距离汉明距离：指（指（n,k）分组码中两个码字）分组码中两个码字xn、yn对应位取对应位取值不同的个

10、数；记为值不同的个数；记为d（xn，yn）.例：例：第30页，讲稿共50张，创作于星期二31汉明距离汉明距离：指（指（n,k）分组码中两个码字）分组码中两个码字xn、yn对应位取对应位取值不同的个数；记为值不同的个数；记为d（xn，yn）.例：例：第31页，讲稿共50张，创作于星期二32线性分组码的最小距离线性分组码的最小距离：称（称（n,k）分组码中任两个码字汉明距离的最）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离小值，为该分组码的最小距离d.（5,2）线性分组码全部码字：）线性分组码全部码字：最小距离最小距离d=3.汉明重量第32页，讲稿共50张，创作于星期二33汉明(Ham

11、ming)码汉汉明明码码是是一一类类能能纠纠正正一一位位差差错错的的线性分组码，其参数为：线性分组码，其参数为：码长：码长：信息位长：信息位长：校验位长：校验位长：最小码距：最小码距：汉明码汉明码 H 矩阵的构造方式：矩阵的构造方式：按按 m 位位的的 2 进进制制数数的的自自然然顺顺序序从从左左到到右右排排列列(不不包包括括全全 0 列列)，当当发发生生可可纠纠的的单单个个差差错错时时，伴伴随随式式为为 H 矩矩阵阵中中对对应应的的列列，译译码码比比较方便较方便将将上上述述非非标标准准形形式式的的 H 矩矩阵阵通通过过列列初初等等置置换换变变成成标标准准形形式式的的校校验验矩矩阵阵，纠纠错错

12、能能力保持不变力保持不变例：构造一个：构造一个 的的 2 元汉明码元汉明码由于由于 故构造的汉明码为故构造的汉明码为 线性分组码线性分组码汉明码的编码效率是很高的，汉明码的编码效率是很高的，第33页，讲稿共50张，创作于星期二34设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？习题课（补充）第34页，讲稿共50张，创作于星期二35解：设码字C=(c5c4c3c2c1c0)，有习题课故得所以n=6，k=3，为(6,3)分组码共有码字2k=8个第35页，讲稿共50张，创作于星期二36设一分组码具有一致校验矩阵：求这个分组码n=？

13、k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？习题课（补充）第36页，讲稿共50张，创作于星期二37习题课由上式可得取一组线性无关的基础解系，得到生成矩阵第37页，讲稿共50张，创作于星期二38设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？习题课（补充）第38页，讲稿共50张，创作于星期二39习题课由可知，向量101010不是码字第39页，讲稿共50张，创作于星期二43系统码消息G1 码字G2 码字000000 000000 000001111 000001 101010110 101010 01

14、1011001 101011 110100101 011100 110101010 011101 011110011 110110 101 111100 110111 000生生成成矩矩阵阵 G 的的选选择择不不是是惟惟一一的的；如如下下面面的的G1 和和 G2 都都可可作作为为同同一一个个(6,3)码码的的生生成成矩矩阵阵，所所对对应应的码字如右表所示：的码字如右表所示：系系统统码码的的编编码码器器仅仅需需存存储储 k (n-k)个个数数字字(非非系系统统码码要要存存储储 k n 个个数数字字)，译译码码时时仅仅需需对对前前 k 个个信信息息位位纠纠错错即即可可恢恢复复信信息息；可可见见系系

15、统统码码的的编编码码和和译译码码比比较较简简单单，而而性性能能与与非非系系统统码码一一样样，所所以以系系统统码码得得到到了了十十分分广广泛泛的的应用应用虽虽然然二二者者用用了了不不同同形形式式的的生生成成矩矩阵阵，却却都都是是(6,3)线线性性分分组组码码，因因此此它它们们的的检检错错和和纠纠错错能能力力是是一一样样的的，但但是是 G2 生生成成的的码码，其其前前 k 位位与与消消息息码码完完全全相相同同，这这种种码码称称为为系统码，其其生生成成矩矩阵阵和和一一致致校校验矩阵分别记为验矩阵分别记为 Gs,Hs第43页，讲稿共50张，创作于星期二44线性分组码的生成矩阵和校验矩阵的关系由于由于

16、G 的每一行都是一个码字，所以的每一行都是一个码字，所以 G 的每一行的每一行 c i 都满足：都满足：从而有：从而有：在在码码字字集集合合不不变变的的前前提提下下，给给定定任任何何一一个个线线性性分分组组码码，通通过过其其生生成成矩矩阵阵 G 实施实施行初等变换，均可以转换为某个系统码，均可以转换为某个系统码当当且且仅仅当当线线性性分分组组码码一一致致校校验验矩矩阵阵 H 中中任任意意 d-1 个个列列线线性性无无关关而而某某 d 列线性相关时，线性分组码的最小码距为列线性相关时，线性分组码的最小码距为 dmin=d第44页，讲稿共50张，创作于星期二45汉明(Hamming)码汉汉明明码码

17、是是一一类类能能纠纠正正一一位位差差错错的的线性分组码，其参数为：线性分组码，其参数为：码长：码长：信息位长：信息位长：校验位长：校验位长：最小码距：最小码距：汉明码汉明码 H 矩阵的构造方式：矩阵的构造方式：按按 m 位位的的 2 进进制制数数的的自自然然顺顺序序从从左左到到右右排排列列(不不包包括括全全 0 列列)，当当发发生生可可纠纠的的单单个个差差错错时时，伴伴随随式式为为 H 矩矩阵阵中中对对应应的的列列，译译码码比比较较方方便便将将上上述述非非标标准准形形式式的的 H 矩矩阵阵通通过过列列初初等等置置换换变变成成标标准准形形式式的的校校验验矩矩阵阵，纠纠错错能能力力保保持持不变不变

18、例：构造一个：构造一个 的的 2 元汉明码元汉明码由于由于 故构造的汉明码为故构造的汉明码为 线性分组码线性分组码汉明码的编码效率是很高的，汉明码的编码效率是很高的，第45页，讲稿共50张，创作于星期二46线性分组码的描述设设信信息息分分组组长长度度为为 ，在在每每一一信信息息组组后后加加上上 4 个个校校验验码码元元，构成构成 线性分组码线性分组码设设该该码码的的码码字字为为 ，其其中中 为信息码元，为信息码元，为为校校验验码码元元，；信信息息码码元元和和校校验验码码元元可可按按下下面方程组计算：面方程组计算：消息码字消息码字000000 0000100100 1110001001 1101

19、101101 0011010101 0111110110 1001011011 1010111111 0100利利用用上上式式每每给给出出一一个个 4 位位的的信信息息组组，就就可可编编出出一一个个码码字字，结果如表所示结果如表所示 模模 2 加加第46页，讲稿共50张，创作于星期二476.2.1线性分组码的描述 分组码的编码包括两个基本步骤分组码的编码包括两个基本步骤首先将信源的输出序列分为首先将信源的输出序列分为 k 位一组的信息组位一组的信息组然然后后信信道道编编码码器器根根据据一一定定的的编编码码规规则则将将 k 位位信信息息组组变变换换成成n 个个码元的码字码元的码字信息组和码字用矩

20、阵表示如下：信息组和码字用矩阵表示如下：信息组：信息组：k 位信息位信息 码字：码字：n 个码元个码元 k 位信息位位信息位r=n-k 位校验位位校验位通通常常对对编编码码器器附附加加一一个个线线性性约约束束条条件件，使使得得码码字字的的校校验验位位与与信信息息位位之之间间呈线性关系，这种码称为呈线性关系，这种码称为(n,k)线性分组码采采用用线线性性分分组组码码进进行行信信道道编编码码，就就是是给给已已知知信信息息组组按按预预定定规规则则添添加加校校验验码码元元以以构构成成码码字字。在在 k 个个信信息息元元之之后后附附加加 r=n-k 个个校校验验码码元元，使使每每个个校验码元是其中某些信

21、息码元的和校验码元是其中某些信息码元的和第47页，讲稿共50张，创作于星期二48线性分组码的生成矩阵和一致校验矩阵在在(n,k)线性分组码中，编码器输出的码字可以由如下方程组来决定：线性分组码中，编码器输出的码字可以由如下方程组来决定：如设：如设：则方程组的矩阵表示为：则方程组的矩阵表示为：c=mG所有满足上式码字所有满足上式码字(n 维向量维向量)的全体构成的全体构成(n,k)线性分组码线性分组码 C生成矩阵生生成成矩矩阵阵 G 是是一一个个 k 行行 n 列列(n k)秩秩为为 k 的的矩矩阵阵，它它 建建立立了了消消息息向向量量与码字的一一对应关系，它起着编码器的变换作用与码字的一一对应

22、关系，它起着编码器的变换作用G 的的每每一一行行都都是是一一个个码码字字，分分别别是是 k 维维消消息息向向量量组组 1000,01000,00010,00001 所对应的码字所对应的码字m 是任意是任意 k 维消息向量维消息向量运算：模运算：模 2 加、模加、模 2 乘乘第48页，讲稿共50张，创作于星期二49线性分组码的生成矩阵的性质设设 是某个二元线性分组码是某个二元线性分组码 的生成矩阵，则：的生成矩阵，则：n 维零向量维零向量 是一个码字，称为是一个码字，称为零码字封闭性：任意两个码字的和仍是一个码字，即：封闭性：任意两个码字的和仍是一个码字，即：线性分组码的最小码距等于最小非零码字重量：线性分组码的最小码距等于最小非零码字重量：(n,k)线线性性分分组组码码实实质质上上是是 n 维维 n 长长向向量量构构成成的的线线性性空空间间中中的的一一个个 k 维维线线性子空间性子空间 线线性性分分组组码码的的任任意意一一个个码码字字均均是是生生成成矩矩阵阵 的的行行向向量量 的的线线性性组组合合，即即 ，存存在在一一组组不不全全为为 0 的系数的系数 ，使得：，使得：第49页，讲稿共50张，创作于星期二感感谢谢大大家家观观看看第50页，讲稿共50张，创作于星期二