数字通信中的信源编码和信道编码.doc

数字通信中的信源编码和信道编码
摘要：如今社会已经步入信息时代，在各种信息技术中，信息的传输及通信起着支撑作用。而对于信息的传输，数字通信已经成为重要的手段。本论文根据当今现代通信技术的发展，对信源编码和信道编码进行了概述性的介绍.
关键词：数字通信；通信系统；信源编码；信道编码
Abstract：Now it is an information society. In the all of information technologies, transmission and communication of information take an important effect. For the transmission of information, Digital communication has been an important means. In this thesis we will present an overview of source coding and channel coding depending on the development of today’s communication technologies.
Key Words：digital communication; communication system; source coding; channel coding

1. 前言
通常所谓的“编码”包括信源编码和信道编码。编码是数字通信的必要手段。使用数字信号进行传输有许多优点, 如不易受噪声干扰, 容易进行各种复杂处理, 便于存贮, 易集成化等。编码的目的就是为了优化通信系统。一般通信系统的性能指标主要是有效性和可靠性。所谓优化，就是使这些指标达到最佳。除了经济性外，这些指标正是信息论研究的对象。按照不同的编码目的，编码可主要分为信源编码和信道编码。在本文中对此做一个简单的介绍。

2. 数字通信系统
通信的任务是由一整套技术设备和传输媒介所构成的总体——通信系统来完成的。电子通信根据信道上传输信号的种类可分为模拟通信和数字通信。最简单的数字通信系统模型由信源、信道和信宿三个基本部分组成。实际的数字通信系统模型要比简单的数字通信系统模型复杂得多。数字通信系统设备多种多样，综合各种数字通信系统，其构成如图2-l所示。

图2-1 数字通信系统模型
信源编码是以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。
信道，通俗地说是指以传输媒质为基础的信号通路。具体地说，信道是指由有线或无线电线路提供的信号通路。信道的作用是传输信号，它提供一段频带让信号通过，同时又给信号加以限制和损害。
信道编码是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率或带宽。与信源编码正好相反。在计算机科学领域，信道编码（channel code）被广泛用作表示编码错误监测和纠正的术语，有时候也可以在通信和存储领域用作表示数字调制方式。信道编码用来在数据传输的时候保护数据，还可以在出现错误的时候来恢复数据。

3. 信源编码
一般情况下，信源编码可分为离散信源编码、连续信源编码和相关信源编码。离散信源编码可做到无失真编码；而连续信源编码则只能做到限失真编码。
3.1 信源编码的一般模型

图3-1
信源编码的一般模型如图3-1所示。如果将编码器看作是一个网络，则它有2个输入和1个输出，分别是消息集合X、信道基本符号集合A和代码集合C。
设消息集合共有N个元素，信道基本符号共有2种，代码组集合的元素个数为N，则
X={x1，x2，…，xN }
A={0，1 }
C={c1，c2，…，cN }
由信源编码器的数学模型可将信源编码器的作用归纳为
(1)用信道的基本符号按照规定的编码方法把信源发出的消息变换成相应的代码组；
(2)建立消息集合X与代码组集合C之间的一一对应关系。
通常称具有上述映射规则的信源编码器为正规编码器，编出来的码称为非奇异码。
由于正规编码器一一对应的规则确保了编码过程不会造成信息量的损失，故等效信源的熵必定与初始信源的熵相等。
3.2 最佳编码
通常称具有最短的代码组平均长度或编码效率接近于1的信源编码为最佳信源编码，亦简称为最佳编码。最佳编码的目的是提高信道传输消息的有效性。
最佳编码的实质：减小每个符号所占用的时间长度，即让每个码元所携带的信息量最大。
最佳编码的原则：①把信源符号集合中出现概率大的符号编成长度较短的代码组，而把出现概率小的符号编成长度较长的代码组；②信源编码器输出的代码组为单义可译码组，即序列中不必使用间隔就能把序列逐个分成代码组（因为间隔不携带信息量，使用了间隔自然降低了编码效率）
3.3 常见信源编码
3.3.1 香农编码
在信源编码方面，1951年香农证明，当信源输出有冗余的消息时可通过编码改变信源的输出，使信息传输速率接近信道容量。1948年香农就提出能使信源与信道匹配的香农编码。香农编码编码步骤如下：
(1) 将符号序列ai i=1,2,…,Nn按概率降序排列;
(2) 确定第i个码字的码长 i=1,2,…,Nn ；
(3) 令P(a0)=0，计算第i-1个符号序列的累加概率
i= i=1,2,…,Nn；
(4) 将Pa(ai)用二进制表示，取小数点后li位作为符号序列ai的码字ci i=1,2,…,Nn；
香农编码方法特点：由于bi总是进一取整，香农编码方法不一定是最佳的；由于第一个消息符号的累加概率总是为0，故它对应的码字总是0、00、000、0…0的式样；码字集合是唯一的，且为即时码；先有码长再有码字；对于一些信源，编码效率不高，多余度稍大，因此其实用性受到较大限制。
3.3.2 费诺编码
费诺编码是一种基于一组符号及及其或然率（估量或测量所得），从而构建前缀码的技术。在理想意义上， 它与哈夫曼编码一样，并未实现码词（code word）长度的最低预期。然而，与哈夫曼编码不同的是，它确保了所有的码词长度在一个理想的理论范围之内。这项技术是香农于1948年，在他介绍信息理论的文章“通信数学理论”中被提出的。这个方法归功于范诺，他在不久以后以技术报告发布了它。费诺编码不应该与香农编码混淆，后者的编码方法用于证明Shannon's noiseless coding theorem，或与Shannon–Fano–Elias coding（又被称作Elias coding）一起，被看做算术编码的先驱。
费诺编码也是一种常见的信源编码方法。其步骤：
(1) 将信源消息符号按其出现的概率大小依次排列，即p(x1) ³ p(x2) ³ … p(xn )；
(2) 将依次排列的信源符号按概率值分为两大组，使两个组的概率之和接近于相同，并对各组赋予一个二进制码元“0”和“1”；
(3) 将每一大组的信源符号进一步再分成两个组，使分解后的两个组的概率之和接近于相同，并又赋予两个组一个二进制符号“0”和“1”；
(4) 如此重复，直至每个组只剩下一个信源符号为止；
信源符号所对应的码字即为费诺编码。
费诺编码特点为：概率大，则分解的次数小；概率小，则分解的次数多。这符合最佳编码原则。码字集合是唯一的。分解完了，码字出来了，码长也有了。因此，费诺编码方法又称为子集分解法。
3.3.3 赫夫曼编码
香农编码算法并非总能得到最优编码。1952年, David A. Huffman提出了一个不同的算法，这个算法可以为任何的可能性提供出一个理想的树。香农编码是从树的根节点到叶子节点所进行的的编码，赫夫曼编码算法却是从相反的方向，即从叶子节点到根节点的方向编码的。编码步骤如下：
(1) 将符号序列ai i=1,2,…,Nn按概率降序排列；
(2) 为概率最小的两个符号序列各自分配一个二进制码元；
(3) 将概率最小的两个符号序列合并成一个新的符号序列，用两者概率之和作为新符号序列的概率；
重复（1）（2）（3）步骤，直到合并出一个以1为概率的新符号序列。分配给符号序列ai的全部码元作为该符号序列的码字ci i=1,2,…,Nn。
赫夫曼码的特点：编码过程中先确定码字，后确定码长；用局部累加概率代替累加概率，多次重新排列合并累加的过程是优化过程；每次合并伴之分配码元保证大概率符号序列编为短码，小概率符号序列编为长码；不具有唯一性，但不同赫夫曼码的编码效率相同；码率不超过熵率1/n个比特，n越大码率越接近熵率。
尽管对同一信源存在着多种结果的赫夫曼编码，但它们的平均码长几乎都是相等的，因为每一种路径选择都是使用最小概率相加的方法，其实质都是遵循最佳编码的原则，因此赫夫曼编码是最佳编码。赫夫曼编码是一种最佳编码，实现也不困难，因此到目前为止它仍是应用最为广泛无失真信源编码之一。
3.3.4 通用编码
对于统计特性已知的平稳信源，有Huffman码和算术码等高效编码方法。但是，它们存在以下共同问题：①在编码时必须知道信源的概率分布，这在许多情况下是不可能的；②它们对无记忆信源较为合适，而实际应用中的信源一般都具有记忆性。因此如何利用信源的记忆性提高它的压缩率是信源编码所必需考虑的问题。因而在此简单介绍一下通用编码。通用编码是指在信源概率分布不知时，对其编码并使编码效率很高的一种码。他的基本原理是利用出现数据序列前后的相关性进行压缩。下面简单介绍一下通用码中的一种LZ码：
1965年苏联数学家Kolmogolov提出利用信源序列的结构特性来编码。而两位以色列研究者J.Ziv和A.Lempel独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的通用压缩算法。将这些算法统称为LZ系列算法。LZ码的基本算法：
(1) 将长度不同的符号串编成一个个新的短语(单词)，形成短语词典的索引表；
(2) 它是一种分段编码，其短语词典是由前面已见到的文本分段来定义的.
LZ码的编码步骤为：
(1) 取第一个符号x作为第一段（单词），记为（0，x）；
(2) 从第二个符号y起，分段时先查看是否与前面的短语相同（匹配）：若没有匹配的，记为（0，y）；若有匹配的符号，就找从该符号开始与之匹配的最大长度L，并使得匹配开始的距离ρ最近，记为（1，L，ρ）；

4. 信道编码
4.1 信道编码的基本思想和基本方式
经过信源编码后并不能将信号直接送到传输通道发送出去, 因为数字信号在传输中受到衰减、杂波、干扰等所造成的质量劣化是突变性的(模拟信号质量的劣化是渐变的), 也就是说,数字信号在衰减、杂波或干扰没有低于某一门限时, 只要接收设备能判别出0码和1码, 信号质量就不会受到大的影响, 而一旦超过此门限, 接收设备判别不出0码和1码, 信号就会丢失。因此, 在数字信号传输中最重要的是防止误码, 也就是要尽量降低误码率。
1949年香农在《有噪声时的通信》一文中提出了信道容量的概念和信道编码定理，为信道编码奠定了理论基础。无噪信道编码定理（又称香农第一定理）指出，码字的平均长度只能大于或等于信源的熵。有噪信道编码定理（又称香农第二定理）则是编码存在定理。它指出只要信息传输速率小于信道容量，就存在一类编码，使信息传输的错误概率可以任意小。随着计算技术和数字通信的发展，纠错编码和密码学得到迅速的发展。信道编码的基本思想是：在发端被传输的信息序列上附加一些多余的检验码元，这些监督码元与信息码元间以某种特定的规则相互关联。接收端按照既定的规则检验信息码元与监督码元间的关系，一但传输出错，则两者间的关系将会受到破坏，从而可以发现错误，乃至纠正错误。
信道编码的基本方式是：前向纠错（FEC）、检错重传（ARQ）、混合差错控制（HEC）和信息反馈（IRQ）。
4.2 常用的信道编码
4.2.1 线性分组码
在分组码中，编码后的码元序列每n位为一组，其中k是信息码元，rr=n-k）个是附加的监督码元。如果信息元与监督码元之间呈线性关系，则为线性分组码。奇偶校验码和汉明码是典型的线性分组码。循环码是线性分组码，既可纠错又可检错。特点是任一码组的每一次循环移位得到的是码中的另一码组。BCH码是一类纠正多个随机错误的循环码。线性分组码的简单编码过程如下：
（1）构造秩为m的m×n校验矩阵H。Hri=si. 其中ri为第i个接收码字，以n列向量表示。si为第i个接收码字的误码标志，以m列向量表示。。使校验矩阵H满足，当ri等于ci时，Hri=Hci=si=0;当ri不等于ci时，Hri=si!=0；
（2）构造k×n生成矩阵G使校验矩阵H与生成矩阵G之间满足HGT=0；
（3）编码ci=GTxi，其中xi为第i个码字的消息，以k列向量表示。
4.2.2 卷积码
卷积码是另一类信道编码，它也是把k位信息编成n（n大于等于k）位，但k和n都很小，适于串行传输。特点是编码后的n个码元不仅与当前段的k位信息有关，而且与前N-1段的信息有关，编码过程中相互关联的码元有Nn个。纠错能力随N的增加而增加，而差错率随N的增加而指数下降。编码过程可以看成是输入信息序列与由移位寄存器和模2加连接所决定的的另一序列的卷积，因此称为卷积没码。N称为约束长度，m=N-1称为编码存储。卷积编码其特点是除能纠正本组的误码外, 也纠正其它组的误码, 卷积编码可以采用不同的比率, 在DVB标准中, 规定5种比率(即1/2、2/3、3/4、5/6、7/8)。

5.结束语
信息论理论的建立，提出了信息、信息熵的概念，接着人们提出了编码定理和编码方法，但至今尚不完善。近几年来，第三代移动通信系统的热衷探索，促进了各种数字信号处理技术发展，编码技术也在不断发展中。本文只是就几种经典的信源编码与信道编码技术做了简单的介绍了。随着通信技术的发展，编码技术也将越来越接近极限值。

6.参考资料
[1] 信息论基础. (美) Thomas M.Cover Joy A.Thomas 著 阮吉寿 张华译.
[2] 通信信息系统的构成及发展. 江沩. 现代通信，2000年第4期，33-34.
[3] 通信原理. 樊昌信等. 国防工业出版社，2003.
[4] MATLAB应用于数字通信系统调制解调技术的仿真设计研究. 张懿. 武汉理工大学.
[5] 信源编码与信道编码. 池秀清. 科技情报开发与经济. 2001年第11卷第6期，71-72.