Trellis Source Coding Methods for Low Rates and Short Blocks

Research output: ThesisDoctoral Thesis (monograph)


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.


  • Tomas Eriksson
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Electrical Engineering, Electronic Engineering, Information Engineering


  • Elektronik och elektroteknik, Electronics and Electrical technology, systemteori, Informatik, systems theory, Informatics, image coding, tailbiting source codes, BCJR algorithm, linear congruential recursions, trellis coding, low rate quantization, rate-distortion theory, Systems engineering, computer technology, Data- och systemvetenskap, Signal processing, Signalbehandling
Original languageEnglish
Awarding Institution
Supervisors/Assistant supervisor
  • Anderson, John B., Supervisor, External person
Award date2005 May 20
  • Department of Information Technology, Lund Univeristy
Print ISBNs91-7167-032-7
Publication statusPublished - 2005
Publication categoryResearch

Bibliographic note

Defence details Date: 2005-05-20 Time: 10:15 Place: Room E:1406, E-building, Lunds Institute of Technology External reviewer(s) Name: Fischer, Thomas R. Title: Professor Affiliation: Washington State University, USA ---