20.3 Cyclic Redundancy and Other Checksums 899 chip (or small part of one).In software,the implementation is not so elegant,since bit-shifting is not generally very efficient.One therefore typically finds(as in our implementation below)table-driven routines that pre-calculate the result of a bunch of shifts and XORs,say for each of 256 possible 8-bit inputs [41 We can now see how the CRC gets its ability to detect all errors in M consecutive bits.Suppose two messages,S and T,differ only within a frame of M bits.Then their CRCs differ by an amount that is the remainder when G is divided into (S-T)M=D.Now D has the form of leading zeros(which can be ignored). followed by some 1's in an M-bit frame.followed by trailing zeros (which are just multiplicative factors of )D=x"F where F is a polynomial of degree at most M-1 and n>0.Since G is always primitive or primitive times(1+x),it is not divisible by x.So G cannot divide D.Therefore S and T must have different CRCs. In most protocols,a transmitted block of data consists of some N data bits directly followed by the M bits of their CRC (or the CRC XORed with a constant. see below).There are two equivalent ways of validating a block at the receiving end. Most obviously,the receiver can compute the CRC of the data bits,and compare it to the transmitted CRC bits.Less obviously,but more elegantly,the receiver can simply compute the CRC of the total block,with N+M bits,and verify that a result of zero is obtained.Proof:The total block is the polynomial SM+C(data left-shifted to 9 make room for the CRC bits).The definition of C is that Sx"=QG+C,where Q is the discarded quotient.But then SzM+C=QG+C+C=QG(remember modulo 2),which is a perfect multiple of G.It remains a multiple of G when it gets multiplied by an additional xM on the receiving end,so it has a zero CRC,q.e.d. A couple of small variations on the basic procedure need to be mentioned [1,3]: 、全二0分N First,when the CRC is computed,the M-bit register need not be initialized to zero. OF SCIENTIFIC Initializing it to some other M-bit value (e.g.,all I's)in effect prefaces all blocks by a phantom message that would have given the initialization value as its remainder. 心 6 It is advantageous to do this,since the CRC described thus far otherwise cannot detect the addition or removal of any number of initial zero bits.(Loss of an initial bit,or insertion of zero bits,are common "clocking errors.")Second,one can add (XOR)any M-bit constant K to the CRC before it is transmitted.This constant can either be XORed away at the receiving end,or else it just changes the expected CRC of the whole block by a known amount,namely the remainder of dividing G Numerical Recipes 10621 into KM.The constant K is frequently"all bits,"changing the CRC into its ones complement.This has the advantage of detecting another kind of error that the CRC 43106 would otherwise not find:deletion of an initial 1 bit in the message with spurious insertion of a 1 bit at the end of the block. The accompanying function icrc implements the above CRC calculation, including the possibility of the mentioned variations.Input to the function is a North pointer to an array of characters,and the length of that array.icrc has two"switch" arguments that specify variations in the CRC calculation.A zero or positive value of jinit causes the 16-bit register to have each byte initialized with the value jinit.A negative value of jrev causes each input character to be interpreted as its bit-reverse image,and a similar bit reversal to be done on the output CRC.You do not have to understand this;just use the values of jinit and jrev specified in the table.(If you insist on knowing,the explanation is that serial data ports send characters least-significant bit first (!)and many protocols shift bits into the CRC register in exactly the order received.)The table shows how to construct a block20.3 Cyclic Redundancy and Other Checksums 899 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). chip (or small part of one). In software, the implementation is not so elegant, since bit-shifting is not generally very efficient. One therefore typically finds (as in our implementation below) table-driven routines that pre-calculate the result of a bunch of shifts and XORs, say for each of 256 possible 8-bit inputs [4]. We can now see how the CRC gets its ability to detect all errors in M consecutive bits. Suppose two messages, S and T , differ only within a frame of M bits. Then their CRCs differ by an amount that is the remainder when G is divided into (S − T )xM ≡ D. Now D has the form of leading zeros (which can be ignored), followed by some 1’s in an M-bit frame, followed by trailing zeros (which are just multiplicative factors of x): D = xnF where F is a polynomial of degree at most M − 1 and n > 0. Since G is always primitive or primitive times (1 + x), it is not divisible by x. So G cannot divide D. Therefore S and T must have different CRCs. In most protocols, a transmitted block of data consists of some N data bits, directly followed by the M bits of their CRC (or the CRC XORed with a constant, see below). There are two equivalent ways of validating a block at the receiving end. Most obviously, the receiver can compute the CRC of the data bits, and compare it to the transmitted CRC bits. Less obviously, but more elegantly, the receiver can simply compute the CRC of the total block, with N +M bits, and verify that a result of zero is obtained. Proof: The total block is the polynomial SxM + C (data left-shifted to make room for the CRC bits). The definition of C is that Sxm = QG + C, where Q is the discarded quotient. But then SxM + C = QG + C + C = QG (remember modulo 2), which is a perfect multiple of G. It remains a multiple of G when it gets multiplied by an additional xM on the receiving end, so it has a zero CRC, q.e.d. A couple of small variations on the basic procedure need to be mentioned [1,3]: First, when the CRC is computed, the M-bit register need not be initialized to zero. Initializing it to some other M-bit value (e.g., all 1’s) in effect prefaces all blocks by a phantom message that would have given the initialization value as its remainder. It is advantageous to do this, since the CRC described thus far otherwise cannot detect the addition or removal of any number of initial zero bits. (Loss of an initial bit, or insertion of zero bits, are common “clocking errors.”) Second, one can add (XOR) any M-bit constant K to the CRC before it is transmitted. This constant can either be XORed away at the receiving end, or else it just changes the expected CRC of the whole block by a known amount, namely the remainder of dividing G into KxM . The constant K is frequently “all bits,” changing the CRC into its ones complement. This has the advantage of detecting another kind of error that the CRC would otherwise not find: deletion of an initial 1 bit in the message with spurious insertion of a 1 bit at the end of the block. The accompanying function icrc implements the above CRC calculation, including the possibility of the mentioned variations. Input to the function is a pointer to an array of characters, and the length of that array. icrc has two “switch” arguments that specify variations in the CRC calculation. A zero or positive value of jinit causes the 16-bit register to have each byte initialized with the value jinit. A negative value of jrev causes each input character to be interpreted as its bit-reverse image, and a similar bit reversal to be done on the output CRC. You do not have to understand this; just use the values of jinit and jrev specified in the table. (If you insist on knowing, the explanation is that serial data ports send characters least-significant bit first (!), and many protocols shift bits into the CRC register in exactly the order received.) The table shows how to construct a block