10 Dual codes Flashcards
inner product
Recall the inner (or scalar) product u.v = uvᵀ of two (row) vectors.
Z₂⁴ : 1001.1101=1+0+0+1=0.
defn 10.2 dual code
Given C ⊂ F^n _q , its dual code is
C⊥
= {u ∈ F^n _q | u.v = 0 ∀ v ∈ C}
orthogonal code
Lemma 10.3 dual code
If C generated by G then v ∈ C⊥ ⇐⇒ vGᵀ = 0.
range/ image of L
If U, V are vector spaces over F_q and
L : U → V is a linear map,
L(U) = {L(x)| x ∈ U} ⊂ V ,
is a subspace of V
rank of L
If U, V are vector spaces over F_q and
L : U → V is a linear map,
dimension of the range of L
range of L is a subspace of v
kernal of L
If U, V are vector spaces over F_q and
L : U → V is a linear map,
The set of vectors
ker L = {u ∈ U | L(u) = 0} ⊂ U
is a subspace of U, called the kernel of U.
nullity of L
If U, V are vector spaces over F_q and
L : U → V is a linear map,
The dimension of the
kernel is called the nullity of L. We have
The Rank-Nullity Theorem
rank L + dim(ker L) = dim U
linear map from matrix
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.
10.4 lemma rank dimension for linear map
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=
10.5. Example. Let’s try a matrix with rank 1:
(x y ) (1 1)
(1 1)
= (x+y x+y)
Clearly the image space has dim=1 (albeit embedded in a 2d
space).
(Av)^T=
v^T A^T
Thm 10.6 considering map existence of code
dual
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.
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.
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.
Example 10.7
C = {000, 110, 011, 101}
dimension
over Z_2
what is dimension of C⊥
over Z_2 has dimension 2
by thm 10.6 C⊥ dimension 3-2=1
Example 10.7
C = {000, 110, 011, 101}
G=
110
011
Example 10.7
C = {000, 110, 011, 101}
give
C⊥
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}.
THM 10.8
For all linear codes (C⊥)⊥ = C.
proof: f: It is easy to see that C ⊆ (C⊥)⊥. Now compare dimensions.
Def 10.9 PCM
Any generator matrix H for C⊥ is called a
Parity Check Matrix (PCM) for C
parity check equations
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)
def 10.10 redudancy
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.
THM 10.11
G linking to PCM H
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
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
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)
10.13 defn PCM H Standard form
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.
