Gate-level design of hardware compression chips and components for data streams

Hello all, I'm an electrical engineering major but I haven't gotten very far in my program. I was just wondering how a hardware compression chip works on a gate-structure level and what other components were involved in compressing a stream of data.

Thanks!

Compression is done using algorithms, which can be implemented in software or hardware. Hardware is obviously faster. Probably the simplest case to consider is codeword substitution where a certain block of data is recognized and substituted by a shorter block at the encoding end, and the shortened block is recognized and replaced by the original block at the receiving end. The mapping of larger block to shorter codes would be hardcoded in the hardware.

I have only a limited understanding of compression techniques, but I'll offer what I've got ;)

There's more than one compression technique. One is called "Run Length Compression". This is the kind used by the GIF file format. As the bitmap image is scanned (row-by-row), any "runs" of pixels with the exact same information (i.e. same three RGB color numbers) then the number of these occurrences is counted and whole run is replaced by the three color numbers and how many occurrences of them there are--which requires fewer bytes than the bytes needed to express the run, itself (assuming a "run" is defined as something like "3 or more in succession").

Another type of compression works to consolidate similar pieces of information. So, in the case of an image, if there is an area, such as a region of sky, that has a similar "signature," it is pared down to a more homogenized version that takes less data to convey. It's my understanding that one way to do this is to convert the data to the frequency domain and then run it through one or more filters (i.e. some sort of low-pass filter, for instance).

Then there is fractal compression where patterns are scanned for and replaced by codes that invoke fractal algorithms at the receiving end. These fractal algorithms mimic the patterns that they replace.

Once again, this is an overview of this subject from someone who is very much on the sidelines. I have gleaned this information from co-workers, and magazine articles. The integrity of this information is purely reliant on the integrity of the sources and on the soundness of my memory

Addendum: I mentioned 3 types of compression. Todd illustrated yet another. it's likely that there are more (that I don't know about or that I have forgotten..

And, I don't know what type of compression is used in whatever "compression chip" you are referring to.

An example of the application of the kind of compression that Todd is referring to is the Tokenization of Keywords (used by such computer languages as Forth to compact code for distribution).

Thus, for example, dictionary words are assigned a single byte "token" and that is stored instead of the multi-byte name. For example: the word "CRANK-IT" might be represented by the token byte 0b00000001, which is a bit shorter than 0b01000011, 0b01010010, 0b01000001, 0b01001110, 0b01001011, 0b00101101, 0b01001001, 0b01010100. Then, the word "STUFF-IT" by might be represented by the byte 0b00000010, etc.

This kind of compression is only effective if the tokenized word is used more than once in the program.