吳冰瑞， 陸玲霞

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

0 引 言

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

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

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

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

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

1 RS-LDPC碼

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

(1)

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

(2)

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

(3)

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

2 LDPC譯碼算法

2.1 MS算法

1)初始化

(4)

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

(5)

3)垂直掃描

(6)

4)譯碼

(7)

5)比特判決

(8)

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

2.2 簡化的MS算法

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

(9)

(10)

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

2.3 所提算法與MS算法復(fù)雜度對比

將(2 048,1 723)RS-LDPC碼分別用式(5)、式(9)、式(10)計(jì)算校驗(yàn)節(jié)點(diǎn)，一次子迭代計(jì)算復(fù)雜度對比如表1所示。

表1 每次迭代譯碼的復(fù)雜度

dv為H矩陣每行平均變量節(jié)點(diǎn)個(gè)數(shù)，dc為每列平均校驗(yàn)節(jié)點(diǎn)個(gè)數(shù)，E為矩陣中校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)相連的個(gè)數(shù)。E，dv和dc滿足式(11)

E=mdv-ndc

(11)

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

2.4 仿真分析

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

圖2 FER曲線

3 LDPC譯碼器硬件實(shí)現(xiàn)

3.1 LDPC譯碼器架構(gòu)

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

圖3 LDPC譯碼器架構(gòu)

整個(gè)硬件架構(gòu)用到3個(gè)存儲單元，包括：寄存器組存儲外信息以及計(jì)算得到的中間值；初始化寄存器存儲信道初始值；后驗(yàn)信息寄存器存儲計(jì)算得到的后驗(yàn)信息。后驗(yàn)信息和外信息均使用4 bit有符號定點(diǎn)數(shù)量化。

3.2 流水線

為了提高數(shù)據(jù)吞吐率和系統(tǒng)時(shí)鐘頻率，設(shè)計(jì)一個(gè)8級流水線。第1級VC(V2C)在VNU模塊計(jì)算變量節(jié)點(diǎn)絕對值和符號值，第2級反向路由VNU(reverse routing VNU,RR VNU)的值到CNU，在CNU模塊用4級流水計(jì)算最小值和符號值，第7級反向路由CNU(RRCNU)的值到VNU，最后一級更新后驗(yàn)信息和外信息。一次迭代譯碼過程如圖4所示，下一次迭代譯碼因?yàn)橐玫竭@次迭代的結(jié)果，所以流水線會產(chǎn)生停頓等到這次迭代完成。

圖4 流水線

3.3 CNU模塊

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

圖5 所提算法的比較樹

3.4 VNU模塊

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

圖6 VNU架構(gòu)

4 性能分析與比較

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

表2 算法資源對比

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

表3 ASIC實(shí)現(xiàn)對比

5 結(jié) 論

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