第10章分組碼10.1BCH碼10.2RS碼10.3卷積碼10.4網格碼10.5TURBO碼10.6LDPC碼10.6空時編碼

10.1BCH碼

10.1.1BCH碼的定義

BCH碼是一類糾正多個隨機錯誤的循環碼，是以3個發現者——博斯(Bose)、查德胡里(Chaudhuri）和霍昆格姆(Hocquenghem)姓氏的字頭命名的。這是迄今為止發現的最好的線性分組碼之一。

BCH碼的重要性在于它解決了生成多項式與最小碼距之間的關系問題。

該碼的糾錯能力很強，且構造簡便。

10.1BCH碼

10.1.1BCH碼的定義

本原多項式的概念。

10.1BCH碼

10.1.2BCH碼及最小漢明距離

定義1設m是一正整數，m0是任意整數，GF(q)表示有q個元素的有限域，其中q是一個素數或素數的冪，GF(qm)是GF(q)的擴域，a∈GF(qm)，如果一個循環碼由GF(q)上的多項式g(x)生成，并且g(x)的根包含下面d-1個根：

a，a

2，a

3，…，a

d－1

那么，稱這個由g(x)生成的循環碼為設計距離為d的q元BCH碼。

如果定義中g(x)有一個根是GF(qm)中的本原元，那么g(x)生成的BCH碼碼長必定為n=qm－1，稱這種BCH碼為本原BCH碼，否則稱為非本原BCH碼。非本原BCH碼是存在的，其碼長是qm－1的因子。

BCH碼的優勢之一在于，如果確定了BCH碼的生成多項式g(x)的連續根，則由g(x)生成的BCH碼的實際最小漢明距離不小于設計距離。

定理10.1.1BCH碼的最小漢明距離至少為d。10.1.3BCH碼的編碼方法

二元BCH碼

二元信號在工程上最容易實現，因而二元BCH碼在工程上應用最廣泛。對給定的正整數m和d(d=2t+1，t<2m－1)，二元BCH碼的碼長、校驗位數和最小漢明距離是什么呢？

定理2給定正整數m和t，存在一個(n，k)二元BCH碼，其生成多項式以a，a

3，a

5，…，a

2t－1為根，其碼長n=2m－1或n|2m－1，能糾正t個錯誤，并且n－k≤mt。

10.1.3BCH碼的譯碼方法

1.一般譯碼方法

1）確定BCH碼的伴隨式；

2）尋找錯誤位置多項式；

3）糾正錯誤；

2迭代譯碼算法10.2RS碼

Reed-Solomon碼是一類有很強糾錯能力的多進制BCH碼，也是一類典型的代數幾何碼。它首先由里德（Reed）和索洛蒙（Solomon）應用MS多項式于1960年構造出來的。

它是一類糾多個隨機錯誤的循環碼，具有嚴格的代數結構，構造方便，便于從理論上對應用進行研究。除了譯碼算法有些復雜之外，它的糾錯能力和譯碼速度均是其它碼類無法比擬的，特別在短和中等碼長下其性能接近于理論值。10.2.1RS碼的定義

定義:對于一個長度為符號的RS碼，每個符號都可以看成是有限域GF（）中的一個元素。最小碼距為d0符號的RS碼的生成多項式具有如下形式：

這里，是GF（）中的一個元素。

10.2.1RS碼的定義

在（n,k）RS碼中，輸入信號分成kmbit一組，每個碼元由mbit組成，因此一個碼組共包括k個碼元。一個能糾正t個碼元錯誤的RS碼的主要參數：

10.2.2RS碼的編碼

時域編碼：時域編譯碼算法出現較早，由于比較成熟而被廣泛采用；

頻域編碼：頻域編譯碼算法出現的較晚，但由于利用了快速傅立葉正反變換(FFT/IFFT)而提高了編譯碼速度，具有較大的發展潛力。

這兩種算法都比較簡單，時域編碼只需要運算一次多項式除法，而頻域編碼只需要計算一次IFFT。

10.2.2RS碼的編碼

它們的區別在于：經時域算法得到的碼字是系統碼，可用于截短編碼；而頻域算法得到的碼字是非系統碼，不能用于截短編碼。

時域編碼：

將待編碼信息多項式升位后除生成多項式,將所得的余式置于升位的信息多項式之后，就形成RS碼。

RS碼的編碼方法與CRC一樣，也是除以，所以同樣可以采用移位寄存器來實現。

10.2.2RS碼的編碼

時域編碼：

n-k級線性移位寄存器編碼電路10.2.2RS碼的編碼

它們的區別在于：經時域算法得到的碼字是系統碼，可用于截短編碼；而頻域算法得到的碼字是非系統碼，不能用于截短編碼。

時域編碼：

將待編碼信息多項式升位后除生成多項式,將所得的余式置于升位的信息多項式之后，就形成RS碼。

RS碼的編碼方法與CRC一樣，也是除以，所以同樣可以采用移位寄存器來實現。

10.2.3RS碼的譯碼方法

RS碼的譯碼算法比其它碼類的譯碼算法復雜得多，這是因為RS碼是一種非二元循環碼，它不再具備特征為2的域的運算等性質。

分類：

RS碼的頻域譯碼算法：RS碼的時域譯碼算法：也是從計算接收碼字的伴隨式入手的，并且在譯碼過程中不僅要找出錯誤位置，而且還要找出對應錯誤位置的錯誤大小，這樣就增加了它的譯碼難度。10.2.3RS碼的譯碼方法

RS碼的譯碼算法步驟：

(1)根據接收碼字求出伴隨式Sj；

(2)由伴隨式求出錯誤位置多項式；

(3)由錯誤位置多項式求出錯誤位置值；

(4)由錯誤位置值求出對應的錯誤值；

(5)求出錯誤圖樣，糾錯成功。

10.3卷積碼的表示方法

10.3.1卷積碼的概念

卷積碼是由伊利亞斯提出，其信息碼個數和碼長通常較小，故時延小，特別適合于以串行形式傳輸的場合。

另外，卷積碼在任何一個碼組中的監督碼元都不僅與本碼組的信息碼元有關，而且還與前面若干個碼組的信息碼元有關，其糾錯能力隨著前面若干個碼組數的增加而增加。故在實際應用中，卷積碼的性能優于分組碼，而且設備簡單。

10.3卷積碼的表示方法

10.3.1卷積碼的概念

一個(n，k，m)卷積碼編碼器由輸入單元、編碼單元和輸出單元三部分組成，如圖所示。圖10.1(n，k，m)卷積碼編碼器 10.2卷積碼的表示方法

10.3.1卷積碼的概念

輸入單元的功能是把1路串行輸入信元變換成k路并行輸出，并作為編碼單元的k路信元輸入；

輸出單元的功能是把編碼單元的n路并行輸出變成1路串行輸出，并作為卷積碼的碼字；

編碼單元的功能是把k路并行輸入信元變成n路并行輸出。是卷積碼中最關鍵的部分。 10.2卷積碼的表示方法

10.3.1卷積碼的概念

（2,1,2）卷積碼編碼器

10.2卷積碼的表示方法

10.3.1卷積碼的概念

（2,1,2）卷積碼編碼器

10.2卷積碼的表示方法

10.3.1卷積碼的概念

當有k位數據輸入時，輸出碼字序列共有卷積碼的編碼效率為10.3.2卷積碼的表示法

1.卷積碼的多項式

用符號D表示延時算子，輸入信息x中的相對于來說晚1個時刻(即一個碼元時間長度)出現，相對于晚2個時刻出現，其余以此類推。用Dk表示延時k個時刻，這樣，我們可以把輸入信息x用一個多項式表示，即

2.卷積碼的生成矩陣

10.3.3卷積碼的圖形表示法

1.樹狀圖

樹狀圖描述的是在任何數據序列輸入時，碼字所有可能的輸出。

卷積碼的樹狀圖由節點和樹枝組成，從一個初始節點(稱為樹根)開始，根據輸入信息碼元是０還是１進行分枝，通常信息碼元為０時向上分枝，信息碼元為１時向下分枝，并將輸出的碼字標于樹枝上。卷積碼的樹狀圖見圖。圖(2，1，2)卷積碼的樹狀圖

2.狀態圖

狀態圖主要用來反映卷積碼編碼器的可能狀態，以及由一個狀態可能向哪些狀態轉移。

3.網格圖

樹狀圖能清晰地反映編碼路徑，標出了各個時刻的編碼狀態，但不能反映狀態間的轉移；狀態圖能緊湊地反映狀態間的轉移情況，但不能顯示編碼路徑及各個時刻的編碼狀態。網格圖有機地結合了兩者的優點，如圖所示。

圖(2，1，2)卷積碼的網格圖 4.2卷積碼的譯碼方法

卷積碼的譯碼方法主要有代數譯碼法和概率譯碼法。代數譯碼法有與分組碼相似的伴隨式、錯誤圖樣等概念，利用伴隨式進行檢錯、糾錯。概率譯碼法則利用信道統計特性，對接收序列進行最大似然判決，目前，概率譯碼法普遍通過維特比(Viterbi)譯碼算法和費諾(Fano)譯碼算法來實現。1.維特比算法

維特比譯碼是一種最大似然譯碼算法。最大似然譯碼算法的基本思路是，把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為譯碼輸出。

當k較大時，由于存儲量太大，應用受到限制。由于接收序列通常很長，所以維特比譯碼是最大似然譯碼算法的簡化。簡化的方法是：它把接收碼字分段處理，每接收一段碼字，計算、比較—次，保留碼距最小的路徑，直至譯完整個序列。

2序列譯碼

當m很大時，可以采用序列譯碼法，該譯碼方法可避免漫長的搜索過程。譯碼先從樹狀圖的起始節點開始，把接收到的第一個子碼的n個碼元與自始節點出發的兩條分支按照最小漢明距離進行比較，沿著差異最小的分支走向第二個節點；

3門限譯碼

除上述的維特比譯碼法、序列譯碼法外，卷積碼的另一種譯碼方法為門限譯碼法。門限譯碼又稱大數邏輯譯碼。門限譯碼的設備簡單，譯碼速度快，約束長度可較大，適用于有突發錯誤的信道。

10.4網格編碼調制（TCM）

TCM的基本原理是基于Ungcrbeck子集劃分理論，將編碼器對信息比特的編碼轉化為對信號點的編碼，使得在信道中傳輸的信號序列遵循一定的規則，即符合網格圖中某條特定的路徑。這類信號具有如下兩個基本持征：(1)在信號空間中，信號點數目比無編碼調制情況下對應的信號點數目要多一倍．這些增加的信號點為糾錯編碼提供了冗余度，但不犧牲帶寬；(2)采用卷積碼編碼規則，在時間上相鄰的信號點之間建立依賴關系，因此僅有某些信號點圖樣或序列才是許用信號序列，這些許用信號序列可用網格結構表示，因此又稱為網格編碼調制。10.4網格編碼調制（TCM）

TCM的基本原理是基于Ungcrbeck子集劃分理論，將編碼器對信息比特的編碼轉化為對信號點的編碼，使得在信道中傳輸的信號序列遵循一定的規則，即符合網格圖中某條特定的路徑。這類信號具有如下兩個基本持征：(1)在信號空間中，信號點數目比無編碼調制情況下對應的信號點數目要多一倍．這些增加的信號點為糾錯編碼提供了冗余度，但不犧牲帶寬；(2)采用卷積碼編碼規則，在時間上相鄰的信號點之間建立依賴關系，因此僅有某些信號點圖樣或序列才是許用信號序列，這些許用信號序列可用網格結構表示，因此又稱為網格編碼調制。10.4網格編碼調制（TCM）

8PSK信號空間的集合劃分10.4網格編碼調制（TCM）

TCM編碼器的一般結構10.4網格編碼調制（TCM）

網格編碼調制的解調與譯碼采用維持比譯碼算法，它是軟判決最大似然譯碼，即在所有可能路徑中尋找與接收信號序列最接近的路徑。不過，這里使用可能發送序列與接收信號之間的歐氏距離作為度量。這部分的處理往往是決定TCM實現復雜度的關鍵環節。10.5TURBO碼

1993年Berrou等人提出的Turbo碼實際上是前人工作的巧妙綜合和發展，它的核心就是構造長序列的偽隨機性的編、譯碼。最初報告的成果表明其譯碼性能可以接近香農理論值，Turbo碼很快成為國際信息論和編碼理論界研究的熱點，并試圖應用于各種通信系統10.5TURBO碼

1Turbo碼的編碼

ClaudeBerrou教授等人最初提出的Turbo碼采用的是并行級聯卷積碼的結構。下圖給出了由兩個分量編碼器組成的Turbo碼的編碼框圖。10.5TURBO碼

1Turbo碼的編碼

Turbo碼編碼器主要由分量編碼、交織器以及刪余矩陣和復接器組成。分量碼一般選擇為遞歸系統卷積(RSC)碼,當然也可以是分組碼、非遞歸卷積碼以及非系統卷積碼。分量碼的最佳選擇是遞歸系統卷積碼。通常兩個分量碼采用相同的生成矩陣，當然，分量碼也可以是不同的。刪余矩陣：為提高碼率和系統頻譜效率，可以將兩個校驗序列經過刪余矩陣刪余后（得到）。刪余矩陣的元素取自集合{0，1}。矩陣中每一行分別與兩個分量編碼器相對應，其中“0”表示相應位置上的校驗比特被刪除，而“1”則表示保留相應位置的校驗比特。10.5TURBO碼

1Turbo碼的編碼交織器的作用：是將信息序列中的比特順序重置。當信息序列經過第一個分量編碼器編碼后輸出的碼字重量較低時，交織器可使交織后的信息序列經過第二個分量編碼器編碼后以很大的概率輸出高重碼字，從而提高碼字的漢明重量；同時好的交織器還可以有效的降低校驗序列間的相關性。通過交織，編碼序列在長為2N或3N（不經過刪余）比特的范圍內具有無記憶性，從而由簡單短碼構造了近似隨機長碼。交織器實際是一個一一映射函數，作用是將輸入信息序列中的比特位置進行重置，以減小分量編碼器輸出校驗序列的相關性和提高碼重。因此，交織器設計的好壞在很大程度上影響著Turbo碼的性能。

10.5TURBO碼

2Turbo碼的譯碼Turbo碼的譯碼通常是運用最大似然譯碼準則，采用迭代譯碼的方法實現的。

10.5TURBO碼

2Turbo碼的譯碼在TURBO碼的譯碼中采用的軟輸入、軟輸出迭代譯碼算法有多種。常見的標準有MAP算法（MAP-Maximum，即最大后驗概率算法）、對數MAP算法（log-MAP算法）、max-log-MAP算法、軟輸出維特比譯碼（SOVA—SoftOutputViterbiAlgorithms）等。10.6LDPC碼

1Ldpc碼的提出低密度奇偶校驗碼（Low-DensityParity-CheckCodcs，LDPC)碼是由Gallager于1962年提出的一種基于稀疏矩陣的線性碼。經過Tanner從圖論的角度研究LDPC碼后，MacKay和Neal重新發現并證明了迭代譯碼的LDPC碼具有漸近香農限的性能。Sac-YoungChung又證明了不規則的LDPC碼性能甚至可以距離香農限0.0045dB。這是目前已知的距離Shannon限最近的糾錯碼。

2LDPC碼的特點

逼近香農限，易于理論分析和研究，譯碼算法為迭代算法且復雜度低，可實行完全并行操作，適合硬件實現，具有高速的譯碼潛力；由于碼長較長時，相距甚遠的信息比特可能參與同一校驗約束，使得連續的突發錯誤對譯碼影響不大，因此LDPC碼本身具有很好的抗突發錯誤的能力。另外，譯碼方法的選擇很靈活，甚至是對同一種譯碼算法，也可通過對不同信道特征選擇適合自己的迭代次數等優點。10.6LDPC碼

3LDPC碼的定義

LDPC碼是一類線性分組碼，用稀疏奇偶校驗矩陣的零空間定義；所謂“稀疏性”指矩陣中包含0的個數遠大于1的個數；“低密度”指矩陣中包含1的密度很低。設碼長為n，信息位為k，則校驗位為r，校驗矩陣是一個r=n-k階的矩陣。校驗矩陣的每一行表示一個校驗約束，其中所有非零元素對應的碼元變量構成一個校驗集，由一個校驗方程表示。校驗矩陣的每一列表示碼元符號參與的校驗約束。

10.6LDPC碼

3LDPC碼的定義

二元LDPC碼的校驗矩陣矩陣的特點歸納如下：每列包含有j個1，即列重量為j；每行包含有k個1，即行重量為k；任何兩列之間同為1的行數（稱為重疊數）不超過1，即矩陣和Tanner圖中無4線循環；j和k均遠小于碼長度n和矩陣行數r，當時，10.6LDPC碼

3LDPC碼的定義

根據上述特點，Gallager給出了一個實例10.6LDPC碼

3LDPC碼的定義

根據上述特點，Gallager給出了一個實例10.6LDPC碼

（15，3，4）LDPC碼的Tanner圖表示

3LDPC碼的定義

一般情況下校驗矩陣是隨機構造的，因而是非系統形式的。編碼時對校驗矩陣進行高斯消去可得：

其中,I是單位矩陣，P是n×(n-m)階矩陣。得生成矩陣由于LDPC碼是一種線性分組碼，它的編碼可采用線性分組碼的編碼方法來完成。則LDPC碼的碼字為：10.6LDPC碼

4LDPC碼的譯碼

硬判決譯碼算法：復雜度較低，但是性能較差，在LDPC碼的研究前期比較受關注；混合譯碼算法：復雜度較高且效果并不明顯，實用價值不如其余兩種譯碼算法。軟判決譯碼算法：性能更加優異，雖然譯碼復雜度相比硬判決譯碼算法更高，但是在目前的硬件水平下已經能夠很容易實現，因此LDPC碼的軟判決譯碼算法一直是人們研究的重點。目前常用的軟判決譯碼方法主要是置信傳播（BeliefPropagation，BP）譯碼算法。10.6LDPC碼

1噴泉碼的提出

經典的RS碼或LDPC碼面臨的主要問題是：RS碼的編譯碼復雜度較大。(n,k)RS碼的標準編譯碼方法需要次運算。較大的編譯碼復雜度限制了RS碼的碼長，通常n<255。無論RS碼還是LDPC碼，其應用都基于一定的信道假設，即必須預先假設刪除信道的刪除概率（即丟包率），據此才能選取(n,k)參數，之后才能設計具體的編譯碼方法。但是實際應用中，由于信道的時變性，會出現信道優于假設和信道劣于假設的情況。10.7噴泉碼

1噴泉碼的提出

噴泉碼不僅具有很小的編譯碼復雜度，而且可以由k個原始分組生成任意數量的編碼分組，有效適應信道的時變性，而其代價僅僅是具有很小的譯碼開銷。噴泉碼(FountainCodes)只是一種比喻的說法，指該種編碼可以由k個原始數據分組生成任意數量的編碼分組，而接收方只要收到其中任意m個編碼分組，即可通過譯碼以高概率成功恢復全部原始數據分組。

10.7噴泉碼10.7噴泉碼

2噴泉碼的優點

噴泉碼是第一個無幾率刪除碼，能即時生成無限糾錯包，保護任何大小的源數據，并不受丟包率的影響。噴泉碼能在任何網絡及操作平臺上以非系統化及系統化碼的形式，在應用層、鏈路層、或應用層與鏈路層上同時運行，提高數據傳輸的可靠性。噴泉碼是線性碼。一般糾錯碼解碼復雜度是二次方，而噴泉碼是線性，因此它能處理一般糾錯碼不能處理的丟包率。10.7噴泉碼

2噴泉碼的優點

噴泉碼是通用刪除碼，因為它不受刪除率的影響，在任何刪除信道都能達到近乎最優化性能，并且在文件越大的情況下它的效率越高。噴泉碼大部分處理只是進行小數量的模二加計算。模二加的所得值與邏輯操作奇偶校驗相等，是計算機的基本操作，對處理器要求很低。因此噴泉碼的編解碼都能實用普通的電腦并高速完成。噴泉碼的應用對內存要求很低，比一般需要進行交織的糾錯碼低約8到10倍。10.7噴泉碼

3噴泉碼的分類

隨機線性編碼LT碼Raptor碼

3噴泉碼的分類

隨機線性編碼數字噴泉碼(FountainCodes)是一種與碼率無關，支持異步接入，具有線性編譯碼復雜度的新型隨機編碼方式，具有很小的編譯碼復雜度，有接近理想的糾刪性能，適合于提供針對脈沖噪聲的編碼保護。噴泉碼輸入信息單元的長度可以為任意長(從1bit到通常的kbits)。由k個原始分組生成任意數量的編碼分組，且每個編碼單元的產生相互獨立。只要接收端的信息不足以完全譯碼，就可以繼續接收，直到全部信息被成功譯出。有效適應信道的時變性，而其代價僅僅是具有很小的譯碼開銷。10.7噴泉碼

3噴泉碼的分類

隨機線性編碼噴泉碼的設計需要考慮兩方面的問題：應該盡量減小譯碼復雜度，理想情況下，應該使生成每個編碼分組需要的運算量是一個與k無關的常數，而成功譯碼m個編碼分組獲得