When performing an FFT, modifying the magnitude spectrum in some arbitrary way, and then applying an inverse FFT, how should I handle circular convolution? How can I determine the appropriate amount of zero-padding needed for each FFT frame to avoid artifacts?

Also, since I'm only altering the magnitude spectrum and leaving the phase untouched, does that imply the resulting filter is linear-phase, or possibly zero-phase?

Thanks!

Yeah, what you are doing by manipulating amplitude is effectively some sort of filtering operation (just not conventional).  Over 20 yrs ago I had a guy doing this at work who claimed he could notch filter anything just by zotting out spectral amplitude bins.  He never really understood why that was a bad idea... 

Anyway, since you are not increasing the FFT size to ensure linear convolution, you will get circular convolution, or in other words time aliasing.  So you need to throw those points out.  You can take a look at overlap-save version of fast convolution - which tells you how many points are valid convolution and how many are aliased.  That might allow you to get away with your method by analyzing the response of your inherent spectral filter and only taking valid convolution points after your ifft.

Jim

To convert circular convolution into linear convolution using the FFT, you must zero-pad both input sequences to a total length that is at least:

$$N \ge L_x + H_h -1$$

Where:

\( L_x \): Length of x[n]

\(L_h \): Length of h[n]

\(N\): FFT size (length after padding)

Typically you would round \(N\) up to the next power of two for use with efficient radix-2 FFT processing.

A zero phase filter will only alter the magnitude spectrum (and is non-causal, but we hide the delay through post processing). A linear phase filter is a zero phase filter with causal delay.

Thanks, that makes sense. But how do i know the length of h[n]? 

I am not designing an impulse response in the time domain. I am (for example) just randomly altering the amplitude of some bins in the frequency domain.

Doing an N-point IFFT of that frequency domain filter gives me a time domain filter with N coefficients. Does that imply the length of h[n] is N? So i should zero pad with N?

Also, i have not touched the phase response, only the magnitudes. So would that mean this is a zero phase filter?

If you are implementing a filter, then your goal is to convolve x[n] with h[n] where x[n] is your time domain sequence and h[n] is the coefficients of your filter. At that point, if you want to know the length of h[n], then this would be in the details of the filter design independent of how you go about doing the convolution. 

I highly recommend NOT designing filters by simply taking the IFFT of the frequency response (this is called the "Frequency Sampling" method and results in the worst performance for the same number of taps vs other design methods). This does work if you significantly oversample the frequency response, then truncate and importantly window the resulting time domain impulse response (which to me is then the traditional "window design method", not frequency sampling-- we're just using the FFT to estimate the ideal time domain impulse response free of time domain aliasing for the desired frequency response which we then truncate and window-- that is exactly the "window design method").  

If you want to design a linear phase FIR filter, my go-to approach is to use 'firls' available in Matlab, Octave or Python scipy.signal to get the optimized solution (in the least squares sense). So to re-iterate, don't do Frequency Sampling (other than the way I described which is not getting N coefficients from an N-point DFT). Don't do Parks-McClellan Equi-ripple. I've never seen either come up with a better filter for the same number of taps for any applications I have ever used.

Below is a YouTube link of my presentation at last year's GNU Radio conference where I explain this in more detail, or even better jump into the "DSP for Wireless Communications" course here at dsprelated.com when it is running next to get the 22 hour but complete explanation including tons of demos in Python, and come out of that as a FIR filter design expert (and have a lot of fun in the process)! 

 Regardless of approach, once you get your filter coefficients (h[n]), then if you want to proceed with frequency domain filtering, use the formula I gave in my first answer above to determine N. In all cases N is larger than the length of h. Your other option is to filter using convolution directly ('firls' in Matlab / Octave and Python scipy's signal.)

Sorry I tried to answer that last question in the last paragraph of my answer but perhaps it wasn't clear. If you have a filter that only modifies the magnitude in its frequency response, this means it's phase response is zero and then yes that is a zero phase filter.

Thanks! I’ll definitely check out the course, it looks like a lot of fun.

I agree that desiging filters from an IFFT is not ideal. But i assumed this would be the best approach since the goal is to compare frequency responses and then filter one spectrum (multiply the magnitude response) to match the magnitude response of the other. The filter would also be constantly changing since the magnitude spectra of the signals are continously changing. 

So i'm not really taking the IFFT of the frequency response of the filter, i'm multiplying the magnitude of the bins, which is equivalent to convolution in the time domain. That's why i got confused about how to deal with circular convolution.

I believe what you are describing is taking the IFFT of the frequency response of the filter even though you say you're not really doing it. The issue is the response you are predicting by just using the FFT bins alone perfectly describes the underlying filter response you are trying to describe ONLY at those bin locations (while a filter response is continuous in the frequency domain: we can pass any frequency tone through the filter, not just the discrete locations you are accounting for). The resulting response in between those bins has larger order then the other approaches. Further doing the other approaches could be a lot easier (depending on what you actually care about between targeting a real time hardware implementation or doing post processing analysis).

I suspect from what you are describing is you would like to do either channel estimation or channel equalization -- that's another topic I go through in helpful practical detail in my "DSP for Software Radio" course starting next week! (and today is the final day to get in at the $100 discount). FYI in case it could help you.

The Matlab/Octave function "fir2" designs filters based on frequency sampling.

Instead of zero padding, it uses a suitably high-resolution frequency grid including interpolation techniques on amplitude values. The grid should be just high enough such that truncation yields the middle main values and several values on either side. This method may result in a better response for arbitrary filters. 

As to applying filtering in frequency domain, you will multiply fft of input with fft of filter followed by iFFT. I will use overlap-add on fft/ifft frames.

Just curious why do you go this expensive way instead of classic time domain filtering.

As to phase, unless you use complex FFT/iFFT and your amplitude response is symmetrical across positive/negative frequencies then I assume you get linear phase filter.

I’ll have a look at the ‘fir2’from MATLAB. Looks pretty similar to what i want to achieve, thanks

The goal is to compare different frequency responses to each other and design a filter based on the differences in the magnitude response.

I guess the frequency domain is most convenient for doing that.

I guess you are focussed on filter design rather than applying filtering. In that case I agree that manually changing amplitude in frequency domain will do but you need to keep the two halves of fft frame symmetrical to achieve linear phase. Consider odd fft frames as it is easier for that symmetry.

Hi

while all the answers above are correct, it seems to me you are not trying to design a specific filter once and then apply it for all ages to come in the frequency domain, but are rather trying to fit two spectra and change your magnitude spectrum manipulation in real time and all the time.

If this is correct, than you are doing something that is done rather freely all the time in audio coding and speech processing and I congratulate you on noticing that this is actually a convolution and you will get circular artifacts. Because many people in the field and paper authors don't seem to notice :)

They do notice, however, that applying sharp or narrow band manipulations in the frequency domain will produce 'ringing' or 'musical noise'. This is due to sharp or narrowband modifications corresponding to long impulse responses and thus more noticable circular convolution. Coming from the pro audio world where everything needs to be as original and untouched as possible, I heavily frowned upon all the nasty stuff going on in speech processing - until I found you can do amazing stuff with these methods if you follow a few guidelines. Here goes:

1. Use windowed overlapping short time ffts

Operate on blocks of audio and let them overlap. Apply a window to the single blocks, that fades out the beginnings and ends of each block (e.g. Von Hann). This will attenuate block-edge effects of circular convolution. If you have a convolution with a rather short impulse response, the artifact will be drowned out by this operation

2. avoid narrow band manipulations

As stated above, narrow band operations result in long sinusoidal impulse responses resulting in strong circular convolution artifacts. How people make sure of this differs, some avergae in the frequency domain, but many combine several frequency domain bins in Mel bins (google mel frequency domain) and then modify those mel bins - this assures all modifications to be rather broad-band

3. avoid too-strong manipulations

This is similar to 2.) - and if you follow 2.), you can actually implement very strong manipulations without too many artifacts, but it helps to keep your manipulations to a minimum. If - for example - you want to implement a noise removal algorithm that mutes all noisy bands by setting them to zero, you will get much more artifacts, than reducing all noisy bands by 12dB

4. don't chnage your manipulations too quickly

While not an artifact of circular convolution, it is still a good custom to change manipulations slowly over time - otherwise, artifacts will become noticable to the point where you manipulation change is actually an audible oscillation that modulates a bin creating entirely new frequencies

Hope, this helps

Markus, audioedge