parameters and bounds

Question 1

q:

Answer 1

the size of the alphabet

Question 2

n:

Answer 2

the length of the code, each codeword consists of n symbols

Question 3

M:

Answer 3

the number of codewords

Question 4

k:

Answer 4

log(q)(M), the information dimension

Question 5

d:

Answer 5

d(C)=min{d(v,w): v,w in C, v!=w} - minimum distance of C

Question 6

R:

Answer 6

k/n, the rate of C

Question 7

δ:

Answer 7

d/n, the relative distance of C

Question 8

ways to write a code:

Answer 8

(n,M,d)q or [n,k,d]q

Question 9

t:

Answer 9

[(d-1)/2]

Question 10

how many errors does a given code detect/correct:

Answer 10

if 1<=d(v,y)<=d-1, then y isn’t in C, so if at most d-1 errors occur, they will all be detected, so a code detects up to d-1 errors
if d(v,y)<=t, then y has a unique nearest neighbour in C, which is v, so if at most t errors occur, they can all be corrected, so the code corrects up to t errors ((d-1)/2)

Question 11

do we want a high or low rate:

Answer 11

high, closer to 1 is better, the closer to 1, the more efficient the code is (least symbols have to be sent to convey the info)

Question 12

the trivial bound:

Answer 12

if [n,k,d]q codes exist, then k<=n and d<=n

Question 13

the trivial code:

Answer 13

the trivial code of length n over an alphabet F is C=F^n

Question 14

Rep(n,F):

Answer 14

the repetition code of length n over the alphabet F, Rep(n,F)={aaa…a|a in F} in F^n, all codewords are formed by repeating the symbol n times

Question 15

the binomial coefficient:

Answer 15

(n
i)
n!/(n-i)!i!
henceforth written (ni) cause mannnn

Question 16

the hamming bound:

Answer 16

M<=q^n/(t)Σ(i=0)(ni)(q-1)^i

Question 17

the hamming sphere:

Answer 17

if y in F^n and r<=n, the hamming sphere with centre y and radius r is the set Sr(y)={v in F^n: d(v,y)<=r}

Question 18

cardinality of a hamming sphere:

Answer 18

Sr(y)=(r)Σ(i=0)(ni)(q-1)^i

Question 19

perfect code:

Answer 19

a code that attains the hamming bound (so M=all that shit)

Question 20

the singleton bound:

Answer 20

k<=n-d+1

Question 21

MDS code:

Answer 21

maximum distance separable code, a code that attains the singleton bound (so k=n-d+1)

Question 22

do these bounds work in reverse:

Answer 22

NO, just cause a hypothetical code fits the bounds doesn’t mean it exists, maybe it breaks bounds we haven’t learnt yet