Dartmouth College Computer Science
Technical Report series
|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:||2020, 2019, 2018, 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|
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.
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.