1.2 信道編碼技術的發展及其在移動通信中的應用

1.2.1 信道編碼技術的發展

1948年，C. E. Shannon在貝爾技術雜志上發表了奠基性文獻“通信的數學理論”[16]，標志著信息與編碼理論這一學科的創立。Shannon在文中提出了著名的有噪信道編碼定理，即對任何通信信道都存在一個稱為信道容量的參數C，只要實際傳輸速率R小于C，就存在一種編碼方法，當碼長充分大時，可使系統的錯誤概率達到任意小；反之，如果R大于C，則不可能有一種編碼能使錯誤概率趨于0。

在Shannon之前，人們普遍認為在有噪信道里進行通信獲得任意小的錯誤概率的唯一途徑就是減小傳輸速率到零。有噪信道編碼定理從理論上證明了通過信道編碼技術可使得信息傳輸速率接近信道容量。編碼定理及其證明雖然沒有給出編碼的具體設計方法，卻指出了達到信道容量的編譯碼方法的指導性路線，即構造隨機長碼和采用接近最大似然譯碼（信道編碼定理最初是Shannon基于典型序列方法證明的，后來Gallager基于最大似然譯碼給出了強編碼定理）。此后，構造可逼近信道容量（Shannon限）的信道編碼具體方法及其可實用的（線性復雜度）有效譯碼算法一直是信道編碼理論與技術研究的中心任務，也就是如何構造出能接近或達到Shannon限的碼（稱為Shannon碼或漸近好碼）是編碼學者長期追求的目標。

過去的幾十年中，有兩類糾錯編碼得到深入研究并在通信/存儲系統得到廣泛應用，即分組碼與卷積碼。1950年，數學家Hamming提出了第一個實用的差錯控制編碼方案，即漢明碼[17]。方法是將輸入數據每4比特分成一組，然后通過對信息比特進行線性組合得到3個校驗比特，組成7比特的碼字。利用校驗比特不僅可以檢測傳輸錯誤，還可以糾正單個隨機錯誤。這個編碼方法就是分組碼的基本思想。分組碼很快引起代數學家的興趣，并迅速發展成系統的代數編碼理論，成為糾錯碼中理論體系最完整、最成熟的一類碼字。1954年，Reed和Muller提出了一種新的分組碼：Reed-Muller碼，簡記為RM碼[18]。RM碼是一類參數選擇很廣的分組碼，在碼字長度和糾錯能力方面具有較強的適應性。1957年，Prange提出了一類重要的分組碼即循環碼[19]，它在線性碼中占有重要地位，是分組碼中研究最深入、應用最廣泛的子集。循環碼的碼字具有循環移位特性，由此大大簡化了編譯碼結構，使得實用成為可能。循環碼中一個重要成員就是由Bose、Ray-Chaudhuri和Hocquenghem于1959―1960年分別提出的可糾正多個隨機錯誤的BCH碼[20][21]。BCH碼糾錯能力強，編碼簡單，具有嚴格的代數結構。1960年，Reed和Solomon構造了一類很強糾錯能力的多進制BCH碼，即著名的Reed-Solomon碼[22]（簡稱RS碼）。RS碼最突出的優點是非常適合糾正突發錯誤，在CD播放器、DVD播放器及DVB和數字用戶線（DSL）標準中有廣泛的應用。分組碼雖然基于數據分組的編碼方式，譯碼時必須等待整個碼字完整接收下來，才能實現譯碼，故在碼長較大時會引入一定的時延。

卷積碼[23]是與分組碼同時發展起來的另一種糾錯編碼方式。卷積碼編碼時本組的校驗元不僅與本組的信息元有關，還與以前時刻輸入到編碼器的若干信息組有關。正是由于利用了各組之間的相關性，且每組的長度及其包含的信息的長度均較小，因此在與分組碼同樣的碼率和設備復雜度條件下，無論從理論上還是從實際上均已證明卷積碼的性能不比分組碼差。但是由于缺少有效的分析工具，分析上得到的成果要少于分組碼，并且好碼往往要借助計算機搜索。在相同的碼長下，卷積碼的譯碼比分組碼相對容易一些，最常用的是維特比（Viterbi）算法[24][25]，它是基于卷積碼網格圖的一種最大似然譯碼算法，卷積碼譯碼以流的方式連續進行，譯碼時延相對較小。

上述各信道編碼方案雖然譯碼復雜度大多在可接受的范圍內，然而由于碼長較短，其性能距Shannon限有較大距離。為了構造出譯碼復雜度可接受且差錯控制性能優異的長碼，Elias在發明卷積碼的前一年便提出了乘積碼的概念，這是第一個由短碼構造長碼的方法。乘積碼以兩個線性分組碼作為分量碼，其碼長為各分量碼碼長的乘積，譯碼可通過對各分量碼單獨譯碼從而得到次優的結果。1966年，Forney提出了另一種由短分量碼構造長碼的編碼方案：（串行）級聯碼[26]。在級聯編碼方案中，將內碼和外碼進行串行級聯，內譯碼器可以看作一個噪聲濾波器，它不僅能改變錯誤分布，而且能有效增加信號的接收信噪比。為了提高級聯碼的性能，常采用卷積碼為內碼，分組碼（如RS碼）為外碼。該方案充分利用了卷積碼和RS碼的糾錯性能互補的特點，在工業界有著廣泛的應用。級聯編碼方案雖然可以提高系統性能，同時也損失了部分編碼效率，而且內、外譯碼器間只是順序譯碼并沒有信息交換。需要說明的是，幾乎同一時期，Gallager提出了LDPC碼，這是一種直接構造長碼并采用低復雜度的迭代譯碼來解決譯碼問題的編碼方法，但在隨后的幾十年中，由于受硬件、軟件所限及級聯碼的影響，低密度校驗碼并沒有引起太多關注。

經典糾錯編碼盡管設計精巧，但其性能與Shannon限存在2～3 dB的明顯差距。現代糾錯編碼的特征是具有逼近Shannon限的譯碼性能。到目前為止，學術界與工業界影響力最大的三類先進的現代糾錯編碼方式分別是Turbo碼、LDPC碼與Polar碼。

1993年，法國的Berrou等提出了并行級聯卷積碼即Turbo碼[27]，他將卷積碼和隨機交織器結合在一起，實現了隨機編碼的思想，同時通過多個軟輸出譯碼器之間的迭代，系統漸近性能逼近容量限。仿真結果表明，在加性高斯白噪聲（Additive White Gaussian Noise, AWGN）信道上，采用長度為65536比特的偽隨機交織器在調制方式為BPSK時，碼率為R=1/2的Turbo碼在誤比特率（Bit Error Rate, BER）為10-5時距離Shannon限約0.7dB。這一驚人發現改變了長期以來把信道截止速率作為實際容量的歷史，使信道編碼理論和實踐進入了一個嶄新的階段。Turbo碼除了性能優異，還由于是卷積碼并行級聯得到，因此編碼復雜度很低；Turbo碼具有很好的靈活性，理論上可以支持任意長度的信息比特進行編碼，通過速率匹配操作可以得到任意碼率的碼字；Turbo碼譯碼算法為軟輸入軟輸出（soft-input soft-output）的迭代譯碼[28][29]，其缺陷在于具有較高的譯碼復雜度，且譯碼并行度受限，同時Turbo碼雖然中低碼率性能優異但在高碼率時，受過度打孔影響，性能惡化，且容易出現較高的譯碼平層。

隨著對Turbo碼的深入研究，發現Turbo碼的實現原理和Gallager提出的LDPC碼極其相似，從此LDPC碼被重新發現。LDPC碼是一類線性分組碼，其對應的奇偶校驗矩陣是“1”的個數很少的稀疏矩陣。LDPC碼最早是由Gallager于20世紀60年代初期在其博士論文中提出的[30][31]，故又稱為Gallager碼。但在其后的長時間里被忽視了，其中一個重要原因是就當時的技術條件而言，LDPC編譯碼器的實現過于復雜；再就是RS碼的發現，RS碼與卷積碼構成的級聯碼被認為是很完美的。直到1996年，MacKay等發現LDPC碼同樣具有逼近信道容量的譯碼性能[32][33], LDPC碼才又引起了人們的研究興趣。MacKay的研究表明，盡管規則LDPC碼性能優異，但與Turbo碼相比還有一定的差距。2001年，Richardson等提出了著名的密度進化算法來優化非規則LDPC碼的參數[34-37]，基于此所設計的1/2碼率的非規則LDPC碼在AWGN信道中，其性能門限距Shannon容量限不超過0.0045dB，仿真也表明在BER=10-6時，長度為107的非規則LDPC碼距離信道容量0.04 dB[38]。這一結果超過所知的最好的Turbo碼，是繼MacKay重新發現LDPC碼后，又一具有里程碑意義的成果。LDPC的主要優點在于譯碼復雜度低且其結構適于部分并行或全并行譯碼，是實現高吞吐譯碼的最有力競爭者。LDPC碼缺點在于編碼復雜度較高，所需的存儲量較大，性能優異的LDPC碼構造比較困難，同時對任意固定的碼長與碼率都需要對應一個校驗矩陣，如果要支持靈活的信息比特長度與編碼碼率對LDPC校驗矩陣構造、譯碼器的設計來說都是個嚴峻的挑戰。LDPC碼性能取決于校驗矩陣的構造，而校驗矩陣構造方法主要分為隨機構造和代數構造兩類。隨機構造方法主要是附加一定的約束條件利用計算機搜索的方法得到目標校驗矩陣；代數構造方法主要是利用組合構造方法、幾何構造方法、圖論方法、實驗設計方法、置換設計方法等來設計性能優異的校驗矩陣。一般來說，代數的方法往往更容易設計出性能優異的LDPC碼，但是隨機構造方法則約束更少，高深的數學知識也不一定是必需的。無論是隨機的還是代數的LDPC碼構造方法在學術界與工業界都得到了廣泛的研究與應用。

盡管Turbo和LDPC碼的性能距離Shannon容量限已經非常小，但是始終沒有達到容量限。2008年，Arikan在國際信息論會議（ISIT）上首次提出了信道極化的概念[39]，并于2009年發表的論文中對極化編碼（Polar碼）給出了詳細的闡述[40]。Polar碼是首個可嚴格證明在二進制輸入對稱離散無記憶信道下可達容量限的編碼方案，Polar碼的出現引起了學術界與工業界的高度關注。Polar碼是線性分組碼，其生成矩陣是基于信道極化現象構造得到的類哈達瑪矩陣。Arikan發現將極化核矩陣使用Kronecker積進行擴展，并使用擴展矩陣對各子信道進行合并，然后按照順序對合并后的矢量信道進行分裂，則對于組合前的二進制信道會發生信道極化。該現象使得分裂后信道產生兩極分化：一部分會變成容量趨于0的純噪聲信道；另一部分變成容量趨于1的無噪聲信道。在這樣的極化信道上信道編碼是非常簡單的：只需要將所要傳輸的數據加載在容量趨近于1的那些信道上，而容量趨近于0的那些信道不使用，就可以實現數據的可靠傳輸。在譯碼算法方面，Arikan給出的原始Polar譯碼方法是逐次抵消（Succesive Cancellation, SC）算法，該算法譯碼復雜度為O(N log N)。在碼長趨于無窮大時，使用簡單的SC譯碼算法就可以取得優異性能，但是在碼長受限時，基于SC算法的Polar碼性能損失嚴重。文獻[41]提出了一種基于SC的改進譯碼算法，稱為SCL（SC List）譯碼算法，在中短長度的碼長時可以獲得接近最大似然譯碼的性能。Polar碼采用SCL譯碼時性能非常優異，編碼簡單，可以很簡單地實現任何碼率的Polar編碼，支持多速率碼的速率適配方法也很簡單，對實際應用來說非常具有吸引力。然而，年輕的Polar碼也存在很多問題，如譯碼列表較大時，SCL譯碼的時間復雜度與存儲空間都很高，同時SCL譯碼適于串行譯碼實現高吞吐譯碼器比較困難；SCL譯碼無法輸出對數似然比軟信息，IR-HARQ方案也不如LDPC與Turbo成熟等。

關于信道編碼理論與技術的發展，可進一步閱讀相關文獻[42][43]，相關應用可參見文獻[44]。

1.2.2 信道編碼技術在移動通信中的應用

蜂窩移動通信系統在過去幾十年中迅猛發展，使得用戶徹底擺脫終端設備的束縛，變成社會發展和進步的必不可少的工具。糾錯編碼作為不可或缺的一環，在移動通信系統中有著廣泛的應用。

第一代通信系統是模擬通信系統，業務信道采用模擬信號傳輸，而控制信道傳輸數字信令并進行了信道編碼與數字調制操作。以英國系統為例，基站與終端信道編碼采用不同的BCH碼，編碼后重復5次發送以提高衰落信道性能。

第二代移動通信系統，如歐洲的GSM系統、北美的IS-95都是數字通信系統。GSM在全速率業務信道與控制信道采用了約束長度為5，碼率為1/2卷積編碼。更具體地，GSM全速率業務信道20ms業務幀包含260個比特，其中50個最重要的比特、132個重要比特、78個不重要比特。50個重要比特首先進行循環冗余校驗（Cyclic Redundancy Check, CRC）編碼得到53個比特的碼字，然后與后面的132個重要比特與4個全零尾比特一起采用1/2碼率的卷積碼進行編碼得到378個比特，最后的78個比特不予保護得到456個比特的語音編碼塊。對于半速率業務信道為了改善通話質量采用碼率為1/3，約束長度為5卷積編碼。GSM控制信道采用外碼為Fire碼[45]、內碼為卷積碼的串行級聯編碼方案，由于Fire碼適于檢測與糾正突發錯誤碼，與善于糾正隨機錯誤的卷積碼結合可以進一步提高控制信令的可靠度。

IS-95窄帶CDMA系統的糾錯編碼是分別按照前向鏈路與反向鏈路來設計的，主要包括卷積編碼與CRC編碼。前向鏈路中除導頻信道之外的同步信道、尋呼信道、業務信道都采用了約束長度為9，碼率為1/2，生成多項式為[561,753]8的(2,1,9)卷積碼。反向鏈路（包括業務信道和接入信道）則采用了約束長度為9，碼率為1/3，生成多項式為[557,663,711]8的(3,1,9)卷積碼。反向鏈路卷積碼的碼率更低，具有更強的糾錯能力，有利于提高基站采用非相干解調接收時的抗干擾能力。卷積碼編碼器如圖1.5所示。

第三代移動通信與2G相比要提供更高的傳輸速率、更多形式的數據業務，所以糾錯編碼提出更高要求。3G仍然以IS-95中的(2,1,9)和(3,1,9)卷積碼作為語音信道和各個控制信道的糾錯編碼方案。確定Turbo碼為數據、多媒體等業務的編碼方案。3GPP在WCDMA系統中采用的Turbo碼的母碼碼率為1/3，兩個8狀態的Turbo分量編碼器的生成多項式為g0=13, g1=15，編碼器結構如圖1.6所示。WCDMA Turbo碼內交織器采用分組（block）交織器，交織器的行的數目為5、10或20，支持的信息比特的長度范圍為40≤K ≤5114，信息比特按行寫入交織器，經過行列置換后，逐列讀出[46]。

第四代移動通信（LTE）同樣采用了卷積碼與Turbo碼作為糾錯編碼方案，而且卷積碼用于控制信道，Turbo碼用于數據信道。與WCDMA的糾錯編碼方案相比，LTE對糾錯編碼方案進行了進一步優化。

LTE卷積編碼采用1/3碼率的咬尾卷積碼（Tail-Biting Convolutional Codes, TBCC），約束長度為7，生成多項式（按八進制）為[133,171,165]8，編碼框圖如圖1.7所示。LTE TBCC有6個移位寄存器，其初始值用信息比特的最后6個比特進行初始化，如此一來，移位寄存器的初始與最后狀態是相同的，與尾比特歸零操作相比，TBCC降低了尾比特的開銷，這對于信息比特長度很短的控制信令來說會明顯提高其頻譜效率。

LTE Turbo編碼結構與WCDMA相近，都是基于兩個8狀態的生成多項式為g0=13, g1=15的Turbo分量編碼器并行級聯得到1/3碼率的母碼，但是分量碼間的內部交織器與WCDMA完全不同。LTE Turbo采用二次置換多項式（Quadratic Permutation Polynomials, QPP）交織器，即f(i)=(f1· i+f2· i2)mod K，其中i代表交織后的序號，f(i)代表交織器輸入的序號，K是編碼器輸入比特序列的長度，其范圍為40≤K ≤6144。QPP交織器的主要優點是無沖突交織處理，能夠支持并行譯碼，相對于WCDMA Turbo碼的串行譯碼能夠顯著提高譯碼速度[47][48]。

LDPC碼作為另外一種接近Shannon限的信道編碼，雖然由于早期研究不夠成熟，錯過了3G與4G標準，但其出色的性能，較低的譯碼復雜度使其被多個重要的國際標準采納，如Wi-Fi、WiMax、CCSDS等。

Wi-Fi中如802.11n與802.11ac采用的LDPC碼支持648、1296、1944三種碼長，1/2、2/3、3/4、5/6四種碼率[49]。上述LDPC碼校驗矩陣具有準循環結構，碼長為648/1296/1944對應的循環子矩陣大小分別為27/54/81，且校驗矩陣具有雙對角結構，該結構導致所設計的碼具有較小的存儲量，便于實現部分并行譯碼，同時可以直接根據校驗矩陣進行編碼。在802.11n/802.11ac協議中通過對LDPC碼執行縮短與打孔操作實現速率匹配。Wi-Fi中LDPC碼能夠實現較大的吞吐量，其設計思想影響了后續標準中LDPC碼的設計。

WiMax（Worldwide Interoperability for Microwave Access）采用的LDPC碼的校驗矩陣，通過將多個基矩陣中的每個元素擴展為一個子矩陣，得到多種碼率和碼長的LDPC碼[50]。實際使用的基矩陣有6種，碼率分別為1/2、2/3、3/4和5/6，基矩陣的列數都為24，擴展因子取值為Z=[24:4:96]。基于基矩陣改變擴展因子就得到不同大小的校驗矩陣，對應不同長度的碼，碼長N=24×Z，范圍為576≤N ≤2304。WiMax采用的校驗矩陣與Wi-Fi類似，都具有雙對角結構可以實現線性復雜度編碼。

針對空間通信應用，CCSDS（Consultative Committee for Space Data Systems）藍皮書標準化了兩類LDPC、碼[51]。第一類為基于歐幾里得幾何構造的(8176,7156)準循環LDPC碼，其校驗矩陣由2行16列循環子矩陣構成，每個循環子矩陣大小為511×511。該碼的碼率較高，其BER誤碼平層低于10-10，譯碼收斂速度快，僅需要10次迭代譯碼就接近收斂。第二類LDPC碼，具有更低的碼率應用于深空通信，分別支持碼率為1/2、2/3、4/5，碼長為1024、4096、16384，共9個碼。該LDPC碼同樣為準循環矩陣，子矩陣的大小根據碼長與碼率的不同分別取值為{128,256,512,1024,2048,4096,8192}。第二類碼的碼長與碼率比較靈活，性能非常優異，但是譯碼收斂速度較慢，其誤碼平層性能不如第一類碼。

各個標準中對糾錯編碼的研究及其工業化經驗為5G糾錯編碼的設計打下了堅實的基礎。