the dual code and syndrome decoding

Question 1

inner product:

Answer 1

u.v=(n)Σ(i=1)uivi (multiply each nth digit and add all the results together)

Question 2

properties of the inner product:

Answer 2

u.v=uv^T (just v is transposed)
u.v=v. (symmetric)
(u+λw).v=u.v+λ(w.v) (bilinear)
u.F={0} iff u=0 (non-degeneracy)

Question 3

dual code:

Answer 3

C⊥={v in F|v.C={0}}
consist of all vectors orthogonal to the code C (v orthogonal to C means v.C={0})

Question 4

check matrix:

Answer 4

a check matrix for a linear code C is a generator matrix for C⊥, aka parity check matrix

Question 5

properties of dual code and check matrix:

Answer 5

if C is a linear code of dimension k, then dimC⊥=n-k and C={v in F: vH^T=0} for any check matrix H of C

Question 6

syndrome:

Answer 6

let H be a check matrix for a linear code C. the vector S(y)=yH^T is called the syndrome of y

Question 7

syndrome map:

Answer 7

the linear map S:Fnq->F(n-k)q

Question 8

syndromes of vectors in the same coset:

Answer 8

S(v)=S(y) <=>v,y are in the same coset of C
S(v)=0 <=> v in C

Question 9

the syndrome decoder:

Answer 9

construct a table of syndromes with q^(n-k) rows of the form | coset leader ai | S(ai) |
start with the top row, 0 in the left column and S(0)=0 in the right
for each subsequent row choose a vector of smallest weight that hasn’t already appeared, this is the coset leader of the new coset
to decode, receive a vector y, calculate S(y)=yH^T, find ai with S(ai)=S(y), return DECODE(y)=y-ai