7 -
`
`I
`
`\
`
`~
`
`IEEE TRANSACTlONS ON COMPUTERS, VOL. 39. NO. 7. JULY 1990
`
`969
`
`0
`0
`11
`
`4.00
`
`lb.00
`
`11.00
`
`d.00
`61.00
`i o 0
`(LOGZNI
`NETWORK S I Z E
`rsus network size for various networks.
`Fig. 5 . Normalized throughput 1
`at the stage cycle i , i > n +
`mi, =k(m‘-‘
`“-1)
`mi = g(m‘.-‘ ,-,’ bf ’
`mh = f ( m , bb-’)
`bl-, = /(m::’l)
`
`4) Numeric Results and Comparisons: The normalized through-
`puts of the B-networks of various sizes are shown in Fig. 5 together
`with those of other networks.’ It shows that the normalized through-
`puts of the B-network are significantly higher than those of the
`crossbar, regular MIN’s,’ and the gamma network. The B-network’s
`higher performance than the crossbar’s is due to the elimination of
`memory conflicts via backward links at the last stage.
`Fig. 5 also shows that the throughputs of the B-network are much
`higher than those of single-buffered regular MIN’s. In buffered net-
`works, the routing decision cannot be made locally at an SE, because
`the decision for a packet to move forward at one stage depends on
`the buffer states of all the remaining stages of the network [8], [7].
`In the B-network, however, the routing decision is made locally at
`each SE. Moreover, each input (or output) port of an SE in buffered
`networks needs buffers as well as additional links to receive/pass the
`control signals (to prevent the overrun of the buffers). Considering
`these facts, the B-network can be a very cost-effective alternative to
`single-buffered networks.
`
`IV. CONCLUSION
`A new multistage interconnection network, the B-network, which
`employs backward links has been proposed and analyzed. A back-
`ward link provides an alternate path for a blocked request at a
`switch or memory. The bandwidth, the acceptance probability, and
`the throughput of the B-network have been analyzed. The B-network
`has been shown to exhibit much higher bandwidths and through-
`puts than the gamma network, single-buffered regular MIN’s based
`on (2 x 2) switches, and the crossbar switches, while its hardware
`
`I The values for the buffered regular MIN are from [8] and [ll], and the
`values for the gamma network are from [ 111. The buffered regular MIN
`denotes the single-buffered MIN based on (2 x 2) switches.
`MIN’s such as the omega, the regular SW banyan, the baseline. and delta
`networks based on (2 x 2) switches.
`
`cost is the same as that of the gamma network. The B-network is
`controlled by the destination tag control scheme.
`We were somewhat surprised by the performance results of the
`B-network exceeding those of the crossbar switch. The high perfor-
`mance is the combined effects of many causes: 1) the backward links
`function as implicit buffers, 2) the backward links at the very last
`switching stage of the B-network can handle memory contentions,
`which cannot be handled by the crossbar switch, 3) the original
`gamma network, on which the B-network is based, connects one
`network input point to a switch, effectively reducing the network
`input request rate.
`
`REFERENCES
`T. Feng, “A survey of interconnection networks,” IEEE Comput.
`Mag., vol. 14, pp. 12-27, Dec. 1981.
`C. Wu and T. k n g , Eds., Tutorial Interconnection Networks for
`Parallel and Distributed Processing, IEEE Computer Society Press,
`1984.
`D. S. Parker and C. S. Raghavendra, “The Gamma network,” IEEE
`Trans. Comput., vol. C-33, no. 4, pp. 367-373, Apr. 1984.
`H. Yoon and K. Y. Lee, “The B-network: A multistage interconnection
`network with backward links for multiprocessor systems,” Tech. Rep.
`OSU-CISRC-TR22, Dep. Comput. Inform. Sci., Ohio State Univ.
`C. Wu and T. Feng, “On a class of multistage interconnection net-
`works,” IEEE Trans. Comput., vol. C-29, no. 8, pp. 694-702, Aug.
`1980.
`J . H. Patel, “Performance of processor-memory
`interconnections for
`multiprocessors,” IEEE Trans. Comput., vol. C-30, no. 10, pp.
`771-780, Oct. 1981.
`D. M. Dias and J. R. Jump, “Analysis and simulation of buffered delta
`networks,” IEEE Trans. Comput., vol. C-30, no. 4 , pp. 273-282,
`Apr. 1981.
`Y. C. Jenq, “Performance analysis of a packet switch based on single-
`buffered banyan network,” IEEE J. Select. Areas Commun., vol.
`SAC-1, no. 6, pp. 1014-1021, Dec. 1983.
`C. P. K ~ s k a l and M. Snir, “The performance of multistage intercon-
`nection networks for multiprocessors,” IEEE Trans. Comput., vol.
`C-32, no. 12, pp. 1091-1098, Dec. 1983.
`M. Kumar and J. R. Jump, “Performance of unbuffered shuffle-
`exchange networks,” IEEE Trans. Comput., vol. C-35, no. 6, pp.
`573-578, June 1986.
`H. Yoon, K. Y. Lee, and M. T. Liu, “Performance analysis and
`comparison of packet switching interconnection networks,” in Proc.
`1987 Int. Conf. Parallel Processing, Aug. 1987, pp. 542-545.
`N. F. Tzeng, P. C. Yew, and C . Q . Zhu, “The performance of a
`fault-tolerant multistage interconnection network,” in P m . 1985 Int.
`Conf. Pamllel Processing, 1985, pp. 458-465.
`
`Analysis of Checksums, Extended-Precision Checksums, and
`Cyclic Redundancy Checks
`
`NIRMAL R. SAXENA AND EDWARD J. McCLUSKEY
`
`Absfract - This paper presents an extensive analysis of the effectiveness
`of extended-precision checksums. It is demonstrated that the extended-
`precision checksums most effectively exploit natural redundancy occur-
`ring in program codes. Honeywell checksums and cyclic redundancy
`checks are compared to extended-precision checksums. Two’s comple-
`
`Manuscript received November 8, 1987; revised August 12, 1988. This
`work was supported in part by the National Science Foundation under Grant
`MIP-8709128, in part by the Innovative Science and Technology Office of the
`Strategic Defense Initiative Organization and administered through the Office
`of Naval Research under Contract N00014-85-K-0600, and in part by Hewlett-
`Packard under the Honors Cooperative Program with Stanford University.
`The authors are with the Center for Reliable Computing, Stanford Univer-
`sity, Stanford, CA 93405.
`IEEE Log Number 9035146.
`
`OO18-9340/90/0700-0969$01 .OO @ 1990 IEEE
`
`Unified Patents
`EX1014
`Page 1 of 7
`
`

`

`970
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 7 , JULY 1990
`
`ment, unsigned, and one's complement arithmetic checksums are treated
`in a unified manner. Results are also extended to any general radix?
`arithmetic checksum. Asymptotic and closed form formulas of aliasing
`probabilities for the various error models are derived.
`
`denoted as [ A I , A 2 , . . . ,AS]'. Block ( n , S ) can also be defined in
`terms of columns. Block ( n , S ) is a block of n , length S, columns
`and is denoted as [c,, c, - 1 , . . , C I ] .
`Definition 4: The checksum K of an ( n , S) block is given by
`
`I
`
`Index Terms- Aliasing probability, checksums, cyclic redundancy
`check, generating functions, linear feedback shift registers.
`
`I. INTRODUCTION
`Checksums are considered one of the least expensive methods of
`error detection. These methods are used for detecting errors in stor-
`age and transmission of data. System firmware or recovery routines
`in most of the commercial computer systems are checksum-protected
`[I]. The checksum of a block of words is formed by adding to-
`gether all of the words in the block modulo-m, where m is arbitrary.
`These words could be data in memory or instructions in a checksum-
`protected code. The choice of m limits the number of bits in the
`checksum. This computed checksum validates the data or code in-
`tegrity. Since checksums are essentially a form of compaction, error
`masking can occur. The metric used to quantify the effectiveness
`of checksums is the error masking probability (aliasing probability)
`under various error models.
`Analysis of the effectiveness of checksums in [2] and [3] has
`largely been based on unidirectional errors. The detection of double
`and triple errors in low cost arithmetic codes has been analyzed in
`[4]. A closed form expression for the probability of checksum vio-
`lation, assuming independent errors, appears in [5]. Error detection
`in serial transmission by arithmetic checksum, as an alternative to
`cyclic redundancy check (CRC), has been considered in [6]. The
`use of checksums is also considered in watchdog processors [7].
`However, one problem that has not been examined in detail is
`the effectiveness of checksums under extended-precision arithmetic.
`Extended-precision checksums are described in [ 11, but their ef-
`fectiveness has not been quantified. The effectiveness of extended-
`precision checksums as a function of the static distribution of in-
`struction words in a program code is examined in Section 111. The
`extended-precision checksums are effective when the static distribu-
`tion of instructions is not uniform. Actual measurements on some
`firmware code show nonuniform distribution of instructions and it is
`believed that, in general, this will be true for other program codes.
`Results reported in [8] suggest this nonuniform distribution.
`Restricted column errors or restricted word errors are analyzed.
`The motivation for this analysis is that some failures [2] in storage
`devices can be modeled as restricted column or word errors. The
`generating function presented in Section I1 provides a framework to
`analyze unsigned, two's complement, and one's complement arith-
`metic checksums. Results are extended to any general radix-p arith-
`metic checksums.
`
`11. GENERATING F~SCTION
`In this section, a generating function f(X) is defined after the
`following definitions.
`Definition I: An n-bit word A , is defined as a string of binary
`symbols U,,, and is denoted as u n , , a n - ~ , ,
`' . , a l , , . The magnitude
`IA, I of A, is given by
`
`/All = C 2 " u , , , .
`, = I
`Definition 2: A length S column C, is a column of binary sym-
`bols a,,, and is denoted by [a,, I , a,, 2 , . . . ,u,,slT. The magnitude
`IC, I of C , is given by
`
`S
`
`i = l
`Definition 3: Block ( n , S) is a block of S n-bit words A i and is
`
`n
`
`S
`
`IC, I =
`
`IA, I.
`
`K =
`, = I
`, = I
`If the addition is performed without any loss of precision then K is
`the extended-precision checksum. K mod 2" and K mod (2" - 1) are
`two's complement and one's complement checksums, respectively.
`Definition 5: C ( S , K , n ) is defined as the number of possible dis-
`tinct ( n , S) blocks that have the same extended-precision checksum
`K .
`The following example illustrates the use of a generating function
`in enumerating C ( S , K , n).
`Example I: Let n = 2, S = 4. Four 2-bit wide words are possi-
`ble. The generating function in this case is
`f(X) = (1 + X + X 2 + X 3 ) 4
`= XI2 + 4X" + 10X'O + 20X9 + 31X8 + 40X' + 44X6
`+40X5+31X4+20X3+10X2+4X+1.
`There are four possible 2-bit (single-precision) checksum: 0, 1,
`2, and 3. For example, the number of distinct ways of producing
`checksum 1 by adding 4 2-bit words is the sum of the coefficients of
`X I , X 5 , X 9 . Adding the coefficients results in 4 + 40 + 20 = 64,
`which is simply 2' x4-2. The same result is obtained for the other
`2-bit checksum values. In the case of extended-precision, modulo-x
`addition is assumed. For example, the number of distinct ways of
`producing checksum 8 under extended-precision is the coefficient of
`X s which is 3 1.
`Generalizing Example 1: The number of distinct ( n , S ) blocks,
`A {, . . , A ; , having the same checksum K is enumerated by the coef-
`ficient of X K in f(X). The function f(X) is given by the following
`relation:
`f(X) = (1 + X + X 2 + . . . +X2'-')s.
`(1)
`ThereareSidenticalfactors,f,=l, ..s = ( l + X + . . . + X 2 " - ' ) , in
`f(X) corresponding to S words. The exponents of X in each factor
`represent 2" distinct values (0, . . ,2" - 1) a word can assume. The
`exponent Ea, of the product of S terms, picking a term
`from
`each f, , will be the checksum of S words. Therefore, the coefficient,
`denoted by C ( S , K , n), of X K in f(X) will be the number of ways
`of obtaining the same checksum K .
`The generating function f(X) can also be written as
`
`Let k' be the number formed by considering only the n least sig-
`nificant bits of K . Thus, k'
`is a single-precision checksum and
`0 5 k' 5 2" - 1. The number of distinct blocks of S words that
`produce the same checksum k' is the sum of the coefficients of
`. . . Xk'tB'n, where fi is the greatest integer less than
`Xk' , Xk'+'' 9
`or equal to (S(2n - 1) - k')/2". This number is evaluated by
`B
`
`9
`
`
`
`(3)
`
`w=o
`
`Expression (3) can be evaluated by using a coset counting argument.
`Function f ( X ) can be reinterpreted as
`f ( X ) = (1 + X + . . . +X~"-')s--l(l + X + . . . +x2"--I ).
`Powers of X in ( 1 + X + . . . +X2"--1)s-1 can be reduced to 2"
`modulo-2" residue classes: class(O), . . . ,class(i), . . ,class(2" - 1).
`Class(r] contains all those terms of ( 1 + X + . . +X2'-I)s-' such
`
`Unified Patents
`EX1014
`Page 2 of 7
`
`

`

`IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 7. JULY 1990
`
`97 I
`
`term X j in (1 + X + . . . + X 2 " - ' ) can be picked such that
`that the powers of X are i modulo-2". For every class(r] a unique
`
`Rewriting (2)
`f(X) = ( 1 -X)-S(l -X2")S
`
`Since the classes exhaust all possible powers of X in ( 1 + X + . . . +
`X z " - ' ) s - ' , the summation CC(S k'+w2", n ) is simply the sum of
`the coefficients in ( l + X + . . .+X21-')s-'. The foregoing expression
`at X = 1 evaluates to the sum of the coefficients. Therefore, the
`following identities are obtained:
`
`B
`
`C C ( S , k' + w2", n) = 2ns-n.
`
`w=o
`
`(4)
`
`From (4), the error masking probability P for single-precision check-
`sums with modulo 2" addition can be derived as
`
`In the case of single-precision checksums, it is clear that the masking
`probability is independent of the value of k' when all error patterns
`are possible. As shall be seen later, this will not be true for restricted
`classes of errors. Relation (5) also applies for two's complement
`arithmetic; however, for one's complement a different relation is
`obtained. The onset of data dependency as the checksum precision
`is increased from n-bits is illustrated in the next example. By data
`dependency, it is meant that the number of possible ways of obtaining
`a particular checksum not only depends on the type of checksum
`computation but also depends on the checksum value. This will be
`illustrated by Example 2.
`Example 2: Let S = 5, n = 2. The generating function is
`f(X) = (1 +x +x* +X3)5
`= X" + 5X14 + 15XI3 + 35X" + 65X" + 101X'O
`+ 135X9 + 155X8 + 155X7 + 135X6
`+ 101X5 + 65X4 + 35X3 + 15X2 + 5X + 1 .
`Following the approach in Example 1, it can be shown that the num-
`ber of ways of obtaining the same 2-bit checksum is 256. Extending
`the precision of the checksum result by 1 bit, we have modulo-2"+'
`addition. With this new precision, there are eight possible checksums:
`0, . . . ,7. For example, the number of ways of producing checksum 7
`is the sum of the coefficients of X7 and X I 5 , which is 156 (155 + 1).
`The number of ways of producing checksum 3 is the sum of the
`coefficients of X 3 and X I 1 , which is 90 (35 + 65). It can readily
`be seen that the number of ways of producing n + 1 bit precision
`checksum also depends on the checksum value.
`
`III. EXTENDED-PRECISION
`CHECKSUMS
`It is easy to show that the checksum value for a block of S n-bit
`wide words cannot exceed S(2" - 1). In a checksum-protected code,
`it is extremely unlikely that S would exceed 2". For instance, in a 32-
`bit computer (n = 32) it is very unlikely that the number of words in
`a checksum-protected code would exceed Z3'. Thus, almost always,
`only a 2n-bit precision result is needed. Furthermore, only an n-bit
`precision adder and a counter to count the overflow carries from
`this n-bit adder is required. The counter is incremented whenever an
`overflow carry is generated by the n-bit adder while computiy the
`checksum. Unbounded precision can be achieved by 11"'
`an n-bit
`adder and a binary counter of variable length. The number of ways
`checksum K is preserved is simply the coefficient of X K in the series
`expansion o f f (X). In this section, exact and asymptotic values of
`the coefficient of X K are derived.
`
`(6)
`In Example 1, the coefficient ofX" is 10. The same result is obtained
`using (6). Substituting S = 4 and n = 2 in (6),
`
`= 286 - 336 +60 = 10.
`C ( S , K, n) now can be defined recursively. Rewriting ( l ) ,
`f(X) = (1 +x + .. . +X2"-')s-'(l + X + . . . +x2'-' ).
`From the above factorization of f(X), the following recurrence re-
`lations are obtained.
`If K > 2" - 1 then
`C ( S , K , n) = C ( S - 1, K, n ) + . . . + C ( S - 1, K -2" + 1 , n).
`(7)
`
`(8)
`
`I f K 5 2 " - 1 then
`C ( S , K, n) = C(S - 1, K , n)
`+ C ( S - l , K - l , n ) + . . . + C ( S - l , O , n ) .
`Some of the boundary conditions for (7) and (8) are as follows:
`C ( S , 0, n) = 1 for all S > 0.
`C(0, K, n) = 1 if K = 0 else C(0, K , n) = 0.
`C(1, K , n) = 1 for all 0 5 K 5 2" - 1 .
`C ( S , S(2" - l), n) = 1.
`The effect of K on error masking is not readily apparent from the
`exact relation (6), unless a simple closed form for C ( S , K, n) ex-
`ists. It appears that there is no simple closed form expression for
`C ( S , K , n); in fact, a special case of this is an open research prob-
`lem in [9]. Therefore, an asymptotic formula for C ( S , K, n) is de-
`rived. As a result of this analysis certain important observations with
`regard to checksum-protected codes are made.
`A . Asymptotic Formula f o r C(S, K, n )
`Functions of the type f(X) belong to a class of functions called
`unimodal functions. The coefficients in the polynomial representa-
`tion of these functions can be approximated by Gaussian distribu-
`tion density functions. The following is an asymptotic approximation
`of C ( S , K , n)
`
`The following is a sketch of the derivation of the asymptotic formula:
`substituting X = 1 in f(X),
`
`f(1) = 2"s.
`Define g ( X ) = f ( X ) / f ( 1); then g( 1) = 1.
`
`Unified Patents
`EX1014
`Page 3 of 7
`
`

`

`972
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 7, JULY 1990
`
`The function g ( X ) has the characteristics of a probability gener-
`ating function. The mean p , is given by g’(l), and the variance U:
`(g’( I))? + g ’ ( I).
`is given by g”( I)
`
`g’(X)]x,, = - [ S ( 1 - x . . . +x*’-’ ) -
`
`~
`
`1
`2“s
`
`s
`
`. ( 1 + 2 X . . . + ( 2 ”
`Simplifying the above expression,
`
`px = S(2” - I).
`2
`Taking the second derivative of g ( X ) and following the above pro-
`cedure the variance U; is obtained.
`
`2617
`
`3290 x10’* 5619 x10”
`
`36720,
`
`~
`
`2498
`
`3 167 x10” 5364 xlOl2I
`
`3792O,
`
`1
`
`~
`
`3140
`
`5571 x10” 6743 xlO”[
`
`16860,
`..________
`
`l C
`
`1 E
`
`The coefficient C ( S , K , n) can be approximated by (using normal
`distribution)
`
`The coefficient of X9 in Example 2 can be estimated by (1 1) by sub-
`stituting S = 5, K = 9, and n = 2 . From expression (1 l), C(5, 9, 2)
`evaluates to 136.48 which closely agrees with the exact value 135.
`Error masking probability closely relates to C ( S , K , n ) ; therefore, it
`strongly depends on the value of K. This is evident from expression
`(11). Modest deviations of K from the mean value, S/2(2” - l),
`can reduce error masking probability significantly. If the data are
`program code then the performance of checksums under extended-
`precision clearly depends on the static instruction distribution. The
`static instruction frequency can influence the checksum value K and
`therefore the error masking probability.
`For extended-precision checksums to be effective it is desirable that
`the static distribution of instructions be nonuniform. Extensive study
`of the distribution of instructions in program codes of the various
`computer architectures has been done in [8]. Results in [8] show a
`nonuniform static distribution of high-level language statements. It is
`quite likely that instructions in the machine code of these high-level
`programs would also have nonuniform distribution characteristics.
`From an information theoretic standpoint most of the program
`codes (at the machine instruction level) have inherent redundancy.
`This is so because not all instruction encodings are meaningful; for
`example, a 32-bit instruction may not have meaning for all 232 en-
`codings of the instruction word. Also, in most of the program codes
`some instructions occur more often than the others. An analogy can
`be drawn with the encoding of decimal digits. Again from an infor-
`mation theoretic standpoint only 3.3219 (log, 10) bits are required
`to represent decimal digits. However, the number of bits must be
`a whole number; therefore, 4 bits are chosen to represent decimal
`digits. This inherent or natural redundancy cannot be avoided if a
`regular representation of decimal numbers is desired. Sometimes this
`natural redundancy is well suited for error detection. In checksum-
`protected program codes, it is highly desirable to have checksum
`values to be far away from the mean value; this will decrease the
`error masking in extended-precision checksums significantly. Next,
`it will be shown how this natural redundancy in program codes can
`be exploited to further enhance error detection in extended-precision
`checksums.
`A typical instruction word is a structured field having an opode,
`register, and other opode-extension fields. Assume that the opcode
`field is the most significant field in the instruction word. If opcodes
`are assigned such that
`an all zero opcode is assigned to that instruction which has, on
`the average, a high frequency of occurrence in program codes,
`
`and increasing values of opcodes are assigned to instructions
`that, on the average, occur in decreasing order of the frequency of
`occurrence
`then this will accomplish the task of moving the checksum value away
`from the mean px . Likewise, compilers can be designed to allocate
`registers in the following manner: registers are allocated starting
`with the register which has the smallest allowed binary encoding
`(for example, register 0) and the rest of the registers are allocated
`in increasing order of their binary value.
`In Table I, the measured checksum values of five different
`checksum-protected codes in the HP-9000 series/840 computers are
`listed. The instructions in these codes are based on the HP Preci-
`sion Instruction Set [ 101; these instructions are 32-bit wide. There-
`fore, n = 32 in this case. It is interesting to note that all the mea-
`sured checksum values differ significantly from their respective mean
`values listed in the table. This would make the extended-precision
`checksums very effective. In fact, for code D , the extended-precision
`checksums would be most effective. The deviations of the measured
`values are given (Table I) in terms of the standard deviation. The
`deviations are considered significant if they are greater than 3a,.
`
`B . Equivalent CRC Length
`One way to quantify the effectiveness of extended-precision check-
`sums is to compare it to CRC. CRC in this case would be equivalent
`to multiple input signature analysis (MISA) [7]. It is known that for
`MISA with signature polynomial degree L the number of masking er-
`rors [I 11 is equal to 2nS-L, when all error patterns are equally likely.
`Masking errors are those errors that escape detection. Equivalent
`CRC length Le is defined similar to that discussed in [ 111. Le is
`the length of the MISA signature register that would mask the same
`number of errors as extended-precision checksums would for a given
`block of data. Following a procedure similar to that discussed in [ 1 I]
`and using expression (1 l),
`
`(12)
`Le grows as the square of the difference between K and S/2(2“ - 1).
`The number of bits required to store extended-precision checksums is
`at most [log, (S(2“ - 1) + I)]. For example, in code C , Le evaluates
`to 1010; the extended-precision checksum value for this code requires
`only 45 bits. Table I1 lists the equivalent lengths for the various codes.
`For values of K close to S/2(2“ - I), CRC would perform better
`than extended-precision checksums.
`Actual measurements on program codes do show significant dif-
`ference between measured K and S/2(2” - 1).
`Conceivably all the node signatures in control flow checking [7]
`could be replaced by extended-precision checksums. However, the
`tradeoff between the cost of adder and the cost of LFSR must be
`considered.
`
`Unified Patents
`EX1014
`Page 4 of 7
`
`

`

`I"-
`
`4
`i
`
`i
`
`IEEE TRANSACTIONS ON COMPUTERS. VOL. 39. NO. 7 . JULY 1990
`
`973
`
`CRC EQUIVALENT LENGTH --
`
`TABLE I1
`
`are equivalent to unsigned arithmetic checksums. This is so, because
`in both cases addition is done in the same manner. The difference
`lies only in the way the checksum number is interpreted. However, in
`one's complement arithmetic, addition is modulo 2" - 1. These dis-
`tinctions do not arise in extended-precision checksums because addi-
`tion is done without loss of precision. In this section, an analysis for
`single-precision one's complement arithmetic checksums using the
`generating function f(X) is presented. Let Q(S, k') be the number
`of possible ways of producing the checksum k' in single-precision
`one's complement arithmetic for a block of S n-bit words. There are
`2" possible checksum values. In one's complement addition, the only
`way block of S n-bit words produce an all zero n-bit checksum is
`when all the S words are zero. This will become clear as Example 3
`is discussed, later in this section. To enumerate Q(S, k') for k' not
`equal to zero, a coset counting argument similar to that in Section
`I
`I1 will be used. The generating function f(X) can be factored as
`follows:
`
`- 44
`
`I
`-
`
`242
`
`46
`
`C. Honeywell Checksums
`The equivalent length measure is also useful in comparing the
`relative effectiveness of extended-precision checksums to Honeywell
`checksums [I], [2]. Honeywell checksums are a modified form of
`double-precision checksums. In Honeywell checksums, all pairs of
`successive words are concatenated and are treated as double-precision
`words. These double-precision words are summed to accumulate a
`double-precision checksum. This is equivalent to analyzing a single-
`precision type checksum where there are S/2 words and each word
`is 2n bits wide. For both S odd or even, the number of possible
`ways (assuming all possible error patterns) of obtaining the same
`Honeywell checksum is 2ns-2n. This can be easily derived by using
`an approach similar to that developed in Section 11.
`The form of the number of masking errors in Honeywell check-
`sums resembles the form of the number of masking errors, 2"s-L, in
`MISA. Therefore, the equivalent length measure can be easily ex-
`tended to Honeywell checksums. When L, is less than 2n, Honeywell
`checksums will be more effective than extended-precision checksums
`(for example, in Codes A , B). However, for cases where Le is
`greater than 2n, extended-precision checksums are more effective. It
`is important to note that a 2n-bit adder is required to compute Hon-
`eywell checksums as opposed to an n-bit adder in extended-precision
`checksums. It is also important to note that the effectiveness measure
`developed in this section is dependent on the error model. Equally
`likely errors were considered for the Le effectiveness measure.
`If the unidirectional-error model [l], [2] is assumed then
`extended-precision checksums will be most effective because they
`guarantee complete coverage under this model. Honey well check-
`sums and MISA do not have complete coverage [l] with respect to
`this error model.
`D . Incremental Precision Analysis
`The effect of increasing the checksum precision on the masking
`probability is examined in this section. Let K be the checksum value
`assuming extended-precision, then under incremental precision the
`checksum value will be k', where k' is the least n + a significant
`bits of K . The number of distinct ways of preserving k' is given by
`
`the following expression: 2 C ( S , k' + j2n+or, n )
`
`(13)
`
`J =o
`where /3 in this case is the greatest integer less than or equal to
`(S(2" - 1) - k')/2"+*. For large S, expression (1 1) can be used to
`evaluate C ( S , k'+j2"+", n ) . In Example 2, a = 1. Let us compute
`(13) using approximation (1 1) for k' = 6. Notice that the approx-
`imate value, 142.04, evaluated using (11) closely agrees with the
`exact value 141.
`
`IV. ONE'S COMPLEMENT CHECKSUMS
`Thus far, the results presented were for unsigned arithmetic check-
`sums. In so far as two's complement checksums are concerned they
`
`Let a ( X ) = (1 + X + , . . +X2n--')s-i and b ( X ) = (1 + X +
`. . . + X 2 n - ' ) . Therefore, f(X) = a ( X ) b ( X ) .
`Powers of X in a ( X ) can be reduced to 2" - 1 mod-(2" - 1) residue
`classes: class(O), . . . ,class(i), . . . ,class(2" - 2 ) . Class(i) contains all
`those terms of a ( X ) such that the powers of X are i mod - (2"
`1).
`For every class(i), a unique term X j in b ( X ) -X2"-' can be picked
`such that
`
`~
`
`X j X i m o d ( Z " - I ) - - ~ k ' m o d ( Z " - - l )
`
`Note that X2"--' was not included in b ( X ) - X2'-'. Terms of the
`form Xk' mod (2"--1)
`can be found in a ( X ) . The sum of the coefficients
`of these terms will be Q(S - 1 k'). Multiplying the left out X Z n - '
`term by the foregoing terms Xk"Od ('"-I) in ' a ( X ) will preserve their
`powers to k' mod (2" - 1) and also the sum of their coefficients to
`Q(S - 1, k'). Thus, the following recurrence on Q:
`
`Solving (14),
`
`~
`
`for k' > 0.
`
`(15)
`
`2"s - 1
`Q(S, k') =
`2 " - 1 '
`Q ( S , k') is independent of checksum value when k'is greater than
`zero. However, Q(S, 0) = 1. The following example will illustrate
`the counting procedure for one's complement checksums.
`Example 3: Let S = 2, n = 2. There are four possible check-
`sums: 0, 1, 2, and 3. These checksums correspond to 2-bit patterns
`00, 01, 10, and 11, respectively. The only way checksum 00 is ob-
`tained is by adding 00 and 00. However, checksum 11 can be pro-
`duced in the following five distinct ways: 11 + 11 = 1 1, 01 + 10 = 11,
`10 +01 = 11, 11 +OO = 11, and 00 + 11 = 11. This is also enu-
`merated by (15) which is 5 for n = 2 and S = 2. Enumeration for
`other checksum values can also be verified.
`From (15) the probability of error masking with one's complement
`checksums is
`
`when k' = 0, the error masking probability is zero.
`
`V. WORD A N D COLUMN ERRORS
`This section examines the error masking probability for single-
`precision and extended-precision checksums under restricted errors.
`For restricted word errors, a straightforward extension of the results
`derived in the previous sections is possible. To analyze restricted
`column errors, the generating function f(X) is useful.
`A . Restricted Word Errors
`Assume that only r specific words in a block of S words,
`A I , . , A s , are in error. Extending previous results for single-
`
`Unified Patents
`EX1014
`Page 5 of 7
`
`

`

`974
`
`IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. I, JULY 1990
`
`precision checksums,
`1) For unsigned arithmetic or two's complement checksums the
`error masking probability is (2,,-" - 1)/(2"' - 1).
`2) For one's complement checksum the masking probability is
`l(2" - 1) - 142" - 1).
`The following can be inferred from 1) and 2). All single word
`errors ( r = 1) in two's complement or one's arithmetic checksums
`are detected. If the restricted r words have sum K, under extended-
`precision the number of masking errors is obtained by substituting
`S = r and K = K, in expression (11).
`B . Restricted Column Errors
`Let the n-bit pattern of word A, be represented as A ,
`=
`an, a, -I, I . . . a I, I , where 1 5 i 5 S . For column t , the column sum
`c, is
`cr = E a f , , .
`
`S
`
`j = I
`The checksum value K under extended-precision can be interpreted
`as
`
`n
`K = z 2 J - l c j .
`j = l
`Analogous to this interpretation of K is the following form of gen-
`erating function:
`+xy.
`f(X) = ( 1 + x ~ ' - ' ) ~ ( 1 + X 2 " - z ) ~ . . . ( 1
`The number of possible sums provided by column t corresponds to
`the factor (1 +X2')' in f ( X ) . Columns vary from 0 to n - 1. With
`this formulation of the generating function f ( X ) , restricted column
`errors can be analyzed very easily. Consider single column errors,
`the number of ways the two's complement checksum is preserved
`when errors occur in column t is given by the expression
`
`0 = [(S - c,)/2"-'1 and h = [ct/2"-'j. Similarly, the number of
`ways in which the single-precision one's complement checksum is
`preserved when errors occur in column t is enumerated by
`
`Here 0 = [(S - ct)/(2" - l)] and h = [c! /(2" - l)]. In two's com-
`plement checksum, error masking is