低密度奇偶校验码译码算法的硬件实现
|
摘要
LDPC码(低密度奇偶校验码)是一种具有极强纠错能力的差错控制编码技术,它的性能接近香农极限,其译码复杂度低于Turbo码,由于LDPC码在光通信、卫星通信、深空通信、第4代移动通信系统、高速与甚高速率数字用户线、光和磁记录系统等诸多领域都有良好的应用前景,所以,开发LDPC硬件译码器已经成为纠错编码领域研发的一大热点。
本文首先概述了LDPC码的定义、基本构造方式和编码理论;讨论了LDPC译码方法——BP译码算法,为方便译码器的硬件实现本文着重研究了低实现复杂度的Log-BP译码算法,通过对两种算法进行了性能仿真,结果表明Log-BP在性能上完全适合,可以作为硬件译码的算法。在硬件实现中,考虑到译码精度要求和硬件资源有限,本文探讨了数据量化位数选择与译码性能的关系并进行了仿真,得出了在本译码器设计指标和现有硬件资源条件下,最合适的量化数据位数。在此基础上,使用Verilog硬件描述语言,采用部分并行译码结构,利用自顶而下的模块化设计方法设计LDPC译码器,并运用EDA设计工具ModelSim和ISE,对各个组成模块进行综合和时序仿真;然后利用原理图输入法将分模块合并为一个完整的译码器电路,对整个译码器进行了全面的功能仿真、综合和时序仿真,验证设计的正确性和译码器的性能。最后,设计了译码器实验板,下载了译码算法,进行了相应的测试。
LDPC code(Low Density Parity Check Code)is a powerful error correcting technique.Mackay and Neal prove that the performance of LDPC codes is close to the Shannon limits .Its decoding complexity is also lower than turbo code. Recently, LDPC code has drawn the worldwide attentions successfully because of its excellent performace and its bright application prospect in optic communications, satellite communications, deep space communication,the fourth generation mobile communication system ,digital subscriber loop with high speed or hypervelocity, optical and magnetic recording system, many companies are urgent to develop LDPC decoder on hardware.
This paper firstly introduces the definition of LDPC codes, the basic construction of LDPC codes and the way of encoding,they are the foundations of decoding Secondly, we discuss the Belief Propagation (BP) algorithm and the Log-BP algorithm and simulate the Log-BP algorithm.The Log-BP algorithm is suitable for the implementation of the hardware decoder.Thirdly, given the decoding precision and the limit hardware resources,we discuss the selection of digital bit, and we offer the most suitable option. Fourthly,this thesis uses Verilog Hardware Description Language and adopts part parallel decoding configuration. We use the idea of top-down design to program the decoder with Verilog Hardware Description Language. Moreover, we synthesize and analyze the static time of the design with ModelSim and ISE to verify the correctness and the function.At last, we use the FPGA and relative hardware cells to design a decding board.
本文首先概述了LDPC码的定义、基本构造方式和编码理论;讨论了LDPC译码方法——BP译码算法,为方便译码器的硬件实现本文着重研究了低实现复杂度的Log-BP译码算法,通过对两种算法进行了性能仿真,结果表明Log-BP在性能上完全适合,可以作为硬件译码的算法。在硬件实现中,考虑到译码精度要求和硬件资源有限,本文探讨了数据量化位数选择与译码性能的关系并进行了仿真,得出了在本译码器设计指标和现有硬件资源条件下,最合适的量化数据位数。在此基础上,使用Verilog硬件描述语言,采用部分并行译码结构,利用自顶而下的模块化设计方法设计LDPC译码器,并运用EDA设计工具ModelSim和ISE,对各个组成模块进行综合和时序仿真;然后利用原理图输入法将分模块合并为一个完整的译码器电路,对整个译码器进行了全面的功能仿真、综合和时序仿真,验证设计的正确性和译码器的性能。最后,设计了译码器实验板,下载了译码算法,进行了相应的测试。
LDPC code(Low Density Parity Check Code)is a powerful error correcting technique.Mackay and Neal prove that the performance of LDPC codes is close to the Shannon limits .Its decoding complexity is also lower than turbo code. Recently, LDPC code has drawn the worldwide attentions successfully because of its excellent performace and its bright application prospect in optic communications, satellite communications, deep space communication,the fourth generation mobile communication system ,digital subscriber loop with high speed or hypervelocity, optical and magnetic recording system, many companies are urgent to develop LDPC decoder on hardware.
This paper firstly introduces the definition of LDPC codes, the basic construction of LDPC codes and the way of encoding,they are the foundations of decoding Secondly, we discuss the Belief Propagation (BP) algorithm and the Log-BP algorithm and simulate the Log-BP algorithm.The Log-BP algorithm is suitable for the implementation of the hardware decoder.Thirdly, given the decoding precision and the limit hardware resources,we discuss the selection of digital bit, and we offer the most suitable option. Fourthly,this thesis uses Verilog Hardware Description Language and adopts part parallel decoding configuration. We use the idea of top-down design to program the decoder with Verilog Hardware Description Language. Moreover, we synthesize and analyze the static time of the design with ModelSim and ISE to verify the correctness and the function.At last, we use the FPGA and relative hardware cells to design a decding board.
引文
[1] D.J.C.Mackay and R.M.Neal,“Near Shannon Limit Performance of Low Density Parity Check Codes”, Electric Lett., vol.32, pp1645-1646, Aug.1996
[2] Thomas J.Richardson and Rudiger L.Urbanke,“Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding”, IEEE Transaction on Information Theory, vol.47, No.2, Feb.2001
[3] D.J.C.Mckay,“Good Error-Correcting Codes Based on Very Sparse Matrices”, IEEE Trans on Inf. Theory, March 1999
[4] Thomas J. Richardson and Rudiger L. Urbanke,“Efficient Encoding of Low-Density Parity-Check Codes”, IEEE Transactions on Information Theory, vol.47, No.2, Feb.2001
[5] Hongxin Song, Richard M. Todd and J.R.Cruz,“Applications of Low-Density Parity-Check Codes to Magnetic Recording Channels”, IEEE Journal on Selected areas in communications, vol.19, No.5, May 2001, pp.918-923
[6] Zang Di, et al.“Low-Density Parity-Check Codes Used for Compressed Image Transmission over Noise Channel”, from Internet, http://image.chonbuk.ac.kr/kwak/datal/2002-4.pdf, Apr.2003
[7] J.G. Proakis,“数字通信”第四版,电子工业出版社, 2003.1,pp.59-65
[8] Bernard Sklar,“数字通信-基础与应用”第二版,电子工业出版社,2002.9,pp.1-42
[9] Luby M, Mizenmacher M, Shokrollahi M A, et al. Improved Low Density Parity Check Codes using Irregular Graphs and Belief Propagation[A]. International Symposium on Information Theory (ISIT). 1998. 117.
[10] Mittelholzer T, Dholakia A, Eleftheriou E.Reduced,“Complexity Decoding of Low Density Parity Check Codes for Generalized Partial Response Channels”, IEEE Transactions on Magnetics, vol.37, No.2, pp.721-727, Mar.2001
[11] C.Berrou, A.Glavieux, P.Thitimajshima, "Near Shannon Limit Error Correcting Coding and Decoding: Turbo-Codes", in ICC'93, Geneva, Switzerland, May 1993, pp.1064-1070
[12] Eleftheriou E et al.,“Low-Density Parity-Check Codes for DSL Transmission”, Temporary Document BI-095, ITU-T SS, Study Group 15/4, Goa, India, 23-27 Oct, 2000
[13] E.Yeo, P.Pakzad, B.Nikolic, and V. Anantharam,“VLSI Architectures for Iterative Decoders in Magnetic Recording Channels”, IEEE Trans. Magnetics, vol.37, No.2, pp.748-755, Mar.2001
[14] Sungwook Kim, etc.“Parallel VLSI Architectures for a Class of LDPC Codes”. 2002 IEEE.2 002:93-96
[15] Sungwook Kim.“High Performance Techniques for Digit-Serial Applications and LDPC Codes”. Dissertation Submitted in Candidate for the Degree of Doctor of Philosophy. Universityof Minnesota. 2002:58-80
[16] Flarion Technologies Inc. Vector-Low-Density Parity-Check Coding Solution Data Sheet On-line. http://www.flarion.com
[17]“Performance of LDPC Coded Modulation for ADSL bits under latency constraints”, Temporary Document RN-073, Study Group 15/4, Red Bank, New Jersey, 21-25 May 2001
[18] Vocal Technologies Ltd. Wireless, RF and Broadcast Semiconductor Information for the Design Engineer. http://www.chipcenter.com
[19] M.Sipser, D.A.Spielman,“Expander Codes”, IEEE Transactions on Information Theory, vol.42, No.6, pp.1710-1722, Nov.1996
[20] M.Luby, M.Mitzenmacher, M.A.Shokrollahi, D.A.Spielman, and V.Stemann,“Practical Loss-Resilient Codes”, Proc.29th Symp. On Theory of Computing, pp.150-159, 1997
[21] Palnitkar著、夏宇闻等译,“Verilog HDL数字设计与综合”,电子工业出版社,2004
[22]杨恒、李爱国等编著,“FPGA/CPLD最新实用技术指南”,清华大学出版社,2005
[23]Tong Zhang, Keshab K., Parhi.“A 54 MBPS (3,6) Regular FPGA LDPC Decoder”. Signal Processing Systems.2002 IEEE.2002:127-132
[24]段吉海、黄智伟等著,“数字通信系统建模与设计”,电子工业出版社2004
[25] Wayne Wolf“FPGA-Based System Design”China Machine Press 2005
[26]夏宇闻著,“Verilog数字系统设计教程”,北京航空航天出版社2003
[27] J.Bhasker著、孙海平译,“Verilog HDL综合实用教程”,清华大学出版社,2004
[28]徐澄析.LDPC码研究进展.南京邮电学院学报.2002,22(3):15-19
[29]李智明等,“基于FPGA的规则(3,6)LDPC码译码器”,电子技术应用2004年12期:54~57
[30]Andrew J, Blanksby and Chris J. Howland. A 690-mW 1-Gb/s 1024-b,Rate-1/2 Low-Density Parity-Check Code Decoder.IEEE Journal of Solid State Circuits.2 002,37(3):404412
[31] TPS70451 Data Sheet, 2002
[32] PT6939 Data Sheet, 2001
[33] Spartan-3 Data Sheet, 2006
[34] MAX3232 Data Sheet, 2002
[35]石英、李新新等著,“ISE应用与开发技巧”,机械工业出版社,2006
[36]林雪红等,“LDPC码的并行译码算法”,北京邮电大学学报2005年第10期
[37]童胜,王鹏等,“LDPC量化和积译码算法的高效实现”,西安电子科技大学学报, 2004年第10期
[38] Kim S,et a1.Parallel VLSI architectures for a class of LDPC codes.Circuits and Systems,2002.In:ISCAS 2002.IEEE Intl.Symposium on ,Volume 2,2002.93～96
[39]孙韶辉,慕建君,王新梅,“低密度校验码研究及其新进展”,西安电子科技大学学报,2001,28(3):393～39
[40]岳田等,“LDPC码几种译码算法的比较”,信息传输与接入技术,2006年第4期
[2] Thomas J.Richardson and Rudiger L.Urbanke,“Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding”, IEEE Transaction on Information Theory, vol.47, No.2, Feb.2001
[3] D.J.C.Mckay,“Good Error-Correcting Codes Based on Very Sparse Matrices”, IEEE Trans on Inf. Theory, March 1999
[4] Thomas J. Richardson and Rudiger L. Urbanke,“Efficient Encoding of Low-Density Parity-Check Codes”, IEEE Transactions on Information Theory, vol.47, No.2, Feb.2001
[5] Hongxin Song, Richard M. Todd and J.R.Cruz,“Applications of Low-Density Parity-Check Codes to Magnetic Recording Channels”, IEEE Journal on Selected areas in communications, vol.19, No.5, May 2001, pp.918-923
[6] Zang Di, et al.“Low-Density Parity-Check Codes Used for Compressed Image Transmission over Noise Channel”, from Internet, http://image.chonbuk.ac.kr/kwak/datal/2002-4.pdf, Apr.2003
[7] J.G. Proakis,“数字通信”第四版,电子工业出版社, 2003.1,pp.59-65
[8] Bernard Sklar,“数字通信-基础与应用”第二版,电子工业出版社,2002.9,pp.1-42
[9] Luby M, Mizenmacher M, Shokrollahi M A, et al. Improved Low Density Parity Check Codes using Irregular Graphs and Belief Propagation[A]. International Symposium on Information Theory (ISIT). 1998. 117.
[10] Mittelholzer T, Dholakia A, Eleftheriou E.Reduced,“Complexity Decoding of Low Density Parity Check Codes for Generalized Partial Response Channels”, IEEE Transactions on Magnetics, vol.37, No.2, pp.721-727, Mar.2001
[11] C.Berrou, A.Glavieux, P.Thitimajshima, "Near Shannon Limit Error Correcting Coding and Decoding: Turbo-Codes", in ICC'93, Geneva, Switzerland, May 1993, pp.1064-1070
[12] Eleftheriou E et al.,“Low-Density Parity-Check Codes for DSL Transmission”, Temporary Document BI-095, ITU-T SS, Study Group 15/4, Goa, India, 23-27 Oct, 2000
[13] E.Yeo, P.Pakzad, B.Nikolic, and V. Anantharam,“VLSI Architectures for Iterative Decoders in Magnetic Recording Channels”, IEEE Trans. Magnetics, vol.37, No.2, pp.748-755, Mar.2001
[14] Sungwook Kim, etc.“Parallel VLSI Architectures for a Class of LDPC Codes”. 2002 IEEE.2 002:93-96
[15] Sungwook Kim.“High Performance Techniques for Digit-Serial Applications and LDPC Codes”. Dissertation Submitted in Candidate for the Degree of Doctor of Philosophy. Universityof Minnesota. 2002:58-80
[16] Flarion Technologies Inc. Vector-Low-Density Parity-Check Coding Solution Data Sheet On-line. http://www.flarion.com
[17]“Performance of LDPC Coded Modulation for ADSL bits under latency constraints”, Temporary Document RN-073, Study Group 15/4, Red Bank, New Jersey, 21-25 May 2001
[18] Vocal Technologies Ltd. Wireless, RF and Broadcast Semiconductor Information for the Design Engineer. http://www.chipcenter.com
[19] M.Sipser, D.A.Spielman,“Expander Codes”, IEEE Transactions on Information Theory, vol.42, No.6, pp.1710-1722, Nov.1996
[20] M.Luby, M.Mitzenmacher, M.A.Shokrollahi, D.A.Spielman, and V.Stemann,“Practical Loss-Resilient Codes”, Proc.29th Symp. On Theory of Computing, pp.150-159, 1997
[21] Palnitkar著、夏宇闻等译,“Verilog HDL数字设计与综合”,电子工业出版社,2004
[22]杨恒、李爱国等编著,“FPGA/CPLD最新实用技术指南”,清华大学出版社,2005
[23]Tong Zhang, Keshab K., Parhi.“A 54 MBPS (3,6) Regular FPGA LDPC Decoder”. Signal Processing Systems.2002 IEEE.2002:127-132
[24]段吉海、黄智伟等著,“数字通信系统建模与设计”,电子工业出版社2004
[25] Wayne Wolf“FPGA-Based System Design”China Machine Press 2005
[26]夏宇闻著,“Verilog数字系统设计教程”,北京航空航天出版社2003
[27] J.Bhasker著、孙海平译,“Verilog HDL综合实用教程”,清华大学出版社,2004
[28]徐澄析.LDPC码研究进展.南京邮电学院学报.2002,22(3):15-19
[29]李智明等,“基于FPGA的规则(3,6)LDPC码译码器”,电子技术应用2004年12期:54~57
[30]Andrew J, Blanksby and Chris J. Howland. A 690-mW 1-Gb/s 1024-b,Rate-1/2 Low-Density Parity-Check Code Decoder.IEEE Journal of Solid State Circuits.2 002,37(3):404412
[31] TPS70451 Data Sheet, 2002
[32] PT6939 Data Sheet, 2001
[33] Spartan-3 Data Sheet, 2006
[34] MAX3232 Data Sheet, 2002
[35]石英、李新新等著,“ISE应用与开发技巧”,机械工业出版社,2006
[36]林雪红等,“LDPC码的并行译码算法”,北京邮电大学学报2005年第10期
[37]童胜,王鹏等,“LDPC量化和积译码算法的高效实现”,西安电子科技大学学报, 2004年第10期
[38] Kim S,et a1.Parallel VLSI architectures for a class of LDPC codes.Circuits and Systems,2002.In:ISCAS 2002.IEEE Intl.Symposium on ,Volume 2,2002.93～96
[39]孙韶辉,慕建君,王新梅,“低密度校验码研究及其新进展”,西安电子科技大学学报,2001,28(3):393～39
[40]岳田等,“LDPC码几种译码算法的比较”,信息传输与接入技术,2006年第4期