Simple question - non-linear filters

I am looking for information on non-linear filters that generate outputs
similar to this:

y[n] = x[n]/x[n-1]

or

y[n] = x[n]*x[n-1]

Do these types of filters have specific names so I can know what to google
for? How can I find their frequency response?

On Jul 11, 11:52 am, "ac123" <d...@myallit.com> wrote:
> I am looking for information on non-linear filters that generate outputs
> similar to this:
>
> y[n] = x[n]/x[n-1]
>
> or
>
> y[n] = x[n]*x[n-1]
>
> Do these types of filters have specific names so I can know what to google
> for? How can I find their frequency response?

You'll find that there's little information out there on analysis of
nonlinear filters, mostly because there's no simple framework to
analyze them with. Frequency response is somewhat meaningless for
nonlinear filters. Impulse response is used to characterize linear
time-invariant systems because you can express any input signal as a
sum of scaled and shifted impulses (I'm talking discrete-time filters
and Kronecker deltas here to avoid the mathematical precision required
when talking about continuous-time systems or Dirac deltas), allowing
you to express the system output via a convolution sum. Frequency
response is used because sinusoids are eigenfunctions of linear
systems; for each tone that you put in, you get one out that is a
scaled and shifted version of the original. This allows you to express
the output of the system in the frequency domain via multiplication of
the input's spectrum by the system frequency response.

These basic tools, which most common "DSP" tasks are based upon, just
don't work in general for nonlinear filters. Sinusoids are not
eigenfunctions of a nonlinear system in general. Impulse response also
doesn't necessarily give you anything useful in the nonlinear case.
So, you'll find that nonlinear techniques are much more rarely used
than their linear counterparts. There is a wealth of information and
techniques that have been developed for bending linear systems to your
will. For a very specific application, you might be able to devise a
nonlinear technique that yields improved performance, but there's no
systematic method for developing such a filter.

More specifically to your question about the two input-output
relations you gave, I'm not aware of any uses or names for them. A
"sliding product" or "sliding ratio", maybe?

Jason

ac123 wrote:
> I am looking for information on non-linear filters that generate outputs
> similar to this:
> 
> y[n] = x[n]/x[n-1]
> 
> or
> 
> y[n] = x[n]*x[n-1]
> 
> Do these types of filters have specific names so I can know what to google
> for? How can I find their frequency response?
> 
> 
"Frequency response" is, in general, meaningless in the context of a 
nonlinear system.  If you can linearize the system model into a 
reasonable approximation of the real thing then "frequency response" 
means something, but only to the degree that your approximation is valid.

The systems above _are_ homologous to linear systems if you take the 
logarithm of both sides.  Define ly = log(y) and lx = log(x).  Then your 
systems become

ly(n) = lx(n) - lx(n-1)

and

ly(n) = lx(n) + lx(n-1)

You should be able to use the above relationships to predict the 
behavior of the logarithms of your variables using linear system 
analysis (including frequency response) and thus the behavior of the 
variables themselves.  (And no, I'm not forgetting to restrict the 
analysis to positive variables -- if you use the complex log it should 
work with the equations as written).

You could extend this to multiplication by arbitrary exponents of the 
variables.  (Although with non-integer exponents you _would_ have to 
restrict the variables to positive values, unless you didn't mind having 
complex values flying around your system).

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" gives you just what it says.
See details at http://www.wescottdesign.com/actfes/actfes.html

On Jul 11, 1:46&#4294967295;pm, Tim Wescott <t...@seemywebsite.com> wrote:
> ac123 wrote:
> > I am looking for information on non-linear filters that generate outputs
> > similar to this:
>
> > y[n] = x[n]/x[n-1]
>
> > or
>
> > y[n] = x[n]*x[n-1]
>
> > Do these types of filters have specific names so I can know what to google
> > for? How can I find their frequency response?
>
> "Frequency response" is, in general, meaningless in the context of a
> nonlinear system. &#4294967295;If you can linearize the system model into a
> reasonable approximation of the real thing then "frequency response"
> means something, but only to the degree that your approximation is valid.
>
> The systems above _are_ homologous to linear systems if you take the
> logarithm of both sides. &#4294967295;Define ly = log(y) and lx = log(x). &#4294967295;Then your
> systems become
>
> ly(n) = lx(n) - lx(n-1)
>
> and
>
> ly(n) = lx(n) + lx(n-1)
>
> You should be able to use the above relationships to predict the
> behavior of the logarithms of your variables using linear system
> analysis (including frequency response) and thus the behavior of the
> variables themselves. &#4294967295;(And no, I'm not forgetting to restrict the
> analysis to positive variables -- if you use the complex log it should
> work with the equations as written).
>
> You could extend this to multiplication by arbitrary exponents of the
> variables. &#4294967295;(Although with non-integer exponents you _would_ have to
> restrict the variables to positive values, unless you didn't mind having
> complex values flying around your system).
>
> --
>
> Tim Wescott
> Wescott Design Serviceshttp://www.wescottdesign.com
>
> Do you need to implement control loops in software?
> "Applied Control Theory for Embedded Systems" gives you just what it says.
> See details athttp://www.wescottdesign.com/actfes/actfes.html

This is related to so-called "log-domain filters", which are
externally linear but internally non-linear; a search of google
scholar will turn up hundreds of articles. Most are continuous-time
but I believe Tsividis covered the discrete-time version.

Another thing this reminds me of is modeling (and possibly cancelling)
intersymbol interference in a 1-bit stream. If x(n) is restricted to
values +1 and -1, then x(n)*x(n-1) is only -1 when a transition has
ocurred, and with intersymbol interference, the error is all in the
transitions.

Thanks for all the helpful responses, I will look into log-domain filters,
I think it's what I'm after.

ac123 wrote:
> I am looking for information on non-linear filters that generate outputs
> similar to this:
>
> y[n] = x[n]/x[n-1]
>
> or
>
> y[n] = x[n]*x[n-1]
>
> Do these types of filters have specific names so I can know what to google
> for? How can I find their frequency response?

Non-linear difference equations can be very interesting. I believe our
own Richard Dobson has written his thesis on this topic (http://
people.bath.ac.uk/masjpf/HK_poster.html), so perhaps he also has
something to say on this topic.

One interesting non-linear recursion that I once came up with is this:

y[n] = y[n-1] (2 - x[n] y[n-1]).

DSP riddle: what is the output y[n] in relation to the input x[n]?
Assume that the sequence x[n] lies in between 0 and 1. Hint: the
"filter" only works well for slowly varying input sequences x[n].

Regards,
Andor

Andor wrote:
> ac123 wrote:
>> I am looking for information on non-linear filters that generate outputs
>> similar to this:
>>
>> y[n] = x[n]/x[n-1]
>>
>> or
>>
>> y[n] = x[n]*x[n-1]
>>
>> Do these types of filters have specific names so I can know what to google
>> for? How can I find their frequency response?
> 
> Non-linear difference equations can be very interesting. I believe our
> own Richard Dobson has written his thesis on this topic (http://
> people.bath.ac.uk/masjpf/HK_poster.html), so perhaps he also has
> something to say on this topic.
> 

<blush>  Umm, hardly a thesis; just the first papers I ever published. 
Nice to know someone knows about them! I "developed"  the filter (and 
oscillator) using a vintage DOS version of Mathcad on a i386 PC, 
plotting waveforms and fiddling with things until I got some plausible 
patterns.

Something to say, well:

If "musical" audio results are sought, there will probably be an 
advantage in extending the delay, thus:

y[n] = x[n] * x[n-N]
where N may be quite large (could think of it as a wavelength 
parameter). Filling the initial delay space with something other than 
zeroes can lead to all sorts of things.

Otherwise, while the formula may give all sorts of "interesting" 
responses, they may all be bunched up near Nyquist (and probably in 
effect alias too). As a filter, it may benefit from a heavily 
band-limited input, at a level well below 0dBFS. These things may do all 
sorts of mischief to attack transients; kept sufficiently under control 
the effects may even be pleasant. I implemented my non-linear filter on 
an early ADI 21020 dsp development card, and with a bland monophonic 
pitched input, got interesting behaviour in that some notes were 
selectively highlighted, others less so - quite a "musical" result.

The filter described in that paper was implemented as a Csound opcode 
"nlfilt".



Richard Dobson

> One interesting non-linear recursion that I once came up with is this:
>
> y[n] = y[n-1] (2 - x[n] y[n-1]).
>
> DSP riddle: what is the output y[n] in relation to the input x[n]?
> Assume that the sequence x[n] lies in between 0 and 1. Hint: the
> "filter" only works well for slowly varying input sequences x[n].

You are all linear sissies :-)! I'm crossposting this to
sci.nonlinear, perhaps they have an idea.

On Jul 15, 8:33&#4294967295;am, Andor <andor.bari...@gmail.com> wrote:
> > One interesting non-linear recursion that I once came up with is this:
>
> > y[n] = y[n-1] (2 - x[n] y[n-1]).
>
> > DSP riddle: what is the output y[n] in relation to the input x[n]?
> > Assume that the sequence x[n] lies in between 0 and 1. Hint: the
> > "filter" only works well for slowly varying input sequences x[n].
>
> You are all linear sissies :-)! I'm crossposting this to
> sci.nonlinear, perhaps they have an idea.

Andor,

Your answer is that this implements the reciprocal function.

y[n] may approach/converge to the reciprocal of x[n] for sufficiently
slowly varying signals and suitable initial conditions on y[n].
Definitely don't want ever want y[n] =0 (for any n) for it to work.

It can also work for some values of x[n] >1.

This is not a complete analysis, but I think it answers the question.

Dirk

Dirk wrote:
> On Jul 15, 8:33�am, Andor wrote:
>
> > > One interesting non-linear recursion that I once came up with is this:
>
> > > y[n] = y[n-1] (2 - x[n] y[n-1]).
>
> > > DSP riddle: what is the output y[n] in relation to the input x[n]?
> > > Assume that the sequence x[n] lies in between 0 and 1. Hint: the
> > > "filter" only works well for slowly varying input sequences x[n].
>
> > You are all linear sissies :-)! I'm crossposting this to
> > sci.nonlinear, perhaps they have an idea.
>
> Andor,
>
> Your answer is that this implements the reciprocal function.

Aha, Dirk is a man with DSP in his heart! The answer is correct,
although not the first one. About one hour ago I recieved the first
correct entry off the list.

>
> y[n] may approach/converge to the reciprocal of x[n] for sufficiently
> slowly varying signals and suitable initial conditions on y[n].
> Definitely don't want ever want y[n] =0 (for any n) for it to work.
>
> It can also work for some values of x[n] >1.

Yes, indeed. However, when I tested this recursion I found that for
some sequences it would blow skyhigh. As you say, it works if x[n]
"varies slowly".

>
> This is not a complete analysis, but I think it answers the question.

The question of its stability is interesting. This seems to depend on
the frequency content of the input sequence x[n]. I never did a
thorough analysis myself because I never got to the point where the
filter would have been useful to me (modern DSPs have a reciprocal
instruction for seeding a Newton iteration algorithm that works more
accurate, stable and faster).

Regards,
Andor