25保研er，希望将自己的面试复习分享出来，供大家参考
part0—英语类
part1—通信类
part2—信号类
part3—高数类
part100—self项目准备

---

---

下面是学校期末复习大纲，以此进行复习整理

---

面试复习总纲

1. 一条主线：香农（Shannon）的研究工作解决了通信的两个核心问题：
   • 数据压缩的极限是什么？ (信源编码，对应熵)
   • 可靠传输的速率极限是什么？ (信道编码，对应信道容量)
2. 两大基石：
   • 信源编码定理 (香农第一定理)：回答了第一个问题。
   • 信道编码定理 (香农第二定理)：回答了第二个问题。
3. 核心思想：用概率论和统计方法来量化“信息”，并研究信息处理的极限。

---

Chap2: 熵、相对熵和互信息 (Entropy, Relative Entropy, and Mutual Information)

这是信息论的基石，几乎是必考内容。面试官会从这里开始，判断你的基础是否扎实。

核心问题 1：请谈谈你对“信息熵”的理解。它的物理意义是什么？

• 回答要点:

  1. 定义: 信息熵 $H(X)$ 是对随机变量不确定性的一种度量。一个随机变量的熵越大，它的不确定性就越大，我们从中获取信息时，得到的信息量也就越大。
  2. 数学公式: 对于离散随机变量 $X\sim p(x)$，其信息熵定义为：
     $$H(X)=-\sum _{x\in \mathcal{X}}p(x){\log }_{2}p(x)$$
     • 解释 -log p(x): 这被称为“自信息”（Self-information）。一个事件发生的概率越小，它一旦发生，所提供的信息量就越大。比如，“太阳从东边升起”（p≈1）信息量很小，而“国足勇夺世界杯”（p很小）信息量就巨大。log底取2时，单位是比特（bit）。
     • 解释 Σ 和 p(x): 整个公式是“自信息”的期望值（Average Self-information）。所以，信息熵是平均意义上描述信源不确定性的。
  3. 物理意义/操作性含义:
     • 不确定性度量: 如上所述。
     • 平均编码长度下界: 这是最重要的物理意义。根据香农第一定理，信息熵 $H(X)$ 代表了对该信源进行无损压缩时，每个符号所需要的平均最小比特数。任何无损压缩算法的平均码长都不可能小于信息熵。

• 深入探讨:

  • 性质: 什么时候熵最大？（均匀分布时）。什么时候熵最小？（确定性分布，即某个事件概率为1时，熵为0）。
  • 与物理学中“熵”的联系: 克劳修斯在热力学中提出的熵是描述系统混乱程度的宏观态指标，而玻尔兹曼用 $S=k\ln \Omega$ 将其与微观状态数联系起来。信息熵在形式上和玻尔兹曼熵高度一致，都描述了“状态的不确定性”或“混乱程度”。这是学科交叉的好话题。

• 追问示例:

  • “为什么熵在均匀分布时取得最大值？请直观解释一下。” (因为所有事件可能性都一样，毫无规律可循，不确定性最高。)
  • “联合熵 $H(X,Y)$ 和条件熵 $H(Y|X)$ 是什么？它们之间有什么关系？” (引出链式法则 $H(X,Y)=H(X)+H(Y|X)$，并解释其意义：两个变量的总不确定性 = 第一个变量的不确定性 + 已知第一个变量后，第二个变量的剩余不确定性。)

---

核心问题 2：请解释一下“互信息” (Mutual Information)，并说明它和熵的关系。

• 回答要点:

  1. 定义: 互信息 $I(X;Y)$ 度量了一个随机变量中包含的关于另一个随机变量的信息量。通俗讲，就是知道 Y 之后，对 X 不确定性的消除程度。
  2. 三种等价的数学公式与解释:
     • $I(X;Y)=H(X)-H(X|Y)$
       • 解释: 这是最直观的定义。知道 $Y$ 后，对 $X$ 的不确定性从 $H(X)$ 降为了 $H(X|Y)$，减少的部分就是 $Y$ 带来的关于 $X$ 的信息。
     • $I(X;Y)=H(Y)-H(Y|X)$
       • 解释: 互信息是对称的。知道 $X$ 对 $Y$ 不确定性的消除程度，等于知道 $Y$ 对 $X$ 不确定性的消除程度。
     • $I(X;Y)=H(X)+H(Y)-H(X,Y)$
       • 解释: 这可以类比集合论中的韦恩图（Venn Diagram）。把 $H(X)$ 和 $H(Y)$ 看作两个集合，$H(X,Y)$ 是它们的并集，$I(X;Y)$ 则是它们的交集。这是一种非常强大的可视化理解方式。
  3. 物理意义: 互信息是通信系统中的核心概念。它代表了信道中可靠传输信息速率的度量。信道容量就是最大化的互信息。

• 深入探讨:

  • 互信息 vs. 相关系数:
    • 相关系数只能度量线性关系。两个变量可能相关系数为0，但不是独立的。
    • 互信息能度量任意类型的统计依赖关系（线性和非线性）。$I(X;Y)=0$ 当且仅当 $X$ 和 $Y$ 相互独立。因此，互信息是更广义的“相关性”度量。
  • 相对熵 (KL散度):
    • $D_{KL}(p||q)=\sum p(x)\log \frac{p(x)}{q(x)}$。它度量了两个概率分布 $p$ 和 $q$ 的差异。
    • 操作性含义: 当真实分布为 $p$ 时，如果我们用基于分布 $q$ 的最优编码去编码，平均会比用基于 $p$ 的最优编码多付出 $D_{KL}(p||q)$ 个比特。
    • 与互信息的关系: $I(X;Y)=D_{KL}(p(x,y)||p(x)p(y))$。这说明互信息度量的是联合分布 $p(x,y)$ 与“独立”假设下的边缘分布乘积 $p(x)p(y)$ 之间的差异。

• 追问示例:

  • “画图解释一下 $H(X)$, $H(Y)$, $H(X|Y)$, $H(Y|X)$, $H(X,Y)$, $I(X;Y)$ 之间的关系。” (一定要会画韦恩图！)
  • “KL散度是距离吗？为什么？” (不是。因为它不满足对称性 $D(p||q)\ne D(q||p)$ 和三角不等式。)

---

Chap 4 & 5: 熵率与数据压缩 (Entropy Rate & Data Compression)

这是香农第一定理的应用，将理论与实践结合。

核心问题：请阐述香农第一定理（信源编码定理），并解释它如何指导数据压缩？

• 回答要点:

  1. 信源编码的目标: 用尽量少的比特来表示信源符号，同时要能无歧义地恢复原始数据（无损压缩）。
  2. 熵率 (Entropy Rate): 对于一个随机过程（比如一段英文文本），它的熵率 $H(\mathcal{X})$ 是指平均每个符号的不确定性。
     • 对于独立同分布(i.i.d.)信源，熵率就是单个符号的熵 $H(X)$。
     • 对于有记忆的信源（如马尔可夫信源），熵率会小于单个符号的熵，因为上下文提供了信息，降低了不确定性。
  3. 香农第一定理 (无损编码定理):
     • 内容: 对于一个熵率为 $H(\mathcal{X})$ 的信源，存在一种编码方式，使得其平均码长 $L$ 满足 $H(\mathcal{X})\le L<H(\mathcal{X})+ϵ$，其中 $ϵ$ 可以任意小。
     • 核心思想: 该定理给出了数据无损压缩的理论极限，这个极限就是信源的熵率。它告诉我们，平均码长可以无限逼近熵率，但不可能小于熵率。
  4. 如何指导数据压缩:
     • 它为所有压缩算法（如ZIP, PNG等）的性能设定了一个无法逾越的标杆。我们可以通过比较一个压缩算法的压缩率和信源熵，来评价该算法的优劣。
     • 霍夫曼编码 (Huffman Coding): 是一个具体的、构造性的例子。它是一种最优的前缀码（对于已知符号概率分布），其平均码长可以很接近熵。你应该能够解释霍夫曼编码的原理（贪心算法，构建二叉树）并手动算一个简单例子。
     • LZ系列算法 (Lempel-Ziv): 提到这类算法能展示你的知识广度。LZ算法是“通用”的，它不需要预先知道信源的概率分布，而是通过动态建立字典来实现压缩，在实践中应用极广。

• 深入探讨:

  • 定长编码 vs. 变长编码: 为什么需要变长编码？（为了让高频符号用短码，低频符号用长码，从而降低平均码长）。
  • 克拉夫特不等式 (Kraft’s Inequality): ${\sum }_i{2}^{-l_i}\le 1$。它是一个即时码（前缀码）存在的充要条件。香农第一定理的证明也依赖于它。

• 追问示例:

  • “为什么说熵是无损压缩的极限？你能从直观上解释一下吗？” (因为熵代表了信源的‘固有信息量’或‘不确定性’，你至少需要等量的比特才能完全无损地描述这份不确定性。)
  • “霍夫曼编码在什么情况下是最优的？它有什么局限性？” (当信源符号概率已知且为 $2^{-k}$ 形式时，霍夫曼编码能达到熵下界。局限性：需要知道概率分布；一次处理一个符号，没有考虑符号间的相关性。)

---

Chap 7 & 9: 信道容量与高斯信道 (Channel Capacity & Gaussian Channel)

这是信息论的另一半，也是香农理论的精髓所在。

核心问题：请解释一下信道容量的定义和香农第二定理（有噪信道编码定理），并阐述其革命性意义。

• 回答要点:
  1. 信道编码的目标: 在有噪声的信道中，通过增加冗余（编码），实现可靠的通信。
  2. 信道容量 (Channel Capacity):
     • 定义: 信道容量 $C$ 是该信道能够无差错地传输信息的最大速率。
     • 数学公式: $C={\max }_{p(x)}I(X;Y)$。
     • 解释: 容量是信道本身的固有属性，与信源无关。它取决于信道的统计特性（如BSC中的翻转概率p，或AWGN信道中的噪声功率N）。我们通过调整输入信号的概率分布 $p(x)$ 来找到这个最大的互信息，从而得到信道容量。
  3. 香农第二定理 (有噪信道编码定理):
     • 内容:
       • 若信息传输速率 $R<C$，则一定存在一种编码方式，使得传输的错误概率可以做到任意小 (arbitrarily small)。
       • 若信息传输速率 $R>C$，则不可能做到任意小的错误概率。
     • 革命性意义: 在香农之前，人们认为噪声是通信的“死敌”，提高可靠性只能通过增大信噪比或降低速率。香农定理石破天惊地指出：只要你的传输速率低于一个明确的极限（信道容量），噪声就不是不可战胜的，我们可以通过足够聪明的编码，实现近乎完美的通信！它将“传输速率”和“可靠性”这对矛盾统一了起来。

核心问题 2：高斯信道的容量是多少？请解释香农-哈特利公式。

• 回答要点:

  1. 高斯信道模型: 这是一个非常重要的连续信道模型。$Y=X+Z$，其中 $X$ 是输入信号，有功率限制 $P$；$Z$ 是均值为0，方差为$N$的高斯白噪声 (AWGN)；$Y$ 是输出信号。
  2. 香农-哈特利公式:
     $$C=W{\log }_2\left(1+\frac{P}{N_{0}W}\right)\text{bits/sec}$$
     或者在归一化带宽下，写成：
     $$C=\frac{1}{2}{\log }_2\left(1+\frac{P}{N}\right)\text{bits/symbol}$$
     • $P$ 是信号功率，$N$ 是噪声功率，$P/N$ 是信噪比 (SNR)。
     • 这个公式揭示了带宽 (W) 和信噪比 (SNR) 如何共同决定了通信速率的上限。
  3. 公式解读与推论:
     • 提高容量的途径:
       1. 增加带宽 $W$: 在 $P/(N_{0}W)$ 很大时，C 和 W 近似线性关系。但在低信噪比下，无限增加带宽，容量会趋于一个极限 $C_{\infty }=\frac{P}{N_0\ln 2}$。
       2. 增加信噪比 $P/N$: 容量与 $\log (1+SNR)$ 成正比。这意味着，当SNR已经很高时，再加倍功率，容量的提升并不大（对数关系）。
     • 带宽与信噪比的权衡: 公式表明，带宽和信噪比可以相互转换。在低信噪比环境下（如深空通信），可以采用扩频等技术，用极大的带宽来换取可靠通信。

• 深入探讨:

  • 为什么是高斯输入: 在给定功率约束下，高斯分布的输入信号可以最大化 $I(X;Y)$，从而达到信道容量。
  • 定理的非构造性: 香农第二定理只证明了这种“好”编码的存在性，但没有给出如何构造它。寻找逼近香农极限的编码方案（如Turbo码，LDPC码，Polar码）是后续几十年通信领域研究的核心。提到这些可以展示你的前沿知识。

• 追问示例:

  • “既然速率低于容量就能做到任意小差错，为什么现实中的通信（比如手机信号不好）还是会出错/卡顿？” (因为逼近香农极限的编码，其译码复杂度和时延都会非常大。实际系统需要在性能、复杂度和时延之间做权衡。)
  • “如果给你无限的带宽，你能传输无限大的信息吗？为什么？” (不能。根据极限 $C_{\infty }=P/(N_0\ln 2)$，容量会趋于一个由信号功率和噪声功率谱密度决定的常数。)

---

Chap 8 & 10: 差分熵与率失真理论 (Differential Entropy & Rate-Distortion Theory)

这部分是信息论的延伸，进入连续信源和有损压缩领域。

核心问题：谈谈你对率失真理论的理解。它解决了什么问题？

• 回答要点:

  1. 动机: 无损压缩的极限是熵，但对于图像、音频、视频这类信源，数据量巨大，熵也很高。如果完全无损压缩，效果有限。同时，人眼/人耳对微小的失真不敏感。因此，我们愿意牺牲一定的保真度（允许失真）来换取更高的压缩率。
  2. 核心问题: 在允许一定失真度 $D$ 的前提下，表示这个信源最少需要多少比特率 $R$？
  3. 率失真函数 $R(D)$:
     • 定义: $R(D)={\min }_{p(\hat{x}|x):E[d(x,\hat{x})]\le D}I(X;\hat{X})$
     • 解释: $R(D)$ 是一个函数。给定一个可接受的最大平均失真 $D$，我们去寻找一种“映射”方式（由条件概率 $p(\hat{x}|x)$ 描述，可以看作是一种量化或有损编码），使得原始信号 $X$ 和重建信号 $\hat{X}$ 之间的互信息 $I(X;\hat{X})$ 最小，同时满足失真约束。这个最小的互信息就是我们需要的最低码率。
  4. 与香农理论的关系:
     • 它是香农第一定理的推广。当失真 $D=0$ 时（对于离散信源），$R(0)=H(X)$，理论退化为无损压缩。
     • 它为所有的有损压缩算法（如JPEG, MP3, H.264）提供了理论基础和性能极限。

• 深入探讨:

  • 差分熵 (Differential Entropy): $h(X)=-\int f(x)\log f(x)dx$。
    • 它是离散熵在连续领域的直接推广。
    • 与离散熵的区别: 差分熵可以是负数；它不是坐标变换下的不变量。它本身不代表编码的比特数，但差分熵的差是有意义的。
  • 高斯信源的率失真函数: 对于均值为0，方差为 ${\sigma }^2$ 的高斯信源，在均方误差失真 $D$ 下，其率失真函数为 $R(D)=\frac{1}{2}{\log }_2\frac{{\sigma }^2}{D}$ (当 $0\le D\le {\sigma }^2$)。这个公式非常有名，被称为“逆高斯水填”。

• 追问示例:

  • “$R(D)$ 函数通常是什么形状的？为什么？” (是D的非增、凸函数。因为允许的失真越大，需要的码率自然越低；并且码率的减少速度会越来越慢。)
  • “JPEG图像压缩和率失真理论有什么关系？” (JPEG的核心是DCT变换+量化+熵编码。其中的“量化”步骤就是典型的率失真实践：通过粗糙的量化（高失真）换取更少的比特（低码率），或者精细的量化（低失真）保留更多的信息（高码率）。用户选择的“图像质量”参数，本质上就是在$R(D)$曲线上选择一个工作点。)

---

面试综合建议

1. 串联知识：面试官很喜欢问“A和B有什么关系”。你要能串联起：
   • 熵 $\to$ 无损压缩极限 (信源编码)
   • 互信息 $\to$ 信道容量 $\to$ 可靠传输速率极限 (信道编码)
   • 率失真理论 $\to$ 有损压缩极限 (信源编码的推广)

---

英语版本

Overall Theme

Shannon’s theory answers two fundamental questions in communication:

1. What is the ultimate limit of data compression? (Answer: Source Coding / Entropy)
2. What is the ultimate rate of reliable communication? (Answer: Channel Coding / Channel Capacity)

---

Chap 2: Entropy, Relative Entropy, and Mutual Information

This is the foundation. Expect questions here to test your basic understanding.

Key Question: “Explain your understanding of Entropy, Mutual Information, and Relative Entropy (KL Divergence).”

• Core Concepts:

  • Entropy $H(X)$: A measure of the uncertainty or “surprise” of a random variable.
    • Physical Meaning: The average number of bits required to describe the random variable. It is the fundamental limit of lossless compression.
    • Formula: $H(X) = -\sum_{x} p(x) \log_2 p(x)$
  • Joint Entropy $H(X,Y)$: Uncertainty of a pair of random variables.
  • Conditional Entropy $H(Y|X)$: Remaining uncertainty of $Y$ given that $X$ is known.
    • Chain Rule: $H(X,Y) = H(X) + H(Y|X)$
  • Mutual Information (MI) $I(X;Y)$: The reduction in uncertainty of one variable due to the knowledge of another. It measures the shared information between $X$ and $Y$.
    • Formulas:
      • $I(X;Y) = H(X) - H(X|Y)$ (Most intuitive definition)
      • $I(X;Y) = H(X) + H(Y) - H(X,Y)$ (Venn diagram analogy)
    • $I(X;Y) \ge 0$, with equality if and only if $X$ and $Y$ are independent.
  • Relative Entropy (Kullback-Leibler Divergence) $D_{KL}(p||q)$: A measure of the “distance” between two probability distributions, $p(x)$ and $q(x)$.
    • Physical Meaning: The extra number of bits required to encode data from a source with true distribution $p$ if we use a code optimized for distribution $q$.
    • Formula: $D_{KL}(p||q) = \sum_{x} p(x) \log_2 \frac{p(x)}{q(x)}$
    • Note: It’s not a true distance metric because it’s not symmetric ($D(p||q) \neq D(q||p)$).

• Potential Follow-up Questions:

  • “Visualize the relationship between different entropy measures using a Venn Diagram.”
  • “What is the difference between mutual information and correlation?” (MI detects any kind of dependency, while correlation only detects linear dependency).

---

Chap 4 & 5: Entropy Rate & Data Compression

This section connects the theory of entropy to the practice of compression.

Key Question: “What is the Source Coding Theorem and how does it relate to algorithms like Huffman Coding?”

• Core Concepts:

  • Source Coding Theorem (Shannon’s First Theorem): For a source with entropy $H(X)$, it’s possible to perform lossless compression to an average codeword length $L$ such that $H(X) \le L < H(X) + 1$.
    • The Limit: Entropy $H(X)$ is the ultimate limit for lossless compression.
  • Entropy Rate: The per-symbol entropy for a stochastic process (e.g., a source with memory).
  • Huffman Coding: A practical greedy algorithm that creates an optimal prefix code for a known probability distribution. It achieves an average length close to the entropy.
  • Lempel-Ziv (LZ) Algorithms: Universal compression algorithms (used in ZIP, GIF, PNG) that do not need prior knowledge of the source statistics.

• Potential Follow-up Questions:

  • “Why is it impossible to compress data losslessly to a rate below its entropy?”
  • “What is the Kraft inequality and what does it guarantee?” (It provides a necessary and sufficient condition for the existence of a prefix code with given word lengths.)

---

Chap 7 & 9: Channel Capacity & Gaussian Channel

This is the second pillar of information theory, dealing with reliable transmission.

Key Question: “Explain Channel Capacity and Shannon’s Second Theorem. What is the capacity of a Gaussian channel?”

• Core Concepts:

  • Channel Capacity $C$: The maximum rate (in bits per channel use) at which information can be transmitted reliably (with an arbitrarily low probability of error) over a channel.
    • Formula: $C = \max_{p(x)} I(X;Y)$
    • Insight: Capacity is a property of the channel itself, found by optimizing over all possible input distributions.
  • Noisy-Channel Coding Theorem (Shannon’s Second Theorem):
    • If the transmission rate $R < C$, reliable communication is possible.
    • If $R > C$, it is not possible.
    • Revolutionary Idea: Error-free communication is possible even over a noisy channel, as long as the rate is below capacity.
  • AWGN Channel (Additive White Gaussian Noise): A fundamental model $Y = X + Z$, where $Z$ is Gaussian noise.
  • Shannon-Hartley Theorem: Gives the capacity for an AWGN channel with bandwidth $W$, signal power $P$, and noise power spectral density $N_0$.
    • Formula: $C = W \log_2 \left(1 + \frac{P}{N_0 W}\right)$ bits/sec.
    • The term $P/(N_0 W)$ is the Signal-to-Noise Ratio (SNR).
    • Insight: Capacity grows logarithmically with SNR but (almost) linearly with bandwidth. This shows the trade-off between bandwidth and power.

• Potential Follow-up Questions:

  • “If you have infinite bandwidth, can you achieve infinite capacity? Why or why not?”
  • “Shannon’s theorem proves such codes exist. Can you name any practical codes that approach this limit?” (e.g., LDPC codes, Turbo codes, Polar codes).

---

Chap 8 & 10: Differential Entropy & Rate-Distortion Theory

This covers the extension to continuous sources and lossy compression.

Key Question: “What is Rate-Distortion Theory and what problem does it solve?”

• Core Concepts:

  • Goal: To find the minimum data rate R required to represent a source if a certain level of distortion D is permitted. This is the fundamental theory for lossy compression (JPEG, MP3, etc.).
  • Rate-Distortion Function R(D): The minimum rate R for a given maximum distortion D.
    • Formula: $R(D) = \min_{p(\hat{x}|x): E[d(x,\hat{x})] \le D} I(X;\hat{X})$
    • $R(D)$ is a non-increasing, convex function of $D$.
  • Differential Entropy $h(X)$: The extension of entropy to continuous random variables.
    • Formula: $h(X) = -\int f(x) \log f(x) dx$
    • Key Property: Unlike discrete entropy, it can be negative. For a given variance, the Gaussian distribution maximizes differential entropy.

• Potential Follow-up Questions:

  • “How does Rate-Distortion Theory relate to the Source Coding Theorem?” (Source coding is a special case of R-D theory where the distortion $D=0$, and $R(0) = H(X)$.)
  • “Briefly explain how JPEG compression is an application of rate-distortion principles.” (The “quality” setting in JPEG directly controls the quantization step, which is a trade-off between rate and distortion.)

Good luck with your interview!