| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

Scribe Note3-3 (9th Feb)

Page history last edited by Lingxiao XIA 15 years ago

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 Formula

 

      What we need: Formula, Formula, Formula,

                             FormulaFormula

                             Formula

 

      Proof: Formula

                                     Formula

                                     Formula

     Note: 1. Formula since Formula

              2. Chain Rule

              3. Directed Markov chain: Formula

 

 

          Formula               Formula                                                      Formula                   Formula

      Formula

      Formula

      Now prove that Formula

 

      What we need: Formula

 

     Proof:  Formula

                                                                                               Fano's inequality

                                                                                  Formula

                                                                                                                   data processing theorem

                                                                                  Formula

                                                                                                                    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 Formula, we get the tree as below:

 

Based on the observation, we get the descendents in level Formula are Formula

so Formula

or Formula 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.