next up previous contents
Next: Average Up: Theoretical Analysis Previous: Theoretical Analysis

Conversions between Representations

The conversion algorithms described in section 3.7 convert between the dyadic and signed binary stream representations.

Conversion from signed binary to dyadic streams is a trivial operation. We require one input digit from the signed binary stream to determine one dyadic output digit, or n input digits to generate n output digits.

Conversion from dyadic to signed binary streams is marginally more complex. We require two input digits from the dyadic stream to determine one output digit in the signed stream. More generally, in order to obtain n signed binary digits, we require (n+1) dyadic digits. The algorithm itself requires three dyadic digit operations for each signed binary digit, but does not branch.

Martin Escardo