信息论与编码第六章信道编码讲稿.ppt
信息论与编码第六章信道编码第一页，讲稿共四十七页哦6.1 概述概述作用作用提高信息传输时的抗干扰能力提高信息传输时的抗干扰能力目的目的增加信息传输的可靠性增加信息传输的可靠性手段手段增加信息冗余度增加信息冗余度名称名称信道码、数据传输码、差错控制码信道码、数据传输码、差错控制码2第二页，讲稿共四十七页哦6.1 概述概述信道编码器在通信系统中的位置信道编码器在通信系统中的位置信源编码信源编码信道编码信源译码信源译码信道译码解密解密加密加密信宿信宿信源信源3第三页，讲稿共四十七页哦分类分类6.1 概述分分组组码码树树码码线线性性码码非非线线性性码码检检错错码码纠纠错错码码抗抗随随机机差差错错码码抗抗突突发发差差错错码码代代数数码码几几何何码码组组合合码码线性分组码线性分组码群码群码 线性树码线性树码卷积码卷积码 4第四页，讲稿共四十七页哦最小差错概率准则最小差错概率准则 理想译码器，依赖于输入概率分布。理想译码器，依赖于输入概率分布。最大似然准则最大似然准则 实用译码准则，与最小差错概率准则等价。实用译码准则，与最小差错概率准则等价。6.2 信道译码准则5第五页，讲稿共四十七页哦6.3 码例码例信道编译码方法的最初范例。信道编译码方法的最初范例。基本思路基本思路将码字分成两段将码字分成两段 用模二和对二元分组码进行一致性校验。用模二和对二元分组码进行一致性校验。奇偶校验码奇偶校验码只有一个校验位的汉明码只有一个校验位的汉明码。二元分组码信息位二元分组码信息位校验位校验位奇校验、偶校验。奇校验、偶校验。6第六页，讲稿共四十七页哦6.3 码例码例 奇校验奇校验 DES算法算法例例1 1 0 0 1 0 111 1 0 0 1 0 10偶校验偶校验7第七页，讲稿共四十七页哦6.3 码例码例多个校验位的汉明码多个校验位的汉明码 每个校验位是部分或全部信息位按每个校验位是部分或全部信息位按模二和规则确定。模二和规则确定。例例N=7，k=4c4c6c5u3u2u1u0c4c6c5c3c2c1c08第八页，讲稿共四十七页哦6.3 码例码例0101011可以纠正一个错误。可以纠正一个错误。译码译码 -验证校验位验证校验位 -错误位取反错误位取反9第九页，讲稿共四十七页哦6.4 线性分组码同时具有线性特性和分组特性把符号同时看成是运算的数把符号同时看成是运算的数引入模引入模2 2算术算术二元有限域有限个元素的集合，定义两种运算有限个元素的集合，定义两种运算加和乘加和乘加法有零元，乘法有幺元加法有零元，乘法有幺元有加逆元和乘逆元有加逆元和乘逆元加、乘满足结合律和交换律，加和乘满足分配加、乘满足结合律和交换律，加和乘满足分配律律 10第十页，讲稿共四十七页哦6.4 线性分组码加法加法 a+b乘法乘法 ab=c不可约不可约多项式多项式11第十一页，讲稿共四十七页哦6.4 线性分组码线性分组码的基本参数码码 长：长：n信息位长：信息位长：k码码 字字 数：数：M监督位长：监督位长：r最小码距：最小码距：dmin例例重复码重复码00011112第十二页，讲稿共四十七页哦6.4 线性分组码（4，3）偶校验码）偶校验码例例例例例例 奇校验码？奇校验码？恒比码？恒比码？010110110113第十三页，讲稿共四十七页哦 6.4 线性分组码衡量码的重要指标衡量码的重要指标 汉明重量（码重）汉明重量（码重）码字中非零码元的数目。码字中非零码元的数目。汉明重量（码重）汉明重量（码重）=例例1011010114第十四页，讲稿共四十七页哦6.4 线性分组码两个码字中相应码元取不同数值的码元数。两个码字中相应码元取不同数值的码元数。汉明距离（码距）汉明距离（码距）汉明距离（码距）汉明距离（码距）=1011010111010011例例15第十五页，讲稿共四十七页哦 6.4 线性分组码 最小最小汉明距离（最小码距）汉明距离（最小码距）同一码所有汉明距离中最小的一个。同一码所有汉明距离中最小的一个。例例（4，3）偶校验码）偶校验码10010000001111001010111101010110最小汉明距离（最小码距）最小汉明距离（最小码距）=16第十六页，讲稿共四十七页哦6.4 线性分组码检错和纠错能力检错和纠错能力1检错检错l=dmin-12纠错纠错t=（dmin-1）/23l+t=dmin-1,tl最小汉明距离最小汉明距离 （最小码距（最小码距d d）：任意两码）：任意两码字之间的汉明距离的最小值字之间的汉明距离的最小值 17第十七页，讲稿共四十七页哦6.4 线性分组码线性分组码检、纠错能力图示检、纠错能力图示18第十八页，讲稿共四十七页哦0011001110101010110001106.4 线性分组码线性分组码检、纠错能力图示检、纠错能力图示19第十九页，讲稿共四十七页哦汉明码简介6.4 线性分组码码码 长：长：n=2r-1信息位长：信息位长：k=n-r=2r-r-1码码 字字 数：数：M=2k监督位长：监督位长：r=n-k最小码距：最小码距：dmin=3纠错能力：纠错能力：t=120第二十页，讲稿共四十七页哦6.4 线性分组码线性分组码编码线性分组码编码信息矢量生成矩阵21第二十一页，讲稿共四十七页哦6.4 线性分组码一致校验方程组一致校验方程组校验矩阵22第二十二页，讲稿共四十七页哦6.4 线性分组码例例编码：编码：23第二十三页，讲稿共四十七页哦6.4 线性分组码译码（无差错）：译码（无差错）：24第二十四页，讲稿共四十七页哦6.4 线性分组码译码（有差错）：译码（有差错）：接收矢量接收矢量伴随式伴随式S可以指示差错的存在可以指示差错的存在25第二十五页，讲稿共四十七页哦6.4 线性分组码例例26第二十六页，讲稿共四十七页哦 6.4 线性分组码伴随式s0s1s2错误位置错误图样101z01000000111z10100000110z20010000011z30001000100z40000100010z50000010001 z6000000127第二十七页，讲稿共四十七页哦 6.4 线性分组码译码步骤：译码步骤：1计算伴随式，构造伴随式计算伴随式，构造伴随式-差错图案表差错图案表（s，e）；）；2对接收向量计算伴随式；对接收向量计算伴随式；3查（查（s，e）表得）表得e；4纠错。纠错。28第二十八页，讲稿共四十七页哦 6.4 线性分组码系统码系统码线性线性(N，k)码生成矩阵码生成矩阵G具有形式具有形式 由此产生的码称为系统码。系统码的一致由此产生的码称为系统码。系统码的一致监督矩阵具有形式监督矩阵具有形式二元有限域上的二元有限域上的-AT=AT码长为码长为N，信息位长度为，信息位长度为k的分组码称为的分组码称为(N，k)码。码。29第二十九页，讲稿共四十七页哦6.4 线性分组码线性分组码的性质线性分组码的性质 零向量零向量 是一个码字，称为零码字是一个码字，称为零码字 两码字之和或差仍是一个码字两码字之和或差仍是一个码字线性性线性性在码的所有码字上减去任一特定的在码的所有码字上减去任一特定的码字，结果仍是这同一码的全部码码字，结果仍是这同一码的全部码字。字。对称性对称性二元有限域上最小码距二元有限域上最小码距 最小码重。最小码重。30第三十页，讲稿共四十七页哦6.5 线性循环码汉明码的对偶码汉明码的对偶码线性循环码线性循环码例例31第三十一页，讲稿共四十七页哦（1）（3）（4）（2）（4）6.5 线性循环码32第三十二页，讲稿共四十七页哦6.5 线性循环码循环码的多项式描述循环码的多项式描述 g(x)一致校验多项式一致校验多项式编码编码译码译码33第三十三页，讲稿共四十七页哦 更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。6.5.1 6.5.1 循环码的多项式描述循环码的多项式描述34第三十四页，讲稿共四十七页哦35第三十五页，讲稿共四十七页哦36第三十六页，讲稿共四十七页哦定义定义 如果一个线性分组码的任意一个码字如果一个线性分组码的任意一个码字c(n元组元组)都是另外一个码字都是另外一个码字c的循环移位的循环移位,称此线性分组码为一个循环码称此线性分组码为一个循环码.将循环码的码字用多项式将循环码的码字用多项式c(x)c(x)，称为码多项，称为码多项式（简称码式）表示后，循环码集合表示式（简称码式）表示后，循环码集合表示C(x),C(x),37第三十七页，讲稿共四十七页哦例 6.3.2 如下确定的如下确定的C CA A是线性循环码，是线性循环码，C CB B是是非循环的线性分组码，非循环的线性分组码，C CC C是非线性的循环码。是非线性的循环码。，38第三十八页，讲稿共四十七页哦定理：定理：（n,k）循环码循环码C(x)中存在唯一的一个中存在唯一的一个非零的，首一的和最低次为非零的，首一的和最低次为r（rn）的码）的码 多项式多项式g(x)满足：满足：g(x)=xr+gr-1xr-1+.+g1X+g0 g00 r=n-k并且并且c(x)是码式当且仅当是码式当且仅当c(x)是是g(x)的倍式的倍式39第三十九页，讲稿共四十七页哦定义定义 由上述定理确定的码式由上述定理确定的码式g(x)g(x)称称为循环码为循环码(n,k)(n,k)的的生成多项式生成多项式.因因此此(n,k)(n,k)循循环环码码的的构构造造是是如如何何构构造造生生成成多多项项式式g(x)g(x)。循环码由生成多项式的倍式组成循环码由生成多项式的倍式组成40第四十页，讲稿共四十七页哦定理：定理：g(x)是（是（n,k）循环码的生成多项式）循环码的生成多项式，当且仅当当且仅当g(x)是是xn-1的的r=n-k次因式。次因式。41第四十一页，讲稿共四十七页哦42第四十二页，讲稿共四十七页哦43第四十三页，讲稿共四十七页哦44第四十四页，讲稿共四十七页哦6.3.1循环码的多项式描述循环码的多项式描述6.3.2 循环码的生成矩阵循环码的生成矩阵6.3.3系统循环码系统循环码6.3.4多项式运算电路多项式运算电路6.3.5循环码的编码电路循环码的编码电路6.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测6.3.7BCH码与码与RS码码45第四十五页，讲稿共四十七页哦6.3.2循环码的生成矩阵和校验矩阵(n,k)循环码的生成矩阵为循环码的生成矩阵为46第四十六页，讲稿共四十七页哦(n,k)循环码的校验矩阵为循环码的校验矩阵为47第四十七页，讲稿共四十七页哦
