10 Dual codes

Question 1

inner product

Answer 1

Recall the inner (or scalar) product u.v = uvᵀ of two (row) vectors.
Z₂⁴ : 1001.1101=1+0+0+1=0.

Question 2

defn 10.2 dual code

Answer 2

Given C ⊂ F^n _q , its dual code is
C⊥
= {u ∈ F^n _q | u.v = 0 ∀ v ∈ C}
orthogonal code

Question 3

Lemma 10.3 dual code

Answer 3

If C generated by G then v ∈ C⊥ ⇐⇒ vGᵀ = 0.

Question 4

range/ image of L
If U, V are vector spaces over F_q and
L : U → V is a linear map,

Answer 4

L(U) = {L(x)| x ∈ U} ⊂ V ,
is a subspace of V

Question 5

rank of L
If U, V are vector spaces over F_q and
L : U → V is a linear map,

Answer 5

dimension of the range of L

range of L is a subspace of v

Question 6

kernal of L
If U, V are vector spaces over F_q and
L : U → V is a linear map,

Answer 6

The set of vectors
ker L = {u ∈ U | L(u) = 0} ⊂ U
is a subspace of U, called the kernel of U.

Question 7

nullity of L
If U, V are vector spaces over F_q and
L : U → V is a linear map,

Answer 7

The dimension of the
kernel is called the nullity of L. We have

Question 8

The Rank-Nullity Theorem

Answer 8

rank L + dim(ker L) = dim U

Question 9

linear map from matrix

Answer 9

Let F be a field (e.g. F_q)
each n x k matrix A with entries in F defines two maps

L_A : v → vA : Fⁿ→ Fᵏ (row vectors)

Lᴬ: v → Av : Fᵏ→ Fⁿ (column vectors)
consider now in futre only L_A and row vectors

Linear because:
for α, β ∈ F we have (αv + βw)A = αvA + βwA.

If we consider the standard ordered basis for F^n then its image under L_A is the set of row vectors in A.

Question 10

10.4 lemma rank dimension for linear map

Answer 10

The rank of LA, i.e. the dimension of
L_A(Fⁿ), is the same as the rank of A.

row rank of A is the dimension of the row span and the column rank is that of the column span
these are equal to the #leading ones/pivots in REF of A
Rank of A
ranks for transpose=

Question 11

10.5. Example. Let’s try a matrix with rank 1:

Answer 11

(x y ) (1 1)
(1 1)

= (x+y x+y)

Clearly the image space has dim=1 (albeit embedded in a 2d
space).

Question 12

(Av)^T=

Answer 12

v^T A^T

Question 13

Thm 10.6 considering map existence of code
dual

Answer 13

If C an [n, k]-code over F_q

(i.e. an [n, k, d]-code for some d), then

C⊥ is an [n, n − k]-code over Fq.

Question 14

thm 10.6 proof:
If C an [n, k]-code over F_q

(i.e. an [n, k, d]-code for some d), then

C⊥ is an [n, n − k]-code over Fq.

Answer 14

Let G be a generator matrix for C, and consider the map
L = L_{Gᵀ} : v → vGᵀ: Fⁿ_q → Fᵏ_q

(note that G has k rows and n columns, so Gᵀ has n rows and k columns).
Then C⊥ = ker L by Lemma 10.3.
Thus C⊥ is linear.

Now, by the Rank-Nullity Theorem,
dim(ker L) = dim Fⁿ_q − rank L = n − rank L

But, by the previous lemma, rank L = rank(Gᵀ ) = rank(G) = k, since a generator matrix has full rank by definition. So
dim (C⊥) = n − k.

Question 15

Example 10.7
C = {000, 110, 011, 101}
dimension
over Z_2

what is dimension of C⊥

Answer 15

over Z_2 has dimension 2

by thm 10.6 C⊥ dimension 3-2=1

Question 16

Example 10.7
C = {000, 110, 011, 101}
G=

Answer 16

110
011

Question 17

Example 10.7
C = {000, 110, 011, 101}

give
C⊥

Answer 17

G=
[110
011]

v ∈ C⊥ iff

(v1, v2, v3)G
T = (v1 + v2, v2 + v3) = (0, 0)
Over Z_2 this holds iff v1 = v2 = v3.

Thus C⊥ = {000, 111}.

Question 18

THM 10.8

Answer 18

For all linear codes (C⊥)⊥ = C.

proof: f: It is easy to see that C ⊆ (C⊥)⊥. Now compare dimensions.

Question 19

Def 10.9 PCM

Answer 19

Any generator matrix H for C⊥ is called a
Parity Check Matrix (PCM) for C

Question 20

parity check equations

Answer 20

the n − k rows of H give the coefficients in n − k
linear equations which x must satisfy to be a codeword:

h₁₁x₁ + h₁₂x₂ + … + h₁ₙxₙ = 0

and so on.

(relates to thinking of C as the kernel of a linear map given by xH^T)

Question 21

def 10.10 redudancy

Answer 21

The redundancy of a linear code is r = n − k,
the number of extra digits added compared to the messageword. Usually r < k (fewer check digits than message digits), so H is
smaller than G and the PCM is a more efficient way to define C than G is.

Question 22

THM 10.11
G linking to PCM H

Answer 22

Let C be a [n, k]-code over F_q generated by
G = [Iₖ |A]

where A is a k × (n − k) matrix

(i.e. G is in standard form).
Then H = [−A^t|1ₙ−ₖ ] is PCM for C

Question 23

10.12. Example. 3-ary [6,4]-code generated by
G =
[1 0 0 0 1 1
0 1 0 0 0 2
0 0 1 0 2 1
0 0 0 1 2 2]
has PCM

Answer 23

H=
[2 0 1 1 1 0]
[2 1 2 1 0 1]

G was 4 x 6
H will be (2 x 6)
B will be (2 x 4)

Question 24

10.13 defn PCM H Standard form

Answer 24

A PCM H is in standard form if
H = [B|1ₙ - ₖ ]
where B is a
(n − k) × k matrix.

PCM is an (n-k) x n matrix

So, by the previous theorem, every linear code is equivalent to one whose PCM is in standard form.