盧海芹，仰楓帆

(南京航空航天大學(xué)電子信息工程學(xué)院，江蘇南京 210016)

低密度奇偶校驗(yàn)(Low Density Parity－Check，LDPC)碼［1］最早于1962年由 R.Gallager提出，其實(shí)質(zhì)是一類具有稀疏校檢矩陣的線性分組碼。1996年，Mackay、Neal等人證明了 LDPC碼是一種具有逼近Shannon極限性能的好碼［2］，但其隨機(jī)構(gòu)成特性又給編譯碼的實(shí)現(xiàn)帶來了較大復(fù)雜度，在碼長較長時(shí)，這種復(fù)雜度是硬件設(shè)計(jì)所難以接受的。準(zhǔn)循環(huán)低密度奇偶校檢(Quasi－Cyclic Low Density Parity－Check，QCLDPC)碼［3］的出現(xiàn)，因其準(zhǔn)循環(huán)特性，使得以更低的復(fù)雜度實(shí)現(xiàn)編譯碼成為可能。同時(shí)，QC－LDPC碼在誤碼率上和隨機(jī)LDPC碼具有同樣優(yōu)秀的性能，因此，QC－LDPC碼成為眾多標(biāo)準(zhǔn)采用的信道編碼方案。QC－LDPC碼譯碼器設(shè)計(jì)初期多采用部分并行結(jié)構(gòu)［4］，此后出現(xiàn)了分層譯碼結(jié)構(gòu)［5］。分層譯碼結(jié)構(gòu)擁有更快的譯碼速度，更好的性能和更簡單的硬件結(jié)構(gòu)，成為QC－LDPC譯碼器的主流結(jié)構(gòu)。但是，分層譯碼要求QC－LDPC碼的校驗(yàn)矩陣每個分層的列重≤1。本文中采用有限域乘群構(gòu)造的QC－LDPC碼的校驗(yàn)矩陣［6］每個分層的列重恰好等于1，滿足分層譯碼的要求。為進(jìn)一步降低硬件復(fù)雜度，采用歸一化最小和算法(NMSA)，整個譯碼過程中只包括比較、移位和加減運(yùn)算，優(yōu)化了硬件結(jié)構(gòu)，降低了硬件實(shí)現(xiàn)復(fù)雜度。

1 基于有限域乘群的QC－LDPC碼的構(gòu)造

設(shè)q是任意質(zhì)數(shù)或質(zhì)數(shù)的冪，則整數(shù)集{0，1，2，…，q－1}在模 q加法和模 q乘法下構(gòu)成有限域GF(q)。GF(q)的q－1個非0元素構(gòu)成GF(q)在乘法操作下的乘法群，簡稱乘群。對于其中的每個非0元素i，定義M位置矢量z(i)為GF(2)上的(q－1)維數(shù)組 z(i)=(z1，z2，…，zq－1)，其第 i個分量 zi=1，所有其余q－2個分量均為0。GF(q)的0元素對應(yīng)的M位置矢量定義為q－1維全0數(shù)組。顯然，GF(q)中的任意元素i+2的M位置矢量z(i+2)可由i的位置矢量z(i)循環(huán)右移2位得到。

構(gòu)造QC－LDPC碼校驗(yàn)矩陣的步驟如下:

步驟1 由本原元確定構(gòu)成有限域GF(q)的全部元素。

設(shè)本原元 α，則 α－∞≡0，α0=1，α，…，αq－2構(gòu)成GF(q)的所有元素。根據(jù)預(yù)期構(gòu)造校驗(yàn)矩陣的大小選擇合適的有限域GF(q)。

步驟2 構(gòu)成在GF(q)上的(q－1)×(q－1)的基矩陣W(1)。

矩陣W(1)具有以下結(jié)構(gòu)特性:(1)任意兩行或者兩列在所有位置上的元素都不相同。(2)任一行或一列中的條目是GF(q)中不同元素。(3)每行或列中有且僅有一個0元素，第i行(1≤i≤q－2)的0元素位于第i行第(q－1－i)mod(q－1)列。(4)矩陣中每一行是上一行的左循環(huán)移位，第一行是最后一行的左循環(huán)移位。

步驟3 矩陣W(1)先后經(jīng)乘對折垂直擴(kuò)展，乘對折水平擴(kuò)展得到矩陣H(1)。

(1)乘對折垂直擴(kuò)展。對于W(1)中的每行wi(0≤i≤q－2)依次與GF(q)中的(q－1)個非0元素α0，α，…，αq－2相乘，得到矩陣 W(1)i

上述W(1)中的wi行垂直擴(kuò)展為一個GF(q)上的(q－1)×(q－1)矩陣，該矩陣可以看作是wi行的(q－1)乘對折垂直擴(kuò)展，故稱W(i1)為wi行的(q－1)乘對折垂直擴(kuò)展。

(2)乘對折水平擴(kuò)展。對于矩陣W(i1)(0≤i≤q－2)的每個元素，利用其M位置矢量來代替，得到一個GF(q)上的(q－1)×(q－1)2的矩陣B(i1)

其中，Aij是由矩陣W(1)i的第j列元素的M位置矢量組成。

把 B(1)0，B(1)1，…，B(1)q－2作為行向量構(gòu)成(q－1)×(q－1)的矩陣H(1)

H(1)具有以下結(jié)構(gòu)特性:(1)A0，0，A1，q－2，A2，q－3，…，Aq－2，1均是(q－1)×(q－1)的0 矩陣，其他子矩陣都是同維數(shù)的循環(huán)置換矩陣。(2)H(1)的每一行或每一列中有且僅有一個0矩陣。(3)H(1)子矩陣的每一行是上一行左循環(huán)移位的結(jié)果，第一行是最后一行的左循環(huán)移位。(4)H(1)是在 GF(2)上的(q－1)2×(q－1)2矩陣，行重和列重都是q－2。

步驟4 構(gòu)造QC－LDPC的校驗(yàn)矩陣Hqc。

構(gòu)造行重為 λ，列重為 ρ(1≤λ，ρ≤q－1)的規(guī)則QC－LDPC碼校驗(yàn)矩陣Hqc的步驟:(1)從0～q－2之間選擇λ和ρ個不相等的隨機(jī)數(shù)組成隨機(jī)坐標(biāo)對。(2)從H(1)中選取相應(yīng)的元素作為基矩陣。(3)將基矩陣填充到Hqc時(shí)，選取的λ×ρ個循環(huán)移位矩陣之間的相對位置保持不變。

采用反正法來證明所構(gòu)造的QC－LDPC碼對應(yīng)的Tanner圖中不存在長為4的環(huán)。

證明 假設(shè)矩陣H(1)不滿足RC約束，即H(1)中在一個矩形的 4 個角存在 4 個 1 分量。設(shè) hi，j，hi，k，hl，j，hl，k是上述矩形 4 個角的 4 個 1 分量，其中 hi，j和hl，j在矩陣的同一列 j，hi，k和 hl，k在同一列 k;hi，j和 hi，k在同一行 i，hl，j和 hl，k在同一行 l。由于 W(1)滿足每行有且僅有一個零矢量以及H(1)是一個循環(huán)置換矩陣的陣列，因此，這些1分量位于4個不同的循環(huán)置換矩陣中，不妨設(shè)矩陣 A，B，C 和 D，其分別包含 hi，j，hi，k，hl，j和hl，k。則A和C在同一列，B和D在同一列;A和B在同一行，C和D在同一行。根據(jù)W(1)的(q－1)重相乘對折散布性質(zhì)，有 hi，j=hl，j=1 和 hi，k=hl，k=1，這就意味著在W(1)中存在兩行ws和wt，使得 αcws和 αdwt有兩個位置是相同的元素。這與W(1)的結(jié)構(gòu)特性1相矛盾，故假設(shè)不成立。結(jié)論得證。

圖1給出了該方法構(gòu)造的規(guī)則(3 060，765，3，12)QC－LDPC碼校驗(yàn)矩陣的結(jié)構(gòu)，其中該矩陣的基矩陣是一個3×12矩陣，每個子矩陣的大小為255×255，矩陣的列重為3，行重為12，碼率為，碼長為3 060。

圖1 基于有限域乘群構(gòu)造的規(guī)則QC－LDPC碼校驗(yàn)矩陣的結(jié)構(gòu)圖

2 QC－LDPC碼的譯碼方案

2.1 LDPC碼傳統(tǒng)譯碼算法

置信度傳播(Belief Propagation，BP)［7］譯碼算法是傳統(tǒng)的LDPC碼譯碼算法，對它進(jìn)行改進(jìn)又出現(xiàn)了最小和算法(Min Sum Algorithm，MSA)，歸一化最小和算法(Normalization Min Sum Algorithm，NMSA)等。這類算法因其通過校驗(yàn)節(jié)點(diǎn)更新和變量節(jié)點(diǎn)更新兩個步驟完成一次迭代譯碼，被稱為2項(xiàng)置信傳播(Two Phase Message Passing，TPMP)算法。TPMP算法在一次迭代譯碼過程中，全部的校驗(yàn)節(jié)點(diǎn)更新結(jié)束后，所有的變量節(jié)點(diǎn)才開始更新，即在一次迭代過程中，所有信息只更新一次。所以，該算法的收斂速度較慢，譯碼延遲較大。

2.2 并行分層置信傳播譯碼算法

并行分層置信傳播譯碼算法的出現(xiàn)改變了TPMP算法的譯碼方式，它是將校驗(yàn)矩陣按行或列分成幾個分層，分別進(jìn)行更新。在一次迭代譯碼過程中，首先對第一分層的所有校驗(yàn)節(jié)點(diǎn)以及相關(guān)變量節(jié)點(diǎn)進(jìn)行更新，然后逐層進(jìn)行信息更新。因此，后面分層更新時(shí)要利用到前面分層已更新的信息，這樣變量節(jié)點(diǎn)在一次迭代過程中得到多次更新，大幅加快了譯碼收斂速度，提高了譯碼性能。但分層譯碼算法能分層進(jìn)行變量節(jié)點(diǎn)更新的要求是:校驗(yàn)矩陣每個分層的列重不大于1。按上述方法構(gòu)造的校驗(yàn)矩陣每個分層的列重恰好等于1。

假設(shè)高斯白噪聲信道的噪聲方差為σ2，接收到的信號序列為y，校驗(yàn)矩陣的大小為M×N。迭代過程中，變量節(jié)點(diǎn)信息用 Zn，m表示，校驗(yàn)節(jié)點(diǎn)信息用 Lm，n表示，后驗(yàn)概率信息用Fn表示。采用BPSK調(diào)制方式，分層譯碼算法的譯碼過程簡述如下:

步驟1 初始化

步驟2 迭代更新過程(第l次迭代，第k層)

步驟3 譯碼判決

其中，F(xiàn)(l，k)n為最后一個分層的輸出。若第k層不是最后一個分層，則進(jìn)入第l次迭代的第k+1層的譯碼過程。

步驟4 結(jié)果校檢。若d^滿足H×d^T=0或到達(dá)了最大迭代次數(shù)，則譯碼停止，否則重復(fù)步驟(2)和步驟(3)繼續(xù)進(jìn)行迭代譯碼，直到滿足結(jié)束條件。

3 分層譯碼器結(jié)構(gòu)設(shè)計(jì)

對構(gòu)造的(3 060，765，3，12)QC －LDPC 碼進(jìn)行分層譯碼器的設(shè)計(jì)，按照校驗(yàn)矩陣的結(jié)構(gòu)，將其按行分為3層，這樣每個子塊的列重恰好等于1。采用層內(nèi)并行，層間串行的分層譯碼算法，每個分層包含255個校驗(yàn)節(jié)點(diǎn)，因此，需要 255個校驗(yàn)節(jié)點(diǎn)處理模塊(PCNPM)同時(shí)工作，即并行度為255。在硬件設(shè)計(jì)時(shí)，將修正因子α設(shè)為0.75，這樣只需要簡單的帶符號右移和加法運(yùn)算即可做到數(shù)據(jù)的修正。對譯碼器的數(shù)據(jù)進(jìn)行7 bit量化，在計(jì)算過程中，若出現(xiàn)了數(shù)據(jù)溢出，則采用截?cái)喾▉硖幚硪绯鰯?shù)據(jù)，這樣的處理方法對譯碼性能帶來約0.1 dB的損失，但大幅降低了設(shè)計(jì)復(fù)雜度，節(jié)約了硬件資源。

圖2 分層譯碼器的硬件結(jié)構(gòu)設(shè)計(jì)

3.1 輸入緩沖模塊

輸入緩沖模塊主要有以下兩個功能:(1)從信道接收譯碼數(shù)據(jù)，且保證數(shù)據(jù)不丟失。(2)將接收到的譯碼數(shù)據(jù)傳遞給變量節(jié)點(diǎn)信息存儲模塊，完成迭代譯碼過程中的部分初始化工作。

3.2 信息存儲模塊

信息存儲模塊包括兩部分:(1)校驗(yàn)節(jié)點(diǎn)信息存儲模塊Rmem，因?yàn)橛?55個校驗(yàn)節(jié)點(diǎn)處理模塊同時(shí)工作，因此需要255個Rmem雙端口RAM來存儲校驗(yàn)節(jié)點(diǎn)更新數(shù)據(jù)，每個RAM的存儲容量為3×7×12=252 bit。(2)變量節(jié)點(diǎn)信息存儲模塊Lmem，用來存儲后驗(yàn)概率信息Fn。基于校驗(yàn)矩陣結(jié)構(gòu)，將3 060個后驗(yàn)概率信息分為12塊來存儲，每塊存儲255個數(shù)據(jù)，即每塊RAM的存儲容量為256×7 bit。

3.3 校驗(yàn)節(jié)點(diǎn)處理模塊

該模塊是整個譯碼器的核心部分，完成迭代譯碼過程中的校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)的信息更新。在更新結(jié)構(gòu)上，采用分層間串行，分層內(nèi)并行的處理機(jī)制。該部分的結(jié)構(gòu)如圖3所示。

圖3 校驗(yàn)節(jié)點(diǎn)處理模塊結(jié)構(gòu)圖

如圖3所示，該模塊分為6部分:(1)減法器，后驗(yàn)概率信息Fn和校驗(yàn)節(jié)點(diǎn)信息Lm，n通過減法器后更新變量節(jié)點(diǎn)信息Zn，m。(2)數(shù)據(jù)比較器1，尋找與一個校驗(yàn)節(jié)點(diǎn)連接的12個變量節(jié)點(diǎn)中變量節(jié)點(diǎn)信息絕對值最小和次最小的數(shù)據(jù)，并記錄這組數(shù)據(jù)的符號。(3)FIFO和最小值、次最小值、符號寄存器，將接收到的數(shù)據(jù)與最小值寄存器和次最小值寄存器中的數(shù)據(jù)進(jìn)行比較，并更新最小值和次最小值寄存器;將數(shù)據(jù)的符號位與符號寄存器的值做異或運(yùn)算，更新符號寄存器，之后將該時(shí)刻輸入的數(shù)據(jù)存入FIFO。(4)數(shù)據(jù)比較器2，將從FIFO中讀出的數(shù)據(jù)與最小值和次最小值寄存器中的數(shù)值進(jìn)行比較，然后做出選擇。(5)校正因子，將從數(shù)據(jù)比較器2中輸出的數(shù)據(jù)做帶符號位的右移一位和右移兩位，再求和，得到修正數(shù)據(jù)。(6)加法器，將從校正因子部分輸出的數(shù)據(jù)和從FIFO中讀出的變量節(jié)點(diǎn)信息通過加法器相加，得到變量節(jié)點(diǎn)后驗(yàn)概率信息Fn。

3.4 控制模塊

該模塊分為兩部分:(1)地址控制模塊，該模塊包含一個存儲著校驗(yàn)矩陣所有子塊位置和偏移量信息的ROM，從中讀取信息來產(chǎn)生變量、校驗(yàn)節(jié)點(diǎn)存儲模塊的讀地址和寫地址。(2)狀態(tài)控制模塊，設(shè)置整個譯碼過程的狀態(tài)機(jī)，控制每個模塊的工作狀態(tài)。

3.5 信息校驗(yàn)?zāi)K

在迭代譯碼的過程中，每個分層更新結(jié)束之后，對所有更新的變量節(jié)點(diǎn)進(jìn)行校驗(yàn)，若所有變量節(jié)點(diǎn)滿足校驗(yàn)方程，就無需進(jìn)行下面分層的譯碼，此次迭代結(jié)束;否則繼續(xù)進(jìn)行迭代譯碼，直到達(dá)到最大迭代次數(shù)。

3.6 輸出緩沖模塊

暫存迭代譯碼過程中產(chǎn)生的判決結(jié)果，并在譯碼結(jié)束后向外部輸出數(shù)據(jù)。

4 FPGA綜合結(jié)果及分析

在實(shí)現(xiàn)譯碼器的過程中，采用Altera公司StratixII系列的器件EP2S60F484C4，綜合結(jié)果如表1所示。

表1 QC－LDPC碼譯碼器綜合結(jié)果

吞吐率和糾錯能力是衡量一個譯碼器性能的兩個主要指標(biāo)。其中吞吐率用式(10)進(jìn)行評估

其中，f是譯碼器的工作頻率;N是碼長;R是碼率;dini表示譯碼器的初始化時(shí)延;dpro表示譯碼器的譯碼時(shí)延。

在譯碼過程中，首先從輸入緩沖模塊讀出數(shù)據(jù)對變量節(jié)點(diǎn)信息存儲模塊進(jìn)行初始化，共需128個時(shí)鐘周期。每個分層進(jìn)行校驗(yàn)、變量節(jié)點(diǎn)信息更新需要16個時(shí)鐘周期，則此迭代過程共需要花費(fèi)3×5×16+128×5=880個時(shí)鐘周期。因此，譯碼器的吞吐率可達(dá)(35.38 ×3 060 ×0.75)/880=92.27 Mbit·s－1。

將構(gòu)造的(3 060，765，3，12)QC －LDPC 碼分別采用分層結(jié)構(gòu)和未分層結(jié)構(gòu)，在NMSA基礎(chǔ)上進(jìn)行的性能仿真如圖4所示。從圖中可看出，BER=10－6時(shí)，分層結(jié)構(gòu)比未分層結(jié)構(gòu)有約0.8 dB的性能增益。

圖4 分層結(jié)構(gòu)與未分層結(jié)構(gòu)的性能比較圖

5 結(jié)束語

本文基于有限域乘群構(gòu)造了Tanner圖中無4環(huán)的QC－LDPC碼，隨后基于構(gòu)造的QC－LDPC碼，采用分層譯碼算法設(shè)計(jì)了分層譯碼器，分層結(jié)構(gòu)較未分層結(jié)構(gòu)有更好的收斂性。最后采用 Altera公司StratixII系列的器件，將分層譯碼器在FPGA上得以實(shí)現(xiàn)，并得到較高的譯碼吞吐率。

［1］Gallager R G.Low － density parity－check codes［J］.IRE Transactions on Information Theory，1962，8(1):21 －28.

［2］Mackay D JC，Neal R M.Near shannon limit performance of low density parity check codes ［J］.Electronics Letters，1996，32(18):1645 －1646.

［3］Fossorier M P C.Quasicyclic low －density parity－check codes from circulant permutation matrices［J］.IEEE Transactions on Information Theory，2004，50(8):1788 －1793.

［4］Karkooti M，Cavallaro J R.Semi－ parallel reconfigurable architectures for real－ time LDPC decoding［C］.International Conference on Information Technology:Coding and Computing，ITCC 2004，IEEE，2004(1):579 －585.

［5］Mansour M M，Shanbhag N R.High － throughput LDPC decoders［J］.IEEE Transactions on Very Large Scale Integration(VLSI)Systems，2003，11(6):976 －996.

［6］賀鶴云.LDPC碼基礎(chǔ)與應(yīng)用［M］.北京:人民郵電出版社，2009.

［7］Mackay D J C.Good error－ correcting codes based on very sparse matrices［J］.IEEE Transactions on Information Theory，1999，45(2):399－431.