编码理论

[拼音]：bianma lilun

[外文]：coding theory

研究信息传输过程中信号编码规律的数学理论。编码理论与信息论、数理统计、概率论、随机过程、线性代数、近世代数、数论、有限几何和组合分析等学科有密切关系，已成为应用数学的一个分支。编码是指为了达到某种目的而对信号进行的一种变换。其逆变换称为译码或解码。根据编码的目的不同，编码理论有三个分支：

（1）信源编码。对信源输出的信号进行变换，包括连续信号的离散化，即将模拟信号通过采样和量化变成数字信号,以及对数据进行压缩,提高数字信号传输的有效性而进行的编码。

（2）信道编码。对信源编码器输出的信号进行再变换，包括区分通路、适应信道条件和提高通信可靠性而进行的编码。

（3）保密编码。对信道编码器输出的信号进行再变换，即为了使信息在传输过程中不易被人窃取而进行的编码。编码理论在数字化遥测遥控系统、电气通信、数字通信、图像通信、卫星通信、深空通信、计算技术、数据处理、图像处理、自动控制、人工智能和模式识别等方面都有广泛的应用。

历史背景

1843年美国著名画家S.F.B.莫尔斯精心设计出莫尔斯码，广泛应用在电报通信中。莫尔斯码使用三种不同的符号：点、划和间隔，可看做是顺序三进制码。根据编码理论可以证明，莫尔斯码与理论上可达到的极限只差15％。但是直到20世纪30～40年代才开始形成编码理论。1928年美国电信工程师H.奈奎斯特提出著名的采样定理，为连续信号离散化奠定了基础。1948年美国应用数学家C.E.香农在《通信中的数学理论》一文中提出信息熵的概念，为信源编码奠定了理论基础。1949年香农在《有噪声时的通信》一文中提出了信道容量的概念和信道编码定理，为信道编码奠定了理论基础。无噪信道编码定理（又称香农第一定理）指出，码字的平均长度只能大于或等于信源的熵。有噪信道编码定理（又称香农第二定理）则是编码存在定理。它指出只要信息传输速率小于信道容量，就存在一类编码，使信息传输的错误概率可以任意小。随着计算技术和数字通信的发展，纠错编码和密码学得到迅速的发展。

在信源编码方面，1951年香农证明，当信源输出有冗余的消息时可通过编码改变信源的输出，使信息传输速率接近信道容量。1948年香农就提出能使信源与信道匹配的香农编码。1949年美国麻省理工学院的R.M.费诺提出费诺编码。1951年美国电信工程师D.A.霍夫曼提出更有效的霍夫曼编码。此后又出现了传真编码、图像编码和话音编码，对数据压缩进行了深入的研究，解决了数字通信中提出的许多实际问题。

在纠错编码方面,1948年香农就提出一位纠错码(码字长n=7,信息码元数k=4)。1949年出现三位纠错的格雷码(码字长n=23，信息码元数k=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完全类问题。算法的复杂性函数呈指数型增长，因此密钥空间扩大，使密码的分析和搜索面临严重的挑战。密码学开始向纵深方向发展。

信源编码

广义的信源编码包括模数转换（即把模拟量变换成二进制的数字量）和数据压缩（即对这些数字量进行编码来降低数码率）两个方面。信源编码的主要任务是压缩数据。它有四种基本方法：

（1）匹配编码。这种方法是根据编码对象的出现概率（概率分布），分别给予不同长短的代码，出现概率越大，所给代码长度越短。这里所谓匹配就是指代码长度与概率分布相匹配。莫尔斯码是一种匹配编码。匹配编码还常采用去相关性的方法进一步压缩数据。

（2）变换编码。这种方法是先对信号进行变换，从一种信号空间变换成另一种信号空间，然后针对变换后的信号进行编码。变换编码在话音和图像编码中有广泛的应用。目前常用的变换编码有预测编码和函数编码两类。预测编码是根据信号的一些已知情况来预测信号即将发生的变化。它不传送信号的采样值，而传送信号的采样值与预测值之差。预测编码用在数字电话和数字电视中。函数变换最常用的是快速傅里叶变换 (FFT)、余弦变换、沃尔什变换、哈尔变换和阿达马变换等。通过变换可得到信号的频谱特性，因而可根据频谱特点来压缩数码。

（3）矢量编码。这种方法是将可能传输的消息分类按地址存储在接收端的电子计算机数据库中，发送端只发送数据库的地址，即可查出消息的内容，从而大大压缩发送的数据。

（4）识别编码。这种方法主要用于有标准形状的文字、符号和数据的编码。但话音也可以进行识别编码。识别编码的作用不仅限于压缩数据，它在模式识别中也有广泛的应用。常用的识别方法有关联识别和逻辑识别等方法。识别编码可大大压缩数据。例如，用话音识别的方法传输话音，平均数码率小于100比特／秒。而用Δ调制话音的方法传输话音,数码率达38400比特／秒。两者相差约400倍。但识别编码在恢复时是根据一个代码恢复一个标准声音，只能用于不必知道发话人是谁的特殊电话和问答装置。识别编码用于文字传输时，恢复出来的都是印刷体符号，只能用于普通电报。

信道编码

信道编码的主要任务是为了区分通路和增加通信的可靠性。以区分通路为主要目的的编码常采用正交码。以增加通信可靠性为主要目的的编码常采用纠错码。正交码也具有很强的抗干扰能力。在信道编码中也采用检错码。

信源编码器输出 k位码元一组的码。它们携带着信息，称为信息元。这样的信息元通过信道编码器后，变换成 n位码元一组的码字。信息元和码字是一一对应的。

正交码

码字与码字之间互相关系数为 0的码称为正交码，在信道编码时主要利用它的正交性去区分通路，但它本身也可以携带信息。最常用的正交码有伪随机码(如 m序列、L序列、巴克序列、M序列等)和沃尔什函数序列。若一个正交信号集的补集也被利用，则可用码组数将增加一倍,这样的正交码称为双正交码。里德-米勒码（Reed-Muller码）就是一种双正交码。正交码广泛用于通信、雷达、导航、遥控、遥测和保密通信等领域。

检错码

有发现错误能力的码称为检错码。常用的检错码有奇偶校验码和等重码。采用检错码的通信系统要有反馈通道，当发现收到的信号有错误时，通过反馈通道发出自动请求重发(ARQ)的信号。

纠错码

接收到错误的码字后能在译码时自动纠正错误的码称为纠错码。纠错码是一种重要的抗干扰码，可增加通信的可靠性。纠错码是利用码字中有规律的冗余度，即利用冗余度使码字的码元之间产生有规律的相关性，或使码字与码字之间产生有规律的相关性。通常把信息元中的码元数k与对应码字的码元数 n的比值R称为编码效率，即R=k/n，码字的冗余度为1-R。

纠错码有两类：分组码和卷积码。分组码常记作(n，k)码，其中n是一个码字的码元数（即码字长），k是信息码元数，n-k是监督码元数。在一个码字中,如果信息码元安排在前k位，监督码元安排在后n-k位，这种码称为组织码或系统码。如果分组码中任何两个 n比特的码字进行模2相加（即不进位的普通二进制加法，模2加法记号是嘰）可得到另一个码字，这种码称为群码。任何一致监督分组码都是群码。如果一个码字经过循环以后必然是另一个码字，这种码称为循环码。循环码是群码的一个重要子集。著名的BCH码是一种循环群码。能纠正突发错误的费尔码是一种分组循环码。汉明码也是一种群码。通常把两个码字之间不同码元的数目称为汉明距离。两两码字之间汉明距离的最小值称为最小汉明距离，它是汉明码检错纠错能力的重要测度。汉明码要纠正E个错误，它的最小汉明距离至少必须是2E+1；要发现最多E个错误，其最小汉明距离应为E+1。

如果特定的一致监督关系不是在一个码字中实现，而是在m个码字中实现,这种码称为卷积码。卷积码可用移位寄存器来实现，这种卷积编码器的输出可看作是输入信息码元序列与编码器响应函数的卷积。能纠正突发错误的哈格伯尔格码也是一种卷积码。在平稳高斯噪声干扰的信道上采用序贯译码方法的卷积码有很好的性能，能用于卫星通信和深空通信。

保密编码

为了防止窃译而进行的再编码称为保密编码。其目的是为了隐藏敏感的信息。它常采用替换或乱置或两者兼有的方法。一个密码体制通常包括两个基本部分：加（解）密算法和可以更换的控制算法的密钥。密码根据它的结构分为序列密码和分组密码两类。序列密码是算法在密钥控制下产生的一种随机序列，并逐位与明文混合而得到密文。其主要优点是不存在误码扩散，但对同步有较高的要求。它广泛用于通信系统中。分组密码是算法在密钥控制下对明文按组加密。这样产生的密文位一般与相应的明文组和密钥中的位有相互依赖性，因而能引起误码扩散。它多用于消息的确认和数字签名中。

密码学还研究通过破译来截获密文的方法。破译方法有确定性分析法和统计性分析法两类。确定性分析法是利用一个或几个未知量来表示所期望的未知量从而破译密文。统计分析法是利用存在于明文与密文或密钥之间的统计关系破译密文。

参考书目

Coding and Infomation Theory，Prentice-Hall