基于FPGA有限域構造的QC-LDPC分層譯碼器設計

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

1 基于有限域乘群的QC-LDPC碼的構造

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

構造QC—LDPC碼校驗矩陣的步驟如下：

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

設本原元α，則

構成GF(q)的所有元素。根據(jù)預期構造校驗矩陣的大小選擇合適的有限域GF(q)。

步驟2 構成在GF(q)上的(q-1)×(q-1)的基矩陣W(1)。

矩陣W(1)具有以下結構特性：(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)乘對折垂直擴展，乘對折水平擴展得到矩陣H(1)。

H(1)具有以下結構特性：(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)移位的結果，第一行是最后一行的左循環(huán)移位。(4)H(1)是在GF(2)上的(q-1)2×(q-1)2矩陣，行重和列重都是q-2。

步驟4 構造QC—LDPC的校驗矩陣Hqc。

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

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

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

2 QC-LDPC碼的譯碼方案

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

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

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

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

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

3 分層譯碼器結構設計

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

3.1 輸入緩沖模塊

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

3.2 信息存儲模塊

信息存儲模塊包括兩部分：(1)校驗節(jié)點信息存儲模塊Rmem，因為有255個校驗節(jié)點處理模塊同時工作，因此需要255個Rmem雙端口RAM來存儲校驗節(jié)點更新數(shù)據(jù)，每個RAM的存儲容量為3×7×12=252 bit。(2)變量節(jié)點信息存儲模塊Lmem，用來存儲后驗概率信息Fn?；谛ｒ灳仃嚱Y構，將3 060個后驗概率信息分為12塊來存儲，每塊存儲255個數(shù)據(jù)，即每塊RAM的存儲容量為256×7 bit。

3.3 校驗節(jié)點處理模塊

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

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

3.4 控制模塊

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

3.5 信息校驗模塊

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

3.6 輸出緩沖模塊

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

4 FPGA綜合結果及分析

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

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

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

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

將構造的(3 060，765，3，12)QC—LDPC碼分別采用分層結構和未分層結構，在NMSA基礎上進行的性能仿真如圖4所示。從圖中可看出，BER=10-6時，分層結構比未分層結構有約0.8 dB的性能增益。

5 結束語

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