NANOSCALE IMAGE PROCESSING - Bio-Inspired and Nanoscale Integrated Computing - page 529

Inputs Outputs

ω = W N/2

X N -1 X[0]/X[N/2]

x 0 x 1 x 2

1 1 1 1

K = 0

X N -1 X[1]/X[N/2+1]

x 0 x 1 x 2

3/2 2 N -1

1 ω ω

ω

K = 1

x 0 x 1 x 2 X N -1

X[N/2-1]/X[N-1]

1

ω ( N/2 − 1) 2 ω ( N/2 − 1) N/ 2

3N/4 − 1/2

ω

K = N/ 2 -1

Figure 19.7. Nanoscale spin-wave FFT module (two-step output method).

or N 2 /2 processing nodes. We present two methods for implementing the FFT
module. The structure of the first implementation of the spin-wave FFT module is
shown in Figure 19.7.
In this implementation, the W N k coefficients are stored in the respective nodes
to which the inputs x[k] are mapped. The multiplication of these two complex
values is performed in the processing nodes and the summation in the spin-wave
bus. Note that for simplifying the equations, W N k term was factored in the odd-
indexed summation. At this step however, for more efficiently implementing the
calculation of W N k F 2 (k), we multiply each of the coefficients by the factor W N k

instead of first finding F 2 (k) and then multiplying it by W N k . So the coefficient that
is multiplied by x[k]isW N k

k

W N/2 :

¼ W 3 N ¼ W 3k = 2

W N W N = 2 ¼ e j2 p k = N e j4 p k = N ¼ e j4 p k = N

ð 19 : 10 Þ

N = 2

The FFT operation is implemented in a similar fashion as the DFT in the
following steps:

1. First the coefficients are multiplied by the inputs in all the nodes. As
explained previously the coefficients in the odd-indexed nodes in each row
contain the extra factor of W N k .
2. All the nodes send the ''real'' part of their data on the spin-wave bus. In
other words, even-indexed nodes send Re[F 1 (k)], and the odd-indexed
nodes send the Re[W N k F 2 (k)]. As a result, X [k] receives the superposition

of these two values: Re[F 1 (k)+W N k F 2 (k)].

3. This step is quite similar to the previous step, except that the nodes send
their ''imaginary'' parts. Therefore,

the superposed result would be

Im[F 1 (k)+W N k F 2 (k)]. At this stage, both the real and imaginary parts

of the complex value [F 1 (k)+W N k F 2 (k)] has been found at row k which is

equal to X[k].