next up previous contents
Next: Multiplication Up: Signed Binary Stream Operations Previous: Signed Binary Stream Operations

Average

  The algorithm for computing the average of two signed binary streams is more complicated than the one for dyadic streams described in section 4.2.1. This is because unlike dyadic digits. individual signed binary digits are not closed under average.

The algorithm described here may require two digits of the input streams to generate one digit of output. A `carry' is used, but the carry is from left (most significant digit) to right (least significant digit), unlike conventional addition algorithms in which the carry occurs from right to left.

We describe the algorithm by first developing it from scratch and the proving its correctness. We then summarise the development by expressing the algorithm as a recursive function which computes the average of two inputs.

Suppose we wish to compute $(x \oplus y)$ where x is of the form (a0::a1::x'') and y is of the form (b0::b1::y''). We use signed binary carry digit c, which adds c/2 to the number represented by the result:

\begin{displaymath}
(a_{0}::a_{1}::x'') \oplus (b_{0}::b_{1}::y'') + \frac{c}{2}\end{displaymath}

Using the properties described in section 3.6.2, this is equal to:

We now wish to generate one signed binary digit of output, and express the remainder of the number as a recursive call. Let e be the digit which is to be output, and the amount c'/2 be the amount which cannot be represented exactly in the digit e and is to be added to the remainder of the stream by passing the digit c' right as the new carry.

\begin{displaymath}
= e \oplus \left((a_{1} \oplus b_{1}) \oplus (x'' \oplus y'') + \frac{c'}{2}\right)\end{displaymath}

These equations may be expanded to give:

\begin{displaymath}
\frac{c}{2} + \frac{a_{0}+b_{0}}{4} + \frac{a_{1}+b_{1}+x''+...
 ... = 
 \frac{e}{2} + \frac{c'}{4} + \frac{a_{1}+b_{1}+x''+y''}{8}\end{displaymath}

By re-arranging this we get c' = a0 + b0 + 2c - 2e.

Now let us assume $-2 \leq (a_{0} + b_{0} + 2c) \leq 2$. We now show how to compute e and c' so that this assumption will hold when we make the recursive call to the stream average operation. Observe that as c = 0 initially, the assumption holds. Now find e, c' such that

As $-2 \leq (a_{0} + b_{0} + 2c) \leq 2$, we find e as follows. Let $d
= 2\!\cdot\!(a_{0} + b_{0} + 2c) + a_{1} + b_{1}$:

\begin{displaymath}
e = \left\{\begin{array}
{rl}
\overline{1}& \qquad \textrm{i...
 ...\ 1 & \qquad \textrm{if }\ (2 < d \leq 6)\ \end{array} \right.\end{displaymath}

These equations lead to an algorithm for average, although it is more complex than dyadic average. In certain situations, however, it is not necessary to examine two digits of each input stream as the average of the first input digits and carry digit may be expressed exactly as a signed binary digit with a carry of zero.

The algorithm developed and proved above amounts to the following recursive definition.



$\begin{array}
{lrcl}
\lefteqn{\mathrm{average}(x,y) \ = \ \mathrm{average'}(x,y...
 ... 2)\ -1 & \qquad \textrm{if }\ (-6 \leq d<-2)\end{array} \right.\ \end{array}$



The sign function is defined as follows:



$\begin{array}
{l}\mathrm{sign}(x) \ = \ \left\{\begin{array}
{rl}
-1&\qquad \te...
 ...xtrm{if }\ (x=0)\ 1&\qquad \textrm{if }\ (x\gt)\end{array} \right. \end{array}$



The implementation of this algorithm is described in section 6.3, and its behaviour is examined further in section 7.1.2.


next up previous contents
Next: Multiplication Up: Signed Binary Stream Operations Previous: Signed Binary Stream Operations
Martin Escardo
5/11/2000