Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-06-12
2001-05-08
Malzahn, David H. (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S290000
Reexamination Certificate
active
06230177
ABSTRACT:
BACKGROUND
The present invention is directed to a method and apparatus for performing fast fourier transforms. More particularly the invention is directed to performing fast fourier transforms in a texturizing subsystem in a graphics processing device.
Computer generated graphics are being used today to perform a wide variety of tasks. Many different areas of business, industry, government, education, and entertainment are tapping into the enormous and rapidly growing list of applications developed for today's increasingly powerful computer devices.
Graphics have also been used for communicating ideas, data, and trends in most areas of commerce, science, and education. Until recently, real time user interaction with three dimensional (3D) model and pseudo-realistic images was feasible on only very high performance workstations. These workstations contain dedicated, special purpose graphics hardware. The progress of semiconductor fabrication technology has made it possible to do real time 3D animation with color shaded images of complex objects, described by thousands of polygons, on powerful dedicated rendering subsystems moving away from the need for a dedicated workstation. The most recent and most powerful workstations are capable of rendering completely life-like, realistically lighted 3D objects and structures. But other graphics processing devices are capable of object rendering which was previously only alterable using high performance work stations.
In addition to the generation of graphics, there has been a continuing development in image processing. Examples of imaging applications include electronic light tables (ELTs) which can be used for defense imaging, two dimensional (2D) and 3D visualization techniques for medical imaging or in other markets where image processing can be critical, e.g., pre-press and post-production to name a few.
In the past, it has been thought that dividing the image processing functionality and the graphics processing functionality into separate dedicated hardware was an advantageous architecture.
Co-pending application entitled A METHOD AND APPARATUS FOR PROVIDING IMAGE AND GRAPHICS PROCESSING USING A GRAPHICS RENDERING ENGINE, U.S. Ser. No. 956,537, filed on Oct. 23, 1997 describes a technique by which the graphics processing and image processing are performed with the same hardware. The description of the graphics rendering engine, including the image processing operations performed thereby, is incorporated herein by reference.
Fast Fourier Transform (FFT) is a key imaging operation in many imaging application domains, for example, medical imaging and image compression, in particular. Due to the special computational requirements of FFT, real-time FFT engines are traditionally implemented as black-box hardwares for special purposes. General purpose FFT sometimes needs the computational power of a supercomputer like a Cray-2.
A review of the mathematical background regarding FFTs will be illuminative of the complexities involved in implementing such an imaging operation.
Basic Formulations
The one dimensional Fourier transform of a continuous function f(x) is
F
(
u
)
=
∫
-
∞
∞
f
(
x
)
ⅇ
-
2
πj
ux
ⅆ
x
(
1
)
Intuitively speaking, the Fourier Transform decomposes a function into a set of sinusoidal basis functions at different frequencies. For each frequency u, F(u), a complex number (i.e., a number having real and imaginary components), tells you the magnitude and the phase of the associated sinusoidal function. Therefore, f(x) can be written as a summation of sinusoidal functions as follows
f
(
x
)
=
∫
-
∞
∞
F
(
u
)
ⅇ
2
πj
ux
ⅆ
u
(
2
)
In fact, we can reverse the role of f(x) and F(u), and call f(x) the Inverse Fourier Transform (IFT) of F(u).
The discrete version of the Fourier Transform of an array f(n) of size N is
F
(
k
)
=
∑
n
=
0
N
-
1
f
(
n
)
ⅇ
-
2
πj
nk
/
N
,
k
=
0
,
…
,
N
-
1
(
3
)
and the Inverse Discrete Fourier Transform (IDFT) of F(k) is
f
(
n
)
=
1
N
∑
k
=
0
N
-
1
F
(
k
)
ⅇ
2
π
j
nk
/
N
(
4
)
The complex phase factor e
−2&pgr;j/N
can be abbreviated as W
N
. We can rewrite Equation 4 as
F
(
k
)
=
∑
n
=
0
N
-
1
f
(
n
)
W
N
nk
k
=
0
,
…
,
N
-
1
(
5
)
Computing F(k) directly from the formula above requires:
2N
2
evaluations of trigonometric functions; and
N(N−1) complex additions.
The order of the complexity of the direct computations of DFT is N
2
, which is typically prohibitive for real-time applications.
It is known that the phase factor W
N
has the following properties:
Symmetry property: W
N
k+N/2
=−W
N
k
Periodicity property: W
N
k+N
=W
N
k
Multiplicity property: W
N
Lk
=W
N/L
k
These properties can be exploited to adopt a divide-and-conquer approach to calculate these Discrete Fourier transform (DFT). The computationally efficient algorithms that exploit these properties are known as Fast Fourier Transforms (FFTs) described as follows.
Suppose that N, the size of the f(n) array, can be factorized as a product of two integers N=L×M, then f(n) and F(k) can be arranged in two dimensional (2-D) arrays f(l, m) and F(q,p) as shown in
FIG. 1
using the mapping
n=Ml+m,
and
k=Lq+p
(6)
where
0
≦l≦L−
1 0≦
m≦M−
1
0
≦p≦L−
1 0
≦q≦M−
1
The top half of the
FIG. 1
shows the M (columns)×L (rows) array of f(n) with an array size N=M×L. The bottom half of the figure shows the M×L array for the DFT F(k).
The DFT of f(n) can be reformulated as:
F
(
q
,
p
)
=
∑
m
=
0
M
-
1
∑
l
=
0
L
-
1
f
(
m
,
l
)
W
N
(
Ml
+
m
)
(
Lq
+
p
)
(
7
)
But,
W
N
(Ml+m) (Lq+p)
=W
N
MLql
W
N
Mpl
W
N
mqL
W
N
mp
According to properties of the phase factor W
N
, as described above,
W
N
MLql
=W
N
Nql
=1,
W
N
Mpl
W
N/M
pl
=W
L
pl
W
N
(mqL)
=W
N/L
mq
=W
M
mq
Using these simplifications,
F
(
q
,
p
)
=
(
∑
m
=
0
M
-
1
W
M
qm
∑
l
=
0
L
-
1
f
(
m
,
l
)
W
L
pl
)
W
N
m
p
(
8
)
For Example: N=12 N=4×3=12 select L=4, m=3
We would store f(n) as:
m = 0
m = 1
m = 2
col. 0
col. 1
col. 2
L = 0 row 0
f(0,0) = f(0)
f(1,0) = f(1)
f(2,0) = f(2)
L = 1 row 1
f(0,1) = f(3)
f(1,1) = f(4)
f(2,1) = f(5)
L = 2 row 2
f(0,2) = f(6)
f(1,2) = f(7)
f(2,2) = f(8)
L = 3 row 3
f(0,3) = f(9)
f(1,3) = f(10)
f(2,3) = f(11)
Using
equation
8:
F
(
q
,
p
)
=
∑
m
=
0
M
=
l
∑
1
=
0
L
-
1
f
(
m
,
1
)
W
L
p
l
W
N
mp
W
M
qm
The computation of the DFT for f(n) can be divided into the following four steps: STEP 1. Compute the L-point DFT of each column m, for all m=0, . . . m−1 that is, we compute
F
(
m
,
p
)
=
∑
l
=
0
L
-
1
f
(
m
,
l
)
W
L
pl
for
m
=
0
,
…
,
M
-
1
(
9
)
where, each point F(m, p) can be considered as a partially transformed function which is indexed by p, a frequency domain coordinate, and m, the same spatial domain coordinate F(m, p) storage can be represented as:
F (0,0)
F (1,0)
F (2,0)
F (0,1)
F (1,1)
F (2,1)
F (0,2)
F (1,2)
F (2,2)
F (0,3)
F (1,3)
F (2,3)
Step 2: Multiply each F (m, p) by W
N
mp
where W
N
mp
is referred to as the phase or twiddling factor so that:
G
(
m, p
)=
F
(
m,p
)
W
N
mp
(10)
G(m, p) storage can be represented as:
m = 0
m = 1
m = 2
p = 0
G (0,0)
Cam Winget Nancy
Gossett Carroll Philip
Lu Chien-Ping
Malzahn David H.
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
Method and apparatus for performing fast fourier transforms does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing fast fourier transforms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing fast fourier transforms will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2541420