通用可編程LDPC編碼器的設計

錢 藝

(泰山學院信息科學技術學院 山東 泰安 271000)

?

通用可編程LDPC編碼器的設計

錢 藝

(泰山學院信息科學技術學院 山東 泰安 271000)

基于靈活性和通用性的考慮，設計一種基于多指令、多數據流的可編程處理器結構，實現準循環低密度奇偶校驗碼(LDPC)的編碼算法。與傳統的LDPC編碼器相比，處理器采用數據位拼接方式實現矩陣與向量相乘，可以獲得較高的計算速度、易于芯片布局。目前已經用硬件描述語言在Xilinx ISE平臺可編程門陣列芯片XC2VP20上仿真實現了該處理器的架構，最大時鐘頻率為75 MHz。實驗結果表明，該結構適用于多標準的LDPC編碼器。

低密度奇偶校驗碼 多標準 多指令多數據流

0 引 言

在無線數字通信系統中，LDPC碼是一類重要的前向糾錯碼。它有逼近香農限的良好性能，具有較高的數據吞吐量和靈活性[1]。因此，LDPC碼已被廣泛應用于各種無線通信標準，如在寬帶無線接入領域的無線局域網(WLAN)和全球微波互聯接入(WiMAX)[2]中。

隨著LDPC碼的廣泛應用，多標準的通用LDPC編碼器也隨之具有廣泛的應用前景。編碼器的軟件實現是基于串行方法，靈活性好；但是不能適應高速應用場合，所以在大規模集成電路上實現高速的多標準通用LDPC編譯碼器則成為 LDPC 碼應用研究的熱點[3]。而半定制硬件實現編碼器通常采用并行計算結構，雖然有較高的速度，但是當通信標準、碼長、碼率變化時，因其結構固定而導致靈活性較差，與專用芯片相比性能相差甚遠，失去了通用的意義。因此，通常選擇專用指令集處理器(ASIP)來迎合這些需求，ASIP設計方法既有硬件實現的速度優勢，又具有依靠指令集編程實現的靈活性，可以在二者之間達到較好的折中。

在基于專用指令集處理器的架構設計方面，文獻[3]設計了一個針對中國數字地面多媒體廣播信道編解碼的編碼器，其核心計算組件是矩陣乘法器，有主處理器和從處理器，并分別為它們設計了專用指令。在文獻[4-6]中，則均采用單核處理器結構，并在其中設計了專門面向LDPC編碼算法的計算單元，從而提高了速度并降低了資源使用率，實現了有實際應用價值的并行編碼方案。而在本文準循環LDPC(QC-LDPC)編碼器的設計中，則是采用了多指令多數據流體系結構，使用了一個專用內存，來完成多標準的循環移位功能，編碼器可以實現并行計算，用較少的資源提高了速度和吞吐量。

1 編碼算法的分析

QC-LDPC碼基于集合結構，它降低了編碼的復雜性，更容易使用半并行的硬件結構來實現。一些通信標準例如WLAN、WiMAX和DTMB等都采用了QC-LDPC碼。準下三角矩陣的編碼算法是由Richarson和Unbanke提出的(RU算法)。該算法充分利用校驗矩陣的稀疏性，并且對奇偶校驗矩陣的行和列重新排列，從而得到類下三角H矩陣，從而可以減少線性編碼[7-8]的復雜性。為了對LDPC碼進行有效編碼，根據RU算法將矩陣H分解成A、B、C、D、E和T等循環置換矩陣。它們的基本塊的大小為g×g，膨脹系數是遠小于整數n的整數z。

假設校驗碼字V=(s，P1，P2)，其中S是信息元，P1、P2是校驗碼的第一和第二部分，則有：

(1)

(2)

Φ=-ET-1B+D

(3)

根據基本塊的劃分方法，s、P1、P2的長度分別為n-m、z、m-z。Ф作為已知參數的可以直接輸入到編碼器，不需要計算。

從硬件實現的角度分析該算法的編碼器，需要計算式(1)和式(2)。根據算法的分析[4]，這兩個方程的核心操作可以分為g×g矩陣乘以g維向量，和兩個g維向量的模2加。模2加法操作一般由異或電路實現。

根據矩陣理論引理：如果一個矩陣循環右移X位再乘以一個列向量，它相當于列向量向上移位X位。因此，循環移位器實現的是一個g×g矩陣和一個g維向量的乘法。如果循環移位器移位n位，這個移位的結果通常是在n個時鐘周期之后得到的。在文獻[5]，對數循環移位器可以在log2n個時鐘周期后輸出結果。這些循環器適合移位長度不變的情況。但是，即使在同一個通信標準中，g也往往有不同的值。例如，在IEEE802.16e標準中，g等于24，28，32,…而在IEEE802.11n標準中g是27，54，81,…如果在一個通用的編碼器中，移位器將被用于所有可能的g維向量的循環移位，那么這個移位器的數據長度應該是所有g中的最大值。這樣，當實際操作的g值較小時，會存在較大的資源浪費及芯片長延時，而且為了不影響后續操作的準確性和吞吐量，還需要額外地控制電路來處理最終結果中的冗余位或無效位。

為了實現通用性，本文結合了循環移位和專用指令設計兩種設計思路[9-14]，將循環移位設計為指令字符串操作，提取針對P1和P2的專用指令。這樣，該芯片的模塊可以與結構并行運行，從而提高了編碼器的資源利用率和運行速度。

2 編碼器的結構設計

信息元s的比特長度從數百乃至數千，只有并行結構可以提高編碼效率和靈活性。在本節中，多指令多數據流的并行體系結構設計如圖1所示。

圖1 處理器的多指令多數據流結構

2.1 多指令多數據流結構

該結構具有多個處理單元組，在圖1中有8個處理單元組。處理單元組內包括處理單元、指令譯碼器、矩陣向量乘法器、指令存儲器和本地存儲器。因此，不同的單元組可以根據不同的指令流進行不同的操作。另外，每個處理單元內有自己的本地存儲器，可以處理不同的數據流，從而實現空間并行，所以該體系結構通常用于特殊用途的計算。

每個處理單元都有自己的算術邏輯單元、寄存器和分支判斷模塊。它執行簡單的加法、減法、邏輯運算和分支等操作。在IEEE802.16e標準中，膨脹系數是4的倍數，而在IEEE802.11n標準中是27。所以，編碼器選擇4位作為一個處理單元的比特長度。

矩陣向量乘法器可以與算術邏輯運算單元同時并行運行，以此來提高系統的并行度、縮短程序運行的時間。它的詳細結構將在第2.2節中介紹。

指令存儲器和本地存儲器從存儲器中讀取程序和運算所需的數據。本地存儲器還要把自己的處理單元組的部分最終結果寫入存儲器。

指令譯碼器解碼來自指令存儲器的指令。對于一個局部指令，指令譯碼器將向處理單元發送控制信號。對于一個全局指令，指令譯碼器將向控制單元發送控制信號。

控制單元協調處理單元組之間的處理任務，管理同步信號、外部握手信號等。

2.2 矩陣向量乘法器

MVMs指令被指令譯碼單元解碼之后，控制模塊發出控制信號，使矩陣向量乘法器完成矩陣向量乘法。矩陣向量乘法器的硬件結構如圖2所示。

圖2 矩陣向量乘法器的硬件結構示意圖

在圖2中，g維向量可讀寫存儲器中的每個單元長度是4位，信息元s作為一個4 位/組的序列信息存儲在其中。

A塊矩陣的元素存儲在g×g矩陣存儲器中。矩陣元素的存儲地址是g×行+列。以IEEE802.16e標準中碼率1/2的基本矩陣為例，矩陣元素的存儲模式如圖3所示。

圖3 A矩陣元素在g×g矩陣存儲器中的存儲示意圖

寄存器#0、寄存器#1、寄存器# 2是三個暫時存放信息元s的4位寄存器。這三個寄存器和數據選擇器實現了數據轉換功能。部分最終數據存儲到本地存儲器中。

控制器讀取來自g×g矩陣的數據，然后確定數據選擇器連接方式。數據選擇器有4種位拼接的方式，假設N是本地存儲器中的部分信息碼的長度，則有：

如果mod(N，4)= 0，即N能被4整除，在寄存器# 0和寄存器# 1中的數據，可以直接輸出，不需要位拼接。

如果mod(N，4)= 1，那么在一個時鐘周期，{寄存器#0 [2:0]，寄存器# 1 [ 3 ] }被拼接起來，寫入本地存儲；并在下一個時鐘周期，{寄存器#1 [2:0]，寄存器# 0 [ 3 ] }寫入本地存儲器。這相當于向上移動1位數據。

如果mod(N，4)= 2，然后在一個時鐘周期，{寄存器# 0 [1:0]，寄存器# 1 [ 2 ] }寫入本地存儲；并在下一個時鐘周期，{寄存器# 1 [1:0]，寄存器# 0 [ 2 ] }寫入本地存儲器。這相當于向上移動數據2位。

如果mod(N，4)= 3，然后在一個時鐘周期，{寄存器# 0 [ 0 ]，寄存器# 1 [3:1] }寫入本地存儲；并在下一個時鐘周期，{寄存器# 1 [ 0 ]，寄存器# 0 [3:1] }寫入本地存儲器。這相當于向上移動數據3位。

矩陣向量乘法的時空任務圖如圖4所示。

圖4 矩陣向量乘法的時空任務圖

在第一個時鐘周期，把g維向量存儲器中地址為0的“數據0”寫入寄存器# 0和寄存器# 2。

在第二個時鐘周期，把g維向量存儲器中地址為1的“數據1”寫入寄存器#1。在緊接著下一個時鐘周期，按照前面所述的四種方式之一，寄存器# 0中的“數據0”和寄存器# 1中的“數據1”拼接成一個4位的新數據。這個數據作為“新數據0”寫入本地存儲器中地址為0的存儲單元。

在第三個時鐘周期，把g維向量存儲器中地址為1的“數據2”寫入寄存器#0。在緊接著下一個時鐘周期，按照前面所述的四種方式之一，寄存器# 0中的“數據2”和寄存器# 1中的“數據1”拼接成一個4位的新數據。這個數據作為“新數據1”寫入本地存儲器中地址為1的存儲單元。

在之后的時鐘周期中，寄存器# 0和寄存器# 1交替被寫入相鄰組的數據，然后按照圖4所示的時序進行位拼接，并將拼接后的結果作為新的4位數據順序寫入本地存儲器。

由于“數據0”已經在第一個時鐘周期時被寫入寄存器#2，因此，在最后一個時鐘周期，寄存器#2中的“數據0”與寄存器#0或者寄存器#1中的數據進行位拼接，得到最后一組4位新數據，并寫入本地存儲器中。

整個工作過程需要(N/4)+ 3個時鐘周期。

2.3 專用指令的設計

處理器的指令集設計采用精簡指令集結構，其中專用指令長度均為25位。部分主要的專用指令及功能描述如表1所示。

表1 部分專用指令

“SYN”指令用于使某幾個處理單元組處于協調一致的工作狀態。在某幾個處理單元組被SYN指令指定接收同步信號之后，它們將繼續執行下一個相同的指令，或等待。

表1中的其他指令均為多周期塊操作指令，能夠在連續的時鐘周期內不間斷地對多組數據進行處理，避免流水線沖突，提高硬件運行的效率，

“MVMs, N”指令完成矩陣與向量的乘法，N是基本塊的行值或列值?！癘UTS N”指令輸出長度為N的碼字?！癤ORS”指令完成異或操作，即兩個g維向量的模2加運算。這三條指令是專用于實現文中第1節所述的式(1)和式(2)的運算。

“Setmrc_pe_EM”和“Setmrc_EM_pe”是存儲器和指定的處理單元組中的本地存儲器進行數據存取的指令，是對每個處理單元組編程時使用。當發生存儲器的讀寫沖突時，按照處理單元組的位號次序排序讀寫。

3 實驗結果與分析

目前，已在XILINX公司的XC2VP20芯片上完成了處理器的功能仿真，使用了8個處理單元組。最大時鐘頻率是75 MHz。該處理器可以并行執行8條指令。在XC2VP20芯片中占用了5 700個邏輯資源和8 000 bits的RAMs。

由于時鐘頻率是75 MHz，可以并行執行8條指令，編碼數據是4位/組，所以，其理論吞吐量為2 400 Mbit/s。

但是由于處理器在實際運行中不能實現完全并行運行，以及實驗尚在初步階段，所以實際吞吐量只是接近于1 000 Mbit/s。但是，這也反映出處理器的并行度還有很大的提升空間。

該處理器已經編程實現了WLAN的碼率為3/4、碼長為1 944的LDPC碼和WiMAX的碼率為1/2、碼長為2 304的LDPC碼。

與其他實現方式相比較，文獻[5]的實驗結果為共消耗7 641個邏輯資源和3 936 bits的RAMs，其吞吐率為752 Mbit/s，實現了WiM AX標準中碼率為1/2、碼長為2304的LDPC碼。其優點是采用了6個對數循環移位器完成編碼過程中的12組矩陣與向量乘法的并行運算，這樣可以降低資源消耗、提高吞吐率。但是該編碼器碼率和碼長是固定不變的，靈活性不足。

文獻[4]的實驗結果為共消耗3 352個邏輯資源和24 576 bits的RAMs，其吞吐率為1 164 Mbit/s，實現了WiMAX標準中碼率為5/6、碼長為2 304的LDPC碼。其優點是采用了類CPU的設計方法，使用2條專用指令實現任意的QC-LDPC編碼，可以實現多碼長多碼率編碼，但是該編碼器是單核結構，如果要達到本文的吞吐率，在不考慮指令間的數據冒險的情況下，則至少需要耗費2倍以上的芯片資源。

而本文提出的結構與上述兩種實現相比，一方面采用了MIMD結構的CPU設計方法，來提高編碼算法的并行度，設計規整，便于布局布線，減少了邏輯資源或RAMs；另一方面，使用了專用內存來完成多標準的矩陣向量乘法運算，把該運算從處理單元中獨立出來，進一步提高了處理單元的并行度，因而具有更高的吞吐率。在WiM AX標準下，可以對應于多碼長、多碼率，除此之外編碼器還可以實現WLAN通信標準，在這兩種標準下實現了接近于1 000 Mbit/s的編碼性能，可以滿足高速的通信要求。

4 結 語

本文研究了LDPC碼適用于WLAN和WiMAX的編碼算法的硬件設計方法。時鐘頻率、處理單元組的數目和處理單元組之間的并行度等都是影響吞吐量的因素，因此，處理器還有進一步提高吞吐量的潛力。實驗結果表明，該結構適用于QC-LDPC碼。此外，處理器還處于研究的初級階段，很多方面可以進一步優化，其性能將進一步提高。

[1] 陳為剛,曹艷,夏曉曉,等.面向衛星導航系統的多進制LDPC碼的構造[J].計算機應用與軟件,2016,33(4):108-110,115.

[2] Chandrasetty V A,Johnson S J,Lechner G.Memory-efficient quasi-cyclic spatially coupled low-density parity-check and repeat-accumulate codes[J].Communications Iet,2014,8(17):3179-3188.

[3] 張小軍.基于專用指令集處理器架構的AA-LDPC編譯碼器研究[D].東南大學,2011.

[4] 趙明,李亮.在線可編程準循環LDPC碼高速編碼器結構[J].清華大學學報(自然科學版),2009(49):1041-1044.

[5] 張洋,王秀敏,陳豪威.基于FPGA的低密度奇偶校驗碼編碼器設計[J].浙江大學學報(工學版),2011(45):1582-1586.

[6] Yuan R J,Bai B M.FPGA-based joint design of LDPC encoder and decoder[J].Journal of Electronics & Information Technology,2012,34(1):38-44.

[7] 李繁華,林基明.ITU-T G.hn標準下QC-LDPC碼性能分析[J].計算機應用與軟件,2014,31(11):151-154.

[8] 汪漢新,王芳,蘇開友,等.基于滑動矩形窗和準三對角線結構的QC-LDPC碼[J].計算機工程與應用,2014,50(17):186-190.

[9] 楊群,李笑天,何虎.面向Superscalar與VLIW混合架構處理器的調試器設計[J].計算機應用與軟件,2015,32(5):84-87,163.

[10] 丁陳飛,鄭啟龍,徐華葉,等.多簇超長指令字DSP復數運算的編譯優化[J].計算機應用與軟件,2015,32(2):14-17.

[11] 陸祎,卜國強.通用處理器加速器研究綜述[J].計算機應用與軟件,2013,30(8):4-8.

[12] 陳明敏,易清明,石敏.高速8位微處理器設計[J].計算機應用與軟件,2016,33(1):240-243.

[13] 杜勇,李秦華,陳峰揚,等.VLIW-Superscalar混合結構處理器分支預測結構設計[J].計算機應用與軟件,2014,31(8):25-27,78.

[14] 周紅月,師少飛,張強.基于傳輸觸發架構的圖像降晰專用處理器設計[J].計算機應用與軟件,2013,30(11):1-3,27.

DESIGNOFUNIVERSALPROGRAMMABLELDPCENCODER

Qian Yi
(SchoolofInformationScienceandTechnology,TaishanUniversity,Taian271000,Shandong,China)

Based on flexibility and versatility, a programmable processor architecture based on multiple instruction and multiple data streams is designed to realize the coding algorithm of quasi cyclic low density parity check codes (LDPC). Compared with the traditional LDPC encoder, the processor uses data bits mosaic method to achieve the matrix and vector multiplication, which can obtain a higher speed and chip layout. Currently processor architecture has been simulated in the ISE Field-Programmable Gate Array (FPGA) platform with Xilinx XC2VP20 chip. The maximum clock frequency is 75 MHz. The experimental results show that the proposed structure is suitable for Multi-standard LDPC encoder.

LDPC Multistandard MIMD

2016-10-26。山東省自然科學基金項目(ZR2013FL030)。錢藝，副教授，主研領域：嵌入式系統，超大規模集成電路設計。

TP3

A

10.3969/j.issn.1000-386x.2017.08.043