摘要 針對QC_LDPC碼的短環(huán)對碼性能的重要影響，采用了1種圍數(shù)為8的QC_LDPC碼設(shè)計。算法首先分別對3個不同的子矩陣進行移位運算，每個子矩陣分別與它們移位后生成的子矩陣共同組合形成1個新的子矩陣，然后再將新生成的3個子矩陣組合成1個矩陣構(gòu)成基陣，最后將該矩陣轉(zhuǎn)置后用單位矩陣及其移位矩陣隨機擴展即可得到所需校驗矩陣。根據(jù)該校驗矩陣的特殊結(jié)構(gòu)，采用分層迭代譯碼算法，選用Altera公司的Stratix III系列FPGA，實現(xiàn)碼率為1/2、碼長為3456的正規(guī)(3，6)QC_LDPC碼譯碼器的布局布線。

LDPC碼是近年來發(fā)展較快且日趨成熟的一種信道編碼方案，因其具有的優(yōu)越性能和實用價值而被人們認知，但由于隨機結(jié)構(gòu)的LDPC碼編譯碼器硬件實現(xiàn)較為復(fù)雜，具有的準循環(huán)特性QC_LDPC碼已成為IEEE 802.11n(WiFi)、IEEE 802.16e(WiMAX)、(DVB—S2)等眾多標準的信道編碼方案。LDPC碼是一種基于稀疏校驗矩陣的線性分組碼，具有類似于Turbo碼的良好糾錯性能。1981年Tanner提出的用二部圖表示一個低密度線性分組碼的方法，成為LDPC碼的主要分析工具。若LDPC碼的Tanner圖是無環(huán)的，那么與積SP(Sum—Product)譯碼算法可實現(xiàn)最佳譯碼，若存在環(huán)尤其是短環(huán)的話，則由和積算法計算所得的概率并非真正的后驗概率(這是因為迭代過程中的獨立性假設(shè)不能成立)，因而譯碼并不是最優(yōu)的逐符號最大后驗概率譯碼，因此，環(huán)的存在大幅影響了譯碼的性能。MacKay和Neal經(jīng)過大量的仿真結(jié)果證明信息傳遞算法(Message —Passing Algorithm，MPA)在Tanner圖中有環(huán)的情況下仍具有較好的譯碼性能，但短環(huán)的存在還是會降低譯碼性能。因此通過增大碼的最小圍數(shù)(環(huán)長)，可提高碼字的性能，圍數(shù)達到一定的值就可接近無環(huán)時的性能。

文獻提出一種圍數(shù)為8的低密度校驗矩陣的設(shè)計算法，獲得的QC_LDPC碼在AWGN信道下的仿真結(jié)果表明，其具有逼近隨機QC_LDPC碼的誤碼率性能。本文采用該算法構(gòu)造的校驗矩陣屬于正規(guī)的QC_LDPC碼，具有更好的分塊循環(huán)移位特性，大幅降低了編譯碼復(fù)雜度，而Mansour和Sha nbhag則提出了一種LDPC譯碼策略——分層譯碼(Lnyered decoding)，本文采用分層譯碼方案，為降低硬件復(fù)雜度，在Mansour和Shanbhag的基礎(chǔ)上進一步優(yōu)化，采用更為簡單的歸一化最小和算法(NMS)代替了傳統(tǒng)的和積算法(SPA)。整個譯碼過程只包含比較、移位和加減運算，運算量比SPA算法大幅降低，同時譯碼性能損失可不超過0.1 dB。

1 校驗矩陣的構(gòu)造

該方法構(gòu)造的是一個列重為3，行重>3的校驗矩陣。首先構(gòu)造3個子矩陣D、E和F，然后將子矩陣D、D和F按照行的方向排列生成H1，H1=[D E F]，再將H1轉(zhuǎn)置生成矩陣H2，最終用pxp的單位矩陣及其移位矩陣作為隨機因子，對矩陣H2中的“1”進行隨機擴展，即可生成所需的校驗矩陣H。

1.1 子矩陣D的構(gòu)造

構(gòu)造一個v行、v2列的矩陣D0，其中D0的元素D0(1，1)=D0(2，1)=D0(3，1)=…=D0(v，1)=1，其余元素均為0，

(1)將矩陣D0中的元素向右循環(huán)移位，每移動1位生成一個新矩陣。當(dāng)D0中所有元素為1的列移動到第v2列時移位完畢，共生成v2-1個新矩陣D1，D2，D3，…，Dv2-1。

(2)將D0，D1，D2，D3，…，Dv2-1按照列的方向排列便生成子矩陣D=[D0，D1，D2，…，Dv2-1]T，其維數(shù)為v3×v2。

1.2 子矩陣E的構(gòu)造

(1)構(gòu)造一個v行、v2列的矩陣E0，其中E0中的元素E0(1，1)=E0(2，2)=E0(3，3)=…=E0(v，v)=1，其余元素均為0，即E0的前v列所構(gòu)成的塊為單位矩陣。如，當(dāng)v=4時

(2)將v個E0矩陣按照列的方向排列生成矩陣E1=[E0，E0，…，E0]T。

(3)將矩陣E1向右循環(huán)移位，每移動v位生成一個新矩陣，由此共生成v-1個新矩陣，分別記為E2，E3，…，Ev。

(4)將E1，E2，E3，…，Ev按照列的方向排列生成子矩陣E=[E1，E2，E3，…，Ev]T，其維數(shù)為v3×v2。

1.3 子矩陣F的構(gòu)造

(1)構(gòu)造一個v行v2、列的矩陣F0。其中F0中的元素F0(1，1)=F0(2，v+1)=F0(3，2v+1)=…=F0(v，v2-v+1)=1，其余元素均為0。即在F0中，從第2行開始，每行中的元素“1”的列位置較上一行中的“1”向右移動v位。假設(shè)，當(dāng)v=4時

(2)將F0向右循環(huán)移位，每移動1位生成v-1個新矩陣，共生成個新矩陣時停止移位，將新矩陣記為F1，F(xiàn)2，F(xiàn)3，…，F(xiàn)v-1。

(3)將F0，F(xiàn)1，F(xiàn)2，F(xiàn)3，…，F(xiàn)v-1按照列的方向排列，生成的矩陣記為Fv=[F0，F(xiàn)1，F(xiàn)2，F(xiàn)3，…，F(xiàn)v-1]T。

(4)將v個Fv按照列的方向排列生成矩陣F=[Fv，F(xiàn)v，…，F(xiàn)v]T，其維數(shù)為v3×v2。

1.4 矩陣H2的擴展算法

將生成的子矩陣按行排列得到H1

1.5 擴展H2得到校驗矩陣H

(1)設(shè)一個單位矩陣I的維數(shù)為p×p，則

(2)隨機產(chǎn)生1-p之間的隨機數(shù)，該隨機數(shù)即為單位矩陣的循環(huán)移位數(shù)。

(3)將矩陣H2中的“1”用產(chǎn)生的隨機數(shù)來替代。

(4)將矩陣中的隨機數(shù)用對應(yīng)的置換矩陣替代填充，而矩陣H2中的元素“0”用p×P的零矩陣代替，由此即可生成所需的校驗矩陣H，其維數(shù)為3pv2×pv3。

文獻中也給出了4環(huán)和6環(huán)的檢驗算法，同時可驗證按照此方法得到的校驗矩陣最小圍長為8。

2 QC_LDPC碼的譯碼算法

置信傳播(Belief Propagation，BP)算法是LDPC的標準譯碼算法，在其基礎(chǔ)上又可改進得到最小和(Min-Sum)算法、歸一化最小和(Nor malization Min-Sum，NMS)算法等。此類算法皆通過校檢節(jié)點更新和變量節(jié)點更新兩步完成一次譯碼迭代，因此又稱為2項迭代置信傳播(Two Phase Message Passing，TPMP)算法。TPMP算法因為在一次迭代過程中，全部校檢節(jié)點更新完后，才對所有變量節(jié)點進行更新，所以在一次迭代過程中，所有信息只能進行一次更新，收斂速度較慢，譯碼延時較大。雖此后又提出了復(fù)用處理的方法，但未能從根本上提升算法的收斂性和譯碼性能。

2.1 QC_LDPC碼的分層譯碼策略

分層譯碼策略則改變了TPMP算法的譯碼方式，其將校檢矩陣按行或列劃分成若干分層。在一次迭代過程中，先并行更新第1分層中的所有校檢節(jié)點和相關(guān)的變量節(jié)點，然后逐層進行更新。因此在一次更新過程中，后更新的分層會利用已更新分層的輸出信息，變量節(jié)點在此過程中得到多次更新，大幅加快了譯碼的收斂速度，并提高了譯碼性能。但為確保變量節(jié)點信息在各分層之間能夠進行傳遞，校檢矩陣一個分層中的列權(quán)重必須1。

2.2 分層迭代譯碼算法

由上述子矩陣移位法構(gòu)造的是規(guī)則的QC_LDPC碼，因而采用分層譯碼時通常就是將校驗矩陣行重的一個子塊行作為一個分層，以碼長3 456，碼率為1/2的(3，6)正規(guī)QC_LDPC碼為例，基陣大小為108×216，填充矩陣塊為16×16，以每個子塊行作為一個分層即每個分層16行，共有108個子層。

設(shè)高斯白噪聲信道的噪聲方差為σ2，接收到的信號序列為y，校驗矩陣H的大小為M×N。迭代過程中信道固有信息Zn，校驗節(jié)點信息Lm,n，變量節(jié)點信息Zm,n，其中0≤m≤M-1，0≤n≤N-1。以BPSK調(diào)制為例，NMSA為基礎(chǔ)，將分層迭代譯碼算法的譯碼過程列述如下

(1)初始化

(2)迭代過程(第t次迭代的第k層)。

Step1分層更新。

Step2譯碼判決。若Zj0，則

=1，否則

=0，更新譯碼結(jié)果

。 (3)譯碼結(jié)構(gòu)校驗。完成一次迭代后，對更新的譯碼結(jié)果進行校驗。若滿足

xHT=0，或迭代次數(shù)達到系統(tǒng)設(shè)置的最大迭代次數(shù)，則停止譯碼，并輸出譯碼結(jié)果。否則，跳回步驟(2)進行新一次迭代。

3 正規(guī)QC_LDPC碼的譯碼器

3.1 譯碼器的結(jié)構(gòu)

對碼長為3 456，碼率為1/2的(3，6)正規(guī)QC_LDPC碼，子矩陣大小為16×16，共有108個子塊行，216個子塊列，648個非零子矩陣。采用分層迭代譯碼算法實現(xiàn)譯碼器，譯碼過程中只保存Zn和Lm,n兩種中間數(shù)據(jù)，變量節(jié)點信息則通過式(2)計算得出，以減小數(shù)據(jù)存儲量。為便于硬件實現(xiàn)，選擇α=0.75作為修正因子，這樣只需簡單的帶符號位右移和加法運算便可完成數(shù)據(jù)修正。由于將每一個子塊行作為一個分層，因此譯碼器的并行度為108，即共需108個基本運算單元。對譯碼器中的數(shù)據(jù)進行6 bit量化，并對計算過程中產(chǎn)生的溢出數(shù)據(jù)采用截斷處理，這樣的量化處理使譯碼性能約有0.1 dB的損失，但節(jié)約了硬件資源。

圖1為分層譯碼器的整體硬件結(jié)構(gòu)。

(1)數(shù)據(jù)輸入模塊。接收解調(diào)模塊輸出量化后的對數(shù)似然比數(shù)據(jù)，完成Zn的初始化。該模塊采用乒乓操作，即當(dāng)其中一個存儲器接收數(shù)據(jù)的同時，譯碼器從另外一個存儲器中讀取數(shù)據(jù)進行譯碼，以此來提高譯碼器的吞吐量。

(2)數(shù)據(jù)存儲模塊。根據(jù)譯碼過程中所存儲數(shù)據(jù)的不同，存儲模塊可劃分為3塊：1)后驗概率存儲模塊Zmem，用于存儲Zn。單個Zn的長度為6位，每個子塊列對應(yīng)的存儲空間為6×16=96位，對應(yīng)子塊列數(shù)，共需216個此類模塊。2)校驗信息更新存儲模塊Lmem，用于存儲，單個的長度為6位，每一行有6個非零元素，所以每行對應(yīng)的存儲空間為6×6=36位，而每一子塊行所對應(yīng)的存儲空間為6×6×16=576位。對應(yīng)子塊行數(shù)，共需108個此類存儲模塊。3)譯碼結(jié)果存儲模塊，用于存儲譯碼的結(jié)果。每一子塊列對應(yīng)的譯碼數(shù)據(jù)長度為16位，對應(yīng)子塊列數(shù)，共需216個此類存儲空間。同樣為了提高吞吐量，譯碼數(shù)據(jù)輸出模塊也采用乒乓操作，當(dāng)一個存儲器進行譯碼結(jié)果更新時，另一個存儲器向外設(shè)輸出存儲器中的譯碼結(jié)果。

(3)校驗節(jié)點更新模塊(Parity—Check UpdateBlock，PCUB)。校驗節(jié)點模塊是譯碼器的核心處理單元，完成迭代的更新過程。共有108個PCUB模塊進行并行處理，一次更新108組數(shù)據(jù)。每一組相關(guān)的6個變量節(jié)點信息串行輸入PCUB中的FIFO寄存器，并逐次進行比較，尋找該組數(shù)據(jù)中的最小值與次最小值。當(dāng)一組數(shù)據(jù)輸入完成后，最小值與次最小值得以確定，再從FIFO寄存器中依次讀出數(shù)據(jù)同最小值與次最小值比較，再更新數(shù)據(jù)。迭代譯碼過程主要被劃分成兩個階段，變量節(jié)點信息輸入FIFO階段和變量節(jié)點信息輸出FIFO階段。這樣的結(jié)構(gòu)適合采用二級流水線，當(dāng)一組已輸入的變量節(jié)點信息從FIFO中讀取時，將下一組變量節(jié)點信息輸入FIFO。通過二級流水線處理，提高了近一倍的數(shù)據(jù)吞吐率。

(4)地址生成模塊。地址生成模塊中包含一個保存校驗矩陣中所有子塊位置和子塊偏移量信息的只讀寄存器(ROM)。通過從ROM中調(diào)取信息，分別產(chǎn)生Zmem和Lmem的讀寫地址。

(5)校驗?zāi)K。校驗?zāi)K在每一次迭代結(jié)束之后，對所有校驗方程進行驗證，若全部滿足則停止迭代，否則進行下一次迭代過程，直至達到預(yù)先設(shè)定的最高迭代次數(shù)為止。

(6)控制模塊。控制模塊中設(shè)置整個譯碼器的狀態(tài)機，控制譯碼器各個子模塊有序運行。

3.2 譯碼器中內(nèi)存讀取的問題及改進

在PCUB模塊中，每個校驗節(jié)點對應(yīng)的6個變量節(jié)點信息串行加入迭代過程，而這些節(jié)點信息存儲在與之對應(yīng)的216個Zmem中。由于校驗矩陣列重為3，因此，若按照校驗矩陣原來的結(jié)構(gòu)，當(dāng)108個PCUB并行從Zmem中讀取數(shù)據(jù)時，順序讀取變量節(jié)點信息時可能從某一子塊列對應(yīng)的Zmem中讀取1～3個數(shù)據(jù)，這樣不同的讀取情況，會增加Zmem的硬件設(shè)計復(fù)雜度。

由于變量節(jié)點信息加入迭代過程的先后順序并不影響譯碼器的結(jié)構(gòu)，因此對變量節(jié)點信息的讀取順序加以改進，將原有的讀取順序重新排列，使得在同一時刻的PCUB從不同的子塊列對應(yīng)的Zmem中讀取數(shù)據(jù)，即每一時刻Zmem最多提供一個數(shù)據(jù)，這便大幅降低了Zmem的設(shè)計復(fù)雜度，進而提高硬件的通用性。

4 FPGA實現(xiàn)

選用Altera公司StratixIII系列的EP3SL340器件，設(shè)置最大迭代次數(shù)為5次，在QuartusII 9.0下完成綜合與布局布線，硬件資源消耗如表1所示。

在譯碼過程中，首先花費108個時鐘進行Zmem的初始化過程，完成后開始迭代譯碼。在每一次迭代過程中，PCUB模塊進行108次更新，由于采用流水線結(jié)構(gòu)，每次更新實際僅需花費6個時鐘，再加上第一組數(shù)據(jù)進入流水線花費的額外6個時鐘，5次迭代共花費6×(108×5)+6=3 246個時鐘。

圖2為傳統(tǒng)迭代與分層迭代譯碼算法的性能曲線比較，為AWGN信道模式下采用BPSK調(diào)制，進行6 bit量化。通過圖中的性能曲線可看出，在最大迭代次數(shù)同為5次的情況下，對正規(guī)QC_LDPC碼采用分層譯碼器處理后相比采用傳統(tǒng)部分并行結(jié)構(gòu)譯碼器具有較好的譯碼性能表現(xiàn)，在信噪比為2.5 dB的情況一，誤碼率可以達到10-5量級。

5 結(jié)束語

文中首先利用3個不同的子矩陣分別按照指定的方法進行移位運算，組合得到無4環(huán)和6環(huán)的基陣，進而利用單位矩陣及其移位矩陣作為替換因子隨機替換基陣中的“1”而擴展得到所需的校驗矩陣。隨后采用分層譯碼算法，該算法較傳統(tǒng)的部分并行結(jié)構(gòu)有較好的收斂性，并降低了迭代次數(shù)的要求。同時在Altera公司的StratixIII系列FPGA上得以實現(xiàn)，驗證其達到了較高的譯碼吞吐量。