2.3 无失真信源编码定理
编码分为信源编码和信道编码，其中信源编码又分为无失真编码和限失真编码，无失真信源编码定理是离散信源编码的基础，而限失真信源编码定理是连续信源编码的基础。本节讨论无失真信源编码的相关概念。
通信的目的是信息通过信道进行传递，传递的过程有两个重要问题需要注意。一个是在不失真或者允许一定失真条件下，如何用尽可能少的符号来传递信息，提高信息的传输率，另一个是如何在信道受干扰的情况下增强信号抗干扰能力，提高传输可靠性并使信息传输率最大。
人们都希望将所有信息没有任何损失地传递到接收端，实现无失真通信，那么首先要对信源进行无差错编码。这里重点讨论离散信源的无失真编码定理。
对信源进行编码，就是设计一个编码器，将信源的原始符号按照一定的数学规则进行变换，生成适合信道传输的符号，通常称为码元（码序列）。
将离散信源输出信息定义为离散符号集，如下所示：
即，序列中每个符号xi属于符号序列Xl，多个Xl构成信源消息组。
那么信源编码就是将上面的输出转换成如下结果：
这种码元序列，通常称为码字，所有码字集合称为码。编码就是从信源符号到码元的映射，要想实现无失真信源编码，这种映射必须一一对应，就是每个信源消息可以编成一个码字，反之，每个码字只能翻译成一个固定消息。这种码称为唯一可译码。
在给消息分配码字的时候分配多少可以做到无失真译码？码字越多，所需要的信息率就越大，很明显，我们希望信息率越小越好，但是信息率小到多少能保证无失真呢？首先要给出关于码的定义。
（1）二元码
如果码符号集为X={0，1}，所得到的码字都是二元序列，称为二元码。
如果将信源通过二元信道进行传输，那么就需要将信源符号转换为由0和1组成的二元码序列，这也是数字图像处理最为常用的一种方法。
（2）等长码（定长码）
如果一组码中所有码字的长度都相等，称之为等长码。
（3）变长码
如果一组码中所有码字的长度都不相同，称之为变长码。
（4）非奇异码
如果一组码中所有码字都不相同，即所有信源符号映射到不同的码元序列，它们之间是一一对应的，那么称之为非奇异码。
（5）奇异码
如果一组码中有相同的码字，即所有信源符号映射到相同的码元序列，那么称之为奇异码。
（6）同价码
如果码符号集中每个码符号所占用的传输时间都相同，则所得到的码为同价码。一般来讲，二元码都是同价码。
（7）码的N次扩展码
假设某码C，它把信源S中的符号si转化成码C中的码字Wi，则码C的N次扩展码是所有N个码字组成的码字序列的集合。
（8）唯一可译码
如果码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，那么此码称为唯一可译码。否则就称为非唯一可译码。
可以看出，信源编码分为定长和变长两种方法。定长的码字长度K是固定的，对应的编码定理叫作定长信源编码定理，是寻找最小K值的编码方法。后者的K是变值，对应的编码定理叫作变长编码定理。
1.定长编码定理
一个熵为H（S）的离散无记忆信源，若对信源长为N的符号序列进行等长编码，假设码字为从r个字母的码符号集中选取l个码元组成，对于任意ε大于0，只要满足
当N无穷大时，则可以实现几乎无失真编码，反之，若
则不可能实现无失真编码，当N趋向无穷大时，译码错误率接近1。该公式的证明过程略，读者感兴趣可以参考相关书籍。
上式可以变换为
公式左边表示长为l的码符号所能载荷的最大信息量，而右边代表长为N的序列平均携带的信息量。因此，只要码字传输的信息量大于信源序列携带的信息量，就可以实现无失真编码。
上式还可以变换为
假设
，表示平均每个符号的信息量，称之为编码信息率。可见，只有编码信息率大于信源的熵，才能实现无失真编码。也就是说，信源熵其实就是一个临界值，当编码器输出信息率超过该临界值时，就能无失真编码，否则就无法不失真。
为了衡量编码效果，定义
称之为编码效率。
那么最佳编码效率为
该定理也说明，编码信息率大于单符号熵时，可以做到几乎无失真，前提是N必须足够大。可以证明，当方差D[I（x）]和ε均为定值时，只要信源序列长度N满足
即
译码差错率就一定小于任意正数δ。
接下来看一个示例。考虑一个如下的离散无记忆信源
如果采用等长二元编码，要求编码效率η=0.96，允许错误率δ≤10-5，那么N≥4.13×107，也就是说长度要达到4130万以上，技术实现非常困难，而且编码效率也不高。为了解决这个问题，就出现了变长编码。
变长编码允许把等长消息变成不等长的码序列，一般情况下把经常出现的消息编成短码，不经常出现的消息编成长码，从而使得平均码长最短，提高通信效率，但是这种方式会增加编译码设备的复杂度。
2.变长编码定理
设离散无记忆信源为
编码后码字
码长为
对唯一可译码来讲，信源符号与码字一一对应，因此
码的平均长度为
当信源给定时，信源的熵就是确定的，编码后平均每个码元携带的信息量也就是编码后的信息传输率为
如果传输一个码符号平均需要t秒，那么编码后每秒信息量为
可以看出
值越小，信息传输效率越高，如果有一个唯一可译码，它的平均码长小于其他唯一可译码的长度，则称此码为紧致码（最佳码），无失真信源编码的基本问题就是寻找紧致码。从而就得到如下定理，即无失真变长信源编码定理（香农第一定理）：
离散无记忆信源S的N次扩展信源SN，其熵为H（SN），并且编码器的码元符号集为A：{α1，…，αq}，对信源SN进行编码，总可以找到一种无失真编码方法，构成唯一可译码，使信源S中每个符号si所需要的平均码长满足
当N→∞时，得到
其中
式中，λi是αi对应的码字长度，
是无记忆扩展信源SN中每个符号αi的平均码长，那么
仍然是信源S中每一单个信源符号所需的平均码长。
和
两者都是每个信源符号所需的码符号的平均数，
表示为了得到这个平均值，不是对单个信源符号进行编码，而是对N个信源符号的序列进行编码。
这个定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，在译码或反变换时必然带来失真或差错，可见，信源的信息熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋近该极限值。
由
可以得到
就是编码后每个信源符号所携带的平均信息量。定义
那么香农第一定理就可以表述为：
·如果R′＞H（S），则存在唯一可译变长码。
·如果R′＜H（S），则不存在唯一可译变长码。
若从信道角度讲，信道的信息传输率为
由于
所以
当平均码长达到极限值时，编码后信道的信息传输率为
此时，信道的信息传输率等于无噪无损信道的信道容量C，编码效率最高，即信息传输率最高。因此无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的符号序列信源尽可能为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，从而使信息传输率R达到信道容量C，实现信源和信道理想的统计匹配。这是香农第一定理的另一层含义，因此无失真信源编码实质上就是无噪信道编码问题。
因此，无失真信源编码定理又称为无噪信道编码定理：若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错地以最大信息传输率C传输信息，若信息传输率R大于信道容量C，那么无差错信息传输是不可能的。