Question 1.
(a) No. Let C = {010,101, 111}, then 0 ■ 010 = 000 £ C.
(b) No. Let C = {0}, then C = {1} which is not a linear code, since 0 • 1 = 0 ^ C.
(c) Yes. We need to verify linear code axioms:
(i) Observe a 0 b = a + b under W2l. Let Ci, c[ g C\ and c2, c'2 g C*2, then:
(ci ® c2) + (cj ® 4) = (ei + c2) + (ci + 4) = (ci+c'1) + (c2 + 4) = C] + c2
= 4' <8) 4 g c",
where c'[ g Ci and 4 g C2. So the axiom of additive closure holds.
(ii) Observe 0 • a = 0" and 1 • a = a under Fg. So we need to check only that 0™ g C". Since 0" g Ci and 0" g C2, then 0" ® 0" = 0™ g C". So the axiom of scalar multiplication closure holds.
Question 2.
(a) We can read out the n = 5 and k = 2 directly from the generating matrix G. With a little effort, since the code contains only four words, we can also see that the codeword with smallest weight is 01010 and therefore d = 2.
(b) The code C has 4 codewords: {00000,10101,01010,11111}. The array has dimension qn~k = 23 = 8 by qk = 4. A standard (Slepian) array is given as follows:
00000	10101	01010	11111
10000	00101	11010	01111
01000	11101	00010	10111
00100	10001	oino	11011
00001	10100	01011	11110
10010	00111	11000	01101
00011	10110	01001	11100
00110	10011	01100	11001
(c) We can find the word 11110 which is decoded to the first row in its column - codeword 00111.
Question 3.
(a) Yes.
Code generated by Gi is Ci {0000, 1001, 0101, 1100} Code generated by G2 is C2 = {0000, 1010, 0011, 1001}
We can get code C\ by doing permutation of 2nd and 3th and of 1st and 4th columns on the code words of C2.
(b) Yes.
Code generated by Gi is C\ = {00000, 11000, 01010, 00101, 01111, 10010, 11101, 10111}. Code generated by G2 is C2 = {00000, 11110, 10010, 01111, 11101, 01100, 10001, 00011}. We can get code C\ by doing permutation of 2nd and 5th columns on the code words of C2.
(c) Two codes are permutation equivalent if they are equal up to a fixed permutation on the code word coordinates, so we can generate the code words and try all the possible permutations and then decide if they arc permutation equivalent. All the combinations have a finite and fixed number.
Question 4.
Consider the binary linear code C with generator matrix
"1   1  1  0  0 0" G=   110 110 10   110 1
(a) Find the parity-check matrix of C.
To get the parity check matrix I first edit the generator G matrix to normal form.
1110 0 0 110 110 10   110 1
1110 0 0 0 0 1110 0   10   10 1
1	1	1	0	0	0
0	1	0	1	0	1
0	0	1	1	1	0
10 110 1 0 10 10 1 0   0 1110
" 1	0	0	0	1	1 "
0	1	0	1	0	1
0	0	1	1	1	0
[h\A
Then parity matrix H is created as:
II
0	1	1	1	0	0
1	0	1	0	1	0
1	1	0	0	0	1
(b) Find the syndrome of the word 100001.
To find the syndrome I have to multiply received word w — 100001 with the matrix H.
w-HT = (010)
Syndrome of this word is 010.
Question 5.
{1001,0111,1110}
(a) Third word is linear combination of the first two. Generator matrix for binary linear code containing these words can look like this:
This code is also the smallest possible, because vectors in matrix G are linearly independent. C    {0000,1001,1110,0111} \C\ = 22
(b) These words are linearly independent in GF(3). Generator matrix for such a code can look like this:
	1	0	0	f		"1	0	0	1"		"1	0	0	r		"1	0	0	f
G =	1	1	1	0	=	0	1	1	2	=	0	1	1	2	=	1	1	1	0
	0	1	1	1		0	1	1	1		0	0	0	2		0	1	1	1
This matrix generates the smallest ternary linear code C3. | C31 = 3' Question 6.
Proof. We know that x = x\x2 ■ ■ ■ xi2 g C <^=> xHT = 0 = (0,..., 0). If Hj denotes the i-th
G =
10 0 1 1110
column in HT, then this is iff   f\   x ■ Hj = 0.
l<i<12
We can sum vip these equations into one and see that the following must hold
3xi = Xi = 0 (mod 2)
1<«12 l<i<12
However, this only holds iff we have an even number indices i g {1
12} s.t. Xi = l.
□
Question 7.
Consider code C\ and its dual Cy . Consider an operation O that transforms C\ into equivalent code C2. We will show that for each such operation, there is a corresponding equivalent operation O' that transforms      into C^; ■
There are two types of operations that we have to consider:
(a) permutation of the words or positions of the code
Permutation of words is trivial case. Permutation of words in C\, doesn't affect so in this case, the corresponding operation on      is to do nothing.
Permutation of positions of the code does affect dual code. To make things simpler, we can decompose permutation into sequence of swapping of two columns. Now, when we swap two columns in C\ to obtain C2, we swap columns on same positions in to obtain to ensure that same pairs of symbols will be multiplied with each other as before swapping. Thus the scalar product will remain the same (zero) for all pairs of codewords.
(b) multiplication of symbols appearing in a fixed position by a non-zero scalar
Consider V1V2V3 ... vn 6 C\ and u\U2U^...un 6 Cj" and suppose that to obtain C2, column i oft) was multiplied by non-zero scalar x. Before, i-th column added V{U{ to the sum. Now it would add xt>iUi so naturally, the sum wouldn't be zero anymore. To fix this in Qf, column i of u can be multiplied by modular inverse of x (mod q), denoted as x . It holds that x~lx = 1 (mod q) and modular inverse exists for all numbers that share no prime factors with q, which are actually all numbers 1,2,... q — 1 since we assume that q is a prime. So now given columns will again be adding xViX Ui = ViUi to the sum. Thus the scalar product will remain the same (zero) for all pairs of codewords.
For any equivalent codes C\ and C2, there is a sequence of operations a) and b) that can transform one code into the other. We can map all of those operations to the corresponding operations on dual codes as shown above. Described operations on dual codes are again operations of type either a) or b) (swapping rows = permutation of positions and multiplying by modular inverse = multiplying by non-zero scalar). So and C% are equivalent because one can be obtained from the other by sequence of operations a) and b).