Digital Logic

Simplification of $xy + x'z + yz$ to Minimum Literals

Given expression:

$$F = xy + x'z + yz$$

Step-by-Step Algebraic Simplification:

Multiply the third term (yz) by ((x + x’)), which equals 1 (Identity Law):

$$F = xy + x'z + yz(x + x')$$

$$F = xy + x'z + xyz + x'yz$$

Rearrange and group like terms:

$$F = (xy + xyz) + (x'z + x'yz)$$

Factor out common literals:

$$F = xy(1 + z) + x'z(1 + y)$$

Since ((1 + A) = 1) (Dominance Law):

$$F = xy(1) + x'z(1)$$

$$\mathbf{F = xy + x'z}$$

(Note: This is the formal algebraic proof of the Consensus Theorem in Boolean algebra).

Implementation of OR and AND Gates Using NAND Gates Only

1. AND Gate Implementation (Requires 2 NAND gates):

• First NAND gate computes (\overline{AB}).
• Second NAND gate acts as an inverter by tying inputs together:
  $$Y = \overline{\overline{AB}} = AB$$

2. OR Gate Implementation (Requires 3 NAND gates):

• Invert (A) using a NAND gate: (\bar{A} = \overline{AA}).
• Invert (B) using a NAND gate: (\bar{B} = \overline{BB}).
• Feed (\bar{A}) and (\bar{B}) into a third NAND gate (De Morgan’s Law):
  $$Y = \overline{\bar{A} \cdot \bar{B}} = \bar{\bar{A}} + \bar{\bar{B}} = A + B$$

Justification: Why Input 1 Cannot Be Applied to Both Inputs of a NOR Flip-Flop

In a basic SR latch constructed from two cross-coupled NOR gates:

1. Violation of Complementary Outputs: The output of a NOR gate is 0 whenever any of its inputs is 1. When both (S = 1) and (R = 1) are applied:
   $$Q = \overline{R + \bar{Q}} = \overline{1 + \bar{Q}} = 0$$
   $$\bar{Q} = \overline{S + Q} = \overline{1 + Q} = 0$$
   This causes both (Q) and (\bar{Q}) to become 0 simultaneously, which violates the fundamental operational definition that (Q) and (\bar{Q}) must always be complements of each other ((Q = \bar{\bar{Q}})).
2. Metastable Race Condition: When the inputs abruptly transition from (S=1, R=1) back to (0, 0), the gates enter an unpredictable race condition where internal propagation delays dictate which gate stabilizes first, causing indeterminate circuit behavior.

When is it Economical to Use a PLA Rather Than a PAL?

A Programmable Logic Array (PLA) features both a programmable AND array and a programmable OR array, whereas a PAL (Programmable Array Logic) has a programmable AND array but a fixed OR array.

Economic Advantages of PLA:

1. Sharing of Product Terms: When multiple output functions share identical minterms (product terms), a PLA generates each shared product term only once in the AND plane and connects it to multiple OR gates. A PAL cannot share product terms across outputs and must regenerate them redundantly.
2. Complex Functions with Large Literal Overlap: For intricate multi-output combinational systems (e.g., control unit micro-sequencers, bus decoders), the PLA requires significantly less silicon chip area and fewer total gates, making it more cost-effective.

Major Characteristics of Integrated Circuits (ICs)

Digital integrated circuits are evaluated based on the following key operational parameters:

1. Propagation Delay ($t_{pd}$): The time delay between the application of an input signal and the resulting change at the output (measured in nanoseconds, ns).
2. Power Dissipation ($P_D$): The electrical power consumed by the IC during operation, dissipated as heat (measured in milliwatts, mW).
3. Fan-Out: The maximum number of standard logic inputs that the output of an IC gate can drive reliably without voltage degradation.
4. Noise Margin: The maximum unwanted extraneous voltage noise signal that can be superimposed on the input without causing a false output transition.
5. Operating Speed / Frequency: The maximum clock frequency at which the IC can reliably function.

Differences Between T and JK Flip-Flop with Truth Table & Diagram

1. Comparison:

• A JK Flip-Flop is a universal 2-input sequential element ((J) for Set, (K) for Reset).
• A T Flip-Flop is a 1-input sequential element derived from the JK flip-flop by tying both (J) and (K) inputs together ((T = J = K)).

2. Truth Tables:

JK Flip-Flop:

(J)	(K)	Next State ((Q_{n+1}))	Mode
0	0	(Q_n)	Hold
0	1	0	Reset
1	0	1	Set
1	1	(\bar{Q}_n)	Toggle

T Flip-Flop:

(T)	Next State ((Q_{n+1}))	Mode
0	(Q_n)	Hold (No Change)
1	(\bar{Q}_n)	Toggle (Invert)

3. Logic Conversion:

A T flip-flop is created from a JK flip-flop by connecting a single control line (T) directly to both (J) and (K) inputs.

Implement $F(W, X, Y, Z) = \sum(0, 2, 4, 6, 10, 12, 14)$ Using Multiplexer

We implement the 4-variable function using an 8:1 Multiplexer.

• Select lines: Connect the three most significant variables:
  $$S_2 = W, \quad S_1 = X, \quad S_0 = Y$$
• Input data lines ((I_0) to (I_7)): Expressed in terms of the remaining variable (Z).

Implementation Table:

Select ((W X Y))	MUX Input	Minterms with (Z=0)	Minterms with (Z=1)	Value of Input Line
0 0 0	(I_0)	0	1	(\bar{Z})
0 0 1	(I_1)	2	3	(\bar{Z})
0 1 0	(I_2)	4	5	(\bar{Z})
0 1 1	(I_3)	6	7	(\bar{Z})
1 0 0	(I_4)	8	9	0
1 0 1	(I_5)	10	11	(\bar{Z})
1 1 0	(I_6)	12	13	(\bar{Z})
1 1 1	(I_7)	14	15	(\bar{Z})

Connection Scheme:

1. Connect select lines: (S_2 = W, S_1 = X, S_0 = Y).
2. For inputs (I_0, I_1, I_2, I_3, I_5, I_6, I_7): Connect to (\bar{Z}) (via NOT gate from (Z)).
3. For input (I_4): Connect to Logic 0 (Ground).

Design of a 3-Bit Synchronous Binary Counter Using JK Flip-Flops

A 3-bit binary counter advances through states: (000 \rightarrow 001 \rightarrow 010 \rightarrow 011 \rightarrow 100 \rightarrow 101 \rightarrow 110 \rightarrow 111 \rightarrow 000).

Excitation Table for JK Flip-Flops:

Present State ((Q_2 Q_1 Q_0))	Next State ((Q_2^+ Q_1^+ Q_0^+))	(J_2, K_2)	(J_1, K_1)	(J_0, K_0)
0 0 0	0 0 1	(0, X)	(0, X)	(1, X)
0 0 1	0 1 0	(0, X)	(1, X)	(X, 1)
0 1 0	0 1 1	(0, X)	(X, 0)	(1, X)
0 1 1	1 0 0	(1, X)	(X, 1)	(X, 1)
1 0 0	1 0 1	(X, 0)	(0, X)	(1, X)
1 0 1	1 1 0	(X, 0)	(1, X)	(X, 1)
1 1 0	1 1 1	(X, 0)	(X, 0)	(1, X)
1 1 1	0 0 0	(X, 1)	(X, 1)	(X, 1)

K-Map Simplification:

• $$J_0 = 1, \quad K_0 = 1$$
• $$J_1 = Q_0, \quad K_1 = Q_0$$
• $$J_2 = Q_1 Q_0, \quad K_2 = Q_1 Q_0$$

Circuit Implementation:

• All clock inputs are tied synchronously to the master clock line.
• (FF_0): (J_0 = K_0 = 1) (toggles every clock).
• (FF_1): (J_1 = K_1 = Q_0).
• (FF_2): (J_2 = K_2 = Q_1 \cdot Q_0) (output of an AND gate receiving (Q_0) and (Q_1)).

Shift Register Selection for Right Shifting Bit Sequence 1101

1. Definition of Shift Register:

A shift register is a cascade of flip-flops sharing a common clock, designed to store binary data and shift the bits laterally from one stage to the next on each clock edge.

2. Recommended Register:

For extracting the bit sequence 1101 serially after shifting to the right, a Serial-In Serial-Out (SISO) or Parallel-In Serial-Out (PISO) shift register configured for Right-Shift operation is used.

3. Operation (4-Bit Right Shift Register):

• Bits are shifted from (FF_3 \rightarrow FF_2 \rightarrow FF_1 \rightarrow FF_0).
• On Clock Pulse 1: Input bit 1 enters (FF_3).
• On Clock Pulse 2: Next bit 1 enters (FF_3); previous bit moves to (FF_2).
• On Clock Pulse 3: Bit 0 enters (FF_3); previous bits shift right.
• On Clock Pulse 4: Bit 1 enters (FF_3); register holds 1101.
• Additional clock pulses extract each bit serially from the (Q_0) output pin.

Design of 8 × 1 Multiplexer

An 8 × 1 Multiplexer selects one of 8 input data lines ((I_0) to (I_7)) and directs it to a single output (Y) using 3 select lines ((S_2, S_1, S_0)).

1. Truth Table:

(S_2)	(S_1)	(S_0)	Output ((Y))
0	0	0	(I_0)
0	0	1	(I_1)
0	1	0	(I_2)
0	1	1	(I_3)
1	0	0	(I_4)
1	0	1	(I_5)
1	1	0	(I_6)
1	1	1	(I_7)

2. Boolean Function:

$$Y = \bar{S}_2\bar{S}_1\bar{S}_0 I_0 + \bar{S}_2\bar{S}_1 S_0 I_1 + \bar{S}_2 S_1\bar{S}_0 I_2 + \bar{S}_2 S_1 S_0 I_3 + S_2\bar{S}_1\bar{S}_0 I_4 + S_2\bar{S}_1 S_0 I_5 + S_2 S_1\bar{S}_0 I_6 + S_2 S_1 S_0 I_7$$

3. Circuit Realization:

Consists of three NOT gates (producing (\bar{S}_2, \bar{S}_1, \bar{S}_0)), eight 4-input AND gates, and one 8-input OR gate.

Design of 3-Bit Synchronous Counter (State Equations)

A 3-bit synchronous counter employs 3 flip-flops clocked simultaneously.

State Equations:

• Let the states be (A, B, C) where (C) is LSB.
• Clock transitions occur simultaneously at all stages.
• Flip-flop excitation equations:
  $$T_C = 1$$
  $$T_B = C$$
  $$T_A = B \cdot C$$
  This ensures that (C) toggles every clock, (B) toggles when (C=1), and (A) toggles when both (B=1) and (C=1).

Standard Design Procedure of a Combinational Circuit

Designing a combinational logic circuit follows five sequential steps:

1. Problem Specification: Clearly define the required functional behavior, inputs, and outputs of the circuit.
2. Variable Assignment: Identify the number of binary input variables and output variables, assigning distinct letter symbols (e.g., (A, B, C) for inputs; (X, Y) for outputs).
3. Truth Table Formulation: Construct the truth table defining the exact required output value (0 or 1) for every possible (2^n) input combinations.
4. Boolean Simplification: Derive Boolean output functions from the truth table and simplify them using Karnaugh Maps (K-Maps) or algebraic laws to minimize literals and gate counts.
5. Logic Circuit Drawing: Draw the schematic circuit diagram using standard logic gate symbols (or universal NAND/NOR gates).

Design of 4 × 16 Decoder Using 2 × 4 Decoders

A 4 × 16 decoder has 4 inputs ((A_3, A_2, A_1, A_0)) and 16 outputs ((Y_0) to (Y_{15})).

Hierarchy Construction:

It is constructed using five 2 × 4 decoders with Enable (E) inputs:

• 1 Master Decoder (Decoder 0):
  • Inputs: (A_3, A_2)
  • Enabled permanently ((E = 1)).
  • Its 4 outputs ((D_0, D_1, D_2, D_3)) drive the Enable ((E)) inputs of the four secondary decoders.
• 4 Slave Decoders (Decoders 1 to 4):
  • All 4 share inputs (A_1, A_0).
  • Decoder 1 (Enabled by (D_0)): Generates outputs (Y_0) to (Y_3) when (A_3 A_2 = 00).
  • Decoder 2 (Enabled by (D_1)): Generates outputs (Y_4) to (Y_7) when (A_3 A_2 = 01).
  • Decoder 3 (Enabled by (D_2)): Generates outputs (Y_8) to (Y_{11}) when (A_3 A_2 = 10).
  • Decoder 4 (Enabled by (D_3)): Generates outputs (Y_{12}) to (Y_{15}) when (A_3 A_2 = 11).

Operating Mechanism:

Only one slave decoder is active at any given moment based on the high-order bits (A_3, A_2), ensuring strictly one of the 16 outputs is activated.

Circuit Design from State Diagram (Sequential Machine)

Standard Design Procedure:

1. State Assignment: Assign binary codes to abstract states (e.g., (S_0 = 00, S_1 = 01, S_2 = 10, S_3 = 11)).
2. Form State Table: List Present State, Input, Next State, and Output.
3. Determine Flip-Flop Type: Choose D, JK, or T flip-flops and derive the excitation requirements.
4. K-Map Simplification: Map Next State and Output functions into K-maps to obtain minimal input equations.
5. Draw Logic Schematic: Connect flip-flops and combinational gates according to the derived equations.

Design of MOD-16 Synchronous Up/Down Counter

A MOD-16 Synchronous Up/Down Counter counts through 16 states ((0000_2) to (1111_2)):

• When control input (M = 1): Counts UP ((0 \rightarrow 1 \rightarrow 2 \dots \rightarrow 15 \rightarrow 0)).
• When control input (M = 0): Counts DOWN ((15 \rightarrow 14 \dots \rightarrow 0 \rightarrow 15)).

Construction (4 T Flip-Flops $Q_3, Q_2, Q_1, Q_0$):

• (FF_0) (LSB): Always toggles on every clock edge:
  $$T_0 = 1$$
• (FF_1): Toggles when (Q_0=1) in UP mode OR when (\bar{Q}_0=1) in DOWN mode:
  $$T_1 = M \cdot Q_0 + \bar{M} \cdot \bar{Q}_0$$
• (FF_2): Toggles when both (Q_1 Q_0 = 1) (UP) OR when (\bar{Q}_1 \bar{Q}_0 = 1) (DOWN):
  $$T_2 = M \cdot Q_1 Q_0 + \bar{M} \cdot \bar{Q}_1 \bar{Q}_0$$
• (FF_3) (MSB):
  $$T_3 = M \cdot Q_2 Q_1 Q_0 + \bar{M} \cdot \bar{Q}_2 \bar{Q}_1 \bar{Q}_0$$

All clock inputs are connected synchronously to the master clock source.