 When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-6025
URL: https://drops.dagstuhl.de/opus/volltexte/2006/602/
 Go to the corresponding Portal

### The optimal sequence compression

 pdf-format:

### Abstract

This paper presents the optimal compression for sequences with undefined values. Let we have \$(N-m)\$ undefined and \$m\$ defined positions in the boolean sequence \$vv V\$ of length \$N\$. The sequence code length can't be less then \$m\$ in general case, otherwise at least two sequences will have the same code. We present the coding algorithm which generates codes of almost \$m\$ length, i.e. almost equal to the lower bound. The paper presents the decoding circuit too. The circuit has low complexity which depends from the inverse density of defined values \$D(vv V) = frac{N}{m}\$. The decoding circuit includes RAM and random logic. It performs sequential decoding. The total RAM size is proportional to the \$\$logleft(D(vv V) ight) ,\$\$ the number of random logic cells is proportional to \$\$log logleft(D(vv V) ight) * left(log log logleft(D(vv V) ight) ight)^2 .\$\$ So the decoding circuit will be small enough even for the very low density sequences. The decoder complexity doesn't depend of the sequence length at all.

### BibTeX - Entry

```@InProceedings{andreev:DSP:2006:602,
author =	{Alexander E. Andreev},
title =	{The optimal sequence compression},
booktitle =	{Complexity of Boolean Functions},
year =	{2006},
editor =	{Matthias Krause and Pavel Pudl{\'a}k and R{\"u}diger Reischuk and Dieter van Melkebeek},
number =	{06111},
series =	{Dagstuhl Seminar Proceedings},
ISSN =	{1862-4405},
publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
DROPS-Home | Fulltext Search | Imprint | Privacy 