4 Optimisation Flashcards
Why optimise?
f_3
length vs error detecting
f3 is more reliable than f1 when transmitting over a channel with errors. But in replacing by sequences 2.5 times as long we are giving it far more digits to get wrong! Is f3 really more reliable? Less reliable? Does
it really make any difference?
working out the probabilities for messages to be wrongly decoded
if p = 0.01 then Perr(01) = .0199 while Perr(01101) ≤ .0009801496. So
increasing word length by 2.5 times reduced error probability
20-fold!
If p is bigger then f1 doesn’t look so bad (for example at around
p = .4 and above it is better than f3).
q-ary symmetric channel with symbol error probability p
Each digit transmitted is corrupted with probability p
If a digit is corrupted, any of the q − 1 other letters in S are
equally likely to occur
e.g. {0,1,2,3}
transmitted ?
corrupted with probability p
received =2 say,
P( 2 is an error) =p
P(2 is transmitted and 1 is received) = p/(q-1) = p/3?
q-ary symmetric channel with symbol error probability p:
Probability of exactly r errors
(binary)
nCr pʳ (1-p)ⁿ⁻ʳ
considers each each position the error could be in. Because ≤t errors can be corrected
for binary
Pₑᵣᵣ ≤ 1 - Σ(nCr pʳ (1-p)ⁿ⁻ʳ) r=0,…t
P꜀ₒᵣᵣ≥ Σ(nCr pʳ (1-p)ⁿ⁻ʳ) r=0,…t
Upper bound for Pₑᵣᵣ as
P꜀ₒᵣᵣ lower bound as
correctly decodes if errors are less than or the same as t , could be decoded correctly otherwise too
example Binary (9,5,6) code p=0.001 error probability
d=5 t=2 errors can be corrected
sum for 0,1,2 errors
Σ(9Cr pʳ (1-p)ⁿ⁻ʳ) r=0,1,2
= 0.9999197
P꜀ₒᵣᵣ≥0.9999197
Pₑᵣᵣ ≤ 0.0000803
q-ary symmetric channel with symbol error probability p:
Probability of exactly r errors
(for non-binary)
we have (p/(q-1))~ probability of error for each digit in q-ary alphabet
Def 4.1
A q-ary (n, M, d)-code
A q-ary (n, M, d)-code is a q-ary code with block length n, M codewords and minimum distance d
P(S)
P(Sⁿ)
P(S) Power set of S
P(Sⁿ) set of length-n |S|-ary codes
a q-ary (n, M, d)-code C is an
element of P(Sⁿ) (some S of size q) such that |C| = M and
d(C) = d.
(n, M, d)-cod_q
the set of q-ary (n, M, d)-codes (or just (n, M, d)-cod if q is fixed). Thus:
P(Sⁿ)
= ⊔_M,d (n, M, d)-cod
How is the size of codewords related to n and q and d?
Note that C ⊆ Sⁿ
implies |C| ≤ qⁿ
If we pick t maximal with 2t + 1 ≤ d, i.e. t = ⌊(d − 1)/2⌋, then
the balls Bt(x) ⊆ Sⁿ x ∈ C, are disjoint.
So the bigger d = d(C) is, the bigger this t is and the smaller the
number of balls |C| can be.
define A_q(n,d)
Max M
for fixed q,n,d
the size of the largest possible q-ary code of block length n
and minimum distance d.
THM 4.2 Singleton bound
For any q-ary (n, M, d)-code,
M ≤ qⁿ⁻⁽ᵈ⁻¹⁾.
Hence A_q(n, d) ≤ qⁿ⁻⁽ᵈ⁻¹⁾
proof: (for length n qⁿ is max #sequences/codewords block length n in q-ary. For c in C delete the first d-1 letters and thus min distance=1. So we have qⁿ⁻⁽ᵈ⁻¹⁾ possibilities)
For C with code alphabet S and define π : C → Sⁿ⁻⁽ᵈ⁻¹⁾ be the map
π : (x₁, x₂, .., xₙ ) = (x₁, x₂, .., xₙ ₋ ₍ₔ ₋₁₎)
Take x ̸= y ∈ C.
If π(x) = π(y) then x, y agree in n − (d − 1) places and hence differ in at most d − 1, i.e d(x, y) ≤ d − 1. Since
d(C) = d, we must have x = y. Hence π is one-to-one. Hence its
domain is no larger than its codomain:
M=|C|=|Sⁿ⁻⁽ᵈ⁻¹⁾|=qⁿ⁻⁽ᵈ⁻¹⁾
example 4.3
What is A₂(3, 2)?
By the singleton bound
A₂(3, 2) ≤ 2
3−(2−1) = 22 = 4
But our example is a 2-ary (3,4,2)-code, so A₂(3, 2) ≥ 4.
Hence A₂(3, 2) = 4.
lemma 4.4
If x ∈ Sⁿ then |Bₜ(x)| =
If x ∈ Sⁿ
then
|Bₜ(x)| = Σᵣ nCr (q − 1)ʳ r=0,..,t
proof: #strings in Sⁿ differing from x in precisely r places. number of choices x number of choices for digits
Theorem 4.5. (Ball packing bound)
Let C be a q-ary
(n, M, d)-code with d ≥ 2t + 1. Then
M Σᵣ nCr (q − 1)ʳ ≤ qⁿ
r=0,..,t
BPB PROOF
Let C be a q-ary
(n, M, d)-code with d ≥ 2t + 1. Then
M Σᵣ nCr (q − 1)ʳ ≤ qⁿ
r=0,..,t
Since d ≥ 2t + 1, the t-balls centred on codewords are all
disjoint. Hence
|∪{x∈C} Bₜ((x)|=
Σ{x∈C} |Bₜ((x)|
= M* Σᵣ nCr (q − 1)ʳ
For r=0,…t
by Lemma 4.4. But
(∪_{x∈C} Bₜ(x)) ⊂ Sⁿ
⇒
| = q
∪x∈C Bt(x)| ≤ |Sⁿ|=qⁿ
e.g existence of a 3-ary (6,10,5)-code?
BPB rules out
t = 2 (d = 2 × 2 + 1)
= M* Σᵣ nCr (q − 1)ʳ
For r=0,…t
= 730
while q^n = 3^6 = 729.
e.g existence of (6,9,4)-code,
even if q,(n, M, d) passes the BP bound it does not follow that a code exists. For example, there is no 2-ary (6,9,4)-code, even though
9(1 + 6) = 63 < 64 passes
singleton bound rules out:
A_q(n, d) ≤ qⁿ⁻⁽ᵈ⁻¹⁾ = 8 but M=9
existence of codes
even if q,(n, M, d) passes both bounds it does not follow that such a code exists.
what does BP thm imply about A_q(n, d) ?
A_q(n, d) ≤
⌊[qⁿ]/[Σᵣ nCr (q − 1)ʳ]⌋
for r=0,…,⌊(d-1)/2⌋
integer by defn remmeber
defn 4.6 perfect code
A q-ary (n, M, d)-code is perfect if the collection of t-balls centred on codewords, t = ⌊(d − 1)/2⌋, is a partition of Sⁿ
collection of t-balls disjoint and completely cover Sⁿ
perfect code happens IFF equality in BPB
perfect code d can be even?
no, perfect codes can’t have even d
Suppose we had d even, for this x,y.
Let z be differing in d/2 places of x and of y. d/2 is an integer.
but as t = ⌊(d/2)-0.5⌋ = (d/2)-1
y is not in Bₜ(x) or in Bₜ(y). Since C is perfect every vector belongs to a ball. x’ s.t d(x’,z) ≤ t. By triangle inequality d(x,x’) ≤ d(x,z)+d(z,x’) =(d/2) + t= d-1<d
contradicting min distance d. C cannot be perfect.
perfect code can d be odd?
yes, check equality in BPB
f_1,f_2 f_3
perfect codes?
(1) is trivially perfect.
(2) d = 2 is even, so not perfect.
(3) is a 2-ary (5,4,3)-code:
BPB no equality 24
while |S^5| = 25 = 32, so not perfect
weight
def 4.9
The weight of a string x ∈ Sⁿ is
w(x) = #non-zero entries in x
E.g. w(011) = 2 = w(10010)=w(20030)
