Digital Logic 2023 Board Question Paper

Concept of Digital System

A digital system is an electronic system that processes, stores, and transmits information represented in discrete, physical electrical states—typically two binary logic voltage levels: Logic 1 (High, e.g., +5V or +3.3V) and Logic 0 (Low, e.g., 0V/Ground).

Key Advantages of Digital Systems over Analog Systems:

1. High Noise Immunity: Less susceptible to electrical noise and voltage fluctuations because minor voltage variations do not alter the interpreted binary 0 or 1 state.
2. Programmability & Flexibility: Digital circuits can be reprogrammed and driven by software.
3. Exact Reproducibility: Data can be duplicated and transmitted without generational degradation.

Combinations Represented by 5-Bit Binary Data

In a positional binary numeral system with (n) bits, the total number of distinct binary permutations or combinations is given by the power formula:

$$\text{Total Combinations} = 2^n$$

For a 5-bit binary data word ((n = 5)):

$$\text{Total Combinations} = 2^5 = 32 \text{ unique combinations}$$

These combinations range in numerical value from:

• Binary: 00000_2 to 11111_2
• Decimal: (0_{10}) to (31_{10}) ((2^n - 1)).

Use of Karnaugh Map (K-Map) in Digital Logic

A Karnaugh Map (K-Map), developed by Maurice Karnaugh in 1953, is a specialized graphical tabular method used to simplify and minimize Boolean algebraic expressions into optimal Sum of Products (SOP) or Product of Sums (POS) forms.

Primary Uses & Benefits:

1. Visual Simplification: Replaces cumbersome and error-prone algebraic manipulation (Boolean theorems) with systematic visual grouping of adjacent 1s (or 0s).
2. Guarantees Minimal Gate Count: Produces prime implicants that directly minimize the number of logic gates and literal inputs required in hardware implementation.
3. Gray Code Ordering: Adjacent cells differ by only a single bit (Hamming distance of 1), enabling visual application of the rule (A + \bar{A} = 1).
4. Handles Don’t Care Conditions: Readily incorporates “don’t care” ((X)) terms to form larger groupings.

Input Lines Required to Generate 995 Decoded Lines

A binary decoder with (n) input selection lines can generate up to (2^n) unique output decoded lines:

$$2^n \ge \text{Number of Output Lines}$$

Given: Decoded output lines = 995.

Let us evaluate powers of 2:

• For (n = 9): (2^9 = 512) ((512 < 995), insufficient lines)
• For (n = 10): (2^{10} = 1024) ((1024 \ge 995), sufficient lines)

$$\therefore \mathbf{10} \text{ input lines are required to generate 995 decoded lines.}$$

(The remaining (1024 - 995 = 29) decoded lines remain unused/don’t care).

Differences Between Combinational and Sequential Circuits

Problem of the “T” (Toggle) Flip-Flop

The primary problem associated with an unclocked or level-triggered T Flip-Flop is the Race Around Condition when (T = 1).

Description of the Problem:

• When (T = 1), the flip-flop is designed to toggle its state ((Q_{n+1} = \bar{Q}_n)) on every clock pulse.
• If the duration/width of the high clock pulse ((t_p)) is greater than the propagation delay of the internal logic gates ((t_{pd})), i.e., (t_p > t_{pd}): The output toggles multiple times uncontrollably within a single clock pulse interval.
• At the end of the clock pulse, the final state of (Q) becomes unpredictable and indeterminate.

Solution:

Overcome by using edge-triggering (positive or negative edge-triggered flip-flop) or a Master-Slave architecture.

Clock Pulses for 5-Bit Parallel-In Serial-Out (PISO) Shift Register

In a Parallel-In Serial-Out (PISO) shift register:

1. Parallel Loading:
   • All 5 bits are loaded simultaneously into the 5 flip-flops in 1 clock pulse (under control of the SHIFT/LOAD line set to Load).
2. Serial Output Shifting:
   • The first bit (least significant bit) is already available at the serial output pin immediately upon loading.
   • To shift out the remaining 4 bits serially, 4 clock pulses are required.

$$\text{Total Clock Pulses Required} = 1 \text{ (Load)} + 4 \text{ (Shifts)} = \mathbf{5 \text{ clock pulses.}}$$

Definition of Don’t Care Condition

In digital logic design, a Don’t Care Condition refers to an input combination for which the output of a Boolean function is not specified because:

1. The particular input combination is physically impossible to occur in the circuit environment (e.g., inputs (1010_2) to (1111_2) in a BCD circuit).
2. The output value produced for that specific input combination has no operational effect on the functioning of the system.

• Symbol: Represented by X or d in truth tables and K-Maps.
• Utility: In K-Map grouping, a don’t care term can be assumed as 1 if it helps form a larger group (quad/octet) to minimize gate count, or as 0 if it does not.

Don’t Care Conditions in an 8 × 3 Encoder

An 8-to-3 binary encoder has 8 input lines ((D_0, D_1, \dots, D_7)) and 3 binary output lines ((Y_2, Y_1, Y_0)).

1. Total Possible Input Combinations: With 8 binary input variables, the total number of theoretical input states is:
   $$2^8 = 256 \text{ states}$$
2. Valid Input Combinations: A standard basic binary encoder operates under the strict assumption that exactly one input line is active (HIGH) at any given moment:
   $$\text{Valid States} = 8 \text{ combinations}$$
   ((10000000, 01000000, \dots, 00000001)).
3. Don’t Care Combinations: All combinations where zero inputs or multiple inputs are HIGH simultaneously are invalid:
   $$\text{Don't Care Conditions} = 256 - 8 = \mathbf{248 \text{ combinations.}}$$

Why a Flip-Flop is Called a 1-Bit Memory Cell

A flip-flop is termed a fundamental 1-bit memory cell because:

1. Bistable States: It is a bistable multivibrator circuit possessing exactly two stable electrical states:
   • State 1: SET ((Q = 1, \bar{Q} = 0)) representing binary 1.
   • State 0: RESET ((Q = 0, \bar{Q} = 1)) representing binary 0.
2. Feedback Latching: Its cross-coupled logic gate structure provides regenerative feedback that latches and retains its stored state indefinitely as long as DC operating power is supplied, even after the initial triggering input signal is removed.
3. Foundation of Storage: By combining multiple flip-flops in parallel, registers, cache, and static RAM (SRAM) arrays capable of storing words of data are constructed.

Number System Conversion: Convert $2A3B.2A_{16}$

Given Hexadecimal number:

$$N = 2A3B.2A_{16}$$

1. Conversion to Binary:

Replace each hexadecimal digit with its 4-bit binary equivalent:

• (2_{16} = 0010_2)
• (A_{16} = 1010_2)
• (3_{16} = 0011_2)
• (B_{16} = 1011_2)
• Radix point .
• (2_{16} = 0010_2)
• (A_{16} = 1010_2)

$$\mathbf{(2A3B.2A)_{16} = (0010101000111011.00101010)_2 = (10101000111011.0010101)_2}$$

---

2. Conversion to Octal:

Group the binary digits into sets of 3 from the radix point:

• Integer part (group leftwards from point): 010 101 000 111 011
  • 010 = 2
  • 101 = 5
  • 000 = 0
  • 111 = 7
  • 011 = 3
• Fractional part (group rightwards from point, pad trailing zeroes if needed): 001 010 100
  • 001 = 1
  • 010 = 2
  • 100 = 4

$$\mathbf{(2A3B.2A)_{16} = (25073.124)_8}$$

---

3. Conversion to Decimal:

Expand by powers of 16:

$$\text{Integer} = (2 \times 16^3) + (10 \times 16^2) + (3 \times 16^1) + (11 \times 16^0)$$

$$= (2 \times 4096) + (10 \times 256) + (3 \times 16) + (11 \times 1)$$

$$= 8192 + 2560 + 48 + 11 = 10811_{10}$$

$$\text{Fraction} = (2 \times 16^{-1}) + (10 \times 16^{-2})$$

$$= \frac{2}{16} + \frac{10}{256} = 0.125 + 0.0390625 = 0.1640625_{10}$$

$$\mathbf{(2A3B.2A)_{16} = 10811.1640625_{10}}$$

Realization of NOT, AND, and OR Gates Using Universal NAND Gates

The NAND gate is a universal logic gate because any Boolean logic function can be constructed solely from NAND gates.

1. NOT Gate Using NAND:

Connect both inputs of a 2-input NAND gate together:

$$Y = \overline{A \cdot A} = \overline{A}$$

A -----+---\ NAND \
       |   )       o----- Y = NOT A
       +---/       /

2. AND Gate Using NAND:

Follow a NAND gate with an inverting NAND gate (cancels the negation):

$$Y = \overline{\overline{A \cdot B}} = A \cdot B$$

A -----+---\ NAND \
       |   )       o-----+---\ NAND \
B -----+---/       /     |   )       o----- Y = A AND B
                         +---/       /

3. OR Gate Using NAND:

By De Morgan’s Theorem:

$$A + B = \overline{\overline{A + B}} = \overline{\overline{A} \cdot \overline{B}}$$

Invert each input using a NAND gate, then feed their inverted outputs into a third NAND gate:

A -----+---\ NAND \
       +---/       o---+
                       |---\ NAND \
                       |   )       o----- Y = A OR B
B -----+---\ NAND \   |--/       /
       +---/       o---+

Solving Boolean Function Using 3-Variable K-Map

Given Boolean function:

$$F(x, y, z) = \bar{x}y + x\bar{y} + xyz$$

Step 1: Expand into Canonical Minterms

• (\bar{x}y = \bar{x}y(z + \bar{z}) = \bar{x}yz + \bar{x}y\bar{z} = m_3 + m_2)
• (x\bar{y} = x\bar{y}(z + \bar{z}) = x\bar{y}z + x\bar{y}\bar{z} = m_5 + m_4)
• (xyz = m_7)

$$\therefore F(x, y, z) = \sum m(2, 3, 4, 5, 7)$$

Step 2: Plotting the 3-Variable K-Map

Step 3: Forming Optimal Groups (Pairs)

1. Group 1 (Pair (m_2, m_3)):
   • Cells: ((0, 1, 0)) and ((0, 1, 1))
   • Term: (\bar{x}y)
2. Group 2 (Pair (m_4, m_5)):
   • Cells: ((1, 0, 0)) and ((1, 0, 1))
   • Term: (x\bar{y})
3. Group 3 (Pair (m_3, m_7)):
   • Cells: ((0, 1, 1)) and ((1, 1, 1))
   • Term: (yz)

Final Simplified Boolean Expression:

$$\mathbf{F(x, y, z) = \bar{x}y + x\bar{y} + yz = (x \oplus y) + yz}$$

Design of a 4 × 1 Multiplexer

A 4 × 1 Multiplexer (MUX) selects one of 4 data input lines ((I_0, I_1, I_2, I_3)) and routes it to a single output line ((Y)) using 2 select lines ((S_1, S_0)).

1. Truth Table:

2. Boolean Logic Equation:

$$Y = \bar{S}_1\bar{S}_0 I_0 + \bar{S}_1 S_0 I_1 + S_1\bar{S}_0 I_2 + S_1 S_0 I_3$$

3. Logic Circuit Realization:

• Components: Two NOT gates (inverters for (S_1, S_0)), four 3-input AND gates, and one 4-input OR gate.
• Each AND gate receives the unique combination of select line values and one data input line.
• The outputs of all 4 AND gates are fed into the OR gate to generate (Y).

Triggering of a Flip-Flop and Its Types

Triggering is the method of applying a clock pulse or control signal to cause a flip-flop to sample its inputs and transition between stable states.

Types of Triggering:

1. Level Triggering (Latches):

   • The circuit responds to inputs during the entire period that the clock pulse remains at a specific voltage level.
   • High-Level Triggering: Active when clock is 1 (+5V).
   • Low-Level Triggering: Active when clock is 0 (0V).
   • Limitation: Susceptible to noise and race conditions if inputs change during the active level.

2. Edge Triggering (Flip-Flops):

   • State transitions occur only at the rapid transition boundary (edge) of the clock signal, not during the high or low level duration.
   • Positive Edge-Triggered (Leading Edge): State changes exactly on the low-to-high transition ((0 \rightarrow 1)).
   • Negative Edge-Triggered (Trailing Edge): State changes exactly on the high-to-low transition ((1 \rightarrow 0)).

3. Pulse Triggering (Master-Slave):

   • Uses two interconnected latches: the Master samples data on the rising edge/high level, and the Slave transfers data to outputs on the falling edge.

Finding Equivalent POS (Product of Sums) for $F = AB + \bar{B}C$

Given SOP expression:

$$F = AB + \bar{B}C$$

Method: Algebraic Distributive Law

We apply the second distributive law of Boolean algebra:

$$X + YZ = (X + Y)(X + Z)$$

Treat (AB) as (X), (\bar{B}) as (Y), and (C) as (Z):

$$F = (AB + \bar{B})(AB + C)$$

Now distribute each sum term:

1. First term ((AB + \bar{B})):

   $$(AB + \bar{B}) = (A + \bar{B})(B + \bar{B})$$
   Since (B + \bar{B} = 1):
   $$(AB + \bar{B}) = (A + \bar{B}) \cdot 1 = (A + \bar{B})$$

2. Second term ((AB + C)):

   $$(AB + C) = (A + C)(B + C)$$

Equivalent POS Expression:

$$\mathbf{F = (A + \bar{B})(A + C)(B + C)}$$

Canonical Maxterm Form:

Evaluating missing literals:

• ((A + \bar{B} + C\bar{C}) = (A + \bar{B} + C)(A + \bar{B} + \bar{C}) = M_2 \cdot M_3)
• ((A + C + B\bar{B}) = (A + B + C)(A + \bar{B} + C) = M_0 \cdot M_2)
• ((B + C + A\bar{A}) = (A + B + C)(\bar{A} + B + C) = M_0 \cdot M_4)

$$\mathbf{F(A, B, C) = \prod M(0, 2, 3, 4) = (A+B+C)(A+\bar{B}+C)(A+\bar{B}+\bar{C})(\bar{A}+B+C)}$$

Gray Code & Design of 3-Bit Synchronous Binary Counter

1. Concept of Gray Code:

Gray Code (reflected binary code) is an unweighted, non-arithmetic binary code in which two successive numerical values differ in only one bit position.

• Primary Advantage: Prevents false intermediate switching transients (hazards and glitches) in high-speed digital systems, encoders, and angle/shaft position sensors.

---

2. Design of 3-Bit Synchronous Binary Counter (Using T Flip-Flops):

Counts from (000_2 \rightarrow 111_2) synchronously on every positive clock edge.

State Transition Table:

Minimal Flip-Flop Input Equations (from K-Maps):

• $$T_0 = 1$$
• $$T_1 = Q_0$$
• $$T_2 = Q_1 \cdot Q_0$$

Circuit Description:

• Connect the system clock simultaneously to all three T flip-flop clock inputs.
• Tie (T_0) to logic 1 (+5V).
• Connect output (Q_0) to input (T_1).
• Use a 2-input AND gate with inputs (Q_0) and (Q_1), and connect its output to (T_2).

Storing and Retrieving Data Bits 1011 Using PISO Shift Register

The specified device is a Parallel-In Serial-Out (PISO) shift register:

• It stores all bits simultaneously in 1 clock pulse (Parallel Load).
• It retrieves stored bits one at a time from the rightmost flip-flop (Serial Shift).

Step-by-Step Operations for Data 1011:

Let the 4-bit register consist of flip-flops (FF_3, FF_2, FF_1, FF_0) with parallel inputs (D_3=1, D_2=0, D_1=1, D_0=1).

1. Step 1: Parallel Loading (Clock Pulse 1):

   • Set control line SHIFT/\overline{LOAD} = 0.
   • Apply Clock Pulse 1: All 4 bits are latched in parallel.
   • Internal register state: (Q_3 Q_2 Q_1 Q_0 = 1011).
   • Bit 1 (from (FF_0)) is immediately available at serial output pin.

2. Step 2: Serial Retrieval (Right Shifting):

   • Set control line SHIFT/\overline{LOAD} = 1.
   • Clock Pulse 2: Bits shift right: State = 0101. Output bit = 1 (from (D_1)).
   • Clock Pulse 3: Bits shift right: State = 0010. Output bit = 0 (from (D_2)).
   • Clock Pulse 4: Bits shift right: State = 0001. Output bit = 1 (from (D_3)).

All 4 bits 1, 1, 0, 1 are completely retrieved serially in 4 clock periods.

Circuit Diagram of a 3-Bit Parallel Adder (Ripple Carry Adder)

A 3-bit parallel adder adds two 3-bit binary numbers:

$$A = (A_2 A_1 A_0)_2 \quad \text{and} \quad B = (B_2 B_1 B_0)_2$$

It generates a 3-bit sum (S = (S_2 S_1 S_0)_2) and an output carry (C_3).

Construction:

Constructed by cascading three Full Adders (FA) in series:

• Stage 0 (LSB): (FA_0) adds (A_0, B_0) and incoming carry (C_0) (typically tied to 0/ground). Produces sum (S_0) and carry (C_1).
• Stage 1: (FA_1) adds (A_1, B_1) and carry (C_1). Produces sum (S_1) and carry (C_2).
• Stage 2 (MSB): (FA_2) adds (A_2, B_2) and carry (C_2). Produces sum (S_2) and final carry (C_3).

Block Diagram:

         A2  B2             A1  B1             A0  B0
          |   |              |   |              |   |
          v   v              v   v              v   v
        +-------+          +-------+          +-------+
C3 <----|  FA2  |<--- C2 --|  FA1  |<--- C1 --|  FA0  |<--- C0 (GND = 0)
        +-------+          +-------+          +-------+
            |                  |                  |
            v                  v                  v
           S2                 S1                 S0

Full Adder Internal Equations:

• $$S_i = A_i \oplus B_i \oplus C_i$$
• $$C_{i+1} = A_i B_i + C_i (A_i \oplus B_i)$$

Advantage of JK Flip-Flop Over Clocked SR Flip-Flop & Operation

1. The Major Advantage:

In a clocked SR flip-flop, the input condition (S = 1, R = 1) is strictly forbidden/invalid because it drives both outputs (Q) and (\bar{Q}) to LOW simultaneously, violating the complementary rule and causing an unpredictable race condition when inputs drop to 0.

• The JK Flip-Flop completely eliminates this invalid state.
• When (J = 1, K = 1), the flip-flop safely and reliably toggles its output state ((Q_{n+1} = \bar{Q}_n)).

---

2. Operational Characteristics of JK Flip-Flop:

Characteristic Equation:

$$Q_{n+1} = J \bar{Q}_n + \bar{K} Q_n$$

Boolean Algebra Rules & Truth Table Verification

1. What is Boolean Algebra?

Boolean algebra, formulated by George Boole in 1854, is a mathematical system of logic used to analyze, model, and simplify binary electronic circuits. It operates on two-valued variables (TRUE/1 and FALSE/0) using three fundamental operations: AND (conjunction (\cdot)), OR (disjunction (+)), and NOT (negation (\bar{\phantom{A}})).

---

2. Five Important Boolean Rules (Laws):

1. Idempotent Law:
   $$A + A = A \quad \text{and} \quad A \cdot A = A$$
2. Complementarity Law:
   $$A + \bar{A} = 1 \quad \text{and} \quad A \cdot \bar{A} = 0$$
3. Identity Law:
   $$A + 0 = A \quad \text{and} \quad A \cdot 1 = A$$
4. De Morgan’s First Law:
   $$\overline{A + B} = \bar{A} \cdot \bar{B}$$
5. De Morgan’s Second Law:
   $$\overline{A \cdot B} = \bar{A} + \bar{B}$$

---

3. Verification of Two Rules Using Truth Table Method:

A. Verification of De Morgan’s First Law: $\overline{A + B} = \bar{A} \cdot \bar{B}$

Conclusion: Since the column for (\overline{A + B}) matches the column for (\bar{A} \cdot \bar{B}) across all rows, the law is verified.

B. Verification of Complementarity Law: $A + \bar{A} = 1$ and $A \cdot \bar{A} = 0$

Conclusion: (A + \bar{A}) is always 1 (Tautology) and (A \cdot \bar{A}) is always 0 (Fallacy).

Difference Between PLA and ROM & Design of MOD-150 Asynchronous Counter

1. Differences Between PLA and ROM:

---

2. Design of MOD-150 Asynchronous (Ripple) Counter:

A MOD-150 counter has 150 distinct states, counting from (0) up to (149_{10}), and resets to (0) on the 150th clock pulse.

Step 1: Number of Flip-Flops Required

$$2^n \ge 150$$

• For (n = 7): (2^7 = 128 < 150) (insufficient)
• For (n = 8): (2^8 = 256 \ge 150)
  $$\therefore \mathbf{8 \text{ Flip-Flops (T or JK)}} \text{ are required } (FF_0 \text{ to } FF_7).$$

Step 2: Binary Representation of Modulus 150

$$150_{10} = 128 + 16 + 4 + 2 = (10010110)_2$$

The bits correspond to:

$$Q_7=1, \; Q_6=0, \; Q_5=0, \; Q_4=1, \; Q_3=0, \; Q_2=1, \; Q_1=1, \; Q_0=0$$

Step 3: Reset Logic

When the counter reaches the transient state (150_{10} = 10010110_2), an active-LOW asynchronous clear signal ((\overline{\text{CLR}})) must be asserted to immediately reset all 8 flip-flops to (00000000_2).

• The bits that are HIGH at 150 are: (Q_7, Q_4, Q_2, Q_1).
• Connect these four outputs into a 4-input NAND gate:
  $$\overline{\text{CLEAR}} = \overline{Q_7 \cdot Q_4 \cdot Q_2 \cdot Q_1}$$
• Connect the output of this NAND gate to the active-low (\overline{\text{CLR}}) inputs of all 8 flip-flops.