c20-3 (779625), страница 2
Текст из файла (страница 2)
Third, ignore the quotient you get. Fourth, when you eventually get to aremainder, 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 stringform, 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 ofwhat you write down in the long-division tableau is superfluous. You are actuallyjust left-shifting sequential bits of S, from the right, into an M -bit register.
Everytime a 1 bit gets shifted off the left end of this register, you zap the register by anXOR with the M low order bits of G (that is, all the bits of G except its leading1). When a 0 bit is shifted off the left end you don’t zap the register. When thelast 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 implemented in hardware. It requires only a shift register with a few hard-wired XORtaps into it. That is how CRCs are computed in communications devices, by a singleSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).XMODEM20.3 Cyclic Redundancy and Other Checksums899Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).chip (or small part of one). In software, the implementation is not so elegant, sincebit-shifting is not generally very efficient. One therefore typically finds (as in ourimplementation below) table-driven routines that pre-calculate the result of a bunchof 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 Mconsecutive bits. Suppose two messages, S and T , differ only within a frame of Mbits. Then their CRCs differ by an amount that is the remainder when G is dividedinto (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 justmultiplicative factors of x).
Since factorization is unique, G cannot possibly divideD: G is primitive of degree M , while D is a power of x times a factor of (at most)degree M − 1. Therefore S and T have inevitably 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 tothe transmitted CRC bits. Less obviously, but more elegantly, the receiver can simplycompute the CRC of the total block, with N + M bits, and verify that a result of zerois obtained. Proof: The total block is the polynomial SxM + C (data left-shifted tomake room for the CRC bits).
The definition of C is that Sxm = QG + C, whereQ is the discarded quotient. But then SxM + C = QG + C + C = QG (remembermodulo 2), which is a perfect multiple of G. It remains a multiple of G when it getsmultiplied 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 bya 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 cannotdetect the addition or removal of any number of initial zero bits.
(Loss of an initialbit, 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 constantcan either be XORed away at the receiving end, or else it just changes the expectedCRC of the whole block by a known amount, namely the remainder of dividing Ginto KxM . The constant K is frequently “all bits,” changing the CRC into its onescomplement.
This has the advantage of detecting another kind of error that the CRCwould otherwise not find: deletion of an initial 1 bit in the message with spuriousinsertion 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 apointer 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 valueof jinit causes the 16-bit register to have each byte initialized with the valuejinit.
A negative value of jrev causes each input character to be interpreted asits bit-reverse image, and a similar bit reversal to be done on the output CRC. Youdo not have to understand this; just use the values of jinit and jrev specified inthe table. (If you insist on knowing, the explanation is that serial data ports sendcharacters least-significant bit first (!), and many protocols shift bits into the CRCregister in exactly the order received.) The table shows how to construct a block900Chapter 20.Less-Numerical Algorithmsunsigned short icrc1(unsigned short crc, unsigned char onech)Given a remainder up to now, return the new CRC after one character is added. This routineis functionally equivalent to icrc(,,1,-1,1), but slower.
It is used by icrc to initialize itstable.{int i;unsigned short ans=(crc ^ onech << 8);for (i=0;i<8;i++) {Here is where 8 one-bit shifts, and some XORs with theif (ans & 0x8000)generator polynomial, are done.ans = (ans <<= 1) ^ 4129;elseans <<= 1;}return ans;}Now look at icrc. There are two parts to understand, how it builds a tablewhen it initializes, and how it uses that table later on. Go back to thinking about acharacter’s bits being shifted into the CRC register from the least significant end.
Thekey observation is that while 8 bits are being shifted into the register’s low end, allthe generator zapping is being determined by the bits already in the high end. SinceXOR is commutative and associative, all we need is a table of the result of all thiszapping, for each of 256 possible high-bit configurations. Then we can play catch-upand XOR an input character into the result of a lookup into this table. The onlyother content to icrc is the construction at initialization time of an 8-bit bit-reversetable from the 4-bit table stored in it, and the logic associated with doing the bitreversals.
References [4-6] give further details on table-driven CRC computations.typedef unsigned char uchar;#define LOBYTE(x) ((uchar)((x) & 0xFF))#define HIBYTE(x) ((uchar)((x) >> 8))unsigned short icrc(unsigned short crc, unsigned char *bufptr,unsigned long len, short jinit, int jrev)Computes a 16-bit Cyclic Redundancy Check for an array bufptr of length len bytes, usingany of several conventions as determined by the settings of jinit and jrev (see accompanyingSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-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 copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).of characters from the input array and output CRC of icrc. You should not needto do any additional bit-reversal outside of icrc.The switch jinit has one additional use: When negative it causes the inputvalue of the array crc to be used as initialization of the register.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
