Searching \ for '[EE]:Compressing a line of bits' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=compressing+line
Search entire site for: 'Compressing a line of bits'.

Exact match. Not showing close matches.
PICList Thread
'[EE]:Compressing a line of bits'
2002\02\12@114935 by David VanHorn

flavicon
face
I have a line of bits, 104 bytes wide.
It might contain anything between
000.......000 to 010101.....0101 to 11111.....11111

I had thought of a simple RLE encoding, where
1XXXXXXX means X+1 pixels of black, and 0XXXXXXX means X+1 pixels of white,
but in the case of 010101 sorts of data, it fails rather badly at compression!

I also thought about compressing the data, and if the "compressed" version
was longer than the uncompressed, to abort and send raw.

However, it seems to me that there has to be something out there that's
simple to work with, yet works better than my little hare-brained scheme.

What say the group?





--
Dave's Engineering Page: http://www.dvanhorn.org

Got a need to read Bar codes?  http://www.barcodechip.com
Bi-directional read of UPC-A, UPC-E, EAN-8, EAN-13, JAN, and Bookland, with
two or five digit supplemental codes, in an 8 pin chip, with NO external parts.

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


2002\02\12@120249 by Walter Banks

picon face
Huffman encode the RLE.
w..

David VanHorn wrote:
{Quote hidden}

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


2002\02\12@131820 by Dipperstein, Michael

face picon face
{Quote hidden}

Are any sequences of bits more common than others, or is there an even
distribution of values.  If all values are equally as common, there's not a lot
that you can do.

-Mike

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


2002\02\12@133051 by David VanHorn

flavicon
face
>
>Are any sequences of bits more common than others, or is there an even
>distribution of values.  If all values are equally as common, there's not
>a lot that you can do.

Well, that's my problem.
Whatever I do, needs to not incur a significant time penalty, and also not
be too much worse than raw, for more or less random data.

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


2002\02\12@143607 by Martin Peach

flavicon
face
More or less random data is more or less incompressible...

/\/\/\/*=Martin

----- Original Message -----
From: "David VanHorn" <.....dvanhornKILLspamspam@spam@CEDAR.NET>
To: <PICLISTspamKILLspamMITVMA.MIT.EDU>
Sent: Tuesday, February 12, 2002 1:32 PM
Subject: Re: [EE]:Compressing a line of bits


{Quote hidden}

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


2002\02\12@152401 by uter van ooijen & floortje hanneman

picon face
> More or less random data is more or less incompressible...

Unless it is really random (that is: the receiver just wants random data),
in which case it is VERY comperssible ;)

Wouter van Ooijen

Van Ooijen Technische Informatica: http://www.voti.nl
Jal compiler for PIC uC's:  http://www.voti.nl/jal
PICs kopen? http://www.voti.nl/shop

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


2002\02\12@152417 by uter van ooijen & floortje hanneman

picon face
> I have a line of bits, 104 bytes wide.
> It might contain anything between
> 000.......000 to 010101.....0101 to 11111.....11111
>
> I had thought of a simple RLE encoding, where
> 1XXXXXXX means X+1 pixels of black, and 0XXXXXXX means X+1 pixels of
white,
> but in the case of 010101 sorts of data, it fails rather badly at
compression!
>
> I also thought about compressing the data, and if the "compressed" version
> was longer than the uncompressed, to abort and send raw.
>
> However, it seems to me that there has to be something out there that's
> simple to work with, yet works better than my little hare-brained scheme.
>
> What say the group?

There is no compression/encoding that works (compresses) ALL possible
inputs. Simply mathematically impossible. All compressions fail (sometimes
miserably) on some inputs. The best you can have is to send one extra bit to
discriminate between compressed and uncompressed, you your maximum overhead
is one bit.

To choose a good (on average) compression algorithm you must know something
about your data. What you describe is RLE (run length encoding), which is
very good for data that contains long rows of unchanged values.

Wouter van Ooijen

Van Ooijen Technische Informatica: http://www.voti.nl
free PIC stuff: Jal compiler, Wisp programmer, WLoader bootloader
PICs kopen? http://www.voti.nl/shop

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


More... (looser matching)
- Last day of these posts
- In 2002 , 2003 only
- Today
- New search...