Problem solving

1. Number System Conversions & Radix Problems

1.1. Number System Conversions (with Fractions)

This method is used for converting a number from one base to another (e.g., Decimal to Hexadecimal to Binary), especially when it includes a fractional part.

Steps:

1. Separate Parts: Split the number into its integer and fractional components.

2. Convert the Integer Part (Repeated Division):

   • Divide the integer by the target base (e.g., 16 for Hex).
   • The remainder of each division becomes the next digit.
   • Continue until the quotient is 0. Read the remainders in reverse order.
   • Example (Convert 757₁₀ to Hex):
     • 757 ÷ 16 = 47 remainder 5
     • 47 ÷ 16 = 2 remainder 15 (F)
     • 2 ÷ 16 = 0 remainder 2
     • Result (reading up): (2F5)₁₆

3. Convert the Fractional Part (Repeated Multiplication):

   • Multiply the fraction by the target base.
   • The integer part of the product becomes the next digit.
   • Continue multiplying the new fractional part of the product until the fraction becomes zero or you reach the desired precision.
   • Read the resulting integer parts in forward order.
   • Example (Convert 0.25₁₀ to Hex):
     • 0.25 × 16 = 4.00. The integer part is 4. The new fraction is .00. Stop.
     • Result (reading down): (0.4)₁₆

4. Combine and Finalize: Combine the integer and fractional parts.

   • (757.25)₁₀ = (2F5.4)₁₆

5. Fast Conversion (Hex ↔ Binary):

   • To convert from Hex to Binary, convert each hex digit into its 4-bit binary equivalent.
   • Example (2F5.4)₁₆:
     • 2 → 0010
     • F → 1111
     • 5 → 0101
     • . → .
     • 4 → 0100
     • Result: (0010 1111 0101.0100)₂

1.2. Determining the Base (Radix) of an Equation

This method is used when you are given an equation that is incorrect in base-10 (e.g., 54 + 24 = 111) and asked to find the base R in which it holds true.

Steps:

1. Set up the Polynomial Equation: Convert every number into its polynomial form using the unknown base R.

   • Example (54 + 24 = 111 in base R):
     • (5 × R¹ + 4 × R⁰) + (2 × R¹ + 4 × R⁰) = (1 × R² + 1 × R¹ + 1 × R⁰)
     • This simplifies to: (5R + 4) + (2R + 4) = R² + R + 1

2. Solve for R: Simplify the polynomial into a standard form (e.g., quadratic) and solve for R.

   • 7R + 8 = R² + R + 1
   • R² - 6R - 7 = 0
   • Factoring gives (R-7)(R+1) = 0. The potential solutions are R=7 and R=-1.

3. Validate the Solution: The base R must satisfy two conditions:

   • It must be a positive integer.
   • It must be strictly larger than any single digit appearing in the equation.
   • In our example: The digits are 5, 4, 2, 1. The largest is 5. Therefore, the base R must be greater than 5.
   • From our solutions (R=7, R=-1), only R=7 is a valid base.

---

2. Binary Arithmetic with Signed Numbers

2.1. 2's Complement Arithmetic (Standard Method)

Used to perform addition or subtraction of signed integers with a fixed number of bits.

Steps:

1. Check the Range: For n bits, the valid range of numbers is -2ⁿ⁻¹ to +2ⁿ⁻¹ - 1.

   • Example (6-bit): Range is -2⁵ to +2⁵ - 1, which is -32 to +31. A result outside this is an overflow.

2. Convert Numbers to Binary:

   • Positive Numbers: Convert to binary and pad with leading zeros.
     • Example (+13 in 6 bits): 13 is 1101. Pad to 001101.
   • Negative Numbers (e.g., -27): a. Start with the positive binary value: +27 is 011011. b. Invert all the bits: 100100. c. Add 1: 100100 + 1 = 100101. This is (-27) in 6-bit 2's complement.

3. Perform Binary Addition: Add the binary numbers. Discard any carry-out from the most significant bit (MSB).

4. Check for Overflow: Overflow can only occur when adding numbers of the same sign.

   • Positive + Positive = Negative → Overflow (MSB of result is 1).
   • Negative + Negative = Positive → Overflow (MSB of result is 0).
   • Positive + Negative → Never overflows.

5. Interpret the Result:

   • If MSB is 0, the number is positive. Convert directly to decimal.
   • If MSB is 1, the number is negative. To find its value, perform the 2's complement operation on the result again (invert all bits, add 1) and place a minus sign in front.
     • Example (Result is 110010): Invert (001101) → Add 1 (001110) → Convert to decimal (14). The final answer is -14.

2.2. 1's Complement Arithmetic

An alternative representation for signed numbers notable for its "end-around carry."

Steps:

1. Check the Range: For n bits, the range is -(2ⁿ⁻¹ - 1) to +(2ⁿ⁻¹ - 1).

   • Example (6-bit): Range is -(2⁵-1) to +(2⁵-1), which is -31 to +31.

2. Convert Numbers to Binary:

   • Positive Numbers: Same as 2's complement.
   • Negative Numbers: Simply take the positive binary value and invert all the bits.
     • Example (-15 in 6 bits): +15 is 001111. Inverting gives 110000.

3. Perform Binary Addition & End-Around Carry:

   • Add the two binary numbers.
   • If a carry-out is generated from the MSB, you must add it back to the least significant bit of the sum.

4. Check for Overflow: Rules are the same as in 2's complement (Pos+Pos=Neg or Neg+Neg=Pos).

5. Interpret the Result:

   • If MSB is 0, the number is positive.
   • If MSB is 1, the number is negative. To find its value, take the 1's complement of the result (invert all bits) and place a minus sign in front.

---

3. Boolean Algebra Rules & Simplification

3.1. Fundamental Rules and Identities

Identity Name	AND Form	OR Form
Identity	X · 1 = X	X + 0 = X
Null/Annihilation	X · 0 = 0	X + 1 = 1
Idempotent	X · X = X	X + X = X
Complement	X · X' = 0	X + X' = 1
Involution	(X')' = X
Commutative	XY = YX	X + Y = Y + X
Associative	(XY)Z = X(YZ)	(X+Y)+Z = X+(Y+Z)
Distributive	X(Y+Z) = XY+XZ	X+YZ = (X+Y)(X+Z)
De Morgan's	(XY)' = X' + Y'	(X+Y)' = X'Y'

3.2. Key Simplification Theorems & Tricks

• Absorption: X + XY = X
• Trick: If a small term (X) appears inside a larger term (XY), the larger term is redundant.

• Example: A'B + A'BC + C simplifies to A'B + C.

• Adjacency: X + X'Y = X + Y

• Trick: A variable (X) is OR-ed with its complement (X') which is AND-ed with another term (Y). The complemented variable X' is eliminated.

• Example: AB + A'C = AB + A'C (no change), but A + A'B simplifies to A + B.

• Consensus Theorem: XY + X'Z + YZ = XY + X'Z

• Trick: Look for a pair of terms where one variable is true in one (X) and complemented in the other (X'). The "consensus" term is formed by the remaining parts of those terms (YZ). If that consensus term exists, it is redundant.

• Example: In A'C + AB + BC, the consensus of A'C and AB is BC. Since BC is present, it can be removed. The expression simplifies to A'C + AB.

• Multiplying Out (POS to SOP): (X+Y)(X'+Z) = XZ + X'Y

• Trick: This is a faster way to multiply out two sums when one variable is true in the first and complemented in the second.

3.3. Applying De Morgan's Law: "Break the Line, Change the Sign"

This is a graphical trick to find the dual of a gate or expression directly on a circuit diagram.

Rules:

1. Break the Inversion Line: Find a line that represents the overall inversion (e.g., the bar over (A+B) in (A+B)'). "Break" this line.
2. Change the Gate: Change the gate's sign from OR to AND, or from AND to OR.
3. Push the Inversion: Push the broken pieces of the line to the inputs of the new gate, where they become smaller inversions (bubbles).

Example: A NAND gate is equivalent to an OR gate with inverted inputs.

• Start: (A · B)' (NAND Gate)
• Step 1 & 2: Break the output inversion bar and change the AND to an OR.
• Step 3: Push the inversion "bubbles" to the inputs.
• Result: A' + B' (Bubbled OR Gate)

This also works in reverse: an OR gate with inverted inputs (A' + B') is equivalent to a NAND gate ((AB)'). This is extremely useful for converting circuits to use only NAND or only NOR gates.

---

4. Boolean Expression & Circuit Simplification

4.1. K-Map Grouping and Simplification

A graphical method for simplifying Boolean expressions.

K-Map Grouping Rules:

1. Target Values: For a Sum-of-Products (SOP) expression, you group the '1's. For a Product-of-Sums (POS) expression, you group the '0's.
2. "Don't Cares" (X): You can optionally include "don't cares" in a group if it helps make the group larger, but you never group only don't cares.
3. Power of 2: Groups must contain 1, 2, 4, 8, or 16 cells.
4. Rectangular: Groups must be rectangular (including squares).
5. Wrap-Around: The map is toroidal: the top edge is adjacent to the bottom edge, and the left edge is adjacent to the right edge. This allows the four corner cells to form a group of 4.

Finding the Minimum SOP Expression (Grouping '1's):

1. Plot the Function: Place 1s and Xs on the K-map.
2. Find Prime Implicants: Circle the largest possible groups of 1s, ensuring every 1 is covered. These are the Prime Implicants (PIs).
3. Identify Essential Prime Implicants (EPIs): An EPI is a group that covers a 1 that no other group can.
4. Form the Expression: The minimal expression is the sum (OR) of all EPIs plus the minimum number of other PIs needed to cover any remaining 1s.

Finding the Minimum POS Expression (Grouping '0's):

1. Plot the Function: Place 1s and Xs on the K-map. The empty cells are 0s.
2. Group the Zeros: Circle the largest possible groups of 0s. This gives you the minimal SOP expression for the inverse function (F').
3. Derive the Term for Each Group: For each group of zeros, find the sum term:
   • If a variable is always 0 in the group, write it in its true form (e.g., A).
   • If a variable is always 1 in the group, write it in its complemented form (e.g., A').
   • If a variable changes within the group, it is omitted.
4. Combine Terms: The final POS expression is the product (AND) of all the sum terms derived from the groups of zeros.

4.2. Circuit Analysis and Simplification

Used when a logic diagram is given and you must find the simplified Boolean expression for the output.

Steps:

1. Label and Trace: Starting from the inputs, write the Boolean expression for the output of each gate.
2. Build the Final Expression: Combine the intermediate expressions until you have a single expression for the final output.
3. Simplify Algebraically: Use the Boolean algebra theorems from Section 3 to simplify the expression to its minimal form.

4.3. Switch Logic to Boolean Expression

Used for diagrams of switches in series or parallel.

• Series switches = AND (·)
• Parallel switches = OR (+)

Steps:

1. Write the Expression: Trace paths from input to output. Combine parallel paths with + and series components with ·.
2. Convert to SOP/POS: Use algebraic manipulation on the expression to convert it to the desired form.

---

5. Advanced Simplification & Design

5.1. Quine-McCluskey (Tabular) Method

Used to systematically find all Prime Implicants (PIs) of a function.

Steps:

1. List and Group Minterms: Convert all minterms to binary and group them by the number of 1s they contain.
2. Combine Terms: Compare terms in adjacent groups. If they differ by only one bit, combine them into a new term with a dash (-) in that position. Check off both original terms.
3. Repeat: Continue combining terms from the new groups until no more combinations are possible.
4. Identify PIs: The terms that were never checked off are the Prime Implicants.

5.2. Prime Implicant (PI) Chart

Used after finding PIs to select the minimum set needed to implement the function.

Steps:

1. Construct Chart: Create a chart with PIs as rows and original minterms as columns. Place an 'X' where a PI covers a minterm.
2. Find Essential Prime Implicants (EPIs): Identify any column that has only a single 'X'. The corresponding row is an EPI. All EPIs must be in the final solution.
3. Reduce the Chart: Remove all EPI rows and all columns covered by them.
4. Cover Remaining Minterms: If minterms remain, use row/column dominance or Petrick's Method to select the minimal set of PIs to cover the rest.

5.3. Petrick's Method

An algebraic method to find all minimum solutions from a reduced PI chart.

Steps:

1. Form the Logic Expression (P): For each remaining minterm column, write a sum expression of the PIs that cover it (e.g., (P1 + P2)).
2. Create the Product-of-Sums: Multiply all these sum expressions together to form P.
3. Expand to Sum-of-Products: Multiply out P to get an SOP expression.
4. Identify Minimum Solutions: Each product term represents a valid solution. Choose the term(s) with the fewest PIs. This, combined with the EPIs found earlier, gives the complete minimum solution(s).

5.4. Truth Table Deduction

Used when a circuit and a partial truth table are given, and you must find the values for an intermediate signal.

Steps:

1. Write the Circuit's Equation: Define the final output in terms of the known and unknown intermediate signals (e.g., H = F + G).
2. Calculate Known Signals: For each row of the truth table, calculate the values of the known signals (e.g., F).
3. Deduce the Unknown Signal: Use the equation from step 1 to work backward and find the value of the unknown signal (G) for each row.
   • Example (H = F + G):
     • If H=1 and F=0, then G must be 1.
     • If H=1 and F=1, G could be 0 or 1, so G is a don't care (X).
     • If H=0, then both F and G must be 0.