I'm looking for something that will be fast and easy to decode at fpga config time.
I just did some statistical analysis of a bunch of existing Spartan 3 bit streams. If you treat them as bytes, and histogram the byte codes, there's some impressive stats, with code 0x00 of course dominant, then
0xFF, and the next 16 most common codes huge, tapering off pretty hard. That makes sense, since LUT bits are usually zero, so simple codes like 0x01...0x80 and simple 2-bit combos are most common. Block ram is usually 0 in our designs, too. So a fixed dictionary should work pretty well.So it looks like a byte stream would do, with byte codes that say stuff like...
00000000 end of file001nnnnn make N zero bytes, N=1 to 31
010nnnnn make N 0xFF bytes, ditto011nnnnn the following N bytes are raw, unencoded stuff
1nnnnnnn look up code N in dictionary, N = 1 to 127where the dictionary is a list of the most common 96 single bytes followed by the most common 32 byte pairs. Net compression in this case is just about 1:1!
Something like that.
Now the question is, how much compression will this give? I suppose I'll have to code it and see. I need less than 2:1 now, and that shouldn't be hard.
John