NOTE: THIS DOCUMENT IS OBSOLETE, PLEASE CHECK THE NEW VERSION: "Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications --- Second Edition", by Julius O. Smith III, W3K Publishing, 2007, ISBN 978-0-9745607-4-8. - Copyright © 2017-09-28 by Julius O. Smith III - Center for Computer Research in Music and Acoustics (CCRMA), Stanford University
<< Previous page TOC INDEX Next page >>
Two's Complement Fixed-Point Format
In two's complement, numbers are negated by complementing the bit pattern and adding 1, with overflow ignored. From 0 to, positive numbers are assigned to binary values exactly as in one's complement. The remaining assignments (for the negative numbers) can be carried out using the two's complement negation rule. Regenerating the example in this way gives Table 4.4.
Table 4.4:Three-bit two's-complement binary fixed-point numbers.
Binary Decimal 000 0 001 1 010 2 011 3 100 -4 101 -3 110 -2 111 -1
Note that according to our negation rule, . Logically, what has happened is that the result has ''overflowed'' and ''wrapped around'' back to itself. Note that also. In other words, if you compute 4 somehow, since there is no bit-pattern assigned to 4, you get -4, because -4 is assigned the bit pattern that would be assigned to 4 if were larger. Note that numerical overflows naturally result in ''wrap around'' from positive to negative numbers (or from negative numbers to positive numbers). Computers normally ''trap'' overflows as an ''exception.'' The exceptions are usually handled by a software ''interrupt handler,'' and this can greatly slow down the processing by the computer (one numerical calculation is being replaced by a rather sizable program).
Note that temporary overflows are ok in two's complement; that is, if you add to to get , adding to will give again. This is why two's complement is a nice choice: it can be thought of as placing all the numbers on a ''ring,'' allowing temporary overflows of intermediate results in a long string of additions and/or subtractions. All that matters is that the final sum lie within the supported dynamic range.
Computers designed with signal processing in mind (such as so-called ''Digital Signal Processing (DSP) chips'') generally just do the best they can without generating exceptions. For example, overflows quietly ''saturates'' instead of ''wrapping around'' (the hardware simply replaces the overflow result with the maximum positive or negative number, as appropriate, and goes on). Since the programmer may wish to know that an overflow has occurred, the first occurrence may set an ''overflow indication'' bit which can be manually cleared. The overflow bit in this case just says an overflow happened sometime since it was last checked.