It was shown in §C.4.3 that the digital waveguide (DW) model for the ideal vibrating string performs the same ``state transitions'' as the more standard finite-difference time-domain (FDTD) scheme (also known as the ``leapfrog'' recursion). This appendix, initially published in , further establishes that the solution spaces of the two schemes are isomorphic. That is, a linear, one-to-one transformation is derived which converts any point in the state-space of one scheme to a unique point in the other scheme. Since boundary conditions and initial values are more intuitively transparent in the DW formulation, the simple means of converting back and forth can be useful in initializing and constructing boundaries for FDTD simulations, as we will see. digital waveguide (DW) method has been used for many years to provide highly efficient algorithms for musical sound synthesis based on physical models [433,447,396]. For a much longer time, finite-difference time-domain (FDTD) schemes have been used to simulate more general situations, usually at higher cost [550,392,74,77,45,397]. In recent years, there has been interest in relating these methods to each other  and in combining them for more general simulations. For example, modular hybrid methods have been devised which interconnect DW and FDTD simulations by means of a KW converter [223,226]. The basic idea of the KW-converter adaptor is to convert the ``Kirchoff variables'' of the FDTD, such as string displacement, velocity, etc., to ``wave variables'' of the DW. The W variables are regarded as the traveling-wave components of the K variables. In this appendix, we present an alternative to the KW converter. Instead of converting K variables to W variables, or vice versa, in the time domain, conversion formulas are derived with respect to the current state as a function of spatial coordinates. As a result, it becomes simple to convert any instantaneous state configuration from FDTD to DW form, or vice versa. Thus, instead of providing the necessary time-domain filter to implement a KW converter converting traveling-wave components to physical displacement of a vibrating string, say, one may alternatively set the displacement variables instantaneously to the values corresponding to a given set of traveling-wave components in the string model. Another benefit of the formulation is an exact physical interpretation of arbitrary initial conditions and excitations in the K-variable FDTD method. Since the DW formulation is exact in principle (though bandlimited), while the FDTD is approximate, even in principle, it can be argued that the true physical interpretation of the FDTD method is that given by the DW method. Since both methods generate the same evolution of state from a common starting point, they may only differ in computational expense, numerical sensitivity, and in the details of supplying initial conditions and boundary conditions. The wave equation for the ideal vibrating string, reviewed in §C.1, can be written as
In the following two subsections, we briefly recall finite difference and digital waveguide models for the ideal vibrating string. C.2, we may use centered finite difference approximations (FDA) for the second-order partial derivatives in the wave equation to obtain a finite difference scheme for numerically integrating the ideal wave equation [481,311]:
where is the time sampling interval, and is a spatial sampling interval. Substituting the FDA into the wave equation, choosing , where is sound speed (normalized to below), and sampling at times and positions , we obtain the following explicit finite difference scheme for the string displacement:
where the sampling intervals and have been normalized to 1. To initialize the recursion at time , past values are needed for all (all points along the string) at time instants and . Then the string position may be computed for all by Eq.(E.3) for . This has been called the FDTD or leapfrog finite difference scheme .
digital waveguide formulation by sampling the traveling-wave solution to the wave equation. It is easily checked that the lossless 1D wave equation is solved by any string shape which travels to the left or right with speed . Denote right-going traveling waves in general by and left-going traveling waves by , where and are assumed twice-differentiable. Then, as is well known, the general class of solutions to the lossless, one-dimensional, second-order wave equation can be expressed as
Sampling these traveling-wave solutions yields
where a ``'' superscript denotes a ``right-going'' traveling-wave component, and ``'' denotes propagation to the ``left''. This notation is similar to that used for acoustic-tube modeling of speech .
In Fig.E.1, ``transverse displacement outputs'' have been arbitrarily placed at and .
linear combinations of past state. As a result, each can be described in ``state-space form'' [449, Appendix G] by a constant matrix operator, the ``state transition matrix'', which multiplies the state vector at the current time to produce the state vector for the next time step. The FDTD operator propagates K variables while the DW operator propagates W variables. We may show equivalence by (1) defining a one-to-one transformation which will convert K variables to W variables or vice versa, and (2) showing that given any common initial state for both schemes, the state transition matrices compute the same next state in both cases. The next section shows that the linear transformation from W to K variables,
for all and , sets up a one-to-one linear transformation between the K and W variables. Assuming this holds, it only remains to be shown that the DW and FDTD schemes preserve mapping Eq.(E.7) after a state transition from one time to the next. While this has been shown previously , we repeat the derivation here for completeness. We also provide a state-space analysis reaching the same conclusion in §E.4. From Fig.E.1, it is clear that the DW scheme preserves mapping Eq.(E.7) by definition. For the FDTD scheme, we expand the right-hand of Eq.(E.3) using Eq.(E.7) and verify that the left-hand side also satisfies the map, i.e., that holds:
digital filters) converting between K variables and W variables have been devised . In this section, an alternative approach is proposed. Mapping Eq.(E.7) gives us an immediate conversion from W to K state variables, so all we need now is the inverse map for any time . This is complicated by the fact that non-local spatial dependencies can go indefinitely in one direction along the string, as we will see below. We will proceed by first writing down the conversion from W to K variables in matrix form, which is easy to do, and then invert that matrix. For simplicity, we will consider the case of an infinitely long string. To initialize a K variable simulation for starting at time , we need initial spatial samples at all positions for two successive times and . From this state specification, the FDTD scheme Eq.(E.3) can compute for all , and so on for increasing . In the DW model, all state variables are defined as belonging to the same time , as shown in Fig.E.2. E.6), and referring to the notation defined in Fig.E.2, we may write the conversion from W to K variables as
where the last equality follows from the traveling-wave behavior (see Fig.E.2). E.3 shows the so-called ``stencil'' of the FDTD scheme. The larger circles indicate the state at time which can be used to compute the state at time . The filled and unfilled circles indicate membership in one of two interleaved grids . To see why there are two interleaved grids, note that when is even, the update for depends only on odd from time and even from time . Since the two W components of are converted to two W components at time in Eq.(E.8), we have that the update for depends only on W components from time and positions . Moving to the next position update, for , the state used is independent of that used for , and the W components used are from positions and . As a result of these observations, we see that we may write the state-variable transformation separately for even and odd , e.g.,
Denote the linear transformation operator by and the K and W state vectors by and , respectively. Then Eq.(E.9) can be restated as
The operator can be recognized as the Toeplitz operator associated with the linear, shift-invariant filter . While the present context is not a simple convolution since is not a simple time series, the inverse of corresponds to the Toeplitz operator associated with
The case of the finite string is identical to that of the infinite string when the matrix is simply ``cropped'' to a finite square size (leaving an isolated 1 in the lower right corner); in such cases, as given above is simply cropped to the same size, retaining its upper triangular structure. Another interesting set of cases is obtained by inserting a 1 in the lower-left corner of the cropped matrix to make it circulant; in these cases, the matrix contains in every position for even , and is singular for odd (when there is one zero eigenvalue).
initial conditions (for time )
Thus, the impulse starts out with amplitude 2 at time 0 and position , and afterwards, impulses of amplitude 1 propagate away to the left and right along the string. In summary, we see that to excite a single sample of displacement traveling in a single-direction, we must excite equally a pair of adjacent colums in . This corresponds to equally weighted excitation of K-variable pairs the form . Note that these examples involved only one of the two interleaved computational grids. Shifting over an odd number of spatial samples to the left or right would involve the other grid, as would shifting time forward or backward an odd number of samples.
velocity excitations are straightforward in the DW paradigm, but can be less intuitive in the FDTD domain. It is well known that velocity in a displacement-wave DW simulation is determined by the difference of the right- and left-going waves . Specifically, initial velocity waves can be computed from from initial displacement waves by spatially differentiating to obtain traveling slope waves , multiplying by minus the tension to obtain force waves, and finally dividing by the wave impedance to obtain velocity waves:
where denotes sound speed. The initial string velocity at each point is then . (A more direct derivation can be based on differentiating Eq.(E.4) with respect to and solving for velocity traveling-wave components, considering left- and right-going cases separately at first, and arguing the general case by superposition.) We can see from Eq.(E.11) that such asymmetry can be caused by unequal weighting of and . For example, the initialization
From Eq.(E.11), it is clear that initializing any single K variable
corresponds to the initialization of an infinite number of W
. That is, a single K variable
corresponds to only a single column of
for only one of the
interleaved grids. For example,
referring to Eq.(E.11),
initializing the K variable
to -1 at time (with all other intialized to 0)
corresponds to the W-variable initialization
More General Velocity Excitations
Below the solid line is the sum of the left- and right-going traveling-wave components, i.e., the corresponding K variables at time . The vertical lines divide positions and . The initial displacement is zero everywhere at time , consistent with an initial velocity excitation. At times , the configuration evolves as follows:
The sequence consists of a dc (zero-frequency) component with amplitude , plus a sampled sinusoid of amplitude oscillating at half the sampling rate . The dc component is physically correct for an initial velocity point-excitation (a spreading square pulse on the string is expected). However, the component at is usually regarded as an artifact of the finite difference scheme. From the DW interpretation of the FDTD scheme, which is an exact, bandlimited physical interpretation, we see that physically the component at comes about from initializing velocity on only one of the two interleaved subgrids of the FDTD scheme. Any asymmetry in the excitation of the two interleaved grids will result in excitation of this frequency component. Due to the independent interleaved subgrids in the FDTD algorithm, it is nearly always non-physical to excite only one of them, as the above example makes clear. It is analogous to illuminating only every other pixel in a digital image. However, joint excitation of both grids may be accomplished either by exciting adjacent spatial samples at the same time, or the same spatial sample at successive times instants. In addition to the W components being non-local, they can demand a larger dynamic range than the K variables. For example, if the entire semi-infinite string for is initialized with velocity , the initial displacement traveling-wave components look as follows:
and the variables evolve forward in time as follows:
Thus, the left semi-infinite string moves upward at a constant velocity of 2, while a ramp spreads out to the left and right of position at speed , as expected physically. By Eq.(E.9), the corresponding initial FDTD state for this case is
initial conditions, ongoing input signals can be defined analogously. For example, feeding an input signal into the FDTD via
corresponds to physically driving a single sample of string displacement at position . This is the spatially distributed alternative to the temporally distributed solution of feeding an input to a single displacement sample via the filter as discussed in .
displacement sample in the FDTD corresponds to driving a velocity input at position on two alternating subgrids over time. Therefore, the filter acts as the filter on either subgrid alone--a first-order difference. Since displacement is being simulated, velocity inputs must be numerically integrated. The first-order difference can be seen as canceling this integration, thereby converting a velocity input to a displacement input, as in Eq.(E.23).
In this section, we will summarize and extend the above discussion by
means of a state space analysis .
E.10). The other subgrid is handled
identically and will not be considered explicitly. In fact, the other
subgrid can be dropped altogether to obtain a half-rate,
staggered grid scheme [55,147]. However, boundary
conditions and input signals will couple the subgrids, in general. To
land on the same subgrid after a state update, it is necessary to
advance time by two samples instead of one. The state-space model for
one subgrid of the FDTD model of the ideal string may then be written
State Space Formulation
To avoid the issue of boundary conditions for now, we will continue working with the infinitely long string. As a result, the state vector denotes a point in a space of countably infinite dimensionality. A proper treatment of this case would be in terms of operator theory . However, matrix notation is also clear and will be used below. Boundary conditions are taken up in §E.4.3. When there is a general input signal vector , it is necessary to augment the input matrix to accomodate contributions over both time steps. This is because inputs to positions at time affect position at time . Henceforth, we assume and have been augmented in this way. Thus, if there are input signals , , driving the full string state through weights , , the vector is of dimension :
The intra-grid state update for even is then given by
For odd , the update in Eq.(E.25) is used. Thus, every other row of , for time , consists of the vector preceded and followed by zeros. Successive rows for time are shifted right two places. The rows for time consist of the vector aligned similarly:
E.2, the traveling-wave decomposition Eq.(E.4) defines a linear transformation Eq.(E.10) from the DW state to the FDTD state:
Since is invertible, it qualifies as a linear transformation for performing a change of coordinates for the state space. Substituting Eq.(E.27) into the FDTD state space model Eq.(E.24) gives
Multiplying through Eq.(E.28) by gives a new state-space representation of the same dynamic system which we will show is in fact the DW model of Fig.E.2:
To verify that the DW model derived in this manner is the computation diagrammed in Fig.E.2, we may write down the state transition matrix for one subgrid from the figure to obtain the permutation matrix ,
and displacement output matrix :
The th block of the input matrix driving state components and multiplying is then given by
Typically, input signals are injected equally to the left and right along the string, in which case
Finally, when and for all , we obtain the result familiar from Eq.(E.23):
Since a displacement input at position corresponds to
symmetrically exciting the right- and left-going traveling-wave
components and , it is of interest to understand what
it means to excite these components antisymmetrically. As
discussed in §E.3.3, an antisymmetric excitation of
traveling-wave components can be interpreted as a velocity
excitation. It was noted that localized velocity excitations in the
FDTD generally correspond to non-localized velocity excitations in the
DW, and that velocity in the DW is proportional to the spatial
derivative of the difference between the left-going and right-going
traveling displacement-wave components (see Eq.(E.13)). More
generally, the antisymmetric component of displacement-wave excitation
can be expressed in terms of any wave variable which is linearly
independent relative to displacement, such as acceleration, slope,
force, momentum, and so on. Since the state space of a vibrating
string (and other mechanical systems) is traditionally taken to be
position and velocity, it is perhaps most natural to relate the
antisymmetric excitation component to velocity.
In practice, the simplest way to handle a velocity input in a
DW simulation is to first pass it through a first-order integrator of the
DW Non-Displacement Inputs
to convert it to a displacement input. By the equivalence of the DW and FDTD models, this works equally well for the FDTD model. However, in view of §E.3.3, this approach does not take full advantage of the ability of the FDTD scheme to provide localized velocity inputs for applications such as simulating a piano hammer strike. The FDTD provides such velocity inputs for ``free'' while the DW requires the external integrator Eq.(E.37). Note, by the way, that these ``integrals'' (both that done internally by the FDTD and that done by Eq.(E.37)) are merely sums over discrete time--not true integrals. As a result, they are exact only at dc (and also trivially at , where the output amplitude is zero). Discrete sums can also be considered exact integrators for impulse-train inputs--a point of view sometimes useful when interpreting simulation results. For normal bandlimited signals, discrete sums most accurately approximate integrals in a neighborhood of dc. The KW-converter filter has analogous properties.
state-space model is given in terms of the FDTD state-space model by Eq.(E.31). The similarity transformation matrix is bidiagonal, so that and are both approximately diagonal when the output is string displacement for all . However, since given in Eq.(E.11) is upper triangular, the input matrix can replace sparse input matrices with only half-sparse , unless successive columns of are equally weighted, as discussed in §E.3. We can say that local K-variable excitations may correspond to non-local W-variable excitations. From Eq.(E.35) and Eq.(E.36), we see that displacement inputs are always local in both systems. Therefore, local FDTD and non-local DW excitations can only occur when a variable dual to displacement is being excited, such as velocity. If the external integrator Eq.(E.37) is used, all inputs are ultimately displacement inputs, and the distinction disappears.
forces consideration of boundary conditions. In this section, we will introduce boundary conditions as perturbations of the state transition matrix. In addition, we will use the DW-FDTD equivalence to obtain physically well behaved boundary conditions for the FDTD method. Consider an ideal vibrating string with spatial samples. This is a sufficiently large number to make clear most of the repeating patterns in the general case. Introducing boundary conditions is most straightforward in the DW paradigm. We therefore begin with the order 8 DW model, for which the state vector (for the 0th subgrid) will be
The simplest choice of state transformation matrix is obtained by cropping it to size :
boundary conditions on the state transition matrices and , it is convenient to write the terminated transition matrix as the sum of of the ``left-clamped'' case (for which ) plus a series of one or more rank-one perturbations. For example, introducing a right termination with reflectance can be written
where is the matrix containing a 1 in its th entry, and zero elsewhere. (Following established convention, rows and columns in matrices are numbered from 1.) In general, when is odd, adding to corresponds to a connection from left-going waves to right-going waves, or vice versa (see Fig.E.2). When is odd and is even, the connection flows from the right-going to the left-going signal path, thus providing a termination (or partial termination) on the right. Left terminations flow from the bottom to the top rail in Fig.E.2, and in such connections is even and is odd. The spatial sample numbers involved in the connection are and , where denotes the greatest integer less than or equal to . The rank-one perturbation of the DW transition matrix Eq.(E.39) corresponds to the following rank-one perturbation of the FDTD transition matrix :
In general, we have
Thus, the general rule is that transforms to a matrix which is zero in all but two rows (or all but one row when ). The nonzero rows are numbered and (or just when ), and they are identical, being zero in columns , and containing starting in column .
reflectance . The condition for passivity of the reflectance is simply that its gain be bounded by 1 at all frequencies :
A very simple case, used, for example, in the Karplus-Strong plucked-string algorithm, is the two-point-average filter:
Kelly-Lochbaum scattering junction [297,447] can be introduced into the string at the fourth sample by the following perturbation
state-space models are equivalent with respect to lossy traveling-wave simulation. Figure E.4 shows the flow diagram for the case of simple attenuation by per sample of wave propagation, where for a passive string.
state-space models which are related to each other by a simple change of coordinates (similarity transformation). It is well known that such systems exhibit the same transfer functions, have the same modes, and so on. In short, they are the same linear dynamic system. Differences may exist with respect to spatial locality of input signals, initial conditions, and boundary conditions. State-space analysis was used to translate initial conditions and boundary conditions from one case to the other. Passive terminations in the DW paradigm were translated to passive terminations for the FDTD scheme, and FDTD excitations were translated to the DW case in order to interpret them physically.
delay lines to obtain an computation per time sample , whereas the FDTD scheme is per sample ( being the number of spatial samples along the string). There is apparently no known way to achieve complexity for the FDTD scheme. In higher dimensions, i.e., when simulating membranes and volumes, the delay-line advantage disappears, and the FDTD scheme has the lower operation count (and memory storage requirements).
linear transformation was derived for converting state variables of the finite-difference time-domain (FDTD) scheme to those of the digital waveguide (DW) scheme. The equivalence of the FDTD and DW state transitions was reviewed, and the proof of state-space equivalence was completed. Since the DW scheme is exact within its bandwidth (being a sampled traveling-wave scheme instead of a finite difference scheme), it can be put forth as the proper physical interpretation of the FDTD scheme, and consequently be used to provide physically accurate initial conditions and excitations for the FDTD method. For its part, the FDTD method provides lower cost relative to the DW method in dimensions higher than one (for simulating membranes, volumes, and so on), and can be preferred in highly distributed nonlinear string simulation applications.
initial conditions and boundary conditions in the DW framework should map to localized counterparts in the FDTD scheme. A generalization of the Toeplitz operator having a known closed-form inverse could be useful in higher dimensions.
Wave Digital Filters