Signed Binary Digit Streams

  The first representation makes use of a stream of signed binary digits $\{\overline{1}, 0, 1\}$. This representation is also known as the redundant binary representation on $\mathbb{R}$ [17]. The real number represented by the stream x = (d₁::d₂::d₃::...) is defined as:

$$\llbracket x \rrbracket = \sum_{i=1}^{\infty}d_i\!\cdot\!2^{... ...} + \frac{d_2}{2^2} + \frac{d_3}{2^3} + \frac{d_4}{2^4} + \dots$$

Hence $\llbracket x \rrbracket \in [-1,1]$. There is a unique representation for the numbers minus one ($\overrightarrow{-1}$) and one ($\overrightarrow{1}$), and infinitely many representations for all other numbers in this range.

We also define the range (see section 3.1) of a finite portion of the stream as follows: Let x' be a list containing the first m digits of x, $\llbracket x' \rrbracket$ is the range of x':

Figure 3.1 shows the range of values represented by the signed binary streams starting with each of the three possible digits.

  

Figure 3.1: The range of streams starting with different digits

There are two further interesting observations to make. The first is that the following identities exist. We use them frequently when developing algorithms using signed binary streams:

 

The second observation is that the signed binary representation has a fixed rate of convergence. In other words, every new digit in the stream refines the range of possible values taken by the stream at a fixed rate.