Digital Electronics and Computer Organisation.

 

Section A :

---

1. Give the logic diagram and truth table of RS flip-flop.

Solution:

• RS Flip-Flop is a type of bistable flip-flop that has two inputs: Set (S) and Reset (R). Its outputs are Q and $\overline{Q}$, where $\overline{Q}$ is the complement of Q.

Logic Diagram: The RS flip-flop can be constructed using two NOR gates or two NAND gates in a cross-coupled configuration.

• Truth Table (Using NOR Gates):

S (Set)	R (Reset)	Q (Output)	$\overline{Q}$ (Complement)
0	0	No Change	No Change
0	1	0	1
1	0	1	0
1	1	Invalid	Invalid

• Explanation:
  • When S = 0, R = 0, the output remains the same (No Change).
  • When S = 1, R = 0, the flip-flop sets Q = 1.
  • When S = 0, R = 1, the flip-flop resets Q = 0.
  • When S = 1, R = 1, the output is undefined (invalid state).

---

2. Why is RAM used in a computer? How is static RAM different from dynamic RAM, and where are these RAMs used in computer systems?

Solution:

• Why RAM is used:

  • RAM (Random Access Memory) is used to store data and instructions temporarily for quick access by the CPU during operation. It is volatile, meaning data is lost when power is off.

• Static RAM (SRAM) vs Dynamic RAM (DRAM):

Feature	Static RAM (SRAM)	Dynamic RAM (DRAM)
Storage Mechanism	Flip-flop circuits	Capacitors
Speed	Faster	Slower
Power Consumption	Higher	Lower
Cost	Expensive	Cheaper
Density	Low (fewer cells/chip)	High (more cells/chip)

• Usage:
  • SRAM is used in cache memory and registers.
  • DRAM is used in main memory (RAM) due to its higher density and lower cost.

---

3. Construct half adder circuit using basic gates.

Solution:

• A half adder is a combinational circuit that adds two binary digits and produces a sum and a carry.

Logic Equations:

• Sum (S): $S = A \oplus B$ (XOR Gate)
• Carry (C): $C = A \cdot B$ (AND Gate)

Circuit Diagram:

• Use one XOR gate for the sum and one AND gate for the carry.

---

4. State and prove De Morgan’s theorem.

Solution: De Morgan’s theorem consists of two rules in Boolean algebra:

1. $\overline{A \cdot B} = \overline{A} + \overline{B}$
2. $\overline{A + B} = \overline{A} \cdot \overline{B}$

Proof (1):

• Starting from $\overline{A \cdot B}$:
  • If $A = 0$ and $B = 0$, $A \cdot B = 0$, so $\overline{A \cdot B} = 1$, and $\overline{A} + \overline{B} = 1$.
  • Verify similarly for other input combinations. The truth table confirms equivalence.

Proof (2):

• Similarly, for $\overline{A + B} = \overline{A} \cdot \overline{B}$, the truth table confirms equivalence.

---

5. With a logic diagram, characteristic table, and characteristic equation, explain the operation of a D Flip-Flop.

Solution:

• D Flip-Flop (Data or Delay Flip-Flop):
  • It has a single data input (D) and a clock signal.
  • The output Q follows the input D at the rising edge of the clock.

Logic Diagram:

• Constructed using an SR flip-flop with additional gates to eliminate the invalid state.

Characteristic Table:

D (Input)	Q (Next State)
0	0
1	1

Characteristic Equation: $Q(t+1) = D$

• Explanation:
  • When D = 1, the flip-flop sets Q = 1.
  • When D = 0, the flip-flop resets Q = 0.

---

Section B 

6. What are multiplexer and demultiplexer? Also, give the logical expression.

Solution:

Multiplexer (MUX):

• A multiplexer is a combinational circuit that selects one input from multiple inputs and forwards it to the output based on the selection lines.
• It acts as a data selector.

Logical Expression: For a 4:1 multiplexer:

$$Y = S_1 S_0 I_3 + S_1 \overline{S_0} I_2 + \overline{S_1} S_0 I_1 + \overline{S_1} \overline{S_0} I_0$$

Where $I_0, I_1, I_2, I_3$ are inputs, and $S_0, S_1$ are selection lines.

Demultiplexer (DEMUX):

• A demultiplexer is a combinational circuit that takes one input and distributes it to one of the several outputs based on the selection lines.
• It acts as a data distributor.

Logical Expression: For a 1:4 demultiplexer:

$$Y_0 = \overline{S_1} \overline{S_0} D, \quad Y_1 = \overline{S_1} S_0 D, \quad Y_2 = S_1 \overline{S_0} D, \quad Y_3 = S_1 S_0 D$$

Where $D$ is the input, and $S_0, S_1$ are selection lines.

---

7. Draw and explain SISO, SIPO, PISO, and PIPO shift registers with suitable examples.

Solution:

Shift Registers:

A shift register is a sequential circuit that is used for storing and shifting data.

1. Serial-In Serial-Out (SISO):

   • Data is input serially (bit by bit) and output serially.
   • Example: Storing and transmitting data one bit at a time.

2. Serial-In Parallel-Out (SIPO):

   • Data is input serially, but the output is available in parallel.
   • Example: Converting serial data received from a communication channel into parallel data for processing.

3. Parallel-In Serial-Out (PISO):

   • Data is input in parallel and output serially.
   • Example: Sending multiple bits of data serially over a single communication line.

4. Parallel-In Parallel-Out (PIPO):

   • Data is input and output in parallel.
   • Example: Temporary data storage and retrieval.

Diagrams: Each type of shift register consists of D flip-flops connected in a series or parallel configuration, depending on the type.

---

8. Implement the following Boolean function using multiplexers: $F(ABCD) = \Sigma(0, 1, 3, 4, 9, 15)$.

To implement the Boolean function $F(ABCD) = \Sigma(0, 1, 3, 4, 9, 15)$ using multiplexers, we need to systematically design the circuit based on the given minterms. Let's proceed step by step:

---

1. Understand the Function:

The function $F(ABCD)$ has 4 variables: $A, B, C, D$. The minterms correspond to the decimal equivalents of combinations of $A, B, C, D$ where $F$ is 1.

The minterms provided are: $0, 1, 3, 4, 9, 15$.

2. Truth Table:

Write the truth table for all combinations of $A, B, C, D$, marking the output $F$ as 1 for the minterms and 0 otherwise:

$A$	$B$	$C$	$D$	$F(ABCD)$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

---

3. Select the Multiplexer:

To implement this function using multiplexers:

• Use a 16:1 Multiplexer (16 inputs, 1 output) because there are 4 variables ($A, B, C, D$).
• The selection lines $A, B, C, D$ will decide which of the 16 inputs (labeled $I_0, I_1, \dots, I_{15}$) is passed to the output.

---

4. Assign the Minterms to Multiplexer Inputs:

The minterms $0, 1, 3, 4, 9, 15$ correspond to the inputs of the multiplexer where the output $F = 1$. All other inputs will have $F = 0$.

Input $I_i$	Value
$I_0$	1
$I_1$	1
$I_2$	0
$I_3$	1
$I_4$	1
$I_5$	0
$I_6$	0
$I_7$	0
$I_8$	0
$I_9$	1
$I_{10}$	0
$I_{11}$	0
$I_{12}$	0
$I_{13}$	0
$I_{14}$	0
$I_{15}$	1

---

5. Logic Diagram:

1. Connect the selection lines $A, B, C, D$ to the multiplexer’s selection inputs.

   • $A$: Most significant bit (MSB).
   • $B$: Second MSB.
   • $C$: Third MSB.
   • $D$: Least significant bit (LSB).

2. Assign the inputs $I_0, I_1, \dots, I_{15}$ to the corresponding minterm values as shown in the table above.

3. The output $F$ of the multiplexer will directly represent the given Boolean function.

---

6. Simplified Explanation:

• The multiplexer acts as a truth table lookup device:
  • For each combination of $A, B, C, D$, the corresponding input $I_i$ determines the output.
• Minterms with $F = 1$ (like $I_0, I_1, I_3, \dots$) are connected to logic HIGH (1).
• All other inputs are connected to logic LOW (0).

---

7. Final Circuit:

The circuit consists of:

• A 16:1 multiplexer with $A, B, C, D$ as the selection lines.
• The input pins $I_0$ through $I_{15}$ connected based on the minterms provided.

---

---

Section C 

9. Explain cache memory and cache initialization. Give the significance of cache memory.

Solution:

Cache Memory:

• Cache memory is a small, high-speed memory located closer to the CPU.
• It stores frequently accessed data and instructions to speed up processing.
• Cache bridges the speed gap between the CPU and main memory.

Significance of Cache Memory:

1. Improved Performance:
   • Cache reduces the time required to access data, leading to faster execution.
2. Minimizes Latency:
   • Data is available closer to the CPU, reducing memory access delays.
3. Cost Efficiency:
   • Although expensive, it reduces the need for higher main memory, optimizing overall cost.
4. Efficient Data Access:
   • Frequently accessed data remains cached, reducing repetitive fetch operations from the main memory.

Cache Initialization:

• During system startup or reset:
  1. The cache controller invalidates all previous data stored in the cache.
  2. Cache lines are marked as invalid until new data is loaded.
  3. Data is gradually loaded into the cache as it is accessed by the CPU.

---

10. Design a synchronous sequential circuit with two inputs T and C. The output attains a value of 1 when T = 1 and C moves from 1 to 0. Otherwise, the output is 0.

Solution:

Steps to Design the Circuit:

1. Understand the Problem Statement:

   • The circuit has two inputs: $T$ and $C$.
   • The output $Q$ becomes 1 when $T = 1$ and $C$ transitions from 1 to 0 (falling edge of $C$).

2. State Table:

   • Define the states based on $T$, $C$, and the required output.

T	C (Current State)	C (Previous State)	Q (Output)
0	X	X	0
1	1	1	0
1	0	1	1
1	0	0	0

3. Logic Implementation:
   • The circuit needs to detect the falling edge of $C$ (when $C_{prev} = 1$ and $C = 0$).
   • Use a D flip-flop to store the previous state of $C$, a NOT gate to detect $C$, and an AND gate for $T \cdot \overline{C} \cdot C_{prev}$.

---

11. What is a decoder? Draw the circuit of a 2-to-4 decoder and explain its functions.

Solution:

Definition:

• A decoder is a combinational circuit that converts binary input signals into a unique output line.
• A 2-to-4 decoder takes 2 input bits and activates one of the 4 output lines.

Truth Table for 2-to-4 Decoder:

Input $A_1 A_0$	Output $Y_3 Y_2 Y_1 Y_0$
00	0001
01	0010
10	0100
11	1000

Logic Equations:

• $Y_0 = \overline{A_1} \cdot \overline{A_0}$
• $Y_1 = \overline{A_1} \cdot A_0$
• $Y_2 = A_1 \cdot \overline{A_0}$
• $Y_3 = A_1 \cdot A_0$

Circuit Diagram:

• Use two inputs $A_1, A_0$, four AND gates, and inverters to implement the logic equations.

Functions:

• Decoders are used in memory addressing, instruction decoding in processors, and data routing.

---

12. Explain the difference between all of the following:

(a) Volatile and Non-Volatile Memory:

Feature	Volatile Memory	Non-Volatile Memory
Data Retention	Requires power to retain data	Retains data even without power
Example	RAM	ROM, Flash Memory

---

(b) Static and Dynamic Memory:

Feature	Static Memory (SRAM)	Dynamic Memory (DRAM)
Data Storage	Flip-flop	Capacitors
Speed	Faster	Slower

---

(c) Sequential and Random Access Memory:

Feature	Sequential Access Memory	Random Access Memory
Access Method	Access in sequential order	Access any location randomly
Example	Magnetic Tape	RAM

---

(d) Magnetic and Semiconductor Memory:

Feature	Magnetic Memory	Semiconductor Memory
Storage Mechanism	Magnetic properties	Semiconductor circuits
Example	Hard Disk, Magnetic Tape	RAM, ROM, Flash Memory

---

(e) Sum of Product (SOP) and Product of Sum (POS):

Feature	SOP	POS
Form	Logical OR of AND terms	Logical AND of OR terms
Example	$F = AB + BC$	$F = (A+B)(B+C)$

---

13. Design a 32 × 8 memory RAM chip using 16 × 4 memory chips.

Solution: To design a $32 \times 8$ RAM using $16 \times 4$ chips:

1. Calculate Memory Requirements:

   • Total memory required: $32 \times 8 = 256$ bits.
   • Memory per chip: $16 \times 4 = 64$ bits.
   • Number of chips required: $\frac{256}{64} = 4$ chips.

2. Configuration:

   • Use 2 rows of 2 chips each to implement the $32 \times 8$ configuration.
   • Address lines: $\log_2(32) = 5$ lines required.
   • Data lines: $8$ data lines.

3. Connections:

   • Combine the address lines and chip select signals to address the required chips.
   • Connect the outputs of the chips to form the required data bus.

---