898 Chapter 20.Less-Numerical Algorithms Conventions and Test Values for Various CRC Protocols args Test Values (C2C1 in hex) Packet Protocol jinitjrev 人 CatMouse987654321 Format CRC XMODEM 0 1A71 E556 S1S2...SNC2C1 0 X.25 255 -1 1B26 F56E S1S2...SNC1C2 FOB8 (no name) 255 -1 1B26 F56E S1S2...SNC1C2 0 SDLC (IBM) same as X.25 HDLC (ISO) same as X.25 CRC-CCITT 0 -1 14A1 C28D S1S2...SNC1C2 0 (no name) 0 -1 14A1 C28D S1S2...SNC1C2 FOB8 Kermit same as CRC-CCITT see Notes Notes: Overbar denotes bit complement.S1...SN are character data.C is CRC's least significant 8 bits,C2 is its most significant 8 bits,so CRC 256C2+C1 (shown in hex).Kermit (block check level 3)sends the CRC as 3 printable ASCII characters (sends value +32).These contain,respectively,4 most significant bits,6 middle bits, 6 least significant bits. ≥ea、s的d旧 Americ "CCITT polynomial,"which is 16+12+5+1.This polynomial is used by all of 9 the protocols listed in the table.Another common choice is the"CRC-16"polynomial 16+15+2+1,which is used for EBCDIC messages in IBM's BISYNCH [1]. A common 12-bit choice,"CRC-12."is x12+11+3+x+1.A common 32-bit choice,.“AUTODIN-IⅡ，”isx32+x26+x23+x22+x16+x12+x11+x10+x8+ x7+5+4+2+x+1.For a table of some other primitive polynomials,see 87.4. 6 Given the generator polynomial G of degree M(which can be written either in polynomial form or as a bit-string,e.g.,10001000000100001 for CCITT),here is how you compute the CRC for a sequence of bits S:First,multiply Sby M,that is, append M zero bits to it.Second divide-by long division-Ginto SM.Keep in mind that the subtractions in the long division are done modulo 2,so that there are never any "borrows":Modulo 2 subtraction is the same as logical exclusive-or Numerica 10621 (XOR).Third,ignore the quotient you get.Fourth,when you eventually get to a 43106 remainder,it is the CRC,call it C.C will be a polynomial of degree M-1 or less, otherwise you would not have finished the long division.Therefore,in bit string form,it has M bits,which may include leading zeros.(C might even be all zeros, see below.)See [3]for a worked example. If you work through the above steps in an example,you will see that most of what you write down in the long-division tableau is superfluous.You are actually just left-shifting sequential bits ofS.from the right,into an M-bit register.Every time a 1 bit gets shifted off the left end of this register,you zap the register by an XOR with the M low order bits of G(that is,all the bits of G except its leading 1).When a 0 bit is shifted off the left end you don't zap the register.When the last bit that was originally part of S gets shifted off the left end of the register,what remains is the CRC. You can immediately recognize how efficiently this procedure can be imple- mented in hardware.It requires only a shift register with a few hard-wired XOR taps into it.That is how CRCs are computed in communications devices,by a single898 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). Conventions and Test Values for Various CRC Protocols icrc args Test Values (C2C1 in hex) Packet Protocol jinit jrev T CatMouse987654321 Format CRC XMODEM 0 1 1A71 E556 S1S2 ...SN C2C1 0 X.25 255 −1 1B26 F56E S1S2 ...SN C1C2 F0B8 (no name) 255 −1 1B26 F56E S1S2 ...SN C1C2 0 SDLC (IBM) same as X.25 HDLC (ISO) same as X.25 CRC-CCITT 0 −1 14A1 C28D S1S2 ...SN C1C2 0 (no name) 0 −1 14A1 C28D S1S2 ...SN C1C2 F0B8 Kermit same as CRC-CCITT see Notes Notes: Overbar denotes bit complement. S1 ...SN are character data. C1 is CRC’s least significant 8 bits, C2 is its most significant 8 bits, so CRC = 256 C2 + C1 (shown in hex). Kermit (block check level 3) sends the CRC as 3 printable ASCII characters (sends value +32). These contain, respectively, 4 most significant bits, 6 middle bits, 6 least significant bits. “CCITT polynomial,” which is x16 +x12 +x5 + 1. This polynomial is used by all of the protocols listed in the table. Another common choice is the “CRC-16” polynomial x16 + x15 + x2 + 1, which is used for EBCDIC messages in IBM’s BISYNCH [1]. A common 12-bit choice, “CRC-12,” is x12 + x11 + x3 + x + 1. A common 32-bit choice, “AUTODIN-II,” is x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 +x5 +x4 +x2 +x+ 1. For a table of some other primitive polynomials, see §7.4. Given the generator polynomial G of degree M (which can be written either in polynomial form or as a bit-string, e.g., 10001000000100001 for CCITT), here is how you compute the CRC for a sequence of bits S: First, multiply S by xM , that is, append M zero bits to it. Second divide — by long division — G into Sx M . Keep in mind that the subtractions in the long division are done modulo 2, so that there are never any “borrows”: Modulo 2 subtraction is the same as logical exclusive-or (XOR). Third, ignore the quotient you get. Fourth, when you eventually get to a remainder, it is the CRC, call it C. C will be a polynomial of degree M − 1 or less, otherwise you would not have finished the long division. Therefore, in bit string form, it has M bits, which may include leading zeros. (C might even be all zeros, see below.) See [3] for a worked example. If you work through the above steps in an example, you will see that most of what you write down in the long-division tableau is superfluous. You are actually just left-shifting sequential bits of S, from the right, into an M-bit register. Every time a 1 bit gets shifted off the left end of this register, you zap the register by an XOR with the M low order bits of G (that is, all the bits of G except its leading 1). When a 0 bit is shifted off the left end you don’t zap the register. When the last bit that was originally part of S gets shifted off the left end of the register, what remains is the CRC. You can immediately recognize how efficiently this procedure can be imple￾mented in hardware. It requires only a shift register with a few hard-wired XOR taps into it. That is how CRCs are computed in communications devices, by a single