ML performance bounds of turbo and LDPC codes

To date there is no practical means to evaluate the true word error probability (WEP) of a given turbo or LDPC code because typical decoders cannot achieve the performance of ML decoding. In this paper, we propose a viable methodology to establish tight bounds on the ML-decoding WEP for these codes through empirical simulation. Our framework centers on the efficient use of multiple-output decoding induced by receiver-generated side information, or gift. At low WEP regime, perturbed decoding can give tight bounds. In high WEP regime, due to the prohibitive complexity of perturbed decoding, we instead pursue other type of gifts. The effectiveness of various types of gifts is investigated in detail. We observe that the complexity of gift-assisted decoding is dominated by the effort to identify partial gifts that can then be further extended. Using bit values as gifts and an algorithm that maximizes the efficiency of identifying valid partial gifts, the ML bounds of turbo and LDPC codes are evaluated. At low WEP regime, our approach successfully yields the ML performance for these codes. Their WEP are shown to be very far from the sphere packing bound. At higher WEP regime, our results indicate that best-performing message-passing decoders underperform an ML decoder by at least 0.2 dB.