defs 5

Question 1

inner product

Answer 1

For u, v ∈ F^n_q the scalar (element of Fq) defined as
u · v = SUM^n_i=1 uivi
is called the inner product of the vectors u and v

Question 2

dual code

Answer 2

Given a code C ⊆ F^n_q, we define the dual code
C⊥ as C⊥ = {v ∈ F^n_q | v · C = {0}}.

We can say that C⊥ consists of all vectors orthogonal to the code C (where v orthogonal to C means v · C = {0})

Question 3

C⊥ has generator matrix

Answer 3

H = [ −A^T| I_n−k ]

Question 4

Check matrix

Answer 4

A check matrix for a linear code C means a generator

matrix for C⊥

Question 5

linearly equivalent codes

Answer 5

Two linear codes C, C’ ⊆ F^n_q are linearly equivalent, if C’ can be obtained from C by a sequence of linear transformations of the following types:

(C1) choose indices i, j; in every codeword, swap symbols xi and xj ;
(C2) choose index i and non-zero λ ∈ Fq; in every codeword, multiply xi by λ

Question 6

syndrome of y

syndrome map

Answer 6

Let H be a check matrix for a linear code C ⊆ F^n_q. Let y ∈ F^n_q
The vector S(y) = yH^T
is called the syndrome of y. The linear map
S : F^n_q → F^n−k_q
is the syndrome map.

Question 7

syndrome decoder algorithm

Answer 7

Preparation: Construct a table of syndromes, with q^n−k rows, of the form

Coset leader ai | S(ai)

The top row contains the codeword 0 and its syndrome S(0) = 0.
At each step, choose a vector ai ∈ F^n_q of smallest weight such that S(ai) does not appear in the table; then ai is a coset leader of a new coset.

Decoding:
• Receive a vector y ∈ F^n_q
• Calculate S(y) = yHT
• In the table, find ai with S(ai) = S(y). Then ai is the coset leader of the coset of y
• Return DECODE(y) = y − ai

Question 8

Mac williams identity

Answer 8

If C is a q-ary linear code,

WC⊥ (x, y) = 1/#C WC(x + (q − 1)y, x − y)