球填充问题

概述

球填充问题（Sphere Packing Problem）在信息论中是指：在高维信号空间内，最多能放置多少个互不重叠的"噪声球"，从而确定信道容量的几何上界。

关键内容

在 Shannon 1949 论文中的角色

Shannon 提出了一个极具洞察力的几何图景：

• 一个持续 T 秒、带宽 W Hz 的信号可以表示为 2WT 维空间中的一个点
• 信号功率约束意味着这个点必须落在半径为 √(ST) 的超球面内
• 噪声使得接收信号偏离发送信号，形成一个半径为 √(NT) 的"噪声球"
• 要可靠区分不同消息，每个消息对应的"噪声球"不能重叠

问题因此转化为：在一个大球面内，最多能塞进多少个互不重叠的小球？

推导

在 n = 2WT 维空间中： - 信号球体积 ∝ (S + N)^(n/2) - 噪声球体积 ∝ N^(n/2) - 最多可容纳消息数 M ≈ ((S + N) / N)^(n/2) = (1 + S/N)^(WT)

因此可传输比特数 = log₂ M = WT · log₂(1 + S/N)，即每秒 W · log₂(1 + S/N) bit。

与编码理论的关系

信道编码问题与球填充、lattice 几何的联系催生了代数几何在编码理论中的应用。好的编码方案对应于高维空间中的最优球填充。

来源

• raw/books/信息论/03_shannon_1949_communication_in_presence_of_noise.md — Shannon (1949) 深度解析

相关

• Shannon-Hartley公式 — 通过球填充推导
• 信道容量 — 几何解释
• 信息论 — 所属学科