糾錯碼Lecture10-LDPC

1、信道編碼理論信道編碼理論邢莉娟，李卓，西安電子科技大學(xué)邢莉娟，李卓，西安電子科技大學(xué)Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論2 LDPC碼的簡介碼的簡介 Tanner圖圖 LDPC碼的幾何構(gòu)造方法碼的幾何構(gòu)造方法 LDPC碼的譯碼方法碼的譯碼方法Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論3LDPC碼是另外一類逼近碼是另外一類逼近Shannon-Limit的碼，是的碼，是由由Gallager在在1960s提出的提出的,與與Turbo碼相比，碼相比，LDPC碼有如下優(yōu)點：碼有如下優(yōu)點： (1)不需要長的交

2、織器來達到好的譯碼性能不需要長的交織器來達到好的譯碼性能. (2)誤比特率誤比特率(BER)達到更低達到更低. (3)錯誤平層在更低的誤比特率錯誤平層在更低的誤比特率(BER)出現(xiàn)出現(xiàn). (4)譯碼不需要譯碼不需要Trellis.Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論4 Gallager提出了提出了LDPC碼，但并沒有給出方法來系碼，但并沒有給出方法來系統(tǒng)的構(gòu)造統(tǒng)的構(gòu)造LDPC碼，只給出了一類隨機碼，只給出了一類隨機LDPC碼的碼的構(gòu)造方法，被發(fā)現(xiàn)的好的構(gòu)造方法，被發(fā)現(xiàn)的好的LDPC碼都是由計算機碼都是由計算機搜索得到的，搜索得到的，LinSh

3、u給出了一類基于有限域的給出了一類基于有限域的LDPC碼代數(shù)構(gòu)造方法，這類碼代數(shù)構(gòu)造方法，這類LDPC碼有著相對較碼有著相對較好的好的 ，并不存在短環(huán)，譯碼性能也不錯，此，并不存在短環(huán)，譯碼性能也不錯，此外，這類碼都是循環(huán)或準(zhǔn)循環(huán)的，編碼器可用線外，這類碼都是循環(huán)或準(zhǔn)循環(huán)的，編碼器可用線性移存器來實現(xiàn)。性移存器來實現(xiàn)。mindLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論5第二章中講到，一個線性分組碼可由其生成矩陣第二章中講到，一個線性分組碼可由其生成矩陣G及校驗及校驗矩陣矩陣H唯一的確定，并且唯一的確定，并且G是是H的零空間，一個在二元域上的零空間，

4、一個在二元域上的的n-維矢量維矢量 V= ( ) 是碼字的充要條件是是碼字的充要條件是 。 LDPC是根據(jù)其校驗矩陣定義的：是根據(jù)其校驗矩陣定義的：1210.nnvvvvTVH 0Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論6定義定義1：給定校驗矩陣：給定校驗矩陣H，若其零空間為，若其零空間為LDPC碼，碼，則該則該H的結(jié)構(gòu)具有以下特征。的結(jié)構(gòu)具有以下特征。 (1)每一行包含每一行包含 個非零元（個非零元（1）。）。 (2)每一列包含每一列包含 個非零元。個非零元。 (3)任意兩列有相同任意兩列有相同1的個數(shù)記為的個數(shù)記為 ，=0或或1。 (4) 與

5、與 與碼長與與碼長與H的行的個數(shù)比較起來非常小。的行的個數(shù)比較起來非常小。 說明：說明：(1)與與(2)說明說明H具有恒定的行重具有恒定的行重 和列和列重重 ,(3)說明說明H中任意兩行相同中任意兩行相同1的個數(shù)不超過的個數(shù)不超過1。(4)說明說明H中非零元的密度非常少，中非零元的密度非常少，H是一個是一個Low-Density Parity-Check Matrix，由這樣的，由這樣的H所確定所確定的碼就是的碼就是LDPC碼。碼。Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論7H的密度的密度r定義為定義為r= = 。 J為為H中的行數(shù)，中的行數(shù)，H的

6、低密度說明的低密度說明H為稀疏矩陣。為稀疏矩陣。 由上述由上述定義定義得到的得到的LDPC碼稱為碼稱為( , )-規(guī)則規(guī)則 LDPC碼碼，如果，如果H的行重與列重都不相同，得到的的行重與列重都不相同，得到的 是是非規(guī)則非規(guī)則-LDPC碼碼，本章主要討論規(guī)則碼一類，本章主要討論規(guī)則碼一類， H中每一行并不是線性獨立的，因此要求碼的維中每一行并不是線性獨立的，因此要求碼的維 數(shù)，需要首先確定數(shù)，需要首先確定H的秩。的秩。nJLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論8 H = 00000001101000110000000110100001000000

7、0110100001000000011010000100000001101100010000000110010001000000011101000100000001110100010000000011010001000000001101000100000000110100010000000011010001000000001101000100000000110100010Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論9 例例1： 上圖給出的上圖給出的H(見書見書P853圖圖17.1),每行與每每行與每列包含列包含4個個1,是一個是一個(4,4)-規(guī)則規(guī)

8、則LDPC碼碼,可以看到任可以看到任意兩列意兩列(行行)相同相同1 的個數(shù)都不超過的個數(shù)都不超過1,密度密度r= =0.267,該矩陣的零空間給出一個該矩陣的零空間給出一個(15,7)LDPC碼碼,其其 =5.nmindLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論10下面給出構(gòu)造隨機下面給出構(gòu)造隨機LDPC碼的碼的H的方法的方法 令令 且且 為正整數(shù)。為正整數(shù)。 給定給定 與與 ,構(gòu)造一個構(gòu)造一個 維的矩陣維的矩陣H。 H包含包含 個個 維子矩陣維子矩陣 ,每個子每個子矩陣中的每行有矩陣中的每行有 個個1,每個子陣的每列只包含每個子陣的每列只包含1個

9、個1,因此因此,每個子陣每個子陣1的個數(shù)為的個數(shù)為 。 當(dāng)當(dāng) 時時, 的第的第 行在第行在第 列列到第到第 列的位置上為列的位置上為1,其余為其余為0。其它子陣只是。其它子陣只是的列置換。的列置換。1kkkkk k12HHHk1ik1Hi(1)1ii1HLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論11 H = 由上述方法構(gòu)造的由上述方法構(gòu)造的H矩陣矩陣,有以下的幾個結(jié)論。有以下的幾個結(jié)論。 (1)在在H的每個子矩陣中的每個子矩陣中,任意兩行都不存在有相同任意兩行都不存在有相同1的情況。的情況。 (2)H的每個子陣中的每個子陣中,任意兩列相同任意兩列相

10、同1的個數(shù)的個數(shù) 。12HHH1Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論12 在在H中中1的個數(shù)共有的個數(shù)共有 位位,而而H共有元素共有元素 ,H的密度為的密度為 ,當(dāng)當(dāng) 取值遠遠大于取值遠遠大于1,則則H為小密度，為小密度，也就是稀疏矩陣。也就是稀疏矩陣。 H是否滿足是否滿足定義定義 第三條的性質(zhì)取決于對第三條的性質(zhì)取決于對 采取哪采取哪種方式進行列置換得到其余種方式進行列置換得到其余 個子陣個子陣, 的零的零空間可能確定的是一個空間可能確定的是一個 的線性分組碼的線性分組碼,不一不一定是一個定是一個LDPC碼碼,因此因此LDPC碼是線性分組碼

11、的碼是線性分組碼的一個子類。一個子類。 Gallager并沒有給出一種有效的置換方式使得并沒有給出一種有效的置換方式使得 得到其他子陣得到其他子陣 ,并且并且H滿足定義的滿足定義的所有性質(zhì)。目前，都借助于計算機來搜索好的所有性質(zhì)。目前，都借助于計算機來搜索好的LDPC碼，尤其在碼，尤其在n較大的時候。較大的時候。k2k1kk1H11Hnk1H12HHHLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論13令令 構(gòu)造一個構(gòu)造一個 的的H矩陣如下所示矩陣如下所示 H =5,4,3,k15 201111000000000000000000001111000000

12、00000000000000111100000000000000000000111100000000000000000000111110001000100010000000010001000100000010000010001000000100010000010000001000100010000000010001000100011000010000010000010001000010001000010000001000010000100000100001000010000100100000001000010000100001Lecture 10 LDPCLecture 10 LDPC碼碼信道

13、編碼理論信道編碼理論14H包含包含3個個 的子陣的子陣 ， 中每行包含中每行包含4個個1，任意兩行沒有相同的，任意兩行沒有相同的1. 與與 由由 置換得到。置換得到。H中任意兩列中任意兩列(行行)相同相同1的個數(shù)不超過的個數(shù)不超過1，而，而H的密度的密度 =0.20,因此因此,這樣的這樣的H確定的是一個確定的是一個LDPC碼碼,碼的參數(shù)是碼的參數(shù)是(20,7)，最小距離最小距離 =6.5 20123,HHH1H2H3H1H1rkmindLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論15一個圖一個圖(Graph)G包括頂點集合包括頂點集合 ,與與邊集合邊

14、集合 ,并且每條邊并且每條邊 確定，確定，這樣的圖這樣的圖G由由G= 來標(biāo)記。邊來標(biāo)記。邊 的頂點的頂點 稱為稱為 的終端頂點。的終端頂點。 頂點頂點 所連接邊的個數(shù)稱為該頂點的度，記所連接邊的個數(shù)稱為該頂點的度，記 例例 2：一個圖包括：一個圖包括6個頂點個頂點,10條邊條邊,如下圖。如下圖。 12vvv12ee(,)ijvv( , )vke(,)ijvvkeiv( )id vLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論16Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論17邊邊b連接點連接點 和和 ,頂點頂

15、點 連接邊連接邊b,c,d。 所以所以 =3。 連接同一頂點的兩條邊稱為相鄰連接同一頂點的兩條邊稱為相鄰(adjacent)。 連接一條邊的兩個頂點也可稱為相鄰連接一條邊的兩個頂點也可稱為相鄰(adjacent)。 例如，上圖中邊例如，上圖中邊a和和b，頂點，頂點 和和 相鄰。相鄰。 有限個頂點與邊組成的圖是有限個頂點與邊組成的圖是有限圖有限圖。 路徑：由某個頂點開始，到某個頂點結(jié)束，經(jīng)過路徑：由某個頂點開始，到某個頂點結(jié)束，經(jīng)過這些頂點所連接的邊，并且每個頂點出現(xiàn)的不超這些頂點所連接的邊，并且每個頂點出現(xiàn)的不超過一次，這樣的組合稱為路徑。過一次，這樣的組合稱為路徑。1v2v2v2()d v1

16、v2vLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論18路徑中邊的個數(shù)稱為該路徑的長度路徑中邊的個數(shù)稱為該路徑的長度(length)。 在例在例2中，中， ,b, ,c, ,h, ,g, 是一條長度為是一條長度為4的路徑，如下圖。的路徑，如下圖。 1v2v4v5v3vV1V5V2V3V4abcdefghijV6Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論19環(huán)：若路徑的起始與結(jié)束頂點相同環(huán)：若路徑的起始與結(jié)束頂點相同,這樣的閉合路這樣的閉合路徑成為環(huán)。除了起始與結(jié)束頂點徑成為環(huán)。除了起始與結(jié)束頂點,環(huán)中的其余

17、頂點環(huán)中的其余頂點出現(xiàn)的次數(shù)不超過一次。出現(xiàn)的次數(shù)不超過一次。 在例在例2中，中， ,f, ,g, ,j, ,i, 是長度為是長度為4的環(huán)，的環(huán)，如下。如下。1v5v3v1v6vV1V5V2V3V4abcdefghijV6Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論20長度為長度為1的環(huán)稱為自環(huán)的環(huán)稱為自環(huán),圖中最短歡的長度稱為圖圖中最短歡的長度稱為圖的圍長的圍長(grith),在例在例2中中,圖的圍長為圖的圍長為3。樹：一個不存在環(huán)的圖成為樹。樹：一個不存在環(huán)的圖成為樹。 例例 3 連接的圖：連接的圖：G中每對頂點至少有一條邊相連，該中每對頂點至少

18、有一條邊相連，該圖稱為連接的圖稱為連接的(connected)。 例例2, 3中的圖都是連接的。中的圖都是連接的。Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論21雙向圖雙向圖(bipartite graph)：圖：圖G= ，若將其頂，若將其頂點點 劃分成劃分成 和和 兩部分兩部分,使得使得 中的每條邊都連中的每條邊都連接的是接的是 中的一個頂點與中的一個頂點與 中的一個頂點，并且中的一個頂點，并且 與與 中任意兩個頂點不相連中任意兩個頂點不相連,這樣的圖不存在自環(huán)。這樣的圖不存在自環(huán)。 例例 雙向圖雙向圖 ( , )v1VV2V1V2V1V2V112

19、3Vvvv245678VvvvvvLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論22如果雙向圖中存在環(huán)，則環(huán)的長度必為偶數(shù)。如果雙向圖中存在環(huán)，則環(huán)的長度必為偶數(shù)。Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論23 線性碼關(guān)于圖的應(yīng)用非常多線性碼關(guān)于圖的應(yīng)用非常多,例如卷積碼中的例如卷積碼中的Trellis,網(wǎng)絡(luò)編碼中的樹表示及網(wǎng)絡(luò)編碼中的樹表示及LDPC碼的碼的Tanner 圖表示。圖表示。 Tanner圖：表示的是碼字比特與其校驗比特和之圖：表示的是碼字比特與其校驗比特和之間的關(guān)系。間的關(guān)系。 一個碼長為一

20、個碼長為n的線性分組碼，其校驗矩陣為的線性分組碼，其校驗矩陣為H，H的每行表示為的每行表示為 ,共共J行。行。 根據(jù)碼字與根據(jù)碼字與H，可構(gòu)造一個圖，可構(gòu)造一個圖 , 包含兩組頂包含兩組頂點點 和和 。 中包含中包含n個頂點個頂點,代表代表n位碼字比特位碼字比特,標(biāo)記為標(biāo)記為12,Jh hh TGTG1V2V1V011nvvvLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論24 稱為稱為碼字頂點集合碼字頂點集合。 定義定義2： 則則 稱為校驗和。稱為校驗和。1V,0,1,2,1jjjjj nhhhhh1jJ0121nvvvvv1,00njjlj llsv

21、 hv h jSLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論25若若 ,則稱碼字比特則稱碼字比特 被被 校驗。校驗。 中包含中包含J個頂點，分別是個頂點，分別是 , 稱稱為校驗和頂點集合。為校驗和頂點集合。 當(dāng)且僅當(dāng)碼字比特當(dāng)且僅當(dāng)碼字比特 被被 校驗，在校驗，在 圖中碼字節(jié)圖中碼字節(jié)點點 和校驗節(jié)點和校驗節(jié)點 通過一條邊項鏈，標(biāo)記為通過一條邊項鏈，標(biāo)記為 顯然顯然 為一雙向圖，由為一雙向圖，由Tanner在在1981年提出，主年提出，主要用于要用于LDPC碼的迭代譯碼研碼的迭代譯碼研,稱為稱為Tanner圖圖 。lv,1j lhjS2V12Jsss

22、2VlvjSTGlvjS( ,)ljv sTGLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論26Tanner圖中圖中 的度等于校驗和中包括的度等于校驗和中包括 的個數(shù)。的個數(shù)。 的度等于被的度等于被 校驗的碼字比特的個數(shù)。校驗的碼字比特的個數(shù)。 對于對于LDPC碼來說碼來說,每個碼字節(jié)點的度都相同每個碼字節(jié)點的度都相同,等于等于 (即即H的列重的列重),每個校驗節(jié)點的度都等于每個校驗節(jié)點的度都等于 (H的的行重行重). 這樣的圖成為規(guī)則這樣的圖成為規(guī)則Tanner圖。圖。 *由定義由定義1(3)可知可知,不存在兩個碼字節(jié)點同時被兩個不存在兩個碼字節(jié)點同

23、時被兩個校驗節(jié)點檢驗的情況校驗節(jié)點檢驗的情況,即即LDPC碼的碼的 不包括長度不包括長度為為4的環(huán)。的環(huán)。lvlvjSjSTGLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論27由于對由于對LDPC碼采用基于碼采用基于belief propagation(置信置信傳播傳播)的迭代譯碼算法的迭代譯碼算法,要求在要求在Tanner圖中不存在圖中不存在短環(huán)短環(huán),尤其是長度為尤其是長度為4的環(huán)的環(huán),4環(huán)為譯碼有很大的影響。環(huán)為譯碼有很大的影響。例例6 (7,3)LDPC碼。碼。 *不包括不包括4環(huán)環(huán) 但包括但包括6環(huán)環(huán) Tanner圖圍長是圖圍長是6 11010

24、00011010000110100001101100011001000111010001HLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論28校驗節(jié)點校驗節(jié)點Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論29本節(jié)介紹兩種基于有限幾何本節(jié)介紹兩種基于有限幾何(finite geometry)的的LDPC碼的構(gòu)造方法，碼的構(gòu)造方法，方法一：方法一： Q：有限幾何，包括：有限幾何，包括n個點個點,J條線。條線。 具有以下的性質(zhì)：具有以下的性質(zhì)： (1)每條線包含每條線包含 個點。個點。 (2)每個點由每個點由 條線確定

25、。條線確定。 (3)任意兩點僅由一條線相連。任意兩點僅由一條線相連。 (4)任意兩條線要么是不相鄰的任意兩條線要么是不相鄰的(即沒有共同點即沒有共同點),要要么只相交于一點。么只相交于一點。Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論30將將Q中的點集合標(biāo)記為中的點集合標(biāo)記為 ,線集合表示線集合表示為為 ,令令 為為GF(2)中的中的n維矢量。維矢量。 與與Q中的頂點集合相對應(yīng)。中的頂點集合相對應(yīng)。 若若L為為Q中的某條線中的某條線,定義如下向量定義如下向量 當(dāng)當(dāng) ,若若 是是L線上的點線上的點 ,否則否則 12nPPP12nLLL12nvvvvvi

26、ivP12lnvvvv10iviPLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論31 顯然該向量的重量為顯然該向量的重量為 。 構(gòu)造構(gòu)造 ,該矩陣為該矩陣為 維。維。 其：每行代表其：每行代表Q中的中的J條線。條線。 每列代表每列代表Q中的中的n個點。個點。 由由Q的性質(zhì)得到關(guān)于的性質(zhì)得到關(guān)于 的一下結(jié)論。的一下結(jié)論。 (1)每行有每行有 個個1。 (2)每列有每列有 個個1（由以上（由以上(2)得到）。得到）。 (3)任意兩行相同的任意兩行相同的1的個數(shù)不超過的個數(shù)不超過 1。（由以上。（由以上(4)得到）得到） (4)任意兩列相同任意兩列相同1的個

27、數(shù)不超過的個數(shù)不超過1 。(由以上由以上(3)得得到到)。 1QH Jn 1QH Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論32 的密度的密度r= = 。若。若 ，則，則 為為一低密度矩陣。一低密度矩陣。 所以所以 的零空間確定是碼長為的零空間確定是碼長為n的的LDPC碼碼,該碼該碼稱為稱為 -型型Q元元-集合集合LDPC碼碼,用用 ,該碼的該碼的 Tanner圖為雙向圖圖為雙向圖,包含包含n個碼字節(jié)點與個碼字節(jié)點與J個校驗節(jié)個校驗節(jié)點。點。 碼字節(jié)點的度為碼字節(jié)點的度為 。 校驗節(jié)點的度為校驗節(jié)點的度為 。 該圖不包括該圖不包括4環(huán)環(huán),但包括但包

28、括6環(huán)。環(huán)。 1QH nJ, n J 1QH 1QH (1)QCmin1dLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論33方法二：方法二： 同樣同樣Q,包含包含n個頂點個頂點P,Q條線條線L。 令令 為為GF(2)上的上的J維矢量。維矢量。 與與Q中的中的J條線一一對應(yīng)，條線一一對應(yīng)， P為為Q中的某個點，定義中的某個點，定義J維矢量維矢量 其中其中 ,Q中的第中的第i條線包含該點條線包含該點P ,否則否則 12JvvvviivLpv12pJvvvv10ivLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論34

29、表示的是相交于表示的是相交于P點的所有線的信息點的所有線的信息,顯然顯然 重重量為量為 . 構(gòu)造構(gòu)造 ,是一個是一個 維的矩陣。維的矩陣。 每行代表每行代表Q中的中的n個點。個點。 每列代表每列代表Q中的中的J條線。條線。 具有以下幾點性質(zhì)：具有以下幾點性質(zhì)： (1)每行行重為每行行重為 。 (2)每列列重為每列列重為 。 (3)任意兩列相同任意兩列相同1的個數(shù)不超過的個數(shù)不超過1 。 (4)任意兩行形同任意兩行形同1的個數(shù)不超過的個數(shù)不超過1 。pvpv(2)QH nJ(2)QH Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論35 與與 有如下的關(guān)系

30、有如下的關(guān)系 且有相同的密度。且有相同的密度。 的零空間確定的是長為的零空間確定的是長為J的的LDPC碼碼, ,用用 標(biāo)記標(biāo)記,稱為稱為 -型型LDPC碼。碼。 與與 稱為同享碼稱為同享碼(companion codes)。 與與 的的Tanner圖互為對偶。圖互為對偶。 即即 的圖中碼字節(jié)點變?yōu)榈膱D中碼字節(jié)點變?yōu)?圖中的校驗節(jié)點。圖中的校驗節(jié)點。 圖中的校驗節(jié)點變?yōu)閳D中的校驗節(jié)點變?yōu)?圖中的碼字節(jié)點。圖中的碼字節(jié)點。 (2)QH 1QH 1(2)TQQHH 2(1)TQQHH (2)QH min1d(2)QC(2)QC(1)QC(1)QC(2)QC(1)QC(1)QC(2)QC(2)QCLe

31、cture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論36LDPC的譯碼方法有的譯碼方法有： majority-logic(MLG) 大數(shù)邏輯譯碼大數(shù)邏輯譯碼 bit-flipping(BF) 比特翻轉(zhuǎn)譯碼比特翻轉(zhuǎn)譯碼 weight BF decoding 重量比特翻轉(zhuǎn)譯碼重量比特翻轉(zhuǎn)譯碼 posterior probability(APP) 后驗概率譯碼后驗概率譯碼 Iterative decoding based on belief propagation(IDBP) 置信傳播的迭代譯碼置信傳播的迭代譯碼 稱為稱為sum-product algorithm(S

32、PA) 和積算法和積算法硬判決硬判決軟判決軟判決介于中間介于中間Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論37譯碼復(fù)雜度譯碼復(fù)雜度性能分析性能分析MLGSimplest一般一般BF比比MLG稍高稍高優(yōu)于優(yōu)于MLGWeighted BF介于兩者之間介于兩者之間 介于兩者之間介于兩者之間APP高復(fù)雜度高復(fù)雜度高性能高性能SPA高復(fù)雜度高復(fù)雜度高性能高性能在在APP與與SPA中中,APP計算機仿真較難實現(xiàn)，計算機仿真較難實現(xiàn)，因此實際中一般用因此實際中一般用SPA算法算法Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼

33、理論38LDPC的碼字的碼字 經(jīng)過經(jīng)過AWGN信道信道,噪聲噪聲 通過通過BPSK映射：映射： c00,2eNn12nvvvv11ev 01ev 01en021nyyyy 為接收端軟判決輸出為接收端軟判決輸出SPA算法：算法：LDPC碼碼 ，碼長為，碼長為n，其，其H為為J行行c12,Jh hh ,0,1,1jjjj nhhhh 1jJ定義定義 ,:1,0jj lB hl hln 第第j行行1的位置的位置Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論39SPA算法是基于邊緣后驗概率的計算算法是基于邊緣后驗概率的計算,即計算即計算lpvy 0ln 后驗概

34、率：后驗概率：0(0)llpp v11llpp v定義定義 ： 與與 相連的校驗和集合相連的校驗和集合lAlv 1,:0,1,0,1Xijj llqlnjJ hA X 1,Xij lq表示第表示第i次迭代譯碼中，已知次迭代譯碼中，已知 矢量的校驗和矢量的校驗和ljAh條件下，條件下， 取值為取值為X的概率值的概率值lvLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論40 1,:1,1,0,1Xijj lllnjJ hA X 1,Xij l表示第表示第i次迭代譯碼中，已知次迭代譯碼中，已知(01)lvX或并且已知并且已知滿足滿足jB h的其它碼字比特的獨立

35、分布：的其它碼字比特的獨立分布： 1,:tVij tjqtBhl 的條件下，校驗和滿足的條件下，校驗和滿足 的概率值。的概率值。0jS 11,:(0|,:() )tjjtV iX ijj ljltj tt B hlV t B hlp SVX V tB hlqLecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論41 1,Xij l用來計算用來計算11,Xij lq 111(1),ttjlXiXiiXj lj llt lhAhqp1,ij l選擇使得選擇使得0,11,1,1iij lj lqq計算得到的計算得到的11,Xij lq用來修正用來修正 ，即得到，即得

36、到11,Xij l 1,Xij lq 1,Xij l與與互相修正互相修正,知道譯碼結(jié)束。知道譯碼結(jié)束。在第在第i步譯碼中步譯碼中,計算后驗概率：計算后驗概率：Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論42 11,|jliiXiXlllj lhApvXyp il選擇使得選擇使得 0|1|1iillpvypvy 計算向量計算向量 011iiiinzzzz 10ilz當(dāng)當(dāng)否則否則 1|0.5ilpvy 然后，計算然后，計算 TizH 如果結(jié)果等于如果結(jié)果等于0，譯碼結(jié)束，輸出為碼字，否則繼續(xù)迭代，譯碼結(jié)束，輸出為碼字，否則繼續(xù)迭代Lecture 10 LDPCLecture 10 LDPC碼碼信道編碼理論信道編碼理論43SPA算法算法初始化初