Communication chapter 3 - definitions and theorems

Question 1

Noisy Channel

Answer 1

A (binary) noisy channel consists of a set of probabilities {p₀₀, p₀₁, p₁₀, p₁₁} where pᵢⱼ is the probability that j is received if i is sent. They must satisfy p₀₁+p₀₀=1=p₁₀ + p₁₁

Question 2

symmetric

Answer 2

A noisy channel is symmetric if the probability of flipping a bit is p for some p∈[0,1/2]

Question 3

memoryless

Answer 3

A noisy channel is memoryless if the outcome of each transmission is independent of the outcome of previous ones

Question 4

Channel encoding scheme

Answer 4

Given a finite set A and n∈ℕ a channel encoding scheme (encoding) of A into string of length n is an injective function f:A->{0,1}ⁿ. The code C=C(f) is the image of f

Question 5

Channel decoding scheme

Answer 5

Given a finite set A and n∈ℕ a channel decoding scheme (decoding) is a map g:{0,1}ⁿ->A such that g(f(x))=x for every x∈A.
We can also consider decoding to be the map h:{0,1}ⁿ->A such that h(y)=y for all y∈C.

Question 6

block

Answer 6

A code C is called a block [n,k]-code if A={0,1}ᵏ for some k∈[n]

Question 7

Probability of wrong decoding

Answer 7

For a code C of length n and a decoding h the probability of wrong decoding is defined as follows
Pₑᵣᵣ (c,h) = max (sum of all y∈{0,1}ⁿ(P y is recieved | C is sent))

Question 8

Transmission rate

Answer 8

The transmission rate of a code C of length n is R(C)=log|C|/n

Question 9

Hamming Distance

Answer 9

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 10

minimum distance

Answer 10

The minimum distance of a code C, denoted by dₕ(C) is the minimum distance amoung all the pairs of codewords
dₕ(C)=min dₕ(c,c’)

Question 11

minimum distance decoding

Answer 11

A decoding h:{0,1}ⁿ-> C is a minimum distance decoding for C if for every x∈{0,1}ⁿ we have dₕ(x,h(x)) = min dₕ(x,c)

Question 12

probability of wrong decoding for a minimum distance decoding

Answer 12

Let C be a code of length n and h a minimum distance decoding for C. The probability of wrong decoding for C is
Pₑᵣᵣ (C) = max (sum of all y∈{0,1}ⁿ( pᵈₕ⁽ˣ,ᶜ⁾ (1-p)ⁿ⁻ᵈₕ⁽ˣ,ᶜ⁾)

Question 13

t-error-detecting

Answer 13

A code is t-error-detecting if a minimum distance decoding can detect up to t errors. That is, if t errors occur then one can identity an error has been made.

Question 14

t-error-correcting

Answer 14

A code is t-error-correcting if a minimum distance decoding can correct up to t-errors. That is, if up to t-errors are made then one can still identify the correct codeword which was sent.

Question 15

proposition. t-error detcing./correcting and minimum distance.

Answer 15

A code C of length n is

(i) t-error-detecting iff dₕ(C)≥t+1
(ii) t-error-correcting iff dₕ(C)≥2t+1