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

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

設q是任意質數或質數的冪，則整數集{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)維數組z(i)=(z1，z2，…，zn-1)，其第i個分量zi=1，所有其余q-2個分量均為0。GF(q)的0元素對應的M位置矢量定義為q-1維全0數組。顯然，GF(q)中的任意元素i+2的M位置矢量z(i+2)可由i的位置矢量z(i)循環(huán)右移2位得到。

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

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

設本原元α，則

構成GF(q)的所有元素。根據預期構造校驗矩陣的大小選擇合適的有限域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)先后經乘對折垂直擴展，乘對折水平擴展得到矩陣H(1)。

H(1)具有以下結構特性：(1)A0,0，A1,q-2，A2,q-3，…，Aq-2,1均是(q-1)×(q-1)的0矩陣，其他子矩陣都是同維數的循環(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之間選擇λ和ρ個不相等的隨機數組成隨機坐標對。(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碼譯碼算法，對它進行改進又出現了最小和算法(Min Sum Algorithm，MSA)，歸一化最小和算法(Normalizat ion Min Sum Algorithm，NMSA)等。這類算法因其通過校驗節(jié)點更新和變量節(jié)點更新兩個步驟完成一次迭代譯碼，被稱為2項置信傳播(Two Phase Message Passing，TPMP)算法。TPMP算法在一次迭代譯碼過程中，全部的校驗節(jié)點更新結束后，所有的變量節(jié)點才開始更新，即在一次迭代過程中，所有信息只更新一次。所以，該算法的收斂速度較慢，譯碼延遲較大。

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

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

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

3 分層譯碼器結構設計

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

3.1 輸入緩沖模塊

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

3.2 信息存儲模塊

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

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

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

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

3.4 控制模塊

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

3.5 信息校驗模塊

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

3.6 輸出緩沖模塊

暫存迭代譯碼過程中產生的判決結果，并在譯碼結束后向外部輸出數據。

4 FPGA綜合結果及分析

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

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

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

在譯碼過程中，首先從輸入緩沖模塊讀出數據對變量節(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上得以實現，并得到較高的譯碼吞吐率。