线性分组码精选课件.ppt

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

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

2、到一份正确的信息.这时，仅有“检错”手段，已无能为力！引例引例第四页，本课件共有50页5引例引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.第五页，本课件共有50页6引例引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.纠错码纠错码信息位校验位第六页，本课件共有50页7线性分组码的基本概念线性分组码的基本概念分组码分组码分组码分组码是把信源输出的信息序列，以k个信息位分为一段，通过编

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

4、个二元集，在其上定义模为一个二元集，在其上定义模2的加法和乘法运算的加法和乘法运算加法：加法：乘法：乘法：可见二元集可见二元集0,1对上述定义的加法及乘法运算封闭，并满足对上述定义的加法及乘法运算封闭，并满足一个一个“域域”所要求的交换律、结合律、分配律等运算规则，因此所要求的交换律、结合律、分配律等运算规则，因此0,1对所规定的加法和乘法运算构成一个域，称为二元域，记作对所规定的加法和乘法运算构成一个域，称为二元域，记作GF(2).第十页，本课件共有50页11注注 第十一页，本课件共有50页12称码为称码为(n,k)码码.二、线性分组码的定义及表示二、线性分组码的定义及表示第十二页，本课件共

5、有50页13若设码字若设码字 ，则即校验位是由信息位线性组合得到即校验位是由信息位线性组合得到.第十三页，本课件共有50页14可见，码字的三个校验元都由其前两位线性组合得到，即可由线性方程组求得；信息位k=2码字数M=4第十四页，本课件共有50页15线性编码线性编码第十五页，本课件共有50页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.解

6、：第十六页，本课件共有50页17例2、（5，2）线性二元码的全部码字设码字 ，可得第十七页，本课件共有50页18改写为用矩阵可表示成：校验校验矩阵矩阵 与任一码字的乘积为0 第十八页，本课件共有50页194线性分组码的特性线性分组码的特性 2k个码字完全可由其中一组k 个独立的码字组合而成；4生成矩阵生成矩阵从线性分组码（n，k）中任取 k 个线性无关的码字，以行的形式写成矩阵G，则称为该线性分组码的线性分组码的生成矩阵生成矩阵.第十九页，本课件共有50页20例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字构造它的一个生成矩阵构造它的一个生成矩阵.解解：由

7、：由k=3 个线性独立的码字组成：个线性独立的码字组成：第二十页，本课件共有50页21例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字验证：验证：第二十一页，本课件共有50页22说明说明第二十二页，本课件共有50页23 一个线性子空间可以有不同的但相互等价的基，亦即不同的一个线性子空间可以有不同的但相互等价的基，亦即不同的G可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。可以产生相同的线性码，所以一个线性码的生成矩阵不唯一。第二十三页，本课件共有50页24例例4 4 矩阵矩阵为一个为一个(7,3)码码.第二十四页，本课件共有50页25系统码系统码 若

8、若（n,k）线性分组码的生成矩阵形如线性分组码的生成矩阵形如 G=(Ik A)其中其中Ik是是k阶单位阵，阶单位阵，A为为 阶子阵，阶子阵，则称这类码为系统码则称这类码为系统码.特点：校验矩阵为特点：校验矩阵为H=(AT I(n-k).三、系统编码与校验矩阵三、系统编码与校验矩阵第二十五页，本课件共有50页26例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字它的一个生成矩阵它的一个生成矩阵请写出它的校验矩阵请写出它的校验矩阵H.第二十六页，本课件共有50页27第二十七页，本课件共有50页28注：系统码的码字的前注：系统码的码字的前k个码元就是它所载荷的数字

9、消息，故个码元就是它所载荷的数字消息，故系统码的前系统码的前k为称为信息位，后为称为信息位，后n-k位称为校验位位称为校验位.第二十八页，本课件共有50页29校验矩阵校验矩阵即即结论：结论：第二十九页，本课件共有50页30汉明距离汉明距离：指（指（n,k）分组码中两个码字）分组码中两个码字xn、yn对应位取对应位取值不同的个数；记为值不同的个数；记为d（xn，yn）.例：例：第三十页，本课件共有50页31汉明距离汉明距离：指（指（n,k）分组码中两个码字）分组码中两个码字xn、yn对应位取对应位取值不同的个数；记为值不同的个数；记为d（xn，yn）.例：例：第三十一页，本课件共有50页32线性

10、分组码的最小距离线性分组码的最小距离：称（称（n,k）分组码中任两个码字汉明距离的最）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离小值，为该分组码的最小距离d.（5,2）线性分组码全部码字：）线性分组码全部码字：最小距离最小距离d=3.汉明重量第三十二页，本课件共有50页33汉明(Hamming)码汉汉明明码码是是一一类类能能纠纠正正一一位位差差错错的的线线性分组码，其参数为：性分组码，其参数为：码长：码长：信息位长：信息位长：校验位长：校验位长：最小码距：最小码距：汉明码汉明码 H 矩阵的构造方式：矩阵的构造方式：按按 m 位位的的 2 进进制制数数的的自自然然顺顺序序从从左左到

11、到右右排排列列(不不包包括括全全 0 列列)，当当发发生生可可纠纠的的单单个个差差错错时时，伴伴随随式式为为 H 矩矩阵阵中中对对应的列，译码比较方便应的列，译码比较方便将将上上述述非非标标准准形形式式的的 H 矩矩阵阵通通过过列列初初等等置置换换变变成成标标准准形形式式的的校校验验矩矩阵阵，纠纠错错能能力保持不变力保持不变例：构造一个：构造一个 的的 2 元汉明码元汉明码由于由于 故构造的汉明码为故构造的汉明码为 线性分组码线性分组码汉明码的编码效率是很高的，汉明码的编码效率是很高的，第三十三页，本课件共有50页34设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组

12、码的生成矩阵；向量101010是否是码字？习题课（补充）第三十四页，本课件共有50页35解：设码字C=(c5c4c3c2c1c0)，有习题课故得所以n=6，k=3，为(6,3)分组码共有码字2k=8个第三十五页，本课件共有50页36设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？习题课（补充）第三十六页，本课件共有50页37习题课由上式可得取一组线性无关的基础解系，得到生成矩阵第三十七页，本课件共有50页38设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？

13、习题课（补充）第三十八页，本课件共有50页39习题课由可知，向量101010不是码字第三十九页，本课件共有50页43系统码消息G1 码字G2 码字000000 000000 000001111 000001 101010110 101010 011011001 101011 110100101 011100 110101010 011101 011110011 110110 101 111100 110111 000生生成成矩矩阵阵 G 的的选选择择不不是是惟惟一一的的；如如下下面面的的G1 和和 G2 都都可可作作为为同同一一个个(6,3)码码的的生生成成矩矩阵阵，所所对对应的码字如右表所示

14、：应的码字如右表所示：系系统统码码的的编编码码器器仅仅需需存存储储 k (n-k)个个数数字字(非非系系统统码码要要存存储储 k n 个个数数字字)，译译码码时时仅仅需需对对前前 k 个个信信息息位位纠纠错错即即可可恢恢复复信信息息；可可见见系系统统码码的的编编码码和和译译码码比比较较简简单单，而而性性能能与与非非系系统统码码一一样样，所所以以系系统统码码得得到到了了十十分分广泛的应用广泛的应用虽虽然然二二者者用用了了不不同同形形式式的的生生成成矩矩阵阵，却却都都是是(6,3)线线性性分分组组码码，因因此此它它们们的的检检错错和和纠纠错错能能力力是是一一样样的的，但但是是 G2 生生成成的的码

15、码，其其前前 k 位位与与消消息息码码完完全全相相同同，这这种种码码称称为为系统码，其其生生成成矩矩阵阵和和一一致校验矩阵分别记为致校验矩阵分别记为 Gs,Hs第四十三页，本课件共有50页44线性分组码的生成矩阵和校验矩阵的关系由于由于 G 的每一行都是一个码字，所以的每一行都是一个码字，所以 G 的每一行的每一行 c i 都满足：都满足：从而有：从而有：在在码码字字集集合合不不变变的的前前提提下下，给给定定任任何何一一个个线线性性分分组组码码，通通过过其其生成矩阵生成矩阵 G 实施实施行初等变换，均可以转换为某个系统码，均可以转换为某个系统码当当且且仅仅当当线线性性分分组组码码一一致致校校验

16、验矩矩阵阵 H 中中任任意意 d-1 个个列列线线性性无无关关而而某某 d 列线性相关时，线性分组码的最小码距为列线性相关时，线性分组码的最小码距为 dmin=d第四十四页，本课件共有50页45汉明(Hamming)码汉汉明明码码是是一一类类能能纠纠正正一一位位差差错错的的线性分组码，其参数为：线性分组码，其参数为：码长：码长：信息位长：信息位长：校验位长：校验位长：最小码距：最小码距：汉明码汉明码 H 矩阵的构造方式：矩阵的构造方式：按按 m 位位的的 2 进进制制数数的的自自然然顺顺序序从从左左到到右右排排列列(不不包包括括全全 0 列列)，当当发发生生可可纠纠的的单单个个差差错错时时，伴

17、伴随随式式为为 H 矩矩阵阵中中对对应应的的列列，译码比较方便译码比较方便将将上上述述非非标标准准形形式式的的 H 矩矩阵阵通通过过列列初初等等置置换换变变成成标标准准形形式式的的校校验验矩矩阵阵，纠纠错错能能力力保持不变保持不变例：构造一个：构造一个 的的 2 元汉明码元汉明码由于由于 故构造的汉明码为故构造的汉明码为 线性分组码线性分组码汉明码的编码效率是很高的，汉明码的编码效率是很高的，第四十五页，本课件共有50页46线性分组码的描述设设信信息息分分组组长长度度为为 ，在在每每一一信信息息组组后后加加上上 4 个个校校验验码码元元，构成构成 线性分组码线性分组码设设该该码码的的码码字字为

18、为 ，其其中中 为信息码元，为信息码元，为为校校验验码码元元，；信信息息码码元元和和校校验验码码元元可可按按下下面方程组计算：面方程组计算：消息码字消息码字000000 0000100100 1110001001 1101101101 0011010101 0111110110 1001011011 1010111111 0100利利用用上上式式每每给给出出一一个个 4 位位的的信信息息组组，就就可可编编出出一一个个码码字，结果如表所示字，结果如表所示 模模 2 加加第四十六页，本课件共有50页476.2.1线性分组码的描述 分组码的编码包括两个基本步骤分组码的编码包括两个基本步骤首先将信源的

19、输出序列分为首先将信源的输出序列分为 k 位一组的信息组位一组的信息组然然后后信信道道编编码码器器根根据据一一定定的的编编码码规规则则将将 k 位位信信息息组组变变换换成成n 个个码码元元的码字的码字信息组和码字用矩阵表示如下：信息组和码字用矩阵表示如下：信息组：信息组：k 位信息位信息 码字：码字：n 个码元个码元 k 位信息位位信息位r=n-k 位校验位位校验位通通常常对对编编码码器器附附加加一一个个线线性性约约束束条条件件，使使得得码码字字的的校校验验位位与与信信息息位位之之间间呈线性关系，这种码称为呈线性关系，这种码称为(n,k)线性分组码采采用用线线性性分分组组码码进进行行信信道道编

20、编码码，就就是是给给已已知知信信息息组组按按预预定定规规则则添添加加校校验验码码元元以以构构成成码码字字。在在 k 个个信信息息元元之之后后附附加加 r=n-k 个个校校验验码码元元，使每个校验码元是其中某些信息码元的和使每个校验码元是其中某些信息码元的和第四十七页，本课件共有50页48线性分组码的生成矩阵和一致校验矩阵在在(n,k)线线性性分分组组码码中中，编编码码器器输输出出的的码码字字可可以以由由如如下下方方程程组组来决定：来决定：如设：如设：则方程组的矩阵表示为：则方程组的矩阵表示为：c=mG所有满足上式码字所有满足上式码字(n 维向量维向量)的全体构成的全体构成(n,k)线性分组码线

21、性分组码 C生成矩阵生生成成矩矩阵阵 G 是是一一个个 k 行行 n 列列(n k)秩秩为为 k 的的矩矩阵阵，它它 建建立立了了消消息息向向量量与码字的一一对应关系，它起着编码器的变换作用与码字的一一对应关系，它起着编码器的变换作用G 的的每每一一行行都都是是一一个个码码字字，分分别别是是 k 维维消消息息向向量量组组 1000,01000,00010,00001 所对应的码字所对应的码字m 是任意是任意 k 维消息向量维消息向量运算：模运算：模 2 加、模加、模 2 乘乘第四十八页，本课件共有50页49线性分组码的生成矩阵的性质设设 是某个二元线性分组码是某个二元线性分组码 的生成矩阵，则

22、：的生成矩阵，则：n 维零向量维零向量 是一个码字，称为是一个码字，称为零码字封闭性：任意两个码字的和仍是一个码字，即：封闭性：任意两个码字的和仍是一个码字，即：线性分组码的最小码距等于最小非零码字重量：线性分组码的最小码距等于最小非零码字重量：(n,k)线线性性分分组组码码实实质质上上是是 n 维维 n 长长向向量量构构成成的的线线性性空空间间中中的的一一个个 k 维线性子空间维线性子空间 线线性性分分组组码码的的任任意意一一个个码码字字均均是是生生成成矩矩阵阵 的的行行向向量量 的的线线性性组组合合，即即 ，存存在在一一组组不不全全为为 0 的系数的系数 ，使得：，使得：第四十九页，本课件共有50页感谢大家观看第五十页，本课件共有50页