0
$\begingroup$

I'm trying to implement an FFT algorithm from scratch. I'm using the recursive algorithm where if N is a power of 2, then I have M = N/2. The algorithm is divided into even and odd parts and I have the following equation: $$X[k] = \sum_{m=0}^{M-1}x[2m]e^{-j\frac{2\pi}{M}km} + e^{-j\frac{\pi}{M}km}\sum_{m=0}^{M-1}x[2m+1]e^{-j\frac{2\pi}{M}km}$$

Now, since I can't guarantee that N is always gonna be a power of 2, I added zero padding. I've noticed this gives a different output than if applying FFT on the signal without padding

import numpy as np
from scipy.fftpack import fft

x = np.array([5, 6, 8, 2, 4])

#Step (1) - Ensure no. of samples is a power of 2
n = np.ceil(np.log2(len(x)))
pad = int(np.power(2,n)-x.size)

xpad = np.pad(x, (0,pad), mode='constant')

#Step (2) - Divide into even and odd
M = int(len(xpad)/2)

def calc_xk(k):
    even = 0.0
    odd = 0.0
    for i in range(M):
        even += xpad[2*i] * np.exp(-1j * 2 * np.pi * k * i / M)
        odd += xpad[2*i+1] * np.exp(-1j * 2 * np.pi * k * i / M)

    return even + np.exp(-1j * np.pi * k / M) * odd


fftx = []
for i in range(len(xpad)):
    fftx.append(calc_xk(i))


print(xpad)
print(fftx)
print(fft(xpad))
print(fft(x))

Shouldn't the zero values give zero and not affect the results at least for the first few original values? What am I missing?

$\endgroup$

2 Answers 2

0
$\begingroup$
  1. Zero padding changes the frequency grid. If your signal is sampled at 1kHz and you apply and DFT of length 100, you evaluate the DFT at 0Hz, 10Hz, 100Hz etc. If you zero pad to 128, you evaluate at 0Hz, 7.8Hz, 15.6Hz etc.
  2. Zero padding (in most cases) changes the spectrum pretty drastically. The input and output of the DFT are both discrete, i.e. they are also periodic. zero padding inserts a zero section into each period. If you do this to, for example, a sine wave, it's NOT a sine wave anymore
$\endgroup$
2
  • $\begingroup$ So, would this make implementing FFT with zero padding wrong? What method should I try that would be better? $\endgroup$ May 21, 2022 at 13:53
  • $\begingroup$ That really depends on your application and what exactly you want to do with it. $\endgroup$
    – Hilmar
    May 21, 2022 at 15:05
0
$\begingroup$

Zero padding inserts new samples in between every sample in the DFT result.

Zero padding just gives you more samples on the signal’s Discrete Time Fourier Transform (DTFT) which is a continuous function in frequency. The DFT itself is samples on this function, so the zero padding isn’t really changing the spectrum but showing you more samples on it (without adding any more actual frequency resolution than what is provided by that underlying DTFT). Simply, it provides an interpolation in the frequency domain.

If you compare the formula for the DFT to that for the DTFT the functionality of zero padding becomes very clear:

DFT:

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

DTFT:

$$X(k) = \sum_{-\infty}^{\infty}x[n]e^{-j2\pi n k/N}$$

Notice for both we are operating on the same samples $x[n]$, such that extending $n$ to plus or minus infinity results in zeros padding. Note in the DFT that for N samples in the time domain we get N samples in the frequency domain, extending from $f=0$ to one sample less than $f=f_s$ where $f_s$ is the sampling rate. Thus as we add more samples (even zero value samples) we add more samples within the same frequency range: interpolation in frequency!

We need not extend all the way to infinity to see a plot of how the continuous time waveform would appear, but the more zeros we add the more samples we get on this same waveform. This is zero padding!

$\endgroup$

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.