937
技術社區[雲棲]
《偉大的計算原理》一通信係統
本節書摘來華章計算機《偉大的計算原理》一書中的第3章 ，［美］彼得 J. 丹寧（Peter J. Denning）
克雷格 H. 馬特爾（Craig H. Martell）著 羅英偉 高良才 張 偉 熊瑞勤 譯 更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
通信係統
通信係統是最簡單的信息係統，在1948年一篇名為《通信的數學理論》的文章中，香農提出了通信係統的第一個理論模型（Shannon 1948）（見圖3.3）。其本質是如下過程：消息源發送一條消息，編碼器按照編碼本規定為這條信息生成一個獨有的信號；信道作為中間媒介從源到端運載這個信號；接收端的解碼器使用同樣的編碼本將這個信號轉換成初始形式——消息就到達接收處了。香農的模型適用於任何使用編碼、解碼、傳輸、存儲或是查詢信號數據的係統，甚至可以作為科學發現的模型：將自然界看作現象（消息）的源頭，而傳輸媒介（即通道）就是探索的過程（Dretske 1981）。
圖3.3 克勞德·香農（1916—2001）描述了一個信息係統模型，它是當今信息論的基石。消息源代表所有可能要發送的消息的集合，信道是存儲和運載信號的媒介，編碼是將消息轉換為信號，解碼是將信號還原為消息，編碼本包含了消息與信號互相轉換的規則，噪聲是指任何改變信號的事物
噪聲是通信模型中的一個重要元素。任何在傳輸通道中改變信號，從而導致解碼出錯誤消息的幹擾都是噪聲。通信技術中噪聲的例子比比皆是：霧氣和黑暗幹擾了船隻之間的信號通信；電報站之間過長的距離減弱了信號的強度；雷電幹擾了調頻廣播的傳輸；DVD上的劃痕會導致讀取失敗；環境的聲音淹沒了演講的聲音。
值得注意的是，在通信係統中，編碼和加密是不一樣的。加密是一個額外的步驟，在消息到達編碼器之前將消息轉換成密文，這樣隻有擁有密鑰的接收器才能夠讀取消息。在這種情況下，通信係統的工作就是將密文準確地傳輸給接收方，如果接收方具有密鑰則可以進行解密。
正如前文所提到的，香農將他的數學模型在二進製位上進行標準化，他認為所有的信號都能夠用二進製位表示，這一過程在字麵上被稱為數字化，即將模擬信號轉變為數字信號。數字化並不是生成信息的一個完全拷貝，而是一種近似化過程，因為其常常會丟失一些信息。顯而易見的例子有許多，如物體邊緣參差不齊的像素化照片，同時也有一些情形是非常微妙不那麼直觀的。物理現象中的定量分析，比如火星探測器的軌道位置，實際上不能通過計算機的有限運算進行精確表達。舍入誤差會隨著計算步驟而逐漸累加，導致整個計算的精確度出現問題，使火星著陸器麵臨危險。更糟糕的是，一些計算步驟會放大錯誤。如兩個幾乎相等的數可以認為它們的差近似為零，在用這個近似的差除另一個數時會導致嚴重錯誤。數學軟件的設計師設計了很多巧妙的技術，來防止這些數字化錯誤破壞計算結果。
Harry Nyquist可謂當代的香農，他指出了上述普遍規律中的一個重要例外：通信係統可以免受數字化錯誤的影響（Nyquist 1928）。每一個連續、帶寬有限的信號都可以無損地數字化，隻要用至於兩倍於最高頻率的采樣率進行采樣。例如音頻光盤（CD），為了使得質量沒有明顯損失，要每秒記錄44?100（44.1千赫）個采樣點，因為幾乎沒人能聽到高於22?000赫茲的聲音。
香農認為，由於我們可以對任何信號進行數字采樣，同時也由於真實的通信係統具有有限的帶寬，那麼將通信模型限製為二進製序列，不會有任何損失。這不但簡化了數學運算，而且使得這一結論適用於所有實際信道。
作為一個實例，一段簡單的編碼就可以說明通信模型的各種特性。假設一個消息源隻傳輸消息的1/4，我們把完整的消息定為A、B、C、D，為這些字母分配2位的編碼：
A：11
B：10
C：01
D：00
隻能表示四種消息的編碼在自然界中並不少見，我們細胞中的DNA序列就是一種隻使用四個字母的自然消息源——G、A、T和C，它們是DNA中四種核苷酸的首字母。
如果消息源想傳輸序列“CAB”，那麼就在信道中傳輸“011110”這個位序列，接收端會逆向這個過程，即在編碼本中查找每一對位碼然後輸出對應的字母。
在任何關於編碼的討論中，我們都需要在編碼長度（碼字的位長）和信道抗擾能力間做出權衡。短的編碼更高效、傳輸更快並且占用較小的存儲空間，然而短編碼非常容易受到噪聲的幹擾，信道中僅僅一位的改變就會將碼字完全改變。例如，如果信道將A的第一個位編碼變為0，接收端就會收到01，然後解碼成C而不是A。其中一個解決方案就是使用奇偶校驗位來提示接收端是否收到錯誤信息，當原編碼中有偶數個1時，奇偶校驗位為偶數，反之則為奇數。下述編碼就是在原始編碼中添加第3位為奇偶校驗：
A：110
B：101
C：011
D：000
現在信道噪聲將A的第一位編碼變成0後，接收端收到010時，會發現編碼錯誤，因為010這個編碼是無效編碼。概括來說，1位的錯誤會導致1的數量變為奇數，從而標識這是一個未編碼的模式。
然而，單一的奇偶校驗位並不能標識出哪一位被改變了。上例中，接收端知道010是一個無效的編碼，但是並不知道這三個編碼（A、C或者D）中的哪一個被這個位錯誤改變了。通過添加冗餘的編碼，解碼器不僅可以檢測是否有錯誤編碼，還可以定位具體受影響的消息位。試想下麵的例子，在原來編碼的基礎上添加了3個位：
A：11111
B：10010
C：01001
D：00100
這個編碼滿足如下準則：加上額外的編碼位，每一個碼字都與別的所有碼字至少有3位不同。若有1位發生錯誤，接收端收到編碼後會發現這個錯誤編碼與正確編碼隻有1位不同，但是與其他的字母編碼卻有2位甚至更多的不同。這樣解碼器就可以檢測並修正隻有1位發生錯誤的編碼情況。
通信工程師理查德·海明（Richard Hamming）在1950年首先提出碼字之間的距離計算方式。兩個碼字之間的距離就是不同位碼的個數，這就是後來有名的“海明距離”。海明指出，若要糾正k個字符，編碼就必須包含足夠的位使得碼字之間的最小距離至少為2k + 1。他也發明了一係列編碼，也就是現在的海明碼。海明碼在2k - 1位的碼字中嵌入k個校驗碼，然後使用一種簡單的方法來構造電路用以將受損的比特位轉換為原來的編碼值。最有名的一種海明編碼是（7，4）編碼，在4個數據位中嵌入3個校驗位，構成7位的編碼。在計算機處理器和存儲器之間傳輸數據時，海明碼被廣泛用於糾錯。
當噪聲在碼位上隨機分布時，海明碼能夠正常工作。然而，在某些信號中噪聲可能會爆發性地出現，比如日暈會影響某些深空信號數秒，光碟上的劃痕會損壞一係列鄰近的凹點，這些噪聲被稱為突發錯誤。另一種類型的編碼——Reed-Solomon碼便是用於檢測和消除突發錯誤的。它的數學計算更加複雜，但是也和海明碼一樣很容易用高速數字電路實現。
不同於信號，位並沒有實際物理意義。1位可以表示可察的任何兩種屬性之一。比如，工程師可能讓“1”代表激光束在DVD表麵某點的反射，而“0”則代表沒有反射；或者“1”代表晶體管的輸出是5V，而“0”則可能代表輸出是3V；或者“1”代表一特定頻率（比如400Hz）出現在一段音樂錄音中，而“0”則代表不是該頻率。位是一種抽象表達，用來聲明我們想讓係統做什麼。工程師將這些物理的“東西”（材料）進行組裝，用以完成所定義的功能。
物理係統中的信息總是要由物理狀態來表達，而讀寫和變換這些信息也需要花費時間和精力，因此通信和計算從來都逃脫不了物理世界的限製。計算機芯片工程師知道蓄熱和尺寸大小（芯片上所有電路元件的平均尺寸）等是影響他們能把電路做成多小的實際限製所在。同時每一個操作的時間消耗量則限製了可用時間內可計算的指令數。盡管新的算法在常規難題優化上有極大的改善，但計算量極大的一些問題仍然非常棘手，因為其物理運算所需要的時間大大超出我們的可等待範圍。例如，在目前廣泛應用的RSA加密係統中，為了尋找構成600位密鑰的兩個因子，即使利用目前最快的計算機也需要幾百年的時間。
這些年，存儲和計算能力呈指數增長。在香農發表其文章的同一年，在同一個地方——貝爾實驗室，電子計算機就開始使用新發明的晶體管來取代真空管。電路設計師能夠壓縮晶體管的大小，每18～24個月的時間就能夠無額外費用地將接近兩倍的晶體管放在同樣大小的物理空間。這種壓縮體積的過程已持續了50年，使得每10年就有了100倍計算能力的增加，這個趨勢就是廣為人知的摩爾定律。英特爾的創始人之一——戈登·摩爾（Gordon Moore）在他1965年的論文中首次描述了摩爾定律（Moore 1965）。
摩爾定律帶給人們兩種效應和影響。一個是驚人的計算能力，這對於20世紀40年代的計算科學先驅們來說如魔法一般；另一個是正如James Gleick（2011）所稱的如洪水般的信息。第一種影響——每一個傳輸和存儲信息的更小物理機製，都會導致第二種影響——信息的極大豐富。人們被巨量的信息淹沒，無法消化信息，變得不知所措。
龐大的計算能力導致了一個流行的錯覺，那就是計算機所操作的是位而非原子，因此計算結構在尺寸和能量上沒有物理限製（Negroponte 1996）。從物理的角度來看，這個概念是完全錯誤的。因為抽象的位必須依靠物理介質來記錄，而且機器要通過介質來獲取位信息。這個記錄的過程將我們帶回了原子世界：沒有它們我們無法完成計算。我們可以在極小的物理元件上進行快速的計算、傳輸和存儲，但從來無法消除它們的時間和功耗。
最後更新：2017-06-26 12:02:24