Causal (Progressive) Encoding over Binary Symmetric Channels with Noiseless Feedback

Traditional communication systems transmit a codeword only after all message bits are available at the transmitter. This paper joins Guo & Kostina and Lalitha et al. in developing approaches for causal encoding, where the transmitter may begin transmitting codeword symbols as soon as the first message bit arrives. Building on the posterior matching encoders of Horstein, Shayevitz & Feder, and Naghshvar et al., this paper extends our computationally efficient systematic encoder to progressively encode using only the message bits that are causally available. Systematic codes work well with posterior matching on a channel with feedback, and they provide an immediate benefit when causal encoding is employed instead of traditional encoding. Our algorithm captures additional gains in the interesting region where the transmission rate it is higher than the source rate A at which message bits become available. In this region, we improve performance further through the transmission of additional, non-systematic symbols before a traditional encoder would have even begun transmission.

Automated summary

This paper introduces a method of causal encoding that allows the transmitter to start transmitting codeword symbols upon receiving the first message bit; systematic codes work well on channels with feedback and provide immediate benefits when employed for causal encoding; in the interesting region where the transmission rate is higher than the source rate, additional gains in performance are achieved by transmitting non-systematic symbols before a traditional encoder would have started transmission.