Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Design and analysis of robust source codes
Luleå University of Technology.
Luleå University of Technology.
1993 (English)Report (Other academic)
Abstract [en]

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_\nabla (\QTR{cal}{C})$ of a variable-length code, $\QTR{cal}{C}$, with code word lengths $l_i$, $i=0\ldots N-1$, is defined as $R_\nabla (C)=\left( \sum_{i=0}^i(l_i-\overline{l})^2\right) ^{-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.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 1993.
Series
Research report / Luleå University of Technology, ISSN 0347-0881 ; 1993:45
National Category
Signal Processing
Research subject
Signal Processing
Identifiers
URN: urn:nbn:se:ltu:diva-23761Local ID: 84c90220-0d30-11dd-9b51-000ea68e967bOAI: oai:DiVA.org:ltu-23761DiVA, id: diva2:996811
Note
Godkänd; 1993; 20080418 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2025-10-21Bibliographically approved

Open Access in DiVA

No full text in DiVA

By organisation
Luleå University of Technology
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 89 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf