【文章內(nèi)容簡介】 的稀疏性，它具有Tanner圖這樣的數(shù)學(xué)模型，因此理論分析相對簡單。20世紀(jì)90年代，人們利用定義在Tanner圖對LDPC碼的譯碼性能進(jìn)行分析，目前己經(jīng)有了一些較為完善的理論，人們還發(fā)現(xiàn)基于稀疏圖的LDPC碼具有非常接近Shannon限的性能。這一章首先介紹線性分組碼的原理，然后簡介LDPC碼的圖論基礎(chǔ)知識，最后給出LDPC碼的分類。線性分組碼在糾錯(cuò)碼中有很重要的地位，它的數(shù)學(xué)模型簡單，較易對其進(jìn)行性能分析。而LDPC碼本質(zhì)上就是一種線性分組碼，它通過一個(gè)生成矩陣G將信息序列映射成碼字序列。每一個(gè)生成矩陣G，都存在一個(gè)奇偶校驗(yàn)矩陣H，所有的碼字序列C構(gòu)成了H的零空間。線性分組碼的信息位和監(jiān)督位之間的關(guān)系滿足一組線形代數(shù)方程。一個(gè)(N，K)線性分組碼的編碼就是根據(jù)己知的K個(gè)信息比特求出NK個(gè)校驗(yàn)比特，因此必須有NK個(gè)線形獨(dú)立的方程。如果線性分組碼的前K位就是原來的信息比特，后NK位是監(jiān)督位，則稱之為線形系統(tǒng)碼。設(shè)二進(jìn)制線性分組碼(N，K)的校驗(yàn)矩陣為，碼字為z，則H的每一行與它的碼字的內(nèi)積均為零，即式(21)成立。 （21）線性分組碼的最小距離就是碼的最小重量(除全“0”碼字外)。線性分組碼有兩個(gè)重要的參數(shù)，一個(gè)是最小碼距，它反映了碼的檢糾錯(cuò)能力，值越大檢糾錯(cuò)能力越強(qiáng)。另一個(gè)是碼率R=K/N ，它表示信息位在碼組中所占的比重，體現(xiàn)了編碼效率。 LDPC碼的圖結(jié)構(gòu)在圖論中一個(gè)圖是由頂點(diǎn)和邊組成的，其中的樹(tree)和二分圖(bipartite graph)都可被用來描述和分析LDPC碼。二分圖中所有的頂點(diǎn)分為兩個(gè)子集，任何一個(gè)子集內(nèi)部各個(gè)頂點(diǎn)之間沒有邊相連，任意一個(gè)頂點(diǎn)都和一個(gè)不在同一個(gè)子集里的頂點(diǎn)相連。 樹Gallager 用校驗(yàn)樹來表示H矩陣[2]，用以說明消息在置信傳播譯碼中傳播的過程。在這之后，表示LDPC矩陣的樹圖有了改進(jìn)，如圖21所示。一條斜線和與其上端相連的一條橫線代表一個(gè)校驗(yàn)方程，線上的節(jié)點(diǎn)即為構(gòu)成此校驗(yàn)方程的節(jié)點(diǎn)：圖21中，黑點(diǎn)代表校驗(yàn)節(jié)點(diǎn)，白點(diǎn)代表變量節(jié)點(diǎn)。圖中有兩層結(jié)構(gòu)，由上至下，第一層表示為校驗(yàn)方程c，第二層表示參與c的信息節(jié)點(diǎn)v，第三層表示v參與的其余校驗(yàn)方程，第四層代表參與上一層校驗(yàn)方程的其它信息節(jié)點(diǎn)。如果繼續(xù)衍生下去，將會出現(xiàn)相同節(jié)點(diǎn)。圖21變量節(jié)點(diǎn)v的校驗(yàn)樹 Tanner圖1981年Tanner建立了編碼的圖模型概念，并證明了和積算法在無環(huán)圖中譯碼的最佳性，后來人們將應(yīng)用于編碼領(lǐng)域的二分圖稱為Tanner 圖。LDPC碼可以用一個(gè)Tanner圖來表征，Tanner圖和校驗(yàn)矩陣一一對應(yīng)。圖中包含三種元素，變量節(jié)點(diǎn)(Variable node) 、校驗(yàn)節(jié)點(diǎn)(Check node)和連接它們的邊，其中變量節(jié)點(diǎn)內(nèi)部和校驗(yàn)節(jié)點(diǎn)內(nèi)部沒有任何邊連接，只有在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間才有邊相連接，任意一對變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)最多只有一條邊相連。Tanner圖中的每一條連線對應(yīng)于校驗(yàn)矩陣中的‘1’。而且對于一個(gè)碼長為N，碼率R=K/N的線性碼，它的校驗(yàn)數(shù)目是M=NK。任意一個(gè)線性碼都可以用一個(gè)Tanner圖來表示，而LDPC的Tanner圖是稀疏的，每一個(gè)變量節(jié)點(diǎn)只和少數(shù)幾個(gè)校驗(yàn)節(jié)點(diǎn)相連，每一個(gè)校驗(yàn)節(jié)點(diǎn)也只和少數(shù)幾個(gè)變量節(jié)點(diǎn)相連。使得圖中邊的數(shù)目幾乎正比于碼長N，而不是N的二次方。下面以一個(gè)(6，3) 線性分組碼說明二分圖。以(6，3)線性分組碼的校驗(yàn)矩陣和其二分圖，圖中上面的節(jié)點(diǎn)是變量節(jié)點(diǎn)，下面的節(jié)點(diǎn)是校驗(yàn)節(jié)點(diǎn)。校驗(yàn)矩陣: (22)相應(yīng)的二分圖:圖 22 (6，3)線性分組碼的校驗(yàn)方程和對應(yīng)的二分圖圖22的第一行節(jié)點(diǎn)表示發(fā)送的比特(稱為變量節(jié)點(diǎn))，第二行是它們滿足的校驗(yàn)(稱為校驗(yàn)節(jié)點(diǎn))。圖中變量節(jié)點(diǎn)集合V=()和校驗(yàn)節(jié)點(diǎn)集C=()內(nèi)部不存在相連的邊，但兩類節(jié)點(diǎn)之間存在著連線。變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間存在連線意味著該變量比特參加了此校驗(yàn)式，也就是校驗(yàn)矩陣某一行中‘1’的位置。每個(gè)節(jié)點(diǎn)上的連線數(shù)目稱為該節(jié)點(diǎn)的次數(shù)(degree)，圖22，變量節(jié)點(diǎn)的次數(shù)都是=2，校驗(yàn)節(jié)點(diǎn)的次數(shù)都是=3?？梢园裈anner圖拆成一個(gè)一個(gè)的子碼(subcode) ，例如圖2－3所示：圖23(6，3)線性分組碼的一個(gè)子碼LDPC碼是線性分組碼的一種，它的最小漢明距離決定了性能優(yōu)劣，然而一般情況下，LDPC碼的碼長較長，無法直接求出一個(gè)碼的最小距離。而Tanner圖中的“環(huán)”在一定程度上反映了譯碼性能。Tanner圖中由變量節(jié)點(diǎn)、校驗(yàn)節(jié)點(diǎn)和邊首尾相連組成的閉合環(huán)路稱為“環(huán)”。環(huán)的長度就是其中邊的數(shù)目。從LDPC碼的Tanner圖中可以看出，每個(gè)節(jié)點(diǎn)都會存在許多這樣的閉合環(huán)路，且每個(gè)環(huán)的周長一定是2的整數(shù)倍。在圖22變量節(jié)點(diǎn)就參與了一個(gè)長度為6的環(huán)，如圖中粗線所示，由起，經(jīng)過，最后返回。環(huán)在LDFC碼的迭代解碼過程中會造成不良影響，形成無效信息的正反饋，使迭代解碼無法達(dá)到最佳性能，環(huán)是如何影響譯碼性能將在譯碼章節(jié)中詳細(xì)說明。理論和實(shí)踐均己證明，Tanner圖中的環(huán)，特別是短環(huán)對迭代解碼的性能影響很大。Tanner圖中最短環(huán)的周長稱為最小圈長girth，例如圖22girth是6。girth的越大，最小距離的下界越大，碼的糾錯(cuò)能力越強(qiáng)，Tanner給出了最小距離的下界和girth的關(guān)系式： （23）其中，D為LDPC碼的最小碼距，g為LDPC碼的girth，y為變量節(jié)點(diǎn)的次數(shù)，d為二分圖中子碼(subcode) 的最小碼距。如果二分圖的girth等于4，將會影響LDPC碼的誤碼率性能，所以在構(gòu)造LDPC碼的校驗(yàn)矩陣時(shí)，要盡量避免二分圖中出現(xiàn)girth為4的情況。 LDPC碼的分類LDPC碼有多種分類方法，例如按行重、列重是否是定值劃分，可以分為規(guī)則碼和非規(guī)則碼；按所在的域劃分，分為二元域和多元域的碼。下面將分別介紹這兩種分類。 規(guī)則碼和非規(guī)則碼1. 規(guī)則(regular)LDPC碼如果LDPC碼的校驗(yàn)矩陣行列重量固定為，即每個(gè)校驗(yàn)方程有比特參與校驗(yàn)，每個(gè)變量參與個(gè)校驗(yàn)方程，我們稱之為規(guī)則LDPC碼。這也是Gallager最初提出的Gallager碼的特點(diǎn)。我們用Gallager對LDPC碼的表示方法：將碼長為N，行重、列重分別為和的LDPC碼稱為(N，)LDPC碼。從Tanner圖的角度來看，這種LDPC碼的變量節(jié)點(diǎn)次數(shù)全部為，而校驗(yàn)節(jié)點(diǎn)的次數(shù)都為。上例就是一個(gè)規(guī)則的(6，2，3)LDPC碼，相應(yīng)的圖22，第一行每個(gè)變量節(jié)點(diǎn)與3條線相連，第二行校驗(yàn)節(jié)點(diǎn)與2條線相連。可以適當(dāng)放寬上述規(guī)則LDPC碼的條件，行或列的重量可以不是固定的整數(shù)，但行列重量盡量服從均勻分布。另外為了保證LDPC碼的Tanner圖上不存在長度為4的圈，通常要求行與行以及列與列之間的交疊部分重量不超過1。當(dāng)校驗(yàn)矩陣H滿秩時(shí)，規(guī)則碼的碼率R=(NM)/N=K/M=1，當(dāng)校驗(yàn)矩陣H不滿秩時(shí)，R=(N一rank(H)/N=K/M。Mackay在文獻(xiàn)[13]中證明了在任意信道中，1)規(guī)則LDPC碼滿足了好碼(Good codes)定理的要求，即在固定列重，碼長N足夠長的情況下，存在一個(gè)0到信道傳輸容量之間的值r，在此速率下可以實(shí)現(xiàn)無差錯(cuò)傳輸。2)規(guī)則LDPC碼滿足了更好碼(very Good Codes)定理的要求，即如果不固定列重，當(dāng)/M很小時(shí)，此LDPC碼可以很接近信道容量。 2. 非規(guī)則(irregular)LDPC碼在Tanner圖中，信息節(jié)點(diǎn)希望能參與盡可能多的校驗(yàn)方程，以便更準(zhǔn)確的判斷自己。而校驗(yàn)節(jié)點(diǎn)希望向盡可能少的信息節(jié)點(diǎn)傳遞消息，以確保更準(zhǔn)確的判斷信息節(jié)點(diǎn)。非規(guī)則LDPC在此要求下受到人們的重視。Luby[12]分析了非規(guī)則的性能和構(gòu)造好的非規(guī)則碼的方法。非規(guī)則碼的行列重已不再是固定值，即每個(gè)變量節(jié)點(diǎn)參與的校驗(yàn)式數(shù)目或每個(gè)校驗(yàn)式中含有的變量節(jié)點(diǎn)數(shù)目不再保持均勻，而是有意設(shè)置部分突出的變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)。在譯碼過程中，那些參與較多校驗(yàn)式的變量節(jié)點(diǎn)迅速得到正確譯碼信息，然后它們給相鄰的校驗(yàn)節(jié)點(diǎn)更加有效的概率信息，而這些校驗(yàn)節(jié)點(diǎn)又可以給與它們相鄰的次數(shù)少的變量節(jié)點(diǎn)更多的信息。整個(gè)譯碼的過程呈現(xiàn)出一種波狀效應(yīng)，次數(shù)越高的變量節(jié)點(diǎn)首先獲得正確信息，然后是次數(shù)較低的節(jié)點(diǎn)，然后依次往下，直到次數(shù)最低的變量節(jié)點(diǎn)。正是這種波浪效應(yīng)，使得非規(guī)則碼獲得比規(guī)則更好的譯碼性能。 二元域和多元域的碼Matthew ，將其放到了多元域GF(q)上。假設(shè)在域GF(2)和域GF(q)()上構(gòu)造的LDPC碼所對應(yīng)的校驗(yàn)矩陣分別是和中的元素是0或1，而是由元素0，1，q1構(gòu)成，中的每個(gè)元素都是中p個(gè)元素的組合。從矩陣看將相應(yīng)GF(2)域中相應(yīng)的1q向量代入GF(q)域的，得到的二進(jìn)制形式，調(diào)節(jié)檢驗(yàn)矩陣可以增加與之對應(yīng)的二進(jìn)制校驗(yàn)矩陣中列的平均重量，從的Tanner圖看，結(jié)構(gòu)并沒有改變，不會造成節(jié)點(diǎn)之間短圈數(shù)目的增加。對于二進(jìn)制LDPC碼來說，如果它的校驗(yàn)矩陣H的列重量增大，那么它的性能也增加，但是如果增加列重量會使得Tanner圖中各節(jié)點(diǎn)之間的短環(huán)數(shù)目急劇增加，從而使BP算法的性能下降。而在GF(q)域上構(gòu)造的LDPC正好可以解決這個(gè)矛盾。例如在GF(16)上構(gòu)造的規(guī)則碼性能已經(jīng)和Turbo碼相差無幾。第三章 LDPC碼的編碼與譯碼 LDPC碼的構(gòu)造LDPC碼是線性分組碼，可以由校驗(yàn)矩陣H等效描述，所以我們只要構(gòu)造了該碼的校驗(yàn)矩陣就完成了LDPC碼的構(gòu)造。 Gallager的構(gòu)造方法Gallager 1962年最初的工作中，給出了正則碼的構(gòu)造方法：對碼長為N的正則碼，他將校驗(yàn)矩陣按行水平