0
$\begingroup$

I am studying the discrete Fourier transform, and in its most basic definition it is an invertible linear transformation on the complex numbers. From Wikipedia:

The sequence of $N$ complex numbers $x_0, x_1, ..., x_{N-1}$ is transformed into an $N$-periodic sequence of complex numbers:

$$ X_k = \sum_{n=0}^{N-1} x_n * e^{-i2\pi kn/N}, k \in \mathbb Z $$

I believe that I understand what this transformation does (it produces the "power" of the signal at each frequency from $0 Hz$ to $F_s/2 Hz$ (where $F_s$ is the sample frequency), and I can easily perform the required arithmetic. However, I am having some trouble understanding the representation of real samples as complex samples.

A typical signal I might wish to transform can be given by a function $f(t) = a$, where $t$ is some time offset and $a$ is the amplitude of the wave at that particular point in time (say it's in the range $[-1, 1]$ for simplicity's sake).

It is my understanding that I can represent this real sampled signal with $N$ samples as a complex sample with $N/2$ samples. I believe that this can be done with the Hilbert transform?

I'm hoping for some help understanding how a real signal can be transformed into a complex signal with half as many samples, and what those complex samples really represent (it's easy to understand a series of amplitude values, but I don't yet understand what the complex values "mean").

$\endgroup$
  • $\begingroup$ Take a look at Richard Lyons book "Understanding Digital Signal processing". There is a whole section about efficiently performing the FFT of real sequences, and many other DSP tricks. The copy I have is a 2nd edition, check section 13.5 $\endgroup$ – Ali Sep 16 '15 at 15:08
1
$\begingroup$

The DFT as you stated it is defined for arbitrary complex-valued sequences $x_n$. If $x_n$ is real-valued then its DFT satisfies the following symmetry condition:

$$X_k=X^*_{N-k},\quad k=0,1,\ldots,N-1$$

This means that, if $N$ is even, the values $X_k$, $k=0,1,\ldots,N/2$ are sufficient to completely represent the sequence $x_n$. So we have $N/2+1$ independent values $X_k$. However, note that if $x_n$ is real-valued, $X_0$ and $X_{N/2}$ are real-valued too, so you have two real-valued and $N/2-1$ complex valued coefficients $X_k$, which in total of course equals exactly $N$ independent (real-valued) numbers to represent the sequence $x_n$, just as expected.

In order to understand what the coefficients $X_k$ mean, it is helpful to look at the inverse transform:

$$x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_ke^{i2\pi kn/N}$$

So $|X_k|$ determines the amplitude and $\arg\{X_k\}$ determines the phase of the contribution to the sequence $x_n$ of the complex exponential with frequency $2\pi k/N$.

$\endgroup$
  • $\begingroup$ So, if I understand correctly, to efficiently compute the DFT of a real-valued sequence with $N$ members, one can simply represent each real valued input $x_n$ as a complex number $x_n+0i$, and then compute the first $N/2$ members of the DFT, at which point each member of the second half can be trivially computed as the complex conjugate of each member of the first half? $\endgroup$ – CmdrMoozy May 25 '14 at 20:14
  • $\begingroup$ Or, rather, the first $N/2+1$ members of the DFT from $X_0$ to $X_{N/2}$. $\endgroup$ – CmdrMoozy May 25 '14 at 20:21
  • $\begingroup$ @CmdrMoozy: You just use $x_n$ as is, no need to add $0i$. Otherwise you're right. However, the FFT (Fast Fourier Transform) is much more efficient than evaluating the sum directly. Anyway, efficient implementation is a totally different matter, and should probably be formulated as a different question. $\endgroup$ – Matt L. May 25 '14 at 20:25
  • $\begingroup$ Indeed. I meant "efficient" just in terms of, if one naively computed all $N$ members of the DFT, one would be performing approximately twice as many computations as necessary. Anyway, thank you for the most clear explanation of how the DFT relates to real inputs I've yet seen online. :) Particularly the point of what "physical" values $|X_k|$ and $arg\{X_k\}$ represent. $\endgroup$ – CmdrMoozy May 25 '14 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.