Appendix G: Exercises - Codes: The Guide to Secrecy from Ancient to Modern Times - page 596

1. (0 , 1 , 1 , 0 , 0 , 1 , 0).
2. (0 , 1 , 1 , 0 , 0 , 0 , 1).
3. (0 , 0 , 1 , 1 , 1 , 0 , 1).
4. (0 , 1 , 1 , 0 , 1 , 0 , 0).
5. (1 , 0 , 0 , 1 , 0 , 1 , 0).
6. (1 , 0 , 0 , 1 , 0 , 0 , 1).
7. (0 , 0 , 0 , 1 , 1 , 0 , 0).
8. (1 , 0 , 1 , 0 , 1 , 0 , 1).

✰ 11.47. Prove that the matrix G given on page 456 is the generator matrix for

the Golay code G 24 , and that properties 1 and 2, listed therein, hold for

this code.
( Hint: If you have a desire and ability at programming and a computer to
execute your algorithm, you can list all 2 12

= 4096 codewords and verify

that d (

24 )=8 directly. Otherwise, first show that the code is self-dual.
To do this, employ the fact that rows 2 through 11 of the matrix M 12 × 12
are cyclic permutations of row 1 as presented on the aforementioned page.
This reduces the work in establishing that any given row of G forms a
zero dot product with all the rows of G . Now you can easily establish that
[ M 12 × 12 |

G

G 24 has generator matrix

I 12 ] is a generator matrix for G 24 since

[ M 12 × 12 | I 12 ] and M 12 × 12 = M 12 × 12 . To show that every codeword of

G 24
has weight divisible by 4 , observe that the weight of the intersection is the
dot product, which is even since the code is self dual. Since all rows have
weight divisible by 4 , it follows from Exercise 11.22 that the weight of the
sum of any two codewords is divisible by 4 . This can be employed to verify
that the weight of any linear combination of rows of G has weight divisible
by 4 . To show that there exists no codeword of weight 4 , look at all the
possibilities for the weight of such a codeword by breaking it into left and
right components. The outcome will be that 0 is the only such word. That
G is the generating matrix for

G 24 now follows from these facts. )

11.48. Prove that G 23 is a linear [23 , 12 , 7]-code.

11.49. Prove that the Golay code G 23 is cyclic.

11.50. Prove that the ternary (11 , 6) Golay code is perfect.

11.51. Prove that Ham(r , 2) is a cyclic code for any r ≥ 2.

11.52. Show that the polynomial g ( x ) chosen with minimal degree for cyclic
codes described on pages 459 and 460 satisfies properties 1-3 listed therein.

11.53. Show that the matrix G displayed on page 460 is the generator matrix
for the cyclic code C as claimed.

11.54. Prove that P given on page 460 is the parity-check matrix for the cyclic
code C , as claimed.