编码理论第1章-绪论

1第1章绪论1.1编码理论的基本概念1.2编码理论的发展1.3编码理论研究的内容和目的21.1编码理论的基本概念1．通信系统•本质——信息的传输系统•目的——把接收方不知道的信息及时、可靠、完整、安全、32．通信系统模型包括：信源、编码器、信道、译码器、信宿五部分信道编码信源编码保密译码信道译码信源译码保密编码噪声信道信源信宿4(1)信源——产生消息和消息序列的源——可以是人、生物、机器或其他事物——是事物各种运动状态或存在状态的集合•消息——信源的输出•消息——具体，如：语音、图像、文字等•信息——抽象2．通信系统模型(续)5(2)编码器——信源编码器、信道编码器、保密编码器①信源编码——对信源输出的消息进行变换和处理•目的——提高信息传输的有效性②信道编码——对消息进行的变换和处理•目的——提高信息传输的可靠性③保密编码——目的是保证信息的安全性2．通信系统模型(续)6(3)信道——信号从甲地传输到乙地的通道•狭义信道——信号的传输媒质(介)[例]明线、电缆、波导、光纤、无线电波空间等•广义信道——除狭义信道外，还包括通信系统某些部分•信道噪声——通信系统各处干扰、噪声的集中等效体现2．通信系统模型(续)7(4)译码器——编码器功能之反•也分成信源译码器、信道译码器、保密译码器三种(5)信宿——消息传送的归宿[说明]①对实际通信系统，还应包括换能、调制、发射等各种变换处理②上述模型只针对一对一单向通信系统。还有一对多单向系统（广播），一对一双向系统（电话），多对多双向系统（会议电视）等2．通信系统模型(续)8•1948年，香农发表“通信的数学理论”，标志着信息论的正式诞生C.E.Shannon,AMathematicalTheoryofcommunication,BellSystemTech.J,vol.27,PP379-423,July1948在前人工作基础上，用概率统计方法研究通信系统揭示：通信系统传递的对象——信息提出：信息熵、信息量指出：通信系统的中心问题——噪声背景下如何有效、可靠地传递信息实现的主要方法——编码•提出了无失真信源编码定理、信道编码定理1.2编码理论的发展1．无失真信源编码9•提出了无失真信源编码定理、信道编码定理给出了编码的性能极限提供了最佳通信系统的理论依据从数学观点看——都是最优编码的存在性定理从工程观点看，信道编码定理不是结构性的无失真信源编码定理是结构性的——码的平均长度～信源统计特性相匹配1．无失真信源编码(续)10•无失真信源编码的方法1948年，香农提出香农编码1952年，费诺(Fano)提出费诺编码1952年，霍夫曼(D．A．Huffman)提出霍夫曼编码，并证明它是最佳码——有限长度的分组码中，平均码长最短1982年，里斯桑内(J．Rissanen)在多年研究的基础上，与兰登(G．G．Langdon)一起将算术码（非分组码）实用化1977年，齐弗(J．Ziv)和兰佩尔(A．Lempel)提出了LZ算法——一种通用编码方法1．无失真信源编码(续)11•1959年，香农发表“保真度准则下的离散信源编码定理”——Codingtheoremsforadiscretesourceatthefidelitycriterion提出——率失真函数和率失真信源编码定理贡献——信源编码的核心，压缩编码的理论基础•连续信源在编成代码后不可能无失真地复原——量化有失真——最佳量化问题（如A律13折线法）•对于有记忆信源，条件熵必不大于无条件熵——解除符号间的相关性可进一步压缩码率2．限失真信源编码12•解除相关性的编码预测编码——利用前几个符号来预测后一符号值，并对差值进行编码（如：DPCM）变换编码——样值空间的变换，如从时域变到频域某些情况下，可减弱相关性，取得良好压缩比现代压缩编码方法——小波变换、神经网络、模型基编码、分形编码等2．限失真信源编码(续)13•1950年•汉明(R．W．Hamming)•发表“检错码与纠错码”论文•开拓编码理论研究的第一篇论文3．信道编码14•1961年•香农•发表“双路通信信道”论文•开拓了多用户信息理论的研究→多用户信息论→网络信息论4．网络信息论15•保密学——一门研究通信安全和保护信息资源的既古老又年青的学科包括：密码编码学、密码分析学•密码编码学——信息安全技术的核心主要任务——对消息进行加密、认证•密码分析学——与密码编码学相反主要任务——破译密码、伪造认证•两个分支——既相互对立又相互依存5．保密编码16•1949年，香农发表论文“保密通信的信息理论”，首次用信息论观点对信息保密问题作了全面论述•1976年，迪弗(Diffe)和海尔曼(Hellman)发表“密码学的新方向”，提出了公开密钥密码体制后，保密通信问题才得到广泛研究•当今，信息的安全和保密问题更加突出和重要•人们把线性代数、初等数论、矩阵等引入保密问题研究，已形成了独树一帜的分支——密码学5．保密编码(续)171.3编码理论研究的内容和目的1．通信系统研究的目的•目的——寻找信息传输过程的共同规律，以提高信息传输可靠性、有效性、保密性和认证性以达到信息传输系统最优化(1)四性①有效性高——占用资源少(时间、空间、频率等)②可靠性高——信源消息尽可能准确地在收端再现③保密性——对所传送的消息进行隐蔽和保护④认证性——接收者能正确判断所接收的消息的正确性和完整性181．通信系统研究的目的(续)(2)研究某性能时的简化框图——在具体研究某一性能时可将某些功能框合并，以简化①有效性研究——把保密编码、信道编码并入信道信源编码信源译码无噪广义信道信源信宿信道编码信源编码保密译码信道译码信源译码保密编码噪声信道信源信宿191．通信系统研究的目的(续)②可靠性研究——把信源编码、保密编码并入信源信道编码信道译码信道广义信源广义信宿信道编码信源编码保密译码信道译码信源译码保密编码噪声信道信源信宿201．通信系统研究的目的(续)③保密性、认证性研究——把信源编码并入信源，信道编码并入信道保密译码保密编码无噪广义信道广义信源广义信宿信道编码信源编码保密译码信道译码信源译码保密编码噪声信道信源信宿212．信源编码(1)目标——压缩信源码率•具体——减小平均码长(信源符号的平均比特数)(2)分类——①经典压缩编码—无失真、限失真信源编码②222．信源编码(续)(3)经典信源编码的两种基本途径①设法改变信源概率分布，使之尽可能不均匀再用最佳编码方法使平均码长逼近信源熵•压缩上界——信息熵[例]霍夫曼编码、算术编码、游程编码等②去除、减少信源序列的相关性，使之成为不相关、低相关信源[例]预测编码、变换编码、混合编码、矢量量化等232．信源编码(续)(4)现代压缩编码•经典压缩编码方法——依据了信源本身固有的统计特性，并利用了人类视觉系统的某些特性来进行压缩编码，但利用得还不够充分•现代压缩编码方法——突破了传统香农理论的框架，注重对感知特性的利用，使压缩率极大提高[例]小波变换、神经网络、模型基编码、分形编码等243．信道编码(1)目标——是提高信息传输的可靠性•干扰、噪声——使通信质量下降模拟信号——信噪比下降数字信号——误码率增大(2)方法——增大传输所需的信道资源(码率或带宽)•模拟信号——增大带宽，换取所需信噪比的减小•数字信号——增高码率（信息位后增设监督位）(3)理论基础——信道编码定理[内容]当信息率R低于信道容量C时，误码可接近零当信息率R高于信道容量C时，必有误码254．保密编码•1949年，香农发表论文“保密通信的信息理论”，首次用信息论观点对信息保密问题作了全面论述•1976年，迪弗(Diffe)和海尔曼(Hellman)发表“密码学的新方向”——一篇具有里程碑意义的文章，此后保密通信问题才得到广泛研究•1978年McEliece用纠错码构造第一个公钥密码体制•此后，有关密码学与纠错码相结合的研究得到了迅速发展，从而把两门原本无关的学科结合在一起•二码合一、三码合一——26•编码理论——一门新兴科学主要研究对象——信息主要研究内容——信息的运动规律和利用原理主要研究方法——信息科学方法论主要研究目标——扩大人的信息功能•基本理论——信息论、控制论和系统论•结论——随着科学发展和社会进步，人们将：揭示出客观世界和人类主观世界更多的内在规律创造出各种性能优异的信息获取系统、信息传输系统、信息控制系统、智能信息系统小结