Coding Theory

Second Assignment: due Fri. Feb. 23

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. Suppose a_1,a_2,a_3,a_4 is the information vector, what is the corresponding codeword?

   c. Find a parity check matrix H for C.

   d. Find the dimension and minimimum distance for C and C-perp. Find the number of codewords in C and C-perp. What is special about C?

   e. 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. Decode 100021, 220120, 020120, 012111,
   000001, 2*2*01, 220121, 1**002.
   The * indicates an erasure. The receiver couldn't distinguish the received digit.