第6章LDPC碼6.1

LDPC碼的概念

6.2二元LDPC碼的編碼方法

6.3

LDPC碼的譯碼方法和性能習(xí)題 LDPC(Low-DensityParity-Check)碼是低密度校驗(yàn)碼，由Gallager于1962年在其博士學(xué)位論文中提出。由于受當(dāng)時(shí)計(jì)算機(jī)發(fā)展水平的影響，LDPC碼譯碼的復(fù)雜度限制了LDPC碼的優(yōu)秀糾錯(cuò)性能的展示，因而LDPC碼當(dāng)時(shí)并未受到人們的重視，直到1995年，Mackay和Neal公布了LDPC碼具有接近香農(nóng)理論界限的譯碼性能仿真結(jié)果，LDPC碼繼Turbo碼后再次引起編碼界轟動(dòng)，在相距兩年左右的時(shí)間內(nèi)兩種性能接近香農(nóng)理論界限的糾錯(cuò)編碼的出現(xiàn)為編碼領(lǐng)域帶來了一場(chǎng)革命性的變化。Ardakani在其博士論文中指出，當(dāng)碼長較短時(shí)，Turbo碼的性能優(yōu)于LDPC碼，但碼長較長時(shí)(典型值超過5000)，LDPC碼具有比Turbo碼更接近香農(nóng)理論界限的譯碼性能，如圖6.1所示。目前，已設(shè)計(jì)出了離香農(nóng)理論界限僅0.0045dB的LDPC碼。LDPC碼與Turbo碼的性能比較見表6.1。圖6.1

LDPC碼與Turbo碼的性能比較表6.1

LDPC碼與Turbo碼的性能比較

6.1

LDPC碼的概念

1.LDPC碼的定義

定義6.1.1如果一個(gè)矩陣只有很少一部分元素非零，大部分元素都是零，那么稱這個(gè)矩陣為稀疏矩陣(SparsityMatrix)。

一個(gè)矩陣的稀疏程度是通過矩陣中非零元素所占的比例來表示的，常稱為矩陣密度。一般認(rèn)為矩陣密度不超過0.5的矩陣是稀疏的。例如，矩陣

的矩陣密度為0.5，所以矩陣H為稀疏矩陣。(6.1.1)

定義6.1.2一個(gè)線性分組碼的校驗(yàn)矩陣H是稀疏的，那么這個(gè)碼稱為LDPC碼。

LDPC碼的校驗(yàn)矩陣是稀疏的，因而校驗(yàn)矩陣的非零元素相對(duì)于零元素表現(xiàn)為具有低密度特性，這就是低密度校驗(yàn)碼名稱的由來。

例6.1.1求出以式(6.1.1)所示的矩陣H為校驗(yàn)矩陣的系統(tǒng)LDPC碼。

解方法一：

設(shè)這個(gè)LDPC碼的碼字為c=(c1c2c3c4c5c6)，那么，有

HcT=0T

(6.1.2)所以，得到校驗(yàn)方程組

式中，(c1c2c3)為信息碼，(c4c5c6)為校驗(yàn)位。

將信息碼{000，001，010，011，100，101，110，111}代入式(6.1.3)，得到LDPC碼的全部碼字如下：

000000

001011

010111

011100

100101

101110

110010

111001(6.1.3a)(6.1.3b)(6.1.3c)(6.1.3d)方法二：

對(duì)式(6.1.1)所示的矩陣H進(jìn)行初等變換，將第一、第二和第三行加到第四行，得

對(duì)矩陣H′進(jìn)行初等變換，使最后三列構(gòu)成一個(gè)單位矩陣。將H′的第二行加到第三行得到

于是，本例LDPC碼的生成矩陣G為

所以，LDPC的碼字應(yīng)當(dāng)按

［c1c2c3c4c5c6］=［c1c2c3］G

(6.1.5)

來生成。讀者可以驗(yàn)證，式(6.1.5)生成的碼字與方法一生成的碼字一致。

2.LDPC碼的圖形表示

對(duì)一般線性分組碼，校驗(yàn)方程、校驗(yàn)矩陣或生成矩陣都是表示線性分組碼的有力工具。在LDPC碼中，表示LDPC碼的有力工具是Tanner圖。

例6.1.2構(gòu)造例6.1.1的LDPC碼的Tanner圖。

解根據(jù)校驗(yàn)方程(6.1.3a)～(6.1.3d)，例6.1.1的LDPC碼的Tanner圖如圖6.2所示。圖6.2例6.1.1的LDPC碼的Tanner圖在LDPC碼的Tanner圖中，有一個(gè)非常重要的概念叫做環(huán)(Cycle)。

定義6.1.3從Tanner圖的某一個(gè)節(jié)點(diǎn)(校驗(yàn)節(jié)點(diǎn)或比特節(jié)點(diǎn))沿著Tanner圖的邊出發(fā)，經(jīng)過其他節(jié)點(diǎn)至多一次，最后又回到出發(fā)節(jié)點(diǎn)所經(jīng)過的路徑稱為Tanner圖的環(huán)。一個(gè)Tanner圖中所有環(huán)所包含的邊數(shù)最小者稱為這個(gè)Tanner圖的環(huán)的周長(Girth)。

對(duì)于LDPC碼的環(huán)的周長有下述結(jié)論。

定理6.1.1

LDPC碼的環(huán)的周長不會(huì)小于4，且環(huán)的周長是2的倍數(shù)。

證明因?yàn)闃?gòu)成一個(gè)環(huán)顯然最少需要三個(gè)節(jié)點(diǎn)，所以LDPC碼的環(huán)的周長≥3。由Tanner圖構(gòu)造知，無論是在比特節(jié)點(diǎn)之間還是在校驗(yàn)節(jié)點(diǎn)之間都不存在邊，每一邊必然一端接校驗(yàn)節(jié)點(diǎn)，另一端接比特節(jié)點(diǎn)。因此，無論從比特節(jié)點(diǎn)還是校驗(yàn)節(jié)點(diǎn)出發(fā)，經(jīng)過的節(jié)點(diǎn)必然是比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)交替出現(xiàn)，回到起始節(jié)點(diǎn)，所經(jīng)過的比特節(jié)點(diǎn)數(shù)和校驗(yàn)節(jié)點(diǎn)數(shù)相同(起始節(jié)點(diǎn)被計(jì)算兩次)，所以，即經(jīng)過的節(jié)點(diǎn)數(shù)目是偶數(shù)(起始節(jié)點(diǎn)經(jīng)過了兩次)，沿經(jīng)過的節(jié)點(diǎn)順序走過的邊是偶數(shù)條邊。結(jié)合環(huán)的周長不小于3，完成定理證明。周長為4的Tanner圖是存在的。例如，以校驗(yàn)矩陣：

構(gòu)成的LDPC的Tanner圖如圖6.3所示。很明顯，環(huán)1→c1→2→c2→1的長度為4。(6.1.6)圖6.3以式(6.1.6)為校驗(yàn)矩陣產(chǎn)生的Tanner圖環(huán)長對(duì)LDPC的譯碼性能有重要影響，周長為4的環(huán)會(huì)導(dǎo)致迭代譯碼算法不收斂而無法糾正錯(cuò)誤(詳細(xì)討論見6.3節(jié))，因此，要避免使用含有周長為4的環(huán)的LDPC碼。O’sullivan等人通過計(jì)算機(jī)仿真指出，LDPC碼環(huán)的周長越大，譯碼性能越好，圖6.4給出了規(guī)則(3，6)LDPC碼在碼長為1002時(shí)對(duì)環(huán)的周長分別為8、10和12的比特誤碼率曲線。圖6.4環(huán)的周長分別為8、10和12的規(guī)則(3，6)LDPC碼的性能

3.LDPC碼的分類

(1)按比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的次數(shù)，LDPC碼可以分為規(guī)則LDPC碼和非規(guī)則LDPC碼兩類。

定義6.1.4一個(gè)LDPC碼的Tanner圖中，每一個(gè)校驗(yàn)節(jié)點(diǎn)有相同的次數(shù)wc，每個(gè)比特節(jié)點(diǎn)有相同的次數(shù)wb，那么這個(gè)LDPC碼稱為規(guī)則LDPC碼，記為規(guī)則(wb，wc)LDPC碼；否則，稱為非規(guī)則LDPC碼，記為非規(guī)則(N，K)LDPC碼，這里N表示LDPC碼的碼長，K表示校驗(yàn)矩陣的行數(shù)或校驗(yàn)方程的個(gè)數(shù)。

實(shí)質(zhì)上，對(duì)于規(guī)則(wb，wc)LDPC碼，其校驗(yàn)矩陣的每一行有wc個(gè)1，每一列有wb個(gè)1。對(duì)于碼長為N，校驗(yàn)方程的方程個(gè)數(shù)為K的規(guī)則LDPC碼，一定有下述關(guān)系：

wcK=wbN

(6.1.7)

很明顯，圖6.2和圖6.3都是規(guī)則(2，3)LDPC碼。非規(guī)則LDPC碼是存在的，例如以校驗(yàn)矩陣：

產(chǎn)生的LDPC碼是非規(guī)則的，其Tanner圖如圖6.5所示。(6.1.8)圖6.5以式(6.1.8)為校驗(yàn)矩陣產(chǎn)生的非規(guī)則LDPC碼圖6.6是Richardson等人給出的規(guī)則(3，6)LDPC碼和優(yōu)化的非規(guī)則LDPC碼的譯碼性能比較，LDPC碼的碼長選取為106，圖6.6表明非規(guī)則LDPC碼具有更好的譯碼性能。圖6.6

(3，6)規(guī)則LDPC碼與非規(guī)則LDPC碼性能比較

(2)按碼元取值，LDPC碼可以分為二元LDPC碼和q元LDPC碼，這里q為一個(gè)素?cái)?shù)的冪。

例6.1.3在有限域GF(28)中，有以下列矩陣為校驗(yàn)矩陣的256元LDPC碼，其中，a是GF(28)中的本原元。求環(huán)的周長。(6.1.9)

解多元LDPC碼的Tanner圖與二元LDPC碼的Tanner圖的構(gòu)造方法基本相同，不同之處在于多元LDPC碼的Tanner圖需要在邊上表明碼元。本例256元LDPC碼的Tanner圖如圖6.7所示。圖6.7以式(6.1.9)為校驗(yàn)矩陣產(chǎn)生的Tanner圖不難發(fā)現(xiàn)，本例LDPC碼的環(huán)周長為4。

Bamult等人對(duì)多元LDPC碼的譯碼性能進(jìn)行了仿真研究，給出了2元、4元、16元、64元和256元的LDPC碼的性能，如圖6.8所示。圖6.8不同q元LDPC碼的譯碼性能

6.2二元LDPC碼的編碼方法

根據(jù)6.1節(jié)的討論，LDPC碼實(shí)質(zhì)上是一類特殊的線性分組碼，它的校驗(yàn)矩陣是稀疏的。如果假設(shè)LDPC碼的碼長為N，信息位為k，即校驗(yàn)位為N－k，那么LDPC碼的校驗(yàn)矩陣是一個(gè)(N－k)×N的矩陣，且LDPC碼的碼率為k/N。用校驗(yàn)矩陣來構(gòu)造LDPC碼是構(gòu)造LDPC碼的重要途徑。一般來說，構(gòu)造規(guī)則二元LDPC碼的校驗(yàn)矩陣應(yīng)當(dāng)遵守下列規(guī)則：

(1)校驗(yàn)矩陣每一列有相同的重量a；

(2)校驗(yàn)矩陣每一行有相同的重量b；

(3)校驗(yàn)矩陣的任意兩行(或兩列)同一位置上為“1”的數(shù)量不超過1；

(4)校驗(yàn)矩陣是稀疏的。滿足規(guī)則(3)是重要的，這能有效地避免在LDPC碼中出現(xiàn)周長為4的環(huán)，因?yàn)楫a(chǎn)生周長為4的環(huán)的校驗(yàn)矩陣必有兩行和兩列在同一位置出現(xiàn)1的數(shù)量至少為2，例如圖6.9中的校驗(yàn)矩陣必定產(chǎn)生周長為4的環(huán)。圖6.9產(chǎn)生周長為4的環(huán)的校驗(yàn)矩陣及對(duì)應(yīng)的Tanner圖(a)校驗(yàn)矩陣；(b)Tanner圖

1.隨機(jī)構(gòu)造法

1)Gallager的隨機(jī)構(gòu)造法

Gallager在博士論文中給出了一種構(gòu)造規(guī)則(wb，wc)LDPC碼的方法，其思路是將LDPC碼的校驗(yàn)矩陣H分成wb個(gè)子矩陣，即

通過一定方法構(gòu)造子矩陣H1，其余子矩陣H2，…，通過隨機(jī)置換H1的列來得到。(6.2.1)

例6.2.1用Gallager的隨機(jī)構(gòu)造法產(chǎn)生碼長N=20的規(guī)則(3，4)LDPC碼。

解首先，求出子矩陣H1。H1共有5行，每行4個(gè)“1”，每列1個(gè)“1”，構(gòu)造的H1如下：

其次，對(duì)H1的列隨機(jī)置換產(chǎn)生子矩陣H2和H3，形成校驗(yàn)矩陣H。Gallager給出的一次實(shí)現(xiàn)校驗(yàn)矩陣如下：

2)Mackay的隨機(jī)構(gòu)造法

Mackay的隨機(jī)構(gòu)造法能生成一種不規(guī)則或規(guī)則LDPC碼。給定正整數(shù)N、r和wb，按以下步驟構(gòu)造LDPC碼：

第一步，隨機(jī)產(chǎn)生一個(gè)階為r×N的矩陣A，每一列有wb個(gè)“1”。

第二步，調(diào)整1的位置使矩陣A的每一行中“1”的個(gè)數(shù)盡可能相等。

第三步，調(diào)整1的位置使矩陣A中任意兩列同一位置上“1”的數(shù)量不超過1，以消除周長為4的環(huán)。

第四步，調(diào)整矩陣A使其環(huán)的周長盡可能大。第五步，如果矩陣A各行線性無關(guān)，對(duì)A進(jìn)行高斯消元以產(chǎn)生系統(tǒng)LDPC碼，即將矩陣A變?yōu)橄到y(tǒng)碼形式的校驗(yàn)矩陣：

H=［Q|I］ (6.2.2)

如果矩陣A的各行線性相關(guān)，那么對(duì)矩陣A實(shí)施列變換，即

A=［B1|B2］ (6.2.3)

式中：B1是一個(gè)階為r×(N－r)的稀疏矩陣；B2是一個(gè)階為r×r的可逆稀疏矩陣。LDPC碼的生成矩陣G定義為

(6.2.4)

3)三角形校驗(yàn)矩陣構(gòu)造法

下三角校驗(yàn)矩陣構(gòu)造法由Richardson和Urbanke共同提出，其特點(diǎn)是利用下三角形矩陣很容易給出LDPC碼的校驗(yàn)位。下三角校驗(yàn)矩陣構(gòu)造法產(chǎn)生LDPC碼有兩種方式。

(1)下三角校驗(yàn)矩陣法。隨機(jī)產(chǎn)生一個(gè)稀疏下三角形校驗(yàn)矩陣H或由一個(gè)隨機(jī)產(chǎn)生的稀疏校驗(yàn)矩陣經(jīng)過高斯消元法變化成一個(gè)下三角矩陣H，下三角線上元素全部為1。設(shè)H的階為r×N，并且是行滿秩的，如圖6.10所示。圖6.10下三角校驗(yàn)矩陣示意圖設(shè)信息碼為m=(m1，m2，…，mN－r)，校驗(yàn)位為p=(p1，p2，…，pr)，即LDPC碼的碼字c=(m，p)，那么校驗(yàn)位可以按如下公式來遞推得到。

由HcT=0T，得

式中：i=1，2，…，r；hi，j表示H中第i行第j列的元素。

(2)近似下三角校驗(yàn)矩陣法。近似下三角校驗(yàn)矩陣法與下三角校驗(yàn)矩陣法的編碼思路基本相同，只不過前者使用的是如圖6.11所示的稀疏近似下三角形校驗(yàn)矩陣。(6.2.5)圖6.11近似下三角校驗(yàn)矩陣示意圖將近似下三角校驗(yàn)矩陣H分成六塊：

式中，六個(gè)子塊矩陣A、B、C、D、E、V的階分別為(r－s)×(N－r)、(r－s)×s、s×(N－r)、s×s、s×(r－s)和(r－s)×(r－s)，子矩陣V是一個(gè)下三角矩陣，下三角線元素全部為1。

設(shè)LDPC碼的碼字c=(m，p1，p2)，m是信息碼，長度為N－r；p1與p2為校驗(yàn)位，長度分別為s和r－s。將校驗(yàn)矩陣H

左乘矩陣 ，得到(6.2.6)

將式(6.2.7)右乘碼字cT并注意到HcT=0T，得

設(shè)矩陣－EV－1B+D可逆，那么校驗(yàn)位p1為(6.2.7)(6.2.8)(6.2.9)校驗(yàn)位p2為

直接計(jì)算式(6.2.9)和式(6.2.10)是不可取的，其計(jì)算量很大，但注意到各分塊矩陣的特點(diǎn)，能夠有效地降低計(jì)算量。計(jì)算式(6.2.9)和式(6.2.10)的流程列于表6.2和表6.3中。表6.2中第3步不直接求V－1(AmT)，而是由

和 來求向量，因?yàn)閂是下三角矩陣，可以利用類似于式(6.2.5)的遞推式來求。(6.2.10)表6.2式(6.2.9)的計(jì)算流程

即有遞推關(guān)系：

式中：l=1，2，…，r－s；vi，j為矩陣V中第l行第j列的元素。

最后有

。表6.3第3步類似處理。(6.2.11)(6.2.12)表6.3式(6.2.10)的計(jì)算流程

例6.2.2設(shè)規(guī)則(3，6)LDPC碼的校驗(yàn)矩陣H為

信息碼m=(1，0，0，0，0，0)，求編碼后的碼字c。

解將校驗(yàn)矩陣H進(jìn)行分塊，有

按照表6.2的計(jì)算順序，得到

于是，校驗(yàn)位為

按照表6.3的計(jì)算順序，得

于是，校驗(yàn)位為

最后，信息碼m的編碼結(jié)果是

c=(m，p1，p2)=(1，0，0，0，0，0，0，1，1，0，1，0)

2.半隨機(jī)構(gòu)造法

1)Ping構(gòu)造法

一個(gè)碼長為N，信息位為k的LDPC碼的碼字c被分塊成c=(p，m)，p=(p1，p2，…，pN－k)，m=(m1，m2，…，mk)，再將LDPC碼的校驗(yàn)矩陣H分塊成

H=［Hp

Hm］

(6.2.13)

式中，Hp為雙對(duì)角線形的下三角矩陣，即(6.2.14)

Hm按下述方法來構(gòu)造。如果存在整數(shù)t同時(shí)滿足t|N－k和kt|N－k，將矩陣Hm分塊成

對(duì)每一子塊矩陣Hmi(i=1，2，…，t)，可以通過在每一列隨機(jī)選取1個(gè)“1”元素，在每一行隨機(jī)選取kt/(N－k)個(gè)“1”元素來構(gòu)成。否則，可以隨機(jī)選取一個(gè)稀疏矩陣Hmi。(6.2.15)于是，由HcT=0T，即

得到(6.2.16)(6.2.17)校驗(yàn)位p的遞推關(guān)系式為

式中，p0=0。

Ping等人對(duì)Ping構(gòu)造法進(jìn)行了仿真，選取信息位k=3000,.碼率分別取1/3、1/2和2/3(相當(dāng)于碼長分別為9000、6000和4500)，取t=4，仿真結(jié)果見圖6.12。(6.2.18)圖6.12碼率分別取1/3、1/2和2/3的Ping構(gòu)造法產(chǎn)生的LDPC碼性能

2)π旋轉(zhuǎn)構(gòu)造法

π旋轉(zhuǎn)構(gòu)造法由Echard提出，其基本思想是通過稱之為π旋轉(zhuǎn)的技術(shù)來構(gòu)造Ping構(gòu)造法中的矩陣Hm，因此，π旋轉(zhuǎn)構(gòu)造法是Ping構(gòu)造法的一種改進(jìn)方法。

設(shè)LDPC碼的校驗(yàn)矩陣H仍表示為式(6.2.13)，其中子矩陣Hm的階為rs×rt，Hm每行有s個(gè)“1”，每列有t個(gè)“1”，Hm由s×t個(gè)隨機(jī)置換矩陣構(gòu)成，每個(gè)矩陣的階為r×r。由階為r×r的單位矩陣經(jīng)過隨機(jī)置換列來得到一個(gè)π旋轉(zhuǎn)矩陣πA，將πA按一定規(guī)則旋轉(zhuǎn)，如按逆時(shí)針旋轉(zhuǎn)90°等，得到另一個(gè)π旋轉(zhuǎn)矩陣πB，如此繼續(xù)下去，得到πC，πD，…。最后將πA，πB，πC，πD，…，共s×t個(gè)隨機(jī)置換矩陣按一定規(guī)則組合起來構(gòu)成Hm。用π旋轉(zhuǎn)構(gòu)造法產(chǎn)生的LDPC碼的信息碼長為rt，碼長為(s+t)r，碼率為t/(s+t)。

例6.2.3取r=3，t=s=4，用π旋轉(zhuǎn)構(gòu)造法產(chǎn)生碼率為1/2的LDPC碼的校驗(yàn)矩陣H。

解取3×3的單位矩陣：

經(jīng)過隨機(jī)置換列產(chǎn)生π旋轉(zhuǎn)矩陣πA為將πA按逆時(shí)針分別旋轉(zhuǎn)90°、180°和270°，得到

于是，Hm為將Hm代入式(6.2.13)，得到LDPC碼的校驗(yàn)矩陣H為

Echard對(duì)π旋轉(zhuǎn)構(gòu)造法產(chǎn)生的LDPC碼的性能進(jìn)行了仿真，給出了碼率為1/2時(shí)，碼長分別為2000、4000、8000、16000和100000的LDPC碼性能，見圖6.13。圖6.13碼率為1/2的π旋轉(zhuǎn)LDPC碼性能

6.3

LDPC碼的譯碼方法和性能

6.3.1

BF譯碼算法

比特翻轉(zhuǎn)(Bit-Flipping，BF)譯碼算法是LDPC碼譯碼算法中復(fù)雜度最小的一種，其基本思想是比特節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳送信息(0或1)，校驗(yàn)節(jié)點(diǎn)檢驗(yàn)信息是否滿足校驗(yàn)方程，并把檢驗(yàn)結(jié)論回傳比特節(jié)點(diǎn)。對(duì)滿足校驗(yàn)方程占多數(shù)的比特節(jié)點(diǎn)，所持有的比特信息不變；對(duì)不滿足校驗(yàn)方程占多數(shù)的比特節(jié)點(diǎn)，把持有的比特信息翻轉(zhuǎn)(即0變1，1變0)，再向校驗(yàn)節(jié)點(diǎn)傳送信息，請(qǐng)求校驗(yàn)。如果所有的校驗(yàn)節(jié)點(diǎn)都宣布校驗(yàn)方程滿足，則譯碼結(jié)束，比特節(jié)點(diǎn)上持有的全部比特信息就是譯出的碼字；否則繼續(xù)按前面的規(guī)則翻轉(zhuǎn)比特節(jié)點(diǎn)上持有的信息，再請(qǐng)求校驗(yàn)，直到全部校驗(yàn)節(jié)點(diǎn)滿足或達(dá)到迭代次數(shù)最大值(宣布譯碼失敗)而終止。

BF譯碼算法的整個(gè)譯碼過程采用了硬判決思想，比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的傳送信息僅有0或1，因而譯碼復(fù)雜度較低，但這樣的硬判決也降低了譯碼算法的性能，導(dǎo)致BF譯碼算法的性能不如和-積譯碼算法好。

一個(gè)矢量使BF譯碼算法中的全部校驗(yàn)方程滿足也就意味著這個(gè)矢量的伴隨式為0，所以，可以說BF譯碼算法與我們?cè)诘?章所學(xué)的伴隨式譯碼法沒有實(shí)質(zhì)性的區(qū)別，兩者都將伴隨式全為0的矢量作為譯出的碼字，所不同的是尋找這樣的矢量的方法不同。伴隨式譯碼法主要通過尋找錯(cuò)誤圖樣而獲得使全部伴隨式為0的矢量，BF譯碼算法則通過迭代、比特翻轉(zhuǎn)的方法來獲得使全部伴隨式為0的矢量。

總結(jié)起來，我們可以得到BF譯碼算法的譯碼流程，如圖6.14所示。圖6.14

BF譯碼算法的譯碼流程

例6.3.1設(shè)有碼率為1/2的LDPC碼的校驗(yàn)矩陣為

發(fā)送碼字(001011)，但發(fā)生一比特錯(cuò)誤，接收矢量y=(101011)。請(qǐng)使用BF譯碼算法譯碼。

解畫出LDPC碼的Tanner圖，并將接收矢量分配給每一個(gè)比特節(jié)點(diǎn)，如圖6.15所示。圖6.15接收矢量(101011)分配給比特節(jié)點(diǎn)

LDPC碼的校驗(yàn)方程為

H［c1c2c3c4c5c6］T=0T

即

將(c1c2c3c4c5c6)=(101011)代入校驗(yàn)方程z1～z4，不難驗(yàn)證z2和z4滿足，z1和z3不滿足，如圖6.16所示。圖6.16校驗(yàn)節(jié)點(diǎn)檢驗(yàn)接收矢量(101011)的結(jié)果將校驗(yàn)節(jié)點(diǎn)檢驗(yàn)結(jié)論回送比特節(jié)點(diǎn)，比特節(jié)點(diǎn)c1收到2個(gè)校驗(yàn)方程不滿足，0個(gè)校驗(yàn)方程滿足；c2，c4，c5和c6收到1個(gè)校驗(yàn)方程滿足，1個(gè)校驗(yàn)方程不滿足；c3收到全部校驗(yàn)方程滿足。于是比特節(jié)點(diǎn)c1的比特信息翻轉(zhuǎn)，變1為0，其余比特節(jié)點(diǎn)的信息不變，如圖6.17所示。圖6.17多數(shù)校驗(yàn)方程不滿足的比特節(jié)點(diǎn)信息翻轉(zhuǎn)將新的矢量(001011)代入校驗(yàn)方程z1～z4，如圖6.18所示。不難驗(yàn)證所有校驗(yàn)方程全部滿足，于是譯碼器將比特節(jié)點(diǎn)上的信息(001011)作為譯出的碼字。很明顯，這是一次成功的譯碼。圖6.18校驗(yàn)節(jié)點(diǎn)檢驗(yàn)矢量(001011)的結(jié)果

例6.3.2一個(gè)LDPC碼的校驗(yàn)矩陣為

發(fā)送碼字(001001)，但發(fā)生一比特錯(cuò)誤，接收矢量y=(101001)。試用BF譯碼算法譯碼。

解畫出LDPC碼的Tanner圖，并將接收矢量分配給每一個(gè)比特節(jié)點(diǎn)，如圖6.19所示。圖6.19接收矢量(101001)分配給比特節(jié)點(diǎn)

LDPC碼的校驗(yàn)方程為

H［c1c2c3c4c5c6］T=0T

即

將接收矢量(c1c2c3c4c5c6)=(101001)代入校驗(yàn)方程z1～z4，不難檢驗(yàn)z1和z2不滿足，z3和z4滿足，如圖6.20所示。圖6.20校驗(yàn)節(jié)點(diǎn)檢驗(yàn)接收矢量(101001)的結(jié)果將校驗(yàn)節(jié)點(diǎn)檢驗(yàn)結(jié)論回送比特節(jié)點(diǎn)，比特節(jié)點(diǎn)c1和c2都收到2個(gè)校驗(yàn)方程不滿足，0個(gè)校驗(yàn)方程滿足；c3和c6收到全部相關(guān)校驗(yàn)方程滿足，c4和c5收到滿足與不滿足的校驗(yàn)方程各1個(gè)。因此，比特節(jié)點(diǎn)c1和c2將持有的比特信息翻轉(zhuǎn)，0變1，1變0，其余比特節(jié)點(diǎn)的信息不變，如圖6.21所示。圖6.21多數(shù)校驗(yàn)方程不滿足的比特節(jié)點(diǎn)信息翻轉(zhuǎn)將新的矢量(011001)代入校驗(yàn)方程z1～z4，不難檢驗(yàn)，z1和z2不滿足，z3和z4滿足，如圖6.22所示。圖6.22校驗(yàn)節(jié)點(diǎn)檢驗(yàn)矢量(011001)的結(jié)果6.3.2

LDPC碼的性能與應(yīng)用

LDPC碼具有非常接近香農(nóng)理論界限的性能。香農(nóng)理論界限是通信編碼性能的極限值，是人們?cè)O(shè)計(jì)編碼要努力達(dá)到的理想目標(biāo)。研究表明，只要碼長足夠長，LDPC碼具有比Turbo碼更接近香農(nóng)理論界限的性能。目前獲得的LDPC碼的最好性能在10－6誤碼率處距離香農(nóng)理論界限僅0.045dB。LDPC碼的優(yōu)秀性能從一個(gè)側(cè)面反映了LDPC碼有很好的距離特性。進(jìn)一步的仿真表明，當(dāng)碼長適當(dāng)長時(shí)，LDPC碼的誤碼率曲線不會(huì)像Turbo碼那樣出現(xiàn)“錯(cuò)誤平層”，而且仿真結(jié)果中出現(xiàn)的錯(cuò)誤都屬于可檢錯(cuò)誤。

LDPC碼能實(shí)現(xiàn)快速編碼。LDPC碼的編碼方法中有許多是結(jié)構(gòu)性的。校驗(yàn)矩陣具有下三角形結(jié)構(gòu)的LDPC碼可以通過遞推校驗(yàn)位而實(shí)現(xiàn)快速編碼；校驗(yàn)矩陣具有循環(huán)或半循環(huán)結(jié)構(gòu)的LDPC碼，可以根據(jù)其生成多項(xiàng)式用非常簡(jiǎn)單的移位寄存器來進(jìn)行編碼，從而實(shí)現(xiàn)線性時(shí)間編碼，即編碼時(shí)間與碼長之間滿足線性關(guān)系，這是對(duì)通常認(rèn)為的平方關(guān)系的一大突破。

LDPC碼在不同信道上都表現(xiàn)出良好的性能。衰落是通信信道不可避免的物理特性，根據(jù)其衰落信號(hào)幅度所服從的概率分布，常見的衰落信道有瑞利衰落信道和賴斯衰落信道等(詳見7.1節(jié))。刪