Design and analysis of robust source codes
Edfors, Ove LU
and Börjesson, Per Ola
LU
(1993)
In Div. of Signal Processing, Research Report
- 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 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... (More) - 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1043842
- author
- Edfors, Ove
LU
and Börjesson, Per Ola
LU
- publishing date
- 1993
- type
- Book/Report
- publication status
- published
- subject
- in
- Div. of Signal Processing, Research Report
- publisher
- Luleå University of Technology
- report number
- TULEA 1993:45
- language
- English
- LU publication?
- no
- id
- 19085501-f9f6-4b5f-8ee8-d1f9d4ba5af2 (old id 1043842)
- date added to LUP
- 2016-04-04 11:34:31
- date last changed
- 2018-11-21 21:05:46
@techreport{19085501-f9f6-4b5f-8ee8-d1f9d4ba5af2,
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 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. <br/><br>
<br/><br>
The basic concepts are robustness in general, and gradient robustness in particular. The gradient robustness, $R_<br/><br>
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_<br/><br>
abla (C)=left( sum_{i=0}^i(l_i-overline{l})^2<br/><br>
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. <br/><br>
<br/><br>
Some of the observations done in the experiments are: <br/><br>
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. <br/><br>
<br/><br>
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.}},
author = {{Edfors, Ove and Börjesson, Per Ola}},
institution = {{Luleå University of Technology}},
language = {{eng}},
number = {{TULEA 1993:45}},
series = {{Div. of Signal Processing, Research Report}},
title = {{Design and analysis of robust source codes}},
year = {{1993}},
}