IV054 Coding, Cryptography and Cryptographic Protocols
2009 ­ Exercises II.
1. Decide which of the following codes are linear.
a) binary code C1 = {0000, 0011, 0110, 1001, 1010, 1100, 1111, 0101}
b) quaternary code C2 = {000, 312, 220, 132}
c) ternary code C3 = {0000, 0101, 1000, 1101}
2. Consider a binary [n, k]-code C with a parity check matrix
H =


1 1 0 1 0 0 1
0 1 1 1 1 0 0
1 0 0 1 1 1 0


a) Find n, k, h(C) and |C|.
b) Find the standard form generator matrix for C.
c) Prove that C
 C.
d) Find coset leaders and the corresponding syndromes.
3. Consider a binary linear code. Prove that either all of the codewords begin with
0 or exactly half of the codewords begin with 0.
4. Compare Pcorr when sending 16 messages unencoded to encoding using a Hamming
code H3. Assume communication is over a binary symmetric channel with
error probability p. Compare results for p = 0.01.
5. Let C be an [n, k, d] code over Fq. Prove that
a) A0(C) + A1(C) + . . . + An(C) = qk
.
b) A0(C) = 1 and A1(C) = A2(C) = . . . = Ad-1(C) = 0.
c) If C is a binary code containing the codeword 1 = 11 . . . 1, then Ai(C) =
An-i(C) for 0  i  n.
6. Let Pi be the set of all binary linear codes with weight equal to pi, where pi is
the ith prime. Decide whether there exists a self-dual code (C = C
) in Pi for
all i  N.
7. Show that two vectors y1 and y2 are elements of the same coset if and only if
Hy1 = Hy2 .
8. a) How many cosets is contained in the Reed-Muller code R(1, m)? Explain
your reasoning.
b) Determine the lower bound for the number of cosets that have a unique
leader in R(1, m). Explain your reasoning.