parameters and bounds Flashcards
q:
the size of the alphabet
n:
the length of the code, each codeword consists of n symbols
M:
the number of codewords
k:
log(q)(M), the information dimension
d:
d(C)=min{d(v,w): v,w in C, v!=w} - minimum distance of C
R:
k/n, the rate of C
δ:
d/n, the relative distance of C
ways to write a code:
(n,M,d)q or [n,k,d]q
t:
[(d-1)/2]
how many errors does a given code detect/correct:
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)
do we want a high or low rate:
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)
the trivial bound:
if [n,k,d]q codes exist, then k<=n and d<=n
the trivial code:
the trivial code of length n over an alphabet F is C=F^n
Rep(n,F):
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
the binomial coefficient:
(n
i)
n!/(n-i)!i!
henceforth written (ni) cause mannnn
the hamming bound:
M<=q^n/(t)Σ(i=0)(ni)(q-1)^i
the hamming sphere:
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}
cardinality of a hamming sphere:
Sr(y)=(r)Σ(i=0)(ni)(q-1)^i
perfect code:
a code that attains the hamming bound (so M=all that shit)
the singleton bound:
k<=n-d+1
MDS code:
maximum distance separable code, a code that attains the singleton bound (so k=n-d+1)
do these bounds work in reverse:
NO, just cause a hypothetical code fits the bounds doesn’t mean it exists, maybe it breaks bounds we haven’t learnt yet
