c20-3 (779625)
Текст из файла
896Chapter 20.Less-Numerical Algorithmsexhausted. Here is a piece of code for doing both G(i) and its inverse.if (is >= 0)This is the easy direction!return n ^ (n >> 1);ish=1;This is the more complicated direction: In hierarchicalans=n;stages, starting with a one-bit right shift, cause eachfor (;;) {bit to be XORed with all more significant bits.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 taskthat depends intimately on the bits of i, looping over many values of i. Then, if thereare economies in repeating the task for values differing by only one bit, it makessense to do things in Gray code order rather than consecutive order. We saw anexample 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 UniversityPress), §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 ChecksumsWhen you send a sequence of bits from point A to point B, you want to knowthat 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 ischosen so as to make the total number of one-bits (versus zero-bits) either alwayseven (“even parity”) or always odd (“odd parity”). Any single bit error in a characterwill thereby be detected. When errors are sufficiently rare, and do not occur closelybunched in time, use of parity provides sufficient error detection.Unfortunately, in real situations, a single noise “event” is likely to disrupt morethan one bit.
Since the parity bit has two possible values (0 and 1), it gives, onaverage, only a 50% chance of detecting an erroneous character with more than onewrong bit. That probability, 50%, is not nearly good enough for most applications.Most communications protocols [1] use a multibit generalization of the parity bitcalled a “cyclic redundancy check” or CRC. In typical applications the CRC is 16bits long (two bytes or two characters), so that the chance of a random error goingundetected is 1 in 216 = 65536.
Moreover, M -bit CRCs have the mathematicalSample 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).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 inverseGray code of n.{int ish;unsigned long ans,idiv;20.3 Cyclic Redundancy and Other Checksums897Sample 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).property of detecting all errors that occur in M or fewer consecutive bits, for anylength of message.
(We prove this below.) Since noise in communication channelstends to be “bursty,” with short sequences of adjacent bits getting corrupted, thisconsecutive-bit property is highly desirable.Normally CRCs lie in the province of communications software experts andchip-level hardware designers — people with bits under their fingernails. However,there are at least two kinds of situations where some understanding of CRCs can beuseful to the rest of us.
First, we sometimes need to be able to communicate witha lower-level piece of hardware or software that expects a valid CRC as part of itsinput. For example, it can be convenient to have a program generate XMODEMor Kermit [2] packets directly into the communications line rather than having tostore the data in a local file.Second, in the manipulation of large quantities of (e.g., experimental) data, itis useful to be able to tag aggregates of data (whether numbers, records, lines, orwhole files) with a statistically unique “key,” its CRC.
Aggregates of any size canthen be compared for identity by comparing only their short CRC keys. Differingkeys imply nonidentical records. Identical keys imply, to high statistical certainty,identical records. If you can’t tolerate the very small probability of being wrong, youcan do a full comparison of the records when the keys are identical. When there is apossibility of files or data records being inadvertently or irresponsibly modified (forexample, by a computer virus), it is useful to have their prior CRCs stored externallyon a physically secure medium, like a floppy disk.Sometimes CRCs can be used to compress data as it is recorded.
If identical datarecords occur frequently, one can keep sorted in memory the CRCs of previouslyencountered 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 applicationone might desire a 4- or 8-byte CRC, to make the odds of mistakenly discardinga different data record be tolerably small; or, if previous records can be randomlyaccessed, a full comparison can be made to decide whether records with identicalCRCs are in fact identical.Now let us briefly discuss the theory of CRCs.
After that, we will giveimplementations of various (related) CRCs that are used by the official or de factostandard protocols [1-3] listed in the accompanying table.The mathematics underlying CRCs is “polynomials over the integers modulo2.” 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 iseither present (1) or absent (0).
A polynomial over the integers modulo 2 may beirreducible, meaning that it can’t be factored. A subset of the irreducible polynomialsare the “primitive” polynomials. These generate maximum length sequences whenused 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 polynomial x4 +x3 +x2 +x+1is irreducible, but it turns out not to be primitive. The polynomial x4 + x + 1 isboth irreducible and primitive.An M -bit long CRC is based on a particular primitive polynomial of degree M ,called the generator polynomial. The choice of which primitive polynomial to useis only a matter of convention. For 16-bit CRC’s, the CCITT (Comité ConsultatifInternational Télégraphique et Téléphonique) has anointed the “CCITT polynomial,”898Chapter 20.Less-Numerical AlgorithmsConventions and Test Values for Various CRC Protocolsicrc argsProtocoljinit jrev1Test Values (C2 C1 in hex)PacketTCatMouse987654321FormatCRC1A71E556S1 S2 . .
. SN C2 C100X.25255−1 1B26F56ES1 S2 . . . SN C1 C2F0B8(no name)255−1 1B26F56ES1 S2 . . . SN C1 C20SDLC (IBM)same as X.25HDLC (ISO)same as X.25CRC-CCITT0−1 14A1C28DS1 S2 . . . SN C1 C20(no name)0−1 14A1C28DS1 S2 . . . SN C1 C2F0B8KermitNotes:same as CRC-CCITTsee NotesOverbar denotes bit complement.
S1 . . . SN are character data. C1 is CRC’s leastsignificant 8 bits, C2 is its most significant 8 bits, so CRC = 256 C2 + C1 (shownin 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.which is x16 + x12 + x5 + 1. This polynomial is used by all of the protocols listed inthe 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-bitchoice, “CRC-12,” is x12 +x11 +x3 +x +1.
A common 32-bit choice, “AUTODINII,” 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 eitherin polynomial form or as a bit-string, e.g., 10001000000100001 for CCITT), here ishow 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 SxM . Keepin mind that the subtractions in the long division are done modulo 2, so that thereare never any “borrows”: Modulo 2 subtraction is the same as logical exclusive-or(XOR).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
