Fixed-Point Arithmetic and Overflow

Fixed-point representation places an implied binary point at a fixed position in a word: integer formats put it after the LSB, fractional formats before the MSB of the fraction field. Arithmetic uses the same adders as integer two's complement, with overflow and scaling rules. This note consolidates unsigned and two's-complement addition, subtraction, multiplication ranges, and overflow detection for GATE.

GATE asks which flags an addition sets, whether a signed or unsigned result overflowed, how many bits a sum or product needs, the range and resolution of a fixed-point format, and the effect of arithmetic shifts.

A word with $i$ integer bits and $f$ fraction bits ($i+f=n$, including sign if signed) represents multiples of $2^{-f}$. Scaling by $2^{f}$ converts to pure integer arithmetic: the pattern read as an integer $k$ stands for $k \cdot 2^{-f}$.

This note writes Q$i$.$f$ with the sign bit counted in $i$, so Q1.7 is an 8-bit signed fraction. Some texts write the same format as Q7 or Q0.7; check the stem's convention.

Converting a real number. Multiply by $2^f$, round (or truncate) to an integer $k$, then encode $k$ in two's complement only if $k$ is representable in the format. With no overflow, truncation error is below $2^{-f}$, and round-to-nearest error is at most $2^{-f-1}$. Reject an out-of-range value here; a separate saturation or wrap policy would not retain these quantization-only bounds.

For positive integers $n,k$, $n+\lceil\lg k\rceil$ bits are a sufficient guard-bit bound for adding $k$ unsigned $n$-bit numbers. The exact minimum width is $\lceil\lg(k(2^n-1)+1)\rceil$. Doubling the term count adds at most one required bit.

Compute $c_n$ and $c_{n-1}$ from the adder; XOR them. Alternatively compare sign bits of operands and result:

Both forms give the same $V$ on every input pair.

After an $n$-bit two's-complement add producing pattern $s$:

Over all 4-bit additions, only 9 of the 16 combinations of $(Z, N, C, V)$ occur. $Z$ and $N$ are never both 1, and when $V = 1$, $N$ is the complement of $C$: a positive overflow has $C = 0$ and $N = 1$, a negative overflow $C = 1$ and $N = 0$. For $5+3$ in 4 bits ($0101+0011=1000$): $Z=0$, $N=1$, $C=0$, $V=1$. For $(-8) + (-8)$: $0000$ with $Z = 1$, $C = 1$, $V = 1$.

Borrow polarity. After $A + \overline{B} + 1$, carry-out 1 means no borrow. Processor families differ in whether the stored flag is this carry or its complement (the borrow); follow the definition the question gives.

Related material. Some DSP datapaths clamp to min/max on overflow instead of wrapping. Saturation circuits are a DSP extension not named separately in the official syllabus.

Patterns are $n$-bit integers; mod is the non-negative remainder.

Identifying bit patterns with $\mathbb{Z}/2^n\mathbb{Z}$ makes wrap modularly correct always. The signed interpretation is only faithful when the mathematical result lies in $[-2^{n-1},2^{n-1}-1]$. Multiplication of two representatives corresponds to modular multiplication; the full signed product needs the double-width two's encoding.

Why $c_n \oplus c_{n-1}$ detects overflow. If both operands are non-negative, $c_n = 0$, and the sign bit of the sum equals $c_{n-1}$; overflow (a negative-looking result) is exactly $c_{n-1} = 1$. If both are negative, $c_n = 1$, and overflow (a non-negative result) is exactly $c_{n-1} = 0$. With mixed signs the true sum lies between the operands, so it cannot overflow, and $c_n = c_{n-1}$.

Product widths. For unsigned operands, $(2^n - 1)^2 = 2^{2n} - 2^{n+1} + 1 < 2^{2n}$. For signed operands, the largest magnitude is $(-2^{n-1})^2 = 2^{2n-2}$, one more than the $2n - 1$-bit maximum $2^{2n-2} - 1$; every other product has magnitude at most $2^{n-1}(2^{n-1} - 1)$, within $2n - 1$ bits.

$1001+1000=0001$ with carry 1: overflow, wrapped 1.

$0101+0011=1000$ ($-8$): overflow (both positive, result negative). Carry into sign 1, carry out 0, XOR 1.

$0101+1101=0010$ (2): no overflow. Carry into sign 1 and carry out 1, so $V = 0$; the unsigned carry $C = 1$ is irrelevant here.

$(-8)\times(-8)=64$ in 4-bit two's (min $-8$): 64 needs at least 8-bit two's ($01000000$). The next largest, $(-8) \times (-7) = 56$, already fits in 7 bits (range $-64$ to $63$).

Signed bit + 3 fraction bits; step $0.125$; range $-1.0$ to $0.875$. The value $-0.375 = -3/8$ is the 4-bit two's-complement pattern of $-3$: $1101$.

$0.3 \times 128 = 38.4$, which rounds to 38 = $00100110$. The stored value is $38/128 = 0.296875$, an error of $0.003125$, within the bound $2^{-8} = 0.00390625$.

In 4 bits, $3 - (-5) = 8$ overflows: $0011 + 0100 + 1 = 1000$, which reads as $-8$. The operands have different signs and the result's sign differs from the minuend's. By contrast $(-3) - 4 = -7$ fits: $1101 + 1011 + 1 = 1\,1001$, result $1001 = -7$.

Common misconceptions.