Next  |  Prev  |  Top  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search


Nonlinear, Time-Varying DWNs

The DWN paradigm is highly useful for constructing time-varying nonlinear digital filters which are guaranteed stable in the Lyapunov sense [59,25]. Lyapunov stability analysis involves finding a positive-definite ``Lyapunov function'' (which is like a norm defined on the filter state), which decreases each time step (given zero inputs) in the presence of linear or nonlinear computations (such as numerical round-off). Whenever each state variable (delay element) in a filter computation has a physical interpretation as an independent wave variable, a Lyapunov function can be defined simply as the sum of wave energies associated with the state variables. By choosing the scattering-junction round-off rules to be passive (e.g., by using magnitude truncation), the total stored energy in the filter decreases or remains the same relative to an infinite-precision implementation. As long as the infinite-precision filter is asymptotically stable, the quantized filter must be also. Thus, the total stored energy in any ``physical'' digital filter is precisely what is needed for a Lyapunov function.

Since many ladder, lattice, and wave digital filters are equivalent to DWNs, possibly after some delay manipulations [51,92,93,75], it is clear that DWNs can be used to realize a wide class of transfer functions. In particular, every filter transfer function can be realized as a linear combination of DWNs (in a manner analogous to using ``tap parameters'' on a ladder or lattice filter [57,12]), and linear combinations are well behaved in the presence of nonlinearities and time-varying parameters.

In practice, Lyapunov stability in a DWN is normally guaranteed by ensuring that wave-variables are never amplified by nonlinear operations or time-varying gains. For example, magnitude truncation on each output of an extended-precision scattering junction suffices to ensure passivity. Non-amplifying nonlinearities and varying gains are sufficient for passivity but sometimes too dissipative, especially in waveguide mesh applications [122]. A more refined rule is obtained by summing rounded-off energy (or an approximation to it) in an accumulator and changing the direction of rounding so as to servo the cumulative energy error to zero [93].

In the normalized case, the energy associated with each signal sample in a DWN is given by the square of that sample,8 so the total energy stored in a DWN is given simply as the sum of squares of all the samples contained in all the delay elements. In the unnormalized case, the energy of the $jth$ sample $x_{i,j}(n)$ in waveguide $i$, at time $n$, is given by $x^2_{i,j}(n)/R_i$, where $R_i$ is the wave impedance of the $i$th waveguide, and the total energy at time $n$ in the DWN can be written as

\begin{displaymath}
{\cal E}(n) = \sum_{i=1}^N \sum_{j=1}^{M_i} \frac{x^2_{i,j}(n)}{R_i}.
\end{displaymath}

where $M_i$ is the length of waveguide $i$ in samples. The DWN is stable in the presence of time-varying nonlinearities so long as ${\cal E}(n)$ (the Lyapunov functional for the DWN) is not increased when all inputs are zero, i.e.,

\begin{displaymath}
{\cal E}(n+1) \leq {\cal E}(n).
\end{displaymath}

Thus, magnitude truncation (rounding toward zero) at the output of all scattering junctions (with extended precision internal to each junction) preserves network stability, as does multiplication of any wave variable by a nonlinear or time-varying gain $g_{i,j}(n)$ not exceeding $1$ in magnitude, i.e., we only require $\vert g_{i,j}(n)\vert \leq 1$, for all $n$.

The above general result is applied in the following specific example (which is related to a waveguide sitar model):

Figure 4: A feedback loop containing a delay line, an allpass filter, and a time-varying nonlinearity.
\begin{figure}\centerline{\epsfxsize=150pt \epsfbox{figure/NonlinearAllpassLoop.eps}}\end{figure}

Theorem 2   A feedback loop containing an allpass filter $A(z)$ (assumed here to be exactly implemented), a delay line of any length $N>0$, and a time-varying nonlinearity $g[n,y(n)]$, as shown in Fig. 4, is stable in the Lyapunov sense if $\vert g[n,y(n)]\vert\leq 1$ for all $n$. If the initial stored energy is ${\cal E}(0)$, then the total energy remaining at time $n$ is given by

\begin{displaymath}
{\cal E}(n) = {\cal E}(0) - \sum_{i=1}^{n} \{1-g^2[i,y(i)]\}y^2(i)
\end{displaymath}

Proof: It suffices to show that (a) the arrangement of Fig. 4 is numerically equivalent to a DWN, and (b) $y(n)$ is a wave variable of the DWN corresponding to a unit impedance. Consider the redrawing of Fig. 4 as in Fig. 5. The delay line is broken into two halves to form a digital waveguide. (If the delay line length is odd, a sample of delay can be moved in cascade with the allpass filter.) It is well known that an arbitrary order $M$ allpass filter can be realized in the form of a digital ladder filter [57] with no ``taps,'' and it is straightforward to show that such a ladder filter can be manipulated into a digital waveguide filter by splitting each unit delay into two half-delays and commuting half of the half-delays around the ladder so that there is a half-delay between each scattering junction on both the upper and lower rails of the lattice [92].9 In this configuration, also shown in Fig. 5, the ladder filter is a DWN consisting of a cascade of digital waveguides, where the input and output of the allpass are the incoming and outgoing wave variables at the left of the leftmost waveguide of the allpass, and the rightmost waveguide is terminated on the right by a perfect reflection (infinite wave impedance, given pressure or force waves). Without loss of generality, we may choose the wave impedance of the bidirectional delay line to be $1$. The return signal $y(n)$ from the allpass is a wave variable at wave impedance 1, and its energy at time $n$ is $y^2(n)$. After scaling by the nonlinearity, its energy becomes $\vert g[n,y(n)]\vert^2y^2(n)$, and the energy lost each sample interval is therefore $\{1-g^2[n,y(n)]\}y^2(n)$, which is nonnegative, and the total energy lost is simply the sum over time of these per-sample losses.

Figure: A system equivalent to Fig. 4 containing a bidirectional delay line (digital waveguide) terminated reflectively on the left, terminated on the right by an allpass reflectance, and containing a time-varying nonlinearity on the return wave from the allpass.
\begin{figure}\centerline{\epsfxsize=6.5in \epsfbox{figure/NonlinearDWNLoop.eps}}\end{figure}

Corollary 1   All lossless nonlinearities or time-varying gains in the system of Fig. 4 can only select between the values $+1$ and $-1$.

Corollary 2   The amplitude of $y(n)$ is bounded by $y(n) \leq \sqrt{{\cal E}(n)}$.

Corollary 3   The signal $y(n)$ will approach zero asymptotically so long as $\vert g[n,y(n)]\vert\leq 1-\epsilon$ for some fixed $\epsilon>0$, irrespective of how $g$ may vary with time or as a function of $y$.

Of course, by keeping track of the energy gained or lost, as illustrated in the above theorem, and by controlling the gain/nonlinearity so that energy gained or lost is compensated at a later time, a wider class of nonlinear and/or time-varying systems may be defined which are lossless on average. An example is the exactly lossless (on average) DWN which servos round-off error energy to zero mentioned above. It is also possible to approximate lossless nonlinear behavior within the allpass filter [67,127].


Next  |  Prev  |  Top  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Download wgj.pdf

``Aspects of Digital Waveguide Networks for Acoustic Modeling Applications'', by Julius O. Smith III and Davide Rocchesso , December 19, 1997, Web published at http://ccrma.stanford.edu/~jos/wgj/.
Copyright © 2007-02-07 by Julius O. Smith III and Davide Rocchesso
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  [Automatic-links disclaimer]