UNIVERSITY OF MINNESOTA This is to certify that I have examined this copy of a doctoral thesis by Tong Zhang and have found that it is complete and satisfactory in all respects, and that any and all revisions required by the final examining committee have been made. Keshab K. Parhi Name of Faculty Advisor Signature of Faculty Advisor Date GRADUATE SCHOOL Efficient VLSI Architectures for Error-Correcting Coding A THESIS SUBMITTED TO THE FACULTY OF THE GRADUATE SCHOOL OF THE UNIVERSITY OF MINNESOTA BY Tong Zhang IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Keshab K. Parhi, Advisor July 2002 (cid:176)c Tong Zhang 2002 Acknowledgments First of all, I wish to thank my advisor, Professor Keshab K. Parhi, for his guidance andsupportthroughallstagesofmystudiesandresearchattheUniversityofMinnesota. Iamverygratefulforhisrecognition,hisinspiration,andtheexposureandopportunities that I have received during the course of my study. I also would like to thank Professor Georgios Giannakis, Professor Mos Kaveh, Pro- fessor Pen-Chung Yew, Professor John Kieffer, Professor Larry Kinney for their support as members of my Ph.D. committee. I would like to express my thanks to the Army Research Office (grant numbers DA/DAAG55-98-1-0315 and DA/DAAD19-01-1-0705) for supporting this research. Mythanksalsogotothemembersofourgroup,particularly,ZhongfengWang,Zhipei Chi, Leilei Song and Jun Jin Kong for many useful discussions during the course of the work. This thesis is dedicated to my wonderful family. I am forever grateful to my parents, myparents-in-law, mywife, andmybrothersfortheirlove, support, andencouragement. I shall not try to put my appreciation and love for them into words. i Abstract This thesis is devoted to several efficient VLSI architecture design issues in error- correcting coding, including finite field arithmetic, (Generalized) Low-Density Parity- Check (LDPC) codes, and Reed-Solomon codes. A systematic low-complexity bit-parallel finite field multiplier design approach is pro- posed. ThisdesignapproachisapplicabletoGF(2m)constructedbyarbitraryirreducible polynomials. It effectively exploits the spatial correlation in the bit-parallel finite field multiplication to reduce the hardware complexity. A systematic low-complexity design approach for modified bit-parallel multiplier that is desirable for GF(2m) constructed by high-Hamming weight irreducible polynomials is also proposed. For the hardware implementation of LDPC code decoder, the finite precision analysis is performed to develop a quantization scheme considering the tradeoff between hard- warecomplexityandLDPCcodeerror-correctingcapability. Ajoint(3,k)-regularLDPC code and codec design approach is proposed to develop good (3,k)-regular LDPC codes that exactly fit to high-speed partly parallel decoder and low-complexity encoder imple- mentations. A modified joint design approach is proposed to further reduce the decoder hardware complexity for those high-rate (3,k)-regular LDPC codes applied to silicon area critical applications. To demonstrate this joint design methodology, an FPGA (Field Programmable Gate Arrays) implementation of a (3,6)-regular LDPC partly par- allel decoder is realized using Xilinx virtex-E device. This decoder can achieve upto 54Mbps symbol decoding throughput and BER of 10−6 at 2dB over AWGN channel. Generalized Low-Density (GLD) Parity-Check has been proposed as an alternative to the product code. This thesis considers the practical GLD codec VLSI design. An approach is proposed to reduce the GLD encoding complexity, which can be effectively implemented using hardware/software codesign. It has been shown that Max-Log-MAP algorithm is a promising candidate decoding scheme for practical GLD coding systems by developing several techniques to reduce the GLD decoding complexity. A Berlekamp-Massey algorithm transformation is performed for high-speed errors- and-erasures RS decoder implementation. A regular hardware architecture is presented to implement the reformulated Berlekamp-Massey algorithm, and an operation schedul- ing scheme is proposed to reduce the hardware complexity without loss of speed. ii Contents 1 Introduction 1 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Summary of Motivations and Contributions . . . . . . . . . . . . . . . . . 2 1.2.1 Bit-Parallel Finite Field Multiplier VLSI Design . . . . . . . . . . 2 1.2.2 LDPC Codec VLSI Architecture Design and Implementation . . . 3 1.2.3 GLD Codec VLSI Architecture Design . . . . . . . . . . . . . . . . 4 1.2.4 Reed-Solomon Decoder Architecture VLSI Design . . . . . . . . . 4 1.3 Outline of The Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Systematic Low-Complexity Design of Finite Field Multipliers 7 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Notation and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Mastrovito Multiplier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.1 Proposed Theorem and Algorithm . . . . . . . . . . . . . . . . . . 13 2.3.2 Multiplier Architecture . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Modified Mastrovito Multiplier . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.1 Proposed Theorem and Algorithm . . . . . . . . . . . . . . . . . . 21 2.4.2 Multiplier Architecture . . . . . . . . . . . . . . . . . . . . . . . . 25 iii 2.5 Special Irreducible Polynomials . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5.1 m ≥ k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2 s 2.5.2 Trinomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5.3 Pentanomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.4 ESP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 APPENDIX 2.A: Proof of Theorem 2.3.1 . . . . . . . . . . . . . . . . . . . . . 42 APPENDIX 2.B: Proof of Theorem 2.4.2 . . . . . . . . . . . . . . . . . . . . . 47 3 Low-Density Parity-Check Code Decoder/Encoder Design 51 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2 LDPC Code Decoding Algorithm . . . . . . . . . . . . . . . . . . . . . . . 53 3.3 Finite Precision Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.1 Quantization of Received Data . . . . . . . . . . . . . . . . . . . . 55 3.3.2 Quantization of α and β . . . . . . . . . . . . . . . . . . . . 56 m,n m,n 3.3.3 Simulation Results Summary . . . . . . . . . . . . . . . . . . . . . 58 3.4 Joint (3,k)-Regular LDPC Code and Decoder/Encoder Design . . . . . . 60 3.4.1 Preliminary Background . . . . . . . . . . . . . . . . . . . . . . . . 61 3.4.2 Joint Design Methodology . . . . . . . . . . . . . . . . . . . . . . . 63 3.4.3 Construction of H and H . . . . . . . . . . . . . . . . . . . . . . 65 0 1 3.4.4 (2,k)-Regular LDPC Decoder Architecture . . . . . . . . . . . . . 67 3.4.5 (3,k)-Regular LDPC Decoder Architecture . . . . . . . . . . . . . 70 3.4.6 Design Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.4.7 Systematic Efficient-Encoding Scheme . . . . . . . . . . . . . . . . 77 3.5 Modified Joint Design for High-Rate Applications . . . . . . . . . . . . . . 80 iv 3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 APPENDIX 3.A: Proof of Theorem 3.4.1 . . . . . . . . . . . . . . . . . . . . . 87 4 An FPGA Implementation of (3,6)-Regular Low-Density Parity-Check Code Decoder 92 4.1 Remarks on Original Decoder Architecture . . . . . . . . . . . . . . . . . 93 4.2 Partly Parallel Decoder Architecture . . . . . . . . . . . . . . . . . . . . . 94 4.2.1 Check node processing . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.2.2 Variable node processing . . . . . . . . . . . . . . . . . . . . . . . . 103 4.2.3 CNU and VNU Architectures . . . . . . . . . . . . . . . . . . . . . 105 4.2.4 Data Input/Output . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.3 FPGA Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5 Generalized Low-Density (GLD) Parity-Check Code Codec Design 113 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.2 GLD Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.3 GLD Code Encoder Design . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.3.1 A Class of Efficient-Encoding GLD Codes . . . . . . . . . . . . . . 117 5.3.2 Hardware/Software Codesign of GLD Encoder . . . . . . . . . . . 122 5.4 GLD Code Decoder Design . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.4.1 Max-Log-MAP Decoding of Linear Binary Block Codes . . . . . . 125 5.4.2 An Earlier Stopping Criterion for GLD decoding . . . . . . . . . . 127 5.4.3 Normalized Max-Log-MAP Decoding . . . . . . . . . . . . . . . . . 128 5.4.4 Complexity Reduction Techniques . . . . . . . . . . . . . . . . . . 130 5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 v 6 High-SpeedVLSIArchitectureofErrors-and-ErasuresCorrectingReed- Solomon Decoders 137 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.2 RS Codes Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.3 Berlekamp-Massey Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.4 High-Speed RS Decoder Architecture . . . . . . . . . . . . . . . . . . . . . 142 6.4.1 Reformulated BM Algorithm . . . . . . . . . . . . . . . . . . . . . 143 6.4.2 Decoder Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 7 Conclusions and Future Research Directions 152 7.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 7.2 Future Research Directions . . . . . . . . . . . . . . . . . . . . . . . . . . 153 Bibliography 155 vi List of Figures 2.1 Tree structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 General Mastrovito Multiplier Architecture. . . . . . . . . . . . . . . . . . 20 2.3 Tree structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 General Modified Mastrovito Multiplier Architecture.. . . . . . . . . . . . 29 2.5 Hybrid Tree Computation Scheme. . . . . . . . . . . . . . . . . . . . . . . 37 3.1 Tanner-graph based fully parallel decoder structure. . . . . . . . . . . . . 55 3.2 Finite precision simulations with various quantization schemes of received data for (a) N=1020 and (b) N=4092, where solid lines correspond to the 3:1scheme, dashanddashdotlinesforthe5:3and4:2schemes, respectively. 56 3.3 Curve of function f(x) (x > 0). . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Finiteprecisionsimulationswithvariousquantizationschemesofextrinsic information for (a) N=1020 and (b) N=4092, where q = 6, solid lines correspond to 6:3 scheme and dash dot lines for the variable precision quantization scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.5 Infinite precision vs. finite precision simulations for (a)(c) N=1020 and (b)(d)N=4092,wheresolidlinescorrespondtoinfinitecase,dashdotlines for the finite case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.6 Code and decoder/encoder joint design flow diagram.. . . . . . . . . . . . 64 3.7 Structure of submatrices H and H . . . . . . . . . . . . . . . . . . . . . . 65 0 1 vii