Re: [[oc] Huffman coding]

["Jim Dempsey" <tapedisk@ameritech.net>]

----- Original Message -----
From: "Graham Seaman" <graham@seul.org>
To: <cores@opencores.org>
Sent: Friday, October 25, 2002 3:37 PM
Subject: Re: [[oc] Huffman coding]


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

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