張 鵬，楊 剛，楊 霏，劉昌銀

（中國傳媒大學(xué) 信息工程學(xué)院，北京 100024）

1 引言

近年來，LDPC碼以其優(yōu)異糾錯(cuò)性能和低譯碼復(fù)雜度備受關(guān)注，在通信、數(shù)字電視廣播等領(lǐng)域得到了廣泛應(yīng)用。

CMMB標(biāo)準(zhǔn)[1]采用了1/2和3/4兩種碼率的LDPC碼作為前向糾錯(cuò)技術(shù)。雖然它們具有一定的循環(huán)特性[2]，但不是準(zhǔn)循環(huán)LDPC碼[3]，需要采用通用的編碼方法，其編碼的硬件實(shí)現(xiàn)是CMMB調(diào)制器的技術(shù)難點(diǎn)。

第一個(gè)具有線性復(fù)雜度的通用編碼方法是Neal提出的LU分解編碼算法[4]，算法非常簡單。筆者通過深入分析CMMB標(biāo)準(zhǔn)中LDPC碼校驗(yàn)矩陣的特點(diǎn)，采用改進(jìn)的LU分解編碼算法，使用較少的存儲(chǔ)器實(shí)現(xiàn)了這兩種碼率的LDPC編碼器。

2 LU分解編碼算法及其改進(jìn)

2.1 LU分解編碼算法

考慮一個(gè)q進(jìn)制LDPC系統(tǒng)碼，其碼字、信息、校驗(yàn)向量的長度分別是 n，k，r（r=n-k）。 設(shè)碼字向量為

式中：S=[si]（si是信息元，i=0，1，…，k-1）是 1×k 階信息向量，P=[pi]（pi是校驗(yàn)元，i=0，1，…，r-1）是 1×r階校驗(yàn)向量。令其r×n階行滿秩校驗(yàn)矩陣為

式中：A是r×k階矩陣，B是r×r階滿秩矩陣。通過行列交換，B可分解成下三角矩陣L和上三角矩陣U的乘積，即

式中：V和W分別是初等行和列交換矩陣，L，U，V和W均是r×r階。因?yàn)閂和W都是初等矩陣，所以它們的轉(zhuǎn)置與逆相等，即VT=V-1和WT=W-1。

作為一種特殊的線性分組碼，LDPC碼同樣滿足以下一般關(guān)系

將式（1）～（3）代入上式，整理可得

根據(jù)上述推導(dǎo)過程，可給出LU分解編碼算法的步驟為：

1）計(jì)算向量 X：XT=VAST；

2）前向迭代計(jì)算向量Y：YT=L-1XT；

3）后向迭代計(jì)算向量Z：ZT=U-1YT。然后對Z重新排序，得到最終的編碼結(jié)果PT=-WZT。PT=-WZT等價(jià)于P=-ZWT。

2.2 改進(jìn)的LU分解編碼算法

圖1 H經(jīng)行列交換后的結(jié)構(gòu)示意圖

圖2 改進(jìn)的LU分解編碼算法示意圖

經(jīng)初等行列交換后，校驗(yàn)矩陣H的右上角可轉(zhuǎn)化成一個(gè)全0的梯形矩陣，如圖1所示。圖中，灰色區(qū)域表示其中的元素可能是0也可能是非0。

利用梯形部分編碼算法和H的前d行可求出校驗(yàn)向量的一部分P1，d是梯形部分編碼算法的編碼能力，其余校驗(yàn)元P2可通過LU分解編碼算法和H的后r-d行求出，如圖2所示。

改進(jìn)的LU分解編碼算法步驟為：

1）由梯形部分編碼算法迭代求出P1；

2）計(jì)算向量 X′：X′T＝V′A′[S P1]T；

3）前向迭代計(jì)算向量 Y′：Y′T＝L′-1X′T；

4）后向迭代計(jì)算向量Z′：Z′T=U′-1Y′T，并對Z′重新排序，=-W′Z′T，得到最終的編碼結(jié)果 P=[P1P2]。

2.3 LU分解

LU分解編碼算法的關(guān)鍵是找出盡可能稀疏的LU分解矩陣L和U[5]。LU分解一個(gè)稀疏方陣得到的上下三角矩陣的非零元素總數(shù)要大于原方陣，方陣越大，分解結(jié)果的非零元素總數(shù)越

多。當(dāng)原LU分解編碼算法及其改進(jìn)均采用相同的LU分解算法時(shí)，由于原算法的分解對象的尺寸要大于改進(jìn)算法的分解對象，所以改進(jìn)算法得到的上下三角矩陣的非零元素總數(shù)要少一些，這就意味著改進(jìn)算法的存儲(chǔ)量需求比原算法少。

3 CMMB標(biāo)準(zhǔn)的LU分解編碼器

3.1 CMMB標(biāo)準(zhǔn)中的LDPC碼

CMMB標(biāo)準(zhǔn)采用RS碼（外碼）和LDPC碼（內(nèi)碼）級聯(lián)的前向糾錯(cuò)方式。CMMB標(biāo)準(zhǔn)采用了1/2和3/4兩種碼率的二進(jìn)制 LDPC 碼，前者是（9216，3，6）規(guī)則碼，后者是（9216，3，12）規(guī)則碼。 它們都是系統(tǒng)碼，但信息向量不是原封不動(dòng)地集中放置在碼字的前半部分，而是被打亂散布在碼字中。標(biāo)準(zhǔn)中只給出了稀疏校驗(yàn)矩陣，而未給出生成矩陣。

兩種碼率的稀疏校驗(yàn)矩陣都具有一定的循環(huán)特性：對于 1/2（3/4）碼率，整個(gè)校驗(yàn)矩陣是由前 18（9）行每隔18（9）行循環(huán)移動(dòng)36位得到。這兩種碼都不是準(zhǔn)循環(huán)LDPC碼，只能采用通用的編碼方法，其編碼是技術(shù)難點(diǎn)。

3.2 CMMB標(biāo)準(zhǔn)的LDPC編碼器

傳統(tǒng)的LU分解編碼算法將H分割成左右兩部分，破壞了校驗(yàn)矩陣的行整體特性。因?yàn)樘菪尾糠志幋a算法使用的是校驗(yàn)矩陣的整行，所以前面述及的改進(jìn)算法能在一定程度上充分利用校驗(yàn)矩陣的固有特性，比如行重相等和行循環(huán)性，而CMMB標(biāo)準(zhǔn)中的LDPC碼恰好具備這些特性。由此得出，改進(jìn)的LU分解編碼算法非常適用于CMMB標(biāo)準(zhǔn)中的LDPC碼。

圖3是CMMB標(biāo)準(zhǔn)的LDPC碼的改進(jìn)LU分解編碼器，采用4級流水線結(jié)構(gòu)，適用于1/2和3/4兩種碼率。圖中，矩形框表示操作，圓圈表示FPGA片內(nèi)存儲(chǔ)器，其中存儲(chǔ)的是矩陣中非零元素所在的行或列地址。與前面述及的算法步驟相比，實(shí)現(xiàn)方案多了一個(gè)重新排序的環(huán)節(jié)。這是因?yàn)镃MMB標(biāo)準(zhǔn)的LDPC碼的信息向量不是原封不動(dòng)地連續(xù)放置在碼字的前半部分，而是要按照一定映射方式亂序后放在碼字中。

圖3 改進(jìn)LU分解編碼器的結(jié)構(gòu)框圖

3.3 存儲(chǔ)器耗用分析

預(yù)處理表明，1/2和3/4兩種碼率的d分別是2544和1776。1/2碼率的矩陣L′和U′分別有22498和18240個(gè)“1”，3/4碼率則為7640和3774。這些數(shù)字均小于文獻(xiàn)[5]給出的數(shù)據(jù)。此外，提出的編碼方案能利用校驗(yàn)矩陣的行循環(huán)性，從而在一定程度上壓縮相關(guān)矩陣的存儲(chǔ)。綜上可見，提出的編碼方案能有效降低存儲(chǔ)器的消耗。

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)中，在Altera公司的Cyclone III系列EP3C120 FPGA上實(shí)現(xiàn)了CMMB標(biāo)準(zhǔn)中兩種碼率LDPC碼的改進(jìn)LU分解編碼器。編碼過程中使用的矩陣和向量均存儲(chǔ)在片內(nèi)RAM中。表1比較了本文和文獻(xiàn)[6]的資源消耗。文獻(xiàn)[6]采用的是Altera公司的Stratix II系列EP2S90 FPGA。

表1 本文和文獻(xiàn)[6]的資源消耗（絕對量/百分比）

由表1可知，兩種方案都使用了少量的邏輯單元。但在RAM資源消耗方面，本文方案的優(yōu)勢非常明顯。本文比文獻(xiàn)[6]少用了1087 079 bit的片內(nèi)RAM，這是非?？捎^的，從而使選用廉價(jià)的低端FPGA成為可能。

改進(jìn)后的LU分解編碼器的最高工作頻率可達(dá)到177.25 MHz。當(dāng)工作頻率是100 MHz時(shí)，系統(tǒng)凈荷數(shù)據(jù)率為 17.082 Mbit/s（1/2 碼率）和 38.9 Mbit/s（3/4 碼率），能夠滿足CMMB標(biāo)準(zhǔn)的最高指標(biāo)：10.852 Mbit/s和16.243 Mbit/s。

5 小結(jié)

筆者設(shè)計(jì)了的改進(jìn)LU分解編碼器能滿足CMMB標(biāo)準(zhǔn)系統(tǒng)指標(biāo)，兼容兩種碼率。該編碼結(jié)構(gòu)能充分利用CMMB標(biāo)準(zhǔn)的LDPC碼校驗(yàn)矩陣的行重相等和行循環(huán)性等固有特性。該編碼器在Altera公司的EP3C120 FPGA上驗(yàn)證通過。實(shí)驗(yàn)結(jié)果表明，提出的設(shè)計(jì)方案大大減少了存儲(chǔ)器資源需求，可選用低價(jià)位的FPGA芯片，從而降低了設(shè)備成本，具有良好的工程實(shí)用價(jià)值。

[1]國家廣播電影電視總局.GY/T220.1-2006移動(dòng)多媒體廣播 第1部分∶廣播信道幀結(jié)構(gòu)、信道編碼和調(diào)制[S].北京：中國標(biāo)準(zhǔn)出版社，2006.

[2]康亮，楊波，沈萌.符合CMMB標(biāo)準(zhǔn)的LDPC解碼器設(shè)計(jì)[J].電視技術(shù)，2009，33（5）：40-42.

[3]WANG Z F,CUI Z Q.Low-complexity high-speed decoder design for quasi-cyclic LDPC codes[J].IEEE Trans.Very Large Scale Integration（VLSI）Systems，2007，15（1）：104-114.

[4]NEAL R M.Sparse matrix methods and probabilistic inference algorithm[EB/OL].[2009-12-20].http∶//www.ima.umn.edu/biology/wkshp_abstracts/neal1.html.

[5]SU J N，JIANG Z，LIU K，et al.An efficient low complexity LDPC encoder based on LU factorization with pivoting[EB/OL].[2009-08-20].http∶//d.wanfangdata.com.cn/NSTLHY_NSTL_HY12420269.aspx.

[6]WANG P，CHEN Y E.Low-complexity real-time LDPC encoder design for CMMB [EB/OL].[2009-08-20].http∶//ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4603986%2F4603987%2F04604260.pdf%3Farnumber%3D4604260&authDecision=-203.