Modulo remainder generator

Details Modulo remainder generator Modulo remainder generator

2001-01-04

2004-04-27

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S653000

Reexamination Certificate

active

06728743

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to computerized arithmetic operations, and specifically to finding a remainder after a computerized operation of division.
BACKGROUND OF THE INVENTION
Computing systems frequently require a rounding-up or a rounding-down operation to be performed. For example, a multi-block transfer is described in a descriptor which typically comprises a header having an arbitrary number of doublewords, and 3 doublewords for each block of data transferred (a first doubleword giving a high address, a second doubleword giving a low address, and a third doubleword giving a length). The descriptor is written to a memory in which each line of the memory includes 3 doublewords. In order to determine how many lines of memory are needed, the total number of doublewords in the descriptor is rounded-up to the closest number which is a multiple of 3. To perform the rounding-up, a modulo-3 (mod-3) division of the number of doublewords in the descriptor is performed. Knowledge of the quotient and remainder of the division allows calculation of the required rounded-up number.
FIG. 1
is a schematic diagram of a finite state machine (FSM)
10
used to determine a mod-3 remainder after a division operation, as is known in the art. Machine
10
may be implemented as a hardware or software device, or as a combined hardware and software device, by methods known in the art. FSM
10
comprises a remainder 0 state
14
, a remainder 1 state
16
, and a remainder 2 state
18
. Remainder 0 state
14
is set as an initial state. A binary number
12
, herein assumed to be 11010 by way of example, is input to state
14
, starting with its most significant digit (MSB). In a first cycle of FSM
10
, since the MSB is 1, the state moves to remainder 1 state
16
. Table I hereinbelow shows the states of FSM
10
as the binary digit is fed into the machine.
TABLE I
Input Number
1
1
0
1
0
Remainder State
+1
+0
+0
+1
+2
Number of Cycles
1
2
3
4
5
Table I shows that after 5 cycles, corresponding to the number of bits in number
12
, FSM
10
halts at remainder 2 state, so that the remainder after dividing 11010 by a mod-3 division is +2. In general, for a binary number of length n, FSM
10
requires n cycles in order to determine the mod-3 remainder.
SUMMARY OF THE INVENTION
It is an object of some aspects of the present invention to provide a method and apparatus for determining a remainder after a modulo division of a binary number.
It is a further object of some aspects of the present invention to provide apparatus for determining a remainder requiring only one cycle of operation of the apparatus.
In preferred embodiments of the present invention, a modulo-n (mod-n) remainder of a binary number is determined, wherein n is a whole number greater than or equal to 2. The mod-n remainder is the value remaining after a mod-n division is performed on the number. The remainder is determined in a generator comprising a plurality of cells, each cell comprising n multiplexers. The plurality of cells corresponds to the number of bits in the binary number, and the multiplexer cells are coupled together in a linear sequence to form the generator. For each binary number input to the generator, the generator outputs an encoded value corresponding to the appropriate mod-n remainder in one cycle of operation of the generator. The ability to determine the mod-n remainder in one cycle significantly enhances the speed of remainder determination compared to methods known in the art.
There is therefore provided, according to a preferred embodiment of the present invention, apparatus for determining a remainder of a module division of a binary number made up of a string of bits, including:
a first plurality of substantially similar cells coupled in a linear sequence, the first plurality of cells including at least a first cell and a last cell, each cell of the first plurality including:
a second plurality of binary input terminals, the input terminals of the first cell being coupled to receive a pre-determined input;
a second plurality of binary output terminals, each coupled, except for the output terminals of the last cell, to a respective one of the input terminals of a subsequent cell in the sequence; and
a control input terminal, coupled to receive one of the bits in the string corresponding to a position of the cell in the sequence, so as to generate the remainder at the output terminals of the last cell in the sequence.
Preferably, the remainder is determined within one cycle of operation of the apparatus.
Preferably, each cell comprises a second plurality of multiplexers, wherein each multiplexer includes:
a first multiplexer input connected to one of the binary input terminals;
a second multiplexer input connected to another of the binary input terminals;
a multiplexer control input connected to the control input terminal; and
an output terminal connected to one of the binary output terminals and coupled to receive the first or the second multiplexer input responsive to a signal on the control input,
wherein each binary input terminal is connected to the first multiplexer input of one of the multiplexers and the second multiplexer input of another of the multiplexers, and each of the binary output terminals is connected to a respective one of the multiplexers.
Further preferably, the second plurality is three, and each of the first plurality of cells, given respective input values for a first one of the input terminals I0, a second one of the input terminals I1, a third one of the input terminals I2, and the control input terminal shown in the following table, a first one of the output terminals o0, a second one of the output terminals o1, and a third one of the output terminals o2 output values as shown in the table:
Input
Output
I0
I1
I2
Control
o0
o1
o2
1
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
1
0
1
0
1
1
0
0
0
0
1
0
0
1
0
0
0
1
1
0
0
1
Preferably, the binary number includes a number of bit that is no more than a value of the first plurality.
Preferably, a module of the module division is equal to a value of the second plurality.
There is further provided, according to a preferred embodiment of the present invention, a method for determining a remainder of a module division of a binary number made up of a string of bits, including:
providing a first plurality of substantially similar cells, the first plurality of cells including at least a first cell and a last cell, each cell including a second plurality of binary input terminals and a second plurality of binary output terminals and a control input terminal;
coupling the cells in a linear sequence so that each of the binary output terminals of a cell in the sequence, except for the output terminals of the last cell, is connected to the respective binary input terminals of a subsequent cell in the sequence;
inputting a pre-determined input to the input terminals of the first cell;
inputting each bit of the string to the corresponding control input terminal of the cell in the sequence; and
generating the remainder at the output terminals of the last cell in the sequence.
Preferably, generating the remainder includes generating the remainder within one cycle of operation of the first plurality of cells.
Preferably, the binary number includes a number of bits that is no more than a value of the first plurality.
Further preferably, a modulo of the modulo division is equal to a value of the second plurality.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings, in which:


REFERENCES:
patent: 4107783 (1978-08-01), Huang
patent: 4190893 (1980-02-01), Gajski
patent: 4555769 (1985-11-01), Carter et al.
patent: 5499202 (1996-03-01), Takahashi et al.

Affiliated with

Also associated with

Rating

Modulo remainder generator does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Modulo remainder generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modulo remainder generator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3248892