Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/8885
標題: 應用於高傳輸量光纖通訊系統之結合RS和LDPC解碼器VLSI實作
VLSI implementation of high throughput combined RS and LDPC decoders for optical communications
作者: 姚長昆
Yao, Chang-Kun
關鍵字: LDPC;低密度同位元查核碼;RS;Reed-Solomon;VLSI;optical;里德索羅門碼
出版社: 電機工程學系所
引用: [1] T. Koonen, “Fiber to the Home/Fiber to the Premises: What, Where, and When?,” Proceeding s of the IEEE, vol. 94, no. 5, pp. 911-934, May 2006. [2] H. M. Shao, T. K. Truong, L. J. Deutsch, J. H. Yuen, and I. S. Reed, “A VLSI design of pipeline Reed-Solomon decoder,” IEEE Trans. Comput., vol. C-34, no. 5, pp.393-403, May 1985. [3] R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, Jan. 1962. [4] IEEE Draft Standard for Information Technology-Telecommunications and information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements-Part 11: Wireless LAN Medium Amendment : Enhancements for Higher Throughput, Feb. 2007, IEEE Std. 802.11n. [5] IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1, Feb. 2006, IEEE Std. 802.16e. [6] IEEE Standard for Information Technology-Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements-Part 3: Carrier Sense Multiple Access With Collision Detection Access Method and Physical Layer Specifications, Sep. 2006, IEEE Std. 802.3an. [7] T. Richardson, “Error floors of LDPC codes,” in Proc. Allerton Conf. Commun., Control, Computing, Monticello, IL, pp. 1426-1435, Oct. 2003. [8] L. Sun, H. Song, and B. V. K. V. Kumar, “Error floor investigation and girth optimization for certain types of low-density parity check codes,” in Proc IEEE ICASSP, pp. 1101-1104, Mar. 2005. [9] Y. Miyata, K. Kubo, H. Yoshida, and T. Mizuochi, “Proposal for frame structure of optical channel transport unit employing LDPC codes for 100 Gb/s FEC,” Optical Fiber Communications, pp. 1-3, Mar. 2009. [10] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electron. Lett., vol. 32, no. 18, pp. 1645-1646, Aug. 1996. [11] N. Wiberg, “Codes and Decoding on General Graphs,” Ph.D. thesis, Linkoping University, Sweden, 1996. [12] D. J. C. MacKay, “Gallager codes that are better than turbo codes,” in Proc. 36th Allerton Conf. Communications, Control, and Computing, Sept. 1998. [13] E. M. Kurtas,A. V. Kuznetsov,I. Djurdjevic, “System perspectives for the application of structured LDPC codes to data storage devices,” IEEE Trans. On Magnetics, vol. 42, no. 2, Feb. 2006. [14] S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice Hall, 1983. [15] L. Chen, J. Xu, I. Djurdjevic, and S. Lin, “Near Shannon limit Quasi-Cyclic Low Density Parity Check Codes,” IEEE Trans. On Communications, vol. 52, no.7, July 2004. [16] J. L. Membe and J. M. F. Moura, “Partition and shift LDPC codes,” IEEE Trans. On Magnetics, vol.41, no. 10, Oct. 2005. [17] T. J. Richardson and R. L. Urbande, “Efficient encoding of low density parity check codes,” IEEE Trans. Inform. Theory, vol. 47, pp. 638-656, Feb. 2001. [18] F. R. Kshischang and B. J. Frey, “Iterative decoding of compound codes by peobability propagation in graphical models,” IEEE Journal on Selected Areas in Communications, vol. 16, pp.219-230, Feb. 1998. [19] J. Hagenauer, E. Offer, L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. On Inform. Theory, vol. 42, no. 2, pp.429-445, March 1996. [20] X. Y. Hu, E. Eleftheriou, D, M. Arnold, A. Dholakia, “Efficient implementations of the sum-product algorithm for decoding LDPC codes,” in Proc. IEEE Global Telecommunications Conf., vol. 2, pp. 1036, Nov. 2001. [21] M. P. C. Fossorier, M. Mihaljevic, H. Imai, “Reduced complexity iterative decoding of low density parity check codes based on belief propagation,” IEEE Trans. On Communications, vol. 47, no. 5, pp. 673-680 May 1999. [22] J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier and X.-Y. Hu, ”Reduced complexity decoding of LDPC codes” IEEE Trans. On Communications, vol. 53, pp. 1288-1299 Aug. 2005. [23] A. Anastasopoulos, “A coparison between the sum-product and the min-sum iterative detection algorithms based on dnsity evolution,” in Proc. IEEE Global Telecommunications Conf., vol. 2, pp. 1021-1015, Nov. 2001. [24] J. Chen, and M. P. C. Fossorier, “Near optimum universal belief propagation based decoding of low density parity check codes,” IEEE Trans. On Communications, vol. 50, no. 3, pp. 406-414 March 2002. [25] J. Chen, and M. P. C. Fossorier, “Density evolution for two improved BP-Based decoding algorithms of LDPC codes,” IEEE Communications Letters, vol. 6, no. 5, pp. 208-210 May 2002. [26] J. Zang, M. Fossorier, “Shuffled iterative decoding,” IEEE Trans. Commun., vol. 53, no. 2, pp. 209-213, Feb. 2005. [27] D. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC codes,” in Proc. IEEE Workshop on SiPS. pp. 107-112, Oct. 2004. [28] K. Zhang, X. Huang, Z. Wang, “High-Throughput layered decoder implementation for Quasi-Cyclic LDPC codes,” IEEE JSAC, vol. 27, no. 6, Aug.2009. [29] A. Blanksby and C. Howland, “A 690-mw 1-Gb/s 1024-b,rate-1/2 low-density parity-check code decoder,” IEEE J. Solid-State Circuits, vol. 37, no. 3, pp. 404–412, Mar. 2002. [30] E. Yeo, B. Nikolic and V. Anantharam, “Architectures and implementations of low-density parity check decoding algorithms,” in Proc. Midwest Symposium on Circuits and Systems, vol. 3, pp. 437-440, Aug. 2002. [31] M. M. Mansour and N. R. Shanbhag, “A 640-Mb/s 2048-bit programmable LDPC decoder chip,” IEEE J. Solid-State Circuits, vol. 41, pp. 684-698, Mar. 2006. [32] 陳後守, 邱茂清, 王忠炫, 吳昭明, “錯誤更正碼 (Error Correcting Codes),” 無線網路教學推廣中心(大 放異彩書局), June 2007. [33] S. Wei, “VLSI Architectures for Computing Exponentiations, Multiplicative Inverses and Divisions in GF(2m),” Proc. Int’l Symp. Circuits and Systems (ISCAS’94), pp. 203-206, 1994. [34] S.-M. Yen, “Improved normal basis inversion in GF(2m),” Electronics Letters, vol. 33, no. 3, 30th Jan. 1997. [35] S.-W. Wei, “VLSI Architectures for Computing Exponentiations, Multiplicative Inverses, and Divisions in GF(2m),” IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing, vol. 44, no. 10, pp. 847-855, Oct. 1997. [36] C.-L. Wang and J.-H. Guo, “New Systolic Arrays for C+AB2 , Inversion, and Division in GF(2m),” IEEE Trans. Computers, vol. 49, no. 10, pp. 1120-1125, Oct. 2000. [37] C.-H. Liu, “New efficient low-complexity architecture for performing inversion and divisions,” VLSI Technology Systems and Applications 2001., pp. 299-302, April 2001. [38] J.-H. Guo and C.-L. Wang, “Systolic Array Implementation of Euclid’s Algorithm for Inversion and Division in GF(2m),” IEEE Trans. Computers, vol. 47, no. 10, pp.1161-1167, Oct. 1998. [39] J.-H. Guo and C.-L. Wang, “Hardware-Efficient Systolic Architecture for Inversion and Division in GF(2m),” IEEE Proc. Computers and Digital techniques, pp. 272-278, 1998. [40] T. Zhou, X. Wu, G. Bai, and H. Chen, “New Algorithm and Fast VLSI Implementation for Modular Inversion in Galois Field GF(P)+,” IEEE 2002 International Conference on Communications, Circuits and Systems and West Sino Expositions, vol. 2, pp.1491-1495, July 2002. [41] Z. Yan and D. V. Sarwate, “Systolic Architectures for Finite Field Inversion and Division,” IEEE International Symposium on Circuits and Systems, vol. 5, pp. 789-792, May 2002. [42] Z. Yan and D. V. Sarwate, “New Systolic Architectures for Inversion and Division in GF(2m),” IEEE Trans. Computers, vol. 52, no. 11, pp. 1514-1519, Nov. 2003. [43] C.-L. Wang and J.-L. Lin, “A Systolic Architecture for Computing Inverses in Finite Fields GF(2m),” VLSI Technology, Systems and Applications, 1991., pp. 312-316, May 1991. [44] M. A. Hasan and V. K. Bhargava, “Bit-Serial Systolic Divider and Multiplier for Finite Fields GF(2m),” IEEE Trans. Computers, vol. 41, no. 8, pp. 972-980, Aug. 1992. [45] C.-L. Wang and J.-L. Lin, “A Systolic Architecture for Computing Inverses and Divisions in Finite Fields GF(2m),” IEEE Trans. Computers, vol. 42, no. 9, pp. 1141-1146, Sep. 1993. [46] R. Conway and J. Nelson, “Systolic Design of a new Finite Field Division/Inverse Algorithm,” International Conference on Application-Specific Array Processors, pp. 188-191, 1993. [47] A. Dur, “Avoiding decoder malfunction in the Peterson-Gorenstein-Zierler decoder,” IEEE Trans. Information Theory, vol. 39, pp. 640-643, March 1993. [48] M. Srinvasan, D. V. Sarwate, “Malfunction in the Peterson-Gorenstein-Zierler decoder,” IEEE Trans. Information Theory, vol. 40, pp. 1649-1653, Sep. 1994. [49] H. Burton, “Inversionless decoding of binary BCH codes,” IEEE Trans. Information Theory, vol. 17, pp. 464-466, Jul. 1971. [50] I. S. Reed and M. T. Shih, “VLSI design of inverse-free Berlekamp-Massey algorithm,” IEEE Proceedings –Computers and Digital Techniques, vol.138, no. 5, pp. 295-298, Sep. 1991. [51] H.-C. Chang and C. B. Shung, “New serial architecture for the Berlekamp Massey algorithm,” IEEE Trans. On Communications, vol. 47, pp. 481-483, Apr. 1999. [52] H. Lee, “An area-efficient Euclidean algorithm block for Reed-Solomon decoder, ” IEEE Computer Society Annual Symposium on VLSI, pp. 209-210, Feb. 2003. [53] 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,’’ IEEE ISCAS Proceedings, pp. 289– 292. 2006. [54] Y.-X. You, J.-X. Wang , F.-C. Lai and Y.-Z. Ye, ‘’VLSI design and implementation of high-speed RS(204,188) decoder,’’ IEEE 2002 International Conference Communications, Circuits and Systems and West Sino Expositions, vol. 1, pp. 82- 86 , July 2002. [55] H.Lee, ’’High speed VLSI architecture for Parallel Reed-Solomon Decoder’’, IEEE Trans.VLSI Integr. Syst., vol. 11, no. 2, pp. 288-294, Apr. 2003 [56] Sung-Woo, S.-S. Choi and H. Lee, ’’RS decoder architecture for UWB,’’ International Conference Advanced Communication Technology ICACT., vol.1, pp.805-808, Feb. 2006. [57] T. K. Truong, J. H. Jeng and I. S. Reed, “Fast algorithm for computing the roots of error locator polynomials up to degree 11 in Reed-Solomon decoder,” IEEE Trans. On Communications, vol. 49, no. 5, pp. 779-783, May 1999. [58] H. Lee, “A high-speed low complexity Reed-Solomon decoder for optical communications,” IEEE Trans. Circuits and System II, Exp. Briefs, vol. 52, no. 8, pp.461-465, Aug. 2005. [59] B. Yuan, J. Sha, Li Li, and Z. Wang, “High-speed Reed-Solomon errors-and erasures decoder design with burst error correcting” IEEE International Conference on ASCI, pp. 485-488, 2009. [60] J. H. Beck and M. H. Sunwoo, “New degree computationless modified Euclid’s algorithm and architecture for Reed-Solomon decoder,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 14, no.8, pp. 915-920, Aug. 2006. [61] B. Yuan, Li Li, Z. Wang, M. Gao, J. Sha and C. Zhang, “Area-efficient Reed-Solomon decoder design for optical communications,” IEEE Trans. Circuits and System II, Exp. Briefs, vol. 56, no. 6, pp.469-473, June 2009. [62] B. Yuan, Li Li, Z. Wang, “High-speed area-efficient versatile Reed-Solomon decoder design for multi-mode applications,” IEEE Workshop Signal Processing Systems, pp. 179-184, 2009. [63] T. K. Truong, P. D. Chen, L. J. Wang, and T. C. Cheng, “Fast transform for decoding both errors and erasures of Reed-Solomon codes voer GF(2m) for 8≦ m ≦10,” IEEE Trans. On Communications, vol. 54, no. 2, pp. 181-186, Feb. 2006. [64] C. Zhang, Z. Wang, J. Sha, Li Li, and J. Lin, “Flexible LDPC decoder design for multigigabit-per-second applications,” IEEE Trans. Circuits and System I, vol. 57, no. 1, Jan. 2010. [65] A. Darabiha, A. C. Carusone, and F. R. Kschischang, “Power reduction techniques for LDPC decoders,” IEEE J. Solid-State Circuits, vol. 43, no. 8, pp. 1835–1845, Aug. 2008. [66] N. Onizawa, T. Ikeda, T. Hanyu, ”3.2-Gb/s 1024-b rate-1/2 LDPC decoder chip using a flooding-type update-schedule algorithm,” MWSCAS , pp. 217 – 220, 2007. [67] H.-Y. Hsu, A.-Y. Wu, and J.-C. Ye, “Area-efficient VLSI design of Reed-Solomon decoder for 10GBase-LX4 optical commumication systems,” IEEE Trans. Circuits and System II, Exp. Briefs, vol. 53, no. 11, pp. 1245-1249, Nov 2006. [68] H. Lee, “A VLSI design of a high-speed Reed-Solomon decoder,” in Proc. 14th Annu. IEEE Int. ASIC/SOC Conf., pp. 316-320, Sep. 2001. [69] L. Gao, and K. K. Parhi, “Custom VLSI design of efficient low latency and low power finite field multiplier for Reed-Solomon codec,” Proc. Of IEEE int’l Symp. On Circuits and System. vol. 4, pp. 574-577, May 2001. [70] H. Lee, M.-L. Yu, and L. Song, “VLSI design of Reed-Solomon deoder architectures,” IEEE international Symposium on Circuits and Systems, pp. 705-708, May 2000. [71] Z. Zhang, V. Anantharam, M. J. Wainwright, and B. Nikolic, “An efficient 10GBase-T Ethernet LDPC decoder design with low error floors,” IEEE J. Solid-State Circuits, vol. 45, no. 4, pp. 843–855, Apr. 2010. [72] X. Y. Shih, C. Z. Zhan, and A. Y. Wu, “A 7.39mm2 76mW(1944,972) LDPC decoder chip for IEEE 802.11n applications,” IEEE Asian Solid-State Citcuits Conf. (ASSCC), pp. 301-304, Nov. 2008. [73] Z. Zhang, L. Dolecek, B. Nikolic, V. Anantharam and M. J. Wainwright “Design of LDPC decoders for improved low error rate performance: quantization and algorithm choices,” IEEE Trans. On Wireless Communications, vol. 8, no. 11, pp. 3258-3268, Nov. 2009.
摘要: 
本論文提出應用於高傳輸量光纖通訊系統之結合RS和LDPC解碼器VLSI實作。在本論文有四個主要的重點:(1).建構分割轉移LDPC Code (Partition and Shift LDPC, PS-LDPC),此PS-LDPC (2550,2040) 是一種規則式的查核矩陣,行權重和列權重分別為3和15,碼率為4/5,其編碼前的資料長度和RS (255,239)編碼後的資料長度一樣,以利硬體實現。(2).提出改善LLR數值量化的方式來達到更好的效能,此Modified LLR的方法並不會影響LDPC的解碼架構。(3).提出2 bits Modified Layered Min Sum Algorithm (2M-LMSA)來減少查核點單元的運算量。(4).提出的RS解碼器和LDPC解碼器在解碼步驟能匹配使用,不造成電路閒置的情形。
本論文RS解碼器的演算法架構使用recursive degree computationless Modified Euclidean Algorithm (rDcMEA),其解碼的潛伏期為(2t)2 +4個clocks。而在每個RS解碼步驟區塊,設計成288 clocks完成其解碼步驟。在使用UMC 90nm CMOS製程下,其RS解碼器經由電路合成動作後,面積為0.19mm2,而頻率可達714 MHz.
LDPC解碼器的架構為雙路徑部分平行式架構,使用的演算法是本論文所提出減少查核點運算的2M-LMSA,每個區塊解碼需96個clocks解碼。本論文整合RS解碼器和LDPC解碼器的使用,在使用UMC 90nm CMOS製程下,RS&LDPC 解碼器可達到在頻率208MHz下,傳輸量為11Gb/s,其核心電路面積為3.45 mm2,而在供應電壓為0.9V下,平均功率消耗為434mW。

In this thesis, VLSI Implementation of high throughput combined RS and LDPC decoders for optical communications is presented with four major objects. The first is constructing a Partition and Shift LDPC Code (PS-LDPC Code). The PS-LDPC (2550, 2040) check matrix is a regular check matrix in which the column weight and row weight are 3 and 15, respectively, with the coding rate of 4/5. The data length of PS-LDPC Code before encoding is the same as the codeword length of RS (255,239) after encoding. Secondly, a modified quantization of likelihood ratio called Modified LLR is proposed to improve the performance. It does not influence the LDPC decoder architecture. The next is the 2 bits modified layered min sum algorithm called 2M-LMSA, which can reduce check node computation complexity. Finally, by appropriate architecture design, the decoding latencies of the RS and LDPC decoders are matched well to avoid idleness.
The RS decoder architecture utilizes recursive degree computationless modified Euclidean Algorithm (rDcMEA) with decoding latency of (2t)2 +4. The total clock cycles are 288 per RS decoding blocks. The RS decoder was designed and implemented using UMC 90nm CMOS technology. The synthesized result shows that the proposed RS (255,239) decoder only occupies about 0.19 mm2 at clock rate of 714MHz.
The LDPC decoder employs a dual path partial parallel architecture using the proposed 2M-LMSA to reduce check node unit (CNU) computation complexity. The total numbers clock cycles are 96 per LDPC decoding blocks. The combined RS and LDPC decoders called RS&LDPC decoder was designed and implemented using UMC 90nm CMOS technology. The RS&LDPC decoder can achieve the decoding throughput of 11Gb/s at the clock frequency of 208 MHz after auto place route (APR) . The average power consumption is 434mW at supply voltage of 0.9 V with the core area of 3.45 mm2.
URI: http://hdl.handle.net/11455/8885
其他識別: U0005-2107201012252100
Appears in Collections:電機工程學系所

Show full item record
 
TAIR Related Article

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.