Coding Theory

Second Assignment: due Wed. Sept. 22

1. Let GG be the following matrix over F_2, and let C be the code generated by it.

   11000011
   10011001
   11101000
   11111111
   

   a. Find a systematic encoding matrix G for C.

   b. Using G encode a_1,a_2,a_3,a_4 (placing the a_i so they will be part of the codeword).

   c. Find a parity check matrix H for C.

   d. Find the dimension of C and C-perp. Find the number of codewords in C and C-perp.

   e. Show that C= C -perp.

   f. How many vectors of each possible weight---0, 1, .., 8--- are there in C?
   
   

2. a. Show that in a binary code either all the vectors have even weight or half have even weight and half have odd weight.

   b. Show that in a binary self-orthogonal code either all the vectors have weight a multiple of 4 or half have weight a multiple of 4 and half do not.
   
   

3. We set up a correspondence between letters and 3-vectors over F_3. The correspondance comes from associating a base 3 number to each letter via the following table, and then taking the digits in the base 3 number as entries in a vector.

   Letter	integer	integer base 3
   blank	0	000
   A	1	001
   B	2	002
   C	3	010
   ...	...	...
   Z	26	222

   Consider the parity check matrix HH for a code C
   221
   201
   222
   210
   121
   200
   

   a.Find a systematic matrix H for C. Then find a systematic generator matrix for C.

   b. Encode HELP.

   c. Make a syndrome decoding array table for C using only error vectors of weight 1. How many coset leaders would you need for complete maximum likelihood decoding? List some of the syndromes that we are not decoding.

   d. Read the secret message by decoding the sequence of 8 letters corresponding to the following codewords:
   100021, 220120, 020120, 012111,
   000001, 2*2*01, 220121, 1**002.
   The * indicates an erasure. The receiver couldn't distinguish the received digit.