BIT103 · TU past paper

Digital Logic 2081 question paper

The complete TU 2081 exam paper for Digital Logic (BIT103), all 12 questions with solved model answers written to the mark scheme.

Past Papers2081.2 2081 2080 2079 2078 2077

Tap a question to open its answer.

110 marksCombinational circuit design methodologyHideAnswer
Design a combinational circuit with three inputs. The output is 1 when the binary value of the input is odd.[10]
Design a combinational circuit with three inputs (A, B, C) where the output F = 1 when the binary value of the inputs is odd. --- Signal Description --------------------- A Most Significant Bit (MSB) B Middle Bit C Least Significant Bit ...

210 marksMagnitude comparator circuitsAnswer

Define magnitude comparator?Design a 4-bit magnitude comparator circuit.[2+8]

Magnitude Comparator

Definition (2 marks)

A magnitude comparator is a combinational logic circuit that compares two binary numbers and determines their relative magnitudes. Given two n-bit numbers A and B, the comparator produces three output signals:

A > B (output is HIGH when A is greater than B)
A = B (output is HIGH when A equals B)
A < B (output is HIGH when A is less than B)

Design of 4-bit Magnitude Comparator (8 marks)

Given

Two 4-bit numbers:

A = A₃A₂A₁A₀
B = B₃B₂B₁B₀

Step 1: Basic Bit Comparison

For each bit position i, define:

Condition	Expression
Aᵢ = Bᵢ	xᵢ = AᵢBᵢ + Āᵢ B̄ᵢ (XNOR)
Aᵢ > Bᵢ	AᵢB̄ᵢ
Aᵢ < Bᵢ	ĀᵢBᵢ

So define equality bits:

x₃ = A₃B₃ + Ā₃B̄₃
x₂ = A₂B₂ + Ā₂B̄₂
x₁ = A₁B₁ + Ā₁B̄₁
x₀ = A₀B₀ + Ā₀B̄₀

Step 2: Derive Output Expressions

Equality Output: (A = B)

All bit pairs must be equal:

(A = B) = x₃ · x₂ · x₁ · x₀

Greater Than Output: (A > B)

A > B if the most significant differing bit of A is 1 and B is 0:

(A > B) = A₃B̄₃
         + x₃·A₂B̄₂
         + x₃·x₂·A₁B̄₁
         + x₃·x₂·x₁·A₀B̄₀

Less Than Output: (A < B)

A < B if the most significant differing bit of B is 1 and A is 0:

(A < B) = Ā₃B₃
         + x₃·Ā₂B₂
         + x₃·x₂·Ā₁B₁
         + x₃·x₂·x₁·Ā₀B₀

Note: Alternatively, (A < B) = NOT(A > B) + NOT(A = B), i.e., (A < B) = (A > B)' · (A = B)'

Step 3: Logic Circuit Block Diagram

A₃,B₃ ──► [XNOR]──► x₃ ──────────────────────────────────────────►|
A₂,B₂ ──► [XNOR]──► x₂ ──────────────────────────────────────────►| AND ──► (A=B)
A₁,B₁ ──► [XNOR]──► x₁ ──────────────────────────────────────────►|
A₀,B₀ ──► [XNOR]──► x₀ ──────────────────────────────────────────►|

For (A > B):
A₃B̄₃ ──────────────────────────────────────────────────────────────►|
x₃·A₂B̄₂ ───────────────────────────────────────────────────────────►| OR ──► (A>B)
x₃·x₂·A₁B̄₁ ────────────────────────────────────────────────────────►|
x₃·x₂·x₁·A₀B̄₀ ─────────────────────────────────────────────────────►|

For (A < B):
Ā₃B₃ ──────────────────────────────────────────────────────────────►|
x₃·Ā₂B₂ ───────────────────────────────────────────────────────────►| OR ──► (A<B)
x₃·x₂·Ā₁B₁ ────────────────────────────────────────────────────────►|
x₃·x₂·x₁·Ā₀B₀ ─────────────────────────────────────────────────────►|

Step 4: Verification Example

Let A = 1010 (10) and B = 0110 (6):

Bit	A	B	xᵢ
3	1	0	0
2	0	1	0
1	1	1	1
0	0	0	1

(A = B) = x₃·x₂·x₁·x₀ = 0·0·1·1 = 0 ✓
(A > B) = A₃B̄₃ = 1·1 = 1 ✓ (since MSB of A is 1, MSB of B is 0)
(A < B) = Ā₃B₃ = 0·0 = 0 ✓

310 marksUp-down countersAnswer

What is counter?Design a 3-bit synchronous up-down counter along with state diagram and timing sequence.[2+8]

Counter: 3-bit Synchronous Up-Down Counter

What is a Counter? [2 marks]

A counter is a sequential logic circuit that goes through a prescribed sequence of states upon the application of input pulses (clock pulses). It is used to count the number of occurrences of an event or to generate a specific sequence of states.

Key features:

Built using flip-flops (usually JK or D flip-flops)
Can be synchronous (all flip-flops clocked simultaneously) or asynchronous (ripple counter)
Can count up, down, or both (up-down counter)

3-bit Synchronous Up-Down Counter [8 marks]

Concept

When UP/DOWN (M) = 1 → counter counts UP: 0→1→2→3→4→5→6→7→0
When UP/DOWN (M) = 0 → counter counts DOWN: 7→6→5→4→3→2→1→0→7
Uses JK flip-flops: Q₂ (MSB), Q₁, Q₀ (LSB)

State Diagram

         M=1 (UP)                    M=0 (DOWN)
    
    000 → 001 → 010 → 011 → 100 → 101 → 110 → 111 → 000
     ↑                                                  |
     |__________________________________________________|
    
    000 ← 001 ← 010 ← 011 ← 100 ← 101 ← 110 ← 111 ← 000

State Diagram (circular):

              M=1 (UP direction)
    ┌──────────────────────────────────────────┐
    ↓                                          |
   000 →(M=1)→ 001 →(M=1)→ 010 →(M=1)→ 011   |
    ↑                                    ↓    |
   111 ←(M=1)← 110 ←(M=1)← 101 ←(M=1)← 100  |
    |                                          ↑
    └──────────────────────────────────────────┘
              M=0 (DOWN direction, reverse)

State Transition Table

Present State	M	Next State
Q₂ Q₁ Q₀		Q₂' Q₁' Q₀'
0 0 0	1 (UP)	0 0 1
0 0 1	1	0 1 0
0 1 0	1	0 1 1
0 1 1	1	1 0 0
1 0 0	1	1 0 1
1 0 1	1	1 1 0
1 1 0	1	1 1 1
1 1 1	1	0 0 0
0 0 0	0 (DOWN)	1 1 1
0 0 1	0	0 0 0
0 1 0	0	0 0 1
0 1 1	0	0 1 0
1 0 0	0	0 1 1
1 0 1	0	1 0 0
1 1 0	0	1 0 1
1 1 1	0	1 1 0

JK Flip-Flop Excitation Table (Reference)

Q → Q'	J	K
0 → 0	0	X
0 → 1	1	X
1 → 0	X	1
1 → 1	X	0

Deriving Boolean Expressions

For Q₀ (LSB):

Q₀ always toggles on every clock pulse (both up and down)
J₀ = K₀ = 1

For Q₁:

Q₁ toggles when Q₀ = 1 (counting up, M=1)
Q₁ toggles when Q₀ = 0 (counting down, M=0)

$J_1 = K_1 = M \cdot Q_0 + \overline{M} \cdot \overline{Q_0}$

This can be written as:

$J_1 = K_1 = \overline{M \oplus Q_0}$

For Q₂:

Q₂ toggles when Q₁ = 1 AND Q₀ = 1 (counting up, M=1)
Q₂ toggles when Q₁ = 0 AND Q₀ = 0 (counting down, M=0)

$J_2 = K_2 = M \cdot Q_1 \cdot Q_0 + \overline{M} \cdot \overline{Q_1} \cdot \overline{Q_0}$

Summary of Excitation Equations

Flip-Flop	J	K
FF₀	1	1
FF₁	M·Q₀ + M̄·Q̄₀	M·Q₀ + M̄·Q̄₀
FF₂	M·Q₁·Q₀ + M̄·Q̄₁·Q̄₀	M·Q₁·Q₀ + M̄·Q̄₁·Q̄₀

In every flip-flop J equals K, so each stage either holds its value or toggles, which is exactly the behaviour a binary counter needs. Writing the two mode terms with an exclusive-OR gives the compact forms:

$J_0 = K_0 = 1$

$J_1 = K_1 = \overline{M \oplus Q_0}$

$J_2 = K_2 = \overline{M \oplus Q_0} \cdot \overline{M \oplus Q_1}$

The third expression is the same function as the sum-of-products form above, because the AND of the two agreement terms is true only when M, Q₀ and Q₁ all agree.

Logic Circuit

                     M (1 = UP, 0 = DOWN)
                     |
                     +----------------+-----------------------+
                     |                |                       |
                     v                v                       v
   +-----+     +-----+------+   +-----+-------+       +-------+---------+
   |  1  |     | control for |  | control for |       |  control for    |
   +--+--+     |    FF1      |  |    FF2      |       |  (uses Q0, Q1)  |
      |        | M.Q0+M'.Q0' |  | M.Q1.Q0 +   |       +-------+---------+
      |        +------+------+  | M'.Q1'.Q0'  |               |
      |               |         +------+------+               |
      v               v                v                      v
  +---+---+       +---+---+        +---+---+
  |  FF0  |       |  FF1  |        |  FF2  |
  | J0 K0 |       | J1 K1 |        | J2 K2 |
  +---+---+       +---+---+        +---+---+
    |   |           |   |            |   |
    Q0  Q0'         Q1  Q1'          Q2  Q2'
    |   |           |   |
    +---+-----------+---+---------------> to the control gates above
      ^               ^                ^
      |               |                |
  CLK +---------------+----------------+
      (all three flip-flops clocked together)

Each control block is two AND gates feeding an OR gate, and the same signal drives both J and K of its flip-flop. The single clock line reaching all three flip-flops is what makes the counter synchronous.

Timing Sequence

Counting up with M = 1, starting from 000:

Clock pulse	Q₂	Q₁	Q₀	Decimal
initial	0	0	0	0
1	0	0	1	1
2	0	1	0	2
3	0	1	1	3
4	1	0	0	4
5	1	0	1	5
6	1	1	0	6
7	1	1	1	7
8	0	0	0	0 (recycles)

Counting down with M = 0, starting from 111:

Clock pulse	Q₂	Q₁	Q₀	Decimal
initial	1	1	1	7
1	1	1	0	6
2	1	0	1	5
3	1	0	0	4
4	0	1	1	3
5	0	1	0	2
6	0	0	1	1
7	0	0	0	0
8	1	1	1	7 (recycles)

Timing Diagram (M = 1, up count)

Pulse      1     2     3     4     5     6     7     8
        __    __    __    __    __    __    __    __
CLK   _|  |__|  |__|  |__|  |__|  |__|  |__|  |__|  |__

Q0    ‾‾‾‾‾‾______‾‾‾‾‾‾______‾‾‾‾‾‾______‾‾‾‾‾‾______

Q1    ______‾‾‾‾‾‾‾‾‾‾‾‾____________‾‾‾‾‾‾‾‾‾‾‾‾______

Q2    __________________‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾______

Q₀ changes on every clock pulse, Q₁ at half that rate and Q₂ at a quarter, so the three waveforms together read as the binary count 000 to 111. With M = 0 the same waveforms appear in reverse order, giving the down count.

Conclusion

A 3-bit synchronous up-down counter needs three JK flip-flops driven by a common clock, with the mode line M steering each stage through the agreement terms M·Q + M̄·Q̄. Because all flip-flops switch on the same clock edge, the counter is free of the cumulative propagation delay of a ripple counter and can be operated at a much higher frequency.

Counter: 3-bit Synchronous Up-Down Counter

What is a Counter? [2 marks]

Key features:

Built using flip-flops (usually JK or D flip-flops)
Can be synchronous (all flip-flops clocked simultaneously) or asynchronous (ripple counter)
Can count up, down, or both (up-down counter)

3-bit Synchronous Up-Down Counter [8 marks]

Concept

When UP/DOWN (M) = 1 → counter counts UP: 0→1→2→3→4→5→6→7→0
When UP/DOWN (M) = 0 → counter counts DOWN: 7→6→5→4→3→2→1→0→7
Uses JK flip-flops: Q₂ (MSB), Q₁, Q₀ (LSB)

State Diagram

         M=1 (UP)                    M=0 (DOWN)
    
    000 → 001 → 010 → 011 → 100 → 101 → 110 → 111 → 000
     ↑                                                  |
     |__________________________________________________|
    
    000 ← 001 ← 010 ← 011 ← 100 ← 101 ← 110 ← 111 ← 000

State Diagram (circular):

              M=1 (UP direction)
    ┌──────────────────────────────────────────┐
    ↓                                          |
   000 →(M=1)→ 001 →(M=1)→ 010 →(M=1)→ 011   |
    ↑                                    ↓    |
   111 ←(M=1)← 110 ←(M=1)← 101 ←(M=1)← 100  |
    |                                          ↑
    └──────────────────────────────────────────┘
              M=0 (DOWN direction, reverse)

State Transition Table

Present State	M	Next State
Q₂ Q₁ Q₀		Q₂' Q₁' Q₀'
0 0 0	1 (UP)	0 0 1
0 0 1	1	0 1 0
0 1 0	1	0 1 1
0 1 1	1	1 0 0
1 0 0	1	1 0 1
1 0 1	1	1 1 0
1 1 0	1	1 1 1
1 1 1	1	0 0 0
0 0 0	0 (DOWN)	1 1 1
0 0 1	0	0 0 0
0 1 0	0	0 0 1
0 1 1	0	0 1 0
1 0 0	0	0 1 1
1 0 1	0	1 0 0
1 1 0	0	1 0 1
1 1 1	0	1 1 0

JK Flip-Flop Excitation Table (Reference)

Q → Q'	J	K
0 → 0	0	X
0 → 1	1	X
1 → 0	X	1
1 → 1	X	0

Deriving Boolean Expressions

For Q₀ (LSB):

Q₀ always toggles on every clock pulse (both up and down)
J₀ = K₀ = 1

For Q₁:

Q₁ toggles when Q₀ = 1 (counting up, M=1)
Q₁ toggles when Q₀ = 0 (counting down, M=0)

$$J_1 = K_1 = M \cdot Q_0 + \overline{M} \cdot \overline{Q_0}$$

This can be written as:

$$J_1 = K_1 = \overline{M \oplus Q_0}$$

For Q₂:

Q₂ toggles when Q₁ = 1 AND Q₀ = 1 (counting up, M=1)
Q₂ toggles when Q₁ = 0 AND Q₀ = 0 (counting down, M=0)

$$J_2 = K_2 = M \cdot Q_1 \cdot Q_0 + \overline{M} \cdot \overline{Q_1} \cdot \overline{Q_0}$$

Summary of Excitation Equations

Flip-Flop	J	K
FF₀	1	1
FF₁	M·Q₀ + M̄·Q̄₀	M·Q₀ + M̄·Q̄₀
FF₂	M·Q₁·Q₀ + M̄·Q̄₁·Q̄₀	M·Q₁·Q₀ + M̄·Q̄₁·Q̄₀

$$J_0 = K_0 = 1$$

$$J_1 = K_1 = \overline{M \oplus Q_0}$$

$$J_2 = K_2 = \overline{M \oplus Q_0} \cdot \overline{M \oplus Q_1}$$

The third expression is the same function as the sum-of-products form above, because the AND of the two agreement terms is true only when M, Q₀ and Q₁ all agree.

Logic Circuit

                     M (1 = UP, 0 = DOWN)
                     |
                     +----------------+-----------------------+
                     |                |                       |
                     v                v                       v
   +-----+     +-----+------+   +-----+-------+       +-------+---------+
   |  1  |     | control for |  | control for |       |  control for    |
   +--+--+     |    FF1      |  |    FF2      |       |  (uses Q0, Q1)  |
      |        | M.Q0+M'.Q0' |  | M.Q1.Q0 +   |       +-------+---------+
      |        +------+------+  | M'.Q1'.Q0'  |               |
      |               |         +------+------+               |
      v               v                v                      v
  +---+---+       +---+---+        +---+---+
  |  FF0  |       |  FF1  |        |  FF2  |
  | J0 K0 |       | J1 K1 |        | J2 K2 |
  +---+---+       +---+---+        +---+---+
    |   |           |   |            |   |
    Q0  Q0'         Q1  Q1'          Q2  Q2'
    |   |           |   |
    +---+-----------+---+---------------> to the control gates above
      ^               ^                ^
      |               |                |
  CLK +---------------+----------------+
      (all three flip-flops clocked together)

Timing Sequence

Counting up with M = 1, starting from 000:

Clock pulse	Q₂	Q₁	Q₀	Decimal
initial	0	0	0	0
1	0	0	1	1
2	0	1	0	2
3	0	1	1	3
4	1	0	0	4
5	1	0	1	5
6	1	1	0	6
7	1	1	1	7
8	0	0	0	0 (recycles)

Counting down with M = 0, starting from 111:

Clock pulse	Q₂	Q₁	Q₀	Decimal
initial	1	1	1	7
1	1	1	0	6
2	1	0	1	5
3	1	0	0	4
4	0	1	1	3
5	0	1	0	2
6	0	0	1	1
7	0	0	0	0
8	1	1	1	7 (recycles)

Timing Diagram (M = 1, up count)

Pulse      1     2     3     4     5     6     7     8
        __    __    __    __    __    __    __    __
CLK   _|  |__|  |__|  |__|  |__|  |__|  |__|  |__|  |__

Q0    ‾‾‾‾‾‾______‾‾‾‾‾‾______‾‾‾‾‾‾______‾‾‾‾‾‾______

Q1    ______‾‾‾‾‾‾‾‾‾‾‾‾____________‾‾‾‾‾‾‾‾‾‾‾‾______

Q2    __________________‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾______

Conclusion

45 marksNumericalBinary decimal octal hexadecimal conversioHideAnswer
Convert (257)₈ into hexadecimal and decimal number system. [5]
Convert (257)₈ to Decimal and Hexadecimal

Given Data
- Number: $(257)_8$ (octal, base 8)
- Required: convert to hexadecimal (base 16) and decimal (base 10)
Part 1: Octal to Decimal

Multiply each digit by its positional weight (power of 8):
$(257)_8 = 2 \times 8^2 + 5 \times 8^1 + 7 \times 8^0$ $= 2 \times 64 + 5 \times 8 + 7 \times 1$ $= 128 + 40 + 7 = 175$ $\boxed{(257)_8 = (175)_{10}}$

Part 2: Octal to Hexadecimal (via Binary)

Step 1: Convert each octal digit to 3-bit binary

Octal Digit 3-bit Binary
2 010
5 101
7 111
$(257)_8 = (010\ 101\ 111)_2 = (10101111)_2$
Step 2: Regroup binary into groups of 4 (from right)
$10101111 \rightarrow 1010\ 1111$
(No padding needed here since 8 bits = two groups of 4.)

4-bit Group Hexadecimal
1010 A
1111 F

Step 3: Result
$\boxed{(257)_8 = (AF)_{16}}$
Verification (decimal check):
$(AF)_{16} = 10 \times 16 + 15 = 160 + 15 = 175 = (175)_{10} \checkmark$

Summary

From To Result
$(257)_8$ Decimal $(175)_{10}$
$(257)_8$ Hexadecimal $(AF)_{16}$
Convert (257)₈ to Decimal and Hexadecimal

Given Data
- Number: $(257)_8$ (octal, base 8)
- Required: convert to hexadecimal (base 16) and decimal (base 10)
Part 1: Octal to Decimal

Multiply each digit by its positional weight (power of 8):

$$ (257)_8 = 2 \times 8^2 + 5 \times 8^1 + 7 \times 8^0 $$

$$ = 2 \times 64 + 5 \times 8 + 7 \times 1 $$

$$ = 128 + 40 + 7 = 175 $$

$$ \boxed{(257)8 = (175){10}} $$

Part 2: Octal to Hexadecimal (via Binary)

Step 1: Convert each octal digit to 3-bit binary

Octal Digit 3-bit Binary
2 010
5 101
7 111

$$ (257)_8 = (010\ 101\ 111)_2 = (10101111)_2 $$

Step 2: Regroup binary into groups of 4 (from right)

$$ 10101111 \rightarrow 1010\ 1111 $$

(No padding needed here since 8 bits = two groups of 4.)

4-bit Group Hexadecimal
1010 A
1111 F

Step 3: Result

$$ \boxed{(257)8 = (AF){16}} $$

Verification (decimal check): $$ (AF){16} = 10 \times 16 + 15 = 160 + 15 = 175 = (175){10} \checkmark $$

Summary

From To Result
$(257)_8$ Decimal $(175)_{10}$
$(257)_8$ Hexadecimal $(AF)_{16}$
55 marksNumericalBinary arithmetic operationsHideAnswer
Perform following arithmetic operation: a) $101101 + 011011$ b) $101111 - 010101$ [5]
Perform following arithmetic operation: a) $101101 + 011011$ b) $101111 - 010101$ [5]
a) $101101 + 011011$ - b) $101111 - 010101$ --- Rules: $0+0=0$ , $0+1=1$ , $1+0=1$ , $1+1=10$ , $1+1+1=11$ Step-by-step (right to left): Position A B Carry In Sum Carry Out ------------------ 1 (LSB) 1 1 0 0 1 2 0 1 1 0 1 3 1 0 1 0 1 4 1 1...

a) $101101 + 011011$ - b) $101111 - 010101$ --- Rules: $0+0=0$, $0+1=1$, $1+0=1$, $1+1=10$, $1+1+1=11$ Step-by-step (right to left): Position A B Carry In Sum Carry Out ------------------ 1 (LSB) 1 1 0 0 1 2 0 1 1 0 1 3 1 0 1 0 1 4 1 1...

Octal Digit	3-bit Binary
2	010
5	101
7	111

4-bit Group	Hexadecimal
1010	A
1111	F

From	To	Result
$(257)_8$	Decimal	$(175)_{10}$
$(257)_8$	Hexadecimal	$(AF)_{16}$

Octal Digit	3-bit Binary
2	010
5	101
7	111

4-bit Group	Hexadecimal
1010	A
1111	F

From	To	Result
$(257)_8$	Decimal	$(175)_{10}$
$(257)_8$	Hexadecimal	$(AF)_{16}$

65 marksNumericalKarnaugh map simplificationAnswer

Simplify (using K-map): F=(A+B+C+D′)(A+B+C′+D)(A+B′+C′+D′)(A+B′+C′+D)(A′+B′+C′+D)(A′+B+C+D′)(A′+B+C′+D)F = (A + B + C + D')(A + B + C' + D)(A + B' + C' + D')(A + B' + C' + D)(A' + B' + C' + D)(A' + B + C + D')(A' + B + C' + D)F=(A+B+C+D′)(A+B+C′+D)(A+B′+C′+D′)(A+B′+C′+D)(A′+B′+C′+D)(A′+B+C+D′)(A′+B+C′+D)[5]

K-Map Simplification of POS Expression

Step 1: Extract Given Data

$F = (A+B+C+D')(A+B+C'+D)(A+B'+C'+D')(A+B'+C'+D)(A'+B'+C'+D)(A'+B+C+D')(A'+B+C'+D)$

For a maxterm, uncomplemented variable = 0, complemented variable = 1.

Sum Term	A	B	C	D	Maxterm
$A+B+C+D'$	0	0	0	1	$M_1$
$A+B+C'+D$	0	0	1	0	$M_2$
$A+B'+C'+D'$	0	1	1	1	$M_7$
$A+B'+C'+D$	0	1	1	0	$M_6$
$A'+B'+C'+D$	1	1	1	0	$M_{14}$
$A'+B+C+D'$	1	0	0	1	$M_9$
$A'+B+C'+D$	1	0	1	0	$M_{10}$

$F = \Pi M(1, 2, 6, 7, 9, 10, 14)$

Step 2: K-Map (place 0 at maxterm positions)

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

The zeros are at cells 1, 2, 6, 7, 9, 10, 14.

Step 3: Group the 0s (for POS)

List of zero cells:

Cell	A	B	C	D
1	0	0	0	1
2	0	0	1	0
6	0	1	1	0
7	0	1	1	1
9	1	0	0	1
10	1	0	1	0
14	1	1	1	0

Group A: {1, 9} (pair): B=0, C=0, D=1; A varies. For a sum term (0→variable, 1→complement): $B + C + D'$

Group B: {2, 6, 10, 14} (quad): C=1, D=0; A and B vary. Sum term: $C' + D$

Group C: {6, 7} (pair): A=0, B=1, C=1; D varies. Sum term: $A + B' + C'$

Check coverage:

Cell 1 → A
Cell 9 → A
Cell 2 → B
Cell 6 → B, C
Cell 10 → B
Cell 14 → B
Cell 7 → C

All seven zeros covered. Each group is essential:

{1,9} is the only group covering cell 1 and 9.
{6,7} is the only group covering cell 7.
{2,6,10,14} covers 2, 10, 14 (needed for 2 and 10 which no other prime implicant covers as a larger group).

Final Simplified POS

$\boxed{F = (B + C + D')\,(C' + D)\,(A + B' + C')}$

K-Map Simplification of POS Expression

Step 1: Extract Given Data

$$F = (A+B+C+D')(A+B+C'+D)(A+B'+C'+D')(A+B'+C'+D)(A'+B'+C'+D)(A'+B+C+D')(A'+B+C'+D)$$

For a maxterm, uncomplemented variable = 0, complemented variable = 1.

Sum Term	A	B	C	D	Maxterm
$A+B+C+D'$	0	0	0	1	$M_1$
$A+B+C'+D$	0	0	1	0	$M_2$
$A+B'+C'+D'$	0	1	1	1	$M_7$
$A+B'+C'+D$	0	1	1	0	$M_6$
$A'+B'+C'+D$	1	1	1	0	$M_{14}$
$A'+B+C+D'$	1	0	0	1	$M_9$
$A'+B+C'+D$	1	0	1	0	$M_{10}$

$$F = \Pi M(1, 2, 6, 7, 9, 10, 14)$$

Step 2: K-Map (place 0 at maxterm positions)

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

The zeros are at cells 1, 2, 6, 7, 9, 10, 14.

Step 3: Group the 0s (for POS)

List of zero cells:

Cell	A	B	C	D
1	0	0	0	1
2	0	0	1	0
6	0	1	1	0
7	0	1	1	1
9	1	0	0	1
10	1	0	1	0
14	1	1	1	0

Group A: {1, 9} (pair): B=0, C=0, D=1; A varies. For a sum term (0→variable, 1→complement): $B + C + D'$

Group B: {2, 6, 10, 14} (quad): C=1, D=0; A and B vary. Sum term: $C' + D$

Group C: {6, 7} (pair): A=0, B=1, C=1; D varies. Sum term: $A + B' + C'$

Check coverage:

Cell 1 → A
Cell 9 → A
Cell 2 → B
Cell 6 → B, C
Cell 10 → B
Cell 14 → B
Cell 7 → C

All seven zeros covered. Each group is essential:

{1,9} is the only group covering cell 1 and 9.
{6,7} is the only group covering cell 7.
{2,6,10,14} covers 2, 10, 14 (needed for 2 and 10 which no other prime implicant covers as a larger group).

Final Simplified POS

$$\boxed{F = (B + C + D'),(C' + D),(A + B' + C')}$$

75 marksMultiplexer implementation using smaller mHideAnswer
Define multiplexer. Implement 8 × 1 multiplexer using 2 × 1 multiplexer. [1+4]
Multiplexer: Definition and Implementation

Definition of Multiplexer

A multiplexer (MUX) is a combinational circuit that selects one of many input lines and forwards it to a single output line based on select lines. It is also called a data selector.
- An n-input multiplexer has:
  
  2^n data input lines
  
  n select lines
  
  1 output line
Implementing 8×1 MUX Using 2×1 MUXes

Key Idea
- An 8×1 MUX has: 8 data inputs (I0-I7), 3 select lines (S2, S1, S0), and 1 output
- A 2×1 MUX has: 2 data inputs, 1 select line, 1 output
How Many 2×1 MUXes Are Needed?

To build an 8×1 MUX from 2×1 MUXes:

Stage MUXes Required Output Lines
Stage 1 (Level 1) 4 × (2×1 MUX) 4 outputs
Stage 2 (Level 2) 2 × (2×1 MUX) 2 outputs
Stage 3 (Level 3) 1 × (2×1 MUX) 1 output (final)

Total = 4 + 2 + 1 = 7 two-input MUXes

Circuit Description
Data Inputs Stage 1 (S0) Stage 2 (S1) Stage 3 (S2) ----------- ------------ ------------ ------------ I0 ─┐ ├─ MUX1 ──┐ I1 ─┘ (S0) │ ├─ MUX5 ──┐ I2 ─┐ │ (S1) │ ├─ MUX2 ──┘ │ I3 ─┘ (S0) ├─ MUX7 ──── Y (Output) │ (S2) I4 ─┐ │ ├─ MUX3 ──┐ │ I5 ─┘ (S0) │ │ ├─ MUX6 ──┘ I6 ─┐ │ (S1) ├─ MUX4 ──┘ I7 ─┘ (S0)
Operation (Truth Table of Selection)

S2 S1 S0 Selected Input
0 0 0 I0
0 0 1 I1
0 1 0 I2
0 1 1 I3
1 0 0 I4
1 0 1 I5
1 1 0 I6
1 1 1 I7

Working Principle
1. Stage 1 (controlled by S0):
  
  MUX1 selects between I0 and I1
  
  MUX2 selects between I2 and I3
  
  MUX3 selects between I4 and I5
  
  MUX4 selects between I6 and I7
2. Stage 2 (controlled by S1):
  
  MUX5 selects between outputs of MUX1 and MUX2
  
  MUX6 selects between outputs of MUX3 and MUX4
3. Stage 3 (controlled by S2):
  
  MUX7 selects between outputs of MUX5 and MUX6 to give the final output Y
Summary

An 8×1 MUX can be implemented using seven 2×1 MUXes arranged in three stages, where each stage is controlled by one select line (S0, S1, S2 respectively), progressively narrowing 8 inputs down to 1 output.

Stage	MUXes Required	Output Lines
Stage 1 (Level 1)	4 × (2×1 MUX)	4 outputs
Stage 2 (Level 2)	2 × (2×1 MUX)	2 outputs
Stage 3 (Level 3)	1 × (2×1 MUX)	1 output (final)

S2	S1	S0	Selected Input
0	0	0	I0
0	0	1	I1
0	1	0	I2
0	1	1	I3
1	0	0	I4
1	0	1	I5
1	1	0	I6
1	1	1	I7

85 marksFlip-flop characteristic tables and equatiAnswer

What is Flip Flop? Differentiate between Combinational circuit and Sequential Circuit. [2+3]

Flip Flop, Combinational vs Sequential Circuits

What is a Flip Flop? [2 marks]

A Flip Flop is a basic bistable sequential logic circuit that can store one bit of binary information (either 0 or 1). It has two stable states and can remain in either state indefinitely until a triggering signal (clock pulse) causes it to change state.

Key characteristics:

It is a memory element -- it remembers its previous output.
It is clock-triggered (edge or level triggered).
It has two outputs: Q (normal output) and Q' (complemented output).

Common types: SR Flip Flop, D Flip Flop, JK Flip Flop, T Flip Flop.

Difference between Combinational and Sequential Circuit [3 marks]

Feature	Combinational Circuit	Sequential Circuit
Definition	Output depends only on the present inputs	Output depends on present inputs AND past outputs (states)
Memory	No memory element is used	Has memory elements (flip flops, latches)
Feedback	No feedback path	Feedback path is present
Clock	Does not require a clock signal	Generally requires a clock signal
Speed	Faster (no clock dependency)	Relatively slower
Examples	Adder, Subtractor, Multiplexer, Decoder, Encoder	Flip Flops, Registers, Counters, Shift Registers
Design	Designed using logic gates only	Designed using logic gates plus flip flops

Summary

A combinational circuit is memoryless -- its output is a pure function of current inputs only. A sequential circuit has memory -- its output is a function of both current inputs and the current state (stored in flip flops), making flip flops the fundamental building block of all sequential circuits.

95 marksJK flip-flop design and operationHideAnswer
Realize JK flip-flop from RS flip-flop. [5]
Realizing JK Flip-Flop from RS Flip-Flop

Review of Both Flip-Flops

RS Flip-Flop Truth Table

S R Q(next) Remarks
0 0 Q No change
0 1 0 Reset
1 0 1 Set
1 1 X Forbidden

JK Flip-Flop Truth Table

J K Q(next) Remarks
0 0 Q No change
0 1 0 Reset
1 0 1 Set
1 1 Q' Toggle

Derivation

The key difference is that JK = 11 toggles the output, whereas SR = 11 is forbidden.

We need to find expressions for S and R in terms of J, K, and the current state Q.

Mapping Table

Compare each input combination and find required S, R inputs:

J K Q Q(next) S R
0 0 0 0 0 X
0 0 1 1 X 0
0 1 0 0 0 X
0 1 1 0 0 1
1 0 0 1 1 0
1 0 1 1 X 0
1 1 0 1 1 0
1 1 1 0 0 1

S and R values are derived from the RS flip-flop excitation table (what S, R must be to achieve the required Q(next) from current Q).

K-Map Simplification for S

Variables: J, K, Q

JK \ Q 0 1
00 0 X
01 0 0
11 1 0
10 1 X

Grouping 1s and X (don't cares):

$\boxed{S = J \cdot Q'}$

K-Map Simplification for R

Variables: J, K, Q

JK \ Q 0 1
00 X 0
01 X 1
11 0 1
10 0 0

Grouping 1s and X (don't cares):

$\boxed{R = K \cdot Q}$

Final Result

The conversion equations are:

$S = J \cdot Q' \qquad R = K \cdot Q$

Logic Circuit Diagram
+-------+ J ------| | | AND |----> S ----+ Q' -----| | | Q +-------+ | +--------+ +-->| |---> Q +-------+ | | RS F/F | K ------| | +-->| |---> Q' | AND |----> R ----+ +--------+ Q -----| | | +-------+ | ^ | | | +----------- Q ---------+
The current output Q is fed back: Q' feeds the S-gate and Q feeds the R-gate, eliminating the forbidden state and enabling toggle operation.

Summary

Condition S = JQ' R = KQ RS Behavior
J=0, K=0 0 0 No change
J=0, K=1 0 Q Reset when Q=1
J=1, K=0 Q' 0 Set when Q=0
J=1, K=1 Q' Q Either Set or Reset (never both 1 simultaneously), achieving toggle

This ensures SR = 11 never occurs, successfully realizing a JK flip-flop from an RS flip-flop.
Realizing JK Flip-Flop from RS Flip-Flop

Review of Both Flip-Flops

RS Flip-Flop Truth Table

S R Q(next) Remarks
0 0 Q No change
0 1 0 Reset
1 0 1 Set
1 1 X Forbidden

JK Flip-Flop Truth Table

J K Q(next) Remarks
0 0 Q No change
0 1 0 Reset
1 0 1 Set
1 1 Q' Toggle

Derivation

The key difference is that JK = 11 toggles the output, whereas SR = 11 is forbidden.

We need to find expressions for S and R in terms of J, K, and the current state Q.

Mapping Table

Compare each input combination and find required S, R inputs:

J K Q Q(next) S R
0 0 0 0 0 X
0 0 1 1 X 0
0 1 0 0 0 X
0 1 1 0 0 1
1 0 0 1 1 0
1 0 1 1 X 0
1 1 0 1 1 0
1 1 1 0 0 1

S and R values are derived from the RS flip-flop excitation table (what S, R must be to achieve the required Q(next) from current Q).

K-Map Simplification for S

Variables: J, K, Q

JK \ Q 0 1
00 0 X
01 0 0
11 1 0
10 1 X

Grouping 1s and X (don't cares):

$$\boxed{S = J \cdot Q'}$$

K-Map Simplification for R

Variables: J, K, Q

JK \ Q 0 1
00 X 0
01 X 1
11 0 1
10 0 0

Grouping 1s and X (don't cares):

$$\boxed{R = K \cdot Q}$$

Final Result

The conversion equations are:

$$S = J \cdot Q' \qquad R = K \cdot Q$$

Logic Circuit Diagram
+-------+ J ------| | | AND |----> S ----+ Q' -----| | | Q +-------+ | +--------+ +-->| |---> Q +-------+ | | RS F/F | K ------| | +-->| |---> Q' | AND |----> R ----+ +--------+ Q -----| | | +-------+ | ^ | | | +----------- Q ---------+
The current output Q is fed back: Q' feeds the S-gate and Q feeds the R-gate, eliminating the forbidden state and enabling toggle operation.

Summary

Condition S = JQ' R = KQ RS Behavior
J=0, K=0 0 0 No change
J=0, K=1 0 Q Reset when Q=1
J=1, K=0 Q' 0 Set when Q=0
J=1, K=1 Q' Q Either Set or Reset (never both 1 simultaneously), achieving toggle

This ensures SR = 11 never occurs, successfully realizing a JK flip-flop from an RS flip-flop.
105 marksNumericalSerial-in serial-out shift registerHideAnswer
Define shift register. Explain the operation of 4-bit Serial-In Serial-Out Shift register with data input 1011. [1+4]
Shift Register: Definition and 4-bit SISO Operation

STEP 1 - EXTRACT (Given Data)
- Register type: 4-bit Serial-In Serial-Out (SISO)
- Number of flip-flops: 4
- Data input: 1011
- Marks distribution: 1 (definition) + 4 (operation)
No values missing. The entry convention (MSB-first vs LSB-first) is not specified; I will state the convention used explicitly.

STEP 2 - SOLVE

Definition of Shift Register (1 mark)

A shift register is a sequential logic circuit made of a cascade of flip-flops (usually D flip-flops) connected in series, in which the stored data bits are shifted one position from one flip-flop to the next on every clock pulse. It is used for temporary storage of data and for serial/parallel data conversion.

4-bit SISO Shift Register (4 marks)

Circuit Description

Four D flip-flops are connected in cascade. The serial input feeds FF0; the output $Q$ of each flip-flop drives the $D$ input of the next; all flip-flops share a common clock. Data appears serially at $Q_3$ .
Serial Serial Input -->[ FF0 ]-->[ FF1 ]-->[ FF2 ]-->[ FF3 ]--> Output D Q0 Q1 Q2 Q3 CLK (common)
Entry convention (chosen): Data 1011 is entered MSB first, so bits enter in order 1, 0, 1, 1.

State Table (shift right, right-most bit entered first at FF0)

Shift direction. On each clock: new bit -> Q0, old Q0 -> Q1, old Q1 -> Q2, old Q2 -> Q3, old Q3 -> out.

Clock Input D Q0 Q1 Q2 Q3 Serial Out
Initial -- 0 0 0 0 --
1 1 1 0 0 0 0
2 0 0 1 0 0 0
3 1 1 0 1 0 0
4 1 1 1 0 1 1

Verification of shifting
- Clock 1: D=1 -> Q0=1, rest 0. State = 1000 ✓
- Clock 2: D=0 -> Q0=0, old Q0(1)->Q1. State = 0100 ✓
- Clock 3: D=1 -> Q0=1, old Q0(0)->Q1, old Q1(1)->Q2. State = 1010 ✓
- Clock 4: D=1 -> Q0=1, old Q0(1)->Q1, old Q1(0)->Q2, old Q2(1)->Q3. State = 1101; the bit leaving Q3 is the old Q3, which is 0.
At the end of clock 4 the register holds the whole word, because the bit entered at clock 1 has been clocked through all four stages and now sits in Q3. Shifting it back out takes three further pulses, so a full load and unload of an n = 4 stage register takes 2n - 1 = 7 clock pulses in total.

Read-out phase (feeding 0s after loading):

Clock Input Q0 Q1 Q2 Q3 Serial Out
4 (loaded) 1 1 1 0 1 --
5 0 0 1 1 0 1 (last bit out)
6 0 0 0 1 1 0
7 0 0 0 0 1 1
8 0 0 0 0 0 1 (first bit out)

So after loading in 4 pulses, the data is retrieved serially over the next 4 pulses. It is worth noting that at clock 4 the bit sitting at Q3 is the LSB-side bit that was loaded first, but the systematic read-out still requires clocks 5 to 8.

Key Characteristics

Feature Description
Data entry 1 bit/clock (serial)
Data output 1 bit/clock (serial)
Pulses to load 4 bits 4
Pulses to read 4 bits 4 more
Main use Time delay / data buffering

Final Result

The 4-bit SISO register loads 1011 in 4 clock pulses. Register state sequence: 0000 -> 1000 -> 0100 -> 1010 -> 1101. The stored data is then read out serially over the next 4 pulses. Note that "serial output = 1 at clock 4" is imprecise, since full retrieval needs clocks 5 to 8.
Shift Register: Definition and 4-bit SISO Operation

STEP 1 - EXTRACT (Given Data)
- Register type: 4-bit Serial-In Serial-Out (SISO)
- Number of flip-flops: 4
- Data input: 1011
- Marks distribution: 1 (definition) + 4 (operation)
No values missing. The entry convention (MSB-first vs LSB-first) is not specified; I will state the convention used explicitly.

STEP 2 - SOLVE

Definition of Shift Register (1 mark)

A shift register is a sequential logic circuit made of a cascade of flip-flops (usually D flip-flops) connected in series, in which the stored data bits are shifted one position from one flip-flop to the next on every clock pulse. It is used for temporary storage of data and for serial/parallel data conversion.

4-bit SISO Shift Register (4 marks)

Circuit Description

Four D flip-flops are connected in cascade. The serial input feeds FF0; the output $Q$ of each flip-flop drives the $D$ input of the next; all flip-flops share a common clock. Data appears serially at $Q_3$.
Serial Serial Input -->[ FF0 ]-->[ FF1 ]-->[ FF2 ]-->[ FF3 ]--> Output D Q0 Q1 Q2 Q3 CLK (common)
Entry convention (chosen): Data 1011 is entered MSB first, so bits enter in order 1, 0, 1, 1.

State Table (shift right, right-most bit entered first at FF0)

Shift direction. On each clock: new bit -> Q0, old Q0 -> Q1, old Q1 -> Q2, old Q2 -> Q3, old Q3 -> out.

Clock Input D Q0 Q1 Q2 Q3 Serial Out
Initial -- 0 0 0 0 --
1 1 1 0 0 0 0
2 0 0 1 0 0 0
3 1 1 0 1 0 0
4 1 1 1 0 1 1

Verification of shifting
- Clock 1: D=1 -> Q0=1, rest 0. State = 1000 ✓
- Clock 2: D=0 -> Q0=0, old Q0(1)->Q1. State = 0100 ✓
- Clock 3: D=1 -> Q0=1, old Q0(0)->Q1, old Q1(1)->Q2. State = 1010 ✓
- Clock 4: D=1 -> Q0=1, old Q0(1)->Q1, old Q1(0)->Q2, old Q2(1)->Q3. State = 1101; the bit leaving Q3 is the old Q3, which is 0.
At the end of clock 4 the register holds the whole word, because the bit entered at clock 1 has been clocked through all four stages and now sits in Q3. Shifting it back out takes three further pulses, so a full load and unload of an n = 4 stage register takes 2n - 1 = 7 clock pulses in total.

Read-out phase (feeding 0s after loading):

Clock Input Q0 Q1 Q2 Q3 Serial Out
4 (loaded) 1 1 1 0 1 --
5 0 0 1 1 0 1 (last bit out)
6 0 0 0 1 1 0
7 0 0 0 0 1 1
8 0 0 0 0 0 1 (first bit out)

So after loading in 4 pulses, the data is retrieved serially over the next 4 pulses. It is worth noting that at clock 4 the bit sitting at Q3 is the LSB-side bit that was loaded first, but the systematic read-out still requires clocks 5 to 8.

Key Characteristics

Feature Description
Data entry 1 bit/clock (serial)
Data output 1 bit/clock (serial)
Pulses to load 4 bits 4
Pulses to read 4 bits 4 more
Main use Time delay / data buffering

Final Result

The 4-bit SISO register loads 1011 in 4 clock pulses. Register state sequence: 0000 -> 1000 -> 0100 -> 1010 -> 1101. The stored data is then read out serially over the next 4 pulses. Note that "serial output = 1 at clock 4" is imprecise, since full retrieval needs clocks 5 to 8.

S	R	Q(next)	Remarks
0	0	Q	No change
0	1	0	Reset
1	0	1	Set
1	1	X	Forbidden

J	K	Q(next)	Remarks
0	0	Q	No change
0	1	0	Reset
1	0	1	Set
1	1	Q'	Toggle

J	K	Q	Q(next)	S	R
0	0	0	0	0	X
0	0	1	1	X	0
0	1	0	0	0	X
0	1	1	0	0	1
1	0	0	1	1	0
1	0	1	1	X	0
1	1	0	1	1	0
1	1	1	0	0	1

JK \ Q	0	1
00	0	X
01	0	0
11	1	0
10	1	X

JK \ Q	0	1
00	X	0
01	X	1
11	0	1
10	0	0

Condition	S = JQ'	R = KQ	RS Behavior
J=0, K=0	0	0	No change
J=0, K=1	0	Q	Reset when Q=1
J=1, K=0	Q'	0	Set when Q=0
J=1, K=1	Q'	Q	Either Set or Reset (never both 1 simultaneously), achieving toggle

S	R	Q(next)	Remarks
0	0	Q	No change
0	1	0	Reset
1	0	1	Set
1	1	X	Forbidden

J	K	Q(next)	Remarks
0	0	Q	No change
0	1	0	Reset
1	0	1	Set
1	1	Q'	Toggle

J	K	Q	Q(next)	S	R
0	0	0	0	0	X
0	0	1	1	X	0
0	1	0	0	0	X
0	1	1	0	0	1
1	0	0	1	1	0
1	0	1	1	X	0
1	1	0	1	1	0
1	1	1	0	0	1

JK \ Q	0	1
00	0	X
01	0	0
11	1	0
10	1	X

JK \ Q	0	1
00	X	0
01	X	1
11	0	1
10	0	0

Condition	S = JQ'	R = KQ	RS Behavior
J=0, K=0	0	0	No change
J=0, K=1	0	Q	Reset when Q=1
J=1, K=0	Q'	0	Set when Q=0
J=1, K=1	Q'	Q	Either Set or Reset (never both 1 simultaneously), achieving toggle

Clock	Input D	Q0	Q1	Q2	Q3	Serial Out
Initial	--	0	0	0	0	--
1	1	1	0	0	0	0
2	0	0	1	0	0	0
3	1	1	0	1	0	0
4	1	1	1	0	1	1

Clock	Input	Q0	Q1	Q2	Q3	Serial Out
4 (loaded)	1	1	1	0	1	--
5	0	0	1	1	0	1 (last bit out)
6	0	0	0	1	1	0
7	0	0	0	0	1	1
8	0	0	0	0	0	1 (first bit out)

Feature	Description
Data entry	1 bit/clock (serial)
Data output	1 bit/clock (serial)
Pulses to load 4 bits	4
Pulses to read 4 bits	4 more
Main use	Time delay / data buffering

Clock	Input D	Q0	Q1	Q2	Q3	Serial Out
Initial	--	0	0	0	0	--
1	1	1	0	0	0	0
2	0	0	1	0	0	0
3	1	1	0	1	0	0
4	1	1	1	0	1	1

Clock	Input	Q0	Q1	Q2	Q3	Serial Out
4 (loaded)	1	1	1	0	1	--
5	0	0	1	1	0	1 (last bit out)
6	0	0	0	1	1	0
7	0	0	0	0	1	1
8	0	0	0	0	0	1 (first bit out)

Feature	Description
Data entry	1 bit/clock (serial)
Data output	1 bit/clock (serial)
Pulses to load 4 bits	4
Pulses to read 4 bits	4 more
Main use	Time delay / data buffering

115 marksShifter circuitsAnswer

Define shifter. Design a 4-bit shifter circuit. [1+4]

Shifter: Definition and 4-bit Design

Definition of Shifter (1 mark)

A shifter is a combinational logic circuit that shifts the bits of a binary input word either to the left or to the right by one or more bit positions. It can also perform logical shift, arithmetic shift, or circular (rotate) operations depending on the control inputs.

Design of a 4-bit Shifter Circuit (4 marks)

Overview

A basic 4-bit combinational shifter accepts:

A 4-bit input: D3, D2, D1, D0 (D3 = MSB, D0 = LSB)
A control signal: S (shift direction)
- S = 0 → Shift Left (each bit moves one position toward MSB; LSB filled with 0)
- S = 1 → Shift Right (each bit moves one position toward LSB; MSB filled with 0)

Truth Table / Operation

S	Y3	Y2	Y1	Y0	Operation
0	D2	D1	D0	0	Shift Left by 1
1	0	D3	D2	D1	Shift Right by 1

Boolean Expressions for Each Output

Using a 2-to-1 MUX at each output bit:

$Y_3 = \bar{S} \cdot D_2 + S \cdot 0 = \bar{S} \cdot D_2$

$Y_2 = \bar{S} \cdot D_1 + S \cdot D_3$

$Y_1 = \bar{S} \cdot D_0 + S \cdot D_2$

$Y_0 = \bar{S} \cdot 0 + S \cdot D_1 = S \cdot D_1$

Circuit Diagram (Gate Level)

Each output bit is implemented using a 2-to-1 MUX (two AND gates + one OR gate):

D3 ─────────────────────────┐
                             AND ──┐
S  ──────────────────────────┘     |
                                   OR ── Y2
S̄  ──────────────────────────┐     |
                             AND ──┘
D1 ─────────────────────────┘

(Similar structure for Y3, Y1, Y0)

Complete structure:

         ┌─────────────────────────────────────────────┐
         │           4-bit Shifter                     │
         │                                             │
D3 ──────┼──── [AND] ──(S·D3)──────────────── Y2      │
         │       ↑                                     │
         │       S                                     │
         │                                             │
D2 ──────┼──── [AND] ──(S̄·D2)──[OR]─────────── Y3     │
         │                        ↑                   │
         │       0 ──[AND]──(S·0)─┘                   │
         │                                             │
D1 ──────┼──── [AND] ──(S̄·D1)──[OR]─────────── Y2     │
         │                        ↑                   │
         │    D3──[AND]──(S·D3)───┘                   │
         │                                             │
D0 ──────┼──── [AND] ──(S̄·D0)──[OR]─────────── Y1     │
         │                        ↑                   │
         │    D2──[AND]──(S·D2)───┘                   │
         │                                             │
  0 ─────┼──── [AND] ──(S̄·0) ──[OR]─────────── Y0     │
         │                        ↑                   │
         │    D1──[AND]──(S·D1)───┘                   │
         └─────────────────────────────────────────────┘

Summary Table

Output	S=0 (Shift Left)	S=1 (Shift Right)
Y3	D2	0
Y2	D1	D3
Y1	D0	D2
Y0	0	D1

Key Points

Each output bit uses one 2-to-1 MUX controlled by S.
Total: 4 MUX units (each built from 2 AND gates + 1 OR gate + 1 NOT gate shared).
The circuit is purely combinational (no clock or memory elements).
The vacated bit position is filled with logic 0 (logical shift).

Shifter: Definition and 4-bit Design

Definition of Shifter (1 mark)

Design of a 4-bit Shifter Circuit (4 marks)

Overview

A basic 4-bit combinational shifter accepts:

A 4-bit input: D3, D2, D1, D0 (D3 = MSB, D0 = LSB)
A control signal: S (shift direction)
- S = 0 → Shift Left (each bit moves one position toward MSB; LSB filled with 0)
- S = 1 → Shift Right (each bit moves one position toward LSB; MSB filled with 0)

Truth Table / Operation

S	Y3	Y2	Y1	Y0	Operation
0	D2	D1	D0	0	Shift Left by 1
1	0	D3	D2	D1	Shift Right by 1

Boolean Expressions for Each Output

Using a 2-to-1 MUX at each output bit:

$$Y_3 = \bar{S} \cdot D_2 + S \cdot 0 = \bar{S} \cdot D_2$$

$$Y_2 = \bar{S} \cdot D_1 + S \cdot D_3$$

$$Y_1 = \bar{S} \cdot D_0 + S \cdot D_2$$

$$Y_0 = \bar{S} \cdot 0 + S \cdot D_1 = S \cdot D_1$$

Circuit Diagram (Gate Level)

Each output bit is implemented using a 2-to-1 MUX (two AND gates + one OR gate):

D3 ─────────────────────────┐
                             AND ──┐
S  ──────────────────────────┘     |
                                   OR ── Y2
S̄  ──────────────────────────┐     |
                             AND ──┘
D1 ─────────────────────────┘

(Similar structure for Y3, Y1, Y0)

Complete structure:

         ┌─────────────────────────────────────────────┐
         │           4-bit Shifter                     │
         │                                             │
D3 ──────┼──── [AND] ──(S·D3)──────────────── Y2      │
         │       ↑                                     │
         │       S                                     │
         │                                             │
D2 ──────┼──── [AND] ──(S̄·D2)──[OR]─────────── Y3     │
         │                        ↑                   │
         │       0 ──[AND]──(S·0)─┘                   │
         │                                             │
D1 ──────┼──── [AND] ──(S̄·D1)──[OR]─────────── Y2     │
         │                        ↑                   │
         │    D3──[AND]──(S·D3)───┘                   │
         │                                             │
D0 ──────┼──── [AND] ──(S̄·D0)──[OR]─────────── Y1     │
         │                        ↑                   │
         │    D2──[AND]──(S·D2)───┘                   │
         │                                             │
  0 ─────┼──── [AND] ──(S̄·0) ──[OR]─────────── Y0     │
         │                        ↑                   │
         │    D1──[AND]──(S·D1)───┘                   │
         └─────────────────────────────────────────────┘

Summary Table

Output	S=0 (Shift Left)	S=1 (Shift Right)
Y3	D2	0
Y2	D1	D3
Y1	D0	D2
Y0	0	D1

Key Points

Each output bit uses one 2-to-1 MUX controlled by S.
Total: 4 MUX units (each built from 2 AND gates + 1 OR gate + 1 NOT gate shared).
The circuit is purely combinational (no clock or memory elements).
The vacated bit position is filled with logic 0 (logical shift).

125 marksDemultiplexer circuitsHideAnswer
Write short notes on: a) De-Multiplexer b) Excitation table [0+2.5+2.5]
A De-Multiplexer is a combinational logic circuit that takes a single input line and routes it to one of several output lines based on the selection inputs. - It is the reverse operation of a Multiplexer. - A DEMUX with n selection lines...

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2081.2 paper 2080 paper 2079 paper 2078 paper 2077 paper

Digital Logic 2081 question paper

Magnitude Comparator

Definition (2 marks)

Design of 4-bit Magnitude Comparator (8 marks)

Given

Step 1: Basic Bit Comparison

Step 2: Derive Output Expressions

Equality Output: (A = B)

Greater Than Output: (A > B)

Less Than Output: (A < B)

Step 3: Logic Circuit Block Diagram

Step 4: Verification Example

Counter: 3-bit Synchronous Up-Down Counter

What is a Counter? [2 marks]

3-bit Synchronous Up-Down Counter [8 marks]

Concept

State Diagram

State Transition Table

JK Flip-Flop Excitation Table (Reference)

Deriving Boolean Expressions

Summary of Excitation Equations

Logic Circuit

Timing Sequence

Timing Diagram (M = 1, up count)

Conclusion

Counter: 3-bit Synchronous Up-Down Counter

What is a Counter? [2 marks]

3-bit Synchronous Up-Down Counter [8 marks]

Concept

State Diagram

State Transition Table

JK Flip-Flop Excitation Table (Reference)

Deriving Boolean Expressions

Summary of Excitation Equations

Logic Circuit

Timing Sequence

Timing Diagram (M = 1, up count)

Conclusion

Convert (257)₈ to Decimal and Hexadecimal

Given Data

Part 1: Octal to Decimal

Part 2: Octal to Hexadecimal (via Binary)

Step 1: Convert each octal digit to 3-bit binary

Step 2: Regroup binary into groups of 4 (from right)

Step 3: Result

Summary

Convert (257)₈ to Decimal and Hexadecimal

Given Data

Part 1: Octal to Decimal

Part 2: Octal to Hexadecimal (via Binary)

Step 1: Convert each octal digit to 3-bit binary

Step 2: Regroup binary into groups of 4 (from right)

Step 3: Result

Summary

K-Map Simplification of POS Expression

Step 1: Extract Given Data

Step 2: K-Map (place 0 at maxterm positions)

Step 3: Group the 0s (for POS)

Final Simplified POS

K-Map Simplification of POS Expression

Step 1: Extract Given Data

Step 2: K-Map (place 0 at maxterm positions)

Step 3: Group the 0s (for POS)

Final Simplified POS

Multiplexer: Definition and Implementation

Definition of Multiplexer

Implementing 8×1 MUX Using 2×1 MUXes

Key Idea

How Many 2×1 MUXes Are Needed?

Circuit Description

Operation (Truth Table of Selection)

Working Principle

Summary

Flip Flop, Combinational vs Sequential Circuits

What is a Flip Flop? [2 marks]

Difference between Combinational and Sequential Circuit [3 marks]

Summary

Realizing JK Flip-Flop from RS Flip-Flop

Review of Both Flip-Flops

RS Flip-Flop Truth Table