Complexity Reduction: A Geometric Approach

A convenient expression for the scattering matrix of a junction of $N$ normalized waveguides is obtained in terms of

$${\mbox{\boldmath$u$}}_n^T \stackrel{\triangle}{=}\left[ \b... ...\sqrt {\Gamma _2}&\dots&\sqrt {\Gamma _N} \end{array} \right]$$ (78)

The normalized scattering matrix ${\tilde {\mbox{\boldmath$A$}}}$ can then be expressed as

$${\tilde {\mbox{\boldmath$A$}}}=2\frac{{\mbox{\boldmath$u$}}{... ...^T}{\Vert{\mbox{\boldmath$u$}}\Vert^2} - {\mbox{\boldmath$I$}}$$ (79)

where $\Vert{\mbox{\boldmath$u$}}\Vert^2 \stackrel{\triangle}{=}{\mbox{\boldmath$u$}}^T{\mbox{\boldmath$u$}}$. Note that ${\mbox{\boldmath$u$}}$ is the eigenvector of ${\tilde {\mbox{\boldmath$A$}}}$ corresponding to the eigenvalue $1$. A matrix of the form $-{\tilde {\mbox{\boldmath$A$}}}$ is known as a Householder reflection [34], and it produces the mirror image of a given vector about the hyperplane orthogonal to the vector ${\mbox{\boldmath$u$}}$.

The Householder structure (80) can be exploited to speed up the matrix-vector multiplication. Define

$$w \stackrel{\triangle}{=}\beta {\mbox{\boldmath$u$}}_n^T {\mbox{\boldmath$p$}}^+$$ (80)

where $\beta = 2\left/\parallel {\mbox{\boldmath$u$}}_n \parallel^2\right.$. The computation of the outgoing waves can be expressed as:

$${\mbox{\boldmath$p$}}^-={\tilde {\mbox{\boldmath$A$}}}{\mbox... ...ath$p$}}^+={\mbox{\boldmath$u$}}_n w - {\mbox{\boldmath$p$}}^+$$ (81)

Thus, $N$ multiplications and $N-1$ additions are needed to compute the scalar product in (81), and $N$ multiplications and $N$ additions are needed for the final multiply-add in (82). In the case of an acyclic network graph, we can eliminate at least one multiplication in (82) by scaling all impedances appropriately. A total of $2N-1$ multiplications and $2N-1$ additions are needed.

The unnormalized Householder reflection is structurally a unitary transformation in the sense that remains a constant diagonal matrix after quantization of the vector ${\mbox{\boldmath$u$}}_n$ [110]. Hence, if all the incoming waves ${\mbox{\boldmath$p$}}^+$ are scaled by ${{\parallel {\mbox{\boldmath$u$}}_n \parallel}^{-2}}$, normalized junctions implemented in this way conserve their losslessness even under coefficient quantization. To be conservative, it is sufficient to scale the incoming waves by a constant slightly less than ${{\parallel {\mbox{\boldmath$u$}}_n \parallel}^{-2}}$, in such a way that the junction has a small loss. Preferably, however, we may scale the $\Gamma_i$ so that they sum to $2^K$ for some integer $K$, in which case ${{\parallel {\mbox{\boldmath$u$}}_n \parallel}^{-2}}$ becomes a power of $2$ implementable as a simple shift in fixed-point binary arithmetic.

Similarly, the unnormalized junction (38) can be interpreted as an ``oblique Householder'' reflection, in the sense that the sum of the vectors ${\mbox{\boldmath$p$}}^+$ and ${\mbox{\boldmath$p$}}^-$ is colinear with the vector $\left[\begin{array}{lll} 1 & \dots & 1 \end{array} \right]$ which lies on the diagonal of the parallelogram whose edges are given by the incoming and outgoing wave vectors. As we have already noticed in section 8, even in this case the matrix can be implemented as a structurally lossless transformation, and therefore it is well suited as a building block for large networks using fixed-point computations.

Computations (64) and (82) do not lend themselves to highly parallel implementations because of the scalar product needed to compute $w$ or $p_J$. A scalar product needs $O(\log_2{N})$ additions to be computed on $O(N)$ processors [55].