17 Exercises Flashcards
17.1. Exercise. Assume given integers M, d ≥ 2. Can you give a linear code C over F_q with |C| ≥ M and d(C) = d in the following situations?
(i) You are allowed to choose the prime power q.
i) minimum distance as big as you like: consider repetition code, this is linear if S is a field S=F_q . (It is linear if S is a field as has basis 1….1 as all a multiple of this so closed under addition)
size of the code is q and block length n. Min distance is also d here.
Choose q ≥M and d=n for the repetition code
C_{q,n}
so C= C_{q,d} = {a1_d: a in F_q}⊆F^d _q
1_d is all one vectors of length d
Then |C|= q ≥M and d(C)=d
17.1. Exercise. Assume given integers M, d ≥ 2. Can you give a linear code C over Fq with |C| ≥ M and d(C) = d in the following
situations?
(ii) Like M and d, the field size q is given.
iI) Dimension k relates to |C|=|F|ᵏ= qᵏ
First choose m s.t qᵐ ≥M
C’=Fᵐ_q this would have minimum distance 1
(all codewords in Fᵐ_q considered, size is qᵐ which is enough codewords for us now we need to meet the required distance.)
Now embed Fᵐ_q into C= Fᵈᵐ_q (which is bigger)
instead replace x → xx….x (concatenate d copies of x)
a repeated block- the minimum weight is d (e.g. min weight of x is 1 so min weight of repeated block is d*this, this will meet the requirements for our min distance)
and take C to be the image. (since its an embedding the number of elements of C is the same |C| = q^m≥ M and d(C) = d (so even if we fix the q we can get the M words we want)
Meaning we have |C| = |C’|=qᵐ ≥M code big enough and distance met
compare to binary Golay code n 24 prev question example
Can you give a binary linear code with
M= 4096
d =8.
F_q with |C| ≥ M
dim = 12
n=24 dim = 12 min dist = 8
if we wanted to achieve the code in the way above prev. using 2¹²=4096≥ M
d(C)=1 so we need to concatenate 8 times
then Z₂¹² embed this in Z₂⁸ˣ¹² = Z₂⁹⁶
so 8 times as big need a much bigger block length
(Z₂¹² embedding binary code length 12 into Z₂⁹⁶ by repeatedly concatenating 8 times so length 96 code min distance 8 ) ie 4 times bigger than Golay code
|C| = |F|ᵏ= qᵏ = 2ᵏ≥ M
2¹² = 4096
so Golay code can do this by only doubling dimension a big min distance, n=24 for Golay code
17.2 question 2: A code C is known to be 21 error correcting give a lower bound for the distance
using d(C) ≥ 2t+1 is 21 error correcting
d(C)≥ 43
Q3: The set Eₙ of even weight binary vectors of length n is a subspace of Z₂ⁿ. Hence Eₙ is a binary linear code.
What are the parameters [n,k,d]
Give the generator matrix in standard form
This is a subspace, since w(x) congruent:
w(x)≡ Σᵢ xᵢ mod 2 {i=1,…n)
(weight is congruent to sum of components mod 2, because we are in binary)
lhs is an integer rhs in Z₂
so Eₙ = {x in Z₂ : Σᵢ xᵢ=0 mod 2 }
Length n given.
We have the subspace given by a spanning set, elements in F₂ length n. So dimension could be n.
I have imposed a linear eq =0 above which takes away one dimension, n-1
Dimension k=n-1 since we impose one non-trivial linear equation (if there were more we would check linearly indep and take any away of linearly independent conditions)
k=dim E_n
d is the min weight of non-zero vectors which must be 2 (all vectors even weight so d≥ 2, and 110…0 ∈ En has weight 2)
Generator matrix? n-1 by n
an obvious vector which lies in this of even weight: (110…0) for length n
n-1 shifts of this would give me a generator matrix
e.g. we have
[1100..0]
[0110..0]
……shifted repeatedly
[0….011]
other version in standard form uses Identity matrix n-1 by n-1
[1…01
………1
……….1
0……11]
standard form achieved by identity then 1…1 column vector
17.4. Exercise.
(i) Construct a binary linear [8, 4, 3]-code
(ii) How many such codes have a generator matrix in standard
form?
Code length 8 C⊂ Z₂⁸
k=4 dimension |C|= |F|⁴= 16
distance d(C)=3
t=1
{00000000, 11100000,00000111,11111111,
01010101, …}
thus the generator matrix will be a 4x 8 matrix WLOG we may assume G is in standard form
G= (I₄| A)
A 4x4 binary matrix
How many binary 4x4 matrices? 2^{16} including the zero and identity. Not all generate d=3 codes so we need a matrix which has no non zero entries o/w not ok.
For example A=0 means each generating vector in G=[I₄0|] has total weight 1 so d=1.
A=I₄ means each generating vector in G=[I₄|I₄] has total weight 2. But we want min distance 3
Each row of A: So we need in each row at least 2 non-zero entries
(weight at least 2)
(so that each row of G has at least 3)
cant have
[1100]
[1100]
[*
[*]
adding first 2 rows of G would cancel and become 0 weight 2 for sum of first two and we cant have this
Also rows of A must be distinct
E.g.
A=
[1 1 0 0
1 0 1 0
1 0 0 1
0 0 1 1]
For each candidate check: min weight of all nonzero vectors is 3
(it wont be any more as any row of G will have weight 3 but we might have combinations contradicting this)
one way is construct PCM:
H=[-Aᵀ |I₄]
Columns of Aᵀ are the rows of A
weights columns in Aᵀ must be ≥ 2
could we have repetition in columns? none of them would be the same as the identity as weights =1 there
By TH, 11.4 no col is 0 check and no two cols are the same check
so min distance is 3
This is clearly the same as checking that no two rows of A are the
same (we have stipulated that each row has at least two non-zero
entries, so their transposes cannot be the same as any of the
vectors in 14).
This requirement is satisfied in our example, so we are done.
17.4. Exercise.
(i) Construct a binary linear [8, 4, 3]-code
prev found G
How many such codes
The
code in full consists in all linear combinations of the row vectors in
our G. Thus it starts
C = {00000000, 10001100, 01001010, 00101001, 00010011, 11000110,
10100101, …………….., 11111100}
(16 elements altogether).
Another example satisfying the criteria is given by
A =
1 1 0 0
1 1 1 0
1 0 0 1
0 0 1 1
To count all binary [8,4,3] codes
first consider [8,4,≤3]:
We consider all A’s that satisfy conditions
*all rows weight ≥ 2
*no repeated rows, rows distinct
*A generator matrix in RF gives rise to a unique subspace, ie. unique RF matrices give rise to different subspaces so we can just count these and must give different codes
choices row of length 4:
2⁴-5 = 11
(need min weight 2 (4 have weight 1), cant have all 0’s)
second row:11-1=10 (no repeats)
third and fourth
total choices 11 x 10 x 9 x 8 = 7920
we knew the d(C)≥ 3 but as it has a row of weight 3 we have d(C)=3
Constructing G from
=[I|A]
what can weights of A tell us
continuing with example
If A has a row of weight 2
G will have a row of weight 3
so d(C)≥ 3
Could have:
a)all rows of A have weight 3
A=
[0111]
[1011]
[1101]
[1110]
That means all rows of G have weight 4
row of weight 4 doesnt mean that the distance d(C)=4 we just know that it is not more than 4
Back to example:
Now if i pick 2 rows and sum: Always has weight 2
if i take 3 rows then they can never be 0
in Z_2 x+y = 0 means x=y
So columns of H :
all cols differ, no 3 cols add up to 0 any 3 columns of H are independent
so d(C)=4
There are 4 rows of weight 3: all must be different so combinations of these
4!=24 #matrices of this kind
(we don’t need these)
other case: A contains the all one row, since all rows must be different the others have weight 3
e.g.
A=
[1111]
[0111]
[1011]
[1110]
in this case what is the min distance?
other case: A contains the all one row, since all rows must be different the others have weight 3
e.g.
A=
[1111]
[0111]
[1011]
[1110]
in this case what is the min distance?
Not enough to consider just rows:
the top one has weight 5 then G would weight 6 not helpful
Can i make a very small weight be combining rows of A?
First two rows weights sum to 1000
First two rows of G therefore sum to 111000 weight 3.
Thus d(C)=3 in this case
final answer 7920-24=7896
Remarkexercise 17.4
Existence of a code
Why can’t it be linear?
A₂ (8, 3) = 20, so a binary (8,20,3)-code exists
Such a code can’t be linear since:
for C linear |C| = M = qᵏ where
k = dim C, and no integer k obeys 20 = 2ᵏ
Thus |C| = 24 = 16 is the biggest linear code we can hope for
Remarkexercise 17.4 counting the matrices summary
Number of distinct G=[I₄|A] matrices
count # giving [8, 4, ≥ 3]-codes
so weights can be 2 or more in A for rows
We can choose 11 possibilities for the first row then
choices are 11 x10x9x8 = 7920 choices
distinguish cases
some of these A’s contain rows of weight 2 which means d(C)=3
those which have weights ≥ 3:
a all rows weight 3, we can see
H=[-Aᵀ |I₄] 3 cols linearly independent so as rows of G have weight 4 d(C)=4
there are 4!=24 of these matrices as 4 poss rows weight 3
b
A has the 1 row, other 3 must have weight 3. adding the all 1 row to any oter is a weight 1 row so for G this is codeword weight 3, d(C)=3 in this case
total
7920-24 = 7896
Exercise 17.5
(i) Construct standard arrays for binary linear codes C₁, C₂ generated:
G₁ =
[101]
[011]
G₂ =
[10110]
[01011]
(ii) Decode the received vectors 11111 and 11011 and 01011 in C₂.
(iii) We receive 00101. What is going on?! Explain with a ball-packing analogy.
Standard array C₁:
k=2 |C₁|= 2ᵏ=4, n=3
#rows here will be #cosets
2³/2^2=2ⁿ⁻ᵏ = 2
000 101 011 110
100 001 111 010
100 has not appeared yet so we use it
from these we can see minimum distance of C is 2 we have
d(C₁)=2 we just look at the mimum possible weight of a non-zero vector
Standard array C₂: k=2 n=5
|C₂|= 2ᵏ = 4
#rows here will be #cosets
2ⁿ⁻ᵏ = 8
00000 10110 01011 11101
10000 00110 11011 01101
01000 11110 00011 10101
00100 11010 01111 11001
00010 10100 01001 11111
00001 10111 01010 11110
**11000 01110 10011 00101
01100 11010 00111 10001
(first row is the code, found from (a,b)G or 0, first row, second row, sum of first and second)
First row gives me d(C₂)=3 from min weight of non 0, means all rows of weight 1 are coset leaders , don’t have to check if they come up elsewhere THM 9.1
next coset leaders: I check for any missing weight 2 and use those
then check i have all vectors weight 2 and sufficient rows
Exercise 17.5
(i) Construct standard arrays for binary linear codes C₁, C₂ generated:
G₁ =
[101]
[011]
G₂ =
[10110]
[01011]
(ii) Decode the received vectors 11111 and 11011 and 01011 in C₂.
00000 10110 01011 11101
10000 00110 11011 01101
01000 11110 00011 10101
00100 11010 01111 11001
00010 10100 01001 11111
00001 10111 01010 11110
**11000 01110 10011 00101
01100 11010 00111 10001
(iii) We receive 00101. What is going on?! Explain with a ball-packing analogy.
11111 decodes as 111101
11011 decodes as 01011
01011 decodes as itself (codeword)
Exercise 17.5
(i) Construct standard arrays for binary linear codes C₁, C₂ generated:
G₁ =
[101]
[011]
G₂ =
[10110]
[01011]
(ii) Decode the received vectors 11111 and 11011 and 01011 in C₂.
00000 10110 01011 11101
10000 00110 11011 01101
01000 11110 00011 10101
00100 11010 01111 11001
00010 10100 01001 11111
00001 10111 01010 11110
**11000 01110 10011 00101
01100 11010 00111 10001
*(iii) We receive 00101. What is going on?! Explain with a ball-packing analogy.
decode 00101 as 11101:
assumed error 11000
But could we have chosen another coset for this? Alt choice for coset leader 00101 and then this would decode as 00000.
* 00000 is a codeword
at distance 2 from 00101
*no codeword closer to 00101 than 11101, but there are codewords equidistant
thus:no codeword closer to 00101 than 11101, but there are codewords equidistant
in ball packing terms: ball around 00000 of radius 2 intersects ball around 11101 of radius 2. They intersect in vectors such
as 10001 and 00101 and 01100. None of these vectors is any closer
to any other codeword, so we know, receiving one of these, that at
least 2 symbol errors have occurred in transmission. In trying to correct this we’d like to choose the closest codeword, but there is no unique closest. Thus there is really nothing to choose between guessing 00000 and 11101. We pick arbitrarily
from these codewords at distance 2 and hope for the best (or
perhaps seek retransmission).
17.6. Exercise
Let C be the 3-ary [4,3]-code generated by
G =
[1 2 2 1
2 1 0 1
0 1 1 1]
Find a PCM for C.
Hence list the codewords of C^⊥
3-ary
n=4 k=3
3x4 generator
|C|= 3^3=27
d(C) not specified
**step 1: standard form by row operations **
in {0,1,2}
[1221]
[0022]
[0111]
=
[1221]
[0111]
[0022]
=
[1002]
[0111]
[0022]
=
[1002]
[0100]
[0022]
=(2*R_3)
[1002]
[0100]
[0011]
G=[I₃|A]
n x(n-k)
set H=[-Aᵀ|Iₙ₋ₖ]
-Aᵀ=[-2 0 -1] = [1 0 2]
H=[1 0 2 1]
C^⊥ = {0000, 1021, 2012}
(we determine all the words in the dual using linear combos of the rows as a generator matrix)
d(C)=
By looking at d(C)= 3:
meaning no two columns are a multiple of each other in PCM. The colums are multiples of each other, there is even a 0 col so d(C)=1
or looking at G in standard form there is a row of weight 1 so there is a word of weight 1 in the code so d(C)=1
