13 Hamming codes

Question 1

Hamming codes intro (binary)

Answer 1

encodes elements x in {0,1} as codewords x∈S⁷ using check digits [7,4] binary hamming code- blocks of 7 symbols which represent:
X₁=a,X₂=b,X₄=c
X₃,X₅,X₆,X₇, = CHECK DIGITS for example s.t
X₄+X₅+X₆+X₇ EVEN
X₂+X₃+X₆+X₇ EVEN
X₁+X₃+X₅+X₇ EVEN
and will give subscript of X_i incorrect
its a linear code since determined by linear equations between variables

Question 2

a hamming code example
H_7
y_3=x_1
y_5=x_2
y_6=x_4
y1,y2,y4 check digits
y in F₂⁷ basis

Answer 2

Basis
v_1={1110000
v_2={1001100}
v_3={0101010}
v_4={1101001}

2⁴ choices m=16 dim =4 from basis

Question 3

venn diagrams considering H_7

Answer 3

Consider the Venn diagram for subsets A, B, C of
{1, 2, 3, 4, 5, 6, 7}

The code H_7 consists of all codewords y ∈ F₂⁷written in this way.

Since H_7 is determined by linear equations between variables y_i
it is a linear code. There are 24
choices for x, and these determine y,

so M = 16. Indeed H_7 has basis
v1 = 1110000, v2 = 1001100,
v3 = 0101010, v4 = 1101001. Thus the dimension is 4.

This code is best understood by looking at its equations: A is the
set of integers in {1, . . . , 7} whose binary digit corresponding to
4 = 2^2 is 1, and B and C can be described similarly

diagram: only one element in each “region”

Question 4

how to check a code has certain d(C) based on the PCM H?

Answer 4

A linear [n,k]-code over F_q with PCM H has d(C) = d

iff

every set of d − 1 columns of H is LI, but there is a set of d columns of H that is LD.

Question 5

how to check a code has certain d(C) based on the PCM H? if the code is binary

Answer 5

no zero column and no repeated columns in H
implies d(C) ≥ 3

Question 6

Hammings idea

Answer 6

Hamming’s idea was to construct the biggest
possible binary H with no zero columns and no repeated columns.

Fixing a positive integer r, then Z₂ʳ
contains 2r − 1 non-zero
vectors. We could simply use them all!:

Question 7

Def 13.1 Ham(Z₂ʳ)

Answer 7

binary hamming code

Let H be a r × (2^r − 1) matrix whose columns
are the distinct non-zero vectors in Z₂ʳ.

Then Ham(Z₂ʳ) is the
binary linear code whose PCM is H.

Question 8

13.2 example Ham(Z₂ʳ) for r=3

Answer 8

H

binary hamming code

3 x 7
columns are distinct non zero vectors

[0001111
0110011
1010101]

Note columns ordered lexicographically.

Really we think of it as a collection of several different equivalent codes, since we can order the columns as we like.

we could also write H~=
[1110 100]
[1101 010]
[1011 001]
which is in the standard form. Then the generator matrix is
G˜ =
[1000 111]
[0100 110]
[0010 101]
0001 011]

Question 9

thm 13.4
Ham(Z₂ʳ)
distance

Answer 9

Ham(Z₂ʳ) has minimum distance 3 and is perfect.

Question 10

proof 13.4 thm
Ham(Z₂ʳ) has minimum distance 3 and is perfect.

Answer 10

Proof: H has no zero or repeated columns by construction, so d ≥ 3. But it contains columns c₁, c₂, c₃ in lex order obeying c₁ + c₂ + c₃ = 0, so d = 3. Hence Ham(Z₂ʳ) is perfect iff
the collection of 1-balls centred on codewords exhausts Ham(Z₂ⁿ) , where
n = 2ʳ − 1. But
|B₁(x)| = 1 + nC1
= 1 + n = 2ʳ
and
M = |Ham(Z₂ⁿ)| = 2ᵏ
where k = 2ʳ− 1 − r. So

⊔_{x∈Ham(Z₂ⁿ)} of B₁(x)|
= 2ᵏ × 2ʳ = 2ⁿ

Question 10

coset leaders of Ham(Z₂ʳ)

Answer 10

S(eᵢ)= eᵢHᵀ

are all vectors of weight ≤ 1.

weight 1 binary vectors are just the eᵢs.

(0,0,…0,1,0,…0) Hᵀ = cᵢ

columns ordered lexicographically then ith column is the binary representation of i
so if we recieve y in Z₂ⁿ with one error its syndrome S(y) is the digit position of the error in binary

Question 10

13.5. Example.
Ham(Z₂ʳ)

Receive y = 1101101. Then

syndrome decoding with H

Answer 10

S(y) = (1, 1, 0, 1, 1, 0, 1)Hᵀ
= 101
= S(e_5)

e_5= 0000100
Syndrome decoding: x = y − e_5 = 1101001.

Question 10

binary lexicographically representing numbers

Answer 10

000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7