Digital processor for two's complement computations

Details Digital processor for two's complement computations Digital processor for two's complement computations

1991-10-29

1993-08-10

Nguyen, Long T.

Boots, shoes, and leggings

364754, G06F 752

Patent

active

052355373

DESCRIPTION:

BRIEF SUMMARY
BACKGROUND OF THE INVENTION

1. Field of the Invention
This invention relates to a digital processor for two's complement computations, and more particularly to a processor of the kind incorporating an array of individual logic cells operating on single bit input. Arrays of this kind are referred to as "bit-level systolic arrays".
2. Discussion of Prior Art
Bit-level systolic arrays are known in the prior art, and are described in for example British Patent No. 2,106,287 B (Ref (1)), (U.S. Pat. Nos. 4,533,993 and 4,639,857). In FIG. 7 et sequi, Ref (1) describes the basic features of one form of bit-level systolic array for matrix-vector multiplication. The FIG. 7 device consists of a rectangular array of individual logic cells each connected to its row and column neighbours. Each cell has a specified logic function, but no gate level constructional details are given. The array includes intercell clocked latches for bit storage and advance along array rows and down array columns. Each cell evaluates the product of input data and coefficient bits received from neighbouring cells. The product is added to input carry and cumulative sum bits. The manner in which bits propagate through the array is governed by the form of computation to be executed. In Ref (1), FIG. 7 relates to multiplication of a vector X by a matrix W to form a product vector Y, the matrix W having coefficients with a value of + 1 or -1. The vectors X and Y represent digital numbers in two's complement form.
The matrix W is input to a first array edge one diagonal per clock cycle. Successive coefficients of X are input to a second array edge orthogonal to the first and in a bit parallel, word serial bit staggered manner; i.e. bits of like significance of different coefficients are input in succession to the respective row, but bits of each word with significance differing by one are input to adjacent rows with a time delay of one clock cycle per row. Coefficient bits propagate along array rows, and are multiplied by successive matrix coefficients to provide contributions to product vector element bits at a third array edge. Carry bits pass between adjacent cells evaluating bits one level higher in significance.
FIG. 9 of Ref (1) relates to a logic cell suitable for use with the FIG. 7 array, and extending its application to multiplication by a matrix of coefficients +1, -1 or 0. This requires two bits to define each matrix coefficient as opposed to one bit previously. Each cell has extra inputs to accommodate this. However, no gate level constructional details of the logic cells are given.
FIG. 15 of Ref (1) relates to a processor for executing a convolution operation, i.e. a convolver. It operates on all positive input data and coefficients, and comprises a rectangular array of gated full adder logic cells with row and column connections; i.e. each cell comprises a full adder with an AND gate connected to one input to act as a multiplier of two input bits. Data and coefficient bits propagate in counter flow along array rows, and product bits are accumulated in cascade down array columns. The array is connected to a full adder array arranged to sum contributions to like convolution results. To avoid the generation of unwanted bit-level partial products, individual bits of each word are separated by zeros. This means that part of the array is idle at any given time, since some of the cells are computing zero products.
British Patent No. 2,144,245 B (corresponding to U.S. Pat. No. 4,686,645 (Ref (2)) relates to a bit-level systolic array for matrix-matrix multiplication. It employs an array of gated full adder logic cells with row and column connections as in Ref (1), FIG. 15. Each cell recirculates its output carry bit to its carry input, since it computes bits in ascending order of significance on successive cycles. Multiplicand matrices move in counterflow along array rows. Contributions to product matrix elements accumulate down array columns. The contributions are grouped appropriately by array output adder trees, which are switchable for

REFERENCES:
patent: 4493048 (1985-01-01), Kung et al.
patent: 4777614 (1988-10-01), Ward
Electronic Letters, vol. 23, No. 9, Apr. 23, 1987, R. A. Evans et al., "Modified Bit-level Systolic Inner Product/Convolver Architecture With Increased Throughput", pp. 460-461.
Microprocessing and Microprogramming, vol. 20, Nos. 1-3, Apr. 1987, North-Holland (Amsterdam, NL), O. Bruschi et al., "Systolic Arrays for Serial Signal Processing", pp. 133-140.
G.E.C. Journal of Research, vol. 2, No. 1, 1984, R. B. Urquhart et al., "Efficient Bit-Level Systolic Arrays for Inner Product Computation", pp. 52-55.

Affiliated with

Also associated with

Rating

Digital processor for two's complement computations does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Digital processor for two's complement computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital processor for two's complement computations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1731018