2.2 Combinational & Arithmetic Circuit

1. Multiplexers, Demultiplexers, Decoders, and Encoders

Multiplexers (MUX)

A multiplexer is a combinational circuit that selects one of many inputs and forwards it to a single output line.

• It has n data inputs, 1 output, and $\log_2(n)$ selection lines.

• Example: A 4-to-1 multiplexer has 4 data inputs, 1 output, and 2 selection lines ($S_1, S_0$).

Truth Table for 4-to-1 MUX:

$S_1$	$S_0$	Output
0	0	$D_0$
0	1	$D_1$
1	0	$D_2$
1	1	$D_3$

---

Demultiplexers (DEMUX)

A demultiplexer takes a single input and routes it to one of many output lines.

• It has 1 input, n outputs, and $\log_2(n)$ selection lines.

• Example: A 1-to-4 demultiplexer takes 1 input and routes it to one of the 4 output lines based on the selection lines ($S_1, S_0$).

Truth Table for 1-to-4 DEMUX:

$S_1$	$S_0$	$Y_0$	$Y_1$	$Y_2$	$Y_3$
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

---

Decoders

A decoder is a combinational circuit that decodes an $n$-bit input to a corresponding $2^n$ output.

• It converts binary information into a specific code.

• Example: A 2-to-4 decoder takes a 2-bit input and produces 4 outputs, with one of the outputs being 1 based on the input.

Truth Table for 2-to-4 Decoder:

$A_1$	$A_0$	$Y_0$	$Y_1$	$Y_2$	$Y_3$
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

---

Encoders

An encoder is the reverse of a decoder. It encodes an n-input into a $\log_2(n)$-bit output.

• Example: A 4-to-2 encoder takes 4 inputs and produces a 2-bit binary code corresponding to the active input.

Truth Table for 4-to-2 Encoder:

$D_3$	$D_2$	$D_1$	$D_0$	$A_1$	$A_0$
0	0	0	1	0	0
0	0	1	0	0	1
0	1	0	0	1	0
1	0	0	0	1	1

---

2. Binary Addition and Subtraction

Binary Addition

• Binary addition is similar to decimal addition but operates with base 2 (digits 0 and 1).

• Rules for binary addition:

  • 0 + 0 = 0

  • 0 + 1 = 1

  • 1 + 0 = 1

  • 1 + 1 = 10 (carry 1 to the next higher bit)

Binary Subtraction

• Binary subtraction follows the same concept as decimal subtraction.

• Rules for binary subtraction:

  • 0 - 0 = 0

  • 1 - 0 = 1

  • 10 - 1 = 1 (borrow 1 from the next higher bit)

  • 1 - 1 = 0

---

3. Operations on Signed and Unsigned Binary Numbers

Unsigned Binary Numbers

• In unsigned binary, all bits are used to represent the value. There is no sign bit, so the number can only represent non-negative values.

• Example: 1011 (binary) = 11 (decimal)

Signed Binary Numbers

• In signed binary, one bit is used as the sign bit, where 0 represents positive and 1 represents negative.

• Two's Complement Representation: Common method to represent signed binary numbers.

• To find the two's complement of a binary number, invert all bits and add 1 to the least significant bit (LSB).

Example: Representing -5 in 4-bit two’s complement:

• Step 1: Convert 5 to binary: 0101

• Step 2: Invert all bits: 1010

• Step 3: Add 1: 1011 (This is -5 in two's complement).

---

Complements in Binary and Decimal Systems

Complements are useful in binary and decimal systems for performing arithmetic operations like subtraction using addition. Below are the explanations for One's Complement, Two's Complement, Nine's Complement, and Ten's Complement.

---

Subtraction: ( 5 - 3 ) using Two's Complement

We know that subtraction can be represented as:

$$5 - 3 = 5 + (-3)$$

Step-by-step:

Step	Action	Explanation	Binary
1.	Represent 5 in binary	Convert 5 to binary (4 bits)	( 0101 )
2.	Convert 3 to binary	Convert 3 to binary (4 bits)	( 0011 )
3.	Two's complement of 3	Invert bits of 3 (0011) and add 1	Invert: ( 0011 to 1100 ), then add 1: ( 1100 + 1 = 1101 )
4.	Add 5 and -3	Perform binary addition of ( 0101 + 1101 )	( 10010 )
5.	Discard the carry	Ignore the carry-over (MSB is discarded)	The result after discarding the carry: ( 0010 )
6.	Final result	Interpret the result	( 0010 ) is the binary representation of ( 2 ). Thus, ( 5 - 3 = 2 ).

---

Subtraction: ( 3 - 5 ) using Two's Complement

We know that subtraction can be represented as:

$$3 - 5 = 3 + (-5)$$

Step-by-step:

Step	Action	Explanation	Binary
1.	Represent 3 in binary	Convert 3 to binary (4 bits)	( 0011 )
2.	Convert 5 to binary	Convert 5 to binary (4 bits)	( 0101 )
3.	Two's complement of 5	Invert bits of 5 (0101) and add 1	Invert: ( 0101 to 1010 ), then add 1: ( 1010 + 1 = 1011 )
4.	Add 3 and -5	Perform binary addition of ( 0011 + 1011 )	( 1110 )
5.	Interpret the result	Convert the result from two's complement to decimal	Since the MSB is 1, the number is negative. Invert ( 1110 to 0001 ), add 1: ( 0001 + 1 = 0010 ), which is 2. The result is negative, so it's ( -2 ). Thus, ( 3 - 5 = -2 ).

---

Summary Table:

Subtraction	Action	Binary Result	Decimal Result
( 5 - 3 )	( 5 + (-3) )	( 0010 )	( 2 )
( 3 - 5 )	( 3 + (-5) )	( 1110 )	( -2 )

Key Difference Between 1's & 2's Complement

In 1's complement, if there is a carry-out (i.e., an extra 1 in the 5th bit position), we discard the carry and add it back to the result (this is called end-around carry).

For 1's Complement:

• When the MSB is 1, the number is negative.

• To convert it to a positive value, you invert all the bits.

For 2's Complement:

• When the MSB is 1, the number is negative.

• To find the positive equivalent, you invert all the bits and add 1 to the result.

Key takeaway:

• MSB = 1 always indicates a negative number in both 1's complement and 2's complement.

• The difference is in how you process the negative number (invert bits and add 1 for 2's complement).

---

Subtraction: ( 5 - 3 ) using 10's Complement

We know that subtraction can be represented as:

$$5 - 3 = 5 + (-3)$$

Step-by-step:

Step	Action	Explanation	Decimal	Binary
1.	Represent 5 in binary	Convert 5 to binary (4 digits)	( 5 )	( 0101 )
2.	Represent 3 in binary	Convert 3 to binary (4 digits)	( 3 )	( 0011 )
3.	10's complement of 3	Find 9's complement and add 1: ( 9 - 3 = 6 ); then add 1: ( 6 + 1 = 7 )	( -3 )	( 0111 )
4.	Add 5 and -3	Add the binary of 5 and the 10's complement of 3: ( 0101 + 0111 )	( 5 + (-3) )	( 1100 )
5.	Interpret the result	Since there's no carry, the result is the answer	( 2 )	( 0010 )

Final result:

$$5 - 3 = 2 \quad \text{(in decimal, binary \( 0010 \))}$$

---

Subtraction: ( 3 - 5 ) using 10's Complement

We know that subtraction can be represented as:

$$3 - 5 = 3 + (-5)$$

Step-by-step:

Step	Action	Explanation	Decimal	Binary
1.	Represent 3 in binary	Convert 3 to binary (4 digits)	( 3 )	( 0011 )
2.	Represent 5 in binary	Convert 5 to binary (4 digits)	( 5 )	( 0101 )
3.	10's complement of 5	Find 9's complement and add 1: ( 9 - 5 = 4 ); then add 1: ( 4 + 1 = 5 )	( -5 )	( 0101 )
4.	Add 3 and -5	Add the binary of 3 and the 10's complement of 5: ( 0011 + 0101 )	( 3 + (-5) )	( 1000 )
5.	Interpret the result	Since the result is negative, invert ( 1000 ) (1's complement) to get ( 0111 ), then add 1: ( 0111 + 1 = 1000 ), so the result is ( -2 )	( -2 )	( 1110 )

Final result:

$$3 - 5 = -2 \quad \text{(in decimal, binary \( 1110 \))}$$

---

Summary Table:

Subtraction	Action	Binary Result	Decimal Result
( 5 - 3 )	( 5 + (-3) )	( 0010 )	( 2 )
( 3 - 5 )	( 3 + (-5) )	( 1110 )	( -2 )

---

Key Difference Between 9's & 10's Complement

In 9's complement, if there is a carry-out (i.e., an extra 1 in the 5th bit position), we discard the carry and add it back to the result (this is called end-around carry).

For 9's Complement:

• When the MSB is 1, the number is negative.

• To convert it to a positive value, you subtract each bit from 9. This means inverting each bit (for a 4-bit number, subtracting each bit from 9).

For 10's Complement:

• When the MSB is 1, the number is negative.

• To find the positive equivalent, you subtract each bit from 9, and then add 1 to the result. This is similar to how 2's complement works but with 9's complement instead.

Key takeaway:

• MSB = 1 always indicates a negative number in both 9's complement and 10's complement.

• The difference is in how you process the negative number:

  • 9's complement: Subtract each bit from 9.

  • 10's complement: Subtract each bit from 9 and add 1 to the result.

---

Conclusion

• Multiplexers (MUX), Demultiplexers (DEMUX), Decoders, and Encoders are essential components in digital circuits for managing data flow.

• A multiplexer selects one input from multiple inputs and forwards it to a single output based on the control signals (selection lines). A demultiplexer takes one input and routes it to one of several outputs based on the control signals (selection lines). It essentially performs the inverse operation of a multiplexer.

• Decoders convert binary inputs to specific outputs, and Encoders perform the reverse.

• Binary addition and subtraction follow base-2 rules with carry and borrow operations, similar to decimal.

• Complements (1's, 2's, 9's, and 10's) are techniques used to simplify subtraction in both binary and decimal systems by converting subtraction into addition.