信源编码定理

✍ dations ◷ 2025-04-03 12:35:48 #信息论

在信息论中,香农的信源编码定理(或无噪声编码定理)确立了数据压缩的限度,以及香农熵的操作意义。

信源编码定理表明(在极限情况下,随着独立同分布随机变量数据流的长度趋于无穷)不可能把数据压缩得码率(每个符号的比特的平均数)比信源的香农熵还小,又不丢失信息。但是有可能使码率任意接近香农熵,且损失的概率极小。

码符号的信源编码定理把码字的最小可能期望长度看作输入字(看作随机变量)的熵和目标编码表的大小的一个函数,给出了此函数的上界和下界。

信源编码是从信息源的符号(串行)到码符号集(通常是bit)的映射,使得信源符号可以从二进制比特(无损信源编码)或有一些失真(有损信源编码)中准确恢复。这是在数据压缩的概念。

在信息论中,信源编码定理非正式地陈述为:

N 个熵均为 () 的独立同分布的随机变量在 → ∞ 时,可以很小的信息损失风险压缩成多于 () bit;但相反地,若压缩到少于 () bit,则信息几乎一定会丢失。

Σ1, Σ2 表示两个有限编码表,并令 Σ∗
1 和 Σ∗
2 (分别)表示来自那些编码表的所有有限字的集合。

X 为从 Σ1 取值的随机变量,令    为从 Σ∗
1 到 Σ∗
2 的唯一可译码,其中 2| = 。令 S 表示字长   () 给出的随机变量。

如果    是对 X 拥有最小期望字长的最佳码,那么(Shannon 1948):

对于 1 ≤ ≤ 令 表示每个可能的 的字长。定义 q i = a s i / C {\displaystyle q_{i}=a^{-s_{i}}/C} 1 + ... + = 1。于是

其中第二行由吉布斯不等式推出,而第五行由克拉夫特不等式推出:

因此 log ≤ 0.

对第二个不等式我们可以令

于是

因此

并且

因此由克拉夫特不等式,存在一种有这些字长的无前缀编码。因此最小的 S 满足

相关

  • 毫升毫升是容量计量单位,符号为mL(为milliliter缩写,音/.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Co
  • 功能主义建筑在建筑中,功能主义(英语:functionalism)是指建筑应该仅根据其用途和功能进行设计的原则。按照此原则设计的建筑称为功能主义建筑。该原则在行业内是一个令人困惑且有争议的问题,
  • ɨ̞次闭央不圆唇元音(near-close central unrounded vowel、near-high central unrounded vowel)是一个用在某些口语上的元音。在国际音标中,这个音可以用数种方法来表现(见右表),但
  • 德意志奥地利德意志-奥地利共和国(德语:Republik Deutschösterreich oder Deutsch-Österreich)是第一次世界大战结束、奥匈帝国解体后,其境内说德语的人所短暂建立的政权。其德语名Deutsch
  • 观鸟观鸟,又称作赏鸟,是指在自然环境中利用望远镜,鸟类图鉴等设备在不影响野生鸟类正常生活的前提下观察和观赏鸟类的一种娱乐活动。鸟是目前存在于自然界中较容易为人类所接近的一
  • 多数意见书复数意见书(英语:Plurality opinion),又译为多数意见书,法律术语,源自英美习惯法,是法律意见书的一种,常见于上诉法庭(Appellate court)中。复数意见书出现于法庭内无法取得过半数共识
  • 獭灵猫属獭狸猫(Cynogale bennettii),又名獭灵猫,是栖息在马来半岛、苏门塔腊及婆罗洲森林、低地近河流及沼泽的麝猫。在越南北部亦有发现它们,不过只有一个标本。獭狸猫的口阔,脚有蹼及长
  • 冬眠 (电影)《冬眠》(土耳其语:Kış Uykusu),是一部努里·比格·锡兰执导的土耳其电影,入围2014年戛纳电影节主竞赛单元,并获得最高荣誉金棕榈奖和国际影评人协会奖,成为继1982年的《生之旅》
  • 莫里斯·迪吕弗莱莫里斯·迪吕弗莱(法语:Maurice Duruflé,1902年1月11日-1986年6月16日),法国作曲家,管风琴家。在巴黎师从图内米尔,成为出色的管风琴演奏者。1943年在巴黎音乐学院任和声学教授。19
  • 与媒体对抗 (网站)与媒体对抗为一台湾网站,简称媒抗。该网站成立之最初目的是因应八掌溪事件时台湾媒体的不当行为,而后内容则多针对台湾媒体乱象。主要内容本为踢爆台湾媒体的假新闻,后逐渐变成