簡易檢索 / 詳目顯示

回結果列表
研究生： 陸永馗
Lu, Yung-Kuei
論文名稱： 高速且低複雜度之硬決定與軟決定里德所羅門解碼器架構設計
High-Speed and Low-Complexity Architecture Designs for Hard-Decision/Soft-Decision Reed-Solomon Decoding
指導教授： 謝明得
Shieh, Ming-Der
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2012
畢業學年度： 100
語文別： 英文
論文頁數： 105
中文關鍵詞： 柏利肯－梅西演算法 、通道解碼器 、歐幾里德演算法 、里德所羅門碼 、超大型積體電路架構
外文關鍵詞： Berlekamp-Massey algorithm, Channel decoder, Euclidean algorithm, Reed-Solomon codes, VLSI architecture
相關次數： 點閱：83  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 　　里德所羅門碼對叢集錯誤具有傑出的更正能力，故常被用於數位通訊及儲存系統之中。為滿足系統的需求，多種基於熟知的硬決定及軟決定解碼演算法所設計之解碼器架構也應運而生。然而至今，如何以較少的硬體成本設計出高效能的解碼器一直都是很重要的議題。
    　　本論文首先提出我們所開發之高效能硬決定解碼演算法及其對應之解碼器架構。此設計之主要特色在於能藉由錯誤位置多項式及錯誤估測多項式的重新編組，有效地移除在傳統歐幾里德演算法(Euclidean algorithm)下發展之架構中的冗餘資訊，進而減少硬體架構中所需之處理單元的數目，及提高整體的硬體使用率。基於此演算法，本論文亦提出一適用於光纖通訊系統之解碼器設計。相對於現今其他的設計方案，此設計在效能與成本方面都具有最佳的效益。
    　　此外，本論文對於另一種常用的柏利肯－梅西演算法(Berlekamp-Massey algorithm)亦有所探討。文中提出了一組有別於大家對此演算法所熟知的初始值設定，而這項新的設定方式不僅有助於降低硬體的複雜度及功耗，同時也間接支持了柏利肯－梅西演算法與歐幾里德演算法是等效的論點。
    　　當然，考量在某些應用的系統下，需要同時具有多組不同的里德－所羅門碼之解碼功能，我們也提出一個有效的解決方案。此方案是以單一硬體架構實現多重模式運作的解碼器設計，其富彈性的可調式機制，足以因應系統在不同通道環境下的需求。此多重模式解碼器可在不犧牲效能的前題下，運用於於絶大多數的應用中；此外，透過我們所發展的無係數擇器之硬體配置方式，使架構上具有定位取值的特性，有效排除於傳統多重模式設計時所需的切換電路，進而避免產生複雜的繞線問題。本設計不僅具有低成本的優點，更能因其架構簡單且有高度的規則性而利於硬體的實現。
    　　最後，為了進一步提昇編碼增益，我們提出了有效的設計方案－高速低成本之軟決定里德所羅門碼解碼器。相較於其他設計，此解碼器能藉由獨創的決策機制，在與其他設計相似的解碼效能下，有效地減少時間及計算複雜度。在速度與硬體複雜度上，本設計較其他方案具有較佳的速度與面積優勢。
    　　由實驗結果顯示，本論文所提出之架構均擁有高速且低成本的特點。因此，綜合上述所言，這些設計提供了優異的效能解決方案，能有效地適用於實際的應用系統。

    Reed-Solomon (RS) codes are commonly used error correcting codes in digital communication and storage systems due to their powerful capability of correcting burst errors. Various hard-decision and soft-decision RS decoders have been proposed to meet the throughput requirement. Decoders with high throughput rates and low complexity are highly desirable.
    In this dissertation, a high-performance Euclidean algorithm, called the ME-R algorithm, for hard-decision decoding is first presented. A high-speed low-complexity architecture based on the ME-R algorithm is then developed. The low-complexity feature of the proposed architecture is obtained by reformulating the error locator and error evaluator polynomials to remove redundant information in the modified Euclidean (ME) algorithm. This efficiently increases the hardware utilization of the processing elements (PEs) used to solve the key equation and significantly reduces the number of required PEs. Based on the ME-R algorithm, an optimal RS decoder for optical communication systems is introduced. Compared to related works, the proposed decoder has the lowest area requirement and smallest area-time complexity.
    A new initial setting of the Berlekamp-Massey (BM) algorithm is also presented. The new initialization leads to a more cost-effective and power-saving architecture compared to the original one. Moreover, the initialization scheme can be used to demonstrate the equivalence of the BM algorithm and the Euclidean algorithm.
    In some applications, there are various RS codes within a system. A multi-mode RS decoder that provides a flexible and unified solution to support various levels of error-correcting capability is presented in this dissertation. The proposed multi-mode decoder can be reconfigured or programmed to decode different RS codes instead of employing a separate decoder for each code. The developed coefficient-selector-free multi-mode arrangement makes the decoder area-efficient and gives it a very simple and regular interconnect topology, making the decoder suitable for VLSI realization.
    Finally, to improve coding gain, an efficient soft-decision RS decoder that has a higher error-correcting capability than that of a conventional hard-decision decoder is proposed. With the proposed decision-making scheme, the complexity of the Chase algorithm can be greatly reduced with comparable error correcting performance. In addition, the proposed architecture has advantages in speed and area.
    Experimental results show that the developed architectures can efficiently lower the hardware requirement and achieve a high throughput rate. The proposed designs are thus very flexile, cost-effective solutions for practical applications.

    TABLE OF CONTENTS vi LIST OF FIGURES ix LIST OF TABLES xi 1 Introduction 1 1.1 Motivation 2 1.2 Organization 5 2 Reed-Solomon Codes 7 2.1 Finite Fields 8 2.2 The Generator Polynomial Approach to Reed-Solomon Codes 9 2.2.1 Encoding of Reed-Solomon Codes 9 2.2.2 Decoding of Reed-Solomon Codes 11 2.3 Hard-Decision Decoding Algorithms 13 2.3.1 Peterson-Gorenstein-Zierler Algorithm 13 2.3.2 Berlekamp-Massay Algorithm 15 2.3.3 Guruswami-Sudan List Decoding Algorithm 20 2.4 Soft-Decision Decoding Algorithms 22 2.4.1 Generalized Minimum Distance Algorithm 22 2.4.2 Chase Algorithm 23 2.4.3 Koetter-Vardy Algorithm 24 3 High-Performance Architecture for Reed-Solomon Decoders 25 3.1 Proposed Reformulated Modified Euclidean Algorithm 26 3.1.1 Truong’s ME algorithm 26 3.1.2 Reformulation of the ME-T Algorithm 28 3.2 Proposed High-Speed and Low-complexity Architecture 33 3.2.1 Basic Cell Design and Boundary Cell Simplification 33 3.2.2 High-Speed and Low-Complexity KES Architecture 36 3.2.3 SC unit 37 3.2.4 CSEE Unit 37 3.3 Performance Evaluation and Comparison 38 3.3.1 Complexity Analysis 38 3.3.2 Experimental Results and Comparisons 42 3.4 Application: Area-Efficient Reed-Solomon Decoder for Optical Communication Systems 45 3.4.1 Folding ME-R Algorithm and Low-Complexity KES Architecture 46 3.4.2 Hardware Utilization 48 3.4.3 Experimental Results and Comparisons 49 3.4.4 High-throughput Optical Communication Systems 52 3.4.5 Low-Complexity Architecture Based on the RiBM Algorithm 53 3.5 New Initial Settings of the Berlekamp-Massey Algorithm 56 3.5.1 Berlekamp Algorithm 56 3.5.2 New Initial Setting 57 3.5.3 Cost-effective Architecture 57 3.6 Summary 60 4 Design of Efficient Reed-Solomon Decoders for Multi-Mode Applications 61 4.1 Multi-Mode Encoding/Decoding of Reed-Solomon Codes 62 4.2 Architecture of Multi-Mode RS Decoders 63 4.2.1 Multi-Mode Key Equation Solver Design 64 4.2.2 Multi-Mode Syndrome Computation Unit 70 4.2.3 Multi-Mode Chien Search & Error Evaluation Unit 72 4.2.4 Multi-Mode RS Decoder 74 4.3 Performance Evaluation and Comparison 76 4.3.1 Complexity Analysis 76 4.3.2 Experimental Results and Comparisons 77 4.3.3 Feasible Application Ranges 80 4.3.4 Multi-mode RS Decoder Generator 81 4.3.5 Multi-mode Structure of Errors-and-Erasures Decoders 82 4.4 Summary 83 5 Area-Efficient Architecture for Soft-Decision Reed-Solomon Decoding 84 5.1 Reduced-complexity Chase Algorithm 85 5.1.1 Fast Decision-making Scheme 85 5.1.2 Proposed Low-Complexity Algorithm for Soft-Decision Decoding 86 5.2 Area-efficient Hardware Architecture 90 5.2.1 Key Equation Solver Unit 91 5.2.2 Syndrome Re-calculation Unit 92 5.2.3 Decision-making Unit 92 5.2.4 Pipelining Strategy 93 5.3 Performance Evaluation and Comparison 94 5.4 Summary 95 6 Conclusion and Future Works 97 6.1 Conclusion 97 6.2 Future Works 98 Bibliography 100

    [1]S. B. Wicker and V. K. Bhargava, Reed-Solomon Codes and Their Applications, IEEE Press, New York, 1994.
    [2]J. L. Massey, “Shift-register synthesis and BCH decoding,” IEEE Trans. Inform. Theory, vol. IT-15, no. 1, pp. 122-127, Jan. 1969.
    [3]H. C. Chang, C. B. Shung, and C. Y. Lee, “A Reed-Solomon product-code (RS-PC) decoder chip for DVD applications,” IEEE J. Solid-State Circuits, vol. 36, no. 2, pp. 229-238, Feb. 2001.
    [4]D. V. Sarwate and N. R. Shanbhag, “High-speed architectures for Reed-Solomon decoders,” IEEE Trans. VLSI Syst., vol. 9, no. 5, pp. 641-655. Oct. 2001.
    [5]H. M. Shao, T. K. Truong, L. J. Deutsch, J. H. Yuen, and I. S. Reed, “A VLSI design of a pipeline Reed-Solomon decoder,” IEEE Trans. Comput., vol. C-34, no. 5, pp. 393-402, May 1985.
    [6]T. K. Truong, J. H. Jeng, and T. C. Cheng, “A new decoding algorithm for correcting both erasures and errors of Reed-Solomon codes,” IEEE Trans. Commun., vol. 51, no. 3, pp.381-388, Mar. 2003.
    [7]Y. W. Chang, T. K. Truong, and J. H. Jeng, “VLSI architecture of modified Euclidean algorithm for Reed-Solomon code,” ELSEVIER J. Inform. Sciences, vol. 155, pp. 139-150, May 2003.
    [8]H. Lee, “High-speed VLSI architecture for parallel Reed-Solomon decoder,” IEEE Trans. VLSI Syst., vol. 11, no. 2, pp. 288-294, Apr. 2003.
    [9]S. Lee, H. Lee, J. Shin and J. S. Ko, “A High-speed pipelined degree-computationless modified Euclidean algorithm architecture for Reed-Solomon decoder,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS’2007), pp. 901-904, May 2007.
    [10]J. H. Baek and M. H. Sunwoo, “New degree computationless modified Euclidean algorithm and architecture for Reed-Solomon decoder,” IEEE Trans. VLSI Syst., vol. 14, no. 8, pp. 915-920. Aug. 2006.
    [11]J. H. Baek and M. H. Sunwoo, “Simplified degree computationless modified Euclid’s algorithm and its architecture,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS’2007), pp. 905-908, May 2007.
    [12]J. H. Baek and M. H. Sunwoo, “Enhanced degree computationless modified Euclid’s algorithm for Reed-Solomon decoders,” IET Electronics Letter, vol. 43, no. 3, Feb. 2007.
    [13]H. Lee, “A High-speed low-complexity Reed-Solomon decoder for optical communications,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 52, no. 8, pp. 461-465, Aug. 2005.
    [14]H. Y. Hsu, A. Y. Wu and J. C. Yeo, “Area-efficient VLSI design of Reed-Solomon decoder for 10GBase-LX4 optical communication systems,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 43, no. 4, pp. 1019-1027, Nov. 2006.
    [15]R. J. McEliece, The Theory of Information and Coding: A Mathematical Framework for Communication, Addison-Wesley, MA, 1977.
    [16]C. H. Wu, C. M. Wu, M. D. Shieh and Y. T. Hwang, “High-speed, low-complexity systolic designs of novel iterative division algorithms in GF(2m),” IEEE Trans. Comput., vol. 53, no. 3, pp. 375-380, Mar. 2004.
    [17]Artisan Components, TSMC 0.18-m Process 1.8-Volt SAGE-XTM Standard Cell Library Databook, Sunnyvale, CA, 2003.
    [18]W. Liu, J. Rho, and W. Sung, “Low-power high-throughput BCH error correction VLSI design for multi-level cell NAND flash memories,” in Proc. IEEE Workshop on Signal Process. Syst .(SIPS '06), pp. 303-308, Oct. 2006.
    [19]B. Yuan, Z. F. Wang, L. Li, M. L. Gao, J. Sha, and C. Zhang, “Area-efficient Reed-Solomon decoder design for optical communications,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 56, no. 6, pp. 469-473, June 2009.
    [20]I. S. Reed, M. T. Shih, and T. K. Truong, “VLSI design of inverse-free Berlekamp–Massey algorithm,” Proc. IEE pt. E, vol. 138, pp. 295–298, Sept. 1991.
    [21]R. E. Blahut, Theory and Practice of Error-Control Codes. Reading, Addison-Wesley, MA, 1983.
    [22]E. R. Berlekamp, Algebraic Coding Theory. McGraw-Hill, New York, 1968. (revised ed.—Laguna Hills, Aegean Park, CA, 1984).
    [23]T. K. Truong, J. H. Jeng, and T. C. Cheng, “A new decoding algorithm for correcting both erasures and errors of Reed-Solomon codes,” IEEE Trans. Commun., vol.51, no.3, pp.381-388, Mar. 2003.
    [24]A. Raghupathy, and K. J. R. Liu, “Algorithm-based low-power/high-speed Reed-Solomon decoder design,” IEEE Trans. Circuits Syst. II - Analog and Digital Signal Processing, vol.41, no.11, pp.1254-1270, Nov. 2000.
    [25]T. Park, “Design of the (248,216) Reed-Solomon decoder with erasure correction for Blu-ray disc,” IEEE Trans. Consumer Electronics, vol.51, no.3, pp.872-878, Aug. 2005.
    [26]M. D. Shieh, Y. K. Lu, S. M. Chung, and J. H. Chen, “Design and implementation of efficient Reed-Solomon decoders for multi-mode applications,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS’2006), Kos, Greece, pp.289-292, May 2006.
    [27]Telecommunication Standardization Section, International Telecom. Union, “Forward error correction for submarine systems,” ITU, Geneva, Switzerland, ITU-T Recommendation G.975, Oct. 2000.
    [28]G. Jr. Forney, “On decoding BCH codes,” IEEE Trans. Inf. Theory, vol.IT-11, no.4, pp. 549-557, Oct. 1965.
    [29]Y. K. Lu, M. D. Shieh, and C. M. Wu, “Low-complexity Reed-Solomon decoder for optical communications,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS’2010), Paris, France, pp.4173-4176, May 2010.
    [30]Y. K. Lu, M. D. Shieh, “High-speed low-complexity architecture for Reed-Solomon decoder,” IEICE Trans. Inf. Syst., vol.E93-D, no.7, pp. 1824-1831, Jul. 2010.
    [31]U. Ladebusch and C. A. Liss, “Terrestrial DVB (DVB-T): A broadcast technology for stationary portable and mobile use,” IEEE Proceedings, vol. 94, no. 1, pp. 183-193, Jan. 2006.
    [32]A. A. El-Azm and J. Kasparian, “Designing a concatenated coding system for reliable satellite and space communications,” in Proc. IEEE Symp. Comput. Commun., pp. 364-369, July 1997.
    [33]R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley, Taipei, 1983.
    [34]S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Prentice-Hill, New Jersey, 1983.
    [35]R. E. Blahut, “A universal Reed-Solomon decoder,” IBM J. Research and Development, vol. 28, no. 2, pp. 150-158, Mar. 1984.
    [36]Y. R. Shayan and T. Le-Ngoc, “A cellular structure for a versatile Reed-Solomon decoder,” IEEE Trans. Comput., vol. 46, no. 1, pp. 80-85, Jan. 1997.
    [37]W. Wilhelm, “A new scalable VLSI architecture for Reed-Solomon decoder,” IEEE J. Solid-State Circuits, vol. 34, no. 3, pp. 388-396, Mar. 1999.
    [38]S. Kwon and H. Shin, “An area-efficient VLSI architecture of A Reed-Solomon decoder/encoder for digital VCRs,” IEEE Trans, Consum. Electron., vol. 43, no. 4, pp. 1019-1027, Nov. 1997.
    [39]L. Song, M. L. Yu, and M. S. Shaffer, “10- and 40-Gb/s forward error correction devices for optical communications,” IEEE J. Solid-State Circuits, vol. 37, no. 11, pp. 1565-1573, Nov. 2002.
    [40]J. C. Huang, C. M. Wu, M. D. Shieh, and C. H. Wu, “An area-efficient versatile Reed-Solomon decoder for ADSL,” in Proc. IEEE Int. Symp. Circuits Syst., pp. 517-520, May 1999.
    [41]H. Y. Hsu and A. Y. Wu, “VLSI design of a reconfigurable multi-mode Reed-Solomon codec for high-speed communication systems,” in Proc. IEEE Asia-Pacific Conf. ASIC, pp.359-362, Aug. 2002.
    [42]K. Seki, K. Mikami, M. Baba, N. Shinohara, S. Suzuki, and H. Tezuka, “Single-chip 10.7 Gb/s FEC CODEC LSI using time-multiplexed RS decoder,” in Proc. IEEE Conf. Custom Integr. Circuits, pp. 289–292, May 2001.
    [43]H. Lee, “An area-efficient Euclidean algorithm block for Reed-Solomon decoder”, in Proc. IEEE Computer Society Annual Symp. VLSI (ISVLSI), pp.209-210, Feb. 2003.
    [44]ITU-T Recommendation G.992.1, Asymmetrical Digital Subscriber Line (ADSL) Transceivers, July 1999.
    [45]ATSC Standard A/53, ATSC Digital Television Standard, Jan. 2007.
    [46]Recommendation for Space Data System Standards, TM Synchronization and Channel Coding, Blue Book CCSDS 131.0-B-1, Sep. 2003.
    [47]H.Y. Hsu, J.C. Yeo, and A.Y. Wu, “Multi-symbol-sliced dynamically reconfigurable Reed-Solomon decoder design based on finite-field processing element,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol.14, no.5, pp.489-500, May 2006.
    [48]F. K. Chang, C. C. Lin, H. C. Chang, and C. Y. Lee, “Universal architectures for Reed-Solomon error-and-erasure decoder,” in Proc. IEEE Asia Solid State Circuits Conf. (ASSCC), pp. 125-128, Nov. 2005.
    [49]Y. R. Shayan, T. Le-Ngoc, and V. K. Bhargava, “A versatile time-domain Reed-Solomon decoder,” IEEE J. Sel. Areas Commun., vol. 8, no. 8, Oct. 1990.
    [50]R. Koetter and A. Vardy, “Algebraic soft-decision decoding of Reed-Solomon codes,” IEEE Trans. Info. Theory, vol. 49, no. 11, pp.2809-2825, Feb. 2003.
    [51]J. Jiang and K. Narayanan, “Algebraic soft-decision decoding of Reed-Solomon codes using bit-level soft information,” IEEE Trans. Info. Theory, vol. 54, no. 9, pp. 3907-3928, Sep. 2008.
    [52]J. Bellorado and A. Kavcic, “Low-complexity soft-decoding algorithms for Reed-Solomon codes - Part I: An algebraic soft-in hard-out Chase decoder,” IEEE Trans. Info. Theory, vol. 56, no. 3, pp. 945-959, Mar. 2010.
    [53]K. Lee and M. O’Sullivan, “An interpolation algorithm using Grobner bases for soft-decision decoding of Reed-Solomon codes,” in Proc. of IEEE Intl. Symp. on Info. Theory, pp. 2032-2036, Seattle, WA, Jul. 2006.
    [54]X. Zhang, Y. Zheng and Y. Wu, “A Chase-type Koetter-Vardy Algorithm for soft-decision Reed-Solomon decoding,” in Proc. Intl. Conf. on Computing, Networking and Commun., Feb. 2012.
    [55]J. Zhu and X. Zhang, “Backward interpolation architecture for algebraic soft-decision Reed-Solomon decoding,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 17, no. 11, pp. 1602-1615, Nov. 2009.
    [56]H. O’Keeffe and P. Fitzpatrick, “Grobner basis solutions of constrained interpolation problems,” Linear Algebra Appl., vol. 351-352, pp. 533-551, 2002.
    [57]R. Keotter, J. Ma and A. Vardy, “The re-encoding transformation in algebraic list-decoding of Reed-Solomon codes,” IEEE Trans. Info. Theory, vol. 57, no. 2, pp. 633-647, Feb. 2011.
    [58]C. H. Hsu, Y. M. Lin, H. C. Chang and C. Y. Lee, “A 2.56 Gb/s soft RS (255,239) decoder chip for optical communication systems,” in Proc. ESSCIRC (ESSCIRC), pp. 79-82, Sep. 2011.
    [59]V. Guruswami and M. Sudan, "Improved decoding of Reed-Solomon and algebraic-geometric codes,” IEEE Trans. Info. Theory, vol. 45, no. 9, pp.1755-1764, Sep. 1999.
    [60]G. D. Forney, “Generalized minimum distance decoding,” IEEE Trans. Inform. Theory, vol. 12, no. 2, pp. 125-131, Apr. 1966.
    [61]J. L. Dornstetter, “On the equivalence between Berlekamp’s and Euclid’s algorithms,” IEEE Trans. Info. Theory, vol. IT-33, no.3, pp. 428-431, Feb. 1987.
    [62]Y. M. Lin, Y. C. Huang, C. H. Yang, and H. C. Chang, “A 30K 2.5Gb/s decision-eased soft RS (224, 216) decoder for wireless systems,” in Proc. Integrated Circuits (ISIC), pp. 164-167, Sep. 2011.
    [63]Y. Sugiyama, M. Kasahara, S. Hirasawa, and T. Namekawa, “A method for solving key equation for Goppa codes,” Inf. and Control, vol. 27, no. 1, pp. 87-99, Jan. 1975.
    [64]H. Tang, Y. Liu, M. Fossorier, and S. Lin, “On combining Chase-2 and GMD decoding algorithms for nonbinary block codes,” IEEE Commun. Letters, vol. 5, no. 5, pp. 209 –211, May 2001.
    [65]S. H. Kang and I. C. Park, “Loosely coupled memory-based decoding architecture for low density parity check codes,” IEEE Trans. Circuits Syst. I, vol.53, no.5, pp.1045-1056, May 2006.
    [66]D. Chase, “A Class of Algorithms for Decoding Block Codes with Channel Measurement Information,” IEEE Trans. Inform. Theory, vol. 18, pp. 170-182, Jan. 1972.

    下載圖示 校內：2017-08-31公開
    校外：2017-08-31公開
    QR CODE