Combinational Circuit: BCD to 1's Complement

STEP 1 - EXTRACT: Given Data

• Number of input lines: 4 (call them $A, B, C, D$)
• Inputs represent a decimal digit in BCD (valid range: 0 to 9)
• Number of output lines: 4 (call them $W, X, Y, Z$)
• Required output: 1's complement of the input binary pattern

No numeric constants missing. All information needed is present.

STEP 2 - SOLVE

1. What is a Combinational Circuit?

A combinational circuit is a digital logic circuit whose output at any given time depends only on the present combination of input values and not on any past inputs or outputs. It contains no memory elements (flip-flops) and no feedback paths. It is built entirely from interconnected logic gates (AND, OR, NOT, NAND, NOR, XOR).

Characteristics:

• Output is a pure Boolean function of current inputs
• No storage / no feedback
• Fully described by a truth table or Boolean expressions
• Examples: adders, subtractors, encoders, decoders, multiplexers, code converters

2. Concept of 1's Complement

The 1's complement of a binary number is obtained by inverting each bit ($0 \to 1$, $1 \to 0$). Hence for a 4-bit input $ABCD$ the outputs are the bitwise inverse.

3. Truth Table

Inputs $A B C D$ are BCD (0-9). Combinations 1010 to 1111 are invalid BCD and treated as don't care ($\times$).

4. K-Map Simplification

Output W (equals $\bar A$): $W=1$ for all minterms with $A=0$; $W=0$ for $A=1$. Don't cares grouped freely.

$$W = A'$$

Output X (equals $\bar B$): $X=1$ only when $B=0$.

$$X = B'$$

Output Y (equals $\bar C$): $Y=1$ only when $C=0$.

$$Y = C'$$

Output Z (equals $\bar D$): $Z=1$ only when $D=0$.

$$Z = D'$$

Each K-map reduces to a single-literal term because 1's complement is a purely bitwise inversion.

5. Simplified Boolean Expressions

$$\boxed{W = A' \quad X = B' \quad Y = C' \quad Z = D'}$$

6. Logic Circuit

The circuit needs only four NOT gates (inverters):

A ----|>o---- W = A'
B ----|>o---- X = B'
C ----|>o---- Y = C'
D ----|>o---- Z = D'

7. Conclusion

Since the 1's complement is a bit-by-bit inversion, the combinational circuit reduces to four independent inverters. The BCD constraint and the don't-care conditions do not change this result; they only confirm the minimal single-literal expressions.

Implementation of F(P,Q,R,S) = Σ(3,4,6,8,9,14)

STEP 1 - EXTRACT (Given Data)

• Function: $F(P,Q,R,S) = \sum m(3,4,6,8,9,14)$
• 4 variables: P (MSB), Q, R, S (LSB)
• Implement using: (a) 8-to-1 MUX, (b) PLA, (c) Decoder

Truth Table

STEP 2 - SOLVE

Part (a): 8-to-1 Multiplexer [4 marks]

Select lines: $S_2=P,\ S_1=Q,\ S_0=R$. Data inputs expressed in terms of $S$.

Connections: $I_0=0,\ I_1=S,\ I_2=S',\ I_3=S',\ I_4=1,\ I_5=0,\ I_6=0,\ I_7=S'$

   I0=0  --|            |
   I1=S  --|            |
   I2=S' --|            |
   I3=S' --|  8-to-1    |--- F
   I4=1  --|   MUX      |
   I5=0  --|            |
   I6=0  --|            |
   I7=S' --|            |
             |  |  |
            S0 S1 S2
             R  Q  P

Part (b): PLA [2 marks]

Simplify with K-map (PQ rows, RS columns):

        RS=00  01  11  10
PQ=00 |  0  |  0 |  1 |  0 |   (m0 m1 m3 m2)
PQ=01 |  1  |  0 |  0 |  1 |   (m4 m5 m7 m6)
PQ=11 |  0  |  0 |  0 |  1 |   (m12 m13 m15 m14)
PQ=10 |  1  |  1 |  0 |  0 |   (m8 m9 m11 m10)

Grouping:

• Minterms 8, 9 (100-): $PQ'R'$
• Minterms 4, 6 (01-0): $P'QS'$
• Minterm 3 (0011): $P'Q'RS$
• Minterm 14 (1110): $PQRS'$

Check coverage:

• $PQ'R'$ → m8, m9 ✓
• $P'QS'$ → m4, m6 ✓
• $P'Q'RS$ → m3 ✓
• $PQRS'$ → m14 ✓

$$F = PQ'R' + P'QS' + P'Q'RS + PQRS'$$

PLA program table (4 product terms, output F):

AND array forms the 4 products; OR array connects all 4 to output F.

Part (c): Decoder [2 marks]

Use a 4-to-16 line decoder (4 inputs P,Q,R,S → 16 outputs, active-high). Since F has 6 minterms, OR the corresponding decoder outputs:

$$F = m_3 + m_4 + m_6 + m_8 + m_9 + m_{14}$$

       ---------
 P --->|         |--- 3  --\
 Q --->| 4-to-16 |--- 4  ---\
 R --->| decoder |--- 6  ----+--- OR gate --- F
 S --->|         |--- 8  ---/
       |         |--- 9  --/
       ---------  |--- 14 -/
    (other outputs unused)

Connect outputs $D_3, D_4, D_6, D_8, D_9, D_{14}$ to a 6-input OR gate; its output is F.

(If active-low decoder outputs are used, replace the OR gate with a NAND gate.)

Final Simplified Expression

$$\boxed{F = PQ'R' + P'QS' + P'Q'RS + PQRS'}$$

Asynchronous Mod-11 Up Counter Using T Flip-Flop

STEP 1 - EXTRACT: Given Data

• Counter type: Asynchronous (ripple)
• Modulus: 11 (counts 0 to 10, i.e. 11 distinct states)
• Flip-flop type: T flip-flop
• Direction: Up counter

No numeric values are missing. The design is fully specified.

STEP 2 - SOLVE

Step 1: Number of Flip-Flops

We need enough flip-flops to represent 11 states:

$$2^n \geq 11 \implies 2^4 = 16 \geq 11$$

So $n = 4$ flip-flops are needed: FF0, FF1, FF2, FF3 with outputs $Q_0, Q_1, Q_2, Q_3$.

Step 2: Count Sequence (0 to 10)

The counter counts 0000 through 1010, then on the next clock it momentarily enters 1011 (decimal 11), which is detected and used to force an immediate asynchronous reset to 0000.

Step 3: Reset (Detection) Logic

The unwanted state to detect is 1011:

$$Q_3 = 1,\ Q_2 = 0,\ Q_1 = 1,\ Q_0 = 1$$

The minimal detection term (using only the bits that are 1 and unique to state 11 among reachable states) is:

$$\text{CLR} = Q_3 \cdot Q_1 \cdot Q_0$$

Verification: Among the valid stable states (0-10), is $Q_3 Q_1 Q_0 = 1$ true anywhere else?

• State 10 (1010): $Q_3=1, Q_1=1, Q_0=0 \Rightarrow$ product $=0$. Safe.
• No other reachable state has $Q_3=1$ and $Q_1=1$ simultaneously with $Q_0=1$.

Hence $\text{CLR}=Q_3 Q_1 Q_0$ uniquely fires at state 1011. Confirmed correct.

Step 4: T Flip-Flop Connections (Ripple Configuration)

For a ripple up counter with negative-edge (falling-edge) triggered flip-flops, each Q drives the clock of the next stage, and all T inputs are held at logic 1 to toggle:

(With $T=1$, each flip-flop toggles on every triggering edge, giving frequency division by 2 down the chain, the standard ripple count-up behaviour.)

Step 5: Circuit Diagram

        +---------+     +---------+     +---------+     +---------+
CLK --->|CLK  FF0 |     |CLK  FF1 |     |CLK  FF2 |     |CLK  FF3 |
        |T=1   Q0 |--+->|T=1   Q1 |--+->|T=1   Q2 |--+->|T=1   Q3 |--+
        |    CLR  |  |  |    CLR  |  |  |    CLR  |  |  |    CLR  |  |
        +----^----+  |  +----^----+  |  +----^----+  |  +----^----+  |
             |       |       |       |       |       |       |       |
             +-------+-------+-------+-------+-------+-------+       |
                     |               |                             |
             CLR<----+-----[ 3-input AND: Q3.Q1.Q0 ]<--------------+
                     Q0            Q1              Q3

Reset logic:

Q3 ---+
Q1 ---+---> [ 3-input AND ] ---> CLR ---> (active-HIGH asynchronous CLEAR of all FFs)
Q0 ---+

Step 6: Summary

Conclusion: A Mod-11 asynchronous up counter uses 4 T flip-flops in ripple cascade with all $T=1$. A 3-input AND gate decoding $Q_3 Q_1 Q_0$ detects the transient state 1011 and asynchronously clears all flip-flops back to 0000, giving a repeating cycle of 11 states.

Short Notes (Any Two)

1. State Diagram

A State Diagram is a graphical representation used to describe the behavior of a sequential circuit. It shows all possible states of the circuit and the transitions between those states based on input conditions.

Key Components:

Important Points:

• Each flip-flop combination corresponds to one state.
• For a circuit with n flip-flops, there are at most 2^n possible states.
• The diagram clearly shows the present state, the next state, and the input/output associated with each transition.
• It is closely related to the state table -- both convey the same information, but the state diagram is a visual/graphical form.

Example:

For a simple 2-bit counter with states 00, 01, 10, 11:

00 --> 01 --> 10 --> 11 --> 00 (cycles back)

Each arrow is labeled with the clock pulse or input that triggers the transition.

Use: State diagrams are widely used in the design and analysis of counters, sequence detectors, and other sequential logic circuits.

2. Encoder

An Encoder is a combinational logic circuit that converts one of 2^n input lines into an n-bit binary output code. It performs the reverse operation of a decoder.

General Structure:

• It has a maximum of 2^n input lines and n output lines.
• At any given time, only one input line is active (HIGH).

Example: Decimal to BCD Encoder

A Decimal to BCD Encoder consists of:

• 10 input lines: D0 to D9 (one for each decimal digit 0--9)
• 4 output lines: W, X, Y, Z (representing BCD bits)

The output relations are derived from the truth table of the encoder. For example:

The Boolean expressions for the outputs are:

W = D8 + D9
X = D4 + D5 + D6 + D7
Y = D2 + D3 + D6 + D7
Z = D1 + D3 + D5 + D7 + D9

Block Diagram:

D0 --|
D1 --|
D2 --|
...  |---> [ENCODER] ---> W, X, Y, Z (4-bit BCD output)
...  |
D9 --|

Use: Encoders are used in keyboards, priority circuits, and data transmission systems to compress input data into a compact binary form.

3. Parallel Adder

A Parallel Adder is a combinational circuit that adds two n-bit binary numbers simultaneously (in parallel), producing an n-bit sum and a carry output.

Construction:

• It is built using n Full Adders (FA) connected in cascade.
• All bits of both numbers are applied to the inputs at the same time.
• The carry output of each full adder is connected to the carry input of the next higher-order full adder.

Block Diagram (4-bit Parallel Adder):

A3 B3    A2 B2    A1 B1    A0 B0
 |  |     |  |     |  |     |  |
[FA3]<--[FA2]<--[FA1]<--[FA0]<-- C_in=0
 |        |        |        |
 S3       S2       S1       S0
C_out

• Inputs: A3A2A1A0 and B3B2B1B0 (two 4-bit numbers)
• Outputs: S3S2S1S0 (4-bit sum) and C_out (final carry)

Characteristics:

Use: Parallel adders are fundamental building blocks in ALUs (Arithmetic Logic Units) of processors and are used in BCD adders and other arithmetic circuits.