12 exercises Flashcards
The 26 letters of the alphabet may be represented in
Z₃³={0,1,2}³
A 7→ 001, B 7→ 002, C 7→ 010, …, Z 7→ 222.
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
what is the codeword for T?
(x, y, z) = (2, 0, 2)
The 26 letters of the alphabet may be represented in
Z₃³={0,1,2}³
A 7→ 001, B 7→ 002, C 7→ 010, …, Z 7→ 222.
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
PCM H
101201
011100
000011
when is w in C?
100012 is it in?
iff wH^T=0
H is a 3 x 6 matrix (n-k) x n
G will be k x n
(100012)H^t = 0, so 100012 ∈ C
(1000012) [100]
[010]
[110]
[210]
[001]
[101]
=(0,0,0)
The 26 letters of the alphabet may be represented in
Z₃³={0,1,2}³
A 7→ 001, B 7→ 002, C 7→ 010, …, Z 7→ 222.
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
PCM H
101201
011100
000011
confirm G is the generator
G=
221000
120100
200021
check the rows of G are a basis for C
H is a 3 x 6 matrix (n-k) x n
G should be a k x n = 3 x 6
G has the right number of rows.
Dual has dimension 3 (number of rows of H)
G must have dimension 3
rows are linearly independent
so that they are a basis for something
A generator matrix for a linear code is made up of linearly independent rows
GHᵀ=0
checks all rows belong to C
ALT H in RREF method
what is the dimension of a code with gen G
what is the dimension of its dual code
Dual has dimension n-k (number of rows of H)
code has dimension k (number of rows of G
The 26 letters of the alphabet may be represented in
Z₃³={0,1,2}³
A 7→ 001, B 7→ 002, C 7→ 010, …, Z 7→ 222.
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
PCM H
101201
011100
000011
confirm G is the generator by using bound vars and pivots
G=
221000
120100
200021
H is in RREF
x₁ x₂ x₅
[1 0 1 2 0 1]
[0 1 1 1 0 0]
[0 0 0 0 1 1]
x₁ x₂ x₅ bound variables correspond to pivots
x₃ x₄ x₆ free variables
we have: xHᵀ=0 each component in x dot prod row
** x₁**+ x₃+2x₄+ x₆ =0 Sum of rows =0
** x₂ **+ x₃+x₄=0
x₅ + x₆=0
giving in Z_3 lhs leading rhs free vars
** x₁=2 x₃+x₄+2x₆
** x₂ =2x₃+2x₄
**x₅ =2x₆
choose for the free vars 100,010,001,
basis from these equations for solutions:
G=
** x₁** x₂ ** x₃ x₄ x₅ x₆
2 ** 2** 1 0 0 0
1 2 0 1 **0 ** 0
2 0 0 0 2 1
forms a basis
if we permute the cols we get the standard form
The 26 letters of the alphabet may be represented in
Z₃³={0,1,2}³
A 7→ 001, B 7→ 002, C 7→ 010, …, Z 7→ 222.
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
PCM H
101201
011100
000011
Write down another generator matrix for C.
Compute the encoding of the letter E, both by G and by your own choice of alternative generator matrix.
G=
221000
120100
200021
For example we can swap row 1 and 2 in G.
G’=
[120100]
[221000]
[200021]
Encoding E: 5= a3^2 +b3 +c (abc)= (012)
The encoding of E is different by gen matrix
(012)G= 220112
(012)G’=021012
what is good about G being in standard form?
Note that we do not in general get the messageword from the first digits of the encoded form — this only happens if G is in standard form. Indeed the digits of the messageword might not appear anywhere
in the encoded version! This emphasises that the practical encoding of a message depends very much on G, rather than on C.
The 26 letters of the alphabet may be represented in
Z₃³={0,1,2}³
A 7→ 001, B 7→ 002, C 7→ 010, …, Z 7→ 222.
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
PCM H
1 0 1 2 0 1
0 1 1 1 0 0
0 0 0 0 1 1
What is d(C)?
G=
221000
120100
200021
looking at columns of H being linearly indep:
no two cols are a multiple of each other
d(c)>=3
Looking at weights of G:
d(C)<=3
d(C)=3
(3 linearly dependent in H but no 2 are linearly dep_
The 26 letters of the alphabet may be represented in
Z₃³={0,1,2}³
A 7→ 001, B 7→ 002, C 7→ 010, …, Z 7→ 222.
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
PCM H
1 0 1 2 0 1
0 1 1 1 0 0
0 0 0 0 1 1
**How many coset leaders are there? How many coset leaders of weight 1
are there? What are the syndromes of coset leaders?
**
G=
221000
120100
200021
|C|=3^3=27
|Z₃⁶|=3^6
#coset leaders=3^3=27
d(C)=3 thus t=1 and all weight 1 vectors are coset leaders
of weight 1 we have: 6 x2= 12
————————————————–
syndromes:
S(000000)=000
S(x00000)=x00
S(0x0000)=0x0
S(00x000)=xx0
S(000100)=210
S(0000x0)=00x
S(00000x)=x0x
The remaining 27 − (12 + 1) = 14 coset leaders are much harder to find.
There are (3 x5)x2x2=60 weight 2 vectors in this space
not all in cosets led by weight 1 vectors
The
syndromes of weight 2 vectors are each easy to compute by linearity,
given the weight 1 syndromes above.
strategy when coset decoding:
It is not impossible, since the standard array is not impossibly large in this case, but it is uncomfortable. In practice, a good strategy might be
to wait and see what message is received, and hence what syndromes we need coset leaders for (in order to try to do error correction), rather than
just computing them all up front
The
syndromes of weight 2 vectors are each easy to compute by linearity,
given the weight 1 syndromes above.
syndromes:
S(000000)=000
S(x00000)=x00
S(0x0000)=0x0
S(00x000)=xx0
S(000100)=210
S(0000x0)=00x
S(00000x)=x0x
S(120000) = S(100000) + S(020000) = 100 + 020 = 120 = S(000200)
S(010001) = S(010000) + S(000001) = 010 + 101 = 111 (new!)
S(001010) = S(001000) + S(000010) = 110 + 001 = 111 = S(010001)
But these cases illustrate the problem. The first is not new; the second is new, and can be taken as a coset leader; but the third is an equally good
choice as leader of the same coset (which thus confirms that the code is not reliably 2 error correcting, as we already knew!).
To this point we do not even know if all the remaining coset leaders can
be found from among the weight 2 vectors, or whether higher weights are
needed. A couple more new ones at weight 2 are: S(010010) = 011 and
S(100001) = 201 (and we can multiply through by 2 to get some more
from these), but we would have to keep working through to find the rest.
This nicely illustrates one of the problems thrown up by coding theory.
The syndrome map S : Z₃⁶ → Z₃³
is a surjective linear map. The set
{S(e1), S(e2), S(e5)} is a basis of the image, so we could choose
‘coset leaders’ of the form
x = α1e1 + α2e2 + α3e5 with (α1, α2, α3) ∈ Z₃³
, but this does not give the lowest possible weights, so for channels with low single digit error probability this would give highly statistically non-optimal error correction behaviour.
Given that G is used for encoding, what messageword encodes to
212012, if any? What messageword encodes to 012212, if any?
The 26 letters of the alphabet may be represented in
Z₃³={0,1,2}³
A 7→ 001, B 7→ 002, C 7→ 010, …, Z 7→ 222.
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
PCM H
1 0 1 2 0 1
0 1 1 1 0 0
0 0 0 0 1 1
**How many coset leaders are there? How many coset leaders of weight 1
are there? What are the syndromes of coset leaders?
**
G=
221000
120100
200021
From this G the 3rd 4th and 6th give messageword itself
(x, y, z) = (2, 0, 2)
The others are checks, all of which are satisfied.
For 012212 the 3-rd, 4-th and 6-th of these give (x, y, z) = (2, 2, 2), but
two of the checks fail, so 222 is unlikely to be what was intended!
To make a guess for the intended messageword we could compute the syndrome:
H(012212)t = (2, 2, 0)t
The coset leader with this syndrome is 002000. Thus the intended encoding was probably 012212-002000=010212. This decodes as 022=H
Decode as much as possible of the following received message, given that
the transmitted message was encoded using C with generator matrix G,
assuming nearest neighbour decoding.
Message:
002112 012212 220112 112100 220112 000000
200021 112000 220112 000000 022022 221000
022200 000000 220112 112000 112000 101200
112000 012020 000000 221000 111112 000000
212012 010212 221000 212021 002000 211121
220112 012021 012021 200021 110221 220112
G=
221000
120100
200021
That is, the k-th letter of the alphabet is represented by abc ∈ Z₃³
where k= a3^2 +b3 +c
000 represents space
002112Ht = 000 so decode as 212 − > W
012212Ht = 220 so must correct by
012212 → 012212 − 002000 = 010212 so decode as 022 → H
− > E − > R − > E space A R E
000000 → 000 → space
022022Ht = 111 so must correct by some choice of weight 2 coset leader
(which is at least as likely to be wrong as right, but it no worse than any other choice): choosing 010001 we get 022022 - 010001 = 012021 − > 201 − > S (choosing 001010 we get 022022 - 001010=021012 → K here
instead!)
221000Ht = 000 so decode as 100 → I
…and so on.
