應用于無線傳感器網絡的低面積LDPC譯碼器

吳冰瑞， 陸玲霞

(1.浙江大學 微納電子學院，浙江 杭州 310058; 2.浙江大學 電氣工程學院，浙江 杭州 310058)

0 引 言

近幾年來，得益于更小、更便宜、更智能的傳感器，無線傳感器網絡(wireless sensor networks,WSNs)在遠程環境監控、目標跟蹤等方面有著重要的應用。然而,數字信號在傳輸過程中,不可避免受到各種噪聲和干擾的影響，采用糾錯編碼技術可以保證數據的可靠傳輸，大大改善通信性能，提高數據傳輸質量[1]。

低密度奇偶校驗(low density parity check,LDPC)碼是一種基于稀疏校驗矩陣的分組碼[2]，可以在低信噪比下接近香農極限[3]。結構化LDPC碼是一種采用代數方法或者組合工具構造的LDPC碼，一般為準循環，易于分析和硬件實現。

里德—所羅門(Reed-Solomon,RS)-LDPC碼基于RS碼構造，最小周長為6，屬于一種規則LDPC碼。仿真結果表明，在迭代譯碼下，RS-LDPC碼的收斂速度很快，性能良好[4]。

部分并行的LDPC譯碼器架構可以提高面積利用率[5]?；赥urbo碼的分層迭代譯碼算法，加快收斂速度，吞吐率可以達到640 Mbps[6]。列并行譯碼架構，單路并行吞吐率達到3.8 Gbps，4路并行吞吐率達到10 Gbps[7]。位串行算法[8,9]減少互連的數量，從而減少完全并行架構中布線面積。

針對最小和(Min-Sum,MS)算法校驗節點信息值計算復雜度高而導致硬件資源消耗過多的問題，本文提出一種簡化的MS算法。該算法只需計算變量節點傳遞到校驗節點信息值的絕對值最小值。根據校驗節點的輸出與變量節點計算值是否相等，添加補償系數以生成補償的校驗節點信息值，與MS算法相比有一定的性能損失，但減少計算復雜度66 %。使用4 bit量化信息值，校驗節點面積減少43 %，路由面積減少30 %，變量節點面積減少20 %。結合上述算法，設計了一種采用流水線和寄存器組部分并行LDPC譯碼器硬件架構。流水線可以提高時鐘頻率和數據吞吐率，寄存器組存儲計算得到的中間值和校驗節點信息值。使用55 nm互補金屬氧化物半導體(complementary metal-oxide-semiconductor,CMOS)工藝實現(6,32)規則(2 048,1 723)RS-LDPC譯碼器。

1 RS-LDPC碼

RS-LDPC碼是一種基于伽羅華域以代數的方式構造的結構化LDPC碼。設α為伽羅華域GF(q)的基本元素,則α∞=0，α0=1，α1，…，αq-2組成伽羅華域GF(q)的所有元素。在伽羅華域GF(q) 構造信息位長度為2,碼長為q的(q,2,q-1)RS碼CRS，生成矩陣G可以表示為式(1)

(1)

CRS可以看成q個子碼字的集合,每個子碼字可以由式(2)表示

(2)

每一個CRS中的子碼字,均為一個維度q×q的矩陣。利用CRS中的子碼字構造的LPDC碼校驗矩陣H,如式(3)所示

(3)

在伽羅華域GF(64)構造H矩陣，取出6×32的子矩陣，可以得到一個列重和行重分別為6和32的384×2 048的矩陣。

2 LDPC譯碼算法

2.1 MS算法

1)初始化

(4)

2)水平掃描，γ為歸一化系數

(5)

3)垂直掃描

(6)

4)譯碼

(7)

5)比特判決

(8)

如果達到最大迭代次數或者HTX=0，則X作為譯碼輸出；否則,迭代次數加1,并跳轉到式(5)繼續迭代。

2.2 簡化的MS算法

在全并行或者部分并行譯碼器中，式(5)的計算已經成為制約系統頻率、數據吞吐率、面積主要因素。式(5)可以轉換為求N(m)中變量節點到校驗節點信息值的第一最小值和第二最小值。為了減少計算復雜度，本文用式(9)和式(10)替換式(5)

(9)

(10)

式(9)中,β為補償系數，λ為小于1的正整數，用來估算第二最小值。

2.3 所提算法與MS算法復雜度對比

將(2 048,1 723)RS-LDPC碼分別用式(5)、式(9)、式(10)計算校驗節點，一次子迭代計算復雜度對比如表1所示。

表1 每次迭代譯碼的復雜度

dv為H矩陣每行平均變量節點個數，dc為每列平均校驗節點個數，E為矩陣中校驗節點和變量節點相連的個數。E，dv和dc滿足式(11)

E=mdv-ndc

(11)

由表1可知，所提算法的復雜度與MS算法比減少66.6 %。

2.4 仿真分析

用本文所提算法和MS算法在不同信噪比下對(2 048,1 723)(6,32)RS-LDPC碼的誤比特率(bit error rate,BER)、誤幀率(frame error rate,FER)進行了評估。信道模型采用加性高斯白噪聲(additive white Gaussian noise,AWGN)。所有仿真中的最大迭代次數為8，幀數設置為5 000。圖1和圖2分別為使用4 bit量化信息值得到的BER和FER曲線。可以看到，所提算法相比MS算法在BER為10-6時有約0.2 dB的性能損失，在FER為10-3時有約0.3 dB的性能損失。

圖2 FER曲線

3 LDPC譯碼器硬件實現

3.1 LDPC譯碼器架構

LDPC譯碼器架構如圖3所示，包含2 048個變量節點更新單元(variable node updates unit,VNU)和64個校驗節點更新單元(checking node updates unit,CNU)，兩個根據H矩陣生成的路由模塊用來交換變量節點和校驗節點信息值，以及一個地址產生控制模塊。

圖3 LDPC譯碼器架構

整個硬件架構用到3個存儲單元，包括：寄存器組存儲外信息以及計算得到的中間值；初始化寄存器存儲信道初始值；后驗信息寄存器存儲計算得到的后驗信息。后驗信息和外信息均使用4 bit有符號定點數量化。

3.2 流水線

為了提高數據吞吐率和系統時鐘頻率，設計一個8級流水線。第1級VC(V2C)在VNU模塊計算變量節點絕對值和符號值，第2級反向路由VNU(reverse routing VNU,RR VNU)的值到CNU，在CNU模塊用4級流水計算最小值和符號值，第7級反向路由CNU(RRCNU)的值到VNU，最后一級更新后驗信息和外信息。一次迭代譯碼過程如圖4所示，下一次迭代譯碼因為要用到這次迭代的結果，所以流水線會產生停頓等到這次迭代完成。

圖4 流水線

3.3 CNU模塊

RS-LDPC碼H矩陣是一個(6,32)規則碼。每個CNU模塊均有32個輸入?？紤]關鍵路徑和時序使用4級比較樹和異或樹求輸入最小值和符號值。本文所提算法對應比較樹如圖5所示，總共包含31個2輸入比較器。

圖5 所提算法的比較樹

3.4 VNU模塊

VNU模塊實現式(9)和式(10)規定的功能，進行后驗信息和校驗節點信息更新，使用加法器、比較器、選擇器和飽和電路實現，架構如圖6所示。后驗信息和外信息相減得到的絕對值使用3 bit量化，在不影響精度情況下減少面積。后驗信息值用流水線累加更新。

圖6 VNU架構

4 性能分析與比較

所提算法和MS算法使用4 bit量化，在Xilinx的XC7K325T—2FFG900芯片上各模塊消耗資源對比如表2所示。使用55 nm CMOS工藝實現結果對比如表3所示。

表2 算法資源對比

由表2可知，所提算法可以減少CNU模塊43 %，路由模塊30 %，VNU模塊21 %的資源。由表3可知,設計的芯片面積是文獻[10]和文獻[11]縮放后面積的79 %和46.5 %。此外，采用流水線的設計使系統時鐘頻率和吞吐率比文獻[10]高1.42和1.13倍。

表3 ASIC實現對比

5 結 論

為了降低WSNs成本，設計了一種低面積部分并行8級流水的LDPC譯碼器。針對MS算法校驗節點信息值計算復雜度高而導致硬件資源消耗過多的問題，本文簡化計算校驗節點信息值的算法。在MS算法優化的基礎上，設計實現 (2 048,1 723)RS-LDPC碼的譯碼器。使用55 nm CMOS工藝，譯碼器面積1.7 mm2，時鐘頻率600 MHz，在信噪比4.4 dB條件下，吞吐率可以達到29 Gbps。