hamming codes

Question 1

check matrix construction:

Answer 1

assume C has a kxn generator matrix G=[I|A] in standard form. then the dual code C^⊥ has generator matrix H=[-A^T|I(n-k)]

Question 2

linearly equivalent codes:

Answer 2

two codes C and C’ are linearly equivalent if C’ can be obtained from C by a sequence of the following linear transformations:
choose indices i,j - in every codeword, swap xi and xj
choose index i and nonzero λ, in every codeword multiply xi by λ

Question 3

distance theorem for linear codes:

Answer 3

let C be a linear code with check matrix H. d(C)=d iff every set of d-1 columns of H is linearly independent and some set of d columns of H is linearly dependent

Question 4

line:

Answer 4

a 1-dimensional subspace of of the vector space Fq^n

Question 5

representative vector:

Answer 5

a representative vector of a line is a nonzero vector u from that line, which is given by {λu|λ in Fq}

Question 6

projective space:

Answer 6

P(n-1)(Fq), the set of all lines in Fq^n

Question 7

hamming codes:

Answer 7

r>=2 is given, Ham(r,q) denotes a linear code whose check matrix has columns which are representatives of the lines in P(r-1)(Fq), exactly one representative vector from each line

Question 8

properties of hamming codes:

Answer 8

Ham(r,q) are perfect [n,k,d]q codes where n=(q^(r)-1)/(q-1), k=n-r, d=3

Question 9

decoding algorithm for a hamming code:

Answer 9

let a hamming code be given by its check matrix H, and suppose a vector y is received. calculate S(y)=yH^T. if S(y)=0, DECODE(y)=y. Otherwise, S(y)=λ(some column of H), let this be the i-th column. subtract λ from the i-th position in y, the result is the codevector DECODE(y)

Question 10

properties of a hamming decoder:

Answer 10

every coset leader of Ham(r,q) is 0 or λe, a vector of weight 0 or 1
the decoder changes at most 1 symbol in the received vector