IN THE EC AND IN SYLLABUS

Number systems and codes

Number systems and codes covers how a digital system stores quantities as bit patterns: positional bases and conversion between them, r's and (r−1)'s complements, unsigned and signed (2's-complement) integers, decimal and unit-distance codes (BCD, excess-3, 2421, Gray), IEEE 754 floating point, and parity-based error detection. Problems on it are short calculations, such as reading a bit pattern as a signed value, deciding whether an addition overflowed, converting Gray to binary or decoding a floating-point word. Each one turns on a convention (which carry, which bias, whether there is a hidden 1), so these notes state every convention explicitly.

5 previous-year questions · 5 solved · 7 practice questions

Positional number systems and base conversion

A base- $r$ (radix- $r$ ) number uses the digits $0$ to $r - 1$ . Each digit is weighted by $r^{i}$ according to its position: $i = 0, 1, 2, \dots$ moving left from the radix point and $i = - 1, - 2, \dots$ moving right of it. The common bases are binary ( $r = 2$ ), octal ( $8$ ), decimal ( $10$ ) and hexadecimal ( $16$ , digits $0$ – $9$ then A–F for $10$ – $15$ ).

Conventions used throughout these notes: a subscript gives the base, e.g. $(1011)_{2}$ . Bits are written MSB first, so in an $n$ -bit word $b_{n - 1}$ is the MSB and $b_{0}$ is the LSB.

VALUE OF A POSITIONAL NUMBER

N = i = - m \sum n - 1 d_{i} r^{i}, 0 \leq d_{i} \leq r - 1

Here $n$ is the number of integer digits $d_{n - 1} \dots d_{0}$ and $m$ the number of fraction digits $d_{- 1} \dots d_{- m}$ . Every digit must be smaller than the base.

RANGE OF AN N-DIGIT UNSIGNED INTEGER; DIGITS NEEDED

0 \leq N \leq r^{n} - 1, n_{m i n} = ⌈ lo g_{r} (N + 1) ⌉ (N \geq 1)

An $n$ -digit base- $r$ integer takes $r^{n}$ distinct values. In bits, $n_{m i n} = ⌈ lo g_{2} (N + 1)⌉$ . For example, 256 needs 9 bits because $2^{8} - 1 = 255$ . The formula needs $N \geq 1$ ; the value 0 still takes one digit.

Conversion procedures

Base $r$ to decimal: expand with the weights $r^{i}$ and add.
Decimal integer to base $r$ : divide by $r$ repeatedly. The remainders, read from the LAST to the first, are the digits (the first remainder is the least significant digit).
Decimal fraction to base $r$ : multiply the fraction by $r$ repeatedly. The integer parts, read from the FIRST to the last, are the digits (the first integer part is the digit just right of the point). Stop when the fraction becomes 0 or you have enough digits.
Binary to octal or hex: group the bits in 3s (octal) or 4s (hex) outward from the binary point, leftward for the integer part and rightward for the fraction. Pad with 0s at the outer ends, then replace each group by its digit.
Octal or hex to binary: replace each digit by its 3-bit or 4-bit group. To go between octal and hex, pass through binary.
Bases that are powers of a common base (2, 8 and 16; or 3 and 9) convert by grouping digits in the same way. Between any other two bases (for example base 5 to base 7), convert through decimal.

WORKED EXAMPLE

Convert $(157.6875)_{10}$ to binary, octal and hexadecimal.

Solution

Integer part, by repeated division by 2: the remainders for 157 are 1, 0, 1, 1, 1, 0, 0, 1 (LSB first). Reading them from the last one gives $157 = (10011101)_{2}$ .
Fraction part, by repeated multiplication by 2: $0.6875 \times 2 = 1.375$ (1), $0.375 \times 2 = 0.75$ (0), $0.75 \times 2 = 1.5$ (1), $0.5 \times 2 = 1.0$ (1). Reading these from the first one gives $0.6875 = (0.1011)_{2}$ .
So $(157.6875)_{10} = (10011101.1011)_{2}$ .
Octal: group in 3s from the point, which gives $010011101.101100$ , i.e. $(235.54)_{8}$ .
Hex: group in 4s, which gives $10011101.1011$ , i.e. $(9 D.B)_{16}$ .
Check: $2 \cdot 64 + 3 \cdot 8 + 5 = 157$ and $5/8 + 4/64 = 0.6875$ .

Answer: $(10011101.1011)_{2} = (235.54)_{8} = (9 D.B)_{16}$

EXAM TIP

A decimal fraction has a terminating binary expansion if and only if its denominator, in lowest terms, is a power of 2. $0.1 = 1/10$ does not terminate: $(0.1)_{10} = (0.000110011 \dots)_{2}$ , with the block 0011 repeating forever after the first 0. Any finite binary format therefore stores 0.1 rounded.

EXAM TIP

Unknown-base problems: expand both sides with their weights, solve, and reject any root that is not an integer larger than every digit that appears. For example, $(132)_{b} = (42)_{10}$ gives $b^{2} + 3 b + 2 = 42$ , i.e. $(b + 8) (b - 5) = 0$ , so $b = 5$ . This is valid because every digit is below 5.

R'S AND (R − 1)'S COMPLEMENTS OF AN N-DIGIT BASE-R NUMBER

r ’s complement of N = r^{n} - N, (r - 1) ’s complement of N = (r^{n} - 1) - N

$N$ is an $n$ -digit base- $r$ integer (leading 0s count towards $n$ ). The $(r - 1)$ 's complement replaces every digit $d$ by $(r - 1) - d$ ; adding 1 to it gives the $r$ 's complement. For $N = 0$ the $r$ 's complement $r^{n}$ has $n + 1$ digits; dropping the extra digit leaves 0. If $N$ also has $m$ fraction digits, its $(r - 1)$ 's complement is $r^{n} - r^{- m} - N$ . Examples: the 9's and 10's complements of $3250$ are $6749$ and $6750$ ; the 7's and 8's complements of $(325)_{8}$ are $(452)_{8}$ and $(453)_{8}$ . With $r = 2$ these are the 1's and 2's complements.

Unsigned subtraction $M - N$ with complements ( $M$ and $N$ both written with $n$ digits)

With the $r$ 's complement: form $M + (r^{n} - N)$ . If a carry comes out of the leftmost digit (the end carry), then $M \geq N$ : drop the carry, and what remains is $M - N$ . If there is no end carry, then $M < N$ : the sum is the $r$ 's complement of $N - M$ , so take its $r$ 's complement and attach a minus sign.
With the $(r - 1)$ 's complement: form $M + (r^{n} - 1 - N)$ . If there is an end carry, add it back into the least significant digit (the end-around carry) to get $M - N$ . If there is none, the answer is minus the $(r - 1)$ 's complement of the sum.
Example: $72532 - 03250$ in 5 decimal digits. The 10's complement of $03250$ is $96750$ , and $72532 + 96750 = 169282$ . Dropping the end carry leaves $69282$ .

Unsigned and signed integers

An $n$ -bit unsigned integer is simply the positional value of $b_{n - 1} \dots b_{0}$ . Signed integers use the MSB as the sign ( $0$ positive, $1$ negative), under one of three conventions. All three store positive numbers identically; they differ only for negative numbers.

These notes use 2's complement for signed numbers unless a question says otherwise. $\overline{b}$ denotes the complement (inversion) of bit $b$ , and $\overline{N}$ denotes the word $N$ with every bit inverted.

VALUE OF AN N-BIT 2'S-COMPLEMENT WORD

N = - b_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 b_{i} 2^{i}

The MSB has weight $- 2^{n - 1}$ . Equivalently, when the MSB is 1, value $=$ (unsigned value) $- 2^{n}$ . For example, $1011001 1_{2} = 179 - 256 = - 77$ .

RANGES FOR N BITS

Unsigned: 2’s complement: Sign-magnitude, 1’s complement: 0 to 2^{n} - 1 - 2^{n - 1} to 2^{n - 1} - 1 - (2^{n - 1} - 1) to 2^{n - 1} - 1

For $n = 8$ : unsigned is 0 to 255, 2's complement is $- 128$ to $+ 127$ , and the other two are $- 127$ to $+ 127$ (each has two codes for zero).

NEGATION (COMPLEMENT) RULES

[- N]_{2’s} = 2^{n} - N = \overline{N} + 1, [- N]_{1’s} = 2^{n} - 1 - N = \overline{N}

$N$ and the results are read as $n$ -bit unsigned values, and the carry out of bit $n - 1$ is dropped (the arithmetic is modulo $2^{n}$ ). So in 2's complement, negating $0$ gives $0$ back; in 1's complement it gives $11 \dots 1$ , the second code for zero. In 2's complement, negating $- 2^{n - 1}$ gives $- 2^{n - 1}$ back (an overflow), because $+ 2^{n - 1}$ has no $n$ -bit code.

Property ( $n$ bits)	Sign-magnitude	1's complement	2's complement
Negative of $N$	flip the sign bit only	invert every bit: $(2^{n} - 1) - N$	invert every bit, add 1: $2^{n} - N$
Range	$- (2^{n - 1} - 1)$ to $+ (2^{n - 1} - 1)$	$- (2^{n - 1} - 1)$ to $+ (2^{n - 1} - 1)$	$- 2^{n - 1}$ to $+ (2^{n - 1} - 1)$
Codes for zero	two: $00 \dots 0$ and $10 \dots 0$	two: $00 \dots 0$ and $11 \dots 1$	one
Distinct values	$2^{n} - 1$	$2^{n} - 1$	$2^{n}$
$- 5$ in 8 bits	$10000101$	$11111010$	$11111011$
Weight of the MSB	sign only (no weight)	$- (2^{n - 1} - 1)$	$- 2^{n - 1}$
Addition	same signs: add the magnitudes and keep the sign; different signs: subtract the smaller magnitude from the larger and take the sign of the larger	add; a carry out of the MSB is added back into the LSB (end-around carry)	add; the carry out of the MSB is discarded
Sign extension to more bits	keep the sign bit as the new MSB, fill the new magnitude bits with 0s	copy the MSB into every new bit	copy the MSB into every new bit

Working rules for 2's complement

Negating by hand: scan from the LSB, copy every bit up to and including the first 1, then invert all the remaining bits. For example, $01101000$ ( $+ 104$ ) becomes $10011000$ ( $- 104$ ).
Reading a negative word: either subtract $2^{n}$ from its unsigned value, or negate it to get the magnitude.
Sign extension from $n$ to $m$ bits: copy the MSB into the $m - n$ new bits. So $1011$ ( $- 5$ ) becomes $11111011$ and $0101$ ( $+ 5$ ) becomes $00000101$ . Padding a negative number with 0s changes its value.
Truncation to fewer bits keeps the value only if every discarded bit equals the new MSB.
Arithmetic shifts: a left shift by one bit multiplies by 2, provided the two most significant bits were equal before the shift (otherwise the result overflows). An arithmetic right shift (the MSB is copied into the vacated bit) divides by 2 and rounds towards $- \infty$ : $1011$ ( $- 5$ ) becomes $1101$ ( $- 3$ ), not $- 2$ .

FIXED-POINT VALUE (2'S COMPLEMENT, F FRACTION BITS)

x = (- b_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 b_{i} 2^{i}) \times 2^{- f}

The binary point sits $f$ bits from the right. The range is $- 2^{n - 1 - f}$ to $2^{n - 1 - f} - 2^{- f}$ in uniform steps of $2^{- f}$ . For the same number of bits, floating point gives up this uniform step in exchange for a far wider range.

EXAM TIP

The 2's-complement range is asymmetric: it holds one more negative value than positive ones. The most negative word, e.g. $10000000 = - 128$ in 8 bits, is its own 2's complement, so $+ 128$ cannot be formed in 8 bits. Questions about the minimum number of bits for a negative value turn on this: $- 128$ fits in 8 bits, but $+ 128$ needs 9.

Addition, subtraction and overflow

With 2's complement, one binary adder serves signed and unsigned numbers alike: add the words, keep $n$ bits and discard the carry out of the MSB. Subtraction $A - B$ is done as $A + \overline{B} + 1$ (invert $B$ and set the adder's carry-in to 1).

The $n$ -bit result is correct whenever the true result lies within the range. When it does not, the stored bits are wrong and the condition is called overflow. Overflow depends on how the bits are interpreted: one carry pattern can be an unsigned overflow and a correct signed result, or the other way round.

Carry convention used here: stage $i$ adds $a_{i}$ , $b_{i}$ and the incoming carry $C_{i}$ , and produces $C_{i + 1}$ . So $C_{n - 1}$ is the carry into the MSB stage and $C_{n}$ is the carry out of it.

SIGNED (2'S-COMPLEMENT) OVERFLOW FLAG

V = C_{n} \oplus C_{n - 1}

Overflow occurs exactly when the carry into the MSB differs from the carry out of it. This holds for addition and for $A + \overline{B} + 1$ alike.

OVERFLOW FROM THE SIGN BITS

V = a_{n - 1} b_{n - 1} \overline{s_{n - 1}} + \overline{a_{n - 1}} \overline{b_{n - 1}} s_{n - 1}

$a_{n - 1}$ and $b_{n - 1}$ are the sign bits of the two words entering the adder, and $s_{n - 1}$ is the sign bit of the sum. In words: two operands of the same sign produced a sum of the other sign. Adding operands of opposite signs can never overflow. For $A - B$ , use the sign bit of $\overline{B}$ , the word the adder actually receives.

UNSIGNED CARRY AND BORROW

unsigned overflow in A + B = C_{n}, borrow in A - B = \overline{C_{n}}

When $A - B$ is computed as $A + \overline{B} + 1$ , $C_{n} = 1$ means $A \geq B$ (no borrow) and $C_{n} = 0$ means $A < B$ .

WORKED EXAMPLE

In 8-bit 2's-complement arithmetic, compute (a) $(+ 100) + (+ 50)$ , (b) $(- 100) + (- 50)$ , (c) $(+ 100) + (- 50)$ . For each, give the 8-bit result, $C_{7}$ (carry into the MSB), $C_{8}$ (carry out of the MSB), and whether signed overflow occurs.

Solution

Codes: $+ 100 = 01100100$ and $+ 50 = 00110010$ . $- 100 = 256 - 100 = 156 = 10011100$ and $- 50 = 256 - 50 = 206 = 11001110$ .
(a) $01100100 + 00110010 = 10010110$ . The lower 7 bits sum to $100 + 50 = 150 \geq 128$ , so $C_{7} = 1$ . The MSB stage adds $0 + 0 + 1$ , so $C_{8} = 0$ and $V = 1 \oplus 0 = 1$ . The result reads $150 - 256 = - 106$ : two positives gave a negative. The true sum, 150, exceeds 127.
(b) $10011100 + 11001110 = 101101010$ . The lower 7 bits sum to $28 + 78 = 106 < 128$ , so $C_{7} = 0$ . The MSB stage adds $1 + 1 + 0$ , so $C_{8} = 1$ and $V = 1$ . The kept 8 bits read $+ 106$ , although the true sum is $- 150 < - 128$ .
(c) $01100100 + 11001110 = 100110010$ . The lower 7 bits sum to $100 + 78 = 178 \geq 128$ , so $C_{7} = 1$ . The MSB stage adds $0 + 1 + 1$ , so $C_{8} = 1$ and $V = 1 \oplus 1 = 0$ . The kept 8 bits are $00110010 = + 50$ , which is correct; the carry out is simply discarded.

Answer: (a) $10010110$ , overflow. (b) $01101010$ , overflow. (c) $00110010 = + 50$ , no overflow, even though there is a carry out of the MSB.

EXAM TIP

A carry out of the MSB is not the same thing as overflow. For signed numbers, test $C_{n} \oplus C_{n - 1}$ (or the sign rule). For unsigned numbers, test $C_{n}$ alone. A frequent trap is a sum of opposite-sign numbers with $C_{n} = 1$ : the unsigned sum has overflowed, but the signed result is correct.

EXAM TIP

1's-complement addition: if a carry leaves the MSB, add it back into the LSB (the end-around carry). For $(+ 6) + (- 2)$ in 4 bits: $0110 + 1101 = 10011$ , and adding the end-around carry gives $0011 + 1 = 0100 = + 4$ .

BCD, excess-3, 2421 and Gray codes

A code assigns a bit pattern to each symbol; the whole pattern is not necessarily a positional number. A code is weighted when each bit position carries a fixed weight and a digit's value is the sum of the weights of its 1 bits.

BCD (8421) encodes each decimal digit separately in 4 bits with weights 8, 4, 2, 1. The six patterns $1010$ to $1111$ are unused (invalid).
Excess-3 is the BCD code of each digit plus $0011$ . It is unweighted and self-complementing: inverting every bit of a digit's code gives the code of its 9's complement.
2421 is a weighted code with weights 2, 4, 2, 1. Its self-complementing form codes 0 to 4 as $0000$ to $0100$ and 5 to 9 as $1011$ to $1111$ .
Gray code is a unit-distance code: consecutive values differ in exactly one bit. The $n$ -bit reflected Gray code is also cyclic, so the last value and 0 differ in one bit too.

Decimal	BCD (8421)	Excess-3	Binary	Gray
0	0000	0011	0000	0000
1	0001	0100	0001	0001
2	0010	0101	0010	0011
3	0011	0110	0011	0010
4	0100	0111	0100	0110
5	0101	1000	0101	0111
6	0110	1001	0110	0101
7	0111	1010	0111	0100
8	1000	1011	1000	1100
9	1001	1100	1001	1101
10	0001 0000	0100 0011	1010	1111
11	0001 0001	0100 0100	1011	1110
12	0001 0010	0100 0101	1100	1010
13	0001 0011	0100 0110	1101	1011
14	0001 0100	0100 0111	1110	1001
15	0001 0101	0100 1000	1111	1000

BINARY TO GRAY

g_{n - 1} = b_{n - 1}, g_{i} = b_{i + 1} \oplus b_{i} (i = n - 2, \dots, 0)

Equivalently, $G = B \oplus (B ≫ 1)$ , where $B ≫ 1$ is $B$ shifted right by one bit with a 0 entering at the MSB. It takes $n - 1$ XOR gates and involves no carries. Example: $B = 10110110$ gives $G = 10110110 \oplus 01011011 = 11101101$ .

GRAY TO BINARY

b_{n - 1} = g_{n - 1}, b_{i} = b_{i + 1} \oplus g_{i} = g_{n - 1} \oplus g_{n - 2} \oplus \dots \oplus g_{i}

Work from the MSB down. Each binary bit is the XOR of the Gray bit at that position with the binary bit just found on its left. Equivalently, $b_{i}$ is the parity of all Gray bits from the MSB down to position $i$ .

BCD addition, one decimal digit at a time

Add the two BCD digits, plus any carry from the previous digit, as ordinary 4-bit binary.
If the 4-bit sum exceeds $1001$ (9), or a carry comes out of the 4-bit group, add $0110$ (6) to that digit.
Send the carry from the correction (or the original carry) on to the next decimal digit.
The correction condition as logic: $C = K + Z_{8} Z_{4} + Z_{8} Z_{2}$ , where $K$ is the binary carry out of the group and $Z_{8} Z_{4} Z_{2} Z_{1}$ is the 4-bit binary sum. $C$ is also the decimal carry passed to the next digit.

WORKED EXAMPLE

Add the decimal numbers 58 and 67 in BCD, showing every correction.

Solution

In BCD, $58 = 01011000$ and $67 = 01100111$ .
Units: $1000 + 0111 = 1111$ (15). This exceeds 9, so add $0110$ : $1111 + 0110 = 10101$ . The units digit is $0101$ (5), with a carry of 1.
Tens: $0101 + 0110 + 1 = 1100$ (12). This exceeds 9, so add $0110$ : $1100 + 0110 = 10010$ . The tens digit is $0010$ (2), with a carry of 1.
Hundreds: the carry gives $0001$ .

Answer: $000100100101$ , which is 125 in BCD.

EXAM TIP

BCD is read digit by digit. $01001001$ in BCD is 49, not 73 (73 is its value read as plain binary). BCD also needs more bits than binary: 8 bits of BCD reach only 99, against 255 in binary.

EXAM TIP

Self-complementing codes (excess-3, 2421) let a 9's-complement circuit be built from inverters alone. Check with excess-3: 2 is $0101$ , and inverting it gives $1010$ , which is 7 in excess-3. Indeed $9 - 2 = 7$ . A weighted code can be self-complementing only if its weights add up to 9, because the codes of $d$ and $9 - d$ between them contain every weight exactly once. The 2421 weights add to 9; the 8421 weights add to 15, so BCD is not self-complementing.

EXAM TIP

Gray code is used wherever several bits would otherwise change at once and a momentary mixed reading would be wrong, such as shaft and position encoders or counters read from another clock domain. The K-map row and column order 00, 01, 11, 10 is the 2-bit Gray code.

IEEE 754 floating point

A floating-point number stores a sign, an exponent and a significand, like scientific notation in base 2. IEEE 754 single precision (32 bits) holds, from MSB to LSB:

the sign $S$ (1 bit, $1$ = negative);
the biased exponent $E$ (8 bits, stored as an unsigned number);
the fraction $F$ (23 bits).

A normalized number has the significand $1. F$ . Its leading 1 is not stored (the hidden bit), which gives 24 bits of precision. The exponent carries a bias of 127, so the true exponent is $E - 127$ . The codes $E = 0$ and $E = 255$ are reserved for zero, denormals, infinity and NaN.

SINGLE PRECISION: NORMALIZED VALUE

x = (- 1)^{S} \times (1. F)_{2} \times 2^{E - 127}, 1 \leq E \leq 254

$(1. F)_{2} = 1 + \sum_{i = 1}^{23} f_{i} 2^{- i}$ , where $f_{1}$ is the fraction MSB. The true exponent runs from $- 126$ to $+ 127$ .

SINGLE PRECISION: DENORMAL (SUBNORMAL) VALUE

x = (- 1)^{S} \times (0. F)_{2} \times 2^{- 126}, E = 0, F \neq = 0

There is no hidden 1, and the exponent is fixed at $- 126$ , not $0 - 127 = - 127$ . Denormals fill the gap between 0 and the smallest normalized number in equal steps of $2^{- 149}$ .

Exponent field $E$	Fraction $F$	Meaning
$0$	$0$	$\pm 0$ (the sign bit gives $+ 0$ or $- 0$ )
$0$	$\neq = 0$	denormal: $(- 1)^{S} \times 0. F \times 2^{- 126}$
$1$ to $254$	any	normalized: $(- 1)^{S} \times 1. F \times 2^{E - 127}$
$255$	$0$	$\pm \infty$
$255$	$\neq = 0$	NaN (not a number), the result of e.g. $0/0$ or $\infty - \infty$

LARGEST AND SMALLEST POSITIVE SINGLE-PRECISION VALUES

x_{m a x} x_{m i n, norm} x_{m a x, denorm} x_{m i n, denorm} = (2 - 2^{- 23}) \times 2^{127} \approx 3.40 \times 1 0^{38} = 2^{- 126} \approx 1.18 \times 1 0^{- 38} = (1 - 2^{- 23}) \times 2^{- 126} = 2^{- 149} \approx 1.40 \times 1 0^{- 45}

$x_{m a x}$ has $E = 254$ and $F$ all 1s (hex 7F7FFFFF). $x_{m i n, norm}$ has $E = 1$ , $F = 0$ (hex 00800000). $x_{m i n, denorm}$ has $E = 0$ and $F = 0 \dots 01$ (hex 00000001). The negative values mirror these with $S = 1$ .

SPACING OF NORMALIZED NUMBERS

gap between neighbours in [2^{e}, 2^{e + 1}) = 2^{e - 23} (- 126 \leq e \leq 127), gap just above 1 = 2^{- 23}

The gap doubles with each power of 2. Absolute resolution therefore worsens as magnitude grows, while the relative gap between neighbours stays between $2^{- 24}$ and $2^{- 23} \approx 1.19 \times 1 0^{- 7}$ . Below $2^{- 126}$ the denormals take over, with the fixed gap $2^{- 149}$ .

EXPONENT BIAS; DOUBLE PRECISION

bias = 2^{k - 1} - 1, x_{double} = (- 1)^{S} \times (1. F)_{2} \times 2^{E - 1023}, 1 \leq E \leq 2046

$k$ is the number of exponent bits: $k = 8$ gives 127 and $k = 11$ gives 1023. Double precision has 1 sign bit, 11 exponent bits and 52 fraction bits, and its denormals use $2^{- 1022}$ . A question that defines its own format, with a stated bias or a different significand convention (for example $0.1 F$ with no hidden bit), overrides these values.

Encoding a decimal number in single precision

Set $S$ from the sign.
Convert the magnitude to binary (integer and fraction parts separately).
Normalize to $1. xxx \times 2^{e}$ by moving the binary point.
Store $E = e + 127$ as an 8-bit unsigned number.
Store the bits after the point as $F$ , left-aligned and padded on the right with 0s to 23 bits. The leading 1 is dropped.
Write the 32 bits as $S ∣ E ∣ F$ and group them in 4s to read the hex.

WORKED EXAMPLE

Give the IEEE 754 single-precision encoding of $- 13.625$ in hexadecimal.

Solution

$S = 1$ , since the number is negative.
$13 = 110 1_{2}$ . For $0.625$ : $0.625 \times 2 = 1.25$ (1), $0.25 \times 2 = 0.5$ (0), $0.5 \times 2 = 1.0$ (1), so $0.625 = 0.10 1_{2}$ . Hence $13.625 = 1101.10 1_{2}$ .
Normalize: $1101.101 = 1.101101 \times 2^{3}$ , so $e = 3$ .
$E = 3 + 127 = 130 = 1000001 0_{2}$ .
$F = 101101$ followed by 17 zeros (the leading 1 is hidden).
The word is $11000001010110100000000000000000$ . In groups of 4 it reads $11000001010110100000000000000000$ .

Answer: C15A0000 in hex.

WORKED EXAMPLE

Decode the single-precision words (a) 3F600000 and (b) 80400000 (hex).

Solution

(a) $00111111011000000000 \dots$ splits into $S = 0$ , $E = 01111110 = 126$ and $F = 1100 \dots 0$ .
$E$ lies between 1 and 254, so the number is normalized: $x = + 1.1 1_{2} \times 2^{126 - 127} = 1.75 \times 2^{- 1} = 0.875$ .
(b) $10000000010000000000 \dots$ splits into $S = 1$ , $E = 00000000$ and $F = 1000 \dots 0$ .
$E = 0$ with $F \neq = 0$ means a denormal: no hidden 1, and the exponent is $- 126$ . So $x = - 0. 1_{2} \times 2^{- 126} = - 2^{- 127} \approx - 5.88 \times 1 0^{- 39}$ .
Reading (b) as a normalized number with exponent $0 - 127$ would give $- 1.5 \times 2^{- 127}$ , which is wrong.

Answer: (a) $0.875$ . (b) $- 2^{- 127} \approx - 5.88 \times 1 0^{- 39}$ , a denormal.

EXAM TIP

Common slips: using a bias of 128 instead of 127; forgetting the hidden 1, or adding a hidden 1 to a denormal; treating the exponent field as 2's complement (it is unsigned and biased); packing $F$ right-aligned instead of left-aligned.

EXAM TIP

Floating-point addition can absorb a small operand completely. In single precision, $2^{24} + 1$ rounds back to $2^{24}$ (round to nearest, ties to even), because the gap between neighbours at $2^{24}$ is $2^{24 - 23} = 2$ . For the same reason, floating-point addition is not associative: $(2^{24} + 1) + 1$ gives $2^{24}$ , while $2^{24} + (1 + 1)$ gives $2^{24} + 2$ .

Parity and error-detecting codes

A parity bit makes the number of 1s in the transmitted word even (even parity) or odd (odd parity). The receiver recomputes the parity, and a mismatch reveals an error. A single parity bit detects any odd number of flipped bits and misses any even number. It cannot tell which bit is wrong, so it detects errors but cannot correct them.

PARITY BIT

P_{even} = d_{1} \oplus d_{2} \oplus \dots \oplus d_{m}, P_{odd} = \overline{P_{even}}

To check, XOR all $m + 1$ received bits; with even parity, a result of 1 flags an error. An XOR tree with $m$ inputs needs $m - 1$ two-input XOR gates.

MINIMUM DISTANCE OF A CODE

detect up to s errors: d_{m i n} \geq s + 1, correct up to t errors: d_{m i n} \geq 2 t + 1

$d_{m i n}$ is the smallest number of bit positions in which any two valid code words differ. To correct up to $t$ errors and also detect up to $s$ errors ( $s \geq t$ ), $d_{m i n} \geq t + s + 1$ . Single parity has $d_{m i n} = 2$ , so it detects 1 error and corrects none.

CHECK BITS FOR A SINGLE-ERROR-CORRECTING HAMMING CODE

2^{p} \geq m + p + 1

$m$ is the number of data bits and $p$ the number of check bits, and you take the smallest $p$ that satisfies the inequality. $m = 4$ needs $p = 3$ (the (7,4) code) and $m = 8$ needs $p = 4$ . $m = 16$ needs $p = 5$ , not 4, because $2^{4} = 16 < 21$ . In the usual layout the check bits sit at positions 1, 2, 4, 8, … (numbered from 1), and the recomputed checks (the syndrome), read as a binary number, give the position of a single flipped bit, with 0 meaning no error. The Hamming code has $d_{m i n} = 3$ ; adding one overall parity bit raises it to 4, so the extended code corrects 1 error and detects 2.

EXAM TIP

The even-parity bit of a word is the XOR of its bits, so these questions reduce to counting 1s. $10110110$ has five 1s, so its even-parity bit is 1 and its odd-parity bit is 0.

PREVIOUS-YEAR QUESTIONS

5 questions from the EC and IN papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE ECE 2026 · GATE ECE 2024 · GATE ECE 2020 · GATE IN 2025 · GATE IN 2018

GATE 2026 EC Q.45

GATE 2026 · ECQ.45 · 2 marks · MCQ

What is the $1 0^{'} s$ complement of $(47)_{10}$ ?

(A)
52
(B)
53
(C)
54
(D)
55

Answer and solution

GATE 2026 EC Q.45: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 EC Q.45: answer and solution

GATE 2025 IN Q.18

GATE 2025 · INQ.18 · 1 mark · MCQ

The 4-bit signed 2's complement form of $(5)_{10} + (5)_{10}$ is

(A)
$(- 6)_{10}$
(B)
$(- 7)_{10}$
(C)
$(- 5)_{10}$
(D)
$(- 8)_{10}$

Answer and solution

GATE 2025 IN Q.18: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 IN Q.18: answer and solution

GATE 2024 EC Q.29

GATE 2024 · ECQ.29 · 1 mark · NAT

In a number system of base $r$ , the equation $x^{2} - 12 x + 37 = 0$ has $x = 8$ as one of its solutions. The value of $r$ is ________.

Answer and solution

GATE 2024 EC Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 EC Q.29: answer and solution

GATE 2020 EC Q.38

GATE 2020 · ECQ.38 · 2 marks · MCQ

P, Q, and R are the decimal integers corresponding to the 4-bit binary number 1100 considered in signed magnitude, 1's complement, and 2's complement representations, respectively. The 6-bit 2's complement representation of (P + Q + R) is

(A)
110101
(B)
110010
(C)
111101
(D)
111001

Answer and solution

GATE 2020 EC Q.38: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 EC Q.38: answer and solution

GATE 2018 IN Q.18

GATE 2018 · INQ.18 · 1 mark · MCQ

The representation of the decimal number $(27.625)_{10}$ in base-2 number system is

(A)
$11011.110$
(B)
$11101.101$
(C)
$11011.101$
(D)
$10111.110$

Answer and solution

GATE 2018 IN Q.18: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 IN Q.18: answer and solution

PRACTICE

7 questions to test yourself

PRACTICE 12 marks · MSQ

Each option shows two 8-bit 2's-complement operands (MSB first) that are added in an 8-bit adder, keeping 8 bits of the sum. Which of these additions produce signed overflow?

(A)
$01110000 + 00010000$
(B)
$10000001 + 11111111$
(C)
$10110000 + 11000000$
(D)
$01100100 + 10011100$

Answer and solution

Answer: (A), (C)

A: $112 + 16 = 128 > 127$ . The sum $10000000$ reads $- 128$ , and two positives gave a negative: overflow.
B: $- 127 + (- 1) = - 128$ , which is in range. The sum is $10000000 = - 128$ (the carry out is discarded): no overflow.
C: $- 80 + (- 64) = - 144 < - 128$ . The sum keeps $01110000 = + 112$ , and two negatives gave a positive: overflow.
D: $100 + (- 100) = 0$ . The sum is $00000000$ with a carry out of 1, but $C_{8} = C_{7} = 1$ , so $V = 0$ : no overflow. A carry out alone is not overflow.

PRACTICE 21 mark · MSQ

Which of the following statements are correct?

(A)
Excess-3 code is self-complementing: inverting every bit of a digit's code gives the code of its 9's complement.
(B)
In IEEE 754 single precision, a word whose exponent field is $11111111$ and whose fraction field is non-zero represents NaN.
(C)
A single even-parity bit detects every error in which exactly two bits of the word are flipped.
(D)
Sign-extending the 4-bit 2's-complement number $1010$ to 8 bits gives $00001010$ .

Answer and solution

Answer: (A), (B)

A is true. For example, 3 is $0110$ in excess-3; inverting gives $1001$ , which is 6 in excess-3, and $9 - 3 = 6$ .
B is true: $E = 255$ with $F \neq = 0$ is NaN, and $E = 255$ with $F = 0$ is infinity.
C is false. Two flips leave the number of 1s even, so the parity check passes and the error goes undetected.
D is false. $1010$ is $- 6$ , and sign extension copies the MSB, giving $11111010$ . The word $00001010$ is $+ 10$ .

PRACTICE 31 mark · NAT

A single-error-correcting Hamming code protects 11 data bits. The minimum number of check bits needed is ______.

Answer and solution

Answer: $4$

The smallest $p$ with $2^{p} \geq m + p + 1$ is needed, with $m = 11$ .
$p = 3$ : $2^{3} = 8$ , but $11 + 3 + 1 = 15$ , so $8 \geq 15$ fails.
$p = 4$ : $2^{4} = 16$ and $11 + 4 + 1 = 16$ , so $16 \geq 16$ holds.
So $p = 4$ , which gives the (15, 11) code.

PRACTICE 41 mark · NAT

The 8-bit word $11010110$ (MSB first) is read as a 2's-complement integer $x$ and as a sign-magnitude integer $y$ . The value of $x - y$ is ______.

Answer and solution

Answer: $44$

Unsigned value $= 128 + 64 + 16 + 4 + 2 = 214$ .
2's complement: the MSB is 1, so $x = 214 - 256 = - 42$ .
Sign-magnitude: the sign bit is 1 and the magnitude is $101011 0_{2} = 64 + 16 + 4 + 2 = 86$ , so $y = - 86$ .
$x - y = - 42 - (- 86) = 44$ .

PRACTICE 51 mark · MCQ

The 8-bit Gray-code word $10110101$ (MSB first) corresponds to which binary number?

(A)
$11011001$
(B)
$11101111$
(C)
$10010110$
(D)
$01001010$

Answer and solution

Answer: (A)

$b_{7} = g_{7} = 1$ .
Each following bit is $b_{i} = b_{i + 1} \oplus g_{i}$ : $b_{6} = 1 \oplus 0 = 1$ , $b_{5} = 1 \oplus 1 = 0$ , $b_{4} = 0 \oplus 1 = 1$ , $b_{3} = 1 \oplus 0 = 1$ , $b_{2} = 1 \oplus 1 = 0$ , $b_{1} = 0 \oplus 0 = 0$ , $b_{0} = 0 \oplus 1 = 1$ .
Binary $= 11011001$ . Check: $11011001 \oplus 01101100 = 10110101$ , the given Gray word.
Option B is what you get by wrongly applying the binary-to-Gray rule to the Gray word.

PRACTICE 62 marks · NAT

$X$ and $Y$ are IEEE 754 single-precision numbers whose 32-bit encodings, in hexadecimal, are $X = 41 A 40000$ and $Y = C0D 80000$ . The decimal value of $X + Y$ is ______.

Answer and solution

Answer: $13.75$ (accepted range $\pm 0.001$ )

$X$ : $01000001101001000000 \dots$ splits into $S = 0$ , $E = 10000011 = 131$ , $F = 010010 \dots 0$ . So $X = + 1.0100 1_{2} \times 2^{131 - 127} = 1.28125 \times 16 = 20.5$ .
$Y$ : $11000000110110000000 \dots$ splits into $S = 1$ , $E = 10000001 = 129$ , $F = 10110 \dots 0$ . So $Y = - 1.101 1_{2} \times 2^{129 - 127} = - 1.6875 \times 4 = - 6.75$ .
$X + Y = 20.5 - 6.75 = 13.75$ .

PRACTICE 71 mark · MCQ

The 16's complement of the 4-digit hexadecimal number $(3 A 0 C)_{16}$ is

(A)
$(C5F3)_{16}$
(B)
$(C5F4)_{16}$
(C)
$(C6F4)_{16}$
(D)
$(C4F4)_{16}$

Answer and solution

Answer: (B)

The 15's complement subtracts every digit from F: $F - 3 = C$ , $F - A = 5$ , $F - 0 = F$ , $F - C = 3$ , giving $(C5F3)_{16}$ .
The 16's complement is the 15's complement plus 1: $(C5F4)_{16}$ .
Check: $(3 A 0 C)_{16} + (C5F4)_{16} = (10000)_{16} = 1 6^{4}$ , as $1 6^{n} - N$ requires.
Option A is the 15's complement (the $+ 1$ is missing).

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE EC

Number Representations: Binary, integer and floating-point- numbers

GATE IN

Basics of number systems

Preparing in Kolkata? IAE Academy's course for GATE ECE or GATE IN.