decoding linear codes

Question 1

coset:

Answer 1

given a linear code C and a vector y, the coset of y is the set y+C={y+c|c in C}

Question 2

basic coset facts:

Answer 2

C=0+C is a coset
C is the coset of any codeword c in C
if y,z in F, then either y+C=z+C (if y-z in C) or (y+C)∩(z+C)=∅ (the cosets are either equal or entirely distinct)
there are q^n-k distinct cosets in a space F

Question 3

coset leader:

Answer 3

a vector of minimum weight in y+C, there may be more than one, but all will be the same weight

Question 4

decoder of a linear code:

Answer 4

for a linear code C, any decoder DECODE:F->C satisfies for all y in F, DECODE(y)=y-e where e is a coset leader of the coset y+C of y

Question 5

standard array:

Answer 5

a table for a linear code with the following properties -
the table has |C|=q^k columns and q^n-k rows
each row is a coset
the leftmost entry in each row is a coset leader
the top row is the trivial coset
each entry is the sum of the leftmost entry in its row and the top of its column
the table contains every vector from F exactly once

Question 6

how to construct a standard array:

Answer 6

row 0 - the codevectors in any order, but 0 must be at the start
row 1 - out of the vectors not yet listed, choose a1 of smallest weight, for each other entry add a1 to the top entry in the column
row 2-q^n-k - continue choosing the vectors of lowest weight and adding them to the top of the columns until you have q^n-k rows, after which you stop

Question 7

standard array decoder:

Answer 7

if you have a standard array and are being given vectors - loook up the vector in the standard array, return the topmost vector of the column of y as DECODE(y)

Question 8

is a standard array unique:

Answer 8

nope, several standard arrays can work for some codes, for perfect codes it is unique tho

Question 9

the weight enumerator:

Answer 9

of a linear code C is the polynomial Wc(x,y)=Σx^(n-w(v))y^(w(v))=A0x^n+A1x^(n-1)y^1+…+Any^n, where Ai=#(v in C: w(v)=i}

Question 10

probability of an undetected error:

Answer 10

Pundetect(C)=Wc(1-p,p)-(1-p)^n

Question 11

Pundetect(C) when sent through a BSC(p) channel:

Answer 11

(1-p)^(2)p^2+2(1-p)p^3

Question 12

probability of a corrected error (transmitted via BSC(p)):

Answer 12

Pcorr(C)=(n)Σ(i=0)αi(1-p)^(n-i)p^i where αi denotes the number of cosets where the coset leader has weight i