| Hybrid VLSI/QCA Architecture for Computing FFTs |
|
|
| NASA's Jet Propulsion Laboratory, Pasadena, California | |
| Mar 31 2003 | |
Simplification is effected through use of QCA circuitry to permute data.
advertisement:
A data-processor architecture that would incorporate elements of both conventional very-large-scale integrated (VLSI) circuitry and quantum- dot cellular automata (QCA) has been proposed to enable the highly parallel and systolic computation of fast Fourier transforms (FFTs). The proposed circuit would complement the QCA- based circuits described in several prior NASA Tech Briefs articles, namely "Implementing Permutation Matrices by Use of Quantum Dots" (NPO-20801), Vol. 25, No. 10 (October 2001), page 42; "Compact Interconnection Networks Based on Quantum Dots" (NPO-20855) Vol. 27, No. 1 (January 2003), page 32; and "Bit-Serial Adder Based on Quantum Dots" (NPO-20869), Vol. 27, No. 1 (January 2003), page 35. The cited prior articles described the limitations of very-large-scale integrated (VLSI) circuitry and the major potential advantage afforded by QCA. To recapitulate: In a VLSI circuit, signal paths that are required not to interact with each other must not cross in the same plane. In contrast, for reasons too complex to describe in the limited space available for this article, suitably designed and operated QCA-based signal paths that are required not to interact with each other can nevertheless be allowed to cross each other in the same plane without adverse effect. In principle, this characteristic could be exploited to design compact, coplanar, simple (relative to VLSI) QCA-based networks to implement complex, advanced interconnection schemes. To enable a meaningful description of the proposed FFT-processor architecture, it is necessary to further recapitulate the description of a quantum-dot cellular automaton from the first-mentioned prior article: A quantum-dot cellular automaton contains four quantum dots positioned at or between the corners of a square cell. The cell contains two extra mobile electrons that can tunnel (in the quantum-mechanical sense) between neighboring dots within the cell. The Coulomb repulsion between the two electrons tends to make them occupy antipodal dots in the cell. For an isolated cell, there are two energetically equivalent arrangements (denoted polarization states) of the extra electrons. The cell polarization is used to encode binary information. Because the polarization of a nonisolated cell depends on Coulomb-repulsion interactions with neighboring cells, universal logic gates and binary wires could be constructed, in principle, by arraying QCA of suitable design in suitable patterns. Again, for reasons too complex to describe here, in order to ensure accuracy and timeliness of the output of a QCA array, it is necessary to resort to an adiabatic switching scheme in which the QCA array is divided into subarrays, each controlled by a different phase of a multiphase clock signal. In this scheme, each subarray is given time to perform its computation, then its state is frozen by raising its interdot potential barriers and its output is fed as the input to the successor subarray. The successor subarray is kept in an unpolarized state so it does not influence the calculation of preceding subarray. Such a clocking scheme is consistent with pipeline computation in the sense that each different subarray can perform a different part of an overall computation. In other words, QCA arrays are inherently suitable for pipeline and, moreover, systolic computations. This sequential or pipeline aspect of QCA would be utilized in the proposed FFT-processor architecture.  Figure 1. QCA Are Assembled Into Binary Wires, and the wires are patterned to implement a perfect-shuffle permutation matrix known as Π8.  where n is an integer; F2n is a radix-2 FFT for a 2n-dimensional vector; Π2n, Si(where i is an integer), and P2n are various permutation operators or matrices; and the Ki are arithmetic operators.  Figure 2. A Hybrid of VLSI and QCA Circuit Modules would perform a parallel, systolic computation of an FFT. The particular circuit architecture is based on a matrix factorization of the FFT. This work was done by Amir Fijany, Nikzad Toomarian, Katayoon Modarres, and Matthew Spotnitz of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Computers/Electronics category. NPO-20923. This Brief includes a Technical Support Package (TSP).
Hybrid VLSI/QCA Archetiecture for Computing FFTs (reference NPO-20923) is currently available for download from the TSP library. Login first to download.
|
