Digital Electronics and Computer Organisation.2021

Section A:

---

1. Prove that NOR and NAND gates are universal gates.

Definition of Universal Gates:

Universal gates are those which can be used to implement any Boolean function without needing any other gate types.

Proof:

• NAND Gate:

  • A NAND gate can be used to create the basic gates:
    1. NOT Gate:
       Input $A$ to both inputs of the NAND gate: $$\text{Output} = A \cdot A = A'$$
    2. AND Gate:
       Combine NOT gates and NAND gates:
       $(A \cdot B)' \cdot (A \cdot B)' = A \cdot B$.
    3. OR Gate:
       Using De Morgan's theorem and NOT gates:
       $A' \cdot B' = (A + B)'$.

• NOR Gate:

  • Similarly, NOR gates can be used to create:
    1. NOT Gate:
       Input $A$ to both inputs of the NOR gate: $$\text{Output} = (A + A)' = A'$$
    2. OR Gate:
       Combine two NOT gates and NOR gates:
       $(A + B)' + (A + B)' = A + B$.
    3. AND Gate:
       Using De Morgan's theorem:
       $(A' + B')' = A \cdot B$.

Thus, both NAND and NOR gates can implement all basic gates and are universal.

---

2. Explain the working of a half-adder with a suitable block diagram.

Half-Adder:

A half-adder is a combinational circuit that adds two binary numbers $A$ and $B$ and produces:

• Sum (S): Represents the XOR of the two inputs.
  $S = A \oplus B$.
• Carry (C): Represents the AND of the two inputs.
  $C = A \cdot B$.

Block Diagram:

The block diagram includes:

• An XOR gate for the Sum.
• An AND gate for the Carry.

Truth Table:

Input A	Input B	Sum (S)	Carry (C)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

---

3. Draw the logic diagram of a Master-Slave D Flip-Flop using NAND gates.

Explanation:

A Master-Slave D Flip-Flop consists of:

• Master: A latch that captures the input data on the clock's rising edge.
• Slave: A latch that reflects the data on the clock's falling edge.

Logic Diagram:

• Constructed using NAND gates.
• The input $D$ and clock (CLK) determine the state of the Master latch.
• The inverted CLK signal drives the Slave latch.

This ensures edge-triggered operation.

---

4. What do you know about K-map?

Definition:

A Karnaugh Map (K-map) is a graphical tool used for simplifying Boolean expressions. It organizes the truth table values into a grid, grouping adjacent terms to minimize the logic.

Key Features:

• Reduces Boolean expressions using grouping of 1's or 0's.
• Minimizes the number of terms in a logic equation.
• Ensures a simplified and optimized circuit.

Steps to Simplify:

1. Plot the 1's from the truth table into the K-map.
2. Group adjacent 1's in sizes of $1, 2, 4, 8, \dots$.
3. Write the minimized expression.

---

5. Make the truth tables of:

(i) Half Adder

Already shown in Question 2.

(ii) Half Subtractor

The Half Subtractor is a combinational circuit that subtracts two bits $A$ and $B$, producing:

• Difference (D): $A \oplus B$.
• Borrow (B_out): $A' \cdot B$.

Truth Table:

Input A	Input B	Difference (D)	Borrow (B_out)
0	0	0	0
0	1	1	1
1	0	1	0
1	1	0	0

---

Section B:

---

Question 6: Prove that (A + B + AB)(A + ̅B)(̅A̅B) = 0

Simplification:

1. Start with the given expression:

   $$(A + B + AB)(A + \bar{B})(\bar{A} \bar{B})$$

2. Simplify $(A + B + AB)$:
   Using the Absorption Law ($A + AB = A + B$), the term becomes:

   $$A + B$$

   So the expression is now:

   $$(A + B)(A + \bar{B})(\bar{A} \bar{B})$$

3. Analyze $(A + B)(A + \bar{B})$:
   Expand using distribution:

   $$(A + B)(A + \bar{B}) = A + AB + A\bar{B} + B\bar{B}$$

   The term $B\bar{B} = 0$, so it reduces to:

   $$A + B$$

4. Multiply the result with $(\bar{A} \bar{B})$:

   $$(A + B)(\bar{A} \bar{B}) = (A \cdot \bar{A} \bar{B}) + (B \cdot \bar{A} \bar{B})$$
   • The term $A \cdot \bar{A} = 0$.
   • Simplify $B \cdot \bar{A} \bar{B}$:
     $\bar{B} \cdot B = 0$.

   So, the entire expression simplifies to:

   $$0$$

Conclusion:

$$(A + B + AB)(A + \bar{B})(\bar{A} \bar{B}) = 0$$

---

Question 7: Simplify the expression using the Karnaugh map method.

Given Expression:

$$ABC' + ABC + AB'C + A'BC + A'BC' + AB'C'$$

Steps:

1. List the minterms:
   Convert the expression into minterms (binary representation):

   • $ABC'$ → (111)
   • $ABC$ → (110)
   • $AB'C$ → (101)
   • $A'BC$ → (010)
   • $A'BC'$ → (011)
   • $AB'C'$ → (100)

2. Fill the K-map:
   Plot the minterms into the K-map.

3. Group adjacent 1's:

   • Group all adjacent terms into pairs or quads to minimize.

4. Simplified expression:
   Use the groups to find the minimized Boolean equation.

---

Question 8: Design a 3-bit binary down counter using SR flip-flops.

Here’s the detailed explanation and solution for designing a 3-bit binary down counter using SR flip-flops.

---

What is a Down Counter?

A down counter counts in reverse order, decrementing its value by 1 in each clock cycle. For a 3-bit binary down counter, the counting sequence is:

$$111 \rightarrow 110 \rightarrow 101 \rightarrow 100 \rightarrow 011 \rightarrow 010 \rightarrow 001 \rightarrow 000$$

It has 8 states (from $2^3$).

---

Steps to Design a 3-bit Down Counter using SR Flip-Flops

1. State Transition Table

The state table shows the current state ($Q_2, Q_1, Q_0$) and the next state after a clock pulse.

Current State (Q2 Q1 Q0)	Next State (Q2' Q1' Q0')
111	110
110	101
101	100
100	011
011	010
010	001
001	000
000	111

---

2. SR Flip-Flop Excitation Table

The SR flip-flop is used to store and toggle bits. Its excitation table defines the required inputs ($S$ and $R$) for transitioning from the current state to the next state.

Current State	Next State	S	R
0 → 0	No change	0	0
0 → 1	Set to 1	1	0
1 → 0	Reset to 0	0	1
1 → 1	No change	0	0

Using this table, calculate the required $S$ and $R$ inputs for each flip-flop.

---

3. Input Requirements for Each Flip-Flop

For each flip-flop ($Q_2, Q_1, Q_0$):

1. Transition Logic for $Q_0$ (LSB):

   • $Q_0$ toggles every clock cycle (i.e., $Q_0' = \bar{Q_0}$).
   • Inputs for SR flip-flop $Q_0$: $$S_0 = \bar{Q_0}, \quad R_0 = Q_0$$

2. Transition Logic for $Q_1$:

   • $Q_1$ toggles when $Q_0 = 0$.
   • Inputs for SR flip-flop $Q_1$: $$S_1 = \bar{Q_1} \cdot \bar{Q_0}, \quad R_1 = Q_1 \cdot \bar{Q_0}$$

3. Transition Logic for $Q_2$ (MSB):

   • $Q_2$ toggles when $Q_1 = 0$ and $Q_0 = 0$.
   • Inputs for SR flip-flop $Q_2$: $$S_2 = \bar{Q_2} \cdot \bar{Q_1} \cdot \bar{Q_0}, \quad R_2 = Q_2 \cdot \bar{Q_1} \cdot \bar{Q_0}$$

---

4. Karnaugh Map Simplification (Optional)

If desired, Karnaugh maps can be used to simplify the logic for $S_2, S_1, S_0$ and $R_2, R_1, R_0$, but the equations above are already minimal.

---

5. Circuit Diagram

• Use three SR flip-flops to represent $Q_2, Q_1, Q_0$.
• Connect the clock to all flip-flops (synchronous counter).
• The input logic for $S$ and $R$ for each flip-flop is derived from the above equations.

---

Final Circuit Explanation

1. Clock Input:
   All flip-flops receive the same clock signal for synchronous operation.

2. SR Inputs:

   • $Q_0$: Toggling logic for $Q_0$ is directly connected to its complement.
   • $Q_1$: Toggling logic depends on $Q_0$.
   • $Q_2$: Toggling logic depends on $Q_1$ and $Q_0$.

3. Outputs:
   The outputs of the flip-flops ($Q_2, Q_1, Q_0$) represent the current state of the counter.

---

Timing Diagram

The timing diagram will show how $Q_2, Q_1, Q_0$ transition through the states $111 \rightarrow 110 \rightarrow 101 \rightarrow \dots \rightarrow 000 \rightarrow 111$.

---

Would you like me to draw a circuit diagram or provide a step-by-step timing diagram for better clarity?

---

Section C:

---

Question 9: Write short notes on the following:

(i) Virtual Memory Organization:

• Definition:
  Virtual memory is a memory management technique that creates the illusion of a large, contiguous memory space for programs, even if the physical memory (RAM) is limited.

• How It Works:

  • The operating system uses paging or segmentation to divide the memory into manageable chunks.
  • Parts of programs or data that are not currently in use are stored on the hard drive or SSD (in a special area called the page file or swap space).
  • When needed, these are loaded into physical memory.

• Advantages:

  • Allows execution of large programs.
  • Provides memory protection by isolating processes.
  • Improves multitasking by sharing physical memory efficiently.

• Disadvantages:

  • Can lead to slower performance if excessive page swapping (thrashing) occurs.

---

(ii) Random Access Memories (RAM):

• Definition:
  RAM is a type of volatile memory that allows data to be read or written in any order (randomly), as opposed to sequential memory (e.g., magnetic tape).

• Types of RAM:

  1. Dynamic RAM (DRAM): Requires periodic refreshing to retain data.
  2. Static RAM (SRAM): Faster than DRAM and does not need refreshing, but it is more expensive.

• Applications:

  • Temporary storage for data currently being processed by the CPU.
  • Used in cache memory and buffers.

• Key Characteristics:

  • High-speed access.
  • Volatile (loses data when power is off).

---

Question 10: What do you mean by cache memory? How is the performance of a memory system improved by using cache?

Cache Memory:

• Definition:
  Cache memory is a small, high-speed memory located close to the CPU that stores frequently accessed data and instructions.

• Levels of Cache:

  1. L1 Cache: Closest to the CPU, very small but extremely fast.
  2. L2 Cache: Larger and slightly slower than L1.
  3. L3 Cache: Shared across multiple CPU cores.

How Cache Improves Performance:

1. Faster Data Access:

   • The CPU can access cache memory faster than main memory (RAM), reducing the time required for data retrieval.

2. Reduces Latency:

   • By storing frequently used data, cache reduces the need to access slower memory tiers.

3. Improves Efficiency:

   • Programs run more smoothly because the CPU spends less time waiting for data.

4. Hit and Miss:

   • A cache hit occurs when the required data is found in the cache, speeding up operations.
   • A cache miss means the data must be fetched from RAM, which is slower.

---

Question 11: Design the binary counters having the following repeated binary sequence. Use JK flip-flops:

(i) 0, 1, 2

(ii) 0, 1, 2, 3

Steps to Design:

1. Determine the Number of Flip-Flops:
   The number of flip-flops required depends on the number of states:

   • For $0, 1, 2$, we need at least 2 flip-flops ($2^2 = 4$ states).
   • For $0, 1, 2, 3$, we need 2 flip-flops ($2^2 = 4$).

2. Truth Table:
   Create the truth table for the given sequence, defining the state transitions and inputs required for each JK flip-flop.

3. Excitation Table for JK Flip-Flops:
   Determine the inputs $J$ and $K$ for each flip-flop based on the current and next states.

4. Logic Circuit Design:
   Use Karnaugh maps to simplify the expressions for $J$ and $K$ inputs, and design the circuit using JK flip-flops.

---

Question 12:

(i) Implement a full adder using two half adders and an OR gate.

• Explanation:
  A full adder adds three binary inputs $A$, $B$, and $Cin$ (carry-in) and produces:

  • Sum (S): The XOR of $A$, $B$, and $Cin$. $$S = A \oplus B \oplus Cin$$
  • Carry (Cout): The OR of two AND gates: $$Cout = (A \cdot B) + (Cin \cdot (A \oplus B))$$

• Steps to Implement:

  1. First half adder calculates $S1 = A \oplus B$ and $C1 = A \cdot B$.
  2. Second half adder calculates the final sum $S = S1 \oplus Cin$ and $C2 = S1 \cdot Cin$.
  3. OR gate combines $C1$ and $C2$ to produce $Cout$.

(ii) Design a combinational circuit whose input is a 4-bit number and whose output is the 2’s complement.

• Explanation:
  The 2’s complement of a number is obtained by inverting all bits and adding 1.

• Steps:

  1. Use NOT gates to invert all input bits.
  2. Add 1 to the inverted bits using a 4-bit binary adder.

---

Question 13: State De Morgan's theorems of Boolean algebra and prove them. What is the physical significance of these theorems?

De Morgan's Theorems:

1. First Theorem:

   $$(A + B)' = A' \cdot B'$$

   Proof:

   • Using the truth table, verify that the output of $(A + B)'$ is identical to $A' \cdot B'$.

2. Second Theorem:

   $$(A \cdot B)' = A' + B'$$

   Proof:

   • Using the truth table, verify that the output of $(A \cdot B)'$ is identical to $A' + B'$.

Physical Significance:

• These theorems simplify logic circuits by transforming NAND and NOR gates into simpler equivalents.
• They allow for flexibility in circuit design, reducing complexity and cost.

---