6 Linear codes Flashcards
span of {v_i}
The set of all vectors expressible as linear combinations of {v_i} is a
subspace called the span of {vi}. We say that {v_i} is spanning for
a vector space V is its span is V.
subspace
A subspace of a vector space V over F is a subset of V containing the zero vector which is closed under scalar multiplication and addition. A subspace is itself a vector space over F.
linearly independent
A set of vectors is linearly independent if the only
way to linearly combine them to 0 is with all coefficients 0.
Any linearly independent set can be extended to a basis and any
spanning set contains a basis
basis
A linearly independent spanning set for a vector space is called a basis.
So if a vector space V has a basis
B = {v1, v2, …, v_k }, then every
vector in V can be uniquely expressed as a linear combination of the v_i
Moreover, if F is finite, then so is V and we have
|V| = |F|ᵏ
dimension
The number k is independent of the chosen basis and we call it the dimension of V
|V| = |F|ᵏ
for finite F
Examples
basis for F_qⁿ
basis for F_qⁿ:
has a basis {100..00, 010..00, …, 000..01}
consisting of n vectors.
Example basis for
V = {000, 001, 010, 011}
V = {000, 001, 010, 011} is a subspace of Z₂³ with basis
{001, 010}.
Example:
V = {000, 001, 002, 010, 020, 011, 022}
its not a subspace of Z₃³
its size is not a power of 3
attempt at a basis
001
010
remove 001 and 020, 002 and 010
V = {000, 011, 022}
size must always be a power of p
p=3 here
contains 0 vector, closed under scalar multiplication and addition? no as no 012, 021 so not a subspace
|V|=|F|^2 = 6
remove 010 and 002 as they add to this
Z₃³
{000, 001,002,010,011,012,020,021, 022,101,102,110,111,112,120,121,122,200,201,202,210,211,212,220,221,222}
3^3= 27
6.3. Proposition
characteristic p
Let F be a finite field of characteristic p. Then F is itself a vector space over Z_p.
Proof: Exercise.
Note that this implies that |F| must be a power of p.
Linear code definition
We say that code C ⊂ F ⁿ is a linear code if it is a linear subspace of Fⁿ, i.e.
it contains the zero vector and it is closed under addition and scalar multiplication.
Is C= {000, 001, 010, 011} a subspace of Z₂³?
V=Z₂³ = {000, 001, 010, 011, 100, 101, 110, 111}
zero vector
closed under + *scalars
size is a power of 2
If C, C’ ⊂ Fⁿ linear codes then is
C ∩ C′
linear?
LINEAR
0
closed under addition
If C, C’ ⊂ Fⁿ linear codes then is
C U C′
linear?
only in certain cases,
require to be closed under + and scalar multiplication
..,…
If C, C’ ⊂ Fⁿ linear codes then is
C + C′
linear?
C + C′:= {u + u′| u ∈ C, u′ ∈ C′}
LINEAR
closed under addition
linear [n, k]-code
When C ⊂ Fⁿ is linear, and of dimension k as a vector space, then
M = |C| = |F|ᵏ.
We call C a linear [n, k]-code.
rate of a code
The rate of a code is
R = R(C) =[log_q M]/n≤ 1
so for a linear code
R = k/n
Thus the bigger k is, the more information we transmit; the bigger n is, the longer it takes to transmit. But of course the bigger n − k is the more checking we are doing, so the better we can confirm or protect the information
repetitition code linear?
If S = F is a field then the repetition code Rn ⊂ F^n
is linear of dimension
- Example: 11…1 + 11…1 = 22…2.
e.g length n encoding (x_1) to (x_1,…x_1) n times
(x_1)[1…1]= (x_1,…x_1)
Parity check code
The parity-check code Pₙ ⊂ Fⁿ
consists of all vectors u such that
Σᵢ uᵢ = 0
We can consider the first n − 1 digits as information, and un as a
check digit, simply defined as
uₙ= − Σᵢ uᵢ from i=0 to n-1
Since it is defined by a linear equation this code is linear. It is a
[n, n − 1]-code, so M = qⁿ⁻¹ and R = (n − 1)/n
def 6.9 A q-ary [n, k, d]-code
A q-ary [n, k, d]-code is a linear code in F_q ⁿ of dim k and minimum distance d.
Write [n, k, d] − cod for the set of all such
Thus C ∈ [n, k, d] − cod implies C ∈ (n, qᵏ, d) − cod, but the
converse is false
examples of binary linear codes:
Our first three examples are all binary linear
codes: C_1 ∈ [2, 2, 1] − cod;
C_2 ∈ [3, 2, 2] − cod;
C_3 ∈ [5, 2, 3] − cod.
Exercise: check this.
finding min distance d(C) for a linear code
we would usually need 0.5|C|(|C|-1) calcs but…
d(x,y)=w(x-y) thus for a linear code we can use the minimum weight!!
thm 6.11 linear code finding d(C)
For a linear code let w(C) = min{w(x) | x ∈ C \ {0}}
(here we write 0 for the appropriate 000..0 sequence, for convenience). Then
w(C) = d(C).
Specifying a linear code
For linear codes we usually just give a basis rather than listing out
the whole thing.
