> For the complete documentation index, see [llms.txt](https://nec-license.gitbook.io/books/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nec-license.gitbook.io/books/2.-digital-logic-and-microprocessor/2.2-combinational-and-arithmetic-circuit.md). # 2.2 Combinational & Arithmetic Circuit ### 1. Multiplexers, Demultiplexers, Decoders, and Encoders 1. **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$$ | *** 2. **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 | *** 3. **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 | *** 4. **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 1. **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) 2. **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 1. **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) 2. **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**. *** 1. **Subtraction: ( 5 - 3 ) using Two's Complement** We know that subtraction can be represented as: * $$5 - 3 = 5 + (-3)$$ **Step-by-step:**
StepActionExplanationBinary
1.Represent 5 in binaryConvert 5 to binary (4 bits)( 0101 )
2.Convert 3 to binaryConvert 3 to binary (4 bits)( 0011 )
3.Two's complement of 3Invert bits of 3 (0011) and add 1

Invert: ( 0011 to 1100 ),

then add 1: ( 1100 + 1 = 1101 )

4.Add 5 and -3Perform binary addition of ( 0101 + 1101 )( 10010 )
5.Discard the carryIgnore the carry-over (MSB is discarded)The result after discarding the carry: ( 0010 )
6.Final resultInterpret the result

( 0010 ) is the binary representation of ( 2 ).

Thus, ( 5 - 3 = 2 ).

*** 2. **Subtraction: ( 3 - 5 ) using Two's Complement** We know that subtraction can be represented as: * $$3 - 5 = 3 + (-5)$$ **Step-by-step:**
StepActionExplanationBinary
1.Represent 3 in binaryConvert 3 to binary (4 bits)( 0011 )
2.Convert 5 to binaryConvert 5 to binary (4 bits)( 0101 )
3.Two's complement of 5Invert bits of 5 (0101) and add 1

Invert: ( 0101 to 1010 ),

then add 1: ( 1010 + 1 = 1011 )

4.Add 3 and -5Perform binary addition of ( 0011 + 1011 )( 1110 )
5.Interpret the resultConvert 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). *** 3. **Subtraction: ( 5 - 3 ) using 10's Complement** We know that subtraction can be represented as: * $$5 - 3 = 5 + (-3)$$ **Step-by-step:**
StepActionExplanationDecimalBinary
1.Represent 5 in binaryConvert 5 to binary (4 digits)( 5 )( 0101 )
2.Represent 3 in binaryConvert 3 to binary (4 digits)( 3 )( 0011 )
3.10's complement of 3Find 9's complement and add 1: ( 9 - 3 = 6 ); then add 1: ( 6 + 1 = 7 )( -3 )( 0111 )
4.Add 5 and -3Add the binary of 5 and the 10's complement of 3: ( 0101 + 0111 )( 5 + (-3) )( 1100 )
5.Interpret the resultSince there's no carry, the result is the answer( 2 )( 0010 )
Final result: * $$5 - 3 = 2 \quad \text{(in decimal, binary ( 0010 ))}$$ *** 4. **Subtraction: ( 3 - 5 ) using 10's Complement** We know that subtraction can be represented as: * $$3 - 5 = 3 + (-5)$$ **Step-by-step:**
StepActionExplanationDecimalBinary
1.Represent 3 in binaryConvert 3 to binary (4 digits)( 3 )( 0011 )
2.Represent 5 in binaryConvert 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 -5Add 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.