20.2 Gray Codes 895 MSB 4 4 XOR XOR 2 G(i） Permission is readable files LSB (a) .com or call 1-800-872- (including this one) 19881992 MSB by Cambridge 4 from NUMERICAL RECIPES IN C: server computer, tusers to make one paper e University Press. THE G(i) 2 是 Programs 1 OR ictly proh 0 XOR 0 LSB to dir (b) ART OF SCIENTIFIC COMPUTING(ISBN Figure 20.2.1.Single-bit operations for calculating the Gray code G(i)from i(a),or the inverse(b). LSB and MSB indicate the least and most significant bits,respectively.XOR denotes exclusive-or. 1881892 10-521 and 7;and so on.The brushes together then read a direct binary code for the position of the wheel. uurggoglrion 43108 The reason this method is bad,is that there is no way to guarantee that all the Numerical Recipes brushes will make or break contact exactly simultaneously as the wheel turns.Going from position 7(0111)to 8(1000),one might pass spuriously and transiently through (outside 6(0110).14 (1110).and 10(1010).as the different brushes make or break contact. North Software. Use of a Gray code on the encoding stripes guarantees that there is no transient state between 7(0100 in the sequence above)and 8(1100). Of course we then need circuitry,or algorithmics,to translate from G(i)to i. Figure 20.2.1(b)shows how this is done by a cascade of XOR gates.The idea is machine that each output bit should be the XOR of all more significant input bits.To do N bits of Gray code inversion requires N-1 steps(or gate delays)in the circuit. (Nevertheless,this is typically very fast in circuitry.)In a register with word-wide binary operations,we don't have to do N consecutive operations,but only In2 N The trick is to use the associativity of XOR and group the operations hierarchically. This involves sequential right-shifts by 1,2,4,8,...bits until the wordlength is20.2 Gray Codes 895 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 4 3 2 1 0 MSB LSB G(i) 4 3 2 1 0 i 4 3 2 1 0 MSB LSB i 4 3 2 1 0 G(i) (a) (b) XOR XOR XOR XOR XOR XOR XOR XOR Figure 20.2.1. Single-bit operations for calculating the Gray code G(i) from i (a), or the inverse (b). LSB and MSB indicate the least and most significant bits, respectively. XOR denotes exclusive-or. and 7; and so on. The brushes together then read a direct binary code for the position of the wheel. The reason this method is bad, is that there is no way to guarantee that all the brushes will make or break contact exactly simultaneously as the wheel turns. Going from position 7 (0111) to 8 (1000), one might pass spuriously and transiently through 6 (0110), 14 (1110), and 10 (1010), as the different brushes make or break contact. Use of a Gray code on the encoding stripes guarantees that there is no transient state between 7 (0100 in the sequence above) and 8 (1100). Of course we then need circuitry, or algorithmics, to translate from G(i) to i. Figure 20.2.1 (b) shows how this is done by a cascade of XOR gates. The idea is that each output bit should be the XOR of all more significant input bits. To do N bits of Gray code inversion requires N − 1 steps (or gate delays) in the circuit. (Nevertheless, this is typically very fast in circuitry.) In a register with word-wide binary operations, we don’t have to do N consecutive operations, but only ln 2 N. The trick is to use the associativity of XOR and group the operations hierarchically. This involves sequential right-shifts by 1, 2, 4, 8,... bits until the wordlength is