Problem Set 3
Q5. Converse for channel coding theorem
intuitively, converse means what you can achieve using a certain of energy
(a). First prove that 
What we need:
,
,
,
, 

Proof: 


Note: 1.
since 
2. Chain Rule
3. Directed Markov chain: 




Now prove that 
What we need: 
Proof: 
Fano's inequality

data processing theorem

Result of part A
Problem Set 4:
Zero-Error Data Compression
Q1. (DNA Encoding)
(a) For scheme 1. Error associated with it
2. encoding time complexity, exponential time to decode it. using the binary search, but you need to sort the sequence beforehead. considering he the DNA sequence, using the random scheme, you need a large codebook
note: complexity contains time and space complexity, for space complexity, it is codebook size.
(c) extend the tree to level
, we get the tree as below:

Based on the observation, we get the descendents in level
are 
so 
or
and it is called Kraft Inequality
(d) from the observation of the tree above, we can conclude that prefix-free code leads to Kradt Inequality and vice versa


Comments (1)
Mak said
at 10:38 am on Feb 23, 2009
Oh... D:\贴图法? :-)
The notes contain the links:
file:///D:/DOCUME~1/POPPIN~1/LOCALS~1/Temp/moz-screenshot.jpg
file:///D:/DOCUME~1/POPPIN~1/LOCALS~1/Temp/moz-screenshot-1.jpg
I guess these can be removed?
You don't have permission to comment on this page.