Electrical computers: arithmetic processing and calculating – Electrical hybrid calculating computer – Particular function performed
Reexamination Certificate
2001-11-26
2004-12-28
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical hybrid calculating computer
Particular function performed
C708S443000
Reexamination Certificate
active
06836783
ABSTRACT:
BACKGROUND OF INVENTION
The present invention is in the field of analog computation circuits, and in particular relates to the use of the parasitic resistance of field programmable interconnect devices to solve finite difference method problems.
The field programmable interconnect device (FPID) is a special-purpose integrated circuit, consisting of a large number of transistor-based electronic switches. The FPID is generically shown in FIG.
1
. Its design normally involves a number of externally available input/output (I/O) terminal contacts, a set of wiring pathways, switches between the pathways (represented as circles at a number of the crossing points), and a control circuit that determines which switches are closed based a prescribed pattern, specified from a configuration port. The FPID permits the flexible and agile interconnection between a number of the device's input/output terminals, so that normally isolated parts of a networks can be shorted together, or conversely, so that in designs, some of the connected parts of a network can be isolated by opening switches.
In the simplified
FIG. 1
representation, each terminal is connected to a row and column in the wiring array, so that “A” is actually connected to row A and column A, etc. For n terminals, this results in 2 n wires (n rows and n columns). Though this arrangement results in n
2
junctions of rows and columns, only (n
2
/2−n) switches are required to fully connect the n terminals in any combination. This configuration is sometimes referred to as a fully connected crossbar.
In the unachievable ideal case, the switches represent zero-ohm, zero-length wires when closed and infinite resistance connections when opened. Since most FPIDs are based on silicon MOSFET devices, however, the switches do not achieve the ideal behavior.
FIG. 2
illustrates the various representations of the switch in an FPID.
FIG. 2
a
is the simplified symbolic representation.
FIG. 2
b
is the familiar standard symbolic representation.
FIGS. 2
c
and
2
d
represent the n-channel MOSFET and CMOS (n-channel plus p-channel) transmission gate structures respectively, which closely represent the actual switch structures in FPID devices.
FIG. 3
provides a more physically accurate representation of an n-channel MOSFET.
FIG. 3
b
illustrates the formation of an inversion channel between the drain and source, resulting in a conductive path, the situation more closely representing the closure of an FPID switch. The switch actually behaves more like the resistor shown in
FIG. 3
c
, a fact very important to the principle behind the present invention.
Since the switch is a poor switch, the FPID is considered a digital device, for use in switched logic systems. Switch logic systems compensate for the slight signal degradations of transmission gates due to the restorative nature of digital logic systems such as CMOS. For general purpose analog, however, the non-zero resistance of the transmission gate switch (values may range from 50 ohms to 500 ohms, based on the underlying switch design and process technology) results in unwanted signal deterioration and design complexity. Hence, even though it is possible to use FPIDs for analog applications, it is uncommon to use them for these applications due to the normally undesired parasitic resistance.
It is conceivable, however, that the parasitic resistance could be harnessed in particular circuit designs. One such possibility includes the utilization of FPIDs to form certain types of resistive networks, in which the normally parasitic resistance now plays a key role in the operation of that network. One such circuit class is a linear equation solver, for example, based on the finite difference method.
The finite difference method uses a discrete approximation of differential equations to reduce them to a system of algebraic equations. For example, the following is a derivation of the finite difference representations of Laplace's equation in one-dimension
Define Laplace's equation:
∇
2
V=0 (1)
In one-dimension, Equation (1) becomes:
ⅆ
2
V
ⅆ
x
2
=
0
(
2
)
The finite forward difference is an approximation of the definition of a derivative:
ⅆ
V
(
x
)
ⅆ
x
≅
V
(
x
+
Δ
)
-
V
(
x
)
(
x
+
Δ
)
-
x
=
V
(
x
+
Δ
)
-
V
(
x
)
Δ
(
3
)
Also, define:
ⅆ
V
(
x
-
Δ
)
ⅆ
x
≅
V
(
x
)
-
V
(
x
-
Δ
)
Δ
(
4
)
Finite difference representation of higher-level derivatives can be analogously defined:
ⅆ
2
V
(
x
)
ⅆ
x
2
≅
ⅆ
V
(
x
+
Δ
)
ⅆ
x
-
ⅆ
V
(
x
)
ⅆ
x
x
(
5
)
As &Dgr;→0, the approximation improves, being identical to the “true” derivative in the limit as &Dgr;→0. Hence,
x
≈
(
x
+
Δ
)
;
V
(
x
)
≈
V
(
x
+
Δ
)
;
ⅆ
V
(
x
)
ⅆ
x
≈
ⅆ
V
(
x
+
Δ
)
ⅆ
x
;
ⅆ
2
V
(
x
)
ⅆ
x
2
≈
ⅆ
2
V
(
x
+
Δ
)
ⅆ
x
2
;
etc. So, for convenience we develop the finite difference representation of
ⅆ
2
V
(
x
-
Δ
)
ⅆ
x
2
and recognize it as an approximation of
ⅆ
2
V
(
x
)
ⅆ
x
2
using (3) and (4):
ⅆ
2
V
(
x
-
Δ
)
ⅆ
x
2
=
ⅆ
V
(
x
)
ⅆ
x
-
ⅆ
V
(
x
-
Δ
)
ⅆ
x
x
=
V
(
x
+
Δ
)
-
V
(
x
)
Δ
-
V
(
x
)
-
V
(
x
-
Δ
)
Δ
Δ
=
V
(
x
+
Δ
)
+
V
(
x
-
Δ
)
-
2
V
(
x
)
Δ
2
≅
ⅆ
2
V
(
x
-
Δ
)
ⅆ
x
2
≅
ⅆ
2
V
(
x
)
ⅆ
x
2
(
6
)
and therefore we can write a finite difference approximation to (1) (using (6)) as:
∇
2
V
≅
V
(
x
+
Δ
)
+
V
(
x
-
Δ
)
-
2
V
(
x
)
Δ
2
=
0
⇒
V
(
x
+
Δ
)
+
V
(
x
-
Δ
)
-
2
V
(
x
)
=
0
⇒
V
(
x
+
Δ
)
+
V
(
x
-
Δ
)
=
2
V
(
x
)
V
(
x
)
=
1
2
(
V
(
x
+
Δ
)
-
V
(
x
-
Δ
)
)
(
7
)
Equation (7) is then the finite difference representation of Laplace's equation in one-dimension.
To simplify implementation in a discrete system or a computer, the A's are typically replaced by integral indices, yielding the familiar form of a finite difference equation:
V
(
x
)
=
1
2
(
V
(
x
+
i
)
-
V
(
x
-
i
)
)
(
8
)
Extending this analysis to multiple dimensions is straightforward. For two dimensions, Equation (1) becomes:
∇
2
V
(
x
,
y
)
=
∂
2
V
(
x
,
y
)
∂
x
2
+
∂
2
V
(
x
,
y
)
∂
y
2
(
9
)
Through the previous analyses, we can directly write the approximation of Equation (9) as:
∇
2
V
(
x
,
y
)
≅
(
V
(
x
+
Δ
,
y
)
-
V
(
x
,
y
)
Δ
-
V
(
x
,
y
)
-
V
(
x
-
Δ
,
y
)
Δ
)
+
(
V
(
x
,
y
+
Δ
)
-
V
(
x
,
y
)
Δ
-
V
(
x
,
y
)
-
V
(
x
,
y
-
Δ
)
Δ
)
Δ
=
V
(
x
+
Δ
,
y
)
+
V
(
x
-
Δ
,
y
)
+
V
(
x
,
y
+
Δ
)
+
V
(
x
,
y
-
Δ
)
-
4
V
(
x
,
y
)
Δ
2
=
0
This results in the two-dimensional finite difference method expression:
V
(
x
,
y
)
=
1
4
(
V
(
x
+
Δ
,
y
)
+
V
(
x
-
Δ
,
y
)
+
V
(
x
,
y
+
Δ
)
+
V
(
x
,
y
-
Δ
)
)
(
10
)
Which can be written in the indexed form as:
V
(
x
,
y
)
=
1
4
(
V
(
x
+
1
,
y
)
+
V
(
x
-
1
,
y
)
+
V
(
x
,
y
+
1
)
+
V
(
x
,
y
-
1
)
)
(
11
)
In particular, it will be shown that it is possible to reduce the solution of Poisson's equation:
∇
2
V=&rgr;
over a two-dimensional (2-D) space to an equation at each of many discrete points on a grid formed onto this space:
V
(
x,y
)=1/4*(
V
(
x+dx,y
)+
V
(
x−dx,y
)+
V
(
x
Lyke James C.
Vreeland David
Callahan Kenneth E.
Mai Tan V.
Skorich James M.
The United States of America as represented by the Secretary of
LandOfFree
Finite-difference solver based on field programmable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Finite-difference solver based on field programmable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite-difference solver based on field programmable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310150