Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: A simple proof for the existence of exponentially balanced Gray codes. | A simple proof for the existence of exponentially balanced Gray codes I Nengah Suparta Department of Applied Mathematics Faculty of Electrical Engineering Mathematics and Computer Science Delft University of Technology . BOX 5031 2600 GA Delft The Netherlands Submitted Apr 21 2005 Accepted Sep 9 2005 Published Oct 13 2005 Mathematics Subject Classifications 94A05 94A12 94A15 94C30 Abstract A Gray code of length n is a circular list of all 2n bitstrings or binary codewords of length n such that successive codewords differ in only one bit position. The frequencies of the positions where these differences occur are called transition counts. An exponentially balanced Gray code is a Gray code the transition counts of which are all the same power of two or are two successive powers of two. A proof for the existence of exponentially balanced Gray codes is derived. The proof is much simpler than an earlier proof presented by van Zanten and Suparta Discrete Analysis and Operation Research 11 2004 81-98 Russian Journal . Keywords Gray codes exponentially balanced Gray codes transition count spectrum. 1 Introduction A Gray code G n of length n is a circular list of all 2n bitstrings or binary codewords of length n such that successive codewords differ in one bit position. The frequencies of the positions where these differences occur are called transition counts in 2 4 11 . If a Gray code is such that any two transition counts differ at most two one says that this Gray code is balanced and it is called totally balanced or uniform if all its transition counts are equal cf. 2 11 . The transition counts can be called exponentially close if they are all the same power of two or are all two consecutive powers of two. We call a Gray code On leave from Dept. of Mathematics IKIP Negeri Singaraja Bali - Indonesia THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 N19 1 with this property an exponentially balanced Gray code cf. 10 as a generalization of totally
