什么是霍夫曼编码？它为何能实现最优的前缀无歧义压缩？
What is Huffman coding, and why does it achieve optimal prefix-free compression?
霍夫曼编码按符号概率自底向上合并最小概率节点构建二叉树，高频符号得到短码、低频符号得到长码。所得码字是前缀码（任一码字不是他者前缀），且在所有前缀码中平均码长最短，达到熵给出的下界（取整后），因而是最优可变长编码。
Huffman coding builds a binary tree by repeatedly merging the two least-probable nodes, giving short codes to frequent symbols and long codes to rare ones. The resulting codewords form a prefix code (no codeword is a prefix of another) and, among all prefix-free codes, minimize average length, approaching the entropy lower bound (after rounding), thus optimal variable-length coding.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《信息论基础》Cover 与 Thomas
Elements of Information Theory by Cover and Thomas
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780471241959 (2006) · 核验依据 2 ISBN 9780665590955 (2002)
#霍夫曼 #前缀码 #压缩
柯尔莫哥洛夫复杂度是什么？
What is Kolmogorov complexity?
它是生成某字符串的最短程序长度，衡量其‘内在随机性’。无法被简短描述的对象（如随机序列）复杂度高；但它本身不可计算（没有通用算法能算出最短程序）。
It is the length of the shortest program that outputs a string, measuring its intrinsic randomness. Objects not briefly describable (like random sequences) have high complexity—but it is uncomputable in general.
难度 专业 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
Cover, T. M. & Thomas, J. A.《Elements of Information Theory》,Wiley
Cover, T. M. & Thomas, J. A., Elements of Information Theory, Wiley
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780471241959 (2006) · 核验依据 2 ISBN 9780665590955 (2002)
#复杂度 #随机性
信道容量定理（香农定理）的核心结论是什么？为何存在不可逾越的可靠传输速率上限？
What is the core conclusion of the channel capacity theorem (Shannon's theorem), and why is there an unsurpassable upper bound on reliable transmission rate?
香农定理给出有噪信道容量 $C=B\log_2(1+S/N)$，即在带宽 B 与信噪比 S/N 下可实现任意小错误概率的最大速率。低于 C 时可编码逼近零误码，高于 C 则无论怎样编码都必有误码——这是通信的理论极限。
Shannon's theorem gives the noisy-channel capacity $C=B\log_2(1+S/N)$, the maximum rate with arbitrarily small error for bandwidth B and signal-to-noise ratio S/N. Below C one can encode to near-zero error; above C no coding can avoid errors, setting a fundamental communication limit.
难度 专业 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《信息论基础》Cover 与 Thomas
Elements of Information Theory by Cover and Thomas
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780471241959 (2006) · 核验依据 2 ISBN 9780665590955 (2002)
#信道容量 #香农定理 #信噪比
什么是哈希函数的基本性质？它为什么难以被逆向？
What are the basic properties of a hash function, and why is it hard to invert?
密码学哈希把任意长度输入映射为固定长度输出，需满足确定性、快速计算、抗碰撞（难找两输入同输出）与单向性（由输出难反推输入）。由于输出空间远小于输入空间且映射高度混合，逆向需穷举，计算上不可行。
A cryptographic hash maps arbitrary input to fixed-length output, requiring determinism, efficiency, collision resistance (hard to find two inputs with the same output), and one-wayness (hard to recover input from output). Since the output space is much smaller than the input space and the mapping is highly mixed, inversion requires infeasible brute force.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《应用密码学》Schneier
Applied Cryptography by Bruce Schneier
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111075882（豆瓣书目条目: 应用密码学）
#哈希 #单向性 #抗碰撞
什么是率失真理论？它如何在允许失真的前提下给出压缩极限？
What is rate-distortion theory, and how does it give the compression limit when some distortion is allowed?
率失真理论在允许最大失真 D 的约束下，求编码所需的最小速率 $R(D)=\min I(X;\hat X)$，其中 $\hat X$ 是重建值。它说明有损压缩存在权衡曲线：允许失真越大，所需比特率越低，由互信息的最小值界定，是 JPEG、MP3 等标准的理论根基。
Rate-distortion theory finds the minimum rate $R(D)=\min I(X;\hat X)$ needed to reproduce a source within maximum distortion D, where $\hat X$ is the reconstruction. It shows a trade-off curve for lossy compression: more allowed distortion means fewer bits, bounded by the minimum mutual information, underpinning standards like JPEG and MP3.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《信息论基础》Cover 与 Thomas
Elements of Information Theory by Cover and Thomas
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780471241959 (2006) · 核验依据 2 ISBN 9780665590955 (2002)
#率失真 #有损压缩 #互信息
无损压缩为什么不能把任何文件都压得更小？
Why can't lossless compression shrink every file?
若每个文件都能无损变小，反复压缩会无限变小，最后只能映射到单一文件，不可能还原。所以随机或已压缩的数据往往‘压不动’。
If every file could shrink losslessly, repeated compression would shrink infinitely to a single file, impossible to invert. So random or already-compressed data usually cannot be compressed further.
难度 进阶 · 适合 小学高段(9-12)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
Cover, T. M. & Thomas, J. A.《Elements of Information Theory》,Wiley
Cover, T. M. & Thomas, J. A., Elements of Information Theory, Wiley
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780471241959 (2006) · 核验依据 2 ISBN 9780665590955 (2002)
#压缩 #信息论
什么是里德-所罗门码？它为何广泛应用于光盘与深空通信？
What are Reed-Solomon codes, and why are they widely used in optical discs and deep-space communication?
里德-所罗门码是基于有限域上多项式的纠错码，把数据视为多项式系数，在多余点上采样作为冗余。它能纠正成块突发错误（整段字节丢失），在 CD/DVD、二维码与旅行者号深空链路中表现优异，因为突发错误比随机位错更常见。
Reed-Solomon codes are error-correcting codes over finite fields that treat data as polynomial coefficients and sample at extra points for redundancy. They correct burst errors (whole byte blocks lost), performing excellently in CDs/DVDs, QR codes, and Voyager deep-space links, where bursts are more common than random bit flips.
难度 进阶 · 适合 大众
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录仅给书名，无版次与年份；同一书名常对应多个版次，不臆测具体版本。
《纠错码理论》MacWilliams 与 Sloane
The Theory of Error-Correcting Codes by MacWilliams and Sloane
#里德-所罗门 #突发错误 #有限域
什么是香农熵？它如何度量一个随机源的不确定性？
What is Shannon entropy, and how does it measure the uncertainty of a random source?
香农熵定义为 $H(X)=-\sum_i p_i\log_2 p_i$，其中 $p_i$ 是各结果概率。熵越大表示结果越难预测：确定事件的熵为 0，均匀分布的熵最大。它以比特为单位，量化了信息源的平均信息量。
Shannon entropy is $H(X)=-\sum_i p_i\log_2 p_i$, where $p_i$ are outcome probabilities. Larger entropy means harder prediction: a certain event has entropy 0 and a uniform distribution maximizes it. Measured in bits, it quantifies the average information content of a source.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《信息论基础》Cover 与 Thomas
Elements of Information Theory by Cover and Thomas
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780471241959 (2006) · 核验依据 2 ISBN 9780665590955 (2002)
#香农熵 #信息量 #不确定性
什么是互信息？它与条件熵有何关系？
What is mutual information, and how is it related to conditional entropy?
互信息 $I(X;Y)=H(X)-H(X|Y)$ 度量从 Y 中获得关于 X 的信息量，也等于 $H(Y)-H(Y|X)$。它衡量两变量间的统计依赖：独立时互信息为 0，完全相关时等于各自熵。它对称且非负。
Mutual information $I(X;Y)=H(X)-H(X|Y)$ measures the information about X gained from Y, equivalently $H(Y)-H(Y|X)$. It captures statistical dependence between variables: zero when independent, equal to the individual entropy when perfectly correlated. It is symmetric and nonnegative.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《信息论基础》Cover 与 Thomas
Elements of Information Theory by Cover and Thomas
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780471241959 (2006) · 核验依据 2 ISBN 9780665590955 (2002)
#互信息 #条件熵 #依赖
Hamming(7,4) 码只靠 3 个校验位就能定位并纠正 7 位分组中的任意单比特错误,这套机制具体怎么运作?为什么 3 个校验位不多不少正好够用?
How does the Hamming(7,4) code pinpoint and repair any single flipped bit in a 7-bit block using only 3 parity bits, and why are exactly 3 check bits neither more nor less than enough?
给 7 个位置写下 1 到 7 的二进制编号后,三个校验方程分别看管索引某一位为 1 的那些位置:第 1 位覆盖全部奇数位置,第 2 位覆盖 2、3、6、7,第 4 位覆盖 4 到 7。收方重算三个奇偶得到的 3 比特伴随式,其数值本身就是出错位置的二进制编号,000 则代表无错。从计数角度看,纠单错必须区分 8 种情形——7 个可能位置加上无错,而 3 个校验位恰好提供 2^3=8 种状态,一种不浪费,这也是它被称为完备码的原因。
Write the seven positions numbered 1 through 7 in binary and let each of the three parity equations watch exactly those indices with a 1 in one bit: bit one covers all odd indices, bit two covers 2, 3, 6 and 7, and bit four covers 4 through 7. On reception the receiver recomputes three parities, and the resulting 3-bit syndrome numerically equals the binary index of the flipped bit, with 000 signaling no error at all. Counted information-theoretically, single-error correction must distinguish 8 outcomes — 7 possible locations plus no error — and 3 check bits supply exactly 2^3=8 states with none squandered, which is why the scheme is called a perfect code.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
R. W. Hamming, Error Detecting and Error Correcting Codes, Bell System Technical Journal, vol. 29, no. 2, pp. 147-160, 1950
R. W. Hamming, Error Detecting and Error Correcting Codes, Bell System Technical Journal 29 (1950) 147-160
独立核验依据 · Independent verification: 核验依据 1 DOI 10.1002/j.1538-7305.1950.tb00463.x
#编码理论 #汉明码