What is the effect of wiping the right half of Fourier Transform bins?

Question

I'm trying to change the pitch of a signal using a Fourier Transform (FFT) followed by an Inverse Fourier Transform (IFFT).

I've found many examples, some of which zero out the right half of the real and imaginary bins before changing the pitch. For example, if the signal was $8192$ bins, the real and imaginary parts from $4096$ to $8192$ are set to $0$. This seems to make the math for pitch changing easier, but reduces the volume by one half. This seems to be corrected by doubling the magnitude.

I'm wondering what effect wiping the right half of the bins has on the final signal, apart from reducing the volume. I am confused why these bins exist if they can be wiped without affecting the final signal too much.

Answer 1

The discrete Fourier transform (DFT) transforms a sequence of generally complex-valued numbers to another sequence of generally complex-valued numbers. If the input to the DFT is real-valued - as is the case for a sampled audio signal - then the right half of the DFT is redundant. If $X[k]$ is the length $N$ DFT of a real-valued length $N$ sequence $x[n]$, the following holds:

$$X[k]=X^*[N-k],\qquad k=0,1,\ldots, N-1\tag{1}$$

where $^*$ denotes complex conjugation.

For even $N$, the values $X[0],X[1],\ldots,X[N/2]$ completely represent the original sequence $x[n]$, so the DFT coefficients $X[N/2+1],\ldots,X[N-1]$ can be discarded. For odd $N$, the coefficients $X[0],\ldots,X[(N-1)/2]$ are sufficient.

Note that there are efficient routines for computing the DFT of real-valued input sequences, which only compute the non-redundant DFT coefficients.

Answer 2

Taking the inverse DFT is like evaluating the Fourier Series produced by the DFT coefficients at integer domain points. This is very efficiently when using the iFFT.

Each bin is a complex value which can be represented by a real part and imaginary part, or as a magnitude and phase value.

$$ X[k] = a_k + i b_k = r_k e^{i\theta} $$

The latter form comes from Eulers formulas (See https://www.dsprelated.com/showarticle/754.php)

The right half, or upper half, counterpart is the complex conjugate for real valued signals.

$$ X[-k] = X[N-k] = a_k - i b_k = r_k e^{-i\theta} = X^*[k] $$

When you are "reading the bin values" in code, you are actually doing this in math:

$$ a_k = (X[k] + X[N-k])/2 $$ $$ b_k = (X[k] - X[N-k])/2i $$

For completeness:

$$ \|X[k]\| = \sqrt{ a_k^2 + b_k^2} = |r| $$

$$ \angle( X[k] ) = \arg( X[k] ) = \theta $$

For bin centered pure tones, these values directly reflect the signal values.

When you zero out the top half and take the inverse DFT you get a complex signal back where each Fourier term(s) has been changed, and compensate by double the coefficients.

$$ x[n] = \dots + 2 a_k \cos \left( \frac{2\pi}{N}kn \right)+ i 2 b_k \cos \left( \frac{2\pi}{N}kn \right) \dots $$

Here the Sine term is being added in the imaginary axis, so if you just strip the results, keeping the real part, all you've done is throw away the phase shift.

Here is a comparison, stripped:

$$ \begin{aligned} \Re(x[n]) &= \dots + 2 a_k \cos \left( \frac{2\pi}{N}kn \right) + \dots \\ \end{aligned} $$

Versus using the upper half:

$$ \begin{aligned} x[n] &= \dots + 2 a_k \cos \left( \frac{2\pi}{N}kn \right) + 2 b_k \cos \left( \frac{2\pi}{N}kn \right) + \dots \\ &= \dots + 2 r_k \cos \left( \frac{2\pi}{N}kn + \theta_k \right) + \dots \end{aligned} $$