Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Balancing cyclic R-ary Gray codes. | Balancing cyclic R-ary Gray codes Mary Flahive Department of Mathematics Oregon State University Corvallis OR 97331 USA flahive@ Bella Bose School of Electrical Engineering and Computer Science Oregon State University Corvallis OR 97331 USA bose@ Submitted Sep 26 2006 Accepted Apr 17 2007 Published Apr 27 2007 Mathematics Subject Classification 05A99 05C45 68R10 Abstract New cyclic n-digit Gray codes are constructed over 0 1 . R 1 for all R 3 n 2. These codes have the property that the distribution of the digit changes transition counts is close to uniform For each n 2 every transition count is within R 1 of the average Rn n and for the 2-digit codes every transition count is either _R2 2J or R2 2 . 1 Introduction For R n 2 an n-digit R-ary Gray code is a sequence in which each n-digit string with digits from the set 0 1 . R 1g occurs exactly once and any two consecutive strings differ in only one digit and the difference equals 1 that is the Lee distance equals 1 where the Lee distance between two n-strings is defined to be n dL ai . an bl . bn min aj - bj I R - aj - bj g . j i When the Lee distance between the last and first strings also equals 1 the code is called cyclic. For instance 10 11 01 00 and 20 21 22 12 02 01 11 10 00 1 are cyclic 2-digit R-ary Gray codes with R 2 and R 3 respectively. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R31 1 It is helpful to consider a cyclic Gray code as a Hamiltonian cycle in the R-ary n-cube the graph whose vertices are all n-strings with digits from the set 0 1 . R 1g in which two vertices are adjacent if they differ in only one digit by 1. Our usual representation of this graph will have the vertices arranged in an 1 X R array where the first n 1 digits of a vertex n-string are given by its row label and the last digit by its column label. Figure 1 has the Hamiltonian cycles for the cyclic Gray codes in 1 . Figure 1 cyclic 2-digit R-ary Gray codes for R 2 3 4. The transition .
