Re: [[oc] Huffman coding]

[Graham Seaman <graham@seul.org>]

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.

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