Browse Prior Art Database

Checking Logical Operations by Residues

IP.com Disclosure Number: IPCOM000078397D
Original Publication Date: 1972-Dec-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 3 page(s) / 46K

Publishing Venue

IBM

Related People

Sih, KY: AUTHOR [+2]

Abstract

Described is an algorithm for using residue relationships to check logical OR operations. The residue of the result of a bit-by-bit logical OR operation between two source operations X and Y may be expressed by: r(V) = 2/k-1/ [r)X) + r(Y) + r(V) ] mod m (1) = r(X) + r(Y) - 2/k-1/ r(C) mod m (2) where r(X) = residue of X r(Y) = residue of Y r(V) = residue of XVY, i.e., (X or Y) r(V) = residue of XVY r(C) = residue of carry generated (and shifted) in the addition X + Y All residues are for modulo m and 2 = 1 mod m. With m = 3 (k = 2), these can be reduced to: r(V) = 2 [ r(X) + r(Y) + r(V) ] mod 3 (3) = r(X) + r(Y) + r(C) mod 3 (4).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Checking Logical Operations by Residues

Described is an algorithm for using residue relationships to check logical OR operations. The residue of the result of a bit-by-bit logical OR operation between two source operations X and Y may be expressed by: r(V) = 2/k-1/ [r)X) + r(Y) + r(V) ] mod m (1) = r(X) + r(Y) - 2/k-1/ r(C) mod m (2) where r(X) = residue of X r(Y) = residue of Y r(V) = residue of XVY, i.e., (X or Y) r(V) = residue of XVY r(C) = residue of carry generated (and shifted) in the addition X + Y All residues are for modulo m and 2 = 1 mod m. With m = 3 (k = 2), these can be reduced to: r(V) = 2 [ r(X) + r(Y) + r(V) ] mod 3 (3) = r(X) + r(Y) + r(C) mod 3 (4).

Note that 2 r(X) is the additive inverse of r(X), mod 3. The additive inverse is referred to loosely as "complement" in the sequel.

The validity of the above relationship may be demonstrated as follows:

In adding X and Y in a binary adder, the sum (S = X + Y) may be obtained by adding the half-sum (H) and the carry shifted one bit position to the left (C), i.e.: S = H + C = X + Y.

It can be shown that the carry may be expressed in terms of the half-sum and the result of bit-by-bit logical ORing X and Y(V). C = 2 (V - H).

The multiplication by 2 in this expression is for the shift. Hence, X + Y = H + 2 (V-H) X + Y = 2V - H Taking residues, r(X) + r(Y) = 2r(V) - r(H) mod m 2r(V) = r(X) + r(Y) + r(H) r(V) = 2 [r(X) + r(Y) + r(H) ] Since 2/k/ = 1 mod m, by definition. r(V) = 2/k-1/ [r(X) + r(Y) + r(H) ] mod m = 2/k-1/ [r(X) + r(Y) + r(V) ] mod m recognizing that r(H) = r(V) From (5), r(V) = r(X) + r(Y) - r(C) mod m Substituting, r(V) = 2/k-1/ [r(X) + r(Y) + r(X) + r(Y) - r(C) ] = 2/k/r(X) + 2 r(Y)...