Advanced

Trellis Source Coding Methods for Low Rates and Short Blocks

Eriksson, Tomas LU (2005)
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Professor Fischer, Thomas R., Washington State University, USA
organization
publishing date
type
Thesis
publication status
published
subject
keywords
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
pages
177 pages
publisher
Department of Information Technology, Lund Univeristy
defense location
Room E:1406, E-building, Lunds Institute of Technology
defense date
2005-05-20 10:15
external identifiers
  • Other:ISRN: LUTEDX/TEIT-05/1029-SE
ISBN
91-7167-032-7
language
English
LU publication?
yes
id
33daa7c1-bc7c-4785-beeb-17adf1ae906e (old id 25114)
date added to LUP
2007-06-01 09:42:37
date last changed
2016-09-19 08:45:08
@misc{33daa7c1-bc7c-4785-beeb-17adf1ae906e,
  abstract     = {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.<br/><br>
<br/><br>
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.<br/><br>
<br/><br>
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.},
  author       = {Eriksson, Tomas},
  isbn         = {91-7167-032-7},
  keyword      = {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},
  language     = {eng},
  pages        = {177},
  publisher    = {ARRAY(0x95e9278)},
  title        = {Trellis Source Coding Methods for Low Rates and Short Blocks},
  year         = {2005},
}