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

even-indexed nodes send their data on two different frequencies, there is no
interference between the two.
3. This step is similar to step 1, except that the nodes send the ''imaginary''
part of their data. The frequency tunings remains the same as previous
step; therefore, out1 nodes receive Im[F 1 (k)], while out2 nodes receive
Im[W N k F 2 (k)]. At this stage, out1 nodes contain the complex value of

F 1 (k), and out2, W N k F 2 (k).

4. At this step, out1 and out2 switch frequencies. The receiving frequency of
the out1 nodes is tuned on f odd and out2 on f even and step 2 is repeated. As
a result the Re[F 1 (k)] is received by out2 and Re[W N k

F 2 (k)] by out1.
5. This step is similar to step 4, except that the imaginary parts are broad-
casted. At this stage each of out1 and out2 contain both the complex values
of W N k

F 2 (k)andF 1 (k).
6. Out1 nodes compute and output X[k]=F 1 (k)+W N k F 2 (k) while out2 nodes

compute and output X[k+N/2]=F 1 (k) W N k

, N/2 1.
These addition and subtraction of complex numbers include two addition
and subtraction for the real and imaginary parts.

F 2 (k) for k=0, y

The time complexity of both methods of implementing FFT, similar to DFT,
is O(1). As mentioned previously, one of the applications of Fourier transform is
in designing digital filters. In digital filter design problems, the filter coefficients
should be found based on a filter's desired frequency response. The filter's
frequency response can be simplified to the form of the Fourier transform of
the filter coefficients. Therefore, the filter coefficients can be calculated simply by
taking the inverse Fourier transform of the desired frequency response. Finding
the inverse Fourier transform using spin-wave architectures is possible in a similar
fashion to finding discrete Fourier transform, discussed in this section.

19.3. CONCLUSIONS

This chapter showed how image processing tasks can be performed very fast on
nanoscale spin-wave architectures. Solutions to three image processing problems,
namely, labeling, finding the convex hull, and finding the nearest neighbor
problem, were presented. In addition, efficient implementations of spin-wave
modules for computing discrete Fourier transform (DFT) and fast Fourier
transform (FFT) were shown.

REFERENCES

1. H. M. Alnuweiri. Constant-time parallel algorithms for image labeling on a reconfigur-
able network of processors. IEEE Transactions on Parallel and Distributed Systems,
5(3): pp 320-326, Mar 1994.