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)
useful weight property
When S is an additive group then so is Sⁿ with componentwise addition so useful
(x+y) ᵢ = x ᵢ+y ᵢ for all i
d(x, y) = w(x − y) = d(0,x-y)
lemma 4.10
Suppose S = {0, 1} and x, y ∈ S
n both have even weight. Then
Suppose S = {0, 1} and x, y ∈ S
n both have even weight.
Then d(x, y) is even
proof:…
Fix x,y ∈ Sⁿ
J ᵢⱼ=Jᵢⱼ(x,y)={k∈{1,…,n}| xₖ=i & yₖ=j}
e.g.
x=01101
y=10110
J₀₀=∅ J₀₁={1,4} J₁₁={3}
w(x)= |J₁₀|+|J₁₁|
w(y)=|J₀₁|+|J₁₁|
d(x,y)= |J₀₁|+|J₁₀|
= w(x)+w(y) - 2|J₁₁|
alt proof uses additive group 1+1=0 …
defn 4.11
Optimal codes
A q-ary (n, M, d)-code is optimal if
M = A_q(n, d).
defining projection
k ∈ {1, 2, …, n} define ‘projection
(deletes the kth digit)
πₖ : Sⁿ → Sⁿ⁻¹
x → πₖ (x) = x₁x₂…xₖxₖ₊₁…xₙ
Restricts any subset of Sⁿ and hence on any code C ∈ P(Sⁿ), to produce a new code πk (C) ∈ P(Sⁿ⁻¹)
define
‘projection onto xₖ = i-hyperplane’
(abusing notation as if Sⁿ were Rⁿ
πₖᶦ : Sⁿ → Sⁿ
x → πₖ (x) = x₁x₂…i xₖ₊₁…xₙ
k ∈ {1, 2, …, n}
replacing the k-th digit by i
D ∈ (n, M, d)-cod with d > 1 then
|πₖ(D)|
what does |πₖ(D)| do to
(n, M, d + 1)-cod?
D ∈ (n, M, d)-cod with d > 1 then
|πₖ(D)| = M,
distinct points are still distinct after projection, caused by deleting one letter
πₖ :
(n, M, d + 1)-cod
→
⊔_d′∈{d,d+1}
of (n − 1, M, d′)-cod
deleting the kth letter from these codes gives codes n-1 length, same number of codewords and either minimum distance the same or reduced by one
THM 4.12
Suppose d odd. A 2-ary (n, M, d)-code exists
Suppose d odd. A 2-ary (n, M, d)-code exists IFF
a 2-ary (n + 1, M, d + 1)-code exists
proof sketch: construct a code by adding a parity check digit dep on w(x) to ensure even. Thus d’= d or d+1
d ≤ d′ ≤ d + 1.
every x’ has even weight so d’ is even by lemma 4.10 hence d’=d+1
(only if)
Let D ∈ (n + 1, M, d + 1)-cod₂
take x,y in D, s.t d(x,y) =d+1
find a digit they differ, say kth and delete to construct D′ ∈ (n, M, d′)-cod2 by D′ = πk (D)
d ≤ d′ ≤ d + 1
d(x’,y’)=d(x,y)-1 = d hence D′ ∈ (n, M, d)-cod₂
corollary of THM 4.12
Suppose d odd. A 2-ary (n, M, d)-code exists….
If d odd then
A₂(n + 1, d + 1) = A₂(n, d)
Lemma 4.13
A_q(n, d + 1) ≤
A_q(n, d + 1) ≤ A_q(n, d).
proof: in notes removing and replacing digits , triangle inequality
Thm 4.14
A_q(n + 1, d) ≤
A_q(n + 1, d) ≤ qA_q(n, d)
proof: using optimal code, taking parts the same and deleting the last digis
examples bounded:
Given A₂(10, 3) ≤ 79 it follows that
Given A₂(10, 3) ≤ 79 it follows that
A₂(11, 3) ≤ 2 × 79 = 158.
example (6,2,6) give
repetition
(111111,000000}
unique code all distinct
e.g give code (3,8,1)
{000,001,010,100,101,110,111}
biggest code in binary q^n = 8
unique code
e.g give code (4, 8, 2)
use (3,8,1) by parity check digit: thm 4.12
{0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111}
d+1 for odd d
n+1
e.g give code (8, 40, 3)
For our fourth case it is no longer obvious how to construct a code.
Under the circumstances it is prudent to check if such a code is impossible, by checking the BP and singleton bounds. In this case one finds that the BP bound fails, so there is no such code.
graphs and codes
(undirected) graph
edges
order
complete
subgraph
morphism
automorphism
(undirected) graph: An (undirected) graph is a pair G = (V, E), where V is a finite set
whose elements are called vertices,
edges: E is a subset of
P₂(V) = {e ∈ P(V)| |e| = 2} whose elements are called edges
order: size of V
complete: A graph G = (V, E) is called complete E = P₂(V), i.e. if every two vertices are connected by an edge
subgraph: G′ of G = (V, E) determined by a subset V′ of V is
given by G′ = (V′, E′), where E′ = {e ∈ E | e ⊆ V′}.
Let G = (V, E) and G′ = (V′, E′) be graphs.
morphism:
A graph morphism
ϕ : G → G′ is a map ϕ : V → V′ such that {v1, v2} ∈ E ⇒ {ϕ(v₁), ϕ(v₂)} ∈ E′
If ϕ is bijective and the
reverse implication also holds, then we call ϕ an isomorphism.
automorphism: An automorphism of G is an isomorphism from G to G.
V={1,2,3}
E={{1,3},{2,3}}
vertices 1,2,3 connected vertex pairs are 1 and 3
3 and 2
subgraph could be only 1 and 3 connected
Graph G_q(n,k) and vertex set S^n edges {x,y} whenever d(x,y)≥ k
graph G ₂(3,3)
G ₂(3,3) (binary, length 3, edges whenever d(x,y)≥ 3 for all x,y
If the subgraph G_q(n,k) is complete then d(C) ≥ 3
Write down a maximal complete subgraph of each of the
following: G₂(3, 3), G₂(4, 3), G₂(5, 3)
A_q(n, k) is the size of a maximal complete subgraph in G_q(n, k
G₂(3, 3)= {000, 111} (equally good would be {001, 110})
G₂(4, 3)= {0000, 1110}
G₂(5, 3)={00000, 11100, 10011, 01111}.
If there is a complete graph of order l in Gq(n, k) (l vertices),
then there is a complete graph of order l including the vertex
000…0. Prove it
If, for i fixed, we apply an alphabet permutation to the ith entry in every vertex sequence in G(n, k) then the Hamming distances between vertices are not changed. This means that in Gq(n, k) two image vertices will be connected iff the original vertices were connected. Now take any vertex x (in a complete subgraph C, say) and change it to 000…0 by applying swapping 0 and xi in the ith coordinate for i = 1, . . . , n. Then the new C will still be complete and contain 000…0.□
Let Ψ : S^n → S^n denote swapping the first two entries in the
sequence (e.g. Ψ(10111) = 01111 when q = 2 and n = 5). Then
Ψ defines a graph automorphism of Gq(n, k). Prove it.
) For every pair of vertices d(x, y) = d(Ψx, Ψy), since the first
two entries are interchanged in both. So Ψ gives a graph
automorphism of G(n, k)
Def 4.19 Equivalent codes
C ∼ C′
Codes C, C′ ⊆ Sⁿ
are equivalent if
C′ = ϕ(C) for some bijection
ϕ : Sⁿ → Sⁿ which is the composite of maps of the following two types:
(1) Permutation of the coordinates,
(2) Applying a permutation of the alphabet S in a fixed coordinate.
Note that for ϕ as above we have
d(x, y) = d(ϕ(x), ϕ(y)) for all x, y ∈ Sⁿ
In particular, d(C) = d(C′).
Furthermore, ϕ is an automorphism of the aforementioned graph Gq(n, k).
4.20. Exercise. Check C ∼ C′
is an equivalence relation, i.e. a
reflexive, symmetric, transitive relation
Subspaces can be represented by a basis, more compact
