A combinational circuit is a digital logic circuit whose output at any instant is determined solely by the current combination of inputs. It does not contain any memory elements, feedback paths, or storage components, meaning its past inputs or outputs do not influence its current output. The relationship between inputs and outputs can be described by Boolean expressions, truth tables, or logic diagrams.

Design of a 1's Complement BCD Circuit:

The objective is to design a combinational circuit with four inputs (W, X, Y, Z) representing a BCD decimal digit and four outputs (F1, F2, F3, F4) representing the 1's complement of the input binary pattern. For valid BCD inputs (0000 to 1001), the outputs will be the bit-wise inverse of the inputs. For invalid BCD inputs (1010 to 1111), the outputs are treated as "don't cares" (X) to simplify the logic.

1. Truth Table:

W	X	Y	Z	Decimal	F1	F2	F3	F4
0	0	0	0	0	1	1	1	1
0	0	0	1	1	1	1	1	0
0	0	1	0	2	1	1	0	1
0	0	1	1	3	1	1	0	0
0	1	0	0	4	1	0	1	1
0	1	0	1	5	1	0	1	0
0	1	1	0	6	1	0	0	1
0	1	1	1	7	1	0	0	0
1	0	0	0	8	0	1	1	1
1	0	0	1	9	0	1	1	0
1	0	1	0	(Invalid)	X	X	X	X
1	0	1	1	(Invalid)	X	X	X	X
1	1	0	0	(Invalid)	X	X	X	X
1	1	0	1	(Invalid)	X	X	X	X
1	1	1	0	(Invalid)	X	X	X	X
1	1	1	1	(Invalid)	X	X	X	X

2. K-Map Simplification for Output Functions:

Using 4-variable K-maps for each output (F1, F2, F3, F4) with inputs W, X, Y, Z, and 'X' for don't cares (minterms 10-15):

• K-map for F1:

  W\XY Z | 00 | 01 | 11 | 10
  -------|----|----|----|----
  00     | 1  | 1  | 1  | 1
  01     | 1  | 1  | 1  | 1
  11     | X  | X  | X  | X
  10     | 0  | X  | X  | X
  

  Grouping the eight '1's (cells 0000-0111) and the don't cares simplifies F1.
  Simplified expression: $F_1 = W'$

• K-map for F2:

  W\XY Z | 00 | 01 | 11 | 10
  -------|----|----|----|----
  00     | 1  | 1  | 1  | 1
  01     | 0  | 0  | 0  | 0
  11     | X  | X  | X  | X
  10     | 1  | X  | X  | X
  

  Grouping (0000, 0001, 0011, 0010) gives $W'X'$.
  Grouping (1000, 1010, 1100, 1110) utilizing don't cares gives $WZ'$.
  Simplified expression: $F_2 = W'X' + WZ'$

• K-map for F3:

  W\XY Z | 00 | 01 | 11 | 10
  -------|----|----|----|----
  00     | 1  | 1  | 0  | 0
  01     | 1  | 1  | 0  | 0
  11     | X  | X  | X  | X
  10     | 1  | 1  | X  | X
  

  Grouping (0000, 0001, 0100, 0101) gives $W'Y'$.
  Grouping (1000, 1001, 1100, 1101) utilizing don't cares gives $WX'$.
  Simplified expression: $F_3 = W'Y' + WX'$

• K-map for F4:

  W\XY Z | 00 | 01 | 11 | 10
  -------|----|----|----|----
  00     | 1  | 0  | 0  | 1
  01     | 1  | 0  | 0  | 1
  11     | X  | X  | X  | X
  10     | 1  | 0  | X  | X
  

  Grouping all '1's and don't cares that align with Z=0 gives Z'.
  Simplified expression: $F_4 = Z'$

3. Logic Diagram:

Based on the simplified Boolean expressions, the circuit can be implemented using NOT, AND, and OR gates.

• $F_1 = W'$
• $F_2 = W'X' + WZ'$
• $F_3 = W'Y' + WX'$
• $F_4 = Z'$

<<<GRAPHVIZ_START>>>
digraph CombinationalCircuit {
rankdir=LR;
splines=ortho;

// Input Nodes
node [shape=none, width=0.1, height=0.1];
W [label="W"];
X [label="X"];
Y [label="Y"];
Z [label="Z"];

// Output Nodes
F1 [label="F1"];
F2 [label="F2"];
F3 [label="F3"];
F4 [label="F4"];

// Inverter Gates
node [shape=box, label="NOT", style="filled", fillcolor="lightblue"];
NOT_W;
NOT_X;
NOT_Y;
NOT_Z;

// AND Gates
node [shape=box, label="AND", style="filled", fillcolor="lightgreen"];
AND_W_X_prime; // for W'X'
AND_W_Z_prime; // for WZ'
AND_W_Y_prime; // for W'Y'
AND_W_prime_X_prime; // for WX' (corrected label to match WX')

// OR Gates
node [shape=box, label="OR", style="filled", fillcolor="lightcoral"];
OR_F2;
OR_F3;

// Connections
// F1 = W'
W -> NOT_W;
NOT_W -> F1;

// F2 = W'X' + WZ'
NOT_W -> AND_W_X_prime;
NOT_X -> AND_W_X_prime;
W -> AND_W_Z_prime;
NOT_Z -> AND_W_Z_prime;
AND_W_X_prime -> OR_F2;
AND_W_Z_prime -> OR_F2;
OR_F2 -> F2;

// F3 = W'Y' + WX'
NOT_W -> AND_W_Y_prime;
NOT_Y -> AND_W_Y_prime;
W -> AND_W_prime_X_prime; // This connection is W -> AND_W_prime_X_prime
NOT_X -> AND_W_prime_X_prime; // This connection is X' -> AND_W_prime_X_prime
AND_W_Y_prime -> OR_F3;
AND_W_prime_X_prime -> OR_F3;
OR_F3 -> F3;

// F4 = Z'
Z -> NOT_Z; // Z is inverted to get NOT_Z, which then goes to F4
NOT_Z -> F4;
}
<<<GRAPHVIZ_END>>>

An asynchronous counter, also known as a ripple counter, is a type of sequential circuit where the flip-flops are not clocked simultaneously. Instead, the output of one flip-flop serves as the clock input for the next flip-flop in the sequence. This cascading clocking mechanism creates a "ripple" effect as the state change propagates through the counter.

Characteristics:

• Sequential Clocking: Each flip-flop (except the first) is triggered by the output transition of the preceding flip-flop.
• Simplicity: Generally simpler to design than synchronous counters for basic binary sequences.
• Propagation Delay: Due to the ripple effect, there is a cumulative propagation delay, limiting the maximum operating frequency. This can lead to race conditions or incorrect states at high speeds.
• Decoding Glitches: Outputs may not change simultaneously, leading to transient intermediate states (glitches) when decoding specific states.

While traditional asynchronous counters are simple binary up/down counters, designing a counter for an arbitrary sequence (like 0-1-4-6-7) typically requires a synchronous state machine approach, even if the term "asynchronous counter" is sometimes used loosely to describe counters that are not standard binary ripple counters. For this specific sequence design, a synchronous design using T flip-flops will be employed.

Design of Asynchronous Counter for 0-1-4-6-7 using T Flip-Flops

The sequence to be counted is 0-1-4-6-7.
The maximum state is 7 (binary 111).
Number of flip-flops required (N) is determined by 2^N >= Max_State_Value.
Since 2^2 = 4 and 2^3 = 8, we need 3 flip-flops (Q2 Q1 Q0).

1. State Table and Excitation Table:
The sequence is 000 -> 001 -> 100 -> 110 -> 111 -> 000.
The unused states are 010 (2), 011 (3), 101 (5). These will be treated as "don't cares" (X) in the K-maps.

Current State (Q2 Q1 Q0)	Next State (Q2+ Q1+ Q0+)	T2	T1	T0
000 (0)	001 (1)	0	0	1
001 (1)	100 (4)	1	0	1
010 (2)	X X X	X	X	X
011 (3)	X X X	X	X	X
100 (4)	110 (6)	0	1	0
101 (5)	X X X	X	X	X
110 (6)	111 (7)	0	0	1
111 (7)	000 (0)	1	1	1

Excitation Table for T Flip-Flop:
| Q | Q+ | T |
| : | :--- | :- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

2. K-Map Simplification for T-Flip-Flop Inputs:

a) T0 Input:
T0(Q2, Q1, Q0) = Σm(0, 1, 6, 7) + d(2, 3, 5)

Q2\Q1Q0	00	01	11	10
0	1	1	X	X
1	0	X	1	1

Groupings:

1. Group of four: Q2' (m0, m1, d2, d3)

2. Group of four: Q1 (m6, m7, d3, d2) -- No, this is incorrect grouping for Q1
   Correct groups for T0:

   • (000, 001) covers Q2'Q1'
   • (110, 111) covers Q2Q1
   • (000, 110) covers Q1'Q0'
   • (001, 111) covers Q1'Q0

   Let's re-simplify the K-map systematically:

   • Group 1 (m0, m1, d3, d2): Q2'
   • Group 2 (m6, m7, d3, d2): Q1

   So, T0 = Q2' + Q1

b) T1 Input:
T1(Q2, Q1, Q0) = Σm(4, 7) + d(2, 3, 5)

Q2\Q1Q0	00	01	11	10
0	0	0	X	X
1	1	X	1	0

Groupings:

1. Group of two: m4 with d5 (100, 101) -> Q2Q1'

2. Group of two: m7 with d3 (111, 011) -> Q1Q0

   Let's re-simplify T1:

   • m4 (100) -> Q2Q1'Q0'
   • m7 (111) -> Q2Q1Q0
   • Can use d5 (101) with m4
   • Can use d3 (011) with m7

   K-map for T1:
   The 1s are at (1,0) and (1,3).
   Using don't cares (0,2), (0,3), (1,1):
   (1,0) is Q2Q1'Q0'
   (1,3) is Q2Q1Q0

   No simple grouping across '1's.
   T1 = Q2Q1'Q0' + Q2Q1Q0
   This simplifies to Q2Q0'(Q1' + Q1) when Q2Q1Q0 is taken as 1. No.
   Let's recheck the table for T1.
   000 -> 0
   001 -> 0
   100 -> 1
   110 -> 0
   111 -> 1
   Ah, T1 for 111 is 1 not 0.
   So T1(Q2, Q1, Q0) = Σm(4, 7) + d(2, 3, 5) is correct.
   My K-map is correct as well.

   No further simplification possible for T1 beyond the sum of minterms:
   T1 = Q2Q1'Q0' + Q2Q1Q0

c) T2 Input:
T2(Q2, Q1, Q0) = Σm(1, 7) + d(2, 3, 5)

Q2\Q1Q0	00	01	11	10
0	0	1	X	X
1	0	X	1	0

Groupings:

1. m1 (001) -> Q2'Q1'Q0
2. m7 (111) -> Q2Q1Q0

No further simplification possible for T2 beyond the sum of minterms:
T2 = Q2'Q1'Q0 + Q2Q1Q0

Summary of Flip-Flop Input Equations:

• T0 = Q2' + Q1
• T1 = Q2Q1'Q0' + Q2Q1Q0
• T2 = Q2'Q1'Q0 + Q2Q1Q0

3. Logic Circuit Diagram:
The circuit will consist of three T flip-flops (FF2, FF1, FF0) with a common clock input. The outputs (Q2, Q1, Q0) and their complements (Q2', Q1', Q0') will feed back as inputs to combinational logic gates to generate the required T inputs.

<<<GRAPHVIZ_START>>>
digraph G {
rankdir=LR;
splines=polyline;

node [shape=rect, style=filled, fillcolor=lightblue];
clk [label="Clock"];

node [shape=box, style=filled, fillcolor=lightgrey, width=0.8, height=0.5];
FF2 [label="T-FF\nQ2"];
FF1 [label="T-FF\nQ1"];
FF0 [label="T-FF\nQ0"];

node [shape=circle, style=filled, fillcolor=white, label=""];
Q2_node [label="Q2"];
Q1_node [label="Q1"];
Q0_node [label="Q0"];
Q2n_node [label="Q2'"];
Q1n_node [label="Q1'"];
Q0n_node [label="Q0'"];

node [shape=circle, style=filled, fillcolor=lightgreen];
INV_Q1 [label="INV", shape=triangle, orientation=270];
INV_Q0 [label="INV", shape=triangle, orientation=270];
INV_Q2 [label="INV", shape=triangle, orientation=270];

node [shape=oval, style=filled, fillcolor=orange];
OR_T0 [label="OR"];
AND_T1_1 [label="AND"];
AND_T1_2 [label="AND"];
OR_T1 [label="OR"];
AND_T2_1 [label="AND"];
AND_T2_2 [label="AND"];
OR_T2 [label="OR"];

// Clock connections
clk -> FF2:clk;
clk -> FF1:clk;
clk -> FF0:clk;

// FF Outputs
FF2:Q -> Q2_node;
FF2:Qn -> Q2n_node;
FF1:Q -> Q1_node;
FF1:Qn -> Q1n_node;
FF0:Q -> Q0_node;
FF0:Qn -> Q0n_node;

// Inverters for complements
Q2_node -> INV_Q2 [label=""];
INV_Q2 -> Q2n_node;
Q1_node -> INV_Q1 [label=""];
INV_Q1 -> Q1n_node;
Q0_node -> INV_Q0 [label=""];
INV_Q0 -> Q0n_node;

// T0 = Q2' + Q1
Q2n_node -> OR_T0:in1;
Q1_node -> OR_T0:in2;
OR_T0 -> FF0:T [label="T0"];

// T1 = Q2Q1'Q0' + Q2Q1Q0
Q2_node -> AND_T1_1:in1;
Q1n_node -> AND_T1_1:in2;
Q0n_node -> AND_T1_1:in3;
AND_T1_1 -> OR_T1:in1;

Q2_node -> AND_T1_2:in1;
Q1_node -> AND_T1_2:in2;
Q0_node -> AND_T1_2:in3;
AND_T1_2 -> OR_T1:in2;
OR_T1 -> FF1:T [label="T1"];

// T2 = Q2'Q1'Q0 + Q2Q1Q0
Q2n_node -> AND_T2_1:in1;
Q1n_node -> AND_T2_1:in2;
Q0_node -> AND_T2_1:in3;
AND_T2_1 -> OR_T2:in1;

Q2_node -> AND_T2_2:in1;
Q1_node -> AND_T2_2:in2;
Q0_node -> AND_T2_2:in3;
AND_T2_2 -> OR_T2:in2;
OR_T2 -> FF2:T [label="T2"];

// Invisible nodes for clean layout
{rank=same; clk;}
{rank=same; FF2; FF1; FF0;}
{rank=same; Q2_node; Q1_node; Q0_node;}
{rank=same; Q2n_node; Q1n_node; Q0n_node;}
}
<<<GRAPHVIZ_END>>>

The Boolean function to be implemented is F(P,Q,R,S) = ∑ (3,4,6,8,9,14).

a. 8 to 1 Multiplexer Implementation

To implement a 4-variable Boolean function using an 8-to-1 multiplexer, three of the variables (P, Q, R) are typically used as select lines, and the remaining variable (S) along with constants (0, 1) and its complement (S') are used as data inputs.

1. Assign Select Lines: Let P, Q, R be the select lines S2, S1, S0 respectively.

2. Derive Data Inputs (I0 to I7): For each combination of PQR, the corresponding MUX input is determined by examining the function's output for S=0 and S=1.

   • I0 (PQR=000): F(0000)=0, F(0001)=0. Input I0 = 0.
   • I1 (PQR=001): F(0010)=0, F(0011)=1 (m3). Input I1 = S.
   • I2 (PQR=010): F(0100)=1 (m4), F(0101)=0. Input I2 = S'.
   • I3 (PQR=011): F(0110)=1 (m6), F(0111)=0. Input I3 = S'.
   • I4 (PQR=100): F(1000)=1 (m8), F(1001)=1 (m9). Input I4 = 1.
   • I5 (PQR=101): F(1010)=0, F(1011)=0. Input I5 = 0.
   • I6 (PQR=110): F(1100)=0, F(1101)=0. Input I6 = 0.
   • I7 (PQR=111): F(1110)=1 (m14), F(1111)=0. Input I7 = S'.

3. Summary of MUX Inputs:

   • I0 = 0
   • I1 = S
   • I2 = S'
   • I3 = S'
   • I4 = 1
   • I5 = 0
   • I6 = 0
   • I7 = S'

The P, Q, R variables are connected to the select lines of the 8-to-1 multiplexer, and the derived inputs (0, 1, S, S') are connected to the corresponding data input lines.

b. PLA (Programmable Logic Array) Implementation

For PLA implementation, the Boolean function must first be simplified into its minimal Sum of Products (SOP) form using a K-map.

1. K-map for F(P,Q,R,S) = ∑ (3,4,6,8,9,14):

   PQ\RS	00	01	11	10
   00	0	0	1	0
   01	1	0	0	1
   11	0	0	0	1
   10	1	1	0	0

2. Grouping Prime Implicants:

   • Group 1 (m8, m9): P Q' R' S' + P Q' R' S = P Q' R'
   • Group 2 (m4, m6): P' Q R' S' + P' Q R S' = P' Q S'
   • Remaining single minterms: m3 (P' Q' R S) and m14 (P Q R S'). These are essential prime implicants.

3. Minimal SOP Expression:
   F = P Q' R' + P' Q S' + P' Q' R S + P Q R S'

4. PLA Structure:
   A PLA consists of an AND array and an OR array. The inputs P, Q, R, S and their complements (P', Q', R', S') are fed into the AND array, which generates the product terms. These product terms are then fed into the OR array, which combines them to produce the final output function F.

   • Product Terms (AND array outputs):

     • T1 = P Q' R'
     • T2 = P' Q S'
     • T3 = P' Q' R S
     • T4 = P Q R S'

   • Sum Term (OR array input):

     • F = T1 + T2 + T3 + T4

   The connections within the PLA's AND and OR arrays are programmed as follows:

   Product Term	P	Q	R	S	P'	Q'	R'	S'	F (Output)
   T1	X					X	X		X
   T2		X			X			X	X
   T3			X	X	X	X			X
   T4	X	X	X					X	X

   (An 'X' indicates a programmable connection.)

c. Decoder Implementation

To implement a 4-variable Boolean function F(P,Q,R,S) using a decoder, a decoder with 4 inputs and 2^4 = 16 outputs is required.

1. Decoder Type: A 4-to-16 line decoder.

2. Inputs: The variables P, Q, R, S are connected to the decoder's input lines (e.g., P as MSB, S as LSB).

3. Outputs: The decoder generates all 16 minterms (M0 to M15) at its output lines.

4. OR Gate Connections: The minterm outputs corresponding to the function's ON-set are connected to the inputs of a multi-input OR gate.

   F(P,Q,R,S) = M3 + M4 + M6 + M8 + M9 + M14

   Therefore, the outputs M3, M4, M6, M8, M9, and M14 from the 4-to-16 decoder are connected as inputs to a 6-input OR gate, whose output will be F.

a. (011101)$_2$ – (110011)$_2$ using 2’s complement

1. Minuend: A = (011101)$_2$
2. Subtrahend: B = (110011)$_2$
3. Find 2's complement of B:
   • 1's complement of B = (001100)$_2$
   • 2's complement of B = 1's complement of B + 1 = (001100)$_2$ + (000001)$_2$ = (001101)$_2$
4. Add A to 2's complement of B:
   • A + (2's complement of B)
   • (011101)$_2$
   • • (001101)$_2$

   • ---

   • (101010)$_2$
5. Analyze result:
   • No carry-out from the most significant bit.
   • The result is negative and in 2's complement form.
6. Find the magnitude of the result:
   • Take 2's complement of (101010)$_2$:
     • 1's complement = (010101)$_2$
     • Add 1 = (010101)$_2$ + (000001)$_2$ = (010110)$_2$
7. Final Answer: -(010110)$_2$

b. (89344)${10}$ – (98654)${10}$ using 9’s complement

1. Minuend: A = 89344
2. Subtrahend: B = 98654
3. Find 9's complement of B:
   • 9's complement of B = 99999 - 98654 = 01345
4. Add A to 9's complement of B:
   • A + (9's complement of B)
   • 89344
   • • 01345

   • ---

   • 90689
5. Analyze result:
   • No end-around carry (no carry out from the leftmost digit).
   • The result is negative and in 9's complement form.
6. Find the magnitude of the result:
   • Take 9's complement of 90689:
     • 9's complement = 99999 - 90689 = 09310
7. Final Answer: -9310

K-map Simplification:

The given Boolean function is f(P,Q,R,S) = ∑(3,4,7,8,14) with don't cares d(P,Q,R,S) = ∑(1,6,9,13).

1. Populate the K-map:
   Place '1's for the minterms in f and 'X's for the don't care conditions in d.

   P Q \ R S | 00 | 01 | 11 | 10

   00 (P'Q') | 0 | X | 1 | 0
   01 (P'Q) | 1 | 0 | 1 | X
   11 (PQ) | 0 | X | 0 | 1
   10 (PQ') | 1 | X | 0 | 0

   (Cell indices: 00=0, 01=1, 02=3, 03=2, etc.)
   Mapped:
   m0=0, m1=X, m2=0, m3=1
   m4=1, m5=0, m6=X, m7=1
   m8=1, m9=X, m10=0, m11=0
   m12=0, m13=X, m14=1, m15=0

2. Group the '1's and 'X's:

   • Group 1 (Quad): (m1(X), m3(1), m7(1), m13(X))
     These four cells (P'Q'R'S, P'Q'RS, P'QRS, PQR'S) share the common literal 'S'.
     This group simplifies to S.
     (Covers m3, m7 and uses m1, m13).

   • Group 2 (Pair): (m4(1), m8(1))
     These two cells (P'QR'S', PQ'R'S') share the common literals 'R'S''.
     This group simplifies to R'S'.
     (Covers m4, m8).

   • Group 3 (Pair): (m13(X), m14(1))
     These two cells (PQR'S, PQRS') share the common literals 'PQR''.
     This group simplifies to PQR'.
     (Covers m14 and uses m13).

3. Minimal SOP Expression:
   All '1's (m3, m4, m7, m8, m14) are now covered. The simplified Boolean expression is the sum of these prime implicants:

   f = S + R'S' + PQR'

---

NAND Gate Circuit Design:

The simplified expression is in Sum-of-Products (SOP) form: F = S + R'S' + PQR'.
A two-level NAND-NAND implementation can directly realize an SOP expression. The first level consists of NAND gates for each product term (including single literals), and the second level is a single NAND gate that takes the outputs of the first level as inputs.

For F = T1 + T2 + T3 where T1 = S, T2 = R'S', T3 = PQR', the NAND implementation is F = ( (T1)' . (T2)' . (T3)' )'.

1. Inverters for required complements:

   • R needs to be inverted to R'. (1x 2-input NAND gate)
   • S needs to be inverted to S'. (1x 2-input NAND gate)

2. NAND gates for product terms:

   • Term R'S': Inputs R' and S' to a 2-input NAND gate. Output: (R'S')'. (1x 2-input NAND gate)
   • Term PQR': Inputs P, Q, and R' to a 3-input NAND gate. Output: (PQR')'. (1x 3-input NAND gate)

3. Final NAND gate:
   This gate takes the inverted versions of the original terms.
   Inputs: S' (from step 1), (R'S')' (from step 2), (PQR')' (from step 2).
   Output: F = ( S' . (R'S')' . (PQR')' )'. (1x 3-input NAND gate)

Total Number of NAND Gates: 5

Circuit Diagram (Graphviz DOT code):
<<<GRAPHVIZ_START>>>
digraph G {
rankdir=LR;
node [shape=circle, style=filled, fillcolor=lightblue];
P [label="P", shape=none];
Q [label="Q", shape=none];
R [label="R", shape=none];
S [label="S", shape=none];
F [label="F", shape=none];

node [shape=box, style="filled,rounded", fillcolor=lightgrey];
// Inverters
g_R_prime [label="NAND (2)", fillcolor=white];
g_S_prime [label="NAND (2)", fillcolor=white];

// First level NAND gates for product terms
g_R_S_prime [label="NAND (2)", fillcolor=white];
g_PQR_prime [label="NAND (3)", fillcolor=white];

// Final NAND gate
g_final [label="NAND (3)", fillcolor=white];

// Connections
R -> g_R_prime;
R -> g_R_prime; // R' = (R NAND R)

S -> g_S_prime;
S -> g_S_prime; // S' = (S NAND S)

g_R_prime -> g_R_S_prime; // Input R' to (R'S')'
g_S_prime -> g_R_S_prime; // Input S' to (R'S')'

P -> g_PQR_prime; // Input P to (PQR')'
Q -> g_PQR_prime; // Input Q to (PQR')'
g_R_prime -> g_PQR_prime; // Input R' to (PQR')'

g_S_prime -> g_final; // Input S' to final NAND
g_R_S_prime -> g_final; // Input (R'S')' to final NAND
g_PQR_prime -> g_final; // Input (PQR')' to final NAND

g_final -> F; // Output F
}
<<<GRAPHVIZ_END>>>

The drawback of an RS Flip-Flop arises from its "forbidden" or "invalid" state where both Set (S) and Reset (R) inputs are simultaneously high (S=1, R=1). In this state, both Q and Q' outputs attempt to go low, violating the fundamental principle that Q and Q' must always be complements. When the S and R inputs then return to 0, the final output state of the flip-flop becomes unpredictable and dependent on which gate switches slightly faster, leading to an indeterminate state.

D Flip-Flop

The D (Data) Flip-Flop is designed to eliminate the forbidden state of the RS Flip-Flop by ensuring that the S and R inputs are always complementary. It acts as a 1-bit memory element, where the output Q follows the input D when the clock signal is active.

Logic Diagram:
A D Flip-Flop can be constructed from an SR Latch by adding an inverter between the D input and the R input of the SR latch, and then gating these inputs with a clock signal.

<<<GRAPHVIZ_START>>>
digraph Clocked_D_Latch {
node [shape=rect];

// Inputs
D_in [label="D"];
Clk_in [label="Clk"];

// Gating logic
and1 [label="AND"];
and2 [label="AND"];
not1 [label="NOT"];

// SR Latch (NAND-based)
nand_s [label="NAND", fillcolor=lightgrey, style=filled];
nand_r [label="NAND", fillcolor=lightgrey, style=filled];

// Outputs
Q_out [label="Q"];
Q_bar_out [label="Q'"];

// Connections
D_in -> and1;
Clk_in -> and1;
and1 -> nand_s; // This is the S input to the SR latch

D_in -> not1;
not1 -> and2;
Clk_in -> and2;
and2 -> nand_r; // This is the R input to the SR latch

nand_s -> Q_out;
Q_out -> nand_r; // Cross-coupling

nand_r -> Q_bar_out;
Q_bar_out -> nand_s; // Cross-coupling

}
<<<GRAPHVIZ_END>>>

Characteristics Table:
The characteristic table of a D Flip-Flop shows the next state Q(t+1) based on the current input D. When the clock is active, the next state of the flip-flop becomes equal to the D input.

D	Clk	Q(t+1)
0	1	0
1	1	1
X	0	Q(t)
X denotes a "don't care" condition. When Clk=0, the output Q(t+1) retains its previous state Q(t).

Characteristic Equation:
The characteristic equation for a D Flip-Flop is derived directly from its behavior, where the next state is simply the value of the D input when the clock is active.

Q(t+1) = D

Full Subtractor Design

A full subtractor is a combinational logic circuit that performs subtraction of three bits: the minuend (A), subtrahend (B), and borrow-in (B_in). It produces two outputs: Difference (D) and Borrow-out (B_out).

Truth Table

The truth table for a full subtractor is as follows:

A	B	B_in	D	B_out
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	1
1	0	0	1	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

Boolean Expressions

From the truth table, the minimized Boolean expressions for Difference (D) and Borrow-out (B_out) can be derived (e.g., using K-maps):

• Difference (D):
  D = A'B'B_in + A'BB_in' + AB'B_in' + ABB_in
  D = A ⊕ B ⊕ B_in

• Borrow-out (B_out):
  B_out = A'B'B_in + A'BB_in' + A'BB_in + ABB_in
  B_out = A'B + A'B_in + BB_in

Logic Diagram

The logic diagram for the full subtractor implemented using XOR, AND, OR, and NOT gates is shown below:

<<<GRAPHVIZ_START>>>
digraph FullSubtractor {
rankdir=LR;
node [shape=box, style=filled, fillcolor=lightgray, fixedsize=true, width=0.8, height=0.4];
edge [dir=none];

// Inputs
A_in [label="A", shape=plaintext, width=0.3, height=0.3];
B_in_main [label="B", shape=plaintext, width=0.3, height=0.3];
BorrowIn_main [label="B_in", shape=plaintext, width=0.3, height=0.3];

// Logic for Difference (D = A XOR B XOR B_in)
xor_D1 [label="XOR"];
xor_D2 [label="XOR"];
D_out [label="D", shape=plaintext, width=0.3, height=0.3];

// Logic for Borrow Out (B_out = A'B + A'B_in + BB_in)
not_A [label="NOT", shape=invtriangle, height=0.3, width=0.3];

and_A_prime_B [label="AND"];
and_A_prime_Bin [label="AND"];
and_B_Bin [label="AND"];

or_Bout [label="OR"];
BorrowOut_out [label="B_out", shape=plaintext, width=0.3, height=0.3];

// Connections for Difference
A_in -> xor_D1;
B_in_main -> xor_D1;
xor_D1 -> xor_D2;
BorrowIn_main -> xor_D2;
xor_D2 -> D_out;

// Connections for Borrow Out
A_in -> not_A;

not_A -> and_A_prime_B;
B_in_main -> and_A_prime_B;

not_A -> and_A_prime_Bin;
BorrowIn_main -> and_A_prime_Bin;

B_in_main -> and_B_Bin;
BorrowIn_main -> and_B_Bin;

and_A_prime_B -> or_Bout;
and_A_prime_Bin -> or_Bout;
and_B_Bin -> or_Bout;
or_Bout -> BorrowOut_out;

// Layout hints
{rank=same; A_in B_in_main BorrowIn_main}
{rank=same; D_out BorrowOut_out}

}
<<<GRAPHVIZ_END>>>

A shift register is a sequential logic circuit that can store and shift binary data. It consists of a series of flip-flops, typically D flip-flops, connected in cascade. The data can be shifted from one flip-flop to the next under the control of a clock signal. Shift registers are fundamental components for data storage, conversion between serial and parallel formats, and various arithmetic operations.

4-bit Serial-In, Serial-Out (SISO) Shift Register

A Serial-In, Serial-Out (SISO) shift register accepts data one bit at a time (serially) and outputs data one bit at a time (serially). For an N-bit SISO register, it requires N clock pulses to load N bits of data and another N clock pulses to output all N bits of data. Data shifts through the register from one flip-flop to the next on each clock edge.

Operation:

1. Data is applied to the serial input (Din).
2. On each active clock edge, the data bit at Din is transferred to the first flip-flop (Q0).
3. Simultaneously, the data from Q0 shifts to Q1, Q1 to Q2, and Q2 to Q3.
4. After N clock pulses, all N bits of data are loaded into the register.
5. To output the data, it is shifted out one bit at a time from the last flip-flop (Q3 in a 4-bit register).

Timing Diagram (Loading '1011' LSB first into Q0):
<<<GRAPHVIZ_START>>>
digraph SISO_Timing {
rankdir=LR;
node [shape=box, style=filled, fillcolor=lightblue];

subgraph cluster_legend {
    label="Legend";
    style=dashed;
    node [shape=plaintext, fillcolor=white];
    L0 [label="Din: Serial Input Data"];
    L1 [label="Clock: System Clock Pulse"];
    L2 [label="Qn: Output of n-th Flip-flop"];
    L3 [label="Sout: Serial Output Data (from Q3)"];
}

subgraph cluster_SISO {
    label="4-bit SISO Register States (Loading '1011' LSB-first)";
    style=dashed;
    edge [dir=forward, arrowhead=open];

    Initial [label="Initial State\nDin=X\nQ3Q2Q1Q0=0000"];
    C1 [label="Clock 1\nDin=1\nQ3Q2Q1Q0=0001"];
    C2 [label="Clock 2\nDin=0\nQ3Q2Q1Q0=0010"];
    C3 [label="Clock 3\nDin=1\nQ3Q2Q1Q0=0101"];
    C4 [label="Clock 4\nDin=1\nQ3Q2Q1Q0=1011\n(Data Loaded)"];
    C5 [label="Clock 5\nDin=X\nQ3Q2Q1Q0=X101\nSout=1"];
    C6 [label="Clock 6\nDin=X\nQ3Q2Q1Q0=XX10\nSout=0"];
    C7 [label="Clock 7\nDin=X\nQ3Q2Q1Q0=XXX1\nSout=1"];
    C8 [label="Clock 8\nDin=X\nQ3Q2Q1Q0=XXXX\nSout=1\n(Data Unloaded)"];

    Initial -> C1 [label="Clock Pulse"];
    C1 -> C2 [label="Clock Pulse"];
    C2 -> C3 [label="Clock Pulse"];
    C3 -> C4 [label="Clock Pulse"];
    C4 -> C5 [label="Clock Pulse"];
    C5 -> C6 [label="Clock Pulse"];
    C6 -> C7 [label="Clock Pulse"];
    C7 -> C8 [label="Clock Pulse"];
}

}
<<<GRAPHVIZ_END>>>

4-bit Parallel-In, Parallel-Out (PIPO) Shift Register

A Parallel-In, Parallel-Out (PIPO) shift register loads data in parallel (all bits simultaneously) and outputs data in parallel (all bits simultaneously). This type is primarily used for storing data temporarily, as it offers the fastest way to input and output data.

Operation:

1. Data bits are applied simultaneously to the parallel input lines (D3, D2, D1, D0).
2. A control signal (e.g., Load/Shift, or a dedicated Load pulse) is asserted.
3. On the next active clock edge, all data bits from the input lines are simultaneously transferred to their respective flip-flops (Q3, Q2, Q1, Q0).
4. Once loaded, the data is immediately available at the parallel output lines (Q3, Q2, Q1, Q0).
5. No shifting is involved for loading or outputting data in this mode.

Timing Diagram (Loading '1011'):
<<<GRAPHVIZ_START>>>
digraph PIPO_Timing {
rankdir=LR;
node [shape=box, style=filled, fillcolor=lightblue];

subgraph cluster_legend {
    label="Legend";
    style=dashed;
    node [shape=plaintext, fillcolor=white];
    L0 [label="D3D2D1D0: Parallel Input Data"];
    L1 [label="Clock: System Clock Pulse"];
    L2 [label="Load: Control Signal (High for Load)"];
    L3 [label="Q3Q2Q1Q0: Parallel Output Data"];
}

subgraph cluster_PIPO {
    label="4-bit PIPO Register States (Loading '1011')";
    style=dashed;
    edge [dir=forward, arrowhead=open];

    Initial [label="Initial State\nD3D2D1D0=XXXX\nQ3Q2Q1Q0=0000\nLoad=0"];
    LoadPulse [label="Pre-Clock\nD3D2D1D0=1011\nLoad=1"];
    AfterClock [label="After Clock Pulse\nQ3Q2Q1Q0=1011\n(Data Loaded)"];
    StableOutput [label="Subsequent State\nQ3Q2Q1Q0=1011\nLoad=0\n(Output Stable)"];

    Initial -> LoadPulse [label="Set Inputs & Load"];
    LoadPulse -> AfterClock [label="Clock Pulse (Rising Edge)"];
    AfterClock -> StableOutput [label="After Load"];
}

}
<<<GRAPHVIZ_END>>>

To design an asynchronous mod 11 up counter using T flip-flops:

• Number of Flip-Flops:

  • A mod 11 counter requires 11 states (0 to 10).
  • The minimum number of flip-flops (N) is determined by 2^N ≥ 11.
  • Since 2^3 = 8 and 2^4 = 16, four (4) T flip-flops are required.

• Counting Sequence:

  • The counter will count from binary 0000 (decimal 0) up to 1010 (decimal 10).

• Reset Condition:

  • The counter must reset to 0000 when it attempts to transition to the eleventh state.
  • The eleventh state is binary 1011 (decimal 11).
  • Therefore, an asynchronous clear (CLR') signal is generated when the outputs Q3, Q1, and Q0 are all high (1011).

• Reset Logic:

  • A 3-input NAND gate is used to detect the reset condition (Q3=1, Q1=1, Q0=1).
  • The output of this NAND gate is connected to the active-low asynchronous clear (CLR') input of all four T flip-flops.

• Flip-Flop Configuration:

  • Each T flip-flop's T input is tied to logic HIGH (VCC) for toggle operation.
  • The clock input of the first flip-flop (FF0) is connected to the external clock signal.
  • The Q output of each preceding flip-flop is connected to the clock input of the next flip-flop, creating a ripple effect.

<<<GRAPHVIZ_START>>>
digraph Mod11Counter {
rankdir=LR;
splines=ortho;

node [shape=box, style="rounded,filled", fillcolor="#e6e6fa"];

// Flip-Flops
FF0 [label="T FF0\nQ0", width=1.0, height=0.7];
FF1 [label="T FF1\nQ1", width=1.0, height=0.7];
FF2 [label="T FF2\nQ2", width=1.0, height=0.7];
FF3 [label="T FF3\nQ3", width=1.0, height=0.7];

// Logic High for T inputs
VCC [label="VCC", shape=circle, fixedsize=true, width=0.4, height=0.4, fillcolor="#ccffcc"];

// Clock Input
CLK [label="CLK", shape=octagon, fillcolor="#ffe0b2"];

// Reset Logic
NAND_GATE [label="NAND", shape=ellipse, width=0.8, height=0.6, fillcolor="#ffcccc"];

// Connections for T inputs
VCC -> FF0:t;
VCC -> FF1:t;
VCC -> FF2:t;
VCC -> FF3:t;

// Clocking connections (ripple)
CLK -> FF0:clk;
FF0:q -> FF1:clk;
FF1:q -> FF2:clk;
FF2:q -> FF3:clk;

// Connections to NAND gate for reset condition (Q3, Q1, Q0 for 1011)
FF3:q -> NAND_GATE:in1 [label="Q3"];
FF1:q -> NAND_GATE:in2 [label="Q1"];
FF0:q -> NAND_GATE:in3 [label="Q0"];

// Reset signal to all flip-flops (active low clear)
NAND_GATE:out -> FF0:clr [label="CLR'"];
NAND_GATE:out -> FF1:clr;
NAND_GATE:out -> FF2:clr;
NAND_GATE:out -> FF3:clr;

// Grouping for clarity
{rank=same; FF0; FF1; FF2; FF3;}
}
<<<GRAPHVIZ_END>>>

A race condition, specifically the "race-around" condition, in a level-triggered JK flip-flop occurs when both J and K inputs are high (J=K=1) and the clock pulse remains high for a duration longer than the propagation delay of the flip-flop. In this scenario, the output can toggle back and forth multiple times within a single clock pulse, leading to an unpredictable final state after the clock pulse ends.

This issue is primarily resolved by using a Master-Slave JK flip-flop or by designing an edge-triggered JK flip-flop.

Resolution using Master-Slave JK Flip-Flop:

1. Configuration: A Master-Slave JK flip-flop consists of two cascaded level-triggered JK flip-flops: a Master flip-flop and a Slave flip-flop. The clock input to the Slave is inverted relative to the Master.
2. Operation during Clock HIGH:
   • When the clock signal is high, the Master flip-flop is enabled, allowing it to respond to the J and K inputs. It captures the state based on these inputs.
   • During this period, the Slave flip-flop is disabled because its clock input (inverted clock) is low. It retains its previous state, and its outputs are stable.
3. Operation during Clock LOW (transition from HIGH to LOW):
   • As the clock transitions from high to low (falling edge), the Master flip-flop becomes disabled, effectively locking its captured state.
   • Simultaneously, the Slave flip-flop becomes enabled (as its inverted clock input goes high). The Slave then copies the stable state from the outputs of the now-locked Master flip-flop to its own outputs (Q and Q').
4. Operation during Clock LOW:
   • When the clock signal is low, the Master flip-flop remains disabled, isolating it from any changes at the J and K inputs.
   • The Slave flip-flop is enabled but is only responding to the stable outputs of the Master, which are locked.
5. Prevention of Race-Around: This two-stage, clock-phased operation ensures that:
   • The inputs J and K can only affect the Master when the clock is high.
   • The output of the entire flip-flop (Q and Q' of the Slave) can only change when the clock goes low, copying the state from the Master.
   • The Master is isolated from its inputs (J, K) while the Slave is updating its output, preventing any further changes or toggling within the same clock cycle.
   • Consequently, the overall flip-flop updates its state only once per full clock cycle, typically at the falling edge, eliminating the race-around condition.

A decoder circuit is a combinational logic circuit that converts a binary input code of N lines into a maximum of 2^N unique output lines. At any given time, only one of the output lines is active (HIGH or LOW, depending on the design) corresponding to the binary value of the N inputs.

Design of a 3-to-8 Decoder Circuit

A 3-to-8 decoder has 3 input lines (A2, A1, A0) and 8 output lines (Y0 to Y7). Each output corresponds to one of the 8 possible minterms of the 3 input variables.

1. Truth Table:

A2	A1	A0	Y7	Y6	Y5	Y4	Y3	Y2	Y1	Y0
0	0	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	1	0	0	0	0	0	0	1	0	0
0	1	1	0	0	0	0	1	0	0	0
1	0	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	0	0	0	0	0
1	1	0	0	1	0	0	0	0	0	0
1	1	1	1	0	0	0	0	0	0	0

2. Boolean Expressions for Outputs:

Each output (Yi) corresponds to a unique minterm of the inputs A2, A1, and A0.

• Y0 = A2' A1' A0'
• Y1 = A2' A1' A0
• Y2 = A2' A1 A0'
• Y3 = A2' A1 A0
• Y4 = A2 A1' A0'
• Y5 = A2 A1' A0
• Y6 = A2 A1 A0'
• Y7 = A2 A1 A0

3. Logic Circuit Diagram:

The circuit can be implemented using three inverters for the complemented inputs and eight 3-input AND gates, one for each output.

<<<GRAPHVIZ_START>>>
digraph G {
rankdir=LR;
node [shape=none];
splines=ortho;

// Inputs
subgraph cluster_inputs {
label="Inputs";
A2_in [label="A2"];
A1_in [label="A1"];
A0_in [label="A0"];
}

// Inverters
node [shape=inv_triangle, style=filled, fillcolor=lightgray, width=0.3, height=0.3];
notA2 [label=""];
notA1 [label=""];
notA0 [label=""];

// Connections for inverters
A2_in -> notA2;
A1_in -> notA1;
A0_in -> notA0;

// AND gates
node [shape=and, style=filled, fillcolor=lightblue, width=0.5, height=0.5];
and0 [label=""];
and1 [label=""];
and2 [label=""];
and3 [label=""];
and4 [label=""];
and5 [label=""];
and6 [label=""];
and7 [label=""];

// Output labels
node [shape=none, label="", width=0, height=0];
Y0_out [label="Y0"];
Y1_out [label="Y1"];
Y2_out [label="Y2"];
Y3_out [label="Y3"];
Y4_out [label="Y4"];
Y5_out [label="Y5"];
Y6_out [label="Y6"];
Y7_out [label="Y7"];

// Connections to AND gates and then to Outputs
// Y0 = A2' A1' A0'
notA2 -> and0 [minlen=1];
notA1 -> and0;
notA0 -> and0;
and0 -> Y0_out;

// Y1 = A2' A1' A0
notA2 -> and1;
notA1 -> and1;
A0_in -> and1;
and1 -> Y1_out;

// Y2 = A2' A1 A0'
notA2 -> and2;
A1_in -> and2;
notA0 -> and2;
and2 -> Y2_out;

// Y3 = A2' A1 A0
notA2 -> and3;
A1_in -> and3;
A0_in -> and3;
and3 -> Y3_out;

// Y4 = A2 A1' A0'
A2_in -> and4;
notA1 -> and4;
notA0 -> and4;
and4 -> Y4_out;

// Y5 = A2 A1' A0
A2_in -> and5;
notA1 -> and5;
A0_in -> and5;
and5 -> Y5_out;

// Y6 = A2 A1 A0'
A2_in -> and6;
A1_in -> and6;
notA0 -> and6;
and6 -> Y6_out;

// Y7 = A2 A1 A0
A2_in -> and7;
A1_in -> and7;
A0_in -> and7;
and7 -> Y7_out;

{rank=same; A2_in; A1_in; A0_in;}
{rank=same; notA2; notA1; notA0;}
{rank=same; and0; and1; and2; and3; and4; and5; and6; and7;}
{rank=same; Y0_out; Y1_out; Y2_out; Y3_out; Y4_out; Y5_out; Y6_out; Y7_out;}
}
<<<GRAPHVIZ_END>>>

State Diagram
A state diagram is a graphical representation used to visualize the behavior of a finite state machine (FSM) or sequential logic circuits.

• Components: Consists of nodes (circles) representing the distinct states of the system and directed edges (arrows) representing transitions between these states.
• Transitions: Each transition is typically labeled with the input condition that causes the state change and the output generated during or after the transition.
• Purpose: Illustrates how the system's current state, combined with specific inputs, determines the next state and the corresponding outputs. It is fundamental in the design and analysis of sequential circuits.

Encoder
An encoder is a combinational logic circuit that converts a set of N input lines into a binary code of M output lines, where 2^M ≥ N.

• Function: It is designed such that when only one of its input lines is active (typically high), it produces a unique M-bit binary code corresponding to that active input line.
• Application: Commonly used to convert decimal or octal inputs into binary coded decimal (BCD) or pure binary format, respectively.
• Types: A common variation is the priority encoder, which resolves ambiguities when multiple input lines are active by assigning a priority to each input and encoding only the highest-priority active input.

Parallel Adder
A parallel adder is a combinational logic circuit that performs the addition of two binary numbers simultaneously across all bit positions.

• Construction: It is typically constructed using multiple full adder circuits connected in parallel. For N-bit numbers, N full adders are used (or one half adder for the least significant bit, followed by N-1 full adders).
• Operation: Each full adder receives two input bits (A_i, B_i) and a carry-in (C_i) from the less significant bit stage, producing a sum bit (S_i) and a carry-out (C_i+1) for the next stage.
• Advantage: Offers faster addition compared to serial adders because all bits are processed concurrently, though carry propagation delay (ripple carry) can still limit overall speed.