BE Computer Engineering (IOE, TU) Digital Logic (IOE, EX 502) Question Paper 2078 Nepal

(a) Number System Conversions

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

Integer part 427 to binary (repeated division by 2, read remainders bottom-up):

So $427 = (110101011)_2$.

Fraction 0.625 to binary (repeated multiplication by 2, read carries top-down): $0.625\times2=1.25\;(1),\;0.25\times2=0.5\;(0),\;0.5\times2=1.0\;(1)$. So $0.625=(0.101)_2$.

$$\boxed{(427.625)_{10}=(110101011.101)_2}$$

Octal — group binary in 3s from the binary point: $\underbrace{110}_{6}\;\underbrace{101}_{5}\;\underbrace{011}_{3}.\underbrace{101}_{5}$

$$=(653.5)_8$$

Hexadecimal — group in 4s from the binary point ($0001\,1010\,1011.1010$): $\underbrace{0001}_{1}\,\underbrace{1010}_{A}\,\underbrace{1011}_{B}.\underbrace{1010}_{A}$

$$=(1AB.A)_{16}$$

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

$$2\times16^2+A\times16^1+F\times16^0+C\times16^{-1}$$ $$=2(256)+10(16)+15(1)+12(0.0625)=512+160+15+0.75$$ $$\boxed{(2AF.C)_{16}=(687.75)_{10}}$$

(b) Weighted vs Non-weighted Codes

Encoding $(58)_{10}$:

• BCD (8421): $5=0101,\;8=1000 \Rightarrow 0101\;1000$
• Excess-3 (add 3 to each digit, then BCD): $5+3=8=1000,\;8+3=11=1011 \Rightarrow 1000\;1011$
• Gray code of $58 = (111010)_2$: MSB unchanged, then each Gray bit = XOR of adjacent binary bits: $1,\;1\oplus1=0,\;1\oplus1=0,\;1\oplus0=1,\;0\oplus1=1,\;1\oplus0=1 \Rightarrow (100111)_{Gray}$

Advantage of Gray code: Only one bit changes between successive values, so in applications like shaft/position encoders and asynchronous state transitions it eliminates spurious intermediate outputs (glitches/false codes) that occur when multiple bits change simultaneously.

(a) De Morgan's Theorems

Statement:

$$\overline{A+B}=\bar A\cdot\bar B \qquad \overline{A\cdot B}=\bar A+\bar B$$

Proof by truth table (for $\overline{A+B}=\bar A\bar B$):

Columns 3 and 4 are identical, so the identity holds. The second theorem is proved similarly (the truth tables of $\overline{AB}$ and $\bar A+\bar B$ match).

Simplify $F=\overline{(A+\bar B)}+\overline{(\bar A\,C)}$:

Apply De Morgan to each term:

$$\overline{(A+\bar B)}=\bar A\cdot B,\qquad \overline{(\bar A\,C)}=A+\bar C$$ $$F=\bar A B + A + \bar C$$

Using the absorption identity $A+\bar A B = A+B$:

$$\boxed{F=A+B+\bar C}$$

NAND-only implementation: A SOP/OR form is realized with NAND by double-inversion. Since $F=A+B+\bar C=\overline{\bar A\cdot\bar B\cdot C}$, invert $A$, $B$ (using NAND as inverters, inputs tied together) and use $C$ directly, then feed $\bar A,\bar B,C$ into one 3-input NAND gate whose output is $F$. (An OR of three terms = NAND of their complements.)

(b) K-map for $F=\sum m(0,1,2,4,5,7,8,9,10,12,13,15)$

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

Minterm 3 is not present, so cell (00,11) = 0. Filling the 12 given minterms and grouping the 1s:

• Group of 8 — column pairs $CD=00$ and $CD=01$ (i.e. $\bar C$) covers $0,1,4,5,8,9,12,13$ ⇒ term $\bar C$.
• Group of 4 — $B\,D$ (cells $5,7,13,15$) ⇒ term $BD$.
• Group of 2 — minterms $2$ and $10$ ($\bar B\,\bar C\,D...$) actually $2,10$ share $B=0,C=0...$; minterm 2 $=\bar A\bar B C\bar D$, 10 $=A\bar B C\bar D$: common $\bar B C\bar D$ ⇒ term $\bar B C\bar D$.

$$\boxed{F=\bar C + BD + \bar B C\bar D}$$

(No don't-care cells were specified; all unlisted minterms are treated as 0.)

Circuit: one inverter for $C$; one 2-input AND for $BD$; one 3-input AND for $\bar B C\bar D$; feed the three product terms into a 3-input OR gate to obtain $F$.

(a) Synchronous vs Asynchronous (Ripple) Counters

Propagation-delay limitation of ripple counters: because each stage clocks the next, the change must ripple through every stage. With $n$ flip-flops each having delay $t_{pd}$, the worst-case settling time is $n\cdot t_{pd}$. This (i) limits the maximum clock frequency to roughly $f_{max}=1/(n\,t_{pd})$ and (ii) produces transient false intermediate counts (decoding spikes) during the ripple interval. Synchronous counters avoid this since all FFs switch together.

(b) Synchronous MOD-6 Counter (0→1→2→3→4→5→0) using JK Flip-Flops

State diagram: a single directed loop $0\to1\to2\to3\to4\to5\to0$. Three flip-flops $Q_C Q_B Q_A$ are needed ($2^3=8\ge6$); states 6 and 7 are unused (don't-cares).

JK excitation table (Q→Q⁺ ⇒ J,K): $0\to0:0,X$; $0\to1:1,X$; $1\to0:X,1$; $1\to1:X,0$.

State / excitation table ($Q_C Q_B Q_A$, present → next):

K-map simplification (using 110,111 as don't-cares):

• $J_A = \bar Q_C + \bar Q_B$? Check: $J_A$ must be 1 at states 000,010,100 (where $Q_A=0$ and we move to $Q_A=1$). $J_A=1$ at 000,010,100 ⇒ $J_A=\bar Q_A$ region; minimal: $J_A = \overline{Q_C Q_B}$ is not needed — simply $\;J_A=1$ except at state 011/101 where $Q_A=1$. Taking $Q_A$=0 rows: 000,010,100 give $J_A=1$. So $\boxed{J_A=\overline{Q_C}\,+\,\overline{Q_B}}$ covering 000,010,100 (and don't-care 110) ⇒ $J_A=\bar Q_C+\bar Q_B$... evaluating, the clean minimal result is:

$$J_A=\overline{Q_C}+\overline{Q_B},\quad K_A=1$$ $$J_B=Q_A\overline{Q_C},\quad K_B=Q_A$$ $$J_C=Q_AQ_B,\quad K_C=Q_A$$

(Verification: at 011 → $J_C=Q_AQ_B=1$ sets $Q_C$; $K_B=Q_A=1$ resets $Q_B$; $K_A=1$ resets $Q_A$ ⇒ next = 100 ✓. At 101 → $K_C=Q_A=1$ resets $Q_C$, $K_A=1$ resets $Q_A$ ⇒ 000 ✓.)

Final circuit: three JK flip-flops $A,B,C$ with a common clock. Wire $J_A=\bar Q_C+\bar Q_B$ (OR of inverted $Q_C,Q_B$) and $K_A=1$ (tied high); $J_B=Q_A\bar Q_C$ (AND of $Q_A$ and $\bar Q_C$), $K_B=Q_A$; $J_C=Q_AQ_B$ (AND), $K_C=Q_A$. Outputs $Q_CQ_BQ_A$ give the 0–5 count.

(a) Full Adder from Two Half Adders

Truth table (inputs $A,B,C_{in}$; outputs $S,C_{out}$):

Expressions:

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

Realization with two half adders (HA):

• HA-1 inputs $A,B$ → sum $S_1=A\oplus B$, carry $C_1=AB$.
• HA-2 inputs $S_1,C_{in}$ → sum $S=S_1\oplus C_{in}=A\oplus B\oplus C_{in}$, carry $C_2=S_1\,C_{in}=(A\oplus B)C_{in}$.
• An OR gate combines the two carries: $C_{out}=C_1+C_2=AB+(A\oplus B)C_{in}$.

(b) Implement $F(A,B,C)=\sum m(1,2,4,7)$ with a 4-to-1 MUX (A,B as select)

With $A,B$ as select lines ($S_1=A,\,S_0=B$), the remaining variable $C$ (and constants) form the data inputs. Tabulate minterms grouped by $AB$:

Data input connections:

$$I_0=C,\quad I_1=\bar C,\quad I_2=\bar C,\quad I_3=C$$

Implementation: a 4:1 MUX with select $S_1=A$, $S_0=B$. Connect $I_0$ and $I_3$ to $C$, and $I_1$ and $I_2$ to $\bar C$ (one inverter generates $\bar C$). The MUX output $Y=F$. This requires just the MUX plus one NOT gate.

$(35)_{10}-(52)_{10}$ using 8-bit 2's complement

Operands in 8-bit binary:

• $+35 = 0010\,0011$
• $+52 = 0011\,0100$

2's complement of 52 (so we can add $-52$): invert $0011\,0100 \to 1100\,1011$, then add 1 → $1100\,1100$. So $-52 = 1100\,1100$.

Addition $35 + (-52)$:

  0010 0011   (+35)
+ 1100 1100   (-52)
-----------
  1110 1111   (no carry out of MSB)

Result $= 1110\,1111$.

Interpretation: MSB $=1$ ⇒ the result is negative. Take its 2's complement to read the magnitude: invert $1110\,1111 \to 0001\,0000$, add 1 → $0001\,0001 = 17$.

$$\boxed{(35)_{10}-(52)_{10}=-17_{10}=1110\,1111_{\,2'\text{s comp}}}$$

There is no carry out of the MSB, which (together with operands of opposite sign) confirms there is no overflow and the result is valid.

3-to-8 Line Decoder

A decoder is a combinational circuit that converts an $n$-bit binary code into one of $2^n$ unique output lines. A 3-to-8 decoder has 3 inputs ($A_2A_1A_0$) and 8 outputs ($D_0$–$D_7$); for each input combination exactly one output is active (HIGH) — the one whose index equals the binary value of the input. Each output is a minterm: $D_i=m_i$.

Block diagram (described): a box with inputs $A_2,A_1,A_0$ and an enable $E$ on the left, and eight outputs $D_0\ldots D_7$ on the right.

Truth table (active-high, $E=1$):

Each output: $D_i=A_2'A_1'A_0'\ldots$ (the corresponding minterm), gated by $E$.

Building a 4-to-16 Decoder from two 3-to-8 Decoders

Use the 4th (most-significant) input $A_3$ to enable one decoder at a time:

• Feed $A_2A_1A_0$ to the address inputs of both decoders.
• Connect $A_3$ through an inverter so that:
  • Decoder-0 is enabled when $A_3=0$ (its enable $=\bar A_3$) → produces outputs $D_0$–$D_7$.
  • Decoder-1 is enabled when $A_3=1$ (its enable $=A_3$) → produces outputs $D_8$–$D_{15}$.

Since only one decoder is enabled for a given $A_3$, exactly one of the 16 outputs is active for each 4-bit input, giving a complete 4-to-16 decoder.

Latch vs Flip-Flop

JK Flip-Flop

The JK flip-flop removes the forbidden state of the SR flip-flop. With clock present:

Characteristic equation: $Q^{+}=J\bar Q+\bar K Q$.

Race-Around Condition

In a level-triggered JK flip-flop with $J=K=1$, the output toggles. If the clock pulse width $t_p$ is greater than the propagation delay $t_{pd}$, the output toggles repeatedly ($Q\to\bar Q\to Q\ldots$) while the clock is HIGH. At the end of the pulse the final state is uncertain. This uncontrolled multiple toggling is the race-around condition, and it occurs when $t_p>t_{pd}$.

Master-Slave Elimination

A master-slave configuration uses two JK flip-flops in cascade driven by complementary clocks:

• The master is enabled when clock $=1$ and captures the inputs, but its output cannot reach the outside.
• The slave is enabled when clock $=0$ and transfers the master's stored value to the output.

Because the master and slave are never transparent at the same time, the data is sampled once and transferred once per clock cycle. The output can change only on the clock edge, so toggling can happen at most once per cycle, eliminating the race-around condition.

4-bit Serial-In Parallel-Out (SIPO) Shift Register

Structure: four D flip-flops $Q_3Q_2Q_1Q_0$ in cascade, all driven by a common clock. Serial data enters $D_0$ of the first flip-flop; each flip-flop's output feeds the next flip-flop's D input ($D_1=Q_0,\;D_2=Q_1,\;D_3=Q_2$). All four outputs $Q_3Q_2Q_1Q_0$ are read out in parallel. On each clock pulse the contents shift one position (here toward $Q_3$) and the new serial bit enters at $Q_0$.

Operation with serial input $1011$ applied LSB first (so the bits enter in time order $1,1,0,1$). Register starts cleared at $0000$; bit shown entering at $Q_0$, shifting left:

After 4 clock pulses the register holds $Q_3Q_2Q_1Q_0 = 1101$, available in parallel. It takes $n=4$ clocks to serially load an $n$-bit SIPO register before the full word is read out.

RAM vs ROM

Internal Organization of a ROM

A ROM is essentially a programmable decoder + OR array. An $n$-input ROM has a fixed $n$-to-$2^n$ decoder (a fixed/hardwired AND array generating all $2^n$ minterms) feeding a programmable OR array that produces the output bits. A ROM with $n$ address lines and $m$ data lines stores $2^n\times m$ bits; each output column is the OR of the minterms programmed for that function.

Implementing functions with one ROM

The functions are given for input variables (extended to three inputs $A,B,C$, $n=3 \Rightarrow 8$ words). The decoder generates minterms $m_0$–$m_7$; we program two outputs $F_1,F_2$:

$$F_1=\sum m(0,2,5,7),\qquad F_2=\sum m(1,3,4,6)$$

ROM truth table (program map):

The 3-to-8 decoder activates the addressed minterm line; the OR-array fuse is present at $(m_i,F_1)$ wherever the $F_1$ column is 1, and similarly for $F_2$. Here $F_1$ and $F_2$ happen to be complementary. Thus a single $8\times2$ ROM implements both combinational functions: every minterm need only be routed to the correct output column.

PROM vs PLA vs PAL

All three are programmable logic devices built from an AND array (forms product terms) feeding an OR array (forms sums). They differ in which array is programmable:

Structure of a PLA

Described diagram: the $n$ inputs (and their complements) drive a programmable AND plane that generates a chosen set of product terms (not all minterms — only those needed). These product terms feed a programmable OR plane whose outputs are the sum-of-products functions. Programmable connection points (fuses/anti-fuses) exist at every cross-point of both planes.

Why a PLA is more flexible than a PROM

• In a PROM the AND array is fixed and decodes all $2^n$ minterms; you can only choose how minterms are OR-ed. For functions of many variables this wastes a huge number of unused product lines ($2^n$ grows exponentially).
• In a PLA the AND plane is programmable, so you generate only the specific product terms your functions require, and product terms can be shared among several outputs. This makes the PLA far more area-efficient for arbitrary, sparse SOP functions of many input variables, whereas a PROM is practical only for small look-up-table-style functions.

(a) NAND as a Universal Gate

A gate is universal if NOT, AND and OR can all be built from it; then any Boolean function is realizable. For a NAND, $Y=\overline{A\cdot B}$.

NOT: tie both inputs together — $\overline{A\cdot A}=\bar A$.

AND: NAND followed by a NAND-inverter — $\overline{\overline{A\cdot B}}=A\cdot B$. (First NAND gives $\overline{AB}$, second NAND used as inverter gives $AB$.)

OR: invert each input with a NAND, then NAND the results — by De Morgan $\overline{\bar A\cdot\bar B}=A+B$. So three NANDs: two as input inverters and one combining them.

Since NOT, AND, OR are all realized using only NAND gates, NAND is universal.

(b) XOR using NAND gates only

$Y=A\oplus B=A\bar B+\bar A B$. A standard 4-NAND realization:

G1 = NAND(A, B)        = (AB)'
G2 = NAND(A, G1)       = (A·(AB)')'
G3 = NAND(B, G1)       = (B·(AB)')'
Y  = NAND(G2, G3)      = A ⊕ B

Thus $Y=\overline{\big(\,\overline{A\cdot\overline{AB}}\,\big)\cdot\big(\,\overline{B\cdot\overline{AB}}\,\big)}=A\oplus B$, using only four 2-input NAND gates.

1-bit Magnitude Comparator

Compare two bits $A$ and $B$ producing $G\;(A>B)$, $E\;(A=B)$, $L\;(A<B)$.

Truth table:

Output expressions:

$$G=(A>B)=A\bar B$$ $$L=(A<B)=\bar A B$$ $$E=(A=B)=\overline{A\oplus B}=AB+\bar A\bar B$$

Implementation: $G$ uses one AND gate ($A$ and $\bar B$); $L$ uses one AND gate ($\bar A$ and $B$); $E$ is an XNOR of $A,B$ (equivalently $E=\overline{G+L}$, i.e. a NOR of the other two outputs). Two inverters supply $\bar A,\bar B$.