現(xiàn)代編碼技術(shù)

現(xiàn)代編碼技術(shù)第1頁(yè)，共61頁(yè)，2023年，2月20日，星期日

10.1

BCH碼

10.1.1

BCH碼的定義

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

BCH碼的重要性在于它解決了生成多項(xiàng)式與最小碼距之間的關(guān)系問(wèn)題。

該碼的糾錯(cuò)能力很強(qiáng)，且構(gòu)造簡(jiǎn)便。

第2頁(yè)，共61頁(yè)，2023年，2月20日，星期日

10.1

BCH碼

10.1.1

BCH碼的定義

本原多項(xiàng)式的概念。

第3頁(yè)，共61頁(yè)，2023年，2月20日，星期日 10.1

BCH碼

10.1.2

BCH碼及最小漢明距離

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

a

，a

2，a

3，…，a

d－1

那么，稱這個(gè)由g(x)生成的循環(huán)碼為設(shè)計(jì)距離為d的q元BCH碼。第4頁(yè)，共61頁(yè)，2023年，2月20日，星期日

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

BCH碼的優(yōu)勢(shì)之一在于，如果確定了BCH碼的生成多項(xiàng)式g(x)的連續(xù)根，則由g(x)生成的BCH碼的實(shí)際最小漢明距離不小于設(shè)計(jì)距離。

定理10.1.1

BCH碼的最小漢明距離至少為d。第5頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.1.3

BCH碼的編碼方法

二元BCH碼

二元信號(hào)在工程上最容易實(shí)現(xiàn)，因而二元BCH碼在工程上應(yīng)用最廣泛。對(duì)給定的正整數(shù)m和d(d=2t+1，t<2m－1)，二元BCH碼的碼長(zhǎng)、校驗(yàn)位數(shù)和最小漢明距離是什么呢？

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

3，a

5，…，a

2t－1為根，其碼長(zhǎng)n=2m－1或n|2m－1，能糾正t個(gè)錯(cuò)誤，并且n－k≤mt。

第6頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.1.3

BCH碼的譯碼方法

1.一般譯碼方法

1）確定BCH碼的伴隨式；

2）尋找錯(cuò)誤位置多項(xiàng)式；

3）糾正錯(cuò)誤；

2迭代譯碼算法第7頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2

RS碼

Reed-Solomon碼是一類有很強(qiáng)糾錯(cuò)能力的多進(jìn)制BCH碼，也是一類典型的代數(shù)幾何碼。它首先由里德（Reed）和索洛蒙（Solomon）應(yīng)用MS多項(xiàng)式于1960年構(gòu)造出來(lái)的。

它是一類糾多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼，具有嚴(yán)格的代數(shù)結(jié)構(gòu)，構(gòu)造方便，便于從理論上對(duì)應(yīng)用進(jìn)行研究。除了譯碼算法有些復(fù)雜之外，它的糾錯(cuò)能力和譯碼速度均是其它碼類無(wú)法比擬的，特別在短和中等碼長(zhǎng)下其性能接近于理論值。第8頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2.1RS碼的定義

定義:對(duì)于一個(gè)長(zhǎng)度為符號(hào)的RS碼，每個(gè)符號(hào)都可以看成是有限域GF（）中的一個(gè)元素。最小碼距為d0符號(hào)的RS碼的生成多項(xiàng)式具有如下形式：

這里，是GF（）中的一個(gè)元素。

第9頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2.1RS碼的定義

在（n,k）RS碼中，輸入信號(hào)分成kmbit一組，每個(gè)碼元由mbit組成，因此一個(gè)碼組共包括k個(gè)碼元。一個(gè)能糾正t個(gè)碼元錯(cuò)誤的RS碼的主要參數(shù)：

第10頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2.2RS碼的編碼

時(shí)域編碼：時(shí)域編譯碼算法出現(xiàn)較早，由于比較成熟而被廣泛采用；

頻域編碼：頻域編譯碼算法出現(xiàn)的較晚，但由于利用了快速傅立葉正反變換(FFT/IFFT)而提高了編譯碼速度，具有較大的發(fā)展?jié)摿Α?/p>

這兩種算法都比較簡(jiǎn)單，時(shí)域編碼只需要運(yùn)算一次多項(xiàng)式除法，而頻域編碼只需要計(jì)算一次IFFT。

第11頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2.2RS碼的編碼

它們的區(qū)別在于：經(jīng)時(shí)域算法得到的碼字是系統(tǒng)碼，可用于截短編碼；而頻域算法得到的碼字是非系統(tǒng)碼，不能用于截短編碼。

時(shí)域編碼：

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

RS碼的編碼方法與CRC一樣，也是除以，所以同樣可以采用移位寄存器來(lái)實(shí)現(xiàn)。

第12頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2.2RS碼的編碼

時(shí)域編碼：

n-k級(jí)線性移位寄存器編碼電路第13頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2.2RS碼的編碼

它們的區(qū)別在于：經(jīng)時(shí)域算法得到的碼字是系統(tǒng)碼，可用于截短編碼；而頻域算法得到的碼字是非系統(tǒng)碼，不能用于截短編碼。

時(shí)域編碼：

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

RS碼的編碼方法與CRC一樣，也是除以，所以同樣可以采用移位寄存器來(lái)實(shí)現(xiàn)。

第14頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2.3

RS碼的譯碼方法

RS碼的譯碼算法比其它碼類的譯碼算法復(fù)雜得多，這是因?yàn)镽S碼是一種非二元循環(huán)碼，它不再具備特征為2的域的運(yùn)算等性質(zhì)。

分類：

RS碼的頻域譯碼算法：RS碼的時(shí)域譯碼算法：也是從計(jì)算接收碼字的伴隨式入手的，并且在譯碼過(guò)程中不僅要找出錯(cuò)誤位置，而且還要找出對(duì)應(yīng)錯(cuò)誤位置的錯(cuò)誤大小，這樣就增加了它的譯碼難度。第15頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.2.3

RS碼的譯碼方法

RS碼的譯碼算法步驟：

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

(2)由伴隨式求出錯(cuò)誤位置多項(xiàng)式；

(3)由錯(cuò)誤位置多項(xiàng)式求出錯(cuò)誤位置值；

(4)由錯(cuò)誤位置值求出對(duì)應(yīng)的錯(cuò)誤值；

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

第16頁(yè)，共61頁(yè)，2023年，2月20日，星期日 10.3卷積碼的表示方法

10.3.1卷積碼的概念

卷積碼是由伊利亞斯提出，其信息碼個(gè)數(shù)和碼長(zhǎng)通常較小，故時(shí)延小，特別適合于以串行形式傳輸?shù)膱?chǎng)合。

另外，卷積碼在任何一個(gè)碼組中的監(jiān)督碼元都不僅與本碼組的信息碼元有關(guān)，而且還與前面若干個(gè)碼組的信息碼元有關(guān)，其糾錯(cuò)能力隨著前面若干個(gè)碼組數(shù)的增加而增加。故在實(shí)際應(yīng)用中，卷積碼的性能優(yōu)于分組碼，而且設(shè)備簡(jiǎn)單。

第17頁(yè)，共61頁(yè)，2023年，2月20日，星期日 10.3卷積碼的表示方法

10.3.1卷積碼的概念

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

(n，k，m)卷積碼編碼器第18頁(yè)，共61頁(yè)，2023年，2月20日，星期日 10.2卷積碼的表示方法

10.3.1卷積碼的概念

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

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

編碼單元的功能是把k路并行輸入信元變成n路并行輸出。是卷積碼中最關(guān)鍵的部分。第19頁(yè)，共61頁(yè)，2023年，2月20日，星期日 10.2卷積碼的表示方法

10.3.1卷積碼的概念

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

第20頁(yè)，共61頁(yè)，2023年，2月20日，星期日 10.2卷積碼的表示方法

10.3.1卷積碼的概念

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

第21頁(yè)，共61頁(yè)，2023年，2月20日，星期日 10.2卷積碼的表示方法

10.3.1卷積碼的概念

當(dāng)有k位數(shù)據(jù)輸入時(shí)，輸出碼字序列共有卷積碼的編碼效率為第22頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.3.2卷積碼的表示法

1.卷積碼的多項(xiàng)式

用符號(hào)D表示延時(shí)算子，輸入信息x中的相對(duì)于來(lái)說(shuō)晚1個(gè)時(shí)刻(即一個(gè)碼元時(shí)間長(zhǎng)度)出現(xiàn)，相對(duì)于晚2個(gè)時(shí)刻出現(xiàn)，其余以此類推。用Dk表示延時(shí)k個(gè)時(shí)刻，這樣，我們可以把輸入信息x用一個(gè)多項(xiàng)式表示，即

2.卷積碼的生成矩陣

第23頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.3.3卷積碼的圖形表示法

1.樹(shù)狀圖

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

卷積碼的樹(shù)狀圖由節(jié)點(diǎn)和樹(shù)枝組成，從一個(gè)初始節(jié)點(diǎn)(稱為樹(shù)根)開(kāi)始，根據(jù)輸入信息碼元是０還是１進(jìn)行分枝，通常信息碼元為０時(shí)向上分枝，信息碼元為１時(shí)向下分枝，并將輸出的碼字標(biāo)于樹(shù)枝上。第24頁(yè)，共61頁(yè)，2023年，2月20日，星期日卷積碼的樹(shù)狀圖見(jiàn)圖。圖(2，1，2)卷積碼的樹(shù)狀圖第25頁(yè)，共61頁(yè)，2023年，2月20日，星期日

2.狀態(tài)圖

狀態(tài)圖主要用來(lái)反映卷積碼編碼器的可能狀態(tài)，以及由一個(gè)狀態(tài)可能向哪些狀態(tài)轉(zhuǎn)移。第26頁(yè)，共61頁(yè)，2023年，2月20日，星期日

3.網(wǎng)格圖

樹(shù)狀圖能清晰地反映編碼路徑，標(biāo)出了各個(gè)時(shí)刻的編碼狀態(tài)，但不能反映狀態(tài)間的轉(zhuǎn)移；狀態(tài)圖能緊湊地反映狀態(tài)間的轉(zhuǎn)移情況，但不能顯示編碼路徑及各個(gè)時(shí)刻的編碼狀態(tài)。網(wǎng)格圖有機(jī)地結(jié)合了兩者的優(yōu)點(diǎn)，如圖所示。

第27頁(yè)，共61頁(yè)，2023年，2月20日，星期日?qǐng)D(2，1，2)卷積碼的網(wǎng)格圖第28頁(yè)，共61頁(yè)，2023年，2月20日，星期日 4.2卷積碼的譯碼方法

卷積碼的譯碼方法主要有代數(shù)譯碼法和概率譯碼法。代數(shù)譯碼法有與分組碼相似的伴隨式、錯(cuò)誤圖樣等概念，利用伴隨式進(jìn)行檢錯(cuò)、糾錯(cuò)。概率譯碼法則利用信道統(tǒng)計(jì)特性，對(duì)接收序列進(jìn)行最大似然判決，目前，概率譯碼法普遍通過(guò)維特比(Viterbi)譯碼算法和費(fèi)諾(Fano)譯碼算法來(lái)實(shí)現(xiàn)。第29頁(yè)，共61頁(yè)，2023年，2月20日，星期日

1.維特比算法

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

當(dāng)k較大時(shí)，由于存儲(chǔ)量太大，應(yīng)用受到限制。由于接收序列通常很長(zhǎng)，所以維特比譯碼是最大似然譯碼算法的簡(jiǎn)化。簡(jiǎn)化的方法是：它把接收碼字分段處理，每接收一段碼字，計(jì)算、比較—次，保留碼距最小的路徑，直至譯完整個(gè)序列。

第30頁(yè)，共61頁(yè)，2023年，2月20日，星期日2序列譯碼

當(dāng)m很大時(shí)，可以采用序列譯碼法，該譯碼方法可避免漫長(zhǎng)的搜索過(guò)程。譯碼先從樹(shù)狀圖的起始節(jié)點(diǎn)開(kāi)始，把接收到的第一個(gè)子碼的n個(gè)碼元與自始節(jié)點(diǎn)出發(fā)的兩條分支按照最小漢明距離進(jìn)行比較，沿著差異最小的分支走向第二個(gè)節(jié)點(diǎn)；

3門(mén)限譯碼

除上述的維特比譯碼法、序列譯碼法外，卷積碼的另一種譯碼方法為門(mén)限譯碼法。門(mén)限譯碼又稱大數(shù)邏輯譯碼。門(mén)限譯碼的設(shè)備簡(jiǎn)單，譯碼速度快，約束長(zhǎng)度可較大，適用于有突發(fā)錯(cuò)誤的信道。

第31頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.4網(wǎng)格編碼調(diào)制（TCM）

TCM的基本原理是基于Ungcrbeck子集劃分理論，將編碼器對(duì)信息比特的編碼轉(zhuǎn)化為對(duì)信號(hào)點(diǎn)的編碼，使得在信道中傳輸?shù)男盘?hào)序列遵循一定的規(guī)則，即符合網(wǎng)格圖中某條特定的路徑。這類信號(hào)具有如下兩個(gè)基本持征：(1)在信號(hào)空間中，信號(hào)點(diǎn)數(shù)目比無(wú)編碼調(diào)制情況下對(duì)應(yīng)的信號(hào)點(diǎn)數(shù)目要多一倍．這些增加的信號(hào)點(diǎn)為糾錯(cuò)編碼提供了冗余度，但不犧牲帶寬；

(2)采用卷積碼編碼規(guī)則，在時(shí)間上相鄰的信號(hào)點(diǎn)之間建立依賴關(guān)系，因此僅有某些信號(hào)點(diǎn)圖樣或序列才是許用信號(hào)序列，這些許用信號(hào)序列可用網(wǎng)格結(jié)構(gòu)表示，因此又稱為網(wǎng)格編碼調(diào)制。第32頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.4網(wǎng)格編碼調(diào)制（TCM）

TCM的基本原理是基于Ungcrbeck子集劃分理論，將編碼器對(duì)信息比特的編碼轉(zhuǎn)化為對(duì)信號(hào)點(diǎn)的編碼，使得在信道中傳輸?shù)男盘?hào)序列遵循一定的規(guī)則，即符合網(wǎng)格圖中某條特定的路徑。這類信號(hào)具有如下兩個(gè)基本持征：(1)在信號(hào)空間中，信號(hào)點(diǎn)數(shù)目比無(wú)編碼調(diào)制情況下對(duì)應(yīng)的信號(hào)點(diǎn)數(shù)目要多一倍．這些增加的信號(hào)點(diǎn)為糾錯(cuò)編碼提供了冗余度，但不犧牲帶寬；

(2)采用卷積碼編碼規(guī)則，在時(shí)間上相鄰的信號(hào)點(diǎn)之間建立依賴關(guān)系，因此僅有某些信號(hào)點(diǎn)圖樣或序列才是許用信號(hào)序列，這些許用信號(hào)序列可用網(wǎng)格結(jié)構(gòu)表示，因此又稱為網(wǎng)格編碼調(diào)制。第33頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.4網(wǎng)格編碼調(diào)制（TCM）

8PSK信號(hào)空間的集合劃分第34頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.4網(wǎng)格編碼調(diào)制（TCM）

TCM編碼器的一般結(jié)構(gòu)第35頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.4網(wǎng)格編碼調(diào)制（TCM）

網(wǎng)格編碼調(diào)制的解調(diào)與譯碼采用維持比譯碼算法，它是軟判決最大似然譯碼，即在所有可能路徑中尋找與接收信號(hào)序列最接近的路徑。不過(guò)，這里使用可能發(fā)送序列與接收信號(hào)之間的歐氏距離作為度量。這部分的處理往往是決定TCM實(shí)現(xiàn)復(fù)雜度的關(guān)鍵環(huán)節(jié)。第36頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.5TURBO碼

1993年Berrou等人提出的Turbo碼實(shí)際上是前人工作的巧妙綜合和發(fā)展，它的核心就是構(gòu)造長(zhǎng)序列的偽隨機(jī)性的編、譯碼。最初報(bào)告的成果表明其譯碼性能可以接近香農(nóng)理論值，Turbo碼很快成為國(guó)際信息論和編碼理論界研究的熱點(diǎn)，并試圖應(yīng)用于各種通信系統(tǒng)第37頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.5TURBO碼

1Turbo碼的編碼

ClaudeBerrou教授等人最初提出的Turbo碼采用的是并行級(jí)聯(lián)卷積碼的結(jié)構(gòu)。下圖給出了由兩個(gè)分量編碼器組成的Turbo碼的編碼框圖。第38頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.5TURBO碼

1Turbo碼的編碼

Turbo碼編碼器主要由分量編碼、交織器以及刪余矩陣和復(fù)接器組成。分量碼一般選擇為遞歸系統(tǒng)卷積(RSC)碼,當(dāng)然也可以是分組碼、非遞歸卷積碼以及非系統(tǒng)卷積碼。分量碼的最佳選擇是遞歸系統(tǒng)卷積碼。通常兩個(gè)分量碼采用相同的生成矩陣，當(dāng)然，分量碼也可以是不同的。刪余矩陣：為提高碼率和系統(tǒng)頻譜效率，可以將兩個(gè)校驗(yàn)序列經(jīng)過(guò)刪余矩陣刪余后（得到）。刪余矩陣的元素取自集合{0，1}。矩陣中每一行分別與兩個(gè)分量編碼器相對(duì)應(yīng)，其中“0”表示相應(yīng)位置上的校驗(yàn)比特被刪除，而“1”則表示保留相應(yīng)位置的校驗(yàn)比特。第39頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.5TURBO碼

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

第40頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.5TURBO碼

2Turbo碼的譯碼

Turbo碼的譯碼通常是運(yùn)用最大似然譯碼準(zhǔn)則，采用迭代譯碼的方法實(shí)現(xiàn)的。

第41頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.5TURBO碼

2Turbo碼的譯碼在TURBO碼的譯碼中采用的軟輸入、軟輸出迭代譯碼算法有多種。常見(jiàn)的標(biāo)準(zhǔn)有MAP算法（MAP-Maximum，即最大后驗(yàn)概率算法）、對(duì)數(shù)MAP算法（log-MAP算法）、max-log-MAP算法、軟輸出維特比譯碼（SOVA—SoftOutputViterbiAlgorithms）等。第42頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.6LDPC碼

1Ldpc碼的提出低密度奇偶校驗(yàn)碼（Low-DensityParity-CheckCodcs，LDPC)碼是由Gallager于1962年提出的一種基于稀疏矩陣的線性碼。經(jīng)過(guò)Tanner從圖論的角度研究LDPC碼后，MacKay和Neal重新發(fā)現(xiàn)并證明了迭代譯碼的LDPC碼具有漸近香農(nóng)限的性能。Sac-YoungChung又證明了不規(guī)則的LDPC碼性能甚至可以距離香農(nóng)限0.0045dB。這是目前已知的距離Shannon限最近的糾錯(cuò)碼。第43頁(yè)，共61頁(yè)，2023年，2月20日，星期日

2LDPC碼的特點(diǎn)

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

第44頁(yè)，共61頁(yè)，2023年，2月20日，星期日

3LDPC碼的定義

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

10.6LDPC碼

第45頁(yè)，共61頁(yè)，2023年，2月20日，星期日3LDPC碼的定義

二元LDPC碼的校驗(yàn)矩陣矩陣的特點(diǎn)歸納如下：每列包含有j個(gè)1，即列重量為j；每行包含有k個(gè)1，即行重量為k；任何兩列之間同為1的行數(shù)（稱為重疊數(shù)）不超過(guò)1，即矩陣和Tanner圖中無(wú)4線循環(huán)；j和k均遠(yuǎn)小于碼長(zhǎng)度n和矩陣行數(shù)r，當(dāng)時(shí)，10.6LDPC碼

第46頁(yè)，共61頁(yè)，2023年，2月20日，星期日3LDPC碼的定義

根據(jù)上述特點(diǎn)，Gallager給出了一個(gè)實(shí)例10.6LDPC碼

第47頁(yè)，共61頁(yè)，2023年，2月20日，星期日3LDPC碼的定義

根據(jù)上述特點(diǎn)，Gallager給出了一個(gè)實(shí)例10.6LDPC碼

（15，3，4）LDPC碼的Tanner圖表示第48頁(yè)，共61頁(yè)，2023年，2月20日，星期日

3LDPC碼的定義

一般情況下校驗(yàn)矩陣是隨機(jī)構(gòu)造的，因而是非系統(tǒng)形式的。編碼時(shí)對(duì)校驗(yàn)矩陣進(jìn)行高斯消去可得：

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

第49頁(yè)，共61頁(yè)，2023年，2月20日，星期日

4LDPC碼的譯碼

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

第50頁(yè)，共61頁(yè)，2023年，2月20日，星期日

1噴泉碼的提出

經(jīng)典的RS碼或LDPC碼面臨的主要問(wèn)題是：RS碼的編譯碼復(fù)雜度較大。(n,k)RS碼的標(biāo)準(zhǔn)編譯碼方法需要次運(yùn)算。較大的編譯碼復(fù)雜度限制了RS碼的碼長(zhǎng)，通常n<255。無(wú)論RS碼還是LDPC碼，其應(yīng)用都基于一定的信道假設(shè)，即必須預(yù)先假設(shè)刪除信道的刪除概率（即丟包率），據(jù)此才能選取(n,k)參數(shù)，之后才能設(shè)計(jì)具體的編譯碼方法。但是實(shí)際應(yīng)用中，由于信道的時(shí)變性，會(huì)出現(xiàn)信道優(yōu)于假設(shè)和信道劣于假設(shè)的情況。10.7噴泉碼第51頁(yè)，共61頁(yè)，2023年，2月20日，星期日

1噴泉碼的提出

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

10.7噴泉碼第52頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.7噴泉碼

2噴泉碼的優(yōu)點(diǎn)

噴泉碼是第一個(gè)無(wú)幾率刪除碼，能即時(shí)生成無(wú)限糾錯(cuò)包，保護(hù)任何大小的源數(shù)據(jù)，并不受丟包率的影響。噴泉碼能在任何網(wǎng)絡(luò)及操作平臺(tái)上以非系統(tǒng)化及系統(tǒng)化碼的形式，在應(yīng)用層、鏈路層、或應(yīng)用層與鏈路層上同時(shí)運(yùn)行，提高數(shù)據(jù)傳輸?shù)目煽啃?。噴泉碼是線性碼。一般糾錯(cuò)碼解碼復(fù)雜度是二次方，而噴泉碼是線性，因此它能處理一般糾錯(cuò)碼不能處理的丟包率。第53頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.7噴泉碼

2噴泉碼的優(yōu)點(diǎn)

噴泉碼是通用刪除碼，因?yàn)樗皇軇h除率的影響，在任何刪除信道都能達(dá)到近乎最優(yōu)化性能，并且在文件越大的情況下它的效率越高。噴泉碼大部分處理只是進(jìn)行小數(shù)量的模二加計(jì)算。模二加的所得值與邏輯操作奇偶校驗(yàn)相等，是計(jì)算機(jī)的基本操作，對(duì)處理器要求很低。因此噴泉碼的編解碼都能實(shí)用普通的電腦并高速完成。噴泉碼的應(yīng)用對(duì)內(nèi)存要求很低，比一般需要進(jìn)行交織的糾錯(cuò)碼低約8到10倍。第54頁(yè)，共61頁(yè)，2023年，2月20日，星期日10.7噴泉碼

3噴泉碼的分類

隨機(jī)線性編碼LT碼Raptor碼第55頁(yè)，共61頁(yè)，2023年，2月20日，星期日

3噴泉碼的分類

隨機(jī)線性編碼數(shù)字噴泉碼(FountainCodes)是一種與碼