Revisiting zero-rate bounds on the reliability function of discrete memoryless channels

12/09/2019
by   Marco Bondaschi, et al.
0

We present a new proof of Berlekamp's zero-rate upper bound on the reliability function of discrete memoryless channels, in its extended form for list-decoding as first proved by Blinovsky. The Berlekamp-Blinovsky proof, which is the only one available in the literature, is based on a rather unusual procedure which prevents the combination with other tools for possible extensions of the result. We present a proof that - we think - is more transparent and more convenient to play with. The main ideas and tools used are not new and our aim is indeed to give a standardized proof based on well established and reusable principles. An important part, namely the use of Ramsey theory and of a beautiful result by Komlos, was already considered by Blinovsky himself for a similar problem of packing in Hamming spaces. However, we use some variations and combinations with other tools which lead, in our opinion, to a cleaner proof also for this specific problem. To the best of our knowledge, this was never presented before.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset