基于CMMB系統(tǒng)的LDPC譯碼器的設(shè)計(jì)與實(shí)現(xiàn)

摘要：根據(jù)CMMB中LDPC碼校驗(yàn)矩陣的結(jié)構(gòu)特點(diǎn)，提出了一種部分并行譯碼結(jié)構(gòu)的實(shí)現(xiàn)方法，并在XILINX的VirtexIV的XC4VLX80型FPGA上實(shí)現(xiàn)了這種結(jié)構(gòu)。該設(shè)計(jì)充分利用了LDPC校驗(yàn)矩陣的規(guī)律，采用了一種適當(dāng)?shù)挠布Y(jié)構(gòu)和獨(dú)特的存儲(chǔ)器調(diào)用控制策略，故可在保證高性能和較大吞吐率的情況下，以較少的硬件資源實(shí)現(xiàn)兩種碼率的復(fù)用。
關(guān)鍵詞：CMMB；中國(guó)移動(dòng)多媒體廣播；LDPC碼；部分并行結(jié)構(gòu)；譯碼器

0 引言
    低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)碼是由Gallager博士在1962年首次提出來(lái)的，由于LDPC碼的誤碼性能能夠逼近香農(nóng)限，因而在無(wú)線通信、衛(wèi)星通信等領(lǐng)域都得到了較多應(yīng)用。中國(guó)移動(dòng)多媒體廣播(CMMB)中使用的就是LDPC糾錯(cuò)編碼。在CMMB標(biāo)準(zhǔn)中，LDPC碼長(zhǎng)為9216，可支持1／2和3／4兩種碼率。作者通過(guò)深入分析CMMB中LDPC碼校驗(yàn)矩陣的特點(diǎn)，采用了一種合適的硬件實(shí)現(xiàn)結(jié)構(gòu)，因而在保證譯碼器較高性能和較快譯碼速度的情況下，以較低的硬件資源實(shí)現(xiàn)了兩種碼率的復(fù)用。

1 CMMB標(biāo)準(zhǔn)中的LDPC譯碼算法
1．1 CMMB中LDPC碼的主要特征
    CMMB采用規(guī)則的LDPC碼，兩種碼率的LDPC校驗(yàn)矩陣有類(lèi)似的規(guī)律。CMMB中1／2碼率的LDPC碼校驗(yàn)矩陣為一個(gè)4608x9216的矩陣，進(jìn)一步可劃分為256個(gè)18x9216行子矩陣。其中下一個(gè)行子矩陣是上一個(gè)行子矩陣的向右循環(huán)移36位，每一個(gè)行子矩陣的行重都為6；也可以把它劃分為256個(gè)4608x36列子矩陣，其中后一個(gè)列子矩陣是前一個(gè)列子矩陣的向下循環(huán)移18位，每一個(gè)列子矩陣的列重都為3。同理，3／4碼率的矩陣也可以進(jìn)行類(lèi)似的劃分，可劃分為256個(gè)9x9216的行子矩陣，每個(gè)行子矩陣的行重為12；當(dāng)然，也可以分為256個(gè)2304x36，列重為3的列子矩陣。從校驗(yàn)矩陣的特點(diǎn)可以看出，只要存儲(chǔ)器能存儲(chǔ)一個(gè)行或列子矩陣的非零元素，則利用這些非零元素，就可以恢復(fù)出整個(gè)校驗(yàn)矩陣，從而進(jìn)行譯碼。而且更為重要的是，對(duì)于同種碼率，行子矩陣組和列子矩陣組之間在非零元素位置上有著潛在的對(duì)應(yīng)關(guān)系。本文正是通過(guò)挖掘這種潛在的對(duì)應(yīng)關(guān)系，設(shè)計(jì)出了一種獨(dú)特的存儲(chǔ)器調(diào)用控制策略，并成功實(shí)現(xiàn)了復(fù)用RAM的同時(shí)，滿(mǎn)足了兩種碼率的硬件結(jié)構(gòu)。
1．2 LDPC譯碼算法
    常用的LDPC碼譯碼算法為置信度傳遞解碼算法(BP decoding)。該算法相對(duì)比較成熟，性能非常優(yōu)異。但是，BP算法中的f(x)函數(shù)包含對(duì)數(shù)運(yùn)算和指數(shù)運(yùn)算，這些復(fù)雜運(yùn)算大大增加了BP譯碼器的運(yùn)算量和復(fù)雜度。Fossorier等在1999年提出了一種min-sum譯碼算法，即利用一種近似的方法來(lái)處理BP算法中的f(x)函數(shù)，以將對(duì)數(shù)和指數(shù)運(yùn)算化簡(jiǎn)為乘法和比較運(yùn)算，從而減少了譯碼器的運(yùn)算量，但該方法在性能上也有一定損失。后來(lái)，Jinghu Chen和Fossorier又提出了修正的min-sum算法。在碼長(zhǎng)較長(zhǎng)的情況下，修正的min-sum算法比BP算法性能只差0．03～0．05 dB，而在算法復(fù)雜度上則只需要乘以一個(gè)常量修正因子?；谝陨戏治觯疚牟捎眯拚膍in-sum算法來(lái)進(jìn)行迭代更新，此更新分為校驗(yàn)節(jié)點(diǎn)更新和變量節(jié)點(diǎn)更新。其迭代譯碼步驟分為兩步。
    第一步是初始化，即對(duì)每個(gè)m和n，
    其次是迭代過(guò)程。而每次迭代又包括以下3個(gè)步驟：

從而達(dá)到預(yù)定的迭代次數(shù)。否則重新更新Qm=n并開(kāi)始下一輪迭代。上面式中的k表示第k次迭代。
    記集合N(m)表示與校驗(yàn)節(jié)點(diǎn)相連的所有變量節(jié)點(diǎn)；集合M(n)表示與變量節(jié)點(diǎn)相連的所有校驗(yàn)節(jié)點(diǎn)；N(m)＼n表示N(m)中除去變量節(jié)點(diǎn)n，同理，M(n)＼m表示M(n)中除去校驗(yàn)節(jié)點(diǎn)m。α一般取值為0．6～0．9，本系統(tǒng)中通過(guò)C模型浮點(diǎn)和定點(diǎn)仿真，可以得到α的最佳取值約為0．8，為了便于移位實(shí)現(xiàn)，取值為0．7875或者0．8125均可。

2 CMMB中LDPC譯碼器的硬件實(shí)現(xiàn)
2．1 譯碼器總體結(jié)構(gòu)
    LDPC碼的譯碼器通常有串行結(jié)構(gòu)、并行結(jié)構(gòu)和部分并行結(jié)構(gòu)等。根據(jù)校驗(yàn)矩陣的特點(diǎn)，LDPC部分并行譯碼結(jié)構(gòu)可簡(jiǎn)單分為輸入和輸出存儲(chǔ)單元、VNU(變量節(jié)點(diǎn)運(yùn)算)單元、CNU(校驗(yàn)節(jié)點(diǎn)運(yùn)算)單元和中間結(jié)果存儲(chǔ)單元。其譯碼器結(jié)構(gòu)如圖1所示。為了便于ASIC實(shí)現(xiàn)，本文采用單端口RAM，每塊RAM由一個(gè)控制器控制以實(shí)現(xiàn)不同碼率的地址初始化、讀RAM、寫(xiě)RAM等操作。

2．2 輸入和輸出存儲(chǔ)單元
    檢測(cè)到輸入數(shù)據(jù)有效后，可把輸入的串行數(shù)據(jù)依次存到初始化RAM里。本譯碼器一共有36個(gè)初始化存儲(chǔ)器，每個(gè)存儲(chǔ)器的深度為256。第1個(gè)數(shù)據(jù)存到第1個(gè)RAM的0地址，第2個(gè)數(shù)據(jù)存到第2個(gè)RAM的0地址，依次類(lèi)推，第37個(gè)數(shù)據(jù)再存到第1個(gè)RAM的1地址，直到一幀9216個(gè)數(shù)據(jù)全部存滿(mǎn)36個(gè)RAM。同樣，輸出存儲(chǔ)單元可采用類(lèi)似的存儲(chǔ)器調(diào)度方式。為了實(shí)現(xiàn)譯碼的連續(xù)性，本設(shè)計(jì)在輸入和輸出部分使用了乒乓結(jié)構(gòu)，即采用兩組相同的36個(gè)RAM交替操作方式。
2．3 VNU單元
    VNU單元用于完成兩部分工作：一是由校驗(yàn)節(jié)點(diǎn)和初始化信息來(lái)更新變量節(jié)點(diǎn)的值；二是對(duì)每一列進(jìn)行硬判決。檢驗(yàn)節(jié)點(diǎn)更新后的值將存儲(chǔ)到存儲(chǔ)單元R_Mem，而硬判決后的比特值則存到輸出存儲(chǔ)單元，直到滿(mǎn)足停止譯碼兩個(gè)條件之一時(shí)才可輸出碼字。第一次垂直更新時(shí)，不用輸入存儲(chǔ)單元Q_Mem的值，而只把輸入存儲(chǔ)單元里的初始值送到VNU單元進(jìn)行更新運(yùn)算即可。由于兩種碼率下LDPC檢驗(yàn)矩陣的列重都是3，因此，兩種碼率下的VNU個(gè)數(shù)都為36個(gè)，且每個(gè)VNU結(jié)構(gòu)也都是4輸入的VNU。每次運(yùn)算時(shí)，都必須讀輸入存儲(chǔ)單元和Q_Mem(除第一次迭代外)中的數(shù)據(jù)的運(yùn)算結(jié)果，但應(yīng)同時(shí)寫(xiě)入R_Mem存儲(chǔ)單元中。本操作內(nèi)部采用流水線結(jié)構(gòu)，每次迭代都延遲2個(gè)時(shí)鐘周期。由于讀地址都為0，而且讀地址每次加1，因此，執(zhí)行變量節(jié)點(diǎn)更新運(yùn)算共需花費(fèi)256+2個(gè)時(shí)鐘，垂直更新結(jié)構(gòu)的變量節(jié)點(diǎn)單元加法運(yùn)算器結(jié)構(gòu)如圖2所示。

2．4 CNU單元
    CNU單元也包括兩部分工作：一是由變量節(jié)點(diǎn)來(lái)更新校驗(yàn)節(jié)點(diǎn)的值，并將更新后的值存儲(chǔ)到外部存儲(chǔ)器；二是對(duì)每一行硬判決后的比特進(jìn)行校驗(yàn)，以確定其是否滿(mǎn)足校驗(yàn)方程，也就是對(duì)每一行所對(duì)應(yīng)比特進(jìn)行異或，并看結(jié)果是否為零。若所有行的異或結(jié)構(gòu)都為零，則譯碼成功，退出迭代。在CMMB標(biāo)準(zhǔn)中，兩種碼率校驗(yàn)矩陣H的行重有所不同(分別為6和12)。為了能共用CNU模塊并且共享存儲(chǔ)器資源，筆者設(shè)計(jì)了12輸入的CNU單元，并且使用9個(gè)CNU單元并行計(jì)算。這樣，當(dāng)碼率為1／2時(shí)，1個(gè)CNU單元更新2行，9個(gè)正好更新18行；而當(dāng)碼率為3／4時(shí)，9個(gè)CNU單元更新9行。每個(gè)12輸入的CNU單元由2個(gè)6輸入CNU單元組成，通過(guò)1個(gè)選擇器可控制CNU輸出。l／2碼率時(shí)，2個(gè)6輸入CNU的輸出結(jié)果可直接作為12輸入CNU的輸出結(jié)果，然后經(jīng)緩存后送入Q_Mem；3／4碼率時(shí)，2個(gè)6輸入CNU的輸出再經(jīng)過(guò)一級(jí)比較器得出的結(jié)果，才作為12輸入CNU的輸出值送到Q_Mem存儲(chǔ)。為了方便比較最后一級(jí)比較器，可在復(fù)用已有的兩組6輸入輸出比較單元的同時(shí)，還得輸出兩組最小值。CNU單元電路采用流水線結(jié)構(gòu)來(lái)設(shè)計(jì)延時(shí)增加4個(gè)時(shí)鐘周期(1／2碼率)和5個(gè)時(shí)鐘周期(3／4碼率)。6輸入輸出CNU單元的結(jié)構(gòu)簡(jiǎn)圖如圖3所示。

2．5 中間結(jié)果存儲(chǔ)單元(R_Mem和Q_Mem)
    由于兩種碼率時(shí)，校驗(yàn)矩陣第1個(gè)子矩陣中非零元素的位置不一樣。故在水平更新時(shí)，RAM的初始化地址也不一樣，需要用兩組初始地址值。對(duì)兩種碼率來(lái)說(shuō)，第1個(gè)行子矩陣非零元素的個(gè)數(shù)都為108(18x6或9x12)。事實(shí)上，第1個(gè)列子矩陣非零元素的個(gè)數(shù)同樣為108(3x36)。第1個(gè)行子矩陣和第1個(gè)列子矩陣非零元素位置有著潛在的一一對(duì)應(yīng)的關(guān)系。舉例來(lái)說(shuō)，第1行(下標(biāo)從0開(kāi)始)6個(gè)1的列位置(下標(biāo)從0開(kāi)始)分別為0，7，19，26，31，5664。若分析第5664列可以發(fā)現(xiàn)5664=157x36+12，即5664列是第12列的移位。第12列中非零位置對(duì)應(yīng)的行號(hào)為0，119，1783=99x18+1。第5664列中非零位置對(duì)應(yīng)的行號(hào)為1，826，2945。于是非零位置(1783，12)的映射為(1，5664)。這樣，通過(guò)挖掘行子矩陣和列子矩陣中每一個(gè)非零位置的對(duì)應(yīng)關(guān)系，就能準(zhǔn)確地得出VNU和CNU運(yùn)算單元數(shù)據(jù)之間的對(duì)應(yīng)關(guān)系。把這種對(duì)應(yīng)關(guān)系體現(xiàn)到memory的調(diào)度上來(lái)，就能準(zhǔn)確地從R_Mem和Q_Mem中取值以進(jìn)行水平和垂直更新。表1所列是中間結(jié)果存儲(chǔ)單元和寫(xiě)地址的對(duì)應(yīng)關(guān)系。

    這里分別用了108個(gè)深度為256、寬度為6bits的單口RAM作為R_Mem和Q_Mem。當(dāng)進(jìn)行變量節(jié)點(diǎn)運(yùn)算時(shí)，VNU輸入可從Q_Mem中讀取，讀數(shù)時(shí)，首地址為0，VNU輸出寫(xiě)入R_Mem中，寫(xiě)順序首地址為黑體數(shù)字，運(yùn)算周期為256；當(dāng)所有變量節(jié)點(diǎn)更新后，接著是校驗(yàn)節(jié)點(diǎn)的運(yùn)算，同時(shí)
可進(jìn)行檢驗(yàn)方程運(yùn)算。此時(shí)，CNU輸入從R_Mem中讀取，讀數(shù)的首地址為0，CNU輸出寫(xiě)入Q_Mem中，寫(xiě)入順序首地址為黑體數(shù)字，運(yùn)算周期同樣為256。如此交替，便可完成迭代過(guò)程。上述例子中，(1，5664)和(1783，1)的對(duì)應(yīng)關(guān)系反映在存儲(chǔ)單元上，正如表1中的第2列所示。

3 譯碼器的性能分析及FPGA實(shí)現(xiàn)
    作者通過(guò)C語(yǔ)言模型和MATLAB模型對(duì)譯碼器進(jìn)行了浮點(diǎn)和定點(diǎn)仿真。為了達(dá)到性能和面積的平衡，位寬的取值為6 bits，而譯碼器性能只比浮點(diǎn)模型損失了約0．15 dB。在AWGN信道和BPSK的調(diào)制解調(diào)方式下，當(dāng)碼率為1／2，信噪比SNR為1．6 dB時(shí)，誤碼率已經(jīng)降至10-5以下。而在信噪比SNR為1．7 dB時(shí)，誤碼率已經(jīng)降至10-7以下；當(dāng)碼率為3／4時(shí)，在信噪比SNR為3．0 dB時(shí)，誤碼率可以降至10-6以下。
    本文按照上面所描述的硬件結(jié)構(gòu)，采用XILINX的VirtexIV-XC4VLX80器件實(shí)現(xiàn)了CMMB標(biāo)準(zhǔn)中兩種碼率的LDPC譯碼，并且達(dá)到了和C定點(diǎn)模型同樣的性能。在ISE開(kāi)發(fā)工具上對(duì)其進(jìn)行編譯時(shí)，其具體的資源利用情況如表2所列。

    從表2中可以看出，此結(jié)構(gòu)不僅完全地復(fù)用了存儲(chǔ)器資源，而且最大限度地復(fù)用了邏輯運(yùn)算單元。正是因?yàn)閮煞N碼率可復(fù)用RAM資源，使memory消耗較少，從而剩下大量的RAM資源可以用作CMMB其余部分(如解交織模塊)使用。LUT資源相對(duì)來(lái)說(shuō)用得較多，這是由于并行結(jié)構(gòu)造成的，它有36個(gè)VNU和9個(gè)CNU交替進(jìn)行運(yùn)算。

4 結(jié)束語(yǔ)
    本文設(shè)計(jì)的部分并行結(jié)構(gòu)的LDPC譯碼器能夠兼容不同碼率和不同校驗(yàn)矩陣行重的LDPC碼。運(yùn)用該譯碼結(jié)構(gòu)在XILINX的VirtexIVC4VLX80器件上可實(shí)現(xiàn)CMMB標(biāo)準(zhǔn)中兩種碼率的LDPC譯碼。事實(shí)上，針對(duì)校驗(yàn)矩陣的特點(diǎn)，采用一種獨(dú)特的存儲(chǔ)器控制策略，可以最大限度地復(fù)用硬件資源，從而大大減少了譯碼器的資源消耗。