信源编码定理

✍ dations ◷ 2025-04-02 11:36:47 #信息论

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

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

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

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

相关

  • 磷壁酸磷壁酸(Teichoic acid)是革兰氏阳性菌细胞壁上的一种多糖,主要成分是由核糖醇或甘油残基经由磷酸二酯键相连而成的多聚物。可以分为壁磷壁酸和膜磷壁酸两种。细菌疾病 · 科莱
  • 良性肿瘤良性肿瘤(英语:benign tumor)是肿瘤的一种,通常区别于恶性肿瘤。良性肿瘤的生长速度缓慢,呈膨胀性生长,表面较光滑。由于良性瘤体在局部会不断增大(一般无全身症状),压迫周围的正常组
  • 阿斯旺阿斯旺(阿拉伯语:أسوان‎),埃及南部城市,阿斯旺省首府,位于尼罗河东岸,人口约20万,著名古城、旅游景点和贸易中心。阿斯旺是世界上最干燥的地方之一,自2006年5月13日以来,阿斯旺
  • 四大换局换局(韩语:환국),在朝鲜王朝即是“政局转换”的意思。1680年(朝鲜肃宗6年)发生庚申换局,南人党被逐出朝廷,西人党掌握朝政。1689年(粛宗15年)发生,册立元子问题引起,南人重掌朝廷。1694
  • 荷兰空间研究组织荷兰空间研究所(英语:Netherlands Institute for Space Research,简称SRON)是该国负责太空研究的专门机构,研究重点为天体物理学、地球科学和行星研究。SRON还对新型、更灵敏的X
  • 黑脚族黑脚联盟(英语:Blackfoot Confederacy),又名Niitsitapi或Siksikaitsitapi(ᖹᐟᒧᐧᒣᑯ,指“人”或“说黑脚语的人”),是北美四支美洲原住民组成的联盟。他们主要分布于加拿大西部,少
  • 大梁大梁城,位于今河南省开封市西北。战国时期魏国都城,魏惠王迁都至此。大梁为魏都凡一百三十八年,是其交通枢纽和商业中心。商鞅、苏秦、张仪、孙膑、庞涓、吴起等名人都曾在大梁
  • 卡尔臼炮卡尔臼炮(德语:Mörser Karl;Gerät 040/041),是二次世界大战纳粹德军所开发、使用的超重型自走炮。一次世界大战后,认为德国是不变的敌人与强敌的法国,在发现德国“施里芬计划”的
  • 吉米·杭特吉米·杭特(Jimmy Hunter、1879年3月6日-1962年12月4日)是一位联盟式橄榄球球员,曾经效力新西兰国家橄榄球全黑队。他参加1905年全黑队(1905 All Blacks),前往英国、法国和北美。
  • 雷丁大学文字设计及图像传播学系雷丁大学文字设计及图像传播学系(Department of Typography & Graphic Communication, University of Reading)是雷丁大学艺术及传意设计学院辖下的一所学系,最初为泰文浩(Micha