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:DagSemProc.06111.19,
author = {Andreev, Alexander E.},
title = {{The optimal sequence compression}},
booktitle = {Complexity of Boolean Functions},
pages = {111},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {18624405},
year = {2006},
volume = {6111},
editor = {Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2006/602},
URN = {urn:nbn:de:0030drops6025},
doi = {10.4230/DagSemProc.06111.19},
annote = {Keywords: Compression, partial boolean function}
}
Keywords: 

Compression, partial boolean function 
Collection: 

06111  Complexity of Boolean Functions 
Issue Date: 

2006 
Date of publication: 

09.10.2006 