我們做到了！
“本課程的目的是讓你為你的技術未來做好準備。”
你好，哈布爾。 記住這篇精彩的文章 （+219、2588 個書籤、429k 閱讀次數）？
所以漢明（是的，是的，自我監控和自我糾正 ）有一個整體 ，根據他的講座編寫。 我們翻譯它，因為這個人說出了他的想法。
這不僅是一本關於 IT 的書，也是一本關於非常酷的人的思維方式的書。 「這不僅能促進正向思考，還能促進正向思考。 它描述了增加完成出色工作的機會的條件。”
感謝安德烈·帕霍莫夫的翻譯。
資訊理論是由 C. E. Shannon 在 1940 世紀 XNUMX 年代末提出的。 貝爾實驗室管理層堅持認為他稱之為“通信理論”，因為… 這是一個更準確的名字。 由於顯而易見的原因，「資訊理論」這個名字對大眾的影響要大得多，這就是香農選擇它的原因，也是我們至今所知道的名字。 這個名字本身就表明該理論涉及訊息，這使得它在我們深入資訊時代時變得重要。 在本章中，我將觸及該理論的幾個主要結論，我將提供該理論的一些個別條款的不是嚴格的，而是直觀的證據，以便您了解“信息理論”實際上是什麼，可以在哪裡應用它哪裡沒有。
首先，什麼是「資訊」？ 香農將訊息等同於不確定性。 他選擇事件機率的負對數作為當機率為 p 的事件發生時您收到的資訊的定量度量。 例如，如果我告訴你洛杉磯的天氣有霧，那麼 p 接近 1，這實際上並沒有給我們太多資訊。 但如果我說六月蒙特雷下雨，那麼消息中就會存在不確定性，並且會包含更多資訊。 可靠事件不包含任何訊息，因為 log 1 = 0。
讓我們更詳細地看看這個。 香農認為，資訊的定量度量應該是事件機率p的連續函數，對於獨立事件，它應該是可加的——兩個獨立事件的發生所獲得的資訊量應該等於由於聯合事件的發生而獲得的信息量。 例如，擲骰子和擲硬幣的結果通常被視為獨立事件。 讓我們把上面的內容翻譯成數學語言。 如果 I (p) 是機率為 p 的事件所包含的資訊量，則對於由機率為 p1 的兩個獨立事件 x 和機率為 p2 的 y 組成的聯合事件，我們得到
（x 和 y 是獨立事件）
這是函數柯西方程，對於所有 p1 和 p2 均成立。 為了求解這個函數方程，假設
p1 = p2 = p，
這給了
若 p1 = p2 且 p2 = p 則
ETC。 使用指數的標準方法擴展此過程，對於所有有理數 m/n，以下是正確的
根據資訊測度的假設連續性，可以得到對數函數是函數柯西方程式的唯一連續解。
在資訊理論中，通常取對數底為2，因此二進位選擇恰好包含1位元資訊。 因此，資訊可以透過以下公式來衡量
讓我們暫停一下並理解上面發生的事情。 首先，我們沒有定義「資訊」的概念，只是定義了其定量衡量的公式。
其次，這項衡量標準存在不確定性，儘管它相當適合機器（例如電話系統、廣播、電視、電腦等），但它並不能反映人類對資訊的正常態度。
第三，這是一個相對的衡量標準，取決於你目前的知識水準。 如果您查看隨機數產生器中的「隨機數」流，您會假設下一個數字是不確定的，但如果您知道計算「隨機數」的公式，則下一個數字將是已知的，因此不會包含資訊。
所以香農對資訊的定義在很多情況下都適合機器，但似乎不符合人類對這個字的理解。 正因為如此，「資訊理論」才應該被稱為「傳播論」。 然而，現在改變定義已經太晚了（這使得該理論最初流行，並且仍然使人們認為該理論涉及“信息”），所以我們必須忍受它們，但同時你必須清楚地理解香農對信息的定義與其通常使用的意思相差有多大。 香農的訊息涉及完全不同的東西，即不確定性。
當您提出任何術語時，需要考慮以下問題。 提議的定義（例如香農對資訊的定義）與您最初的想法有何一致以及有何不同？ 幾乎沒有術語能夠準確反映您先前對某個概念的看法，但最終，所使用的術語反映了該概念的含義，因此透過清晰的定義將某些內容形式化總是會帶來一些噪音。
考慮一個系統，其字母表由符號 q 和機率 pi 組成。 在這種情況下 平均資訊量 系統中的（其期望值）等於：
這稱為機率分佈 {pi} 系統的熵。 我們使用術語“熵”，因為相同的數學形式出現在熱力學和統計力學中。 這就是為什麼「熵」這個詞在其周圍創造了某種重要的光環，但這最終是不合理的。 相同的數學表示法並不意味著相同的符號解釋！
機率分佈的熵在編碼理論中扮演重要角色。 兩個不同機率分佈 pi 和 qi 的吉布斯不等式是該理論的重要結論之一。 所以我們必須證明
證明是基於一個明顯的圖，如圖所示。 13.I，這表明
並且只有當 x = 1 時才實現相等。讓我們將不等式應用到左側總和的每一項上：
若通訊系統的字母表由q個符號組成，則取每個符號的傳輸機率qi = 1/q並代入q，由吉布斯不等式得到
圖13.I
這意味著如果傳輸所有 q 個符號的機率相同且等於 - 1 / q，則最大熵等於 ln q，否則不等式成立。
對於唯一可解碼的程式碼，我們有卡夫不等式
現在如果我們定義偽機率
當然在哪裡 = 1，由吉布斯不等式得出，
並且應用一點代數（記住 K ≤ 1，所以我們可以去掉對數項，也許稍後會加強不等式），我們得到
其中 L 是平均代碼長度。
因此，熵是任何具有平均碼字長度 L 的逐個符號代碼的最小界限。這是無幹擾通道的香農定理。
現在考慮關於通訊系統局限性的主要定理，其中資訊作為獨立比特流傳輸並且存在噪聲。 據了解，一位正確傳輸的機率為 P > 1/2，傳輸過程中該位元值發生反轉（出現錯誤）的機率等於 Q = 1 - P。為了方便起見，我們假設錯誤是獨立的，並且每個發送位的錯誤機率相同，即通訊通道中存在「白噪聲」。
我們將一長串 n 位元編碼成一條訊息的方式是一位代碼的 n 維擴展。 稍後我們將確定 n 的值。 將由 n 位元組成的訊息視為 n 維空間中的一個點。 由於我們有一個 n 維空間 - 為簡單起見，我們假設每個訊息具有相同的發生機率 - 有 M 個可能的訊息（M 也將在稍後定義），因此發送任何訊息的機率為
（寄件者）
附表 13.II
接下來考慮通道容量的想法。 在不詳細討論的情況下，通道容量被定義為考慮到最有效編碼的使用，可以透過通訊通道可靠地傳輸的最大資訊量。 毫無疑問，透過通訊頻道可以傳輸的資訊多於其容量。 這可以透過二進制對稱通道（我們在我們的例子中使用）來證明。 發送位元時的頻道容量指定為
其中，與之前一樣，P 是任何發送位中沒有錯誤的機率。 當發送n個獨立位元時，通道容量由下式給出
如果我們接近通道容量，那麼我們必須為每個符號 ai, i = 1, ..., M 發送幾乎這個量的信息。考慮到每個符號 ai 出現的機率為 1 /米，我們得到
當我們發送 M 個同等機率的訊息 ai 中的任何一個時，我們有
當發送 n 位元時，我們預計會發生 nQ 個錯誤。 實際上，對於由 n 位元組成的訊息，我們在接收到的訊息中大約會出現 nQ 個錯誤。 對於較大的 n，相對變化（變化 = 分佈寬度，）
隨著n的增加，錯誤數的分佈將變得越來越窄。
因此，從發送端，我接收訊息 ai 發送並在其周圍繪製半徑為 的球體
它比預期錯誤數 Q 略大 e2（圖 13.II）。 如果n夠大，則訊息點bj出現在超出該球體的接收方一側的機率為任意小。 讓我們從發射器的角度來概述一下情況：從發射的訊息 ai 到接收的訊息 bj 的任意半徑，誤差機率等於（或幾乎等於）常態分佈，達到最大值的nQ。 對於任何給定的 e2，n 如此之大，以至於結果點 bj 在我的球體之外的機率與您想要的一樣小。
現在讓我們從您這邊看一下同樣的情況（圖13.III）。 在接收端，在n 維空間中，在接收點bj 周圍有一個半徑為r 的球體S(r)，這樣如果接收到的消息bj 在我的球體內，那麼我發送的消息ai 在你的球體內領域。
怎麼會出現錯誤呢？ 該錯誤可能發生在下表所述的情況：
圖13.III
在這裡我們看到，如果在圍繞接收點構建的球體中至少還有一個點對應於可能發送的未編碼訊息，則在傳輸過程中會發生錯誤，因為您無法確定傳輸的是哪一條訊息。 只有當與其對應的點位於球體中時，發送的訊息才是無錯誤的，並且給定程式碼中不可能有其他點位於同一球體中。
如果發送訊息 ai，我們有一個關於錯誤機率 Pe 的數學方程
我們可以把第二項中的第一個因素去掉，取1，這樣我們就得到了不等式
顯然那
最後
重新套用到右側的最後一項
當 n 夠大時，第一項可以根據需要取小，例如小於某個數字 d。 因此我們有
現在讓我們看看如何建構一個簡單的替換碼來編碼由 n 位元組成的 M 個訊息。 由於不知道如何準確地建構代碼（當時還沒有發明糾錯碼），香農選擇了隨機編碼。 為訊息中的 n 位中的每一位拋一枚硬幣，並對 M 則訊息重複此過程。 總共需要投擲 nM 次硬幣，所以有可能
具有相同機率 ½nM 的代碼字典。 當然，創建密碼本的隨機過程意味著存在重複的可能性，以及彼此接近的代碼點，因此可能是錯誤的來源。 必須證明，如果這種情況發生的機率大於任何選定的小誤差水平，則給定的 n 足夠大。
關鍵是香農對所有可能的密碼本進行了平均，以找到平均誤差！ 我們將使用符號 Av[.] 來表示所有可能的隨機碼本集合的平均值。 當然，對常數 d 進行平均會得到一個常數，因為平均每一項與總和中的所有其他項相同，
可以增加（M–1 變成 M）
對於任何給定的訊息，當對所有碼本進行平均時，編碼會遍歷所有可能的值，因此點位於球體中的平均機率是球體體積與空間總體積的比率。 球體的體積是
其中 s=Q+e2 <1/2 且 ns 必須是整數。
右邊的最後一項是這個總和中最大的。 首先，讓我們使用斯特林階乘公式來估計它的值。 然後，我們將查看前面項的遞減係數，請注意，當我們向左移動時，該係數會增加，因此我們可以：（1）將總和的值限制為幾何級數的總和這個初始係數，（2 ）將幾何級數從ns項擴展到無限項，（3）計算無限幾何級數的總和（標準代數，沒什麼意義）並最終獲得極限值（對於足夠大的n):
注意熵 H(s) 如何出現在二項式恆等式中。 請注意，泰勒級數展開式 H(s)=H(Q+e2) 給出了僅考慮一階導數並忽略所有其他導數而獲得的估計值。 現在讓我們組合一下最終的表達式：
哪裡
我們要做的就是選擇 e2 使得 e3 < e1，然後最後一項將任意小，只要 n 夠大。 因此，在通道容量任意接近 C 的情況下，可以得到盡可能小的平均 PE 誤差。
如果所有編碼的平均值具有足夠小的誤差，則至少有一種編碼是合適的，因此至少存在一個合適的編碼系統。 這是香農獲得的一個重要結果——“噪音通道的香農定理”，儘管應該指出的是，他證明了這一點是針對比我使用的簡單二元對稱通道更一般的情況。 對於一般情況，數學計算要複雜得多，但思想並沒有那麼不同，所以很多時候，透過特定情況的例子，你可以揭示定理的真正意義。
讓我們批評一下這個結果。 我們反覆重複：“對於足夠大的n。” 但n有多大呢？ 如果您確實想要既接近通道容量又確保正確的資料傳輸，則非常非常大！ 事實上，如此之大，以至於您將不得不等待很長時間才能累積足夠位的訊息以便稍後對其進行編碼。 在這種情況下，隨機碼字典的大小將非常巨大（畢竟，這樣的字典不能以比所有 Mn 位元的完整列表更短的形式表示，儘管 n 和 M 非常大）！
糾錯碼避免等待很長的訊息，然後透過非常大的碼本對其進行編碼和解碼，因為它們避免了碼本本身並使用普通計算。 從簡單的理論上講，此類程式碼往往會失去接近通道容量的能力，但仍保持較低的錯誤率，但當程式碼糾正大量錯誤時，它們表現良好。 換句話說，如果你分配了一些頻道容量用於糾錯，那麼大多數時候你必須使用糾錯能力，即每發送一條訊息就必須糾正大量的錯誤，否則你就浪費了這個容量。
同時，上面證明的定理仍然不是沒有意義的！ 它表明高效的傳輸系統必須對很長的比特串使用巧妙的編碼方案。 一個例子是飛越外行星的衛星； 當它們遠離地球和太陽時，它們被迫糾正資料區塊中越來越多的錯誤：一些衛星使用太陽能電池板，提供約 5 W 的功率，其他衛星使用核電源，提供大約相同的功率。 電源功率低，發射器碟形天線尺寸小，地球上接收器碟形天線尺寸有限，訊號必須傳播的距離很遠——所有這些都需要使用具有高水平糾錯能力的代碼來構建有效的溝通系統。
讓我們回到上面證明中使用的 n 維空間。 在討論中，我們表明球體的幾乎整個體積都集中在外表面附近 - 因此，幾乎可以肯定，發送的信號將位於圍繞接收信號構建的球體表面附近，即使具有相對這種球體的半徑很小。 因此，接收到的訊號在修正任意大量的錯誤 nQ 之後，結果任意接近無錯誤的訊號，這並不奇怪。 我們前面討論的連結容量是理解這現象的關鍵。 請注意，為糾錯漢明碼構造的類似球體不會相互重疊。 n 維空間中存在大量幾乎正交的維度，這說明了為什麼我們可以在空間中容納 M 個幾乎沒有重疊的球體。 如果我們允許小的、任意小的重疊（這在解碼過程中只會導致少量錯誤），我們就可以獲得空間中球體的密集放置。 漢明保證了一定程度的糾錯，香農保證了較低的錯誤機率，但同時保持了實際吞吐量任意接近通訊頻道的容量，這是漢明碼無法做到的。
資訊理論並沒有告訴我們如何設計高效的系統，但它確實為高效通訊系統指明了道路。 它是建立機器對機器通訊系統的寶貴工具，但如前所述，它與人類如何相互溝通幾乎沒有關係。 生物遺傳在多大程度上類似於技術通訊系統尚不清楚，因此目前尚不清楚資訊理論如何應用於基因。 我們別無選擇，只能嘗試，如果成功向我們展示了這種現象的機器性質，那麼失敗將指向資訊性質的其他重要方面。
我們不要離題太多。 我們已經看到，所有原始定義都或多或少必須表達我們原始信念的本質，但它們具有某種程度的扭曲特徵，因此不適用。 傳統上認為，最終，我們使用的定義實際上定義了本質； 但是，這只是告訴我們如何處理事物，並沒有向我們傳達任何意義。 假設方法在數學界如此受到青睞，但在實務上仍有許多不足之處。
現在我們將看一個智商測驗的例子，其中的定義就像你喜歡的那樣循環，因此會產生誤導。 創建了一個旨在測量智力的測驗。 然後對其進行修改，使其盡可能一致，然後將其發布，並以簡單的方法進行校準，以便測量的“智能”結果呈正態分佈（當然，在校準曲線上）。 所有定義都必須重新檢查，不僅是在第一次提出時，而且是在很久以後，當它們被用於得出的結論時。 定義邊界在多大程度上適合所解決的問題？ 在一個環境中給出的定義多久會被應用在完全不同的環境？ 這種情況經常發生！ 在生活中不可避免會遇到的人文學科中，這種情況發生得更頻繁。
因此，介紹資訊理論的目的之一，除了展示其有用性之外，還在於警告您這種危險，或者準確地向您展示如何使用它來獲得所需的結果。 人們早就注意到，最初的定義決定了你最終會發現什麼，其程度比看起來大得多。 初始定義需要您投入大量注意力，不僅在任何新情況下，而且在您長期工作的領域也是如此。 這將使您了解所獲得的結果在多大程度上是同義反覆而不是有用的東西。
愛丁頓的著名故事講述了人們用網在海裡捕魚的故事。 在研究了他們捕獲的魚的大小後，他們確定了在海裡發現的魚的最小大小！ 他們的結論是由所使用的工具決定的，而不是現實。
待續...
誰想幫助翻譯、排版和出版這本書 - 請寫在個人資訊或電子郵件中 [電子郵件保護]
對了，我們還推出了另一本很酷的書的翻譯—— )
我們特別尋找 那些願意幫忙翻譯的人 。 （換乘10分鐘，前20名已被佔用)
本書內容與翻譯章節
- 科學與工程藝術簡介：學會學習（28 年 1995 月 XNUMX 日）
- 「數位（離散）革命的基礎」（30 年 1995 月 XNUMX 日）
- 《電腦史 - 硬體》（31 年 1995 月 XNUMX 日）
- 《電腦史 - 軟體》（4 年 1995 月 XNUMX 日）
- 《電腦的歷史 - 應用》（6 年 1995 月 XNUMX 日）
- 「人工智慧 - 第 I 部分」（7 年 1995 月 XNUMX 日）
- 「人工智慧 - 第二部分」（11 年 1995 月 XNUMX 日）
- 《人工智慧III》（13年1995月XNUMX日）
- 《n維空間》（14年1995月XNUMX日）
- 「編碼理論 - 資訊的表示，第一部分」（18 年 1995 月 XNUMX 日）
- 「編碼理論 - 資訊的表示，第二部分」（20 年 1995 月 XNUMX 日）
- 「糾錯碼」（21 年 1995 月 XNUMX 日）
- 《資訊理論》（25年1995月XNUMX日）
- 「數位濾波器，第一部分」（27 年 1995 月 XNUMX 日）
- 「數位濾波器，第二部分」（28 年 1995 月 XNUMX 日）
- 「數位濾波器，第三部分」（2 年 1995 月 XNUMX 日）
- 「數位濾波器，第四部分」（4 年 1995 月 XNUMX 日）
- 「模擬，第一部分」（5 年 1995 月 XNUMX 日）
- 「模擬，第二部分」（9 年 1995 月 XNUMX 日）
- 「模擬，第三部分」（11 年 1995 月 XNUMX 日）
- 「光纖」（12 年 1995 月 XNUMX 日）
- 《電腦輔助教學》（16 年 1995 月 XNUMX 日）
- 《數學》（18年1995月XNUMX日）
- 《量子力學》（19 年 1995 月 XNUMX 日）
- 「創造力」（23 年 1995 月 XNUMX 日）。 翻譯：
- 《專家》（25年1995月XNUMX日）
- 「不可靠的數據」（26 年 1995 月 XNUMX 日）
- 《系統工程》（30 年 1995 月 XNUMX 日）
- 「你得到你所衡量的」（1 年 1995 月 XNUMX 日）
- （六月2，1995） 翻譯成 10 分鐘的片段
- Hamming，「你和你的研究」（6 年 1995 月 XNUMX 日）。
誰想幫助翻譯、排版和出版這本書 - 請寫在個人資訊或電子郵件中 [電子郵件保護]
來源： www.habr.com