896 Chapter 20.Less-Numerical Algorithms exhausted.Here is a piece of code for doing both G(i)and its inverse unsigned long igray(unsigned long n,int is) For zero or positive values of is,return the Gray code of n;if is is negative,return the inverse Gray code of n. int ish; unsigned long ans,idiv; if(1s>=0) This is the easy direction! return n (n >1); ish=1; This is the more complicated direction:In hierarchical 三 ans=n; stages,starting with a one-bit right shift,cause each for (;;) bit to be XORed with all more significant bits. ans (idiv=ans >ish); if (idiv <1 II ish ==16)return ans; 1sh<<=1; Double the amount of shift on the next cycle. 发 In numerical work,Gray codes can be useful when you need to do some task that depends intimately on the bits of i,looping over many values of i.Then,if there 令 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 Press. example of this in 87.7,for the generation of quasi-random sequences. CITED REFERENCES AND FURTHER READING: Horowitz,P.,and Hill,W.1989,The Art of Electronics,2nd ed.(New York:Cambridge University Press),$8.02. SCIENTIFIC Knuth,D.E.Combinatorial Algorithms,vol.4 of The Art of Computer Programming (Reading. MA:Addison-Wesley),87.2.1.[Unpublished.Will it be always so?] 61 20.3 Cyclic Redundancy and Other Checksums Numerica 10.621 When you send a sequence of bits from point A to point B,you want to know 43106 that it will arrive without error.A common form of insurance is the "parity bit," (outside Recipes 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 always even ("even parity")or always odd (odd parity).Any single bit error in a character North Software. will thereby be detected.When errors are sufficiently rare,and do not occur closely bunched in time,use of parity provides sufficient error detection. Unfortunately,in real situations,a single noise"event"is likely to disrupt more than one bit.Since the parity bit has two possible values(0 and 1),it gives,on average.only a 50%chance of detecting an erroneous character with more than 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 mathematical896 Chapter 20. Less-Numerical Algorithms 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). exhausted. Here is a piece of code for doing both G(i) and its inverse. unsigned long igray(unsigned long n, int is) For zero or positive values of is, return the Gray code of n; if is is negative, return the inverse Gray code of n. { int ish; unsigned long ans,idiv; if (is >= 0) This is the easy direction! return n ^ (n >> 1); ish=1; 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. ans=n; for (;;) { ans ^= (idiv=ans >> ish); if (idiv <= 1 || ish == 16) return ans; ish <<= 1; Double the amount of shift on the next cycle. } } In numerical work, Gray codes can be useful when you need to do some task that depends intimately on the bits of i, looping over many values of i. Then, if there 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., and Hill, W. 1989, The Art of Electronics, 2nd ed. (New York: Cambridge University 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 Cyclic Redundancy 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 always even (“even parity”) or always odd (“odd parity”). Any single bit error in a character will thereby be detected. When errors are sufficiently rare, and do not occur closely bunched in time, use of parity provides sufficient error detection. Unfortunately, in real situations, a single noise “event” is likely to disrupt more than one bit. Since the parity bit has two possible values (0 and 1), it gives, on average, only a 50% chance of detecting an erroneous character with more than 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