通道解碼器之設計與實作

Abstract

本論文由演算法到架構設計與電路實現探討通道解碼器。依解碼方式不同可分成三個主要部分討論，分別是代數解碼，機率解碼以及重複解碼方式。 採用代數解碼的Reed-Solomon code用以研究其通用多系統的可能性。我們應用Montgomery 乘法演算法於通用有限場乘法器，使得有限場算數運算器不受有限場的限制。利用這些通用型運算器與簡化結構即可建構出一可符合大部分系統規範之Reed-Solomon解碼器，且不需進行電路修正。經由電路實現可以發現達成此通用能力僅需要小於一倍複雜度的額外成本，電路量測結果則證實解碼速度足以滿足目前大部分應用的需求。 Viterbi 解碼演算法是一種針對convolutional code 的最大可能性解碼方式，目前被廣泛應用於數位通訊系統。針對低功率設計，我們採行動態殘存路徑記憶體存取以及資料路徑變形。殘存路徑記憶體搭配所提出之路徑匹配與路徑預測方法可根據通道狀況動態調整截斷長度。運用一暫存記憶體，當路徑回歸至暫存路徑時，即可關閉大量記憶體讀取而降低功率消耗。另一方面吾人提出將加法-比較-選擇運算轉換成比較-選擇-加法，藉以降低運算量而達到降低電路成本與功率消耗。由電路量測結果得知這兩種技術可降低Viterbi解碼器的功率消耗達 30%~ 40%。針對高速Viterbi解碼器則提出二維加法-比較-選擇運算結構，在實際基數16的柵狀圖上實現Viterbi解碼器可達到1Gb/s的資料解碼速度。 再進一步研究重複解碼方式，以turbo code 與 low-density parity-check (LDPC) code 為對象。針對turbo解碼器應用於行動通訊系統並具有大型打亂器之編碼，以簡單解碼器架構降低電路成本，並考量記憶體最佳化以降低功率消耗。並且在一整合型turbo與Viterbi解碼器晶片上得到更好的能量效率。對於LDPC 解碼器則因其高平行度解碼演算法而進行高速應用之研究。由於不規則之對偶檢查矩陣以及大量運算元造成大量不規則資訊交換，我們提出一交換式記憶體以容納此大量資訊之傳遞。在電路實做上可達到 5.92Gb/s之資料解碼速度，面積則因大於70%之晶片密度而顯的更有效益。 本論文在研究三種通道解碼方式以及其應用上的實做，並探討系統規範提出可實現之方案並進行分析。最後透過電路實做進行量測或評估，實驗結果則顯示如預期之正面結論。

This dissertation investigates the channel decoders from algorithms to architecture designs and circuit implementation. Three different decoding schemes are studied, including the algebraic, the probabilistic, and the iterative decoding algorithms. The Reed-Solomon code based on the algebraic decoding is exploited to many system specifications. We apply the Montgomery multiplication algorithm to the universal finite field multiplier; as a result, the arithmetic units are capable of different finite field definitions. The Reed-Solomon decoder is constructed based on the proposed arithmetic operations and modified for less complexity. Hence the decoder can be applied to many systems without circuit modification. The chip implementation results show that the overhead due to the universality is no more than 100%. Moreover, the decoding speed from the measurement can meet most current or future applications. The maximum-likelihood decoding, Viterbi decoding algorithm, for the convolutional code is widely used in many digital communications. The low power design techniques for the Viterbi decoder are proposed for the dynamically survivormemory access and the datapath transformation. The survivor memory unit with the path merging and the path prediction algorithms can adaptively adjust the truncation length according to the channel conditions. Combining a cache buffer, we can avoid many read operations in the memory, leading less power consumption. On the other hand, we also transform the add-compare-select (ACS) operation to compare-select-add (CSA) for less computations resulting in lower cost as well as lower power dissipation. The implementation results indicate about 30%~40% power reduction is accomplished with the proposed architecture. The high speed and area efficient Viterbi decoder is also presented with the two-dimensional ACS structure. The decoder on the radix-16 trellis is implemented and shown to achieve over 1Gb/s data throughput. iii We further conduct the research into the iterative decoding based turbo codes and low-density parity-check (LDPC) codes. The turbo decoder is considered in the mobile communication system with large interleaver size. The simple decoder architecture is utilized for cost consideration, and the memory is optimized for power consumption. The unified turbo and Viterbi decoder chip is also shown to achieve better energy efficiency. The LDPC decoder is designed for high speed applications for its highly parallelizable decoding algorithm. Because of the irregular parity check matrix and the large number of processing elements, the register exchange memory is introduced to accommodate the large message passing in the decoder. As a result, the circuit implementation leads to a high decoding speed, which is 5.92Gb/s, and area efficient decoder chip whose chip density is larger than 70%. In this dissertation, the research includes different channel decoding schemes as well as their implementation for applications. Exploring the system requirements, we provide various design methods and analysis for the decoders. Finally, the circuits are realized for measurement or analysis, and the results reveal the positive consequence as expected.