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

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

1 引言

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

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

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

2 LU分解編碼算法及其改進

2.1 LU分解編碼算法

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

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

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

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

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

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

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

1）計算向量 X：XT=VAST；

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

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

2.2 改進的LU分解編碼算法

圖1 H經(jīng)行列交換后的結構示意圖

圖2 改進的LU分解編碼算法示意圖

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

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

改進的LU分解編碼算法步驟為：

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

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

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

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

2.3 LU分解

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

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

3 CMMB標準的LU分解編碼器

3.1 CMMB標準中的LDPC碼

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

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

3.2 CMMB標準的LDPC編碼器

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

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

圖3 改進LU分解編碼器的結構框圖

3.3 存儲器耗用分析

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

4 實驗分析

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

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

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

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

5 小結

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

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

[2]康亮，楊波，沈萌.符合CMMB標準的LDPC解碼器設計[J].電視技術，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.