信道編碼第6章

1、第六章第六章 LDPC 編碼編碼介紹了LDPC 碼的定義、分類Tanner 圖表示；對其編碼和譯碼方法進(jìn)行了簡單的討論一、一、LDPC 碼概述碼概述1、 LDPC碼歷史碼歷史Robert Gallager 1960 年在MIT Ph. D. 論文中提出，當(dāng)時(shí)由于1. 計(jì)算量大2. RS碼的引入3. RS卷積碼被認(rèn)為是最佳搭配 因此該碼被忽視了幾十年 MacKay (1999) 和Richardson/Urbanke(1998) 重新發(fā)現(xiàn)了該碼的優(yōu)點(diǎn)和利用方式.LDPC碼碼是Low-Density Parity-Check Codes（低密度校驗(yàn)碼低密度校驗(yàn)碼） 的簡稱。是一類特殊的線性奇偶檢驗(yàn)

2、分組碼奇偶檢驗(yàn)分組碼，其奇偶校驗(yàn)矩陣是稀疏的：只有很小數(shù)目的非0矩陣元素（對于二進(jìn)制碼來說，非0元素即為元素1），其他元素都為0。一個(gè)矩陣的密度表示矩陣中非0元素所占的比例，一個(gè)矩陣的密度小于0.5時(shí)可以被認(rèn)為是稀疏的。2、LDPC碼的定義碼的定義逼近Shannon限，例如碼長1 million （1000000）的非正則（Irregular） LDPC碼，離香農(nóng)限0.3 dB (Richardson:1999)最接近的記錄離香農(nóng)容量0.0045 dB (Chung:2001)糾碼字差錯(cuò)block error的性能好差錯(cuò)平臺error floor低 最小距離正比于碼長譯碼復(fù)雜度與碼長是線性關(guān)系

3、 適合并行譯碼運(yùn)算3、LDPC 碼性能碼性能信道編碼定理信道編碼定理具體公式見第一章1、為滿足一定誤碼率的要求，可以增加信道容量2、在碼率一定的情況下，增加分組碼的長度（增加分組信號持續(xù)時(shí)間）可使誤碼率隨著分組碼長的增加呈指數(shù)下降。由于碼長的增加，在碼率一定的情況下，可能導(dǎo)致發(fā)送的碼字迅速增加，增加了譯碼的復(fù)雜性。但指出了減少誤碼的另一個(gè)方向。LDPC 就是基于上面第二條，以增加算法的復(fù)雜度為代價(jià)，獲得更好的性能。這是復(fù)雜性和通信可靠性兩者之間的一個(gè)權(quán)衡，即在保證可靠性的基礎(chǔ)上適當(dāng)增加復(fù)雜性。與Turbo相比，LDPC的簡化譯碼算法和并行解碼并不會讓系統(tǒng)過于復(fù)雜；同時(shí)，單純就時(shí)延來看，LDPC

4、雖然迭代解碼時(shí)延略大，但是本身分集特性分集特性減少了交織交織的過程，整體和Turbo相當(dāng)。根據(jù)校驗(yàn)矩陣中各行各列的“1”的個(gè)數(shù)是否相等分為規(guī)則（Regular）碼和不規(guī)則（Irregular）碼。根據(jù)LDPC碼的值域劃分為二進(jìn)制LDPC碼和多進(jìn)制LDPC碼。這樣LDPC碼分為規(guī)則二進(jìn)制LDPC碼、不規(guī)則二進(jìn)制LDPC碼、規(guī)則多進(jìn)制LDPC碼、不規(guī)則多進(jìn)制LDPC碼四種。通常情況多進(jìn)制碼的性能優(yōu)于二進(jìn)制碼；同一域的LDPC碼，不規(guī)則碼性能優(yōu)于規(guī)則碼。但復(fù)雜度正好相反，規(guī)則二進(jìn)制碼最簡單，多進(jìn)制不規(guī)則碼最為復(fù)雜。實(shí)際應(yīng)用時(shí)根據(jù)需要，在系統(tǒng)性能和實(shí)現(xiàn)復(fù)雜度兩者之間權(quán)衡。4、LDPC碼的分類碼的分類二

5、進(jìn)制規(guī)則（Regular）碼的奇偶校驗(yàn)矩陣有如下特征：每列包括j個(gè)元素，每行包括k元素，其中j、k都是較小的正整數(shù)（j 1 0 如如L 1 算法所用符號定義算法所用符號定義qij 從比特節(jié)點(diǎn)ci 傳遞到校驗(yàn)節(jié)點(diǎn)fj的消息 rji 從校驗(yàn)節(jié)點(diǎn)fj傳遞到比特節(jié)點(diǎn)ci 的消息 Rj = i:hji=1 - H矩陣第j行中,值為1的元素所在的列號的集合 Rji =i:hji=1i -集合Rj中扣除了列號i后剩余的集合Ci = j:hji=1 - H矩陣第i列中,值為1的元素所在的行號的集合Cij = j:hji=1j -集合Ci中扣除了行號j后剩余的集合pi = Pr(ci=1| ri) 收碼ri條件

6、下,發(fā)碼ci=1的概率比如H 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1R2=0,3,6, R23=0, 6C4=1,3, C43 =1 f0 f0 f2 c0 c1 c2 c0位翻轉(zhuǎn)譯碼位翻轉(zhuǎn)譯碼1 1 0 1 0 1 0 11 1 0 01除去本身路徑的校驗(yàn)和采用三中取二的原則做判決Soft-decision decodingThe above description of hard-decision decoding was mainly for educational purpose to get an

7、 overview about the idea. Soft-decision decoding of LDPC codes, which is based on the concept of belief propagation, yields in a better decoding performance and is therefore belief the prefered method. The underlying idea is exactly the same as in propagation hard decision decoding. Before resenting

8、 the algorithm lets introduce some notations: Pi = Pr(ci = 1|yi) qij is a message sent by the variable node ci to the check node fj. Every message contains always the pair qij(0) and qij(1)which stands for the amount of belief that yi is a ”0” or a ”1”. rji is a message sent by the check node fj to

9、the variable node ci. Again there is a rji(0) and rji(1) that indicates the (current) amount of believe in that yi is a ”0” or a ”1”.The step numbers in the following description correspond to the hard decision case.1. All variable nodes send their qij messages. Since no other information is avaiabl

10、e at this step, qij(1) = Pi and qij(0) =1 Pi.2 . The check nodes calculate their response messages rji:So they calculate the probability that there is an even number of 1s amoung the variable nodes except ci (this is exactly what Vji means). This propability is equal to the probability rji(0) that c

11、i is a 0.3. The variable nodes update their response messages to the check nodes. This is done according to the following equations,whereby the Konstants Kij are chosen in a way to ensure that qij(0)+qij(1) = 1. Cij now means all check nodes except fj.At this point the v-nodes also update their current estimation ci of their variable ci. This is done by calculating the propabilities for 0 and 1 and voting for the bigger one. The used equations are quite similar to the ones to compute qij(b) but now the information from every c