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.
generator matrix
A k × n matrix is called a generator matrix for C if its rows form a basis for C
Generator matrix for
C_3 ={00000,01101,10110,11011}
what is d(C)?
binary
G=
[01101]
[10110]
rows form a basis
linear combos of rows give all the combos
note its multiples of the rows, all combos of these
could also do (ab)G with ab 0 or 1 combos
d(C)?
min weight is 3, d(C)=1!
thm 6.14 what operations can we do to generator matrix
Let G generate C. Any matrix obtained from G
by
(R1) permuting rows
(R2) multiplying a row by a non-zero scalar
(R3) adding one row to another
generates the same code.
6.15. Example. Show that the 3-ary linear codes generated by
G =
[210222]
[012101]
[011112]
G′ =
[100201]
[010120]
[001022]
generate the same code.
Deduce d(C)
Row operations
d(C) ≤ 3, since there is a weight 3 row in G′
3 by 6 matrix k=6 |C|= 3^6 large to find each
THM 6.16 column operations on G
Let C be a linear code generated by G. Let G′ be obtained from G by
(C1) permuting columns
(C2) multiplying a column by a non-zero scalar a ∈ Fq.
Then G′ generates C′
an equivalent linear code to C.
Proof: This amounts to specialising operation (2) in Definition 4.19 to multiplication by a nonzero scalar (we could call this “linear equivalence”)
standard form of G
By using all the row operations and column operations (C1) you can always reduce G to the standard form
G’=
[Iₖ|A]
A has entries in F_q
A binary [5,3,d]-code is generated by
[11111
10101
11100]
give in standard form
row operations to:
[10101]
[01001]
[00011]
which is in RREF.
Now we have to pass to a “linearly equivalent”
code by swapping the 3rd and 4th column to get a generator matrix in standard form.
REF
A matrix is in row echelon form if
All rows having only zero entries are at the bottom.[1]
The leading entry (that is, the left-most nonzero entry) of every nonzero row, called the pivot, is on the right of the leading entry of every row above
RREF
A matrix is in reduced row echelon form (also called row canonical form) if it satisfies the following conditions:
It is in row echelon form.
The leading entry in each nonzero row is 1 (called a leading one).
Each column containing a leading 1 has zeros in all its other entries.
The last condition is equivalent to:
Each column containing a leading 1 has zeros in all entries above the leading 1
6.18. Exercise. Let Ci be the 3-ary code generated by G_i, where
G1 =
[1011]
[0112]
G2 =
[1011]
[0111]
List Ci and hence compute d(Ci). Is Ci perfect?
3 ary
C_1={0000,1011,0112,1120,2022,0221,2210,1202,2101}
d(C_1)=w(C_1)= min(w(x ∈ C_1*))= 3
to check if perfect compare with t=1 balls, total space occupied by M=9 balls is 9x9 (1 differ by 0, 8 differ by 1)
perfect code can’t have even distance
|3^4|=81 equality in BPB so perfect
C_2={0000,1011,0111,1122,2022,0222,1200,2100,2211}
w(C) is at most 2
also both rows as vectors have sum of entries 0, so all combinations will have some 0. so only way to get a codeword with form 00*0, say, (w(x) ≤ 1) is with ∗ = 0. Thus w(C) = 2. Thus d(C) = 2
C_2 is not perfect
(since t is smaller than for C1, which has the same M and ‘universe’) (or on general grounds, since d even)
