3 hamming distance

Question 1

Hamming distance

Answer 1

MS under this metric
x,y ∈S^n
d(x,y)= #positions in which x and y differ
=#{i: x_i ≠y_i}

Question 2

Prove that Hamming distance is a metric space

Answer 2

(M1) d(x,y) =0 iff x,y don’t differ in any position iff x and y are the same for every position iff x =y
(M2) symmetric by defn
(M3) If x=y then 0= d(x,y) ≤ d(x,z) +d(z,y)
if x ≠y then for some i in {1,..,n} if x_i ≠y_i then d(x,y) increases by 1.
d(x,z)+d(z,y) must also increase by 1 or 2.
(if no increase then both x_i=z_i and z_i=y_i but this means x=y which is a contradiction). It increases by 2 if both x≠z and z≠y or just by 1 if only one of these.

Question 3

Hamming weight

Answer 3

non zero positions in x
d(x,y) = d(0,x-y) = w(x-y) useful

w(x) = d(x,0)

Question 4

Minimum distance d(C)

Answer 4

of code C⊆ S^n
min{d(x,y): x,y∈C s.t x≠y}

Question 5

Notation Σ_5
Σ^2 _5

Answer 5

Σ_q alphabet
| Σ_q|= q

Σ^n _q means sequence length n from alphabet size q
ordered n-tuples from Σ_q

Question 6

Σ
^3
_2

Answer 6

{1,2}^3 ={1,2} X{1,2} X{1,2}
{111,112,211,121,221,212,222,121,}
where we have ijk to mean (i,j,k) for alli,j,k in {1,2})

common exam q notation

Question 7

Encoding map examples:
T= {a,b}
S={0,1}
f(a)=001
f(b)=010
S^3? T*?
f(abba)?

Answer 7

T* words over T S^3 ={0,1}^3
Not all S^3 are in image of map

f(abba)=00101000

Question 8

Encoding map examples: T={N,S,E,W} S={0,1}
f_1(N)=00
f_1(E)=10
f_1(S)=01
f_1(W)=11
Min distance?

Answer 8

f1(EESW ) = f ((E, E, S, W )) = 10100111

f_1 is a perfect code,
all S^2 are in image
Min distance = 1

Question 9

Encoding map examples: T={N,S,E,W} S={0,1}
f_2(N)=000
f_2(E)=101
f_2(S)=011
f_2(W)=110
How is it generated from f_1?
f_2(EESW ) =

Min distance?

Answer 9

by parity check digit on f_1
f_2: T to S^2

f2(EESW ) = 101101011110
Min distance d(c)=2
check by 2 way table

Question 10

Encoding map examples: T={N,S,E,W} S={0,1} S^5
f_3: T to S^5
f_3(N)=00000
f_3(E)=10110
f_3(S)=01101
f_3(W)=11011
How is it generated from f_1 and f_2?

Min distance?

Answer 10

concatenation f_2 and f_1

Min distance d(c)=3

Question 11

relationship between C_i and C_{i+1} extending the codes in examples NESW

Answer 11

C_i⊆ C_{i+1}
d(C_{i+1}) bigger than or equal to? d(C_{i))