Lynn Batten - Linear binary codes of minimum distance

A linear binary [n, k, d]-code C is a k-dimensional subspace of V(n, 2). Here, d refers to the minimum distance of the code, which is the minimum of all Hamming distances between two distinct vectors (Hamming distance being defined as the number of positions in which two vectors differ).

A good [n, k, d]-code has small n (for fast transmission of messages), large k (to enable transmission of many messages) and large d (to correct many errors). These aims conflict, and produce the main coding theory problem which is to optimize one of the three parameters for fixed values of the other two. It turns out that maximizing n and maximizing k are equivalent problems.

If C has minimum distance d the packing radius is t=(d - 1)/2. Thus, each codeword is located at the centre of a sphere of radius t in which it is the only codeword. The best error correction is therefore achieved for largest possible t, and hence largest possible d. Thus the packing problem of covering V(n,2) with large spheres, is equivalent to maximizing d in C.

Much is known about the maximum n(k) possible when k(n) and d are fixed and d is . However, for d = 5 there are still many questions which need answers.

In this talk we review what is known for d = 4, and consider what needs to be done for d = 5.