IV054 Coding, Cryptography and Cryptographic Protocols
2012 - Exercises II.
1. Decide which of the following codes are linear. Find the standard form of generator matrix for codes
that are linear.
(a) binary code C1 = {00000, 00110, 00101, 10111, 10010, 10001, 10100, 00011}
(b) ternary code C2 = {000, 001, 110, 111}
(c) quinary (5-ary) code C3 = {000, 224, 132, 444, 312}
2. Consider the binary linear code C generated by the matrix
G =




1 0 0 0 1 0 1 1
0 1 0 0 1 1 0 0
0 0 1 0 1 1 1 0
0 0 0 1 0 1 1 1




(a) Show that C is able to correct any one-bit error.
(b) The set {11001011, 01110101, 10101010} consists of exactly one codeword, one word obtained
by making an error in exactly one bit and one word obtained by making an error in exactly
two bits. Decide which word has which property. Explain.
3. Consider the 5-ary code C such that
a1a2a3a4 ∈ C ⇔ a1 + 2a2 + 3a3 + 4a4 ≡ 0 (mod 5)
. Show that C is a linear code and find its generator matrix in standard form.
4. Given a linear code prove that the minimum distance equals the minimal weight among all non-zero
codewords.
5. For any set of k independent columns of a generator matrix G, the corresponding set of coordinates
forms an information set for an [n, k] code C. How many information sets are there for the binary
repetition code of length n?
6. Let C1 and C2 be linear codes of the same length. Decide whether the following statements hold.
(a) If C1 ⊆ C2, then C⊥
2 ⊆ C⊥
1 .
(b) (C1 ∩ C2)
⊥
= C⊥
1 ∪ C⊥
2 .
7. Show that there exists a [2k, k] self-dual code over Fq if and only if there is a k × k matrix P with
entries from Fq such that PPT
= −Ik.
8. Let Mi be the family of all binary linear codes with weight equal to mi where mi is the ith Mersenne
prime (a prime of the form 2j
− 1 for some j ∈ N). For all i ∈ N, decide whether there exists a
self-dual code in Mi.