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

Complexity Reduction: A Physical Approach

The scattering matrix of a physical junction of $N$ waveguides (38) can be expressed in terms of the alpha parameters as

{\mbox{\boldmath$A$}}= {\mbox{\boldmath$1$}}{\mbox{\boldmath$\alpha$}}^T - {\mbox{\boldmath$I$}}
\end{displaymath} (61)

where \( {\mbox{\boldmath$\alpha$}}^T = \left[
\alpha_1 &
\alpha_2 &
\dots &
\end{array} \right] \), and in the lossless case,
\alpha_i {\tiny\stackrel{\triangle}{=}}2\Gamma_i \left/ {\displaystyle \sum_{j=1}^{N}{\Gamma_j}}. \right.
\end{displaymath} (62)

The vector of outgoing pressure waves can be expressed as
{\mbox{\boldmath$p$}}^-= {\mbox{\boldmath$A$}}{\mbox{\boldma...
...angle}{=}{\mbox{\boldmath$1$}}p_J- {\mbox{\boldmath$p$}}^+
\end{displaymath} (63)

where $p_J= {\mbox{\boldmath$\alpha$}}^T {\mbox{\boldmath$p$}}^+$ can be interpreted as the ``junction pressure.'' Thus, the matrix-vector multiplication can be seen to require only $N$ multiplications and $2N-1$ additions.

Equation (64) can be rewritten as

$\displaystyle p_J$ $\textstyle =$ $\displaystyle \sum_{i=1}^N \alpha_i p^+_i, \qquad
\alpha_i \stackrel{\triangle}{=}\frac{2\Gamma_i}{\Gamma_1 + \cdots + \Gamma_N}$  
$\displaystyle p^-_j$ $\textstyle =$ $\displaystyle p_J- p^+_j$ (64)

This is the canonical form of the scattering relations for a physical $N$-way scattering junction parametrized in terms of the alpha parameters.

Whenever possible, it is advisable to set the branch impedances so that $\alpha_i=1$ for some $i$, and therefore only $N-1$ multiplications are needed. This is achieved when the $i$th waveguide admittance equals the sum of all the other admittances. According to Fettweis' terminology for wave digital filters, the $i$th junction port is called a reflection-free port, and the $i$th branch is said to be adapted to the other $N-1$ branches. Physically, a wave traveling into the junction on a reflection-free port will be fully scattered into the other branches meeting at the junction, with no reflection back along branch $i$.

In time-varying applications, it is also convenient to maintain scaling such that \( \sum_{j=1}^N{\Gamma_j} = 1 \) so that no divisions or renormalizations are necessary in the alpha parameters. This is easily accomplished by setting the admittance of branch $1$, say, to

\Gamma_1(n) = 1-\sum_{i=2}^N \Gamma_i(n)
\end{displaymath} (65)

provided this remains nonnegative.

Since the alpha parameters sum to $2$ in the lossless case, the first element, say, of the vector ${\mbox{\boldmath$\alpha$}}$ can be expressed as

\alpha_1 = 2 - {\displaystyle \sum_{i=2}^{N}{\alpha_i}}
\end{displaymath} (66)

Thus, the vector of outgoing pressure waves can be computed as
$\displaystyle {\mbox{\boldmath$p$}}^-$ $\textstyle =$ $\displaystyle {\mbox{\boldmath$1$}}{\mbox{\boldmath$\alpha$}}^T {\mbox{\boldmath$p$}}^+- {\mbox{\boldmath$p$}}^+$  
  $\textstyle =$ $\displaystyle {\mbox{\boldmath$1$}}\left(2 p_1^+ - {\displaystyle \sum_{i=2}^{N...
...{\displaystyle \sum_{i=2}^{N}{\alpha_i} p_i^+}\right) - {\mbox{\boldmath$p$}}^+$  
  $\textstyle =$ $\displaystyle {\mbox{\boldmath$1$}}\left[ 2 p_1^+
+ {\displaystyle \sum_{i=2}^{N}{\alpha_i} (p_i^+ - p_1^+)}\right] - {\mbox{\boldmath$p$}}^+$ (67)

which implies
$\displaystyle p^-_j$ $\textstyle =$ $\displaystyle 2 p_1^+ + {\displaystyle \sum_{i=2}^N{\alpha_i} (p_i^+ - p_1^+)} - p^+_j$  
  $\textstyle =$ $\displaystyle p_1^- - \underbrace{(p_j^+ - p_1^+)}_{\hbox{available}}$ (68)

In Fettweis' terminology, the port corresponding to the first waveguide is called the dependent port. Organizing the computations as in (68), a scattering junction can be performed with $N-1$ multiplications and $3 N - 2$ additions instead of $N$ multiplies and $2N-1$ additions using (64). Saving and reusing differences as implied in (69) eliminates another addition to get the number of [multiplies,adds] down to $[N-1,3(N-1)]$ (see Fig. 6 for $N=2$). If we add the assumption that one of the ports is reflection-free, we get additional savings and use only $N-2$ multiplications and $3 N - 5$ adds [28]. Exploiting the dependent port leads to a small savings in the number of multiplies at the expense of an increase in the constant of proportionality in the number of adds. Nevertheless, for the case $N=2$, the formulation (69) is advantageous, since it can be implemented with one multiply and three adds.

Figure: A one-multiply, three-add, scattering junction parametrized by an alpha parameter.

An important advantage provided by the organization of computations (68) and (69) is that they force the junction to be row allpass complementary (see section 5) even under coefficient quantization. The following theorem establishes the connection between allpass complementarity and structural losslessness of the scattering matrix.

Theorem 4   Condition (67) (implying row allpass complementarity of the scattering matrix) is necessary and sufficient for structural losslessness of the physical scattering junction of $N$ scalar waveguides in the presence of coefficient quantization.

Proof: Denote the quantized scattering matrix by $\hat{{\mbox{\boldmath$A$}}}\stackrel{\triangle}{=}
{\mbox{\boldmath$1$}}\hat{{\mbox{\boldmath$\alpha$}}}^T-{\mbox{\boldmath$I$}}$, where $\hat{{\mbox{\boldmath$\alpha$}}}= {\mbox{\boldmath$\alpha$}}- {\mbox{\boldmath$\epsilon$}}$, and ${\mbox{\boldmath$\epsilon$}}=[\epsilon _1, \ldots, \epsilon _N]^T$ is the vector of quantization errors in the alpha parameters $\alpha_i=\hat{\alpha}_i+\epsilon _i$. We must show that for every ${\mbox{\boldmath$\epsilon$}}$, there exists a positive-definite matrix $\hat{{\mbox{\boldmath$\Gamma$}}}$ such that $\hat{{\mbox{\boldmath$A$}}}^T\hat{{\mbox{\boldmath$\Gamma$}}}\hat{{\mbox{\boldmath$A$}}}=\hat{{\mbox{\boldmath$\Gamma$}}}$ exactly. Under the assumption that $\hat{{\mbox{\boldmath$\Gamma$}}}$ is diagonal, which follows from restriction to a physical junction of scalar waveguides, we need only find $N$ positive diagonal elements $\hat{\Gamma}_i$ which satisfy the definition of losslessness of $\hat{{\mbox{\boldmath$A$}}}$. Let $\hat{{\mbox{\boldmath$\gamma$}}}=\hat{{\mbox{\boldmath$\Gamma$}}}{\mbox{\boldmath$1$}}= [\hat{\Gamma}_1, \ldots, \hat{\Gamma}_N]^T$ denote the vector of diagonal elements of $\hat{{\mbox{\boldmath$\Gamma$}}}$. Then losslessness requires
$\displaystyle \hat{{\mbox{\boldmath$\Gamma$}}}$ $\textstyle =$ $\displaystyle \hat{{\mbox{\boldmath$A$}}}^T\hat{{\mbox{\boldmath$\Gamma$}}}\hat{{\mbox{\boldmath$A$}}}$  
  $\textstyle =$ $\displaystyle (\hat{{\mbox{\boldmath$\alpha$}}}{\mbox{\boldmath$1$}}^T-{\mbox{\...
  $\textstyle =$ $\displaystyle \hat{{\mbox{\boldmath$\alpha$}}}\hat{{\mbox{\boldmath$\alpha$}}}^...
...\gamma$}}}\hat{{\mbox{\boldmath$\alpha$}}}^T + \hat{{\mbox{\boldmath$\Gamma$}}}$ (69)

Thus, we must find positive $\hat{\Gamma}_i$ such that
\hat{\Gamma}_i \hat{\alpha}_j + \hat{\Gamma}_j \hat{\alpha}_i = \hat{\alpha}_i\hat{\alpha}_j\sum_{l=1}^N \hat{\Gamma}_l
\end{displaymath} (70)

Let $\hat{\Gamma}_i=c\hat{\alpha}_i/2$ where $c$ is any positive constant. Since $\hat{\alpha}_i$ is positive, so is $\hat{\Gamma}_i$. (While $\hat{\alpha}_i$ is restricted to certain values, $\hat{\Gamma}_i$ may be any positive real value). The condition (71) becomes
\hat{\alpha}_i \hat{\alpha}_j c = \hat{\alpha}_i\hat{\alpha}_j c\sum_{l=1}^N \hat{\alpha}_l/2
\end{displaymath} (71)

which holds if and only if
\sum_{l=1}^N \hat{\alpha}_l = 2
\end{displaymath} (72)

and this identity is provided by condition (67).

We see that exact losslessness of a physical waveguide junction is assured provided only that the actual alpha parameters are positive and sum precisely to 2 after quantization. The proof extends readily to nonnegative $\hat{\alpha}_i$ by assigning $\hat{\Gamma}_i=0$ to any waveguide branch corresponding to a port for which $\hat{\alpha}_i=0$. (Note that $\hat{\alpha}_i=0$ corresponds to a branch which contributes no signal to the junction, and a branch with zero admittance can convey no signal power. Such a situation is physically degenerate so that if quantization forces $\hat{\alpha}_i$ to zero for some $i$, the corresponding branch may be removed from the junction.)

The above theorem is quite simple from a physical point of view: All we require for exact losslessness is that the quantized scattering matrix correspond to some valid lossless scattering matrix. From the physical correspondence (63) between the alpha parameters and the branch wave admittances it is clear that losslessness holds when $\hat{\alpha}_1+\cdots+\hat{\alpha}_N=2$. For more general passivity, we can add a positive real ``load'' admittance $\Gamma_L$ to the sum over $\Gamma_j$ above to obtain that scattering passivity holds if and only if the alpha parameters are positive and sum to a value not exceeding $2$.

The above discussion is only concerned with passivity of the scattering matrix itself. The application of the matrix is assumed to be exact. Since rounding of the final outgoing waves is necessary in practice, we add

Corollary 4   Sufficient conditions for the passivity of a DWN are (1) all scattering matrices are passive, (2) intermediate outgoing waves are computed exactly at each junction in extended precision before rounding, and (3) the final outgoing waves from each junction are rounded passively.

Since extended intermediate precision is required to ensure passivity, it is of interest to examine the additional bits required.

Theorem 5   For an order $N$ junction with $m$-bit alpha parameters ($m>1$) and $n$-bit scalar wave variables ($n>2$) computed in fixed point, the extended precision needed to implement the canonical scattering formula (64) is (a) one additional bit for the computation of junction pressure $p_J$, and (b) two additional bits for the computation of each outgoing wave $p^-_j$.

Proof: From (64), assuming $0<\alpha_i \leq 2$ and $-1\leq p^+_i<1$, we have

\left\vert p_J\right\vert = \left\vert\sum_{i=1}^N\alpha_i p...
...a_i \left\vert p^+_i\right\vert
< \sum_{i=1}^N\alpha_i \leq 2

Hence (a) one additional bit is sufficient for the inner-product accumulator for $p_J$. That the extra bit is necessary is shown by taking $p^+_i= -1$ for all $i$ in which case $p_J=-2$ for any set of lossless alpha parameters.

The outgoing wave variables are computed as $p^-_i= p_J- p^+_i$, and a single bit is clearly sufficient to provide the needed headroom for a single subtraction in general. That the second headroom bit is necessary is shown by considering the example $N=2$, $\alpha_1=0$, $\alpha_2=2$, $p^+_1=1/2$, $p^+_2=-1$, in which case $p^-_1 = -2 - 1/2 = -2.5$. If $\alpha_1=0$ is not allowed, then an example is obtained with $\alpha_1=\epsilon _1$, $\alpha_2=2-\epsilon _1$, $p^+_1=-1$, $p^+_2=1-\epsilon _2$, for which $p^-_1 = (\epsilon _1-1)(-1) + (2-\epsilon _1)(1-\epsilon _2) = 3 - 2 \epsilon _1 -
2\epsilon _2 + \epsilon _1 \epsilon _2$. For this to exceed $2$, we must have $2
\epsilon _1+2\epsilon _2 - \epsilon _1\epsilon _2<1$. With $m=3$ or more, we can choose $\epsilon _1=1/4$, and with $n=3$ or more, we can take $\epsilon _2=1/4$, and the inequality is satisfied. Thus, (b) two extra bits are necessary and sufficient for the computation of each outgoing wave variable $p^-_j$.

It is perhaps surprising at first that only one extra bit suffices for the junction pressure computation, no matter how many branches are impinging on the junction. Ordinarily, an inner product of length $N$ requires $\log_2(N)$ headroom bits. The single headroom bit requirement is a direct result of the alpha parameters being restricted to positive partitions of $2$ in the lossless case, or a positive partitioning of a positive number less than $2$ in the lossy, passive case.

Since an out-of-range outgoing traveling wave typically must be ``clipped'' in practice (i.e., replaced by $-1$ if negative and $1-\epsilon _2$ if positive), the two extra carry bits are normally fed along with the next lower bit (the in-range sign bit) to saturation logic which implements clipping as needed.

The computations (68) or (69) can also be used to implement precisely lossless or passive time-varying junctions. In this case, the passivity constraints become

$\displaystyle \sum_{i=2}^{N} \alpha_i(n) \leq 2$      
$\displaystyle \alpha_i(n) \geq 0$     (73)

where $n$ is time in samples, since $\alpha_1$ implicitly obeys (67) in formulas (68) and (69). (Here we allow $\alpha_i (n)=0$ which may be a convenient way to eliminate waveguide branches momentarily in the time-varying case.)

A junction of normalized waveguides can be obtained from (68) or (69) by transformer-coupling each branch other than the first with a waveguide having wave admittance $\Gamma_1$. The ideal transformer introduces two additional multiplications for each branch except one. Therefore, the normalized junction for arbitrary impedances can be implemented using $3(N-1)$ multiplications and $3(N-1)$ additions.

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
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]