Single-Track Gray Codes: An Efficiently Decodable Maximum Period General Construction and Extensions

Overview

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 (1)

• Second Award of $2,000 $2,000

Competition history

• ISEF 2015 Category not listed · Entry EBED056I

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.