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

• Whenever you search in PBworks or on the Web, Dokkio Sidebar (from the makers of PBworks) will run the same search in your Drive, Dropbox, OneDrive, Gmail, Slack, and browsed web pages. Now you can find what you're looking for wherever it lives. Try Dokkio Sidebar for free.

View

# Scribe Note3-3 (9th Feb)

last edited by 14 years, 3 months 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

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

#### Mak said

at 10:38 am on Feb 23, 2009

Oh... D:\贴图法? :-)