IT 04・通道容量與可靠通訊
先備知識:IT 03・無損編碼與通用壓縮
導覽:本頁與本系列: 導覽:本頁與本系列
本頁內容
資訊理論
你將學到
- 定義離散無記憶通道,區分訊息與通道符號。
- 推導二元對稱通道與二元抹除通道的容量。
- 透過聯合典型性與配置直覺理解隨機編碼可達性。
- 利用 Fano 不等式推導可靠速率的反向界限。
- 以 Blahut–Arimoto 計算容量與最佳性差距。
- 區分漸近限制、有限區塊可靠性與任務導向通訊。
先看全貌
雜訊通道不必正確還原每個傳送符號,接收者仍可能恢復訊息。編碼將每個訊息表示成較長且有結構的序列;接收端把帶雜訊觀測與可能序列比較,判斷送出哪個訊息。
來源編碼移除可預測冗餘,通道編碼增加有用冗餘;兩者目標不同。重複位元是簡單通道編碼,卻不一定有效利用通道。核心問題是每次通道使用能傳多少不同訊息,同時讓重建錯誤趨近零。
主要閱讀是 Cover 與 Thomas 第 7 章;書中的計算討論將容量最佳化與 Blahut–Arimoto 方法連結 [1]。Stanford 的通訊與反向定理講義 [2,3] 提供原始推導。我們先建立假設與數值實驗,再說明實際短訊息為何需要額外評估。
先定義通道,再談容量
通道指定輸入符號如何隨機轉成輸出符號。來源分布與通道轉換是不同的對象。
對有限輸入字母集 與輸出字母集 ,離散無記憶通道由列隨機矩陣表示:
其中 是符號索引, 且每列總和為一。區塊 長度為 , 索引一次使用。分解定義無記憶性與不隨時間改變的轉移律。
無記憶性描述給定整個輸入區塊後的輸出。編碼輸入符號可能相依,因為它們都由同一訊息決定;未條件化的輸出也可能因此相依。證明反向界限時假設輸入獨立,會不必要地限制允許編碼。
單符號計算中,發送者選擇輸入分布 ,誘導輸出機率
其中 是輸出邊際。改變 時,通道 不變。更改傳播律、接收觀測、資源限制或可用回饋,便定義不同通訊問題。
相同的轉移列無法區分對應輸入。不同列也會因重疊程度而較易或較難區分。輸出字母大小給出粗略資訊上界,實際可利用的區別則由轉移機率決定。
速率與可靠性是操作量
通訊速率是訊息資訊除以通道使用次數。可靠性討論恢復整個訊息,不只是讓多數通道符號正確。
設訊息 在 個選項中均勻分布,長度 編碼把它映至 ,再從收到的 估計 。定義
其中 是碼本大小, 是每次使用的位元數, 是指定均勻訊息與通道下的平均訊息錯誤機率。它不同於符號錯誤率。
若存在一系列編碼,使漸近速率至少為 且訊息錯誤趨近零,則 可達。容量是可達速率的上確界:
其中 遍歷有限字母集上的所有輸入分布, 是聯合分布 下的互資訊。第二個等號是指定有限無記憶通道的通道編碼定理 [1,2]。
標準可達敘述討論嚴格低於容量的速率,不保證有限長度零錯誤,也不提供快速解碼器。容量也不同於零錯誤容量:後者要求允許輸出集合永遠不混淆訊息。某通道可以有正的一般容量,但每個有限區塊仍有非零混淆機率。
平均錯誤設定假設均勻訊息。所有訊息的最大錯誤是另一種操作準則;標準有限無記憶結果可移除差的碼字,僅付出漸近可忽略的速率損失,連結兩種容量設定。有限長度可靠性統計仍可能不同。
二元對稱通道
每個位元以相同機率獨立翻轉。公平輸入充分利用兩種輸出選項。
翻轉機率為 的二元對稱通道滿足
其中 是翻轉機率, 是二元熵,容量單位為每次使用的位元數。任一輸入的條件輸出熵為 。因為 ,互資訊至多 ;公平輸入達到此界。
時無雜訊傳送一位元; 時輸出與輸入獨立,容量為零; 時每個位元確定翻轉,接收端反轉即可,容量又為一。整個區間的雜訊程度不能只看原始翻轉比例。
圖將翻轉機率限制於零至二分之一,這段範圍自然對應不確定性增加;另一半分支可透過重新標記輸出得到。
二元抹除通道
接收者不是看到正確位元,就是看到明確的缺失標記。知道哪些觀測缺失,本身就有用。
抹除機率為 的二元抹除通道,其輸出是零、一與抹除符號:
其中列對應輸入零與一,欄對應兩種正確符號與抹除。抹除事件與輸入獨立。
給定未抹除輸出,輸入已知;給定抹除,不確定性仍為 。因此 ,公平輸入達到每次使用 位元。
相同數值的事件機率,對翻轉與可見抹除產生不同容量。抹除告訴接收者資訊在哪裡缺失,未標記翻轉卻可能暗示錯誤選項。差異來自不同輸出律,不是所有實體通訊系統的普遍排名。

不對稱通道需要不對稱訊號分布
一種輸入比另一種可靠時,均勻分布未必最佳。容量最佳化各輸入使用頻率。
考慮零正確到達,而一以機率 變成零的 Z 通道:
其中 是一轉零機率, 是純量輸入參數。輸出一機率為 ,條件輸出熵為 。
第一項鼓勵多樣輸出,第二項計入使用一時付出的雜訊成本。權衡可能使最大值偏離 。只傳可靠的零也沒有用:常數輸入不攜帶訊息資訊。

互資訊對輸入分布為凹函數,因為輸出熵是凹的,條件輸出熵是線性的,因此數值最佳化可行。不同輸入冗餘時,仍可能有平坦最大區域,最佳分布不必唯一。
為何低於容量的速率可達
選許多看起來像合法來源區塊的長碼字。收到的區塊通常符合真正碼字的通道關係,卻很少符合無關碼字。
固定輸入分布 ,從 獨立產生約 個碼字。聯合典型解碼器依聯合律 ,尋找唯一符合收到輸出的碼字 [1]。
主要有兩種錯誤:真正輸入輸出配對未通過典型測試,或另一個碼字通過。第一種機率由聯合 AEP 趨近零;獨立競爭碼字的聯合典型機率,其指數尺度約為 。
對競爭碼字使用聯集界限,得到示意尺度
其中 是出現競爭典型碼字的機率, 吸收典型性容許誤差, 省略有限前因子與細節。這是證明直覺,不是精確有限長度效能公式。
若 ,競爭錯誤界限趨近零。選擇最大化輸入並令容許誤差夠小,便得到低於容量的速率。隨機碼本的平均錯誤很小,表示至少有一個確定碼本錯誤很小。
論證不需要每次訊息傳送隨機種子。碼本在通訊前已固定,兩端皆已知。若實際系統選擇或傳送新碼本,設定協定需另外計算。
隨機編碼證明存在性。逐一搜尋指數大小碼本通常不可行;典型性不是部署解碼器的直接配方。容量定理指出目標,實際結構化編碼另外解決複雜度問題。
Fano 不等式限制接收端推論
接收者經常猜錯,就仍有訊息不確定性。反之,低錯誤機率意味很少剩餘的條件訊息不確定性。
對 個可能訊息,以及任何根據 的估計,
其中 是真訊息, 是收到區塊,, 是二元熵。這是 Fano 不等式 [1,3]。
引入錯誤指標便能理解邏輯:描述是否錯誤,至多需要其二元熵。沒有錯誤時,估計識別訊息;有錯誤時,至多剩 個選項。平均後得到第一個界限。
均勻訊息滿足 。資料處理與通道無記憶性限制
其中 是傳送碼字。中間不等式允許碼符號相依:輸出熵至多為各邊際輸出熵總和,條件輸出熵則在無記憶通道下分離。
合併兩個界限得到
其中 ,只有右側為正時下界才有意義。固定速率嚴格超過容量時,錯誤不可能趨近零。
這個基本反向證明建立超過容量的正錯誤底限,單獨並未證明錯誤趨近一。強反向敘述需要額外定理與假設。應精確說明顯示的不等式到底證明什麼。
手算速率、錯誤與來源預算
翻轉機率 時,BSC 容量為 位元/次使用。同樣抹除機率的 BEC 容量是 0.9。差異來自觀測模型:BEC 會揭露哪些符號遺失。
長度 100、碼率 0.8 的編碼共有 種可能訊息。把 BSC 容量代入基本逆定理:
是平均整訊息錯誤,100 是通道使用數,0.8 是每次使用的訊息位元。代入容量保留較多小數位,再將答案取整。在指定通道下,無論解碼器如何,這個編碼都不可能達成 1% 訊息錯誤目標。但此界限不決定任何特定編碼的精確錯誤。
碼率改成 0.5 時,同一界限為負,因此只剩平凡下界零。它與低於容量的漸近可達性相容,卻不證明長度 100 已經有足夠可靠性。兩個問題需要不同證據:區塊持續增長的定理,以及有限編碼計算或實驗。
再取一個一的機率為 0.2 的獨立二元來源,每符號熵為 0.721928 位元。漸近分離設定下,要透過此 BSC 幾乎無損傳送,需要每來源符號超過 次通道使用。一次不足,兩次則有速率餘裕。若先用原始表示,每來源符號需要一位元,再加通道保護;這說明利用來源偏差與抵抗雜訊是不同設計步驟。
頻寬比例不必是整數。長區塊可以分配相應通道使用總數,實現有理數或近似比例;延遲與有限區塊額外成本仍是另外的限制。
Blahut–Arimoto 容量計算
從輸入混合開始,檢查每個通道列與其輸出混合有多能區分,再把機率移向較有資訊的列。重複直到上下界接近。
對目前正輸入機率 與誘導 ,以自然單位定義列散度:
其中 是通道列 與目前輸出分布的散度, 是自然對數, 索引輸入。分母使用同一目前分布,更新不會將它換成均勻先驗。自然單位除以 轉成位元。
目前分布的上下界為
其中 是目前互資訊, 是以目前輸出混合作候選參照分布得到的對偶形式界限。差距可作為數值停止準則。
這個無限制演算法適用於固定有限通道。輸入成本限制需要修改最佳化,不能先算無限制容量,再宣稱符合功率或符號使用預算。
數值上界為什麼成立?
停止間隙有用的前提,是兩端真的夾住最佳值。固定目前輸出混合 ,考慮任意候選輸入分布 ,其輸出混合為 。展開對數比得到
是通道列 , 是候選使用機率, 是固定參照輸出, 是候選輸出邊際, 是 下的互資訊。整個恆等式使用自然對數。
最後散度非負,因此候選互資訊不超過左側加權總和;該總和又不超過最大的列散度。因為對所有 都成立,目前最大列散度就是容量上界。目前輸入本身的互資訊,是單字母最佳化可行值,提供下界。
最佳點分配正機率的輸入,具有相同資訊列散度;未使用輸入也不能提供更高邊際增益。更新把機率移向目前散度較高的列,直到這些條件近乎平衡。因此,間隙衡量此矩陣還可能改善多少,不只是最新參數變動有多小。
程式:驗證解析容量與最佳化 Z 通道
完整實作移除所有輸入都不可能產生的輸出欄,遮罩零列元素,並用穩定對數正規化。回傳輸入分布與其對應下界速率。
程式碼 · Python · 43 行
import numpy as np
from scipy.special import logsumexp
from scipy.optimize import minimize_scalar
def binary_entropy(p):
if p == 0 or p == 1:
return 0.0
return -p * np.log2(p) - (1 - p) * np.log2(1 - p)
def capacity(W, tolerance=1e-10, maximum=20000):
W = np.asarray(W, dtype=float)
assert W.ndim == 2 and np.all(W >= 0)
assert np.allclose(W.sum(axis=1), 1)
W = W[:, W.sum(axis=0) > 0]
q = np.full(W.shape[0], 1 / W.shape[0])
positive = W > 0
for iteration in range(maximum):
r = q @ W
ratio = np.zeros_like(W)
np.log(np.divide(W, r, out=np.ones_like(W), where=positive),
out=ratio, where=positive)
d = (W * ratio).sum(axis=1)
lower, upper = q @ d / np.log(2), d.max() / np.log(2)
if upper - lower < tolerance:
return lower, q, upper - lower, iteration + 1
log_q = np.log(q) + d
q = np.exp(log_q - logsumexp(log_q))
raise RuntimeError("Capacity iteration did not meet the requested gap")
e = 0.1
bsc = np.array([[1-e, e], [e, 1-e]])
bec = np.array([[1-e, 0, e], [0, 1-e, e]])
for W, analytic in [(bsc, 1-binary_entropy(e)), (bec, 1-e)]:
value, q, gap, steps = capacity(W)
print("Capacity / analytic / input / gap:", value, analytic, q, gap)
assert abs(value - analytic) < 1e-8
a = 0.35
z = np.array([[1, 0], [a, 1-a]])
value, q, gap, steps = capacity(z)
objective = lambda p: binary_entropy(p*(1-a)) - p*binary_entropy(a)
reference = minimize_scalar(lambda p: -objective(p), bounds=(0, 1), method="bounded")
assert abs(value + reference.fun) < 1e-8
print("Z capacity / P(input one) / gap / iterations:", value, q[1], gap, steps)與解析二元例子一致,能檢查單位與矩陣方向;與獨立純量最佳化一致,能檢查不對稱例子。這些測試可發現誤用欄隨機機率、漏掉目前 因子,或混用自然與二進位對數。
幾乎冗餘輸入與極端機率可能收斂慢或造成浮點下溢。小差距是計算精度內,對這個有限矩陣的數值證據,不證明矩陣準確描述真實通道。
重複實驗顯示有限區塊權衡
重複一位元能幫助多數決解碼,但每個訊息位元消耗更多使用次數。可靠性較高,不自動代表容量效率好。
位元在獨立 BSC 中重複奇數 次,使用多數決,則
其中 是翻轉副本數, 是翻轉機率, 是單位元訊息錯誤, 是碼率。這是精確有限編碼計算,不是容量公式。
程式碼 · Python · 12 行
import numpy as np
from scipy.stats import binom
rng = np.random.default_rng(35)
e = 0.1
for copies in [1, 3, 5, 9]:
noise = rng.binomial(1, e, size=(50000, copies))
observed_error = np.mean(noise.sum(axis=1) > copies // 2)
exact_error = binom.sf(copies // 2, copies, e)
print("Copies / rate / simulated error / exact error:",
copies, 1 / copies, observed_error, exact_error)
assert abs(observed_error - exact_error) < 0.005模擬可假設訊息位元為零,因為對稱編碼對任一傳送位元有相同錯誤機率。更多副本降低此單位元問題的錯誤,同時使速率趨近零。容量則允許碼本以正漸近速率攜帶持續增加的位元數。
有限評估應指定區塊長度、速率、訊息錯誤準則、通道參數與解碼規則。只報告容量,無法描述短編碼的延遲、複雜度或可靠性。
資源限制與不同通道假設
容量計算回答一個精確問題。更改發送者預算、加入記憶或提供不同觀測,問題就改變了。
若輸入 的非負成本為 ,每次使用的平均預算為 ,有限無記憶通道的限制問題為
其中 是輸入使用成本, 是允許平均, 是滿足限制的機率分布。通道仍是相同矩陣。公式採平均成本慣例;每個符號的嚴格峰值限制定義不同可行集合。
對不對稱二元通道,輸入一的頻率限制可能排除無限制最佳分布。結果應是容量與成本函數,不能將功率標籤貼在無限制數字上。
每秒位元的吞吐量也需要指定每秒通道使用次數。每次使用位元數,不自動等於每個樣本、像素或詞元的位元數。比較調變或表示選擇時,說明每種選擇如何改變使用次數與資源。
回饋允許編碼器先觀察過去通道輸出,再選下一輸入。一般無記憶點對點模型中,無雜訊因果回饋不增加漸近容量 [1,3],仍可改變有限編碼設計、停止規則與可達錯誤行為。不能未檢查就移用至有記憶或多使用者通道。
持續隱藏雜訊狀態可能造成群聚錯誤,而不是獨立翻轉。合併全部使用估計單一矩陣,會隱藏相依性。上述容量證明使用條件乘積律,不能直接把群聚錯誤當成平均翻轉機率的獨立取樣。
接收端側資訊也會造成類似差異。若側資訊揭露抹除位置、雜訊狀態或部分原訊息,就改變接收觀測。應比較完整觀測模型,不能讓解碼器利用基準沒有取得的資訊,卻把好處全部歸給解碼方法。
通道估計是另一個實驗
數值最佳化可能對錯誤矩陣非常準確。相信速率前,先判斷轉移機率是否描述操作條件。
對帶輸入標籤的輸入輸出觀測,簡單列估計為
其中 計算輸入 與輸出 的配對次數, 遍歷輸出, 是經驗通道矩陣。每個輸入列都需觀測;經驗零次數不證明事件不可能。
有限樣本使估計容量與最佳分布都不確定。跨獨立取得資料重複實驗可揭露變異;依已知操作條件分組可揭露不同通道律。最佳化差距衡量一個矩陣的計算收斂,實驗不確定性則討論該最佳化哪個矩陣。
若從資料擬合解碼器或輸入策略,訓練與評估也應使用分開觀測。在同一個極小樣本選擇有利輸入分布並估計表現,容易得到樂觀速率。
有用報告因此包含取樣協定、各輸入次數、操作條件、經驗列機率與保留資料重建結果。稀有輸出需明確處理,因為把它們當成零機率,會扭曲解碼器與資訊估計。
來源資訊如何配合通道資訊
來源編碼把有用不確定性打包成位元,通道編碼可靠地運送位元。兩者速率必須使用相同來源與通道使用預算比較。
若有限無記憶來源每符號熵為 ,每來源符號可使用 次通道,熟悉的漸近分離條件為
其中 是來源符號, 是使用比例, 是點對點容量。在標準長區塊假設下,來源與通道編碼能各自以餘裕接近限制 [1]。
不等式未指定實際區塊長度,也不要求有限延遲下獨立設計最佳;更未宣稱所有網路都有一般來源通道分離。保留假設,才能避免把漂亮公式套至無關限制。
有損重建需要的來源速率改為率失真函數,而不是完整熵;連續振幅通道的容量由實體限制決定。這兩個延伸引出後續章節。
現代觀點
Nguyen 等人的 2025 年已出版綜述 [4],將語意通訊分成接收者意圖模型、生成模型與深度聯合來源通道編碼。分類依系統想保留什麼、兩端如何協調區分,而非把所有學習系統當成相同編碼器。
這些目標可能改變所需重建。任務接收者也許只需要類別標籤,而非全部原始像素,因此需要的來源資訊可能減少;但在通道與限制不變時,Shannon 容量不會增加。
生成式重建也需要明確準則。合理輸出與原始內容的關係,可能不同於精確解碼訊息。明確評估任務準確度或感知失真很合理,但不能用它們取代位元可靠性主張中的訊息錯誤機率。
從古典模型推論,應分清三層:來源接收者需要什麼、實體通道傳遞什麼,以及編碼如何使用有限資源。聯合最佳化可改善實際匹配,無須推翻對應限制。
開放問題包含通道律變動時的穩健表現、短區塊可靠操作、共享模型同步,以及跨任務與接收者知識的評估。一種任務或通道的綜述結果,不建立通用語意速率。
下一章將字母從有限符號改成連續振幅,先建立微分熵與功率限制,再推導 Gaussian 容量。把連續密度直接代入離散熵公式,會漏掉重要的單位依賴。
重點整理
- 無記憶通道在給定輸入下分解輸出,碼符號不必獨立。
- 容量是可靠訊息速率,在指定假設下等於最佳化互資訊。
- 翻轉與可見抹除有不同通道容量。
- 不對稱通道可能偏好非均勻輸入。
- 隨機編碼以典型性與配置建立存在性。
- Fano 與資料處理限制訊息錯誤趨零的速率。
- Blahut–Arimoto 最佳化有限通道並提供數值差距。
- 有限可靠性與語意目標各需明確評估。
練習
- 說明翻轉機率 0.9 與 0.1 的 BSC 容量為何相同,描述接收端如何重新標記輸出。
提示
反轉每個輸出。
- 對任意二元輸入機率推導 BEC 互資訊,不預設公平輸入。
提示
抹除保留原輸入熵。
- 將 Z 通道參數改成 0.1 與 0.7,比較最佳輸入機率與二分之一,解釋兩個熵項的競爭。
提示
最佳化輸出熵減加權列熵。
- 長度 100、碼率 0.8 的編碼通過翻轉機率 0.1 的 BSC,計算基本 Fano 訊息錯誤下界,說明它證明與未證明的事。
提示
使用 ,負值時保留零下界。
- 複製通道矩陣某一列並重跑容量,解釋容量為何不變,最佳輸入混合卻可能不再唯一。
提示
相同列產生相同條件輸出。
- 在相同總使用預算下比較重複長度 3 與 9,說明單位元錯誤較小,為何不能單獨判斷系統可靠傳送的資訊較多。
提示
同時計算訊息位元與錯誤。
參考文獻
- T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, Chapter 7 and the computational capacity/rate–distortion discussion. 出版社書籍與目錄.
- T. Weissman, “Communication and Channel Capacity,” Stanford EE276 Lecture 7 notes, 2024. 原始課程講義.
- T. Weissman, “Channel Coding Theorem: Converse Part,” Stanford EE276 Lecture 10 notes, 2024. 原始課程講義.
- L. X. Nguyen, A. D. Raha, P. S. Aung, D. Niyato, Z. Han and C. S. Hong, “A Contemporary Survey on Semantic Communications: Theory of Mind, Generative AI, and Deep Joint Source-Channel Coding,” IEEE Communications Surveys & Tutorials, 2025, DOI: 10.1109/COMST.2025.3616973. 已出版論文資料與作者版本.
檢查理解
本篇有 6 題練習。不看提示,你能解出來嗎?
前往練習 ↑下一篇 IT 05・微分熵與高斯通道 · 15 分鐘