Search NASA⌕ Search

SEARCH · Search NASA

Results for “Fast 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.

At least 181 records · Page 10
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Rotational Millimeter-Wave Shoe Scanner Using the Discrete Fourier Transform for Backprojection-Based Image Reconstruction

An active 3D microwave / millimeter-wave shoe scanner was previously developed at the Pacific Northwest National Laboratory (PNNL) using two linear arrays scanned over a rectilinear aperture. The radar system chirps a frequency sweep from 10-40 GHz. These frequencies allow imaging through optically opaque material such as leather, rubber, plastics, and other dielectrics. The system was designed to detect concealed items in the soles of shoes while allowing people to leave their shoes on through a security checkpoint. To shrink the footprint of the system, a new iteration of the design has been developed that scans the two linear arrays over a circular aperture. This new footprint opens the possibility of it being installed in the floor of a cylindrical millimeter-wave body scanner. The backprojection-based multilayer dielectric image reconstruction developed at PNNL can easily handle arbitrary spatial sampling, accommodating the new rotational shoe scanner design. Commonly, the fast Fourier transform (FFT) is used to efficiently compute the range response from the data collected by the system as a preprocessing step to the backprojection algorithm. It was found that converting to range using the discrete Fourier transform (DFT) directly has some advantages over the FFT. For example, nonlinear and non-uniform frequency sweeps can easily be compensated for during the computation of the DFT and only the range bins of interest need to be computed and their spacing can be chosen arbitrarily. Because the range conversion step of the image reconstruction is the fastest part of the process there is very little speed penalty for using the DFT over the FFT and it can even increase the speed of image reconstruction when the ranges of interest are fewer than the total span that is calculated in the FFT.

Millimeter-wave imaging, microwave imaging, shoe s↗
DOE OSTI2025

A Linear-Complexity Tensor Butterfly Algorithm for Compressing High-Dimensional Oscillatory Integral Operators

This paper presents a multilevel tensor compression algorithm called tensor butterfly algorithm for efficiently representing large-scale and high-dimensional oscillatory integral operators, including Green's functions for wave equations and integral transforms such as Radon transforms and Fourier transforms. The proposed algorithm leverages a tensor extension of the so-called complementary low-rank property of existing matrix butterfly algorithms. The algorithm partitions the discretized integral operator tensor into subtensors of multiple levels and factorizes each subtensor at the middle level as a Tucker-type interpolative decomposition, whose factor matrices are formed in a multilevel fashion. For a d-dimensional (d > 1) integral operator discretized into a 2d-mode tensor with n2d entries, the overall CPU time and memory requirement scale as O(nd), in stark contrast to the O(nd log n) complexity of existing matrix algorithms such as matrix butterfly algorithms and fast Fourier transforms (FFTs), where n is the number of points per direction. When comparing with other tensor algorithms such as quantized tensor train (QTT), the proposed algorithm also shows superior CPU and memory performance for tensor contraction. Remarkably, the tensor butterfly algorithm can efficiently model high-frequency Green's function interactions between two unit cubes, each spanning 512 wavelengths per direction, which represents problems of scale over 512× larger than that existing butterfly algorithms can handle, with the same amount of computation resources. On the other hand, for a problem representing 64 wavelengths per direction, which is the largest size existing algebraic matrix algorithms can handle, our tensor butterfly algorithm exhibits 200x speedups and 30× memory reduction compared with existing ones. Moreover, the tensor butterfly algorithm also permits O(nd)-complexity FFTs and Radon transforms up to d = 6 dimensions.

Kielstra, P Michael↗
NASA NTRS2011

NASA Tech Briefs, April 2011

Topics covered include: Amperometric Solid Electrolyte Oxygen Microsensors with Easy Batch Fabrication; Two-Axis Direct Fluid Shear Stress Sensor for Aerodynamic Applications; Target Assembly to Check Boresight Alignment of Active Sensors; Virtual Sensor Test Instrumentation; Evaluation of the Reflection Coefficient of Microstrip Elements for Reflectarray Antennas; Miniaturized Ka-Band Dual-Channel Radar; Continuous-Integration Laser Energy Lidar Monitor; Miniaturized Airborne Imaging Central Server System; Radiation-Tolerant, SpaceWire-Compatible Switching Fabric; Small Microprocessor for ASIC or FPGA Implementation; Source-Coupled, N-Channel, JFET-Based Digital Logic Gate Structure Using Resistive Level Shifters; High-Voltage-Input Level Translator Using Standard CMOS; Monitoring Digital Closed-Loop Feedback Systems; MASCOT - MATLAB Stability and Control Toolbox; MIRO Continuum Calibration for Asteroid Mode; GOATS Image Projection Component; Coded Modulation in C and MATLAB; Low-Dead-Volume Inlet for Vacuum Chamber; Thermal Control Method for High-Current Wire Bundles by Injecting a Thermally Conductive Filler; Method for Selective Cleaning of Mold Release from Composite Honeycomb Surfaces; Infrared-Bolometer Arrays with Reflective Backshorts; Commercialization of LARC (trade mark) -SI Polyimide Technology; Novel Low-Density Ablators Containing Hyperbranched Poly(azomethine)s; Carbon Nanotubes on Titanium Substrates for Stray Light Suppression; Monolithic, High-Speed Fiber-Optic Switching Array for Lidar; Grid-Tied Photovoltaic Power System; Spectroelectrochemical Instrument Measures TOC; A Miniaturized Video System for Monitoring Drosophila Behavior; Hydrofocusing Bioreactor Produces Anti-Cancer Alkaloids; Creep Measurement Video Extensometer; Radius of Curvature Measurement of Large Optics Using Interferometry and Laser Tracker n-B-pi-p Superlattice Infrared Detector; Safe Onboard Guidance and Control Under Probabilistic Uncertainty; General Tool for Evaluating High-Contrast Coronagraphic Telescope Performance Error Budgets; Hidden Statistics of Schroedinger Equation; Optimal Padding for the Two-Dimensional Fast Fourier Transform; Spatial Query for Planetary Data; Higher Order Mode Coupling in Feed Waveguide of a Planar Slot Array Antenna; Evolutionary Computational Methods for Identifying Emergent Behavior in Autonomous Systems; Sampling Theorem in Terms of the Bandwidth and Sampling Interval; Meteoroid/Orbital Debris Shield Engineering Development Practice and Procedure; Self-Balancing, Optical-Center-Pivot, Fast-Steering Mirror; Wireless Orbiter Hang-Angle Inclinometer System; and Internal Electrostatic Discharge Monitor - IESDM.

Source record↗
NASA NTRS1984

Microprocessor implementation of an FFT for ionospheric VLF observations

A fast Fourier transform algorithm is implemented on a CMOS microprocessor for application to very low-frequency electric fields (less than 10 kHz) sensed on high-altitude scientific balloons. Two FFT's are calculated simultaneously by associating them with conjugate symmetric and conjugate antisymmetric results. One goal of the system was to detect spectral signatures associated with fast time variations present in natural signals such as whistlers and chorus. Although a full evaluation of the system was not possible for operational reasons, a measure of the system's success has been defined and evaluated.

Elvidge, J.↗
NASA NTRS1981

Rapid, high-order accurate calculation of flows due to free source or vortex distributions

Fast Fourier transform (FFT) techniques are applied to the problem of finding the flow due to source or vortex distributions in the field outside an airfoil or other two-dimensional body. Either the complex potential or the complex velocity may be obtained to a high order of accuracy, with computational effort similar to that required by second-order fast Poisson solvers. These techniques are applicable to general flow problems with compressibility and rotation. An example is given of their use for inviscid compressible flow.

Halsey, D.↗
NASA NTRS2006

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.↗
NASA NTRS1980

On the application of a fast polynomial transform and the Chinese remainder theorem to compute a two-dimensional convolution

A fast algorithm is developed to compute two dimensional convolutions of an array of d sub 1 X d sub 2 complex number points, where d sub 2 = 2(M) and d sub 1 = 2(m-r+) for some 1 or = r or = m. This algorithm requires fewer multiplications and about the same number of additions as the conventional fast fourier transform method for computing the two dimensional convolution. It also has the advantage that the operation of transposing the matrix of data can be avoided.

Truong, T. K.↗
NASA NTRS2004

Faster Processing for Inverting GPS Occultation Data

A document outlines a computational method that can be incorporated into two prior methods used to invert Global Positioning System (GPS) occultation data [signal data acquired by a low-Earth-orbiting satellite as either this or the GPS satellite rises above or falls below the horizon] to obtain information on altitude-dependent properties of the atmosphere. The two prior inversion methods, known as back propagation and canonical transform, are computationally expensive because for each occultation, they involve numerical evaluation of a large number of diffraction-like spatial integrals. The present method involves an angular-spectrum-based phase-extrapolation approximation in which each data point is associated with a plane-wave component that propagates in a unique direction from the orbit of the receiving satellite to intersect a straight line tangent to the orbit at a nearby point. This approximation enables the use of fast Fourier transforms (FFTs), which apply only to data collected along a straight-line trajectory. The computation of the diffraction-like integrals in the angular-spectrum domain by use of FFTs takes only seconds, whereas previously, it took minutes.

Ao, Chi↗
NASA NTRS1997

Tracking of Ice Edges and Ice Floes by Wavelet Analysis of SAR Images

This paper demonstrates the use of wavelet transforms in the tracking of sequential ice features in the ERS-1 synthetic aperture radar (SAR) imagery, especially in situations where feature correlation techniques fail to yield reasonable results. Examples include the evolution of the St. Lawrence polynya and summer sea ice change in the Beaufort Sea. For the polynya, the evolution of the region of young ice growth surrounding a polynya can be easily tracked by wavelet analysis due to the large backscatter difference between the young and old ice. Also within the polynya, a 2D fast Fourier transform (FFT) is used to identify the extent of the Langmuir circulation region, which is coincident with the wave-agitated frazil ice growth region, where the sea ice experiences its fastest growth. Therefore, the combination of wavelet and FFT analysis of SAR images provides for the large-scale monitoring of different polynya features. For summer ice, previous work shows that this is the most difficult period for ice trackers due to the lack of features on the sea ice cover. The multiscale wavelet analysis shows that this method delineates the detailed floe shapes during this period, so that between consecutive images, the floe translation and rotation can be estimated.

Liu, Antony K.↗
DOE OSTI2022

Apodization Specific Fitting for Improved Resolution, Charge Measurement, and Data Analysis Speed in Charge Detection Mass Spectrometry

Short-time Fourier transforms with short segment lengths are typically used to analyze single ion charge detection mass spectrometry (CDMS) data either to overcome effects of frequency shifts that may occur during the trapping period or to more precisely determine the time at which an ion changes mass or charge, or enters an unstable orbit. The short segment lengths can lead to scalloping loss unless a large number of zero-fills are used, making computational time a significant factor in real-time analysis of data. Apodization specific fitting leads to a 9-fold reduction in computation time compared to zero-filling to a similar extent of accuracy. This makes possible real-time data analysis using a standard desktop computer. Rectangular apodization leads to higher resolution than the more commonly used Gaussian or Hann apodization and makes it possible to separate ions with similar frequencies, a significant advantage for experiments in which the masses of many individual ions are measured simultaneously. Equally important is a >20% increase in S/N obtained with rectangular apodization compared to Gaussian or Hann, which directly translates to a corresponding improvement in accuracy of both charge measurements and ion energy measurements that rely on the amplitudes of the fundamental and harmonic frequencies. Finally, combined with computing the fast Fourier transform in a lower-level language, this fitting procedure eliminates computational barriers and should enable real-time processing of CDMS data on a laptop computer.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRS1994

The Block V Receiver fast acquisition algorithm for the Galileo S-band mission

A fast acquisition algorithm for the Galileo suppressed carrier, subcarrier, and data symbol signals under low data rate, signal-to-noise ratio (SNR) and high carrier phase-noise conditions has been developed. The algorithm employs a two-arm fast Fourier transform (FFT) method utilizing both the in-phase and quadrature-phase channels of the carrier. The use of both channels results in an improved SNR in the FFT acquisition, enabling the use of a shorter FFT period over which the carrier instability is expected to be less significant. The use of a two-arm FFT also enables subcarrier and symbol acquisition before carrier acquisition. With the subcarrier and symbol loops locked first, the carrier can be acquired from an even shorter FFT period. Two-arm tracking loops are employed to lock the subcarrier and symbol loops parameter modification to achieve the final (high) loop SNR in the shortest time possible. The fast acquisition algorithm is implemented in the Block V Receiver (BVR). This article describes the complete algorithm design, the extensive computer simulation work done for verification of the design and the analysis, implementation issues in the BVR, and the acquisition times of the algorithm. In the expected case of the Galileo spacecraft at Jupiter orbit insertion PD/No equals 14.6 dB-Hz, R(sym) equals 16 symbols per sec, and the predicted acquisition time of the algorithm (to attain a 0.2-dB degradation from each loop to the output symbol SNR) is 38 sec.

Aung, M.↗
NASA NTRS2013

Intraseasonal and Interannual Variability of the Quasi-Two Day Wave in the Northern Hemisphere Summer Mesosphere

This study uses global synoptic meteorological fields from a high-altitude data assimilation system to investigate the spatial and temporal characteristics of the quasi-2 day wave (Q2DW) and migrating diurnal tide during the Northern Hemisphere summers of 2007, 2008, and 2009. By applying a 2-dimensional fast Fourier transform to meridional wind and temperature fields, we are able to identify Q2DW source regions and to diagnose propagation of Q2DW activity into the upper mesosphere and lower thermosphere. We find that Q2DW is comprised primarily of westward propagating zonal wavenumber 3 and wavenumber 4 components that originate from within baroclinically unstable regions along the equatorward flank of the summer midlatitude easterly jet. Amplitude variations of wavenumbers 3 and 4 tend to be anti-correlated throughout the summer, with wavenumber 3 maximizing in July and wavenumber 4 maximizing in late June and early August. Monthly mean Q2DW amplitudes between 30 50N latitude are largest when diurnal tidal amplitudes are smallest and vice versa. However, there is no evidence of any rapid amplification of the Q2DW via nonlinear interaction with the diurnal tide. Instead, variations of Q2DW amplitudes during July are closely linked to variations in the strength and location of the easterly jet core from one summer to the next, with a stronger jet producing larger Q2DW amplitudes. Linear instability model calculations based on the assimilated wind fields find fast growing zonal wavenumber 3 and 4 modes with periods near 2 days in the vicinity of the easterly jet.

Two day wave↗
NASA NTRS2011

High-Throughput, Adaptive FFT Architecture for FPGA-Based Spaceborne Data Processors

Exponential growth in microelectronics technology such as field-programmable gate arrays (FPGAs) has enabled high-performance spaceborne instruments with increasing onboard data processing capabilities. As a commonly used digital signal processing (DSP) building block, fast Fourier transform (FFT) has been of great interest in onboard data processing applications, which needs to strike a reasonable balance between high-performance (throughput, block size, etc.) and low resource usage (power, silicon footprint, etc.). It is also desirable to be designed so that a single design can be reused and adapted into instruments with different requirements. The Multi-Pass Wide Kernel FFT (MPWK-FFT) architecture was developed, in which the high-throughput benefits of the parallel FFT structure and the low resource usage of Singleton s single butterfly method is exploited. The result is a wide-kernel, multipass, adaptive FFT architecture. The 32K-point MPWK-FFT architecture includes 32 radix-2 butterflies, 64 FIFOs to store the real inputs, 64 FIFOs to store the imaginary inputs, complex twiddle factor storage, and FIFO logic to route the outputs to the correct FIFO. The inputs are stored in sequential fashion into the FIFOs, and the outputs of each butterfly are sequentially written first into the even FIFO, then the odd FIFO. Because of the order of the outputs written into the FIFOs, the depth of the even FIFOs, which are 768 each, are 1.5 times larger than the odd FIFOs, which are 512 each. The total memory needed for data storage, assuming that each sample is 36 bits, is 2.95 Mbits. The twiddle factors are stored in internal ROM inside the FPGA for fast access time. The total memory size to store the twiddle factors is 589.9Kbits. This FFT structure combines the benefits of high throughput from the parallel FFT kernels and low resource usage from the multi-pass FFT kernels with desired adaptability. Space instrument missions that need onboard FFT capabilities such as the proposed DESDynl, SWOT (Surface Water Ocean Topography), and Europa sounding radar missions would greatly benefit from this technology with significant reductions in non-recurring cost and risk.

NguyenKobayashi, Kayla↗
DOE OSTI2025

Comparative Analysis of Radial and Random Microstructures of Mesophase Pitch Carbon Fibers

Carbon fibers (CF) with radial and random microstructures are produced. Here, these fibers are subjected to identical treatment before being mechanically tested and analyzed with Weibull analysis, with the results revealing a statistically significant difference in tensile strengths of 2.23 GPa for random CF and 1.69 GPa for radial CF. Raman mapping probed the crystalline structure perpendicular to the fiber axis and found a uniform structure, while wide‐angle X‐ray diffraction showed a significant difference of 7.5 Å in the crystallites’ basal lengths parallel to the fiber. Small‐angle X‐ray scattering is completed parallel to the fiber for the first time. A cross‐section Guinier plot of the 1D azimuthal integration is generated assuming symmetric scattering, and the parallel scatterers are found to have a similar length scale to the crystallite's length, validating the testing method. Finally, transmission electron microscopy is completed on the longitudinal cross‐section of each fiber. The radial carbon fiber is found to have a core–shell structure, as evidenced further by fast Fourier transform images. Through all studies, it is shown that the structure developed during mesophase pitch spinning altered the microstructure, thus impacting the mechanical properties, confirming a direct relationship between processing, structure, and properties.

Scherschel, Alexander [Univ. of Virginia, Charlott↗
DOE OSTI2023

Studying performance portability of LAMMPS across diverse GPU-based platforms

The molecular dynamics simulation software, LAMMPS, utilizes the Kokkos acceleration library to port computation to a diverse set of architectures including those based on GPU accelerators. In addition to Kokkos, LAMMPS contains a vast code base that leverages the CUDA application programming interface using library functions such as cuFFT, CUDA's fast-fourier transform (FFT) library, and, more recently, also support for AMD's Heterogeneous Interface for Portability (HIP) that is rapidly growing. While preparing LAMMPS tests for the AMD GPU-based test system precursors to Frontier, we investigated several strategies for accelerating LAMMPS on AMD GPUs, using the AMD Instinct MI100 and MI250X. In this work, we integrated the HIP FFT library, hipFFT, into the particle-particle particle-mesh (PPPM) long-range solver, which allowed the porting of PPPM calculations to the GPUs. Kokkos behavior on the MI100 and MI250X was also investigated through the package kokkos command of LAMMPS, targeting communication, memory usage, and particle grid decomposition. The Tersoff, Reax, Lennard-Jones (LJ), EAM, Granular, and PPPM potentials were investigated in this effort, and results from these experiments are provided. In conclusion, the selected potentials were run on Spock (AMD Instinct MI100), Crusher (AMD Instinct MI250X), AFW HPC11 (NVIDIA A100) and Summit (NVIDIA V100), for comparison. Operational roofline models were constructed and analyzed for the Tersoff, Reax, and Lennard–Jones potentials on Crusher and Summit.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Chatter detection in simulated machining data: a simple refined approach to vibration data

Vibration monitoring is a critical aspect of assessing the health and performance of machinery and industrial processes. This study explores the application of machine learning techniques, specifically the Random Forest (RF) classification model, to predict and classify chatter—a detrimental self-excited vibration phenomenon—during machining operations. While sophisticated methods have been employed to address chatter, this research investigates the efficacy of a novel approach to an RF model. The study leverages simulated vibration data, bypassing resource-intensive real-world data collection, to develop a versatile chatter detection model applicable across diverse machining configurations. The feature extraction process combines time-series features and Fast Fourier Transform (FFT) data features, streamlining the model while addressing challenges posed by feature selection. By focusing on the RF model’s simplicity and efficiency, this research advances chatter detection techniques, offering a practical tool with improved generalizability, computational efficiency, and ease of interpretation. The study demonstrates that innovation can reside in simplicity, opening avenues for wider applicability and accelerated progress in the machining industry.

42 ENGINEERING↗
DOE OSTI2021

An FFT-based approach for Bloch wave analysis: application to polycrystals

A method based on the Fast Fourier Transform is proposed to obtain the dispersion relation of acoustic waves in heterogeneous periodic media with arbitrary microstructures. The microstructure is explicitly considered using a voxelized Representative Volume Element (RVE). The dispersion diagram is obtained solving an eigenvalue problem for Bloch waves in Fourier space. To this aim, two linear operators representing stiffness and mass are defined through the use of differential operators in Fourier space. The smallest eigenvalues are obtained using the implicitly restarted Lanczos and the subspace iteration methods, and the required inverse of the stiffness operator is done using the conjugate gradient with a preconditioner. The method is used to study the propagation of acoustic waves in elastic polycrystals, showing the strong effect of crystal anistropy and polycrystaline texture on the propagation. It is shown that the method combines the simplicity of classical Fourier series analysis with the versatility of Finite Elements to account for complex geometries proving an efficient and general approach which allows the use of large RVEs in 3D.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Micromechanical Fields Associated with Irregular Deformation Twins in Magnesium

Understanding and controlling the development of deformation twins is paramount for engineering strong and stable hexagonal close-packed (HCP) Mg alloys. Actual twins are often irregular in boundary morphology and twin crystallography, deviating from the classical picture commonly used in theory and simulation. In this work, the elastic strains and stresses around irregular twins are examined both experimentally and computationally to gain insight into how twins develop and the microstructural features that influence their development. A nanoprecession electron diffraction (N-PED) technique is used to measure the elastic strains within and around a $\left\{ {10\overline{1}2} \right\}$ tensile twin in AZ31B Mg alloy with nm scale resolution. A full-field elasto-viscoplastic fast Fourier transform (EVP-FFT) crystal plasticity model of the same sub-grain and irregular twin structure is employed to understand and interpret the measured elastic strain fields. The calculations predict spatially resolved elastic strain fields in good agreement with the measurement, as well as all the stress components and the dislocation density fields generated by the twin, which are not easily obtainable from the experiment. The model calculations find that neighboring twins, several twin thicknesses apart, have little influence on the twin-tip micromechanical fields. Furthermore, this work reveals that irregularity in the twin-tip shape has a negligible effect on the development of the elastic strains around and inside the twin. Importantly, the major contributor to these micromechanical fields is the alignment of the twinning shear direction with the twin boundary.

36 MATERIALS SCIENCE↗