Andreev, Alexander E.
The optimal sequence compression
Abstract
This paper presents the optimal compression for sequences with
undefined values.
Let we have $(Nm)$ 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 = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2006/602},
annote = {Keywords: Compression, partial boolean function}
}
Keywords: 

Compression, partial boolean function 
Seminar: 

06111  Complexity of Boolean Functions

Issue date: 

2006 
Date of publication: 

09.10.2006 