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?

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

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'.

"Richard Owlett" <rowlett@atlascomm.net> wrote in message 
news:10l95qaraa69vab@corp.supernews.com...
> 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 

On Fri, 24 Sep 2004 17:38:57 -0500, Richard Owlett
<rowlett@atlascomm.net> 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

Eric Jacobsen wrote:
> On Fri, 24 Sep 2004 17:38:57 -0500, Richard Owlett
> <rowlett@atlascomm.net> 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

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! =-----

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.

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! =-----

Richard Owlett <rowlett@atlascomm.net> wrote in message news:<10l95qaraa69vab@corp.supernews.com>...
> 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