Questions tagged [dft]

The Discrete Fourier Transform (DFT) is a mapping between a finite set of discrete points in a (primal) domain (time, space) and the dual frequency domain. DFT requires an input sequence which is discrete, such as a sampling from an analogue audio signal.

Filter by
Sorted by
Tagged with
4 votes
1 answer
2k views

Goertzel algorithm: Relationship of magnitude

I've written a quick test app that uses the Goertzel algorithm to determine if a given frequency is present in the signal. This is to pick up DTMF tones and various other signals. The app appears to ...
3 votes
1 answer
1k views

Chirp z algorithm clarification

I am attempting to implement a chirp z algorithm to handle random sized DFTs, and I can not seem to obtain any meaningful results. I have gone over several write ups and "think" I have a handle on ...
  • 51
13 votes
2 answers
4k views

How does subpixel image shifting using DFT really work?

I am trying to assess the quality of several image interpolation methods for an application that involves generating subpixel-shifted images. I thought I could compare the results of a subpixel shift ...
3 votes
1 answer
653 views

DFT as convolution question

I have tried to make this question as readable and consistent as possible. The short of it, is that I am trying to ascertain how one gets from the math equation shown, (which I understand), to the ...
  • 9,419
0 votes
2 answers
119 views

Filtering + Images [duplicate]

Possible Duplicate: What does frequency domain denote in case of images? I am studying applications of low and high pass filters in images. However, first I'm trying to understand what exactly ...
  • 173
115 votes
4 answers
48k views

Why is it a bad idea to filter by zeroing out FFT bins?

It's very easy to filter a signal by performing an FFT on it, zeroing out some of the bins, and then performing an IFFT. For instance: ...
  • 15.3k
3 votes
2 answers
6k views

Time domain interpolation using FFT with zero padding on the end

I've got a situation where I'd like to use an FFT to do interpolation in time on some complex data (I need to go to the frequency domain anyways to window my data). The notional way of doing this ...
  • 31
7 votes
1 answer
3k views

Failed to implement Goertzel algorithm in Python

After some questioning on stackoverflow, I tried to implement a Goertzel algorithm in Python. But it doesn't work : https://gist.github.com/4128537 ...
  • 283
5 votes
1 answer
420 views

Determining the type of filter on an image

I have the following mask where the origin is marked in bold text $$ \left[ \frac{-1}{4}~~~{\bf\frac{1}{2}}~~~\frac{-1}{4} \right ] $$ After computing the DFT, the result is: $$ \frac{1}{2} - \frac{...
  • 301
4 votes
1 answer
857 views

Mapping the Value of a Sample in a 2D DFT to Cycles/Pixel

If I have an image and its 2-D DFT of that image, what is the mapping between the value of the DFT at (u,v), and the frequency in the spatial domain in the x and y components, in cycles/pixel? I want ...
  • 183
10 votes
1 answer
13k views

What is the meaning of the DFT? [duplicate]

Possible Duplicate: Real Discrete Fourier Transform What is the most lucid, intuitive explanation for the various FTs - CFT, DFT, DTFT and the Fourier Series? Discrete-time Fourier transform ...
3 votes
1 answer
427 views

Circular Time Delay in signal, effect on phase spectra of DFT

If you circularly shift a signal x[n]= [-3 -2 -1 0 1 2 3 2 1 0 -1 -2 ] to the right by M=1 compared to M=2, the phase spectra has a lot many zeros when M=2 compared to M=1. here, I am talking about ...
  • 33
48 votes
3 answers
92k views

Why is the FFT "mirrored"?

If you do an FFT plot of a simple signal, like: t = 0:0.01:1 ; N = max(size(t)); x = 1 + sin( 2*pi*t ) ; y = abs( fft( x ) ) ; stem( N*t, y ) 1Hz sinusoid + DC ...
  • 915
3 votes
2 answers
2k views

Comparing Image FFT with Sine wave FFT

So, When we take the FFT of any Composite or Single Sine Wave we get exact frequency on x-axis of the plot. The point where we get the original frequency in FFT is depend upon the Sampling Rate and ...
5 votes
1 answer
494 views

Why idft(dft(a) * dft(b)) not equal to convolve(a, b)?

I'm a little confused... I always thought the DFT of a convolution was equal to a product of DFTs, but when I tried this in Python: ...
2 votes
0 answers
63 views

how to break the input signal into segments while calculating DFT [duplicate]

Possible Duplicate: breaking the input signal into segments while calculating DFT Im reading a book about DSP and there is an example about investigating the sound that travel through the ocean. ...
  • 319
12 votes
2 answers
7k views

Z-transform of a downsampler

In this paper or multirate filtering, the author establishes the following mathematical relationship. Let $y_D$ be the output of a downsampler such that $$y_D[n] = x[Mn]$$ where $M$ is the ...
  • 5,018
15 votes
3 answers
16k views

How to demodulate an AFSK signal in software

I am trying to transmit binary data from one device to another over an audio channel (speaker/mic). I use AFSK (Audio Frequency Shift Keying) as in Packet Radio, with $1200 \text{ Baud}$ and two ...
2 votes
1 answer
2k views

DFT of complex signal using Goertzel algorithm in C

I am implementing a BFSK frequency hopping system with TX and Rx modules. I am using Goertzel Algorithm at the receiver end to demodulate the data i.e. to determine the carrier frequency of the ...
  • 241
4 votes
1 answer
8k views

Difference Between Linear Convolution and Circular Convolution

If I understood correctly (and this page should confirm: http://www.cs.ioc.ee/~khoros2/linear/convolution-teo/front-page.html) if I convolve linearly (the usual point-to-point multiplication and ...
11 votes
3 answers
26k views

Discrete Fourier transform symmetry

I was reading the chapter on discrete Fourier transforms in Lyons' book -- Understanding Digital Signal Processing -- and could not understand the last paragraph about symmetry. There’s an ...
  • 307
8 votes
3 answers
2k views

FFT for line detection

I am trying use the FFT in a different way then most people ask about. I want to be able to take a picture of a graph with regular repeating vertical lines, and to process the image to determine how ...
user avatar
2 votes
1 answer
672 views

Sliding DFT: I think my results are accurate, but I can't buy a swap-swap IDFT

I've got a sliding DFT implementation that appears to be working (judging from an output plot). I would like to be able to invert this implementation using the standard tricks of swapping the real and ...
  • 295
4 votes
3 answers
4k views

What's the best criterion for determining a frequency peak?

I'm writing an algorithm that analyzes results of discrete Fourier transform (DFT). The algorithm should detect amplitude peaks in predefined ranges of frequencies. This is an example of such a peak: ...
  • 141
17 votes
2 answers
2k views

DFT with geometrically-spaced bins?

The traditional Discrete Fourier Transform (DFT) and its cousin, the FFT, produce bins that are spaced equally. In other words, you get something like the first 10 hertz in the first bin, 10.1 through ...
  • 295
127 votes
5 answers
83k views

What does frequency domain denote in case of images?

I was just learning about the frequency domain in images. I can understand the frequency spectrum in case of waves. It denotes what frequencies are present in a wave. If we draw the frequency ...
2 votes
1 answer
2k views

Express a wave as a sum of cosine

I started off with this: $$ x = 5 \cos(200 \times 2 \pi t ) + 10 \cos( 400 \times 2 \pi t)$$ by performing a 1024 point DFT on it. Then I performed IDFT on the complex values obtained through DFT. ...
  • 43
2 votes
1 answer
1k views

Calculate harmonics using DFT from real points

I have a real data of 144 points, when I perform a 144-point DFT on this data, I get $X$ with real and complex values. I want to calculate harmonics using these $X$'s. The $X[0]$ and $X[72]$, added ...
  • 43
4 votes
2 answers
280 views

Creating an array whose DFT is all whole numbers

I'm working on a simple FFT implementation and currently running some unit tests. Long floating point numbers in C and assembly become very hard to keep track of, and this whole thing is error prone. ...
  • 5,018
14 votes
2 answers
14k views

Real discrete Fourier transform

I am trying to understand the real DFT and the DFT and why the distinction exists. From what I know so far the DFT uses $e^{i2\pi kn/N}$ for basis vectors and gives the representation $$x[n]=\sum_{k=...
36 votes
9 answers
14k views

Is there an algorithm for finding a frequency without DFT or FFT?

I was looking in the Android app store for a guitar tuner. I found a tuner app that claimed it was faster than other apps. It claimed it could find the frequency without using the DFT (I wish I still ...
  • 463
-3 votes
1 answer
284 views

How Can I practically implement the FFT with size unequal to a power of two?

Can anybody explain how I can implement the Fast Fourier Transform (FFT) of length unequal to a power of two in hardware, e.g. FPGA? What is the algorithm for this implementation? Does anybody know ...
  • 411
7 votes
1 answer
309 views

Deriving 2-D discrete Fourier transforms

I have a problem in DFT. It was one of my past-year exam papers questions. Question: Let $F(u,v)$ be the 2-D Fourier transform of a 2-D continuous function $f(x,y)$. Derive in terms of $F(:,:)$ ...
14 votes
3 answers
677 views

How to efficiently calculate only the low coefficients of a zero-padded FFT

I've got an algorithm that zero pads a sequence to 4N, does an FFT, and only uses the lowest frequency N points out of the generated 4N. This seems like a lot of wasted work, any ideas how this can ...
7 votes
2 answers
952 views

Which unit does the power spectrum of microphone output have?

If I sample sound with a microphone and find the absolute square of the (non-normalized) DFT, I get the discrete power spectrum (correct me if I'm wrong). Which unit does it have?
  • 1,948
20 votes
3 answers
6k views

Frequency-domain zero padding - special treatment of X[N/2]

Suppose we wish to interpolate a periodic signal with an even number of samples (e.g. N=8) by zero-padding in the frequency domain. Let the DFT X=[A,B,C,D,E,F,G,H] ...
  • 391
23 votes
2 answers
10k views

How can I compute a log-spaced power spectrum?

I would like to compute a power spectrum in which the frequencies are logarithmically spaced. In Welch's method there is a trade-off between the frequency resolution of the resulting power spectrum ...
  • 3,673
16 votes
2 answers
2k views

Could a DCT be used for an audio magnitude spectrum rather than DFT?

From what I understand, the DCT has half the bin size as a DFT of the same size N. The DFT also includes phase information, but often this is not needed when only the magnitude spectrum is desired. ...
  • 351
103 votes
4 answers
86k views

What is the difference between a Fourier transform and a cosine transform?

In speech recognition, the front end generally does signal processing to allow feature extraction from the audio stream. A discrete Fourier transform (DFT) is applied twice in this process. The first ...
  • 1,147
6 votes
1 answer
220 views

Variant of discrete fourier transform that isolates phase delay?

I'm not quite sure of the mathematical terminology here but... Is there a variant (or post-processing) of a Discrete Fourier Transform that separates the shape of a signal from any phase shift ...
  • 391

1
16 17 18 19
20