fft

0th

Percentile

Fast Discrete Fourier Transform (FFT)

Computes the Discrete Fourier Transform (DFT) of an array with a fast algorithm, the “Fast Fourier Transform” (FFT).

Keywords
math, dplot
Usage
fft(z, inverse = FALSE)
mvfft(z, inverse = FALSE)
Arguments
z

a real or complex array containing the values to be transformed. Long vectors are not supported.

inverse

if TRUE, the unnormalized inverse transform is computed (the inverse has a + in the exponent of \(e\), but here, we do not divide by 1/length(x)).

Value

When z is a vector, the value computed and returned by fft is the unnormalized univariate discrete Fourier transform of the sequence of values in z. Specifically, y <- fft(z) returns $$y[h] = \sum_{k=1}^n z[k] \exp(-2\pi i (k-1) (h-1)/n)$$ for \(h = 1,\ldots,n\) where n = length(y). If inverse is TRUE, \(\exp(-2\pi\ldots)\) is replaced with \(\exp(2\pi\ldots)\).

When z contains an array, fft computes and returns the multivariate (spatial) transform. If inverse is TRUE, the (unnormalized) inverse Fourier transform is returned, i.e., if y <- fft(z), then z is fft(y, inverse = TRUE) / length(y).

By contrast, mvfft takes a real or complex matrix as argument, and returns a similar shaped matrix, but with each column replaced by its discrete Fourier transform. This is useful for analyzing vector-valued series.

The FFT is fastest when the length of the series being transformed is highly composite (i.e., has many factors). If this is not the case, the transform may take a long time to compute and will use a large amount of memory.

References

Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988). The New S Language. Wadsworth & Brooks/Cole.

Singleton, R. C. (1979). Mixed Radix Fast Fourier Transforms, in Programs for Digital Signal Processing, IEEE Digital Signal Processing Committee eds. IEEE Press.

Cooley, James W., and Tukey, John W. (1965). An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation, 19(90), 297--301. 10.2307/2003354.

See Also

convolve, nextn.

Aliases
  • fft
  • mvfft
Examples
library(stats) # NOT RUN { x <- 1:4 fft(x) fft(fft(x), inverse = TRUE)/length(x) ## Slow Discrete Fourier Transform (DFT) - e.g., for checking the formula fft0 <- function(z, inverse=FALSE) { n <- length(z) if(n == 0) return(z) k <- 0:(n-1) ff <- (if(inverse) 1 else -1) * 2*pi * 1i * k/n vapply(1:n, function(h) sum(z * exp(ff*(h-1))), complex(1)) } relD <- function(x,y) 2* abs(x - y) / abs(x + y) n <- 2^8 z <- complex(n, rnorm(n), rnorm(n)) # } # NOT RUN { ## relative differences in the order of 4*10^{-14} : summary(relD(fft(z), fft0(z))) summary(relD(fft(z, inverse=TRUE), fft0(z, inverse=TRUE))) # }
Documentation reproduced from package stats, version 3.6.1, License: Part of R 3.6.1

Community examples

wangxuanp@gmail.com at Apr 17, 2019 stats v3.5.3

wavobj <- readWave("age1.wav") x <- wavobj@left fs <- wavobj@samp.rate nbits <- wavobj@bit x <- x[1:(fs*5)] y <- fft(x) y.tmp <- Mod(y) y.tmp <- Mod(y) y.ampspec <- y.tmp[1:(length(y)/2+1)] y.ampspec[2:(length(y)/2)] <- y.ampspec[2:(length(y)/2)] * 2 f <- seq(from=0, to=fs/2, length=length(y)/2+1) plot(f, y.ampspec, type="h", xlab="Frequency (Hz)", ylab="Amplitude Spectrum", xlim=c(0, 350)) text(f,y) save(f,y)

wangxuanp@gmail.com at Apr 17, 2019 stats v3.5.3

my_age1<- text(f,y) save(my_age1) save(plot) wavobj <- readWave("age1.wav") x <- wavobj@left fs <- wavobj@samp.rate nbits <- wavobj@bit x <- x[1:(fs*5)] y <- fft(x) y.tmp <- Mod(y) y.tmp <- Mod(y) y.ampspec <- y.tmp[1:(length(y)/2+1)] y.ampspec[2:(length(y)/2)] <- y.ampspec[2:(length(y)/2)] * 2 f <- seq(from=0, to=fs/2, length=length(y)/2+1) plot(f, y.ampspec, type="h", xlab="Frequency (Hz)", ylab="Amplitude Spectrum", xlim=c(0, 350)) text(f,y) save(f,y)