===========================================================================
CSC 310                     Lecture 18 Summary                    Fall 2007
===========================================================================

Topics:

 -  Linear Codes

 -  Generator matrices

 -  Parity check matrices

 -  Equivalent codes, systematic form

 -  Parity check matrix from systematic form generator matrix

References: lectures 15, 16 from 2006 course by prof. Roweis.

------------
Linear Codes
------------

Definition:

    A linear code C for the N-th extension of a binary channel is a
    subspace of (F_2)^N.

Ideas:

 -  The all-0 N-bit string is always a codeword.

 -  If u and v are codewords, so is u+v.

 -  Let K be the dimension of the subspace C, so 0 <= K <= N. Then,
    |C| = 2^K. We call this an [N,K] code.

 -  Can select K vectors as a basis for C: u_1, .., u_K.

 -  Every v in C can be written as sum_{i=1}^K{a_i*u_i} for some a_i in
    {0, 1}.

 -  We encode the K-bit block x as the N-bit vector sum_{i=1}^K{x_i*u_i}.

------------------
Generator matrices
------------------

Definition:

    A generator matrix G for a code C is obtained by listing K basis
    vectors as the rows of G. Thus, G will have dimension KxN: K rows and
    N columns.

 -  Given K-bit column vector x, its encoding is (G^T)*x (matrix product).

 -  A code might have many generator matrices, and for each generator
    matrix, the encoding will be different but the set of codewords stays
    the same.

---------------------
Parity check matrices
---------------------

Ideas:

 -  We can specify a code C as the set of vectors that satisfy certain
    linear constraints: v is a codeword in C if

        c_1*v_1 + c_2*v_2 + .. + c_N*v_N = 0

 -  Look at a linear constraint as an N-bit column vector c. Then, for v to
    be a codeword, we must have (c^T)*v = 0.

 -  If we have N-K linearly independent constraints, the dimension of the
    code will be N-(N-K) = K.

Definition:

    A parity check matrix H for a code C of dimension K is obtained by
    listing N-K linearly independent constraints as rows of H. Thus, H will
    have dimension (N-K)xN.

Notes:

 -  Unlike a generator matrix, a parity check matrix does not say how we
    should encode (i.e., it does not map N-bit codewords to K-bit blocks).
    Instead, it just identifies the set of valid codewords.

 -  An N-bit string v is a codeword if H*v = 0, where the 0 on the right is
    the N-K column vector.

 -  A code with a single parity check equation of the form v_1+..+v_N = 0
    is called a single parity check code.

---------------------------------
Equivalent codes, systematic form
---------------------------------

Ideas:

 -  Applying elementary row operations to G (or H), such as swapping 2 rows
    or adding one row to another, does not change the set of codewords, but
    it might change the mapping of K-bit messages to codewords.

 -  Swapping 2 columns of G (or H) might change the set of codewords by
    permuting certain bits in all possible codewords. We say two codes are
    equivalent if one can be obtained in this way from the other.

 -  We say a code is in systematic form if its G is of the form [I_k P],
    where I_k is the KxK identity matrix and P is some Kx(N-K) matrix.

---------------------------------------------------------
Parity check matrix from systematic form generator matrix
---------------------------------------------------------

 -  Given a generator matrix G for a code C, a parity check matrix H for C
    must satisfy

        H*((G^T)*x) = 0

    for every K-bit column vector x. This means that H*(G^T) is the all-0
    (N-K)xK matrix.

 -  Furthermore, H must have N-K linearly independent rows.

 -  If G is in systematic form [I_K P], check that H = [P^T I_{N-K}]
    satisfies H*(G^T) = 0. Remember that P^T + P^T = 0 in F_2 (addition
    modulo 2).