4 Optimisation

Question 1

Why optimise?
f_3
length vs error detecting

Answer 1

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).

Question 2

q-ary symmetric channel with symbol error probability p

Answer 2

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?

Question 3

q-ary symmetric channel with symbol error probability p:

Probability of exactly r errors
(binary)

Answer 3

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

Question 4

example Binary (9,5,6) code p=0.001 error probability

Answer 4

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

Question 5

q-ary symmetric channel with symbol error probability p:

Probability of exactly r errors
(for non-binary)

Answer 5

we have (p/(q-1))~ probability of error for each digit in q-ary alphabet

Question 6

Def 4.1
A q-ary (n, M, d)-code

Answer 6

A q-ary (n, M, d)-code is a q-ary code with block length n, M codewords and minimum distance d

Question 7

P(S)
P(Sⁿ)

Answer 7

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.

Question 8

(n, M, d)-cod_q

Answer 8

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

Question 9

How is the size of codewords related to n and q and d?

Answer 9

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.

Question 10

define A_q(n,d)

Answer 10

Max M
for fixed q,n,d

the size of the largest possible q-ary code of block length n
and minimum distance d.

Question 11

THM 4.2 Singleton bound

Answer 11

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ⁿ⁻⁽ᵈ⁻¹⁾

Question 12

example 4.3
What is A₂(3, 2)?

Answer 12

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.

Question 13

lemma 4.4
If x ∈ Sⁿ then |Bₜ(x)| =

Answer 13

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

Question 14

Theorem 4.5. (Ball packing bound)

Answer 14

Let C be a q-ary
(n, M, d)-code with d ≥ 2t + 1. Then
M Σᵣ nCr (q − 1)ʳ ≤ qⁿ

r=0,..,t

Question 15

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

Answer 15

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ⁿ

Question 16

e.g existence of a 3-ary (6,10,5)-code?

Answer 16

BPB rules out

t = 2 (d = 2 × 2 + 1)

= M* Σᵣ nCr (q − 1)ʳ

For r=0,…t

= 730

while q^n = 3^6 = 729.

Question 17

e.g existence of (6,9,4)-code,

Answer 17

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

Question 18

existence of codes

Answer 18

even if q,(n, M, d) passes both bounds it does not follow that such a code exists.

Question 19

what does BP thm imply about A_q(n, d) ?

Answer 19

A_q(n, d) ≤

⌊[qⁿ]/[Σᵣ nCr (q − 1)ʳ]⌋

for r=0,…,⌊(d-1)/2⌋

integer by defn remmeber

Question 20

defn 4.6 perfect code

Answer 20

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

Question 21

perfect code d can be even?

Answer 21

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.

Question 22

perfect code can d be odd?

Answer 22

yes, check equality in BPB

Question 23

f_1,f_2 f_3
perfect codes?

Answer 23

(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

Question 24

weight

def 4.9

Answer 24

The weight of a string x ∈ Sⁿ is

w(x) = #non-zero entries in x

E.g. w(011) = 2 = w(10010)=w(20030)

Question 25

useful weight property

Answer 25

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)

Question 26

lemma 4.10

Suppose S = {0, 1} and x, y ∈ S
n both have even weight. Then

Answer 26

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 …

Question 27

defn 4.11
Optimal codes

Answer 27

A q-ary (n, M, d)-code is optimal if
M = A_q(n, d).

Question 28

defining projection

Answer 28

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ⁿ⁻¹)

Question 29

define
‘projection onto xₖ = i-hyperplane’

(abusing notation as if Sⁿ were Rⁿ

Answer 29

πₖᶦ : Sⁿ → Sⁿ
x → πₖ (x) = x₁x₂…i xₖ₊₁…xₙ

k ∈ {1, 2, …, n}
replacing the k-th digit by i

Question 30

D ∈ (n, M, d)-cod with d > 1 then
|πₖ(D)|

what does |πₖ(D)| do to
(n, M, d + 1)-cod?

Answer 30

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

Question 31

THM 4.12
Suppose d odd. A 2-ary (n, M, d)-code exists

Answer 31

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₂

Question 32

corollary of THM 4.12
Suppose d odd. A 2-ary (n, M, d)-code exists….

Answer 32

If d odd then
A₂(n + 1, d + 1) = A₂(n, d)

Question 33

Lemma 4.13
A_q(n, d + 1) ≤

Answer 33

A_q(n, d + 1) ≤ A_q(n, d).

proof: in notes removing and replacing digits , triangle inequality

Question 34

Thm 4.14
A_q(n + 1, d) ≤

Answer 34

A_q(n + 1, d) ≤ qA_q(n, d)

proof: using optimal code, taking parts the same and deleting the last digis

Question 35

examples bounded:
Given A₂(10, 3) ≤ 79 it follows that

Answer 35

Given A₂(10, 3) ≤ 79 it follows that
A₂(11, 3) ≤ 2 × 79 = 158.

Question 36

example (6,2,6) give

Answer 36

repetition
(111111,000000}
unique code all distinct

Question 37

e.g give code (3,8,1)

Answer 37

{000,001,010,100,101,110,111}

biggest code in binary q^n = 8
unique code

Question 38

e.g give code (4, 8, 2)

Answer 38

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

Question 39

e.g give code (8, 40, 3)

Answer 39

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.

Question 40

graphs and codes
(undirected) graph
edges
order
complete
subgraph
morphism
automorphism

Answer 40

(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.

Question 41

V={1,2,3}
E={{1,3},{2,3}}

Answer 41

vertices 1,2,3 connected vertex pairs are 1 and 3
3 and 2

subgraph could be only 1 and 3 connected

Question 42

Graph G_q(n,k) and vertex set S^n edges {x,y} whenever d(x,y)≥ k

graph G ₂(3,3)

Answer 42

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

Question 43

Write down a maximal complete subgraph of each of the
following: G₂(3, 3), G₂(4, 3), G₂(5, 3)

Answer 43

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}.

Question 44

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

Answer 44

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.□

Question 45

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.

Answer 45

) 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)

Question 46

Def 4.19 Equivalent codes
C ∼ C′

Answer 46

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).

Question 47

4.20. Exercise. Check C ∼ C′
is an equivalence relation, i.e. a
reflexive, symmetric, transitive relation

Answer 47

Subspaces can be represented by a basis, more compact