動機
二元對稱通道具有足夠的對稱性,使漢明(Hamming)距離與漢明球計數成為自然的工具。一般的通道則可能擦除某些符號,可能對某些符號對的混淆多於其他符號對,也可能有多個輸入產生相同的輸出分佈。此時,單靠距離閾值已無法描述一個接收字作為某個候選輸入之證據的說服力。
資訊密度透過比較兩個概率來度量這種證據:一是在某個候選輸入下該輸出的概率,二是在整體輸入分佈下該輸出的概率。對於真實發送的符號對,其平均值趨近於互資訊。對於不相關的競爭輸入,一個簡單的期望界使大的取值不太可能出現。這兩個事實合起來,就給出每個有限無記憶通道的存在性編碼定理。
證明隨機地選取碼本,以說明存在一個好的確定性碼本。它並不提供快速編碼器、實用解碼器或強逆定理。我們還會證明必要的碼率界,且不假設實際碼字的各座標相互獨立;這一區別對幾乎所有有結構的碼都很重要。
定義
定義 3.4.1
(有限無記憶通道)
設 為非空有限輸入字母表與輸出字母表。通道是一個隨機矩陣 ,且對每個輸入 有 。其無記憶擴張的條件分佈為
這表示在給定整個輸入字的條件下各輸出相互條件獨立;它並不要求輸入分佈本身具有任何獨立性。
定義 3.4.2
(資訊密度)
對選定的輸入分佈 ,令 。所有對數均以二為底。在聯合概率為正的符號對上,定義資訊密度
對於滿足 但 的候選符號對,規定其資訊密度為負無限大。滿足 的輸出在基於 的隨機試驗中從不出現,解碼器可以對其一律拒絕。在概率為正的真實發送符號對上,資訊密度總是有限的。
定義 3.4.3
(碼、錯誤準則與容量)
一個 次使用的碼含有 個附有編號的訊息,一個把訊息映至 的確定性編碼器,以及一個輸出訊息編號的解碼器(也可以報告失敗)。平均錯誤概率是對均勻分佈的訊息與通道噪聲取平均。最大錯誤概率是各訊息條件錯誤概率中的最大值。碼率為 。定義
該最大值存在: 在緊緻的有限維概率單純形上連續,其中約定 。熵、條件熵、散度、數據處理不等式與 Fano 不等式已在前面各單元中證明,此處按有限字母表的約定使用。
定理/命題
定理 3.4.4
(每個更小的碼率都可達)
對每個 ,存在一列確定性碼,其碼率趨近於 ,且最大錯誤概率趨於零。只含一個訊息的零碼率碼總是存在的,包括 的情形。我們不斷言這些碼的構造或解碼具有任何效率保證。
定理 3.4.5
(不要求輸入獨立的弱逆定理)
對任意 、平均錯誤概率為 的 次使用碼,有
因此,每個錯誤概率趨於零的碼序列,其碼率的上極限至多為 。這一界並不證明在每個更大的碼率下錯誤概率都趨於一。
證明思路或證明
真實發送的符號對具有典型的資訊密度
證明
(真實符號對的集中性)
選取 使 ,並選取 使 。從 中獨立地生成 個碼字,並保留其訊息編號。當 足夠大時至少有兩個碼字。這個臨時的隨機列表容許出現重複;重複的情形會被納入錯誤分析,而不是被悄悄假定不存在。
當一個附有編號的碼字經 傳輸時,對隨機列表取平均,其各座標上的符號對相互獨立,聯合分佈為 。分組資訊密度是 個單座標密度之和。這些加項的均值為 ,且方差 有限,因為它們在正概率下的支撐集是有限的。Chebyshev 不等式給出
這裏利用碼字的隨機性是為了證明存在性。最終選定的固定碼本,在均勻選取訊息時,並不一定使其各座標相互獨立。
競爭字很少通過閾值
證明
(競爭字的似然比界)
解碼時,取分組資訊密度大於 的那個唯一編號;若沒有這樣的編號或有多個,則報告失敗。對於與通道輸出獨立的競爭字 ,其分佈為 ,而在對發送的隨機字取平均後,輸出的邊緣分佈為 。在輸出的支撐集上定義非負似然比 。由獨立性,
對每個概率為正的 ,條件概率為正的輸出也具有正的 概率,這就說明了儘管通道矩陣可能有零元素,最後一個等號仍然成立。由 Markov 不等式得 。
固定一個被發送的訊息編號。只有當其真實符號對未通過閾值,或某個競爭編號通過閾值時,才可能出錯。並集界不要求各競爭事件相互獨立。再對訊息編號取平均,得到平均錯誤概率的期望至多為
它趨於零。若兩個附有編號的碼字恰好相同,它們之間的衝突已包含在這些事件之中。
固定碼本並剔除高錯誤概率的訊息
證明
(剔除至最大錯誤)
隨機系綜是有限的,因此至少有一個確定性碼本,其平均錯誤概率至多為 。在該碼本中,至少有一半的訊息其個別錯誤概率至多為 ;否則平均值將超過 。保留這些訊息,捨棄其餘的。當解碼器原先的答案指向某個保留的訊息時予以保留,指向其他任何訊息時則改為失敗。這不會把原先對保留訊息的正確回答變成錯誤。
保留下來的碼最大錯誤概率至多為 ,且至少含有 個訊息。其碼率與 至多相差 ,而 趨於 。因此最大錯誤概率趨於零,而漸近碼率沒有損失。當 足夠大時,這一錯誤概率小於二分之一,這也排除了保留碼字中出現重複:兩個相同的發送字具有相同的輸出分佈,所以它們被正確識別的兩個概率不可能都超過二分之一。
證明透視
三個概率空間與連接它們的閾值
三個概率空間各司其職,每個假設都只在其中一處進入。真實符號對的估計是對隨機碼字與通道噪聲取平均。此時各座標對互相獨立,分佈為 ,所以無記憶性與乘積輸入分佈使區塊資訊密度成為 個獨立項之和;Chebyshev 不等式只需要有限方差,而有限字母表正好提供這一點。
競爭字的界使用另一個與輸出獨立的隨機字。關鍵的一步是:這種獨立性使 恰好成立,所以 Markov 不等式給出 ,無須再知道通道的任何結構。閾值 是平衡兩個估計的唯一參數:它低於真實符號對的典型密度,又高到使約 個競爭字仍然不能通過,這之所以可能,是因為 。只有在這些平均之後才選定一個確定性碼本,剔除步驟再只對通道噪聲界定錯誤。論證中沒有任何地方聲稱最終碼本的各座標互相獨立。
約束任意固定碼所能攜帶的資訊
證明
(弱逆定理)
現在考慮任意固定的編碼器及其可能相關的輸入字 。無記憶條件分佈給出
第一個等式來自對每個輸入字上乘積條件分佈的熵取平均。不等式來自熵的鏈式法則以及條件不會增加熵這一事實。兩式相減得 ,因為每個座標都有某個輸入分佈,屬於容量最大值所容許的範圍。
令均勻分佈的訊息為 ,解碼器的輸出為 。馬爾可夫(Markov)鏈 給出 。Fano 不等式給出 ,其中包括可能的失敗輸出。由於 ,把兩個陳述合併便得到所述的逆定理。最大錯誤概率的保證同時也界住了平均錯誤概率,所以它無法規避這一限制。
例題詳解
例題 3.4.6
(擦除通道與一個明確的存在性估計)
一個二元擦除通道以概率 顯示輸入,否則返回一個不同於輸入符號的擦除符號,且每次使用相互獨立。對任意輸入分佈,,所以 ,容量為每次使用 位元,在公平輸入下達到。
對該公平輸入,資訊密度在被顯示的符號上為一,在擦除上為零,故其方差為 。取目標碼率 與 。證明給出,存在某個固定碼本,其平均錯誤概率至多為 ,剔除後至多為其兩倍。這一估計在小分組長度下較為粗略,但它明確地趨於零。它並沒有給出所承諾的碼本,也沒有建立高效的實現。
例題 3.4.7
(均勻輸入不一定使容量最大)
設輸入為 ,其中 總是產生輸出零, 總是產生輸出一。該通道是確定性的,所以互資訊等於輸出熵。均勻輸入給出輸出概率 ,互資訊為 。改為以各二分之一的概率選取 ,且從不使用 。此時輸出是公平的,互資訊為一;因輸出字母表是二元的,這就是容量。一個與另一輸入行為完全相同的額外輸入標籤,並不會自動提供另一個可區分的訊息符號。
例題 3.4.8
(無記憶的輸出並不迫使輸入獨立)
取無噪聲二元通道,其容量為一。選取一個公平位元 ,令每個輸入座標都等於 。每個輸出座標是公平的,所以 ,但整個輸出字的熵僅為一,因為它要麼全為零,要麼全為一。因此 ,而不是 。逆定理正確地使用了不等式,並適用於這個重複編碼器。若以未經論證的輸入獨立性假設取代這個不等式,就會誇大實際碼所攜帶的資訊。
常見錯誤
反例模式
單座標噪聲分佈相同並不能證明通道無記憶
假設把同一個公平位元 加到所傳輸二元分組的每一位上。單獨看每個座標,它都像一個完全有噪聲的二元通道。然而接收者看到的要麼是整個字,要麼是它的補。選取第一位為零的碼字,用其餘 位表示訊息。接收到的第一位揭示了 ,所以所有位都可以被糾正,錯誤概率為零,碼率為 。噪聲在分組內是相關的,所以乘積條件分佈不成立;若由單座標邊緣分佈得出容量為零的結論,就是錯誤的。
常見錯誤
(證明不是一種構造)
該定理同樣沒有斷言均勻輸入是最優的,確定性通道的例子已說明這一點。其指數規模的隨機列表也不構成實用的編碼算法。解碼器可以把接收字與每個附有編號的碼字比較;證明的目標是在某一碼率下的存在性,高效的構造則需要另外的工作。
反例模式
平均錯誤概率小並不約束每個訊息
聲稱:若一列碼的平均錯誤概率趨於零,則其最大錯誤概率也趨於零。取無噪二元通道與 個訊息,每個訊息以它自己的 位字發送;解碼器除把輸出 映至 的訊息以外都正確。於是訊息 總被解錯,其他訊息全被解對,平均錯誤概率為 ,最大錯誤概率卻對每個 都是 。修正方法是剔除:捨棄錯誤概率超過平均值兩倍的訊息(這裏只有 ),剩下的碼最大錯誤概率為零,碼率損失至多 。
總結
對有限無記憶通道,容量是輸入與輸出之間互資訊的最大值。資訊密度的集中性與似然比的界證明所有更小的正碼率都是可達的。固定碼本並剔除高錯誤概率的訊息,得到最大錯誤概率意義下的可靠性。Fano 不等式與無記憶熵恆等式證明了弱逆定理,即使編碼後的輸入是相關的亦然。
練習
快速檢查
(證明:容量為零當且僅當每個輸入符號都誘導出相同的輸出分佈。)
把容量寫成相對於輸出混合分佈的散度的平均。
解答
若各行都相同,則對任意輸入分佈,輸入與輸出都獨立,所以互資訊為零。反之,若有兩行不同,讓它們對應的輸入取相等概率。互資訊是這兩個分佈各自相對於輸出混合分佈的散度的平均值。散度非負,且僅當分佈相同時為零,所以至少有一個為正,互資訊為正。因此容量的最大值為正。
快速檢查
(為甚麼在系綜論證中,競爭的隨機碼字與輸出獨立,而被發送的隨機碼字則不獨立?)
想一想輸出由哪些隨機變量產生。
解答
在給定被發送的編號的條件下,輸出由該編號的隨機字與新的通道噪聲產生。每個不同編號的字都與這兩者獨立地抽取。被發送的字與輸出由通道聯繫在一起,聯合分佈為 ;若把這個聯合分佈換成獨立的乘積分佈,就會破壞真實符號對的集中性論證。
快速檢查
(若目標碼率是固定的 ,已證明的逆定理給出平均錯誤概率怎樣的漸近下界?它是否迫使錯誤概率趨於一?)
以 整理逆定理。
解答
重排得 ,其中 。若 ,則下極限至少為 。除了容量為零的特殊情形外,這一般小於一。強逆定理的證明需要這一不等式之外的進一步推理。
快速檢查
(解釋為甚麼保留至少一半的訊息在漸近意義下不損失碼率,儘管它可能在絕對數量上去掉很多訊息。)
比較 與 。
解答
把 換成不小於 的數,至多使 減少一,因此至多使碼率減少 。這一損失隨分組長度趨於零。直接計算被去掉的訊息數,忽略了碼率使用的是訊息數的對數。