2.2 Combinational and Arithmetic Circuits

What the syllabus asks you to cover

Multiplexetures, Demultiplexetures, Decoder, Encoder, Binary Addition, Binary Subtraction, operation on Unsigned and Signed Binary Numbers.

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:

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

We know that subtraction can be represented as:

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

Step-by-step:

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:

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:

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.

Pause and recall

Without looking back, explain the main idea, recall a key definition or formula, and describe when it applies. Include assumptions and units where relevant. Revisit any step you could not explain.

What the syllabus asks you to cover

Multiplexetures, Demultiplexetures, Decoder, Encoder, Binary Addition, Binary Subtraction, operation on Unsigned and Signed Binary Numbers.

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

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

We know that subtraction can be represented as:

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

Step-by-step:

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

We know that subtraction can be represented as:

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

Step-by-step:

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:

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:

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.

Pause and recall

Without looking back, explain the main idea, recall a key definition or formula, and describe when it applies. Include assumptions and units where relevant. Revisit any step you could not explain.