Turbo碼啟示錄從默默無聞到廣泛應(yīng)用

Turbo碼啟示錄：從默默無聞到廣泛應(yīng)用科技日?qǐng)?bào)>>>特別關(guān)注/gb/stdaily/2004-07/03/content_269414.htm一見編譯十年以前，1993年在瑞士日內(nèi)瓦舉行的IEEE國(guó)際通信學(xué)會(huì)。會(huì)上兩位法國(guó)電機(jī)工程師克勞德?伯勞和阿雷恩?格萊維歐克斯聲稱他們發(fā)明了一種數(shù)字編解碼方案，可以實(shí)現(xiàn)事實(shí)上無誤碼而碼率與發(fā)射功率效率超出所有專家預(yù)期的傳輸。幾乎沒有專家相信他們的結(jié)果。這兩位法國(guó)人都是位于布萊斯特的布列塔尼國(guó)立高等電信學(xué)校的教授，當(dāng)時(shí)在信息理論領(lǐng)域都是名不見經(jīng)傳的。一些人想當(dāng)然地認(rèn)為他們的計(jì)算一定有什么錯(cuò)誤。結(jié)論看來如此不合常理以致一些專家懶得去閱讀這篇文章。似乎不可思議的是，當(dāng)其他研究人員開始試驗(yàn)重復(fù)其結(jié)果時(shí)，很快證明這些結(jié)論是正確的。于是編解碼理論專家認(rèn)識(shí)到這篇文章的重要。伯勞和格萊維歐克斯提出的糾錯(cuò)編碼方案是對(duì)的，這一方案就被命名為Turbo編碼，它對(duì)糾錯(cuò)編碼產(chǎn)生了革命性的影響。一開始，Turbo碼只是應(yīng)用于一些特殊場(chǎng)合，主要是用于衛(wèi)星鏈路。至少還有一次用于深度空間通信，現(xiàn)在這個(gè)技術(shù)要走上主流舞臺(tái)了。當(dāng)這個(gè)技術(shù)與下一代移動(dòng)電話結(jié)合，成百萬人就會(huì)用上它。這一技術(shù)會(huì)使手機(jī)或其它移動(dòng)設(shè)備有能力進(jìn)行多媒體數(shù)據(jù)，如視頻信號(hào)及圖形圖像信號(hào)的通信。由于在這種環(huán)境下通常信道噪聲嚴(yán)重，其它技術(shù)很難滿足要求。不僅如此，研究人員還在研究把Turbo碼用于數(shù)字音頻和視頻廣播，以及用于增強(qiáng)型無線互聯(lián)網(wǎng)，以提高數(shù)據(jù)傳輸速率。由于Turbo碼的這種巨大前景，它已經(jīng)成為通信研究的前沿。在全世界各大公司和大學(xué)的成百個(gè)小組都聚焦在這個(gè)領(lǐng)域。其中有電信巨子如法國(guó)電信、NTT(日本電話電報(bào)公司)、DoCoMo；有高技術(shù)公司巨頭如索尼、NEC(日本電氣)、朗訊、三星、愛立信、諾基亞、摩托羅拉和高通(Qualcomm);有硬件和芯片制造商如Broadcom、Conexant、ComtechAHA和STMi鄄croelectronics；還有新興高技術(shù)企業(yè)如Turbo鄄concept和iCodingTurbo碼其實(shí)只是實(shí)現(xiàn)了一件簡(jiǎn)單但了不起的事情———使工程師能夠設(shè)計(jì)出非常接近信道容量（即在一定發(fā)射功率電平下信道可傳輸?shù)拿棵氡忍財(cái)?shù)值的絕對(duì)最大容量）的系統(tǒng)。這一極限值是由當(dāng)時(shí)在貝爾實(shí)驗(yàn)室工作的著名的電機(jī)工程師和數(shù)學(xué)家，以信息論之父聞名于世的克勞德?香農(nóng)發(fā)現(xiàn)的。在1948年的一篇標(biāo)志性論文中，香農(nóng)（2001年去世）證明在使用正確的糾錯(cuò)碼的條件下，數(shù)據(jù)可以以接近信道容量的速率幾乎無誤碼地傳輸，而所需的功率卻十分低。在香農(nóng)這篇文章以前，工程師們認(rèn)為要減少誤碼，要么就得增加發(fā)射功率，要么就得反復(fù)發(fā)送同一段消息———就好像在人聲嘈雜的啤酒館里人們得大聲地反復(fù)呼叫要啤酒一樣。這成了近四十年工程界不斷努力的目標(biāo)，一直到伯勞和格萊維歐克斯在九十年代初做出了他們的發(fā)現(xiàn)為止。1993年他們提出Turbo碼概念時(shí)展示了在誤碼率為十萬分之一的情形下把實(shí)際功率和香農(nóng)理論的差距驚人地縮小為0.5分貝的可能。今天Turbo碼甚至還在繼續(xù)縮小這一已經(jīng)很小的差距。按照香農(nóng)奠基性的文章，克服困擾所有通信信道的噪聲的辦法是把要傳輸?shù)臄?shù)據(jù)劃分成一段一段的比特串，在每一段加上額外的比特，稱之為奇偶比特，這些碼在接收端可以幫助識(shí)別和糾正誤碼。數(shù)據(jù)比特加奇偶比特所形成的一組比特群稱之為編碼詞，通常表示一段字符、若干像素、一段聲音取樣或其他數(shù)據(jù)塊。IEEE的會(huì)士，麻省理工學(xué)院的電機(jī)系教授戴維?佛內(nèi)指出：香農(nóng)證明了對(duì)于一個(gè)正確的編碼詞集合———也就是說正確的編碼，有可能達(dá)到信道容量。但是，什么編碼可以實(shí)現(xiàn)這一點(diǎn)？香農(nóng)沒有回答。香農(nóng)從數(shù)學(xué)上證明了編碼是達(dá)到信道容量的手段，但他沒有給出如何構(gòu)建這樣的編碼的準(zhǔn)確方法。但香農(nóng)的工作提供了寶貴的啟示。香農(nóng)把編碼詞當(dāng)作（編碼）空間中的一個(gè)點(diǎn)。例如編碼詞011可以當(dāng)成三維空間中坐標(biāo)為x=0,y=1,z=1的一個(gè)點(diǎn)。多于三個(gè)比特的編碼詞可以看成多維空間的點(diǎn)。噪聲會(huì)擾動(dòng)一個(gè)編碼詞的比特，從而擾動(dòng)其在空間的坐標(biāo)，使其位置發(fā)生變化。如果兩個(gè)點(diǎn)位置靠近，其中一點(diǎn)被噪聲影響，這點(diǎn)就有可能正好落到另一點(diǎn)上，形成解碼錯(cuò)誤。因此，編碼詞之間的空間距離分得越開，噪聲就越難以造成誤碼。為了達(dá)到信道容量的傳輸極限，香農(nóng)證明應(yīng)該隨機(jī)地選取無限長(zhǎng)度的編碼詞。如果回到他提出的空間比擬，如果你能夠按照你的意愿使編碼詞盡可能隨機(jī)、盡可能長(zhǎng)，你就能把這些編碼詞在空間分布得盡可能彼此遠(yuǎn)離，自然一點(diǎn)錯(cuò)誤地落到另一點(diǎn)上的情況就難以發(fā)生?？上н@種隨機(jī)、冗長(zhǎng)的編碼是不現(xiàn)實(shí)的。首先編碼詞的數(shù)量會(huì)是天文數(shù)字，其次這樣做就要發(fā)射許多許多比特來表示一個(gè)編碼詞，這種編碼使用起來會(huì)非常慢。然而編碼的隨機(jī)性對(duì)Turbo碼仍舊是關(guān)鍵。編碼專家在開發(fā)現(xiàn)實(shí)世界可以使用的編碼時(shí)只能把香農(nóng)的理想隨機(jī)碼放在一邊。他們很快就開始利用巧妙地選擇奇偶比特，把編碼詞限制在一定值域來開發(fā)有效編碼，使編碼詞彼此之間不易混淆。例如我們有一個(gè)8比特的編碼詞（7位有效比特加一位奇偶比特）。假設(shè)我們保持每個(gè)編碼詞“1”的個(gè)數(shù)是偶數(shù)，并通過改變外加的奇偶比特來滿足這個(gè)要求?，F(xiàn)在如果任何一個(gè)比特，包括奇偶比特在內(nèi)被噪聲所干擾而發(fā)生改變，則接收端就會(huì)檢測(cè)出誤碼，因?yàn)槠媾紨?shù)不對(duì)，“1”的個(gè)數(shù)變成了奇數(shù)。這一方案可以檢測(cè)出誤碼卻不能糾錯(cuò)———我們無法知道是哪一個(gè)比特被改變了。為了糾錯(cuò)需要更多奇偶比特。編碼專家提出了許多越來越復(fù)雜的產(chǎn)生奇偶比特的方法。區(qū)塊碼(blockcodes)、海明碼(Hamming)、李德所羅門碼(Reed-Solomon)和卷積碼(convolutional)是幾種廣泛使用的編碼方案，其誤碼率都很低。然而，在這些編碼方案中計(jì)算復(fù)雜性問題困擾著編碼專家。當(dāng)人們估算對(duì)所收到的數(shù)據(jù)進(jìn)行解碼所需要的計(jì)算量及由此產(chǎn)生的成本時(shí)，計(jì)算復(fù)雜性問題就浮現(xiàn)出來。越接近香農(nóng)極限編解碼過程就越復(fù)雜，因?yàn)樾枰嗟钠媾夹ｒ?yàn)比特因而編碼詞變得越來越長(zhǎng)。例如，對(duì)于長(zhǎng)度為3個(gè)比特的編碼詞，所有不同詞匯總量?jī)H為23，即8個(gè)。要逼近信道傳輸極限，就可能需要長(zhǎng)度為1000比特的編碼詞，解碼器就得遍尋一個(gè)大得無法想象的集合———21000大約10301個(gè)編碼詞匯。而人類所能探索到的宇宙的原子總數(shù)也才是1080而已。結(jié)論只能是如果要設(shè)法用已有編碼方案，即使是最好的，來達(dá)到香農(nóng)極限下的可靠通信注定是不可能的。按照伊利諾伊大學(xué)電機(jī)系教授塔納的說法，現(xiàn)有編碼不可能達(dá)到香農(nóng)極限，因?yàn)橛?jì)算復(fù)雜性達(dá)到天文數(shù)字程度?？床坏娇朔@一壁壘的途徑。七十年代末，不少人認(rèn)為沒有希望解決這一問題。通過把編碼分成若干易于處理的“組件”Turbo碼解決了計(jì)算復(fù)雜性問題。和現(xiàn)有多數(shù)系統(tǒng)在發(fā)射端只有單個(gè)編碼器，接收端只有單個(gè)解碼器不同，Turbo碼在一端用兩個(gè)編碼器另一端用兩個(gè)解碼器。研究人員在60年代末發(fā)現(xiàn)傳輸數(shù)據(jù)通過兩個(gè)串接的編碼器可以使傳輸數(shù)據(jù)具有更強(qiáng)的抗誤碼能力———在這種情形下整體大于各部分之和。Turbo碼則利用兩個(gè)聯(lián)合工作的編碼器，不是串接而是并接。Turbo編碼過程一開始就把要傳輸?shù)臄?shù)據(jù)塊制成三份拷貝。第一份拷貝送到兩個(gè)編碼器之一然后通過卷積編碼器從數(shù)據(jù)比特計(jì)算出奇偶校驗(yàn)比特。第二份拷貝送到第二個(gè)編碼器，里面也有一份完全一樣的卷積編碼器。第二個(gè)編碼器得到的比特流次序和原來不同，是經(jīng)過一個(gè)交織器系統(tǒng)加擾的。然后由這個(gè)編碼器讀出經(jīng)過擾動(dòng)的比特流并從中計(jì)算出奇偶校驗(yàn)比特。最后發(fā)射器把原來數(shù)據(jù)的第三份拷貝和上面兩組奇偶校驗(yàn)碼一起沿著信道發(fā)送出去。整個(gè)過程的關(guān)鍵是交織器對(duì)比特順序的重組。這一重新排列增加了編碼詞的參差性；用空間概念理解相當(dāng)在比特空間把編碼詞之間的距離拉開了。按照伯勞的說法，重新排列的作用是在編碼中引入某種隨機(jī)行為。換句話說，交織器在發(fā)射的信息中加入了隨機(jī)特征，作用類似香農(nóng)的隨機(jī)碼。

但像其他編碼詞匯量很大的編碼系統(tǒng)一樣，Turbo碼也會(huì)碰到計(jì)算復(fù)雜性之墻。其實(shí)Turbo碼通常是用大約1000比特編碼詞工作，非常不利的長(zhǎng)度。沒有希望了嗎？如果在接受端只有一個(gè)編碼器，確實(shí)如此?？墒荰urbo碼用兩個(gè)分量解碼器繞過了復(fù)雜性問題。每個(gè)解碼器的作用都是獲取數(shù)據(jù)，在信道噪聲影響下，數(shù)據(jù)可能被破壞，所以兩個(gè)解碼器還要判斷所收到的每一比特?cái)?shù)據(jù)究竟更可能是“1”還是“0”。這有點(diǎn)像在屋子里猜外面否在下雨，而你又無法從窗戶里看到外面，也聽不到外面的聲音。這種情況下你沒有任何“跡象”作依據(jù)，也許只能靠拋硬幣看哪面沖上來進(jìn)行猜測(cè)?？墒侨绻隳芸吹教鞖忸A(yù)報(bào)，而且天氣預(yù)報(bào)說要下雨，情形又如何呢？還有，要是你突然聽到雷聲又如何呢？這些事件都會(huì)影響你的猜測(cè)。這時(shí)情形可以比拋硬幣有所改進(jìn)。你也許會(huì)說正在下雨的機(jī)會(huì)大一些，而且你可能帶把傘出門。每個(gè)turbo解碼器也考慮“跡象”來幫助其猜測(cè)收到的比特是“0”還是“1”。首先，檢驗(yàn)收到的比特的信號(hào)電平。許多解碼方案把收到的信號(hào)直接轉(zhuǎn)換成“0”或“1”，因此把非常有價(jià)值的信息拋棄了。模擬信號(hào)會(huì)產(chǎn)生漲落起伏，這會(huì)給我們關(guān)于每一比特的更多信息。Turbo解碼把信號(hào)轉(zhuǎn)換成整數(shù)，用其可以度量信號(hào)是“0”還是“1”的可信度。此外解碼器還觀察奇偶校驗(yàn)碼，從中可以得知所收到的比特是否有誤碼。這些分析的結(jié)果對(duì)于“猜測(cè)”每一比特非常有用。按照貝爾實(shí)驗(yàn)室的戴維?伽瑞特的話：Turbo碼從內(nèi)部看就是在比特判決過程中利用判據(jù)可靠性信息。這種比特可靠性用數(shù)字表示，稱之為對(duì)數(shù)似然性系數(shù)，其取值范圍例如可以在-7到+7之間。+7意味解碼器幾乎可以肯定該比特是“1”；而-5意味解碼器判斷該比特是“0”但不是完全有把握。（實(shí)際系統(tǒng)常常采用更大的間距，例如從-127到+127）盡管信號(hào)電平和奇偶校驗(yàn)是非常有用的“跡象”，但對(duì)做出判決仍嫌不夠。單一的解碼器還不能保證判決總是正確，常常產(chǎn)生錯(cuò)誤的碼流。解碼器會(huì)在編碼詞空間迷失，作為其數(shù)據(jù)解碼結(jié)果所選擇的編碼詞未必總是正確的。所以單一解碼器不能完成任務(wù)。但一個(gè)解碼器的判決可靠性信息對(duì)另一解碼器也是有用的，因?yàn)閮蓚€(gè)碼流的奇偶校驗(yàn)比特實(shí)際上是對(duì)同一組數(shù)據(jù)得出的；只不過比特順序排列作了改變。因此兩個(gè)解碼器實(shí)際上是在解同一問題，但觀察的視圖不同。這樣，兩個(gè)解碼器就可以用迭代的方式交換可靠性信息來改進(jìn)各自的解碼結(jié)果。要求就是把碼流內(nèi)容按照每個(gè)解碼器工作的需要重新排列順序，然后在兩個(gè)解碼器之間交換可靠性碼流。使得一個(gè)解碼器對(duì)某一特定比特做出的判決，例如強(qiáng)烈認(rèn)為該比特為“1”，這一信息能夠?qū)α硪唤獯a器對(duì)相應(yīng)比特的判決產(chǎn)生影響。就像在猜測(cè)是否下雨的那個(gè)比喻一樣，假如你看到你的同事拿著傘出去了，這對(duì)于影響你的猜測(cè)應(yīng)該是非常有用的信息。在Turbo解碼器的例子中，每個(gè)解碼器不僅有其自己的“觀點(diǎn)”，還得到了外界觀點(diǎn)的幫助來對(duì)每一比特做出判決。貝爾實(shí)驗(yàn)室數(shù)學(xué)研究中心的杰哈德?卡拉米說，就好像有一個(gè)精靈在給你信息，精靈在你耳邊悄悄告訴你每個(gè)比特為“1”或“0”的可信度有多大，這將幫助你做出判決。Turbo編解碼的核心是這一迭代過程，其中每一解碼器利用了另一解碼器在上一步解碼過程得到的結(jié)果。在若干次迭代（通常為4到10次）之后，兩個(gè)解碼器就在所有的比特的判定上一致了。這就意味解碼器不會(huì)在編碼詞空間迷失，從而克服了復(fù)雜性壁壘。加州理工大學(xué)的羅伯特?麥克艾立斯教授說“這是個(gè)分而治之的解決方案，把問題分解成兩個(gè)小一些的問題，然后再把結(jié)果拼起來”。伯勞指出：也可以從猜縱橫字謎的角度來理解Turbo解碼過程。假想A解決了一個(gè)縱橫字謎，要傳送給B。在一個(gè)無噪聲信道，只要傳送詞匯陣列就夠了。但在一個(gè)噪聲信道，陣列中的字母會(huì)被搞亂。當(dāng)B收到字謎答案時(shí)，許多詞無法辨認(rèn)。為了幫助B糾錯(cuò)，A可以把水平詞匯和豎直詞匯的“跡象”也傳給B。這是多余的信息，因?yàn)樽种i已經(jīng)解開了，但這確實(shí)對(duì)B有幫助。因?yàn)楹推媾夹ｒ?yàn)比特一樣，這一信息對(duì)可以放進(jìn)陣列的詞匯加了約束。這是一個(gè)二維問題，行的解有助于得到列的解，反之亦然，就好像在Turbo解碼中兩個(gè)解碼器互相幫助一樣?；仡?1年前，當(dāng)42歲的伯勞穿過日內(nèi)瓦會(huì)展中心的走廊時(shí)，從人們的肩膀上望過去看到許多出席者試圖弄懂他們的論文。在演講過程中年輕的博士生和老練的編解碼專家擠滿了演講廳，有些人擠在門邊。當(dāng)伯勞和格萊維歐克斯結(jié)束演講時(shí)許多人涌上來要求進(jìn)一步給出解釋，或者只是簡(jiǎn)單地握握手。讓懷疑者信服花了不少時(shí)間，伯勞回憶說數(shù)字通信需要很堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，一般都認(rèn)為糾錯(cuò)碼是數(shù)學(xué)家的領(lǐng)地。使伯勞和格萊維歐克斯取得突破的不是什么深?yuàn)W的定理，而是要解決現(xiàn)實(shí)世界電信問題的探求努力。在80年代末當(dāng)他們開始在編碼方案方面工作時(shí)他們驚訝地發(fā)現(xiàn)在電子學(xué)領(lǐng)域廣泛應(yīng)用的反饋原理在數(shù)字接收機(jī)研究中從來沒有得到應(yīng)用。在放大器中，輸出信號(hào)總有一小部分回饋到輸入端，以保持放大器的性能穩(wěn)定。伯勞和格萊維歐克斯想為什么這一方法在編解碼中就不能應(yīng)用？1991年他們第一次用計(jì)算機(jī)模擬實(shí)驗(yàn)他們的新編解碼方案，當(dāng)結(jié)果出來以后他們大吃一驚。伯勞說：“那時(shí)我每天都問自己是不是程序有什么毛病。”伯勞和格萊維歐克斯在確認(rèn)他們的結(jié)果無誤以后做的第一件事就是為他們的發(fā)明申請(qǐng)法國(guó)、歐洲和美國(guó)專利。當(dāng)時(shí)法國(guó)電信是他們研究工作的主要資助者。所以這家法國(guó)公司擁有Turbo編解碼的有關(guān)專利。但是發(fā)明者和他們所在的學(xué)校分享部分許可收益。（Turbo碼在亞洲沒有申請(qǐng)專利，因此在亞洲可以免費(fèi)使用。）法國(guó)電信要伯勞為這一編碼方案起一個(gè)商品名字。有一天他在電視里看汽車比賽時(shí)想出了現(xiàn)在的這個(gè)名字。他注意到新發(fā)明的編解碼利用解碼器的輸出來改進(jìn)解碼過程，和渦輪增壓(Turbocharger)用排出的氣體把空氣壓入引擎提高內(nèi)燃機(jī)效率的原理很類似，于是就起了“Turbo碼”這個(gè)名字。在日本Turbo碼已經(jīng)得到應(yīng)用，成為第三代移動(dòng)通信，其正式名稱為“通用移動(dòng)電信系統(tǒng)”（UMTS）標(biāo)準(zhǔn)的一部分。Turbo碼被用于圖像、視頻和郵件傳送。但語音仍用卷積碼。因?yàn)槠浣獯a時(shí)延小于Turbo碼。事實(shí)上解碼時(shí)延（解碼過程所用的時(shí)間）是Turbo碼的主要弱點(diǎn)。解碼所需的幾次迭代使時(shí)延在實(shí)時(shí)語音通信和其他需要即時(shí)數(shù)據(jù)處理的應(yīng)用場(chǎng)合（如硬盤數(shù)據(jù)存取和光傳輸?shù)龋┳兊脽o法接受。對(duì)于可以容忍解碼時(shí)延的應(yīng)用如深空通信，Turbo碼成為極有吸引力的選擇。事實(shí)上歐洲航天局去年9月發(fā)射的SMART—1，第一個(gè)深空探測(cè)器，就使用了基于Turbo碼的數(shù)據(jù)傳輸設(shè)備。歐空局在其他航天任務(wù)中也會(huì)選擇這種編碼，像定于今年發(fā)射的與彗星會(huì)合的羅塞塔（Rosetta）。美國(guó)國(guó)家宇航局也計(jì)劃在未來的任務(wù)中用Turbo碼提升通信的可靠性。第一個(gè)使用這種編碼的將是火星軌道勘測(cè)器。除了糾錯(cuò)，Turbo碼還可以提高移動(dòng)裝置的接收性能。提供CD質(zhì)量的數(shù)字音頻廣播和衛(wèi)星鏈路，像新成立的海事衛(wèi)星全球網(wǎng)公司，都在計(jì)劃把Turbo碼用于他們的系統(tǒng)。除了糾錯(cuò)，Turbo碼，或Turbo原理也對(duì)工程師解決通信中的一系列問題有所裨益。英國(guó)南安普敦大學(xué)電子與計(jì)算機(jī)科學(xué)系教授拉杰斯?漢索認(rèn)為Turbo碼激發(fā)了許多靈感。一個(gè)例子就是消除多徑效應(yīng)———一種由于信號(hào)在不同表面被反射到接收機(jī)引起的信號(hào)失真。Turbo碼可能可以為解決