线性分组码的例子.pptVIP

第1页，共18页，星期日，2025年，2月5日内容提要汉明码RM码格雷码交织码第2页，共18页，星期日，2025年，2月5日汉明码对任意整数m2，存在满足如下条件的汉明码码长n=2m-1信息符号数k=2m-m-1校验符号数n-k=m纠错能力t=1（dmin=3）该码的奇偶校验阵H由所有非零的m维列向量构成，前m列可写成单位阵。H的任何两列都不同，且非零，故任意两列相加不为0，故最小距离至少为3；而任意两列之和必定为H的某个列向量，因为H包括所有非零m维列向量，故有三个列向量之和为0，所以最小距离为3第3页，共18页，星期日，2025年，2月5日汉明码的标准阵可将所有重量为t=1的n=2m-1个向量作为陪集首，共2m-1个，又因为n-k=m，即该码有2m个陪集，因此0向量和所有重量为1的m维向量首构成了标准阵的所有陪集首故汉明码只能纠正t=1个错误，可用查表译码完备码：若标准阵的陪集首全都是重量小于等于t的向量（错误模式），即可纠正错误模式的重量都小于等于t。汉明码和(23,12)格雷码是完备码，完备码很少第4页，共18页，星期日，2025年，2月5日汉明码的改造删除H的若干列，如重量为偶数的列，得到新的H，其最小距离为4，称为“缩短的汉明码”缩短汉明码保证校验位数目不变，减少了信息位的数目，降低了码率纠错能力没变，陪集首依然没变，全是重量为1的错误模式，检错能力？译码：看校正子的情况：0，重量为奇数（可纠正1个错，查表），重量为偶数（不可纠正错误）漏检率很低，符合漏检率的理论上界，故是好的差错检测码第5页，共18页，星期日，2025年，2月5日检测两个错，纠正一个错的码SEC-DED首先构造码长n=2m-1，最小距离为3的汉明码从此汉明码的H阵中删除一些列，得到H0满足：每列有奇数个11的个数尽可能小每一行中1的个数都应该相等或极可能接近均值第一个条件保证最小距离至少为4，二、三个条件为了实现简单Hsiao提出了一种构造H0的算法并找到了一些最优的SEC-DED码第6页，共18页，星期日，2025年，2月5日Reed-Muller，RM码r阶RM(r,m)码，纠正多个错误，Muller提出，Reed译码码长：n=2m维数(信息序列的长度)：最小距离：dmin=2m-r若令m=5，r=2，那么n=32，k(2,5)=16,dmin=8，即存在一个(32,16)RM码第7页，共18页，星期日，2025年，2月5日RM码的构造设v0是全1向量，1=i=m，由此定义了v0,v1,…,vm定义向量运算“·”，a·b=(a1·b1,a2·b2,…,an·bn)，简记为ab集合Grm(r,m)={v0,v1,…,vm,v1v2,v1v3,…,vm-1vm,…,vm-r+1…vm}共有k(r,m)个元素，是(2m,k)RM码的生成向量，即可张成整个码空间的基。将每个元素看成矩阵的一行，就得到生成矩阵。集合Grm(r-1,m)是Grm(r,m)的真子集，是r-1阶RM码的生成矩阵。第8页，共18页，星期日，2025年，2月5日RM码Grm(r,m)中所有向量都是偶数重量m-r-1阶RM码(m-r-1,m)的对偶码是r阶RM码(r,m)零阶RM码RM(0,m)是重复码而(m-1)阶RM码是单奇偶校验码，k=2m-1第9页，共18页，星期日，2025年，2月5日RM码的译码，例子说明此码是最小距离为4的(16,11)线性码，假设信息序列：观察上述11个生成向量，注意到除了v1v2，其他生成向量每连续4个分量一组求和都是0，可推出：4个彼此独立的方程求a12的值，可用于校验，若接受序列中只有一个错误，则4个值中只错一个，采用大多数原则可纠错，这就是大数逻辑判决准则译码第10页，共18页，星期日，2025年，2月5日RM码的译码aij被正确译码后，考虑传输没出错，则有利用基向量的特点，发现两个连续分量的和的关系，构建ai的独立判定方程，再用大数逻辑判决译码类似上面步骤，最后译码a0，共三步（r+1步）第11页，共18页，星期日，2025年，2月5日(24,12)格雷码汉明码外唯一一个非平凡二进制完备码(23,12)格雷码，最小距离7(23,12)格雷码通过增加一个总的奇偶校验位，构成(24,12)码，最小距离为8，但非完备码设其生成矩阵G=[PI12],P