Communication Chapter 6 defs and theorems Flashcards
Linear [n,k]-code
A linear [n,k]-code is a subspace of 𝔽ⁿ₂ of dimension k.
length of linear [n,k]-code
n
dimension/rank of linear [n,k]-code
k
Lemma 6.2. Hamming distance and weight.
For any x,y∈𝔽ⁿ₂ we have that dₕ(x,y)=w(x+y)
Proposition 6.5. minimum hamming distance and minumum weight
.
If C is a linear code then the minimum hamming distance of C is the minimum weight of a codeword c∈C
basis of a subspace
A basis of a subspace C⊆𝔽ⁿ₂ is a collection of vectors c₁,..,cₖ s.t.
(1) They are linearly independent
(2) They span C
basis of a linear [n,k]-code
A basis of a linear [n,k]-code c is a set of k vectors c₁,…,cₖ∈C s.t. for all c∈C there exists λ₁,…,λₖ∈𝔽₂ s.t. c = λ₁c₁+…+λₖcₖ.
lemma 6.7. Size of a linear code.
Every linear [n,k]-code C satisfies |C|=2ᵏ.
generator matrix
Let C be a linear [n,k]-code and {c₁,…,cₖ} be an ordered basis of C. The associated generator matrix of C is a kxn matrix where rows correspond to c₁,…,cₖ.
normal form
Given a linear [n,k]-code C a generator matrix B is in normal form if it is in the form B = (Iₖ|A) where Iₖ is the kxk identity matrix.
equivilent
Two codes C₁ and C₂ are equivilent if there exists a generator matrix B₁ of C₁ and B₂ of C₂ s.t. B₁ can be obtained from B₂ by a permutation of the columns.
Theorem 6.14. equivilent codes with normal form.
For every linear [n,k]-code C there exists an equivilent linear [n,k]-code C₀ that has a normal form.
Parity check matrix
Let C be a linear [n,k]-code. A parity check matrix H of C is an (n-k)xn matrix such that C={c∈𝔽ⁿ₂: Hcᵀ = 0}
Theorem 6.16. The parity check matrix from generator matrix.
Let C be a linear [n,k]-code and suppose C has normal form B₀=(Iₖ|A). Then H=(Aᵀ|Iₙ₋ₖ).
Theorem 6.18. minimum hamming distance from parity check matrix.
Let C be a linear [n,k]-code with parity check matrix H. If r is the smallest integer for which there exists r linearly dependent columns in H, then dₕ(c)=r
Hamming code of order r
Let r∈ℕ. The hamming code of order r is a linear code whose parity check matrix H has as its columns all 2ʳ-1 non-zero vectors of length r
proposition 6.21. properties of hamming code of order r.
The hamming code of order r is a linear [n,k]-code C with
(i) n = 2ʳ-1 (length of codewords) k= 2ʳ-r-1 (dimension of codewords)
(ii) |C|=2²ʳ⁻ʳ⁻¹ and R(C) = 1 - r/(2ʳ-1)
(iii) dₕ(c)=3
proposition 6.22. decoding hamming codes.
Let C be the hamming code of order r with parity check matrix H. For every x∈𝔽ⁿ₂ there exists a unique c∈C such that dₕ(x,c)≤1.
Moreover, if x is not in C and i is the position where x and c differ then Hxᵀ=hᵢ where hᵢ is the ith column of H
Hamming decoding scheme for x∈𝔽ⁿ₂
- calculate s=Hxᵀ
- Decode it
(a) is s=0 then x∈C so return x
(b) if s≠0 then x is not in C and by prop 6.22 there exists i such that s=hᵢ so return x+eᵢ
coset
Let C be a linear [n,k]-code with parity check matrix H. Then for any vector s∈𝔽ⁿ⁻ᵏ₂ we let the coset of s be defined as follows:
Q(s) := {x∈𝔽ⁿ₂: Hxᵀ =s}
syndrome of x
If x∈Q(s), then we say s is the syndrome of x
Equipartition
disjoint sets of the same size
coset leader
For every s∈𝔽ⁿ⁻ᵏ₂ a coset leader q(s) is a vector in Q(s) with smallest weight. That is q(s)∈Q(s) satisfies w(q(s)) = min w(x) for all x∈Q(s).
Theorem 6.27. Minimum Distance Decoding via a coset leader.
Let C be a linear [n,k]-code. If x∈Q(s) and q(s) is a coset leader of Q(s) then c=x+q(s)∈C and c is the nearest codeword to x.
Syndrome Decoding Scheme for x∈𝔽ⁿ₂
- Calculate the syndrome of x, Hxᵀ =s
- Choose a coset leader q(s) of Q(s)
- Decode x as x+q(s)
Theorem 6.29. Gilbert-Var Shamov bound.
Let 2≤d≤n and let k be the largest integer that satisfies 2ᵏ<2ⁿ/bⁿₔ₋₁. Then, A(n,d)≥2ᵏ.
