信息论基础课件：信源编码

1、信源编码编码：改变信息的表示方式。物理编码：把物理输入信息变成符合信道传输要求的物理内容。数学编码：通过把信息集合内所有信息扩展，排列，组合，省 略等方式，改变信息集合的数学表示。数学编码的目的：数学上匹配信道，以更高的效率，正确，安 全的传输信息。 数学上匹配信道是基本的。更高的效率：信源编码。正确：信道编码。安全：加密编码。码的分类：1.定长码与变长码定长码固定码的长度变长码不固定定长码不如变长码实用2.奇异码与非奇异码非奇异码输入信息与编码一一对应奇异码不一一对应。3.唯一可译码把多个码字连在一起（码序列），译码的过程就是“断句”。唯一可译码：任意码序列只有一种不出现未定义码的分割方法。

2、100010=10,0,0,10/10,00,10/10,0,01,04.即时码和非即时码即时码：收到一个码后能立刻判定完整，并开始译码。非即时码：收到一个码后也不知道是否完整。码奇异码非分组码分组码非奇异码非唯一可译码非即时码 即时码唯一可译码分组码：把发码序列分成一段段的组，进行编码。非分组码：输入与编码不能一一对应，也写不成码表奇异码必然非唯一可译，非唯一可译必然非即时（非即时未必非唯一可译）逆否就是即时必然唯一可译，能判定是否完整当然唯一可译即时码的另一种数学描述：码树 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

3、1码树从一个点(树根)开始分裂成多个点(节点)，末端节点对应于输入信息，输入信息对应编码就是从树根开始沿最短路径到对应节点所有经过的(节点/树枝)码字顺序排列。码的长度就等于节数。满树每层都完全分裂定长码不满树非定长码由于路径不同，任意一个码都不是其他码的前缀(即时码的充要条件)，所以必然是即时码唯一可译码存在的充要条件克劳夫特不等式是即时码存在的充分必要条件：满足不等式的一定能用码树来描述，不满足的一定不能用码树。总路径数目是1，进制的码长次方表示了该码长(码树的层)一共有多少种编码可能(码树的路径)，每一个编码的倒数即它占据了该层几分之1的路径。满足不等式说明，路径没有被占满（或者刚好占满

4、）。因此总能画出码树。即必能画出至少一组即时码，唯一可译码存在。McMillan证明了克劳夫特不等式也是唯一可译码存在的充要条件。同时，即时码任意码字不能是其他码的前缀，所以一定能画出码树，同时说明路径没占满，不等式一定成立。唯一可译码只要存在一定有对应的码长分配相同的即时码形式。逆命题也成立无失真信源编码失真限制：平均失真为0。如果译码会产生错误，则可能失真，因此要无失真就需要唯一可译码。(非极限情况)信源编码的目的就在于提高传输效率。提高效率有两种等价的描述：1)单位码长携带的平均信息量最大。2)传输一个信源信息所需要的平均最大信息率最小。其实就是用平均码长最短的码信源熵信源最大熵编码最大熵0不存在无差错编码 唯一可译码不存在无差错编码存在但是只存在于极限唯一可译码存在存在唯一可译码不知道是否存在无差错码在这个范围内，给定差错率限制的有失真定长编码总可以通过扩展信源来实现定长编码定理：在这个范围内，给定差错率限制的有失真定长编码