Feedback in the Non-Asymptotic Regime
Without feedback, the back-off from capacity due to non-asymptotic block-length can be quite substantial for block-lengths and error probabilities of interest in many practical applications. In this paper, novel achievability bounds are used to demonstrate that in the non-asymptotic regime, the maximal achievable rate improves dramatically thanks to variable-length coding and feedback. For example, for the binary symmetric channel with capacity 1/2 the block-length required to achieve 90% of the capacity is smaller than 200, compared to at least 3100 for the best fixed-block-length code (even with noiseless feedback). Virtually all the advantages of noiseless feedback are shown to be achievable, even if the feedback link is used only to send a single signal informing the encoder to terminate the transmission (stop-feedback).