20.3 Cyclic Redundancy and Other Checksums 897 property of detecting all errors that occur in M or fewer consecutive bits,for any length of message.(We prove this below.)Since noise in communication channels tends to be "bursty,"with short sequences of adjacent bits getting corrupted,this consecutive-bit property is highly desirable. Normally CRCs lie in the province of communications software experts and chip-level hardware designers-people with bits under their fingernails.However, there are at least two kinds of situations where some understanding of CRCs can be useful to the rest of us.First,we sometimes need to be able to communicate with a lower-level piece of hardware or software that expects a valid CRC as part of its input.For example,it can be convenient to have a program generate XMODEM 81 or Kermit [2]packets directly into the communications line rather than having to store the data in a local file Second,in the manipulation of large quantities of(e.g.,experimental)data,it is useful to be able to tag aggregates of data (whether numbers,records,lines,or whole files)with a statistically unique"key,"its CRC.Aggregates of any size can then be compared for identity by comparing only their short CRC keys.Differing keys imply nonidentical records.Identical keys imply,to high statistical certainty. identical records.Ifyou can't tolerate the very small probability of being wrong,you can do a full comparison of the records when the keys are identical.When there is a 9 possibility of files or data records being inadvertently or irresponsibly modified (for example,by a computer virus),it is useful to have their prior CRCs stored externally on a physically secure medium,like a floppy disk. Sometimes CRCs can be used to compress data as it is recorded.Ifidentical data 、心宴 records occur frequently,one can keep sorted in memory the CRCs of previously encountered records.A new record is archived in full if its CRC is different, OF SCIENTIFIC otherwise only a pointer to a previous record need be archived.In this application one might desire a 4-or 8-byte CRC,to make the odds of mistakenly discarding 6 a different data record be tolerably small;or,if previous records can be randomly accessed,a full comparison can be made to decide whether records with identical CRCs are in fact identical. Now let us briefly discuss the theory of CRCs.After that,we will give implementations of various(related)CRCs that are used by the official or de facto standard protocols [1-3]listed in the accompanying table. 国心8 Numerica 10621 The mathematics underlying CRCs is"polynomials over the integers modulo 2.Any binary message can be thought of as a polynomial with coefficients 0 and 1. For example,the message "1100001101"is the polynomial x+++2+1. Since 0 and I are the only integers modulo 2,a power of x in the polynomial is 腿 either present (1)or absent(0).A polynomial over the integers modulo 2 may be irreducible,meaning that it can't be factored.A subset of the irreducible polynomials North are the "primitive"polynomials.These generate maximum length sequences when used in shift registers,as described in $7.4.The polynomial z2+1 is not irreducible: x2+1=(x+1)(x+1),so it is also not primitive.The polynomialz+x+++1 is irreducible,but it turns out not to be primitive.The polynomial z4+z+1 is both irreducible and primitive. An M-bit long CRC is based on a primitive polynomial of degree M,called the generator polynomial.Alternatively,the generator is chosen to be a primitive polynomial times(1+)(this finds all parity errors).For 16-bit CRC's,the CCITT (Comite Consultatif International Telegraphique et Telephonique)has anointed the20.3 Cyclic Redundancy and Other Checksums 897 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). property of detecting all errors that occur in M or fewer consecutive bits, for any length of message. (We prove this below.) Since noise in communication channels tends to be “bursty,” with short sequences of adjacent bits getting corrupted, this consecutive-bit property is highly desirable. Normally CRCs lie in the province of communications software experts and chip-level hardware designers — people with bits under their fingernails. However, there are at least two kinds of situations where some understanding of CRCs can be useful to the rest of us. First, we sometimes need to be able to communicate with a lower-level piece of hardware or software that expects a valid CRC as part of its input. For example, it can be convenient to have a program generate XMODEM or Kermit [2] packets directly into the communications line rather than having to store the data in a local file. Second, in the manipulation of large quantities of (e.g., experimental) data, it is useful to be able to tag aggregates of data (whether numbers, records, lines, or whole files) with a statistically unique “key,” its CRC. Aggregates of any size can then be compared for identity by comparing only their short CRC keys. Differing keys imply nonidentical records. Identical keys imply, to high statistical certainty, identical records. If you can’t tolerate the very small probability of being wrong, you can do a full comparison of the records when the keys are identical. When there is a possibility of files or data records being inadvertently or irresponsibly modified (for example, by a computer virus), it is useful to have their prior CRCs stored externally on a physically secure medium, like a floppy disk. Sometimes CRCs can be used to compress data as it is recorded. If identical data records occur frequently, one can keep sorted in memory the CRCs of previously encountered records. A new record is archived in full if its CRC is different, otherwise only a pointer to a previous record need be archived. In this application one might desire a 4- or 8-byte CRC, to make the odds of mistakenly discarding a different data record be tolerably small; or, if previous records can be randomly accessed, a full comparison can be made to decide whether records with identical CRCs are in fact identical. Now let us briefly discuss the theory of CRCs. After that, we will give implementations of various (related) CRCs that are used by the official or de facto standard protocols [1-3] listed in the accompanying table. The mathematics underlying CRCs is “polynomials over the integers modulo 2.” Any binary message can be thought of as a polynomial with coefficients 0 and 1. For example, the message “1100001101” is the polynomial x9 + x8 + x3 + x2 + 1. Since 0 and 1 are the only integers modulo 2, a power of x in the polynomial is either present (1) or absent (0). A polynomial over the integers modulo 2 may be irreducible, meaning that it can’t be factored. A subset of the irreducible polynomials are the “primitive” polynomials. These generate maximum length sequences when used in shift registers, as described in §7.4. The polynomial x2 + 1 is not irreducible: x2+1 = (x+1)(x+1), so it is also not primitive. The polynomialx4+x3+x2+x+1 is irreducible, but it turns out not to be primitive. The polynomial x4 + x + 1 is both irreducible and primitive. An M-bit long CRC is based on a primitive polynomial of degree M, called the generator polynomial. Alternatively, the generator is chosen to be a primitive polynomial times (1 + x) (this finds all parity errors). For 16-bit CRC’s, the CCITT (Comite Consultatif International T ´ el´ egraphique et T ´ el´ ephonique) has anointed the ´