EE Seminar: Maximum-Likelihood Decoding Based on an ADMM Algorithm
Speaker: Omry Adam
M.Sc. student under the supervision of Prof. Yair Be’ery
Wednesday, December 27th, 2017 at 15:00
Room 011, Kitot Bldg., Faculty of Engineering
Maximum-Likelihood Decoding Based on an ADMM Algorithm
Abstract
The communication of information over a noisy channel is one of most practical fields of research today, wherein a major part of the latest research in this field involves the decoding process.
Generally, an optimal Maximum-Likelihood decoder is considered to be NP-hard. Therefore, the common practical decoders are based on sub-optimal methods, such as Belief Propagation (BP) decoders.
A Maximum-Likelihood decoder based on a Linear Program (LP) algorithm was previously suggested by Feldman and his collaborators (2003). Feldman showed that the decoding of a binary linear block code can be described as a relaxed integer LP optimization problem, which has the ML certificate property. That means that whenever the return output is a valid codeword it is guaranteed to be the ML codeword. However, it is not guaranteed that the LP decoder output converges into a valid codeword.
In 2014, Helmling et al. introduced a Maximum-Likelihood decoder based on integer linear programming. The proposed decoder is based on a LP solver component integrated in a Branch and Bound algorithm. However, the introduced algorithm implementation is based on a software black-box tool as the LP solver component.
In this talk we propose an alternative approach for Helmling‘s ML decoder implementation, based on the Alternating Direction Method of Multipliers (ADMM) algorithm as the LP solver component. We introduce an efficient way to integrate the ADMM algorithm inside the ML decoder, instead of the black-box tool.
We compare the ML decoder performance to two alternative decoders: a Message-Passing (MP) decoder and the MLD algorithm that was introduced by Helmling. The comparison to the MP decoder performance demonstrates that our proposed decoder can achieve significantly better FER performance, compared to the basic MP decoder. The comparison to Helmling’s MLD algorithm indicates that the ADMM properties make it a fair substitute for the more common linear programming solver, the Simplex Method.
