Help help help on Huffman Encoder

[kude]

Hi all,

I tried and read a lot on how to construct huffman tree from a give
(Character,frequency) input and it is easy to do it on software but can'
get the idea on Hardware and pls give me a hint.

1)on how to make sort (synthesizable) and construct huffman tree

2)How to read the codeword from the tree


Thanks



---------------------------------------
Posted through http://www.FPGARelated.com

 

[glen herrmannsfeldt]

kude <tadmas09@n_o_s_p_a_m.n_o_s_p_a_m.gmail.com> wrote:

I tried and read a lot on how to construct huffman tree from a given
(Character,frequency) input and it is easy to do it on software but can't
get the idea on Hardware and pls give me a hint.

This is exactly why hardware is different from software.

In software, operations are serial. (Or, for multicore, some number
of threads of serial operation, in parallel.)

For hardware, you have to think about how fast something needs
to be done, and how parallel it can, and should, be. The problem,
which only you can answer, is what hardware vs. speed tradeoff
is needed. How many clock cycles are available per input character?

The hardware can be designed bit serial, such that one (hopefully
fast) clock cycle is used per input bit. For finite (and known
in advance) input width, it can be done fully parallel, such that
the whole output comes out one (long) clock cycle later. That latter
is usually called combinatorial, though there is likely a latch
before and after the logic block.

Usually it will be somewhere in between, and exactly where you
have to figure out. It is a tradeoff between logic used and speed,
sometimes made without knowing all the parameters.

You could crosspost to comp.compression, where Huffman might be
discussed, but not FPGAs.

If you give some of the requirements, such as input and output
speed, data (character) width, and such, we might be able to
suggest something. Otherwise, you might look at the systolic
array architecture, though I am not completely sure that it
can be done that way.

1)on how to make sort (synthesizable) and construct huffman tree

I believe the usual one is to generate, and use, the tree as data
is being processed. That is, dynamic tree. In that case, the
important part is that the encoder tree stays synchronized with
the decoder tree, not that each is optimal for the given input.

2)How to read the codeword from the tree

A lookup table? Maybe a hash table.

-- glen