State Space Formulation

In this section, we will summarize and extend the above discussion by means of a state space analysis [220].

FDTD State Space Model

Let denote the FDTD state for one of the two subgrids at time , as defined by Eq.(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 as

 (E.24)

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 [325]. 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 :

When there is only one physical input, as is typically assumed for plucked, struck, and bowed strings, then and is . The matrix weights these inputs before they are added to the state vector for time , and its entries are derived in terms of the coefficients below.

forms the output signal as an arbitrary linear combination of states. To obtain the usual displacement output for the subgrid, is the matrix formed from the identity matrix by deleting every other row, thereby retaining all displacement samples at time and discarding all displacement samples at time in the state vector :

The state transition matrix may be obtained by first performing a one-step time update,

and then expanding the two terms in terms of the state at time :
 (E.25)

The intra-grid state update for even is then given by
 (E.26)

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:

From Eq.(E.26) we also see that the input matrix is given as defined in the following expression:

DW State Space Model

As discussed in §E.2, the traveling-wave decomposition Eq.(E.4) defines a linear transformation Eq.(E.10) from the DW state to the FDTD state:

 (E.27)

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
 (E.28) (E.29)

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:
 (E.30)

where
 (E.31)

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 ,

 (E.32)

and displacement output matrix :

DW Displacement Inputs

We define general DW inputs as follows:

 (E.33) (E.34)

The th block of the input matrix driving state components and multiplying is then given by

 (E.35)

Typically, input signals are injected equally to the left and right along the string, in which case

Physically, this corresponds to applied forces at a single, non-moving, string position over time. The state update with this simplification appears as

Note that if there are no inputs driving the adjacent subgrid ( ), such as in a half-rate staggered grid scheme, the input reduces to

To show that the directly obtained FDTD and DW state-space models correspond to the same dynamic system, it remains to verify that . It is somewhat easier to show that

A straightforward calculation verifies that the above identity holds, as expected. One can similarly verify , as expected. The relation provides a recipe for translating any choice of input signals for the FDTD model to equivalent inputs for the DW model, or vice versa. For example, in the scalar input case (), the DW input-weights become FDTD input-weights according to

The left- and right-going input-weight superscripts indicate the origin of each coefficient. Setting results in

 (E.36)

Finally, when and for all , we obtain the result familiar from Eq.(E.23):

Similarly, setting for all , the weighting pattern appears in the second column, shifted down one row. Thus, in general (for physically stationary displacement inputs) can be seen as the superposition of weight patterns in the left column for even , and the right column for odd (the other subgrid), where the is aligned with the driven sample. This is the general collection of displacement inputs.

DW Non-Displacement Inputs

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 form

 (E.37)

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.

Input Locality

The DW 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.

Boundary Conditions

The relations of the previous section do not hold exactly when the string length is finite. A finite-length string 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 displacement output matrix is given by

and the input matrix is an arbitrary matrix. We will choose a scalar input signal driving the displacement of the second spatial sample with unit gain:

The state transition matrix is obtained by reducing Eq.(E.32) to finite order in some way, thereby introducing boundary conditions.

Resistive Terminations

Let's begin with simple resistive'' terminations at the string endpoints, resulting in the reflection coefficient at each end of the string, where corresponds to nonnegative (passive) termination resistances [447]. Inspection of Fig.E.2 makes it clear that terminating the left endpoint may be accomplished by setting

and the right termination corresponds to

By allowing an additional two samples of round-trip delay in each endpoint reflectance (one sample in the chosen subgrid), we can implement these reflections within the state-transition matrix:

 (E.38)

The simplest choice of state transformation matrix is obtained by cropping it to size :

An advantage of this choice is that its inverse is similarly a simple cropping of the case. However, the corresponding FDTD system is not so elegant:

where and . We see that the left FDTD termination is non-local for , while the right termination is local (to two adjacent spatial samples) for all . This can be viewed as a consequence of having ordered the FDTD state variables as instead of . Choosing the other ordering interchanges the endpoint behavior. Call these orderings Type I and Type II, respectively. Then ; that is, the similarity transformation matrix is transposed when converting from Type I to Type II or vice versa. By anechoically coupling a Type I FDTD simulation on the right with a Type II simulation on the left, general resistive terminations may be obtained on both ends which are localized to two spatial samples.

In nearly all musical sound synthesis applications, at least one of the string endpoints is modeled as rigidly clamped at the nut''. Therefore, since the FDTD, as defined here, most naturally provides a clamped endpoint on the left, with more general localized terminations possible on the right, we will proceed with this case for simplicity in what follows. Thus, we set and obtain

Boundary Conditions as Perturbations

To study the effect of 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

 (E.39)

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 :

where
 (E.40)

In general, we have

 (E.41)

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 .

Reactive Terminations

In typical string models for virtual musical instruments, the nut end'' of the string is rigidly clamped while the bridge end'' is terminated in a passive reflectance . The condition for passivity of the reflectance is simply that its gain be bounded by 1 at all frequencies [447]:

 (E.42)

A very simple case, used, for example, in the Karplus-Strong plucked-string algorithm, is the two-point-average filter:

To impose this lowpass-filtered reflectance on the right in the chosen subgrid, we may form

which results in the FDTD transition matrix

This gives the desired filter in a half-rate, staggered grid case. In the full-rate case, the termination filter is really

which is still passive, since it obeys Eq.(E.42), but it does not have the desired amplitude response: Instead, it has a notch (gain of 0) at one-fourth the sampling rate, and the gain comes back up to 1 at half the sampling rate. In a full-rate scheme, the two-point-average filter must straddle both subgrids.

Another often-used string termination filter in digital waveguide models is specified by [447]

where is an overall gain factor that affects the decay rate of all frequencies equally, while controls the relative decay rate of low-frequencies and high frequencies. An advantage of this termination filter is that the delay is always one sample, for all frequencies and for all parameter settings; as a result, the tuning of the string is invariant with respect to termination filtering. In this case, the perturbation is

and, using Eq.(E.41), the order FDTD state transition matrix is given by

where

The filtered termination examples of this section generalize immediately to arbitrary finite-impulse response (FIR) termination filters . Denote the impulse response of the termination filter by

where the length of the filter does not exceed . Due to the DW-FDTD equivalence, the general stability condition is stated very simply as

Interior Scattering Junctions

A so-called Kelly-Lochbaum scattering junction [297,447] can be introduced into the string at the fourth sample by the following perturbation

Here, denotes the reflection coefficient seen'' from left to right, and is the reflectance of the junction from the right. When the scattering junction is caused by a change in string density or tension, we have . When it is caused by an externally imposed termination (such as a plectrum or piano-hammer touching the string), we have , and the reflectances may become filters instead of real values in . Energy conservation demands that the transmission coefficients be amplitude complementary with respect to the reflection coefficients [447].

A single time-varying scattering junction provides a reasonable model for plucking, striking, or bowing a string at a point. Several adjacent scattering junctions can model a distributed interaction, such as a piano hammer, finger, or finite-width bow spanning several string samples.

Note that scattering junctions separated by one spatial sample (as typical in digital waveguide filters'' [447]) will couple the formerly independent subgrids. If scattering junctions are confined to one subgrid, they are separated by two samples of delay instead of one, resulting in round-trip transfer functions of the form (as occurs in the digital waveguide mesh). In the context of a half-rate staggered-grid scheme, they can provide general IIR filtering in the form of a ladder digital filter [297,447].

Lossy Vibration

The DW and FDTD 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.

The DW state update can be written in this case as

where the loss associated with two time steps has been incorporated into the chosen subgrid for physical accuracy. (The neglected subgrid may now be considered lossless.) In changing coordinates to the FDTD scheme, the gain factor can remain factored out, yielding

When the input is zero after a particular time, such as in a plucked or struck string simulation, the losses can be implemented at the final output, and only when an output is required, e.g.,

where denotes the corresponding lossless simulation. When there is a general input signal, the state vector needs to be properly attenuated by losses. In the DW case, the losses can be lumped at two points per spatial input and output [447].

State Space Summary

We have seen that the DW and FDTD schemes correspond to 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.

Next Section:
Computational Complexity
Previous Section:
Excitation Examples