The “hallucination” bound for the BSC

Though the schemes are different, both Horstein\´s and Kudryashov\´s non-block strategies for communication with feedback over the binary-symmetric channel asymptotically achieve the identical reliability function (error exponent); a function that displays some curious features. For positive rates it is strictly larger than Burnashev\´s reliability function and transitions discontinuously at the channel capacity from a strictly positive value to zero. The purpose of this paper is to connect this reliability function to familiar coding contexts and to demonstrate that it provides an upper bound on the error exponents achievable in these contexts. We first show that this function gives a lower bound on the minimum probability of decoding error across codewords in a block-coding context with (or without) feedback. We then show that the same reliability function also gives an upper bound on the maximum probability of bit error in a non-block "streaming" context where noiseless feedback is available and the destination is (occasionally) allowed to declare erasures (per Forney). The basic insight underlying the bound leads to the moniker the "hallucination" bound.