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.


    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

    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.