UCLA

The reliable communication of short messages provides a foundation for today's information ecosystem. Text messages, control messages that initiate and manage calls on the cellular network, and messages from millions of sensors in the internet of things all need to communicate short messages promptly and reliably. For short messages, list Viterbi decoding (LVD) of tail-biting convolutional codes (TBCCs) aided by a cyclic redundancy check (CRC) has been shown to approach the random-coding union bound on frame error rate. There are two alternative approaches to LVD, serial LVD (S-LVD) and parallel LVD (P-LVD). Both S-LVD and P-LVD approach maximum-likelihood (ML) decoding performance as the maximum list size is increased. While several recent papers have focused on serial LVD, parallel LVD offers significant structural advantages for an implementation on a field-programmable gate-array (FPGA) board. This thesis presents a complete FPGA implementation of P-LVD and analyzes its performance. The thesis begins by introducing the general LVD paradigm and comparing P-LVD with S-LVD in terms of throughput and computational complexity. An adaptive version of P-LVD allows the list size to grow as with S-LVD. The thesis investigates various hardware architectures, culminating with selection of the best trade-off between throughput and FPGA resource requirements. The conclusion describes several directions for future work on this exciting and relevant area at the crossroads of cutting edge communication theory and practical communication system implementation.