基于FPGA有限域構(gòu)造的QC-LDPC分層譯碼器設(shè)計(jì)

低密度奇偶校驗(yàn)(Low Density Parity—Check，LDPC)碼最早于1962年由R.Gallager提出，其實(shí)質(zhì)是一類具有稀疏校檢矩陣的線性分組碼。1996年，Mackay、Neal等人證明了LDPC碼是一種具有逼近Shannon極限性能的好碼，但其隨機(jī)構(gòu)成特性又給編譯碼的實(shí)現(xiàn)帶來(lái)了較大復(fù)雜度，在碼長(zhǎng)較長(zhǎng)時(shí)，這種復(fù)雜度是硬件設(shè)計(jì)所難以接受的。準(zhǔn)循環(huán)低密度奇偶校檢(Quasi-Cyclic Low Density Party-Check，QC-LDPC)碼的出現(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)，此后出現(xiàn)了分層譯碼結(jié)構(gòu)。分層譯碼結(jié)構(gòu)擁有更快的譯碼速度，更好的性能和更簡(jiǎn)單的硬件結(jié)構(gòu)，成為QC—LDPC譯碼器的主流結(jié)構(gòu)。但是，分層譯碼要求QC—LDPC碼的校驗(yàn)矩陣每個(gè)分層的列重≤1。本文中采用有限域乘群構(gòu)造的QC—LDPC碼的校驗(yàn)矩陣每個(gè)分層的列重恰好等于1，滿足分層譯碼的要求。為進(jìn)一步降低硬件復(fù)雜度，采用歸一化最小和算法(NMSA)，整個(gè)譯碼過(guò)程中只包括比較、移位和加減運(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個(gè)非0元素構(gòu)成GF(q)在乘法操作下的乘法群，簡(jiǎn)稱乘群。對(duì)于其中的每個(gè)非0元素i，定義M位置矢量z(i)為GF(2)上的(q-1)維數(shù)組z(i)=(z1，z2，…，zn-1)，其第i個(gè)分量zi=1，所有其余q-2個(gè)分量均為0。GF(q)的0元素對(duì)應(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è)本原元α，則

構(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)每行或列中有且僅有一個(gè)0元素，第i行(1≤i≤q-2)的0元素位于第i行第(q-1-i)mod(q-1)列。(4)矩陣中每一行是上一行的左循環(huán)移位，第一行是最后一行的左循環(huán)移位。

步驟3 矩陣W(1)先后經(jīng)乘對(duì)折垂直擴(kuò)展，乘對(duì)折水平擴(kuò)展得到矩陣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)的每一行或每一列中有且僅有一個(gè)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之間選擇λ和ρ個(gè)不相等的隨機(jī)數(shù)組成隨機(jī)坐標(biāo)對(duì)。(2)從H(1)中選取相應(yīng)的元素作為基矩陣。(3)將基矩陣填充到Hqc時(shí)，選取的λ×ρ個(gè)循環(huán)移位矩陣之間的相對(duì)位置保持不變。

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

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

2 QC-LDPC碼的譯碼方案

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

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

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

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

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

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

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

3.1 輸入緩沖模塊

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

3.2 信息存儲(chǔ)模塊

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

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

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

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

3.4 控制模塊

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

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

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

3.6 輸出緩沖模塊

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

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

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

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

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

在譯碼過(guò)程中，首先從輸入緩沖模塊讀出數(shù)據(jù)對(duì)變量節(jié)點(diǎn)信息存儲(chǔ)模塊進(jìn)行初始化，共需128個(gè)時(shí)鐘周期。每個(gè)分層進(jìn)行校驗(yàn)、變量節(jié)點(diǎn)信息更新需要16個(gè)時(shí)鐘周期，則此迭代過(guò)程共需要花費(fèi)3×5×16+128×5=880個(gè)時(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的性能增益。

5 結(jié)束語(yǔ)

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