[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [[oc] Huffman coding]
----- Original Message -----
From: "Richard Herveille" <richard@asics.ws>
To: <cores@opencores.org>
Sent: Friday, October 25, 2002 6:15 PM
Subject: 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.
>
In my example the data had a 2 bit field indicating the field width
not the shift count. You could conserve RAM width by encoding
a shift count (one bit in this example).
Address bit pattern shift count bit message
000 01 0 0
001 10 0 10
010 11 0 110
011 10 1 111
In this case the decoded field width is bit pattern + shift count
However, now note that instead of shift count you could store
the value itself and interpret the field width differently
Address data bit message
000 001 0
001 010 10
010 011 110
011 100 111
Field width is most significant 2 bits of data + 1
The stragies and table design would change depending on the
universe of numbers.
Note, if incomming data is unknown then it must be examined to
determine the best strategy to lay out the tables. Because there
is a tradeoff between RAM (ROM) size and logic elements or
program space you may find it better to use a bit more RAM
or ROM than the LE's or code space to compress and extract
the data. Huffman encoding appears to work best with a small
number of values with biased distribution (i.e. very few numbers
in universe occure most often). Another area where use of Huffman
works best is if you can re-arange the input data such that it
provides for better encoding density. An example of this is when
sampleing A/D data that you convert the absolute value into a
relative value as compared to the prior value. (i.e. record the deltas).
In this way, even with a large universe of numbers you can encode
with a relatively small set of frequently re-occuring values.
Regarding FPLD and RAM for encoding/decoding.
Keep in mind that the logic gates in an FPLD are emulated by use
of the equivalence of a lookup table in RAM. Instead of programming
these lookup tables to construct logic gates you can also construct the
tables to directly encode/decode the data.
Jim Dempsey
> 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
--
To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml