有噪信道编码定理(又称香农第二定理)是编码存在定理。它指出只要
信息传输速率小于
信道容量,就存在一类编码,使信息传输的
错误概率可以任意小。随着计算技术和数字通信的发展,
纠错编码和
密码学得到迅速的发展。
在
信源编码方面,1951年
香农证明,当
信源输出有冗余的消息时可通过编码改变信源的输出,使
信息传输速率接近
信道容量。1948年香农就提出能使信源与信道匹配的香农编码。1949年美国麻省理工学院的R.M.费诺提出
费诺编码。1951年美国电信工程师D.A.
霍夫曼提出更有效的霍夫曼编码。此后又出现了
传真编码、
图像编码和话音编码,对
数据压缩进行了深入的研究,解决了数字通信中提出的许多实际问题。
在
纠错编码方面,1948年香农就提出一位
纠错码(码
字长=7,信息
码元数=4)。1949年出现三位纠错的
格雷码(码字长=23,信息码元数=12)。1950年美国数学家R.W.汉明发表论文《检错码和纠错码》,提出著名的
汉明码,对纠错编码产生了重要的影响。1955年出现
卷积码。卷积码至今仍有很广泛的应用。1957年引入
循环码。循环码构造简单,便于应用代数理论进行设计,也容易实现。1959年出现能纠正突发错误的哈格伯尔格码和
费尔码。1959年美国的R.C.博斯和D.K.雷·乔达利与法国的A.奥昆冈几乎同时独立地发表一种著名的循环码,后来称为
BCH码(即Bose-Chaudhuri-Hocquenghem码)。1965年提出序贯
译码序贯译码已用于
空间通信1967年A.J.
维特比提出最大
似然卷积译码,称为维特比译码1978年出现矢量编码法。矢量编码法是一种高效率的编码技术。1980年用数论方法实现里德-所罗门码(Reed-Solomon码),简称RS码。它实际上是多进制的BCH码。这种
纠错编码技术能使编码器集成电路的元件数减少一个
数量级。它已在
卫星通信中得到了广泛的应用。RS码和
卷积码结合而构造的级连码,可用于深空通信。
在密码学方面,1949年
香农发表
《保密系统的通信理论》,通常它被认为是密码学的先驱性著作。1976年狄菲和赫尔曼首次提出
公开密钥体制,为密码学的研究开辟了新的方向。
超大规模集成电路和高速计算机的应用,促进了保密
编码理论的发展,同时也给
保密通信的安全性带来很大的威胁。70年代以来把计算机复杂性理论引入密码学,出现了所谓P类、NP类和NP完全类问题。
算法的复杂性函数呈指数型增长,因此密钥空间扩大,使密码的分析和搜索面临严重的挑战。密码学开始向纵深方向发展。
信源编码广义的信源编码包括
模数转换(即把
模拟量变换成二进制的数字量)和
数据压缩(即对这些
数字量进行编码来降低数码率)两个方面。信源编码的主要任务是压缩数据。它有四种基本方法:、
这种方法是根据编码对象的出现概率(
概率分布),分别给予不同长短的代码,出现概率越大,所给代码长度越短。这里所谓匹配就是指代码长度与概率分布相匹配。莫尔斯码是一种匹配编码。匹配编码还常采用去相关性的方法进一步压缩数据。
这种方法是先对信号进行变换,从一种信号空间变换成另一种信号空间,然后针对变换后的信号进行编码。
变换编码在话音和
图像编码中有广泛的应用。目前常用的变换编码有
预测编码和函数编码两类。预测编码是根据信号的一些已知情况来预测信号即将发生的变化。它不传送信号的采样值,而传送信号的采样值与预测值之差。预测编码用在数字电话和数字电视中。函数变换最常用的是
快速傅里叶变换(FFT)、余弦变换、
沃尔什变换、
哈尔变换和
阿达马变换等。通过变换可得到信号的频谱特性,因而可根据频谱特点来压缩数码。
这种方法主要用于有标准形状的文字、符号和数据的编码。但话音也可以进行识别编码。识别编码的作用不仅限于压缩数据,它在模式识别中也有广泛的应用。常用的识别方法有关联识别和逻辑识别等方法。识别编码可大大压缩数据。例如,用话音识别的方法传输话音,平均数
码率小于100比特/秒。而用Δ调制话音的方法传输话音,数码率达38400比特/秒。两者相差约400倍。但识别编码在恢复时是根据一个代码恢复一个标准声音,只能用于不必知道发话人是谁的特殊电话和问答装置。识别编码用于文字传输时,恢复出来的都是印刷体符号,只能用于普通电报。