Đ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 ngành toán học tạp chí toán học quốc tế đề tài: Balanced Gray Codes. | Balanced Gray Codes Girish S. Bhat Department of Computer Science North Carolina State University Raleigh NC 27695-8206 gsbhat1@eos.ncsu.edu Carla D. Savage Department of Computer Science North Carolina State University Raleigh NC 27695-8206 cds@cayley.csc.ncsu.edu Submitted June 3 1996 Accepted August 28 1996. Abstract It is shown that balanced n-bit Gray codes can be constructed for all positive integers n. A balanced Gray code is one in which the bit changes are distributed as equally as possible among the bit positions. The strategy used is to prove the existence of a certain subsequence which will allow successful use of the construction proposed by Robinson and Cohn in 1981. Although Wagner and West proved in 1991 that balanced Gray code schemes exist when n is a power of 2 the question for general n has remained open since 1980 when it first attracted attention. 1 Introduction An n-bit binary Gray code is an exhaustive listing of n-bit strings in which successive strings differ in exactly one bit position. Alternatively an n-bit binary Gray code can be viewed as a Hamilton path in the n-cube and a cyclic binary Gray code as a Hamilton cycle. One such cyclic Gray code the Binary Reflected Gray Code BRGC was patented by Frank Gray 1 as a solution to a communications problem involving digitization of analogue data. Since Supported in part by NSF grant DMS9302505 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R25 2 then binary Gray codes have been used in a wide variety of other applications including databases experimental design and puzzle solving 4 5 6 7 8 . As discussed for example in 7 the BRGC scheme though sufficient to solve the communications problem is not adequate for certain other applications because of its lack of uniformity . The term uniformity refers to the manner in which the bits change in the Gray code. Several different measures of uniformity and techniques to construct Gray codes satisfying these measures have been proposed in literature.
