諸 葉，張福洪，方洪燦

(杭州電子科技大學 通信工程學院，浙江 杭州310018)

低密度奇偶校驗(LDPC)碼是 Gallager于 1962年提出的一種基于稀疏矩陣的線性分組碼，具有能夠逼近香農極限的優(yōu)良特性。基于Q矩陣的準規(guī)則LDPC碼由一組循環(huán)正交Q矩陣構成，能根據給定的碼率和碼長設計校驗矩陣H，使Q矩陣LDPC碼的碼長和碼率的取值具有更大的靈活性。為了符合實際情況中的可變碼率、可變碼長，本文設計了一種直接基于準規(guī)則 Q矩陣，碼率分別為 1/2、5/8，碼長分別為短碼中的192、40。根據具體要求，實現(xiàn)了變碼率的LDPC編碼。本文只實現(xiàn)了針對性的可變，沒有實現(xiàn)任意可變。

1 編碼原理[1]

1.1 Q矩陣的性質

Q矩陣主要的性質：(1)矢量表示性；(2)循環(huán)移位性；(3)相互正交性；(4)定位性。

1.1.1 矩陣的矢量表示

通常將一個n×n階的Q矩陣用一個n維矢量來表示，稱為Q矢量 。Q矢量與Q矩陣的對應關系是，矢量中每一個元素的位置表示矩陣中“1”元素所在列的位置，矢量中每一個元素的值表示矩陣中“1”元素所在行的位置，按從上到下的順序計數(shù)。例如，用皇后算法[4]搜索一個n=5的Q矩陣：

Q15的上標表示矩陣的維數(shù)，下標表示在維數(shù)為 5的Q矩陣的集合中任取一個矩陣作為第一個矩陣。Q15也可以表示成含有 5 個元素的矢量 Q15=（1，3，5，2，4），其中3表示Q矩陣中第3行第2列的元素為1。

1.1.2 矩陣的循環(huán)移位性

設A表示Q矩陣的集合，S表示循環(huán)移位(包括左移 L、右移 R、上移 U、下移 D)算子，Si(I：i=1，2，…，n）表示循環(huán)移位i次。當n≥5時，循環(huán)移位性可以這樣描述：如果一個矩陣Q屬于A，則SiQ屬于A。同理Q矢量也可進行循環(huán)移位，但只能進行左移和右移，如S1LQ15=S1L(1，3，5，2，4)=Q25=(3，5，2，4，1)。

1.2 基于依據H矩陣的編碼方法

準規(guī)則Q矩陣LDPC碼奇偶校驗矩陣H分解為2個子矩陣，即 H=[HpHd]。 其中，Hp是（N-K）×(N-K)階方陣，稱為校驗位矩陣，是雙對角線形式的下三角矩陣;Hd是(N-K)×K階矩陣，稱為信息位矩陣，由 Q矩陣排列組合而成。

1.2.1 Q矩陣構造Hd矩陣的算法

Hd是由n維Q矩陣所構成的。算法內容為：第一行和第一列是相同的Q1矩陣，剩下的各行各列不能再出現(xiàn)Q1矩陣，第2行是Q1矩陣2的倍數(shù)次循環(huán)左移，即Q2，Q4，Q6，Q8，…，第 3 行是 Q1 矩陣 3 的倍數(shù)次循環(huán)左移，即 Q3，Q6，Q9，Q12，…，如此下去可以構造不含 4線循環(huán)的H矩陣。但這個方法有其缺陷。因為每個n維Q矢量，當它左移n+1次時，就會出現(xiàn)Q1矩陣，而算法又明確說明只能在第一行和第一列出現(xiàn)Q1矩陣，剩下的各行各列不能再出現(xiàn)Q1矩陣了。于是本文最終選擇的構造法為：

簡單的平移，不僅解決了這個問題，而且占用的FPGA資源更少。本文構造的H矩陣與隨機法構造的H矩陣誤碼性能如圖1所示，其中輸入為200 000 bit。

圖1 LDPC(40，20)的誤碼率

1.2.2 LDPC碼編碼的算法

根據H矩陣的結構特點把其對應的碼字C分解為對應的校驗序列 Cp和信息序列 Cd，即有 C=[Cp|Cd]。因為HCT=0，可得 Hp(Cp)T+Hd(Cd)T=0。 給定信息序列 Cd={dj}，其校驗位矢量Cp={pi}，可得：

根據式(1)、式(2)可得算法流程：實現(xiàn)（N，K）LDPC 編碼，根據信息位矩陣存儲的1的列號，也就是完成校驗位計算所需要的信息位的序號，找出相應的信息位進行異或運算。計算第一個校驗位時，只需要將對應的信息位進行異或；計算剩下的校驗位時，需要將對應信息位和上一個校驗位的值進行異或運算。而根據異或運算的特點：相同則為0，相異則為1，校驗位的計算，可以修改一下算法。因為，與對應的信息位進行異或的是Hd中的1，所以，異或運算相當于對信息位進行取反運算。修改后的算法描述為：對應的信息位進行取反運算，然后把結果進行異或運算。第一位的校驗位就是一次異或運算的結果，計算剩下的校驗位時，需要將對應信息位和上一個校驗位的值進行異或運算。

2 LDPC碼編碼設計

2.1 LDPC碼的Hd矩陣[2]

編碼設計就涉及到H矩陣的選取。為了實現(xiàn)碼率分別為1/2、5/8，碼長分別為短碼中的192、40。選取了 n=16的 Q矩陣構成碼長為 192的Hd矩陣，n=5的 Q矩陣構成碼長為40的Hd矩陣。為了便于描述，碼率為1/2，碼長為40的Hd矩陣如圖2。同樣，可以改變Q矩陣的維數(shù)來構造實際需要的 Hd矩陣。 如圖2，Q15=（5，3，1，4，2），循環(huán)左移 4 次， 可得 到 4 矢 量 Q25，Q35，Q45，Q55分別為(3，1，4，2，5)， (1，4，2，5，3)， (4，2，5，3，1)， (2，5，3，1，4)。同樣，當構成碼長為 192的 Hd矩陣時，Q116=(15，13，11，9，7，5，3，1，16，14，12，10，8，6，4，2)循環(huán)左移 15 次，可得 15 個 矢 量 Q216，Q316，Q416，Q516，Q616，Q716，Q85，Q916，Q1016，Q1116，Q1216，Q1316，Q1416，Q1516，Q1616。 根據 16 個矢量構造碼率為1/2，碼長為192的Hd矩陣。當要改變碼率時，根據碼率的定義及Hd矩陣的性質，選取部分Hd矩陣進行編碼運算，就能實現(xiàn)變碼率的LDPC編碼。

圖2 碼長為40的Hd矩陣

2.2 用Verilog實現(xiàn)LDPC編碼

為了描述方便，功能將逐個用Verilog實現(xiàn)。首先實現(xiàn)定碼率、碼長的LDPC編碼，然后實現(xiàn)可變碼率、碼長的LDPC編碼。

2.2.1 定碼率碼長編碼

根據本文的算法，先進行取反運算，第一位的校驗位對應的信息位是 2，6，10，19，則 result[0]=(～data_reg[2])^(～data_reg[9])^(～data_reg[12])^(～data_reg[19])，其 中data_reg為輸入信息位，result為暫存寄存器。因為第一位的校驗位不需要與剩下的校驗位進行異或運算，因此check_bit[0]=result[0]。check_bit為保存校驗位的寄存器。當計算下一個校驗位時，首先校驗位對應的信息位分別是 4、8、12、16，則相應的編程語言為 result[1]=(～data_reg[4])^(～data_reg[8])^(～data_reg[12])^(～data_reg[16])； 然后根據算法步驟，check_bit[1]=check_bit[0]^result[1]；最后剩下18位校驗位，根據第2位校驗位的計算方法，依次計算，將結果保存在check_bit。在通過對對應的信息位進行取反、異或運算時，Hd矩陣中對應的信息位有如下規(guī)律： 從 1～5行對應的信息位為 2，6，10，19；4，8，12，16；1，5，14，18；3，7，11，15；0，9，13，17。 而6～10行對應的信息位為仍然是這些數(shù)字，只是相應行的對應信息位發(fā)生變化。剩下的 11～15，16～20行都是這個規(guī)律。Verilog編程可以充分利用這個規(guī)律節(jié)約資源。

2.2.2 變碼率碼長編碼

變碼率涉及到碼長與信息位數(shù)。本文提出的變碼率基于變信息位數(shù)，碼長不變。在保持碼長40的情況下，當碼率為 5/8時，信息位就變成 25了，Hd成了 15×25的矩陣。與不變的相比，第一位的校驗位對應的信息位分別是 2，6，10，19，23，多了 1 位。 方法不變，result[0]=(～data_reg[2])^(～data_reg[9])^(～data_reg[12])^(～data_reg[19])^(～data_reg[23])。因為校驗位的減少，只需要計算1～15位的相應信息位。

同樣，在碼率不變的情況下，變碼長。如在保持碼率1/2不變的情況下，從40換成192時，仍舊需要改變Hd矩陣。由2.1節(jié)所述的16個Q子矩陣組成Hd矩陣。

總之，在具體應用時，通過仿真取一個相對性能好的Q矩陣，根據要求選取碼率與碼長。

3 LDPC碼編碼實現(xiàn)

3.1 原Q矩陣與改進Q矩陣的比較

3.1.1 Verilog程序對比

原Q矩陣實現(xiàn)碼率 1/2，碼長40，是通過狀態(tài)機實現(xiàn)。狀態(tài)的個數(shù)是根據校驗位的個數(shù)來定的。20個校驗位需要21個狀態(tài)，其中1個是空閑狀態(tài)。原Q矩陣實現(xiàn)校驗位的Verilog程序如下：

改進Q矩陣的實現(xiàn)，只需要一個行號row做判斷。由于其循環(huán)性，只需要5個狀態(tài)。改進Q矩陣實現(xiàn)校驗位其中1個狀態(tài)的Verilog程序如下：

3.1.2 FPGA的占用資源對比

通過軟件綜合后的結果，資源中Total registers的數(shù)量從 123個降到了93個，Total logic elements的數(shù)量略微減少。這說明改進的算法效果明顯。

3.2 變碼率LDPC編碼實現(xiàn)

數(shù)據由data_in輸入，enable控制數(shù)據編碼的開始。sp_change是碼率選擇標志，1表示碼率1/2，0表示碼率5/8，data_out輸出。整個模塊如圖3。

3.3 仿真結果

check_reg[19:0]是校驗位的存儲器。如圖4，是碼率1/2的一次編碼完成。data_in是[0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1]，低位在前，高位在后，轉換成整型677204，從data_out[39:20]輸出。check_reg一次編碼完成后，為[0 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0]，低位在前，高位在后，轉換成整型301932，從data_out[19:0]輸出。輸出結果為710100163436。

本文利用FPGA實現(xiàn)了基于Q矩陣可變碼率、碼長的LDPC碼的設計與實現(xiàn)。Quartus II軟件環(huán)境下對LDPC編碼器進行仿真，使用CycloneII系列EP2CS35F484I8芯片，對碼長為40的碼字進行編碼?；痉暇幋a器設計的要求。該編碼器結構是一種通用的設計方案，可以應用于各種不同的LDPC編碼中。另外通過優(yōu)化時序和編碼結構，可以進一步提高本編碼器的編碼速度。

圖4 LDPC編碼仿真結果

[1]彭立，朱光喜.基于 Q矩陣的 LDPC碼編碼器設計[J].電子學報，2005，33(10)：1734-1740.

[2]赫凌俊.低密度奇偶校驗碼編譯碼器的FPGA實現(xiàn)[碩士學位論文].南京：南京理工大學，2008.

[3]姜慧源，田斌，易克初.準規(guī)則Q矩陣 LDPC碼編碼器設計[J].電視技術，2007，31(11)：19-21.

[4]SOSIC R，GU J.Efficient local search with conflict minimization：a case study of the N-queens problem[J].IEEE Trans Knowledge and Data Eng，1994，6(5)：661-668.

[5]羅杰.Verilog HDL與數(shù)字ASIC設計基礎[M].武漢：華中科技大學出版社，2008，3.