A neural net approach to discrete fourier transforms: A.D. Culhane, M.C. Peckerar, & C.R.K. Marrian. c/o M. C. Peckerar, Code 6804, US Naval Research Laboratory, Washington, D.C. 20375-5000, USA

• Book ID: 103926312
• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 106 KB
• Volume: 1
• Category: Article
• ISSN: 0893-6080
• DOI: 10.1016/0893-6080(88)90456-x

✦ Synopsis

The Discrete Fourier Transform (DFT) is encountered frequently in signal processing, and in general, the faster one can do it, the better. Sequential techniques, such as brute force matrix multiplication or the more efficient Fast Fouder Transform (FFT), regardless of how they are implemented, have the limitation that they operate step-wise, usually on one piece of the data at a time. A brute force approach (for a vector of length N) is O(N2), and the FFT is O(Nlog2N ) in the number of processing steps. The architecture of analog neural nets suggests that a DFT net could be made to operate on entire vectors simultaneously. In addition, it might be hoped that all components of the transformed vector might be made to settle into their correct values with a simple node-charging time constant, without the clocking and synchronization delays normally associated with digital circuits. It is because of this view of neural nets as analog systems that makes them so useful for the DFT, where earlier work, considering neural nets as digital systems, suggested that they would not be [t]. The fact that this can be achieved is demonstrated in this paper.

We have based our approach on the Linear Programming neural net of Tank & Hopfield [2], and its extension by coauthors, Marrian & Peckerar [3], to deconvolution. Tank & Hopfield showed that a neural net could perform optimization subject to constraint, and Marrian & Peckerar manipulated this circuit so as to reconstruct the original value of data convolved with a known system transfer function. To overcome the problem of noise corruption of the data, they introduced a regularizer based on the concept of maximum entropy.

We have modified this deconvolution net so that it will calculate DFTs. We have made use of the Discrete Hartley Transform (DHT) [4], from which the DFT can be derived using a bank of adders, and we are not at this point using a regularizer. The addition of the regularizer is, of course, always possible in the Marrian & Peckerar net. This approach was taken because of the many convenient features of the DHT. For example: (1) the DHT of a real signal is always real, so complex arithmetic is not necessary, (2) the DHT matrix is symmetric, (3) the DHT matrix is always non-singular, and indeed equals a constant times its own inverse, and (4) the DHT matrix has relatively few unique values (alleviating one problem of fabricating the interconnect conductance matrix). Using these and other features, we have been able to show that, in the ideal case, the error between the network's solution and the correct value can be made arbitrarily small by manipulating network parameters, as can the solution time. Furthermore, both the error and the solution time actually decrease with increasing vector length N.

In preparation for device fabrication, we have concentrated on the non.ideal case, and, specifically, on the departures from ideality that we can expect in a VLS1 implementation. We have derived the effects of capacitive delay in the constraint plane amplifiers, and the effects of fabrication inaccuracies in the interconnect conductance matrix. Treating the net as a linear system, we have proven that under reasonable assumptions, a (non-oscillatory) matrix exponential solution is guaranteed. The accuracy of the solutions provided are comparable to those obtained by FFT. We have derived an expression for the error, showing that the error in the result is less than or equal to the error in the interconnect matrix dampened by a factor of approximately "~/'N'. We have also devised an approach to a practical fabrication of the interconnect matrix so as to minimize the error in the result, We have verified our analyses, both ideal and non-ideal, using circuit simulations.

In this paper, we will present the results of neural-net DFT and compare these results with those obtained by standard FFT packages both in terms of speed and accuracy. Circuit simulations verifying the speed and accuracy claims made above will be presented. The need and impact of regularization will also be discussed.Techniques for utilizing the symmetry and limited range of values of the Hartley matrix in providing minimum area circuit layouts will be provided.