IV054-2021 Homework 1 solutions
1.
Statement is false, proof by finding a specific case where statement is false.
Let C be a binary (2,2,2) code, where C — {00,11}. Let C be a code obtained from C by adding a parity bit,, therefore C = {000,110}. C is not a (n+l,M,d+l) code, but a (3,2,2.) code, therefore statement is false.
2.
Proof that A2(5.4) — 2: Let C be a code containing codeword 00000. To satisfy d = 4. all other codewords in C must have at least four ones (their distance from the codeword 00000 must be larger than. four). Two codewords of length 5 containing four ones have distance at most 2, therefore we can't construe! code (">.:{. 1).
3.
ISBN can correct a single digit error, thanks to the last digit used as a checksum so that: £i£i(n -i)xi = 0 mod 11.
For the code 0444851x33, we need to solve the following equation:
0-l+4-2 + 4- 3 + 4- 4 + 8- 5 + 5- 6 + l- 7 + x- 8 + 3- 9 + 3-10 = 0 mod 11 0 + 8 + 12 + 16 + 40 + 30 + 7 + 8x + 27 + 30 = 0 mod 11
170 + 8x = 0 mod 11 5 + 8.x = 0 mod 11
x = 9
The ISBN code 0444851933 is The Theory Of Error-Correcting Codes by F. J. Macwilliams and N. J. Sloane
4.
Writing out M codewords on log2M bits produces a "code" with Hamming distance equal to 1. We can create each new code by adding trailing zeroes to it, then:
Vrc € N > log2 M : d(n) = 1
- such a function is increasing (although not strictly increasing, but that's not the question, right?)
- such a function is also decreasing so let's show that we can also create non-decreasing increasing function:
Let us create each new code by repeating the elements of the original code e.g.
for M — 8 : X1X2X3 in C3 ~+ X1X2X3X1 in C4     ■-■ ~* x\X2Xzx\X2X-iXi in Cj —+ ... for such a code:
Vfc, n e N; k > 1, n e [k log2 M, (k + 1) log2 M) : d(n) = k This function is increasing and even non-decreasing!
5.
(a) Not a linear code: 111 + 111 = 000 and 000 Ca
(b) Not a linear code: let's have a ternary linear code C\ = {000,111,222},
then Cb = {000111,111222, 222000}. We can see that Cb is not a linear code since 000111 + 111222 = 111000 and 111000 i Ch.
(c) Is a linear code: the result of applying addition operation on two linear codes is a linear superset code of those two codes.
(d) Not a linear code: if C\ = {000,001,100,101} and C2 = {000, 111.222}, then 101 + 222 = 020 6 Cd, but 020 + 001 = 021 $ Cd
(a) Standard generator matrix for C:
	"l	0	1	1	0'		"1	0	1	1	0"		"0	1	1	0	(f		" 0	1	1	0	0 "
	l	0	0	0	1		1	0	0	0	1		1	0	(J	0	1		1	1	0	1	0
	0	1	0	1	1		1	1	0	1	0		1	1	(J	1	0		1	0	0	0	1
G = [ Ik I A ]
G =
" 1	0	0	1	1 "
0	1	1	1	0
(b) The minimal distance of C, h(C) = w(C), where w(C) is the smallest weight of non-zero code words of C.
c = {ooooo, iooii, oino, 11101}.
h(C) = w(C) = 3.
(c) Syndrome decoding table:
l(z)	z
ooooo	000
10000	110
01000	001
00100	100
00010	101
00001	011
10100	010
10110	111
w = 10111
w • HT = e • HT = 100 1(100) = 00100
Decoded word is w + l(z) = 10111 + 00100 = 10011.
7.
(a) Generator matrix of polynomial 1 + x2 + x3 + x4 in Rj:
'I   0   1   1   1   0 0N £=(0101110 ,0010111,
1 0 0 1 0 1 r 0101110
,0010111,
Gr
(b) To find parity-check matrix, first we need to find check polynomial h(x) — ^j^y-'-
(x7 - l)/(x4 + x3 + x2 + 1) = 1 + x2 + x3
From the result, we obtain parity-check matrix H:
(\ 1 0 1 0 0 ()\
0 110   10 0
0 0   110 10
\o 0 0  1   1  0  IJ
H
(\   1   0   1 0   0 0\
0   110 10 0
1110 0 10
\1  0  1  0 0  0 1/
H„
We can also get the same parity matrix by transposition from Gr
(c) codeword 1010 cannot be encoded by this code as maximum length of message word this polynomial can encode is 3. Best we can do is 101 which is encoded as:
(1 + x2 + x3 + x4)(l + x2) = (1 + x2 + x3 + x4) + x2(l + x2 + x3 + x4)
= (1 + x2 + x3 + x4) + {x2 + x4 + x5 + x6) = 1 + x3 + x5 + x6
thus 101 will be encoded as 1001011 (same result can be obtained by using generator matrix)
8.
n(3,3) > 3 + n(2,2) n(2,2) > 2 + n(l.l)
77(1,1) = 1
The lower bound of 77 for k = 3, d = 3 is 6, since n(3, 3) > 3 + (2 + 1) => n(3, 3) > 6.
(b) Since 77 = 6 and k = 3, the generator matrix will be 3 x 6. It's left half will be identity matrix 73, and we choose the right half such that all it's rows contain exactly two Is. The [6,3,3] linear code's generator matrix is:
/l   0  0   1   1 0\ G =   0   1   0   1   0 1 \o 0  10 11/
The resulting code C = {000000,100110,010101,110011,001011,101101,011110,111000}.
(c)
10 > d + n(2, \d/2\) n(2, \d/2\) = \d/2\+ n(l, IW21/21) n(l,\\d/2\/2\ = rrd/21/2] +n(0, \\\d/2\/2\/2\)
n(o(rrrrd/21/21/21/2i) = o
10 = d + pi/2! + \\dl2\/2\ +0        d = 5. The upper bound for d is 5.
9.
(a) All binary cyclic codes C of length 10 can be described using irreducible polynomials of x10 — 1:
x10 - 1 = (x + l)(x + l)(x4 + X3 + X2 + x + l)(x4 + X3 + X2 + X + 1)
We can therefore construct 24 = 16 cyclic codes from these irreducible polynomials. But since some of these irreducible polynomials are equal, some cyclic codes will be equal. In the end, we can build 9 different cyclic codes:
1
(x + 1) (a;4 + a:3 + x2 + x + 1) (x + l){x4 + x3 + x2 + x + 1) = x5 + 1 (x+l){x+l)=x2 + l (x4 + X3 + X2 + x + l){x4 + X3 + X2 + X + 1) = X8 + X6 + X4 + X2 + 1 (x + l)(x + l)(x4 + X3 + X2 + X + 1) = X6 + X5 + X + 1 (x4 + X3 + X2 + x + l)(x4 + X3 + X2 + x + l)(x + 1) = X9 + X8 + X7 + X6 + X5 + X4 + X3 + X2+X+1 (x4 + x3 + x2 + x + l)(x4 + x3 + x2 +x + l)(x + l)(x + 1) = x10 + 1
(b) To construct the smallest binary code with the codewords (0110000000) and (1010000000), we will use the previous question and choose C =< 1 + x >. Let's see if this code contains both codewords (0110000000) and (1010000000) :
• By shifting (0110000000) 1 bit to the left, we obtain the codeword (1100000000) which can be constructed with 1 + x.
• The codeword (1010000000) can be constructed using 1 + x2 which is (x + l)(x + 1) = 1 + x2 Therefore, the smallest binary code containing both codewords is C =< 1 + x >.