BE Computer Engineering (Pokhara University) Digital Logic (PU, ELX 110) Question Paper 2078 Nepal

(a) Number system conversions

(i) $(189.625)_{10}$ to binary, octal and hexadecimal

Integer part (189) to binary — repeated division by 2:

Reading remainders bottom-to-top: $(189)_{10} = (10111101)_2$.

Fractional part (0.625) — repeated multiplication by 2:

$0.625\times2 = 1.25 \Rightarrow 1$; $0.25\times2 = 0.5 \Rightarrow 0$; $0.5\times2 = 1.0 \Rightarrow 1$.

So $(0.625)_{10} = (0.101)_2$.

$$\boxed{(189.625)_{10} = (10111101.101)_2}$$

Binary to octal — group in 3s from the binary point: $\underbrace{010}_{2}\,\underbrace{111}_{7}\,\underbrace{101}_{5}\,.\,\underbrace{101}_{5} = (275.5)_8$.

Binary to hexadecimal — group in 4s from the binary point: $\underbrace{1011}_{B}\,\underbrace{1101}_{D}\,.\,\underbrace{1010}_{A} = (BD.A)_{16}$.

$$\boxed{(189.625)_{10} = (275.5)_8 = (BD.A)_{16}}$$

(ii) $(2AF.C)_{16}$ to decimal

Using positional weights ($A=10,\,F=15,\,C=12$):

$$2\times16^2 + 10\times16^1 + 15\times16^0 + 12\times16^{-1}$$ $$= 512 + 160 + 15 + 0.75 = \boxed{(687.75)_{10}}$$

(b) $(45)_{10}-(78)_{10}$ in 8-bit 2's complement

$+45 = (00101101)_2$.

$+78 = (01001110)_2$. Its 2's complement (i.e. $-78$):

• 1's complement: $10110001$
• add 1: $10110010 = -78$.

Add $45 + (-78)$:

  00101101   (+45)
+ 10110010   (-78)
-----------
  11011111

Result $= (11011111)_2$. The MSB is 1, so the result is negative. Its magnitude = 2's complement of $11011111$:

• 1's complement $00100000$, add 1 $\Rightarrow 00100001 = 33$.

Hence the result is $-33$, which matches $45-78 = -33$. Verified.

(c) Weighted vs non-weighted codes; BCD and Excess-3 of $(947)_{10}$

Weighted code: each bit position carries a fixed numeric weight, and the digit value is the weighted sum of bits (e.g. BCD/8421, 2421, 84-2-1). Non-weighted code: positions have no fixed weights, so the digit cannot be obtained by a weighted sum (e.g. Excess-3, Gray code). Non-weighted codes are used for special properties such as error detection or self-complementing arithmetic.

BCD (8421) — encode each decimal digit in 4 bits: $9 = 1001,\;4 = 0100,\;7 = 0111$

$$\boxed{(947)_{10} = (1001\;0100\;0111)_{BCD}}$$

Excess-3 — add 3 to each digit, then encode in 4 bits: $9+3=12=1100,\;4+3=7=0111,\;7+3=10=1010$

$$\boxed{(947)_{10} = (1100\;0111\;1010)_{XS3}}$$

(a) K-map simplification — minimal SOP

$$F(A,B,C,D)=\sum m(0,1,2,5,8,9,10,12,13,14)$$

Four-variable K-map (rows $AB$, columns $CD$ in Gray order $00,01,11,10$):

Prime implicants (PIs):

• $B'C'$ = {0,1,8,9}
• $B'D'$ = {0,2,8,10}
• $AC'$ = {8,9,12,13}
• $AD'$ = {8,10,12,14}
• $C'D$ = {1,5,9,13}

Essential prime implicants (EPIs):

• $B'D'$ — only PI covering m2
• $C'D$ — only PI covering m5
• $AD'$ — only PI covering m14

These three EPIs together cover all ten minterms $\{0,1,2,5,8,9,10,12,13,14\}$, so no other PI is needed.

$$\boxed{F = B'D' + C'D + AD'}$$

(b) Minimal POS

Group the 0s (maxterms $M_3,M_4,M_6,M_7,M_{11},M_{15}$):

• $\{3,7,11,15\}$ (C=1, D=1) $\Rightarrow$ sum term $(C'+D')$ — essential
• $\{4,6\}$ (A=0,B=1,D=0) $\Rightarrow$ sum term $(A+B'+D)$ — essential (covers m4)

Together they cover all zeros, giving

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

(c) NAND-only realization of the SOP

The two-level SOP $F = B'D' + C'D + AD'$ is converted to NAND-NAND by replacing every AND and the final OR with NAND gates (double inversion leaves the function unchanged):

$$F = \overline{\overline{(B'D')}\cdot\overline{(C'D)}\cdot\overline{(AD')}}$$

Logic diagram (described):

• Generate complements $B',C',D',A'$ using NAND gates as inverters (tie both inputs of a NAND together).
• First level: three 2-input NAND gates produce $\overline{B'D'}$, $\overline{C'D}$, $\overline{AD'}$.
• Second level: a 3-input NAND combines these three outputs to give $F$.

Thus $F$ is realized with a NAND-NAND (two-level) network plus inverters, all NAND gates.

Synchronous Mod-6 counter ($0\to1\to2\to3\to4\to5\to0$) with JK flip-flops

Three flip-flops are needed ($2^3=8\ge6$). Let outputs be $Q_2Q_1Q_0$ (MSB $Q_2$). States 6 and 7 are unused (treated as don't-cares).

(a) State diagram and next-state table

State diagram (described): a single directed ring $000\to001\to010\to011\to100\to101\to000$, each transition on a clock edge.

(b) Excitation table and input equations

JK excitation rules: $0\to0:J=0,K=d$; $0\to1:J=1,K=d$; $1\to0:J=d,K=1$; $1\to1:J=d,K=0$.

Using K-maps over $Q_2Q_1Q_0$ (states 6,7 as don't-cares):

$$J_0 = 1,\qquad K_0 = 1$$ $$J_1 = Q_0,\qquad K_1 = Q_0$$ $$J_2 = Q_1Q_0,\qquad K_2 = 1$$

Check of $K_2$: $Q_2=1$ occurs only at 100 and 101; from 101 the counter must go to 000 so $Q_2$ resets ($K_2=1$), and from 100 it stays ($K_2$ is don't-care), so $K_2=1$ is valid. $J_2=Q_1Q_0$ is 1 only at state 011 (the 3$\to$4 transition), correct.

(c) Logic circuit and unused-state handling

Circuit (described):

• $FF_0$: $J_0=K_0=1$ (toggles every clock).
• $FF_1$: $J_1=K_1=Q_0$ (toggles when $Q_0=1$).
• $FF_2$: $J_2=Q_1\cdot Q_0$ (one AND gate), $K_2=1$.
• All three flip-flops share a common clock (synchronous).

Unused states 110 and 111: Because they were entered as don't-cares, their behaviour follows the derived equations. Evaluating:

• From 110: $J_0K_0=11\Rightarrow Q_0:0\to1$; $J_1K_1=Q_0=0\Rightarrow Q_1$ holds at 1; $J_2=Q_1Q_0=0,K_2=1\Rightarrow Q_2:1\to0$. Next = 011 (a valid state).
• From 111: $Q_0:1\to0$; $J_1K_1=1\Rightarrow Q_1:1\to0$; $J_2=1,K_2=1\Rightarrow Q_2:1\to0$. Next = 000 (a valid state).

Both unused states return to valid states within one clock, so the counter is self-correcting and cannot lock up.

(a) Full adder design

Inputs $A,B,C_{in}$; outputs $S$ (sum) and $C_{out}$ (carry).

$S=\sum m(1,2,4,7)$, $C_{out}=\sum m(3,5,6,7)$. Simplifying:

$$S = A\oplus B\oplus C_{in}$$ $$C_{out} = AB + BC_{in} + AC_{in}$$

Logic diagram (described): Two XOR gates in cascade produce $S$ ($A\oplus B$, then $\oplus C_{in}$). $C_{out}$ uses three 2-input AND gates ($AB$, $BC_{in}$, $AC_{in}$) feeding a 3-input OR gate. (Equivalently two half-adders + one OR.)

(b) SUM using an 8-to-1 multiplexer

Use $A,B,C_{in}$ as the three select lines ($S_2S_1S_0$). The data input $I_n$ for line $n$ equals the SUM value of that minterm:

$$I_0=0,\;I_1=1,\;I_2=1,\;I_3=0,\;I_4=1,\;I_5=0,\;I_6=0,\;I_7=1$$

So connect $I_1,I_2,I_4,I_7$ to logic 1 and $I_0,I_3,I_5,I_6$ to logic 0; the MUX output then equals $S=A\oplus B\oplus C_{in}$.

(c) Two functions with one 3-to-8 decoder

A 3-to-8 decoder with inputs $A,B,C$ produces all eight minterm lines $D_0\ldots D_7$ (each output high for exactly one input combination). Any SOP function is then the OR of the decoder outputs for its minterms.

• $F_1=\sum m(1,3,5,7)$: OR-gate the lines $D_1,D_3,D_5,D_7 \Rightarrow F_1 = D_1+D_3+D_5+D_7$.
• $F_2=\sum m(0,2,4,6)$: OR-gate the lines $D_0,D_2,D_4,D_6 \Rightarrow F_2 = D_0+D_2+D_4+D_6$.

The same decoder feeds two separate 4-input OR gates, realizing both functions simultaneously. (Note: $F_1=C$ and $F_2=C'$, since the odd/even minterms correspond to $C=1/0$.) For active-low decoder outputs, NAND gates would replace the OR gates.

De Morgan's theorems (two variables)

Theorem 1: $\overline{A+B} = \bar{A}\cdot\bar{B}$
Theorem 2: $\overline{A\cdot B} = \bar{A}+\bar{B}$

Proof by truth table (Theorem 1):

Columns 3 and 4 are identical, proving $\overline{A+B}=\bar A\bar B$. Theorem 2 is proved the same way (its truth table gives 1,1,1,0, equal on both sides). The two theorems are duals of each other.

Simplification of $Y = AB + A(B+C) + B(B+C)$

$$Y = AB + AB + AC + BB + BC$$

Using $X+X=X$ (so $AB+AB=AB$) and $BB=B$ (idempotence):

$$Y = AB + AC + B + BC$$

Apply absorption $B + BC = B$ and $B + AB = B$:

$$Y = B + AC$$ $$\boxed{Y = B + AC}$$

(a) NOR-gate SR latch

An SR latch is built from two cross-coupled NOR gates: the output of each NOR feeds back to one input of the other. Inputs are $S$ (Set) and $R$ (Reset); outputs are $Q$ and $\bar Q$.

Operation: With $S=1,R=0$ the latch sets ($Q=1$); with $S=0,R=1$ it resets ($Q=0$); with $S=R=0$ it holds the stored value.

Forbidden condition: $S=R=1$ forces both $Q$ and $\bar Q$ to 0, violating the requirement that they be complementary. Worse, if both inputs then return to 0 simultaneously, the final state is unpredictable (a race), so this input combination is disallowed.

(b) Race-around condition and master-slave solution

Race-around: In a level-triggered JK flip-flop with $J=K=1$ (toggle), if the clock pulse width $t_p$ is longer than the propagation delay $t_{pd}$ of the gates, the output toggles repeatedly for the entire duration the clock is high. The final state at the end of the pulse becomes uncertain — this oscillation is the race-around condition.

Master-slave elimination: A master-slave JK uses two latches in series. The master latch is enabled when the clock is HIGH and accepts the inputs; the slave is enabled when the clock is LOW (clock inverted) and copies the master's state to the output. Because the two are never transparent at the same time, the output can change only once per clock cycle, removing the multiple-toggle oscillation. (Edge-triggered flip-flops achieve the same result.)

(a) Synchronous vs asynchronous (ripple) counter

(b) 4-bit SIPO shift register using D flip-flops

Circuit (described): Four D flip-flops $FF_0,FF_1,FF_2,FF_3$ are cascaded. Serial data enters $D_0$ of $FF_0$; the output $Q_0$ connects to $D_1$, $Q_1$ to $D_2$, and $Q_2$ to $D_3$. All four flip-flops share a common clock. The four outputs $Q_0Q_1Q_2Q_3$ are available in parallel.

Operation: On each clock pulse, every flip-flop loads the value at its $D$ input, so the bit pattern shifts one position. A serial bit stream applied at $D_0$ is shifted in one bit per clock; after 4 clock pulses the 4 input bits occupy $Q_0$–$Q_3$ and can be read out simultaneously (serial-to-parallel conversion). For example, to load 1011 the input bits are fed one per clock until all four bits sit in the register.

Half subtractor

Inputs $A$ (minuend), $B$ (subtrahend); outputs $D$ (difference $A-B$) and $B_{out}$ (borrow).

$$D = A\oplus B,\qquad B_{out} = \bar{A}B$$

Full subtractor

Inputs $A,B,B_{in}$ (incoming borrow); outputs $D$ and $B_{out}$.

$D=\sum m(1,2,4,7)$, $B_{out}=\sum m(1,2,3,7)$. Simplifying:

$$D = A\oplus B\oplus B_{in}$$ $$B_{out} = \bar{A}B + \bar{A}B_{in} + BB_{in} = \bar A B + (\overline{A\oplus B})B_{in}$$

Logic diagram of full subtractor (described):

• Two XOR gates produce the difference: $A\oplus B$, then $\oplus B_{in} = D$.
• The borrow uses: an inverter for $\bar A$, an AND gate $\bar A B$, and an AND gate $\overline{(A\oplus B)}\cdot B_{in}$ (taking the complement of the first XOR), combined by a 2-input OR gate to give $B_{out}$.

A full subtractor can thus be built from two half subtractors and one OR gate.

(a) Multiplexer and 4-to-1 MUX

A multiplexer (MUX) is a combinational circuit that selects one of several input data lines and routes it to a single output, the choice being controlled by select (address) lines. An $n$-select MUX has $2^n$ data inputs (a data selector / many-to-one switch).

4-to-1 MUX block (described): four data inputs $I_0,I_1,I_2,I_3$, two select lines $S_1S_0$, one output $Y$.

Function table:

Boolean output:

$$Y = \bar{S_1}\bar{S_0}I_0 + \bar{S_1}S_0 I_1 + S_1\bar{S_0}I_2 + S_1 S_0 I_3$$

The select lines decode to enable exactly one AND gate, passing its data input through the final OR gate.

(b) 8-to-1 MUX from two 4-to-1 MUX + one gate

Use three select lines $S_2S_1S_0$:

• MUX-A (4-to-1) handles data inputs $I_0$–$I_3$ with selects $S_1S_0$.
• MUX-B (4-to-1) handles data inputs $I_4$–$I_7$ with selects $S_1S_0$.
• The MSB $S_2$ chooses between the two: when $S_2=0$ the lower group is wanted, when $S_2=1$ the upper group.

Combining gate: Enable each 4-to-1 MUX with $S_2$ via its active-low enable (MUX-A enabled by $\bar{S_2}$, MUX-B by $S_2$) and OR their outputs:

$$Y = \bar{S_2}\,Y_A + S_2\,Y_B$$

A single 2-input OR gate (with the enable arrangement) merges the two outputs, giving a complete 8-to-1 multiplexer.

(a) Self-complementing code

A self-complementing code is one in which the code of the 9's complement of a decimal digit is obtained simply by complementing (inverting) each bit of the code for that digit. Equivalently, the codes of a digit $d$ and of $(9-d)$ are bit-wise complements.

Example: Excess-3 code. For digit 4 the XS-3 code is $0111$; its bit-complement is $1000$, which is the XS-3 code for $5 = 9-4$. (The 2421 code is another example.)

(b) Gray code conversions

Binary $(10110110)_2 \to$ Gray

Rule: MSB of Gray = MSB of binary; each next Gray bit $g_i = b_i \oplus b_{i+1}$ (XOR of adjacent binary bits).

Binary:  1  0  1  1  0  1  1  0
Gray:    1  1  1  0  1  1  0  1

Check: $1$; $1\oplus0=1$; $0\oplus1=1$; $1\oplus1=0$; $1\oplus0=1$; $0\oplus1=1$; $1\oplus1=0$; $1\oplus0=1$.

$$\boxed{(10110110)_2 = (11101101)_{Gray}}$$

Gray $(11011)_{Gray} \to$ binary

Rule: MSB of binary = MSB of Gray; each next binary bit $b_i = b_{i+1}\oplus g_i$ (XOR of the previous binary bit with the current Gray bit).

Gray:    1  1  0  1  1
Binary:  1  0  0  1  0

Check: $b_4=1$; $b_3=1\oplus1=0$; $b_2=0\oplus0=0$; $b_1=0\oplus1=1$; $b_0=1\oplus1=0$.

$$\boxed{(11011)_{Gray} = (10010)_2}$$

Mealy vs Moore finite state machines

Both are clocked sequential machines with a state register and combinational logic; they differ in how the output is generated.

Block diagrams (described):

• Mealy: Inputs and the state-register outputs both feed the output combinational logic (so inputs reach the output directly) as well as the next-state logic.
• Moore: Only the state-register outputs feed the output logic; the inputs feed only the next-state logic, so outputs are a pure function of state.

Mealy — Advantage: generally needs fewer states/flip-flops and reacts to input changes faster (lower latency). Disadvantage: outputs can change asynchronously with inputs, making them prone to glitches/spikes and harder to time.

Moore — Advantage: outputs change only on the clock edge, so they are stable and glitch-free, easier to synchronize. Disadvantage: usually requires more states/flip-flops and responds one clock cycle later to input changes.

Don't-care conditions

A don't-care condition is an input combination for which the output value is irrelevant — either because that input combination never occurs (e.g. unused codes in BCD, where 1010–1111 never appear) or because the output is not used for that case. In a K-map a don't-care is marked $d$ (or X) and may be grouped as either 0 or 1, whichever yields a larger, simpler grouping, helping to minimize the logic.

K-map simplification

$$F(A,B,C,D)=\sum m(1,3,5,7,9) + \sum d(10,11,12,13,14,15)$$

K-map (rows $AB$, columns $CD$):

All the 1-cells lie where $D=1$ (the $CD=01$ and $CD=11$ columns). Using the don't-cares $m_{11},m_{13},m_{15}$ to extend the grouping, the entire two columns where $D=1$ form a single group of eight, i.e. the single literal $D$.

$$\boxed{F = D}$$