Efficient Computation of Viterbi Decoder Reliability with an Application to Variable-Length Coding

This thesis compares the accuracy and complexity of Raghavan and Baum’s Reliability Out-put Viterbi Algorithm (ROVA), Polyanskiy’s accumulated information density (AID), and Fricke and Hoeher’s approximation of ROVA. It turns out that AID is far less accurate than ROVA in practice. This thesis proposes codeword information density (CID), which modifies AID to improve its accuracy and leads to a lower-complexity implementation of ROVA. This thesis 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 thesis examines both the complexity and the simulation time of ROVA, CID, AID, and the Fricke and Hoe- her approximation to ROVA. This thesis 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 thesis compares the performance of an incremental retransmission scheme using ROVA as a stopping condition to one that uses a CRC as a stopping condition. This thesis concludes by applying the sequential differential optimization algorithm (SDO) to determine the trans- mission lengths in an incremental transmission scheme to maximize the throughput when limiting the maximum number of transmissions