一.LDPC編碼介紹

1.為什么要用LDPC編碼，LDPC編碼相對(duì)其他編碼的好處

LDPC(低密度奇偶檢驗(yàn))碼是由稀疏校驗(yàn)矩陣定義的線性分組碼，具有能夠逼近香農(nóng)極限的優(yōu)良特性，其描述簡(jiǎn)單，具有較大的靈活性和較低的差錯(cuò)誤碼特性，可實(shí)現(xiàn)并行操作，譯碼復(fù)雜度低，適合硬件實(shí)現(xiàn)，吞吐量大，極具高速譯碼的潛力，在碼長(zhǎng)較長(zhǎng)的情況下，仍然可以有效譯碼。

目前常用的信道編碼體制有BCH碼、RS碼、卷積碼、Turbo碼和LDPC碼等。其中BCH碼和RS碼都屬于線性分組碼的范疇，在較短和中等碼長(zhǎng)下具有良好的糾錯(cuò)性能；卷積碼在編碼過程中引入了寄存器，增加了碼元之間的相關(guān)性，在相同復(fù)雜度下可以獲得比線性分組碼更高的編碼增益；Turbo碼采用并行級(jí)聯(lián)遞歸的編碼器結(jié)構(gòu)，其分量采用系統(tǒng)的卷積碼，能夠在長(zhǎng)碼時(shí)逼近香農(nóng)極限，同時(shí)譯碼復(fù)雜度也可以接收，但是它的譯碼復(fù)雜性仍然較大，且碼長(zhǎng)較長(zhǎng)時(shí)，由于交織器的存在具有較大的時(shí)延。

相比之下LPDC具有以下特性：

(1)譯碼的復(fù)雜度很低，運(yùn)算量不會(huì)因?yàn)榇a長(zhǎng)的增加而急劇增加；

(2)采用迭代譯碼算法，可以實(shí)現(xiàn)并行操作，具有高速的譯碼能力；

(3)吞吐量大，從而改善系統(tǒng)的傳輸效率，并且便于硬件實(shí)現(xiàn)；

(4)譯碼復(fù)雜度與碼長(zhǎng)成線性關(guān)系，克服了分組碼在長(zhǎng)碼時(shí)所面臨的巨大譯碼計(jì)算復(fù)雜度的問題，使長(zhǎng)編碼分組的應(yīng)用成為可能。

二.LDPC編碼基礎(chǔ)
1. LDPC編碼的定義及矩陣表示
LDPC碼是一類具有稀疏矩陣的線性分組碼，在線性分組碼中，任意兩個(gè)碼字的和仍屬于這個(gè)分組碼，輸出的碼字只和輸入的信息位有關(guān)，即每個(gè)消息是獨(dú)立編碼的。

假設(shè)信源輸出一系列的二進(jìn)制0和1，這些二進(jìn)制塊分成固定長(zhǎng)的消息塊，每個(gè)消息塊記作M，由k比特信息組成,其中M=[m0,m1,…m(k-1)]。然后根據(jù)一定的編碼方式產(chǎn)生一個(gè)n維向量，這個(gè)向量就叫做m的碼字，假設(shè)信息M對(duì)應(yīng)的碼字位C，其中C=[c0,c1,…c(n-1)]，則可以找到k個(gè)線性無關(guān)的碼字g0,g1,…,g(k-1)，使得：

C= m0*g0+m1*g1+……+m(k-1)*g(k-1)

在C中，信息位不變，校驗(yàn)位附加在信息為之后，寫成矩陣的形式就是：

C= M*G

G是k行n列的矩陣，又稱為生成矩陣。

另外，可以由n-k個(gè)n維線性無關(guān)向量h0,h1,…h(huán)(n-k-1)生成C⊥(表示與C對(duì)應(yīng)的零空間)。因此對(duì)于任意的i，hi*CT=0寫成矩陣的形式就是H*CT=0。

H為(n-k)行n列的矩陣，通常被稱為校驗(yàn)矩陣,用來判斷碼字是否合法。

2. LDPC碼的Tanner圖
LDPC編碼可以用Tanner圖來唯一確定，其和校驗(yàn)矩陣是完全等價(jià)的。Tanner圖的頂點(diǎn)稱為節(jié)點(diǎn)，分為變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)，每個(gè)變量節(jié)點(diǎn)與每個(gè)碼字比特相對(duì)應(yīng)，它對(duì)應(yīng)校驗(yàn)矩陣的每一行，每個(gè)校驗(yàn)節(jié)點(diǎn)與每個(gè)校驗(yàn)方程相對(duì)應(yīng)，它對(duì)應(yīng)校驗(yàn)矩陣的每一列，變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間的連線稱為沿，也代表校驗(yàn)矩陣中的1。例如校驗(yàn)矩陣H如下：

圖1

用Tanner圖來表示H矩陣如下：

圖2

在上圖中，從節(jié)點(diǎn)v1出發(fā)，經(jīng)節(jié)點(diǎn)c1,v2,c3，再回到v1，稱為一個(gè)環(huán)，環(huán)的周長(zhǎng)為該環(huán)所包含的邊數(shù)，周長(zhǎng)較短的環(huán)影響譯碼的性能，短環(huán)的存在會(huì)使得譯碼重復(fù)迭代，影響譯碼效率，使譯碼收斂速度變慢，在構(gòu)造LDPC編碼時(shí)應(yīng)盡量避免出現(xiàn)短環(huán)。

3.eIRA編碼算法
對(duì)LDPC碼的編碼可以采用線性分組碼的通用編碼方法，但通用編碼方法的編碼復(fù)雜度與碼長(zhǎng)的平方成正比，編碼時(shí)延較大，實(shí)用性不強(qiáng)。eIRA(extended Irregular Repeat Accumulate，擴(kuò)展的非規(guī)則重復(fù)累積碼)編碼算法，利用校驗(yàn)矩陣的稀疏性進(jìn)行有效編碼，使編碼復(fù)雜度與碼長(zhǎng)成線性關(guān)系。

eIRA編碼算法需要構(gòu)造具有如下形式的校驗(yàn)矩陣

H=[H1 H2]

其中，H1是一個(gè)mXk維稀疏矩陣，H2是一個(gè)階梯狀下三角形矩陣，H2的形式如下：

圖3

系統(tǒng)碼的生成矩陣形式為G=[I P]，其中I是單位矩陣 P=H1^TH2-T，H2^-T的形式為：

圖4

H2^-T可以看成一個(gè)累加器，也稱差分編碼器。因此，eIRA 編碼算法分兩步進(jìn)行，首先將待編碼的信息矢量 m 乘以稀疏矩陣H1T，得到中間結(jié)果S，然后將中間結(jié)果S進(jìn)行重復(fù)累加，得到校驗(yàn)比特，最后將信息比特和校驗(yàn)比特合并起來就得到最終的碼字。

三.LPDC編碼實(shí)現(xiàn)
1.LDPC編碼過程
LDPC編碼器的任務(wù)是將K個(gè)信息比特M=[m0,m1,…,m(k-1)]通過編碼得到(N-K)個(gè)奇偶校驗(yàn)比特P=[p0,p1,…,p(n-k-1)]，最后得到的碼字是將信息比特與校驗(yàn)比特合并，即得到碼長(zhǎng)為N的碼字[i0,i1,…i(k-1),p0,p1,…,p(n-k-1)]。假設(shè)LDPC的碼長(zhǎng)位16200，碼率為1/2，其中Nldpc = 16200,Kldpc =7200,Qldpc=25。

具體計(jì)算步驟如下：

(1)初始化p0=p1=p2=…=p(n-k-1)=0

(2)在表格中第一行指定的校驗(yàn)位地址處累加信息位i0,如下圖所示，這一步的操作為編碼的信息矢量i乘以稀疏矩陣H1^T，一共有20行，即360*20 = 7200。

圖5

對(duì)于接下來的359個(gè)信息位，im,m=1,2,…,359。在{x+(m mod 360) * Qldpc } mod(Nldpc-Kldpc)指定的校驗(yàn)位地址累加信息位im，其中x表示信息為i0對(duì)應(yīng)的校驗(yàn)位地址。

(3)對(duì)于信息i1，校驗(yàn)位的地址需要根據(jù) i0的地址來求，例如第一個(gè)校驗(yàn)位地址,{20+(1 mod 360) * 25 } mod (9000) = 45，第二個(gè)校驗(yàn)位{712+(1 mod 360) * 25} mod (9000) = 737，求出所有的校驗(yàn)位地址，然后進(jìn)行信息累加，如下：

圖6

(4)對(duì)于第361個(gè)信息位i360，在表中的第二行指定了累加器對(duì)應(yīng)的校驗(yàn)位地址。和步驟3相同的處理方式，接下來的359個(gè)信息位對(duì)應(yīng)的校驗(yàn)位地址為{x+(m mod 360) * Qldpc} mod (Nldpc-Kldpc)，其中x表示i360對(duì)應(yīng)的校驗(yàn)位地址。

(5)以同樣的方式處理每一組信息位，給出每一組對(duì)應(yīng)的校驗(yàn)位地址。

(6)從i=1開始，按照下面的公式完成迭代計(jì)算

圖7

2.matlab實(shí)現(xiàn)
在matlab中，有專門的函數(shù)來實(shí)現(xiàn)ldpc編碼，但是在實(shí)現(xiàn)編碼之前，需要我們產(chǎn)生一個(gè)我們需要的校驗(yàn)矩陣H。這里以Nldpc = 16200 ,碼率1/2為例，介紹校驗(yàn)矩陣H的產(chǎn)生過程。

(1)按照上述LDPC編碼中提到的，把校驗(yàn)位起始的地址存儲(chǔ)起來，用于計(jì)算

其他的校驗(yàn)位。

圖8

把數(shù)據(jù)分成兩組是因?yàn)閿?shù)據(jù)的列數(shù)不一樣，把相同列數(shù)的歸到同一組里，這樣更方便計(jì)算。

(2)根據(jù)公式，第一行，計(jì)算剩余359個(gè)校驗(yàn)位地址，其他行也做同樣的操作，如下代碼表示計(jì)算ct1所表示的校驗(yàn)位，ct2校驗(yàn)位的計(jì)算同ct1。

圖9

(3)計(jì)算完所有的校驗(yàn)位之后，按照如下操作產(chǎn)生校驗(yàn)矩陣

圖10

(4)用產(chǎn)生的校驗(yàn)矩陣，計(jì)算LDPC編碼，這里使用comm.LDPCEncoder函數(shù)來實(shí)現(xiàn)，在較早的matlab版本中是fec.ldpcenc函數(shù)。

圖11

3.FPGA實(shí)現(xiàn)
FGPA不可能一次性存儲(chǔ)那么多的數(shù)據(jù)，并且也不現(xiàn)實(shí)，需要根據(jù)實(shí)時(shí)的計(jì)算產(chǎn)生校驗(yàn)位。通過上述的分析可知，LDPC碼的編碼具有周期為360的并行結(jié)構(gòu)，如果把長(zhǎng)度為K的信息比特分成r=K/360組，長(zhǎng)度為N-K的校驗(yàn)比特分成s=(N-K)/360如下所示

圖12

由每個(gè)信息比特對(duì)應(yīng)的校驗(yàn)比特公式pj=pj⊕im，其中j={x+(m mod 360)*q} mod(N-K)，x是第im個(gè)信息比特所對(duì)應(yīng)的校驗(yàn)比特地址。可知,每一組信息比特均參與了同一組校驗(yàn)比特校驗(yàn)的過程。

考慮到碼的周期性，我們可以同時(shí)進(jìn)行M=360次并行處理，增加編碼效率，可以寫成以下迭代公式:

圖13

其中符號(hào)‘r’和‘c’表示校驗(yàn)矩陣 H 的行和列，和信息節(jié)點(diǎn)連接的所有檢驗(yàn)節(jié)點(diǎn)的集合定義為CN(c)。兩個(gè)迭代循環(huán)，每次計(jì)算M個(gè)信息位，按照下面的矩陣形式存儲(chǔ)Sr

圖14

從公式中可以看到，并行更新的M個(gè)Sr處于矩陣的同一行，但是輸出的順序并不是我們想要的順序，不是從行的第一位到最后一位，因此需要對(duì)輸入的信息位做循環(huán)移位，以保證S矩陣的結(jié)構(gòu)。

一旦得到Sr就可以得到pr

圖15

計(jì)算S矩陣所有列的累加和，可以的到下面的向量

圖16

然后按照下面的公式計(jì)算s’

圖17

其中，L位MXM的下三角矩陣，然后將s’邏輯右移一位，得到

圖18

最后按照下面的公式，每次計(jì)算Mbit校驗(yàn)位

圖19

根據(jù)以上的公式推導(dǎo)，提出以下的實(shí)現(xiàn)結(jié)構(gòu)，有三個(gè)主要部分組成：第一部分計(jì)算Sr的值，第二部分就算S矩陣中列的累加和，第三部分計(jì)算校驗(yàn)位。編碼器的系統(tǒng)結(jié)構(gòu)主要包括編碼配置模塊(Ldpc_contrl)，信息位分組計(jì)數(shù)模塊(data_recv)，基地址產(chǎn)生模塊(Bom_addr)，數(shù)據(jù)地址計(jì)算模塊(ADDER_GEN)，校驗(yàn)位計(jì)算模塊(iterator)，整個(gè)系統(tǒng)結(jié)構(gòu)如下圖所示：

圖20

3.1編碼配置

在配置模塊中提供了1/4，1/2，3/5，2/3，3/4，4/5，5/6七種碼率，為了實(shí)現(xiàn)編碼方式的可配置，利用寄存器保存不同碼率下的參數(shù)，主要包括Qldpc,Kldpc，可以在整個(gè)系統(tǒng)結(jié)構(gòu)中看到。首先檢測(cè)配置使能信號(hào)，然后加載配置數(shù)據(jù)，保存參數(shù)。其中fram和fram_en是輸入信息位和使能延遲輸出，考慮到最壞的情況下，配置信號(hào)和數(shù)據(jù)同時(shí)到來，需要先配置，才能進(jìn)行數(shù)據(jù)的處理，所以對(duì)數(shù)據(jù)要延遲幾個(gè)時(shí)鐘周期。

3.2 信息位分組計(jì)數(shù)

模塊的主要作用是對(duì)輸入的信息比特進(jìn)行序號(hào)標(biāo)記，采用三個(gè)計(jì)數(shù)器，其中data_cnt為 0~14 表示15個(gè)數(shù)據(jù) rom_cnt 為 0~23，24組表示共24*15=360個(gè)數(shù)據(jù)，0表示初始數(shù)據(jù)，fram_cnt，360bit的組數(shù)統(tǒng)計(jì)。如對(duì)應(yīng)1/2碼率，輸入數(shù)據(jù)為7200bit，則數(shù)據(jù)可分為：20*360 = 20*15*24 =7200，下圖為信息位分組計(jì)數(shù)模塊主要信號(hào)的時(shí)序圖，延遲的是因?yàn)樵谟?jì)算校驗(yàn)位地址的時(shí)候會(huì)花費(fèi)時(shí)間，為了后邊計(jì)算校驗(yàn)位時(shí)信息位能夠和校驗(yàn)地址對(duì)齊。

圖21

3.3 基地址產(chǎn)生

基地址產(chǎn)生模塊根據(jù)輸入的碼率選擇存在rom中的基地址，選擇基地址的讀取位置由輸入的碼率和輸入序號(hào)共同確定，輸入碼率確定及地址的起始位置，序號(hào)fram_cnt確定基地址的偏移。以1/2碼率為例，rom中初始地址為63，當(dāng)fram為0時(shí)表示第一行，讀取的基地址如下：

圖22

仿真時(shí)鐘周期為20ns，地址輸出相對(duì)信息位使能延遲了16個(gè)時(shí)鐘周期，其中移位輸出的計(jì)數(shù)器分別延時(shí)了兩個(gè)時(shí)鐘周期。延遲是為了在校驗(yàn)位計(jì)算的時(shí)候，地址能夠和信息位對(duì)齊。

3.4 數(shù)據(jù)地址計(jì)算

地址計(jì)算模塊需要根據(jù)公式{x+(m mod360) * Qldpc } mod (Nldpc-Kldpc)，計(jì)算每個(gè)信息位所對(duì)應(yīng)的校驗(yàn)位。但是這個(gè)公式所用的取模以及乘法運(yùn)算不適合在FPGA中運(yùn)算，會(huì)占用很多的DSP資源，而且也是不必要的。以1/2碼率為例，可以轉(zhuǎn)化為如下的加減運(yùn)算。

圖23

result = Amod B ，當(dāng)A小于B時(shí)result等于A本身，當(dāng)A大于B時(shí)result等于A-B，通過這個(gè)模塊計(jì)算出每個(gè)信息位所對(duì)應(yīng)的的校驗(yàn)位。

圖24

其中data_in_bom為初始地址，data_in_addr為計(jì)算的校驗(yàn)位地址。

3.5校驗(yàn)比特計(jì)算

校驗(yàn)比特計(jì)算需要完成兩個(gè)部分，第一部分為信息位的輸出，第二部分為校驗(yàn)位的輸出。因?yàn)樵谟布袨閷?shí)時(shí)處理。以1/2碼率為例，發(fā)送的16200bit碼字，包括7200bit信息位，9000bit校驗(yàn)位，兩個(gè)部分分時(shí)段進(jìn)行。系統(tǒng)采用13個(gè)并行度計(jì)算校驗(yàn)位，其中的一個(gè)的時(shí)序如下：

圖25

雙口ram設(shè)置為read first，數(shù)據(jù)相對(duì)于地址有三個(gè)時(shí)鐘的延遲。上述中所涉及的延遲均在調(diào)試中根據(jù)運(yùn)算所需時(shí)鐘數(shù)進(jìn)行的延遲。采用13個(gè)并行度計(jì)算校驗(yàn)位，其中的一個(gè)的結(jié)構(gòu)如下，addr_ena和addr_flag均由read_addr控制。

圖26

最后把每個(gè)13個(gè)并行度的數(shù)據(jù)相加，然后與上一位的值異或，得到最終的輸出。

圖27

通過modelsim把結(jié)果輸出和matlab計(jì)算的結(jié)果進(jìn)行比較，可以看到我們使用FPGA實(shí)現(xiàn)的結(jié)果和用matlab做出的結(jié)果是一樣的。

圖28

編輯：hfy