香农第一定理（Shannon's Source Coding Theorem / Noiseless Coding Theorem）：
\[
H(S) \le \bar{L} < H(S) + 1
\]
其中 \(H(S) = -\sum_{i=1}^{n} p_i \log_2 p_i\) 为信源的信息熵，\(\bar{L}\) 为编码后的平均码长。
定理指出：平均码长可以无限接近信息熵，但永远不能低于信息熵。
📖 问题背景
在数字通信和数据存储中，如何用最少的比特数表示信源符号？香农第一定理给出了答案：信源的信息熵 \(H(S)\) 是无损编码的理论极限。任何编码方法的平均码长 \(\bar{L}\) 都不可能小于 \(H(S)\)，但可以无限接近 \(H(S)\)。
🎯 核心思想
- 信息熵：衡量信源的不确定性，也是表示信源所需的最小平均比特数
- 编码效率：\(\eta = H(S)/\bar{L} \times 100\%\)，效率越高，压缩效果越好
- 冗余度：\(R = 1 - \eta\)，反映编码中的冗余信息
📐 严格数学证明（概要）
① 信息熵定义：\(H(S) = \sum_{i=1}^{n} p_i \log_2(1/p_i)\)，表示信源的平均信息量。
② 前缀码条件（Kraft不等式）：任意唯一可译码的码长 \(\{l_i\}\) 满足 \(\sum 2^{-l_i} \le 1\)。
③ 下界证明（Gibbs不等式）：对于任意满足Kraft不等式的码长，\(\bar{L} - H(S) = \sum p_i l_i + \sum p_i \log_2 p_i \ge 0\)，等号成立当且仅当 \(l_i = -\log_2 p_i\)。
④ 上界证明：选择 \(l_i = \lceil -\log_2 p_i \rceil\)，则 \(-\log_2 p_i \le l_i < -\log_2 p_i + 1\)，加权平均得 \(H(S) \le \bar{L} < H(S) + 1\)。
⑤ 渐近极限：对符号序列分组编码（扩展信源），平均每个符号的码长可无限接近 \(H(S)\)。
🔬 本实验的验证方法
本实验采用哈夫曼编码（Huffman Coding）进行动态验证：
- 哈夫曼编码：最优前缀码，平均码长最接近信息熵
- 验证指标：信息熵 \(H\)、平均码长 \(\bar{L}\)、编码效率 \(\eta\)
- 对比曲线：信息熵与平均码长的关系，验证香农定理的界限
下方动态仿真中，调节符号概率分布，观察：
- 概率分布越均匀 → 信息熵越大 → 压缩空间越小
- 概率分布越不均匀 → 信息熵越小 → 压缩空间越大
- 哈夫曼编码的平均码长始终 ≥ 信息熵，且差距 ≤ 1 bit