A branch-cut-and-price algorithm for optimal decoding in digital communication systems

Banu Kabakulak (), Z. Caner Taşkın () and Ali Emre Pusane ()
Additional contact information
Banu Kabakulak: Istanbul Bilgi University
Z. Caner Taşkın: Boğaziçi University
Ali Emre Pusane: Boğaziçi University

Journal of Global Optimization, 2021, vol. 81, issue 3, No 10, 805-834

Abstract: Abstract Channel coding aims to minimize the errors that occur during the transmission of digital information from one place to another. Low-density parity-check codes can detect and correct transmission errors if one encodes the original information by adding redundant bits. In practice, heuristic iterative decoding algorithms are used to decode the received vector. However, these algorithms may fail to decode if the received vector contains multiple errors. We consider decoding the received vector with minimum error as an integer programming (IP) problem and propose a branch-and-price method for its solution. We improve the performance of our method by introducing heuristic feasible solutions and adding valid cuts to the mathematical formulation. Our computational experiments reveal that our branch-cut-and-price algorithm significantly improves solvability of the problem compared to a state-of-the-art IP decoder in the literature and has superior error performance than the conventional sum-product algorithm.

Keywords: Telecommunications; LDPC decoding; Integer programming; Branch-cut-and-price algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01073-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:81:y:2021:i:3:d:10.1007_s10898-021-01073-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01073-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().