吳安宇臺灣大學：電子工程學研究所許槐益Hsu, Huai-YiHuai-YiHsu2007-11-272018-07-102007-11-272018-07-102006http://ntur.lib.ntu.edu.tw//handle/246246/57617為了達到低成本/低功率之高效能設計目標與多重功能/可擴充性之可重規劃性設計，本論文提出利用包含新技術之應用設計導向方法論去設計具有多重功能之可重規劃性里德所羅門（Reed Solomon, RS）超大積體電路架構。本論文所提之設計技術從演算法推導、硬體架構設計、邏輯及電路設計等層面進行最佳化設計，以達到應用導向為主之高效能前饋式錯誤更正碼（Forward Errorr Correciton）設計目標。所提之架構技術包含：多模式以PGZ演算法為基礎之低延遲架構、可擴充性之可重規劃性架構、以運算單元（Processing element）為基礎建構Multi-Symbol Sliced資料流處理架構、以及Just-in-Time folding 架構。利用這些技術，本論文提出了四項里德所羅門矽智產（RS Silicon IP）設計實例，依據應用設計導向方法分別為：1) PGZ-RS IP：適用於低錯誤更正能力的儲存系統之低成本/低延遲RS架構設計，2) RC-RS IP：適用於多重規格/多重模式的通訊/儲存系統之可重規劃性RS架構設計，3) MSS-RS IP：適用於可攜式系統之通曉功率消耗架構設計、以及 4) OC-RS IP：適用於光纖通訊之低成本架構設計。PGZ-RS提供PGZ演算法的錯誤更正能力適用於t=1~3，並利用可重規劃性架構硬體來支援多個錯誤更正能力以減少硬體成本。RC-RS利用規則的可擴充特性建構一個可適用於多重規格/多重模式系統之可重規劃性架構，可大量的降低設計者的負擔並縮減設計到量產的時程。MSS-RS可有效率的控管功率消耗，使得使用者可在不同的資料傳輸率與動態功率消耗之間做取捨（tradeoff），因此可以大大的提升可攜式產品電池使用效率。OC-RS不僅提供超高速傳輸效能可適用於光纖通訊，並且利用所提新技術大大地提升硬體效能，使得每個邏輯閘效能（gate efficiency）能夠提供最有效率的使用。本論文中所提出的可擴充性及可重規劃性之架構，應用在四個RS矽智產的設計實例，突顯高效能之RS矽智產的優勢。For high-performance reconfigurable Reed-Solomon Silicon IP design, this dissertation proposes various new techniques to design the VLSI architectures with both versatility and scalability. The proposed design techniques include multi-mode PGZ-based architecture, scalable modified Euclidean architecture, multi-symbols sliced PE-based architecture, and just-in-time folding ME architecture. They provide optimization to achieve the target of high performance in algorithmic, architecture, logic, and circuit levels. By using these techniques, this dissertation presents four design approaches, which are 1) a low-cost low-latency implementation for small t (t≦3) RS design (PGZ-RS IP), 2) a Reconfigurable RS codec for multi-standard / multi-mode communication/storage systems (RC-RS IP), 3) a power-aware dynamically reconfigurable RS design for portable device (MSS-RS IP), and 4) an area-efficient optical-rate RS design (OC-RS IP). The PGZ-RS IP design can solve t=0, 1, 2, 3 errors in one unified VLSI architecture with very low hardware cost by using algorithm strength reduction method. The RC-RS IP design can easily be configured to serve the specified (n, k, t) value to perform multi-standard based on the scalable ME architecture for different systems. The MSS-RS IP design can provides power-aware feature to extend the battery life of portable devices. The OC-RS IP design can provide ultra high-speed performance for fiber systems by using the just-in-time folding ME architecture. In summary, these four design examples presented in this dissertation demonstrate various design techniques which can be adopted in designing application-oriented reconfigurable Reed-Solomon Silicon IP.中文摘要 I Abstract V Contents VII Lists of Figures XI List of Tables XVI Chapter 1 Introduction 1 1.1 Background 1 1.2 Design Methodology 5 1.3 Motivation and Goal 7 1.3.1 Low-Cost Low-Latency Implementation for Small t (t≦3) RS Codec (PGZ-RS IP) 8 1.3.2 RS codec for Multi-Standard/Multi-Mode Communication/Storage Systems (RC-RS IP) 9 1.3.3 Dynamically Reconfigurable RS codec for Power-Aware (MSS-RS IP) 11 1.3.4 Area-Efficient Optical-Rate RS VLSI Designs (OC-RS IP) 12 1.4 Organization 16 Chapter 2 Reviews of Reed-Solomon Algorithm and Architectures 17 2.1 Review of Reed-Solomon Code 17 2.2 Reed-Solomon Encoding Algorithm 20 2.2.1 The g(x)-Basis Algorithm and Architecture 20 2.2.2 The a(x)-Basis Algorithm and Architecture 21 2.3 Reed-Solomon Decoding Algorithm 23 2.3.1 Syndrome Calculation 23 2.3.2 Modified Euclidean GCD Algorithm 24 2.3.3 Chien’s Search and Forney Algorithm 25 2.3.4 Architecture Mapping 25 Chapter 3 Low-Cost Low Latency PGZ-based Reed-Solomon Decoder Designs 29 3.1 Overview 29 3.2 Review of PGZ Algorithm 30 3.2.1 PGZ Algorithm for t =1 31 3.2.2 PGZ Algorithm for t=2 32 3.2.3 PGZ Algorithm for t=3 32 3.2.4 Reduced-Complexity Reed-Solomon Decoder Architecture for t=3 34 3.2.5 FFI-free Modified PGZ algorithm for t=3 35 3.3 Multi-Mode PGZ Algorithm and Architecture 38 3.3.1 Problems of t=3 PGZ Architecture when t=1 or 2 38 3.3.2 The Proposed Multi-mode Decoding Algorithm 39 3.4 Comparison of Complexity 42 3.5 Summary 44 Chapter 4 RC Reed-Solomon codec for Multi-Standard/Multi-Mode Communication/Storage Systems 45 4.1 Overview 45 4.2 Scalable Design of Reed Solomon Decoder 47 4.2.1 Syndrome Calculation 47 4.2.2 Scalable Modified Euclidean GCD Algorithm 48 4.2.2.1 Modified Euclidean Division 48 4.2.2.2 Modified Euclidean Multiplication 50 4.2.2.3 Retimed MEM Architecture 51 4.2.3 Chien’s Search with Bias-Vector Method and Forney Algorithm 52 4.3 Run-Time Programmable Control Unit 55 4.4 Chip Implementation and Comparison 56 4.5 Summary 60 Chapter 5 Dynamically Reconfigurable RS codec for Power-Aware System 61 5.1 Overview 61 5.2 Unified Finite-Field Processing Element 64 5.3 Multi-Symbol-Sliced Architecture 65 5.3.1 Direct-Mapping Data Path RS Architecture 66 5.3.2 Proposed Multi-Symbol-Sliced (MSS) Data-Path Architecture 68 5.4 Operations of Dynamically Reconfigurable Reed-Solomon Decoder 70 5.4.1 Dynamically Reconfigurable Property for d-PE Mode 70 5.4.2 Operations of Dynamically Reconfigurable RS Decoder Using 4 PEs 71 5.4.2.1 Full-Run (4-PE) Mode 71 5.4.2.2 Half-Run (2-PE) Mode 72 5.4.2.3 Single-PE Mode 73 5.5 Performance and Comparison 73 5.5.1 Decision of m-PE MSS Data-Path Architecture 73 5.5.1.1 Theoretical Performance Analysis of m-PE design in Different Run-Time Modes 73 5.5.1.2 Synthesized Data throughput Rate Analysis 74 5.5.2 Prototyping RS Decoder Implementation with 4-PE MSS Data-Path Architecture 75 5.5.2.1 Dynamic Power Analysis 75 5.5.2.2 Applications of the Prototyping Design 77 5.5.2.3 Performance Comparison 78 5.6 Summary 80 Chapter 6 Area-Efficient Optical-Rate Reed-Solomon VLSI Designs 81 6.1 Overview 81 6.2 Drawback of Existing RS Decoding Architectures 83 6.2.1 Problem in Fully Parallel MEA Architecture 83 6.2.2 Problem in Direct Folding MEA Architecture 84 6.3 Proposed Just-in-Time Folding Modified Euclidean Algorithm 85 6.3.1 Pre-calculation Scheme (PCS) 85 6.3.2 Just-in-Time Folding Modified Euclidean Algorithm 86 6.4 Just-in-Time Folding Modified Euclidean Architecture 88 6.5 Chip Implementation and Comparison 91 6.6 Summary 96 Chapter 7 Conclusions and Future Researches 97 7.1 Conclusions 97 7.1.1 Comparison of Performance 98 7.2 Future Researches 100 7.2.1 Self-Checking Reed-Solomon Codec 100 7.2.2 Fault-Tolerate Reed-Solomon Codec 101 Bibliography 103 Publication List 113 Awards 1162107888 bytesapplication/pdfen-US里德所羅門碼可重規劃性Reed-Solomon CodeReconfigurablethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/57617/1/ntu-95-D90943010-1.pdf