6 Linear codes

Question 1

span of {v_i}

Answer 1

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.

Question 2

subspace

Answer 2

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.

Question 3

linearly independent

Answer 3

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

Question 4

basis

Answer 4

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|ᵏ

Question 5

dimension

Answer 5

The number k is independent of the chosen basis and we call it the dimension of V

|V| = |F|ᵏ
for finite F

Question 6

Examples
basis for F_qⁿ

Answer 6

basis for F_qⁿ:
has a basis {100..00, 010..00, …, 000..01}
consisting of n vectors.

Question 7

Example basis for
V = {000, 001, 010, 011}

Answer 7

V = {000, 001, 010, 011} is a subspace of Z₂³ with basis
{001, 010}.

Question 8

Example:
V = {000, 001, 002, 010, 020, 011, 022}

Answer 8

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

Question 9

Z₃³

Answer 9

{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

Question 10

6.3. Proposition
characteristic p

Answer 10

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.

Question 11

Linear code definition

Answer 11

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.

Question 12

Is C= {000, 001, 010, 011} a subspace of Z₂³?

Answer 12

V=Z₂³ = {000, 001, 010, 011, 100, 101, 110, 111}
zero vector
closed under + *scalars
size is a power of 2

Question 13

If C, C’ ⊂ Fⁿ linear codes then is
C ∩ C′
linear?

Answer 13

LINEAR
0
closed under addition

Question 14

If C, C’ ⊂ Fⁿ linear codes then is
C U C′
linear?

Answer 14

only in certain cases,
require to be closed under + and scalar multiplication
..,…

Question 15

If C, C’ ⊂ Fⁿ linear codes then is
C + C′
linear?

Answer 15

C + C′:= {u + u′| u ∈ C, u′ ∈ C′}
LINEAR
closed under addition

Question 16

linear [n, k]-code

Answer 16

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.

Question 17

rate of a code

Answer 17

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

Question 18

repetitition code linear?

Answer 18

If S = F is a field then the repetition code Rn ⊂ F^n
is linear of dimension

1. 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)

Question 19

Parity check code

Answer 19

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

Question 20

def 6.9 A q-ary [n, k, d]-code

Answer 20

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

Question 21

examples of binary linear codes:

Answer 21

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.

Question 22

finding min distance d(C) for a linear code

we would usually need 0.5|C|(|C|-1) calcs but…

Answer 22

d(x,y)=w(x-y) thus for a linear code we can use the minimum weight!!

Question 23

thm 6.11 linear code finding d(C)

Answer 23

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).

Question 24

Specifying a linear code

Answer 24

For linear codes we usually just give a basis rather than listing out
the whole thing.

Question 25

generator matrix

Answer 25

A k × n matrix is called a generator matrix for C if its rows form a basis for C

Question 26

Generator matrix for
C_3 ={00000,01101,10110,11011}

what is d(C)?

Answer 26

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!

Question 27

thm 6.14 what operations can we do to generator matrix

Answer 27

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.

Question 28

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)

Answer 28

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

Question 29

THM 6.16 column operations on G

Answer 29

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”)

Question 30

standard form of G

Answer 30

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

Question 31

A binary [5,3,d]-code is generated by
[11111
10101
11100]
give in standard form

Answer 31

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.

Question 32

REF

Answer 32

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

Question 33

RREF

Answer 33

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

Question 34

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?

Answer 34

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)