Design and analysis of robust source codes
Forskningsoutput: Bok/rapport › Rapport
Abstract
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 timeinvariant. 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 variablelength code, $QTR{cal}{C}$, with code word lengths $l_i$, $i=0ldots N1$, is defined as $R_
abla (C)=left( sum_{i=0}^i(l_ioverline{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 entropyclose 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.
The basic concepts are robustness in general, and gradient robustness in particular. The gradient robustness, $R_
abla (QTR{cal}{C})$ of a variablelength code, $QTR{cal}{C}$, with code word lengths $l_i$, $i=0ldots N1$, is defined as $R_
abla (C)=left( sum_{i=0}^i(l_ioverline{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 entropyclose 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.
Detaljer
Författare  

Externa organisationer 

Forskningsområden  Ämnesklassifikation (UKÄ) – OBLIGATORISK

Originalspråk  engelska 

Förlag  Luleå University of Technology 
Volym  TULEA 1993:45 
Status  Published  1993 
Publikationskategori  Forskning 
Externt publicerad  Ja 
Publikationsserier
Namn  Div. of Signal Processing, Research Report 

Volym  TULEA 1993:45 