Post by thread:[EE]:Compressing a line of bits

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

Huffman encode the RLE. w.. David VanHorn wrote: {Quote hidden}> > 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 -- 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

{Quote hidden}> From: David VanHorn [spam_OUTdvanhornTakeThisOuTCEDAR.NET] > > 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? 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

> >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

More or less random data is more or less incompressible... /\/\/\/*=Martin ----- Original Message ----- From: "David VanHorn" <.....dvanhornKILLspam@spam@CEDAR.NET> To: <PICLISTKILLspamMITVMA.MIT.EDU> Sent: Tuesday, February 12, 2002 1:32 PM Subject: Re: [EE]:Compressing a line of bits {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. > > 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 > > -- 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 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

> 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