Information Technology Reference
In-Depth Information
Inputs
Output
X[0]
ω = W N
x 0
x 1
x 2
x N 1
1
1
1
1
K
= 0
x 0
x 1
x 2
x N 1
X[1]
2
ω
ω
N
1
1
ω
K
= 1
x N 1
x 0
x 1
x 2
X[N-1]
ω ( N 1) 2
ω ( N 1) N
1
N
1
ω
K
= N -1
Figure 19.6. Nanoscale spin-wave DFT module.
part on the second step. Therefore, the outputs receive the real and imaginary
parts of the X[k] in two steps. The time complexity of this process depends on the
time complexity of the multiplication, since the summation in done in O(1) time.
Multiplication of two numbers can be performed in constant time using a
nanoscale spin-wave multiplication module presented in Chapter 9. Therefore
the time-complexity of computing the DFT coefficients is O(1).
The IDFT module can be implemented in a similar fashion as the DFT
module. The only difference is in the coefficients that are stored in each processing
node. In a DFT module the coefficient stored in the node in row k and column N is
W N k , while in an IDFT module, this coefficient is 1/N W N k .
The design of the DFT module, as shown in Figure 19.2, requires N 2
processing nodes. In the following we show that the radix-2 decimation-in-time
FFT algorithm can be implemented by N 2 /2 processing nodes. As discussed in the
previous section, the outputs of the radix-2 decimation-in-time FFT algorithm are
computed as
N
2 1
X ð k Þ¼ F 1 ð k Þþ W N F 2 ð k Þ;
k ¼ 0
;
1
; ...;
¼ F 1 ð k Þþ W N F 2 ð k Þ;
2 1 :
ð 19
:
9 Þ
N
2
N
Xk þ
k ¼ 0
;
1
; ...;
From Equation 19.9, we can see that by finding F 1 (k) and F 2 (k) for N/2 (odd
and even) points, two Fourier coefficients, namely X[k] and X[k+N/2], can be
computed at the same time. By observing this fact, we implement the FFT module
as an array of N/2 N input and N output computing nodes. In other words, the
design of the DFT module is improved by eliminating half of the processor rows
 
Search WWH ::




Custom Search