School.lisk.in

To find a code that satisfies C = C⊥, C has to be a [2k, k]-code satisfying In particular, ∀u ∈ C : u · u = 0, therefore every codeword in C has even parity. This alsoimplies that all codewords have to differ in even number of zeros.
Next, let me claim that we can consider only bases with codewords containing exactly two ones (instead of considering bases with four ones; zero and six are useless, obviously).
If we have two codewords with four ones, differring from each other in even number of ones(which basically means two in this case), and sum them, we get a codeword with two ones.
Also, the codewords in a basis may not share a signle one. If they shared a single one, their inner product would not be equal one. If they shared two ones, they would beidentical.
Let’s just count the number of such bases: First, let’s calculate the number of ways to choose k independent vectors in the vector space V (n, q). For the first vector, the only limitation is that it can’t be zero. Therefore,we have qn − 1 choices. The next one has to be linearly independent of the first one. Sincethere are q vectors linearly dependent on the first one, this leaves us with qn − q choices.
The number of ways to choose k independent vectors is therefore (qn − 1)(qn − q) · · · (qn − qk−1).
All these k-tuples of vectors are bases of k-dimensional subspaces of V (n, q). However,a lot of these span the same subspace.
We shall divide that by the number of ways to choose a basis for a particular k-dimen- sional subspace. This is in fact just the number of ways to choose k independent vectorsin the subspace. That is (qk − 1)(qk − q) · · · (qk − qk−1).
Finally, the number of different k-dimensional subspaces of V (n, q) is (qn − 1)(qn − q) · · · (qn − qk−1) , (qk − 1)(qk − q) · · · (qk − qk−1) which is, by the way, the value of the Gaussian polynomial G(n, k).
Theorem. Let C be a binary code of length n and C = {x1 · · · xnxn+1 | x1 · · · xn ∈ C, xn+1 = If C is a linear code, then C is also a linear code.
(1) We shall show that ∀u, v ∈ C : u + v ∈ C .
∀u, v ∈ C : u = u1 · · · unun+1 ∧ u1 · · · un ∈ C ∧ un+1 = u + v = w1 · · · wnwn+1 ∧ w1 · · · wn ∈ C ∧ (∀wi : wi = ui ⊕ vi) ∧ wn+1 = un+1 ⊕ vn+1.
wn+1 = (2) For a binary code, it’s obvious that ∀u ∈ C , a ∈ GF (2) : au ∈ C .
(a) Let’s just take all linearly independent vectors. Since the sum of the second and the third is the fourth, the basis consists of the first three vectors. We will just put theminto a matrix, obtaining a generator matrix: (b) By the dimensions of the Slepian array given in the lecture slides, we can see that a [n, k]-code has qn−k cosets each consisting of qk words.
In this case we have a [5, 3]-code, therefore it has 4 cosets each having 8 words.
(c) Let’s complete the code C and construct a Slepian array in the way described in the lecture slides (I’m not listing the Haskell code used this time): The word 11111 decodes as 01111, word 00011 is already in C.
array is a bit ambiguous, since it decodes 10001 as 00011, but h(10001, 00011) =h(10001, 00000) so it may very well be decoded as 00000; and indeed, if we choosethe coset leaders differently, we get a Slepian array that does so.
It is easy to see that this follows from the Theorem in exercise Let C = V (n − 1, 2).
Then constructing the code C as in exercise gives us exactly all words with even weight,i.e. C = En. Since |C| = |C | = |En|, the basis of En will have n − 1 vectors, just like thebasis of C has. Also, the basis of En may be created just by adding a parity bit. Therefore,the generator matrix of code En is this (it also happens to be in a standard form): The idea behind that is that the first n rows of the parity check matrix check for the presence of such word (its prefix, in fact) in code C and the last row checks the parity.
Formally speaking, we shall prove that ∀u ∈ V (n + 1, 2) : u ∈ C Proof. For all words v ∈ V (n, 2) and for all rows h in the matrix H, (v | vn+1) · (h | 0) =0 ⇐⇒ v · h = 0 ⇐⇒ v ∈ C. For all words u ∈ V (n + 1, 2) and for the parity check row(s | 1), u · (s | 1) = 0 ⇐⇒ w(u) is even. Logically, v ∈ C ∧ w((v | vn+1)) is even ⇐⇒(v | vn+1) ∈ C .
The parity check matrix of a code C = Ham(r, 2) is a r × (2r − 1) matrix like this: It is also the generator matrix of the code C⊥. Since the ones and zeroes in this matrixare very much like a fractal, the properties we will see hold for matrices for other valuesof r as well.
It can be seen that every row has exactly 2r−1 ones and 2r−1 − 1 zeroes. Therefore, the codewords in the basis have all weight of 2r−1. It it also not hard to see that summing upany rows just reverts half of ones to zeros and half of zeros to ones, creating again a wordwith a weight of 2r−1. Therefore, all non-zero linear combinations of these have a weightof 2r−1.
The code C is defined by the parity check matrix using this equation: Because of the correspondence between a code’s parity check matrix and a dual code’sgenerator matrix, C is a [6, 3]-code. From xHT = 0 ⇒ x ∈ C, we get: x1 ⊕ x2 ⊕ x4 = 0x1 ⊕ x3 ⊕ x5 = 0x1 ⊕ x2 ⊕ x6 = 0 Now, we’ll try to find minimal non-zero solution to this system. If we set x1 = 1, we’reforced to set at least 2 other variables to 1, the same holds for x2, x4 and x6, whereassetting x3 = 1 impies only x5 = 1. Therefore, the word we were looking for is 001010.
The distance of C is the same as the weight of the non-zero word of minimum weight,

Source: http://school.lisk.in/_media/iv054:xjanous3_02.pdf?id=iv054%3Astart&cache=cache