The GMD decoder is an algorithm for decoding concatenated codes up to half their minimal distance. The standard presentation of this algorithm usually proceeds in two steps: First, one shows a randomized decoding algorithm, and proves that this algorithm works in expectation, rather than with high probability. Then, one uses the latter proof to show how to derandomize the latter algorithm to get an algorithm that always works.

In all the presentations that I could find, it is never shown that the randomized algorithm works with high probability. However, it is not hard to see that this is indeed the case. I need to use this fact, and I wonder whether it was proved somewhere and I can give a reference, or whether I need to prove it myself.

So in short, my question is: Is there a reference for a paper that proves that the randomized decoder works with high probability?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.