Communication Chapter 3

Question 1

Symmetric p₁₀=p₀₁ =

Answer 1

p₁₀ = p₀₁ = p

Question 2

Symmetric p₀₀ = p₁₁ =

Answer 2

p₀₀ = p₁₁ = 1-p

Question 3

noisy channel probabilities satisfy

Answer 3

p₀₁+p₀₀=1=p₁₀ + p₁₁

Question 4

crossover probability

Answer 4

the probability p which is the probability that 0 is flipped to 1 which is equal to the probability that 1 is flipped to a 0.

Question 5

if p = 0 then

Answer 5

the channel is noiseless

Question 6

if p = 1/2 then

Answer 6

the channel is useless (it is too noisy to decipher any of the messages)

Question 7

What is the probability that precisely i errors occur with crossover probability p

Answer 7

(n choose i) p ^ i (1-p)^ (n-i)

i.e. the binomial distrubution

Question 8

Channel Encoding map

Answer 8

f:A->{0,1}ⁿ

Question 9

Channel decoding maps

Answer 9

g: {0,1}ⁿ->A such that g(f(x))=x for every x∈A.
h: {0,1}ⁿ->A such that h(y)=y for all y∈C.

Question 10

length of a code

Answer 10

we say a code C has length n is all its codewords have length n

Question 11

If a code has length n then the code is automatically…

Answer 11

it is automatically prefix free

Question 12

A

Answer 12

the alphabet which we are encoding (or decoding to)

Question 13

probability of wrong decoding (in words)

Answer 13

Pₑᵣᵣ = maximum of the sum over all y∈{0,1}ⁿ of the probability y is received given c is sent

Question 14

Transmission rate formula

Answer 14

R(C)=log|C|/n

Question 15

The higher the transmission rate…

Answer 15

the more efficiently the codewords are sent

Question 16

Transmission rate is always less than or equal to

Answer 16

`1

Question 17

|A|=

Answer 17

|C|

Question 18

How to calculate the smallest code length you can achieve for a code C of size |C|

Answer 18

log|C|

i.e. there are 2ˣ strings of length x

Question 19

if C is and [n-k] code then R(C)=

Answer 19

R(C)=k/n

Question 20

How to check a decoding is valid

Answer 20

check g(f(c))=c

Question 21

Hamming Distance

Answer 21

The Hamming Distance denoted dₕ(x,y) between x=x₁,..,xₙ∈{0,1}ⁿ and y=y₁,..,yₙ∈{0,1}ⁿ is the number of places where the two strings differ
dₕ(x,y) = |{i∈[n]: xᵢ≠yᵢ}|

Question 22

metric axioms

Answer 22

1. Positive
2. Symmetric
3. triangle inequality

Question 23

The bigger the minimum distance…

Answer 23

The further codewords are away from each other which means its less likely to have errors

Question 24

minimum distance decoding informal

Answer 24

A decoding is a minimum distance decoding if no matter what string you take x is denoted as h(x) and h(x) is the closest codeword to x

Question 25

if two codewords are equally close to c in a minimum distance decoding…

Answer 25

choose either

Question 26

How to work out a minimum distance decoding

Answer 26

• work out the hamming distance between the encoded word and all the codewords
• choose the codeword with the smallest hamming distance

Question 27

We want Pₑᵣᵣ (C) to be…

Answer 27

as small as possible

Question 28

How to tell if a code is t-error-detecting

Answer 28

if t errors are made and the result is not another codeword in C then it is t-error-detecting

Question 29

How to tell is a code is t-error-correcting

Answer 29

If you received a codeword with t errors and then apply minimum distance decoding it is t-error-correcting if the result is the correct code

Question 30

A (repetition code) string is wrongly decoded via a minimum distance decoding if…

Answer 30

it contains n+1/2 errors where n is the length of codewords

Question 31

how many strings of length x

Answer 31

2ˣ

Question 32

number of strings of length n that differ from x in exactly i positions

Answer 32

n choose i

Question 33

Probability of erroneous decoding for the repetiion code

Answer 33

Pₑᵣᵣ (C) = P( bin(n,p)) ≥ (n+1)/2 )

Question 34

Hamming Distance Equation

Answer 34

dₕ(x,y) = |{i∈[n]: xᵢ≠yᵢ}| = the sum from i=1 to n of |xᵢ-yᵢ|

Question 35

Probability of erroneous decoding for a minimum distance decoding

Answer 35

maximum over all c inC of the sum over y in {0,1}^n where h(y) is not c of p to the power of the hamming distance between c and y multiplied by (1-p) to power of (n minus the hamming distance between c and y).