prob036: Fixed Length Error Correcting Codes

proposed by Alan Frisch, Chris Jefferson, and Ian Miguel
frisch@cs.york.ac.uk, caj@cs.york.ac.uk, ianm@cs.york.ac.uk

Specification

A fixed length error correcting code C of length n over an alphabet F is a set of strings from Fn. Given two strings from Fn we can define the distance between them. The most commonly used distance is the Hamming distance, defined as the number of positions where the strings differ. Using this we define the minimum distance of C as the minimum of the distances between distinct pairs of strings from C.

There are a number of other distances which can be used, for example the 'Lee distance'. When F={0,1,...,n-1} the Lee distance between a,b in F is defined as min(|a-b|,n-|a-b|). For two vectors x and y defined over Fn, the Lee distance is calculated by summing the lee distance of the pairs xi, yi. Most commonly F={0,1,2,3} as this case proves useful in a number of areas.