let C be a Prefix Code d1...dn length of each word

let C be a Prefix Code d1...dn length of each word

Post by mastere198 » Fri, 18 Nov 2005 02:05:30


I need to show that

2^(-d1)+...+2^-(-dn)<=1

Tried to do it in induction but it didn't work. Is that the way to do
it?
 
 
 

let C be a Prefix Code d1...dn length of each word

Post by Wille » Fri, 18 Nov 2005 02:27:33

Please don't put meaningful content in the subject line.


) Subject: Re: let C be a Prefix Code d1...dn length of each word
) I need to show that
)
) 2^(-d1)+...+2^-(-dn)<=1

Isn't that the Kraft Inequality ?
I assume you mean prefix-free code, by the way.

) Tried to do it in induction but it didn't work. Is that the way to do
) it?

I'm no expert on it, but one possibility would be to
assume that it's >1 and then try to derive a contradiction.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 
 
 

let C be a Prefix Code d1...dn length of each word

Post by Jackso » Fri, 18 Nov 2005 17:27:32


2^-1 + 2^-2 + 2^-3 + ... = 1 is well-known and almost obvious[1/2 + 1/4
+ 1/8 + ...]. I'm uncertain precisely what you asked, but I'm almost
certain that the inequality follows from this equation.