Meny

Du är här

Design and analysis of robust source codes

Publiceringsår: 1993
Språk: Engelska
Publikation/Tidskrift/Serie: Div. of Signal Processing, Research Report
Dokumenttyp: Rapport
Förlag: Luleå University of Technology

Sammanfattning

In this report, we are proposing a framework for robustness analysis of source codes, in combination with a design procedure for finding an optimal robust code. The robustness is defined as low susceptibility to changes in the probability distribution of the source. In many applications, the probability distribution is not well known, nor time-invariant. Hence, by introducing a robustness measure we can design a code, based on a relatively poor estimate of the probability distribution, without risking a catastrophic increase of the average code word length if the estimate was incorrect or the source characteristics change.

The basic concepts are robustness in general, and gradient robustness in particular. The gradient robustness, $R_
abla (QTR{cal}{C})$ of a variable-length code, $QTR{cal}{C}$, with code word lengths $l_i$, $i=0ldots N-1$, is defined as $R_
abla (C)=left( sum_{i=0}^i(l_i-overline{l})^2
ight) ^{-1/2}$, where $overline{l}$ is the arithmetic mean of the code word lengths. In the experimental part, it is shown that even a small loss in the degree of compression can give a substantial increase of the robustness of the code. The procedure for finding the optimal robust code is computationally intense, but an easy to compute approximation formula is given. The experiments performed, using the approximation formula, only lead to minor differences in the obtained robustness, compared to the optimal robust code.

Some of the observations done in the experiments are:
The lengths of the longest code words are reduced when introducing robustness, thus reducing the required memory space for storing code books. When the experiments on entropy-close codes are applied to Huffman codes, we get roughly the same results. The differences is due to the quantization of code word lengths in the Huffman code. Three different methods for measuring the behaviour of the gradient robust codes, compared to the optimal data compression codes, are showing promising results.

The analysis and experiments in this report only cover a small part of the possibilities, but the results obtained are providing incentive for further studies. A robustness measure we are planning to investigate in the future is based on the arithmetic mean of the code word costs.

Disputation

Nyckelord

  • Technology and Engineering

Övriga

Published
TULEA 1993:45

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen