f20-2

886 Chapter20. Less-NumericalAlgorithmsSample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).if (i.gt.20) maxexp=maxexp-1 if (a.ne.y) maxexp=maxexp-2 xmax=one-epsneg if (xmax*one.ne.xmax) xmax=one-beta*epsnegxmax=xmax/(beta*beta*beta*xmin) i=maxexp+minexp+3 do 12j=1,i if (ibeta.eq.2) xmax=xmax+xmaxif (ibeta.ne.2) xmax=xmax*beta enddo 12 return END Some typical values returned by macharare given in the table, above. IEEE- compliantmachinesreferredto in the table includemost UNIX workstations(SUN,DEC, MIPS), and Apple Macintosh IIs. IBM PCs with floating co-processors are generally IEEE-compliant, except that some compilers underflow intermediate resultsungracefully,yielding irnd =2ratherthan 5. Notice,asinthecaseofaVAX (fourthcolumn),thatrepresentationswith a “phantom”leading1bit in the mantissa achievea smaller epsfor the same wordlength,but cannot underflowgracefully. CITED REFERENCES AND FURTHER READING: Goldberg, D. 1991, ACM Computing Surveys , vol. 23, pp. 5–48. Cody, W.J. 1988, ACM Transactions on Mathematical Software , vol. 14, pp. 303–311. [1] Malcolm, M.A. 1972, Communications of the ACM , vol. 15, pp. 949–951. [2] IEEE Standard for Binary Floating-Point Numbers , ANSI/IEEE Std 754–1985 (New York: IEEE, 1985). [3] 20.2 Gray Codes A Gray code is a function G(i)of the integers i, that for each integer N≥0 is one-to-one for 0≤i≤2N−1, and that has the following remarkable property: Thebinaryrepresentationof G(i)and G(i+1 )differinexactlyonebit . Anexample of a Gray code (in fact, the most commonly used one) is the sequence 0000, 0001,0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, and 1000, for i=0 ,..., 15. The algorithm for generating this code is simply to form the bitwise exclusive-or (XOR) of iwith i/2(integer part). Think about how thecarriesworkwhenyouaddonetoanumberinbinary,andyouwillbeabletosee whythisworks. Youwillalsoseethat G(i)and G(i+1 )differinthebitpositionof the rightmost zero bit of i(prefixing a leading zero if necessary). The spellingis “Gray,”not“gray”: Thecodes are namedafter oneFrankGray, whofirstpatentedtheideaforuseinshaftencoders. Ashaftencoderisawheelwithconcentric coded stripes each of which is “read” by a fixed conducting brush. The idea is to generate a binary code describing the angle of the wheel. The obvious, but wrong, way to build a shaft encoder is to have one stripe (the innermost, say)conducting on half the wheel, but insulating on the other half; the next stripe is conducting in quadrants 1 and 3; the next stripe is conducting in octants 1, 3, 5, and 7; and so on. The brushes together then read a direct binary code for the position of the wheel. 20.2Gray Codes 887Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).4 3 2 10MSB LSBG(i)4 3 2 10i4 3 2 10MSB LSBi4 3 2 10G(i) (a) (b)XOR XOR XOR XOR XORXOR 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 signi ficant bits, respectively. XOR denotes exclusive-or. The reason this method is bad, is that there is no way to guarantee that all the brusheswillmakeorbreakcontact exactlysimultaneouslyasthewheelturns. Going fromposition7(0111)to8(1000),onemightpassspuriouslyandtransientlythrough 6 (0110), 14 (1110), and 10 (1010), as the different brushes make or break contact. UseofaGraycodeontheencodingstripesguaranteesthatthereis notransientstatebetween 7 (0100 in the sequence above) and 8 (1100). Of course we then need circuitry, or algorithmics, to translate from G(i)toi. 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 signi ficant input bits. To do Nbits of Gray code inversion requires N−1steps (or gate delays) in the circuit. (Nevertheless, this is typically very fast in circuitry.) In a register with word-wide binary operations, we don ’th a v et od o Nconsecutive operations, but only ln 2N. The trick is to use the associativity of XOR and groupthe operationshierarchically.This involves sequential right-shifts by 1,2,4,8,...bits until the wordlength is exhausted. Here is a piece of code for doing both G(i)and its inverse. 888 Chapter20. Less-NumericalAlgorithmsSample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).FUNCTION igray(n,is) INTEGER igray,is,n F o rz e r oo rp o s i t i v ev a l u e so f is, return the Gray code of n;i fisis negative, return the inverse Gray code of n. INTEGER idiv,ish if (is.ge.0) then This is the easy direction! igray=ieor(n,n/2) else This is the more complicated direction: In hierarchical stages, starting with a one-bit right shift, cause each bit to be XORed with all more significant bits.ish=-1 igray=n 1 continue idiv=ishft(igray,ish)igray=ieor(igray,idiv) if(idiv.le.1.or.ish.eq.-16)return ish=ish+ish Double the amount of shift on the next cycle. goto 1 endif returnEND In numerical work, Gray codes can be useful when you need to do some task thatdependsintimatelyonthebitsof i,loopingovermanyvaluesof i. Then,ifthere are economies in repeating the task for values differing by only one bit, it makes sense to do things in Gray code order rather than consecutive order. We saw an example of this in §7.7, for the generation of quasi-random sequences. CITED REFERENCES AND FURTHER READING: Horowitz,P., andHill,W.1989, TheArtofElectronics ,2nded.(NewYork:CambridgeUniversity Press), §8.02. Knuth, D.E. Combinatorial Algorithms , vol. 4 of The Art of Computer Programming (Reading, MA: Addison-Wesley), §7.2.1. [Unpublished. Will it be always so?] 20.3 CyclicRedundancy and Other Checksums When you send a sequence of bits from point A to point B, you want to know that it will arrive without error. A common form of insurance is the “parity bit, ” attached to 7-bit ASCII characters to put them into 8-bit format. The parity bit is chosen so as to make the total number of one-bits (versus zero-bits) either alwayseven(“evenparity ”)oralwaysodd( “oddparity ”). Anysinglebit errorinacharacter will therebybe detected. When errors are suf ficientlyrare,and do notoccurclosely bunched in time, use of parity provides suf ficient error detection. Unfortunately,inrealsituations,asinglenoise “event”islikelytodisruptmore than one bit. Since the parity bit has two possible values (0 and 1), it gives, onaverage,onlya 50% chanceofdetecting an erroneouscharacterwith morethan one wrong bit. That probability, 50%, is not nearly good enough for most applications. Most communications protocols [1]use a multibit generalization of the parity bit called a“cyclic redundancy check ”or CRC. In typical applications the CRC is 16 bits long (two bytes or two characters), so that the chance of a random error going undetected is 1 in 216= 65536. Moreover, M-bit CRCs have the mathematical property of detecting allerrors that occur in Mor fewerconsecutive bits, for any