Electrical computers: arithmetic processing and calculating – Electrical analog calculating computer – Particular function performed
Reexamination Certificate
1999-03-08
2001-09-25
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical analog calculating computer
Particular function performed
Reexamination Certificate
active
06295547
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Fourier transform apparatus for performing Fourier transform used for processes such as signal analysis, signal compression and decoding.
2. Description of the Related Art
Fourier transform is indispensable for the processes such as signal analysis, signal compression and decoding. The Fourier transform is based on the idea that “any periodic function can be represented as the sum of trigonometric functions”. A non-periodic signal is considered as a function having an infinite cycle.
Recently, discrete Fourier transform has often been used. A cycle of a sample signal obtained from N sample values of t=0 to t=(N−1) is T=N. A frequency f
N
of this signal is given by the following expression (1):
f
N
=1/
N
(1)
A component of the frequency f
N
is a fundamental-wave component, whereby a harmonic-wave component having a frequency k/N equal to the frequency f
N
multiplied by an integer can be obtained. By using these frequencies, the following expressions of discrete Fourier transform and inverse discrete Fourier transform can be defined based on the definition of the Fourier transform.
Fourier-transform expression (represented by sine-wave and cosine-wave components):
a
(
0
)
=
1
N
∑
k
=
0
k
=
N
-
1
g
(
k
)
a
(
n
/
N
)
=
1
N
∑
k
=
0
k
=
N
-
1
g
(
k
)
cos
(
-
2
π
kn
/
N
)
b
(
n
/
N
)
=
1
N
∑
k
=
0
k
=
N
-
1
g
(
k
)
sin
(
-
2
π
kn
/
N
)
}
(
2
)
Inverse Fourier-transform expression (represented by sine-wave and cosine-wave components):
g
(
n
)
=
a
(
0
)
+
∑
k
=
1
N
-
1
a
(
k
/
N
)
cos
(
2
π
kn
/
N
)
+
∑
k
=
1
N
-
1
b
(
k
/
N
)
sin
(
2
π
kn
/
N
)
(
3
)
where g(n) is a sample signal, and a(n/N) and b(n/N) are Fourier coefficients.
Each of the above expressions, Expressions (2) and (3), is a Fourier expansion expression in which the sine-wave component and cosine-wave component are separated.
Moreover, each of the above Fourier expansion expressions is represented by a complex number by using the following Expression (4):
G
(
n/N
)=
a
(
n/N
)+
jb
(
n/N
) (4)
Fourier-transform expression (represented by a complex number):
G
(
n
/
N
)
=
1
N
∑
k
=
0
k
=
N
-
1
g
(
k
)
exp
(
-
j
2
π
nk
/
N
)
(
5
)
Inverse Fourier-transform expression (represented by a complex number):
g
(
n
)
=
∑
k
=
0
N
-
1
G
(
k
/
N
)
exp
(
j
2
π
kn
/
N
)
(
6
)
Moreover, G(n/N) and G
n
, are simplified as g(n) and g
n
, respectively, and each of the above Fourier-transform expressions is represented by a rotator T given by the following Expression (7):
T=
exp(−
j
2&pgr;/
N
) (7)
Fourier-transform expression (represented by a rotator):
G
n
=
1
N
∑
k
=
0
N
-
1
g
k
T
nk
(
8
)
Inverse Fourier-transform expression (represented by a rotator):
g
n
=
∑
k
=
0
N
-
1
G
n
T
-
nk
(
9
)
Each of the above Fourier-transform expressions requires an enormous amount of calculation. Therefore, it is difficult to apply such Fourier-transform expressions directly to an actual operation. As a result, more practical “fast Fourier transform” (hereinafter, simply referred to as “FFT”) is used.
The FFT is an algorithm wherein the number of multiplying operations of sample signal g
k
and rotator T
nk
as well as the number of adding and subtracting operations represented by &Sgr; in a transform expression are significantly reduced.
The FFT is applied in a variety of fields, and numerous types of algorithms have been proposed for the FFT. Each such algorithm has respective specific characteristics in terms of simplicity, operation speed, software-program configuration, advantageous property for implementing hardware, or the like. Among these, the FFT with a radix of 2 is most typically used.
The FFT with a radix of 2 is as follows:
First, it is assumed that the number N of sample values is 2
n
(where n is an integer).
e
(
n
)
=
g
(
2
n
)
h
(
n
)
=
g
(
2
n
+
1
)
;
n
=
0
,
1
,
…
,
N
/
2
-
1
}
(
10
)
When a coefficient 1/N is omitted, the following Fourier-transform expression can be obtained:
G
k
=
∑
n
=
0
N
-
1
g
k
T
nk
=
∑
n
=
0
N
/
2
-
1
(
e
(
n
)
T
2
nk
+
h
(
n
)
T
(
2
n
+
1
)
k
)
(
11
)
G
k
{
E
k
+
T
k
H
k
;
0
≤
k
≤
N
2
-
1
E
k
-
N
/
2
+
T
k
H
k
-
N
/
2
;
N
2
≤
k
≤
N
-
1
}
(
12
)
where
E
k
=
∑
n
=
0
N
/
2
-
1
e
(
n
)
T
2
nk
H
k
=
∑
n
=
0
N
/
2
-
1
h
(
n
)
T
2
nk
}
(
13
)
In the case of, for example, N=2
n0
, this algorithm can be utilized n
0
times, as shown in FIG.
7
.
In
FIG. 7
, DFT indicates discrete Fourier transform. In the case of, for example, N=2
4
, the algorithm is repeated four times.
The algorithm is primarily configured from a basic operation called “butterfly operation”. In order to implement the butterfly operation, a bit-reversal method of input data and coefficient is used.
Only the fast Fourier transform has been mentioned herein. The operation of inverse Fourier transform is substantially the same as that of the fast Fourier transform, except that G
k
and g
n
are exchanged each other. Therefore, description thereof is omitted.
Other specific examples include the techniques disclosed in Japanese Laid-Open Publication Nos. 5-189470, 5-174046 and 5-189471, respectively.
Japanese Laid-Open Publication No. 5-189470 relates to a method for performing time-series data input type Fourier transform, and discloses Fourier transform which is performed in a digital manner. In this method, a number of operation devices and buffers are employed together with the above-mentioned FFT algorithm to perform Fourier transform In real time. This method is characterized in that the process is initiated before all of N data have been collected.
Japanese Laid-Open Publication No. 5-174046 shows a circuit configuration wherein the butterfly operation is performed in a digital manner by using a multiplier or the like as an operation circuit.
In Japanese Laid-Open Publication No. 5-189471, a butterfly-type operation device performs FFT in a pipeline manner by using a bit-reversal addressing technique or the like. This is a typical method for implementing an FFT processor.
The above-mentioned FFT algorithm is not problematic in the case of off-line data analysis using a high-level language. However, in the case where on-line data processing is conducted by using DSP (Digital Signal Processor), that is, in the case where audio data or image data which has been compressed by Fourier transform is reproduced, for example, in real time, the FFT algorithm has some disadvantages as follows:
(1) the algorithm must be changed dependent upon hardware.
Since software is dependent upon the hardware, new software and a new algorithm must be produced when the hardware is changed, whereby the development period is increased;
(2) Since a special operation is performed, data processing other than FFT is adversely affected.
In order to implement the bit-reversal of the butterfly operation, special addressing must be conducted by hardware. Therefore, when general-purpose processes are simultaneously conducted by the same hardware, a long instruction code is required. As a result, the hardware is not efficiently utilized, as well as an instruction-memory capacity is increased, leading to an increase in the cost;
(3) The accuracy is limited by the speed.
In order to increase the processing accuracy, the number of bits must be increased to some extent. According t
Fukuda Naoyuki
Zhang Xiaomang
Mai Tan V.
Sharp Kabushiki Kaisha
LandOfFree
Fourier transform apparatus 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 transform apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fourier transform apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2464027