錢 藝

(泰山學(xué)院信息科學(xué)技術(shù)學(xué)院 山東 泰安 271000)

?

通用可編程LDPC編碼器的設(shè)計

錢 藝

(泰山學(xué)院信息科學(xué)技術(shù)學(xué)院 山東 泰安 271000)

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

低密度奇偶校驗碼 多標(biāo)準(zhǔn) 多指令多數(shù)據(jù)流

0 引 言

在無線數(shù)字通信系統(tǒng)中，LDPC碼是一類重要的前向糾錯碼。它有逼近香農(nóng)限的良好性能，具有較高的數(shù)據(jù)吞吐量和靈活性[1]。因此，LDPC碼已被廣泛應(yīng)用于各種無線通信標(biāo)準(zhǔn)，如在寬帶無線接入領(lǐng)域的無線局域網(wǎng)(WLAN)和全球微波互聯(lián)接入(WiMAX)[2]中。

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

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

1 編碼算法的分析

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

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

(1)

(2)

Φ=-ET-1B+D

(3)

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

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

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

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

2 編碼器的結(jié)構(gòu)設(shè)計

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

圖1 處理器的多指令多數(shù)據(jù)流結(jié)構(gòu)

2.1 多指令多數(shù)據(jù)流結(jié)構(gòu)

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

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

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

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

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

控制單元協(xié)調(diào)處理單元組之間的處理任務(wù)，管理同步信號、外部握手信號等。

2.2 矩陣向量乘法器

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

圖2 矩陣向量乘法器的硬件結(jié)構(gòu)示意圖

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

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

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

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

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

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

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

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

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

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

圖4 矩陣向量乘法的時空任務(wù)圖

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

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

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

在之后的時鐘周期中，寄存器# 0和寄存器# 1交替被寫入相鄰組的數(shù)據(jù)，然后按照圖4所示的時序進行位拼接，并將拼接后的結(jié)果作為新的4位數(shù)據(jù)順序?qū)懭氡镜卮鎯ζ鳌?/p>

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

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

2.3 專用指令的設(shè)計

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

表1 部分專用指令

“SYN”指令用于使某幾個處理單元組處于協(xié)調(diào)一致的工作狀態(tài)。在某幾個處理單元組被SYN指令指定接收同步信號之后，它們將繼續(xù)執(zhí)行下一個相同的指令，或等待。

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

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

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

3 實驗結(jié)果與分析

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

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

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

該處理器已經(jīng)編程實現(xiàn)了WLAN的碼率為3/4、碼長為1 944的LDPC碼和WiMAX的碼率為1/2、碼長為2 304的LDPC碼。

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

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

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

4 結(jié) 語

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

[1] 陳為剛,曹艷,夏曉曉,等.面向衛(wèi)星導(dǎo)航系統(tǒng)的多進制LDPC碼的構(gòu)造[J].計算機應(yīng)用與軟件,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] 張小軍.基于專用指令集處理器架構(gòu)的AA-LDPC編譯碼器研究[D].東南大學(xué),2011.

[4] 趙明,李亮.在線可編程準(zhǔn)循環(huán)LDPC碼高速編碼器結(jié)構(gòu)[J].清華大學(xué)學(xué)報(自然科學(xué)版),2009(49):1041-1044.

[5] 張洋,王秀敏,陳豪威.基于FPGA的低密度奇偶校驗碼編碼器設(shè)計[J].浙江大學(xué)學(xué)報(工學(xué)版),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標(biāo)準(zhǔn)下QC-LDPC碼性能分析[J].計算機應(yīng)用與軟件,2014,31(11):151-154.

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

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

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

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

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

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

[14] 周紅月,師少飛,張強.基于傳輸觸發(fā)架構(gòu)的圖像降晰專用處理器設(shè)計[J].計算機應(yīng)用與軟件,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。山東省自然科學(xué)基金項目(ZR2013FL030)。錢藝，副教授，主研領(lǐng)域：嵌入式系統(tǒng)，超大規(guī)模集成電路設(shè)計。

TP3

A

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