GATE CS - DIGITAL LOGIC:Number Systems, Arithmetic Circuits and Floating Point

Mastering number systems, arithmetic circuits and floating point concepts and implementation.

Number Systems, Arithmetic Circuits and Floating Point

Binary Arithmetic

Addition

  0110  (6)
+ 0101  (5)
------
  1011  (11)

Sum bit = A ⊕ B ⊕ Cᵢₙ; Carry out = AB + ACᵢₙ + BCᵢₙ

Subtraction using 2's Complement

Subtraction A − B = A + (2's complement of B)

2's complement of B = flip all bits + 1

  0110  (6)
- 0011  (3)

2's complement of 3: 0011 → 1100 + 1 = 1101

  0110
+ 1101
------
 10011 → ignore carry, result = 0011 (3) ✓

Overflow Detection

Overflow occurs in signed arithmetic when:

Two positive numbers sum to a negative result
Two negative numbers sum to a positive result

Rule: Overflow = Carry into MSB ⊕ Carry out of MSB

4-bit signed: 0111 (7) + 0001 (1)
  0111
+ 0001
------
  1000  ← result = -8 in 2's complement (OVERFLOW!)
Carry_in to MSB = 1, Carry_out = 0, 1 ⊕ 0 = 1 → overflow detected

Adder Circuits

Half Adder

Inputs: A, B
Outputs: Sum = A ⊕ B, Carry = A·B
Cannot handle carry-in

Full Adder

Inputs: A, B, Cᵢₙ
Outputs: Sum = A ⊕ B ⊕ Cᵢₙ, Cₒᵤₜ = AB + Cᵢₙ(A ⊕ B)
Can be chained for multi-bit addition

Ripple Carry Adder (RCA)

Chain of n full adders
Carry propagates from LSB to MSB
Delay: O(n) gate delays
GATE fact: For n-bit RCA, worst case is n full adder delays

Carry Lookahead Adder (CLA)

Generate (G) and Propagate (P) for each bit:
G = A·B (generate a carry)
P = A ⊕ B (propagate an incoming carry)
Carry computed in parallel: C₁ = G₀ + P₀·C₀
Delay: O(log n) — significantly faster than RCA
GATE: CLA is faster but uses more hardware

Multiplexers and Demultiplexers

Multiplexer (MUX) — Function Realization

A 2ⁿ-to-1 MUX with n select lines can implement any Boolean function of (n+1) variables.

Example: Implement F(A,B,C) using a 4-to-1 MUX (2 select lines = A,B)

A	B	F(A,B,C)	Simplification	MUX Input
0	0	F = C (when A=0,B=0)	—	I₀ = C
0	1	F = 0 or 1? (depends on function)	—	I₁ = 0 or 1
1	0	F depends on C	—	I₂ = C or C'
1	1	F depends on C	—	I₃ = C or 0 or 1

GATE application: Any function can be implemented with a MUX of one size smaller by using one variable as data input.

IEEE 754 Floating Point (Single Precision)

32-bit format: 1 sign bit + 8 exponent bits + 23 mantissa bits

Bit: [31] [30..23] [22..0]
     Sign  Exponent  Mantissa (fraction)

Value = (−1)ˢ × 1.mantissa × 2^(exponent − 127)

The 127 bias means stored exponent = actual exponent + 127.

Example: Represent 12.5 in IEEE 754

12.5 in binary: 1100.1₂ = 1.1001 × 2³
Sign = 0 (positive)
Exponent = 3 + 127 = 130 = 10000010₂
Mantissa = 10010000000000000000000 (23 bits, implicit leading 1 dropped)

0  10000010  10010000000000000000000

Special Values

Pattern	Meaning
exp=0, mantissa=0	±0
exp=0, mantissa≠0	Denormalized (subnormal) numbers
exp=255, mantissa=0	±Infinity
exp=255, mantissa≠0	NaN (Not a Number)

GATE fact: Adding 1.0 to a sufficiently large float loses precision because the mantissa has limited bits. This is the representation error in floating point.

Practice Problems

Add 01101011 + 00110101 in binary. Detect overflow if treating as 8-bit signed.
Convert -37 to 8-bit 2's complement binary.
Implement F(A,B,C,D) = Σm(0,3,5,6,9,10,12,15) using a minimal MUX with A,B as select lines.
Express 0.1 in IEEE 754 single precision (hint: it's a repeating binary fraction).
In a 16-bit ripple carry adder, what is the worst-case number of gate delays if each full adder takes 3 gate delays?

Progress

Previous Complete Course