f20-3

888 Chapter20. Less-NumericalAlgorithmsSample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).FUNCTION igray(n,is) INTEGER igray,is,n F o rz e r oo rp o s i t i v ev a l u e so f is, return the Gray code of n;i fisis negative, return the inverse Gray code of n. INTEGER idiv,ish if (is.ge.0) then This is the easy direction! igray=ieor(n,n/2) else Thisisthe more complicated direction: Inhierarchical stages, starting with a one-bit right shift, cause each bit to be XORed with all more significant bits.ish=-1 igray=n 1 continue idiv=ishft(igray,ish)igray=ieor(igray,idiv) if(idiv.le.1.or.ish.eq.-16)return ish=ish+ish Double the amount of shift on the next cycle. goto 1 endif returnEND In numerical work, Gray codes can be useful when you need to do some task thatdependsintimatelyonthebitsof i,loopingovermanyvaluesof i. Then,ifthere are economies in repeating the task for values differing by only one bit, it makes sense to do things in Gray code order rather than consecutive order. We saw an example of this in §7.7, for the generation of quasi-random sequences. CITED REFERENCES AND FURTHER READING: Horowitz,P., andHill,W.1989, TheArtofElectronics ,2nded.(NewYork:CambridgeUniversity Press), §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 CyclicRedundancy and Other Checksums When you send a sequence of bits from point A to point B, you want to know that 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 is chosen so as to make the total number of one-bits (versus zero-bits) either alwayseven(“evenparity”)oralwaysodd(“oddparity”). Any singlebit errorinacharacter will therebybe detected. When errors are sufficientlyrare,and do notoccurclosely bunched in time, use of parity provides sufficient error detection. Unfortunately,inrealsituations,asinglenoise“event”islikelytodisruptmore than one bit. Since the parity bit has two possible values (0 and 1), it gives, onaverage,onlya 50% chanceofdetecting an erroneouscharacterwith morethan one wrong bit. That probability, 50%, is not nearly good enough for most applications. Most communications protocols [1]use a multibit generalization of the parity bit called a “cyclic redundancy check” or CRC. In typical applications the CRC is 16 bits long (two bytes or two characters), so that the chance of a random error going undetected is 1 in 216= 65536. Moreover, M-bit CRCs have the mathematical property of detecting allerrors that occur in Mor fewerconsecutive bits, for any 20.3Cyclic RedundancyandOtherChecksums 889Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).length of message. (We prove this below.) Since noise in communicationchannels tends 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 and chip-levelhardware designers — peoplewith bits under their fingernails. However,there are at least two kinds of situations where some understandingof 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, orwhole 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,identicalrecords. Ifyoucan’ttoleratetheverysmallprobabilityofbeingwrong,you candoafullcomparisonofthe recordswhenthekeysareidentical. Whenthereis a possibility of files or data records beinginadvertentlyor irresponsiblymodified(for example,byacomputervirus),itisusefultohavetheirpriorCRCsstoredexternally on a physically secure medium, like a floppy disk. SometimesCRCscanbeusedtocompressdataasitisrecorded. Ifidenticaldata 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.” Anybinarymessagecanbethoughtofasapolynomialwithcoefficients0and1. Forexample,themessage“1100001101”is thepolynomial x9+x8+x3+x2+1. Since 0 and 1 are the only integers modulo 2, a power of xin the polynomial is either present (1) or absent (0). A polynomial over the integers modulo 2 may beirreducible,meaningthatitcan’tbefactored. Asubsetoftheirreduciblepolynomials are the “primitive” polynomials. These generate maximum length sequences when usedinshiftregisters,asdescribedin §7.4. Thepolynomial x 2+1isnotirreducible: x2+1 = ( x+1)( x+1),soitisalsonotprimitive. Thepolynomial x4+x3+x2+x+1 is irreducible, but it turns out not to be primitive. The polynomial x4+x+1is both irreducible and primitive. AnM-bitlongCRCisbasedonaprimitivepolynomialofdegree M,calledthe generatorpolynomial. Alternatively,thegeneratorischosentobeaprimitivepolyno-mialtimes (1 + x)(thisfindsallparityerrors). For16-bitCRC’s,theCCITT(Comit ´e Consultatif International T ´el´egraphique et T ´el´ephonique) has anointed the “CCITT polynomial,” which is x 16+x12+x5+1. This polynomial is used by all of the 890 Chapter20. Less-NumericalAlgorithmsSample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).Conventions and Test Values for Various CRCProtocols icrcargsTest Values (C2C1in hex) Packet Protocol jinit jrevTCatMouse987654321 Format CRC XMODEM 011A71 E556 S1S2...S NC2C1 0 X.25 255−11B26 F56E S1S2...S NC1C2 F0B8 (no name) 255−11B26 F56E S1S2...S NC1C2 0 SDLC(IBM) same as X.25 HDLC(ISO) same as X.25 CRC-CCITT 0−114A1 C28D S1S2...S NC1C2 0 (no name) 0−114A1 C28D S1S2...S NC1C2 F0B8 Kermit same as CRC-CCITT see Notes Notes: Overbar denotes bit complement. S1...S Nare character data. C1is CRC’s least significant 8 bits, C2is 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. 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 common12-bitchoice,“CRC-12,”is x12+x11+x3+x+1. A common32-bit choice,“AUTODIN-II,”is x32+x26+x23+x22+x16+x12+x11+x10+x8+ x7+x5+x4+x2+x+1. Foratableofsomeotherprimitivepolynomials,see §7.4. Giventhegeneratorpolynomial Gof degree M(whichcanbe writteneitherin polynomial form or as a bit-string, e.g., 10001000000100001 for CCITT), here ishowyoucomputetheCRCforasequenceofbits S: First,multiply Sbyx M,thatis, append Mzero bits to it. Second divide — by long division — Ginto SxM. 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 aremainder,it is the CRC, call it C.Cwill bea polynomialofdegree M−1orless, otherwise you would not have finished the long division. Therefore, in bit string form, it has Mbits, which may include leading zeros. ( Cmight 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 whatyouwritedowninthelong-divisiontableauissuperfluous. Youareactuallyjust left-shiftingsequentialbitsof S,fromtheright,intoan M-bitregister. Everytimea1 bitgetsshiftedofftheleftendofthisregister,youzaptheregisterbyanXORwiththeMloworderbitsof G(thatis,allthebitsof Gexceptits leading1). Whena0bitis shiftedofftheleftendyoudon’tzaptheregister. Whenthelastbitthatwasoriginally part of Sgets 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 tapsintoit. ThatishowCRCs arecomputedincommunicationsdevices,byasingle chip (or small part of one). In software, the implementationis not so elegant, since 20.3Cyclic RedundancyandOtherChecksums 891Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).bit-shifting is not generally very efficient. One therefore typically finds (as in our implementationbelow) table-drivenroutines that pre-calculatethe 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 Mconsec- utive bits. Suppose two messages, Sand T, differ only within a frame of Mbits. Then their CRCs differ by an amount that is the remainder when Gis divided into (S−T)xM≡D.N o w Dhas 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=xnFwhere Fis a polynomial of degree at most M−1and n> 0. Since Gis always primitive or primitive times (1 + x),i ti sn o t divisibleby x.S o Gcannotdivide D. Therefore Sand TmusthavedifferentCRCs. In most protocols, a transmitted block of data consists of some Ndata bits, directly followed by the Mbits of their CRC (or the CRC XORed with a constant, seebelow). Therearetwoequivalentwaysofvalidatingablockatthereceivingend. Mostobviously,thereceivercancomputetheCRCofthedatabits,andcompareitto thetransmittedCRCbits. Lessobviously,butmoreelegantly,thereceivercansimplycomputetheCRCofthetotalblock,with N+Mbits,andverifythataresultofzero is obtained. Proof: The total blockis the polynomial Sx M+C(data left-shiftedto make room for the CRC bits). The definition of Cis that Sxm=QG +C, where Qis thediscardedquotient. But then SxM+C=QG +C+C=QG(remember modulo2),whichis a perfectmultipleof G. It remainsa multipleof Gwhenit gets multipliedby an additional xMon the receivingend, so it has a zeroCRC, q.e.d. A coupleofsmall variationson thebasic procedureneed tobe mentioned [1,3]: First, when the CRC is computed,the M-bit register neednot be initialized to zero. Initializingit tosomeother M-bitvalue(e.g.,all1’s)ineffectprefacesallblocksby 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 Kto 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 Kx M. The constant Kis frequently“all bits,” changingthe CRC into its ones complement. ThishastheadvantageofdetectinganotherkindoferrorthattheCRC 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 icrcimplements the above CRC calculation, including the possibility of the mentioned variations. Input to the function is the starting address of an array of characters, and the length of that array. (In practice, FORTRAN allows you to use the address of anydata structure; icrcwill treat it as a byte array.) Output is in both of two formats. The function value returns the CRC as a 4-byte integer in the range 0 to 65535. The character array crc,o f length2, returnstheCRC as two 8-bitcharacters. icrchastwo “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 negativevalueof jrevcauseseachinputcharactertobeinterpretedasitsbit-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 jinitandjrevspecified in the table. 892 Chapter20. Less-NumericalAlgorithmsSample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).(If youinsiston 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 of characters from the input array and output CRC of icrc. You should not need to do any additional bit-reversal outside of icrc. The switch jinithas one additional use: When negative it causes the input valueofthearray crctobeusedasinitializationoftheregister. If crcisunmodified sincethelast callto icrc,thisineffectappendsthecurrentinputarraytothatofthe previouscall or calls. Use this feature,forexample,to buildup theCRC ofa whole file a line at a time, without keeping the whole file in memory. Atinitialization,theroutine icrcfiguresouttheorderinwhichthebytesoccur whena 4-bytecharacterarrayis equivalencedtoa 4-byteinteger. Thisis notstrictly portable FORTRAN, but it should work on all machines with 32-bit word lengths. icrcis loosely based on a more portable C function in [4], a good place to turn if you have trouble running the program here. Here is how to understand the operation of icrc: First look at the function icrc1. This incorporates one input character into a 16-bit CRC register. The only trick used is that character bits are XORed into the most significant bits, eight at a time, instead of being fed into the least significant bit, one bit at a time, at the time oftheregistershift. ThisworksbecauseXOR isassociativeandcommutative—we can feed in character bits anytime before they will determine whether to zap with thegeneratorpolynomial. (Thedecimalconstant4129hasthegenerator’sbitsinit.) FUNCTION icrc1(crc,onech,ib1,ib2,ib3) INTEGER icrc1,ib1,ib2,ib3 Given a remainder up to now, return the new CRC after one character is added. This routine is functionally equivalent to icrc(,,1,-1,1) , but slower. It is used by icrcto initialize its table. INTEGER i,ichr,ireg CHARACTER*1 onech,crc(4),creg(4) EQUIVALENCE (creg,ireg)ireg=0 creg(ib1)=crc(ib1) Here is where the character is folded into the register. creg(ib2)=char(ieor(ichar(crc(ib2)),ichar(onech)))do 11i=1,8 Here is where 8 one-bit shifts, and some XORs with the gen- erator polynomial, are done. ichr=ichar(creg(ib2)) ireg=ireg+ireg creg(ib3)=char(0)if(ichr.gt.127)ireg=ieor(ireg,4129) enddo 11 icrc1=ireg returnEND Now look at icrc. There are two parts to understand, how it builds a table when it initializes, and how it uses that table later on. Go back to thinking about acharacter’sbitsbeingshiftedintotheCRCregisterfromtheleastsignificantend. The key observation is that while 8 bits are being shifted into the register’s low end, all the generatorzappingis beingdeterminedbythe bits alreadyin the highend. SinceXOR is commutative and associative, all we need is a table of the result of all this zapping,foreachof256possiblehigh-bitconfigurations. Thenwecanplaycatch-up and XOR an input character into the result of a lookup into this table. The routine makes repeated use of an equivalenced 4-byte integer and 4-byte character array to 20.3Cyclic RedundancyandOtherChecksums 893Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).get at different 8-bit chunks.The only other content to icrcis the construction at initialization time of an 8-bit bit-reverse table from the 4-bit table stored in it, and thelogicassociatedwith doingthebit reversals. References [4-6]givefurtherdetails on table-driven CRC computations. FUNCTION icrc(crc,bufptr,len,jinit,jrev) INTEGER icrc,jinit,jrev,lenCHARACTER*1 bufptr(*),crc(2) C USES icrc1 Computes a 16-bit Cyclic Redundancy Check for an array bufptrof length lenbytes, using any of several conventions as determined by the settings of jinitandjrev(see accompanying table). The result is returned both as an integer icrcand as a 2-byte array crc.I fjinitis negative, then crcis used on input to initialize the remainder register, in effect concatenating bufptrto the previous call. INTEGER ich,init,ireg,j,icrctb(0:255),it(0:15),icrc1,ib1,ib2,ib3 CHARACTER*1 creg(4),rchr(0:255) SAVE icrctb,rchr,init,it,ib1,ib2,ib3EQUIVALENCE (creg,ireg) Used to get at the 4 bytes in an integer. DATA it/0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15/, init /0/ Table of 4-bit bit-reverses, and flag for initialization. if (init.eq.0) then Do we need to initialize tables? init=1 ireg=256*(256*ichar(’3’)+ichar(’2’))+ichar(’1’) do 11j=1,4 Figure out which component of cregaddresses which byte of ireg. if (creg(j).eq.’1’) ib1=j if (creg(j).eq.’2’) ib2=j if (creg(j).eq.’3’) ib3=j enddo 11 do12j=0,255 The two tables are: CRCs of all characters, and bit-reverses of all characters. ireg=j*256 icrctb(j)=icrc1(creg,char(0),ib1,ib2,ib3)ich=it(mod(j,16))*16+it(j/16)rchr(j)=char(ich) enddo 12 endif if (jinit.ge.0) then Initialize the remainder register. crc(1)=char(jinit) crc(2)=char(jinit) else if (jrev.lt.0) then If not initializing, do we reverse the register? ich=ichar(crc(1)) crc(1)=rchr(ichar(crc(2))) crc(2)=rchr(ich) endifdo 13j=1,len Main loop over the characters in the array. ich=ichar(bufptr(j)) if(jrev.lt.0)ich=ichar(rchr(ich))ireg=icrctb(ieor(ich,ichar(crc(2)))) crc(2)=char(ieor(ichar(creg(ib2)),ichar(crc(1)))) crc(1)=creg(ib1) enddo 13 if (jrev.ge.0) then Do we need to reverse the output? creg(ib1)=crc(1) creg(ib2)=crc(2) else creg(ib2)=rchr(ichar(crc(1))) creg(ib1)=rchr(ichar(crc(2)))crc(1)=creg(ib1)crc(2)=creg(ib2) endif icrc=iregreturn END 894 Chapter20. Less-NumericalAlgorithmsSample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).What if you need a 32-bit checksum? For a true 32-bit CRC, you will need to rewritetheroutinesgiventoworkwithalongergeneratingpolynomial. Forexample,x 32+x7+x5+x3+x2+x+1isprimitivemodulo2,andhasnonleading,nonzero bitsonlyinitsleastsignificantbyte(whichmakesforsomesimplification). Theidea of table lookup on only the most significant byte of the CRC register goes through unchanged. Pay attention to the fact that FORTRAN does not have unsignedintegers, so half of your CRCs will appear to be negative in integer format. If you do not care about the M-consecutive bit property of the checksum, but rather only need a statistically random 32 bits, then you can use icrcas given here: Call it once with jrev =1to get 16 bits, and againwith jrev =−1to get another 16 bits. The internal bit reversals make these two 16-bit CRCs in effect totally independent of each other. OtherKinds of Checksums QuitedifferentfromCRCs arethevarioustechniquesusedtoappendadecimal “check digit” to numbers that are handled by human beings (e.g., typed into a computer). Check digits need to be proof against the kinds of highly structured errorsthathumanstendtomake,suchastransposingconsecutivedigits. WagnerandPutter [7]giveaninterestingintroductiontothissubject,includingspecificalgorithms. Checksums now in widespread use vary from fair to poor. The 10-digit ISBN (International Standard Book Number) that you find on most books, including thisone, uses the check equation 10d 1+9d2+8d3+···+2d9+d10= 0 (mod 11) ( 20.3.1 ) where d10is the right-hand check digit. The character “X” is used to represent a checkdigitvalueof10. Anotherpopularschemeistheso-called“IBMcheck,”oftenusedforaccountnumbers(including,e.g.,MasterCard). Here,thecheckequationis 2#d 1+d2+2 # d3+d4+···= 0 (mod 10) ( 20.3.2 ) where 2#dmeans,“multiply dbytwoandaddtheresultingdecimaldigits.” United States bankscodecheckswitha 9-digitprocessingnumberwhosecheckequationis 3a1+7a2+a3+3a4+7a5+a6+3a7+7a8+a9= 0 (mod 10) ( 20.3.3 ) The bar code put on many envelopes by the U.S. Postal Service is decoded by removing the single tall marker bars at each end, and breaking the remaining bars into 6 or 10 groups of five. In each group the five bars signify (from left to right)the values 7,4,2,1,0. Exactly two of them will be tall. Their sum is the represented digit,exceptthatzeroisrepresentedas 7+4. The5-or9-digitZipCodeisfollowed by a check digit, with the check equation /summationdisplay d i= 0 (mod 10) ( 20.3.4 ) None of these schemes is close to optimal. An elegantscheme due to Verhoeff is describedin [7]. Theunderlyingidea is touse theten-element dihedralgroup D5, 20.3Cyclic RedundancyandOtherChecksums 895Sample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).which corresponds to the symmetries of a pentagon, instead of the cyclic group of the integers modulo 10. The check equation is a1*f(a2)*f2(a3)*···*fn−1(an)=0 ( 20.3.5 ) where *is (noncommutative)multiplication in D5, and fidenotes the ith iteration of a certain fixed permutation. Verhoeff’s method finds allsingle errors in a string, andalladjacent transpositions. It also finds about 95% of twin errors ( aa→bb), jump transpositions ( acb→bca), and jump twin errors ( aca→bcb). Here is an implementation: LOGICAL FUNCTION decchk(string,n,ch) INTEGER n CHARACTER string*(*),ch*1 Decimal check digit computation or verification. Returns as cha check digit for appending tostring(1:n) , that is, for storing into string(n+1:n+1) . In this mode, ignore the returned logical value. If string(1:n) already ends with a check digit ( string(n:n) ), returns the function value .true.if the check digit is valid, otherwise .false. In this mode, ignore the returned value of ch.N o t et h a t stringandchcontain ASCII characters corresponding to the digits 0-9, notbyte values in that range. Other ASCII characters are allowed in string, and are ignored in calculating the check digit. INTEGER ij(10,10),ip(10,8),i,j,k,mSAVE ij,ip Group multiplication and permutation tables. DATA ip/0,1,2,3,4,5,6,7,8,9,1,5,7,6,2,8,3,0,9,4, * 5,8,0,3,7,9,6,1,4,2,8,9,1,6,0,4,3,5,2,7,9,4,5,3,1,2,6,8,7,0, * 4,2,8,6,5,7,3,9,0,1,2,7,9,3,8,0,6,4,1,5,7,0,4,6,9,1,3,2,5,8/,* ij/0,1,2,3,4,5,6,7,8,9,1,2,3,4,0,9,5,6,7,8,2,3,4,0,1,8,9,5,6, * 7,3,4,0,1,2,7,8,9,5,6,4,0,1,2,3,6,7,8,9,5,5,6,7,8,9,0,1,2,3, * 4,6,7,8,9,5,4,0,1,2,3,7,8,9,5,6,3,4,0,1,2,8,9,5,6,7,2,3,4,0,* 1,9,5,6,7,8,1,2,3,4,0/ k=0 m=0 do 11j=1,n Look at successive characters. i=ichar(string(j:j))if (i.ge.48.and.i.le.57)then Ignore everything except digits. k=ij(k+1,ip(mod(i+2,10)+1,mod(m,8)+1)+1) m=m+1 endif enddo 11 decchk=(k.eq.0) do12i=0,9 Find which appended digit will check properly. if (ij(k+1,ip(i+1,mod(m,8)+1)+1).eq.0) goto 1 enddo 12 1 ch=char(i+48) Convert to ASCII. return end CITED REFERENCES AND FURTHER READING: McNamara, J.E.1982, TechnicalAspects ofDataCommunication , 2nded.(Bedford,MA:Digital Press). [1] da Cruz, F. 1987, Kermit, A File Transfer Protocol (Bedford, MA: Digital Press). [2] Morse, G. 1986, Byte, vol. 11, pp. 115–124 (September). [3] LeVan, J. 1987, Byte, vol. 12, pp. 339–341 (November). [4] Sarwate, D.V. 1988, Communications of the ACM , vol. 31, pp. 1008–1013. [5] Griffiths, G., and Stones, G.C. 1987, Communications of the ACM , vol. 30, pp. 617–620. [6] Wagner, N.R., and Putter, P.S. 1989, Communications of the ACM , vol. 32, pp. 106–110. [7] 896 Chapter20. Less-NumericalAlgorithmsSample page from NUMERICAL RECIPES IN FORTRAN 77: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43064-X) Copyright (C) 1986-1992 by Cambridge University Press.Programs Copyright (C) 1986-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 copyin g of machine- readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes booksor CDROMs, v isit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to [email protected] (outside North Amer ica).20.4 Huffman Codingand Compression of Data A lossless data compression algorithm takes a string of symbols (typically ASCII charactersorbytes)andtranslatesit reversibly intoanotherstring,onethatis ontheaverage ofshorterlength. Thewords“ontheaverage”arecrucial;itisobvious that no reversible algorithm can make all strings shorter — there just aren’t enough short strings to be in one-to-one correspondence with longer strings. Compression algorithms are possible only when, on the input side, some strings, or some inputsymbols, are more common than others. These can then be encoded in fewer bits than rarer input strings or symbols, giving a net average gain. There exist many, quite different, compression techniques, corresponding to differentwaysofdetectingandusingdeparturesfromequiprobabilityininputstrings. Inthissectionandthenextweshallconsideronly variablelengthcodes withdefined wordinputs. In these, the input is sliced into fixed units, for example ASCII characters, while the corresponding output comes in chunks of variable size. The simplest such method is Huffman coding [1], discussed in this section. Another example, arithmetic compression , is discussed in §20.5. At the opposite extremefrom defined-word,variable lengthcodes are schemes thatdivideupthe inputintounitsofvariablelength(wordsorphrasesofEnglishtext, forexample)andthentransmitthese,oftenwithafixed-lengthoutputcode. Themost widely used code of this type is the Ziv-Lempel code [2]. References [3-6]give the flavorofsome othercompressiontechniques,with referencesto thelargeliterature. The idea behind Huffman coding is simply to use shorter bit patterns for more commoncharacters. We can make this idea quantitative by consideringthe conceptofentropy. Suppose the input alphabet has N chcharacters, and that these occur in the input string with respective probabilities pi,i=1 ,...,N ch, so that/summationtextpi=1. Then the fundamental theorem of informationtheory says that strings consisting ofindependentlyrandomsequencesofthese characters(a conservative,but not always realistic assumption) require, on the average, at least H=−/summationdisplay p ilog2pi (20.4.1 ) bits per character. Here His the entropy of the probability distribution. Moreover, coding schemes exist which approach the bound arbitrarily closely. For the case of equiprobable characters, with all pi=1 /N ch, one easily sees that H=l o g2Nch, which is the case of no compression at all. Any other set of pi’s gives a smaller entropy, allowing some useful compression. Noticethattheboundof(20.4.1)wouldbeachievedifwecouldencodecharacter iwith a code of length Li=−log2pibits: Equation (20.4.1) would then be the average/summationtextpiLi. The trouble with such a scheme is that −log2piis not generally an integer. How can we encode the letter “Q” in 5.32 bits? Huffman coding makesa stab at this by, in effect, approximating all the probabilities p iby integer powers of 1/2, so that all the Li’s are integral. If all the pi’s are in fact of this form, then a Huffman code does achieve the entropy bound H. The construction of a Huffman code is best illustrated by example. Imagine a language, Vowellish, with the Nch=5character alphabet A, E, I, O, and U, occurringwiththerespectiveprobabilities0.12,0.42,0.09,0.30,and0.07. Thenthe constructionofaHuffmancodeforVowellishisaccomplishedinthefollowingtable: