Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-06-28
2003-12-16
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06665697
ABSTRACT:
FIELD OF THE INVENTION
My present invention relates to an analysis method and apparatus and, more particularly, to a system utilizing Fourier transformation methods for analyzing data and deriving useful information from spectrally analyzed signals, i.e. signals obtained from physical processes and in which there is a frequency variation and amplitudes associated with frequency of such signals.
BACKGROUND OF THE INVENTION
In a number of imaging processes, it is common to subject an object to electromagnetic radiation over a broad spectral range and to analyze reflected or transmitted or scattered or back scattered radiation as a function of time to determine, for example, amplitude as a function of frequency or other parameters of the radiation.
By such methods, which frequently can utilize Fourier analysis of the signals of mixed or varying frequency, it is possible to measure a change in signal intensity as a function of time or a relationship between intensity and frequency which represents data providing information as to the analyzed object. The object can be a part of the human body, some other animate object, an inanimate object or a less tangible object such as speech, music or the like.
The analysis can involve decomposing a mixed frequency signal into different oscillation segments, for example, elemental frequencies, and determining the relative intensities of these segments at a point in time and/or variation of the amplitudes of the different frequencies as a function of time. Typically the analysis utilizes Fourier transformation (FT) and yields an indication of the components or shape or variation in density or presence or absence of cell masses or other patterns of the object.
Fourier transforms are thus used in a variety of image generating and spectroscopic analyses and methods.
In nuclear magnetic resonance spectroscopy, for example, the object can be irradiated with radiant energy pulses in the ultrashort wavelength range whereby protons or other atomic particles or nuclei absorb the applied energy and, depending upon their Larmor frequencies reemit energy. By measuring the time course of a summation signal from the radiation scanning or analysis of the object and utilizing Fourier transformation, for example, in nuclear magnetic resonance spectrometry, frequency spectra can be produced from the time spectra. It is thus possible to determine how many nuclei, for example, absorb or emit and at which frequencies and over the course of time.
An image can thus be generated of tissue densities in the human body and, if the calculation and analysis is done on a real time such images can be displayed and can be interpreted by skilled technicians to signal pathologies or the like.
There are other measurement processes utilizing the same or similar principles in, for example, computer tomography in which the applied radiation is x-ray radiation, magnetic resonance technology also utilizing ultrashort waves, music and spectral analyses of voice or other acoustic signals, as well as various process which utilize data compression (JPEG or MPEG).
The digitized results obtained are processed by, for example, DISCRETE FOURIER TRANSFORMATION (DFT) which yields results which can be treated in terms of the following formula.
A
n
:
=
∑
k
=
0
N
-
1
W
N
nk
a
k
FORMULA
1
In Formula 1:
A=spectrum,
A
n
=point in spectrum,
W
N
=Fourier Factor
N=Number of the Measuring point
a=Measuring Signal
a
k
=point in the measurement signal
n=run number=0, 1, 2, . . . N−1
k=summation index=0,1,2, . . . N−1
The Fourier factor W
N
in turn is equal to the value given in Formula 2
W
N
=exp (±
i
2&pgr;/
N
) Formula 2
or in Formula 3
W
N
nk
=exp (±
i
2&pgr;
nk/N
) Formula 3
In order to process the information especially quickly, the computer or analysis circuitry can be designed so that the right side of Formula 1 is decomposed into sums with even and odd indices k. A
N
can thus be given as shown in Formula 4,
A
n
=
∑
k
=
0
N
-
1
W
N
/
2
n
′
k
a
2
k
⏟
=
:
A
n
′
(
0
)
+
W
N
n
′
∑
k
=
0
N
/
2
-
1
W
N
/
2
n
′
k
a
2
k
+
1
⏟
=
:
A
n
′
(
1
)
FORMULA
4
as the sum of two N/2-point Fourier transformations A
n
′
(0)
and A
n
′
(1)
.
In this relationship:
n′=the number in the sequence of data points=0,1,2. . . ,N/2−1
(0)=the even indices n
(1)=the odd indices n.
With this set of rules, measured information can be evaluated especially rapidly.
A discrete Fourier transformation with N complex value data points (N-Point-DFT) can be reduced by the following mixing rules to two N/2-point DFT:
A
n
·=A
n
(0)
+W
n
′
n
A
n
′(1) Formula 5
A
n
·
+N/2
=A
n
·
(0)
−W
N
n′
A
n
·
(1)
Formula 6
With
n·=
0,1 . . . ,
N/
2−1 For Formulas 4, 5 and 6
If N is the second power, the calculation can be carried out in a fully recursive manner: A
n
results by the mixing of A
n
·
(0)
and A
n
·
(0)
, A
n
·
(0)
can be obtained by a mixing of A
n
(00)
: =(A
n*
(0)
)
(0)
and A
n*
(01)
:=(A
n*
(0),
), A
n′
(1)
by a mixing of A
n*
(10)
:=(A
n*
(1)
)
(0)
) and A
n*
(11)
:=(An″
(1)
)
(1)
etc.
As the starting point for the recursion, the DFT according to Formulas 1 and 2 has individual values equal to this value itself. This means that for each sample of m: =Log
2
(N) ones and zeroes, there is a 1-point DFT which corresponds to the input value
k &egr;<−
0,1, . . . ,
N−
1>:
A
o
(b1b2. . . bm)
=a
k
Formula 7
b
i
&egr;<0,1>;
i=
1,2, . . .
m
Formula 8
For the successive separation of the sum into even and odd indices, for the determination of k the bit sample (b
1
, b
2
, . . . b
m
) is only read from right to left:
A
0
(k)
=a
bit-reversed(k)
Formula 9
With:
k=
0,1, . . . ,
N−
1
which has been found to be cost effective in practice because of the shorter processing time.
OBJECTS OF THE INVENTION
It is, therefore, the principal object of the invention to provide a measurement process or method and a measurement apparatus or chip which significantly reduces the relative error and permits the Fourier transformation to be carried out more rapidly in earlier systems.
It is also an object of the invention to provide improved electronic circuitry for facilitating the improved measurement process or for incorporation in the improved measurement apparatus.
Still another object of the invention is to provide a system for a Fourier transformation of data, especially in image formation, whereby drawbacks of earlier systems are avoided.
SUMMARY OF THE INVENTION
These objects are achieved, in accordance with the invention in an automatic method which comprises the steps of:
(a) acquiring data-carrying signals representing a condition to be analyzed;
(b) subjecting the data-carrying signals to at least one conversion from one domain to at least one other domain by a Fourier transformation involving determination of a Fourier factor W
N
; and
(c) calculating the Fourier factor W
N
using a Factor II defined by the relationship:
&Dgr;
c
1
=cos
x−
1=−2 sin
2
(
x/
2)
where x=2&pgr;/N and N=number of data points.
Preferably the Factor II is transformed in the relationships V and VII as follows:
&Dgr;
c
n+1
=2 &Dgr;
c
1
·c
n
+&Dgr;c
n
Relationship V,
&Dgr;
s
n+1
=2 &Dgr;
c
1
·s
n
+&Dgr;s
n
Relationship VII.
The electronic circuitry in which the method of the invention is embedded can be a chip as will be discussed in greater detail below.
The
Dubno Herbert
Forschungszentrum Julich GmbH
Malzahn David H.
LandOfFree
Fourier analysis method and apparatus calculating the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fourier analysis method and apparatus calculating the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fourier analysis method and apparatus calculating the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3170039