Re: [[oc] Huffman coding]

[Graham Seaman <graham@seul.org>]

On Thu, 24 Oct 2002, Richard Herveille wrote:

> Thanks Andras and Graham,
> 
> Here's the useage: hardware Motion-JPEG codec.
> One of the last steps in JPEG encoding (and one of the first in decoding) is 
> to huffman-code some of the generated data.
> The dictionary is user programmable (i.e. it is stored in memory). Encoding 
> isn't a major problem. I can use the generated data as an address into the 
> memory. Also I (probably) can figure out how to handle the different 
> bit-length for each code.
> The real problem is decoding. For decoding I receive the encoded bit-stream, 
> then I need to match this with a bitstream from the dictionary (i.e. the 
> memory) and return the original data (i.e. the address). I don't want to use 
> CAM (content addressable memory), and I certainly don't want to do a search 
> on the entire memory.
> Anybody any suggestions ??

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! 

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