1.2 信源编码问题

1.无失真信源编码

对于离散信源，当已知信源符号的概率分布时可以计算信源的熵，用它可以表示每个信源符号平均承载的信息量。信源编码定理表明必然存在一种编码方法，使得代码的平均长度可以任意接近但不能低于信源的熵，而且还阐明为了达到这一目标，应该使得概率与码长匹配。

从无失真信源编码定理出发，1948年香农在论文中提出并给出了一种简单的编码方法，即香农编码。1952年，R.M.Fano提出了费诺码。同年，D.A.Huffman提出了一种编码方法并证明了它是最佳码，称为霍夫曼码。霍夫曼码是有限长度的块码中最好的码，其代码总长度最短。但是，霍夫曼码在实际应用中存在一些块码和变长码所具有的缺点：首先，信源的概率分布必须精确地测量，如果略有变化，就需要更换码表；其次，对于二进制信源，常需要多个符号合起来编码才能取得好的效果。

针对霍夫曼码在实用中的局限，出现了一种称为算术码的非块码，它是从整个序列的概率匹配角度来进行编码的。这种概念也是由香农首先提出的，后经许多学者改进逐渐进入实用阶段。1968年前后，P.Elias发展了香农—费诺码，提出了算术编码的初步思想。1976年，J.J.Rissanen给出和发展了算术编码，1982年他和G.G.Langdon一起将算术编码系统化，省去了乘法运算，使其更为简单，从而易于实现。

如果离散信源符号的概率分布未知，或是对于不确知的信源进行有效编码时，上述方法就无能为力了，因此人们希望能有一种适用于各类概率特性信源的编码方法。通用编码就是在信源统计特性未知时可以进行编码且编码效率很高的一种码。1977年，A.Lempel和J.Ziv提出了一种语法解析码，称为LZ码。1978年，他们又提出了改进算法LZ77和LZ78。1984年，T.A.Welch以LZ编码中的LZ78算法为基础设计了一种实用的算法，称为LZW算法。LZW算法保留了LZ78算法的自适应性能，压缩效果大致相同，并且逻辑性更强，易于硬件实现，价格低廉，运算速度快，目前作为一种通用压缩方法广泛应用于二进制数据的压缩。

2.限失真信源编码

无失真信源编码只适用于离散信源，对输出模拟信号的连续信源并不适用。因为连续信源输出信号的每个样值所载荷的信息量是无限大的，所以用有限长度的信息序列进行编码时必然导致失真。不过，作为信宿的人或机器都存在一定的灵敏度和分辨力，超过灵敏度和分辨力所传送的信息是毫无价值的，也是完全没有必要的，故而当失真在某一限度以下时是不影响正常通信的。例如，语音信源当量化分层超过256级时人耳就很难分辨，所以没有必要在量化时超过256级。对图像信源亦是如此，人们看电影时，可以充分利用人眼的视觉暂留效应，当放映速度达24张/秒时，人眼就能将离散的照片在人脑内反映成连续画面，因此大大超过24张/秒的放映速度是没有意义的。

限失真信源编码的研究相对于信道编码和无失真信源编码落后约十年左右。1948年，香农的论文已体现了关于率失真函数的思想。1959年，他发表了《保真度准则下的离散信源编码定理》，首先提出了率失真函数及率失真信源编码定理。1971年，T.Berger的《信息率失真理论》是一本较全面的论述有关率失真理论的专著。率失真信源编码理论是信源编码的核心问题，是频带压缩、数据压缩的理论基础，直到今天它仍是信息论研究的课题。

连续信源的信号编成代码后就不能无失真地再恢复成原来的连续值，此时只能根据率失真理论进行限失真编码，因此限失真编码实际上就是最佳量化问题。最佳标量量化常不能达到率失真函数所规定的R（D）值，因此人们后来又提出了向量量化的概念，将多个信源符号合成一个向量并对它进行编码。从理论上讲，某些条件下用向量量化来编码可以达到上述的R（D）值，但在实现上还是非常困难的，有待进一步改进。1955年，P.Elias提出了预测编码方法，利用前几个符号来预测后一个符号的值，然后将预测值与实际值之差即预测误差作为待编码的符号，这样得到的符号间的相关性就大为减弱，从而可提高压缩比。另一种限失真信源编码方式是变换编码，该方法通过样值空间的变换，例如从时域变到频域，在某些情况下可以减弱符号间的相关性，从而取得良好的压缩比。