信源编码定理

✍ dations ◷ 2025-10-16 17:45:25 #信息论

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

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

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

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

相关

  • 高铁血红蛋白高铁血红蛋白(也称变性血红素,英语:Methemoglobin或英语:Methaemoglobin)是氧携带金属蛋白血红蛋白的一种形式,这种血红蛋白中血红素基团里的铁离子呈正三价状态(高铁状态,Fe3+),并不
  • 苔藓学苔藓学(英语:Bryology, 来源于希腊语 bryon,苔藓,地钱)是一个关注苔藓植物(苔藓,地钱门,和角苔门)科学研究的植物学分支。 苔藓学家是积极关注观察,记录,分类,或研究苔藓植物的人 。苔藓
  • 拉瓦锡安托万-洛朗·德·拉瓦锡(法语:Antoine-Laurent de Lavoisier,1743年8月26日-1794年5月8日),法国贵族,著名化学家、生物学家,被后世尊称为“近代化学之父”。他使化学从定性转为定量
  • 胶片胶片,是一种制成影像物料。现今广泛应用的胶片是将卤化银涂抹在聚乙酸酯片基上,此种胶片为软性,卷成整卷方便使用,所以又称胶卷,当有光线照射到卤化银上时,卤化银转变为黑色的银,经
  • 大陆集团德国马牌(又名大陆集团,德语:Continental AG,简称:Conti)是一间德国运输行业制造商。主要产品为轮胎、制动系统、车身稳定控制系统、发动机喷射系统、转速表以及其它汽车和运输零
  • 屯溪区屯溪区是中国安徽省黄山市下辖的一个区。东汉建安十三年(208年),吴主孙权在屯溪设犁阳县,属新都郡,为屯溪建制之始。晋改犁阳为黎阳。南朝宋大明八年(464年)撤黎阳县,并入海宁县(今
  • 克里斯蒂安·埃里克森克里斯蒂安·丹纳曼·埃里克森(丹麦语:Christian Dannemann Eriksen,1992年2月14日-),丹麦足球运动员,司职攻击中场,现效力意甲球队国际米兰。他先前在欧登塞效力并于2008年当选丹麦
  • 加德纳蛙加德纳蛙()是塞舌蛙科的一种小型青蛙,是塞舌尔群岛的特有种。加德纳蛙是世界上最小的青蛙之一,其最大长度也只有11毫米(0.4英寸),新出生的加德纳蛙体长仅有3毫米(0.1英寸),成年雄
  • 东思忠东思忠(?-1486年),字进伯,陕西西安府华州(今陕西渭南市华州区)人。明朝政治人物。成化二年(1466年)丙戌科进士,授刑部河南司主事,后升任员外郎、郎中。改任四川按察司副使、松潘兵备使,成
  • 龙三角龙三角(英语:Dragon's Triangle)又称日本龙三角、福尔摩沙三角(英语:Formosa Triangle)、恶魔海或魔鬼海(英语:Devil's Sea;日语:魔の海)。是位于西太平洋北回归线的一块三角形区域,与位