Exam Prep

Question 1

Explain what capacity implies in practice for an error correction code

Answer 1

The capacity is the highest rate of the error correction code whilst maintaining errorless decoding

Question 2

Capacity

Answer 2

max_pmf I(X;Y)

Question 3

Conditional Entropy Inequality

Answer 3

“Information Can’t hurt”

H(X | Y) <= H(X)

Question 4

Chain Rule of Entropy

Answer 4

H(X, Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)

Question 5

Conditional Entropy

Answer 5

H(Y|X) = SUM_x p(x) H(Y|X=x)
= - SUM_x SUM_y p(x) p(y|x) log p(y|x)

Question 6

Chain Rule of Conditional Entropy

Answer 6

H(X, Y|Z) = H(Y|Z) + H(X|Y, Z) = H(X|Z) + H(Y|X, Z)

Question 7

Joint Entropy

Answer 7

H(X, Y) = - SUM_xy p(x,y) log p(x,y)

Question 8

Relative Entropy (Kullbach-Leiber Distance)

Answer 8

D(p||r) = SUM_x p(x) log p(x)/r(x)

Question 9

Bayes Theorem

Answer 9

P(B|A) = P(A|B) × P(B)/ P(A)

Question 10

Conditional Probability

Answer 10

P(B|A) = P(A ∩ B) / P(A)

Question 11

Total Probability

Answer 11

if {A1,A2, . . . ,Ak } is a partition of Ω,
then for any B ⊂ Ω

P(B) = SUM(i=1 -> k) P(B|A_i)P(A_i)

Question 12

Mutual Information

Answer 12

I(X;Y) = = H(Y) − H(Y|X)

Question 13

Entropy

Answer 13

H(X) = - SUM_x p(x) log p(x)

Question 14

Two key properties of Entropy (value)

Answer 14

Always nonnegative

Only depends on the probabilities in the pmf of the RV

Question 15

Binomial pmf X ∼ Bi(n, q)

Answer 15

X ∼ Bi(n, q)

p(k) = (nCk) (q^k)(1-q)^n-k for k = 0,1,2,…,n

Question 16

Joint Distribution

Answer 16

Pr(X = x, Y = y) = p(x, y)

Question 17

Conditional Distribution

Answer 17

p(y|x) = p(x, y)/ p(x)

Question 18

Marginalisation

Answer 18

p(x) = SUM_y p(x,y)

Question 19

Independence of RV

Answer 19

p(x,y) = p(x)p(y) for all x, y

Question 20

Expectation of a discrete RV

Answer 20

E(X) = SUM_x p(x) x

Question 21

Expectation of two RVs

Answer 21

E(X+Y) = E(X) + E(Y) unless independent then
E(X+Y) = E(X)E(Y)

Question 22

Log 1/x =

Answer 22

• log x

Question 23

log(x/y) =

Answer 23

log x - log y

Question 24

When is entropy maximised and minimised

Answer 24

When p = u, H(X) = log|X|
When p has one probability = 1 and the rest = 0, cardinality > 1

Question 25

Fundamental Lower Bound

Answer 25

L(C) >= H(X)

Question 26

Kraft’s Inequality

Answer 26

SUM(i=1, m) D^-l_i <= 1

Question 27

Average Codeword Length

Answer 27

SUM_x p(x)l(x)

Question 28

Property of H(X|g(X))

Answer 28

H(X|g(X)) >= 0

Question 29

How many errors can a repetition code detect and correct. What is its main issue

Answer 29

The code can detect n-1 errors, it can detect and correct up to floor(n/2) errors.

Its main issue is efficiency, the rate is 1/n, so as n tends to inf, the rate tends to 0.

Question 30

Rate of an error detection/correction code

Answer 30

rate = len(msg) / len(msg) + len(redundancy)

measured in bits/ channel use

Question 31

Data Processing Inequality

Answer 31

if X → Y → Z then
I(X; Y ) ≥ I(X; Z)

Question 32

AEP

Answer 32

p(X_1, . . . ,X_n) → 2^−nH(X)

Question 33

Shannon codeword length

Answer 33

l*_i = ceiling(log_D 1/p_i)

Question 34

Shannon average codeword length and its relationship with entropy

Answer 34

H(X) ≤ L* < H(X) + 1

Question 35

What is the probability distribution associated with a transition probabilility matrix Π

Answer 35

[p(y|x)]

Question 36

What is the channel capacity of a BSC

Answer 36

C = 1 - h(ε) bits/channel use

Question 37

What is the channel capacity of a Binary Erasure channel

Answer 37

C = 1 − α bits/channel use

Question 38

Definition of a symmetric channel

Answer 38

if all the rows of the transition probability matrix Π are permutations of each other, and so are the columns, the channel is said to be symmetric

Question 39

Definition of a weakly symmetric channel

Answer 39

if all the rows of Π are permutations of each other, and its columns add up to the same value, the channel is weakly symmetric

Question 40

Key property of channel capacity in relation to I(X;Y)

Answer 40

any maximum of I(X; Y ) is the global maximum

Question 41

binomial theorem

Answer 41

(a+b)^n = SUM(k=0, n) (nCk) a^k b^n-k

Question 42

Probability of undetectble errors in parity checking (excluding zero)

Answer 42

SUM(k=2, n) (nCk) q^k (1-q)^n-k

Question 43

Pr(E is even) in parity checking under errors (binomial expansion of (1-2q)^n

Answer 43

(1 − 2q)^n = (1 − q − q)^n
= SUM(k=0, n) (nCk)(-1)^k q^k (1-q)^n-k

Question 44

What is the minimum hamming distance and its relation to the number of errors that can be corrected

Answer 44

d = 2t + 1, we can correct t errors

EX: (7,4,3) Hamming code we can detect two errors and correct one

Question 45

Rate of a hamming code (n, k, d)

Answer 45

k/n bits/ channel use