Декодирование линейным программированием: эффективный способ декодирования кодов контроля четности с низкой плотностью

Автор(и)

  • Мохамед Ракибул Ислам Исламский технологический университет, Бангладеш

DOI:

https://doi.org/10.20535/S0021347013020015

Ключові слова:

контроль четности с низкой плотностью, LPDC, линейное программирование, ЛП, адаптивное линейное программирование, АЛП, низкая сложность, декодирование

Анотація

Декодирование линейным программированием (ЛП) является альтернативой итеративным алгоритмам декодирования кодов контроля четности с низкой плотностью (LPDC). Хотя практические характеристики ЛП декодирования сравнимы с декодированием в процессе передачи сообщения, однако значительным преимуществом является его сравнительная совместимость с неасимптотическим анализом. Более того, оказывается, что существуют важные теоретические связи между ЛП декодированием и стандартными формами итеративного декодирования. Эти связи позволяют перенести теоретические новшества ЛП декодирования на итеративные алгоритмы. Отмеченные преимущества привлекли многих исследователей к использованию этого нового способа декодирования при работе с LPDC кодами. В данной статье приводится обширный обзор и обсуждение различных вопросов ЛП декодирования.

Посилання

Gallager, R. G. Low-Density Parity-Check Codes. MIT Press, 1963.

Richardson, T. J.; Shokrollahi, M. A.; Urbanke, R. L. "Design of capacity-approaching irregular low-density parity-check codes," IEEE Trans. Inf. Theory, Vol. 47, No. 2, p. 619–637, Feb. 2001. DOI: https://doi.org/10.1109/18.910578.

Chung, S.-Y.; Forney, G. D.; Richardson, T. J.; Urbanke, R. "On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit," IEEE Commun. Lett., Vol. 5, No. 2, p. 58–60, Feb. 2001. DOI: https://doi.org/10.1109/4234.905935.

Tanner, R. M. "A recursive approach to low complexity codes," IEEE Trans. Inf. Theory, Vol. 27, No. 5, p. 533–547, Sep. 1981. DOI: https://doi.org/10.1109/TIT.1981.1056404.

Feldman, J.; Karger, D. "Decoding turbo-like codes in polynomial time with provably good error-correcting performing via linear programming," Proc. of Int. Conf. on Foundations of Computer Science, Jul. 2002.

Feldman, J.; Karger, D. R.; Wainwright, M. J. "Linear programming-based decoding of turbo-like codes and its relation to iterative approaches," Proc. of 40th Annu. Allerton Conf. on Communication, Control, and Computing, Oct. 2002, Monticello, IL. Monticello, 2002.

Feldman, J.; Wainwright, M. J.; Karger, D. R. "Using linear programming to decode binary linear codes," IEEE Trans. Inf. Theory, Vol. 51, No. 3, p. 954–972, Mar. 2005. DOI: https://doi.org/10.1109/TIT.2004.842696.

Feldman, J.; Malkin, T.; Servedio, R. A.; Stein, C.; Wainwright, M. J. "LP decoding corrects a constant fraction of errors," IEEE Trans. Inf. Theory, Vol. 53, No. 1,P. 82–89, Jan. 2007. DOI: https://doi.org/10.1109/TIT.2006.887523.

Tanatmis, A.; Ruzika, S.; Hamacher, H. W.; Punekar, M.; Kienle, F.; When, N. "A separation algorithm for improved LP-decoding of linear block codes," IEEE Trans. Inf. Theory, Vol. 56, No. 7, p. 3277–3289, July 2010. DOI: https://doi.org/10.1109/TIT.2010.2048489.

Chertkov, M.; Stepanov, M. G. "An efficient pseudocodeword search algorithm for linear programming decoding of LDPC codes," IEEE Trans. Inf. Theory, Vol. 54, No. 4, P. 1514–1520, April 2008. DOI: https://doi.org/10.1109/TIT.2008.917682.

Sason, I. "Linear programming bounds on the degree distributions of LDPC code ensembles," Proc. of IEEE Int. Symp. on Information Theory, 28 June–3 July 2009, Seoul, Korea. IEEE, 2009. DOI: https://doi.org/10.1109/ISIT.2009.5205866.

Daskalakis, C.; Dimakis, A. G.; Karp, R. M.; Wainwright, M. J. "Probabilistic analysis of linear programming decoding," IEEE Trans. Inf. Theory, Vol. 54, No. 8, P. 3565–3578, August, 2008. DOI: https://doi.org/10.1109/TIT.2008.926452.

Daskalakis, C.; Dimakis, A. G.; Karp, R. M.; Wainwright, M. J. "Probabilistic analysis of linear programming decoding," Proc. of Forty-Fourth Annual Allerton Conf., 27–29 Sept 2006, Allerton House, UIUC, Illinois, USA. Illinois, 2006.

Arora, S.; Daskalakis, C.; Steurer, D.; "Message passing algorithms and improved LP decoding," IEEE Trans. Inf. Theory, Vol. 58, No. 12, p. 7260-7271, 2012. DOI: https://doi.org/10.1109/TIT.2012.2208584.

Halabi N.; Even, G. "LP decoding of regular LDPC codes in memoryless channels," IEEE Trans. Inf. Theory, Vol. 57, No. 2, P. 887–897, Feb. 2011. DOI: https://doi.org/10.1109/TIT.2010.2094830.

Halabi, N.; Even, G. "LP decoding of regular LDPC codes in memoryless channels," Proc. of Int. Conf. ISIT, 13–18 June 2010, Austin, Texas, USA. Texas, 2010.

Flanagan, M. F.; Skachek, V.; Byrne, E.; Greferath, M. "Linear-programming decoding of nonbinary linear codes," IEEE Trans. Inf. Theory, Vol. 55, No. 9, P. 4134–4154, Sept 2009. DOI: https://doi.org/10.1109/TIT.2009.2025571.

Taghavi, M. H.; Siegel, P. H. "Adaptive linear programming decoding," Proc. of Int. Symp. on Inf. Theory, 9-14 July 2006, Seattle, USA. IEEE, 2006, p. 1374–1378. DOI: https://doi.org/10.1109/ISIT.2006.262071.

Taghavi, M. H. N.; Siegel, P. H. "Adaptive methods for linear programming decoding," IEEE Trans. Inf. Theory, Vol. 54, No. 12, p. 5396–5410, Dec. 2008. DOI: https://doi.org/10.1109/TIT.2008.2006384.

Taghavi, M. H.; Siegel, P. H. "Efficient implementation of linear programming decoding," Proc. of Forty-Sixth Annual Allerton Conf., 23–26 Sept. 2008, Allerton House, UIUC, Illinois, USA. Illinois, 2008.

Taghavi, M. H.; Shokrollahi, A.; Siegel, P. H. "Efficient implementation of linear programming decoding," IEEE Trans. Inf. Theory, Vol. 57, No. 9, p. 5960-5982, 2011. DOI: https://doi.org/10.1109/TIT.2011.2161920.

Draper, S. C.; Yedidia, J. S.; Wang, Y. "ML decoding via mixed-integer adaptive linear programming," Proc. of Int. Symp. on Inf. Theory, 24-29 July 2007, Nice, France. IEEE, 2007. DOI: https://doi.org/10.1109/ISIT.2007.4557459.

Draper, S. C.; Yedidia, J. S. "Complexity scaling of mixed-integer linear programming decoding," Proc. of UCSD Workshop Inf. Theory Apps., Jan. 2008, San Diego. San Diego, 2008.

GNU linear programming kit. URI: http://www.gnu.org/software/glpk.

Yang, K.; Feldman, J.; Wang, X. "Nonlinear programming approaches to decoding low-density parity-check codes," IEEE J. Select. Areas Commun., Vol. 24, No. 8, p. 1603–1613, Aug. 2006. DOI: https://doi.org/10.1109/JSAC.2006.879405.

Wang, Y.; Yedidia, J. S.; Draper, S. C. "Multi-stage decoding of LDPC codes," Proc. of Int. Symp. on Inf. Theory, 28 June –3 July 2009, Seoul, Korea. IEEE, 2009. DOI: https://doi.org/10.1109/ISIT.2009.5205786.

Vontobel, P. O.; Koetter, R. "Towards low-complexity linear-programming decoding," Proc. of 4th Int. Symp. on Turbo Codes and Related Topics, 3-7 Apr 2006, Munich, Germany. VDE, 2006. URI: https://ieeexplore.ieee.org/document/5755808.

Vontobel, P. O.; Koetter, R. "On low-complexity linear-programming decoding of LDPC codes," European Trans. Telecom., Vol. 18, No. 5, p. 509–517, Aug 2007. DOI: https://doi.org/10.1002/ett.1184.

Yang, K.; Wang, X.; Feldman, J. "A new linear programming approach to decoding linear block codes," IEEE Trans. Inf. Theory, Vol. 54, No. 3, p. 1061–1072, Mar. 2008. DOI: https://doi.org/10.1109/TIT.2007.915712.

Burshtein, D.; Goldenberg, I. "Improved linear programming decoding and bounds on the minimum distance of LDPC codes," Proc. of IEEE Inf. Theory Workshop, ITW 2010, Dublin. Dublin, 2010. DOI: https://doi.org/10.1109/CIG.2010.5592887.

Punekar, M.; Flanagan, M. F. "Low complexity linear programming decoding of nonbinary linear codes," Proc. of 48th Annual Allerton Conf. on Communication, Control, and Computing (Allerton), 29 Sept–1 Oct 2010, Allerton House, UIUC, Illinois, USA. IEEE, 2010. DOI: https://doi.org/10.1109/ALLERTON.2010.5706881.

Punekar, M.; Vontobel, P. O.; Flanagan, M. F. "Low complexity LP decoding of nonbinary linear codes," arXiv:1007.1368v2 [cs.IT]. 4 Oct 2010.

Vontobel, P. O.; Koetter, R. "On the relationship between linear programming decoding and min-sum algorithm decoding," Proc. of IEEE Int. Symp. on Inf. Theory Applications, Oct. 2004, p. 991–996.

Vontobel, P. O.; Koetter, R. "Graph-cover decoding and finite-length analysis of message-passing iterative decoding of LDPC codes," URI: https://arxiv.org/pdf/cs/0512078.pdf.

Karmarkar, N. "A new polynomial-time algorithm for linear programming," Combinatorica, Vol. 4, No. 4, p. 373–395, Dec. 1984. DOI: https://doi.org/10.1007/BF02579150.

Bertsimas, D.; Tsitsiklis, J. N. Introduction to Linear Optimization. Athena Scientific, 1997.

Wadayama, T. "Interior point decoding for linear vector channels based on convex optimization," IEEE Trans. Inf. Theory, Vol. 56, No. 10, p. 4905–4921, Oct. 2010. DOI: https://doi.org/10.1109/TIT.2010.2060030.

Wadayama, T. "An LP decoding algorithm based on primal path-following interior point method," Proc. of IEEE Int. Symp. on Inf. Theory, 28 June-3 Jul 2009, Seoul, Korea. IEEE, 2009, p. 389–393. DOI: https://doi.org/10.1109/ISIT.2009.5205741.

Vontobel, P. O. "Interior-point algorithms for linear-programming decoding," Proc. of 3rd Annual Workshop on Inf. Theory and Its Appl., 27 Jan-1 Feb. 2008, San Diego, CA, USA. IEEE, 2008. DOI: https://doi.org/10.1109/ITA.2008.4601085.

Ngatched, T. M. N.; Alfa, A. S.; Cai, J. "Hybrid linear programming based decoding algorithm for LDPC codes," IEEE Trans. Commun., Vol. 59, No. 3, p. 740-749, 2011. DOI: https://doi.org/10.1109/TCOMM.2011.011811.090638.

Burshtein, D. "Iterative approximate linear programming decoding of LDPC codes with linear complexity," Proc. of Int. Conf. ISIT, 6-11 July 2008, Toronto, Canada. Toronto, 2008.

Burshtein, D. "Iterative approximate linear programming decoding of LDPC codes with linear complexity," IEEE Trans. Inf. Theory, Vol. 55, No. 11, p. 4835–4859, Nov. 2009. DOI: https://doi.org/10.1109/TIT.2009.2030477.

Goldin, D.; Burshtein, D. "Approximate iterative LP decoding of LDPC codes over GF(q) in linear complexity," Proc. of IEEE 26th Convention of Electrical and Electronics Engineers, 17-20 Nov. 2010, Eliat, Israel. IEEE, 2010. DOI: https://doi.org/10.1109/EEEI.2010.5661933.

Donoho, D. L. "High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension," Discrete Computational Geometry, Vol. 35, No. 4, p. 617–652, 2006. DOI: https://doi.org/10.1007/s00454-005-1220-0.

Donoho, D.; Tanner, J. "Neighborliness of randomly-projected simplices in high dimensions," PNAS, Vol. 102, No. 27, p. 9452–9457, 2005. DOI: https://doi.org/10.1073/pnas.0502258102.

Donoho, D. L.; Huo, X. "Uncertainty principles and ideal atomic decomposition," IEEE Trans. Inf. Theory, Vol. 47, No. 7, p. 2845–2862, 2001. DOI: https://doi.org/10.1109/18.959265.

Stojnic, M.; Xu, W.; Hassibi, B. "Compressed sensing - probabilistic analysis of a null-space characterization," Proc. of IEEE Int. Conf. on Acoustic, Speech and Signal Processing, ICASSP, 31 Mar-4 Apr 2008, Las Vegas, USA. IEEE, 2008. DOI: https://doi.org/10.1109/ICASSP.2008.4518375.

Cohen, A.; Dahmen, W.; DeVore, R. "Compressed sensing and best k-term approximation," J. Amer. Math. Soc., Vol. 22, No. 1, p. 211–231, Jan. 2009. DOI: https://doi.org/10.1090/S0894-0347-08-00610-3.

Xu, W.; Hassibi, B. "On sharp performance bounds for robust sparse signal recoveries," Proc. of IEEE Int. Symp. on Inf. Theory, 28 Jun-3 Jul 2009, Seoul, South Korea. IEEE, 2009. DOI: https://doi.org/10.1109/ISIT.2009.5205718.

Dimakis, A. G.; Vontobel, P. O. LP Decoding Meets LP Decoding: A Connection Between Channel Coding and Compressed Sensing. Allerton, 2009.

Dimakis, A. G.; Smarandache, R.; Vontobel, P. O. "LDPC codes for compressed sensing," IEEE Trans. Inf. Theory, Vol. 58, No. 5, p. 3093-3114, 2012. DOI: https://doi.org/10.1109/TIT.2011.2181819.

Khajehnejad, A.; Dimakis, A. G.; Hassibi, B.; Bradley, W. "Reweighted LP decoding for LDPC codes," IEEE Trans. Inf. Theory, Vol. 58, No. 9, p. 5972-5984, 2012. DOI: https://doi.org/10.1109/TIT.2012.2202211.

Khajehnejad, A.; Dimakis, A. G.; Hassibi, B.; Bradley, W. "Reweighted LP decoding for LDPC codes," arXiv:1103.2837v1 [cs.IT]. — 15 Mar. 2011.

Khajehnejad, M. A.; Xu, W.; Avestimehr, A. S.; Hassibi, B. "Improved sparse recovery thresholds with two-step reweighted minimization," Proc. of IEEE Int. Symp. on Information Theory, 13-18 Jun 2010, Austin, USA. IEEE, 2010. DOI: https://doi.org/10.1109/ISIT.2010.5513417.

Kurkoski, B. M.; Siegel, P. H.; Wolf, J. K. "Joint message-passing decoding of LDPC codes and partial-response channels," IEEE Trans. Inf. Theory, Vol. 48, No. 6, p. 1410–1422, June 2002. DOI: https://doi.org/10.1109/TIT.2002.1003830.

Kim, B.-H.; Pfister, H. D. "On the joint decoding of LDPC codes and finite-state channels via linear programming," Proc. of IEEE Int. Symp. on Inf. Theory, 13-18 June 2010, Austin, TX, USA. IEEE, 2010, p. 754–758. DOI: https://doi.org/10.1109/ISIT.2010.5513614.

Kim, B.-H.; Pfister, H. D. "Joint decoding of LDPC codes and finite-state channels via linear-programming," IEEE J. Select. Topics Signal Processing, Vol. 5, No. 8, p. 1563-1576, 2011. DOI: https://doi.org/10.1109/JSTSP.2011.2165525.

Kim, B.-H.; Pfister, H. D. "An iterative joint linear-programming decoding of LDPC codes and finite-state channels," Proc. of IEEE Int. Conf. Commun., 5-9 June 2011, Kyoto, Japan. IEEE, 2011. DOI: https://doi.org/10.1109/icc.2011.5962814.

Flanagan, M. F. "A unified framework for linear-programming based communication receivers," IEEE Trans. Commun., Vol. 59, No. 12, p. 3375-3387, 2011. DOI: https://doi.org/10.1109/TCOMM.2011.100411.100417.

Опубліковано

2013-02-23

Як цитувати

Ислам, М. Р. (2013). Декодирование линейным программированием: эффективный способ декодирования кодов контроля четности с низкой плотностью. Вісті вищих учбових закладів. Радіоелектроніка, 56(2), 3–23. https://doi.org/10.20535/S0021347013020015

Номер

Розділ

Оглядові статті