Booth Id:
MATH004
Category:
Mathematics
Year:
2021
Finalist Names:
Tsei, Tsz Tung (School: Maryknoll Fathers' School)
Abstract:
The goal of this project is to do fundamental research on Gray codes and develop a new algorithm to determine a Gray code given its corresponding decimal number. A Gray code sequence is a set of 2^n n-bit binary numbers, where only one bit changes between consecutive elements. Gray codes are used in our everyday lives in a wide range of applications, primarily in reducing errors with data transmission. Emerging applications in GPS location recognition or autonomous driving, can help improve accuracy and security, and thus reduce accidents.
This novel algorithm converts from decimal numbers to Gray code, the only direct method to not involve binary as an intermediate. The quickest methods of generating Gray codes is mirror method which involving binary and requiring the generation of almost the entire sequence up until the desired number. Our algorithm can directly output the value of any particular bit of the Gray code from decimal, without involving binary or recursion.
This project incorporates the Chinese rings puzzle bridge between decimal and Gray code. Treating each ring as a bit, the n-bit Gray code sequence is the concatenation of the reversed solutions of the n-Chinese Rings and non-reversed solutions of the (n-1)-Chinese rings. A special pattern was obtained by viewing the sequence vertically. Through the lens of the Chinese rings mechanism, where possible movements of the bits are limited, we derived several formulae which have never appeared in any journals that have assisted in deriving our new algorithm. We further validated the algorithm by fitting it to the Gros sequence.
By performing empirical run-time studies on the existing methods, we show that this new algorithm is the most efficient way to generate a Gray code from a specified decimal number.
Awards Won:
Shanghai Youth Science Education Society : Science Seed Award
Innopolis University : Full tuition scholarships for the Bachelor program in Computer Science