FPGA Central

Simple but hard question::

Given a stable filter h[n]<-DFT->H[k] with less than unity Gain (defn:
DFT coefficients are <= 1), what is the bound on output to a input
bounded by Bx in discrete time domain. (I am talking about DFT pairs
only)

Please don't tell me that it is Bx. THAT IS WRONG.

The bound on output for a general stable filter is
sc_mh * Bx

where
sc_mh = sigma(complex_mod(h[n]),n,-infinity,infinity)

where
sigma(a,b,c,d) means sum 'a' with variable 'b' varying from 'c' to
'd'.

So the question boils down to finding a bound on 'sc_mh' given a
causal h[n] with all H[k]'s <= 1

The best bound I have got till now is sqrt(N) where the DFT is taken
over N points.

PLEASE HELP, I am getting mad over this question

[email protected] (Nitesh) writes:

> Simple but hard question::
>
> Given a stable filter h[n]<-DFT->H[k] with less than unity Gain (defn:
> DFT coefficients are <= 1), what is the bound on output to a input
> bounded by Bx in discrete time domain. (I am talking about DFT pairs
> only)
>
> Please don't tell me that it is Bx. THAT IS WRONG.
>
> The bound on output for a general stable filter is
> sc_mh * Bx
>
> where
> sc_mh = sigma(complex_mod(h[n]),n,-infinity,infinity)
>
> where
> sigma(a,b,c,d) means sum 'a' with variable 'b' varying from 'c' to
> 'd'.
>
> So the question boils down to finding a bound on 'sc_mh' given a
> causal h[n] with all H[k]'s <= 1
>
> The best bound I have got till now is sqrt(N) where the DFT is taken
> over N points.
>
> PLEASE HELP, I am getting mad over this question

Hi Nitesh,

Your initial bound seems like it's in the right direction. It
was shown how a sinc filter can produce an unbounded output with
a bounded input here:

http://www.google.com/groups?q=serie...eee.org&rnum=3

--Randy


PS: Is this the Nitesh I know? (Nitesh Soni?)
--
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
[email protected], 919-472-1124

[email protected] (Nitesh) wrote in message news:<[email protected] m>...
> Simple but hard question::
>
> Given a stable filter h[n]<-DFT->H[k] with less than unity Gain (defn:
> DFT coefficients are <= 1), what is the bound on output to a input
> bounded by Bx in discrete time domain. (I am talking about DFT pairs
> only)
>
> Please don't tell me that it is Bx. THAT IS WRONG.
>
> The bound on output for a general stable filter is
> sc_mh * Bx
>
> where
> sc_mh = sigma(complex_mod(h[n]),n,-infinity,infinity)
>
> where
> sigma(a,b,c,d) means sum 'a' with variable 'b' varying from 'c' to
> 'd'.
>
> So the question boils down to finding a bound on 'sc_mh' given a
> causal h[n] with all H[k]'s <= 1
>
> The best bound I have got till now is sqrt(N) where the DFT is taken
> over N points.
>
> PLEASE HELP, I am getting mad over this question

Unfortunately, that is the best you can do. You can verify this by
constructing examples where your upper bound is met.

One example:

input signal:

Bx, -Bx, Bx, -Bx, Bx, -Bx ...

causal filter:

1/sqrt(N), -1/sqrt(N), 1/sqrt(N), -1/sqrt(N), ...,

Then the DFT coefficients are all zero except one which has magnitude
1.

More can be done if you have some lower limits on magnitudes of the
DFT coefficients.

> > So the question boils down to finding a bound on 'sc_mh' given a
> > causal h[n] with all H[k]'s <= 1. The best bound I have got
> > till now is sqrt(N)
>
> Unfortunately, that is the best you can do. You can verify this by
> constructing examples where your upper bound is met.
>
> One example:
> input signal:
> Bx, -Bx, Bx, -Bx, Bx, -Bx ...
> causal filter:
> 1/sqrt(N), -1/sqrt(N), 1/sqrt(N), -1/sqrt(N), ...,
>
> Then the DFT coefficients are all zero except one which has magnitude
> 1.

Hi Mahesh!

Thanks, but I have a sincere feeling that sqrt(N) is a loose bound.
The problem with your example is that H[k] = sqrt(N) at N/2 (N assumed
to be even). So it is not a unity gain filter anymore....

In fact it can be very easily proved by Parseval's Theorem and some
logic that to reach the bound of sqrt(N) you have no choice but to
have a filter with all
|h[n]| = 1/sqrt(N) and all |H[k]| = 1 (both have length N).

From the DFT pair equations you will get 2N REAL equations in 2N REAL
variables which satisfy the above criteria. To prove that sqrt(N) is a
loose bound we have to show there is no solution to those equations.
(Not very easy)... May be it is easy to find solution using computer
program because the variables move in a [0, 2pi) space along all 2N
dimensions.

But I have a strong feeling that the above method to prove anything
(tight or loose) is too complicated, but it does indicates (without
proof ofcourse) that sqrt(N) is a loose bound.

Hope that someone else looses his/her nights sleep over it

)
Nitesh

Randy Yates <[email protected]> wrote in message news:<[email protected]>...
> [email protected] (Nitesh) writes:
>
> > Simple but hard question::
> >
> > Given a stable filter h[n]<-DFT->H[k] with less than unity Gain (defn:
> > DFT coefficients are <= 1), what is the bound on output to a input
> > bounded by Bx in discrete time domain. (I am talking about DFT pairs
> > only)
> Hi Nitesh,
>
> Your initial bound seems like it's in the right direction. It
> was shown how a sinc filter can produce an unbounded output with
> a bounded input here:
>
> http://www.google.com/groups?q=serie...eee.org&rnum=3
>
> --Randy
> PS: Is this the Nitesh I know? (Nitesh Soni?)

Thanks Randy!

I am not that Nitesh I am Nitesh Bhandari

[email protected] (Nitesh) wrote in message news:<[email protected] com>...
> > > So the question boils down to finding a bound on 'sc_mh' given a
> > > causal h[n] with all H[k]'s <= 1. The best bound I have got
> > > till now is sqrt(N)
> >
> > Unfortunately, that is the best you can do. You can verify this by
> > constructing examples where your upper bound is met.
> >
> > One example:
> > input signal:
> > Bx, -Bx, Bx, -Bx, Bx, -Bx ...
> > causal filter:
> > 1/sqrt(N), -1/sqrt(N), 1/sqrt(N), -1/sqrt(N), ...,
> >
> > Then the DFT coefficients are all zero except one which has magnitude
> > 1.
>
> Hi Mahesh!
>
> Thanks, but I have a sincere feeling that sqrt(N) is a loose bound.
> The problem with your example is that H[k] = sqrt(N) at N/2 (N assumed
> to be even). So it is not a unity gain filter anymore....
>
> In fact it can be very easily proved by Parseval's Theorem and some
> logic that to reach the bound of sqrt(N) you have no choice but to
> have a filter with all
> |h[n]| = 1/sqrt(N) and all |H[k]| = 1 (both have length N).
>
> From the DFT pair equations you will get 2N REAL equations in 2N REAL
> variables which satisfy the above criteria. To prove that sqrt(N) is a
> loose bound we have to show there is no solution to those equations.
> (Not very easy)... May be it is easy to find solution using computer
> program because the variables move in a [0, 2pi) space along all 2N
> dimensions.
>
> But I have a strong feeling that the above method to prove anything
> (tight or loose) is too complicated, but it does indicates (without
> proof ofcourse) that sqrt(N) is a loose bound.
>
> Hope that someone else looses his/her nights sleep over it
>
> )
> Nitesh

Nitesh, it IS a unity gain filter.

Recall DFT(k) = 1/sqrt(N) \sum_{n=1}^N h(n) exp(-j*2*pi*k*n/N).

So, the coefficient indeed works out to 1.

I think you are using the following definition of DFT

DFT(k) = \sum_{n=1}^N h(n) exp(-j*2*pi*k*n/N)

in which case your upper bound sc_mh works out to 1 rather than
sqrt(N) because inverse DFT in that case would be defined as

h(n) = 1/N \sum_{k=1}^N DFT(k) exp(j*2*pi(k*n/N).

Mahesh

> Nitesh, it IS a unity gain filter.
> Recall DFT(k) = 1/sqrt(N) \sum_{n=1}^N h(n) exp(-j*2*pi*k*n/N).
> So, the coefficient indeed works out to 1.
> I think you are using the following definition of DFT
> DFT(k) = \sum_{n=1}^N h(n) exp(-j*2*pi*k*n/N)
> in which case your upper bound sc_mh works out to 1 rather than
> sqrt(N) because inverse DFT in that case would be defined as
> h(n) = 1/N \sum_{k=1}^N DFT(k) exp(j*2*pi(k*n/N).
> Mahesh

Oops! Sorry for that definition mismatch.
In later posts we will assume the following definition of DFT, where
DFT(k) = \sum_{n=1}^N h(n) exp(-j*2*pi*k*n/N). This definition because
this is what it is in Matlab

Here the bound on sc_mh is NOT 1 (as I anyway said in my first post,
but without the definition of DFT).

I will give you an example where H[k]'s <=1 but sc_mh >=1.

Take h[n] = [1 -0.9 -0.8 -0.7 -0.6 -0.5 -0.4 -0.3 -.2 -.1]/(3.5)
Here max(complex_abs(H[k]))=1 for k=0
and sc_mh = 1.5714

Now sc_mh is a tight bound on ratio of output to input...

To work on this h[n] on your definition of DFT multiply h[n] by
sqrt(10) and take a 10 point DFT. With your defnition of DFT the best
bound I have on sc_mh is "N".

I have examples where sc_mh even exceeds 2, but I have a feeling that
sqrt(N) is a loose bound

Regards
Nitesh

[email protected] (Nitesh) wrote in message news:<[email protected] com>...
> > Nitesh, it IS a unity gain filter.
> > Recall DFT(k) = 1/sqrt(N) \sum_{n=1}^N h(n) exp(-j*2*pi*k*n/N).
> > So, the coefficient indeed works out to 1.
> > I think you are using the following definition of DFT
> > DFT(k) = \sum_{n=1}^N h(n) exp(-j*2*pi*k*n/N)
> > in which case your upper bound sc_mh works out to 1 rather than
> > sqrt(N) because inverse DFT in that case would be defined as
> > h(n) = 1/N \sum_{k=1}^N DFT(k) exp(j*2*pi(k*n/N).
> > Mahesh
>
> Oops! Sorry for that definition mismatch.
> In later posts we will assume the following definition of DFT, where
> DFT(k) = \sum_{n=1}^N h(n) exp(-j*2*pi*k*n/N). This definition because
> this is what it is in Matlab
>
> Here the bound on sc_mh is NOT 1 (as I anyway said in my first post,
> but without the definition of DFT).
>
> I will give you an example where H[k]'s <=1 but sc_mh >=1.
>
> Take h[n] = [1 -0.9 -0.8 -0.7 -0.6 -0.5 -0.4 -0.3 -.2 -.1]/(3.5)
> Here max(complex_abs(H[k]))=1 for k=0
> and sc_mh = 1.5714
>
> Now sc_mh is a tight bound on ratio of output to input...
>
> To work on this h[n] on your definition of DFT multiply h[n] by
> sqrt(10) and take a 10 point DFT. With your defnition of DFT the best
> bound I have on sc_mh is "N".
>
> I have examples where sc_mh even exceeds 2, but I have a feeling that
> sqrt(N) is a loose bound
>
> Regards
> Nitesh

Got it! Let me see if I can come up with something useful.

Staying alive