Re: huffman code question.....


"Dirk Van de moortel" <dirkvandemoortel@xxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:YpRcf.44759$Lz7.2091100@xxxxxxxxxxxxxxxxxxxxxxxx
>
> "pitter" <fishy_1980@xxxxxxxxxxx> wrote in message news:25500100.1131664147297.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxxxxx
> > anyone can help ???
> >
> > Suppose a data file contains a sequence of 8-bit characters such that all 256 characters are
> > about as common: the maximum character frequency is less than twice the minimum
> > character frequency. Prove that Huffman coding in this case is no more efficient than using an
> > ordinary 8-bit fixed-length code.
>
> Suppose fmax = f(0) > f(1) > ... > f(254) > f(255) = fmin

Ow, this should be
fmax = f(0) >= f(1) >= ... >= f(254) >= f(255) = fmin

> Given your
> f(0) < 2 f(255),
> try to prove that also
> f(0)+f(1) < 2 ( f(254)+f(255) )

that remains the essential part.

>
> and you'll need some induction as well :-)

and of course, you don't need induction in this case.
It's just a matter of notation and bookkeeping.

Dirk Vdm


.