信息论基础线性分组码.pptx

1展望展望提高信息传输的可靠性和有效性，始终是通信工作所追求的目标；近几节课掌握的几个编码定理，已经明确指出在一定条件下总存在简单、有效编、译的“好码”.但是，都没有给出这类好码的编、译方法.24.6 线性分组码线性分组码基础知识基础知识抽象代数基础抽象代数基础线性代数基础线性代数基础3引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码4.6 线性分组码线性分组码4引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码4.6 线性分组码线性分组码5设传输一比特字符x=0或1若传输过程中出现差错,不能被发现引例引例6引例引例n0后附加字符0，1后附加1；即只有00和11被接受，且00视为0，11视为1；n故：如果有一位错误发生，可以被检出！7n如果通信过程中发现差错，如果通信过程中发现差错，可以通过要求对方重新发送来获得正确的信息，即所谓的“数量换质量”.但是这在实时信息采集系统中可能是有困难的，因为信息源已经发生变化；即使是在发方保留原信息样本的情况下，也只有在差错率很低的条件下是比较可行的.n因为如果通信条件比较恶劣，差错出现频繁，以至多次重发仍然得不到一份正确的信息.n这时，仅有“检错”手段，已无能为力！引例引例8引例引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.9引例引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.纠错码纠错码信息位信息位校验位校验位10引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的编码线性分组码的编码汉明码的编码与译码汉明码的编码与译码4.6 线性分组码线性分组码11线性分组码的基本概念线性分组码的基本概念n分组码分组码分组码分组码是把信源输出的信息序列，以k个信息位分为一段，通过编码器把这段信息位按一定规则f 产生r个校验位，输出长为n=k+r的一个码字，所得码字的全体.称之为（n，k）分组码）分组码！n表示码长，k信息位个数.12引例引例0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时：发生不超过两位的错误均可被检出；发生一位错误可以被纠正.(3,1)分组分组码码信息位信息位校验位校验位13线性分组码的基本概念线性分组码的基本概念（n，k）分组码分组码若校验位与信息位之间的关系是线性的，即上述编码规则是线性的，称之为（n，k）线性分组码！线性分组码！14n线性编码线性编码从到的一个线性映射称为一个线性编码线性编码；线性分组码的基本概念线性分组码的基本概念即均有；若是一一映射，则称其为唯一可译线性编码；15线性分组码的基本概念线性分组码的基本概念n线性分组码线性分组码线性分组码线性分组码是把信源输出的信息序列，以k个信息位分为一段，通过编码器把这段信息位按线性编码规则f 产生r个校验位，输出长为n=k+r的一个码字，所得码字的全体.称之为（n，k）线性分组码）线性分组码！n表示码长，k信息位个数.码字个数码字个数M=2k.16若设码字若设码字，则即校验位是由信息位线性组合得到即校验位是由信息位线性组合得到.线性分组码的基本概念线性分组码的基本概念17可见，码字的三个校验元都由其前两位线性组合得到，即可由的线性方程组求得；线性分组码的基本概念线性分组码的基本概念信息位k=2码字数M=418线性编码线性编码线性分组码的基本概念线性分组码的基本概念19例题例题1：下面是某个下面是某个（n，k）线性二元码的全部码字线性二元码的全部码字x16=000000 x26=100011x36=010101x46=001111x56=110110 x66=101100 x76=011010 x86=111001求求n、k的值；的值；n=6;线性分组码的基本概念线性分组码的基本概念M=2k k=3.解：20n例2、（5，2）线性二元码的全部码字n设码字，可得线性分组码的基本概念线性分组码的基本概念21线性分组码的基本概念线性分组码的基本概念n改写为n用矩阵可表示成：校验校验矩阵矩阵 与任一码字与任一码字的乘积为的乘积为0 224线性分组码的特性线性分组码的特性2k个码字完全可由其中一组k 个独立的码字组合而成；线性分组码的基本概念线性分组码的基本概念4生成矩阵生成矩阵从线性分组码（n，k）中任取 k 个线性无关的码字，以行的形式写成矩阵G，则称为该线性分组码线性分组码的的生成矩阵生成矩阵.23例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字构造它的一个生成矩阵构造它的一个生成矩阵.线性分组码的基本概念线性分组码的基本概念解：由k=3个线性独立的码字组成：24例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字验证：验证：线性分组码的基本概念线性分组码的基本概念25n系统码系统码 若若（n,k）线性分组码的生成矩阵形如线性分组码的生成矩阵形如 G=(Ik A)其中其中Ik是是k阶单位阵，阶单位阵，A为为 阶子阵，阶子阵，则称这类码为系统码则称这类码为系统码.线性分组码的基本概念线性分组码的基本概念特点：校验矩阵为特点：校验矩阵为H=(-AT I(n-k).26例题例题3：下面是一个（下面是一个（6，3）线性二元码的全部码字）线性二元码的全部码字它的一个生成矩阵它的一个生成矩阵线性分组码的基本概念线性分组码的基本概念请写出它的校验矩阵请写出它的校验矩阵H.信息组原封不动地搬到码字前位的码27线性分组码的基本概念线性分组码的基本概念28线性分组码的基本概念线性分组码的基本概念n汉明距离：指（n,k）分组码中两个码字xn、yn对应位取值不同的个数；记为d（xn，yn）.例：29线性分组码的基本概念线性分组码的基本概念n理查德理查德卫斯里卫斯里汉明汉明（Richard Wesley Hamming，1915.2.111998.1.7.），美国数学家，主要贡献在计算机科学和电讯。n1937年芝加哥大学学士学位毕业，1939年内布拉斯加大学硕士学位毕业，1942年伊利诺伊大学香槟分校博士学位毕业，博士论文为一些线性微分方程边界值理论上的问题（Some Problems in the Boundary Value Theory of Linear Differential Equations）。n二战期间在路易斯维尔大学当教授，1945年参加曼哈顿计划，负责编写电脑程式，计算物理学家所提供方程的解。该程式是判断引爆核弹会否燃烧大气层，结果是不会，于是核弹便开始试验。n1946至76年在贝尔实验室工作。他曾和约翰怀尔德杜奇、克劳德艾尔伍德香农合作。1956年他参与了IBM650的程式语言发展工作。30线性分组码的基本概念线性分组码的基本概念n汉明距离：指（n,k）分组码中两个码字xn、yn对应位取值不同的个数；记为d（xn，yn）.例：31线性分组码的基本概念线性分组码的基本概念n线性分组码的最小距离：称（n,k）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离d.n（5,2）线性分组码全部码字：n最小距离d=3.汉明重量汉明重量32引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码4.6 线性分组码线性分组码生成矩阵校验矩阵码的最小距离33引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码4.6 线性分组码线性分组码34线性分组码的译码线性分组码的译码n基本概念基本概念错误图样错误图样n设发送的码字xn=(x1，x2，xn)，通过有扰信道传输，到达接收端译码器的序列为 rn=(r1，r2，rn)n信道中的干扰表示为二进序列：错误图样错误图样en=(e1，e2，en).相应有错的ei取值为1.nrn=xn+en，其中ri=xi+ei，xi，ri，eiGF(2)称en为信道中的错误图样.译码器任务译码器任务从从rn中得中得到到xn或或en.35线性分组码的译码线性分组码的译码n例例4 设发送序列xn=(1111100000)，收到的序列rn=(1001010000).第二、三、五、六位产生了错误，第二、三、五、六位产生了错误，因此信道的错误图样因此信道的错误图样en的二、的二、三、三、五、五、六位取值为六位取值为1，其它各位取值为，其它各位取值为0，即即 en=(0110110000).用式子可表示成：用式子可表示成：rn=xn+en36线性分组码的译码线性分组码的译码n基本概念基本概念伴随式伴随式n由于分组码中的任一码字满足：xnHT=0，所以，可对收到的序列rn进行检验：rnHT=(xn+en)HT=xnHT+enHT=enHT若en=0，则rnHT=0；若en0，则rnHT 0.n记S=enHT，称之为接收序列rn的伴随式.rnHT仅与错误图样有关，与发送什么码字无关！37n（n，k）线性分组码的校验矩阵，用列向量表出：线性分组码的译码线性分组码的译码其中，hn-i为H矩阵的第i列.38n设en=(e1，e2，en)=(0，ei1，0，ei2，0，ei3，0，eit，0，0)其中eij=1,即第i1，i2，it位有错，则线性分组码的译码线性分组码的译码S是是H中相应于中相应于eij那几那几列的线性组合！列的线性组合！39线性分组码的译码线性分组码的译码n例例5已知（7，3）码的校验矩阵为若发送码字xn=（1110100），收到rn=（0010100）.则错误图样为en=（1100000）.40线性分组码的译码线性分组码的译码由定义可以求得，rn的伴随式：是是H矩阵第一列与第矩阵第一列与第二列之和！二列之和！41线性分组码的译码线性分组码的译码n若错误图样en=（0010000），则是是H矩阵第三列！矩阵第三列！若错误图样中只有一个分量非零，则ST是H矩阵相应的列，因而能够纠正单个错误！42线性分组码的译码线性分组码的译码n若错误图样en=（0010100），则是是H矩阵第三列与第矩阵第三列与第五列之和！五列之和！43线性分组码的译码线性分组码的译码由定义可以求得，rn的伴随式：是是H矩阵第一列与第矩阵第一列与第二列之和！二列之和！若发生两个错误，译码器只能判决传输有错（en 0）,不能判定由哪几位错误引起！44线性分组码的译码线性分组码的译码n线性分组码能自动纠正t个错误的充要条件是d=2t+1.最大似然译码准则是纠错的策略依据.若收到的字符串是码字本身，则直接按码字译码；否则，按与接收到的字的Hamming距离最接近的码字译码.45线性分组码的译码线性分组码的译码n例例5已知（7，3）码的校验矩阵为最小距离d=3 d=2t+146线性分组码的译码线性分组码的译码n（n,k）码的译码步骤）码的译码步骤 （1）由接收到的）由接收到的rn，计算伴随式，计算伴随式S=rnHT；（2）若）若S=0，则认为接收无误；，则认为接收无误；若若S0，则由，则由S找出错误图样找出错误图样en；（3）由）由en和和rn找出找出xn=rn-en.47引例引例线性分组码的基本概念线性分组码的基本概念线性分组码的译码线性分组码的译码汉明码的编码与译码汉明码的编码与译码4.6 线性分组码线性分组码48线性分组码线性分组码n汉明码(Hamming Code)n汉明码是1950年由汉明首先构造，用以纠正单个错误的线性分组码.n由于它的编译码非常简单，很容易实现，因此用得很普遍，特别是在计算机的存贮和运算系统中更常用到，是一类特别引人注意的码.49线性分组码线性分组码n汉明码(Hamming Code)n汉明码不是指一个码，而是代表一类码；汉明码不是指一个码，而是代表一类码；u汉汉明明码码码码长长n和和信信息息位位k服服从从以以下下规规律律：(n,k)=(2m-1,2m-1-m)，其中其中m=n-k；汉明码的最小距离汉明码的最小距离d=3；所以，纠错能力纠错能力t=1；50n汉明码汉明码(Hamming Code)的译码的译码n例例6已知GF(2)上的（6，3）汉明码的一致校验矩阵H为：线性分组码线性分组码51线性分组码线性分组码n若发送码字xn=(101011),接收序列为rn=(101011).n若发送码字xn=(101011),接收序列为rn=(100011).判定传输中没有发判定传输中没有发生错误！生错误！判定接收序列判定接收序列rn的第的第3 3位是有错的！位是有错的！52线性分组码：线性分组码：生成矩阵，校验矩阵；生成矩阵，校验矩阵；伴随式：伴随式：线性分组码的译码；线性分组码的译码；汉明码的编码与译码汉明码的编码与译码.结语结语53作业设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？54习题课n1-b)解：解：信道的信道矩阵为其满足对称性，所以信道为对称离散信道.由对称离散信道的信道容量公式得55最佳输入分布是输入为等概分布.习题课56习题课n1-c)解：解：信道的信道矩阵为可设P(0)=P(1)=1/2，此时输出端的概率分布为P(0)=P(1)=(1-q)/2，P()=q由定理可以求得572 达到信道容量输入分布的充要条件达到信道容量输入分布的充要条件信道容量的计算信道容量的计算令令定理定理4.2.2 一般离散信道的互信息一般离散信道的互信息I(X；Y)达到极大值达到极大值（即等于信道容量）的充要条件是输入概率分布（即等于信道容量）的充要条件是输入概率分布p(x)满足满足58习题课n1-f)解：解：信道的信道矩阵为可设P(0)=p，此时输出端的概率分布为P(Y=0)=p/2.平均互信息I(X;Y)=H(p/2)-pH(1/2)对互信息求驻点，它的极值即为信道容量.59dI/dp=1/2*log(2-p)/p-H(1/2)=0；整理得p=2/5，所以C=H(Y)-H(Y|X)=H(1/5)-2/5=0.3219bit/symbol习题课60习题课n1-h)解：解：信道的信道矩阵为设j=C+logP(yj)，则61习题课即解得所以j=C+logP(yj)62从而，习题课由于可以解得635)由信道的信道矩阵可知：是非对称信道，不能利用公式；可以利用方程组求解习题课j=C+logP(yj)64习题课65n由于输入为1、2时信道的转移概率对称分布，所以可设信源的概率分布为习题课66设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？习题课（补充）67解：设码字C=(c5c4c3c2c1c0)，有习题课故得所以n=6，k=3，为(6,3)分组码共有码字2k=8个68设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？习题课（补充）69习题课由上式可得取一组线性无关的基础解系，得到生成矩阵70设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？习题课（补充）71习题课由可知，向量101010不是码字72设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？此分组码的生成矩阵；向量101010是否是码字？设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？习题课（补充）73习题课接收序列R的伴随式是校验矩阵的第五列据此可以判定码字中的第五个分量发生错误，则E=(000010)74但实际的错误图样E为E=(000010)+(001111)=(001101)是码字传输中发生了三位码元错误因为该（6，3）码dmin=3，所以根据伴随式只能纠正一位码元发生错误的错误图样；从而。当传输过程中码字发生的多于一位错误就无法纠正习题课