Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Dense Gray Codes in Mixed Radices
Jessica C. Fan
Dartmouth TR2017-818

Abstract: The standard binary reflected Gray code describes a sequence of integers 0 to n-1, where n is a power of 2, such that the binary representation of each integer in the sequence differs from the binary representation of the preceding integer in exactly one bit. In September 2016, we presented two methods to compute binary dense Gray codes, which extend the possible values of n to the set of all positive integers while preserving both the Gray-code property such that only one bit changes between each pair of consecutive binary numbers, and the density property such that the sequence contains exactly the n integers 0 to n-1. The first of the two methods produces a dense Gray code that does not have the cyclic property, meaning that the last integer and the first integer of the sequence do not differ in exactly one bit. The second method, based on the first, produces a cyclic dense Gray code if n is even. This thesis summarizes our previous work and generalizes the methods for binary dense Gray codes to arbitrary radices that may either be a single fixed radix for all digits or mixed radices where each digit may be represented in a different radix. We show how to produce a non-cyclic mixed-radix dense Gray code for any set of radices and any positive integer n---that is, a permutation of the sequence <0,1,...,n-1> such that the digit representation of each number differs from the digit representation of the preceding number in only one digit, and the values of the digits that differ is exactly 1. To this end, we provide a simple formula to compute each digit of each number in the permutation in constant time. Though we do not provide such a formula to generate the digits of a cyclic mixed-radix dense Gray code, we do present, for n equal to the product of the radices, a recursive algorithm that computes the entire cyclic mixed-radix Gray code with the density, strict Gray-code, and modular cyclic properties: given a k-tuple of mixed radices r = (r_(k-1),r_(k-2),…,r_0), each of the n integers in the cyclic mixed-radix Gray code differs from its preceding integer—with the first integer differing from the last integer---in only one digit position i, and the values of those digits differ by exactly 1, except for the digits of the first and last numbers, which may also be the integers 0 and r_i-1. For values of n that are less than the product of the radices, we show a list of cases for which we prove it is impossible to generate a mixed-radix dense Gray code that has the modular Gray-code and cyclic properties for a set of mixed radices r and a positive integer n.

Note: Senior Honors Thesis. Advisor: Thomas H. Cormen


Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Jessica C. Fan, "Dense Gray Codes in Mixed Radices." Dartmouth Computer Science Technical Report TR2017-818, March 2017.

Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.