LDPC码编译码技术研究
|
摘要
信道编码是数字通信系统和计算机系统的重要组成部分。LDPC信道编码技术是编码界的重要成果之一,1/2码率的二元LDPC码在AWGN信道下的性能距信息论中的Shannon限仅差0.0045dB,它是目前距Shannon限最近的纠错码。Gallager在1962年提出低密度校验码(LDPC码),1996年经过Mackay、Spielman和Wiberg等人的再发现后,LDPC码以其性能优越、全并行迭代译码结构,译码复杂度线形增长,便于硬件实现等一系列优点,在无线通信、深空通信和存储工业等诸多领域得到了广泛应用。
本文首先回顾了信道编码技术的发展历史,介绍了LDPC码的基本概念和原理。在几个重点的研究方向:校验矩阵的构造、相关编码方式、简化译码算法以及性能估计分析等方面作了详细的介绍,并提出了自己的创新解决方案。本文的重点是新型校验矩阵的构造和译码算法的优化。
校验矩阵的构造是编码的前提,好的构造方案可以大大简化复杂度。本文首先回顾了几种主要的矩阵构造方法:随机化构造、半随机化构造和结构化构造,并比较了各自的优缺点。在此基础上提出了一种基于码长连续变化的QC-LDPC码的构造方法,设计出的H矩阵具有较大girth值,且码率码长可以灵活变化。此外,对于非规则码我们采用了码率压缩的方法同样实现了高码率并且连续变化。
译码算法是LDPC码的关键,译码复杂度的大小直接影响系统的实现。主要分硬判决译码、软判决和复合译码,经典的译码算法有比特反转(BF)译码算法和置信度传播(BP)译算法。对于硬判决的比特反转算法,作者在基于加权错误校验比特反转算法基础上做了优化,主要是科学合理的引入了判决门限,使得在保证系统性能的前提下大大简化了译码的复杂度。仿真表明:保证了系统性能,并且大大减少了译码所需迭代次数。
对LDPC码的译码性能,本文用经典的密度进化和高斯近似等理论进行了估计和分析。此举有助于优化校验矩阵行和列的度分布,并能有效预测LDPC码字的译码性能,同时还能够确定信道阀值。
Channel coding is an important component for digital communications systems and computer systems, and LDPC channel coding technology is one of the encoding results. Half of the binary bit-rate LDPC codes in AWGN channel performance only with a tap of 0.0045dB to the Shannon information theory limit. It is the latest error-correcting codes from the Shannon limit. Gallager proposed LDPC codes in 1962, after Mackay and others re-discovered it In 1996, with best performance, completely decoding algorithm in parallel scheme, decoding complexity of linear growth and easily realized for hardware design, LDPC codes has already been widely used in many practical systems, such as wireless communication system, deep-space communication system, and storage system.
This thesis reviews the channel coding technology development at first, and introduces the basic concept of LDPC codes and principles. For the focus of research in several directions: Check matrix of structure, related to encoding and decoding ,simplified algorithm , analysis and estimated of the performance, author Put forward own innovative solutions. The focus of this paper is a new calibration matrix of the structure and the optimization algorithm.
the construction of the Check matrix is a precondition for coding, a good program construction can greatly simplify the complexity. This thesis reviews main construction types of low-density parity matrix: randomized method, semi-random method and structured construction method, and compare their advantages and disadvantages,then propose a method of construction based on Continuously Variable Length, whose parity check matrix has large girth, and the block length and code rate can be increased. Furthermore, we make use of the compression for code rate to achieve a high code rate and change agilely.
The decoding algorithm is the key to LDPC code and the complexity of decoding direct impact realization of the system. It has three kinds of decoding algorithms: hard-decision method, soft-decision methods and hybrid decoding, classical algorithm is BF and BP. To hard-decision methods, author optimizes the WVBF, mainly set the scientific and rational decision threshold and ensures the system performance at the same time greatly simplified the complexity of the decoding. By simulation it has best performance and significantly reduced the number of iterations required for decoding.
We analyses decoding performance of LDPC codes with Density Evolution and Gaussian Approximation. It helps to optimize the degree distribution for low-density parity, accurately evaluate the performance matrix without simulations and determine the channel value limit.
本文首先回顾了信道编码技术的发展历史,介绍了LDPC码的基本概念和原理。在几个重点的研究方向:校验矩阵的构造、相关编码方式、简化译码算法以及性能估计分析等方面作了详细的介绍,并提出了自己的创新解决方案。本文的重点是新型校验矩阵的构造和译码算法的优化。
校验矩阵的构造是编码的前提,好的构造方案可以大大简化复杂度。本文首先回顾了几种主要的矩阵构造方法:随机化构造、半随机化构造和结构化构造,并比较了各自的优缺点。在此基础上提出了一种基于码长连续变化的QC-LDPC码的构造方法,设计出的H矩阵具有较大girth值,且码率码长可以灵活变化。此外,对于非规则码我们采用了码率压缩的方法同样实现了高码率并且连续变化。
译码算法是LDPC码的关键,译码复杂度的大小直接影响系统的实现。主要分硬判决译码、软判决和复合译码,经典的译码算法有比特反转(BF)译码算法和置信度传播(BP)译算法。对于硬判决的比特反转算法,作者在基于加权错误校验比特反转算法基础上做了优化,主要是科学合理的引入了判决门限,使得在保证系统性能的前提下大大简化了译码的复杂度。仿真表明:保证了系统性能,并且大大减少了译码所需迭代次数。
对LDPC码的译码性能,本文用经典的密度进化和高斯近似等理论进行了估计和分析。此举有助于优化校验矩阵行和列的度分布,并能有效预测LDPC码字的译码性能,同时还能够确定信道阀值。
Channel coding is an important component for digital communications systems and computer systems, and LDPC channel coding technology is one of the encoding results. Half of the binary bit-rate LDPC codes in AWGN channel performance only with a tap of 0.0045dB to the Shannon information theory limit. It is the latest error-correcting codes from the Shannon limit. Gallager proposed LDPC codes in 1962, after Mackay and others re-discovered it In 1996, with best performance, completely decoding algorithm in parallel scheme, decoding complexity of linear growth and easily realized for hardware design, LDPC codes has already been widely used in many practical systems, such as wireless communication system, deep-space communication system, and storage system.
This thesis reviews the channel coding technology development at first, and introduces the basic concept of LDPC codes and principles. For the focus of research in several directions: Check matrix of structure, related to encoding and decoding ,simplified algorithm , analysis and estimated of the performance, author Put forward own innovative solutions. The focus of this paper is a new calibration matrix of the structure and the optimization algorithm.
the construction of the Check matrix is a precondition for coding, a good program construction can greatly simplify the complexity. This thesis reviews main construction types of low-density parity matrix: randomized method, semi-random method and structured construction method, and compare their advantages and disadvantages,then propose a method of construction based on Continuously Variable Length, whose parity check matrix has large girth, and the block length and code rate can be increased. Furthermore, we make use of the compression for code rate to achieve a high code rate and change agilely.
The decoding algorithm is the key to LDPC code and the complexity of decoding direct impact realization of the system. It has three kinds of decoding algorithms: hard-decision method, soft-decision methods and hybrid decoding, classical algorithm is BF and BP. To hard-decision methods, author optimizes the WVBF, mainly set the scientific and rational decision threshold and ensures the system performance at the same time greatly simplified the complexity of the decoding. By simulation it has best performance and significantly reduced the number of iterations required for decoding.
We analyses decoding performance of LDPC codes with Density Evolution and Gaussian Approximation. It helps to optimize the degree distribution for low-density parity, accurately evaluate the performance matrix without simulations and determine the channel value limit.
引文
[1] C. E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J.. vol. 27. pp.379-423. 623-656. July-Oct.1948; Reprinted in C. E. Shannon and W. Weaver. The Mathematical Theory of Communication. Urbana. IL: Univ. Illinois Press. 1949.
[2] R. W Hamming. Error detecting and correcting codes. USA Bell Systematic Technical Journal, 1950, 29:147-150.
[3] M. J. E. Golay. Notes on digital coding. Proc. IRE, June 1949, 37: 657-658.
[4] D.E. Muller, Application of Boolean algebra to switching circuit design, IEEE on Computers, vol. 3, pp. 6-12, Sept. 1954.
[5] E. Prange, Cyclic error-correcting codes in two symbols, Tech. Rep. TN-57-103, Air Force Cambridge Research Center, Cambridge, MA, Sept. 1957
[6] P. Elias. Coding for noisy channels. IRE Conv Record, 1955, 4:37-47.
[7] A. J. Viterbi, Error bounds for convolutional codes and an asymptotically optimum decoding algorithm, IEEE Trans. Inform. Theory vol. 13 pp.260-269, Apr. 1967.
[8] C. Berrou, A.Glavieux and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding: Turbo-codes(1). Proc. ICC'93, Geneva, Switzerland, May 1993:1064-1074.
[9] R. G. Gallager. Low-Density Parity-Check Codes. IRE Trans.Inform. Theory, Jan.1962, 8: 21-28.
[10] R. Michael Tanner,“A recursive approach to low complexity codes,”IEEE Trans. on Information Theory, vol. IT-27, no. 5, Sep. 1981, pp. 533-547.
[11] D. J. C. Mackay and R. M. Neal. Near Shannon limit performance of low density parity check codes. Electronics Letters, Aug. 1996, 32: 1645-1646.
[12] M. C. Davey and D.J.C.Mackay. Low density parity check codes over GF(q). IEEE Commun. Lett., June 1998, 2: 165-167.
[13] S.-Y Chung, G D. Forney, Jr., T. J. Richardson, et al. On the design of low-density parity-check codes within 0.0045dB of the Shannon limit. IEEE Commun. Lett., Feb.2001,5: 58-60.
[14] T. J. Richardson and R.Uranke, Efficient encoding of low-density parity check codes, IEEE Trans. Inform.Theory, vol.47, No.2, Feb.2001, pp.638-656.
[15] A. M. Chan, and F. R. Kschischang, "A simple taboo-based soft-decision decoding algorithm for expandercodes," IEEE Communications Letters, Vol. 2, No. 7, pp. 183-185, 1998.
[16] Y. Kou, S. Lin, and M. P. C. Fossorier, "Low Density Parity Check Codes based on Finite Geometries: A Rediscovery," in Proc. IEEE ISIT'00, Sorrento, Italy, 2000 p. 200.
[17] J. Zhang, and M. P. C. Fossorier, "A modified weighted bit-flipping decoding of low-density Parity-check codes," IEEE Communications Letters, Vol. 8, No. 3, pp. 165-167, 2004.
[18]董桂强,徐鹰, and朱近康, "一种改进的LDPC码比特反转解码算法,"无线通讯技术(已录用), 2008.
[19] N. Wiberg, "Codes and decoding on general graphs," Doctor dissertation, Department of Electrical Engineering, Linkoping University, Linkoping, Sweden, 1996.
[20] M. P. C. Fossorier, M. Miladinovic, and H. Imai, "Reduced Complexity Iterative Decoding of Low-Density Parity Check Codes Based on Belief Propagation," IEEE Trans. Information Theory, Vol. 47, No. 5, pp. 673-680, 1999
[21] J. Chen, and M. P. C. Fossorier, "Near Optimum Universal Belief Propagation Based Decoding of Low-Density Parity Check Codes," IEEE Trans. Information Theory, Vol. 50, No. 3, pp. 404-414, 2002.
[22] J. Chen, and M. P. C. Fossorier, "Density evolution for BP-based decoding algorithms of LDPC codes and their quantized versions," in Proc. Global Telecommunications Conference, 2002 Vol. 2, pp. 1387-1391
[23] 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, 2002
[24] N. Kim, and H. Park, "Modified UMP-BP decoding algorithm based on mean square error," Electronics Letters, Vol. 40, No. 13, pp. 816-817, 2004.
[25] J. Zhang, M. P. C. Fossorier, D. Gu, et al., "Two-Dimensional Correction for Min-Sum Decoding of Irregular LDPC Codes," IEEE Communications Letters, Vol. 10, No. 3, pp. 180-182, 2006
[26]徐鹰,卫国, and朱近康, "一种最小区域选择的LDPC迭代译码算法,"中国科学技术大学学报(已录用), 2007
[27] Y. Xin, and S. A. Mujtaba, "A hybrid decoding approach for LDPC coded MIMO-OFDM systems," in Proc. Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, 2004 Vol. 1, pp. 1173-1177.
[28] P. Zarrinkhat, and A. H. Banihashemi, "Hybrid decoding of low-density parity-check codes," in Proc. 3rd Int. Symp. Tu rbo Codes, Brest, France, 2003 pp. 503-506.
[29] P. Zarrinkhat, and A. H. Banihashemi, "Hybrid decoding of irregular LDPC codes," in Proc. IEEE ISIT'05, Adelaide, Australia, 2005 pp. 312-316
[30] P. Zarrinkhat, and A. H. Banihashemi, "Hybrid hard-decision iterative decoding of regular low-density parity-check codes," IEEE Communications Letters, Vol. 8, pp. 250-252, 2004
[31] P. Zarrinkhat, and A. H. Banihashemi, "Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes," IEEE Trans. Communications, Vol. 55, No. 2, pp. 292-302, 2007.
[32]周立媛,张立军, and陈常嘉, "低密度校验码的混合比特反转译码算法,"北京交通大学学报(自然科学版), Vol. 2, pp. 47-50, 2005
[33]卞月广,王有政,肖立民, et al., "一种LDPC码的两步混合译码算法,"微计算机信息, Vol. 31, pp. 223-225, 2007
[34] D. J. C. Mackay. Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Trans. Info. Theory, vol. IT-45, pp.399-413, March 1999.
[35] L. Ping, W. Leung, and N. Phamdo, Low density parith check codes with semi-random parity check matrix, IEEE Electron. Lett.,vol. 35, pp. 38-39, 1999.
[36] Echard R, Chang S C. Theπ-rotation low-density parity check codes [J]. Proc.GLOBECOM 2001,2002. 980-984.
[37] B. Vasic, "Combinatorial Constructions of Low-Density Parity Check Codes for Iterative Decoding," in Proc. IEEE ISIT'02, Lausanne, Switzerland, 2002 p. 312.
[38] Fan Zhang, Ying Xu, Xuehong Mao and Wuyang Zhou. High Girth LDPC Codes Construction Based on Combinatorial design. IEEE Vehicular Technology Conference Spring 2005.
[39] Lei Liu, Jie Huang,Wuyang Zhou and Shengli Zhou. Construction of Nonbinary Quasi-Cyclic LDPC Codes with Continuously Variable Length [J], submmittied to Communication letter 2008.
[40] Jeongseok Ha, Jaehong Kim, and Steven W. McLaughlin, Senior Member, IEEE“Rate-Compatible Puncturing of Low-Density Parity-Check Codes”IEEE Transactions on information theory vol.50, NO 11, November 2004.
[2] R. W Hamming. Error detecting and correcting codes. USA Bell Systematic Technical Journal, 1950, 29:147-150.
[3] M. J. E. Golay. Notes on digital coding. Proc. IRE, June 1949, 37: 657-658.
[4] D.E. Muller, Application of Boolean algebra to switching circuit design, IEEE on Computers, vol. 3, pp. 6-12, Sept. 1954.
[5] E. Prange, Cyclic error-correcting codes in two symbols, Tech. Rep. TN-57-103, Air Force Cambridge Research Center, Cambridge, MA, Sept. 1957
[6] P. Elias. Coding for noisy channels. IRE Conv Record, 1955, 4:37-47.
[7] A. J. Viterbi, Error bounds for convolutional codes and an asymptotically optimum decoding algorithm, IEEE Trans. Inform. Theory vol. 13 pp.260-269, Apr. 1967.
[8] C. Berrou, A.Glavieux and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding: Turbo-codes(1). Proc. ICC'93, Geneva, Switzerland, May 1993:1064-1074.
[9] R. G. Gallager. Low-Density Parity-Check Codes. IRE Trans.Inform. Theory, Jan.1962, 8: 21-28.
[10] R. Michael Tanner,“A recursive approach to low complexity codes,”IEEE Trans. on Information Theory, vol. IT-27, no. 5, Sep. 1981, pp. 533-547.
[11] D. J. C. Mackay and R. M. Neal. Near Shannon limit performance of low density parity check codes. Electronics Letters, Aug. 1996, 32: 1645-1646.
[12] M. C. Davey and D.J.C.Mackay. Low density parity check codes over GF(q). IEEE Commun. Lett., June 1998, 2: 165-167.
[13] S.-Y Chung, G D. Forney, Jr., T. J. Richardson, et al. On the design of low-density parity-check codes within 0.0045dB of the Shannon limit. IEEE Commun. Lett., Feb.2001,5: 58-60.
[14] T. J. Richardson and R.Uranke, Efficient encoding of low-density parity check codes, IEEE Trans. Inform.Theory, vol.47, No.2, Feb.2001, pp.638-656.
[15] A. M. Chan, and F. R. Kschischang, "A simple taboo-based soft-decision decoding algorithm for expandercodes," IEEE Communications Letters, Vol. 2, No. 7, pp. 183-185, 1998.
[16] Y. Kou, S. Lin, and M. P. C. Fossorier, "Low Density Parity Check Codes based on Finite Geometries: A Rediscovery," in Proc. IEEE ISIT'00, Sorrento, Italy, 2000 p. 200.
[17] J. Zhang, and M. P. C. Fossorier, "A modified weighted bit-flipping decoding of low-density Parity-check codes," IEEE Communications Letters, Vol. 8, No. 3, pp. 165-167, 2004.
[18]董桂强,徐鹰, and朱近康, "一种改进的LDPC码比特反转解码算法,"无线通讯技术(已录用), 2008.
[19] N. Wiberg, "Codes and decoding on general graphs," Doctor dissertation, Department of Electrical Engineering, Linkoping University, Linkoping, Sweden, 1996.
[20] M. P. C. Fossorier, M. Miladinovic, and H. Imai, "Reduced Complexity Iterative Decoding of Low-Density Parity Check Codes Based on Belief Propagation," IEEE Trans. Information Theory, Vol. 47, No. 5, pp. 673-680, 1999
[21] J. Chen, and M. P. C. Fossorier, "Near Optimum Universal Belief Propagation Based Decoding of Low-Density Parity Check Codes," IEEE Trans. Information Theory, Vol. 50, No. 3, pp. 404-414, 2002.
[22] J. Chen, and M. P. C. Fossorier, "Density evolution for BP-based decoding algorithms of LDPC codes and their quantized versions," in Proc. Global Telecommunications Conference, 2002 Vol. 2, pp. 1387-1391
[23] 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, 2002
[24] N. Kim, and H. Park, "Modified UMP-BP decoding algorithm based on mean square error," Electronics Letters, Vol. 40, No. 13, pp. 816-817, 2004.
[25] J. Zhang, M. P. C. Fossorier, D. Gu, et al., "Two-Dimensional Correction for Min-Sum Decoding of Irregular LDPC Codes," IEEE Communications Letters, Vol. 10, No. 3, pp. 180-182, 2006
[26]徐鹰,卫国, and朱近康, "一种最小区域选择的LDPC迭代译码算法,"中国科学技术大学学报(已录用), 2007
[27] Y. Xin, and S. A. Mujtaba, "A hybrid decoding approach for LDPC coded MIMO-OFDM systems," in Proc. Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, 2004 Vol. 1, pp. 1173-1177.
[28] P. Zarrinkhat, and A. H. Banihashemi, "Hybrid decoding of low-density parity-check codes," in Proc. 3rd Int. Symp. Tu rbo Codes, Brest, France, 2003 pp. 503-506.
[29] P. Zarrinkhat, and A. H. Banihashemi, "Hybrid decoding of irregular LDPC codes," in Proc. IEEE ISIT'05, Adelaide, Australia, 2005 pp. 312-316
[30] P. Zarrinkhat, and A. H. Banihashemi, "Hybrid hard-decision iterative decoding of regular low-density parity-check codes," IEEE Communications Letters, Vol. 8, pp. 250-252, 2004
[31] P. Zarrinkhat, and A. H. Banihashemi, "Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes," IEEE Trans. Communications, Vol. 55, No. 2, pp. 292-302, 2007.
[32]周立媛,张立军, and陈常嘉, "低密度校验码的混合比特反转译码算法,"北京交通大学学报(自然科学版), Vol. 2, pp. 47-50, 2005
[33]卞月广,王有政,肖立民, et al., "一种LDPC码的两步混合译码算法,"微计算机信息, Vol. 31, pp. 223-225, 2007
[34] D. J. C. Mackay. Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Trans. Info. Theory, vol. IT-45, pp.399-413, March 1999.
[35] L. Ping, W. Leung, and N. Phamdo, Low density parith check codes with semi-random parity check matrix, IEEE Electron. Lett.,vol. 35, pp. 38-39, 1999.
[36] Echard R, Chang S C. Theπ-rotation low-density parity check codes [J]. Proc.GLOBECOM 2001,2002. 980-984.
[37] B. Vasic, "Combinatorial Constructions of Low-Density Parity Check Codes for Iterative Decoding," in Proc. IEEE ISIT'02, Lausanne, Switzerland, 2002 p. 312.
[38] Fan Zhang, Ying Xu, Xuehong Mao and Wuyang Zhou. High Girth LDPC Codes Construction Based on Combinatorial design. IEEE Vehicular Technology Conference Spring 2005.
[39] Lei Liu, Jie Huang,Wuyang Zhou and Shengli Zhou. Construction of Nonbinary Quasi-Cyclic LDPC Codes with Continuously Variable Length [J], submmittied to Communication letter 2008.
[40] Jeongseok Ha, Jaehong Kim, and Steven W. McLaughlin, Senior Member, IEEE“Rate-Compatible Puncturing of Low-Density Parity-Check Codes”IEEE Transactions on information theory vol.50, NO 11, November 2004.