  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.
