信源编码定理

✍ dations ◷ 2025-04-26 12:20:27 #信息论

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

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

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

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

相关

  • 下目亚目(suborder)是生物分类法中的一级,一般是界于目和科之间,但有时亚目和科之间会再分下目(又译作次目)。亚目的拉丁文名称较无固定的字尾。下目(infra-order),又译作次目是生物分类
  • 珊瑚藻珊瑚藻,又名钙化藻,是一科红藻,即珊瑚藻科。它们的叶状体坚硬,原因是在细胞壁中含有石灰。珊瑚藻一般都呈粉红色,有些呈红色,有些则呈紫色、黄色、蓝色、白色或灰绿色。没有附着的
  • 智能手机智能手机(Smartphone)是一种可拨打移动电话和进行多功能移动计算的设备。有定制的移动操作系统,可浏览网页和播放多媒体文件,也可通过安装应用软件、游戏等程序来扩充功能。智能
  • 余嘉锡余嘉锡(1884年2月9日-1955年1月23日),字季豫,号狷庵,狷翁,湖南常德县(今常德鼎城区长茅岭乡)人。父余嵩庆是清光绪二年(1876年)进士。光绪十年正月十三日出生于河南商丘,少年勤学,十四岁
  • 唐·钱德尔唐·钱德尔(英语:Don Cheadle,全名小唐纳德·弗兰克·“唐”·钱德尔 Donald Frank "Don" Cheadle, Jr. /ˈtʃiːdəl/; 1964年11月29日-)是一名美国演员和制片人。
  • 爱的妇产科《爱的妇产科》(英文:OB·Gyns),前名《@妇产科》,是一部中国湖南卫视剧情类电视剧周播剧情类电视剧,也是该台第一部真正意义上自制的周末剧集,共2季。该剧第一季于2013年7月开始拍
  • 保罗·柯艾略保罗·柯艾略(葡萄牙语:Paulo Coelho de Souza,发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Co
  • 第八套广播体操音乐第八套广播体操音乐,是中华人民共和国第八套广播体操播放时的背景音乐。该音乐总共有3个版本,原版为交响乐版(张仲霖版本),第2版为电子琴版,第3版为电子琴模拟版。也可以称为模仿
  • 费利克斯·尤苏波夫费利克斯·费利克苏维奇·尤苏波夫亲王(英语:Knyaz),苏马罗科夫-埃尔斯顿伯爵(俄语:Князь Фéликс Фéликсович Юсýпов, Граф Сумароков-
  • 欢迎航空欢迎航空(Welcome Air)的官方名称是“欢迎航空有限公司”(Welcome Air Luftfahrt GmbH & Co KG)是一家奥地利的航空公司。欢迎航空已经暂停了所有剩余的计划航线和欧洲境内包机