請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/15692
標題: | 可配置低密度奇偶檢查碼解碼器設計與實作 Design and Implementation of Configurable Low-Density Parity-Check Codes Decoder |
作者: | Yi-Hsing Chien 簡義興 |
指導教授: | 顧孟愷(Mong-Kai Ku) |
關鍵字: | 低密度奇偶檢查碼,解碼,排程,迴圈控制,終止條件,編碼增益,可配置解碼器, Low-density parity-check codes (LDPC),decoding,scheduling,iteration control,termination condition,coding gain,configurable decoder, |
出版年 : | 2013 |
學位: | 博士 |
摘要: | 低密度奇偶檢查碼 (low-density parity-check code, LDPC code)提供接近Shannon極限錯誤更正能力。由於LDPC解碼器利用反覆解碼(iterative decoding)持續更新與交換檢查節點(check node)與位元節點(bit node)的資訊,導致解碼器能量消耗增加與總處理量低落。本論文針對LDPC解碼器,提出三項技術:一、利用排程技術減少解碼器延遲並提升硬體使用效率;二、藉由低複雜度解碼迴圈控制減少非必要計算;三、增強式節點更新演算法。
首先,我們針對部份平行的高速解碼器設計一排程演算法。此排程演算法在遵守資料相依性下,利用重疊訊息傳遞(overlapped message passing)以減少解碼器延遲並提昇硬體使用效率。此解碼器使用正規階層式類迴旋(regular hierarchical quasi-cyclic,regular H-QC)LDPC編碼,以提供較好的編碼增益。解碼器結構利用二階層正規H-QC結構平行處理運算,提供781.63Mbps的傳輸速度。 其次,為了減少LDPC解碼器不必要的能量消耗,提出一低複雜度解碼迴圈控制演算法。此演算法與解碼計算同時進行,偵測解碼收斂並消除解碼器等待時間。此演算法利用解碼過程中,藉由持續監測位元反轉(hard decision flipping)與同位元檢查(parity check)消除位元錯誤率(bit error rate)效能的減退。且此演算法利用位元反轉率 (hard decision flipping rate)來偵測無法解碼區塊(undecodable block)減少解碼器花費於無法解碼區塊的計算。此演算法可用於多編碼率(multi-rate)解碼器中,且僅需可適用於單一編碼率完全平行解碼症狀偵測(syndrome test)23.32%的硬體成本。 接著,提出一基於最小和解碼(min-sum algorithm)的低複雜度增強解碼演算法。此演算法保留最小和解碼低複雜度與可資料壓縮的優點,利用最小值與次小值之差做為決策,促進不可靠變數節點的可信度。在使用IEEE 802.16e標準、編碼率(code rate) 1/2、碼長(code length) 2304位元的編碼情況下,相較於調整比率的最小和演算法(scaling min-sum algorithm)此方法在可提供額外0.35dB的編碼增益。且在序列解碼處理單元中,實現成本僅需增加6%以下硬體成本。 最後,提出一可動態程式化的解碼器。藉由低成本的記憶體位址產生器,此解碼器可透過寫入不同奇偶檢查矩陣的資料至組態記憶體,可動態支援不同編碼率的類迴旋低密度奇偶檢查碼。此解碼器整合了本論文提出的低複雜度迴圈控制演算法與增強解碼演算法,提供一通用型低成本高效率的解碼器。 Low-density parity-check (LDPC) code has been shown to provide near-Shannon-limit performance for communication systems. Implementation cost, throughput, and power consumption are the most important issues for all communication design. In this dissertation, three techniques are proposed for efficient LDPC decoders: 1) a scheduling algorithm for high hardware utilization efficiency and throughput, 2) an iteration control algorithm for power efficiency and throughput, and 3) an enhanced min-sum decoding algorithm for better coding gains. First of all, we present a design of a high throughput LDPC decoder using an overlapped message-passing scheduling algorithm. Regular hierarchical quasi-cyclic (H-QC) LDPC code is used in this design to provide good coding performance at a long code length. The two-level regular H-QC LDPC code matrix structure is exploited to parallelize the row and column decoding operations. Our scheduling algorithm re-arranges these operations across iteration boundaries to avoid memory access conflicts. The memory requirements are reduced by half compared to pipelined decoders without scheduling. An (12288, 6144) LDPC decoder implemented in FPGA achieves 781.63 Mbps throughput performance. Second, the concurrent partially-parallel syndrome computation reduces complexity but incurs increased error rates due to the hard decision flipping (HDF) problem. We propose a low-complexity iteration control algorithm that eliminates BER degradation. The HDF rate is also used to terminate undecodable blocks to further save iterations. The algorithm works over multiple code rates. The implementation results show that a six-rate iteration control logic requires only 23.32% of the hardware of a single-rate fully parallel syndrome. Next, the min-sum algorithm is low complexity and has been shown to significantly reduce memory requirements by compression. We propose an enhanced min-sum decoding algorithm that yields better coding gains and maintains a low implementation cost. The difference of minimum values in the min-sum algorithm is used as a decision to boost unreliable bit nodes in the Tanner graph. Proposed enhanced min-sum algorithm offers a 0.35dB gain against the scaling min-sum algorithm for rate-½ LDPC code in IEEE 802.16e. The implementation results show that proposed enhanced min-sum decoding yields increases of less than 6% for a serial decoding processing unit. Finally, we propose a dynamically configurable layered decoder to support multiple quasi-cyclic parity-check matrices and different code rates. Parity-check matrices are described in an efficient way to reduce both the memory size and implementation cost of the address generator. Both iteration control and enhanced min-sum algorithms are integrated with the decoder for a complete verification and performance evaluation. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/15692 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf 目前未授權公開取用 | 2.99 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。