信道編碼，也叫差錯(cuò)控制編碼，是所有現(xiàn)代通信系統(tǒng)的基石。

幾十年來，信道編碼技術(shù)不斷發(fā)展，不斷逼近香農(nóng)極限，推動(dòng)著人類通信邁過一個(gè)又一個(gè)頂峰。

今天，我就帶大家一起回顧它波瀾壯闊的一生。

所謂信道編碼，就是在發(fā)送端對(duì)原數(shù)據(jù)添加冗余信息，這些冗余信息是和原數(shù)據(jù)相關(guān)的，再在接收端根據(jù)這種相關(guān)性來檢測(cè)和糾正傳輸過程產(chǎn)生的差錯(cuò)。

這些加入的冗余信息就是糾錯(cuò)碼，用它來對(duì)抗傳輸過程的干擾。

1948年，現(xiàn)代信息論的奠基人香農(nóng)發(fā)表了《通信的數(shù)學(xué)理論》，標(biāo)志著信息與編碼理論這一學(xué)科的創(chuàng)立。

根據(jù)香農(nóng)定理，要想在一個(gè)帶寬確定而存在噪聲的信道里可靠地傳送信號(hào)，無非有兩種途徑：加大信噪比或在信號(hào)編碼中加入附加的糾錯(cuò)碼。

這就像在嘈雜的酒吧里，酒喝完了，你還想來一打，要想讓服務(wù)員聽到，你就得提高嗓門（信噪比），反復(fù)吆喝（附加的冗余信號(hào)）。

但是，香農(nóng)雖然指出了可以通過差錯(cuò)控制碼在信息傳輸速率不大于信道容量的前提下實(shí)現(xiàn)可靠通信，但卻沒有給出具體實(shí)現(xiàn)差錯(cuò)控制編碼的方法。

克勞德·香農(nóng)

人類在信道編碼上的第一次突破發(fā)生在1949年。

R.Hamming和M.Golay提出了第一個(gè)實(shí)用的差錯(cuò)控制編碼方案。

受雇于貝爾實(shí)驗(yàn)室的數(shù)學(xué)家R.Hamming將輸入數(shù)據(jù)每4個(gè)比特分為一組，然后通過計(jì)算這些信息比特的線性組合來得到3個(gè)校驗(yàn)比特，然后將得到的7個(gè)比特送入計(jì)算機(jī)。 

計(jì)算機(jī)按照一定的原則讀取這些碼字，通過采用一定的算法，不僅能夠檢測(cè)到是否有錯(cuò)誤發(fā)生，同時(shí)還可以找到發(fā)生單個(gè)比特錯(cuò)誤的比特的位置，該碼可以糾正7個(gè)比特中所發(fā)生的單個(gè)比特錯(cuò)誤。

這個(gè)編碼方法就是分組碼的基本思想，Hamming提出的編碼方案后來被命名為漢明碼。

漢明碼的編碼效率比較低，它每4個(gè)比特編碼就需要3個(gè)比特的冗余校驗(yàn)比特。另外，在一個(gè)碼組中只能糾正單個(gè)的比特錯(cuò)誤。

M.Golay先生研究了漢明碼的缺點(diǎn)，提出了Golay碼。

Golay碼分為二元Golay碼和三元Golay碼，前者將信息比特每12個(gè)分為一組，編碼生成11個(gè)冗余校驗(yàn)比特，相應(yīng)的譯碼算法可以糾正3個(gè)錯(cuò)誤；后者的操作對(duì)象是三元而非二元數(shù)字，三元Golay碼將每6個(gè)三元符號(hào)分為一組，編碼生成5個(gè)冗余校驗(yàn)三元符號(hào)，這樣由11個(gè)三元符號(hào)組成的三元Golay碼碼字可以糾正2個(gè)錯(cuò)誤。

Golay碼曾應(yīng)用于NASA的旅行者1號(hào)(Voyager 1)，將成百張木星和土星的彩色照片帶回地球。

在接下來的10年里，無線通信性能簡直是跳躍式的發(fā)展，這主要?dú)w功于卷積碼的發(fā)明。

卷積碼是Elias在1955年提出的。

卷積碼與分組碼的不同在于：它充分利用了各個(gè)信息塊之間的相關(guān)性。

通常卷積碼記為(n,k,N)碼。卷積碼的編碼過程是連續(xù)進(jìn)行的，依次連續(xù)將每k個(gè)信息元輸入編碼器，得到n個(gè)碼元，得到的碼元中的檢驗(yàn)元不僅與本碼的信息元有關(guān)，還與以前時(shí)刻輸入到編碼器的信息元(反映在編碼寄存器的內(nèi)容上)有關(guān)。

同樣，在卷積碼的譯碼過程中，不僅要從本碼中提取譯碼信息，還要充分利用以前和以后時(shí)刻收到的碼組。從這些碼組中提取譯碼相關(guān)信息,，而且譯碼也是可以連續(xù)進(jìn)行的，這樣可以保證卷積碼的譯碼延時(shí)相對(duì)比較小。

通常，在系統(tǒng)條件相同的條件下，在達(dá)到相同譯碼性能時(shí)，卷積碼的信息塊長度和碼字長度都要比分組碼的信息塊長度和碼字長度小，相應(yīng)譯碼復(fù)雜性也小一些。

很明顯，在不到10年的時(shí)間里，通信編碼技術(shù)的發(fā)展是飛躍式的，直到遇到了瓶頸。

根據(jù)香農(nóng)前輩的指示，要提高信號(hào)編碼效率達(dá)到信道容量，就要使編碼的分段盡可能加長而且使信息的編碼盡可能隨機(jī)。但是，這帶來的困難是計(jì)算機(jī)科學(xué)里經(jīng)常碰到的“計(jì)算復(fù)雜性”問題。

還好，這個(gè)世界有一個(gè)神奇的摩爾定律。

得益于摩爾定律，編碼技術(shù)在一定程度上解決了計(jì)算復(fù)雜性和功耗問題。而隨著摩爾定律而來的是，1967年，Viterbi提出了Viterbi譯碼算法。

在Viterbi譯碼算法提出之后，卷積碼在通信系統(tǒng)中得到了極為廣泛的應(yīng)用，如GSM、 IS-95 CDMA、3G、商業(yè)衛(wèi)星通信系統(tǒng)等。

但是，計(jì)算復(fù)雜性依然是一道邁不過的墻。

盡管人們后來在分組碼、卷積碼等基本編碼方法的基礎(chǔ)上提出了許多簡化譯碼復(fù)雜性的方法，但是均因無比高聳的計(jì)算復(fù)雜性之墻阻擋而變得不可逾越。

編碼專家們苦苦思索，試圖在可接受的計(jì)算復(fù)雜性條件下設(shè)計(jì)編碼和算法，以提高效率，但其增益與香農(nóng)理論極限始終都存在2~3dB的差距。

直到1993年，在日內(nèi)瓦召開的 IEEE通信國際會(huì)議上，兩位當(dāng)時(shí)名不見經(jīng)傳的法國電機(jī)工程師C.Berrou和A.Glavieux聲稱他們發(fā)明了一種編碼方法，可以使信道編碼效率接近香農(nóng)極限。

Claude Berrou，帥！

這一消息太“轟動(dòng)”了，因?yàn)閹缀跛械膶＜叶颊J(rèn)為這倆“棒槌”是來搗亂的。

這么多數(shù)學(xué)家都沒能突破，就你這兩個(gè)小角色也敢宣稱接近香農(nóng)極限？不是存心搗亂嗎？一定是計(jì)算上出了錯(cuò)誤吧？

許多專家甚至懶得去讀完這篇論文。

事實(shí)上，這兩位法國老兄的數(shù)學(xué)功底可能真的不怎么樣，他們沒有試圖從數(shù)學(xué)上找突破口，因此他們的論文在會(huì)上被懷疑和忽略就不足為奇了。

但是，專家們忽略了一個(gè)問題。

憑著電機(jī)工程師的經(jīng)驗(yàn)，他們發(fā)現(xiàn)在電子學(xué)中經(jīng)常用到的反饋概念似乎被數(shù)學(xué)家們忽略。也許反饋能夠使我們繞過計(jì)算復(fù)雜性問題，于是他們就設(shè)計(jì)了一套新的辦法。

首先他們擯棄了“純粹”的數(shù)字化概念。

在典型的數(shù)字化方法中，總是先把某一電平設(shè)定為閾值。信號(hào)電平高于這一閾值就判決為“1”，低于就判決為“0”。在Turbo碼解碼過程中，某一特定比特的電平被量化為整數(shù)，例如從-127 到+127。其數(shù)值就作為判決該比特為“1”或“0”的可置信度的度量（例如-110意味該比特非常非常可能是“0”，而+40 意味該比特也許是“1”但把握不大）。

其次，與其他系統(tǒng)不同，Turbo碼系統(tǒng)在發(fā)射端和接收端分別設(shè)置兩個(gè)編碼器和解碼器。其中一對(duì)編解碼器對(duì)特定的一段比特流進(jìn)行奇偶校驗(yàn)碼的加入和校驗(yàn)計(jì)算，另一對(duì)編解碼器則在同一段碼流經(jīng)過交織擾動(dòng)后對(duì)其進(jìn)行上述同樣操作。

▲Turbo編碼器結(jié)構(gòu)。Turbo碼編碼器是由兩個(gè)或多個(gè)反饋的系統(tǒng)卷積碼編碼器通過一個(gè)隨機(jī)交織器并行連接而成，編碼后的校驗(yàn)位經(jīng)過刪余矩陣，從而產(chǎn)生不同碼率的碼字。

由于這兩段碼流包含同樣的數(shù)據(jù)，如果沒有信道噪聲，解碼結(jié)果應(yīng)該一致。但在噪聲干擾下兩組結(jié)果會(huì)產(chǎn)生差別。通過上述對(duì)比特判決的可置信度信息的幫助，把這兩組結(jié)果彼此參照，可以得出第一次近似的結(jié)果。把這一結(jié)果“反饋”到解碼器前端，再進(jìn)行迭代，經(jīng)過幾次迭代兩個(gè)解碼器的結(jié)果就會(huì)互相接近（收斂）。這樣就繞過了計(jì)算復(fù)雜性問題。

▲Turbo碼的譯碼器有兩個(gè)分量碼譯碼器，譯碼在兩個(gè)分量譯碼器之間進(jìn)行迭代譯碼，故整個(gè)譯碼過程類似渦輪（turbo）工作，所以又形象的稱為Turbo碼。

當(dāng)然這樣做也得付出代價(jià)。由于迭代解碼，必然會(huì)產(chǎn)生時(shí)延。所以對(duì)于實(shí)時(shí)性要求很高的場(chǎng)合，Turbo碼直接應(yīng)用會(huì)受到限制。

接下來，那些編碼專家們跌破了眼鏡。不可思議，當(dāng)其他小組驗(yàn)證了這兩位法國老兄的方案時(shí)，證明了結(jié)論是正確的。現(xiàn)在人們談?wù)摰囊呀?jīng)是和香農(nóng)極限相差0.1dB還是0.01dB了。

一個(gè)通信編碼史上的革命性的時(shí)代到來了！兩位名不見經(jīng)傳的電機(jī)工程師不顧科學(xué)權(quán)威認(rèn)定的種種“極限”，在一片嘲笑聲中，另辟蹊徑，突破了理論壁壘。

一開始，Turbo碼只是應(yīng)用于一些特殊場(chǎng)合，比如衛(wèi)星鏈路。后來，研究人員將它擴(kuò)展到數(shù)字音頻和視頻廣播領(lǐng)域。

緊接著，Turbo碼成為通信研究的前沿，全世界各大公司都聚焦在這個(gè)領(lǐng)域，包括法國電信、NTT、DoCoMo、索尼、NEC、朗訊、三星、愛立信、諾基亞 、 摩托羅拉和高通等等。

Turbo碼成為了始于本世紀(jì)初的3G/4G移動(dòng)通信技術(shù)的核心，直到今天4.5G，我們依然在采用。

現(xiàn)在，編碼專家們都松了一口氣，總算解決了這個(gè)棘手的問題。也同時(shí)都嘆了一口氣，因?yàn)檫@已經(jīng)接近香農(nóng)極限了，發(fā)現(xiàn)似乎在這領(lǐng)域已經(jīng)很難再突破了。

收工，回家，帶娃。

但是，在1999年，編碼界又發(fā)生了一件有趣的事。人們重燃起了對(duì)LDPC的興趣，盡管它已經(jīng)被人們遺忘了幾十年。

LDPC（ low-density parity check），即低密度奇偶校驗(yàn)碼。它于1962年由Gallager提出，然后，被人們遺忘了。直到Turbo碼被提出以后，人們才發(fā)現(xiàn)Turbo碼從某種角度上說也是一種LDPC碼。

另一件讓人們感興趣的事是，LDPC碼發(fā)明較早，其基本專利到1999年就到期了，而Turbo碼要到2013年才到期。

LDPC利用校驗(yàn)矩陣的稀疏性，使得譯碼復(fù)雜度只與碼長成線性關(guān)系，在長碼長的情況下仍然可以有效的進(jìn)行譯碼，因而具有更簡單的譯碼算法。隨著人們對(duì) LDPC碼重新進(jìn)行了研究，發(fā)現(xiàn)LDPC 碼與Turbo一樣具有逼近香農(nóng)極限的性能。較新的研究結(jié)果顯示，實(shí)驗(yàn)中已找到的最好 LDPC 碼，其極限性能距香農(nóng)理論限僅相差0.0045dB。

接著，LDPC在IEEE 802.11n 以及802.16的技術(shù)提案中被熱烈討論。DVB-S2也決議以LDPC替代Turbo碼。有人認(rèn)為，LDPC是終極糾錯(cuò)編碼，極有可能成為未來主流編碼技術(shù)。

所以，一場(chǎng)關(guān)于Turbo碼和LDPC碼的爭(zhēng)論就拉開了。隨著5G標(biāo)準(zhǔn)化的到來，Turbo碼和LDPC碼像拳擊臺(tái)上兩名重量級(jí)選手，兩人都宣稱自己將是獲勝者，但裁判的結(jié)束哨聲卻一直未吹響。

裁判很頭痛，這是一場(chǎng)幾乎無法打分的比賽。因?yàn)椋杂袪?zhēng)論，無非是要證明，誰才更適合未來5G用例？誰才能更好滿足新的技術(shù)需求？

眾所周知，2G的應(yīng)用場(chǎng)景是語音和低速率數(shù)據(jù)業(yè)務(wù)，3G和4G的應(yīng)用場(chǎng)景是語音和更高速率的數(shù)據(jù)業(yè)務(wù)。可以確定的是，Turbo碼和LDPC碼都能很好的滿足3/4G，甚至是4.5G用例。

而5G用例呢？市場(chǎng)上還沒有出現(xiàn)，而且很多。不管是Turbo碼，還是LDPC碼，都無法確定誰才是最好的選擇。而且，由于兩者各有優(yōu)缺點(diǎn)，要覆蓋全部5G應(yīng)用，不太現(xiàn)實(shí)。

正當(dāng)Turbo碼和LDPC碼打拳擊賽之時(shí)，Polar碼沖上了拳臺(tái)，變成了一場(chǎng)摔角運(yùn)動(dòng)。

很幸運(yùn)，在編碼技術(shù)不斷打破記錄帶給我們驚喜時(shí)，另一項(xiàng)編碼領(lǐng)域里的激動(dòng)人心的研究已浮出水面。

2007年，土耳其比爾肯大學(xué)教授E. Arikan基于信道極化理論提出的一種線性信道編碼方法，即Polar碼。該碼字是迄今發(fā)現(xiàn)的唯一一類能夠達(dá)到香農(nóng)限的編碼方法，并且具有較低的編譯碼復(fù)雜度，當(dāng)編碼長度為N時(shí)，復(fù)雜度大小為 O ( NlogN)。

Erdal Ar?kan（右）

有趣的是，LDPC發(fā)明人Gallager博士是他的博士生導(dǎo)師

Polar碼的理論基礎(chǔ)就是信道極化。信道極化包括信道組合和信道分解部分。當(dāng)組合信道的數(shù)目趨于無窮大時(shí)，則會(huì)出現(xiàn)極化現(xiàn)象：一部分信道將趨于無噪信道，另外一部分則趨于全噪信道，這種現(xiàn)象就是信道極化現(xiàn)象。

無噪信道的傳輸速率將會(huì)達(dá)到信道容量 I (W )，而全噪信道的傳輸速率趨于零。Polar碼的編碼策略正是應(yīng)用了這種現(xiàn)象的特性，利用無噪信道傳輸用戶有用的信息，全噪信道傳輸約定的信息或者不傳信息。

這就像一個(gè)班上的同學(xué)，上學(xué)時(shí)間足夠長的話，差的學(xué)生大部分會(huì)跌到谷底，好的學(xué)生大部分會(huì)飛向云巔，然后，拋棄那些學(xué)渣…

Polar碼比Turbo碼和LDPC碼更接近信道容量，Polar碼可以保證5G任何場(chǎng)景的高性能通信。夸張的講，如果不考慮系統(tǒng)設(shè)計(jì)問題，編碼技術(shù)的歷史就應(yīng)該到此終結(jié)了，終結(jié)在Polar碼的手里。

但是，編解碼的復(fù)雜性是Polar的問題，不過，在使用改進(jìn)后的SCL（Successive Cancelation List）譯碼算法時(shí)能以較低復(fù)雜度的代價(jià)，接近最大似然譯碼的性能。

關(guān)鍵是，Polar碼還是太年輕了，發(fā)明得比較晚，很多研究還建立在理論基礎(chǔ)上，不像Turbo碼和LDPC碼已經(jīng)廣泛應(yīng)用于實(shí)際場(chǎng)景。只有等待時(shí)間來告訴我們，Polar碼到底是不是5G信道編碼的王者（小棗君注：2016年底，在華為的力挺下，polar碼被確定為5G eMBB場(chǎng)景的信道編碼解決方案）。

回顧信道編碼歷史，跌宕起伏，波瀾壯闊。在幾十年并不漫長的歲月里，一次又一次關(guān)鍵技術(shù)的歷史性突破，造就了今天人類通信奇跡。

未來還會(huì)有新的突破嗎？讓我們拭目以待！

來源：機(jī)器人網(wǎng)