linear codes

Question 1

linear code:

Answer 1

a subspace of the vector space F^(n)q

Question 2

codevector:

Answer 2

codewords of a linear code

Question 3

is the trivial code a linear code:

Answer 3

yes, F^(n)q is a vector subspace of itself

Question 4

are rep codes a linear code:

Answer 4

yes

Question 5

weight of a vector:

Answer 5

the weight of a vector v is the number of nonzero symbols in v - w(v)=d(v,0)

Question 6

weight of a code:

Answer 6

the weight of a code C is w(C)=min{w(v)|v in C{0}}

Question 7

distance and weight:

Answer 7

d(v,y)=w(v-y)

Question 8

does minimum distance equal weight:

Answer 8

yep for linear codes, d(C)=w(C)

Question 9

the zero sum code:

Answer 9

Z={(v1,v2,…vn) in F^(n)q|v1+v2+…+vn=0 in Fq} basically when you add everything together you get 0

Question 10

binary even weight code:

Answer 10

the binary even weight code of length n is En={v in F^(n)2: w(v) is even}, note that this is an alternative way of writing a zero sum code (cause 1+1=0 in a binary alphabet) so is linear

Question 11

properties of En:

Answer 11

d(En)=w(En)=2
we have 2^(n-1) codewords
En is a [n,n-1,2]2 code
cannot correct errors, only detects up to one error

Question 12

the linear code generated by a matrix:

Answer 12

let G be a kxn matrix with linearly independent rows r1,…,rk in F^(n)q. the code C={u1r1+…+ukrk|u1,…,uk in Fq} in F^(n)q is said to be generated by the matrix G. the function ENCODE:F^(k)q->C, ENCODE(u)=uG for all u in F^(k)q is the encoder for C given by the matrix G

Question 13

properties of a code generated by a matrix:

Answer 13

C is a linear code
the function ENCODE is a bijective linear map between F^(k)q and C
the information dimension of C is k and equal to the vector space dimension, dimC

Question 14

linear codes and codes generated by matrices:

Answer 14

all linear codes can be generated by a matrix

Question 15

generator matrix:

Answer 15

G=[r1
r2
…
rk], where the row vectors r1,…,rk are a basis of C

Question 16

matrices that generate a trivial code:

Answer 16

the identity matrix In, also any other nxn matrix with linearly independent rows

Question 17

matrices that generate repetition codes:

Answer 17

G=[1 1 … 1] of size 1xn, also the matrices λG where λ!=0

Question 18

matrices that generate E3:

Answer 18

E3 has 4 codewords, so 2^2, so dimension 2, so the generator matrix has 2 rows and 3 columns
take 2 linearly independent codevectors but not the zero one, and slap one on top of the other, bada bing bada boom

Question 19

storing the generator matrix vs the whole code:

Answer 19

the matrix takes less space, Much less
however
it’s not unique

Question 20

standard form of a matrix:

Answer 20

the left side is an nxn matrix that is the identity matrix, the remaining n-k columns have arbitrary members of Fq, denoted G[Ik|A]
if G is in standard form then, after encoding, the first k symbols are the original message (called information symbols), making it easy to decode, the last n-k are called check symbols, the standard form matrix is unique

Question 21

how to make a matrix the standard form:

Answer 21

you can use permutations of rows, multiplications of rows by a nonzero scalar, and adding a scalar multiple of one row to another, literally just jangle it around

Question 22

Alphabet field for linear codes properties:

Answer 22

Fq is an alphabet for a linear code
q=p^m, where p is a prime