噪聲通道能傳遞甚麼?
精簡的源編碼可減少傳送前的平均位元數,卻不能自行阻止通道改變位元。本節先計算一次通道使用中輸出透露多少輸入資訊,再研究一個小型糾錯碼。
定義 7.1.1
(二元對稱通道)
設輸入 ,噪聲位元 與 獨立,輸出為 ,其中 是模二加法。假設 ,。這是二元對稱通道:不論輸入為何,位元都以概率 翻轉。令 ;輸入分佈是與通道參數 分開選擇的。
我們要計算的量都是有限隨機變量的熵。
定義 7.1.2
(二元熵與互資訊)
對 ,定義二元熵
並以連續延拓約定 。對有限隨機變量,,而 。本節對數均以二為底,單位為位元。概率為零的輸入值對條件熵之和沒有貢獻。
一次使用的計算
定理 7.1.3
(一次使用的最大互資訊)
對上述通道,
對每個 ,取 可達到上界。
證明
(輸出分佈、條件熵與 的峰值)
輸出為一恰好發生於 或 。由獨立性,
因此 是公式中的第一項熵。給定任一輸入後,輸出分佈只是 的可能重標記,所以 。對 ,, 先增至 再遞減。由端點的連續值可知 。取 使輸出均勻,故達到上界。
證明透視
通道和輸入各司其職
與 的獨立性用了兩次:一次計算輸出分佈,一次說明給定 時的條件輸出分佈就是(可能重標記的)噪聲分佈。關鍵一步是 與 無關,所以對輸入最大化 就化為只最大化 。論證之所以能收結,是因為無論 為何, 時 都等於 ;當 ,每個 都給出 ,上界 自然達到。輸出均勻本身不代表它透露輸入;還須扣除條件不確定性。
這是一次使用的互資訊最大值。將它與長區塊可靠傳輸速率連結,需要另行證明有相應假設的編碼定理;本節沒有證明該定理。互資訊是聯合分佈的平均性質,並不表示單個觀察位元有小數個可能值。
端點與數值例子
時 ; 時 。兩者每次使用的最大互資訊都是一位元,因為已知的確定翻轉可逆。 時,輸出與輸入獨立,任何 都有 。因此 的圖像關於 對稱,並非在整個 上單調遞減。
例題 7.1.4
(四分之一的位元翻轉)
若 且輸入公平,輸出也公平, 位元,因為 。若 ,輸入為常數,而 ,故互資訊為零。輸出的隨機性本身並非關於常數輸入的資訊。
例題 7.1.5
(端點 :每個位元都翻轉)
此時 ,故 ,。給定 後輸出完全確定,所以 。因此 ,在 時為一位元,與 一致。接收者只需把每個位元取補。
常見錯誤
(互資訊並非隨翻轉概率單調變化)
容易把 看作通道有多差的量度。但 ,所以 的最大值 位元與 相同。最差的情況是 ,而不是 。
三次使用的重複碼
將訊息位元 傳送三次,即 ,並以多數決解碼。
命題 7.1.6
(多數決解碼的錯誤概率)
假設三個噪聲位元相互獨立,它們組成的向量與 獨立,且各自翻轉概率為 。則三次重複碼的多數決解碼出錯的概率為
證明
(計算重量為二或三的噪聲圖樣)
恰有至少兩位翻轉時解碼出錯。由獨立性,不論 為何,每個重量為 的噪聲圖樣的概率都是 。三種雙位翻轉及一種三位翻轉給出 。
時錯誤概率為 ,低於單次傳送的 。當 時嚴格較小,因為 ; 時兩者都是 。當 ,原來的多數決可能更差;若通道參數已知,先反轉收到的位元便可把有效翻轉概率變成 。
常見錯誤
(在不同傳輸率下比較錯誤概率)
重複碼每個訊息位元使用通道三次。它較低的錯誤概率因此並非與每位元只傳一次在相同傳輸率下的比較,本身也不說明編碼能多接近一次使用的值 。
例題 7.1.7
( 時的多數決解碼)
若不理會已知參數,錯誤概率為 ,比單次傳送的錯誤 更差。若先把每個收到的位元取補,便得到翻轉概率為 的通道,多數決解碼的錯誤概率變成 。
反例模式
邊際概率相同不代表錯誤獨立
假設三個噪聲位元都等於同一個翻轉概率為 的伯努利(Bernoulli)變量。每個位元仍以概率 翻轉,但只會全部翻轉或全部不翻轉。多數決錯誤概率因此是 ,可能與 不同:例如 時前者為 ,後者為 。上面的乘積計算用了各次使用之間的獨立性。
習題
快速檢查
(對 和任意 ,計算 及 。)
解答 · 答案
輸出均勻:。 和 都是一位元,所以 。
快速檢查
(對 、,寫出 的精確表達式。)
解答 · 答案
輸出為一的概率是 ,故 。
快速檢查
(計算 時三次重複碼的錯誤概率,並與 比較。)
解答 · 答案
錯誤概率為 。
快速檢查
(為何 時每個位元都翻轉,互資訊仍可以是正數?)
解答 · 答案
接收者可反轉這個已知的確定翻轉。公平輸入與其取補後的輸出互相確定,每次使用有一位元互資訊。
延伸閱讀
麻省理工開放式課程,資訊理論第八講 討論二元對稱通道及互資訊與通道編碼的關係;後者超出本節的一次使用證明。