Re: [[oc] Huffman coding]

["Ryan Henderson" <ryan.henderson@attbi.com>]

I'm trying to do a similar thing to create LZSS encoding.
http://www.rasip.fer.hr/research/compress/algorithms/fund/lz/lzss.html I've
got a forward looking buffer, and a backwards looking window that I slide
along the stream.  I'm using pointers into memory for the buffer and window
and treating them like a ring buffer.

I roll through, looking for the longest match in the window.  When I get to
the end I offset the window by one and look again.  It takes me 256^2 clocks
to search a 255 long window.

I don't know if this helps you much 'cause I think this is how a CAM works.
The only other choice is to use a pile of flip flops and comparitors.

I guess your implementation depends on how big your dictionary is.

$0.02
- Ryan


----- Original Message -----
From: "Graham Seaman" <graham@seul.org>
To: <cores@opencores.org>
Sent: Thursday, October 24, 2002 2:44 PM
Subject: Re: [[oc] Huffman coding]


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

--
To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml