信息论

概念

• Berry悖论 — Berry 悖论（1906）是"最小的不能用二十个英文单词定义的正整数"——这个描述本身只用了不到二十个词。Chaitin 将其形式化为 安德烈·柯尔莫哥洛</li> <li>[[Chaitin常数 — Chaitin 常数 Ω = Σ 2^{-|p|}（对所有停机程序求和）是"随机程序停机的概率"，一个不可计算的超越数，其二进制展开的每一位都是算法随机的，包含
• Hamming界 — Hamming 界（也称球填充界）是纠错码的理论上界：在 n 位空间中，码字数 2ᵏ 与纠错能力 t 满足 2ᵏ · Σ C(n,i) ≤ 2ⁿ，达到此界的编码
• Hamming码 — Hamming 码是 Richard Hamming (1950) 发明的第一个实用纠错编码方案，用 7 位传输 4 位信息（码率 4/7 ≈ 57%）
• Hamming距离 — Hamming 距离是两个等长字符串在相同位置上不同字符（或比特）的数目，是编码理论、生物信息学和机器学习中的基本度量。
• Hartley信息量 — Hartley 信息量是 R. V. L. Hartley (1928) 提出的信息度量公式：H = n · log s，表示在 s 个
• KL散度 — KL 散度（Kullback-Leibler Divergence）度量两个概率分布之间的差异：D_KL(P||Q) = Σ P(x) log(P(x)/Q(x
• Kraft不等式 — Kraft 不等式指出前缀码的码字长度 l₁, ..., lₙ 必须满足 Σ 2^(-lᵢ) ≤ 1，McMillan (1956) 将其推广到所有唯一
• Shannon-Hartley公式 — Shannon-Hartley 公式是 Shannon (1949) 给出的连续信道容量公式：C = W log₂(1 + S/N)，精确量化了带宽 W
• 互信息 — 互信息（Mutual Information）度量两个随机变量共享的信息量：I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)，是</li> <li>[[交叉熵 — 交叉熵 H(P,Q) = -Σ P(x) log Q(x) 度量用基于分布 Q 设计的编码来编码来自分布 P 的数据时的平均编码长度，是机器学习分类任务的标准损
• 信噪比 — 信噪比（Signal-to-Noise Ratio, SNR）是信号平均功率与噪声平均功率的比值（S/N），是衡量通信信道质量的核心参数，直接决定[[信道容量]
• 信息与语义分离 — 信息与语义分离是 Hartley (1928) 提出的认识论原则：信息度量必须与消息的"意义"分离，选择完全客观的标准——信息量取决于发送者在多少个可能的消息中
• 信息几何 — 信息几何（Information Geometry）将概率分布族视为黎曼流形，其度量张量由 Fisher 信息矩阵给出，KL 散度在局部近似为 Fish
• 信息熵 — 信息熵（Information Entropy）是 Shannon (1948) 定义的离散随机变量不确定性的度量：H(X) = -Σ p(xᵢ) log₂ p
• 信息论 — 信息论（Information Theory）是研究信息的量化、存储、传输和处理的数学理论，由 Shannon (1948) 正式建立，其思想源头可追溯至 Ha
• 信源编码定理 — 信源编码定理（Source Coding Theorem）是 Shannon (1948) 的第一定理：一个信源产生的消息序列不可能被无损压缩到低于其熵率 H
• 信道容量 — 信道容量（Channel Capacity）是 Shannon (1948) 定义的通信信道可靠传输信息的最大速率：C = max I(X;Y)，是[[信息论]
• 信道编码定理 — 信道编码定理（Channel Coding Theorem）是 Shannon (1948) 的第二定理：对于传输速率 R < 信道容量 C，存在编码方
• 典型序列 — 典型序列（Typical Sequence）是 Shannon 信源编码定理证明中的核心概念：当消息足够长时，绝大多数实际产生的消息都集中在一个远小于所
• 前缀复杂性 — 前缀 Kolmogorov 复杂性 K_prefix(x) 要求合法程序集构成前缀码，修复了原始 安德烈·柯尔莫哥洛夫</li> <li>[[前缀码 — 前缀码（Prefix Code）是一组二进制码字，其中没有任何码字是另一个码字的前缀，保证编码可以即时解码（不需要回溯），是数据压缩的基础编码类型。
• 归一化压缩距离 — 归一化压缩距离（NCD）是基于 Kolmogorov 复杂性的近似距离度量，用于无参数聚类和分类，是算法信息论在数据挖掘中
• 微分熵 — 微分熵（Differential Entropy）是 Shannon (1949) 引入的连续随机变量的信息度量，是离散信息熵在连续域的推广，但缺少离散
• 数据处理不等式 — 数据处理不等式（Data Processing Inequality）指出：对数据进行任何确定性或随机变换不会增加关于原始变量的信息——只可能减少或保持。
• 最小描述长度原理 — 最小描述长度（MDL）原理是 Rissanen (1978) 提出的模型选择准则：最佳模型是使"模型描述长度 + 数据在模型下的编码长度"最小的那个，是 安</li> <li>[[有损压缩 — 有损压缩（Lossy Compression）是允许重构结果与原始数据存在一定失真的数据压缩方法，通过舍弃"不重要"的信息来显著降低比特率，是多媒体技术的核心。
• 柯尔莫哥洛夫复杂性 — 柯尔莫哥洛夫复杂性 K(x) 是产生字符串 x 的最短程序长度（以 bit 计），度量了单个对象的内在信息含量，是算法信息论的核心概念。
• 率失真函数 — 率失真函数 R(D) 是在平均失真不超过 D 的所有条件分布 p(y|x) 中，使互信息 I(X;Y) 最小的值，刻画了比特率与失真之间的最优权衡曲线。
• 率失真理论 — 率失真理论（Rate Distortion Theory）是 Shannon (1959) 建立的有损压缩数学理论，回答"给定可接受的失真水平 D，最少
• 球填充问题 — 球填充问题（Sphere Packing Problem）在信息论中是指：在高维信号空间内，最多能放置多少个互不重叠的"噪声球"，从而确定[[信道容量]
• 算术编码 — 算术编码（Arithmetic Coding，1976）是一种数据压缩方法，不受"整数码长"约束，可以将整个消息编码为一个 [0,1) 区间内的实数，压缩率逼近
• 算法信息论 — 算法信息论（Algorithmic Information Theory, AIT）将信息论与计算理论结合，用程序长度（而非概率
• 算法随机性 — 算法随机性（Algorithmic Randomness）将"随机性"从概率分布的集合性质转化为单个对象的内禀性质：一个字符串如果无法被显著压缩（K(x) ≈
• 纠错编码 — 纠错编码（Error Correcting Code, ECC）是通过在数据中添加冗余比特，使得接收方能够检测并自动纠正传输或存储中的比特错误的编码技术。
• 通信系统模型 — 通信系统模型是 Shannon (1948) 提出的五组件抽象框架：信源 → 编码器 → 信道（含噪声）→ 解码器 → 信宿，同时涵盖电报、电话、无线电、人类语
• 采样定理 — 采样定理（Sampling Theorem）指出：一个频率不超过 W Hz 的连续信号，可以由每秒 2W 个等间隔采样值完全确定，并通过 sinc 插值精确重构

实体

• 克劳德·香农 — 克劳德·艾尔伍德·香农（Claude Elwood Shannon，1916–2001）是美国数学家和电子工程师，"信息论之父"，1948 年发表"A
• 大卫·哈夫曼 — 大卫·阿尔伯特·哈夫曼（David Albert Huffman，1925–1999）是美国计算机科学家，1952 年在 MIT 攻读研究生期间发明了 Huff
• 奈奎斯特 — 哈里·奈奎斯特（Harry Nyquist，1889–1976）是瑞典裔美国电子工程师和物理学家，贝尔实验室研究员，1924 年分析电报传输速度的物理限
• 所罗门·库尔巴克 — 所罗门·库尔巴克（Solomon Kullback，1907–1994）是美国数学家和统计学家，二战期间从事密码分析工作，1951 年与 Richard Lei
• 拉尔夫·哈特莱 — 拉尔夫·维顿·莱昂·哈特莱（Ralph Vinton Lyon Hartley，1888–1970）是美国电子工程师和信息论先驱，1928 年发表论文"
• 格雷戈里·柴廷 — 格雷戈里·柴廷（Gregory J. Chaitin，1947—）是阿根廷裔美国计算机科学家和数学家，算法信息论的三大独立发源之一，1966 年独立发现
• 沃伦·韦弗 — 沃伦·韦弗（Warren Weaver，1894–1978）是美国数学家和科学管理者，1949 年为 Shannon 的 1948 年论文撰写了非技术性导读，使
• 理查德·哈明 — 理查德·韦斯利·哈明（Richard Wesley Hamming，1915–1998）是美国数学家和计算机科学家，贝尔实验室研究员，1950 年发明
• 理查德·莱布勒 — 理查德·莱布勒（Richard A. Leibler，1914–2003）是美国统计学家，二战期间从事密码分析工作，1951 年与 Sol</li> <li>[[贝尔实验室 — 贝尔实验室（Bell Telephone Laboratories）是美国 AT&T 公司的研究机构，20 世纪最重要的工业研究实验室之一，信息论的诞生
• 雷·所罗门诺夫 — 雷·J·所罗门诺夫（Ray J. Solomonoff，1926–2009）是美国数学家和计算机科学家，算法信息论的三大独立发源之一，1964 年发表"