Trellis Source Coding Methods for Low Rates and Short Blocks
(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:
https://lup.lub.lu.se/record/25114
- author
- Eriksson, Tomas LU
- supervisor
- opponent
-
- Professor Fischer, Thomas R., Washington State University, USA
- organization
- publishing date
- 2005
- 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:00
- 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
- 2016-04-04 11:09:56
- date last changed
- 2018-11-21 21:03:04
@phdthesis{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}},
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}},
language = {{eng}},
publisher = {{Department of Information Technology, Lund Univeristy}},
school = {{Lund University}},
title = {{Trellis Source Coding Methods for Low Rates and Short Blocks}},
year = {{2005}},
}