Re: [[oc] Huffman coding]

[John Sheahan <jrsheahan@optushome.com.au>]

On Fri, Oct 25, 2002 at 07:24:05PM +0200, Richard Herveille wrote:
> >
> > for many cam applications - its better to prearrange the data in a ram and
> > look it up directly by address.  I would have thought that would fit here
> > actually.
> 
> Isn't that a waiste of memory when I use the huffman-coded result to find the 
> original data. For example, the huffman code can be 16bits wide, to do 
> reverse lookup I would need a memory with a 16bit addressbus to store say 256 
> results.

If the codes you are looking up are large - it may be
expensive. around 16 bits you would probably consider carefully.
I've never looked carefully at huffman codes - but I thought the space
was fully used. And I thought many applications stopped at the 12-14
bit mark.   In this case address lookup is probably feasible.

> 
> >
> > or sort the data in the ram and do a binary search on contents. with a
> > few more bits to store the key.
> 
> Hmm this sounds interresting. Any pointers??
> 

I'm sure this has been invented many times before. Had an applcation
where ATM headers were being looked up and a big CAM was requested.
It was an envelope design to demonstrate the area of a custom CAM was
a perhaps bad idea.

It was fairly easy to show that as itmes were only added slowly - an
insertion sort on write (block shift up above the insertion point)
This does not inhibit reading.

and a binary search on read - given there were pipeline delays
available - worked in that application.

Are enough timeslots available for log2(address-space) memory reads available
on the read side?
john




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