Booth Id:
MATH025T
Category:
Mathematics
Year:
2020
Finalist Names:
Tsei, Tsz Tung (School: Maryknoll Fathers' School)
Tsui, Ho Yin (School: Maryknoll Fathers' School)
Abstract:
A Gray Code sequence is a set of 2^n binary numbers in which only one bit changes between two consecutive elements and this property helps in reducing errors in data transmission in hardware. A few methods are available to generate Gray Code, like XOR which must first include the conversion from decimal number to binary numbers then using XOR process or the use of mirroring method which is only efficient for generating the whole set of Gray Code sequence. This project introduces a new algorithm in which conversion can be directly changed from a decimal number to Gray Code. It does not involve calculating the previous sequence and no recursive function.
The new algorithm generates Gray Code in a more effective way by using the idea of Chinese Ring - Double Chinese Ring Algorithm. The double Chinese Ring algorithm can be viewed as two parts, the first part being a reversed solution of nth rings Chinese Ring, the second part is the non-reversed solution of (n-1)th rings Chinese Ring. There are four unique formulae created and the algorithm further fits into the Gros Sequence to ensure correctness and completeness.
By writing computer programs for existing methods, the running time of the new algorithm is 50% faster than the Chinese Ring method. Hence, our new algorithm is most effective one in all the existing method .