IEEE International Symposium on Information Theory (ISIT)

The approximate maximum-likelihood certificate

Idan Goldenberg, David Burshtein

Published Jul 1, 2011• 1 citation

Abstract

A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced. When the belief propagation decoder outputs a codeword, this property is satisfied if this codeword is close to the LP solution. Using upper bounding techniques, it is demonstrated that the conditional frame error probability given that the AMLC holds is, with some degree of confidence, below a threshold. In channels with low noise, this threshold is several orders of magnitude lower than the simulated frame error rate, and our bound holds with very high degree of confidence. In contrast, showing this error performance by simulation would require very long Monte Carlo runs. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.

DOI: 10.1109/isit.2011.6033742

Related papers

The approximate maximum-likelihood certificate

Idan Goldenberg, David Burshtein

A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced. When using the belief propagation decoder, this property is a measure of how close the decoded codeword is to the LP solution. Using upper bounding techniques, it is demonstrated that the conditional frame error probability given that the AMLC holds is, with some degree of confidence, below a threshold. In channels with low noise, this threshold is several orders of magnitude lower than the simulated frame error rate, and our bound holds with very high degree of confidence. In contrast, showing this error performance by simulation would require very long Monte Carlo runs. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.

arXiv:1105.3006May 16, 20111 citation

The Approximate Maximum-Likelihood Certificate

Idan Goldenberg, David Burshtein

The confidence in the reliability of a codeword output by some (not necessarily optimal) decoding algorithm is discussed. A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced to address this issue as follows. First, the channel output vector is decoded by some symmetric decoder D, e.g., belief propagation or min-sum algorithm decoding. Second, the channel output vector is decoded by LP decoding. Third, if the decoding result of D is a codeword, its LP value is compared to the LP value of the LP decoding result (the latter need not be a codeword). If these two values are close, the AMLC holds. Using upper bounding techniques, we show that the conditional frame error probability given that the AMLC holds, is with some degree of confidence below a threshold. In channels with low noise, this threshold is orders of magnitude lower than the simulated frame error rate, and our bound holds with a very high degree of confidence. This is in stark contrast with standard Monte Carlo simulation, which would require excessively long runs to demonstrate like performance. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.

IEEE Transactions on Information TheoryMay 16, 20132 citations

A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel

Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20110 citations

On the joint decoding of LDPC codes and finite-state channels via linear programming

Byung‐Hak Kim, Henry D. Pfister

In this paper, the linear programming (LP) decoder for binary linear codes, introduced by Feldman, et al. is extended to joint-decoding of binary-input finite-state channels. In particular, we provide a rigorous definition of LP joint-decoding pseudo-codewords (JD-PCWs) that enables evaluation of the pairwise error probability between codewords and JD-PCWs. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the LP joint decoder also has the maximum-likelihood (ML) certificate property and all integer valued solutions are codewords. In this case, the performance loss relative to ML decoding can be explained completely by fractional valued JD-PCWs.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20105 citations

On the Joint Decoding of LDPC Codes and Finite-State Channels via Linear Programming

Byung‐Hak Kim, Henry D. Pfister

arXiv:1005.0052May 1, 20105 citations

Decoding error-correcting codes via linear programming

Jon Feldman, David Ron Karger

Abstract. Error-correcting codes are fundamental tools used to transmit digital infor-mation over unreliable channels. Their study goes back to the work of Hamming [Ham50] and Shannon [Sha48], who used them as the basis for the field of information theory. The problem of decoding the original information up to the full error-correcting potential of the system is often very complex, especially for modern codes that approach the theoretical limits of the communication channel. In this thesis we investigate the application of linear programming (LP) relaxation to the problem of decoding an error-correcting code. Linear programming relaxation is a standard technique in approximation algorithms and operations research, and is central to the study of efficient algorithms to find good (albeit suboptimal) solutions to very difficult optimization problems. Our new "LP decoders " have tight combinatorial characterizations of decoding success that can be used to analyze error-correcting performance. Furthermore, LP decoders have the desirable (and rare) property that whenever they output a result, it is guaranteed to be the optimal result: the most likely (ML) information sent over the channel. We refer to this property as the ML certificate property.

Jan 1, 2003225 citations