Booth Id:
EBED056I
Category:
Year:
2015
Finalist Names:
Botev, Georgie
Abstract:
Gray codes are sequences of binary codewords with numerous applications in telecommunications, robotics, error correction, and graph theory. Single-track Gray codes are a subclass of Gray codes that are represented as a single binary vector. Previously studied constructions investigated reading heads with even spacing. These codes can be constructed from a seed code, but for bit-lengths greater than 18, little is known. A general construction for odd bit-lengths n with a period approaching 2n^2-4n was presented from an investigation of Lyndon words. An optimized brute force algorithm that checked for the Gray property in all permutations of Lyndon words was introduced. This approach, which was implemented in Java, significantly reduced runtime by fast-forwarding through many invalid arrangements as they were found and can be easily adapted to other permutation searches. For a bit-length of seven, all 112 valid seed codes were presented. A general construction for single-track Gray codes was introduced, and the resulting codes yielded an optimal, 2^n distinct codewords. Non-evenly spaced reading heads were utilized, and the use of logical bitwise operators made decoding efficient.
Awards Won:
Second Award of $2,000