Browse Prior Art Database

Residue Checking with Array Logic

IP.com Disclosure Number: IPCOM000081008D
Original Publication Date: 1974-Mar-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 5 page(s) / 119K

Publishing Venue

IBM

Related People

Larson, RH: AUTHOR

Abstract

In computers the primitive operations done are usually well checked by carrying along parity bits and predicting them where necessary. In high-speed units where quite complex functions are performed, often at cycle rate faster than the basic CPU this may not be possible without affecting performance or circuit count unacceptably. In such cases a residue system may be chosen.

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 54% of the total text.

Page 1 of 5

Residue Checking with Array Logic

In computers the primitive operations done are usually well checked by carrying along parity bits and predicting them where necessary. In high-speed units where quite complex functions are performed, often at cycle rate faster than the basic CPU this may not be possible without affecting performance or circuit count unacceptably. In such cases a residue system may be chosen.

The general method of finding a residue, is to divide the number by the modulus chosen in the arithmetic appropriate to the base of the number. The quotient is discarded and the remainder is the residue. If the modulus is one less than the base, then the residue of the sum of the digits is the residue of the number. Thus the familiar "casting out nines" of decimal arithmetic which becomes "casting out fifteens" in hexadecimal. To find a residue by division, the number must be available starting with the high order while the sum residue may be obtained in any order. On the other hand, 9 and 15 are not quite as desirable as prime numbers are for moduli.

Currently available array logic is well suited for generating and manipulating residues up to four bits in length, and its flexibility allows free choice of modulus and base within the bit limitation. Two examples will be given. Checking High- Speed Multiply (Fig. 1)

In the IBM Technical Disclosure Bulletin December 1973, Vol. 16, No. 7, pages 2195 to 2198, a unit is shown, into which a number to be of the operation, the multiplier is fed into the unit digit-by-digit from a low order and after a delay product digits start becoming available, again from the low order. A modulus of 15 makes best use of these flows. A residue adder can be attached to each digit bus. Each adder would consist of a 256 x 4 array module and 4 bits of latching, so a partial residue could be reentered. The array would be programmed to add tw...