Browse Prior Art Database

High Speed Comparators Involving Sums and Differences

IP.com Disclosure Number: IPCOM000044912D
Original Publication Date: 1983-Jan-01
Included in the Prior Art Database: 2005-Feb-06
Document File: 3 page(s) / 47K

Publishing Venue

IBM

Related People

Blount, FT: AUTHOR

Abstract

The general formula for a high speed comparator involving sums and differences is: Formula (1) A(1) +/- A(2) +/- A(3)..... +/- A(N) > (*)K.

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 3

High Speed Comparators Involving Sums and Differences

The general formula for a high speed comparator involving sums and differences is:
Formula (1) A(1) +/- A(2) +/- A(3)..... +/- A(N) > (*)K.

The A 's are binary fixed point operands of various lengths; K is a fixed point constant; +/- indicates that a choice of a + or an operation is to be made; and >(*) indicates that a choice of >, <,=, greater than equal to,or less than is to be made. Simple examples include: A(0:7)< B(0:7), A(0:7) + B(4:7) greater than equal to C(0:7) and A(0:31)=0, where bit 0 is the high-order bit.

To implement formula (1), first make all operands the same length by prefixing zeros or sign bits to the shorter operands. Call the resulting length M. Formula (1) can now be expressed as: Formula (2) 2/M-1/ A(1,0) + 2/M-2/ A(1,1) +..... +2A(1,M-2)
+ A(1,M-1) /- (2/M-1/ A(2,0) +2/M-2/ A(2,1) + .... +2A(2,M-2) + A(2,M-1))

/- (2/M-1/ A(N,0) + 2/M-2/ A(N,1) + .... +2A(N,M-2) +

A(N,M-1)) >(*)K where A(i,j) is the jth bit position of operand A(i).

Formula (2) can be written as: Formula (3) 2/M-1/S(0) + 2/M-2/S(1) +...2S(M-2) + S(M-1)>(*)K, where each S(i)=A(1,i) +/- A(2,i) +/- .... +/- A(n,i).

It's simple to prove that each S(i) is an N+1 valued variable.

The implementation proceeds by finding the minimum sum of products (MSP) or the minimum product of sums (MPS) solution for Formula (3) in terms of simple functions of S(i). This minimization process is just an extension of any of the standard minimization techniques for two valued (binary) variables. The next step is to express the functions of S(i) in terms of the corresponding bit variables, A(1,i), A(2,i).....A(N,i). The block diagram for this solution is shown in Fig. 1.

To illustrate the implementation, conside...