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～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!