matlabsignal-processingfftpaddingdft

How adding Zero-Head and Zeros at the end of an input sequence effect a DFT-IDFT process?


if I put zeros at the end of an input sequence, and take FFT, then take IFFT of a greater length by padding zeros to the FFT output, will the zeros of the input sequence reflect on the final IFFT output?

I tried to do this in MATLAB, it seems the last part of the final IFFT output deviates from being nearly zero in the absence of any zero-head in original data. IFFT output without adding zeros at the beginning of input sequence

But, when I add zero at the beginning of the data as well, the last part of the data seems nearly being zero. IFFT output with zeros at the beginning of input sequence

Could anyone give any mathematical explanation to this?


Solution

  • FFT & iFFT

    When you pad zeros to the end of a signal and then FFT followed by an iFFT of a "longer" length signal by zero-padding the FFT output, the zeros can affect the final iFFT result.

    We know that the FFT of a signal transforms it from the time to the frequency domain. Right? and the iFFT transforms it back to the time domain. If we zero-pad in the time domain, it increases the "resolution" in the frequency domain, but does not "fundamentally" alter the original signal's frequency content.

    When you zero-pad a signal before computing the FFT, you're increasing the signal's length then. This increases the frequency resolution, but the actual values in the original signal remain unchanged. However, zero-padding at the end of the sequence can introduce a "discontinuity" at the boundary where the padding starts, which affects the iFFT output.

    FFT implicitly assumes "circular convolution". If the signals ends abruptly (without zero-padding at the end) rather than smoothly, the circular convolution assumption causes the iFFT output to wrap around, which leads to discontinuities and deviations from zero at the end of the signal.

    Code

    import numpy as np
    import matplotlib.pyplot as plt
    
    
    def pad_end(size, pad):
        np.random.seed(42)
        x = np.random.randn(size)
    
        x_padded_end = np.concatenate((x, np.zeros(pad)))
        X_padded_end = np.fft.fft(x_padded_end)
        x_ifft_end = np.fft.ifft(np.concatenate((X_padded_end, np.zeros(pad))))
        return x_ifft_end
    
    
    def pad_both(size, pad):
        np.random.seed(42)
        x = np.random.randn(512)
        x_padded_both = np.concatenate((np.zeros(pad), x, np.zeros(pad)))
        X_padded_both = np.fft.fft(x_padded_both)
        x_ifft_both = np.fft.ifft(np.concatenate((X_padded_both, np.zeros(pad))))
        return x_ifft_both
    
    
    end = pad_end(512, 64)
    both = pad_both(512, 64)
    
    plt.figure(figsize=(12, 6))
    plt.subplot(2, 1, 1)
    plt.plot(np.real(end), label='Real')
    plt.plot(np.imag(end), label='Imaginary')
    plt.title('iFFT with Zero-padding at the End')
    plt.legend()
    
    plt.subplot(2, 1, 2)
    plt.plot(np.real(both), label='Real')
    plt.plot(np.imag(both), label='Imaginary')
    plt.title('iFFT with Zero-Padding at the Start')
    plt.legend()
    
    plt.tight_layout()
    plt.show()
    
    

    Prints

    enter image description here

    Note

    Zero-padding at the start and the end of a signal helps mitigate the boundary effects due to the "circular convolution" in FFT/iFFT, which leads to a "smoother" iFFT, if you will, that is closer to zero at the end. That's why you see the difference in the iFFT output when you added zeros at the start of your signal.


    DCT and iDCT

    The same principle can also be applied to DCT and iDCT, even though the nature and applications of these transforms are different from FFT and iFFT.

    Zero-padding a signal before applying DCT increases the resolution in the frequency domain. The additional zeros don't change the original frequency content, but provide a more detailed representation of the spectrum.

    When you perform an iDCT on a zero-padded DCT, the original part of the signal remains mostly unaffected. However, the additional zeros can introduce artifacts similar to FFT/iFFT, although the DCT's real-valued nature might lead to different visual effects.

    Note that, as opposed to FFT, DCT does not inherently assume circular convolution. Instead, it implicitly assumes that the signal is "even-symmetric". This means that padding, especially if not done symmetrically, can affect the transformed signal differently.

    Code

    import numpy as np
    import matplotlib.pyplot as plt
    from scipy.fftpack import dct, idct
    
    
    def pad_end_dct(size, pad):
        np.random.seed(4)
        x = np.random.randn(size)
    
        x_padded_end = np.concatenate((x, np.zeros(pad)))
        X_padded_end = dct(x_padded_end, norm='ortho')
        x_idct_end = idct(np.concatenate((X_padded_end, np.zeros(pad))), norm='ortho')
        return x_idct_end
    
    
    def pad_both_dct(size, pad):
        np.random.seed(4)
        x = np.random.randn(size)
    
        x_padded_both = np.concatenate((np.zeros(pad), x, np.zeros(pad)))
        X_padded_both = dct(x_padded_both, norm='ortho')
        x_idct_both = idct(np.concatenate((X_padded_both, np.zeros(pad))), norm='ortho')
        return x_idct_both
    
    
    end_dct = pad_end_dct(512, 64)
    both_dct = pad_both_dct(512, 64)
    
    plt.figure(figsize=(12, 6))
    plt.subplot(2, 1, 1)
    plt.plot(np.real(end_dct), label='Real')
    plt.plot(np.imag(end_dct), label='Imaginary')
    plt.title('iDCT with Zero-padding at the End')
    plt.legend()
    
    plt.subplot(2, 1, 2)
    plt.plot(np.real(both_dct), label='Real')
    plt.plot(np.imag(both_dct), label='Imaginary')
    plt.title('iDCT with Zero-padding at the Start and End')
    plt.legend()
    
    plt.tight_layout()
    plt.show()
    
    

    Prints

    enter image description here

    Link

    See circular convolution