低密度校验码二部图构造算法研究
|
摘要
低密度校验(LDPC)码由于其低译码复杂度和可任意逼近香农限的良好性能而成为目前最佳的编码技术之一,越来越多的编码研究学者开始关注如何构造性能好的LDPC码。Tanner图的构造是基于图模型构造LDPC码中一个非常重要的问题。通过构造良好的LDPC码的Tanner图,可以改善LDPC码的译码性能。
本文在对LDPC码现有理论研究基础上,基于启发性的搜索方法和EMD算法的特点,提出了一种新的二部图展开算法。本文的主要工作概括为：
1.简要阐述了LDPC码基于图模型的编译码思想,系统分析了影响LDPC码译码性能的主要因素——二部图的度分布序列、环和连通性,重点研究了二部图的连通性对LDPC码译码性能的影响。
2.详细分析了LDPC码中构造二部图的几种构造算法：消环算法和改善图的连通性的算法。并通过仿真表明这些算法都能有效降低LDPC码的误码率和错误平层。同时,对所构LDPC码译码性能进行了简单的分析。
3.在深入研究以上几种构图算法的基础上,给出了IPEG算法中ACE值的计算方法,提出了基于EMD算法的一种二部图展开算法,新的展开算法更适合在EMD算法中使用。同时给出了EMD算法的仿真及其性能分析。
Low-density parity-check codes (LDPC) in graphical models come to be one of the best coding technologies because of their low-complicity iterative decoding algorithm and capacity approaching performance, and it is how to construct LDPC code with good performance that attract more and more researchers'eyes in recent years. The construction of bipartite graph plays an important role in the LDPC code-construction which is based on graphical models. The performance of low-density parity-check codes can be improved by constructing a good Tanner graph.
In this dissertation, the basic principles of the coding and decoding of LDPC codes are studied systematically. A new algorithm of bipartite-graph-expanding is proposed for construction of Tanner graph. The main results and contents are summarized as follows.
1. The principles of coding and decoding for low-density parity-check codes are briefly summarized, the main factors which can impact the performance of LDPC codes such as degree sequence, cycles and connectivity of Tanner graph are systematically analyzed, emphasis on the graph connectivity.
2. Several algorithms for constructing Tanner graph of LDPC codes such as cycle-eliminating algorithms and connectivity-improving algorithms are analyzed in detail. The simulation results show that the codes constructed with these algorithms has lower bit error rate and error floor. The graph of simulation performance is presented. Besides, the performance of the codes constructed with these algorithms is analyzed.
3. Based on the study of construction algorithm mentioned before, a mothed of computing ACE value is given, a new bipartite-graph-expanding algorithm based on EMD algorithm is proposed, and the new algorithm is fit for EMD algorithm. Moreover, the software simulation was given, and the performance of EMD algorithm was analyzed.
本文在对LDPC码现有理论研究基础上,基于启发性的搜索方法和EMD算法的特点,提出了一种新的二部图展开算法。本文的主要工作概括为：
1.简要阐述了LDPC码基于图模型的编译码思想,系统分析了影响LDPC码译码性能的主要因素——二部图的度分布序列、环和连通性,重点研究了二部图的连通性对LDPC码译码性能的影响。
2.详细分析了LDPC码中构造二部图的几种构造算法：消环算法和改善图的连通性的算法。并通过仿真表明这些算法都能有效降低LDPC码的误码率和错误平层。同时,对所构LDPC码译码性能进行了简单的分析。
3.在深入研究以上几种构图算法的基础上,给出了IPEG算法中ACE值的计算方法,提出了基于EMD算法的一种二部图展开算法,新的展开算法更适合在EMD算法中使用。同时给出了EMD算法的仿真及其性能分析。
Low-density parity-check codes (LDPC) in graphical models come to be one of the best coding technologies because of their low-complicity iterative decoding algorithm and capacity approaching performance, and it is how to construct LDPC code with good performance that attract more and more researchers'eyes in recent years. The construction of bipartite graph plays an important role in the LDPC code-construction which is based on graphical models. The performance of low-density parity-check codes can be improved by constructing a good Tanner graph.
In this dissertation, the basic principles of the coding and decoding of LDPC codes are studied systematically. A new algorithm of bipartite-graph-expanding is proposed for construction of Tanner graph. The main results and contents are summarized as follows.
1. The principles of coding and decoding for low-density parity-check codes are briefly summarized, the main factors which can impact the performance of LDPC codes such as degree sequence, cycles and connectivity of Tanner graph are systematically analyzed, emphasis on the graph connectivity.
2. Several algorithms for constructing Tanner graph of LDPC codes such as cycle-eliminating algorithms and connectivity-improving algorithms are analyzed in detail. The simulation results show that the codes constructed with these algorithms has lower bit error rate and error floor. The graph of simulation performance is presented. Besides, the performance of the codes constructed with these algorithms is analyzed.
3. Based on the study of construction algorithm mentioned before, a mothed of computing ACE value is given, a new bipartite-graph-expanding algorithm based on EMD algorithm is proposed, and the new algorithm is fit for EMD algorithm. Moreover, the software simulation was given, and the performance of EMD algorithm was analyzed.
引文
[1]J.G. Proakis. Digital Communications,3rd ed. New York:McGraw-Hill,1995.
[2]王新梅,肖国镇.纠错码原理与方法.西安电子科技大学出版社,1991.
[3]王育民,梁传甲.信息与编码理论.西北电讯工程学院出版社,1986.
[4]T.M. Cover and J.A. Thomas, Elements of Information Theory. New York, Wiley 1991.
[5]R.E.Blahut, Principles and Practice of Information Theory. Reading, MA: Addison-wesley,1987.
[6]C. Berrou a,A. Glavieux. Near optimum error correcting coding and decoding: turbo-codes. IEEE Trans. Comm.,44(10):1261-1271, Oct.1996.
[7]C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding:turbo-codes. In Proc. of ICC'93. pp.1064-1070, May 1993.
[8]R.G. Gallager. Low density parity-check codes. Cambridge. MA:MIT Press, 1963.
[9]R.G. Gallager. Low density parity-check codes. IRE Trans. Inf. Theory,Jan.1962. 8(1):21-28,
[10]G. D. Forney, Jr, "Codes on graphs:New and wiews," In Proc.2nd International Symposium on Turbo Codes and Related Topics, Brest France, pp.9-16, Sept. 1988.
[11]G. D. Forney, Jr, "Codes on graphs:normal realizations," IEEE Trans. Inform. Theory, vol47, no2, pp.520-548, Feb.2001.
[12]R. J. McEliece, "Are Turbo-like codes effective on nonstandard channels?" IEEE Inform. Theory Society Newsletter, vol.51, no.4, Dec.2001.
[13]D.J.C. MacKay. Good error correcting codes based on very sparse matrices. IEEE Trans. Inf. Theory,45(2):399-431,1999.
[14]N. Wiberg. Codes and decoding on general graphs. Ph.D. dissertation. Linkoping University, Linkoping, Sweden,1996.
[15]D.J.C. MacKay. Turbo codes are low-density parity-check codes. [Online], available:http://www.cs.toronto.edu/-mackay/abstracts/-turbo-ldpc-html,1998.
[16]N. Wiberg, H.-A. Loeliger, and R. Koetter. Codes and iterative decoding on general graphs. European Trans. Telecomm.,6:513-525,1995.
[17]M. Siper and D. A. Spielman, "Expander codes," IEEE Trans. Inform. Theory, vol.42, no.6, November 1996. pp.1710-1722.
[18]D. J. C. MacKay and R. M. Neal, "Near Shannon limit performance of low-density parity-check codes," Electronics Letters, vol.32, August 1996. pp. 1645-1646.
[19]Tanner, "A recursive approach to low complexity codes," IEEE Trans. Inform. Theory, vol.27, no.5. Sept.1981. pp.533-547.
[20]G. Ungerboeck, "Channel coding with multilevel/phase signals," IEEE Trans. Inform. Theory, vol.28, no.1, Jan.1982. pp.55-67.
[21]N. Alon and M. Luby, "A linear-time erasure-resilient code with nearly optimal recovery," IEEE Trans. Inform. Theory, vol.42, Nov.1996. pp.1732-1736.
[22]Sae-Young Chung, G. D. Forney, Jr., T. J. Richardson, and Rudiger Urbanke, "On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit, " IEEE Comm. Letters, vol.5, no.2, Feb.2001.
[23]X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, "Progressive edge-growth Tanner graphs," in Proc. IEEE GLOBECOM 2001, San Antonio, TX, Nov.2001. pp. 995-1001.
[24]J. A. McGowan and R. C. Williamson, "Loop removal from LDPC Codes," in Information Theory Workshop,2003. Proceedings.2003 IEEE,2003, pp. 230-233.
[25]Tao Tian, Christopher R.Jones,John D.Villasenor and Richard D.Wesel, "Selective avoidance of cycles in Irregular LDPC code Construction,"IEEE Trans.on Commun.,vol.52,no.8, Aug.2004. pp.1242-1247.
[26]Hua Xiao and Amir H. Banihashemi, "Improved Progressive-Edge-Growth (PEG) Construction of Irregular LDPC Codes" in Proc. IEEE COMMUNICATIONS LETTERS, VOL.8, NO.12, DECEMBER 2004
[27]Sung-Ha Kim, Joon-Sung kim, Dae-Son Kim, "LDPC code Construction with Low Error Floor Based on the IPEG Algorithm" in Proc. IEEE COMMUNICATIONS LETTERS, VOL.11,NO.7,JULY 2007
[28]M.C. Davey. Error-correction using low-density parity-check codes. Ph.D. dissertation, University Cambridge, Cambridge, UK, Dec.1999.
[29]M.G. Luby, M. Mitzenmacher, M.A. Shokrollahi, D.A.Spielman, and V. Stemann. Practical loss-resilient codes. In Proc.29th Annu. Symp. Theory of Computing, 1997. pp.150-159.
[30]J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege. A digital fountain approach to reliable distribution of bulk data. [Online], available at http://www. icsi. berkeley. edu/-luby/,1998.
[31]M.G. Luby, M. Mitzenmacher, and M.A. Shokrollahi. Analysis of random processes via and-or tree evaluation. In Proc.9th Annu. ACM-SIAM Symp. Discrete Algorithms,1998. pp.364-373.
[32]Luby, M. Mitzenmacher, M.A. Shokrollahi, and D.A. Spielman. Improved low-density parity-check codes using irregular graphs and belief propagation. In Proc. of 1998 IEEE ISIT, Cambridge, MA, Aug.1998. pp.117.
[33]M. A. Shokrollahi and R. Storn, "Design of efficient erasure codes with differential evolution," In Proc. of 2000 IEEE ISIT, Sorrento, Italy, June 2000.
[34]M. A. Shokrollahi, "New sequences of linear time erasure codes approaching the channel capcity," In Pro. AAECC'13, Lecture Notes in Computer Science 1719, 1999. pp.65-76.
[35]M. A. Shokrollahi, "Codes and graphs," available at http://www. Shokrollahi. com/amain.pyb.html.
[36]M. A. Shokrollahi, "Capacity-achieving sequences," available at http://www. shokrollahi. com/amain.pyb.html.
[37]C.Di, D. Proietti, E.Telatar, T.Richardson and R.Urbanke, "Finite length analysis of low-density parity-check codes on the binary erasure channel,"IEEE Trans. Inform. Theory, vol.48.1982. pp.71-78.
[38]S. Deering. Multicast Routing in a Datagram Internetwork. Ph.D. dissertation. Stanford University, Dec.1991.
[39]D. Rubenstein, J. Kurose, and D. Towsley. Real-time reliable multicast using proactive forward error correction. [Online], available at http://citeseer.nj. nec.com/110093.html.
[40]J.C. Lin, S. Paul. RMTP:A reliable Multicast Transport Protocol. IEEE INFOCOM'96, Mar.1996. pp.1414-1424.
[41]S. Floyd, V. Jacobson, C.G. Liu, S. McCanne, L. Zhang. A reliable multicast framework for light-weight sessions and application level framing. In ACM SIGCOMM'95, Aug.1995. pp.342-356.
[42]S. McCanne, V. Jacobson, and M. Vetterli. Receiver-driven layered multicast. In Proc. of ACM SIGCOMM'96,1996. pp.117-130.
[43]C.K. Miller. Reliable multicast protocols:A practical View. In Proc. of the 22nd Annual Conference on Local Computer networks (LCN'97),1997.
[44]L. Rizzo. Effective erasure codes for reliable computer communication protocols. In Computer communication Review. April 1997.
[45]L. Rizzo, and L. Vicisano. A reliable multicast data distribution protocol based on software FEC Techniques. In Proc. of HPCS'97, Greece, June 1997.
[46]L. Vicisano, L. Rizzo, and J. Crowcroft. TCP-like congestion control for layered multicast data transfer. In Proc. of INFOCOM'98, CA, April 1998.
[47]L.Rizzo. On the feasibility of software FEC. DEIT technical Report LR970131.
[48]T.J. Richardson, M.A. Shokrollahi, and R.L. Urbanke. Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inf. Theory, Feb.2001.47(2):619-637.
[49]M.G. Luby, M. Mitzenmacher, M.A. Shokrollahi, and D.A. Spielman. Analysis of low-density codes and improved designs using irregular graphs. In Proc.30th Annu. Symp. Theory of Computing,1998. pp.249-258.
[50]Tom Richardson, "Error floors of LDPC codes," tjr@flarion.com.
[51]David J.C.MacKay and Michael S.Postol, "Weaknesses of Margulis and Ramanujan-Margulis Low-Density Parity-Check Codes," available at http://www.elsevier.nl/locate/entcs/volume74.html
[52]T. Richardson, M. Shokrollahi, and R. Urbanke, "Design of capacity approaching irregular low-density parity check codes." IEEE Trans. Inf.Theory, vol.47, pp. 619-637, Feb.2001.
[2]王新梅,肖国镇.纠错码原理与方法.西安电子科技大学出版社,1991.
[3]王育民,梁传甲.信息与编码理论.西北电讯工程学院出版社,1986.
[4]T.M. Cover and J.A. Thomas, Elements of Information Theory. New York, Wiley 1991.
[5]R.E.Blahut, Principles and Practice of Information Theory. Reading, MA: Addison-wesley,1987.
[6]C. Berrou a,A. Glavieux. Near optimum error correcting coding and decoding: turbo-codes. IEEE Trans. Comm.,44(10):1261-1271, Oct.1996.
[7]C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding:turbo-codes. In Proc. of ICC'93. pp.1064-1070, May 1993.
[8]R.G. Gallager. Low density parity-check codes. Cambridge. MA:MIT Press, 1963.
[9]R.G. Gallager. Low density parity-check codes. IRE Trans. Inf. Theory,Jan.1962. 8(1):21-28,
[10]G. D. Forney, Jr, "Codes on graphs:New and wiews," In Proc.2nd International Symposium on Turbo Codes and Related Topics, Brest France, pp.9-16, Sept. 1988.
[11]G. D. Forney, Jr, "Codes on graphs:normal realizations," IEEE Trans. Inform. Theory, vol47, no2, pp.520-548, Feb.2001.
[12]R. J. McEliece, "Are Turbo-like codes effective on nonstandard channels?" IEEE Inform. Theory Society Newsletter, vol.51, no.4, Dec.2001.
[13]D.J.C. MacKay. Good error correcting codes based on very sparse matrices. IEEE Trans. Inf. Theory,45(2):399-431,1999.
[14]N. Wiberg. Codes and decoding on general graphs. Ph.D. dissertation. Linkoping University, Linkoping, Sweden,1996.
[15]D.J.C. MacKay. Turbo codes are low-density parity-check codes. [Online], available:http://www.cs.toronto.edu/-mackay/abstracts/-turbo-ldpc-html,1998.
[16]N. Wiberg, H.-A. Loeliger, and R. Koetter. Codes and iterative decoding on general graphs. European Trans. Telecomm.,6:513-525,1995.
[17]M. Siper and D. A. Spielman, "Expander codes," IEEE Trans. Inform. Theory, vol.42, no.6, November 1996. pp.1710-1722.
[18]D. J. C. MacKay and R. M. Neal, "Near Shannon limit performance of low-density parity-check codes," Electronics Letters, vol.32, August 1996. pp. 1645-1646.
[19]Tanner, "A recursive approach to low complexity codes," IEEE Trans. Inform. Theory, vol.27, no.5. Sept.1981. pp.533-547.
[20]G. Ungerboeck, "Channel coding with multilevel/phase signals," IEEE Trans. Inform. Theory, vol.28, no.1, Jan.1982. pp.55-67.
[21]N. Alon and M. Luby, "A linear-time erasure-resilient code with nearly optimal recovery," IEEE Trans. Inform. Theory, vol.42, Nov.1996. pp.1732-1736.
[22]Sae-Young Chung, G. D. Forney, Jr., T. J. Richardson, and Rudiger Urbanke, "On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit, " IEEE Comm. Letters, vol.5, no.2, Feb.2001.
[23]X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, "Progressive edge-growth Tanner graphs," in Proc. IEEE GLOBECOM 2001, San Antonio, TX, Nov.2001. pp. 995-1001.
[24]J. A. McGowan and R. C. Williamson, "Loop removal from LDPC Codes," in Information Theory Workshop,2003. Proceedings.2003 IEEE,2003, pp. 230-233.
[25]Tao Tian, Christopher R.Jones,John D.Villasenor and Richard D.Wesel, "Selective avoidance of cycles in Irregular LDPC code Construction,"IEEE Trans.on Commun.,vol.52,no.8, Aug.2004. pp.1242-1247.
[26]Hua Xiao and Amir H. Banihashemi, "Improved Progressive-Edge-Growth (PEG) Construction of Irregular LDPC Codes" in Proc. IEEE COMMUNICATIONS LETTERS, VOL.8, NO.12, DECEMBER 2004
[27]Sung-Ha Kim, Joon-Sung kim, Dae-Son Kim, "LDPC code Construction with Low Error Floor Based on the IPEG Algorithm" in Proc. IEEE COMMUNICATIONS LETTERS, VOL.11,NO.7,JULY 2007
[28]M.C. Davey. Error-correction using low-density parity-check codes. Ph.D. dissertation, University Cambridge, Cambridge, UK, Dec.1999.
[29]M.G. Luby, M. Mitzenmacher, M.A. Shokrollahi, D.A.Spielman, and V. Stemann. Practical loss-resilient codes. In Proc.29th Annu. Symp. Theory of Computing, 1997. pp.150-159.
[30]J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege. A digital fountain approach to reliable distribution of bulk data. [Online], available at http://www. icsi. berkeley. edu/-luby/,1998.
[31]M.G. Luby, M. Mitzenmacher, and M.A. Shokrollahi. Analysis of random processes via and-or tree evaluation. In Proc.9th Annu. ACM-SIAM Symp. Discrete Algorithms,1998. pp.364-373.
[32]Luby, M. Mitzenmacher, M.A. Shokrollahi, and D.A. Spielman. Improved low-density parity-check codes using irregular graphs and belief propagation. In Proc. of 1998 IEEE ISIT, Cambridge, MA, Aug.1998. pp.117.
[33]M. A. Shokrollahi and R. Storn, "Design of efficient erasure codes with differential evolution," In Proc. of 2000 IEEE ISIT, Sorrento, Italy, June 2000.
[34]M. A. Shokrollahi, "New sequences of linear time erasure codes approaching the channel capcity," In Pro. AAECC'13, Lecture Notes in Computer Science 1719, 1999. pp.65-76.
[35]M. A. Shokrollahi, "Codes and graphs," available at http://www. Shokrollahi. com/amain.pyb.html.
[36]M. A. Shokrollahi, "Capacity-achieving sequences," available at http://www. shokrollahi. com/amain.pyb.html.
[37]C.Di, D. Proietti, E.Telatar, T.Richardson and R.Urbanke, "Finite length analysis of low-density parity-check codes on the binary erasure channel,"IEEE Trans. Inform. Theory, vol.48.1982. pp.71-78.
[38]S. Deering. Multicast Routing in a Datagram Internetwork. Ph.D. dissertation. Stanford University, Dec.1991.
[39]D. Rubenstein, J. Kurose, and D. Towsley. Real-time reliable multicast using proactive forward error correction. [Online], available at http://citeseer.nj. nec.com/110093.html.
[40]J.C. Lin, S. Paul. RMTP:A reliable Multicast Transport Protocol. IEEE INFOCOM'96, Mar.1996. pp.1414-1424.
[41]S. Floyd, V. Jacobson, C.G. Liu, S. McCanne, L. Zhang. A reliable multicast framework for light-weight sessions and application level framing. In ACM SIGCOMM'95, Aug.1995. pp.342-356.
[42]S. McCanne, V. Jacobson, and M. Vetterli. Receiver-driven layered multicast. In Proc. of ACM SIGCOMM'96,1996. pp.117-130.
[43]C.K. Miller. Reliable multicast protocols:A practical View. In Proc. of the 22nd Annual Conference on Local Computer networks (LCN'97),1997.
[44]L. Rizzo. Effective erasure codes for reliable computer communication protocols. In Computer communication Review. April 1997.
[45]L. Rizzo, and L. Vicisano. A reliable multicast data distribution protocol based on software FEC Techniques. In Proc. of HPCS'97, Greece, June 1997.
[46]L. Vicisano, L. Rizzo, and J. Crowcroft. TCP-like congestion control for layered multicast data transfer. In Proc. of INFOCOM'98, CA, April 1998.
[47]L.Rizzo. On the feasibility of software FEC. DEIT technical Report LR970131.
[48]T.J. Richardson, M.A. Shokrollahi, and R.L. Urbanke. Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inf. Theory, Feb.2001.47(2):619-637.
[49]M.G. Luby, M. Mitzenmacher, M.A. Shokrollahi, and D.A. Spielman. Analysis of low-density codes and improved designs using irregular graphs. In Proc.30th Annu. Symp. Theory of Computing,1998. pp.249-258.
[50]Tom Richardson, "Error floors of LDPC codes," tjr@flarion.com.
[51]David J.C.MacKay and Michael S.Postol, "Weaknesses of Margulis and Ramanujan-Margulis Low-Density Parity-Check Codes," available at http://www.elsevier.nl/locate/entcs/volume74.html
[52]T. Richardson, M. Shokrollahi, and R. Urbanke, "Design of capacity approaching irregular low-density parity check codes." IEEE Trans. Inf.Theory, vol.47, pp. 619-637, Feb.2001.