Efficient Booth Multiplier and Reed-Solomon Codec Architecture Design and Implementation

無論是應用在各領域的電路,我們都可以透過最佳化的演算法去創新與改良高效率架構，我們也實際針對目前熱門的電路作佳化的演算法設計，論文中提出一些相關的研究成果與創新，確實改良高效率架構與演算法。並獲得新型廣義性低誤差低面積固定寬度乘法器和大型磁碟陣列系統的解編碼器的設計。 在數位訊號處理與無線/有線通訊的技術日益發達，使得高速、低面積、低功率論點的要求也日益迫切需要。發展出好的演算法與架構將會大大地減少在邏輯層、電路層、佈局層的設計成本。論文中我們所提出新型或改良式架構與演算法將會突顯其中論點的效能而稍微犧牲剩餘論點的效能，我們的確可找到許多低誤差低面積固定寬度乘法器，我們提出(Binary-Thresholding Method)和(Binary- Condition Method)這兩種高效率架構與演算法為新型廣義性低誤差低面積固定寬度乘法器，此新型乘法器在語音處理上有很好的子音與母音波形因所提出的乘法器有較低捨棄誤差(Truncation Error)。改良的固定寬度乘法器並以TSMC 0.35微米製作成單一晶片，此晶片可操作在3.3伏特66MHz。 隨著網際網路及各種多媒體資料庫的發展，一個大型的儲存系統(如大型磁碟陣列系統)可以說是越來越重要，除了必須提供高速的介面供使用者存取，還必須提供非常穩定的資料保存環境，以防寶貴的資料因為各種可能的狀況而喪失。我們透過硬體或軟體的方式，使得資訊能夠可靠且正確的來做傳遞或是保存以因應各種可能使資料受到威脅的可能狀況(諸如熱雜訊、機器故障、不佳的保存環境或傳播通道等)。在各種容錯技術中，又以錯誤更正碼為最重要。我們發展出最佳化的演算法與架構的錯誤更正碼，並設計用來適應在各種不同的環境中，以因應各種環境可能遇到的資訊喪失。我們採用Altera Stratix FPGA Device(EP1S10F484C5)去實作RS的解編碼。No matter in what field the circuit is applied, we can always innovate or improve the high efficiency architecture by using the optimal algorithm. We have also implemented the optimal algorithm on the most popular circuits currently used. In this paper we presented some of our research results and innovation, which actually improve the efficiency architecture and algorithm. We also proposed new structures of generally low error, low area, fixed-width multiplier and the design of a decoder for large scale disk array system. Due to the fast development of digital signal processing and wireless/wired communication techniques, the demand for high speed, low area and low power becomes more and more urgent. The development of a good algorithm and architecture will largely reduce the design cost in the levels of logic, circuit and layout. The new or improved version of architecture and algorithm in this paper will illuminate the efficiency for some point while sacrificing some efficiency of the other. We did find some low error, low area fixed-width multiplier. We proposed two efficient architectures and algorithms, the Binary-Thresholding Method and Binary-Condition Method, which are new generally low error and low area fixed-width multiplier. Due to the lower truncation error this new multiplier has better waveforms for consonants and vowels. The improved fixed-width multiplier has been implemented as a single chip with a TSMC 0.35μm process, and operates under 3.3V and 66MHz. Along with the development of internet and various multimedia data base, a large scale storage system (such as a large scale disk array system) has become more and more important. In addition to providing a high speed interface for user access, it also has to provide a very stable data storage environment to prevent the loss of valuable data due to a variety of possible causes. We have applied methods with hardware or software to deal with every possible threatening situations (such as heat noise, machine malfunction, unfavorable preserving environment or transmission passages, etc.) to assure the storage or transmission of data reliable and correct. Among the various fault-tolerant techniques the error correction code is the most important one. We have developed the optimal algorithm and architecture for error correction code and have designed to cope with various environment in order to overcome data loss in various situations. We have used Altera Stratix FPGA device (EP1S10F484C5) to realize the RS codec.Abstract…………………………………………………………i Contents…………………………………………………………iii List of Figures………………………………………………iii List of Tables………………………………………………iii Chapter 1 Introduction………………………………………………1 1.1 Lower-Error Area-Efficient Fixed-Width Multipliers……………… 2 1.2 Fixed-Width Booth Multiplier with Efficient Compensation Circuits… 3 1.3 Introduction of Reed Solomon Code and RAID 6 system……………… 4 1.4 Reed Solomon Code Algorithm for Advanced RAID System…………… 4 1.5 Organization of Dissertation………………………… 5 Chapter 2 Fixed-Width Booth Multiplier with Efficient Compensation Circuits………………………………………………………… 6 2.1 Introduction…………………………………………………………6 2.2 Modified Booth Multiplier…………………………………8 2.3 Design of Fixed-Width Booth Multiplier……………………………… 11 2.3.1 Realizable error-compensation bias by keeping n most significant columns (w=0)………………………………………………… 13 2.3.2 Realizable error-compensation bias by keeping more than n columns (w=1)…………………………………………………………… 17 2.3.3 Low-Error Fixed-Width Booth Multipliers with Large Width …… 20 2.4 Performance and Area Comparisons………………………………… 23 2.4.1 Comparison Results of Four Kinds of Errors among Different Booth Multipliers……………………………………………………… 23 2.4.2 Comparison Results of Power Consumption among Different Booth Multipliers……………………………………………………… 26 2.5 DSP Application of Fixed-Width Booth Multipliers………………… 28 2.6 Summary…………………………………………………… 33 Chapter 3 Fixed-Width Booth Multiplier with Efficient Compensation Circuits……………………………………………………… 35 3.1 Introduction……………………………………………… 35 3.2 Modified Booth Multiplier……………………………………… 36 3.3 Design of Fixed-Width Booth Multiplier……………………… 38 3.4 Performance and Area Comparisons…………………… 44 3.5 Summary……………………………………………………… 47 Chapter 4 Introduction of Reed Solomon Code and RAID 6 system ……………………………………… 48 4.1 Introduction…………………………………………… 48 4.2 RAID 6 Architecture………………………………… 49 4.3 Introduction of Reed Solomon Code………………… 50 4.3.1 The basic concepts of finite field and BCH codes…………………….. 51 4.3.2 The construction of …………………… 54 4.3.3 BCH bound (Designed Distance)…………………… 57 4.3.4 Basic Design flow and Encoding of RS Codes…………………..…... 58 4.4 Comparisons between EvenOdd Code and RS Code………………….…….. 59 4.4.1 Update Complexity……………………………… 60 4.4.2 Analysis of Coding Computation…………………… 60 4.5 Summary……………………………………………64 Chapter 5 Reed Solomon Code Algorithm for Advanced RAID System……………………………………… 65 5.1 Introduction…………………………………………… 65 5.2 Previous Works on RS Code and RAID 6…………… 67 5.2.1 Encoding of RS code………………………………… 67 5.2.2 Decoding of RS code………………………………… 69 5.2.3 Construction of RAID6 system……………………… 70 5.3 System Optimization and RS codec design…………… 73 5.3.1 Reduced Static-Checksum Table Approach………… 75 5.3.2 The constant-multiplier-coefficient table…… 77 5.3.3 RS RAID decoder…………………………………… 81 5.4 Results And Comparisons……………………………… 84 5.5 Hardware Implementation of This RS-RAID Codec…… 87 5.5.1 The Encoder Block……………………………………… 88 5.5.2 The Decoder Block……………………………………… 89 5.5.3 Implementation Follow and EDA Tools…………… 90 5.5.4 Simulation Waveform…………………………………… 92 5.6 Summary……………………………………………… 93 Chapter 6 Conclusions……………………… 95 Bibliography…………………………………………………… 97 Publication List…………………………………………… 10