Re: [[oc] Huffman coding]

[Richard Herveille <richard@asics.ws>]

> On Fri, 25 Oct 2002, Richard Herveille wrote:
> > > Off the top of my head, but I think something like this works. You have
> > > a shift register presenting (say) 8 bits of the incoming stream to two
> > > roms (ie. same address selected in each). In rom 1 you have the data
> > > (what you called addresses above). The data is stored many times over;
> > > say have you huffman codes 00, 01, 110, etc then ALL addresses starting
> > > 00 contain the same data, all addresses starting 110 contain the same
> > > data etc. So your 8 incoming bits select the valid data for the the
> > > first incoming code. ROM 2 contains lengths; ie. at addresses starting
> > > 00 you store the number 2; at addresses starting 1110 you store the
> > > number 4 etc. This length is used to control the shift register to
> > > shift out the x bits already used for the first code, ready to look at
> > > the next code. Would that work? Be too slow? I'm pretty sure the prefix
> > > condition guarantees uniqueness of the addresses done this way, but I
> > > haven't tried working it out on paper - tell me if I'm being silly!
> >
> > I was thinking about something similar.
> > For encoding:
> > The incomming data is of a fixed size, 6bits to be exact.
> > This data is huffman coded into a variable bit-length (2 to 16bits).
> > I want to use the incomming data as an address into a 6x20bit memory.
> > The memory's lower 16bits contain the huffman code, and the upper contain
> > the code-size.
> > This should be pretty easy.
> >
> > For decoding:
> > I receive a bitstream and I need to match the incomming variable
> > huffman-code with an address. The more I think about it, the more I am
> > pushed to a CAM. Anybody any suggestions how to code a CAM in HDL?? Or do
> > you have a better suggestion.
>
> I don't understand. Why won't the same method work for decoding as
> encoding (as I described above)? The prefix condition should guarantee it
> to work, as far as I can see. It needs a 16x10 ROM, so it's slightly
> larger than your encoder, but isn't that still going to work out cheaper
> than a CAM? If you're worried about efficient space usage of the ROM, you
> have the same lack of efficiency in the encoder: most of the bits stored
> will be zeros in the encoder, as compared to duplicates in the decoder.

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.

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

Richard



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