Variable-rate coding with feedback for universal communication systems

Classical coding schemes that rely on joint typicality (such as Slepian-Wolf coding and channel coding) assume known statistics and rely on asymptotically long sequences. However, in practice the statistics are unknown, and the input sequences are of finite length. In this finite regime, we must allow a non-zero probability of codeword error ε and also pay a penalty in the rate. The penalty manifests itself as redundancy in source coding and a gap to capacity in channel coding. Our contributions in this paper are two-fold. First, we develop a universal scheme for the specific example of the binary symmetric channel. With n channel uses and a fixed ε, the gap to capacity of our scheme is O(√n). The prior art for channel coding with known statistics shows that the penalty is ω(√n). Therefore, we infer for communication systems that rely on joint typicality that the penalty needed to accommodate universality is φ(√n). Second, we derive the penalty incurred in variable-rate universal channel coding when we restrict the number of rounds of feedback. Surprisingly, it turns out that using only two or three rounds of feedback provides near-optimal performance for systems of practical interest. This rule of thumb is valuable for practical communication systems.