Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@math.oregonstate.edu Bella Bose School of Electrical Engineering and Computer Science Oregon State University Corvallis OR 97331 USA bose@eecs.oregonstate.edu 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 .
