Discrete Fourier Transform = Correlation?

[BertKoor]

5.what is complex input signal?

https://en.wikipedia.org/wiki/Real_number
https://en.wikipedia.org/wiki/Complex_number

You know about this stuff, right? In FT the "real" part of complex numbers is what you keep calling "sine part", and the "imaginary" part of the complex numbers is what you call the "cosine part". These two are orthogonal (have an angle of 90 degrees) and the whole complex number can also be described as amplitude (square root of the real & imaginary parts squared) plus a phase.

[neodymDNB]

5.what is complex input signal?

https://en.wikipedia.org/wiki/Real_number
https://en.wikipedia.org/wiki/Complex_number

You know about this stuff, right? In FT the "real" part of complex numbers is what you keep calling "sine part", and the "imaginary" part of the complex numbers is what you call the "cosine part". These two are orthogonal (have an angle of 90 degrees) and the whole complex number can also be described as amplitude (square root of the real & imaginary parts squared) plus a phase.

I thought "real" = cosine and "imaginary" = sine,or is it backward/opposite?

yes,you mix the sine and cosine of the same freqency bin to get the complex sine,which is sine with changing amplitude and phase

about that complex number amplitude,I reed on internet that in FFT you get the specific freqency bin value like this "sine x sine + cosine x cosine" and then count the highest amplitude point,and that is the final value of the specific freqency bin in freqency axis and window along the time axis.

The sine and cosine are multipled by itself becose they can have negative numbers due to signed 16bit wav -32768 to +32767.... so negative number multiplied by another negative number is positive,that gives us "squared" value right?



back to the point,so what is "real valued input signal" and "complex input signal"??? I understand how OUTPUT of FFT can be real or complex,but INPUT?? as far as I know you can only input normal wav audio file,I have no idea what "real valued input" is in FFT

[Miles1981]

That's because you are only thinking about audio processing of sounds. Now think of DFT of a generic/not audio signal.

DFT is usually done on floating point values, then it's usual math and other properties, nothing to do with audio samples and the specific of the support (int or others).

[mystran]

back to the point,so what is "real valued input signal" and "complex input signal"??? I understand how OUTPUT of FFT can be real or complex,but INPUT?? as far as I know you can only input normal wav audio file,I have no idea what "real valued input" is in FFT

Real-valued input is simply input signal that has zero-value imaginary component. Most real-world signals are like that (unless you stuff another signal to imaginary component; processing two channels of stereo is usually faster done this way). This results in symmetric spectrum, so a "real FFT" is simply a normal FFT routine, but optimised to assume that all the imaginary components in the input are real (and need not be calculated) and the output is symmetric (so need not be stored twice). All the math still needs to be done in complex numbers and the output is still complex, it's just that we can skip some of the work depending on the properties of the input, which makes it somewhat faster (typically a real-input FFT is slightly slower than a complex FFT of half the size and two real-input FFTs done separately are slightly slower than a single complex FFT of the same size).

There is also cosine and sine transforms. Cosine transform essentially treats the input as even-symmetric, so all the sines in the spectrum cancel out. Sine transform does the same with odd-symmetric assumption. Again, these are essentially the same as the standard FFT but allow some of the computations to be skipped.

The bottom line is, FFT is always just FFT (and as far as the math goes, it's always complex). The actual computer program can be made faster if we know some properties of the input or output, so we can skip some useless work by not actually bothering to push zeroes around or duplicate the same information twice (eg. for known symmetries).

[mystran]

5.what is complex input signal?

https://en.wikipedia.org/wiki/Real_number
https://en.wikipedia.org/wiki/Complex_number

You know about this stuff, right? In FT the "real" part of complex numbers is what you keep calling "sine part", and the "imaginary" part of the complex numbers is what you call the "cosine part". These two are orthogonal (have an angle of 90 degrees) and the whole complex number can also be described as amplitude (square root of the real & imaginary parts squared) plus a phase.

I thought "real" = cosine and "imaginary" = sine,or is it backward/opposite?

Complex number (in polar coordinates) r*exp(i*w) can be written as r*(cos(w)+i*sin(w)).

The number is real when sin(w)=0 and imaginary when cos(w)=0.

[JCJR]

Hi neodymDNB

This link is one of the clearest-written introductory practical explanations I recall seeing, regarding complex math and signals. Actually all the chapters seem clearly written. But some of the complex math aspects I either forgot or never got exposed to it "the EE way".

http://www.eas.uccs.edu/~mwickert/ece26 ... _chap2.pdf

I vaguely recall rect-to-polar and vice-versa in calculus long ago, using trig identities to solve "non-trig" problems etc. But the methods in this chapter (also as described rather well by Miles and MyStran) were either long-forgotten or never explained that particular way. My vague recollections of complex numbers mostly involved brain-damaging pencil-and-paper algebra manipulations.

Thinking of signal cos/sin as complex number adds a "concrete" aspect easier to understand because I can try to visualize the literal result of the math on a signal. Back in math classes they were discussing the topic in abstract and I didn't much care about the abstract concept. At the time maybe I wouldn't have cared about the signal aspect either, but a concrete application may have been useful in the teaching.

[xoxos]

sigh


w = 2 * pi * f / fs
s0 = 1
s1 = 0

s0 -= w * s1
s1 += w * s0


try and learn from someone who helps. if you prefer style over substance, i've left plenty of swears on kvr for you to get angry about and feel distainful towards if you'd like to do that instead of cultivating your mind.

[neodymDNB]

could it be said that REAL dft only show us the amplitude of freqencies while COMPLEX dft gives us also phase information on top of amplitude information? is that correct?

REAL dft = amplitude
COMPLEX dft = amplitude + phase

edit: I just want to tell you how much I love you all,srsly guys you are godsend,this is best forum I ever been! <3

[stratum]

Complex dft is easier to understand.i'd suggest reading the related chapter at dspguide. That can clear the confusion about the two. Once you realize that the complex one is all that you need you wont really bother with the real one anymore. Maybe its faster in some cases but thats all there is to it. Probably the real one does not take any input that can quantify phase info, i do not recall.

Edit: http://www.dspguide.com/ch12/1.htm
This says exactly that. There is nothing to quantify phase info in the real version's input.


Edit2: actually if the input is a time domain signal nothing additional needs to be specified as phase. The imaginary input in complex version serves the purpose of keeping the transform symmetric i.e its inverse is the same function except a scaling factor.

[mystran]

could it be said that REAL dft only show us the amplitude of freqencies while COMPLEX dft gives us also phase information on top of amplitude information? is that correct?

Now.. you are missing something important: the DFT of a real-value signal gives you a complex spectrum!

This is what we normally call "real DFT" because "DFT of a real-valued signal" is kinda long for every day speech (or forum writing)... but the result is still complex!

So why do libraries have special "real FFT" routines?
Because the (complex-)spectrum of a real-value signal is symmetric: you only need the positive (or the negative) frequencies since for any real signal the positive and negative frequencies are simply conjugates of each other (such that the imaginary components cancel out), but it's still as complex as ever, you just need half as many values to describe the signal.

This is why the "complex DFT" (or FFT) is easier to understand, because the "real DFT" is not really "real" at all, it's just an optimisation of the same complex thing for signals that happen to have nothing but zeroes in their imaginary component.

[aciddose]

It is easier if you understand that each input is a vector (sample, pixel, etc) and each output is a vector also.

The transform is like any other transform, it's a rotation + translation.

https://en.wikipedia.org/wiki/Rotation_matrix

The transform only includes two dimensions although that need not be the case. In the case of a discrete signal the "imaginary" or "y" component of the vector is zero. During a rotation coordinates are scaled and so any zero can be ignored as the result of zero scaled by any other number is zero!

The rotation matrices however will rotate those normalized vectors through a wide range of angles and the resulting transformed vectors will no longer point in the same direction as the inputs.

The problem which leads to so much confusion is that many of the people who learn about such transforms (Fourier, etc) do so without first understanding linear algebra and Nth dimensional coordinate systems such as "complex" (2d) and how they relate to one-another.

The numbers: 1, 2, 3, 4 are already containing every dimension 1 through infinity.

In order to make these "complex" (2d) we only need to add an axis!

(1,0), (2,0), (3,0), (4,0)

[stratum]

The idea dft=some rotation plus translation sound wrong to me as the result does not ever put the sine axis to the place of cosine

[aciddose]

So you're saying that the idea the Fourier transform is a transform as in linear algebra sounds incorrect to you?

Okay.

Have you by any chance noticed that the transform is a 2d rotation matrix applied to a 2d vector?

Code: Select all

// DFT
for (i = 0; i < length; i++) {
	T th = T(0);
	T d = T(2) * T(pi) * T(i) / T(length);
	for (j = 0; j < length; j++) {
		matrix<2,2> rotation_matrix(cos(th), -sin(th),
			sin(th), cos(th));
		frequency[i] += time[j] * rotation_matrix;
		th += d;
	}
}

[stratum]

Well actually yes, to me dft does not look like a translation+rotation matrix. Can you elaborate in what sense it can be considered so? That code does not seem to have a clear interpretation to me because of that frequency += part. its not just =

[aciddose]

No. If it isn't obviously a 2d rotation through a range of angles I don't know what else I can say to you.

Read the article I linked on rotation matrices and transformations. It includes THE SAME 2d rotation matrix as an example in the article.



I find it incredibly stupid that people don't learn linear algebra as teens in grade-school.