Factorization of spectra by discrete Fourier transforms
Discrete Fourier transform factorization of arbitrary spectral density functions
Rino, C. L.↗
SEARCH · Search NASA
Results for “Discrete fourier transform”
Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.
Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.
Factorization of spectra by discrete Fourier transforms
Discrete Fourier transform method for factoring spectral density functions, calculating absolute error
Rino, C. L.↗
Geometric interpretations of the Discrete Fourier Transform (DFT)
One, two, and three dimensional Discrete Fourier Transforms (DFT) and geometric interpretations of their periodicities are presented. These operators are examined for their relationship with the two sided, continuous Fourier transform. Discrete or continuous transforms of real functions have certain symmetry properties. The symmetries are examined for the one, two, and three dimensional cases. Extension to higher dimension is straight forward.
Campbell, C. W.↗
High-dimensional discrete Fourier transform gates with a quantum frequency processor
The discrete Fourier transform (DFT) is of fundamental interest in photonic quantum information, yet the ability to scale it to high dimensions depends heavily on the physical encoding, with practical recipes lacking in emerging platforms such as frequency bins. In this article, we show that d -point frequency-bin DFTs can be realized with a fixed three-component quantum frequency processor (QFP), simply by adding to the electro-optic modulation signals one radio-frequency harmonic per each incremental increase in d . We verify gate fidelity F W > 0.9997 and success probability P W > 0.965 up to d = 10 in numerical simulations, and experimentally implement the solution for d = 3, utilizing measurements with parallel DFTs to quantify entanglement and perform tomography of multiple two-photon frequency-bin states. Our results furnish new opportunities for high-dimensional frequency-bin protocols in quantum communications and networking.
97 MATHEMATICS AND COMPUTING↗
Discrete fourier transform (DFT) analysis for applications using iterative transform methods
According to various embodiments, a method is provided for determining aberration data for an optical system. The method comprises collecting a data signal, and generating a pre-transformation algorithm. The data is pre-transformed by multiplying the data with the pre-transformation algorithm. A discrete Fourier transform of the pre-transformed data is performed in an iterative loop. The method further comprises back-transforming the data to generate aberration data.
Dean, Bruce H.↗
Multiplexing and Demultiplexing Signals for Radiography Application Using the Discrete Fourier Transform
Our goal is to develop an X-ray phase-contrast imaging system that can provide excellent soft tissue contrast of phase, attenuation, and small-angle scatter. We propose to replace the common system of G0, G1, and G2 gradings with a biprism array to replace the G1 grading and introduce a novel X-ray tube designed to replace the motion of the phase stepping grading G2. The proposed X-ray tube uses temporal multiplexing to provide simultaneous virtual “electronic phase stepping.” In this work the discrete Fourier transform is used to separate from the composite measurement individual X-ray phase contrast measurements sampled at different frequencies. The method performs a discrete Fourier transform of a composite refence sequence to obtain using the frequency amplitudes calibration factors needed to extract the X-ray phase contrast measurement amplitudes from the composite image. The composite reference sequence is the sum of the individual sequences, at different frequencies, with amplitudes of one. The method takes the discrete Fourier transform of this composite reference sequence; whereby, the amplitude of each frequency component is compared with the total sum of its stand-alone sequence amplitude. A calibration factor is determined so that the amplitude of this composite reference frequency times the calibration factor must equal the total sum of the sequence amplitude—the zero-frequency amplitude of the discrete Fourier transform of its stand-alone sequence. To demultiplex the composite measured signal these calibration factors are multiplied by the amplitudes of the frequency components of the discrete Fourier transform of the composite X-phase-contrast measurement to obtain the amplitude of each frequency encoded measurement. Using these calibration factors, we demonstrate with the discrete Fourier transform in Mathematica the extraction of individual images from a composite image that one would expect obtaining from our proposed new X-ray phase contrast imaging system. We then demonstrate as an example how using images from X-ray phase contrast data one can calculate phase, attenuation and the dark field images using grading phase step data supplied to use from Microworks, GmbH in Karlsruhe, Germany.
42 ENGINEERING↗
Geometric Representations for Discrete Fourier Transforms
Simple geometric representations show symmetry and periodicity of discrete Fourier transforms (DFT's). Help in visualizing requirements for storing and manipulating transform value in computations. Representations useful in any number of dimensions, but particularly in one-, two-, and three-dimensional cases often encountered in practice.
Cambell, C. W.↗
A Study of Derivative Filters Using the Discrete Fourier Transform
Important properties of derivative (difference) filters using the discrete Fourier transform are investigated. The filters are designed using the derivative theorem of Fourier analysis. Because physical data are generally degraded by noise, the derivative filter is modified to diminish the effects of the noise, especially the noise amplification which normally occurs while differencing. The basis for these modifications is the reduction of those Fourier components for which the noise most dominates the data. The various filters are tested by applying them to find differences of two-dimensional data to which various amounts of signal dependent noise, as measured by a root mean square value, have been added. The modifications, circular and square ideal low-pass filters and a cut-off pyramid filter, are all found to reduce noise in the derivative without significantly degrading the result.
Ioup, G. E.↗
A prescription of Winograd's discrete Fourier transform algorithm
A detailed and complete description of Winograd's discrete Fourier transform algorithm (DFT) is presented omitting all proofs and derivations. The algorithm begins with the transfer of data from the input vector array to the working array where the actual transformation takes place, otherwise known as input scrambling and output unscrambling. The third array holds constraints required in the transformation stage that are evaluated in the precomputation stage. The algorithm is made up of several FORTRAN subroutines which are not to be confused with practical software algorithmic implementation since they are designed for clarity and not for speed.
Zohar, S.↗
A discrete Fourier transform for virtual memory machines
An algebraic theory of the Discrete Fourier Transform is developed in great detail. Examination of the details of the theory leads to a computationally efficient fast Fourier transform for the use on computers with virtual memory. Such an algorithm is of great use on modern desktop machines. A FORTRAN coded version of the algorithm is given for the case when the sequence of numbers to be transformed is a power of two.
Galant, David C.↗
A Discussion of Using a Reconfigurable Processor to Implement the Discrete Fourier Transform
This paper presents the design and implementation of the Discrete Fourier Transform (DFT) algorithm on a reconfigurable processor system. While highly applicable to many engineering problems, the DFT is an extremely computationally intensive algorithm. Consequently, the eventual goal of this work is to enhance the execution of a floating-point precision DFT algorithm by off loading the algorithm from the computing system. This computing system, within the context of this research, is a typical high performance desktop computer with an may of field programmable gate arrays (FPGAs). FPGAs are hardware devices that are configured by software to execute an algorithm. If it is desired to change the algorithm, the software is changed to reflect the modification, then download to the FPGA, which is then itself modified. This paper will discuss methodology for developing the DFT algorithm to be implemented on the FPGA. We will discuss the algorithm, the FPGA code effort, and the results to date.
White, Michael J.↗
A new hybrid algorithm for computing a fast discrete Fourier transform
For certain long transform lengths, Winograd's algorithm for computing the discrete Fourier transform is extended considerably. This is accomplished by performing the cyclic convolution, required by Winograd's method, with the Mersenne-prime number theoretic transform. This new algorithm requires fewer multiplications than either the standard fast Fourier transform or Winograd's more conventional algorithm.
Reed, I. S.↗
High resolution frequency analysis techniques with application to the redshift experiment
High resolution frequency analysis methods, with application to the gravitational probe redshift experiment, are discussed. For this experiment a resolution of .00001 Hz is required to measure a slowly varying, low frequency signal of approximately 1 Hz. Major building blocks include fast Fourier transform, discrete Fourier transform, Lagrange interpolation, golden section search, and adaptive matched filter technique. Accuracy, resolution, and computer effort of these methods are investigated, including test runs on an IBM 360/65 computer.
Decher, R.↗
Discrete Fourier Transform Analysis in a Complex Vector Space
Alternative computational strategies for the Discrete Fourier Transform (DFT) have been developed using analysis of geometric manifolds. This approach provides a general framework for performing DFT calculations, and suggests a more efficient implementation of the DFT for applications using iterative transform methods, particularly phase retrieval. The DFT can thus be implemented using fewer operations when compared to the usual DFT counterpart. The software decreases the run time of the DFT in certain applications such as phase retrieval that iteratively call the DFT function. The algorithm exploits a special computational approach based on analysis of the DFT as a transformation in a complex vector space. As such, this approach has the potential to realize a DFT computation that approaches N operations versus Nlog(N) operations for the equivalent Fast Fourier Transform (FFT) calculation.
Dean, Bruce H.↗
A new hybrid algorithm for computing a fast discrete Fourier transform
In this paper for certain long transform lengths, Winograd's algorithm for computing the discrete Fourier transform (DFT) is extended considerably. This is accomplished by performing the cyclic convolution, required by Winograd's method, with the Mersenne prime number-theoretic transform developed originally by Rader. This new algorithm requires fewer multiplications than either the standard fast Fourier transform (FFT) or Winograd's more conventional algorithm. However, more additions are required.
Reed, I. S.↗
Direct interpolative construction of the discrete Fourier transform as a matrix product operator
The quantum Fourier transform (QFT), which can be viewed as a reindexing of the discrete Fourier transform (DFT), has been shown to be compressible as a low-rank matrix product operator (MPO) or quantized tensor train (QTT) operator. However, the original proof of this fact does not furnish a construction of the MPO with a guaranteed error bound. Meanwhile, the existing practical construction of this MPO, based on the compression of a quantum circuit, is not as efficient as possible. We present a simple closed-form construction of the QFT MPO using the interpolative decomposition, with guaranteed near-optimal compression error for a given rank. This construction can speed up the application of the QFT and the DFT, respectively, in quantum circuit simulations and QTT applications. We also connect our interpolative construction to the approximate quantum Fourier transform (AQFT) by demonstrating that the AQFT can be viewed as an MPO constructed using a different interpolation scheme.
97 MATHEMATICS AND COMPUTING↗
A Discussion of the Discrete Fourier Transform Execution on a Typical Desktop PC
This paper will discuss and compare the execution times of three examples of the Discrete Fourier Transform (DFT). The first two examples will demonstrate the direct implementation of the algorithm. In the first example, the Fourier coefficients are generated at the execution of the DFT. In the second example, the coefficients are generated prior to execution and the DFT coefficients are indexed at execution. The last example will demonstrate the Cooley- Tukey algorithm, better known as the Fast Fourier Transform. All examples were written in C executed on a PC using a Pentium 4 running at 1.7 Ghz. As a function of N, the total complex data size, the direct implementation DFT executes, as expected at order of N2 and the FFT executes at order of N log2 N. At N=16K, there is an increase in processing time beyond what is expected. This is not caused by implementation but is a consequence of the effect that machine architecture and memory hierarchy has on implementation. This paper will include a brief overview of digital signal processing, along with a discussion of contemporary work with discrete Fourier processing.
White, Michael J.↗
Calibration of optical detectors using discrete Fourier transform techniques
A method for determining the detector electrooptical transfer function (DEOTF) at different discrete frequencies simultaneously is presented. It involves simulation of the detector with a waveform of unknown frequency composition, such as a square wave or impulse function. The DEOTF is calculated as the ratio of the discrete Fourier transform of the detector output to the transform of the input waveform. This technique was successfully applied to Golay cell and bolometer detectors and can be used for other linear detector systems.
Hagopian, John G.↗