Compressing a signal with loss

Hello,

I would like to compress a signal that has some major constraints, and
compress it so that it will still keep the constraint after
decompression.

It a signal made of 0 and 1, where there can't be less than 2 ones in
a row, and more than 8. There can't be as well less than 2 zeros in a
row, and no more than 20 zeros.

The signal is coding for something, and 15 bits in the signal only
code a bit less than 3 bits. I would like to compress the 15 bits on 4
bits, and to be able to do it on the fly.

A dictionnary looks like the simplest thing, since i can allow bit
inversions (and stay in the constraint), but i don't know how to
choose the 'closest' pattern mapping the data. I'm not even sure it's
the best thing to do...

Thank you very much for your advices,
Nick

On Sat, 09 Apr 2005 16:26:17 +0200, Nick <no-email@published.nul>
wrote:
>Hello,
>
>I would like to compress a signal that has some major constraints, and
>compress it so that it will still keep the constraint after
>decompression.
>
>It a signal made of 0 and 1, where there can't be less than 2 ones in
>a row, and more than 8. There can't be as well less than 2 zeros in a
>row, and no more than 20 zeros.
>
>The signal is coding for something, and 15 bits in the signal only
>code a bit less than 3 bits. I would like to compress the 15 bits on 4
>bits, and to be able to do it on the fly.
>
>A dictionnary looks like the simplest thing, since i can allow bit
>inversions (and stay in the constraint), but i don't know how to
>choose the 'closest' pattern mapping the data. I'm not even sure it's
>the best thing to do...
>
>Thank you very much for your advices,
>Nick

Use simple run length encoding.
Each series of 1 can be encoded as 3 bits
and each series of 0 can be encoded as 5 bits.
(for an average of 4 bits)
You will of course also need to store/transmit which (0 or 1) comes
first.
(A simple dictionary lookup combing a 0-1 pair results in basically
the same thing)

It's simple, easy to do on the fly and doesn't depend of the data
distrubution.  If you know the distribution before hand  (ie. 4 zeros
occurs twice as often as 20 zeros, etc.) then huffman or other coding
may help further.

-Tim