Stephan M. Bernsee <spam@dspdimension.com> wrote in message news:<2sc8a6F1ib1cdU1@uni-berlin.de>...
> On 2004-10-04 08:06:36 +0200, allnor@tele.ntnu.no (Rune Allnor) said:
>
> > We are back to that 'periodic/non-periodic' thing with the DFT.
> > A FIR filter implemented in time domain, works on a finite section of a
> > discrete-time sequence of infinite duration. End transients are
> > appended to this section.
> >
> > In frequency domain, the DFT is formally correct for periodic discrete-
> > time sequences of infinite duration. So instead of a start-up transient
> > where the initial registers of the FIR filter are 0, the initial states
> > of the registers are the tail samples of x, because of the signal being
> > extended periodically. Which is why one needs to zero-pad M-1 samples
> > to x before transforming to frequency domain.
> >
> > Rune
>
> Wasn't that what I said? :-)
Yes it was. The only difference was that you condenced the whole
explanation of my last paragraph into one term, 'circular convolution'.
I've been in 'instructor mode' that last couple of days, so I have
this nasty habit of expanding and elaborating on those kinds of terms.
Sorry.
Rune
Reply by Stephan M. Bernsee●October 4, 20042004-10-04
On 2004-10-04 08:06:36 +0200, allnor@tele.ntnu.no (Rune Allnor) said:
> We are back to that 'periodic/non-periodic' thing with the DFT.
> A FIR filter implemented in time domain, works on a finite section of a
> discrete-time sequence of infinite duration. End transients are
> appended to this section.
>
> In frequency domain, the DFT is formally correct for periodic discrete-
> time sequences of infinite duration. So instead of a start-up transient
> where the initial registers of the FIR filter are 0, the initial states
> of the registers are the tail samples of x, because of the signal being
> extended periodically. Which is why one needs to zero-pad M-1 samples
> to x before transforming to frequency domain.
>
> Rune
Stephan M. Bernsee <spam@dspdimension.com> wrote in message news:<2s7qidF1i1aqcU1@uni-berlin.de>...
> On 2004-10-02 15:30:12 +0200, Jerry Avins <jya@ieee.org> said:
>
> > I was under the impression that ccnvolution was convolution, no matter
> > how implemented; that implemention via FFT/IFFT and via transversal
> > methods produce the same result. Was I wrong?
> >
> > Jerry
>
> The DFT produces circular convolution while plain FIRs produce the
> linear flavor. So, yes and no - the result *can* be the same if you
> take this into account.
We are back to that 'periodic/non-periodic' thing with the DFT.
A FIR filter implemented in time domain, works on a finite section of
a discrete-time sequence of infinite duration. End transients are
appended to this section.
In frequency domain, the DFT is formally correct for periodic discrete-
time sequences of infinite duration. So instead of a start-up transient
where the initial registers of the FIR filter are 0, the initial states
of the registers are the tail samples of x, because of the signal being
extended periodically. Which is why one needs to zero-pad M-1 samples
to x before transforming to frequency domain.
Rune
Reply by Stephan M. Bernsee●October 2, 20042004-10-02
On 2004-10-02 16:52:03 +0200, Jerry Avins <jya@ieee.org> said:
> That's a matter of implementation detail. I can do circular transversal
> convolution as well as linear. With transversal convolution, linear
> convolution is usually the simple case, while with transform
> convolution, it's the other way around.
>
> Jerry
Yes. That's why I said you *can* get the same result if you take this
into account.
--
Stephan M. Bernsee
http://www.dspdimension.com
Reply by Jerry Avins●October 2, 20042004-10-02
Stephan M. Bernsee wrote:
> On 2004-10-02 15:30:12 +0200, Jerry Avins <jya@ieee.org> said:
>
>> I was under the impression that ccnvolution was convolution, no matter
>> how implemented; that implemention via FFT/IFFT and via transversal
>> methods produce the same result. Was I wrong?
>>
>> Jerry
>
>
> The DFT produces circular convolution while plain FIRs produce the
> linear flavor. So, yes and no - the result *can* be the same if you take
> this into account.
That's a matter of implementation detail. I can do circular transversal
convolution as well as linear. With transversal convolution, linear
convolution is usually the simple case, while with transform
convolution, it's the other way around.
Jerry
--
... they proceeded on the sound principle that the magnitude of a lie
always contains a certain factor of credibility, ... and that therefor
... they more easily fall victim to a big lie than to a little one ...
A. H.
�����������������������������������������������������������������������
Reply by Stephan M. Bernsee●October 2, 20042004-10-02
On 2004-10-02 15:30:12 +0200, Jerry Avins <jya@ieee.org> said:
> I was under the impression that ccnvolution was convolution, no matter
> how implemented; that implemention via FFT/IFFT and via transversal
> methods produce the same result. Was I wrong?
>
> Jerry
The DFT produces circular convolution while plain FIRs produce the
linear flavor. So, yes and no - the result *can* be the same if you
take this into account.
--
Stephan M. Bernsee
http://www.dspdimension.com
Reply by Jerry Avins●October 2, 20042004-10-02
Rune Allnor wrote:
> "Jon Harris" <goldentully@hotmail.com> wrote in message news:<2s6dh9F1g4vvpU1@uni-berlin.de>...
>
>>They probably internally add zeros before and after the data, run the data
>>through the FIR filter, and then trim off some of the transient elements off the
>>front and back end so the result is equal number of output to input samples.
>
>
> Good implementations do that. The quick'n dirty method is to do all the
> computations in frequency domain:
>
> % Matlab pseudocode
> X=fft(x);
> H=fft(h,N);
> y=real(ifft(X.*H));
>
> where x is the data, h is the FIR filter impulse response and N is the
> number of samples in x. Here, I would expect wrap-around effects.
>
> It ought to be easy to spot such a quick'n dirty implementation, though:
> Test the routine with an impulse sequence x (x(0)=1, all other
> samples = 0), and plot the output y. If there are non-zero samples
> near the tail end of y, you know something is wrong.
>
> Rune
I was under the impression that ccnvolution was convolution, no matter
how implemented; that implemention via FFT/IFFT and via transversal
methods produce the same result. Was I wrong?
Jerry
--
... they proceeded on the sound principle that the magnitude of a lie
always contains a certain factor of credibility, ... and that therefor
... they more easily fall victim to a big lie than to a little one ...
A. H.
�����������������������������������������������������������������������
Reply by Rune Allnor●October 2, 20042004-10-02
"Jon Harris" <goldentully@hotmail.com> wrote in message news:<2s6dh9F1g4vvpU1@uni-berlin.de>...
> They probably internally add zeros before and after the data, run the data
> through the FIR filter, and then trim off some of the transient elements off the
> front and back end so the result is equal number of output to input samples.
Good implementations do that. The quick'n dirty method is to do all the
computations in frequency domain:
% Matlab pseudocode
X=fft(x);
H=fft(h,N);
y=real(ifft(X.*H));
where x is the data, h is the FIR filter impulse response and N is the
number of samples in x. Here, I would expect wrap-around effects.
It ought to be easy to spot such a quick'n dirty implementation, though:
Test the routine with an impulse sequence x (x(0)=1, all other
samples = 0), and plot the output y. If there are non-zero samples
near the tail end of y, you know something is wrong.
Rune
> "Shafik" <shafik@u.arizona.edu> wrote in message
> news:1096677693.488575.276830@k26g2000oda.googlegroups.com...
> > Ahh ok.
> >
> > How come then, some DSP packages do an "inplace" buffer filtration.
> > Meaning I can take an input buffer X and just FIR filter it, and I'll
> > get X but filtered (same length). How is that possible?
> >
Reply by Jon Harris●October 1, 20042004-10-01
They probably internally add zeros before and after the data, run the data
through the FIR filter, and then trim off some of the transient elements off the
front and back end so the result is equal number of output to input samples.
"Shafik" <shafik@u.arizona.edu> wrote in message
news:1096677693.488575.276830@k26g2000oda.googlegroups.com...
> Ahh ok.
>
> How come then, some DSP packages do an "inplace" buffer filtration.
> Meaning I can take an input buffer X and just FIR filter it, and I'll
> get X but filtered (same length). How is that possible?
>
Reply by Jerry Avins●October 1, 20042004-10-01
Shafik wrote:
> Ahh ok.
>
> How come then, some DSP packages do an "inplace" buffer filtration.
> Meaning I can take an input buffer X and just FIR filter it, and I'll
> get X but filtered (same length). How is that possible?
>
I don't know the details of how it's done, but there must be some
intermediate storage somewhere. That the data start and end in the same
place doesn't mean that it has never been elsewhere. As for the size
being the same, there's a certain amount of sense to discarding the
outer parts of the transients.
Jerry
--
... they proceeded on the sound principle that the magnitude of a lie
always contains a certain factor of credibility, ... and that therefor
... they more easily fall victim to a big lie than to a little one ...
A. H.
�����������������������������������������������������������������������