FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > DSP

DSP comp.dsp newsgroup, mailing list

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 09-24-2004, 10:57 PM
Richard Owlett
Guest
 
Posts: n/a
Default Is "brick wall" filter realizable?

This is intentionally "dumb" question.
I suspect a good answer will illuminate a fallacy in my thinking.

assume a real input
perform FFT
set all bins to 0 that are outside pass band
perform suitably scaled IFFT

What's wrong with this picture?
Reply With Quote
  #2 (permalink)  
Old 09-24-2004, 11:20 PM
glen herrmannsfeldt
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?



Richard Owlett wrote:

> This is intentionally "dumb" question.
> I suspect a good answer will illuminate a fallacy in my thinking.


> assume a real input
> perform FFT
> set all bins to 0 that are outside pass band
> perform suitably scaled IFFT


> What's wrong with this picture?


It is as sharp as the number of points in the transform.
(The frequency resolution is 1/(total length of transform).)

You need an infinite number of points for an infinitely
sharp cutoff.

-- glen

Reply With Quote
  #3 (permalink)  
Old 09-24-2004, 11:38 PM
Richard Owlett
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?

glen herrmannsfeldt wrote:

>
>
> Richard Owlett wrote:
>
>> This is intentionally "dumb" question.
>> I suspect a good answer will illuminate a fallacy in my thinking.

>
>
>> assume a real input
>> perform FFT
>> set all bins to 0 that are outside pass band
>> perform suitably scaled IFFT

>
>
>> What's wrong with this picture?

>
>
> It is as sharp as the number of points in the transform.
> (The frequency resolution is 1/(total length of transform).)
>
> You need an infinite number of points for an infinitely
> sharp cutoff.
>
> -- glen
>


Caution: I'm learning DSP by asking questions on this group

I had gotten the impression there was another problem other than what
may be considered "resolution issues'.

Reply With Quote
  #4 (permalink)  
Old 09-25-2004, 01:00 AM
Fred Marshall
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?


"Richard Owlett" <[email protected]> wrote in message
news:[email protected]
> This is intentionally "dumb" question.
> I suspect a good answer will illuminate a fallacy in my thinking.
>
> assume a real input
> perform FFT
> set all bins to 0 that are outside pass band
> perform suitably scaled IFFT
>
> What's wrong with this picture?


Answer #1: nothing is wrong with this picture. It is a good description of
what you did.

Answer #2: you have multiplied the FFT with a discrete "gate".
(Multiplication in frequency is equivalent to convolution in time). The
IFFT of the gate is a discrete Dirichlet function - so you have convolved
the original time series with a discrete, periodic Dirichlet function.
Depending on the orignal FFT of the time series, you may have created sharp
discontinuities in the frequency spectrum which will result in "high-time"
components in the IFFT. High-time components can introduce temporal
aliasing.

Because the Fourier Transform or DFT has duality, it might be easier to
imagine what happens if you do this operation in the time domain:

> assume a real spectrum
> perform IFFT
> set all bins to 0 that are outside some time interval
> perform suitably scaled FFT
>
> What's wrong with this picture?


Answer: If the real spectrum is zero around fs/2 (as it should be) then the
IFFT results in a bandlimited, periodic time sequence. When the time
sequence is multiplied by a gate, new frequencies can be introduced.
Depending on the shape of the original time sequence, this can introduce new
frequencies that are above the Nyquist limit so there will be spectral
aliasing.

Fred


Reply With Quote
  #5 (permalink)  
Old 09-25-2004, 01:34 AM
Eric Jacobsen
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?

On Fri, 24 Sep 2004 17:38:57 -0500, Richard Owlett
<[email protected]> wrote:

>glen herrmannsfeldt wrote:
>
>>
>>
>> Richard Owlett wrote:
>>
>>> This is intentionally "dumb" question.
>>> I suspect a good answer will illuminate a fallacy in my thinking.

>>
>>
>>> assume a real input
>>> perform FFT
>>> set all bins to 0 that are outside pass band
>>> perform suitably scaled IFFT

>>
>>
>>> What's wrong with this picture?

>>
>>
>> It is as sharp as the number of points in the transform.
>> (The frequency resolution is 1/(total length of transform).)
>>
>> You need an infinite number of points for an infinitely
>> sharp cutoff.
>>
>> -- glen
>>

>
>Caution: I'm learning DSP by asking questions on this group
>
>I had gotten the impression there was another problem other than what
>may be considered "resolution issues'.


You can implement a filter that way, and sometimes it's a fine thing
to do. Another thread here mentioned how this was used successfully
in some data processing, but subsequent use of a FIR with a sharp (but
not infinite) cutoff worked better.

The typical problem with the zero-ing-the-DFT trick is that the zeros
are only really valid at exactly the frequency sampling points and the
filter will have non-zero magnitude response between them. In other
words, you may think you're getting a stopband that's zero everywhere,
but it's only zero at the points represented by the bin, not the full
width of the bin.

An easy experiment reveals the issue. Apply your zeroing technique
to a data sequence and take the inverse transform. Now, zero pad
that sequence so that you get k more samples per bin, enough to see
what happens between the bins of the original DFT. Take the
transform of the zero-padded sequence and compare it to your
zeroed-stopband frequency response. There will still be zeros at the
spots where you put zeros, but there will k-1 non-zero frequency
samples in between them, and the ones close to the transition region
are typically not very well behaved. This is why this technique is
not widely used; you give up control of what happens between the
frequency samples. It's predictable, it's just not very good for many
applications.

Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org
Reply With Quote
  #6 (permalink)  
Old 09-25-2004, 12:24 PM
Richard Owlett
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?

Eric Jacobsen wrote:
> On Fri, 24 Sep 2004 17:38:57 -0500, Richard Owlett
> <[email protected]> wrote:
>
>
>>glen herrmannsfeldt wrote:
>>
>>
>>>
>>>Richard Owlett wrote:
>>>
>>>
>>>>This is intentionally "dumb" question.
>>>>I suspect a good answer will illuminate a fallacy in my thinking.
>>>
>>>
>>>>assume a real input
>>>>perform FFT
>>>>set all bins to 0 that are outside pass band
>>>>perform suitably scaled IFFT
>>>
>>>
>>>>What's wrong with this picture?
>>>
>>>
>>>It is as sharp as the number of points in the transform.
>>>(The frequency resolution is 1/(total length of transform).)
>>>
>>>You need an infinite number of points for an infinitely
>>>sharp cutoff.
>>>
>>>-- glen
>>>

>>
>>Caution: I'm learning DSP by asking questions on this group
>>
>>I had gotten the impression there was another problem other than what
>>may be considered "resolution issues'.

>
>
> You can implement a filter that way, and sometimes it's a fine thing
> to do. Another thread here mentioned how this was used successfully
> in some data processing, but subsequent use of a FIR with a sharp (but
> not infinite) cutoff worked better.
>
> The typical problem with the zero-ing-the-DFT trick is that the zeros
> are only really valid at exactly the frequency sampling points and the
> filter will have non-zero magnitude response between them. In other
> words, you may think you're getting a stopband that's zero everywhere,
> but it's only zero at the points represented by the bin, not the full
> width of the bin.
>


In my case I'm starting with speech recorded on CD under studio
conditions. I assume the signal was suitably low pass filtered before
sampling. I will playback the filtered signal using the original sample
rate. Would that make the effect moot or not?

I doubt I'll would do a true "brick wall" but it is a worst case limit
of what I might do.

Now off to do some Scilab experiments.





> An easy experiment reveals the issue. Apply your zeroing technique
> to a data sequence and take the inverse transform. Now, zero pad
> that sequence so that you get k more samples per bin, enough to see
> what happens between the bins of the original DFT. Take the
> transform of the zero-padded sequence and compare it to your
> zeroed-stopband frequency response. There will still be zeros at the
> spots where you put zeros, but there will k-1 non-zero frequency
> samples in between them, and the ones close to the transition region
> are typically not very well behaved. This is why this technique is
> not widely used; you give up control of what happens between the
> frequency samples. It's predictable, it's just not very good for many
> applications.
>
> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org

Reply With Quote
  #7 (permalink)  
Old 09-25-2004, 01:22 PM
jim
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?



Richard Owlett wrote:

> >
> > The typical problem with the zero-ing-the-DFT trick is that the zeros
> > are only really valid at exactly the frequency sampling points and the
> > filter will have non-zero magnitude response between them. In other
> > words, you may think you're getting a stopband that's zero everywhere,
> > but it's only zero at the points represented by the bin, not the full
> > width of the bin.
> >

>
> In my case I'm starting with speech recorded on CD under studio
> conditions. I assume the signal was suitably low pass filtered before
> sampling. I will playback the filtered signal using the original sample
> rate. Would that make the effect moot or not?
>
> I doubt I'll would do a true "brick wall" but it is a worst case limit
> of what I might do.


A little while ago you were discussing frequency domain filtering using
overlap add method. To do that you need a filter with a impulse
response of about half the FFT block length. It's impossible for such a
filter when transformed to the frequency domain to end up being pure 1's
and 0's.
Your so called brick wall filter (all 1's and 0's) would not work with
that filtering method because the impulse response of your filter will
be just as long as the FFT/IFFT block.

-jim


-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 100,000 Newsgroups - 19 Different Servers! =-----
Reply With Quote
  #8 (permalink)  
Old 09-25-2004, 04:25 PM
Richard Owlett
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?

jim wrote:
>
> Richard Owlett wrote:
>
>
>>>The typical problem with the zero-ing-the-DFT trick is that the zeros
>>>are only really valid at exactly the frequency sampling points and the
>>>filter will have non-zero magnitude response between them. In other
>>>words, you may think you're getting a stopband that's zero everywhere,
>>>but it's only zero at the points represented by the bin, not the full
>>>width of the bin.
>>>

>>
>>In my case I'm starting with speech recorded on CD under studio
>>conditions. I assume the signal was suitably low pass filtered before
>>sampling. I will playback the filtered signal using the original sample
>>rate. Would that make the effect moot or not?
>>
>>I doubt I'll would do a true "brick wall" but it is a worst case limit
>>of what I might do.

>
>
> A little while ago you were discussing frequency domain filtering using
> overlap add method. To do that you need a filter with a impulse
> response of about half the FFT block length. It's impossible for such a
> filter when transformed to the frequency domain to end up being pure 1's
> and 0's.
> Your so called brick wall filter (all 1's and 0's) would not work with
> that filtering method because the impulse response of your filter will
> be just as long as the FFT/IFFT block.
>
> -jim
>


I think I've missed something fundamental or applying procedures
inappropriately.

I understood that when processing data longer than the width of one
block of data I understood the procedure to be

1. apply a window function such as Hanning etc to avoid leakage between
FFT bins.
2. perform FFT
3. manipulate data as desired in frequency domain
4. perform suitably scaled IFFT
5. take the middle 1/3 ( for example ) of the new time domain data and
append it to existing output stream.
6. shift the input block by 1/3 it's width
7. repeat above until end of data

I my application "step 3" would be a point by point multiplication of a
function in the frequency domain.

I appreciate the patience of one and all.

Reply With Quote
  #9 (permalink)  
Old 09-25-2004, 05:51 PM
jim
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?



Richard Owlett wrote:
>
>
> I think I've missed something fundamental or applying procedures
> inappropriately.
>


maybe, have you grasp the concept of duality or transform pairs? That
is, an action in one domain (time or frequency) is equivalent to doing
something else in the opposite domain. There are bunches of these
dualities - knowing what they are will help you understand DFT<->IFFT.

> I understood that when processing data longer than the width of one
> block of data I understood the procedure to be
>
> 1. apply a window function such as Hanning etc to avoid leakage between
> FFT bins.


Multiplying by a window function in time domain is equivalent to
convolution in frequency domain, that's one of those dualities you need
to know. Why or whether you apply a window function in time domain is up
to you.

> 2. perform FFT
> 3. manipulate data as desired in frequency domain


Multiplying by a window function in frequency domain is equivalent to
convolution in time domain (the other half of the same duality).
Generally, you would be doing this because it takes less time than
convolving directly in the time domain (if the convolution kernel is
large). So all your doing is applying a convolution filter in the time
domain. The reason for applying this filter I have no idea.

> 4. perform suitably scaled IFFT
> 5. take the middle 1/3 ( for example ) of the new time domain data and
> append it to existing output stream.


If the valid portion of your FFT->IFFT is 1/3 block then your time
domain convolution kernel can be no longer than 2/3 of FFT block in
length. My point was that the FFT of a kernel of that length can't be
"brick wall like" frequency domain window function, because such a
function will have a corresponding non-zero time domain length that is
too wide for what you are doing. You need to find a frequency domain
function that will work. Usually that's done by creating the appropiate
time domain kernel and padding with zeroes and taking the FFT of that.
So the answer to your original question is no. That brick wall like
function you envision will not work for what you are doing.

-jim

> 6. shift the input block by 1/3 it's width
> 7. repeat above until end of data
>
> I my application "step 3" would be a point by point multiplication of a
> function in the frequency domain.
>
> I appreciate the patience of one and all.



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 100,000 Newsgroups - 19 Different Servers! =-----
Reply With Quote
  #10 (permalink)  
Old 09-26-2004, 11:31 AM
Rune Allnor
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?

Richard Owlett <[email protected]> wrote in message news:<[email protected]>...
> This is intentionally "dumb" question.
> I suspect a good answer will illuminate a fallacy in my thinking.
>
> assume a real input
> perform FFT
> set all bins to 0 that are outside pass band
> perform suitably scaled IFFT
>
> What's wrong with this picture?


It's nothing inherently wrong. The problem is that the filter is only
partially specified. A matlab exercise might iluminate the problem.
I'll plot an ideal brick-wall magnitude response, design a frequency-
domain filter from that, and plot the true frequency response for
the realized filter.

The exercise is, unfortunately, in matlabese.

%%%%%%%%%%%%% Begin matlab script %%%%%%%%%%%%%%%%%%%

clear % Clear workspace
clf % Clear current figure

fc= 0.25; % Cut-off frequency (fs = 1)
N = 32; % Number of taps in FIR filter.
Nfft=1024; % Number of points in interpolated spectrum

% Plot Brick-wall filter, ideal response in blue color, thick line
plot([0 fc, fc, 1-fc,1-fc,1],[1 1 0 0 1 1],'b','linewidth',3')
% Adjust axes of plot
axis([0 1 0 1.5])

% Specify that further plots should go on top of the current one
hold on

% Specify magnitude spectrum for N-tap 'brick-wall' filter
fv=[0:N-1]/N;
Hbw=zeros(N,1);
idx=find((fv<=fc)|(fv>=1-fc));
if ~isempty(idx)
Hbw(idx)=ones(length(idx),1);
end

% Plot samples on top of ideal response as large, red x'es.
plot(fv,Hbw,'xr','markersize',14,'linewidth',2)

% Compute interpolated frequency spectrum: Perform IFFT
% to find impulse response N-tap 'brick-wall' filter,
% re-arrange coefficients, then compute interpolated DFT
% by zero-padding impulse response and computing DFT.

hbw=ifft(Hbw);
% Rearrange coefficients in impulse response. Matlab users
% should use the function FFTSHIFT here.
hbw=[hbw(N/2+1:N);hbw(1:N/2)];

% Plot interpolated spectrum in green
fvzp=[0:Nfft-1]/Nfft;
plot(fvzp,abs(fft(hbw,Nfft)),'g','linewidth',2)

% Bring figure to the foreground
figure(gcf)

%%%%%% End matlab script %%%%%%%%%%%%%%%%%%%%%%%%%

When you get this to run, you will see that the FIR filter response
(the green line) coincides with the ideal brick-wall response (the blue
line) only at a finite number of pints (the red x'es). Since you can
only specify the filter response at a finite number of points, you
can get as close to the ideal response as you like (except for the Gibbs
phenomenon), but you can't get all the way, and the actual response
deviates from the required response in the intervals between
specifications.

Rune
Reply With Quote
  #11 (permalink)  
Old 09-26-2004, 11:41 AM
Rune Allnor
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?

[email protected] (Eric Jacobsen) wrote in message news:<[email protected]>...
> On Fri, 24 Sep 2004 17:38:57 -0500, Richard Owlett
> <[email protected]> wrote:
>
> >glen herrmannsfeldt wrote:
> >
> >>
> >>
> >> Richard Owlett wrote:
> >>
> >>> This is intentionally "dumb" question.
> >>> I suspect a good answer will illuminate a fallacy in my thinking.
> >>
> >>
> >>> assume a real input
> >>> perform FFT
> >>> set all bins to 0 that are outside pass band
> >>> perform suitably scaled IFFT
> >>
> >>
> >>> What's wrong with this picture?
> >>
> >>
> >> It is as sharp as the number of points in the transform.
> >> (The frequency resolution is 1/(total length of transform).)
> >>
> >> You need an infinite number of points for an infinitely
> >> sharp cutoff.
> >>
> >> -- glen
> >>

> >
> >Caution: I'm learning DSP by asking questions on this group
> >
> >I had gotten the impression there was another problem other than what
> >may be considered "resolution issues'.

>
> You can implement a filter that way, and sometimes it's a fine thing
> to do. Another thread here mentioned how this was used successfully
> in some data processing, but subsequent use of a FIR with a sharp (but
> not infinite) cutoff worked better.


Well, there are two problems with 'brick wall' filters. First, the
frequency responses are determined only at a finite number of
frequencies, with the magnitude response left unspecified in between.
Second, the transition band is exactly one frequency bin wide, which
is un-necessary sharp in most situations, and causes extensive ringing
in time domain.

Whaich is the reason why one started using windowed FIR filters in the
first place: The filter lengths are specified in terms of the allowable
transition bands, and ripple is specified over the full band.

Rune
Reply With Quote
  #12 (permalink)  
Old 09-26-2004, 11:59 PM
glen herrmannsfeldt
Guest
 
Posts: n/a
Default Re: Is "brick wall" filter realizable?

Richard Owlett wrote:

(snip)

> In my case I'm starting with speech recorded on CD under studio
> conditions. I assume the signal was suitably low pass filtered before
> sampling. I will playback the filtered signal using the original sample
> rate. Would that make the effect moot or not?
>
> I doubt I'll would do a true "brick wall" but it is a worst case limit
> of what I might do.


I have wondered in past discussions how long it takes to do
an FFT of a whole CD. The filter can't be sharper than
1/(length of data), but for a 60 minute CD that is about
0.0003Hz, close enough to brick wall for most of us.

-- glen

Reply With Quote
  #13 (permalink)  
Old 09-27-2004, 10:35 PM
Richard Owlett
Guest
 
Posts: n/a
Default Thanks to all was[Re: Is "brick wall" filter realizable?]

Richard Owlett wrote:

> This is intentionally "dumb" question.
> I suspect a good answer will illuminate a fallacy in my thinking.
>
> assume a real input
> perform FFT
> set all bins to 0 that are outside pass band
> perform suitably scaled IFFT
>
> What's wrong with this picture?


Thank you one and all.
I've learned at least one thing.

If wandering lost, ask about "degenerate" (spelling?) case.
Responses will point out fallacious logic.

Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
As "Nyquist" is to "sample rate" "????" is to "sample period/duration/width/?"? Richard Owlett DSP 16 09-22-2004 09:10 PM
"Les Cargill [[email protected]]" tries to seperate "FM" from "digital" Radium DSP 0 12-31-2003 06:31 AM
Warning: FlipFlops/Latches "/"ADR_reg<0>"/Q_reg" are set/reset by "". (FPGA-GSRMAP-14) Martin Bammer VHDL 0 11-17-2003 11:28 PM
Nonlinear brick wall filters Matt Timmermans DSP 6 10-02-2003 12:01 AM
Adaptive filter code - "Free ASPT" Andrew N Rimell DSP 0 08-11-2003 11:56 AM


All times are GMT +1. The time now is 05:48 AM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved