Trellis Source Coding Methods for Low Rates and Short Blocks

Sammanfattning: Trellis quantization is a finite state machine based method for data compression. It is mainly applied to quantizing noise-like sources. In this thesis new trellis codes suitable for low rate quantization are derived. Rate-distortion theory predicts source coding performance, but unfortunately provides only limited insight in how to construct good codes. In general, good trellis source codes combine a good trellis structure with suitable reproducer values. Further, to obtain excellent performance good codes must be combined with suitable trellis search algorithms. All these code design topics are addressed in the thesis. The new contributions can be divided into four main parts. The first considers the pure form trellis coding problem, i.e., trellis code constructions consisting of a single trellis populated by reproducer letters. These codes do not require further processing such as entropy coding. Entropy-constrained trellis codes are treated separately. We compare a method based on simple scaling of the set of reproducer values to constructions with individually optimized reproducer levels. Results show that the proposed methods are competitive with the best in the literature. Many real-life systems for data transmission are based on short information blocks and it is shown that the Viterbi search algorithm is not suitable for such short source sequences. Instead we propose a method based on the tailbiting BCJR algorithm and derive it from rate-distortion theoretic arguments. The thesis provides one of the first major studies of the tailbiting BCJR algorithm for source coding. In the final part of the thesis the new trellis codes are applied to image coding. All trellises have in common a code design based on linear congruential (LC) recursions. These are the key elements in pseudo-random number generators. Here they are used to associate the trellis branches with reproducer values. LC trellis codes are easy to generate and analyze. In addition to competitive performance the new codes easily adapt to different sources, state sizes, and coding rates. We also point out two label correlation measurements that predict good trellis code performance.