非二位元低密度同位元檢查區塊/迴旋碼解碼器之設計與實現

Design and Implementation of Nonbinary LDPC-BC/CC Decoders

林佳龍(Chia-Lung Lin)

指導教授 ： 李鎮宜 ； 張錫嘉

國立交通大學/電機學院/電子工程系所/博士(2016年)

摘要

錯誤更正碼在通訊或儲存系統中提供錯誤更正的能力。 在過去數十年中，因為二位元低密度檢查碼的優秀更正能力及高平行度的處理特性，所以該碼廣泛地運用在許多系統或標準中。非二位元低密度檢查碼在多根天線系統以及衰弱通道下擁有更傑出的錯誤更正能力，且可同時更正連續及隨機的錯誤。然而，解碼器的高複雜度及大量的儲存需求使得非二位元低密度檢查碼無法在實際的應用中被採用。許多文獻在演算法及硬體架構上簡化及改善解碼過程，但吞吐量、矽面積使用效率以及能量使用效率仍然跟其它種類的錯誤更正碼相之甚遠。另一方面來說，二位元低密度檢查區塊碼不利提供多種碼長及多種碼率。非二位元低密度檢查迴旋碼不僅具有優秀的錯誤更正能力，並且像迴旋碼一樣能提供多種碼長。然而，該碼卻有些缺點，例如長延遲、低平行度以及一般的吞吐量。除此之外，目前文獻中並無該類解碼器的討論。因此，在此論文中探討並研究非二位元低密度檢查區塊碼/迴旋碼來探索未來通訊系統中該碼的潛力。
非二位元低密度檢查區塊碼方面，此論文提出了兩個完整設計。第一個是運用在類循環非二位元低密度檢查區塊碼的高矽面積使用效率解碼器架構，解碼演算法是根據延伸的最小值-總和演算法(Extended Min-Sum)。藉由提出的雙倍吞吐量的校驗節點單元以及節點單元間的重疊處理來提升吞吐量。訊息隱藏以及簡化的變數節點單元被提出來降低儲存量及運算量。綜合以上技巧，實作了一個GF(64)(112,56)非二位元低密度檢查區塊碼解碼器。在post-layout結果中，core面積是2.24 mm^2，功率是274mW而吞吐量是124.6 Mb/s。第二個設計是針對近年興起的低耗移動裝置或IoT應用。根據trellis min-max演算法，提出了高吞吐量的校驗節點單元以及兩階段的變數節點單元來提升吞吐量和能源效率。為了提供多樣化的通道品質，提出訊息長度切換方法來調整錯誤更正能力來節省能源。為了驗證提出的方法，我們用90nm CMOS實作了一個GF(32)(400,200)的非二位元低密度檢查區塊碼解碼器。在量測結果中，core面積是5.02 mm^2，吞吐量是1.53 Gb/s而功率是434mW。比起過去的研究，此設計具有最高的吞吐量以及最好的能源及矽面積使用效率，並能節省90%以上的能源。
在非二位元低密度檢查迴旋碼方面，提出一個同時考慮到硬體架構及錯誤更正能力的的建碼方式。此碼的特色在簡單的架構以及低連線數。針對所提出的建碼方式，我們也提出了相對應的記憶體基礎之解碼器架構。其中，運算單元及運算排程皆針對能源效率來改進。綜合以上方法，用90nm CMOS實作了一個時變GF(256)(50,2,4)的非二位元低密度檢查迴旋碼解碼器。錯誤更正能力在SNR=0.9dB時達到位元錯誤率10^{-5}，並且藉由穿刺可提供多種碼率。
此論文中針對非二位元低密度檢查區塊碼/迴旋碼在通訊相關系統進行了研究與探討。所提出的研究方法與實作結果在解碼校能跟硬體效率之間有更好的平衡，更有機會應用在實際應用。

關鍵字

非二位元低密度同位元檢查碼 ； 迴旋碼 ； 錯誤更正碼 ； 解碼器 ； VLSI ； 低密度同位元檢查碼

並列摘要

Channel codes support an error-correcting capability in communication or storage systems. In the past decades, binary LDPC block codes (LDPC-BCs) are widely adopted in many systems and standards because of its excellent error-correction capability and high parallelism. Nonbinary LDPC-BCs (NB-LDPC-BCs) have even better error correcting performance under MIMO systems and fading channels, and can combat burst and random errors simultaneously. However, the high complexity and huge storage requirement in decoder design prevent NB-LDPC codes in practical applications. Many works in the literature improve and simplify decoding process in algorithm and architecture levels, but the throughput, area-efficiency and energy-efficiency still cannot catch up the other channel codes. In the other hand, LDPC-BCs have weakness for supporting flexible block length and multi-code-rate. NB-LDPC convolutional codes (NB-LDPC-CCs) not only have excellent error-correcting performance, but also support variable block length naturally as convolutional codes. Nevertheless, the codes have serious drawback, such as long latency, low parallelism, and normal throughput. Besides, there is no relative work in the literature before. Hence, this dissertation investigates both NB-LDPC-BCs and NB-LDPC-CCs to explore the potential for the next generation of communication systems.
For NB-LPDC-BCs, this dissertation presents two works. The first one is an area-efficient decoder architecture for quasi-cyclic NB-LDPC codes with EMS algorithm. The throughput is improved by not only double-throughput elementary check node unit that processes two combinations within one clock cycle, but also overlapped processing for both check node and variable node units. To reduce memory usage and computing complexity, edge-message hiding and simplified variable node unit (VNU) are proposed as well. With these schemes, the post-layout results of a decoder for a (112,56) NB-LDPC over GF(64) are presented. The core area occupies 2.24 mm^2 and consumes 274 mW with throughput of 124.6 Mb/s. The second one is targeting emerging energy constrained mobile devices or internet-of-things (IoT). We propose high-throughput check node unit with trellis min-max algorithm and two-stage variable node unit to improve the throughput and energy efficiency. Message-length switching is also proposed for adjusting error-correcting capability to fit the diversity of channel, and further saving power consumption. To demonstrate the proposed techniques, a decoder for (400,200) NB-LDPC code over GF(32) is implemented with 90-nm CMOS technology. The core occupies 5.02 mm^2, and the measurement results show that 1.53 Gb/s can be achieved with 434 mW. The implementation result has higher throughput and higher hardware-efficiency than the state-of-the-art designs, and saves more than 90% energy in technology normalized comparison.
For NB-LDPC-CCs, a design approach for architecture-aware NB-LDPC-CCs is presented to jointly optimizes the code performance and decoder complexity for achieving high energy-efficiency decoder. The proposed NB-LDPC-CCs feature simple structure and low degree. We also present a corresponding memory-based decoder architecture, where the computation units and the scheduling of the computations are optimized to increase energy efficiency. A time-varying (50,2,4) NB-LDPC-CC over GF(256) is constructed, and associated decoder is implemented in 90nm CMOS. The code can reach BER = 10^{-5} at SNR=0.9dB, and support multi-code-rate with puncturing.
NB-LDPC-BCs and NB-LDPC-CCs decoders are investigated for communication relative systems. The proposed design methodologies would make NB-LDPC codes more competitive to the other channel codes.

並列關鍵字

nonbinary low-density parity-check codes ； convolutional codes ； error correcting codes ； decoder ； VLSI ； low-density parity-check codes

參考文獻

[7] R. Yazdani and M. Ardakani, “Efficient LLR calculation for non-binary modulations over fadingchannels,” IEEE Trans. Commun., vol. 59, no. 5, pp. 1236–1241, 2011.

[8] R. Peng and R. R. Chen, “Application of nonbinary LDPC cycle codes to mimo channels,” IEEE Trans. Wireless Commun., vol. 7, pp. 2020–2026, 2008.

[9] D. Declercq and M. Fossorier, “Decoding algorithms for nonbinary LDPC codes over GF(q),” IEEE Trans. Commun., vol. 55, no. 4, pp. 633–643, 2007.

[10] A. Voicila, D. Declercq, F. Verdier, M. Fossorier, and P. Urard, “Low-complexity decoding for non-binary LDPC codes in high order fields,” IEEE Transactions on Communications, vol. 58, no. 5, pp. 1365–1375, 2010.

[11] V. Savin, “Min-max decoding for non binary LDPC codes,” in IEEE International Symposium on Information Theory, 2008, pp. 960–964.