数字通信介绍(2)香农与信息论
原文地址:http://blog.sciencenet.cn/home.php?mod=space&do=blog&id=275997
上個世紀四十年代,半導體三極管還未發(fā)明,電子計算機也尚在襁褓之中。但是通信技術(shù)已經(jīng)有了相當?shù)陌l(fā)展。從十九世紀中葉,電報就已經(jīng)很普遍了。電報所用的摩斯碼(Morse Code),就是通信技術(shù)的一項杰作。摩斯碼用點和線(不同長度的電脈沖)來代表字母,而用空格來代表字母的邊界。但是每個字母的碼不是一樣長的。常用的字母E只有一個點。而不常用的Z有兩劃兩點。這樣,在傳送英語時,平均每個字母的碼數(shù)就減少了。事實上,摩斯碼與現(xiàn)代理論指導下的編碼相比,傳送速度只差15%。這在一百五十多年前,是相當了不起了。
除了用點,劃來表示兩個狀態(tài)外,后來的電報也用極性相反的電流來代表這兩個狀態(tài),從而使“點”和“劃”都能用短的脈沖來表達,加快了傳送速度。愛迪生更發(fā)明了用四個不同的電流值來同時傳輸兩路電報。這和今天用的數(shù)字調(diào)幅(ASK)很像,只是沒有載波而已(見前文《數(shù)字通信介紹(1) 調(diào)制》)。另一方面,電話在二十世紀初也迅速發(fā)展。電話公司通過在不同載波上的調(diào)制,可以用一路電線傳輸多路電話。
在二次世界大戰(zhàn)時,雷達和無線電在軍事上廣泛應(yīng)用。無線電受各種噪聲的干擾很厲害,這也給通訊技術(shù)提出了新的課題。各種不同的調(diào)制方式也紛紛問世。于是就出現(xiàn)了這樣一個問題:給定信道條件,有沒有最好的調(diào)制方式,來達到最高的傳送速率?
在前文《數(shù)字通信介紹(1) 調(diào)制》的結(jié)尾談到:“傳輸速率是波特率與每波特所含比特數(shù)的乘積。波特率受頻寬的限制,而每波特所含比特數(shù)受噪聲的限制。”前一個限制,由那奎斯特(Harry Nyquist)在1928年漂亮地解決了。而后一個問題則更復雜。1928年,哈特利(R. V. L. Hartley)首先提出了信息量的概念,并指出編碼(如摩斯碼)在提高傳送速度中的重要作用。但是他未能完整定量地解決這個問題。二戰(zhàn)期間,維納(Norbert Wiener)發(fā)展了在接收器上對付噪聲的最優(yōu)方法。但是傳輸速率的上限還是沒有進展。
在這種情況下,香農(nóng)(Claude E Shannon)在1948年發(fā)表了《通信的一個數(shù)學理論》(C. E. Shannon, A Mathematical Theory of Communication”, The Bell System Technical Journal, Vol. 27, pp. 379-423, 1948 http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf),完整地解決了通訊速度上限的問題。“信息論”(Information Science)從此誕生。
香農(nóng)(1916 – 2001)可說是二十世紀最偉大的科學家之一。他二十歲就以數(shù)學和電子工程雙學位畢業(yè),進入MIT讀研究生。一年以后(1937年),他的碩士論文開創(chuàng)了使用布爾邏輯(Boole’s Logic)分析電子計算機線路的途徑。布爾邏輯今天仍是分析數(shù)字電路的基本工具。1940年,香農(nóng)以題為“理論遺傳學的代數(shù)”的論文得到博士學位,到數(shù)學物理研究的圣地普林斯頓高等研究院任職。后來他轉(zhuǎn)任貝爾實驗室繼續(xù)研究工作。除了信息論外,香農(nóng)在加密理論,取樣理論等領(lǐng)域都有開創(chuàng)性的貢獻。他還活躍于人工智能,計算機等領(lǐng)域。他1956年到MIT任教,直到1978年退休。
香農(nóng)雖然是數(shù)學出身,卻十分重視直覺。他的同事評價說,香農(nóng)最擅長的就是把一個復雜的問題簡化,去掉無關(guān)緊要的細節(jié)而保留關(guān)鍵的問題。在他創(chuàng)立信息論的工作,就是一個非常優(yōu)美的例子。我以為,他的原始論文比 我所見到過的所有教科書上的推導都要直觀易懂。以下,就簡要地介紹一下這個工作【注一】。
要建立信息理論,首先要能夠度量信息。信息是由信號傳播的。但是信息與信號有本質(zhì)的區(qū)別。所以如何度量一個信號源的信息量,就不是簡單的問題。從直覺上說,如果一個信號源發(fā)出不變的符號值(比如總是1),它是沒有信息量的,因為它沒有告訴別人任何東西【注二】。而且如果信號源發(fā)出的符號值是變化的但是可以預計的(比如圓周率的數(shù)字序列),那也是沒有信息量的,因為我不需要接受任何東西,就可以把這些符號值重復出來。而且,即使信號源發(fā)出的符號不是完全可確定的,它的信息量也和“確定”的程度有關(guān)。例如,如果一個地方90%的時候是晴天,氣象報告就沒有多大用處。而如果50%的時候是晴天其余時候下雨,人們就需要氣象報告了。
從這點出發(fā),香農(nóng)就把信息量與信號源的不確定性,也就是各個可能的符號值的幾率分布聯(lián)系起來。他從直觀上給出了信息量需要滿足的幾個簡單的數(shù)學性質(zhì)(如連續(xù)性,單調(diào)性等),而給出了一個唯一可能的表達形式。
那么這樣定義的信息量與我們通常所說的數(shù)據(jù)量,也就是需要多少比特來傳送數(shù)據(jù),有什么關(guān)系呢?(比特就是二進制數(shù)據(jù)的位數(shù))。為此,我們來看看一個含有固定符號數(shù)的序列(也就是信號或碼字)。由于每個符號值的出現(xiàn)是隨機的,這樣的序列就有很多可能性。顯然,每個可能的符號在序列中出現(xiàn)次數(shù),對于所有可能序列的平均值正比于符號出現(xiàn)的幾率。我們把每個符號出現(xiàn)次數(shù)“正好”等于其次數(shù)平均值的序列叫做“典型序列”,而其他的就叫作“非典型序列”。而數(shù)學上可以證明,當N趨于無窮大時,“非典型序列”出現(xiàn)的幾率趨于零。也就是說,我們只要注意“典型序列”就行了。而典型序列的個數(shù),就是它們出現(xiàn)概率的倒數(shù)(因為總概率為1)。而碼字所攜帶的數(shù)據(jù)量,就是它的個數(shù)以2為底的對數(shù)?!咀⑷克?#xff0c;這樣的分析就得出了序列所含的數(shù)據(jù)量。除以序列的長度,就得到每個符號所含的數(shù)據(jù)量。而這個結(jié)果恰好就等于上面所說的信息量!
至此,香農(nóng)開創(chuàng)性地引入了“信息量”的概念,從而把傳送信息所需要的比特數(shù)與信號源本身的統(tǒng)計特性聯(lián)系起來。這個工作的意義甚至超越了通信領(lǐng)域,而成為信息儲存,數(shù)據(jù)壓縮等技術(shù)的基礎(chǔ)。
解決了信號源的數(shù)據(jù)量問題后,我們就可以來看信道了。信道(channel)的作用是把信號從一地傳到另一地。在香農(nóng)以前,那奎斯特已經(jīng)證明了:信道每秒能傳送的符號數(shù)是其頻寬的一半。但問題是,即使這些符號,也不是總能正確地到達目的地的。在有噪聲的情況下,信道傳送的信號會發(fā)生畸變,而使得接收者不能正確地判斷是哪個符號被發(fā)送了。前文《數(shù)字通信介紹(1) 調(diào)制》中談到,對付噪聲的辦法是減少每個符號所帶的比特數(shù):
“而每個波特所含的比特數(shù),則是受噪聲環(huán)境的限制。這是因為當每個波特所含的比特數(shù)增加時,它的可能值的數(shù)目也增加。這樣代表不同數(shù)據(jù)的信號就會比較接近。例如,假定信號允許的電壓值在正負1伏之間。如果每個波特含一個比特,那么可能的值是0或1。這樣我們可以用-1伏代表0,用1伏代表1。而假如每波特含兩個比特,那么可能的值就是0,1,2,3。我們需要用-1伏,-0.33伏,0.33伏,1伏來代表著四個可能值。這樣,如果噪聲造成的誤差是0.5伏的話,那么在前一種情況不會造成解讀的錯誤(例如把-1V錯成了-0.5伏,它仍然代表0)。而在后一種情況則會造成錯誤(例如把-1V錯成了-0.5伏,它就不代表0,而代表1了)。所以,每個波特所含的比特數(shù)也是不能隨便增加的。以上兩個因素合起來,就構(gòu)成了對于數(shù)據(jù)傳輸速率的限制?!?br />
其實,除此之外,還有一個對付噪聲的辦法,就是在所有可能的符號序列中只選用一些來代表信息。例如,如果符號值是0和1,那么三個符號組成的序列就有8個:000,001,010,011,100,101,110,111。我們現(xiàn)在只用其中兩個來代表信息:000和111。這樣,如果噪聲造成了一個符號的錯誤,比如000變成了010,那我們還是知道發(fā)送的是000而不是111【注四】。這個方法的代價與前面的方法一樣,就是降低了傳送速率(原來可以送三個比特,現(xiàn)在只能送一個比特了)。這種選取特定序列,而不是使用所有序列的方法稱為編碼。以上的例子,是一個極為簡單的碼,遠非最優(yōu)。
可見,用降低速率來減少錯誤的方法有很多選項。那么怎樣才能達到速度和準確度之間最好的權(quán)衡呢?這看來是一個非常棘手的問題。然而,香農(nóng)卻得出了一個非常簡明的結(jié)論:對于一個信道,有這樣一個速率(稱為信道的容量):一定有一個方法能在這個速率以下傳送數(shù)據(jù)而誤差的幾率達到任意小;而超過這個速率的話,誤差的幾率就一定會大于某個下限。也就是說,香農(nóng)同時給出了無錯誤的條件下傳送速度的上限(即不可能超過)和下限(即有辦法達到),而這兩者是同一個值!
不僅結(jié)論出乎意料地簡單,香農(nóng)的證明也是如此。他的基本思路是:噪聲使得接收端收到信號后,對于所發(fā)送的信號仍然有個不確定性。也就是說,一個收到的序列可能對應(yīng)多個發(fā)送的序列。這個對應(yīng)的個數(shù)可以用上面講到的“典型序列”的個數(shù)來估計。因為如此,我們只能用這多個發(fā)送序列之中的一個來作為碼字,代表要傳送的信息,而其余都棄之不用。這樣才能避免混淆。所以,我們的傳送速率就要降低了【注五】。這個直觀解釋聽起來簡化得離譜。我們知道,隨機過程是很復雜的,怎么可能用平均值就搞定呢?然而,香農(nóng)在數(shù)學上嚴格地證明了這些結(jié)論。關(guān)鍵在于:他考慮序列長度趨向于無窮的情況。這樣,在樣本數(shù)量趨于無窮的情況下,實際情況偏于平均值的幾率趨向于零。所以說,香農(nóng)的簡化顯示他真正抓住了問題的關(guān)鍵。
對于通常遇到的信道,香農(nóng)定理說:信道容量(即最高傳送速率)與頻寬成正比,與信噪比的對數(shù)(底數(shù)為2)成正比。信噪比是在接收端信號功率與噪聲功率的比。增加發(fā)射功率能增加信噪比從而增加容量,但因為是對數(shù)關(guān)系,不是那么有效。而增加頻寬則是線性地增加容量。通常,頻率較低的頻道頻寬也小。如前一講中提到的調(diào)幅(AM)廣播,在幾百千赫頻段,頻寬是20千赫。而調(diào)頻(FM)廣播是在一百兆赫頻段,頻寬是200千赫。這就是調(diào)頻廣播音質(zhì)較好的主要原因【注六】。所以現(xiàn)代的數(shù)字通信服務(wù)不斷往高頻段擴展(目前已到2千兆赫)。當我們聽到某個服務(wù)能提供更高速率的時候,并不等于它使用了性能更好的技術(shù)。很可能它只是用了更寬的頻道而已。
香農(nóng)完美地給出了信道容量,所以有人說他“開創(chuàng)并結(jié)束”了信息論。但是香農(nóng)還是留下了一些困難的問題。比如,當信道隨時間變化時,應(yīng)用香農(nóng)理論就遠不是直截了當?shù)?。最重要?#xff0c;是為了達到香農(nóng)極限,我們處理的符號序列必須無限長。而實際上,信道編碼的長度受著傳送延遲和系統(tǒng)復雜性的限制。在這樣的限制下,如何達到最高的傳送速度?六十年后的今天,人們還在為此奮斗。這是下一講的題目了。
【注一】 為簡明起見,我們這里僅討論符號值是離散的情況。香農(nóng)的論文中還包括了連續(xù)值的情況。
【注二】 我們這里用的術(shù)語是:“信號”是攜帶信息的某種物理量(如電波,聲音,光等)?!胺枴笔且粋€信號單元,如一個字母,一個音節(jié),一個調(diào)制單位,一個脈沖等。信號可以看成是很多符號組成的一個序列。這樣的序列也叫“碼字”。
【注三】 例如,如果我們有八個可能的碼字(例如字母A到H),我們可以將其編號為0到7。用二進制數(shù)來代表這八個數(shù),需要3個比特(3 是8以2為底的對數(shù))。如0是000,6是110,7是111等。將這三個比特傳到接受者,接收者就能還原出碼字的編號,從而知道所傳送的碼字了。
【注四】 當然,如果錯了兩個符號,收到了011,那我們就認為發(fā)送的是111,而產(chǎn)生了錯誤。但是,錯兩位的概率要比錯一位小得多。如果錯一位的概率是0.001,那么錯兩位的概率就是0.000001.
【注五】 這里的敘述還是不很清楚,因為我想避免使用數(shù)學公式。有興趣的讀者應(yīng)該去讀香農(nóng)的原始論文,那里的解釋要好得多。
【注六】 當然,AM和FM是模擬調(diào)制,其性能離香農(nóng)極限差得遠。但基本道理還是一樣的。
總結(jié)
以上是生活随笔為你收集整理的数字通信介绍(2)香农与信息论的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Keil插件推荐及使用教程
- 下一篇: 数字通信介绍(4) OFDM为何如此热门