信源编码定理

✍ dations ◷ 2025-06-08 12:15:20 #信息论

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

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

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

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

相关

  • 归属动词归属动词(attributive verb)在语法上是指直接修饰名词,而不做谓语的动词。在英语、德语等一些语言中,归属动词会以分词或不定式等形式呈现,像例如英语的the walking man(意即“
  • 资产会计学上的资产(英文:Asset),指一企业透过交易或非交易事项所获得之经济资源,能以货币衡量,并预期未来能提供效益者。资产,就是能够为个人或企业带来收益的东西。在财务会计中,资产
  • 露薏丝·蕾娜路易丝·赖纳(英语:Luise Rainer,1910年1月12日-2014年12月29日)是出生在德国的美国电影演员,也是犹太人。1936年和1937年主演《歌舞大王齐格菲》《大地》连续荣获第9届、第10届奥
  • 铁岭铁岭市是中华人民共和国辽宁省下辖的地级市,位于辽宁省北部,松辽平原中段。地处东经123°27' ~ 125°06',北纬41°59' ~ 43°29' 之间。南与沈阳市、抚顺市毗邻,北与吉林省四平市
  • 干细胞技术干细胞技术包括了所有与干细胞相关的生物工程学技术,它包含了干细胞的生成及诱导演化所需技术的研究。这些技术,可以把各种干细胞透过不同的手段,使它们表现出不同的特性。例如
  • 美丽的美利坚《美丽的阿美利加》(英语:"America the Beautiful",或译《美丽的美利坚》、《美哉美国》)是美国一首很受欢迎的爱国歌曲,几乎与其国歌《星条旗》一样脍炙人口。歌词由任教于卫斯
  • 卡罗琳·贝尔托西卡罗琳·露丝·贝尔托西(英语:Carolyn Ruth Bertozzi;1966年10月10日-),美国化学家,美国国家科学院院士,美国国家发明家科学院(英语:National Academy of Inventors)院士,(美国国家科学
  • 胡键 (政治人物)胡键(?-?),字希准,直隶大名府长垣县(今河南长垣县)人,军籍,明朝政治人物。弘治五年(1492年)壬子科顺天乡试举人。弘治九年(1496年)丙辰科二甲第五十名进士。官至陕西布政使司参政。曾祖胡友
  • 卡济梅尔兹·塔多斯基卡济梅尔兹·塔多斯基(Kazimierz Jerzy Skrzypna-Twardowski,1866年10月20日 – 1938年2月11日)是一位波兰 哲学家、逻辑学家。1866年10月20日,卡济梅尔兹·塔多斯基出生在奥地
  • 亚太旅行协会亚太旅行协会(Pacific Asia Travel Association, PATA)是1952年于美国夏威夷创立的一个非营利组织,其宗旨为促进在亚太地区的观光事业发展,为亚太地区最重要的国际观光组织之一,