基于LDPC码的联合信源信道译码算法研究及其应用
|
摘要
低密度奇偶校验码(Low-Density Parity-Check codes, LDPC码)是由Gallager在1962年提出的一种基于稀疏校验矩阵的线性分组纠错码,因其具有逼近香农限的优秀性能,而成为了当前信道编码领域最受瞩目的热点之一。信源信道联合编译码是由M.C.Elience于1977年首先提出来,被用于提高通信系统的整体优化,取得了预期效果。本文采用理论分析和计算机仿真相结合的方法,对基于LDPC码的联合信源信道译码算法及其在数字水印系统中的应用展开研究。论文主要工作包括：
(1)系统地论述了LDPC码的基本原理,LDPC码的结构和校验矩阵的构造方法。详细分析了LDPC码的编译码原理和影响LDPC码性能的几个因素,在此基础之上进行了LDPC码编译码器的结构设计。
(2)研究了基于隐马尔可夫信源估计和LDPC码的联合信源信道译码算法。从隐马尔可夫信源估计算法入手,利用它与LDPC码进行联合译码,对该联合译码算法进行了改进,并对信源模型的阶数进行了更新,对各种译码算法的性能进行了全面的仿真分析。
(3)将基于LDPC码的联合译码算法应用到数字图像水印系统。在该系统中先对数字水印进行LDPC纠错编码,然后在DCT域将编码后的序列嵌入到原始图像中,提取水印时,用隐马尔可夫模型来描述水印图像,利用信源信道联合迭代译码算法进行提取,从而降低了水印在传输过程中的误码率。
AWGN信道的仿真结果表明,采用联合的信源信道译码算法能够改善LDPC码的译码性能。将此联合算法应用到图像数字水印系统中,可以提高水印传输的可靠性,增强水印的抗攻击能力。
Low-Density Parity-Check code, introduced by Gallager in 1962, is one of linear block error-correcting codes based on the sparse parity-check matrix and its performance is close to Shannon limit. Due to such good performance, LDPC has become more and more attractive in channel encoding field. Joint source-channel encoding and decoding was firstly introduced by McElience in 1977 and then used in optimizing communication system. In this paper, we focus on joint source-channel decoding algorithms based on LDPC codes and their applications to digital watermark systems. The main work is as follows:
(1) This paper gives a systematic investigation of LDPC codes. Firstly, how to construct the LDPC check matrix is introduced; and then the encoding and decoding theory of LDPC codes is describled in detailed. Besides, several factors influencing LDPC codes are given. On the basis, the encoder and decoder of LDPC are designed.
(2) Research on joint source-channel decoding based on Hidden Markov Source Model and LDPC codes. Starting with re-estimated algorithm of Hidden Markov Model, this paper describes the joint decoding algorithm, the improved algorithm and the algorithm with changed steps of source, also gives the simulation results of each algorithm.
(3)The joint source-channel decoding algorithm based on LDPC is applied to digital watermark system. In the system, the watermark is firstly coded, and then embedded into the DCT field of the image. In the decoder, the watermark can be describled as Hidden Markov Model, extracted with joint source-channel iterative decoding algorithm.
The experiment based on AWGN channel shows that the algorithm of joint source-channel decoding can improve the performance of LDPC codes. When the algorithm is applied to the digital image watermark, it can successfully improve the reliability of watermark and enhance its anti-attacking ability.
(1)系统地论述了LDPC码的基本原理,LDPC码的结构和校验矩阵的构造方法。详细分析了LDPC码的编译码原理和影响LDPC码性能的几个因素,在此基础之上进行了LDPC码编译码器的结构设计。
(2)研究了基于隐马尔可夫信源估计和LDPC码的联合信源信道译码算法。从隐马尔可夫信源估计算法入手,利用它与LDPC码进行联合译码,对该联合译码算法进行了改进,并对信源模型的阶数进行了更新,对各种译码算法的性能进行了全面的仿真分析。
(3)将基于LDPC码的联合译码算法应用到数字图像水印系统。在该系统中先对数字水印进行LDPC纠错编码,然后在DCT域将编码后的序列嵌入到原始图像中,提取水印时,用隐马尔可夫模型来描述水印图像,利用信源信道联合迭代译码算法进行提取,从而降低了水印在传输过程中的误码率。
AWGN信道的仿真结果表明,采用联合的信源信道译码算法能够改善LDPC码的译码性能。将此联合算法应用到图像数字水印系统中,可以提高水印传输的可靠性,增强水印的抗攻击能力。
Low-Density Parity-Check code, introduced by Gallager in 1962, is one of linear block error-correcting codes based on the sparse parity-check matrix and its performance is close to Shannon limit. Due to such good performance, LDPC has become more and more attractive in channel encoding field. Joint source-channel encoding and decoding was firstly introduced by McElience in 1977 and then used in optimizing communication system. In this paper, we focus on joint source-channel decoding algorithms based on LDPC codes and their applications to digital watermark systems. The main work is as follows:
(1) This paper gives a systematic investigation of LDPC codes. Firstly, how to construct the LDPC check matrix is introduced; and then the encoding and decoding theory of LDPC codes is describled in detailed. Besides, several factors influencing LDPC codes are given. On the basis, the encoder and decoder of LDPC are designed.
(2) Research on joint source-channel decoding based on Hidden Markov Source Model and LDPC codes. Starting with re-estimated algorithm of Hidden Markov Model, this paper describes the joint decoding algorithm, the improved algorithm and the algorithm with changed steps of source, also gives the simulation results of each algorithm.
(3)The joint source-channel decoding algorithm based on LDPC is applied to digital watermark system. In the system, the watermark is firstly coded, and then embedded into the DCT field of the image. In the decoder, the watermark can be describled as Hidden Markov Model, extracted with joint source-channel iterative decoding algorithm.
The experiment based on AWGN channel shows that the algorithm of joint source-channel decoding can improve the performance of LDPC codes. When the algorithm is applied to the digital image watermark, it can successfully improve the reliability of watermark and enhance its anti-attacking ability.
引文
[1]C.E.Shannon, "A Mathematical Theory of Communications", B.S.T.J, Vol.27, pp.379-423,623-656, July 1948.
[2]R.C.Bose,D.K.Ray-Chaudhuri, "On a class of error correcting binary group codes",Information and Control, vol.3,March 1960, pp.68-79.
[3]P.Elias, "Coding for noisy channels", IRE Convention Record, vol.3, part,1965, pp 37-46.
[4]C.Berror,A.Glaviex and P.Thitimajshima, "Near Shannon limit error-correcting coding and decoding: Turbo-codes",In Proc 1993 IEEE.International Conference on Communication,Geneva,Switaerland,pp 1064-1070,1993.
[5]R.G.Gallager, "Low-Density Parity-Check Codes", IRE Trans Inform Theory, IT-8:21-28, January 1962.
[6]LUBYMG,Improved Low-Density Parity-Check Codes Using Irregular Graphs[J].IEEE Trans on Inform Theroy,2001,47(2):285-298.
[7]DAVEYM C.Error-correction using Low-Density Parity-Check Codes,Dissertation submitted in candidature for the degree of Doctor of Philosophy[D].Univ of Cambirdge,1999.
[8]LUBY M G.Efficient Erasure Correcting Codes [J].IEEE Trans on Inform Theory,2001,47(2):569-584.
[9]CAMPELLO J.Extended Bit-Filling and LDPC codes Design[A].Proc IEEE Globecom Conf[C].San Antonio,TX,Nov.2001,form Internet,(campello,dmodha)@us.ibm.com.
[10]KOUY,LINS,FOSSORIER,M. Low density parity check codes Construction based on finite geometries [A]. Proc IEEE Globecom Conf[C].Sam Francisico,2000.825-829.
[11]GALLAGERR G.Low density parity check codes [J].IRE Trans on Inform Theory,1962,8:21-28.
[12]RICHARDSON T J,URBANKER L.The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding[J].IEEE Trans on Inform Theroy,2001,47(2):599-618.
[13]CHEN J.FORRORIER M. Near optimum universal belief propagation based decoding of LDPC codes[J]. IEEE Trans on communication,2002,50(3):344-346.
[14]BHATT T. Fixed Point DSP Implementation of Low-Density Parity-Check Codes[EB/OL].from Internet, tejas@ee.tamu.edu.
[15]Mattew C,Davey,David,J.C.MacKay. Low Density Parity Check Codes overGF(q)[M].ITW1998, Kill(?)ney,Ireland:22-26
[16]D.J.C.McKay,"Good Error-Correcting Codes Based on Very Sparse Matrices"[J].IEEE Trans Inform Theory.1990.45(3):399-431.
[17]M.F(?)ssorier.Quasi-cyclic Low Density Parity Check Codes.Proc IEEE IntSymp Information Theory.2003:150.
[18]Zhenyu Liu,Dimitris A.Pados.A Decoding Algorithm for Finite-geometry LDPC codes.IEEE Transactions on communications 2005,53(3):415-421.
[19]M.Sipser,D.A.Spielman, "Expander Codes",IEEE Trans Inform Theory,1996,42(6):1710-1722.
[20]A.Lu(?)otzky,R.Phillips,P.Sarnak.Ramanujan Graphs.Combinatorica.1988,8(3):261-277.
[21]Hao Zhong,Tong Zhang.Block-LDPC:A Practical LDPC Coding System Design Approach.IEEE Transactions on Information Theory.April 2005,52(4):766-775.
[22]J.Rosenthal,P.O.Vontobel.Constructions of LDPC Codes Using Ramanujan Graphs and Ideas form Margulis.Proc.38th.Allerton conference on Communications,Control and Computing.October2000: 248-257.
[23]M.G.Luby,M.Mitzenmacher,M.A.Shokrollahi and D.A.Spielman, "Improved low density parity-check Codes using irregular graphs and bilief propagation",In Proceedings of the IEEE International Symposium on Information Theory(ISIT),1998:117.
[24]Y.Kou,S.Lin and M.Fossorier, "Low-Density Parity-Check Codes Based on Finite Geometries: Arediscovery and New Results",IEEE Trans Inform Theory,Vol.47,No.7,pp.2711-2736,Nov2001.
[25]T.J.Richardson and R.Urbanke, "Efficient encoding of low density parity checki codes",IEEE Trans Inform Theory,2001,47(2):638-656
[26]吴伟陵.通信系统的优化理论基础-纪念Shannon信息论四十周年[J].电子学报,1990,18(3)：100-105.
[27]G.F.Elmasry,Embedding channel coding in arithmetic coding.IEEE Proc.1999,126(2):73-78.
[28]BINCHAN J A C.Multicarrier modulation for data transmission:an idea whose time has come[J].IEEE Communication Magazine,1990,37(5):5-14.
[29]Tarokh V,Seshadri N,Calderbank A.R.Space-time codes for high data rate wireless communication: Performance analysis and code construction[J].IEEE Transaction on Information Theory,1998.44(3):
744-765.
[30]Agatwal D,Tarokh V,Nagubi A,Seshadri N.space-time coded OFDM for high data rate wireless communication over wideband channels[A].The 48th IEEE Vehicular Technology Conference[C]. Ottawa,Canada,1998:2232-2236.
[31]Sayood K,Hasan H O,Demir N.Joint source/channel coding for variable length codes[J].IEEE Tans.On Comm.2000,48(5):787-794.
[32]陈明.通信与信息工程中的随机过程[M].南京：东南大学出版社,2001.
[33]Miller D J,Moonseo Park.A sequence-based approximate MMSE decoder for source coding over noisy channels using discrete hidden Markov models[J].IEEE Transaction on Communication,1998,46(2): 222-231.
[34]殷玮玮,吴乐南.基于HMM的信源-信道迭代联合译码[J].通信学报,2006,27(7)：61-63.
[35]王炳锡,陈琦,邓峰森.数字水印技术[M].西安：西安电子科技大学出版社.2003.
[36]Liu Guoyin,Lu Jianhua and Wu Youshou. LDPC-based Joint Source-Channel Coding Scheme for Multimedia Communication [Z].The 2002 International Conference on Computational Science, Amsterdam,2002.
[37]田秋玲,王童,崔惠娟,唐昆.利用语音残留冗余的LDPC译码算法[J].清华大学学报,2006,46[7]：1254-1258.
[38]Tahereh Fazel, Thomas Fuja. Robust Transmission of MELP-Compressed Speech:An Illustrative Example of Joint Source-Channel Decoding [J].IEEE Transactions on Communication,2003,51(6): 973-982.
[39]SAYOOD K, BORKENHAGEN J C. Use of residual redundancy in the design of joint source and channel coders[J],IEEE Trans.on Commun.,1991,39(6),838-846.
[40]袁东风,张海霞等.宽带移动通信中的先进信道编码技术[M].北京：北京邮电大学出版.2004：54-65
[41]李赵红,侯建军.基于Logistic混沌映射的DCT域脆弱数字水印算法[J].电子学报,2006,34(12)：2134-2137.
[42]戴跃伟.信息隐藏技术的理论及应用研究[D].南京理工大学博士论文,2002.
[43]王丽娜,郭迟,李鹏.信息隐藏技术试验教程[M].武汉：武汉大学出版社.2004.
[2]R.C.Bose,D.K.Ray-Chaudhuri, "On a class of error correcting binary group codes",Information and Control, vol.3,March 1960, pp.68-79.
[3]P.Elias, "Coding for noisy channels", IRE Convention Record, vol.3, part,1965, pp 37-46.
[4]C.Berror,A.Glaviex and P.Thitimajshima, "Near Shannon limit error-correcting coding and decoding: Turbo-codes",In Proc 1993 IEEE.International Conference on Communication,Geneva,Switaerland,pp 1064-1070,1993.
[5]R.G.Gallager, "Low-Density Parity-Check Codes", IRE Trans Inform Theory, IT-8:21-28, January 1962.
[6]LUBYMG,Improved Low-Density Parity-Check Codes Using Irregular Graphs[J].IEEE Trans on Inform Theroy,2001,47(2):285-298.
[7]DAVEYM C.Error-correction using Low-Density Parity-Check Codes,Dissertation submitted in candidature for the degree of Doctor of Philosophy[D].Univ of Cambirdge,1999.
[8]LUBY M G.Efficient Erasure Correcting Codes [J].IEEE Trans on Inform Theory,2001,47(2):569-584.
[9]CAMPELLO J.Extended Bit-Filling and LDPC codes Design[A].Proc IEEE Globecom Conf[C].San Antonio,TX,Nov.2001,form Internet,(campello,dmodha)@us.ibm.com.
[10]KOUY,LINS,FOSSORIER,M. Low density parity check codes Construction based on finite geometries [A]. Proc IEEE Globecom Conf[C].Sam Francisico,2000.825-829.
[11]GALLAGERR G.Low density parity check codes [J].IRE Trans on Inform Theory,1962,8:21-28.
[12]RICHARDSON T J,URBANKER L.The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding[J].IEEE Trans on Inform Theroy,2001,47(2):599-618.
[13]CHEN J.FORRORIER M. Near optimum universal belief propagation based decoding of LDPC codes[J]. IEEE Trans on communication,2002,50(3):344-346.
[14]BHATT T. Fixed Point DSP Implementation of Low-Density Parity-Check Codes[EB/OL].from Internet, tejas@ee.tamu.edu.
[15]Mattew C,Davey,David,J.C.MacKay. Low Density Parity Check Codes overGF(q)[M].ITW1998, Kill(?)ney,Ireland:22-26
[16]D.J.C.McKay,"Good Error-Correcting Codes Based on Very Sparse Matrices"[J].IEEE Trans Inform Theory.1990.45(3):399-431.
[17]M.F(?)ssorier.Quasi-cyclic Low Density Parity Check Codes.Proc IEEE IntSymp Information Theory.2003:150.
[18]Zhenyu Liu,Dimitris A.Pados.A Decoding Algorithm for Finite-geometry LDPC codes.IEEE Transactions on communications 2005,53(3):415-421.
[19]M.Sipser,D.A.Spielman, "Expander Codes",IEEE Trans Inform Theory,1996,42(6):1710-1722.
[20]A.Lu(?)otzky,R.Phillips,P.Sarnak.Ramanujan Graphs.Combinatorica.1988,8(3):261-277.
[21]Hao Zhong,Tong Zhang.Block-LDPC:A Practical LDPC Coding System Design Approach.IEEE Transactions on Information Theory.April 2005,52(4):766-775.
[22]J.Rosenthal,P.O.Vontobel.Constructions of LDPC Codes Using Ramanujan Graphs and Ideas form Margulis.Proc.38th.Allerton conference on Communications,Control and Computing.October2000: 248-257.
[23]M.G.Luby,M.Mitzenmacher,M.A.Shokrollahi and D.A.Spielman, "Improved low density parity-check Codes using irregular graphs and bilief propagation",In Proceedings of the IEEE International Symposium on Information Theory(ISIT),1998:117.
[24]Y.Kou,S.Lin and M.Fossorier, "Low-Density Parity-Check Codes Based on Finite Geometries: Arediscovery and New Results",IEEE Trans Inform Theory,Vol.47,No.7,pp.2711-2736,Nov2001.
[25]T.J.Richardson and R.Urbanke, "Efficient encoding of low density parity checki codes",IEEE Trans Inform Theory,2001,47(2):638-656
[26]吴伟陵.通信系统的优化理论基础-纪念Shannon信息论四十周年[J].电子学报,1990,18(3)：100-105.
[27]G.F.Elmasry,Embedding channel coding in arithmetic coding.IEEE Proc.1999,126(2):73-78.
[28]BINCHAN J A C.Multicarrier modulation for data transmission:an idea whose time has come[J].IEEE Communication Magazine,1990,37(5):5-14.
[29]Tarokh V,Seshadri N,Calderbank A.R.Space-time codes for high data rate wireless communication: Performance analysis and code construction[J].IEEE Transaction on Information Theory,1998.44(3):
744-765.
[30]Agatwal D,Tarokh V,Nagubi A,Seshadri N.space-time coded OFDM for high data rate wireless communication over wideband channels[A].The 48th IEEE Vehicular Technology Conference[C]. Ottawa,Canada,1998:2232-2236.
[31]Sayood K,Hasan H O,Demir N.Joint source/channel coding for variable length codes[J].IEEE Tans.On Comm.2000,48(5):787-794.
[32]陈明.通信与信息工程中的随机过程[M].南京：东南大学出版社,2001.
[33]Miller D J,Moonseo Park.A sequence-based approximate MMSE decoder for source coding over noisy channels using discrete hidden Markov models[J].IEEE Transaction on Communication,1998,46(2): 222-231.
[34]殷玮玮,吴乐南.基于HMM的信源-信道迭代联合译码[J].通信学报,2006,27(7)：61-63.
[35]王炳锡,陈琦,邓峰森.数字水印技术[M].西安：西安电子科技大学出版社.2003.
[36]Liu Guoyin,Lu Jianhua and Wu Youshou. LDPC-based Joint Source-Channel Coding Scheme for Multimedia Communication [Z].The 2002 International Conference on Computational Science, Amsterdam,2002.
[37]田秋玲,王童,崔惠娟,唐昆.利用语音残留冗余的LDPC译码算法[J].清华大学学报,2006,46[7]：1254-1258.
[38]Tahereh Fazel, Thomas Fuja. Robust Transmission of MELP-Compressed Speech:An Illustrative Example of Joint Source-Channel Decoding [J].IEEE Transactions on Communication,2003,51(6): 973-982.
[39]SAYOOD K, BORKENHAGEN J C. Use of residual redundancy in the design of joint source and channel coders[J],IEEE Trans.on Commun.,1991,39(6),838-846.
[40]袁东风,张海霞等.宽带移动通信中的先进信道编码技术[M].北京：北京邮电大学出版.2004：54-65
[41]李赵红,侯建军.基于Logistic混沌映射的DCT域脆弱数字水印算法[J].电子学报,2006,34(12)：2134-2137.
[42]戴跃伟.信息隐藏技术的理论及应用研究[D].南京理工大学博士论文,2002.
[43]王丽娜,郭迟,李鹏.信息隐藏技术试验教程[M].武汉：武汉大学出版社.2004.