信源编码定理

✍ dations ◷ 2025-04-04 11:15:04 #信息论

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

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

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

信源编码是从信息源的符号(串行)到码符号集(通常是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 满足

相关

  • 伞型束梗孢菌纲伞型束梗孢菌目(Agaricostilbales) Spiculostilbales伞型束梗孢菌纲(学名:Agaricostilbomycetes)是担子菌门柄锈菌亚门下的一个纲。该纲共包含2个目、3个科、10个属、47个种。.
  • 临床流行病学临床流行病学是将流行病学知识应用于临床实践。从70年代以来开始盛行,循证医学是临床流行病学应用的表现。与一般的流行病学一样,临床流行病学也分为描述型和分析型两类。
  • 剧情片剧情片(drama film)指以故事剧情为主题的电影,是其中一种片种。剧情片一般长度在30分钟或以上,以电影院作为发放对像。相对于其他片种如动作片或爱情片以动作或爱情带动故事的推
  • 三氢阳离子氢分子合质子、三氢阳离子或H3+,是一种由三个氢原子构成的阳离子。它是宇宙中最丰富的离子之一,因为星际空间温度和密度均很低,所以它在星际介质中能稳定存在。尽管星际介质中
  • 亚述语叙利亚语是中古阿拉姆语(属闪米特语族)的一种方言,在新月沃土的大部分地方都有分布。经典叙利亚语成为4-8世纪中东地区的书面语言,古典叙利亚语文学的作品就是以它为载体。现在
  • 瓦戈纳瓦戈纳县(Wagoner County, Oklahoma)是美国俄克拉荷马州东部的一个县。面积1,531平方公里。根据美国2010年人口普查,共有人口73085人。县治瓦戈纳(英语:Wagoner, Oklahoma)。成立
  • 科罗拉多急流科罗拉多急流(英语:Colorado Rapids)是美国职业足球大联盟球队。球队的主场是科罗拉多州商贸城 (科罗拉多州)的Dick's Sporting Goods Park。于在1997年的美国职业足球大联盟杯
  • 在宅医疗在宅医疗(英语:Home healthcare)源自日本,是为了配合高龄化社会 的长期照顾需要,发展出结合医疗与健康照护的全天候到宅医疗照顾服务,在日本已行之多年,成为日本政府制定的社区整体
  • 廖忠伟廖忠伟(1964年-2012年2月7日),中国小提琴演奏家、教育家。福建省龙岩市人。一级演奏员、福建省歌舞剧院交响乐团团长、乐团首席、独奏演员、福建省政协委员、中国小提琴学会理事
  • 波兰甜甜圈波兰甜甜圈(波兰语:Pączki)为波兰的传统油炸面食,与甜甜圈相似;是一种扁平的球形面团,里面装满果酱或其他甜馅,并且油炸。 在肥胖星期四(天主教圣灰星期三(Ash Wednesday)与大斋节(Len