linear codes Flashcards
linear code:
a subspace of the vector space F^(n)q
codevector:
codewords of a linear code
is the trivial code a linear code:
yes, F^(n)q is a vector subspace of itself
are rep codes a linear code:
yes
weight of a vector:
the weight of a vector v is the number of nonzero symbols in v - w(v)=d(v,0)
weight of a code:
the weight of a code C is w(C)=min{w(v)|v in C{0}}
distance and weight:
d(v,y)=w(v-y)
does minimum distance equal weight:
yep for linear codes, d(C)=w(C)
the zero sum code:
Z={(v1,v2,…vn) in F^(n)q|v1+v2+…+vn=0 in Fq} basically when you add everything together you get 0
binary even weight code:
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
properties of En:
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
the linear code generated by a matrix:
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
properties of a code generated by a matrix:
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
linear codes and codes generated by matrices:
all linear codes can be generated by a matrix
generator matrix:
G=[r1
r2
…
rk], where the row vectors r1,…,rk are a basis of C
matrices that generate a trivial code:
the identity matrix In, also any other nxn matrix with linearly independent rows
matrices that generate repetition codes:
G=[1 1 … 1] of size 1xn, also the matrices λG where λ!=0
matrices that generate E3:
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
storing the generator matrix vs the whole code:
the matrix takes less space, Much less
however
it’s not unique
standard form of a matrix:
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
how to make a matrix the standard form:
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
Alphabet field for linear codes properties:
Fq is an alphabet for a linear code
q=p^m, where p is a prime
