Posterior matching uses variable-length encoding controlled by noiseless feedback of the received symbols to achieve high rates for short average blocklengths. Traditionally, the feedback of a received symbol occurs before the next symbol is transmitted. The transmitter optimizes the next symbol transmission with full knowledge of every past received symbol.To move posterior matching closer to practical communication, this paper limits how often feedback can be sent. We focus on reducing the frequency of the feedback while still maintaining the high rates that posterior matching achieves with feedback after every symbol. As it turns out, the frequency of the feedback can be reduced significantly with no noticeable reduction in rate.

Convolutional codes have been widely studied and used in many systems. As the number of memory elements increases, frame error rate (FER) improves but computational complexity increases exponentially. Recently, decoders that achieve reduced average complexity through list decoding have been demonstrated when the convolutional encoder polynomials share a common factor that can be understood as a CRC or more generally an expurgating linear function (ELF). However, classical convolutional codes avoid such common factors because they result in a catastrophic encoder. This paper provides a way to access the complexity reduction possible with list decoding even when the convolutional encoder polynomials do not share a common factor. Decomposing the original code into component encoders that fully exclude some polynomials can allow an ELF to be factored from each component. Dual list decoding of the component encoders can often find the ML codeword. Including a fallback to regular Viterbi decoding yields excellent FER performance while requiring less average complexity than always performing Viterbi on the original trellis. A best effort dual list decoder that avoids Viterbi has performance similar to the ML decoder. Component encoders that have a shared polynomial allow for even greater complexity reduction.

Horstein, Burnashev, Shayevitz and Feder, Naghshvar et al. and others have studied sequential transmission of a k-bit message over the binary symmetric channel (BSC) with full, noiseless feedback using posterior matching. Yang et al. provide an improved lower bound on the achievable rate using martingale analysis that relies on the small-enough difference (SED) partitioning introduced by Naghshvar et al. SED requires a relatively complex encoder and decoder. To reduce complexity, this paper replaces SED with relaxed constraints that admit the small enough absolute difference (SEAD) partitioning rule. The main analytical results show that achievable-rate bounds higher than those found by Yang et al. (2021) are possible even under the new constraints, which are less restrictive than SED. The new analysis does not use martingale theory for the confirmation phase and applies a surrogate channel technique to tighten the results. An initial systematic transmission further increases the achievable rate bound. The simplified encoder associated with SEAD has a complexity below order$O(K^{2})$and allows simulations for message sizes of at least 1000 bits. For example, simulations achieve 99% of of the channel’s 0.50-bit capacity with an average block size of 200 bits for a target codeword error rate of$10^{-3}$.

The Consultative Committee for Space Data Systems (CCSDS) 141.11-O-1 Line Product Code (LPC) provides a rare opportunity to compare maximum-likelihood decoding and message passing. The LPC considered in this paper is intended to serve as the inner code in conjunction with a (255,239) Reed Solomon (RS) code whose symbols are bytes of data. This paper represents the 141.11-O-1 LPC as a bipartite graph and uses that graph to formulate both maximum likelihood (ML) and message passing algorithms. ML decoding must, of course, have the best frame error rate (FER) performance. However, a fixed point implementation of a Neural-Normalized MinSum (N-NMS) message passing decoder closely approaches ML performance with a significantly lower complexity.

In this paper, we consider variable-length coding over the memoryless binary asymmetric channel (BAC) with full noiseless feedback, including the binary symmetric channel (BSC) as a special case. In 2012, Naghshvar et al. introduced a coding scheme, which we refer to as the small-enough-difference (SED) coding scheme. For symmetric binary-input channels, the deterministic variable-length feedback (VLF) code constructed with the SED coding scheme asymptotically achieves both capacity and Burnashev’s optimal error exponent. Building on the work of Naghshvar et al., this paper extends the SED coding scheme to the BAC and develops a non-asymptotic VLF achievability bound that is shown to achieve both capacity and the optimal error exponent. For the specific case of the BSC, we develop an additional non-asymptotic VLF achievability bound using a two-phase analysis that leverages both a submartingale synthesis and a Markov chain time of first passage analysis. Numerical evaluations show that both new VLF achievability bounds outperform Polyanskiy’s achievability bound for variable-length stop-feedback codes.

Traditional communication systems transmit a code-word 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$\mu$is higher than the source rate$\lambda$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.

Building on the work of Horstein, Shayevitz and Feder, and Naghshvar et al., this paper presents algorithms for low-complexity sequential transmission of a k-bit message over the binary symmetric channel (BSC) with full, noiseless feedback. To lower complexity, this paper shows that the initial k binary transmissions can be sent before any feedback is required and groups messages with equal posteriors to reduce the number of posterior updates from exponential in k to linear in k. Simulation results demonstrate that achievable rates for this full, noiseless feedback system approach capacity rapidly as a function of average blocklength, faster than known finite-blocklength lower bounds on achievable rate with noiseless active feedback and significantly faster than finite-blocklength lower bounds for a stop feedback system.