Home /
Expert Answers /
Advanced Math /
proof-of-the-kraft-inequality-for-uniquely-decodable-codes-a-6-pts-assume-a-uniquely-decodable-pa329
(Solved): Proof of the Kraft inequality for uniquely decodable codes: (a) (6 pts) Assume a uniquely decodable ...
Proof of the Kraft inequality for uniquely decodable codes: (a) (6 pts) Assume a uniquely decodable code has lengths
l_(1),dots,l_(M). In order to show that
\sum_j 2^(-l_(j))<=1, demonstrate the following identity for each integer
n>=1:
[\sum_(j=1)^M 2^(-l_(j))]^(n)=\sum_(j_(1)=1)^M \sum_(j_(2)=1)^M cdots\sum_(j_(n)=1)^M 2^(-(l_(j_(1))+l_(j_(2))+cdots+l_(j_(n))))(b) (6 pts) Show that there is one term on the right for each concatenation of
ncodewords (i.e.. for the encoding of one
n-tuple
x^(n)) where
l_(j_(1))+l_(j_(2))+cdots+l_(j_(n))is the aggregate length of that concatenation. (c) (6 pts) Let
A_(i)be the number of concatenations which have overall length
iand show that
[\sum_(j=1)^M 2^(-l_(j))]^(n)=\sum_(i=1)^(nl_(max)) A_(i)2^(-i)(d) (6 pts) Using the unique decodability, upper bound each
A_(i)and show that
[\sum_(j=1)^M 2^(-l_(j))]^(n)<=nl_(max)(e) (6 pts) By taking the
nth root and letting
n->\infty , demonstrate the Kraft inequality.
