Digital Logic — Chapter 4: Data Processing Circuits

Asked 4 times
2081 Bhadra · 5 marks
2070 Chaitra · 5 marks
2069 Chaitra · 4 marks
2068 Baisakh · 6 marks

Explain the operation of two bit magnitude comparator with truth table and circuit diagram.

Answer

A magnitude comparator is a combinational circuit that compares two binary numbers A and B and gives three outputs: $A>B$ , $A=B$ and $A<B$ . Exactly one output is 1 at a time.

A 2-bit comparator compares $A = A_1A_0$ with $B = B_1B_0$ (4 inputs, 3 outputs).

Operation

Compare the most significant bits first. If $A_1 = 1$ and $B_1 = 0$ , then $A>B$ ; if $A_1 = 0$ and $B_1 = 1$ , then $A<B$ .
Only if $A_1 = B_1$ are the LSBs $A_0$ , $B_0$ compared in the same way.
$A=B$ only when both bit pairs are equal.

Equality of bit $i$ is given by an X-NOR gate:

x_i = A_iB_i + \overline{A_i}\,\overline{B_i} = \overline{A_i \oplus B_i}

Truth table

$A_1A_0$	$B_1B_0$	$A>B$	$A=B$	$A<B$
0 0	0 0	0	1	0
0 0	0 1	0	0	1
0 0	1 0	0	0	1
0 0	1 1	0	0	1
0 1	0 0	1	0	0
0 1	0 1	0	1	0
0 1	1 0	0	0	1
0 1	1 1	0	0	1
1 0	0 0	1	0	0
1 0	0 1	1	0	0
1 0	1 0	0	1	0
1 0	1 1	0	0	1
1 1	0 0	1	0	0
1 1	0 1	1	0	0
1 1	1 0	1	0	0
1 1	1 1	0	1	0

Output expressions

\begin{aligned} (A=B) &= x_1x_0 \\ (A>B) &= A_1\overline{B_1} + x_1A_0\overline{B_0} \\ (A<B) &= \overline{A_1}B_1 + x_1\overline{A_0}B_0 \end{aligned}

(The same results come from 4-variable K-maps of the table, e.g. $A>B = A_1\overline{B_1} + A_0\overline{B_1}\,\overline{B_0} + A_1A_0\overline{B_0}$ .)

Circuit diagram

A1,B1 ─[XNOR]── x1        A0,B0 ─[XNOR]── x0

x1, x0 ───────────[AND]────────────── A=B

A1, B1' ──────────[AND]──┐
                         ├─[OR]────── A>B
x1, A0, B0' ──────[AND]──┘

A1', B1 ──────────[AND]──┐
                         ├─[OR]────── A<B
x1, A0', B0 ──────[AND]──┘

Gates: 2 X-NOR gates for $x_1$ , $x_0$ ; one AND for $A=B$ ; two ANDs and an OR for each of $A>B$ and $A<B$ (inverters give the complemented bits).

Example: $A = 10$ , $B = 11$ : $A_1 = B_1$ so $x_1 = 1$ ; $\overline{A_0}B_0 = 1$ , so $A<B = 1$ , and the other outputs are 0.

Asked 3 times
2082 Baisakh · 5 marks
2081 Baisakh · 5 marks
2078 Bhadra · 5 marks

Design 5×32 line decoder using 3×8 line decoders and necessary logic gates.

Answer

A 5×32 decoder has 5 inputs $A_4A_3A_2A_1A_0$ and 32 outputs $D_0$ – $D_{31}$ ; exactly one output is active for each input code. A 3×8 decoder (e.g. 74138) has 3 inputs, 8 outputs and an enable input E. Since $32/8 = 4$ , four 3×8 decoders are needed.

Design idea

The three low bits $A_2A_1A_0$ go to the inputs of all four decoders in parallel.
The two high bits $A_4A_3$ select which one decoder is enabled. This is done with two NOT gates and four AND gates (a 2×4 decoding of $A_4A_3$ ):

$A_4$	$A_3$	Enable signal	Decoder enabled	Outputs active
0	0	$E_0 = \overline{A_4}\,\overline{A_3}$	DEC 0	$D_0$ – $D_7$
0	1	$E_1 = \overline{A_4}A_3$	DEC 1	$D_8$ – $D_{15}$
1	0	$E_2 = A_4\overline{A_3}$	DEC 2	$D_{16}$ – $D_{23}$
1	1	$E_3 = A_4A_3$	DEC 3	$D_{24}$ – $D_{31}$

Circuit

A4 ──┬────────[NOT]── A4'
A3 ──┼──┬─────[NOT]── A3'
     │  │
  E0 = A4'·A3'  (AND)
  E1 = A4'·A3   (AND)
  E2 = A4 ·A3'  (AND)
  E3 = A4 ·A3   (AND)

A2 A1 A0 (common to all four decoders)
     │
     ├──>+-----------+
     │   | 3x8  DEC0 |── D0 ... D7
     │   +-----------+
     │       E ── E0
     ├──>+-----------+
     │   | 3x8  DEC1 |── D8 ... D15
     │   +-----------+
     │       E ── E1
     ├──>+-----------+
     │   | 3x8  DEC2 |── D16 ... D23
     │   +-----------+
     │       E ── E2
     └──>+-----------+
         | 3x8  DEC3 |── D24 ... D31
         +-----------+
             E ── E3

Operation

For an input $A_4A_3A_2A_1A_0$ , only one enable is 1, so only one decoder works; the others keep all outputs inactive. Inside that decoder, $A_2A_1A_0$ selects one of its 8 outputs. Output number = $8 \times (A_4A_3)_{10} + (A_2A_1A_0)_{10}$ .

Example: input 10110 (22): $A_4A_3 = 10$ enables DEC2 (outputs 16–23); $A_2A_1A_0 = 110 = 6$ selects its output 6, i.e. $D_{16+6} = D_{22}$ .

(With 74138 chips, the enable can instead be done using its three enable pins $G_1, \overline{G_{2A}}, \overline{G_{2B}}$ , but the AND-gate method above works with any 3×8 decoder having one active-high enable.)

Asked 3 times
2079 Bhadra · 5 marks
2076 Chaitra · 5 marks
2072 Chaitra · 6 marks

Realize a full-subtractor logic circuit using a single 1:4 demultiplexer and necessary logic gates.

Answer

A full subtractor subtracts $B$ and a borrow-in $B_{in}$ from $A$ , giving difference $D$ and borrow-out $B_o$ .

Truth table

A	B	$B_{in}$	D	$B_o$
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

D = \Sigma m(1,2,4,7) = A \oplus B \oplus B_{in}, \qquad B_o = \Sigma m(1,2,3,7)

Using a 1:4 DEMUX as a 2-to-4 decoder

Connect the data input of the 1:4 demultiplexer to logic 1 and use A, B as its select lines $S_1S_0$ . Each output is then one minterm of A and B:

Y_0 = \overline{A}\,\overline{B},\quad Y_1 = \overline{A}B,\quad Y_2 = A\overline{B},\quad Y_3 = AB

Group the truth table by A, B and see how D and $B_o$ depend on $B_{in}$ :

AB	Active output	D	$B_o$
00	$Y_0$	$B_{in}$	$B_{in}$
01	$Y_1$	$\overline{B_{in}}$	1
10	$Y_2$	$\overline{B_{in}}$	0
11	$Y_3$	$B_{in}$	$B_{in}$

So:

\begin{aligned} D &= B_{in}(Y_0+Y_3) + \overline{B_{in}}(Y_1+Y_2) = B_{in} \oplus (Y_1+Y_2) \\ B_o &= Y_1 + B_{in}(Y_0+Y_3) \end{aligned}

(Since exactly one Y is 1, $Y_0+Y_3 = \overline{Y_1+Y_2}$ .)

Circuit

        +------------+
 1 ────>| Din    Y0  |── Y0
        |        Y1  |── Y1
        |  1:4   Y2  |── Y2
        | DEMUX  Y3  |── Y3
        +------------+
          S1    S0
          A     B

Y1, Y2 ─────[OR]── Q
Q, Bin ─────[XOR]─────────────── D

Y0, Y3 ─────[OR]── P
P, Bin ─────[AND]── Bin·P ──┐
                            ├─[OR]── Bo
Y1 ─────────────────────────┘

Gates needed: one 1:4 DEMUX, three 2-input OR gates, one AND gate and one XOR gate.

Check: A=0, B=1, $B_{in}$ =1 (row 3): $Y_1 = 1$ , so $Q = 1$ , $D = 1 \oplus 1 = 0$ and $B_o = Y_1 = 1$ . This matches the truth table.

Asked 2 times
2080 Baisakh · 8 marks
2078 Bhadra · 4 marks

Realize Full Adder Circuit using a 2×4 decoder and using logic gates.

Answer

A full adder adds three bits A, B and carry-in $C_{in}$ and gives sum S and carry-out $C_o$ .

Truth table

A	B	$C_{in}$	S	$C_o$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

S = \Sigma m(1,2,4,7), \qquad C_o = \Sigma m(3,5,6,7)

Realization with logic gates

From K-maps / algebra:

\begin{aligned} S &= A \oplus B \oplus C_{in} \\ C_o &= AB + BC_{in} + AC_{in} = AB + C_{in}(A \oplus B) \end{aligned}

A, B ────────[XOR]── P = A⊕B
P, Cin ──────[XOR]──────────────── S

P, Cin ──────[AND]── Cin·P ──┐
                             ├─[OR]── Co
A, B ────────[AND]── AB ─────┘

(Two XOR, two AND and one OR gate.)

Realization with a 2×4 decoder

A 2×4 decoder has only two inputs, so it cannot generate all 8 minterms. Feed A and B to the decoder; its outputs are the minterms of A, B:

Y_0 = \overline{A}\,\overline{B},\quad Y_1 = \overline{A}B,\quad Y_2 = A\overline{B},\quad Y_3 = AB

Write S and $C_o$ for each AB combination in terms of $C_{in}$ :

AB	Decoder output	S	$C_o$
00	$Y_0$	$C_{in}$	0
01	$Y_1$	$\overline{C_{in}}$	$C_{in}$
10	$Y_2$	$\overline{C_{in}}$	$C_{in}$
11	$Y_3$	$C_{in}$	1

\begin{aligned} S &= C_{in}(Y_0+Y_3) + \overline{C_{in}}(Y_1+Y_2) = C_{in} \oplus (Y_1+Y_2) \\ C_o &= Y_3 + C_{in}(Y_1+Y_2) \end{aligned}

( $Y_1 + Y_2 = A \oplus B$ , so these are the same equations as the gate realization.)

          +----------+
 A ──────>| I1    Y0 |── (not used)
 B ──────>| I0    Y1 |── Y1
          |  2x4  Y2 |── Y2
          |  DEC  Y3 |── Y3
          +----------+

Y1, Y2 ──────[OR]── P (= A⊕B)
P, Cin ──────[XOR]─────────────── S

P, Cin ──────[AND]── Cin·P ──┐
                             ├─[OR]── Co
Y3 ──────────────────────────┘

Gates needed besides the decoder: two OR gates, one XOR gate and one AND gate.

Check: A=1, B=1, $C_{in}$ =0: $Y_3 = 1$ , $P = 0$ , so $S = 0 \oplus 0 = 0$ and $C_o = Y_3 = 1$ ; correct ( $1+1 = 10_2$ ).

(With a 3×8 decoder, the usual method $S = Y_1+Y_2+Y_4+Y_7$ , $C_o = Y_3+Y_5+Y_6+Y_7$ would need no XOR gate.)

Asked 2 times
2078 Kartik · 2+6 marks
2069 Chaitra · 2+4 marks

What is a priority encoder? Design an octal priority encoder.

Answer

A priority encoder is an encoder that, when more than one input is active at the same time, outputs the code of the input with the highest priority and ignores the others. It also has a valid output V that is 1 when at least one input is active, to separate "input $D_0$ active" from "no input active" (both give code 000).

Octal (8-to-3) priority encoder

Inputs $D_0$ – $D_7$ (active high), $D_7$ has the highest priority. Outputs $A_2A_1A_0$ (binary code) and V. X = don't care.

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$A_2$	$A_1$	$A_0$	V
0	0	0	0	0	0	0	0	X	X	X	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

Output equations

Each output is 1 for the rows where the highest active input has that bit set. For example, $A_0 = 1$ for highest input 7, 5, 3 or 1. Input 5 counts only if 6 and 7 are 0, and so on. After simplification (a term like $\overline{D_7}D_6$ reduces to $D_6$ because $D_7 + \overline{D_7}D_6 = D_7 + D_6$ ):

\begin{aligned} A_2 &= D_4 + D_5 + D_6 + D_7 \\ A_1 &= D_7 + D_6 + D_3\overline{D_4}\,\overline{D_5} + D_2\overline{D_4}\,\overline{D_5} \\ A_0 &= D_7 + D_5\overline{D_6} + D_3\overline{D_4}\,\overline{D_6} + D_1\overline{D_2}\,\overline{D_4}\,\overline{D_6} \\ V &= D_0 + D_1 + D_2 + D_3 + D_4 + D_5 + D_6 + D_7 \end{aligned}

Logic diagram

D4,D5,D6,D7 ─────────────────[OR]── A2

D7 ─────────────────────────┐
D6 ─────────────────────────┤
D3,D4',D5' ──[AND]──────────┼[OR]── A1
D2,D4',D5' ──[AND]──────────┘

D7 ─────────────────────────┐
D5,D6' ──────[AND]──────────┤
D3,D4',D6' ──[AND]──────────┼[OR]── A0
D1,D2',D4',D6' ─[AND]───────┘

D0 ... D7 ───────────────────[OR]── V

Complements $\overline{D_2}, \overline{D_4}, \overline{D_5}, \overline{D_6}$ come from NOT gates.

Example: $D_6 = D_3 = D_1 = 1$ , others 0. Then $A_2 = 1$ , $A_1 = D_6 = 1$ , $A_0 = 0$ (since $\overline{D_6} = 0$ blocks every term except $D_7$ ). Output = 110 = 6, the highest-priority active input, and V = 1. The IC 74148 is a standard 8-to-3 priority encoder (with active-low inputs and outputs).

Asked 2 times
2075 Chaitra · 6 marks
2072 Chaitra · 7 marks

Design a simplest logic circuit for 'b' segment of the BCD-to-7 segment display decoder.

Answer

A BCD-to-7-segment decoder converts a 4-bit BCD digit $ABCD$ (A = MSB) into the seven signals a–g that light the segments of a display. Assume a common-cathode display, so a segment glows when its signal is 1.

     a
   ─────
  │     │
 f│     │b
  │  g  │
   ─────
  │     │
 e│     │c
  │     │
   ─────
     d

Truth table for segment b

Segment b (upper right) is ON for digits 0, 1, 2, 3, 4, 7, 8, 9 and OFF for 5 and 6. Inputs 1010–1111 are not valid BCD, so they are don't-cares.

Digit	A B C D	b
0	0 0 0 0	1
1	0 0 0 1	1
2	0 0 1 0	1
3	0 0 1 1	1
4	0 1 0 0	1
5	0 1 0 1	0
6	0 1 1 0	0
7	0 1 1 1	1
8	1 0 0 0	1
9	1 0 0 1	1
10–15	invalid	X

b = \Sigma m(0,1,2,3,4,7,8,9) + d(10,11,12,13,14,15)

K-map

        CD
AB      00  01  11  10
      +---+---+---+---+
 00   | 1 | 1 | 1 | 1 |
      +---+---+---+---+
 01   | 1 | 0 | 1 | 0 |
      +---+---+---+---+
 11   | X | X | X | X |
      +---+---+---+---+
 10   | 1 | 1 | X | X |
      +---+---+---+---+

Octet m(0,1,2,3,8,9,10,11) → $\overline{B}$
Quad m(0,4,8,12) → $\overline{C}\,\overline{D}$
Quad m(3,7,11,15) → $CD$

b = \overline{B} + \overline{C}\,\overline{D} + CD = \overline{B} + (C \odot D)

Check: digit 5 ( $B=1$ , $C=0$ , $D=1$ ): $\overline{B}=0$ , $\overline{C}\,\overline{D}=0$ , $CD=0$ , so b = 0. Digit 6 ( $B=1$ , $C=1$ , $D=0$ ): b = 0. All other digits give 1.

Simplest logic circuit

Since $\overline{C}\,\overline{D} + CD = \overline{C \oplus D}$ , segment b needs only one X-NOR gate, one NOT gate and one OR gate:

B ──[NOT]── B' ──────────┐
                         [OR]── b
C ──┐                    │
    [XNOR]── C⊙D ────────┘
D ──┘

(If X-NOR is not allowed, use two NOT gates, two AND gates and a 3-input OR for $\overline{B} + \overline{C}\,\overline{D} + CD$ .)

Asked 2 times
2075 Chaitra · 5 marks
2074 Chaitra · 5 marks

Explain the operation of 3 bit magnitude comparator with truth table and draw the circuit.

Answer

A magnitude comparator compares two binary numbers and indicates whether $A>B$ , $A=B$ or $A<B$ . A 3-bit comparator compares $A = A_2A_1A_0$ with $B = B_2B_1B_0$ (6 inputs, 64 combinations, 3 outputs).

Operation

Comparison starts at the most significant bit:

If $A_2 \ne B_2$ , the result is decided: $A_2 = 1, B_2 = 0$ gives $A>B$ ; $A_2 = 0, B_2 = 1$ gives $A<B$ .
If $A_2 = B_2$ , compare $A_1$ and $B_1$ in the same way.
If $A_2 = B_2$ and $A_1 = B_1$ , compare $A_0$ and $B_0$ .
If all three pairs are equal, $A = B$ .

Bit equality is detected by X-NOR gates:

x_i = A_iB_i + \overline{A_i}\,\overline{B_i}, \quad i = 0, 1, 2

Truth table (condensed)

The full table has 64 rows; it is written compactly by bit priority (X = any value):

$A_2$ vs $B_2$	$A_1$ vs $B_1$	$A_0$ vs $B_0$	$A>B$	$A=B$	$A<B$
$A_2>B_2$ (1,0)	X	X	1	0	0
$A_2<B_2$ (0,1)	X	X	0	0	1
$A_2=B_2$	$A_1>B_1$	X	1	0	0
$A_2=B_2$	$A_1<B_1$	X	0	0	1
$A_2=B_2$	$A_1=B_1$	$A_0>B_0$	1	0	0
$A_2=B_2$	$A_1=B_1$	$A_0<B_0$	0	0	1
$A_2=B_2$	$A_1=B_1$	$A_0=B_0$	0	1	0

Sample rows: $A=101, B=011$ gives $A>B$ (decided at $A_2$ ); $A=110, B=111$ gives $A<B$ (decided at $A_0$ ); $A=B=010$ gives $A=B$ .

Output expressions

\begin{aligned} (A=B) &= x_2x_1x_0 \\ (A>B) &= A_2\overline{B_2} + x_2A_1\overline{B_1} + x_2x_1A_0\overline{B_0} \\ (A<B) &= \overline{A_2}B_2 + x_2\overline{A_1}B_1 + x_2x_1\overline{A_0}B_0 \end{aligned}

Circuit

A2,B2 ─[XNOR]─ x2     A1,B1 ─[XNOR]─ x1
A0,B0 ─[XNOR]─ x0

x2, x1, x0 ──────────[AND]──────────── A=B

A2, B2' ─────────[AND]──┐
x2, A1, B1' ─────[AND]──┼─[OR]──────── A>B
x2, x1, A0, B0' ─[AND]──┘

A2', B2 ─────────[AND]──┐
x2, A1', B1 ─────[AND]──┼─[OR]──────── A<B
x2, x1, A0', B0 ─[AND]──┘

Gates: 3 X-NOR, 7 AND, 2 OR (plus inverters for the complemented bits). The $A<B$ output can also be obtained as $\overline{(A>B) + (A=B)}$ using one NOR gate.

Asked 2 times
2079 Bhadra · 1+5 marks
2074 Asoj · 1+4 marks

What is an encoder? Explain 8 to 3 line encoder with circuit diagram and truth table.

Answer

An encoder is a combinational circuit that converts an active signal on one of its $2^n$ (or fewer) input lines into an n-bit binary code. It does the reverse of a decoder.

8-to-3 line (octal-to-binary) encoder

It has 8 inputs $D_0$ – $D_7$ (one per octal digit) and 3 outputs $A_2A_1A_0$ . It is assumed that only one input is 1 at any time.

$D_0$	$D_1$	$D_2$	$D_3$	$D_4$	$D_5$	$D_6$	$D_7$	$A_2$	$A_1$	$A_0$
1	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0	0	1	1
0	0	0	0	1	0	0	0	1	0	0
0	0	0	0	0	1	0	0	1	0	1
0	0	0	0	0	0	1	0	1	1	0
0	0	0	0	0	0	0	1	1	1	1

Output expressions

Each output is the OR of the inputs whose code has a 1 in that bit:

\begin{aligned} A_2 &= D_4 + D_5 + D_6 + D_7 \\ A_1 &= D_2 + D_3 + D_6 + D_7 \\ A_0 &= D_1 + D_3 + D_5 + D_7 \end{aligned}

Circuit diagram

 D0 D1 D2 D3 D4 D5 D6 D7
  │  │  │  │  │  │  │  │
  x  │  │  │  ├──┼──┼──┼──[OR]── A2  (D4,D5,D6,D7)
     │  ├──┼──┼──┼──┼──┼──[OR]── A1  (D2,D3,D6,D7)
     ├──┼──┼──┼──┼──┼──┼──[OR]── A0  (D1,D3,D5,D7)

Three 4-input OR gates are enough; $D_0$ is not connected (no output bit is 1 for it).

Limitations

If no input is active, the output is 000, the same as for $D_0$ ; a valid-output line is needed to tell them apart.
If two inputs are active together, the output is wrong (e.g. $D_3$ and $D_5$ give $011 + 101 = 111$ , which reads as 7). A priority encoder solves this by encoding only the highest active input.

Asked 2 times
2080 Bhadra · 5 marks
2080 Baisakh · 5 marks

Realize a full-adder circuit using a single 1:4 demultiplexer and necessary logic gates.

Answer

A 1:4 demultiplexer with its data input tied to logic 1 behaves as a 2-to-4 decoder: with $A, B$ on the select lines, each output $Y_i$ is one minterm of $A$ and $B$ . The third input $C_{in}$ is then combined with these outputs using a few gates.

Truth table of the full adder

A	B	$C_{in}$	S	$C_{out}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Expressing S and $C_{out}$ in terms of the DEMUX outputs

With $S_1 = A$ , $S_0 = B$ and data input $D = 1$ :

Y_0 = A'B',\quad Y_1 = A'B,\quad Y_2 = AB',\quad Y_3 = AB

From the table, grouping by $AB$ :

AB	DEMUX output	S	$C_{out}$
00	$Y_0$	$C_{in}$	0
01	$Y_1$	$C_{in}'$	$C_{in}$
10	$Y_2$	$C_{in}'$	$C_{in}$
11	$Y_3$	$C_{in}$	1

\begin{aligned} S &= (Y_0 + Y_3)C_{in} + (Y_1 + Y_2)C_{in}' \\ &= (Y_1 + Y_2) \oplus C_{in} \\ C_{out} &= Y_3 + (Y_1 + Y_2)\,C_{in} \end{aligned}

(Here $Y_1 + Y_2 = A \oplus B$ .)

Circuit

        +----------+
  1 --->| D     Y0 |-- (not used)
        |  1:4  Y1 |--+
  A --->| S1    Y2 |--+--[OR]--- P  (= A xor B)
  B --->| S0    Y3 |------------ Y3
        +----------+

  P, Cin  ---[XOR]-------------------- S
  P, Cin  ---[AND]--- P.Cin --+
  Y3 -------------------------+--[OR]-- Cout

Gates needed: one 2-input OR ( $P = Y_1 + Y_2$ ), one XOR ( $S = P \oplus C_{in}$ ), one AND ( $P \cdot C_{in}$ ) and one OR ( $C_{out} = Y_3 + P C_{in}$ ).

Check: for $A=1, B=1, C_{in}=1$ : $Y_3 = 1$ , $P = 0$ , so $S = 0 \oplus 1 = 1$ and $C_{out} = 1$ , i.e. $1+1+1 = 11_2$ . Correct.

2081 Bhadra · 2+2+3 marks

Compare a demultiplexer with the decoder. What is a seven-segment decoder? Find out the simplest logic expression for "b" segment of the BCD to 7-segment display decoder and realize the circuit.

Answer

DEMUX vs decoder

A demultiplexer sends one data input to one of $2^n$ outputs chosen by $n$ select lines. A decoder converts an $n$ -bit input code into one active line out of $2^n$ lines. A decoder with an enable input works as a DEMUX if the enable is used as the data input.

Point	Demultiplexer	Decoder
Inputs	1 data + n select	n code inputs (+ enable)
Function	Routes data to a chosen line	Activates the line for a code
Output content	Copy of the data bit	Fixed 1 (or 0) on one line
Use	Data distribution, serial-to-parallel	Address decoding, code conversion
Example	1:8 DEMUX	3-to-8 decoder (74138)

Seven-segment decoder

A BCD-to-seven-segment decoder (e.g. 7447/7448) takes a 4-bit BCD digit $ABCD$ and produces seven outputs $a$ to $g$ that light the segments of an LED display so that the decimal digit 0–9 is shown. Inputs 1010–1111 never occur, so they are don't-cares.

     a
    ---
 f | g | b
    ---
 e |   | c
    ---
     d

Simplest expression for segment "b"

Segment b is ON for digits 0, 1, 2, 3, 4, 7, 8, 9 and OFF for 5 and 6 (standard 7447 style).

b = \Sigma m(0,1,2,3,4,7,8,9) + d(10,11,12,13,14,15)

K-map (rows AB, columns CD):

AB \ CD	00	01	11	10
00	1	1	1	1
01	1	0	1	0
11	X	X	X	X
10	1	1	X	X

Groups: rows 00 and 10 (all $B=0$ ) give $B'$ ; column 00 gives $C'D'$ ; column 11 gives $CD$ .

b = B' + C'D' + CD = B' + (C \odot D)

Circuit

 B ---[NOT]----------------+
 C --+                     |
     +--[XNOR]--------- --[OR]--- b
 D --+

So segment b needs one inverter, one XNOR and one 2-input OR gate (or with AND/OR: $C'D'$ and $CD$ from two AND gates and a 3-input OR).

2081 Bhadra · 1+3 marks

What is a multiplexer tree? Construct a 1:16 demultiplexer using only 1:4 demultiplexers and logic gates if necessary.

Answer

Multiplexer tree

A multiplexer tree is a larger multiplexer built by connecting smaller multiplexers in two or more levels. The lower select bits drive the first-level MUXes and the higher select bits drive the next level, which picks one first-level output. Example: a 16:1 MUX from five 4:1 MUXes. The same idea used with DEMUXes is called a demultiplexer tree.

1:16 DEMUX from 1:4 DEMUXes

A 1:16 DEMUX needs 4 select lines $S_3 S_2 S_1 S_0$ . Use five 1:4 DEMUXes in two levels:

Level 1: one 1:4 DEMUX receives the data input $D$ ; its selects are the MSBs $S_3 S_2$ . It sends $D$ to one of four lines.
Level 2: four 1:4 DEMUXes, each fed from one level-1 output, all with selects $S_1 S_0$ . They give the 16 outputs $Y_0$ – $Y_{15}$ .

                         S1 S0
                        +------+-- Y0
                     +->| DM1  |-- Y1..Y3
          S3 S2      |  +------+
        +------+     |  +------+-- Y4
  D --->| DM0 0|-----+->| DM2  |-- Y5..Y7
        |     1|--------+------+
        |     2|-----+  +------+-- Y8
        |     3|--+  +->| DM3  |-- Y9..Y11
        +------+  |     +------+
                  |     +------+-- Y12
                  +---->| DM4  |-- Y13..Y15
                        +------+

Working: if $S_3S_2S_1S_0 = 1001$ , DM0 ( $S_3S_2 = 10$ ) sends $D$ to DM3; DM3 ( $S_1S_0 = 01$ ) sends it to its second output, which is $Y_9$ . No extra gates are needed.

2081 Baisakh · 2+3+3 marks

What is a priority encoder? Find out the simplest logic circuit for "e" and "f" segments of the BCD-to-seven segment display decoder.

Answer

Priority encoder

A priority encoder is an encoder that gives the binary code of the highest-priority active input when more than one input is active at the same time. It also has a valid output $V$ that shows at least one input is active. Example: in a 4:2 priority encoder with $D_3$ highest, if $D_1$ and $D_2$ are both 1, the output is $10$ (code of $D_2$ ). The 74148 is an 8:3 priority encoder used for interrupt handling and keyboard encoding.

Segment "e"

Segment e is ON for digits 0, 2, 6, 8 (inputs 10–15 are don't-cares).

e = \Sigma m(0,2,6,8) + d(10\text{–}15)

AB \ CD	00	01	11	10
00	1	0	0	1
01	0	0	0	1
11	X	X	X	X
10	1	0	X	X

Groups: corners (0, 2, 8, 10) give $B'D'$ ; column 10 (2, 6, 10, 14) gives $CD'$ .

e = B'D' + CD' = D'(B' + C)

 B --[NOT]--+
            +--[OR]--+
 C ---------+        +--[AND]--- e
 D --[NOT]-----------+

Segment "f"

Segment f is ON for digits 0, 4, 5, 6, 8, 9.

f = \Sigma m(0,4,5,6,8,9) + d(10\text{–}15)

AB \ CD	00	01	11	10
00	1	0	0	0
01	1	1	0	1
11	X	X	X	X
10	1	1	X	X

Groups: rows 11 and 10 give $A$ ; column 00 gives $C'D'$ ; cells 4, 5, 12, 13 give $BC'$ ; cells 4, 6, 12, 14 give $BD'$ .

f = A + C'D' + BC' + BD'

 C' -+-[AND]-- C'D' --+
 D' -+                |
 B  -+-[AND]-- BC' ---+
 C' -+                +--[OR 4]--- f
 B  -+-[AND]-- BD' ---+
 D' -+                |
 A  ------------------+

Both circuits are checked against the digit table: e.g. for digit 6 ( $0110$ ): $e = 0 + 1\cdot1 = 1$ and $f = 0 + 0 + 0 + 1 = 1$ , both segments lit as required.

2080 Bhadra · 6 marks

Realize the following logic function using a single 1:8 demultiplexer and necessary logic gates. Y(A,B,C,D) = Σm(0,2,3,5,7,8,10,13,15)

Answer

A 1:8 DEMUX with data input tied to 1 produces the 8 minterms of its three select variables. The 4-variable function is realized by choosing three variables as selects and handling the fourth with a gate.

Choice of select lines

Use $B, C, D$ as selects ( $S_2 S_1 S_0$ ) and the data input $= 1$ . Then output $Y_j$ is 1 when $BCD = j$ . Each $Y_j$ covers two minterms of the function: $j$ (with $A=0$ ) and $j+8$ (with $A=1$ ).

BCD = j	Minterm j (A=0)	Minterm j+8 (A=1)	Contribution
0	0 ✓	8 ✓	$Y_0$
1	1 ✗	9 ✗	–
2	2 ✓	10 ✓	$Y_2$
3	3 ✓	11 ✗	$A' Y_3$
4	4 ✗	12 ✗	–
5	5 ✓	13 ✓	$Y_5$
6	6 ✗	14 ✗	–
7	7 ✓	15 ✓	$Y_7$

Hence

Y = Y_0 + Y_2 + Y_5 + Y_7 + A'Y_3

Circuit

            +---------+
   1 ------>| D    Y0 |----------------> to OR
            |      Y1 |
  B --->S2  |      Y2 |----------------> to OR
  C --->S1  | 1:8  Y3 |--+
  D --->S0  |      Y4 |  +--[AND]------> to OR
            |      Y5 |-----^-|--------> to OR
            |      Y6 |       |
            |      Y7 |-------|--------> to OR
            +---------+       |
  A ---[NOT]--- A' -----------+

  Y0, Y2, Y5, Y7, A'Y3 ---[OR 5]---> Y

Gates: one NOT (for $A'$ ), one 2-input AND ( $A'Y_3$ ) and one 5-input OR.

Check: minterm 11 ( $A=1, BCD=011$ ): only $Y_3 = 1$ , but $A' = 0$ , so $Y = 0$ (correct, 11 is not in the list). Minterm 3 ( $A=0$ ): $A'Y_3 = 1$ , so $Y = 1$ . All nine minterms 0, 2, 3, 5, 7, 8, 10, 13, 15 give $Y = 1$ .

(For reference, the minimal SOP is $Y = B'D' + BD + A'B'C$ , which matches the result above.)

2080 Bhadra · 4+2 marks

Design the full-subtractor circuit using decoder and required logic gates. What is a combinational logic circuit?

Answer

Full subtractor using a decoder

A full subtractor computes $A - B - B_{in}$ and gives the difference $D$ and borrow out $B_{out}$ .

A	B	$B_{in}$	D	$B_{out}$	Minterm
0	0	0	0	0	0
0	0	1	1	1	1
0	1	0	1	1	2
0	1	1	0	1	3
1	0	0	1	0	4
1	0	1	0	0	5
1	1	0	0	0	6
1	1	1	1	1	7

D = \Sigma m(1,2,4,7), \qquad B_{out} = \Sigma m(1,2,3,7)

A 3-to-8 decoder with inputs $A, B, B_{in}$ (A = MSB) gives all 8 minterms at $Y_0$ – $Y_7$ . Each output function is the OR of its minterm lines:

D = Y_1 + Y_2 + Y_4 + Y_7, \qquad B_{out} = Y_1 + Y_2 + Y_3 + Y_7

          +--------+
  A ----->| 2   Y0 |
  B ----->| 1   Y1 |---> D, Bout
  Bin --->| 0   Y2 |---> D, Bout
          | 3:8 Y3 |---> Bout
          |     Y4 |---> D
          |     Y5 |
          |     Y6 |
          |     Y7 |---> D, Bout
          +--------+
  Y1, Y2, Y4, Y7 ---[OR 4]---> D
  Y1, Y2, Y3, Y7 ---[OR 4]---> Bout

Two 4-input OR gates complete the design (with an active-low decoder like 74138, use 4-input NAND gates instead).

Combinational logic circuit

A combinational logic circuit is a circuit whose outputs at any instant depend only on the present values of its inputs. It has no memory and no feedback from output to input. It is built only from logic gates. Examples: adders, subtractors, multiplexers, decoders, encoders and comparators.

2080 Baisakh · 4+3 marks

Draw the simplest logic circuit for "a" segment of the BCD-to-seven segment display decoder and realize the simplest logic expression using only NOR gates.

Answer

Segment a of a BCD-to-seven-segment decoder is ON for digits 0, 2, 3, 5, 6, 7, 8, 9 and OFF only for 1 and 4. Inputs 10–15 are don't-cares.

a = \Sigma m(0,2,3,5,6,7,8,9) + d(10\text{–}15)

Simplest SOP and its circuit

AB \ CD	00	01	11	10
00	1	0	1	1
01	0	1	1	1
11	X	X	X	X
10	1	1	X	X

Groups: rows 11, 10 give $A$ ; columns 11, 10 give $C$ ; cells 5, 7, 13, 15 give $BD$ ; corners 0, 2, 8, 10 give $B'D'$ .

a = A + C + BD + B'D' = A + C + (B \odot D)

 B --+-[AND]--------+
 D --+              |
 B'--+-[AND]--------+--[OR 4]--- a
 D'--+              |
 A -----------------+
 C -----------------+

Realization using only NOR gates

NOR-NOR logic directly implements a product-of-sums. Take the 0s of the map (cells 1 and 4) with don't-cares:

Cell 1 ( $0001$ ): cannot combine with 9 (9 is a 1), so the maxterm is $(A + B + C + D')$ .
Cell 4 ( $0100$ ) combines with don't-care 12: $(B' + C + D)$ .

a = (A + B + C + D')(B' + C + D)

Using De Morgan's theorem:

a = \overline{\overline{(A + B + C + D')} + \overline{(B' + C + D)}}

So: two first-level NORs form the complemented sums, a second-level NOR combines them, and the complemented inputs $B'$ and $D'$ are made with NOR gates used as inverters (both inputs tied together).

 B --[NOR]-- B'      D --[NOR]-- D'
 A  --+
 B  --+--[NOR 4]--N1--+
 C  --+               |
 D' --+               +--[NOR 2]--- a
 B' --+               |
 C  --+--[NOR 3]--N2--+
 D  --+

Total: 2 NOR inverters + one 4-input NOR + one 3-input NOR + one 2-input NOR = 5 NOR gates.

Check: digit 1 ( $0001$ ): $N_1 = \overline{0+0+0+0} = 1$ , so $a = 0$ . Digit 4 ( $0100$ ): $N_2 = 1$ , so $a = 0$ . Digit 9 ( $1001$ ): $N_1 = 0$ , $N_2 = \overline{0+0+1} = 0$ , so $a = 1$ . Correct.

2079 Baisakh · 6 marks

Design the logic circuit for 4:2 Priority Encoder.

Answer

A 4:2 priority encoder has four inputs $D_0$ – $D_3$ and gives the 2-bit code $XY$ of the highest-priority active input. Here $D_3$ has the highest priority and $D_0$ the lowest. A valid bit $V$ shows that at least one input is 1 (otherwise $XY$ is meaningless).

Truth table (X = don't care)

$D_3$	$D_2$	$D_1$	$D_0$	X	Y	V
0	0	0	0	X	X	0
0	0	0	1	0	0	1
0	0	1	X	0	1	1
0	1	X	X	1	0	1
1	X	X	X	1	1	1

K-maps (rows $D_3D_2$ , columns $D_1D_0$ )

For X:

$D_3D_2$ \ $D_1D_0$	00	01	11	10
00	X	0	0	0
01	1	1	1	1
11	1	1	1	1
10	1	1	1	1

X = D_2 + D_3

For Y:

$D_3D_2$ \ $D_1D_0$	00	01	11	10
00	X	0	1	1
01	0	0	0	0
11	1	1	1	1
10	1	1	1	1

Y = D_3 + D_1 D_2'

Valid output:

V = D_0 + D_1 + D_2 + D_3

Logic circuit

 D3 ------+-----------------[OR]---- X
 D2 ---+--|-----------------^
       |  |
       +-[NOT]--+
 D1 ----------[AND]--+
                     +--[OR]------- Y
 D3 -----------------+

 D0,D1,D2,D3 -------[OR 4]--------- V

Check: $D_3D_2D_1D_0 = 0110$ : $X = 1$ , $Y = 0 + 1\cdot 0 = 0$ , so output $10$ = input 2, the highest active one. $D_3 = 1$ gives $XY = 11$ whatever the others are. All cases were verified against the table.

2079 Baisakh · 6 marks

Design 8:1 Multiplexer using 4:1 Multiplexer and 2:1 Multiplexer.

Answer

An 8:1 MUX has 8 data inputs $I_0$ – $I_7$ and 3 select lines $S_2S_1S_0$ . It can be built as a multiplexer tree from two 4:1 MUXes and one 2:1 MUX.

Design

Level 1: two 4:1 MUXes. MUX-1 takes $I_0$ – $I_3$ , MUX-2 takes $I_4$ – $I_7$ . Both use the lower select bits $S_1 S_0$ .
Level 2: one 2:1 MUX picks MUX-1 output (when $S_2 = 0$ ) or MUX-2 output (when $S_2 = 1$ ).

           S1 S0
         +-------+
 I0 ---->|       |
 I1 ---->| 4:1   |--P--+
 I2 ---->| MUX-1 |     |    S2
 I3 ---->|       |     |  +-----+
         +-------+     +->|0    |
         +-------+        | 2:1 |---> Y
 I4 ---->|       |     +->|1    |
 I5 ---->| 4:1   |--Q--+  +-----+
 I6 ---->| MUX-2 |
 I7 ---->|       |
         +-------+
           S1 S0

Function table

$S_2$	$S_1$	$S_0$	Y
0	0	0	$I_0$
0	0	1	$I_1$
0	1	0	$I_2$
0	1	1	$I_3$
1	0	0	$I_4$
1	0	1	$I_5$
1	1	0	$I_6$
1	1	1	$I_7$

Working

P = S_1'S_0'I_0 + S_1'S_0 I_1 + S_1S_0'I_2 + S_1S_0I_3

Q = S_1'S_0'I_4 + S_1'S_0 I_5 + S_1S_0'I_6 + S_1S_0I_7

Y = S_2'P + S_2 Q

Substituting gives $Y = \sum_{k=0}^{7} m_k I_k$ , the 8:1 MUX equation, where $m_k$ is the minterm of $S_2S_1S_0$ .

Example: $S_2S_1S_0 = 110$ . Both 4:1 MUXes select their input 2, so $P = I_2$ and $Q = I_6$ . The 2:1 MUX with $S_2 = 1$ passes $Q$ , so $Y = I_6$ . Correct.

2079 Bhadra · 5 marks

Implement the following Boolean function using a single 8:1 multiplexer. F(A,B,C,D) = Σm(2,4,5,7,10,14).

Answer

Use $A, B, C$ as the select lines $S_2S_1S_0$ of the 8:1 MUX and feed each data input with $0$ , $1$ , $D$ or $D'$ .

Implementation table

Each data input $I_j$ corresponds to $ABC = j$ and covers minterms $2j$ ( $D=0$ ) and $2j+1$ ( $D=1$ ). Required minterms: 2, 4, 5, 7, 10, 14.

$I_j$	ABC	Minterms (D=0, D=1)	In F?	$I_j$
$I_0$	000	0, 1	no, no	0
$I_1$	001	2, 3	yes, no	$D'$
$I_2$	010	4, 5	yes, yes	1
$I_3$	011	6, 7	no, yes	$D$
$I_4$	100	8, 9	no, no	0
$I_5$	101	10, 11	yes, no	$D'$
$I_6$	110	12, 13	no, no	0
$I_7$	111	14, 15	yes, no	$D'$

The same result in the usual two-row form:

	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
$D'$	0	2	4	6	8	10	12	14
$D$	1	3	5	7	9	11	13	15
Input	0	$D'$	1	$D$	0	$D'$	0	$D'$

Circuit

             +--------+
  0 -------->| I0     |
  D --[NOT]->| I1     |
  1 -------->| I2     |
  D -------->| I3 8:1 |----> F
  0 -------->| I4 MUX |
  D' ------->| I5     |
  0 -------->| I6     |
  D' ------->| I7     |
             +--------+
               S2 S1 S0
               A  B  C

Only one inverter is needed besides the MUX.

Check: $ABCD = 1010$ (minterm 10): select $101$ picks $I_5 = D' = 1$ , so $F = 1$ . $ABCD = 1011$ (minterm 11): $I_5 = D' = 0$ , so $F = 0$ . Correct.

2078 Kartik · 3+3 marks

Realize full adder circuit using decoder and gates. Subtract (43)₁₀ from (57)₁₀ using 2's complement method.

Answer

Full adder using a decoder and gates

A full adder adds $A$ , $B$ and carry-in $C$ :

A	B	C	S	$C_o$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

S = \Sigma m(1,2,4,7), \qquad C_o = \Sigma m(3,5,6,7)

A 3-to-8 decoder (inputs $A, B, C$ ) produces every minterm; OR the required lines:

S = Y_1 + Y_2 + Y_4 + Y_7, \qquad C_o = Y_3 + Y_5 + Y_6 + Y_7

          +-------+
  A ----->| 2  Y0 |
  B ----->| 1  Y1 |---> to S
  C ----->| 0  Y2 |---> to S
          |    Y3 |---> to Co
          | 3:8 Y4|---> to S
          |    Y5 |---> to Co
          |    Y6 |---> to Co
          |    Y7 |---> to S and Co
          +-------+
  Y1,Y2,Y4,Y7 --[OR 4]--> S
  Y3,Y5,Y6,Y7 --[OR 4]--> Co

(57)₁₀ − (43)₁₀ by 2's complement

Use 7 bits (57 needs 6 bits; one extra bit for sign safety).

57 = 0111001_2, \qquad 43 = 0101011_2

1's complement of 43: $1010100$ . Add 1: 2's complement $= 1010101$ .

      0111001     (+57)
    + 1010101     (2's complement of 43)
    ---------
    1 0001110
    ^ end carry discarded

An end carry appears, so the result is positive and equals the remaining bits: $0001110_2 = 8 + 4 + 2 = 14$ .

Answer: $(57)_{10} - (43)_{10} = (0001110)_2 = (14)_{10}$

2078 Kartik · 6 marks

Realize a following logic expression using a 4:1 multiplexer and standard logic gates. Y(A,B,C) = ΠM(0,2,6,7)

Answer

First convert the maxterm list to minterms. A 3-variable function has minterms 0–7; the ones not listed as maxterms are the minterms:

Y = \Pi M(0,2,6,7) = \Sigma m(1,3,4,5)

Implementation table

Use $A, B$ as select lines ( $S_1 = A$ , $S_0 = B$ ) and express each data input in terms of $C$ . Input $I_j$ covers minterms $2j$ ( $C = 0$ ) and $2j + 1$ ( $C = 1$ ).

	$I_0$	$I_1$	$I_2$	$I_3$
$C'$	0	2	4	6
$C$	1	3	5	7
Input	$C$	$C$	1	0

$I_0$ : only minterm 1 present, so $I_0 = C$ .
$I_1$ : only minterm 3, so $I_1 = C$ .
$I_2$ : both 4 and 5, so $I_2 = 1$ .
$I_3$ : neither 6 nor 7, so $I_3 = 0$ .

Circuit

             +--------+
  C -------->| I0     |
  C -------->| I1 4:1 |----> Y
  1 (Vcc) -->| I2 MUX |
  0 (GND) -->| I3     |
             +--------+
                S1  S0
                A   B

No extra gate is needed here (no $C'$ input appears).

Check

The MUX equation gives

Y = A'B'C + A'BC + AB'(1) + AB(0) = A'C + AB'

ABC	000	001	010	011	100	101	110	111
Y	0	1	0	1	1	1	0	0

Y is 0 exactly at 0, 2, 6, 7, which matches $\Pi M(0,2,6,7)$ .

2078 Bhadra · 5 marks

Design a circuit that compares two 2-bit numbers, A and B, to check if they are equal. The circuit has one output x, so that x = 1 if A = B and x = 0 if A≠B.

Answer

Two 2-bit numbers $A = A_1A_0$ and $B = B_1B_0$ are equal only when each pair of corresponding bits is equal. Bit equality is given by the XNOR gate.

Truth table (16 rows; x = 1 only when A = B)

$A_1A_0$	$B_1B_0$	x
00	00	1
01	01	1
10	10	1
11	11	1
any other pair		0

So

x = A_1'A_0'B_1'B_0' + A_1'A_0B_1'B_0 + A_1A_0'B_1B_0' + A_1A_0B_1B_0

Simplification

Group the terms by the bit-1 pair and the bit-0 pair:

\begin{aligned} x &= (A_1'B_1' + A_1B_1)(A_0'B_0' + A_0B_0) \\ &= (A_1 \odot B_1)(A_0 \odot B_0) \\ &= \overline{(A_1 \oplus B_1)}\cdot\overline{(A_0 \oplus B_0)} \end{aligned}

The K-map (rows $A_1A_0$ , columns $B_1B_0$ ) has 1s only on the diagonal cells 0, 5, 10, 15, which cannot be grouped, confirming that the SOP form has four terms; the XNOR form is the simplest circuit.

Logic circuit

 A1 --+
      +--[XNOR]-- E1 --+
 B1 --+                |
                       +--[AND]--- x
 A0 --+                |
      +--[XNOR]-- E0 --+
 B0 --+

Alternative: $x = \overline{(A_1 \oplus B_1) + (A_0 \oplus B_0)}$ , i.e. two XOR gates followed by one NOR gate.

Check: $A = 10$ , $B = 10$ : $E_1 = 1$ , $E_0 = 1$ , so $x = 1$ . $A = 10$ , $B = 11$ : $E_0 = 0$ , so $x = 0$ .

2076 Chaitra · 2+4 marks

Describe the importance of parity bits in communication system. Explain 3 bits even parity generator circuit clearly.

Answer

Importance of parity bits

A parity bit is an extra bit added to a data word so that the total number of 1s is even (even parity) or odd (odd parity). Its importance in communication:

Error detection: noise can flip a bit during transmission. The receiver recounts the 1s; a wrong parity shows that an error occurred.
Simple and cheap: only one extra bit and a few XOR gates are needed at each end.
Detects all single-bit (odd-number) errors, which are the most common in many links. (It cannot detect two-bit errors and cannot correct errors.)
Used in serial links (UART), memory (parity RAM) and as the base of Hamming codes.

3-bit even parity generator

Inputs: data bits $A, B, C$ . Output: parity bit $P$ chosen so that $A, B, C, P$ together have an even number of 1s.

A	B	C	P
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

P = \Sigma m(1,2,4,7)

The K-map is a checkerboard (no adjacent 1s), so it is simplified with XOR:

\begin{aligned} P &= A'B'C + A'BC' + AB'C' + ABC \\ &= A'(B \oplus C) + A(B \odot C) \\ &= A \oplus B \oplus C \end{aligned}

 A --+
     +--[XOR]--+
 B --+         +--[XOR]--- P
 C ------------+

Working: $P$ is 1 when the data has an odd number of 1s, which makes the total even. Example: data $101$ has two 1s, so $P = 1 \oplus 0 \oplus 1 = 0$ , and the transmitted word $1010$ has two 1s (even). At the receiver, a 4-bit checker $PEC = A \oplus B \oplus C \oplus P$ gives 0 for no error and 1 if a single bit has flipped.

2076 Chaitra · 3+3 marks

Explain the operation of 8:1 multiplexer with necessary diagrams. Construct 32:1 MUX using only 8:1 MUXs.

Answer

Operation of an 8:1 multiplexer

An 8:1 multiplexer selects one of 8 data inputs $I_0$ – $I_7$ and passes it to a single output $Y$ . The input is chosen by three select lines $S_2S_1S_0$ ( $2^3 = 8$ ).

Y = S_2'S_1'S_0'I_0 + S_2'S_1'S_0I_1 + S_2'S_1S_0'I_2 + S_2'S_1S_0I_3 + S_2S_1'S_0'I_4 + S_2S_1'S_0I_5 + S_2S_1S_0'I_6 + S_2S_1S_0I_7

$S_2S_1S_0$	000	001	010	011	100	101	110	111
Y	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$

Internally it has eight 4-input AND gates (each gets one data input and one combination of $S_2, S_1, S_0$ or their complements) and one 8-input OR gate. Only the AND gate whose select combination is true is enabled.

 I0..I7 ---->+---------+
             |  8:1    |
             |  MUX    |-----> Y
 S2 S1 S0 -->+---------+   (74151)

32:1 MUX using only 8:1 MUXes

A 32:1 MUX needs 5 select lines $S_4$ – $S_0$ .

Level 1: four 8:1 MUXes (M1–M4) take $I_0$ – $I_7$ , $I_8$ – $I_{15}$ , $I_{16}$ – $I_{23}$ , $I_{24}$ – $I_{31}$ . All use $S_2S_1S_0$ .
Level 2: a fifth 8:1 MUX (M5) selects one of the four outputs. Its select lines are $S_4$ , $S_3$ on its two lower selects and its MSB select tied to 0, so only inputs $I_0$ – $I_3$ of M5 are used.

  I0-I7   -->[M1 8:1]--+      M5 (8:1)
  I8-I15  -->[M2 8:1]--+---> I0
  I16-I23 -->[M3 8:1]--+---> I1 ...  -->  Y
  I24-I31 -->[M4 8:1]--+---> I2, I3
              S2S1S0      sel: 0, S4, S3
                          I4-I7 = 0

Total: 5 MUXes of 8:1. Example: $S_4..S_0 = 10110$ gives M3 output $I_{16+6} = I_{22}$ , and M5 with $S_4S_3 = 10$ passes M3, so $Y = I_{22}$ .

2076 Asoj · 1+5 marks

What is a decoder? Realize a 2-to-4 line decoder as a full adder circuit.

Answer

Decoder

A decoder is a combinational circuit that converts an $n$ -bit binary input code into $2^n$ output lines, of which exactly one is active for each input combination. Each output is one minterm of the inputs (e.g. 2-to-4, 3-to-8 (74138), BCD-to-decimal decoders).

Full adder using a 2-to-4 decoder

A 2-to-4 decoder has only two inputs, so feed it $A$ and $B$ . Its outputs are the minterms of $A, B$ :

D_0 = A'B',\quad D_1 = A'B,\quad D_2 = AB',\quad D_3 = AB

Group the full-adder truth table by $AB$ and write $S$ and $C_{out}$ in terms of $C_{in}$ :

AB	Active line	S	$C_{out}$
00	$D_0$	$C_{in}$	0
01	$D_1$	$C_{in}'$	$C_{in}$
10	$D_2$	$C_{in}'$	$C_{in}$
11	$D_3$	$C_{in}$	1

Let $P = D_1 + D_2$ ( $= A \oplus B$ ). Then

\begin{aligned} S &= (D_0 + D_3)C_{in} + (D_1 + D_2)C_{in}' = P \oplus C_{in} \\ C_{out} &= D_3 + (D_1 + D_2)C_{in} = D_3 + P\,C_{in} \end{aligned}

Circuit

          +--------+
  A ----->| 2-to-4 |-- D0 (unused)
  B ----->| decoder|-- D1 --+
          |        |-- D2 --+--[OR]-- P
          |        |-- D3 -----------------+
          +--------+                       |
  P ---+--[XOR]------------------- S       |
  Cin -+                                   |
  P ---+--[AND]--------------------+       |
  Cin -+                           +-[OR]--+-- Cout

Gates: 2 OR, 1 XOR, 1 AND.

Check

A B $C_{in}$	P	S	$C_{out}$	A+B+C (binary)
0 1 1	1	0	1	10
1 1 0	0	0	1	10
1 1 1	0	1	1	11
1 0 0	1	1	0	01

All eight combinations were verified.

Alternative: two 2-to-4 decoders with enable can be joined (using $A$ on the enables) into a 3-to-8 decoder; then $S = \Sigma m(1,2,4,7)$ and $C_{out} = \Sigma m(3,5,6,7)$ are taken with two 4-input OR gates.

2076 Asoj · 3 marks

Realize the logic circuit of 1×16 DMUX using 1×4 DMUX and gates if necessary.

Answer

A 1×16 DMUX needs 4 select lines $S_3S_2S_1S_0$ . It is built as a demultiplexer tree from five 1×4 DMUXes; no extra gates are needed.

Stage 1: one 1×4 DMUX receives the data $D$ and uses the MSBs $S_3S_2$ to send it to one of four second-stage DMUXes.
Stage 2: four 1×4 DMUXes use $S_1S_0$ and produce $Y_0$ – $Y_{15}$ .

                       S1 S0
                     +------+-- Y0..Y3
         S3 S2    +->| DM1  |
       +------+   |  +------+
  D -->| DM0 0|---+  +------+-- Y4..Y7
       |     1|----->| DM2  |
       |     2|---+  +------+
       |     3|-+ |  +------+-- Y8..Y11
       +------+ | +->| DM3  |
                |    +------+
                |    +------+-- Y12..Y15
                +--->| DM4  |
                     +------+

$S_3S_2$	Active stage-2 DMUX	Outputs reached by $S_1S_0$
00	DM1	$Y_0$ – $Y_3$
01	DM2	$Y_4$ – $Y_7$
10	DM3	$Y_8$ – $Y_{11}$
11	DM4	$Y_{12}$ – $Y_{15}$

Example: $S = 1110$ → DM0 picks DM4, DM4 picks its output 2, so $D$ appears at $Y_{14}$ .

2075 Chaitra · 7 marks

Design the operation of octal priority encoder with neat diagram.

Answer

An octal (8-to-3) priority encoder has eight inputs $D_0$ – $D_7$ and three outputs $Y_2Y_1Y_0$ giving the binary code of the highest-numbered active input ( $D_7$ = highest priority). A valid output $V$ is 1 when any input is active. The 74148 is a common IC (active-low).

Truth table (X = don't care)

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$Y_2$	$Y_1$	$Y_0$	V
0	0	0	0	0	0	0	0	X	X	X	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

Output equations

Write each output as the OR of the rows where it is 1; each row requires all higher inputs to be 0, and redundant conditions are dropped.

$Y_2 = 1$ for highest input 4, 5, 6 or 7:

Y_2 = D_4 + D_5 + D_6 + D_7

$Y_1 = 1$ for highest input 2, 3, 6 or 7. Inputs 2 and 3 count only if $D_4 = D_5 = 0$ (if $D_6$ or $D_7$ is 1, $Y_1$ is 1 anyway):

Y_1 = D_7 + D_6 + D_5'D_4'D_3 + D_5'D_4'D_2

$Y_0 = 1$ for highest input 1, 3, 5 or 7:

Y_0 = D_7 + D_6'D_5 + D_6'D_4'D_3 + D_6'D_4'D_2'D_1

Valid bit:

V = D_0 + D_1 + \dots + D_7

Logic diagram

 D4,D5,D6,D7 ----------------------[OR 4]--- Y2

 D7 ---------------------------+
 D6 ---------------------------+
 D5',D4',D3 ---[AND 3]---------+--[OR 4]--- Y1
 D5',D4',D2 ---[AND 3]---------+

 D7 ---------------------------+
 D6',D5 -------[AND 2]---------+
 D6',D4',D3 ---[AND 3]---------+--[OR 4]--- Y0
 D6',D4',D2',D1 [AND 4]--------+

 D0 ... D7 ------------------------[OR 8]--- V

Inverters provide $D_2', D_4', D_5', D_6'$ .

Operation

When several keys or interrupt lines are active together, only the highest one is encoded. Example: $D_6 = D_3 = D_1 = 1$ , others 0. Then $Y_2 = 1$ , $Y_1 = 1$ (from $D_6$ ), $Y_0 = 0$ (since $D_6' = 0$ blocks all $Y_0$ terms and $D_7 = 0$ ). Output $110 = 6$ and $V = 1$ . All 255 non-zero input patterns were checked against these equations.

2075 Asoj · 3+3 marks

Explain the operation of octal to binary encoder with necessary diagrams. Convert A+B'C in to canonical form.

Answer

Octal-to-binary encoder

An octal-to-binary (8-to-3) encoder has eight inputs $D_0$ – $D_7$ , one for each octal digit, and three outputs $Y_2Y_1Y_0$ giving the 3-bit binary code of the active input. Only one input is assumed to be active at a time.

Active input	$Y_2$	$Y_1$	$Y_0$
$D_0$	0	0	0
$D_1$	0	0	1
$D_2$	0	1	0
$D_3$	0	1	1
$D_4$	1	0	0
$D_5$	1	0	1
$D_6$	1	1	0
$D_7$	1	1	1

Each output is 1 for the inputs whose code has a 1 in that position:

Y_2 = D_4 + D_5 + D_6 + D_7,\quad Y_1 = D_2 + D_3 + D_6 + D_7,\quad Y_0 = D_1 + D_3 + D_5 + D_7

 D4 D5 D6 D7 --[OR 4]--> Y2
 D2 D3 D6 D7 --[OR 4]--> Y1
 D1 D3 D5 D7 --[OR 4]--> Y0
 (D0 is not connected: it gives 000)

Limitations: $D_0$ active and "no input active" both give 000, and two active inputs give a wrong code (e.g. $D_3 + D_5$ → 111). A priority encoder solves these.

Canonical form of $A + B'C$

Expand each term with the missing variables using $X + X' = 1$ :

\begin{aligned} A &= A(B + B')(C + C') = ABC + ABC' + AB'C + AB'C' \\ B'C &= B'C(A + A') = AB'C + A'B'C \end{aligned}

Combine and remove the repeated term $AB'C$ :

A + B'C = A'B'C + AB'C' + AB'C + ABC' + ABC

= \Sigma m(1, 4, 5, 6, 7)

The canonical POS form uses the remaining combinations:

A + B'C = \Pi M(0, 2, 3) = (A + B + C)(A + B' + C)(A + B' + C')

2075 Asoj · 3+3 marks

Describe the importance of parity bits in communication system. Explain 3 bits odd parity generator circuit clearly.

Answer

Importance of parity bits

A parity bit is one extra bit attached to a data word so that the total count of 1s is either even (even parity) or odd (odd parity). In communication systems it matters because:

Error detection: noise or interference may flip a bit. The receiver checks the parity; a mismatch shows an error, and the data can be re-requested.
Low cost: only one extra bit per word and a few XOR gates.
Single-bit errors are always detected (in fact any odd number of errors).
Limits: an even number of bit errors goes unnoticed, and the faulty bit cannot be located or corrected. Codes like Hamming code extend the parity idea to correct errors.
Odd parity is often preferred because an all-zero word (e.g. a dead line) still carries a 1, so a stuck-at-0 line is detected.

3-bit odd parity generator

Inputs $A, B, C$ ; output $P$ is chosen so that $A, B, C, P$ together contain an odd number of 1s.

A	B	C	P
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

P = \Sigma m(0,3,5,6) = A'B'C' + A'BC + AB'C + ABC'

The K-map has no adjacent 1s, so it is simplified with XOR/XNOR:

\begin{aligned} P &= A'(B \odot C) + A(B \oplus C) \\ &= \overline{A \oplus B \oplus C} \end{aligned}

 A --+
     +--[XOR]--+
 B --+         +--[XNOR]--- P
 C ------------+

Working: if the data already has an odd number of 1s, $P = 0$ ; if even, $P = 1$ . Example: data $110$ (two 1s) gives $P = \overline{1 \oplus 1 \oplus 0} = 1$ , so the word $1101$ has three 1s (odd). The receiver's odd parity checker computes $\overline{A \oplus B \oplus C \oplus P}$ , which is 0 when no error is present.

2075 Asoj · 3+3 marks

Realize the circuit diagram for BCD decoder. Explain 1's and 2's complements with examples?

Answer

BCD decoder (BCD-to-decimal, 4-to-10)

A BCD decoder takes a 4-bit BCD code $ABCD$ ( $A$ = MSB) and activates one of ten outputs $D_0$ – $D_9$ (IC 7442). Codes 1010–1111 never occur, so they are don't-cares and allow partial decoding.

Digit	ABCD	Full decoding	Simplified (with don't-cares)
0	0000	$A'B'C'D'$	$A'B'C'D'$
1	0001	$A'B'C'D$	$A'B'C'D$
2	0010	$A'B'CD'$	$B'CD'$
3	0011	$A'B'CD$	$B'CD$
4	0100	$A'BC'D'$	$BC'D'$
5	0101	$A'BC'D$	$BC'D$
6	0110	$A'BCD'$	$BCD'$
7	0111	$A'BCD$	$BCD$
8	1000	$AB'C'D'$	$AD'$
9	1001	$AB'C'D$	$AD$

 A B C D   A' B' C' D'  (inverters)
 |  |  |  |
 +--+--+--+--[AND]--- D0 = A'B'C'D'
 +--+--+--+--[AND]--- D1 = A'B'C'D
      ...  (one AND gate per output)
 +--------+--[AND]--- D8 = AD'
 +--------+--[AND]--- D9 = AD

Ten AND gates and four inverters form the decoder.

1's and 2's complements

1's complement: invert every bit (0 → 1, 1 → 0). Example: 1's complement of $10110$ is $01001$ .

2's complement: 1's complement + 1. Example: 2's complement of $10110$ is $01001 + 1 = 01010$ .

They represent negative numbers and turn subtraction into addition. Example $9 - 5$ in 4 bits:

 1's complement method        2's complement method
   1001  (9)                    1001  (9)
 + 1010  (1's comp of 0101)   + 1011  (2's comp of 0101)
 ------                       ------
 1 0011                       1 0100
     +1  end-around carry      carry discarded
 ------                       
   0100  = 4                    0100  = 4

In 1's complement the end carry is added back; in 2's complement it is discarded. 2's complement has a single zero and is used in computers.

2075 Asoj · 2+4 marks

What is the role of hazards in asynchronous circuit design? Explain two bit magnitude comparator with necessary diagrams.

Answer

Role of hazards in asynchronous circuit design

A hazard is an unwanted momentary pulse (glitch) at a circuit output caused by unequal propagation delays along different paths when an input changes. Types: static-1 (output should stay 1 but dips to 0), static-0, and dynamic hazards; essential hazards come from feedback delays.

In asynchronous circuits there is no clock to wait until signals settle, and outputs are fed back as state variables. A glitch can therefore be taken as a real change and drive the circuit into a wrong stable state, causing malfunction. So hazards must be removed, e.g. by adding redundant (consensus) terms in the K-map so that every pair of adjacent 1s is covered by a common group, and by careful delay control.

Two-bit magnitude comparator

It compares $A = A_1A_0$ and $B = B_1B_0$ and gives three outputs: $G$ ( $A > B$ ), $E$ ( $A = B$ ) and $L$ ( $A < B$ ).

Let $x_1 = A_1 \odot B_1$ and $x_0 = A_0 \odot B_0$ (bit-equal signals). Compare the MSBs first; only if they are equal, compare the LSBs:

\begin{aligned} E &= x_1 x_0 \\ G &= A_1B_1' + x_1A_0B_0' \\ L &= A_1'B_1 + x_1A_0'B_0 \end{aligned}

From K-maps the same functions in plain SOP are:

G = A_1B_1' + A_0B_1'B_0' + A_1A_0B_0', \quad L = A_1'B_1 + A_0'B_1B_0 + A_1'A_0'B_0

Partial truth table:

$A_1A_0$	$B_1B_0$	G	E	L
10	01	1	0	0
01	01	0	1	0
01	11	0	0	1
11	10	1	0	0

 A1,B1 --[XNOR]-- x1      A0,B0 --[XNOR]-- x0
 x1, x0 ------------------[AND]------------ E
 A1,B1' ---[AND]---+
 x1,A0,B0' [AND]---+------[OR]------------- G
 A1',B1 ---[AND]---+
 x1,A0',B0 [AND]---+------[OR]------------- L

Example: $A = 11$ , $B = 10$ : $x_1 = 1$ , $A_0B_0' = 1$ , so $G = 1$ . All 16 input combinations were verified.

2074 Chaitra · 4+2 marks

Design the 32:1 Multiplexer using 4:1 multiplexers tree concept and implement the function F = Σ(0,1,3,8,9,13) using suitable Multiplexer.

Answer

32:1 MUX using a 4:1 multiplexer tree

A 32:1 MUX has 32 data inputs and 5 select lines $S_4S_3S_2S_1S_0$ ( $2^5 = 32$ ). With 4:1 MUXes (2 selects each) the tree has three levels:

Level	4:1 MUXes	Select lines	Function
1	8 (M1–M8)	$S_1S_0$	Each picks 1 of 4 inputs
2	2 (M9, M10)	$S_3S_2$	Each picks 1 of 4 level-1 outputs
3	1 (M11)	$S_4$ (on its $S_0$ ; its $S_1 = 0$ )	Picks M9 or M10

 I0-I3   ->[M1 ]--+
 I4-I7   ->[M2 ]--+->[M9 ]--+
 I8-I11  ->[M3 ]--+  S3S2   |
 I12-I15 ->[M4 ]--+         |    S4 on S0,
                            +--->[M11]---> Y
 I16-I19 ->[M5 ]--+         |    S1 = 0
 I20-I23 ->[M6 ]--+->[M10]--+
 I24-I27 ->[M7 ]--+  S3S2
 I28-I31 ->[M8 ]--+
   (M1-M8 use S1S0)

Total: 11 MUXes of 4:1 (the last one uses only two inputs; a 2:1 MUX could replace it). Example: $S_4..S_0 = 10110$ → M6 passes $I_{22}$ , M10 ( $S_3S_2 = 01$ ) passes M6, M11 ( $S_4 = 1$ ) passes M10, so $Y = I_{22}$ .

Implementing $F = \Sigma m(0,1,3,8,9,13)$

The largest minterm is 13, so F is a 4-variable function $F(A,B,C,D)$ . A suitable MUX is an 8:1 MUX with $A, B, C$ as selects and $D$ on the data side.

	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
$D'$	0	2	4	6	8	10	12	14
$D$	1	3	5	7	9	11	13	15
Input	1	$D$	0	0	1	0	$D$	0

            +--------+
  1 ------->| I0     |
  D ------->| I1     |
  0 ------->| I2,I3  |
  1 ------->| I4 8:1 |----> F
  0 ------->| I5     |
  D ------->| I6     |
  0 ------->| I7     |
            +--------+
             A  B  C (S2 S1 S0)

Check: $ABCD = 1101$ (13): select 110 → $I_6 = D = 1$ , so $F = 1$ . $ABCD = 1100$ (12): $I_6 = 0$ , so $F = 0$ .

2074 Asoj · 1+4 marks

What is a multiplexer tree? Design the 16 to 1 multiplexer using 4 to 1 multiplexer.

Answer

Multiplexer tree

A multiplexer tree is the connection of small multiplexers in levels to make a larger multiplexer. The first level selects within groups using the lower select bits, and the next level selects one group using the higher select bits.

16:1 MUX from 4:1 MUXes

A 16:1 MUX has inputs $I_0$ – $I_{15}$ and four select lines $S_3S_2S_1S_0$ . Use five 4:1 MUXes:

Level 1: four 4:1 MUXes (M1–M4) with selects $S_1S_0$ . M1 gets $I_0$ – $I_3$ , M2 gets $I_4$ – $I_7$ , M3 gets $I_8$ – $I_{11}$ , M4 gets $I_{12}$ – $I_{15}$ .
Level 2: one 4:1 MUX (M5) with selects $S_3S_2$ picks one of the outputs of M1–M4.

             S1 S0
 I0-I3   -->[ M1 ]--Y1--+
 I4-I7   -->[ M2 ]--Y2--+--> I0..I3 of
 I8-I11  -->[ M3 ]--Y3--+    [ M5 ] ----> Y
 I12-I15 -->[ M4 ]--Y4--+     S3 S2

$S_3S_2$	M5 passes	Y for $S_1S_0$ = 00, 01, 10, 11
00	$Y_1$	$I_0, I_1, I_2, I_3$
01	$Y_2$	$I_4, I_5, I_6, I_7$
10	$Y_3$	$I_8, I_9, I_{10}, I_{11}$
11	$Y_4$	$I_{12}, I_{13}, I_{14}, I_{15}$

Example: $S_3S_2S_1S_0 = 1011$ . Every level-1 MUX selects its input 3, so M3 outputs $I_{11}$ . M5 with $S_3S_2 = 10$ selects M3, so $Y = I_{11}$ , which is input number $1011_2 = 11$ . Correct.

2074 Asoj · 3 marks

Write a short note on ROM.

Answer

ROM (Read-Only Memory) is a non-volatile semiconductor memory whose contents are written once (at manufacture or by programming) and then mainly read. It keeps data when power is removed, so it stores fixed programs such as BIOS/boot code, look-up tables and microcode.

Structure: a $2^n \times m$ ROM has $n$ address lines and $m$ data outputs. An $n$ -to- $2^n$ decoder selects one word (row); a programmable OR array (links at row–column crossings) gives the $m$ output bits. So a ROM can implement any set of $m$ Boolean functions of $n$ variables in sum-of-minterms form.

 A(n-1)..A0 -->[ n:2^n decoder ]--> 2^n word lines
                     |
               [ OR array (links) ]
                     |
               D(m-1) ... D0  (outputs)

Types:

Type	How programmed / erased
Mask ROM	Fixed by the maker using a photo-mask
PROM	Fuses blown once by the user
EPROM	Electrically written, erased by UV light
EEPROM	Electrically written and erased, byte-wise
Flash	Electrically erased in blocks

Example: a $32 \times 8$ ROM has 5 address lines and 8 outputs, storing 256 bits.

2074 Asoj · 3 marks

Write a short note on DE-MUX tree.

Answer

A DEMUX tree is a large demultiplexer formed by connecting smaller demultiplexers in two or more levels. It is used when a DEMUX of the required size is not available as one IC.

Principle: the first-level DEMUX receives the data input and is driven by the higher-order select bits; each of its outputs feeds a second-level DEMUX driven by the lower-order select bits. Number of outputs = product of the outputs of each level.

Example: 1:16 DEMUX from five 1:4 DEMUXes

                      S1 S0
         S3 S2     +-->[1:4]-- Y0..Y3
       +-------+   |
  D -->|  1:4  |---+-->[1:4]-- Y4..Y7
       | DEMUX |---+
       +-------+   +-->[1:4]-- Y8..Y11
                   |
                   +-->[1:4]-- Y12..Y15

If $S_3S_2S_1S_0 = 0110$ , the first DEMUX sends D to the second DEMUX (group 01), which sends it to its output 2, i.e. $Y_6$ .

Features:

No extra gates are needed; only select lines are shared.
Other sizes: 1:32 from 1:8 and 1:4 (or 1:2), 1:8 from 1:2 DEMUXes, etc.
Delay increases with the number of levels.

2073 Shrawan · 5 marks

Implement a full adder circuit using 4:1 Multiplexers.

Answer

A full adder has inputs $A$ , $B$ , $C_{in}$ and outputs Sum $S$ and Carry $C_{out}$ . Two 4:1 MUXes are used, one for each output, with $A$ and $B$ on the select lines ( $S_1 = A$ , $S_0 = B$ ) and $C_{in}$ on the data side.

Truth table

A	B	$C_{in}$	S	$C_{out}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

S = \Sigma m(1,2,4,7), \qquad C_{out} = \Sigma m(3,5,6,7)

Implementation tables

For data input $I_j$ ( $AB = j$ ), the two rows are $C_{in} = 0$ (minterm $2j$ ) and $C_{in} = 1$ (minterm $2j+1$ ).

Sum:

	$I_0$	$I_1$	$I_2$	$I_3$
$C_{in}'$	0	2	4	6
$C_{in}$	1	3	5	7
Input	$C_{in}$	$C_{in}'$	$C_{in}'$	$C_{in}$

Carry:

	$I_0$	$I_1$	$I_2$	$I_3$
$C_{in}'$	0	2	4	6
$C_{in}$	1	3	5	7
Input	0	$C_{in}$	$C_{in}$	1

Circuit

               +-------+                  +-------+
  Cin -------->| I0    |      0 --------->| I0    |
  Cin --[NOT]->| I1 4:1|-> S  Cin ------->| I1 4:1|-> Cout
  Cin'-------->| I2    |      Cin ------->| I2    |
  Cin -------->| I3    |      1 --------->| I3    |
               +-------+                  +-------+
                 A  B                       A  B

Check

From the MUX equation:

C_{out} = A'B(C_{in}) + AB'(C_{in}) + AB(1) = (A \oplus B)C_{in} + AB

which is the standard carry expression. For $A = 1, B = 0, C_{in} = 1$ : select $10$ gives $S = I_2 = C_{in}' = 0$ and $C_{out} = I_2 = C_{in} = 1$ , i.e. $1 + 0 + 1 = 10_2$ . All eight rows were verified.

2073 Shrawan · 6 marks

Design 1:32 demultiplexer tree using 1:8 DEMUXs and 1:2 DEMUXs only.

Answer

A 1:32 DEMUX has one data input $D$ , five select lines $S_4S_3S_2S_1S_0$ and 32 outputs $Y_0$ – $Y_{31}$ . Since $32 = 2 \times 2 \times 8$ , it can be built with three 1:2 DEMUXes and four 1:8 DEMUXes in three levels.

Design

Level	DEMUXes	Select	Outputs
1	one 1:2 (DM-A)	$S_4$	2 lines
2	two 1:2 (DM-B, DM-C)	$S_3$	4 lines
3	four 1:8 (DM1–DM4)	$S_2S_1S_0$	32 outputs

                         S2S1S0
                 S3   +->[1:8 DM1]-- Y0..Y7
         S4    +[1:2]-+
       +[1:2]--+ DM-B +->[1:8 DM2]-- Y8..Y15
  D -->| DM-A  |
       +-------+ S3   +->[1:8 DM3]-- Y16..Y23
               +[1:2]-+
                 DM-C +->[1:8 DM4]-- Y24..Y31

DM-A output 0 (when $S_4 = 0$ ) feeds DM-B; output 1 feeds DM-C.
DM-B sends data to DM1 ( $S_3 = 0$ ) or DM2 ( $S_3 = 1$ ); DM-C to DM3 or DM4.
Each 1:8 DEMUX decodes $S_2S_1S_0$ to one of its eight outputs.

$S_4S_3$	Active 1:8 DEMUX	Output range
00	DM1	$Y_0$ – $Y_7$
01	DM2	$Y_8$ – $Y_{15}$
10	DM3	$Y_{16}$ – $Y_{23}$
11	DM4	$Y_{24}$ – $Y_{31}$

Example

$S_4S_3S_2S_1S_0 = 11010$ ( $= 26$ ): DM-A ( $S_4 = 1$ ) → DM-C; DM-C ( $S_3 = 1$ ) → DM4; DM4 ( $S_2S_1S_0 = 010$ ) → its output 2, which is $Y_{24+2} = Y_{26}$ . So $D$ appears at $Y_{26}$ and all other outputs stay 0.

Total: 3 DEMUXes of 1:2 + 4 DEMUXes of 1:8 = 7 ICs, no extra gates.

2073 Shrawan · 2+6 marks

Differentiate between combinational and sequential circuits. Explain BCD-to-Decimal decoder circuit with suitable diagram.

Answer

Combinational vs sequential circuits

Point	Combinational	Sequential
Output depends on	Present inputs only	Present inputs and past state
Memory	None	Has memory (flip-flops)
Feedback	No	Yes
Clock	Not needed	Usually needed (synchronous)
Building blocks	Gates	Gates + flip-flops
Examples	Adder, MUX, decoder	Counter, register, FSM

BCD-to-decimal decoder

A BCD-to-decimal (4-line to 10-line) decoder accepts a 4-bit BCD code $ABCD$ ( $A$ = MSB) and makes exactly one of ten outputs $D_0$ – $D_9$ active, showing the decimal digit. The 7442 is the TTL IC (active-low outputs).

Truth table

ABCD	Active output	ABCD	Active output
0000	$D_0$	0101	$D_5$
0001	$D_1$	0110	$D_6$
0010	$D_2$	0111	$D_7$
0011	$D_3$	1000	$D_8$
0100	$D_4$	1001	$D_9$

Codes 1010–1111 are invalid in BCD, so they are don't-cares.

Output expressions. With full decoding each output is a 4-variable minterm, e.g. $D_5 = A'BC'D$ . Using the don't-cares (K-map grouping), shorter expressions are obtained:

Output	Full decoding	Simplified
$D_0$	$A'B'C'D'$	$A'B'C'D'$
$D_1$	$A'B'C'D$	$A'B'C'D$
$D_2$	$A'B'CD'$	$B'CD'$
$D_3$	$A'B'CD$	$B'CD$
$D_4$	$A'BC'D'$	$BC'D'$
$D_5$	$A'BC'D$	$BC'D$
$D_6$	$A'BCD'$	$BCD'$
$D_7$	$A'BCD$	$BCD$
$D_8$	$AB'C'D'$	$AD'$
$D_9$	$AB'C'D$	$AD$

For example, $D_8$ : 1000 can be grouped with don't-cares 1010, 1100, 1110, giving $AD'$ .

Logic diagram

 A  B  C  D
 |  |  |  |---[NOT]-- D'
 |  |  |------[NOT]-- C'
 |  |---------[NOT]-- B'
 |------------[NOT]-- A'

 A',B',C',D' --[AND4]--> D0
 A',B',C',D  --[AND4]--> D1
 B',C,D'     --[AND3]--> D2
 B',C,D      --[AND3]--> D3
 B,C',D'     --[AND3]--> D4
 B,C',D      --[AND3]--> D5
 B,C,D'      --[AND3]--> D6
 B,C,D       --[AND3]--> D7
 A,D'        --[AND2]--> D8
 A,D         --[AND2]--> D9

Working: for input $0111$ , only the gate $BCD$ has all inputs 1, so $D_7 = 1$ and the others are 0. The simplified version gives false outputs for invalid codes (e.g. 1111 activates $D_7$ and $D_9$ ); if invalid codes must be rejected, full decoding is used, as in the 7442 which keeps all outputs inactive for 1010–1111. Uses: driving decimal indicators (Nixie tubes, LEDs) and selecting one of ten devices.

2072 Chaitra · 4+3 marks

How do you design 32:1 Mux by using multiplexer tree? Implement logic function Y = Σm(0,1,3,8,9,13,15) by using suitable multiplexer.

Answer

32:1 MUX by multiplexer tree

A 32:1 MUX needs 5 select lines $S_4$ – $S_0$ . A common tree uses four 8:1 MUXes and one 4:1 MUX:

Level 1: four 8:1 MUXes with selects $S_2S_1S_0$ : M1 takes $I_0$ – $I_7$ , M2 $I_8$ – $I_{15}$ , M3 $I_{16}$ – $I_{23}$ , M4 $I_{24}$ – $I_{31}$ .
Level 2: one 4:1 MUX (M5) with selects $S_4S_3$ selects one of M1–M4.

           S2 S1 S0
 I0-I7   -->[M1 8:1]--+
 I8-I15  -->[M2 8:1]--+-->[M5 4:1]---> Y
 I16-I23 -->[M3 8:1]--+     S4 S3
 I24-I31 -->[M4 8:1]--+

$S_4S_3$	Selected MUX	Inputs reached
00	M1	$I_0$ – $I_7$
01	M2	$I_8$ – $I_{15}$
10	M3	$I_{16}$ – $I_{23}$
11	M4	$I_{24}$ – $I_{31}$

Example: $S = 10101$ → M3 picks its input 5 ( $I_{21}$ ) and M5 ( $S_4S_3 = 10$ ) passes it, so $Y = I_{21}$ . (With only 4:1 MUXes the tree would need 8 + 2 + 1 = 11 MUXes.)

Implementing $Y = \Sigma m(0,1,3,8,9,13,15)$

The largest minterm is 15, so $Y = Y(A,B,C,D)$ . A suitable MUX is an 8:1 MUX with $A, B, C$ on the selects and $D$ on the data inputs.

	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
$D'$	0	2	4	6	8	10	12	14
$D$	1	3	5	7	9	11	13	15
Input	1	$D$	0	0	1	0	$D$	$D$

            +--------+
  1 ------->| I0     |
  D ------->| I1     |
  0 ------->| I2     |
  0 ------->| I3 8:1 |----> Y
  1 ------->| I4 MUX |
  0 ------->| I5     |
  D ------->| I6     |
  D ------->| I7     |
            +--------+
             A  B  C

Check: $ABCD = 1111$ (15): select 111 → $I_7 = D = 1$ , $Y = 1$ . $ABCD = 0010$ (2): select 001 → $I_1 = D = 0$ , $Y = 0$ . All 16 rows match.

2070 Chaitra · 4 marks

Realize the logic circuit of the following using 8:1 MUX. F(W,X,Y,Z) = Σm(1,2,5,7,8,10,12,13,15)

Answer

Use $W, X, Y$ as the select lines $S_2S_1S_0$ of the 8:1 MUX and connect $Z$ , $Z'$ , 0 or 1 to the data inputs. Input $I_j$ covers minterms $2j$ ( $Z = 0$ ) and $2j+1$ ( $Z = 1$ ).

Required minterms: 1, 2, 5, 7, 8, 10, 12, 13, 15.

	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
$Z'$	0	2	4	6	8	10	12	14
$Z$	1	3	5	7	9	11	13	15
Input	$Z$	$Z'$	$Z$	$Z$	$Z'$	$Z'$	1	$Z$

             +--------+
  Z -------->| I0     |
  Z' ------->| I1     |
  Z -------->| I2     |
  Z -------->| I3 8:1 |----> F
  Z' ------->| I4 MUX |
  Z' ------->| I5     |
  1 -------->| I6     |
  Z -------->| I7     |
             +--------+
              W  X  Y
  (Z' from one NOT gate)

Check: $WXYZ = 1100$ (12): select 110 → $I_6 = 1$ , so $F = 1$ . $WXYZ = 1001$ (9): select 100 → $I_4 = Z' = 0$ , so $F = 0$ (9 is not a minterm). Correct.

2068 Chaitra · 5 marks

Design a 32 to 1 multiplexer using 16 to 1 and 2 to 1 multiplexers.

Answer

A 32:1 MUX has inputs $I_0$ – $I_{31}$ and five select lines $S_4S_3S_2S_1S_0$ . It is built from two 16:1 MUXes and one 2:1 MUX (a multiplexer tree).

Design

Level 1: MUX-1 (16:1) takes $I_0$ – $I_{15}$ ; MUX-2 (16:1) takes $I_{16}$ – $I_{31}$ . Both share the lower selects $S_3S_2S_1S_0$ .
Level 2: a 2:1 MUX with select $S_4$ passes MUX-1 output when $S_4 = 0$ and MUX-2 output when $S_4 = 1$ .

             S3 S2 S1 S0
           +-----------+
 I0-I15 -->| 16:1 MUX-1|--P--+      S4
           +-----------+     |   +------+
                             +-->|0     |
           +-----------+         | 2:1  |---> Y
 I16-I31 ->| 16:1 MUX-2|--Q----->|1     |
           +-----------+         +------+
             S3 S2 S1 S0

Output equation

Y = S_4'P + S_4Q

where $P = \sum_{k=0}^{15} m_k I_k$ and $Q = \sum_{k=0}^{15} m_k I_{k+16}$ , with $m_k$ the minterms of $S_3S_2S_1S_0$ .

$S_4$	$S_3S_2S_1S_0$	Y
0	0000 – 1111	$I_0$ – $I_{15}$
1	0000 – 1111	$I_{16}$ – $I_{31}$

Example

$S_4S_3S_2S_1S_0 = 11001$ (= 25). MUX-1 gives $I_9$ and MUX-2 gives $I_{25}$ (both select input 9). The 2:1 MUX with $S_4 = 1$ passes $Q$ , so $Y = I_{25}$ . Correct.

Alternative: if the 16:1 MUXes (e.g. 74150) have enable inputs, connect $S_4'$ to the enable of MUX-1 and $S_4$ to MUX-2, and OR the two outputs instead of using the 2:1 MUX.

2068 Chaitra · 5 marks

Design a 3-bit even parity generator and 4-bit even parity checker circuit.

Answer

Parity is used to detect single-bit errors. With even parity, the transmitted word (data + parity bit) always has an even number of 1s.

3-bit even parity generator

Inputs $A, B, C$ ; output $P$ makes the total number of 1s even.

A	B	C	P
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

\begin{aligned} P &= \Sigma m(1,2,4,7) = A'B'C + A'BC' + AB'C' + ABC \\ &= A'(B \oplus C) + A(B \odot C) = A \oplus B \oplus C \end{aligned}

 A --+
     +--[XOR]--+
 B --+         +--[XOR]--- P
 C ------------+

4-bit even parity checker

The receiver gets $A, B, C, P$ and produces the parity error check $PEC$ : 0 if the count of 1s is even (no error), 1 if odd (error).

A B C P	No. of 1s	PEC
0000	0	0
0001	1	1
0011	2	0
0111	3	1
1111	4	0
(other rows follow the same rule)

$PEC = 1$ for minterms 1, 2, 4, 7, 8, 11, 13, 14 (odd number of 1s). The K-map is a checkerboard, so

PEC = A \oplus B \oplus C \oplus P = (A \oplus B) \oplus (C \oplus P)

 A --+
     +--[XOR]--+
 B --+         |
               +--[XOR]--- PEC
 C --+         |
     +--[XOR]--+
 P --+

Example

Data $110$ : generator gives $P = 1 \oplus 1 \oplus 0 = 0$ ; sent word $1100$ . If received correctly, $PEC = 1 \oplus 1 \oplus 0 \oplus 0 = 0$ (no error). If bit C flips (received $1110$ ), $PEC = 1$ , so an error is flagged.

2082 Shrawan · 4 marks

Implement 16:1 multiplexer using only 8:1 multiplexers.

Answer

A 16:1 MUX has inputs $I_0$ – $I_{15}$ and four selects $S_3S_2S_1S_0$ . Using only 8:1 MUXes, three are needed:

MUX-1 (8:1): inputs $I_0$ – $I_7$ , selects $S_2S_1S_0$ , output $P$ .
MUX-2 (8:1): inputs $I_8$ – $I_{15}$ , selects $S_2S_1S_0$ , output $Q$ .
MUX-3 (8:1) used as a 2:1 MUX: $P$ to its $I_0$ , $Q$ to its $I_1$ ; its select $S_0$ is driven by $S_3$ and its other two selects are tied to 0.

         S2 S1 S0
        +--------+
 I0-I7->| MUX-1  |--P--+     +--------+
        +--------+     +---->| I0     |
        +--------+     +---->| I1 MUX3|---> Y
 I8-15->| MUX-2  |--Q--+     | I2-I7=0|
        +--------+           +--------+
         S2 S1 S0            0  0  S3
                             (S2 S1 S0 of MUX-3)

Y = S_3'P + S_3Q

$S_3$	Y
0	$P$ = one of $I_0$ – $I_7$
1	$Q$ = one of $I_8$ – $I_{15}$

Example: $S_3S_2S_1S_0 = 1101$ : $P = I_5$ , $Q = I_{13}$ ; MUX-3 select $= 001$ passes $Q$ , so $Y = I_{13}$ . Correct.

2082 Shrawan · 4 marks

Realize a full-subtractor circuit using a single 2×4 decoder and necessary logic gates.

Answer

A full subtractor computes $A - B - B_{in}$ , giving difference $D$ and borrow $B_{out}$ . A single 2×4 decoder has only two inputs, so feed it $A$ and $B$ ; its outputs are the minterms of $A, B$ , and $B_{in}$ is combined with gates.

Truth table grouped by AB

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

AB	Decoder line	D	$B_{out}$
00	$Y_0$	$B_{in}$	$B_{in}$
01	$Y_1$	$B_{in}'$	1
10	$Y_2$	$B_{in}'$	0
11	$Y_3$	$B_{in}$	$B_{in}$

Equations

\begin{aligned} D &= (Y_1 + Y_2) \oplus B_{in} \\ B_{out} &= Y_1 + (Y_0 + Y_3)\,B_{in} \end{aligned}

(Here $Y_1 + Y_2 = A \oplus B$ and $Y_0 + Y_3 = A \odot B$ .)

          +--------+
  A ----->| 2x4  Y0|---> E (OR)
  B ----->|      Y1|---> P (OR), Bout (OR)
          |      Y2|---> P (OR)
          |      Y3|---> E (OR)
          +--------+
  Y0, Y3 ---[OR]--- E  (= A xnor B)
  Y1, Y2 ---[OR]--- P  (= A xor B)
  P, Bin ---[XOR]------------------ D
  E, Bin ---[AND]--- E.Bin --+
  Y1 ------------------------+-[OR]-- Bout

Gates: 2 OR (2-input), 1 XOR, 1 AND, 1 OR.

Check: $A=0, B=1, B_{in}=1$ : $Y_1 = 1$ , $P = 1$ , $D = 1 \oplus 1 = 0$ , $B_{out} = 1$ ; indeed $0 - 1 - 1 = -2$ , i.e. $D = 0$ with borrow 1. All 8 rows were verified.

2082 Shrawan · 2+3 marks

Differentiate between RAM and ROM. How does an EEPROM cell work?

Answer

RAM vs ROM

Point	RAM	ROM
Full form	Random Access Memory	Read Only Memory
Operation	Read and write	Read only (written once / rarely)
Volatility	Volatile: data lost on power off	Non-volatile: data kept
Use	Temporary data, running programs	Firmware, BIOS, look-up tables
Types	SRAM, DRAM	Mask ROM, PROM, EPROM, EEPROM
Write speed	Fast	Slow or not possible

Working of an EEPROM cell

EEPROM (Electrically Erasable PROM) can be written and erased electrically, byte by byte, in the circuit. Each cell uses a floating-gate MOSFET (FLOTOX) plus a select transistor.

       Control gate
     ==============
       oxide
     --------------  Floating gate (isolated)
       thin tunnel oxide (~10 nm)
  n+ Source  [ p-substrate ]  n+ Drain

Structure: a floating gate, fully surrounded by oxide, lies between the control gate and the channel. A small region of very thin oxide lies over the drain.
Programming (write): a high voltage (about 12–20 V) is applied to the control gate with the drain grounded. Electrons tunnel through the thin oxide into the floating gate (Fowler–Nordheim tunnelling). The trapped negative charge raises the transistor's threshold voltage.
Erasing: the voltage is reversed (high voltage on the drain, control gate grounded), so electrons tunnel back out of the floating gate and the threshold falls to its normal value.
Reading: a normal voltage is applied to the control gate. A charged cell does not conduct (read as 0); an uncharged cell conducts (read as 1). The charge stays for 10+ years without power, so the memory is non-volatile.

EEPROM does not need UV light (unlike EPROM), but the cell is larger and the number of write cycles is limited (about $10^5$ – $10^6$ ).

2082 Baisakh · 5 marks

Design a circuit that compares two 4-bit numbers, A and B, to check if they are equal. The circuit has one output X, so that X = 1 if A = B and X = 0 if A ≠ B.

Answer

Two 4-bit numbers $A = A_3A_2A_1A_0$ and $B = B_3B_2B_1B_0$ are equal only when every pair of corresponding bits is equal. Equality of one pair is detected by an XNOR gate.

Bit-equality signals

x_i = A_i \odot B_i = A_iB_i + A_i'B_i', \quad i = 0, 1, 2, 3

$A_i$	$B_i$	$x_i$
0	0	1
0	1	0
1	0	0
1	1	1

Output

$X = 1$ only if all four $x_i = 1$ :

X = x_3x_2x_1x_0 = (A_3 \odot B_3)(A_2 \odot B_2)(A_1 \odot B_1)(A_0 \odot B_0)

Equivalent form with XOR and NOR:

X = \overline{(A_3 \oplus B_3) + (A_2 \oplus B_2) + (A_1 \oplus B_1) + (A_0 \oplus B_0)}

A full truth table would have $2^8 = 256$ rows with $X = 1$ in only 16 of them ( $A = B$ ), so the bit-wise method is used instead of a K-map.

Logic circuit

 A3 --+
 B3 --+--[XNOR]-- x3 --+
 A2 --+                |
 B2 --+--[XNOR]-- x2 --+
                       +--[AND 4]--- X
 A1 --+                |
 B1 --+--[XNOR]-- x1 --+
 A0 --+                |
 B0 --+--[XNOR]-- x0 --+

Gates: four 2-input XNOR gates and one 4-input AND gate.

Examples

A	B	$x_3x_2x_1x_0$	X
1011	1011	1111	1
1011	1001	1101	0
0110	1110	0111	0

This is the "A = B" part of the 7485 4-bit magnitude comparator.

2082 Baisakh · 4 marks

Implement the following function with 8:1 multiplexer F(A,B,C,D) = Σm(0,1,3,4,8,9,15) + dΣ(2,6,13).

Answer

Use $A, B, C$ as the select lines $S_2S_1S_0$ and $D$ (or $D'$ , 0, 1) on the data inputs. Input $I_j$ covers minterms $2j$ ( $D=0$ ) and $2j+1$ ( $D=1$ ).

Minterms: 0, 1, 3, 4, 8, 9, 15
Don't-cares: 2, 6, 13 (each can be taken as 0 or 1, whichever gives a simpler input)

Implementation table (X = don't care)

	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
$D'$	0	X(2)	4	X(6)	8	10	12	14
$D$	1	3	5	7	9	11	X(13)	15
Input	1	1	$D'$	0	1	0	0	$D$

Choices for the don't-cares:

$I_1$ : minterm 3 is 1; taking d(2) = 1 gives $I_1 = 1$ (no gate needed).
$I_3$ : minterm 7 is 0; taking d(6) = 0 gives $I_3 = 0$ .
$I_6$ : minterm 12 is 0; taking d(13) = 0 gives $I_6 = 0$ .

Circuit

             +--------+
  1 -------->| I0     |
  1 -------->| I1     |
  D --[NOT]->| I2     |
  0 -------->| I3 8:1 |----> F
  1 -------->| I4 MUX |
  0 -------->| I5     |
  0 -------->| I6     |
  D -------->| I7     |
             +--------+
              A  B  C

Check: $ABCD = 0100$ (4): select 010 → $I_2 = D' = 1$ , $F = 1$ . $ABCD = 0101$ (5): $I_2 = D' = 0$ , $F = 0$ . $ABCD = 1111$ (15): $I_7 = D = 1$ . All required minterms give 1 and all other non-don't-care minterms give 0.

2082 Baisakh · 6 marks

Implement the circuit with a PLA of the following Boolean function: F1 = Σm(3,5,6,7) and F2 = Σm(0,2,4,7).

Answer

A PLA (Programmable Logic Array) has a programmable AND array that forms product terms and a programmable OR array that sums them into outputs. To use it efficiently, each function is minimized and product terms are shared where possible.

Simplification

$F_1 = \Sigma m(3,5,6,7)$ :

A \ BC	00	01	11	10
0	0	0	1	0
1	0	1	1	1

F_1 = AB + AC + BC

$F_2 = \Sigma m(0,2,4,7)$ :

A \ BC	00	01	11	10
0	1	0	0	1
1	1	0	1	0

Groups: (0, 2) gives $A'C'$ ; (0, 4) gives $B'C'$ ; 7 alone gives $ABC$ .

F_2 = A'C' + B'C' + ABC

PLA programming table

Six product terms are needed (none is common to both functions). In the input columns 1 = true variable, 0 = complemented, – = not connected; in the output columns 1 = term connected to that OR gate.

Term	Product	A	B	C	$F_1$	$F_2$
1	$AB$	1	1	–	1	–
2	$AC$	1	–	1	1	–
3	$BC$	–	1	1	1	–
4	$A'C'$	0	–	0	–	1
5	$B'C'$	–	0	0	–	1
6	$ABC$	1	1	1	–	1

Size: 3 inputs × 6 product terms × 2 outputs.

PLA diagram

 A  A' B  B' C  C'        (input buffers)
 |  |  |  |  |  |
 x--+--x--+--+--+--[AND]-- P1 = AB
 x--+--+--+--x--+--[AND]-- P2 = AC
 +--+--x--+--x--+--[AND]-- P3 = BC
 +--x--+--+--+--x--[AND]-- P4 = A'C'
 +--+--+--x--+--x--[AND]-- P5 = B'C'
 x--+--x--+--x--+--[AND]-- P6 = ABC
            OR array
 P1, P2, P3 ----------[OR]--> F1
 P4, P5, P6 ----------[OR]--> F2
 (x = programmed connection)

Check: $ABC = 110$ (6): $P_1 = 1$ , so $F_1 = 1$ ; $P_4 = P_5 = P_6 = 0$ , so $F_2 = 0$ . Both match the given minterm lists for all 8 inputs.

2081 Bhadra · 3+3 marks

Realize logic circuit for segment "b" and "d" of the seven segment display decoder.

Answer

A BCD-to-seven-segment decoder takes BCD input $ABCD$ ( $A$ = MSB) and drives segments a–g. Inputs 10–15 never occur, so they are don't-cares (X).

     a
    ---
 f | g | b
    ---
 e |   | c
    ---
     d

Segment "b"

Segment b is ON for digits 0, 1, 2, 3, 4, 7, 8, 9 (OFF for 5, 6).

b = \Sigma m(0,1,2,3,4,7,8,9) + d(10\text{–}15)

AB \ CD	00	01	11	10
00	1	1	1	1
01	1	0	1	0
11	X	X	X	X
10	1	1	X	X

Groups: $B'$ (rows 00 and 10), $C'D'$ (column 00), $CD$ (column 11).

b = B' + C'D' + CD = B' + (C \odot D)

 B ---[NOT]---------------+
 C --+                    +--[OR]--- b
 D --+--[XNOR]------------+

Segment "d"

Segment d is ON for digits 0, 2, 3, 5, 6, 8, 9 (OFF for 1, 4, 7).

d = \Sigma m(0,2,3,5,6,8,9) + d(10\text{–}15)

AB \ CD	00	01	11	10
00	1	0	1	1
01	0	1	0	1
11	X	X	X	X
10	1	1	X	X

Groups: $A$ (rows 11, 10); $B'D'$ (corners 0, 2, 8, 10); $B'C$ (2, 3, 10, 11); $CD'$ (2, 6, 10, 14); $BC'D$ (5 with 13).

d = A + B'D' + B'C + CD' + BC'D

 B',D' ---[AND]---+
 B',C  ---[AND]---+
 C,D'  ---[AND]---+--[OR 5]--- d
 B,C',D --[AND]---+
 A ---------------+

Check: digit 5 ( $0101$ ): $b = 0 + 0 + 0 = 0$ (b off) and $d = BC'D = 1$ (d on). Digit 7 ( $0111$ ): $b = CD = 1$ and every term of $d$ is 0. Both expressions were verified for digits 0–9.

2081 Baisakh · 2+5 marks

Differentiate between encoder and decoder. Design an 8 to 3 encoder with diagrams.

Answer

Encoder vs decoder

Point	Encoder	Decoder
Function	Converts one active line to a binary code	Converts a binary code to one active line
Inputs / outputs	$2^n$ inputs, $n$ outputs	$n$ inputs, $2^n$ outputs
Main gates	OR gates	AND gates
Example	8-to-3 (octal to binary)	3-to-8 (74138)
Use	Keyboards, interrupt encoding	Address decoding, display driving

8-to-3 encoder

An 8-to-3 (octal-to-binary) encoder has eight inputs $D_0$ – $D_7$ and three outputs $Y_2Y_1Y_0$ . When one input $D_k$ is 1, the output is the binary code of $k$ . Only one input is assumed active at a time.

Truth table

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$Y_2$	$Y_1$	$Y_0$
0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	1	0	0	0	1	0
0	0	0	0	1	0	0	0	0	1	1
0	0	0	1	0	0	0	0	1	0	0
0	0	1	0	0	0	0	0	1	0	1
0	1	0	0	0	0	0	0	1	1	0
1	0	0	0	0	0	0	0	1	1	1

Output equations. Each output is 1 for the inputs whose code has a 1 in that bit:

\begin{aligned} Y_2 &= D_4 + D_5 + D_6 + D_7 \\ Y_1 &= D_2 + D_3 + D_6 + D_7 \\ Y_0 &= D_1 + D_3 + D_5 + D_7 \end{aligned}

Logic diagram

 D4, D5, D6, D7 ---[OR 4]---> Y2
 D2, D3, D6, D7 ---[OR 4]---> Y1
 D1, D3, D5, D7 ---[OR 4]---> Y0
 (D0 not connected: it gives 000)

Example: $D_6 = 1$ → $Y_2 = 1$ , $Y_1 = 1$ , $Y_0 = 0$ , output $110 = 6$ .

Limitations: $D_0 = 1$ and "no input active" both give 000, and two active inputs give a wrong code (e.g. $D_3$ and $D_4$ give 111). A valid-output bit and a priority encoder (74148) remove these problems.

2081 Baisakh · 2+4 marks

Explain the applications of de-multiplexer. Subtract 011 from 010 using 2's complement method.

Answer

Applications of a demultiplexer

A demultiplexer sends one input to one of many outputs selected by the select lines. Uses:

Data distribution / serial-to-parallel conversion: serial data on one line is sent to different output lines in turn.
Time-division demultiplexing in communication: separating signals from a shared line at the receiver (e.g. telephone exchanges).
Decoder function: with data input held at 1 (or used as enable), a 1: $2^n$ DEMUX works as an $n$ -to- $2^n$ decoder for memory address decoding and chip selection.
Boolean function generation: outputs give minterms, which can be ORed to realize functions (e.g. full adder).
Control signal routing in ALUs, microprocessors and multi-display systems.

(010)₂ − (011)₂ using 2's complement

Here $010 = 2$ and $011 = 3$ ; expected result $2 - 3 = -1$ .

2's complement of the subtrahend $011$ $011$ :
- 1's complement: $100$
- add 1: $100 + 1 = 101$
Add to the minuend:

     010    (+2)
   + 101    (2's complement of 3)
   -----
     111    (no end carry)

There is no end carry, so the result is negative and is in 2's complement form. Take the 2's complement of $111$ $111$ to get its magnitude:
- 1's complement: $000$
- add 1: $001$

Answer: $(010)_2 - (011)_2 = -(001)_2 = (-1)_{10}$ . In 3-bit 2's complement form the result is stored as $111$ .

2081 Baisakh · 2+5 marks

Differentiate between de-multiplexer and decoder. Construct 4×16 line decoder using 2×4 line decoders with enable.

Answer

DEMUX vs decoder

Point	Demultiplexer	Decoder
Inputs	1 data + $n$ select lines	$n$ code inputs (+ enable)
Outputs	$2^n$	$2^n$
Job	Routes the data bit to one output	Activates the output for the input code
Output value	Equals the data input	Fixed active level (1 or 0)
Typical use	Data distribution	Address decoding, code conversion

A decoder with enable becomes a DEMUX when the enable pin is used as the data input; e.g. 74138 serves both roles.

4×16 decoder from 2×4 decoders with enable

A 4×16 decoder has inputs $A B C D$ ( $A$ = MSB) and outputs $Y_0$ – $Y_{15}$ . Use five 2×4 decoders:

Decoder 0 (control): inputs $A, B$ ; enable tied to 1 (or to an overall enable $E$ ). Its outputs $O_0$ – $O_3$ enable one of the four output decoders.
Decoders 1–4: inputs $C, D$ ; each enable comes from one output of decoder 0. Each produces four of the final outputs.

        A B                     C D
     +--------+             +--------+
 E ->|E    O0 |------------>|E DEC1  |--> Y0 .. Y3
     |     O1 |---------+   +--------+
     | DEC0   |         |   +--------+
     |     O2 |------+  +-->|E DEC2  |--> Y4 .. Y7
     |     O3 |---+  |      +--------+
     +--------+   |  |      +--------+
                  |  +----->|E DEC3  |--> Y8 .. Y11
                  |         +--------+
                  |         +--------+
                  +-------->|E DEC4  |--> Y12 .. Y15
                            +--------+
   (C, D go to all of DEC1 - DEC4)

Connections: $O_0 \to$ DEC1, $O_1 \to$ DEC2, $O_2 \to$ DEC3, $O_3 \to$ DEC4 (all enables).

AB	Enabled decoder	Outputs for CD = 00…11
00	DEC1	$Y_0$ – $Y_3$
01	DEC2	$Y_4$ – $Y_7$
10	DEC3	$Y_8$ – $Y_{11}$
11	DEC4	$Y_{12}$ – $Y_{15}$

Working

Input $ABCD = 1101$ : decoder 0 sees $AB = 11$ and enables DEC4 only; DEC4 decodes $CD = 01$ and makes its second output high, i.e. $Y_{13}$ . The disabled decoders keep all their outputs at 0, so exactly one of the 16 lines is active, giving $Y_k = m_k(A,B,C,D)$ .

2081 Baisakh · 2 marks

Write a short note on PROM.

Answer

PROM (Programmable Read-Only Memory) is a ROM that is manufactured blank and can be programmed once by the user with a PROM programmer. After programming its contents cannot be changed (one-time programmable, OTP).

Structure: a fixed AND array (decoder producing all minterms of the address lines) and a programmable OR array. Each cross-point has a fusible link (nichrome or polysilicon fuse, or a diode).
Programming: all fuses are intact at first (all bits 1). A high current pulse blows selected fuses, making those bits 0. This is permanent.
Uses: storing fixed programs, look-up tables and code converters; it can implement any combinational function in sum-of-minterms form.

Unlike EPROM or EEPROM, a PROM cannot be erased; a mistake means a new chip.

2081 Baisakh · 2 marks

Write a short note on MUX tree.

Answer

A MUX tree is a way of building a large multiplexer from several smaller multiplexers connected in levels (a tree). It is used when a single IC with enough inputs is not available.

The first level of small MUXes receives the data inputs. The lower-order select lines are applied to all of them in common.
The outputs of the first level go to the data inputs of the next level, which is driven by the higher-order select lines.
The last MUX gives the final output $Y$ .

Example: 8:1 MUX from 2:1 MUXes (needs 4 + 2 + 1 = 7 MUXes):

I0,I1 -[2:1]-+
I2,I3 -[2:1]-+-[2:1]-+
I4,I5 -[2:1]-+       +-[2:1]--> Y
I6,I7 -[2:1]-+-[2:1]-+
      ^S0       ^S1     ^S2

Similarly a 16:1 MUX can be built from five 4:1 MUXes (four in the first level using $S_1S_0$ , one in the second level using $S_3S_2$ ).

Advantages: large MUX from standard small ICs; easy to expand. Drawback: more ICs and more propagation delay (one MUX delay per level).

2080 Bhadra · 1+4 marks

What is meant by a decoder? Construct 3×8 decoder using two 2×4 decoders and additional gates if required.

Answer

A decoder is a combinational circuit that converts an $n$ -bit binary input code into one of $2^n$ unique output lines; for each input combination exactly one output is active (it generates all minterms).

3×8 decoder using two 2×4 decoders

Let the inputs be $A$ (MSB), $B$ , $C$ (LSB). Each 2×4 decoder has an enable input $E$ (active high).

$B$ and $C$ go to the inputs of both 2×4 decoders.
$A$ selects which decoder works: $A'$ (through a NOT gate) drives $E$ of decoder 1 and $A$ drives $E$ of decoder 2.
When $A = 0$ , decoder 1 is enabled and gives $D_0$ – $D_3$ ; when $A = 1$ , decoder 2 gives $D_4$ – $D_7$ .

              +---------+
B,C ---+----->| 2x4 #1  |--> D0..D3
       |   +->| E       |
       |   |  +---------+
A -+-[NOT]-+
   |   |      +---------+
   |   +----->| 2x4 #2  |--> D4..D7
   +--------->| E       |
              +---------+

A	B	C	Active output
0	0	0	$D_0$
0	0	1	$D_1$
0	1	0	$D_2$
0	1	1	$D_3$
1	0	0	$D_4$
1	0	1	$D_5$
1	1	0	$D_6$
1	1	1	$D_7$

Only one extra gate (an inverter) is needed. With an overall enable $E$ , use $E\cdot A'$ and $E\cdot A$ (two AND gates) for the two enables.

2080 Baisakh · 2+4 marks

What is a priority encoder? Find out logic expressions and draw the logic circuit of 4 to 2 priority encoder.

Answer

A priority encoder is an encoder that gives the binary code of the highest-priority active input when more than one input is active at the same time. It also has a valid output $V$ that shows whether any input is active (an ordinary encoder gives a wrong code when two inputs are high).

4-to-2 priority encoder

Inputs $D_0$ – $D_3$ , with $D_3$ the highest priority. Outputs $Y_1Y_0$ and $V$ (X = don't care).

$D_3$	$D_2$	$D_1$	$D_0$	$Y_1$	$Y_0$	$V$
0	0	0	0	X	X	0
0	0	0	1	0	0	1
0	0	1	X	0	1	1
0	1	X	X	1	0	1
1	X	X	X	1	1	1

Expressions (from K-maps of the expanded table):

$Y_1 = 1$ when $D_3 = 1$ or $D_2 = 1$ :

Y_1 = D_3 + D_2

$Y_0 = 1$ when $D_3 = 1$ , or when $D_1 = 1$ with $D_2 = 0$ (and $D_3=0$ ):

Y_0 = D_3 + D_3'D_2'D_1 = D_3 + D_2'D_1

$V$ is 1 if any input is 1:

V = D_3 + D_2 + D_1 + D_0

Logic circuit

D3 -----------+---------> [OR] --> Y1
D2 ---+-------|---------> [  ]
      |       |
      +-[NOT]-|-+
              | [AND]-+
D1 -----------|-[   ] +-> [OR] --> Y0
              +---------> [  ]

D0,D1,D2,D3 ----------> [4-in OR] --> V

So the circuit needs one NOT, one 2-input AND, two 2-input OR gates and one 4-input OR gate. Example: $D_3D_2D_1D_0 = 0110$ gives $Y_1Y_0 = 10$ because $D_2$ has higher priority than $D_1$ .

2080 Baisakh · 2+4 marks

What is a ROM? Explain it how one bit memory is stored as '1' or '0', based on BJT circuit.

Answer

ROM (Read Only Memory) is a non-volatile semiconductor memory in which data is written once (during manufacture or by programming) and afterwards can only be read. Data stays even when power is removed. It is used to store fixed programs (BIOS, firmware), look-up tables and code converters. Types: mask ROM, PROM, EPROM, EEPROM.

Storing 1 or 0 in a BJT ROM cell

A bipolar ROM is an array of row (word) lines and column (bit) lines. At each crossing there is a cell position where a BJT may or may not be connected.

The base of the transistor is connected to the row line.
The collector is connected to $V_{CC}$ .
The emitter is connected to the column line only if a 1 is to be stored. Each column line has a resistor to ground.

 Vcc        Row line (from decoder)
  |          |
  C          |
   \|--------+       (stored '1')
   /| B
  E
  |
==+===== Column line --> sense --> Data = 1
         |
        [R]
         |
        GND

 Stored '0': emitter link absent (or fuse blown),
 so column stays at 0 V through R.

Reading:

The address decoder makes the selected row line HIGH.
In a cell storing 1, the transistor's base is high, so it conducts (emitter follower). Current flows through the column resistor and the column line goes HIGH, which is read as 1.
In a cell storing 0, there is no emitter connection, so no current flows into that column; the resistor keeps it at 0 V, read as 0.
Unselected rows are LOW, so their transistors are off and do not affect the columns.

In a mask ROM the connection is made or left out by the metal mask. In a bipolar PROM every cell is made with a fusible link in the emitter; the user stores a 0 by blowing the fuse with a high current pulse, and the intact fuse keeps a 1. Since the stored pattern is fixed by a physical connection, the data is non-volatile.

2079 Bhadra · 4 marks

Realize full-adder using a single 4:1 MUX and logical gates.

Answer

A full adder adds $A$ , $B$ and $C_{in}$ and gives

S = A \oplus B \oplus C_{in}, \qquad C_{out} = AB + C_{in}(A \oplus B)

Use $A$ and $B$ as the select lines ( $S_1 = A$ , $S_0 = B$ ) of the 4:1 MUX and express each output in terms of $C_{in}$ .

Truth table grouped by A, B

A	B	$C_{in}$	S	$C_{out}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

AB	S in terms of $C_{in}$	$C_{out}$ in terms of $C_{in}$
00 ( $I_0$ )	$C_{in}$	0
01 ( $I_1$ )	$C_{in}'$	$C_{in}$
10 ( $I_2$ )	$C_{in}'$	$C_{in}$
11 ( $I_3$ )	$C_{in}$	1

Realization

Sum from the single 4:1 MUX: $I_0 = C_{in}$ , $I_1 = C_{in}'$ , $I_2 = C_{in}'$ , $I_3 = C_{in}$ (one NOT gate gives $C_{in}'$ ).
Carry from gates: $C_{out} = AB + C_{in}(A\oplus B)$ , using one XOR, two AND and one OR gate (or the simpler $C_{out} = AB + BC_{in} + AC_{in}$ ).

Cin ------+----------> I0 +-------+
          +-[NOT]--+-> I1 | 4:1   |
                   +-> I2 | MUX   |--> S
Cin -----------------> I3 |       |
                          +-------+
                          S1=A S0=B

A --+--[AND]---------------+
B --+--[   ]               +--[OR]--> Cout
A,B --[XOR]--[AND]---------+
Cin ---------[   ]

Check: $A=1, B=0, C_{in}=1$ selects $I_2 = C_{in}' = 0$ so $S = 0$ , and $C_{out} = 0 + 1\cdot1 = 1$ . This matches $1+0+1 = 10_2$ .

(If a second 4:1 MUX were allowed, $C_{out}$ would use $I_0=0, I_1=C_{in}, I_2=C_{in}, I_3=1$ .)

2079 Bhadra · 6 marks

Design the BCD to seven segment decoder. Obtain the simplest logic expressions for segments "a" and "e" also draw their circuits.

Answer

A BCD-to-seven-segment decoder takes a 4-bit BCD digit $ABCD$ ( $A$ = MSB) and drives the seven segments a–g of a display so that the decimal digit 0–9 is shown. Inputs 1010–1111 never occur, so they are don't cares. (Common-cathode display: a 1 lights the segment.)

   --a--
  |     |
  f     b
  |--g--|
  e     c
  |     |
   --d--

Truth table for segments a and e

Digit	A B C D	a	e
0	0000	1	1
1	0001	0	0
2	0010	1	1
3	0011	1	0
4	0100	0	0
5	0101	1	0
6	0110	1	1
7	0111	1	0
8	1000	1	1
9	1001	1	0

So $a = \Sigma m(0,2,3,5,6,7,8,9) + d(10\text{–}15)$ and $e = \Sigma m(0,2,6,8) + d(10\text{–}15)$ .

K-map for a

        CD=00 01  11  10
AB=00     1   0   1   1
AB=01     0   1   1   1
AB=11     X   X   X   X
AB=10     1   1   X   X

Groups: $A$ (rows 11, 10 with don't cares), $C$ (columns 11, 10), $BD$ (cells 5, 7, 13, 15), $B'D'$ (corners 0, 2, 8, 10).

a = A + C + BD + B'D'

K-map for e

        CD=00 01  11  10
AB=00     1   0   0   1
AB=01     0   0   0   1
AB=11     X   X   X   X
AB=10     1   0   X   X

Groups: $B'D'$ (corners 0, 2, 8, 10) and $CD'$ (column 10: 2, 6, 14, 10).

e = B'D' + CD' = D'(B' + C)

Circuits

a:  A --------------------+
    C --------------------+
    B --+[AND]------------+--[4-in OR]--> a
    D --+[   ]            |
    B'--+[AND]------------+
    D'--+[   ]

e:  B' --+--[OR]--+
    C  --+--[  ]  +--[AND]--> e
    D' -----------+--[   ]

$e$ needs only one OR gate, one AND gate and an inverter for $D$ ( $B'$ is shared with segment a). Check: digit 6 (0110): $a = 0+1+0+0 = 1$ , $e = D'(B'+C) = 1\cdot(0+1) = 1$ , correct.

2079 Bhadra · 2+4 marks

What is a memory device? Distinguish between PAL and PLA memory devices.

Answer

A memory device is a device that stores binary information (bits) and lets it be read back, and in some types written. Each stored word is reached by an address. Examples: ROM, PROM, EPROM, RAM. Programmable logic devices such as PROM, PAL and PLA use the same array structure (an AND array that decodes the inputs and an OR array that holds the pattern), so they are studied with memories.

PAL vs PLA

PLA (Programmable Logic Array): both the AND array and the OR array are programmable. PAL (Programmable Array Logic): the AND array is programmable but the OR array is fixed (each OR gate gets a fixed group of product terms).

Point	PAL	PLA
AND array	Programmable	Programmable
OR array	Fixed	Programmable
Sharing of product terms	Not possible; each output has its own terms	Any product term can feed any output
Flexibility	Less	More
Speed	Faster (fewer programmable links in path)	Slower
Cost and complexity	Cheaper, simpler to make	Costlier, more complex
Terms per output	Limited to a fixed number	Limited only by total AND gates
Typical use	Simple glue logic, widely used (e.g. PAL16L8)	Multi-output functions with common terms

 PAL:  inputs -> [programmable AND] -> [fixed OR] -> out
 PLA:  inputs -> [programmable AND] -> [prog. OR] -> out

Example: if $F_1 = AB + C$ and $F_2 = AB + D$ , a PLA generates $AB$ once and feeds it to both outputs; a PAL must generate $AB$ twice, once in each OR group.

2078 Bhadra · 4+3 marks

Implement the given function F = Σ(0,2,3,5,8,12,14) using only one 8:1 MUX. Add the binary numbers 1011 and 1101 by using Full adders.

Answer

Implementing F = Σ(0,2,3,5,8,12,14) with one 8:1 MUX

Take $A, B, C$ as select lines ( $S_2S_1S_0$ ) and the LSB $D$ as the data variable. Each data input $I_i$ covers minterms $2i$ ( $D = 0$ ) and $2i+1$ ( $D = 1$ ).

$I_i$	ABC	Minterms ( $D$ =0, $D$ =1)	In F?	$I_i$
$I_0$	000	0, 1	yes, no	$D'$
$I_1$	001	2, 3	yes, yes	1
$I_2$	010	4, 5	no, yes	$D$
$I_3$	011	6, 7	no, no	0
$I_4$	100	8, 9	yes, no	$D'$
$I_5$	101	10, 11	no, no	0
$I_6$	110	12, 13	yes, no	$D'$
$I_7$	111	14, 15	yes, no	$D'$

D' --> I0 +--------+
1  --> I1 |        |
D  --> I2 |  8:1   |
0  --> I3 |  MUX   |--> F
D' --> I4 |        |
0  --> I5 |        |
D' --> I6 |        |
D' --> I7 +--------+
           S2 S1 S0
           A  B  C

Only one NOT gate is needed for $D'$ .

Adding 1011 and 1101 with full adders

Use a 4-bit parallel adder: four full adders FA0–FA3, with $C_0 = 0$ and each carry going to the next stage.

 A3B3     A2B2     A1B1     A0B0
  1 1      0 1      1 0      1 1
 [FA3]<-C3[FA2]<-C2[FA1]<-C1[FA0]<-C0=0
  |  \     |        |        |
 C4  S3    S2       S1       S0

Stage	$A_i$	$B_i$	$C_i$	$S_i$	$C_{i+1}$
FA0	1	1	0	0	1
FA1	1	0	1	0	1
FA2	0	1	1	0	1
FA3	1	1	1	1	1

Answer: $1011 + 1101 = 11000_2$ (carry $C_4 = 1$ , sum $S_3S_2S_1S_0 = 1000$ ). Check: $11 + 13 = 24 = 11000_2$ .

2078 Bhadra · 6 marks

Find out the simplest logic circuit as far as possible for the 'e' segment of the seven segment display decoder.

Answer

For a BCD-to-seven-segment decoder the input is a BCD digit $ABCD$ ( $A$ = MSB). Codes 1010–1111 never occur, so they are don't cares. Segment e is the lower-left segment (common-cathode display: 1 = ON).

   --a--
  f     b
   --g--
  e     c
   --d--

Truth table for e

Segment e is ON only for digits 0, 2, 6 and 8.

Digit	A B C D	e
0	0000	1
1	0001	0
2	0010	1
3	0011	0
4	0100	0
5	0101	0
6	0110	1
7	0111	0
8	1000	1
9	1001	0
10–15	1010–1111	X

e = \Sigma m(0,2,6,8) + d(10,11,12,13,14,15)

K-map

        CD=00 01  11  10
AB=00     1   0   0   1
AB=01     0   0   0   1
AB=11     X   X   X   X
AB=10     1   0   X   X

Quad 1: the four corners $m_0, m_2, m_8, m_{10}$ give $B'D'$ .
Quad 2: column $CD = 10$ : $m_2, m_6, m_{14}, m_{10}$ give $CD'$ .

e = B'D' + CD' = D'(B' + C)

Simplest circuit

The factored form needs only one OR, one AND and two inverters:

B --[NOT]-- B' --+
                 +--[OR]--+
C ---------------+        +--[AND]--> e
D --[NOT]-- D' -----------+

Check: digit 2 (0010): $D' = 1$ , $B' + C = 1$ , so $e = 1$ ; digit 4 (0100): $B' = 0$ , $C = 0$ , so $e = 0$ . Both correct.

2078 Bhadra · 2+3 marks

Define PLA (Programmable Logic Array). Implement the full subtractor using PLA.

Answer

A PLA (Programmable Logic Array) is a programmable logic device with a programmable AND array followed by a programmable OR array. The AND array generates the needed product terms of the inputs and the OR array sums any of them for each output, so it can implement several SOP functions that share product terms.

Full subtractor using PLA

Inputs $A$ (minuend), $B$ (subtrahend), $B_{in}$ (borrow in). Outputs: difference $D$ and borrow out $B_o$ .

A	B	$B_{in}$	D	$B_o$
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

D = \Sigma m(1,2,4,7) = A'B'B_{in} + A'BB_{in}' + AB'B_{in}' + ABB_{in}

B_o = \Sigma m(1,2,3,7) = A'B_{in} + A'B + BB_{in}

$D$ (XOR) cannot be simplified, so 4 + 3 = 7 product terms are needed.

PLA programming table (1 = true input, 0 = complemented, – = not used):

Term	Product	A	B	$B_{in}$	D	$B_o$
1	$A'B'B_{in}$	0	0	1	1	–
2	$A'BB_{in}'$	0	1	0	1	–
3	$AB'B_{in}'$	1	0	0	1	–
4	$ABB_{in}$	1	1	1	1	–
5	$A'B_{in}$	0	–	1	–	1
6	$A'B$	0	1	–	–	1
7	$BB_{in}$	–	1	1	–	1

A  B  Bin (true and complement lines)
|  |  |
[ AND array: P1 ... P7 ]   (programmed)
   |
[ OR array ]
   OR1 = P1+P2+P3+P4  ---> D
   OR2 = P5+P6+P7     ---> Bo

So a 3-input, 7-product-term, 2-output PLA implements the full subtractor.

2078 Kartik · 4 marks

Implement the given function F = Σ(0,1,3,6,10,12,14) using 8×1 MUX only.

Answer

Use $A, B, C$ as the select lines ( $S_2 S_1 S_0$ ) and the LSB $D$ as the data variable. Data input $I_i$ covers minterm $2i$ (when $D=0$ ) and $2i+1$ (when $D=1$ ).

Implementation table (F = Σ(0,1,3,6,10,12,14)):

	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
$D'$ row	0	2	4	6	8	10	12	14
$D$ row	1	3	5	7	9	11	13	15
Input	1	$D$	0	$D'$	0	$D'$	$D'$	$D'$

(Bold = minterm present in F.)

Rules: both entries present gives 1, none gives 0, only the $D'$ row gives $D'$ , only the $D$ row gives $D$ .

1  --> I0 +--------+
D  --> I1 |        |
0  --> I2 |  8x1   |
D' --> I3 |  MUX   |--> F
0  --> I4 |        |
D' --> I5 |        |
D' --> I6 |        |
D' --> I7 +--------+
           S2 S1 S0
           A  B  C

Inputs 1 and 0 are tied to $V_{CC}$ and ground; one inverter gives $D'$ .

Check: $ABCD = 1100$ (minterm 12) selects $I_6 = D' = 1$ , so $F = 1$ ; $ABCD = 0101$ (minterm 5) selects $I_2 = 0$ , so $F = 0$ . Both agree with the given function.

2078 Kartik · 2+2×2 marks

Differentiate between PROM and PLA. Implement the following boolean functions using PAL. a) A(x,y,z) = Σ(2,4,5,7) b) B(x,y,z) = Σ(0,2,6)

Answer

PROM vs PLA

Point	PROM	PLA
AND array	Fixed (full decoder, all $2^n$ minterms)	Programmable
OR array	Programmable	Programmable
Functions in form	Sum of minterms (no simplification)	Simplified SOP, shared terms
Size for many inputs	Grows as $2^n$ , wasteful	Only needed product terms
Typical use	Look-up tables, code converters	Multi-output logic with common terms

Functions using PAL

In a PAL the AND array is programmable and the OR array is fixed, so each function is first simplified to SOP.

a) $A(x,y,z) = \Sigma(2,4,5,7)$

       yz=00 01 11 10
x=0      0   0  0  1
x=1      1   1  1  0

$m_4, m_5$ give $xy'$ ; $m_5, m_7$ give $xz$ ; $m_2$ alone gives $x'yz'$ .

A = xy' + xz + x'yz'

b) $B(x,y,z) = \Sigma(0,2,6)$

       yz=00 01 11 10
x=0      1   0  0  1
x=1      0   0  0  1

$m_0, m_2$ give $x'z'$ ; $m_2, m_6$ give $yz'$ .

B = x'z' + yz'

PAL programming table (each OR gate has 3 AND inputs; 1 = true, 0 = complement, – = not connected):

Product term	x	y	z	Output
1: $xy'$	1	0	–	A
2: $xz$	1	–	1	A
3: $x'yz'$	0	1	0	A
4: $x'z'$	0	–	0	B
5: $yz'$	–	1	0	B
6: (unused)	–	–	–	B

x y z --[prog. AND]-- P1,P2,P3 --[fixed OR]--> A
               \----- P4,P5,P6 --[fixed OR]--> B

The unused term 6 has all its fuses intact (both $x$ and $x'$ connected) so it gives 0 and does not affect B.

2076 Chaitra · 4 marks

Implement 1:16 demultiplexer using 1:2 demultiplexer.

Answer

A 1:16 demultiplexer sends one data input $D$ to one of 16 outputs chosen by 4 select lines $S_3S_2S_1S_0$ . With 1:2 demultiplexers (one select line each) we build a tree of four levels.

Number of 1:2 DEMUXes: $1 + 2 + 4 + 8 = 15$ .

Level	DEMUXes	Select line	Outputs
1	1	$S_3$ (MSB)	2
2	2	$S_2$	4
3	4	$S_1$	8
4	8	$S_0$ (LSB)	16 ( $Y_0$ – $Y_{15}$ )

                         +-[1:2]-Y0,Y1
                +-[1:2]--+
                |        +-[1:2]-Y2,Y3
       +-[1:2]--+
       |        |        +-[1:2]-Y4,Y5
       |        +-[1:2]--+
       |                 +-[1:2]-Y6,Y7
D-[1:2]+
       |                 +-[1:2]-Y8,Y9
       |        +-[1:2]--+
       |        |        +-[1:2]-Y10,Y11
       +-[1:2]--+
                |        +-[1:2]-Y12,Y13
                +-[1:2]--+
                         +-[1:2]-Y14,Y15
   S3      S2       S1       S0

Working:

The first DEMUX sends $D$ to its upper output if $S_3 = 0$ (towards $Y_0$ – $Y_7$ ) or lower output if $S_3 = 1$ (towards $Y_8$ – $Y_{15}$ ).
Each level halves the group again using $S_2$ , then $S_1$ , then $S_0$ .
All DEMUXes at one level share the same select line.

Example: $S_3S_2S_1S_0 = 1011$ : level 1 goes to the lower half (8–15), level 2 ( $S_2=0$ ) to 8–11, level 3 ( $S_1=1$ ) to 10–11, level 4 ( $S_0=1$ ) to $Y_{11}$ . So $Y_{11} = D$ and all other outputs are 0.

2076 Chaitra · 2+4 marks

Differentiate between RAM and ROM. Implement F1 = Σ(1,2,4,6) and F2 = Σm(0,2,3) using PROM.

Answer

RAM vs ROM

Point	RAM	ROM
Full form	Random Access Memory	Read Only Memory
Operation	Read and write	Read only (written once/rarely)
Volatility	Volatile: data lost on power off	Non-volatile
Use	Temporary data and running programs	Fixed programs (BIOS, firmware), tables
Types	SRAM, DRAM	Mask ROM, PROM, EPROM, EEPROM
Speed	Fast read and write	Fast read; writing slow or impossible

F1 = Σ(1,2,4,6) and F2 = Σ(0,2,3) using PROM

Three inputs ( $A$ , $B$ , $C$ ) and two outputs, so an 8 × 2 PROM is used: a fixed 3-to-8 decoder (AND array) produces all minterms $m_0$ – $m_7$ , and the programmable OR array connects the needed minterms to each output.

PROM truth table (contents):

Address $ABC$	Minterm	$F_1$	$F_2$
000	$m_0$	0	1
001	$m_1$	1	0
010	$m_2$	1	1
011	$m_3$	0	1
100	$m_4$	1	0
101	$m_5$	0	0
110	$m_6$	1	0
111	$m_7$	0	0

A 1 means the fuse/link between that minterm line and the OR gate is kept; a 0 means it is blown.

A B C
| | |
[3-to-8 decoder] (fixed AND array)
 m0 m1 m2 m3 m4 m5 m6 m7
 |  x  x  |  x  |  x  |   --> OR1 --> F1
 x  |  x  x  |  |  |  |   --> OR2 --> F2
 (x = intact link)

$F_1 = m_1 + m_2 + m_4 + m_6$
$F_2 = m_0 + m_2 + m_3$

No simplification is needed with a PROM, because the decoder already gives every minterm.

2076 Asoj

Define encoder. Design 4×16 Decoder using 2×4 Decoder only.

Answer

An encoder is a combinational circuit that does the reverse of a decoder: it has $2^n$ (or fewer) input lines and $n$ output lines, and gives the binary code of the input line that is active. Example: an 8-to-3 (octal-to-binary) encoder gives $Y_2Y_1Y_0 = 101$ when input $D_5$ is high.

4×16 decoder using only 2×4 decoders

Inputs $A$ (MSB), $B$ , $C$ , $D$ (LSB). Each 2×4 decoder has an enable input $E$ . Five 2×4 decoders are needed, in two levels.

First level (1 decoder): inputs $A$ , $B$ . Its four outputs act as enables, selecting one of the second-level decoders.
Second level (4 decoders): inputs $C$ , $D$ in common. Only the enabled one gives an active output.

                       +-------+
            C,D ------>| 2x4 #1|--> Y0..Y3
                  +--->| E     |
                  |    +-------+
  +--------+  O0--+    +-------+
A-|  2x4   |  O1------>| 2x4 #2|--> Y4..Y7
B-|  (#0)  |  O2--+    +-------+
E-|        |  O3-+|    +-------+
  +--------+     |+--->| 2x4 #3|--> Y8..Y11
                 |     +-------+
                 |     +-------+
                 +---->| 2x4 #4|--> Y12..Y15
                       +-------+
 (C,D go to all four second-level decoders)

AB	Enabled decoder	Outputs active (by CD)
00	#1	$Y_0$ – $Y_3$
01	#2	$Y_4$ – $Y_7$
10	#3	$Y_8$ – $Y_{11}$
11	#4	$Y_{12}$ – $Y_{15}$

Example: $ABCD = 1101$ : decoder #0 makes O3 high, enabling #4; $CD = 01$ makes its second output high, so $Y_{13} = 1$ (since $1101_2 = 13$ ).

2076 Asoj

Write a short note on PLA.

Answer

A PLA (Programmable Logic Array) is a programmable logic device made of a programmable AND array followed by a programmable OR array. It implements several Boolean functions in sum-of-products (SOP) form.

Structure (n inputs, k product terms, m outputs):

inputs --[buffers: true and complement]
            |
   [ programmable AND array ] -> P1 ... Pk
            |
   [ programmable OR array ]  -> F1 ... Fm
            |
   [ XOR / inverter (optional) ] -> outputs

Each input is given in true and complemented form.
Each AND gate forms one product term by connecting chosen literals.
Each OR gate adds any chosen product terms. A product term can be shared by several outputs.
Size is given as $n \times k \times m$ , e.g. a 3 × 4 × 2 PLA.

Design steps:

Simplify each function to minimum SOP (try both $F$ and $F'$ to reduce product terms).
Find the common product terms.
Write the PLA programming table (inputs used, output connections, true/complement).

Example: $F_1 = AB' + AC$ , $F_2 = AC + BC$ need only three product terms ( $AB'$ , $AC$ , $BC$ ) since $AC$ is shared.

Advantages: both arrays programmable, so very flexible; shares product terms; uses fewer terms than a PROM for functions with many inputs.

Disadvantages: two programmable arrays make it slower and costlier than a PAL; harder to manufacture.

2075 Chaitra · 5 marks

Implement the following function using 8×1 MUX. F(A,B,C,D) = Σ(0,2,3,6,7,8,12,13,15)

Answer

Use $A, B, C$ as select lines ( $S_2S_1S_0$ ) and $D$ (LSB) as the data variable. Input $I_i$ corresponds to minterms $2i$ (with $D=0$ ) and $2i+1$ (with $D=1$ ).

Implementation table for $F = \Sigma(0,2,3,6,7,8,12,13,15)$ (bold = minterm in F):

	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
$D'$ row	0	2	4	6	8	10	12	14
$D$ row	1	3	5	7	9	11	13	15
Input	$D'$	1	0	1	$D'$	0	1	$D$

Rule: both circled gives 1, none gives 0, only the upper ( $D'$ ) row gives $D'$ , only the lower ( $D$ ) row gives $D$ .

Circuit:

D' --> I0 +--------+
1  --> I1 |        |
0  --> I2 |  8x1   |
1  --> I3 |  MUX   |--> F
D' --> I4 |        |
0  --> I5 |        |
1  --> I6 |        |
D  --> I7 +--------+
           S2 S1 S0
           A  B  C

Logic 1 is tied to $V_{CC}$ , logic 0 to ground, and a NOT gate gives $D'$ .

Verification:

ABCD	Minterm	Selected input	F
0000	0	$I_0 = D' = 1$	1
0001	1	$I_0 = D' = 0$	0
1101	13	$I_6 = 1$	1
1110	14	$I_7 = D = 0$	0
1111	15	$I_7 = D = 1$	1

All agree with the given minterm list, so the function is realised with one 8×1 MUX and one inverter.

2075 Chaitra · 1+4 marks

What is ROM? Implement given functions F1(A,B,C) = Σ(2,3,5,6) and F2(A,B,C) = Σ(0,1,5) using ROM.

Answer

ROM (Read Only Memory) is a non-volatile memory whose contents are fixed once programmed and can only be read in normal operation. As a logic device it is a fixed AND array (decoder) that generates all minterms of the address inputs, followed by a programmable OR array.

F1 = Σ(2,3,5,6), F2 = Σ(0,1,5) using ROM

Three inputs and two outputs, so an 8 × 2 ROM (3-to-8 decoder + 2 OR gates).

Address $ABC$	Minterm	$F_1$	$F_2$
000	$m_0$	0	1
001	$m_1$	0	1
010	$m_2$	1	0
011	$m_3$	1	0
100	$m_4$	0	0
101	$m_5$	1	1
110	$m_6$	1	0
111	$m_7$	0	0

F_1 = m_2 + m_3 + m_5 + m_6, \qquad F_2 = m_0 + m_1 + m_5

 A B C
 | | |
[3-to-8 decoder]
 m0 m1 m2 m3 m4 m5 m6 m7
  .  .  x  x  .  x  x  .  --> OR1 --> F1
  x  x  .  .  .  x  .  .  --> OR2 --> F2
 (x = connection kept, . = removed)

When an address is applied, the decoder makes one minterm line high; each output is 1 if that line is connected to its OR gate. Example: $ABC = 101$ activates $m_5$ , which is connected to both OR gates, so $F_1 = F_2 = 1$ .

$A_1A_0$	$B_1B_0$	$A>B$	$A=B$	$A<B$
0 0	0 0	0	1	0
0 0	0 1	0	0	1
0 0	1 0	0	0	1
0 0	1 1	0	0	1
0 1	0 0	1	0	0
0 1	0 1	0	1	0
0 1	1 0	0	0	1
0 1	1 1	0	0	1
1 0	0 0	1	0	0
1 0	0 1	1	0	0
1 0	1 0	0	1	0
1 0	1 1	0	0	1
1 1	0 0	1	0	0
1 1	0 1	1	0	0
1 1	1 0	1	0	0
1 1	1 1	0	1	0

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$A_2$	$A_1$	$A_0$	V
0	0	0	0	0	0	0	0	X	X	X	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

$D_0$	$D_1$	$D_2$	$D_3$	$D_4$	$D_5$	$D_6$	$D_7$	$A_2$	$A_1$	$A_0$
1	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0	0	1	1
0	0	0	0	1	0	0	0	1	0	0
0	0	0	0	0	1	0	0	1	0	1
0	0	0	0	0	0	1	0	1	1	0
0	0	0	0	0	0	0	1	1	1	1

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$Y_2$	$Y_1$	$Y_0$	V
0	0	0	0	0	0	0	0	X	X	X	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$Y_2$	$Y_1$	$Y_0$
0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	1	0	0	0	1	0
0	0	0	0	1	0	0	0	0	1	1
0	0	0	1	0	0	0	0	1	0	0
0	0	1	0	0	0	0	0	1	0	1
0	1	0	0	0	0	0	0	1	1	0
1	0	0	0	0	0	0	0	1	1	1

$A_1A_0$	$B_1B_0$	$A>B$	$A=B$	$A<B$
0 0	0 0	0	1	0
0 0	0 1	0	0	1
0 0	1 0	0	0	1
0 0	1 1	0	0	1
0 1	0 0	1	0	0
0 1	0 1	0	1	0
0 1	1 0	0	0	1
0 1	1 1	0	0	1
1 0	0 0	1	0	0
1 0	0 1	1	0	0
1 0	1 0	0	1	0
1 0	1 1	0	0	1
1 1	0 0	1	0	0
1 1	0 1	1	0	0
1 1	1 0	1	0	0
1 1	1 1	0	1	0

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$A_2$	$A_1$	$A_0$	V
0	0	0	0	0	0	0	0	X	X	X	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

$D_0$	$D_1$	$D_2$	$D_3$	$D_4$	$D_5$	$D_6$	$D_7$	$A_2$	$A_1$	$A_0$
1	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0	0	1	1
0	0	0	0	1	0	0	0	1	0	0
0	0	0	0	0	1	0	0	1	0	1
0	0	0	0	0	0	1	0	1	1	0
0	0	0	0	0	0	0	1	1	1	1

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$Y_2$	$Y_1$	$Y_0$	V
0	0	0	0	0	0	0	0	X	X	X	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$Y_2$	$Y_1$	$Y_0$
0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	1	0	0	0	1	0
0	0	0	0	1	0	0	0	0	1	1
0	0	0	1	0	0	0	0	1	0	0
0	0	1	0	0	0	0	0	1	0	1
0	1	0	0	0	0	0	0	1	1	0
1	0	0	0	0	0	0	0	1	1	1

Past questions and answers

1.Explain the operation of two bit magnitude comparator with truth table and circuit diagram.

Operation

Truth table

Output expressions

Circuit diagram

2.Design 5×32 line decoder using 3×8 line decoders and necessary logic gates.

Design idea

Circuit

Operation

3.Realize a full-subtractor logic circuit using a single 1:4 demultiplexer and necessary logic gates.

Truth table

Using a 1:4 DEMUX as a 2-to-4 decoder

Circuit

4.Realize Full Adder Circuit using a 2×4 decoder and using logic gates.

Truth table

Realization with logic gates

Realization with a 2×4 decoder

5.What is a priority encoder? Design an octal priority encoder.

Octal (8-to-3) priority encoder

Output equations

Logic diagram

6.Design a simplest logic circuit for 'b' segment of the BCD-to-7 segment display decoder.

Truth table for segment b

K-map

Simplest logic circuit

7.Explain the operation of 3 bit magnitude comparator with truth table and draw the circuit.

Operation

Truth table (condensed)

Output expressions

Circuit

8.What is an encoder? Explain 8 to 3 line encoder with circuit diagram and truth table.

8-to-3 line (octal-to-binary) encoder

Output expressions

Circuit diagram

9.Realize a full-adder circuit using a single 1:4 demultiplexer and necessary logic gates.

Truth table of the full adder

Expressing S and CoutC_{out}Cout​ in terms of the DEMUX outputs

Circuit

10.Compare a demultiplexer with the decoder. What is a seven-segment decoder? Find out the simplest logic expression for "b" segment of the BCD to 7-segment display decoder and realize the circuit.

DEMUX vs decoder

Seven-segment decoder

Simplest expression for segment "b"

Circuit

11.What is a multiplexer tree? Construct a 1:16 demultiplexer using only 1:4 demultiplexers and logic gates if necessary.

Multiplexer tree

1:16 DEMUX from 1:4 DEMUXes

12.What is a priority encoder? Find out the simplest logic circuit for "e" and "f" segments of the BCD-to-seven segment display decoder.

Priority encoder

Segment "e"

Segment "f"

13.Realize the following logic function using a single 1:8 demultiplexer and necessary logic gates. Y(A,B,C,D) = Σm(0,2,3,5,7,8,10,13,15)

Choice of select lines

Circuit

14.Design the full-subtractor circuit using decoder and required logic gates. What is a combinational logic circuit?

Full subtractor using a decoder

Combinational logic circuit

15.Draw the simplest logic circuit for "a" segment of the BCD-to-seven segment display decoder and realize the simplest logic expression using only NOR gates.

Simplest SOP and its circuit

Realization using only NOR gates

16.Design the logic circuit for 4:2 Priority Encoder.

Truth table (X = don't care)

K-maps (rows D3D2D_3D_2D3​D2​, columns D1D0D_1D_0D1​D0​)

Logic circuit

17.Design 8:1 Multiplexer using 4:1 Multiplexer and 2:1 Multiplexer.

Design

Function table

Working

18.Implement the following Boolean function using a single 8:1 multiplexer. F(A,B,C,D) = Σm(2,4,5,7,10,14).

Implementation table

Circuit

19.Realize full adder circuit using decoder and gates. Subtract (43)₁₀ from (57)₁₀ using 2's complement method.

Full adder using a decoder and gates

(57)₁₀ − (43)₁₀ by 2's complement

20.Realize a following logic expression using a 4:1 multiplexer and standard logic gates. Y(A,B,C) = ΠM(0,2,6,7)

Implementation table

Circuit

Check

21.Design a circuit that compares two 2-bit numbers, A and B, to check if they are equal. The circuit has one output x, so that x = 1 if A = B and x = 0 if A≠B.

Truth table (16 rows; x = 1 only when A = B)

Explain the operation of two bit magnitude comparator with truth table and circuit diagram.

Design 5×32 line decoder using 3×8 line decoders and necessary logic gates.

Realize a full-subtractor logic circuit using a single 1:4 demultiplexer and necessary logic gates.

Realize Full Adder Circuit using a 2×4 decoder and using logic gates.

What is a priority encoder? Design an octal priority encoder.

Design a simplest logic circuit for 'b' segment of the BCD-to-7 segment display decoder.

Explain the operation of 3 bit magnitude comparator with truth table and draw the circuit.

What is an encoder? Explain 8 to 3 line encoder with circuit diagram and truth table.

Realize a full-adder circuit using a single 1:4 demultiplexer and necessary logic gates.

Expressing S and $C_{out}$ in terms of the DEMUX outputs

Compare a demultiplexer with the decoder. What is a seven-segment decoder? Find out the simplest logic expression for "b" segment of the BCD to 7-segment display decoder and realize the circuit.

What is a multiplexer tree? Construct a 1:16 demultiplexer using only 1:4 demultiplexers and logic gates if necessary.

What is a priority encoder? Find out the simplest logic circuit for "e" and "f" segments of the BCD-to-seven segment display decoder.

Realize the following logic function using a single 1:8 demultiplexer and necessary logic gates. Y(A,B,C,D) = Σm(0,2,3,5,7,8,10,13,15)

Design the full-subtractor circuit using decoder and required logic gates. What is a combinational logic circuit?

Draw the simplest logic circuit for "a" segment of the BCD-to-seven segment display decoder and realize the simplest logic expression using only NOR gates.

Design the logic circuit for 4:2 Priority Encoder.

K-maps (rows $D_3D_2$ , columns $D_1D_0$ )

Design 8:1 Multiplexer using 4:1 Multiplexer and 2:1 Multiplexer.

Implement the following Boolean function using a single 8:1 multiplexer. F(A,B,C,D) = Σm(2,4,5,7,10,14).

Realize full adder circuit using decoder and gates. Subtract (43)₁₀ from (57)₁₀ using 2's complement method.

Realize a following logic expression using a 4:1 multiplexer and standard logic gates. Y(A,B,C) = ΠM(0,2,6,7)

Design a circuit that compares two 2-bit numbers, A and B, to check if they are equal. The circuit has one output x, so that x = 1 if A = B and x = 0 if A≠B.

Describe the importance of parity bits in communication system. Explain 3 bits even parity generator circuit clearly.

Explain the operation of 8:1 multiplexer with necessary diagrams. Construct 32:1 MUX using only 8:1 MUXs.

What is a decoder? Realize a 2-to-4 line decoder as a full adder circuit.

Realize the logic circuit of 1×16 DMUX using 1×4 DMUX and gates if necessary.

Design the operation of octal priority encoder with neat diagram.

Explain the operation of octal to binary encoder with necessary diagrams. Convert A+B'C in to canonical form.

Canonical form of $A + B'C$

Describe the importance of parity bits in communication system. Explain 3 bits odd parity generator circuit clearly.

Realize the circuit diagram for BCD decoder. Explain 1's and 2's complements with examples?

What is the role of hazards in asynchronous circuit design? Explain two bit magnitude comparator with necessary diagrams.

Design the 32:1 Multiplexer using 4:1 multiplexers tree concept and implement the function F = Σ(0,1,3,8,9,13) using suitable Multiplexer.

Implementing $F = \Sigma m(0,1,3,8,9,13)$

What is a multiplexer tree? Design the 16 to 1 multiplexer using 4 to 1 multiplexer.

Write a short note on ROM.

Write a short note on DE-MUX tree.

Implement a full adder circuit using 4:1 Multiplexers.

Design 1:32 demultiplexer tree using 1:8 DEMUXs and 1:2 DEMUXs only.

Differentiate between combinational and sequential circuits. Explain BCD-to-Decimal decoder circuit with suitable diagram.

How do you design 32:1 Mux by using multiplexer tree? Implement logic function Y = Σm(0,1,3,8,9,13,15) by using suitable multiplexer.

Implementing $Y = \Sigma m(0,1,3,8,9,13,15)$

Realize the logic circuit of the following using 8:1 MUX. F(W,X,Y,Z) = Σm(1,2,5,7,8,10,12,13,15)

Design a 32 to 1 multiplexer using 16 to 1 and 2 to 1 multiplexers.

Design a 3-bit even parity generator and 4-bit even parity checker circuit.

Implement 16:1 multiplexer using only 8:1 multiplexers.

Realize a full-subtractor circuit using a single 2×4 decoder and necessary logic gates.

Differentiate between RAM and ROM. How does an EEPROM cell work?

$A_1A_0$	$B_1B_0$	$A>B$	$A=B$	$A<B$
0 0	0 0	0	1	0
0 0	0 1	0	0	1
0 0	1 0	0	0	1
0 0	1 1	0	0	1
0 1	0 0	1	0	0
0 1	0 1	0	1	0
0 1	1 0	0	0	1
0 1	1 1	0	0	1
1 0	0 0	1	0	0
1 0	0 1	1	0	0
1 0	1 0	0	1	0
1 0	1 1	0	0	1
1 1	0 0	1	0	0
1 1	0 1	1	0	0
1 1	1 0	1	0	0
1 1	1 1	0	1	0

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$A_2$	$A_1$	$A_0$	V
0	0	0	0	0	0	0	0	X	X	X	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

$D_0$	$D_1$	$D_2$	$D_3$	$D_4$	$D_5$	$D_6$	$D_7$	$A_2$	$A_1$	$A_0$
1	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0	0	1	1
0	0	0	0	1	0	0	0	1	0	0
0	0	0	0	0	1	0	0	1	0	1
0	0	0	0	0	0	1	0	1	1	0
0	0	0	0	0	0	0	1	1	1	1

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$Y_2$	$Y_1$	$Y_0$	V
0	0	0	0	0	0	0	0	X	X	X	0
0	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	1	X	0	0	1	1
0	0	0	0	0	1	X	X	0	1	0	1
0	0	0	0	1	X	X	X	0	1	1	1
0	0	0	1	X	X	X	X	1	0	0	1
0	0	1	X	X	X	X	X	1	0	1	1
0	1	X	X	X	X	X	X	1	1	0	1
1	X	X	X	X	X	X	X	1	1	1	1

$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$Y_2$	$Y_1$	$Y_0$
0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	1	0	0	0	1	0
0	0	0	0	1	0	0	0	0	1	1
0	0	0	1	0	0	0	0	1	0	0
0	0	1	0	0	0	0	0	1	0	1
0	1	0	0	0	0	0	0	1	1	0
1	0	0	0	0	0	0	0	1	1	1