- 7th January, 10:00-11:00. First lecture.
Sender -> encoder -> channel -> decoder -> recipient. Motivation.
Redundancy, natural language. Alphabets, words and block codes.
Repetition codes of lengths 2 and 3.
Informal description of error detection and correction. Definition:
Hamming distance, proof that Hamming distance is a metric.
- 7th January, 12:00-13:00.
Proof (continued). Definitions: t-error detecting, t-error correcting,
minimum distance d(C) of a code C.
Lemma: C is t-error-detecting iff d(C) > t, and
C is t-error-correcting if d(C) > 2t. This means we can focus on
minimum distance from now on! Informal description of the central
problem addressed in this course in terms of sphere-packing in the metric space
of words with Hamming distance.
- 10th January, 15:00-16:00. Corollary of the lemma from last
time: A code is 2t-error-detecting iff it is t-error-correcting.
Definitions: q-ary (n,M,d)-code and A_q(n,d).
"Main coding theory problem" (as far as this course is concerned)
is to evaluate A_q(n,d).
Examples: The code {000, 111} shows that A_2(3,3) >= 2;
{000, 012, 021, 102, 111, 120, 201, 210, 222} shows that
A_3(3,2) >= 9; and {00000, 00111, 11011, 11100} that A_2(5,3) >= 4.
All these inequalities are tight. Exercise: try to show this!
(Later in the course, we'll be encountering general techniques for
proving upper bounds on A_q(n,d).)
Determining good bounds on A_q(n,d)
is difficult even for small values of n and d.
E.g., the exact value of A_2(10,3) was determined as
recently as 1999! We can reduce the search space considerably by
lumping together equivalent codes. To this end, define two operations
on codes: Op1 is a permutation of columns, Op2 is a permutation
of alphabet symbols at a given position. Op1 preserves
distances between words (Lemma 1.5).
- 14th January, 10:00-11:00.
[Exercise Sheet 1 released.] Op2 preserves
distances between words (Lemma 1.8).
Definition of equivalence of codes. Equivalent codes have
the same minimum distance. Ex: ternary "parity-check" code of
length 2 {00, 12, 21}, and the ternary repetition code of length 2
{00, 11, 22}.
Ex: There is a unique ternary (2,3,2)-code, up to equivalence.
Ex: There is a unique binary (5,4,3)-code, up to equivalence.
Interval quiz: Are the ternary codes {000, 001, 010, 100} and
{000, 001, 010, 021} equivalent?
- 14th January, 12:00-13:00.
Solution to quiz.
Lemma: A_q(n,n) = q and A_q(n,1) = q^n.
Singleton bound (Thm 2.8): statement and proof.
Ex: A_3(3,2) <= 9 (and hence A_3(3,2) = 9). If d is even then
A_2(n,d) = A_2(n-1, d-1) (Thm 2.3). Ex: A_2(6,4) = 4. Outline
of proof of Thm 2.3; details held over to Thursday.
- 17th January, 15:00-16:00.
Completion of the proof of Thm 2.3. Ex. (continued from last time):
since the proof is constructive we can write down an explicit (6,4,4)
code, namely {000000, 001111, 111001, 110110}. The Hamming
(sphere-packing) bound (Thm 2.6). Statement looks daunting, but we'll
see that all the components have a clear interpretation, and the whole
is easier to grasp than appears at first sight! Condition of
"t-error-correcting" in terms of "spheres" (really balls) of radius t.
Volume of a sphere, i.e., number of words in a sphere of (Hamming)
radius t. Completion of the proof of Thm 2.6.
- 21st January, 10:00-11:00.
[Exercise Sheet 2 released.
Plotkin bound in a weaker form: A_2(n,d) <= 2d/(2d - n), provided
2d > n. Key idea: define a 0,1-matrix, then count the number of
1s in two ways: by row and by column. Quiz: construct this matrix
for the code {00000, 00111, 11100, 11011}. What is the minimum
number of 1s in any row? What is the maximum number of 1's in any
column? Explain these findings. Proof of the weaker
version of the Plotkin bound. [To be continued.]
- 21st January, 12:00-13:00.
Completion of the proof from last lecture.
Tighten the Plotkin bound a little by treating separately the cases
d even or odd, and M even or odd. This yields the Plotkin bound
as stated in Thm 2.12. Ex: A_2(5,3) <= 4. Ex: A_2(9,6) <= 4.
These are both tight (see Q2 of Exercise Sheet 2).
The "Bound with No Name"
(Thm 2.9): statement and proof.
- 24th January, 15:00-16:00.
Definitions. Noisy channel, with error probability p. (Nearest neighbour)
decoding process. Word error probability. Ex: binary repetition
code of length 5 with nearest neighbour decoding. Pr(00000 is
correctly received) = (1 - p)^5 + 5p(1 - p)^4 + 10p^2(1 - p)^3 =
918/1024 when p = 1/4. (Compare with 3/4 without repetition.)
Nearest-neighbour decoding is not in general unique. Ex:
ternary repetition code of length 3, i.e., {000, 111, 222}.
We must map {000, 001, 002, 010, 020, 100, 200}
to 000; we may map any
of {012, 021, 102, 120, 201, 210} to 000. Convention: in the
latter case, use the first symbol to decide the decoding,
so that 012 and 021 map to 000.
Definitions: rate of a code, and capacity of a
channel. Statement of Shannon's Theorem (proof is outside the
scope of the course) and an intuitive reading.
- 28th January, 10:00-11:00.
No lecture.
- 28th January, 12:00-13:00.
No lecture.
- 31st January, 15:00-16:00.
Start of new topic: linear codes. Brief review
of fields concentrating on finite fields and particularly
those of prime order.
Identify the alphabet
A with F_q, and codewords with vectors over F_q. A^n can now be
viewed as a vector space over F_q. Review of vector space axioms.
Definition of vector subspace.
Now restrict attention to linear codes, which are vector subspaces
of A^n. Ex: (6,4,3)-code {000000, 011011,
101101, 110110}; parity check code {000, 012, 021, 102, ..., 222}.
Review of linear independence of vectors, span of vectors, basis of
subspace. Ex: {011011, 101101}, and {012, 102} are bases for the
earlier examples.
- 1st February.
No examples class.
- 4th February, 10:00-11:00.
[Exercise Sheet 3 released.]
Weight of vector; invariance of distance under addition of
fixed vector and multiplication by a fixed scalar;
d(x,y) = weight(x - y) (Lemma 4.3, statement
and proof). Cor. 4.4: the minimum distance of a linear code is
the weight of a minimum-weight codeword.
A vector space of dimension k over F_q contains q^k vectors.
[n,k]- and [n,k,d]-codes.
- 4th February, 12:00-13:00.
Ex: <1022, 0121> over F_3. This has
dimension 2 and hence 3^2 = 9 codewords. We listed these
systematically and checked that the minimum distance (minimum
weight of a non-zero codeword) is 3. So what we have is a
ternary [4,2,3]-code. The Hamming bound is 3^4/(1 + 4*2) = 9,
so this is a perfect code. (The hamming spheres exactly cover
(F_3)^4.) Generator matrix (not unique). Review of linear maps:
image Im(alpha), kernal ker(alpha), rank r(alpha) = dim Im(alpha),
and nullity n(alpha) = dim ker(alpha). Rank-nullity theorem.
Equivalence for linear codes. Review of operations 1 and 2.
Statement and proof of Lemma 4.6.
(Operation 1 is a linear map on F_q^n and hence preserves linearity
of codes.) Operation 2 does not preserve linearity;
example to illustrate this.
- 7th February, 15:00-16:00.
Restrict the allowed permutations of symbols to ones that that
arise from multiplication by a non-zero field element. Lemma 4.7
(multiplication by a non-zero field element induces a permutation).
Restriction of Operation 2 is Operation 2'. Statement and proof
of Lemma 4.8. (Operation 2' is a linear map on F_q^n and hence
preserves linearity of codes.)
Quiz. How many [3,1,3]-codes are there over F_3, up to
equivalence? Recall generator matrix. Aim to relate
equivalence of linear codes (as defined above) to familiar
row/column matrix operations.
- 11th February, 10:00-11:00. [Exercise Sheet 4 released,
questionnaire distributed.] Matrix
operations MO1 (permutation of rows), MO2 (scaling of rows) and
MO3 (adding a multiple of one row to another). If G is a generator
matrix for C, and G' is obtained from G through a sequence of operations
MO1--3, then G' is a generator matrix for C (Lemma 4.9).
Example, based on the code <1022, 0112>.
Column operations MO4 (permutation or columns) and MO5 (scaling
of columns). If G is a generator matrix for C, and G' is obtained
from G through a sequence of operations MO4--5, then H is a generator
matrix for a code C' that is equivalent to C (Lemma 4.10).
[Time for questionnaire completion.]
Why no column operation "MO6" (add a multiple of one column to another)
corresponding to row operation MO3? Answer, if
H is obtained from G through operation "MO6", then G and H are in
general generator matrices for inequivalent codes. Ex: the ternary
[4,2,3]-code <1022, 0112> goes under "MO6" to <1022, 0111> which
has minimum distance at most 2, and hence is inequivalent to
the original code.
- 11th February, 12:00-13:00.
In summary,
If G' is obtained from G through a sequence of operations MO1--5, then
G and G' are generator matrices for equivalent codes. In particular,
If G is the generator matrix of an [n,k]-code then so is G'. Definition
of generator matrix G in standard form: G = (I_k | A) where I_k is the
k * k identity matrix and A is an arbitrary k * (n-k) matrix.
Lemma 4.12: any k * n matrix of rank k can be reduced to standard
form using operations MO1--5. Ex: <0244, 3304, 1040>, "parity check"
code of length 4 over F_5. Ex. There is a unique [4,3,2]-code over
F_5 up to equivalence (namely the one we just considered).
- 14th February, 15:00-16:00.
Equivalence relation u ~ v iff u - v \in
C; equivalence classes are cosets. Ex: cosets of <0011,1100>.
Proposition 4.14: cosets partition F_q^n; there are q^{n-k} cosets,
all of size q^k. Interlude: use concept of generator matrix in
standard form to construct a [7,4,3]-code over F_2 and show that it
is unique.
Definition of coset leader and
construction of the Slepian array; the associated decoding process.
Each row of the array contains the words in a particular coset.
Ex: [4,2]-code <0011, 1100> over F_2.
- 18th February, 10:00-11:00.
No lecture.
- 18th February, 12:00-13:00.
Review of the first half of the course.
(Revision, sample examination questions, etc.)
- 21st February, 15:00-16:00.
No lecture.
- 22nd February, 15:00-16:00.
No examples class.
- 25th February, 10:00-11:00.
[Exercise Sheet 5 released.]
Review of the Slepian array and decoding process derived from
in in the context of the code {00000, 00111, 11100, 11011}.
Lemma: the decoding process
defined by the Slepian array is nearest neighbour. Note however,
that the Slepian array can be very big (q^{n-k} \times q^k). Ideally
we want a decoding process that can be described compactly, just as
the generator matrix compactly describes the code itself. To this
end, consider the dual code to C. Review of scalar product and its
properties, specifically that it is symmetric and bilinear.
Definition of the dual of a code.
Ex. From first principles, construct the dual of {00000, 00111, 11100, 11011}.
- 25th February, 12:00-13:00.
Direct proof that the code dual to C is linear. Lemma 5.2,
statement and proof. (C is a code with generator matrix G.
A word w is in the code C' dual to C iff Gw^T = 0.) Consider
the linear map alpha: F_q^n -> F_q^k defined by alpha(w) = Gw^T.
The code C' dual to C is ker alpha. By the Rank-nullity Theorem
dim C' = dim ker alpha = n - dim Im alpha = n - k, since G
has full rank. Ex. the dual of the repetition code of length 3
over F_3 is the "parity-check code" of length 3 over F_3. And vice
versa.
Statement and proof of Theorem 5.4:
(C')' = C, where prime denotes "dual".
- 28th February, 15:00-16:00.
Definition of parity-check matrix of C
(= generator matrix of C').
Statement and proof of Lemma 5.5: Suppose that C is a code with parity-check
matrix H. Then v \in C iff Hv^T = 0. Statement a proof of Lemma 5.6:
Suppose C is an [n,k] code with generator matrix G, and H an
(n-k) times n matrix. Then H is a parity check code for C iff (1) the
rows of H are linearly independent and (2) GH^T = 0.
Ex. The [4,2]-code generated by <0111, 1100>.
- 3rd March, 10:00-11:00.
[Exercise Sheet 6 released.]
Review of generator matrix, dual code and parity-check matrix.
Why the parity-check matrix is better than the generator matrix for
testing membership in a code.
Lemma 5.7, statement and proof: If G = (I_k | A) is a generator
matrix for some code C, then H = (-A^T | I_{n-k}) is a parity-check
matrix for C. Ex: C = <00111, 11100> and C = <1022, 0112>.
Definition of syndrome S(w) of a word.
Lemma 5.8, statement and proof: If v and w are in the
same coset, S(v) = S(w).
- 3rd March, 12:00-13:00.
Review of the Slepian array,
using the example C = <00111, 11100> over F_2.
Decoding process
in inefficient if n is large. Can do better using the idea of syndrome
of a vector.
Construction of a syndrome
look-up table. Ex: C = <00111, 11100> (continued). Quiz: consider
the code C = <0011, 1100> over F_2. Write down a parity-check
matrix for C. Now calculate a syndrome look-up table for H.
Answer to quiz. Description of the decoding process associated
with the syndrome look-up table. Why does this process
produce a codeword? Why is it nearest neighbour? Claim:
the syndrome look-up table process produces the same result as
the Slepian array. Summary of material on linear codes.
New topic: constructing codes. Redundancy r = n - k. Definition
of H_r, the parity-check matrix for the Hamming code Ham(r,2).
Explicit construction of Ham(2,2) (= repetition code of length 3
over F_2).
- 6th March, 15:00-16:00.
Review of the construction of binary Hamming codes Ham(r,2).
Ex. Ham(3,2). Note that the minimum distance of Ham(3,2) is 3.
Ham(r,2) is a [2^r-1, 2^r-r-1]-code.
Proof that Ham(r,2) has minimum distance 3 in general.
(So Ham(r,2) is a binary [2^r-1, 2^r-r-1, 3]-code.)
Where would the proof break down for q>2? The problem
is that pairs of columns of H_r may be linearly dependent.
Solution: define an equivalence relation ~ on (F_q)^r:
v ~ w iff there exists lambda not= 0 with v = lambda w.
The columns of H_r include one vector from each equivalence
class, except the singleton class containing 0.
- 10th March, 10:00-11:00.
[Exercise Sheet 7 released.]
Lemma 6.2: number of equivalence classes under ~ (not counting
the singleton containing the zero vector) is (q^r-1)/(q-1).
Ex. Ham(2,3) and Ham(3,3). An easy way to write down the
columns of the parity-check matrix of Ham(r,q).
Proof than Ham(r,q) has minimum distance 3
(i.e., is 1-error-correcting) for all r,q.
Number of columns in H_r is
n = (q^r-1)/(q-1). Thus Ham(r,q) is a [n, n-r, 3]-code
with n as above.
The Hamming (sphere-packing bound)
for 1-error correcting codes of length n over F_q is
q^n/(1 + n(q-1)) = q^n/(1 + q^r - 1) = q^(n-r) = q^k.
Hamming codes achieve this bound and are henc "perfect".
- 10th March, 12:00-13:00.
A picture of a perfect code. Perfect codes have a uniquely
defined nearest-neighbour decoding process.
Lemma 6.6. If C is a Hamming code then every coset of C contains
a unique word of weight at most 1. This leads to a
simple trick for
decoding Hamming codes when q = 2.
Theorem 6.8: Suppose C is a code
with parity-check matrix H. C has minimum distance d
iff no set of d-1 columns of H is linearly dependent.
(Statement and one direction of the proof.)
- 13th March, 15:00-16:00.
Warm-up: use Theorem 6.8 to construct a parity-check
matrix of a [6,2,4]-code.
Theorem 6.10 (Gilbert-Varshamov bound.)
If n, r, d, q satisfy a certain inequality then an [n, n-r, d]-code
exists. (Statement and proof.)
- 17th March, 10:00-11:00.
[Exercise Sheet 8 released; deadline 31st March.]
Definition of MDS code:
simply an [n,n-r,r+1]-code. The significance of an MDS code
is that it attains the Singleton bound (indeed this could be
taken as a definition). Another way of looking at MDS codes
is via Theorem 6.8: a code is MDS if every r*r submatrix
of its parity check is non-sigular.
The trival code, parity check code and repetition codes
are MDS codes with r = 0, r = 1 and r = n-1 respectively.
Definition of a Vandermonde matrix and a proof
that it is non-singular. (The proof is non-examinable.)
- 17th March, 12:00-13:00.
Theorem 6.12(3): If r <= q then a [q+1, q-r+1, r+1]-code over F_q
exists. Proof, by explicit construction of a parity-check matrix.
Example: the parity-check matrix of a [6,3,4]-code over F_5.
Theorem 6.12(2) says that there does not exist a
[r+2,r,r+1]-code when r > q. Proof by considering the parity-check
matrix of such a code and obtaining a contradiction.
- 20th March, 15:00-16:00.
No lecture (University holiday).
- 21st March, 15:00-16:00.
No examples class (University holiday).
- 24th March, 10:00-11:00.
No lecture (University holiday).
- 24th March, 12:00-13:00.
No lecture (University holiday).
- 27th March, 15:00-16:00.
No lecture (course organiser away).
- 31st March, 10:00-11:00. Final topic: Reed-Muller codes.
Definition of the building blocks x_i(n). *-product, and construction
of the Reed-Muller code R(r,n). (NB: For this section of the lecture
notes only, r and n don't have their usual meanings! In fact, the
length of codewords will be N = 2^n.) Example: R(0,3), R(1,3),
R(2,3) and R(3,3). R(0,3) is the repetition code, R(3,3) the complete
code and R(2,3) the parity-check code of length N. Note the collection
of all N *-products are linearly independent. We'll prove this next
time.
- 31st March, 12:00-13:00.
Review of the construction of R(r,n). Observation: if i < n-1,
x_i(n) = x_i(n-1)x_i(n-1), while x_{n-1}(n) = 00...011...1 (N/2
0s and N/2 1s). Lemma 6.14: a similar statement holds for *-products
(statement and proof). Proposition 6.15: If x = x_{i_1} * ... *
x_{i_s}, where 0 <= i_1 < i_2 < ... < i_s < n, then the first 1 in
x occurs in position 1 + 2^{i_1} + 2^{i_2} + ... + 2^{i_s} (statement
and proof). We can order the *-products y_1, ..., y_{2^m} so that
y_i has its first 1 in position i. Corollary: the dimension of
R(r,n) is a sum of binomial coefficiants.
- 3rd April, 15:00-16:00.
Theorem 6.17: the minimum distance of the code R(r,n)
is 2^{n-r} (statement and proof; the proof is non-examinable).
