Implementation of FIR filters

FIR filters can be implemented in time domain and frequency domain. From 
time domain I mean the multiplication and addition applied directly to the 
samples. In frequency domain, samples are transformed to frequency domain 
and processed and converted back to time domain.

My understanding is that frequency domain implementation can be done only 
for recorded signals, and cannot be used for real time applications, where 
an output sample is generated soon after a new input sample arrives. Is this 
correct? 

> My understanding is that frequency domain implementation can be done only
> for recorded signals, and cannot be used for real time applications, where
> an output sample is generated soon after a new input sample arrives. Is this
> correct?

Assume that you have an algorithm implementing FIR filters of order N
for recorded signals of length M. For streaming (real-time)
application, you can break up the stream into sections of length M and
apply your algorithm. Afterwards, you can splice the resultant output
blocks (now of length M+N-1) back together to form a continuous output
stream. You will have a processing latency of at least M until the
filtered output appears.

These techniques are known as overlap-add or overlap-save, and are
described, for example, in the DSP guide: http://www.dspguide.com,
Chapter 18.

Regards,
Andor

I. R. Khan wrote:

> My understanding is that frequency domain implementation can be done 
> only for recorded signals, and cannot be used for real time 
> applications, where an output sample is generated soon after a new input 
> sample arrives. Is this correct?

Not really.  Either one can be applied in real-time;  both of
them will exhibit a certain delay (a "processing lattency"),
only that the Fast convolution lattency is a lot higher -- but
one block of, say, 1024 samples at 44100 kHz sampling rate is
in the order of the 20msec, which is an acceptable processing
delay for audio (well, it probably depends on the particular
application)

HTH,

Carlos
--

Google for BruteFIR and download the description. You will see that it
is possible to do a lot in realtime.

E.g. I run 8 FIR filters with 65536 taps each with online audio.

Uli

Thanks Andor, Carlos and Uli.

If filtering can be done in frequency domain in real time, then why there is 
any need of calculating filter coefficients? Do these coefficients offer any 
advantage in any way over frequency domain implementaton?

ACTUAL frequency response of an FIR filter just APPROXIMATES the IDEAL 
frequency response. If filtering can be done in frequency domain quite 
efficiently, then why don't we use IDEAL frequency response, instead of 
using an APPROXIMATE response? For example, in case of halfband lowpass 
filter, why don't we set all the frequencies above Nyguest/2 to zero, 
instead of using equiripple or MAXFLAT filters with large ripple or wide 
transition band?

Regards,
Ishtiaq.




"I. R. Khan" <ir_khan@hotmail.com> wrote in message 
news:3h9vdcFfv3qnU1@individual.net...
> FIR filters can be implemented in time domain and frequency domain. From 
> time domain I mean the multiplication and addition applied directly to the 
> samples. In frequency domain, samples are transformed to frequency domain 
> and processed and converted back to time domain.
>
> My understanding is that frequency domain implementation can be done only 
> for recorded signals, and cannot be used for real time applications, where 
> an output sample is generated soon after a new input sample arrives. Is 
> this correct? 

in article 3hc0bbFgcoh2U1@individual.net, I. R. Khan at ir_khan@hotmail.com
wrote on 06/15/2005 20:49:

> If filtering can be done in frequency domain in real time, then why there is
> any need of calculating filter coefficients? Do these coefficients offer any
> advantage in any way over frequency domain implementaton?

what you have to do is design your FIR to be *finite* in length, whether
it's a regular old FIR or the fancy-smancy "fast" FIR (using FFT and
overlap-add/save).  what you are likely thinking of is what we might call
the "windowing method".

> ACTUAL frequency response of an FIR filter just APPROXIMATES the IDEAL
> frequency response. If filtering can be done in frequency domain quite
> efficiently, then why don't we use IDEAL frequency response, instead of
> using an APPROXIMATE response?

because it's too long of an impulse response.

> For example, in case of halfband lowpass
> filter, why don't we set all the frequencies above Nyguest/2 to zero,

then you better have all frequencies below Nyquist/2 be 1 or some constant
for it to be a halfband LPF.

> instead of using equiripple or MAXFLAT filters with large ripple or wide
> transition band?

suppose you do that for an FFT of size, say, 1024K.  then do it for a more
reasonable size of, say, 1024.  now compare the two.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

I. R. Khan wrote:
> Thanks Andor, Carlos and Uli.
> 
> If filtering can be done in frequency domain in real time, then why 
> there is any need of calculating filter coefficients? Do these 
> coefficients offer any advantage in any way over frequency domain 
> implementaton?
> 
> ACTUAL frequency response of an FIR filter just APPROXIMATES the IDEAL 
> frequency response. If filtering can be done in frequency domain quite 
> efficiently, then why don't we use IDEAL frequency response, instead of 
> using an APPROXIMATE response? For example, in case of halfband lowpass 
> filter, why don't we set all the frequencies above Nyguest/2 to zero, 
> instead of using equiripple or MAXFLAT filters with large ripple or wide 
> transition band?
> 

Ishtiaq,
It is an appealing idea, to be able to 'pluck out' all the unwanted
frequency components in a signal by setting them to zero in the
frequency domain.  In effect we would be implementing a filter with an
ideal, or 'brick wall' frequency response and no-one has found a way to
do that in the time domain.

Unfortunately, it turns out that we can't do that in the frequency
domain either.

The problem that arises when you attempt to define a 'brick-wall'
frequency response by plucking out frequency-domain samples is that the
intended filter has an infinitely-long impulse response.

Frequency-domain filters require that the impulse-response duration of
the filter must be shorter than the sample batch-length used with the
filter.  Typically the impulse-response duration is designed to be one
half of the batch length.  Noise and distortion results if this
requirement is not observed.

Of course with an infinite impulse-response length it is impossible to
implement a batch-length that is long enough, so noise and distortion
will result.

If, on the other hand an overlap-save frequency-domain filter is
designed so that its impulse-response is short enough then we avoid the
noise and distortion problem.  Unfortunately, the frequency-response now
has all the familiar non-ideal characteristics of ripple, finite
transition band and non-zero stop-band response.

The advantage of frequency-domain filters is that the computation time
can be far less than time-domain.  Unfortunately, it is not a way to
realise an 'ideal' frequency response.

Regards,
John

John wrote:

> Frequency-domain filters require that the impulse-response duration of
> the filter must be shorter than the sample batch-length used with the
> filter.  Typically the impulse-response duration is designed to be one
> half of the batch length.  Noise and distortion results if this
> requirement is not observed.

John,

I don't think that this is correct, and it is easy to see why:
convolution is symmetric. Swaping the role of the filter kernel and the
input signal (ie. viewing the input signal as the filter and vice
versa) shows that that you can also use a filter with a longer impulse
response than the data you are filtering.

Another way of viewing it is as follows: frequency domain filtering is
equivalent to time domain filtering. Is there any reason why one should
not be able to filter a segment of data that is shorter than the finite
impulse response by straight forward convolution? Think about filtering
an impulse ... you get the famous impulse response of the filter, a
perfectly valid operation!

In general, the only limitation in frequency domain filtering is that
the sample batch length (let's call it M) and the filter impulse
response length (let's call it N) must satisfy N+M-1 <= FFT length. The
reason for this limitation is to avoid circular convolution.

Regards,
Andor

Thank you John for your explaination. It has made things quite clearer, but 
I still have some confusions.

Does the time domain implementation have any advantage over frequency domain 
implementation, in any way?

If the answer is no, then do we ever need to know the filter coefficients? 
Most of the FIR designs found in literature give filter's coefficients. 
Shouldn't we be intersted in knowing only the frequency response? For 
example, if we can find a formula to generate a nice equiripple lowpass 
curve, do we need to know the corresponding time domain coefficients?

Regards,
Ishtiaq.


"John Monro" <johnmonro@remove-this.optusnet.com.au> wrote in message 
news:42b131da$0$16705$afc38c87@news.optusnet.com.au...
> I. R. Khan wrote:
>> Thanks Andor, Carlos and Uli.
>>
>> If filtering can be done in frequency domain in real time, then why
>> there is any need of calculating filter coefficients? Do these
>> coefficients offer any advantage in any way over frequency domain
>> implementaton?
>>
>> ACTUAL frequency response of an FIR filter just APPROXIMATES the IDEAL
>> frequency response. If filtering can be done in frequency domain quite
>> efficiently, then why don't we use IDEAL frequency response, instead of
>> using an APPROXIMATE response? For example, in case of halfband lowpass
>> filter, why don't we set all the frequencies above Nyguest/2 to zero,
>> instead of using equiripple or MAXFLAT filters with large ripple or wide
>> transition band?
>>
>
> Ishtiaq,
> It is an appealing idea, to be able to 'pluck out' all the unwanted
> frequency components in a signal by setting them to zero in the
> frequency domain.  In effect we would be implementing a filter with an
> ideal, or 'brick wall' frequency response and no-one has found a way to
> do that in the time domain.
>
> Unfortunately, it turns out that we can't do that in the frequency
> domain either.
>
> The problem that arises when you attempt to define a 'brick-wall'
> frequency response by plucking out frequency-domain samples is that the
> intended filter has an infinitely-long impulse response.
>
> Frequency-domain filters require that the impulse-response duration of
> the filter must be shorter than the sample batch-length used with the
> filter.  Typically the impulse-response duration is designed to be one
> half of the batch length.  Noise and distortion results if this
> requirement is not observed.
>
> Of course with an infinite impulse-response length it is impossible to
> implement a batch-length that is long enough, so noise and distortion
> will result.
>
> If, on the other hand an overlap-save frequency-domain filter is
> designed so that its impulse-response is short enough then we avoid the
> noise and distortion problem.  Unfortunately, the frequency-response now
> has all the familiar non-ideal characteristics of ripple, finite
> transition band and non-zero stop-band response.
>
> The advantage of frequency-domain filters is that the computation time
> can be far less than time-domain.  Unfortunately, it is not a way to
> realise an 'ideal' frequency response.
>
> Regards,
> John 

I wrote:

>In general, the only limitation in frequency domain filtering is that
>the sample batch length (let's call it M) and the filter impulse
>response length (let's call it N) must satisfy N+M-1 <= FFT length

On second thoughts, not even this limitation is required. This is only
required for overlap-add. In overlap-save, you can have M (or N) equal
to the FFT length (but you only use the part of the inverse FFT which
is not destroyed by circular convolution).