1
$\begingroup$

Quick question: Is it correct to define Discrete Fourier Transform like this, if my input signal is real valued:

$$ X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-i2 \pi n \frac{k}{N}} $$

Where $k \in \{0, 1, \dots, \frac{N}{2} -1\}$

This should result in a spectrum where the highest frequency is the Nyquist frequency right? And as a result there should be no aliases (no need to cut the spectrum in half?)

$\endgroup$
1
  • $\begingroup$ You can do a real-input FFT by putting each even-indexed $x_\text{r}[n]$ into the real part of $x[n/2]$ and each odd-indexed $x_\text{r}[n]$ into the imaginary part of $x[(n-1)/2]$, running the FFT on $N/2$ complex samples and detangling the output of the FFT. $\endgroup$ Apr 21, 2023 at 3:41

2 Answers 2

1
$\begingroup$

The DFT is given as $$ X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-i2 \pi n \frac{k}{N}} \tag{1} $$

A direct consequence of this definition is that both time and frequency domain sequences are periodic with $N$. If a signal is real in one domain it has complex conjugate symmetry in the other domain, for example

$$x[n] \in \mathbb{R} \rightarrow X[-k] = X[N-k] = X^*[k] \tag{2}$$

Where $k \in \{0, 1, \dots, \frac{N}{2} -1\}$

You need Nyquist as well, i.e. $k \in \{0, 1, \dots, \frac{N}{2} \}$ . The values for $k \in \{\frac{N}{2} +1, ... , N-1\}$ are also well defined and not zero, you can't ignore them. However, you can easily calculate them using eq (2) and don't need to evaluate eq (1).

In practice you rarely evaluate eq (1) directly but use an algorithm like the FFT, which will always calculate all frequencies. There is a way to leverage the real property of the input to implement a real-input FFT but that's a topic for a different question.

$\endgroup$
-1
$\begingroup$

Discrete Fourier Transform(DFT) represents a signal as weighted sum of the frequency components. Consider a discrete time signal $x[n]$ of length $N$. The coefficients obtained from the discrete Fourier transform of $x[n]$ are used to represent $x[n]$ as shown in the equation below

$$x[n] = \frac{1}{N}\sum_{k=0}^{N-1}X[k]e^\frac{j2\pi kn}{N}$$

Here the weights applied on frequency component - $k$ is $X[k]$.

The original signal $x[n]$ can be faithfully reconstructed only if the entire set of $X[k]$s with $k\in \{0, 1, 2, \dots ,N-1\}$. By taking only half the set i.e., $k\in \{0, 1, 2, \dots ,\frac{N}{2}-1\}$, faithful reconstruction of original real-signal $x[n]$ is not guaranteed (unless the second half of coefficients are defined as complex conjugates of first half). Hence its not correct to limit the definition of DFT to first half as the invertibility property of DFT will be affected.

$\endgroup$
7
  • $\begingroup$ $x$ is real. rfft is an exact subset of fft. This answer is incorrect. $\endgroup$ Apr 16, 2023 at 13:34
  • $\begingroup$ I don't understand. Can You help me understand what part of the answer is incorrect? I am asking this to better my understanding $\endgroup$
    – SakSath
    Apr 16, 2023 at 14:39
  • $\begingroup$ @OverLordGoldDragon - or it's okay even if You can point out which part of the answer doesn't agree with Your statement of "rfft is an exact subset of fft" $\endgroup$
    – SakSath
    Apr 16, 2023 at 14:48
  • $\begingroup$ "x can be faithfully reconstructed only if entire set of ... 0 to N - 1" $\endgroup$ Apr 16, 2023 at 14:51
  • $\begingroup$ Yes, what if the second half of $X[k]$ are assumed to be zeros since the OP talks about defining DFT to only upto $\frac{N}{2} - 1$ coefficients ? $\endgroup$
    – SakSath
    Apr 16, 2023 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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