This paper compares the accuracy and complexity of Raghavan and Baum’s Reliability Output Viterbi Algorithm (ROVA), Polyanskiy’s accumulated information density (AID), and Fricke and Hoeher’s lower complexity approximation of ROVA. It turns out that AID is far less accurate than ROVA in practice. This paper proposes codeword information density (CID), which modifies AID to improve its accuracy and leads to a lower-complexity implementation of ROVA. The paper includes an analytical expression for the random variable describing the correct decoding probability computed by ROVA and uses this expression to characterize how the probabilities of correct decoding, undetected error, and negative acknowledgement behave as a function of the selected threshold for reliable decoding. This paper examines both the complexity and the simulation time of ROVA, CID, AID, and the Fricke and Hoeher approximation to ROVA. This paper also derives an expression for the union bound on the frame error rate for zero-terminated trellis codes with punctured symbols and uses it to optimize the order of symbol transmission in an incremental retransmission scheme. This paper concludes by comparing the performance of an incremental retransmission scheme using ROVA as a stopping condition to one that uses a CRC as a stopping condition.

Variable-length (VL) coding sends an initial codeword followed by subsequent transmissions of incremental redundancy (IR) sent when the decoder indicates through feedback that it has not yet identified a reliable codeword. VL coding is a staple of modern communication to handle fading, and recent theoretical analysis and applications have demonstrated its value on non-fading channels for applications that require short blocklengths. To maximize throughput in a VL setting, the length of each IR transmission should be optimized. Sequential differential optimization (SDO) computes transmission lengths that optimize throughput by minimizing average blocklength. SDO produces a family of solutions that each maximize throughput for a specified maximum number of transmissions. This paper considers the average number of feedback transmissions per message as an alternative metric for the cost of the feedback resource. A Lagrangian approach provides a new SDO solution that jointly minimizes both the average blocklength and the average number of feedback transmissions associated with a message. The mapping of real-valued SDO solutions to the necessarily integer transmission lengths is also addressed.

This paper uses a case study of a tail-biting convolutional code (with successful decoding indicated by the reliability output Viterbi algorithm) to present an information density approach for analyzing and optimizing the throughput of systems using incremental redundancy controlled by feedback. Polyan-skiy's normal approximation combined with a linear model for the information gap of a rate-compatible code family provides a simple and accurate characterization of the behavior of feedback systems employing practical codes, such as convolutional or low-density parity-check codes. Especially for short message lengths on the order of k <; 50 message bits, the newly proposed model is more accurate than Vakilinia's model in which the rate of first successful decoding has a Gaussian probability density function.