Stack Overflow
Stack Overflow

Questions tagged [dft]

Discrete Fourier transform (DFT) is a specific kind of discrete transform, used in Fourier analysis.

Given a sequence of N samples f(n), indexed by n = 0..N-1, the discrete Fourier transform (DFT) is defined as F(k), where k=0..N-1:

Enter image description here

Source: engineeringproductivitytools

428 questions
73
votes
3 answers

only integers, slices (`:`), ellipsis (`...`), numpy.newaxis (`None`) and integer or boolean arrays are valid indices

I am implementing fft as part of my homework. My problem lies in the implemention of shuffling data elements using bit reversal. I get the following warning: DeprecationWarning: using a non-integer number instead of an integer will result in an…
MessitÖzil
  • 1,298
  • 4
  • 13
  • 23
47
votes
1 answer

Why is FFT of (A+B) different from FFT(A) + FFT(B)?

I have been fighting with a very weird bug for almost a month. Asking you guys is my last hope. I wrote a program in C that integrates the 2d Cahn–Hilliard equation using the Implicit Euler (IE) scheme in Fourier (or reciprocal) space: Where the…
Tropilio
  • 1,395
  • 1
  • 9
  • 27
30
votes
2 answers

Discrete Fourier transform

I am currently trying to write some fourier transform algorithm. I started with a simple DFT algorithm as described in the mathematical definition: public class DFT { public static Complex[] Transform(Complex[] input) { int N =…
Marcel
  • 312
  • 4
  • 8
24
votes
7 answers

DFT matrix in python

What's the easiest way to get the DFT matrix for 2-d DFT in python? I could not find such function in numpy.fft. Thanks!
Uri Cohen
  • 3,488
  • 1
  • 29
  • 46
22
votes
4 answers

FFT real/imaginary/abs parts interpretation

I'm currently learning about discret Fourier transform and I'm playing with numpy to understand it better. I tried to plot a "sin x sin x sin" signal and obtained a clean FFT with 4 non-zero points. I naively told myself : "well, if I plot a "sin +…
Cyrille
  • 13,905
  • 2
  • 22
  • 41
20
votes
4 answers

DSP - Filtering in the frequency domain via FFT

I've been playing around a little with the Exocortex implementation of the FFT, but I'm having some problems. Whenever I modify the amplitudes of the frequency bins before calling the iFFT the resulting signal contains some clicks and pops,…
Trap
  • 12,050
  • 15
  • 55
  • 67
17
votes
3 answers

neural networks can't figure out Fourier transforms?

I'm trying to understand a few things about neural networks. First, after looking around on the web, it seems that there is no way to compute a (discrete) Fourier transform through a neural network. You can hack it by hard-coding the thing to…
Brannon
  • 5,324
  • 4
  • 35
  • 83
13
votes
3 answers

Fast Fourier Transform

I need to multiply two polynomials each having small integral coefficients. I need a fast FFT routine in C/C++ which can convolve them. I have seen several libraries but they seem to be too large spread over multiple files. What is important is I…
Nikhil Garg
  • 3,944
  • 9
  • 30
  • 37
13
votes
2 answers

FFT on image with Python

I have a problem with FFT implementation in Python. I have completely strange results. Ok so, I want to open image, get value of every pixel in RGB, then I need to use fft on it, and convert to image again. My steps: 1) I'm opening image with PIL…
Tatarinho
  • 754
  • 2
  • 11
  • 31
13
votes
2 answers

Is there any simple C++ example on how to use Intel MKL FFT?

I need to perform FFT and Inverse-FFT transformations. The input would be vector and matrices of double. Ideally, the output should be an array of std::complex but I can live with double _Complex. I haven't found any simple example, all Intel…
Baptiste Wicht
  • 7,472
  • 7
  • 45
  • 110
12
votes
1 answer

amplitude of numpy's fft results is to be multiplied by sampling period?

I try to validate my understanding of Numpy's FFT with an example: the Fourier transform of exp(-pi*t^2) should be exp(-pi*f^2) when no scaling is applied on the direct transform. However, I find that to obtain this result I need to multiply the…
user1163676
  • 155
  • 1
  • 1
  • 7
12
votes
2 answers

Writing a simple Discrete Fourier Transform for real inputs in C

So I'm trying to write the Discrete Fourier Transform in C to work with real 32-bit float wav files. It reads in 2 frames at a time (one for each channel, but for my purposes I'm assuming they are both the same and so I use frame[0]). This code is…
maniciam
  • 365
  • 5
  • 10
11
votes
4 answers

FFT of a real symmetric vector is not real and symmetric

I am having a hard time understanding what should be a simple concept. I have constructed a vector in MATLAB that is real and symmetric. When I take the FFT in MATLAB, the result has a significant imaginary component, even though the symmetry rules…
craigim
  • 3,884
  • 1
  • 22
  • 42
9
votes
1 answer

Implementing FFT over finite fields

I would like to implement multiplication of polynomials using NTT. I followed Number-theoretic transform (integer DFT) and it seems to work. Now I would like to implement multiplication of polynomials over finite fields Z_p[x] where p is arbitrary…
minmax
  • 493
  • 3
  • 10
8
votes
2 answers

FFTW vs. OpenCV cvDFT

Can I expect a speedup when using FFTW (http://www.fftw.org/) instead of OpenCV's cvDFT (http://goo.gl/YCHj0)? My program's runtime is heavily determined by the application of inverse and forward DFT and I am thinking about using FFTW instead of…
Arvid Terzibaschian
  • 317
  • 3
  • 10
1
2 3
…
28 29