Comp080425.qxd The Journal of Engineering Research Vol. 6, No. 2 (2009) 12-19 1. Introduction Although many codes for example Binary Coded Decimal (BCD), Excess-3 Code, Hamming Code, Cyclic Redundancy Code (CRC), Check Sum and many others exist and are in use. But the Gray codes which are named for Frank Gray who patented the use of them in shaft encoders (Gray, 1953) due to its attribute of single dis- tance only, which avoids ambiguous switching situations, is particularly used to handle safely and conveniently the control problems. The term Gray code is sometimes used to refer to any single-distance code, that is, one in which adjacent code words differ by 1 in one digit position only, This property can be seen in Table 1 which shows the Gray codes for size n = 1 to 4 bits. Unlimited applications are accounted for the Gray code. Some of them are mentioned here as follows. However, more can be learned through the references pro vided as in the references (Sundberg, 1975; Ludman, 1981; Er, 1984, and Proskurowski and Ruskey, 1985; _____________________________________ *Corresponding author’s e-mail: afaq@squ.edu.om Lee, 1986; Conway, et al. 1989; Skiena, 1990; Press, et al. 1992; Etzion and Peterson, 1992; Hiltgen, et al. 1996; Savage, 1997; Ruskey, 1997; Guan and Dah-Jyu, 1998, Moshe and Tuvi, 1999; Black Paul 2004; Alan and Alessandro Mei, 2004; Jywe-Fei and Lai, 2005; Bitner, et al. 2005). Gray codes were applied to mathematical puzzles before they became known to engineers. The Gray code arises naturally in many situations. Gray's interest in the code was related to what we would now call analog to dig- ital conversion. The goal was to convert an integer value, represented as a voltage, into a series of pulses represent- ing the same number in digital form. The technique, as described in Gray's patent, was to use the voltage being converted to displace vertically an electron beam that is being swept horizontally across the screen of a cathode ray tube. The screen has a mask etched on it that only allows the passage of the beam in certain places; a current is generated only when the beam passes through the mask. The passage of the beam will then give rise to a series of on/off conditions corresponding to the pattern of mask holes that it passes. A Less Complex Algorithmic Procedure for Computing Gray Codes Afaq Ahmad*a and Mohammed M. Bait Suwailama *a Department of Electrical and Computer Engineering, College of Engineering, Sultan Qaboos University, P.O. Box 33, Postal Code 123, Muscat, Sultanate of Oman Received 25 April 2008; accepted 26 October 2008 Abstract: The purpose of this paper is to present a new and faster algorithmic procedure for generating the n- bit Gray codes. Thereby, through this paper we have presented the derivation, design and implementation of a newly developed algorithm for the generation of an n-bit binary reflected Gray code sequences. The developed algorithm is stemmed from the fact of generating and properly placing the min-terms from the universal set of all the possible min-terms [m0 m1 m2 …. mN] of Boolean function of n variables, where, 0 < N < 2 n-1. The resulting algorithm is in concise form and trivial to implement. Furthermore, the developed algorithm is equipped with added attributes of optimizing of time and space while executed. Keywords: Gray code, Min-terms, Boolean function, Algorithm, Processing time, Memory space, Binary …ôL RƒeQ ÜÉ°ù◊◊ G~«≤©J πbG á«eRQGƒN äGƒ£N º∏jƒ°S â«H ~ªfi h ~ªMG ¥ÉaCG ::áá°°UUÓÓÿÿGG~«dƒàd I~j~÷G á«eRQGƒÿG ΩG~îà°SG h º«ª°üJ äGƒ£Nh ¥É≤à°TG Ë~≤J ” ~≤d .»FÉæK ºbQ -¿ ºéëH …ôL RƒeQ ~«dƒàd á©jô°S I~j~L á≤jôW Ë~≤J ¤G åëÑdG Gòg ±~¡j á«æ«dƒÑdG ádG~∏d áeÉ©dG Oh~◊G áYƒªÛG iô¨°üdG Oh~ë∏d ™bGƒŸG QÉ«àNG h ~«dƒJ á≤«≤M øe á°ùÑà≤e IQƒ£ŸG á«eRQGƒÿG ¿EG .»FÉæK ºbQ -¿ ºéM äGPh á°ùµ©æŸG …ôL õeQ á∏°ù∏°S πbCG ¬e~îà°ùe IôcGòH h π° aCG ò«ØæJ øeR äGP ’ƒ∏M èàæJ IQƒ£ŸG á≤jô£dG ¿CG ¤EG áaÉ°VEÓH Gòg .≥«Ñ£à∏d á∏HÉb ᨫ°üH ÓM áŒÉædG á≤jô£dG »£©J .Ò¨àe ¿ øe áfƒµàŸG ádG~∏d .ɪéM áá««MMÉÉààØØŸŸGG ääGGOOôôØØŸŸGG.»FÉæãdG ΩɶædG ,IôcGòdG ºéM ,ò«ØæàdG øeR ,äÉ«eRQGƒÿG ,á«æ«dƒÑdG ádG~dG ,iô¨°üdG Oh~◊G ,…ôL õeQ : 13 The Journal of Engineering Research Vol. 6, No. 2 (2009) 12-19 Mechanical position sensors use Gray code to convert the angular position (angle-measuring devices) of a shaft to digital form. Gray codes were used in telegraphy. The Gray code also forms a Hamiltonian cycle on a hypercube, where each bit is seen as one dimension. In data transmis- sion, Gray codes play an important role in error detection and correction. Solving puzzles such as the Tower of Hanoi and the Brain, the study of bell-ringing, analog-dig- ital signal conversion, classifying of Venn diagrams, con- tinuous space-filling curves, enhancing the resolution of spectrometer for a satellite application, labeling the axes of Karnaugh maps are the processes where Gray codes are used due to its uniqueness. Gray codes are also beneficial in Genetic Algorithms due to its incremental change prop- erty. Using Gray codes for addressing the memory results in saving of the power because a few address lines change as the program counter advances to the next location. Also, Gray codes are extensively used by digital system designers for passing multi-bit count information between synchronous logic that operates at different clock frequen- cies. In some numerical problems, Gray codes can be use- ful in situations of looping over many values of a bit. Furthermore, due to its attribute Gray code could be a good choice for the search of the optimal test-sequences in digital system testing. Hence it can be said that the Gray codes which were originally designed to prevent spurious output from electromechanical switches. Today they are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems. Since the Gray code has enormous applications as men- tioned above has many facet researches as is evident in surveying the literature (Gray, 1953; Sundberg, 1975; Ludman, 1981; Lee, 1986; Conway, et al. 1989; Skiena, 1990; Press, et al. 1992; Etzion Peterson, 1992; Hiltgen, et al. 1996; Savage, 1997; Ruskey, 1997; Guan Dah-Jyu, 1998, Moshe and Tuvi, 1999; Black Paul 2004; Alan and Alessandro Mei, 2004; Jywe-Fei and Lai, 2005; Bitner, et al. 1976; Er, 1984; Proskurowski and Ruskey, 1985; Ruskey, 1993; Dominique, 2000; Lassing, et al. 2003, Goddyn and Gvozdjak 2003 and Vajnovszki and Walsh 2006). It is clear through the literature survey that there had been much discovered and written about the Gray code; it is associated with many elegant circuits and algo- rithms. However, the algorithms generating the Gray code was still done with the crude techniques (Ruskey, 1993; Dominique, 2000; Lassing, et al. 2003, Goddyn, Gvozdjak 2003 and Vajnovszki and Walsh 2006). Researches are available in the literature only to script the faster codes but not much deviated from the existing crude algorithms for generating the Gray codes. This paper pres- ents a new concept of generating the Gray code of n-bit size. The developed algorithm is stemmed from the fact of generating and properly placing the min-terms from the universal set of all the possible min-terms (m0 m1 m2 …. mN) of Boolean function of n variables, where, 0 < N < 2n-1. The resulting algorithm is in concise form and triv- ial to implement. We designed an efficient algorithm to write the codes which reduces the processing time and memory space requirements. 2. Gray Code Conversion - Conventional Approaches No doubt, a simple recursive equation in mod (2) oper- ation can convert a simple binary -…-8-4-2-1 codes to the Gray one. The hardware is also simple which is based on the bank of Exclusive-OR gates. To make the content of this paper more readable to audience the description of the generation procedure of the Gray code is given below: To convert a binary number [bn-1 bn-2 …. b1 b0] to its corresponding Gray code (gn-1 gn-2 …. g1 g0), start at the left with the bit bn-1 (the nth, most significant bit) and use the following recursive equations. gn-1 = bn-1 (1) (2) Or, in general for ith bit where i varies as, 2 < i < n, the following Eq. (3) can be used. (3) The above Eqs. (1) and (3) are illustrated for a 3-bit Gray code encoder in an example below. Example 1: Let a Binary code [b3 b2 b1] = [1 0 0]. Base 10 Binary code Gray code 4-bit Gray code 3-bit Gray code 2-bit Gray code 1-bit 0 0000 0000 000 00 0 1 0001 0001 001 01 1 2 0010 0011 011 11 3 0011 0010 010 4 0100 0110 110 5 0101 0111 111 6 0110 0101 101 7 0111 0100 100 8 1000 1100 9 1001 1101 10 1010 1111 11 1011 1110 12 1100 1010 13 1101 1011 14 1110 1001 15 1111 1000 Table 1. Gray code patterns of size n = 1 to 4 bits gn-2 = bn-1 ⊕ bn-2 gn-I = bn-i+1 ⊕ bn-I So, g3 = b3 = 1; g2 = b3 ⊕ b2 = (1 + 0) mod 2 =1; g1 = b2 ⊕ b1 = (0 + 0) mod 2 = 0. Therefore, Binary code [b3 b2 b1] = [1 0 0] when encoded in Gray code gives [g3 g2 g1] = [1 1 0]. 14 The Journal of Engineering Research Vol. 6, No. 2 (2009) 12-19 The derivation of the generalized Eqs. (1) - (3) can be computed as below. From Table 1 above, a set of the following Boolean functions expressed in the form of min-terms Σ mi where i varies from 0 to 7, can be derived as: g3 (b3, b2, b1) = Σ (m4, m5, m6, m7) (4) g2 (b3, b2, b1) =Σ (m2, m3, m4, m5) (5) g1 (b3, b2, b1) = Σ (m1, m2, m5, m6) (6) The minimized version of above Boolean functions using the K-maps and hence the implementations of those minimized functions are as given in Figs. 1 and 2 respec- tively. Similarly, the reversal of Gray code bits [gn gn-1 … g2. g1] again into -…-8-4-2-1 weighted binary code bits [bn bn-1 … b2. b1] can be performed by using the equations as given below: bn = g n (7) (8) . . (9) Or, in general, to compute the binary code bits bn-1, … , b2, and. b1 the following recursion equation can be used where, i varies from 1 to n-1. (10) Example 2: Let a Gray code [g3 g2 g1] = [1 1 0]. The derivation of the generalized Eqs. (7) - (10) can be easily computed as: From Table 1 above, a set of the following Boolean functions expressed in the form of min-terms Σ mi where i varies from 0 to 7, can be derived as: b3 (g3, g2, g1) = Σ (m4, m5, m6, m7) (11) b2 (g3, g2, g1) = Σ (m2, m3, m4, m5) (12) b1 (g3, g2, g1) = Σ (m1, m2, m4, m7) (13) The above Boolean functions can be minimized using the K-maps as demonstrated below (see Fig. 3). Whereas, the implementation of those minimized Boolean functions is shown in Fig. 4. Since the Gray code encoder needs first to obtain the Figure 1. K-maps and minimized Boolean functions for g3, g2 and g1 G3 G2 G1 B3 B2 B1 MSB LSB Figure 2. A 3-bit Binary to Gray Converter Circuit b1 = b2 ⊕ g1 bn-i = bn-i+1 ⊕ gn-i So, b3 = g3 = 1; b2 = b3 ⊕ g2 = (1 + 1) mod 2 =0 ; b1 = b2 ⊕ g1 = (0 + 0) mod 2 = 0. Therefore, Gray code [g 3 g2 g1] = [1 0 0] when encoded in Binary code [b3 b2 b1] gives = [1 1 0]. bn-1 = bn ⊕ gn-1 15 The Journal of Engineering Research Vol. 6, No. 2 (2009) 12-19 binary data (through a binary counter) before generating the Gray code. This process requires 2-stages as shown in Fig. 5. Thus, it is imperative to derive a mechanism to avoid this situation which needs much time and space to implement. The ensuing section is a consequence to it. 3. Computing Gray Codes - Proposed Methodology If we look to the Table 2 and 3 which lists the Gray codes, respective min-terms and equivalent decimals for n = 1 to 6 forced us to derive the following conclusions. 1. Gray code of size n has a specific pattern relationship between min-terms of the Gray code of its predeces- sor code of size n-1. 2. The Gray code of size n can be directly scripted using the n-bit K-map where the min-terms cells are to be read clock-wise and down to the row as explained in the Fig. 6. The example of Fig. 6 is a 4-variable K-map used to Figure 3. K-maps and minimized Boolean functions for b3, b2 and b1 B3 B2 B1 G3 G2 G1 MSB LSB Figure 4. A 3-bit Gray to Binary converter circuit CLK Binary Counter Binary to Gray Converter Figure 5. Black model of Binary to Gray code conversion Table 2. Decimal, Gray code, and (min-terms): For, n = 1 to 5 16 The Journal of Engineering Research Vol. 6, No. 2 (2009) 12-19 generate Gray code which reads as [m0 m1 m3 m2 m6 m7 m5 m4 m12 m13 m15 m14 m10 m11 m9 m8]/. The derivation 2 is not feasible since generating the K-map for higher vari- ables are difficult to manipulate. Therefore, the derivation 1 is the point of our work. 4. Proposed Algorithm The following Eqs. (14) to (18) describe the Gray codes for bit size 1 to 5 respectively. A specific relation between the min-terms patterns is visible and summarized in the form of a theorem below: G(1) = [m0 | m1]/ (14) G(2) = [m0 m1 | m3 m2]/ = [G(1); [m3 m2]/] (15) G(3) = [m0 m1 m3 m2 | m6 m7 m5 m4]/ = [G(2); [m6 m7 m5 m4]/] (16) G(4) = [m0 m1 m3 m2 m6 m7 m5 m4 | m12 m13 m15 m14 m10 m11 m9 m8]/ = [G(3); [m12 m13 m15 m14 m10 m11 m9 m8]/ (17) G(5)SETI = [m0 m1 m3 m2 m6 m7 m5 m4 m12 m13 m15 m14 m10 m11 m9 m8]/ = G(4) G(5)SET II = [m24 m25 m27 m26 m30 m31 m29 m28 m20 m21 m23 m22 m18 m19 m17 m16]/ G(5) = [G(4); [m24 m25 m27 m26 m30 m31 m29 m28 m20 m21 m23 m22 m18 m19 m17 m16]/] (18) Theorem 1: G (n) is a matrix of order 2n x n in binary format of n- bit forming 2n min-terms of n variables. By analyzing the patterns we reach to the conclusion that G(n) can be obtained first by writing the min-terms of G(n-1) then appending the min-terms by advancing each of the min- terms starting from the last to the first by a value of 2n-1. Proof: Proof is as visible through the Eqs. from (14) to (18). An algorithm is designed on the basis of the study of Theorem 1 and is as given below. Algorithm STEP 0: START by inputting the bit size (n) of the Gray code to be generated; STEP 1: Initialize a vector V = [0 1]; STEP 2: Count a loop for k = 1 to n; STEP 3: Check that k = n or not, if YES GO TO STEP 8; STEP 4: Increment the counter k by 1 i.e. k = k +1; STEP 5: Deci mal Gray code (m) Deci mal Gray code (m) 0 000000 (m 0) 48 110000 (m 48) 1 00001 (m 1) 49 110001 (m 49) 3 000011 (m 3) 51 110011 (m 51) 2 000010 (m 2) 50 110010 (m 50) 6 000110 (m 6) 54 110110 (m 54) 7 000101 (m 7) 55 110111 (m 55) 5 000101 (m 5) 53 110101 (m 53) 4 000100 (m 4) 52 110100 (m 52) 12 001100 (m 12) 60 111100 (m 60) 13 001101 (m 13) 61 111101 (m 61) 15 001111 (m 15) 63 111111 (m 63) 14 001110 (m 14) 62 111110 (m 62) 10 001010 (m 10) 58 111010 (m 58) 11 001011 (m 11) 59 111011 (m 59) 9 001001 (m 9) 57 111001 (m 57) 8 001000 (m 8) 56 111000 (m 56) 24 011000 (m 24) 40 101000 (m 40) 25 011001 (m 25) 41 101001 (m 41) 27 011011 (m 27) 43 101011 (m 43) 26 011010 (m 26) 42 101010 (m 42) 30 011110 (m 30) 46 101110 (m 46) 31 011111 (m 31) 47 101111 (m 47) 29 011101 (m 29) 45 101101 (m 45) 28 011100 (m 28) 44 101100 (m 44) 20 010100 (m 20) 36 100100 (m 36) 21 010101 (m 21) 37 100101 (m 37) 23 010111 (m 23) 39 100111 (m 39) 22 010110 (m 22) 38 100110 (m 38) 18 010010 (m 18) 34 100010 (m 34) 19 010011 (m 19) 35 100011 (m 35) 17 010001 (m 17) 33 100001 (m 33) 16 010000 (m 16) 32 100000 (m 32) Table 3. Decimal, Gray code, and (min-terms): For, n = 6 Figure 6. A 4-variable K-map 17 The Journal of Engineering Research Vol. 6, No. 2 (2009) 12-19 For i = 0 to 2n-1-1; Vi = [V(2n-1-i) + 2n-1]; STEP 6: Modify vector V as V = [V, Vi]; STEP 7: GO TO STEP 3; STEP 8: Transpose V i.e. V/; STEP 9: STEP 10: Output G(n); STEP 11: STOP A Debug Example: Example 3: To elaborate the computing of variables in the above mentioned steps a debug test of the above algorithm is car- ried out for n = 3 and is presented below in Table 4. 5. Implementation of Algorithm The above designed algorithm is implemented using the MATLAB code. The out put of the m-file with the name "gray_generator_proposed" can be visualized as shown in Fig. 7. A sample output of the program shown in the figure is only for n = 4. This is provided just to make it more readable, otherwise the output for the higher val- ues of n will require much space to present. Similarly, we also encoded the conventional method of Gray code con- version into MATLAB script. To compare the efficiency amongst these two approaches we run both of the pro- grams for n = 2 to 10 and some of the results are present- ed and made available through Figs. 8 to 9 in the ensuing section below. >>gray_generator_proposed Please enter a valid positive integer ( > 1) : 4 Gran output (s) =================== 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 1 Convert V / into binary format i.e. (V /)10 → (V/)2 = Gray code of n -bit size i.e. a matrix G (n) of size (N+1) by n; i Vi V (V /)base 2 - [0 1] - 0 to 1 [3 2] [0 1 3 2] - 0 to 3 [6 7 5 4] [0 1 2 3 6 7 5 4] - 000 001 011 010 110 111 101 100 Table 4. A debug test of algorithm for, n = 3 2 3 4 5 6 7 8 9 10 0 0.5 1 1.5 2 2.5 x 10 5 n-bits M e m o ry s p a c e Our propos ed Method Conventional Method Figure 8. Memory requirements comparison 2 3 4 5 6 7 8 9 10 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 n-bits R e la ti v e E rr o r Figure 9. Relative error judgment 18 The Journal of Engineering Research Vol. 6, No. 2 (2009) 12-19 Elapsed time is 0.000000 seconds. Figure 7. MATLAB command window output 6. Results MATLAB 7.0 on a P 4 CPU 1.5 GHz, 512 MB of RAM is used as the bench marks for testing the codes for both of the computing methodologies. The processing time and memory space required to implement both of the pro- grams (the conventional and the proposed one) are record- ed while running the programs. The results for a subset of the study, for n = 2 to 10 where the memory requirement comparison of the con- ventional approach of Gray code converter and the pro- posed approach is presented in Fig. 8. The memory requirement is mapped in bytes. Further, to judge the effi- ciency of the proposed algorithm, a relative error plot is shown in Fig. 9. With respect to the memory require- ments, the behavior of the relative error shown in Fig. 9, demonstrates almost an exponential characteristic except for n = 2. And, this exception for (n = 2) is because of that the implementing the Gray code generator using conven- tional approach requires significant more memory space than the proposed approach of generating the Gray codes for n = 2. The run time requirements comparison is demonstrated through Fig. 10. 7. Conclusions A time space optimal algorithmic procedure to gener- ate Gray code-words of any bit length n is presented through this paper. The comparative study reveals that the proposed approach is not only faster but also, requires about 25% less memory space on average while compared with the conventional method of Gray code-word genera- tion technique. Since Gray code is widely used for on line system monitoring hooked with sensors and with on board systems and hence these two parameters (space and time requirements) are very critical in these applications. Therefore this proposed algorithmic procedure is more advantageous. 8. References Alan, A., Bertossi, Alessandro, Mei., 2004, "Time and Work Optimal Simulation of Basic Reconfigurable Meshes on Hypercubes," J. of Parallel and Distributed Computing, Vol. 64(1), pp.173 - 180. Bitner, J., Ehrlich, G. and Reingold, E., 1976, 'Efficient Generation of the Binary Reflected Gray Code and its Applications," Communications of the ACM, Vol. 19(9), pp. 517-521. Black Paul, E., (2004), "Gray Code," NIST National Institute of Standards and Technology. Conway, J., Sloane, N. and Wilks, A., 1989, "Gray Codes and Reflection Groups," Graphs and Combinatorial, Vol. 5, pp. 315-325. Dominique Roelants van Baronaigien., 2000, "A Loopless Gray-Code Algorithm for Listing K-Array Trees," J. of Algorithms, Vol. 35(1), pp.100-107. Er, M.C., 1984, "On Generating the N-Array Reflected Gray Codes," IEEE transactions on computers, Vol. 33, pp. 739-741. Etzion, T., Paterson, K.G., 1996, "Near Optimal Single- Track Gray Codes," IEEE Trans. on Information Theory, Vol. 42(3), pp. 779-789. Goddyn, L., Gvozdjak, P., 2003, "Binary Gray Codes with Long Bit Runs," Electron. J. Combin. Vol. 10, pp. 1- 10. Gray, F., 1953, "Pulse Code Communication," United States Patent Number 2, 632, 058. Guan Dah-Jyu., 1998, "Generalized Gray Codes with Applications," Proceeding National Science Council of Republic of China, Vol. A(22), pp. 841 - 848. Hiltgen, P., Paterson, K. G. and Brandestini, M., 1996, "Single-Track Gray Codes," IEEE Trans. on Information Theory, Vol. 42(5), pp. 1555-1561. Jywe-Fei Fang , Kuan-Chou Lai, 2005, "Embedding the Incomplete Hypercube in Books," Information Processing Letters, Vol. 96(1), pp. 1-6. Lassing, E. G. Strom, T., Ottosson. and Agrell, E., (2003), "Computation of the Exact Bit Error rate of Coherent M-array PSK with Gray Code Bit Mapping," IEEE Transactions on Communications, Vol. 51(11), pp. 1758-1760. Lee, P. J., 1986, "Computation of the Bit Error Rate of Coherent M-array PSK with Gray Code Bit Mapping," IEEE Transactions on Communications, Vol. COM-34(5), pp. 488-491. Ludman, J. E., 1981, "Gray Code Generation for MPSK Signals," IEEE Transactions on Communications, Vol. COM-29(10), pp. 1519-1522. Moshe Schwartz and Tuvi Etzion, 1999, "The Structure of Single-Track Gray Codes," IEEE Transactions on Information Theory, Vol. 45(7), pp. 2383 - 2396. Figure 10. Run time requirements comparison 19 The Journal of Engineering Research Vol. 6, No. 2 (2009) 12-19 Press, W.H., Flannery, B.P., Teukolsky, S. A. and Vetterling, W.T., 1992, "Gray Codes, Numerical Recipes in Fortran," Cambridge, England: Cambridge University Press, pp. 886-888. Proskurowski, A. and Ruskey, F., '1985, "Binary Tree Gray Codes," J. Algorithms 6, pp. 225-238. Ruskey, F., 1997, "A Survey of Venn Diagrams," Elec. J. of Comb, a special issue. Ruskey, F., 1993, "Simple Combinatorial Gray Codes Constructed by Reversing Sub-lists," Proceedings of the 4th International Symposium on Algorithms and Computation, p. 201-208, December 15-17. Savage, Carla., 1997, "A Survey of Combinatorial Gray Codes," Society of Industrial and Applied Mathematics Review, Vol. 39, pp. 605-629. Skiena, S., 1990, "Gray Code, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica," Reading, MA: Addison-Wesley, pp. 42-43 and 149. Sundberg, C. E., 1975, "Bit Error Probability Properties of Gray-coded M.P.S.K Signals," IEE Electronics Letters, Vol. 11(22), pp. 542-544. Vajnovszki, V. and Walsh, T.R., 2006, "A Loop-free two-