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

Автор(и)

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

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.

##submission.downloads##

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

2013-02-23

Як цитувати

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

Номер

Том 56 № 2 (2013)

Розділ

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

Ліцензія

Авторське право (c) 2013 Известия высших учебных заведений. Радиоэлектроника

Издатель журнала Известия высших учебных заведений. Радиоэлектроника (сокр. "Известия вузов. Радиоэлектроника"), Национальный технический университет Украины "Киевский политехнический институт", учитывает, что доступ автора к его статье является важным как для самого автора, так и для спонсоров его исследований. Мы представлены в базе издателей SHERPA/RoMEO как зеленый издатель (green publisher), что позволяет автору выполнять самоархивирование своей статьи. Однако важно, чтобы каждая из сторон четко понимала свои права. Просьба более детально ознакомиться с Политикой самоархивирования нашего журнала.

Политика оплаченного открытого доступа POA (paid open access), принятая в журнале, позволяет автору выполнить все необходимые требования по открытому доступу к своей статье, которые выдвигаются институтом, правительством или фондом при выделении финансирования. Просьба более детально ознакомиться с политикой оплаченного открытого доступа нашего журнала (см. отдельно).

Варианты доступа к статье:

1. Статья в открытом доступе POA (paid open access)

В этом случае права автора определяются лицензией CC BY (Creative Commons Attribution).

2. Статья с последующим доступом по подписке

В этом случае права автора определяются авторским договором, приведенным далее.

  • Автор (каждый соавтор) уступает Издателю журнала «Известия высших учебных заведений. Радиоэлектроника» НТУУ «КПИ» на срок действия авторского права эксклюзивные права на материалы статьи, в том числе право на публикацию данной статьи издательством Аллертон Пресс, США (Allerton Press) на английском языке в журнале «Radioelectronics and Communications Systems». Передача авторского права охватывает исключительное право на воспроизведение и распространение статьи, включая оттиски, переводы, фото воспроизведения, микроформы, электронные формы (он- и оффлайн), или любые иные подобные формы воспроизведения, а также право издателя на сублицензирование третьим лицам по своему усмотрению без дополнительных консультаций с автором. При этом журнал придерживается Политики конфиденциальности.
  • Передача прав включает право на обработку формы представления материалов с помощью компьютерных программам и систем (баз данных) для их использования и воспроизводства, публикации и распространения в электронном формате и внедрения в системы поиска (базы данных).
  • Воспроизведение, размещение, передача или иное распространение или использование материалов, содержащихся в статье должно сопровождаться ссылкой на Журнал и упоминанием Издателя, а именно: название статьи, имя автора (соавторов), название журнала, номер тома, номер выпуска, копирайт авторов и издателя "© Национальный технический университет Украины "Киевский политехнический институт"; © автор(ы)".
  • Автор (каждый соавтор) материалов сохраняет все права собственника материалов, включая патентные права на любые процессы, способы или методы и др., а также права на товарные знаки.
  • Издатель разрешает автору (каждому соавтору) материалов следующее:
  1. Право пользоваться печатными или электронными вариантами материалов статьи в форме и содержании, принятыми Издателем для публикации в Журнале. Подробнее см. политики Оплаченного открытого доступа, подписки и самоархивирования.
  2. Право бесплатно копировать или передавать коллегам копию напечатанной статьи целиком или частично для их личного или профессионального использования, для продвижения академических или научных исследований или для учебного процесса или других информационных целей, не связанных с коммерческими целями.
  3. Право использовать материалы из опубликованной статьи в написанной автором (соавторами) книге, монографии, учебнике, учебном пособии и других научных и научно-популярных изданиях.
  4. Право использовать отдельные рисунки или таблицы и отрывки текста из материалов в собственных целях обучения или для включения их в другую работу, которая печатается (в печатном или электронном формате) третьей стороной, или для представления в электронном формате во внутренние компьютерные сети или на внешние сайты автора (соавторов).
  • Автор (соавторы) соглашаются, что каждая копия материалов или любая ее часть, распространенная или размещенная ими в печатном или электронном формате, будет содержать указание на авторское право, предусмотренное в Журнале и полную ссылку на Журнал Издателя.
  • Автор (соавторы) гарантирует, что материалы являются оригинальной работой и представлены впервые на рассмотрение только в этом Журнале и ранее не публиковались. Если материалы написаны совместно с соавторами, автор гарантирует, что проинформировал их относительно условий публикации материалов и получил их подписи или письменное разрешение подписываться от их имени.
  • Если в материалы включаются отрывки из работ или имеются указания на работы, которые охраняются авторским правом и принадлежат третьей стороне, то автору необходимо получить разрешение владельца авторских прав на использование таких материалов в первом случае и сделать ссылку на первоисточник во втором.
  • Автор гарантирует, что материалы не содержат клеветнических высказываний и не посягают на права (включая без ограничений авторское право, права на патент или торговую марку) других лиц и не содержат материалы или инструкции, которые могут причинить вред или ущерб третьим лицам. Автор (каждый соавтор) гарантирует, что их публикация не приведет к разглашению секретных или конфиденциальных сведений (включая государственную тайну). Подтверждением этого является Экспертное заключение (см. перечень документов в Правила для авторов).
  • Издатель обязуется опубликовать материалы в случае получения статьей положительного решения редколлегии о публикации на основании внешнего рецензирования (см. Политика рецензирования).
  • В случае публикации статьи на английском языке в журнале «Radioelectronics and Communications Systems» (Издатель: Аллертон Пресс, США, распространитель Springer) автору (соавторам) выплачивается гонорар после выхода последнего номера журнала года, в котором опубликована данная статья.
  • Документ Согласие на публикацию, который подают русскоязычные авторы при подаче статьи в редакцию, является краткой формой данного договора, в котором изложены все ключевые моменты настоящего договора и наличие которого подтверждает согласие автора (соавторов) с ним. Аналогичным документом для англоязычных авторов является Copyright Transfer Agreement (CTA), предоставляемый издательством Allerton Press.
  • Настоящий Договор вступает в силу в момент принятия статьи к публикации. Если материалы не принимаются к публикации или до публикации в журнале автор (авторы) отозвал работу, настоящий Договор не приобретает (теряет) силу.