Re: [[oc] Huffman coding]

[Graham Seaman <graham@seul.org>]

On Fri, 25 Oct 2002, Richard Herveille wrote:

> 
> I understand how this will work for encoding. This is how I intended to do it.
> But I don't understand how this works for decoding. For decoding I have an 
> unknown size, an unkown data-stream, and I need the first matching result.
> I want to use the same dictionary-table (i.e. memory) for decoding and 
> encoding. It's probably me, but I just don't understand what you want to do.

Ok, here's a ridiculously simple example. We have the numbers 1 to 4
Huffman encoded as 1=0, 2=10, 3=110, 4=111, and I want to send the
message 4,1,1,2,1,3, which will be huffman encoded as 11100100110

To decode this I need a RAM with an address bus the size of the largest
huffman code, ie. 3 bits. The data width is equal to the width of the
largest decoded value + log_2 of the address bus width.

I load the decoder memory as follows, where the data stored is in two
parts: the reconstructed values and the length of the huffman code for 
that value, so:
Address Data 
000    001 01
001    001 01
010    001 01
011    001 01
100    010 10
101    010 10
110    011 11
111    100 11

My data to decode (from above) is 11100100110. To initialise the system
I shift this till the first bit is aligned with the MSB of the address
bus. That presents the address 111 to the RAM, outputting 4, and telling 
me to shift the data along by three bits. That presents 001 to the RAM,
outputting 1, and telling me to shift by one bit. Keep on doing this
and we get in succession (I've restarted from the beginning):
Address     Data out  Bits to shift by
111		4	3
001		1	1
010		1       1
100		2       2
011		1       1	 
110		3       3
xxx

That always works: it's the fact that no huffman code is a prefix of any
other that lets you do it. But it's very heavy on RAM use; for your
16bit huffman code and 6 bit data you need a 16x10 RAM, most of the
contents of which is duplicates of the values for the very short codes.

Now you're going to tell me I've misunderstood and this isn't what you
wanted to do at all...

Graham
> 
> Also the data is stored in RAM, not in ROM; it is user programmable.
> 
> Richard
> 

--
To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml