2 Error detection correction

Question 1

𝜏- Error detecting

Answer 1

𝜏- Error correcting
d(C) ≥ 𝜏+1
can detect up to 𝜏 errors

Question 2

t- Error correcting

Answer 2

t- Error correcting
d(C) ≥ 2t+1
can correct up to t errors
using nearest neighbour algorithm

Question 3

q-ary (n,M,d) codes

Answer 3

Codes block length n , M codewords and min dist d

Question 4

q-ary (n,M,d) codes correct up to

Answer 4

t = floor((d-1)/2)
errors

proof: If x transmitted and y=x+e received weight(e)=t #errors

Contradiction:Assume there is a codeword z closer to y than x. (That we can’t correct t errors correctly).
d(z,y) ≤ d(y,x) then
d(z,x) ≤ d(x,y) +d(y,z) ≤2d(y,x) = 2w(x-y)= 2*t#errors ≤d-1 which contradicts the min distance
thus we can correct t errors correctly

Question 5

d(C)inequalities for error detec and correct 3.5. Proposition

Answer 5

(a) d(C) ≥ t + 1 if and only if C can detect
up to t errors;
(b) d(C) ≥ 2t + 1 if and only if C can correct up to t errors using
“nearest neighbour” decoding.

Question 6

3.5. Proposition PROOF
(a) d(C) ≥ t + 1 if and only if C can detect
up to t errors;

Answer 6

Let C ⊆ S^n. Consider the collection of t-balls centred on all
x ∈ C. , balls NHD caused by up to t transmission errors.
(a) If d(C) ≥ t + 1 then no x lies in another’s ball. Thus if 1 up to
t errors occur then the received message is not in C and we know
we have an error.

Question 7

3.5. Proposition PROOF
(b) d(C) ≥ 2t + 1 if and only if C can correct up to t errors using
“nearest neighbour” decoding.

Answer 7

Let C ⊆ S^n. Consider the collection of t-balls centred on all
x ∈ C. , caused by up to t transmission errors.

(b) If d(C) ≥ 2t + 1 then even the balls are disjoint (this is
perhaps not so obvious with the Hamming distance, cf. say the
usual Euclidean metric, but the triangle inequality is what we need
to confirm it), and if 1 up to t errors occur then the received
message is closer to x than any other y ∈ C The reverse implications of (a) and (b) are left as an exercise.
Hint: You may assume that any number of errors can occur in any
positions. □

Question 8

r-ball

Answer 8

ball of radius r (or
r-ball) centred on x is
Br(x) := {y ∈ S^n|d(x, y) ≤ r}
That is, the set of sequences that differ from x in no more than r
places

Question 9

r-sphere

Answer 9

Sr(x) := {y ∈ S^n|d(x, y) = r}
That is, the ‘outer shell’ of an r-ball

Question 10

The reverse implications of (a) and (b) are left as an exercise.
Hint: You may assume that any number of errors can occur in any
positions. □

Answer 10

c can detect up to t errors implies d(c) ≥ t + 1:

c can correct up to t errors implies d(c) ≥2 t + 1:

Question 11

q-ary code of length n subset of….

How many subsets?

Answer 11

Σn^ _q
|P( Σn^ _q )|2^(q^n) #of these subsets