Design and analysis of robust source codes
Författare
Summary, in English
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.
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.
Publiceringsår
1993
Språk
Engelska
Publikation/Tidskrift/Serie
Div. of Signal Processing, Research Report
Dokumenttyp
Rapport
Förlag
Luleå University of Technology
Ämne
- Electrical Engineering, Electronic Engineering, Information Engineering
Status
Published
Report number
TULEA 1993:45