FIR filter with output same length as input which is also time-aligned with input

I want to do some frame-based processing of an input signal with a
C-code program on a hardware DSP.  One of the things I really want is
an FIR filter which gives an output signal with the same length (in
terms of samples) as the input signal and is also time-aligned with the
input (i.e no delay or offset).  All of the FIR implementations I have
seen either result in a shorter output, delay the output by m/2 samples
(where m is the filter order), or truncate the last m/2 samples.

Since we are talking about frame-based processing and not
point-by-point processing, I think what I want should be possible.  I
expect that the filter will probably need to be acausal, but I only
have experience with designing/implementing causal filters.

Does anyone hvae any code that implements this sort of filter or can
someone point me to a book, article, or webpage which describes how to
do it in sufficient detail that I would be able to implement it myself?

The MATLAB Signal Processing Toolbox command "filtfilt" comes very
close to doing what  I want.  It actually does something significantly
more complicated  than what I need (and is thus significantly less
efficient than I would like).  But it's existence is essentially proof
to me that what I want should be doable.

Any advice would be greatly appreciated.

todd.leonhardt@gmail.com wrote:
> I want to do some frame-based processing of an input signal with a
> C-code program on a hardware DSP.  One of the things I really want is
> an FIR filter which gives an output signal with the same length (in
> terms of samples) as the input signal and is also time-aligned with the
> input (i.e no delay or offset).  All of the FIR implementations I have
> seen either result in a shorter output, delay the output by m/2 samples
> (where m is the filter order), or truncate the last m/2 samples.
> 
> Since we are talking about frame-based processing and not
> point-by-point processing, I think what I want should be possible.  I
> expect that the filter will probably need to be acausal, but I only
> have experience with designing/implementing causal filters.
> 
> Does anyone hvae any code that implements this sort of filter or can
> someone point me to a book, article, or webpage which describes how to
> do it in sufficient detail that I would be able to implement it myself?
> 
> The MATLAB Signal Processing Toolbox command "filtfilt" comes very
> close to doing what  I want.  It actually does something significantly
> more complicated  than what I need (and is thus significantly less
> efficient than I would like).  But it's existence is essentially proof
> to me that what I want should be doable.
> 
> Any advice would be greatly appreciated.
> 

If your frames are contiguous samples from a stream of data, then
you should really save state between frames, or you will get chirps at
frame boundaries.  Find a way to live with the m/2 delay.

If the data frames are standalone sequences that do not represent
streams, read on.

With a symmetric FIR filter of length 2L+1, the group delay is L.
Convolving that with a vector of length K would yield a full convolution
sequence of length K+2L.

Assuming you are using a Matlab-style filter that gives you all of the
input-on transient and none of the input-off transient; Drop L samples
from the input-on transient and pad L zeros on the end of your input
sequence.

If all the above is true, this should nicely superimpose the input &
output vectors.  The beginning and ending of the sequence will show some
warbling, but *if* you don't know what the signal was before or after,
then this is about as good as you can do.

I repeat.  If the frames are chunks of a continuous signal -- keep the
state and find a way to deal with the group delay.


-- Mark Borgerding

Mark Borgerding wrote:
> todd.leonhardt@gmail.com wrote:
> 
>>I want to do some frame-based processing of an input signal with a
>>C-code program on a hardware DSP.  One of the things I really want is
>>an FIR filter which gives an output signal with the same length (in
>>terms of samples) as the input signal and is also time-aligned with the
>>input (i.e no delay or offset).  All of the FIR implementations I have
>>seen either result in a shorter output, delay the output by m/2 samples
>>(where m is the filter order), or truncate the last m/2 samples.
>>
>>Since we are talking about frame-based processing and not
>>point-by-point processing, I think what I want should be possible.  I
>>expect that the filter will probably need to be acausal, but I only
>>have experience with designing/implementing causal filters.
>>
>>Does anyone hvae any code that implements this sort of filter or can
>>someone point me to a book, article, or webpage which describes how to
>>do it in sufficient detail that I would be able to implement it myself?
>>
>>The MATLAB Signal Processing Toolbox command "filtfilt" comes very
>>close to doing what  I want.  It actually does something significantly
>>more complicated  than what I need (and is thus significantly less
>>efficient than I would like).  But it's existence is essentially proof
>>to me that what I want should be doable.
>>
>>Any advice would be greatly appreciated.
>>
> 
> 
> If your frames are contiguous samples from a stream of data, then
> you should really save state between frames, or you will get chirps at
> frame boundaries.  Find a way to live with the m/2 delay.
> 
> If the data frames are standalone sequences that do not represent
> streams, read on.
> 
> With a symmetric FIR filter of length 2L+1, the group delay is L.
> Convolving that with a vector of length K would yield a full convolution
> sequence of length K+2L.
> 
> Assuming you are using a Matlab-style filter that gives you all of the
> input-on transient and none of the input-off transient; Drop L samples
> from the input-on transient and pad L zeros on the end of your input
> sequence.
> 
> If all the above is true, this should nicely superimpose the input &
> output vectors.  The beginning and ending of the sequence will show some
> warbling, but *if* you don't know what the signal was before or after,
> then this is about as good as you can do.
> 
> I repeat.  If the frames are chunks of a continuous signal -- keep the
> state and find a way to deal with the group delay.
> 
> 
> -- Mark Borgerding

Alternatively, if you find a non-causal filter,
please post the code! :=)

Regards,
John

Just chop off what you don't like.  :)

dbell

Mark,

Thanks for your advice.

The frames are contiguous samples from a sensor.  However, I plan on
extracting relevant info/parameters on a frame-by-frame basis, at least
to start with, so I'm not overly concerned with discontinuities at
frame boundaries.

I quickly tested your advice in MATLAB regarding taking the full-blown
convolution and chopping m/2 samples off both the beginning and end of
the output.  This seems to work very well except at the edges.  I might
be able to live with that and I also think I might be able to make it
work a litlte better if I make some intelligent assumptions regarding
the filter's initial state.  But your point about keeping the state is
well taken.  It would obviously work much better if I saved some
information from the previous frame.

Thanks for your advice,

Todd

John,

Implementing a non-causal filter is not an oxymoron if you are doing
frame-based processing (as opposed to point-by-point "hard" realtime
processing).  Here is my pseudocode for implementing a noncausal
filter:

x = input signal
X = FFT{x}
A = desired magnitude response of filter
(could have A = FFT{h}, where h are filter coefficients)
y = output signal

y = IFFT{X * A}

So I found one and there's the code .... ;-)

I guess I was just wondering if there was an easy way to implement this
type of filtering in the time-domain and if so what the
advantages/disadvantages are.  I think Mark basically answered my
question.

-Todd

Todd Leonhardt wrote:
> John,
> 
> Implementing a non-causal filter is not an oxymoron if you are doing
> frame-based processing (as opposed to point-by-point "hard" realtime
> processing).  Here is my pseudocode for implementing a noncausal
> filter:
> 
> x = input signal
> X = FFT{x}
> A = desired magnitude response of filter
> (could have A = FFT{h}, where h are filter coefficients)
> y = output signal
> 
> y = IFFT{X * A}
> 
> So I found one and there's the code .... ;-)
> 
> I guess I was just wondering if there was an easy way to implement this
> type of filtering in the time-domain and if so what the
> advantages/disadvantages are.  I think Mark basically answered my
> question.
> 
> -Todd
> 
Todd,
I could not resist that comment and I am sure it did not cause any offence.

I think we differ as to what we mean by acausal.
I take an 'acausal' filter to be one in which the output is derived in 
part at least from signal samples that have yet to arrive.  The term 
comes up in textbooks because it is easiest to define t=0 as the centre 
of the impulse response.  If I had an acausal filter (a very long one) I 
think I could make a lot of money on the stock market, hence my request :=)

Unfortunately I don't think your pseudo-code qualifies because it does 
not even begin processing until all the samples in one batch have arrived.

By the way, I don't think it makes any sense to talk about causality or 
non-causality in regard to processing that is not real-time, but of 
course this may depend on your definition.

Regards,
John

John Monro wrote:

   ...

> I think we differ as to what we mean by acausal.
> I take an 'acausal' filter to be one in which the output is derived in 
> part at least from signal samples that have yet to arrive.  The term 
> comes up in textbooks because it is easiest to define t=0 as the centre 
> of the impulse response.  If I had an acausal filter (a very long one) I 
> think I could make a lot of money on the stock market, hence my request :=)
> 
> Unfortunately I don't think your pseudo-code qualifies because it does 
> not even begin processing until all the samples in one batch have arrived.
> 
> By the way, I don't think it makes any sense to talk about causality or 
> non-causality in regard to processing that is not real-time, but of 
> course this may depend on your definition.

John,

I have seen "acausal" loosely applied to off-line processing when the 
center of the (usually symmetric) impulse is assigned the value t=0. 
This simplifies the mathematics in many instances, but it has the 
unfortunate effect of allowing the unwary to believe that latency has 
been eliminated. It is easy to see how its formal definition (output 
before input) and its metaphoric use (t=0 later than the first element) 
can together create confusion.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:
> John Monro wrote:
> 
>   ...
> 
>> I think we differ as to what we mean by acausal.
>> I take an 'acausal' filter to be one in which the output is derived in 
>> part at least from signal samples that have yet to arrive.  The term 
>> comes up in textbooks because it is easiest to define t=0 as the 
>> centre of the impulse response.  If I had an acausal filter (a very 
>> long one) I think I could make a lot of money on the stock market, 
>> hence my request :=)
>>
>> Unfortunately I don't think your pseudo-code qualifies because it does 
>> not even begin processing until all the samples in one batch have 
>> arrived.
>>
>> By the way, I don't think it makes any sense to talk about causality 
>> or non-causality in regard to processing that is not real-time, but of 
>> course this may depend on your definition.
> 
> 
> John,
> 
> I have seen "acausal" loosely applied to off-line processing when the 
> center of the (usually symmetric) impulse is assigned the value t=0. 
> This simplifies the mathematics in many instances, but it has the 
> unfortunate effect of allowing the unwary to believe that latency has 
> been eliminated. It is easy to see how its formal definition (output 
> before input) and its metaphoric use (t=0 later than the first element) 
> can together create confusion.
> 
> Jerry

Jerry,
I thought I could indulge in a little pedantry, especially since Mark 
had pretty well answered Todd's query.
Actually something useful did occur to me, and I hope Todd is still 
following this thread.  Todd, why not tack extra samples onto each 
frame, taking these from the end of the previous frame and the start of 
the next frame?  If the impulse response is N samples long and you add 
N/2 signal samples to each end then this will eliminate the 'end 
effect,' as far as the original frame is concerned.

I am of course describing what is done with the 'overlap/save' method of 
doing fast convolution, and this technique is well documented.

Regards,
John

John Monro wrote:

> Jerry,
> I thought I could indulge in a little pedantry, especially since Mark 
> had pretty well answered Todd's query.
> Actually something useful did occur to me, and I hope Todd is still 
> following this thread.  Todd, why not tack extra samples onto each 
> frame, taking these from the end of the previous frame and the start of 
> the next frame?  If the impulse response is N samples long and you add 
> N/2 signal samples to each end then this will eliminate the 'end 
> effect,' as far as the original frame is concerned.
> 
> I am of course describing what is done with the 'overlap/save' method of 
> doing fast convolution, and this technique is well documented.

I don't see that you were any more pedantic than I was. I merely wanted 
to enter a caveat; that the formal meaning of "causal" and the 
colloquial way it is used to to mean a shifted time reference can lead 
the unwary to believe that latency can be circumvented. I don't think I 
contradicted you in any way.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������