該文通過對低密度校驗（LDPC）碼的編譯碼過程進行分析，提出了一種基于FPGA 的LDPC 碼編譯碼器聯合設計方法，該方法使編碼器和譯碼器共用同一校驗計算電路和復用相同的RAM 存儲塊，有效減少了硬件資源的消耗量。該方法適合于采用校驗矩陣進行編碼和譯碼的情況，不僅適用于全并行的編譯碼器結構，同時也適用于目前廣泛采用的部分并行結構，且能夠使用和積、最小和等多種譯碼算法。采用該方法對兩組不同的LDPC 碼進行部分并行結構的編譯碼器聯合設計，在Xilinx XC4VLX80 FPGA 上的實現結果表明，設計得到的編碼器和譯碼器可并行工作，且僅占用略多于單個譯碼器的硬件資源，提出的設計方法能夠在不降低吞吐量的同時有效減少系統對硬件資源的需求。

　　1 引言

　　在數字通信系統中，采用前向糾錯編碼（FEC）技術可大幅提高數據傳輸的可靠性。其中，LDPC碼憑借其優異的糾錯性能、較低的譯碼復雜度和可并行實現的譯碼結構，已被數字衛星廣播（DVBS2）、無線局域網（WLAN）和全球微波互聯接入（WIMAX）等多個通信標準采納。

　　如何在大規模集成電路上實現高速的LDPC 編譯碼器一直是LDPC 碼應用研究的一個焦點。理論上，可根據二部圖中的所有節點及邊線實現全并行結構的LDPC 碼譯碼器，但隨著碼長的增長，過高的布線復雜度及龐大的資源需求量將導致全并行結構的譯碼器難以實現。采用串行結構雖然可以減少硬件資源的消耗量，但譯碼器所需的存儲空間會隨著碼長的增長而迅速增加，并且其較低的譯碼吞吐量通常不能滿足實際應用的需求。2001 年Kou 等人［1］提出了準循環結構的LDPC 碼，由于其校驗矩陣的準循環特性，譯碼器可以采用部分并行結構進

　　行實現，從而使得基于長碼的高吞吐量LDPC 碼譯碼器得以實用化。現階段部分并行結構QC-LDPC譯碼器實現的研究工作已全面展開，文獻［2-8］給出了幾種有效的基于FPGA的譯碼器實現方法。在編碼器的實現上，如果直接采用生成矩陣編碼，那么算法復雜度將隨著碼長的增加以平方速度遞增，2001 年Richardson 等人［9］提出了一種簡化的編碼算法，但其所需的存儲和運算量依然過于龐大。此后，學者們提出了一些結構化的編碼方法，其中一種是設計生成矩陣也具備準循環性質的LDPC 碼，利用生成矩陣進行編碼，文獻［10］給出了該方法的編碼電路；另一種方法是采用特殊結構的準循環校驗矩陣進行編碼，例如IEEE 802.16e （WiMAX），IEEE 802.11n（WLAN）等標準采用了一種雙對角結構的準循環校驗矩陣進行編碼，針對該結構，文獻［11］提出了一種快速遞歸編碼算法及該算法的并行硬件實現架構。但現有的LDPC 碼編譯碼器設計方法都只針對編碼器或譯碼器單獨設計，并各自優化其吞吐量和FPGA資源，而實際的應用系統多數屬于全雙工通信系統，系統需要編碼器和譯碼器兩者同時工作，采用分離式設計將使得編碼器和譯碼器的硬件資源無法得到有效復用，導致FPGA資源的利用率不高。

　　本文針對IEEE 802.16e， IEEE 802.11n 等標準建議的LDPC 碼，提出了一種編碼器與譯碼器聯合設計方法，該方法使得編碼器能夠利用譯碼器在垂直運算時閑置的校驗計算電路進行編碼。提出的實現結構中，待編碼數據、待譯碼數據和譯碼碼字共用相同的存儲塊，編譯碼器的各處理單元共享同一組地址信息，有效減少了編譯碼系統對硬件資源的需求。

　　2 基于H 矩陣的LDPC 編碼

　　個矩陣與向量相乘的結果相加，且共有mb 個bi 向量需要求解，即便由于矩陣的結構特性使得矩陣乘法可以使用向量的循環移位代替，其計算量仍然較大。而其它式子均為2~3 個向量的加和，其計算量實際較少，因此整個編碼器的計算復雜度主要集中于式（2）。通過對式（2）分析可知，bi 實際由H 矩陣每行對應位為1 的各信息位相加得到，顯然，如果將碼字序列的校驗位部分全部置零后利用H 矩陣求解其伴隨式，那么得到的伴隨式與bi 等效。因此可以利用系統中現存且閑置的校驗計算電路，通過把校驗位置零后計算伴隨式的方法將其復用到對信息位的編碼上。本文的編譯碼器資源復用方案即利用了這種校驗計算電路編碼的思想進行設計。

　　3 LDPC 碼的譯碼過程分析

　　下面以歸一化最小和算法為例，分析LDPC 碼的譯碼過程及常見的譯碼器實現方式，結果表明：常規LDPC 碼譯碼器實現中包含一校驗計算電路，且由于譯碼算法本身的交替迭代性質導致該校驗計算電路在譯碼過程中有一半的時間處于空閑狀態。

　　現有的LDPC 碼譯碼器實現通常被劃分為3 個主要工作模塊［5?12］ ，其中變量節點處理單元（VNU）完成垂直運算，校驗節點處理單元（CNU）完成水平運算，校驗方程計算單元（PCU）完成譯碼判決。從上面的譯碼過程可知，垂直運算和水平運算不能同時進行，每次迭代中垂直運算需要以水平運算產生的作為輸入，水平運算反過來又需要垂直運算的結果，因此在同一時間里VNU與CNU必有一方空閑。另外，PCU 的校驗處理必需安排在VNU 對信息更新完畢之后，但其與CNU 沒有數據處理交集，因此PCU 與CNU 通常被設計為并行工作。對于部分并行結構的譯碼器，各模塊的并行度一般按照校驗矩陣的分塊來劃分。對于子矩陣大小為z×z的校驗陣，每輪迭代的前半部分各個VNU 對其對應分塊的z 列變量節點順序進行更新，若VNU 數據更新處理的流水線長度為Lv ，那么VNU 模塊在一次迭代中的工作總時長為z+Lv個系統時鐘周期。而PCU 則在CNU 處理的同時順序將z 行的校驗和進行加和，另外還需要Lp 個時鐘周期檢查伴隨式的各分量是否全部為0，因此CNU 模塊在一次迭代中的工作總時長為z+Lp 個系統時鐘周期。對于大部分校驗陣，z 比Lv ，Lc 和Lp 要大得多，而且Lv ，Lc 和Lp 通常大小相近，或可以被設計為完全相等。比如為了運算方便VNU 和CNU 通常需要用不同的數據形式（補碼和原碼）表示，而在實際設計中，可以選擇將原碼和補碼間的轉換安排在VNU或CNU 部分來達到兩者流水線長度的平衡。譯碼器各模塊的工作時序如圖1 所示。

　　由圖1 的工作時序可以看到，負責譯碼判決的PCU 只有在每次迭代的后半部分處于工作狀態，而PCU 模塊主要由校驗計算電路組成，根據第1節的討論，我們可以利用該校驗計算電路在垂直運算的空閑時間對信息位進行編碼，從而提高整個編譯碼系統的資源利用率，達到減少硬件資源消耗量的目的。以上討論基于歸一化最小和算法，但對其它LDPC 譯碼算法其迭代過程類似，只有水平運算和垂直運算的計算處理有所變化，因此該資源共享的設計思路對一般譯碼算法具有通用性。

　　4 編譯碼器的聯合設計

　　4.1 編譯碼器復合結構

　　本文利用編碼器和譯碼器在碼字校驗計算上的可協作特性，針對二者的數據流向復用存儲資源，提出了如圖2 所示的編譯碼器復合結構。該結構包含3 個處理單元，其中變量節點處理單元（VNU）和校驗節點處理單元（CNU）只作譯碼處理，校驗方程計算單元/編碼校驗位計算單元（PCU/ENC）被設計為一個時分復用模塊，在一半的處理時間里，它作為校驗方程計算單元（PCU）檢查譯碼結果的合法性，另一半處理時間里，它作為編碼校驗位計算單元（ENC）計算編碼產生的各校驗位。存儲單元分為4 部分，分別是位寬為Q bit 的信道初始信息存儲塊RAM_F，位寬為Q+T+1 bit 的混合信息存儲塊RAM_M，位寬為kb bit 的譯碼碼字存儲塊RAM_C 和位寬為mb bit 的編碼校驗位存儲塊RAM_P，其中Q 是譯碼器處理數據的量化比特數，T 是譯碼器最大迭代次數。

　　本文提出的復合編譯碼系統工作過程如下：

　　（1）初始化：將Q bit 的信道接收信息存儲到RAM_F 中，將T bit 的待編碼數據補零后擴展為Q+T+1 bit 存入RAM_M，初始化迭代次數為0次。RAM_M存儲塊中的數據由3 部分組成，其中包括Q bit 的譯碼迭代外信息（即的更新結果），T bit 的待編碼數據和1 bit 的譯碼判決結果。初始化完成后RAM_M 中的迭代外信息和譯碼判決位均為全零。

　　（2） 變量節點更新及編碼處理： 分別從RAM_F 和RAM_M中取出Q bit 的信道信息和迭代外信息送入VNU 處理，然后將更新得到的Q bit迭代外信息和1 bit 的譯碼碼字回寫到RAM_M中。其中譯碼碼字被重復存儲到RAM_M 和RAM_C 中，采用這樣的存儲結構需要額外的一塊

　　RAM 資源作為RAM_C 的碼字輸出緩存，但它可以使得PCU 能夠從RAM_M 中迅速讀取判決所需的譯碼比特，且有效降低了電路的布線復雜度，從而提高運行時鐘頻率，增大系統的編譯碼吞吐量。在變量節點更新的同時， PCU/ENC 單元從RAM_M 讀出的數據中取出1 bit 待編碼信息進行編碼，計算得到的校驗比特存入RAM_P。需要說明的是系統編碼幀數是譯碼幀數的T 倍，T 是譯碼器的總迭代次數，RAM_M中總共存儲T組信息序列，每次迭代中PCU/ENC 取出的待編碼比特對應T 組不同的信息序列。如果需要等吞吐量的編譯碼系統，可以通過屏蔽部分編碼處理得到。

　　（3）校驗節點更新及譯碼判決：從RAM_M 中取出Q bit 迭代外信息送入CNU 處理，處理結果回寫入RAM_M。同時從RAM_M 中取出變量節點更新得到的譯碼碼字，送入PCU/ENC 進行碼字的合法性校驗。如果校驗滿足或達到最大迭代次數，將RAM_C中的判決碼字作為譯碼結果輸出，否則轉到（2）繼續下一輪迭代處理。

　　這種結構中待編碼數據，待譯碼數據和譯碼碼字共用同一存儲塊，可以有效減少編譯碼器對存儲資源數量的要求，而且讀取一個存儲塊可以同時獲得編碼和譯碼所需的數據，使得VNU， CNU 和PCU/ENC 3 個模塊可以共享相同的地址信息，避免了ENC 獨立產生讀寫地址所需的大量邏輯資源，這樣的設計同時也有效降低了運算單元和存儲單元之間的布線復雜度。最后，T 路信息序列在不同迭代中分時復用ENC 進行校驗位的計算，能有效提高硬件資源的利用率和編碼器的吞吐量。

　　通過改變VNU， CNU 和PCU/ENC 運算單元的數量，該復合結構可以實現不同并行度的編譯碼器。當VNU， CNU 和PCU/ENC 只設置一個運算單元時，整個編譯碼系統為串行架構，此時系統占用的硬件資源少，但編譯碼吞吐量也較低，適合硬件資源十分緊缺且對數據速率要求不高的實現平臺。當VNU 運算單元個數與碼長相等、CNU 和PCU/ENC 運算單元數量為校驗位個數時，編譯碼系統為全并行架構，此時架構中的存儲單元應采用邏輯資源表示，系統的編譯碼吞吐量大，但要求大量的硬件資源，適合于短碼的實現。當VNU 運算單元個數與檢驗矩陣的列分塊數一致，CNU 和PCU/ENC 運算單元個數與行分塊數一致時，編譯碼器為部分并行架構，此時系統可以達到硬件資源需求量和吞吐量的折中，適合于吞吐量較大的長LDPC 碼編譯碼器實現。

　　4.2 編譯碼器的碼長碼率兼容設計

　　在編譯碼器采用完全相同的校驗矩陣進行編譯碼的情況下，本文提出的復合結構能夠將整個PCU 的校驗電路資源復用到編碼器的碼字計算上，從而節省編碼器所需的大部分硬件資源。典型的應用有中繼通信和對等的點對點通信等，尤其在衛星中繼通信中，由于低軌道中繼衛星需要通過譯碼再生對高軌道衛星的數據進行轉發，同時還需要將自身觀測得到的數據回傳到地面站，其要求的編碼吞吐量比譯碼吞吐量高，是該編譯碼器聯合設計方法應用的一個理想場景。但在更多的實際應用中，由于信道條件不對稱、設備的尺寸及功耗的約束不對等以及上下行業務需求不同等原因，通信系統的收發兩端很難采用完全一致的編譯碼體制。下面討論提出的復合結構在編譯碼矩陣的碼長和碼率上的兼容設計。

　　當編譯碼采用不同的校驗矩陣時，需要根據兩矩陣的差異性對復合結構進行修正，需要考慮的矩陣差異主要包括4 個方面：（1）矩陣對應分塊的偏移量不相同；（2）對應各分塊的行重列重不同及分布不一致；（3）矩陣的分塊數不相等；（4）子矩陣的大小不同。假設不同的兩校驗矩陣H1 和H2 ，其中兩矩陣的公共部分標記為A，矩陣H1 中獨立于H2 的部分標記為B， H2 中獨立于H1 的部分標記為C，如圖3所示。

　　首先，由于矩陣的偏移量不同并且各分塊間的偏移量差值不可能完全一致，這將導致對應分塊的編碼和譯碼信息無法共用相同的RAM 和地址發生器。針對這一問題，可以對初始化編碼信息的存儲地址作一定的偏移來達到數據訪問的一致性。對于兩矩陣相同的情況，在數據初始化階段，RAM_M中對應各矩陣分塊的各塊RAM 均從0 地址開始順序存入各編碼信息，而在譯碼迭代階段，編譯碼器則以公共偏移量作為初始地址順序讀寫子矩陣中的信息進行計算。而對于兩矩陣不相同的情況，若編譯碼校驗陣在同一位置的兩個子矩陣的向右循環移位次數分別為σ1 和σ2 ，那么在數據初始化階段，該分塊的RAM 可以將編碼矩陣和譯碼矩陣的地址差值作為初始地址對編碼信息進行存儲，具體操作時考慮到地址的循環移位性質，還需要對分塊大小進行取模運算， 即信息存儲首地址應為（σ1?σ2）?modz ，這樣在譯碼迭代時就可以將譯碼矩陣的地址偏移量σ2 作為公共地址來讀取編譯碼信息。由于RAM 共用，改變編碼信息的寫入順序顯然需要同時更改初始譯碼外信息的存儲順序， 但是由于RAM_M 存儲塊中的各外信息部分的初始值均為0，因此信息位存儲的初始順序的改變實際并不擾亂譯碼初始信息的讀寫順序；其次，兩校驗陣在行重和列重上的差異也會產生一些問題，在垂直運算階段，由于VNU 和ENC 同時工作，相同列分塊的列重不同和分布不一致將使得編譯碼數據的訪問不一致，造成RAM 資源共用困難。而在水平運算階段，由于CNU 和PCU 使用的同為譯碼矩陣，因此不存在矩陣差異對數據讀寫帶來的影響。另外，在垂直和水平運算間需要復用校驗計算電路，而行重不相同則會引起校驗計算電路不通用。在具體的電路實現中，由于存儲的編譯碼數據是經過拆分和組合后讀出或寫入的，因此并非必須相同位置的矩陣分塊才能共享RAM 存儲，實際上只要在垂直運算階段兩矩陣在同一列分塊的列重相等即可組合共用相同的RAM，而兩矩陣對應列分塊的列重不同則可以通過列分塊的交換來緩解，這是由于校驗陣的列交換不改變碼本空間，對于最后無法通過列分塊解決的列重不相等則需要放棄RAM 共用。對于行重不同引起的校驗計算電路不通用，可以在校驗計算電路中實現較大的行重，在處理行重較小的校驗矩陣時作屏蔽處理來解決問題；還有，矩陣的分塊數不相等會對資源復用帶來較大的影響，顯然只有兩個矩陣的交集部分（區域A）能夠采用資源復用設計，其余各矩陣的獨立部分（區域B 和區域C）則需要分開設計，需要注意的是，考慮編碼矩陣的區域范圍時只需考慮系統位部分，因為編碼時校驗位部分本身就需要通過置零的方式進行屏蔽，而對于編碼矩陣中與譯碼矩陣不重合的部分在校驗計算電路上可以直接舍去校驗位的加和；最后，對于子矩陣大小不同的情況，雖然也可以通過資源復用來達到節約資源的目的，但從圖1 的時序分析可以知道，子矩陣的大小不同將引起各模塊計算時間的不相等，造成時隙等待，從而增加控制上的復雜度，并且會造成吞吐量的降低。而從碼構造上看，矩陣的分塊大小并不會對碼性能構成大的約束，因此子矩陣大小差異的問題通過構造分塊大小相等的編譯碼矩陣來解決顯然更加合適。

　　5 硬件實現結果

　　采用提出的編譯碼器聯合設計方法對兩組不同的LDPC 碼編譯碼器進行部分并行結構的實現，第1 組編譯碼均采用碼長為2304 bit，碼率為5/6 的LDPC 碼；第2 組編譯碼采用不同的校驗矩陣，兩矩陣的分塊大小相同，其中譯碼采用16800 bit 的1/2 碼率LDPC 碼，編碼采用8400 bit 的3/4 碼率LDPC 碼。芯片使用Xilinx 公司的XC4VLX80FPGA，在ISE 10.1 平臺上進行邏輯綜合和布局布線，在ModelSim 6.2 上進行功能仿真和時序仿真。兩個譯碼器均采用4 bit 均勻量化，譯碼算法采用歸一化最小和算法，歸一化修正因子α 選擇為0.75，最大迭代次數均為10 次。圖4 是在AWGN信道，BPSK調制條件下，沒有量化的50 次和積迭代譯碼和量化后的歸一化最小和譯碼的性能對比。

　　對于兩組編譯碼器實現，表1 分別列出了單個編碼器、單個譯碼器和聯合設計的編譯碼器三者的資源使用情況及系統的信息吞吐量。除了采用提出的編譯碼復合結構以外，聯合設計的編譯碼器和單個編譯碼器實現使用的設計優化技術均相同。對于碼率為5/6 的第1 組實現，獨立設計和聯合設計兩種情況下編譯碼器均滿足5 ns 的布局布線約束，工作時鐘頻率為200 MHz。從表1 的數據可見，聯合設計的編譯碼器消耗的系統資源僅略多于單個譯碼器實現，其中邏輯資源多0.1%， BRAM 資源多2塊，而在編譯碼器分開設計的情況下，單獨設計一個編碼器需要消耗6.6%的芯片邏輯資源及14 塊BRAM資源，采用復合結構設計可以節省約30%的

　　邏輯資源和10%的BRAM 資源。對于編譯碼矩陣不同的第2 組實現，獨立設計時編譯碼器的工作時鐘頻率分別可達222 MHz 和200 MHz，聯合設計時系統工作主頻稍有降低，為196 MHz。聯合設計的編譯碼器消耗的系統邏輯資源比單個譯碼器多0.3%， BRAM 資源多2 塊，與分開設計的情況相比可節省約25%的邏輯資源和12%的BRAM 資源。在本文提出的編譯碼器復合結構中，編碼器的絕大部分資源由譯碼器共享得到，因而減少了編碼器對硬件資源的額外需求，從而顯著提高了FPGA資源的利用率。

　　該復合結構主要從工作時序上對編碼器和譯碼器的各組成部分作資源復用，除了要求RAM 的位寬較一般的譯碼器位寬寬以外，其它主要的譯碼模塊的設計與現有的設計技術不沖突，多數的其它設計優化方法都可以應用到本結構中，該設計僅利用了譯碼工作時的空閑時序進行額外計算。從設計原理上看，對各模塊增加資源復用設置只需要在原有電路上增加一些選通開關，對譯碼電路的布線復雜度影響較少，因此對整個編譯碼系統的工作頻率及吞吐量影響也較少，具體的實現結果也表明了這一點。該資源復用方案適用于一般的編譯碼系統，能夠達到節省系統資源而基本不降低編譯碼吞吐量的目的，其資源復用程度只與編碼和譯碼采用的校驗矩陣的相似度有關，而與系統具體使用的LDPC 碼的碼長和碼率等參數沒有關系。從兩組編譯碼器的實現結果可以看到，對于第1 組高碼率短幀長LDPC 碼和第2 組碼率較低的LDPC 長碼，提出的聯合設計方法都能夠在節省資源的同時實現與獨立設計的編譯碼器相當的吞吐量，而第1 組實現由于使用完全相同的校驗矩陣進行編譯碼，其資源節約百分比明顯要高于編譯碼矩陣不同的第2 組實現。需要說明的是，編譯碼器所能夠實現的吞吐量大小只與采用的LDPC 碼結構和具體模塊的設計有關，而該資源復用結構僅提供一種不降低吞吐量的資源復用設計，正如給出的兩個實現例子中，第1 組實現的吞吐量明顯要高于第2 組，但并不表明該方法更適合于高碼率短碼的編譯碼器設計，也不表明該方法能夠使高碼率譯碼器的吞吐量做得更高，這是由于編譯碼系統本身選用的參數不同而導致吞吐量大小的差異，第1 組實現的編碼并行度本身要高于第2 組，且計算信息吞吐量時，高碼率LDPC 碼的信息位比例要較低碼率情況時高，因此在相同的幀處理速度下，高碼率碼可實現的信息吞吐量也高。綜上所述，與分離式設計相比，本文提出的聯合設計方法能夠在不降低系統吞吐量的前提下減少硬件資源的需求量，特別適用于資源受限的硬件平臺。

　　6 結論

　　本文分析了準循環雙對角結構LDPC 碼的編譯碼過程，利用譯碼器在垂直運算時閑置的校驗計算電路，通過把校驗位置零后計算伴隨式的方法將其復用到編碼器的碼字計算中，提出了一種利用校驗矩陣編譯碼的編譯碼器聯合設計方法。該方法使得編譯碼器共享相同的RAM 存儲塊及地址產生器，有效減少了實現所需的存儲資源和邏輯資源。在Xilinx XC4VLX80 FPGA 上的實現結果表明，聯合設計的編譯碼器能夠進行高速編譯碼，且僅占用略多于單個譯碼器的硬件資源，提出的設計方法能夠在不降低系統吞吐量的同時減少對硬件資源的需求量。