Exam Prep Flashcards

1
Q

Explain what capacity implies in practice for an error correction code

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Capacity

A

max_pmf I(X;Y)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Conditional Entropy Inequality

A

“Information Can’t hurt”

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Chain Rule of Entropy

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Conditional Entropy

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Chain Rule of Conditional Entropy

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Joint Entropy

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Relative Entropy (Kullbach-Leiber Distance)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Bayes Theorem

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Conditional Probability

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Total Probability

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Mutual Information

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Entropy

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Two key properties of Entropy (value)

A

Always nonnegative

Only depends on the probabilities in the pmf of the RV

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Binomial pmf X ∼ Bi(n, q)

A

X ∼ Bi(n, q)

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Joint Distribution

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Conditional Distribution

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Marginalisation

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Independence of RV

A

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

20
Q

Expectation of a discrete RV

A

E(X) = SUM_x p(x) x

21
Q

Expectation of two RVs

A

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

22
Q

Log 1/x =

23
Q

log(x/y) =

A

log x - log y

24
Q

When is entropy maximised and minimised

A

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

25
Fundamental Lower Bound
L(C) >= H(X)
26
Kraft's Inequality
SUM(i=1, m) D^-l_i <= 1
27
Average Codeword Length
SUM_x p(x)l(x)
28
Property of H(X|g(X))
H(X|g(X)) >= 0
29
How many errors can a repetition code detect and correct. What is its main issue
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.
30
Rate of an error detection/correction code
rate = len(msg) / len(msg) + len(redundancy) measured in bits/ channel use
31
Data Processing Inequality
if X → Y → Z then I(X; Y ) ≥ I(X; Z)
32
AEP
p(X_1, . . . ,X_n) → 2^−nH(X)
33
Shannon codeword length
l*_i = ceiling(log_D 1/p_i)
34
Shannon average codeword length and its relationship with entropy
H(X) ≤ L* < H(X) + 1
35
What is the probability distribution associated with a transition probabilility matrix Π
[p(y|x)]
36
What is the channel capacity of a BSC
C = 1 - h(ε) bits/channel use
37
What is the channel capacity of a Binary Erasure channel
C = 1 − α bits/channel use
38
Definition of a symmetric channel
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
39
Definition of a weakly symmetric channel
if all the rows of Π are permutations of each other, and its columns add up to the same value, the channel is weakly symmetric
40
Key property of channel capacity in relation to I(X;Y)
any maximum of I(X; Y ) is the global maximum
41
binomial theorem
(a+b)^n = SUM(k=0, n) (nCk) a^k b^n-k
42
Probability of undetectble errors in parity checking (excluding zero)
SUM(k=2, n) (nCk) q^k (1-q)^n-k
43
Pr(E is even) in parity checking under errors (binomial expansion of (1-2q)^n
(1 − 2q)^n = (1 − q − q)^n = SUM(k=0, n) (nCk)(-1)^k q^k (1-q)^n-k
44
What is the minimum hamming distance and its relation to the number of errors that can be corrected
d = 2t + 1, we can correct t errors EX: (7,4,3) Hamming code we can detect two errors and correct one
45
Rate of a hamming code (n, k, d)
k/n bits/ channel use