Math 480, Fall 2016, Assignment 13
From cartan.math.umb.edu
"Reeling and Writhing, of course, to begin with," the Mock Turtle replied; "And then the different branches of Arithmetic - Ambition, Distraction, Uglification, and Derision."
- - Lewis Carroll, Alice's Adventures in Wonderland
Carefully state the following theorems (you do not need to prove them):[edit]
- Fano's inequality.
- Theorem relating $H(\mathscr{A}|\mathscr{X})$ to $H(\mathscr{B}|\mathscr{X})$ when $\mathscr{A}$ is an amalgamation of $\mathscr{B}$.
- Theorem relating $H(\mathscr{X}|\mathscr{A})$ to $H(\mathscr{X}|\mathscr{B})$ when $\mathscr{A}$ is an amalgamation of $\mathscr{B}$.
- Theorem relating $I(\mathscr{A},\mathscr{X})$ to $I(\mathscr{B},\mathscr{X})$ when $\mathscr{A}$ is an amalgamation of $\mathscr{B}$.
- Theorem relating $H(\mathscr{X}^n|\mathscr{Y}^n)$ to $H(\mathscr{X}|\mathscr{Y})$.
- Theorem relating $I(\mathscr{X}^n,\mathscr{Y}^n)$ to $I(\mathscr{X},\mathscr{Y})$.
- Discouraging half of the noisy channel theorem.
Solve the following problems:[edit]
- In a 1950 paper, Shannon estimated the entropy of English text, neglecting case and punctuation, to be approximately 1 bit per character when encoded in sufficiently large blocks. (See here for the original paper and here for an expository summary.) How fast do you expect to be able to transmit such text through a 1Mbps DSL connection, modeled as a symmetric binary channel with reliability $\rho=0.95$, without introducing significant message corruption?
- A communication system transmits characters from a $27$-letter alphabet with an error rate of $e=0.01$. Give an upper bound for the equivocation of the system, measured in characters per transmission (i.e. in $27$-ary digits per transmission).
- (Optional, but not terribly hard) Formulate and prove a version of the discouraging half of the noisy channel theorem that allows for variable-length encodings.
