Function block

Details Function block Function block

2002-06-24

2004-12-28

Tan, Vibol (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Array

C326S038000, C326S041000, C708S505000, C708S670000, C708S703000, C708S710000, C708S711000, C708S524000, C708S525000

Reexamination Certificate

active

06836147

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a reconfigurable device in which various functions can be implemented by a user, and in particular to a function block which is a logic function constituting unit. More specifically, the present invention relates to a function block suitable for implementing a multiplier and a multiplexer. In this specification, a circuit bearing a main portion of a logic function in a programmable function cell is referred to as a function block.
2. Description of the Related Art
Recently, reconfigurable devices such as a PLD (programmable logic device), FPGA (field programmable gate array) and the like in which various functions can be set by a user have been rapidly developed. With increase of degree of integration and speed, such a reconfigurable device is expected to be used not only for emulation during the designing of ASIC (application-specific integrated circuit) or substitution of a simple peripheral circuit but also for a reconfigurable computer whose hardware structure can be changed depending on an application.
However, a multiplier that is frequently used in computing cannot be effectively realized by a conventional PLD or FPGA, which is one of tho causes disturbing practical use of a reconfigurable computer. Furthermore, the conventional PLD and FPGA cannot effectively realize a multi-input multiplexer (MUX). Owing to this, it has been impossible to obtain a compact barrel shifter, for example, used for floating-point addition/subtraction.
FIG. 103
shows a typical example of an ordinary multiplier. This multiplier multiplies X=x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
by Y=y
3
y
2
y
1
y
0
to produce Z=z
11
z
10
z
9
z
8
z
7
z
6
z
5
z
4
z
3
z
2
z
1
z
0
that is the product of X and Y, where each of x
i
, y
i
or z
i
represents (i+1)-th bit of binary data X, Y and Z, and is 0 or 1 (i−0, 1, 2, . . . ). For example, the notation of x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
represents a bit arrangement of binary data X. As is clear from
FIG. 103
, this multiplier is constructed by systematically arranging a multiplier unit
76
in an array. In the multiplier unit
76
, an output of an AND circuit
31
is connected to one argument input b of a 1-bit full adder
43
. In the 1-bit full adder
43
of
FIG. 103
, the other argument input is denoted by a, a carry input by ic, a carry output by oc, and an addition output by s. The multiplier as shown in
FIG. 103
is the most basic array-type multiplier having a simple and systematic configuration, which is suitable for implementation in the FPGA.
FIG. 104
shows an example of a conventional function block
4
for FPGA (for example, see U.S. Pat. Nos. 5,349,250, 5,481,206, and 5,546,018). Here, only those parts related to the description are shown. In the figure, a logic function generator
40
is a circuit capable of realizing various logic functions in accordance with contents of a built-in configuration memory.
FIG. 105
shows an example of the logic function generator
40
. This has sixteen 1-bit memory cells
13
as a configuration memory and the outputs of respective ones of the memory cells are inputted to a 16-input multiplexer (MUX)
20
. In accordance with values of four control inputs in
0
, in
1
, in
2
and in
3
, the 16-input MUX
20
selects one of the 16 inputs to output it as denoted by out. This logic function generator
40
has a logic function which is determined in accordance with contents stored in the configuration memory
13
and can realize an arbitrary 4-input 1-output logic function having four inputs in
0
, in
1
, in
2
and in
3
and one output. In general, a logic function generator having 2 k-bit memory cells and capable of realizing all the k-input 1-output logic functions is referred to as a Look-Up Table (hereinafter, abbreviated as LUT).
FIG. 105
shows an example of 4-input LUT. Examples of other configurations of the LUT are disclosed in, for example, U.S. Re. Pat. No. 34,363 and U.S. Pat. No. 4,706,216.
The function block
4
of
FIG. 104
uses the logic function generator
40
to which a 2-input MUX
22
as a ripple carry circuit and a 2-input exclusive OR circuit (XOR)
30
required for constituting an adder are added.
With regard to the 2-input MUX, see FIG.
7
. In
FIG. 7
, the 2-input MUX
22
has an input to which input in
0
is connected (input-
0
) and another input to which input in
1
is connected (input-
1
). When a control input in
2
is logical 0, a signal in
0
fed to the input-
0
is outputted as denoted by out, and when the control input in
2
is logical 1, a signal in
1
fed to the input
1
is outputted. Hereinafter, when MUX is briefly written as “MUX” omitting the number of inputs, it represents two inputs (exclusive of a control input).
The multiplier of
FIG. 103
may be configured using the function block
4
of
FIG. 104
to implement the function as shown in
FIG. 106
in the logic function generator
40
of FIG.
104
. In this case, the function block
4
of
FIG. 104
functions as the multiplier unit
76
of FIG.
103
. Here, an input in
0
, an output os, a ripple carry input irc, and a ripple carry output orc of
FIG. 104
correspond to the argument input a, the adder output s, the carry input ic, and the carry output oc of the 1-bit full adder
43
, respectively. Moreover, the AND
31
in the circuit of
FIG. 106
implemented in the logic function generator
40
of
FIG. 104
corresponds to the AND
31
in the multiplier unit
76
of FIG.
103
.
As has been described above, the multiplier unit
76
of
FIG. 103
can be constructed of one function block
4
of FIG.
104
. However, when a multiplier is constructed by this method, multiplication of m-bit data and n-bit data requires m×n function blocks, occupying a great area. Furthermore, in the case of a multiplier of n bits, a signal should be transferred through n stages of function blocks
4
(besides a carry propagation delay) and accordingly, a signal propagation delay is also increased.
In addition to the function block shown in
FIG. 104
, several methods have been devised for realizing by a single function block a multiplier unit in which an AND gate is attached to one argument input of a 1-bit full adder (for example, see Japanese Patent Application Laid-open Publication Nos. 11-24891, 11-122096, and 11-353152, and U.S. Pat. No. 5,570,039). These conventional techniques also have the aforementioned problem.
In order to solve the aforementioned problem, U.S. Pat. No 5,754,459 discloses a method for implementing a multiplier using the modified Booth algorithm and the Wallace Tree into a PLD. However, this multiplier has disadvantages that its circuit configuration is complicated, a plenty of wiring resources is needed, and the area reduction effect is small.
Furthermore, the conventional FPGA has a problem that multi-input (3-input or more in this specification) MUX cannot be effectively realized. As shown in
FIG. 104
, in the function block
4
having one 4-input logic function generator
40
, only one 2-input MUX which is the simplest can be implemented. This is because a 2-input MUX can be realized by three input terminals including a control input while a 3-input MUX requires 5 input terminals and a 4-input MUX requires 6 input terminals. Thus, the 4-input logic function generator cannot provide a sufficient number of inputs.
From this reason, for example, for realizing a 4-input MUX having a high usability by the conventional FPGA, as shown in
FIG. 107
, it is necessary to use two function blocks
4
a
and
4
b
and a MUX
22
. (
FIG. 107
shows only a portion of the function block related to the present explanation). Here, the logic function generator
40
of each function block has a 2-input MUX (for example, as shown in
FIG. 7
) implemented therein. In this case, in
FIG. 107
, two pairs of inputs i
0
and i
1
of the function blocks
4
a
and
4
b
correspond to the four inputs of the 4-input MUX, respectively. The respective inputs i
2
and i
4
correspond to first and second control inputs of the

Affiliated with

Also associated with

Rating

Function block does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3306269