[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [[oc] Huffman coding]
>
> > 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
>
> Good example. If sent using 3 bits each (octal) then message length would
> be 18 bits (6 octits * 3 bits). The encoding reduced this from 18 to 11
> bits.
>
> Note though if this were indeed the example (universe of numbers are
> 1, 2, 3, 4) then you could also encode by subtracting 1 then sending
> the data as 2 bits. Decode by adding one to the 1 bits. In this manner the
> data message would be 12 bits (6 quadits * 2 bits).
>
> > 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.
>
> You can make the table smaller than this. If you use a counter to count the
> ones the table can be reduced to the maximum number of ones.
>
> > 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
>
> Address Data bit message
> 000 001 01 0
> 001 010 10 10
> 010 011 10 110
> 011 100 11 111
Thanks for the examples, that did the trick. smart way of doing it.
What I was thinking about is actually using the same RAM for encoding and
decoding, but after thinking some more I came to the conclusion that that is
not possible (unless you do a full memory search).
Question shouldn't the tables be:
Address Data
000 01 01
001 01 01
010 01 01
011 01 01
100 10 10
101 10 10
110 11 11
111 11 11
Address Data bit message
000 01 01 0
001 10 10 10
010 11 10 110
011 11 11 111
because you need to shift 3bits for the last result, not four.
Richard
>
> Note, you end counting at 0 bit or at limit of bit width.
> The above table is one half the size of your example.
>
> Jim Dempsey
>
> > 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
--
To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml