Unit3 - Subjective Questions

1. to Decimal:

Use positional weights ():
(Note: )

2. to Binary:

Divide by 2 repeatedly:

• rem $1$
• rem $0$
• rem $1$
• rem $0$
• rem $1$
• rem $1$
  Read from bottom to top:

3. to Octal:

Group bits in 3s starting from LSB:

Binary to Gray Conversion:

1. The MSB (Most Significant Bit) of the Gray code is the same as the MSB of the Binary number.
2. Each subsequent bit of the Gray code is obtained by performing an XOR operation between the current binary bit and the previous binary bit.

Gray to Binary Conversion:

1. The MSB of the Binary number is the same as the MSB of the Gray code.
2. Each subsequent binary bit is obtained by XORing the previous calculated binary bit with the current Gray bit.

Example: Convert Binary $10110$ to Gray:
Let Binary

Result: Gray Code = $11101$

We need to perform: or .

Step 1: Represent numbers in 8-bit binary.

Step 2: Find 2's complement of the subtrahend (14).

• 1's complement of 14: $11110001$
• Add 1: (This represents -14)

Step 3: Add minuend to 2's complement of subtrahend.

Step 4: Analyze result.

• There is a carry out of $1$ (9th bit). In 2's complement addition, discard the final carry.
• Result: $00001100$

Verification: .
Calculation: . The result is correct.

BCD (8421 Code):

• Definition: A weighted code where each decimal digit (0-9) is represented by its 4-bit binary equivalent.
• Weights: It uses weights 8, 4, 2, 1.
• Valid Range: $0000$ (0) to $1001$ (9). Codes from $1010$ to $1111$ are invalid.
• Arithmetic: Requires correction (adding 6) if the sum exceeds 9.

Excess-3 (XS-3) Code:

• Definition: A non-weighted code derived by adding 3 ($0011$) to the corresponding BCD code.
• Weights: It is not a positional weighted code.
• Self-Complementing: It is a self-complementing code (9's complement of the decimal can be found by taking the 1's complement of the Excess-3 code).
• Example: Decimal 5 in BCD is $0101$; in Excess-3 it is .

Theorem 1: The complement of a product is equal to the sum of the complements.
Expression:

Theorem 2: The complement of a sum is equal to the product of the complements.
Expression:

Proof (using Truth Table):

From the table, columns and are identical. Columns and are identical.

Universal Gates:
NAND and NOR gates are called universal gates because any boolean function or any other logic gate (AND, OR, NOT, XOR, etc.) can be implemented using a combination of only NAND gates or only NOR gates, without the need for any other type of gate.

Implementation using NAND:

1. NOT Gate using NAND:

   • Connect both inputs of a NAND gate together.

2. AND Gate using NAND:

   • Connect a NAND gate followed by a NOT gate (made from NAND).
   • First stage:
   • Second stage:

3. OR Gate using NAND:

   • Invert inputs A and B individually using NAND gates, then feed them into a third NAND gate.
   • Inputs:
   • Output:
   • Using De Morgan's:

Operation:
The XOR gate produces a HIGH (1) output only when the inputs are different (one is HIGH and the other is LOW). If both inputs are the same (both 0 or both 1), the output is LOW (0).

Boolean Expression:

Truth Table:

Logic Symbol:
The symbol resembles an OR gate with a curved line across the input side.

Application: Used in Parity generators/checkers and binary adders (Half Adder/Full Adder).

Given:

Step 1: Group terms.
Combine terms with common variables.

Step 2: Apply Inverse Law ().

Step 3: Factor out .

Step 4: Apply Inverse Law.

Step 5: Apply Distributive Law ().

Using :

Alternative Simplification from Step 4:
(if applying Redundancy/Absorption directly)

Final Simplified Expression:

Definitions:

• Sum of Products (SOP): A boolean expression where several product terms (AND terms) are summed (ORed) together. Example: .
• Product of Sums (POS): A boolean expression where several sum terms (OR terms) are multiplied (ANDed) together. Example: .

Conversion of to Canonical SOP:

1. Expand the expression:
   

   
   (Since )

2. Simplify (Absorptive Law):
   

   
   

3. Convert to Canonical (Standard) SOP:
   Each term must contain all variables (A, B, C).

   • Term A: Multiply by
     
   • Term BC: Multiply by
     

4. Combine and remove duplicates:
   

   
   

   Minterm Notation:

Step 1: Plot the K-Map (4 Variables)
We place 1s in cells: 0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14.

Rows (AB): 00, 01, 11, 10
Cols (CD): 00, 01, 11, 10

Step 2: Grouping

1. Quad 1: Cells 0, 1, 4, 5 ($0000, 0001, 0100, 0101$).
   • AB changes 00->01, CD changes 00->01.
   • Common: and . Term: .
2. Quad 2: Cells 0, 2, 4, 6 ($0000, 0010, 0100, 0110$).
   • AB changes 00->01, CD changes 00->10 (wraparound).
   • Common: and . Term: .
3. Quad 3: Cells 0, 1, 8, 9 ($0000, 0001, 1000, 1001$).
   • AB changes 00->10, CD changes 00->01.
   • Common: and . Term: .
4. Quad 4: Cells 8, 9, 12, 13 ($1000, 1001, 1100, 1101$).
   • AB changes 10->11, CD changes 00->01.
   • Common: and . Term: .
5. Quad 5: Cells 4, 5, 6, 12, 13, 14 (Can we group larger?)
   • Let's check optimized grouping.
   • Group Cells 0,1,8,9,4,5,12,13 -> Octet. Corresponds to .
   • Group Cells 0,2,4,6,8,10(empty),12,14. -> Cell 10 is missing.
   • Let's refine:
     • Octet 1: Cells 0, 1, 4, 5, 8, 9, 12, 13. Covers three columns except column 11 and 10. Actually, these cells are columns 00 and 01. Covers all rows. The variable constant is .
     • Quad 2: Cells 2, 6, 14. We can group 2, 6, 14 with something?
     • Group 4, 6, 12, 14. Corresponds to .
     • Group 0, 2, 8, 10(empty)? No.
     • Group 2, 6 with 0, 4 (Already covered).
     • Remaining 1s to cover: Cell 2, 6, 14.
     • Group 2, 6, 0, 4? (Redundant).
     • Group 2, 6, 14, and... maybe 10 is 0? Yes.
     • Let's group 6, 14, 4, 12 ($0110, 1110, 0100, 1100$). Term: .
     • Is Cell 2 covered? We need 0, 2, 4, 6. Term .

Final Simplified Expression:

Circuit Realization:
Use NOT gates for inversions, AND gates for product terms, and an OR gate for the sum.

Don't Care Conditions:
These are input combinations for which the output state (0 or 1) does not matter or will never occur. They are denoted by 'X' or 'd' in the K-Map. They can be treated as 1s or 0s to help form larger groups for better minimization.

Simplification:
Plotting 1s: 1, 3, 7, 11, 15
Plotting Xs: 0, 2, 5

Grouping:

1. Quad 1: Cells 1, 3, 5(X), 7. (Row 00/01, Col 01/11). Common: .
2. Quad 2: Cells 3, 7, 11, 15. (Column 11). Common: .
3. Quad 3: Cells 0(X), 1, 2(X), 3. (Row 00). Common: .

Wait, let's optimize:

• Group 1 (Cells 3, 7, 11, 15): Term .
• Group 2 (Cells 1, 3, 5, 7): Term . (Redundant if 3 and 7 covered? No, need 1 and 5).
• Group 3 (Cells 0, 1, 2, 3): Term .

Check coverage:

• 1s at 1, 3, 7, 11, 15 must be covered.
• covers 3, 7, 11, 15.
• We need to cover '1'.
• We can use Don't cares 0 and 5.
• Group 0, 1, 2, 3? No, 2 is X, 0 is X. Covers 1. Term .
• Alternative: Group 1, 3, 5, 7. Covers 1. Term .

Simplified Expression:
or (Depending on selection).
Using covers 1,3,5,7. 1 is covered. 3,7 covered twice. 11,15 covered by .
Result:

Problem: where and .

Step 1: Find the 1's complement of the subtrahend ().
1's Comp = $10001$.

Step 2: Add to the 1's complement of .

Step 3: Check for Carry.
There is a carry of 1 (End-Around Carry).

Step 4: Add the carry to the LSB of the result.

Result:

Verification:
. . Correct.

1. to Decimal:
Weights:

2. to Binary:
Convert each Hex digit to 4-bit Binary.

Combine:

Step 1: Simplify/Modify Expression for NOR logic.
NOR logic corresponds to .
We have . This is typically easier with NAND, but for NOR:
Apply double inversion: (This is OR form).

To use NOR, we generally want Product of Sums (POS) or manipulation.
Convert to POS: .

Step 2: Realize using NOR.

1. Create term: Use a NOR gate, output is . Invert this to get .
   • Gate 1: Inputs A, B Output .
   • Gate 2 (Inverter): Input Output .
2. Create term: Similarly.
   • Gate 3: Inputs A, C Output .
   • Gate 4 (Inverter): Input Output .
3. AND them together.
   • AND using NOR: Invert inputs, then NOR. (We have and ).
   • Actually, a clearer way using standard 2-level NOR-NOR logic is typically for POS forms.
   • NOR . Not quite.

Alternative Direct Mapping:
.
Using standard POS realization:

1. Gate 1: into NOR .
2. Gate 2: into NOR .
3. Gate 3: Feed outputs of Gate 1 and 2 into a NOR gate.
   
   
   Apply De Morgan's: .

Conclusion:
Three NOR gates are required.

1. NOR(A, B)
2. NOR(A, C)
3. NOR(Output1, Output2)

Definitions:

• Minterm: A product term in a boolean function containing all variables in either complemented or uncomplemented form. Corresponding to SOP.
• Maxterm: A sum term in a boolean function containing all variables. Corresponding to POS.

Conversion of :

1. Term : Missing .
   
   Binary: , .
2. Term : Missing .
   
   
   Binary: , , , .

Combine:
Total Minterms: .
Expression:

Statement: The consensus term () is redundant if the terms and exist.

Algebraic Proof:

Conclusion: The theorem is proved.

Note: We are given Maxterms (), which corresponds to placing 0s in the K-Map and grouping them to find the POS expression.

Step 1: Plot 0s.
Cells: 0, 1, 3, 8, 9, 11, 15.

Step 2: Grouping 0s.

1. Quad 1: Cells 0, 1, 8, 9.
   • Row 00, 10 (), Col 00, 01 ().
   • Note: In POS, variables are inverted. Variable, Complemented Variable.
   • Constant bits: . Sum term: .
2. Quad 2: Cells 1, 3, 9, 11.
   • Row 00, 10 (), Col 01, 11 ().
   • Constant bits: . Sum term: .
3. Pair: Cells 11, 15.
   • Row 10, 11 (), Col 11 ().
   • Grouping with 3,7,11,15? Cell 7 is not 0. So just pair 11, 15?
   • Wait, is 3, 11, 15... Can we group 3, 11 with 1, 9 (Already done).
   • Left with 15. Group 11, 15.
   • Better: Group 11, 15 with 9, 13 (Is 13 a 0? No).
   • Group 3, 11? (Already in Quad 2).
   • Must cover 15. Group 11, 15. Term: .
   • Wait, let's check input again. Maxterms: 0,1,3,8,9,11,15.
   • 11 is $1011$, 15 is $1111$. changes. . constant $11$. Term is incorrect. changes? No. $10, 11$. is 1. changes. . Term .
   • Is there a better group for 15? 3, 7, 11, 15 (7 is not 0).
   • Actually, let's look at grouping 3 and 1? Done.
   • 15 can only group with 11.

Expression:

1. Addition:

Result: $1100100$

2. Multiplication:

Result: $10000111$

1. Representation of Zero:

• 1's Complement: Has two representations for zero: Positive zero ($0000...$) and Negative zero ($1111...$).
• 2's Complement: Has a unique representation for zero ($0000...$).

2. Range (for n bits):

• 1's Complement: to .
• 2's Complement: to . 2's complement can represent one extra negative number.

3. Arithmetic Complexity:

• 1's Complement: Requires 'End-Around Carry' (if a carry is generated at the MSB, it must be added to the LSB).
• 2's Complement: The carry generated at the MSB is simply discarded, making arithmetic circuitry simpler and faster.

4. Usage:

• 2's Complement is the standard for signed integer arithmetic in modern computers due to the unique zero and simpler arithmetic.

Original Circuit:
Requires three 3-input AND gates and one 3-input OR gate (plus inverters).

Simplification:

Optimized Circuit:

1. OR Gate: Inputs B, C Output .
2. AND Gate: Inputs A, Output of OR Final .
   Requires only 1 AND gate and 1 OR gate (2 inputs each).