===========================================================================
CSC 310                     Lecture 19 Summary                    Fall 2007
===========================================================================

Topics:

 -  Hamming distance

 -  Minimum distance for a code

 -  Minimum distance from parity check matrix

 -  Hamming codes

 -  References: sections 13.1, 13.2, 13.3, lectures 16 and 19 from 2006
    course by prof. Roweis.

----------------
Hamming distance
----------------

 -  For two N-bit vectors u, v, d(u,v) := number of bit positions where
    they differ. This is the Hamming distance between u and v.

 -  Satisfies trinagle inequality: d(u,w) <= d(u,v) + d(v,w).

---------------------------
Minimum distance for a code
---------------------------

Definition:

    The minimum distance for a code C is the minimum Hamming distance
    between any two codewords of C.

Notes:

 -  If d >= 2t+1 and a code has minimum distance d, it can correct any t or
    fewer errors.

 -  For a general code, need to consider all (2^K choose 2) pairs to
    compute minimum distance.

 -  For linear codes, minimum distance = minimum weight (i.e., number of
    non-zero coordinates) of a codeword other than all-zeros.

 -  If d = 2t is even (e.g. d = 2), and t errors occur, the code can detect
    this but not necessarily correct them.

 -  Ideally, we want: large minimum distance, so that we can correct many
    errors AND large number of codewords, to get good transmission rate.

-----------------------------------------
Minimum distance from parity check matrix
-----------------------------------------

Ideas:

 -  Can show: minimum distance = minimum number of linearly dependent
    columns in the parity check matrix H of the code.

 -  If H has an all-zero column, d = 1.

 -  If H has two identical columns but no all-zero column, d = 2.

 -  If H has distinct columns and no all-zero column, d >= 3.

-------------
Hamming codes
-------------

Ideas:

 -  Parity check matrix has N-K rows. List all numbers 1..2^{N-K} as
    columns in H. Then d = 3.

 -  Can correct any single bit error.