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

(a) Arithmetic Operations

(i) Subtract $(1010110)_2$ from $(1101001)_2$ using 2's complement

Minuend $= 1101001_2 = 105$, Subtrahend $= 1010110_2 = 86$. Expected result $= 19 = 0010011_2$.

Step 1 — 2's complement of the subtrahend $1010110$:

• 1's complement: $0101001$
• Add 1: $0101001 + 1 = 0101010$

Step 2 — Add to minuend:

  1101001   (minuend)
+ 0101010   (2's complement of subtrahend)
-----------
 10010011

Step 3 — End-around carry rule: A carry-out of the MSB (the leading $1$) is generated, so the result is positive; discard the carry.

$$\text{Result} = 0010011_2 = (19)_{10}$$

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

Hex → Decimal:

$$2\times16^2 + A\times16^1 + F\times16^0 + C\times16^{-1}$$ $$= 2\times256 + 10\times16 + 15\times1 + 12/16 = 512 + 160 + 15 + 0.75 = (687.75)_{10}$$

Hex → Octal (via binary, 4 bits per hex digit):

$$2=0010,\; A=1010,\; F=1111,\; C=1100$$

So $(2AF.C)_{16} = (0010\,1010\,1111\,.\,1100)_2 = 1010101111.11_2$.

Regroup in 3-bit groups from the binary point:

• Integer: $001\,010\,101\,111 = 1257$
• Fraction: $110 = 6$

$$\boxed{(2AF.C)_{16} = (687.75)_{10} = (1257.6)_8}$$

(b) Weighted and Non-weighted Codes

Weighted code: each bit position carries a fixed numerical weight, and the digit value equals the weighted sum of its bits (e.g., BCD 8421, 2421). Non-weighted code: positions carry no fixed weight, so the value is not a simple weighted sum (e.g., Gray code, Excess-3).

Gray code (non-weighted, reflected binary): successive numbers differ in exactly one bit. Conversion from binary: MSB stays the same, each lower Gray bit $g_i = b_{i+1} \oplus b_i$.

Application: shaft/rotary position encoders and K-map ordering, where single-bit change avoids switching glitches.

Excess-3 code (non-weighted, self-complementing): each decimal digit is coded as its BCD value plus 3. Example: $4 \to 4+3 = 7 = 0111$; $9 \to 12 = 1100$.

Application: used in older BCD arithmetic units because it is self-complementing (the 1's complement of a code word gives the 9's complement of the digit), simplifying subtraction.

(a) K-map Simplification of $F(A,B,C,D)=\sum m(0,1,2,5,8,9,10)+\sum d(3,11,15)$

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

Grouping (using don't-cares to enlarge groups):

• $B'C'$ — cells 0,1,8,9 (an eight-cell band combined): minterms 0,1,8,9 give $B'C'$.
• $B'D'$ — cells 0,2,8,10 give $B'D'$.
• $A'C'D$ — cells 1,5 (with 3 as don't-care assists, but the tight group of 1 and 5): minterm 5 needs covering. Cells 1 and 5 give $A'C'D$. Using don't-care 3, group 1,3,5,7? — 7 is 0, so the valid pair is $A'C'D$ covering 1,5.

Combining the prime implicants that cover all required 1's:

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

Check: $B'C'$ covers 0,1,8,9; $B'D'$ covers 0,2,8,10; $A'C'D$ covers 1,5. All required minterms covered.

NAND-only implementation: A two-level SOP maps directly to two-level NAND-NAND. Each product term is formed by a NAND gate (with its inputs), and the term outputs feed a final NAND gate:

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

Describe: three NAND gates produce $\overline{B'C'}$, $\overline{B'D'}$, $\overline{A'C'D}$ (literals $B',C',D'$ obtained by inverters or available complements); a fourth NAND gate combines them to give $F$. This is the standard NAND-NAND realization of an SOP function.

(b) DeMorgan's Theorems and XOR/XNOR Equivalence

DeMorgan's Theorems:

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

Proof by truth table (theorem 1):

Columns match for all input combinations, proving $\overline{A+B}=\overline{A}\,\overline{B}$. The second theorem follows identically.

Positive-logic XOR = Negative-logic XNOR: In positive logic, HIGH voltage = 1. Under negative logic, the same physical HIGH represents 0 and LOW represents 1, so every input/output value is complemented. For an XOR gate, the negative-logic function is $\overline{(\overline{A}\oplus\overline{B})}$. Since $\overline{A}\oplus\overline{B} = A\oplus B$, we get $\overline{A\oplus B} = A\odot B$ (XNOR). Hence a physical XOR gate read in negative logic behaves as an XNOR gate.

(a) "1011" Sequence Detector (overlapping) using JK Flip-flops

States (Mealy machine, output depends on input + state):

• $S_0$: no useful prefix
• $S_1$: got "1"
• $S_2$: got "10"
• $S_3$: got "101"

State diagram (described): From $S_0$: input 1 → $S_1$, 0 → $S_0$. From $S_1$: 1 → $S_1$, 0 → $S_2$. From $S_2$: 1 → $S_3$, 0 → $S_0$. From $S_3$: 1 → $S_1$ with output 1 (overlap: the final 1 starts a new "1"), 0 → $S_2$.

State / output table:

State assignment: $S_0=00,\ S_1=01,\ S_2=10,\ S_3=11$ (flip-flops $Q_1Q_0$).

Transition table:

JK excitation (rule: $0\to0:J=0,K=\times$; $0\to1:J=1,K=\times$; $1\to0:J=\times,K=1$; $1\to1:J=\times,K=0$):

Simplified input equations (from K-maps over $Q_1,Q_0,x$):

$$J_1 = Q_0 x' ,\quad K_1 = Q_0' x'$$ $$J_0 = x ,\quad K_0 = Q_1' \;\;(\text{i.e. } K_0 = \overline{Q_1}+x' \text{ after simplification})$$ $$\text{Output } Z = Q_1 Q_0 x$$

Implementation: Two JK flip-flops clocked together; combinational gates realize the four input equations above, and an AND gate $Q_1Q_0x$ produces the output $Z$.

(b) Moore vs Mealy Machine

State reduction removes redundant/equivalent states — two states are equivalent if, for every input, they produce the same output and go to equivalent next states. Merging them reduces flip-flop count and gate cost. Example: if states $S_2$ and $S_5$ always give the same output and equivalent next states, replace all references to $S_5$ with $S_2$; a machine of 6 states reducible to 4 needs only 2 flip-flops instead of 3.

(a) Full Adder from Two Half Adders

A half adder adds two bits: $S = A\oplus B$, $C = A\cdot B$. A full adder adds three bits $A,B,C_{in}$.

Truth table:

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

Using two half adders: HA-1 adds $A,B$ giving sum $S_1=A\oplus B$ and carry $C_1=AB$. HA-2 adds $S_1$ and $C_{in}$ giving final Sum $=S_1\oplus C_{in}$ and carry $C_2 = S_1 C_{in}$. An OR gate combines: $C_{out}=C_1+C_2 = AB + (A\oplus B)C_{in}$.

4-bit parallel (ripple-carry) adder: Cascade four full adders FA0..FA3. The carry-out of each stage feeds the carry-in of the next: $C_{in0}=0$, $C_1=C_{out0}$, ..., producing $S_0S_1S_2S_3$ and final carry $C_4$. The carry ripples from LSB to MSB.

(b) $F(A,B,C)=\sum m(1,3,5,6)$ with multiplexers

Using an $8\times1$ MUX: Apply $A,B,C$ to select lines $S_2S_1S_0$. Tie each data input $I_k=1$ for minterms in the list, else 0:

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

The MUX output equals $F$ directly.

Using a $4\times1$ MUX: Use $A,B$ as select lines; express each data input as a function of $C$ (the residual variable):

So $I_0=I_1=I_2=C$ and $I_3=C'$. The $4\times1$ MUX with these inputs realizes $F$ using one less variable on the select lines.

BCD-to-Seven-Segment Decoder (Common-Cathode)

A common-cathode display lights a segment when its input is HIGH (1). The decoder has 4 BCD inputs $A,B,C,D$ ($A$=MSB) and 7 outputs $a$–$g$. Inputs 10–15 are don't-cares ($d$). Digit patterns (segments lit):

Segment a truth table and K-map

$a=1$ for digits 0,2,3,5,6,7,8,9 → $a=0$ only for 1 and 4. So $\sum m(0,2,3,5,6,7,8,9)+d(10..15)$.

K-map simplification gives:

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

Segment b truth table and K-map

$b=1$ for 0,1,2,3,4,7,8,9 → $b=0$ for 5 and 6. So $\sum m(0,1,2,3,4,7,8,9)+d(10..15)$.

K-map simplification gives:

$$b = B' + C'D' + CD$$

(i.e. $b = \overline{B} + (C\odot D)$ — segment b is OFF only when $B=1$ and $C\neq D$, i.e. digits 5 and 6.)

Each output is realized as a two-level AND-OR (or NAND-NAND) network from these expressions; the remaining segments $c$–$g$ are derived identically.

Decoder vs Encoder

Octal-to-Binary (8-to-3) Priority Encoder

Inputs $D_0$–$D_7$, outputs $A_2A_1A_0$ plus a valid bit $V$. Priority means if several inputs are active, the highest-numbered input wins. $\times$ = don't-care.

Output expressions:

$$A_2 = D_7 + D_6 + D_5 + D_4$$ $$A_1 = D_7 + D_6 + \overline{D_5}\,\overline{D_4}D_3 + \overline{D_5}\,\overline{D_4}D_2$$ $$A_0 = D_7 + \overline{D_6}D_5 + \overline{D_6}\,\overline{D_4}D_3 + \overline{D_6}\,\overline{D_4}\,\overline{D_2}D_1$$ $$V = D_0+D_1+\dots+D_7$$

Need for priority: In an ordinary encoder, if two or more inputs are simultaneously active the output is an invalid superposition of codes. A priority encoder resolves this ambiguity by always encoding only the highest-priority active input, guaranteeing a meaningful output. The valid bit $V$ distinguishes the all-zero input (no active line) from the code for $D_0$.

NOR-gate SR Latch

Two cross-coupled NOR gates: $Q = \overline{R + \overline{Q}}$ and $\overline{Q} = \overline{S + Q}$. Inputs $S$ (set), $R$ (reset) are active-HIGH.

Invalid state: When $S=R=1$, both NOR outputs are forced to $0$, so $Q=\overline{Q}=0$ — they are no longer complementary. Worse, if both inputs then return to $0$ simultaneously, the latch enters an unpredictable (race) state because the final value depends on which gate switches faster. Hence $S=R=1$ is forbidden.

Master-Slave JK Flip-flop and Race-Around

Race-around occurs in a level-triggered JK flip-flop when $J=K=1$: while the clock is HIGH, the feedback makes the output toggle repeatedly (oscillate) because the output keeps changing the inputs as long as the clock stays high. If the clock pulse width $t_p$ is larger than the propagation delay, the final state is uncertain.

Master-slave configuration uses two JK latches in series:

• The master is enabled when CLK = 1 and accepts the J,K inputs.
• The slave is enabled when CLK = 0 (inverted clock) and copies the master's output.

Because master and slave are never transparent at the same time, the output of the whole flip-flop changes only once per clock cycle (on the falling edge effectively), eliminating multiple toggles.

Timing diagram (described): During CLK HIGH, the master latches the new value (master output changes) but the slave output $Q$ holds. On the CLK falling edge, the slave transfers the master's value to $Q$. With $J=K=1$, $Q$ toggles exactly once per clock pulse instead of oscillating — the race-around condition is removed.

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

Construction: Four D flip-flops (FF0–FF3) connected in cascade, all driven by a common clock. The serial data enters $D_0$ of FF0; 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$. The four outputs $Q_0,Q_1,Q_2,Q_3$ are available in parallel.

Logic diagram (described):

Serial in --> D0 [FF0] Q0 --> D1 [FF1] Q1 --> D2 [FF2] Q2 --> D3 [FF3] Q3
                |            |            |            |
CLK ------------+------------+------------+------------+

Operation: On each rising clock edge, every flip-flop loads the value present at its D input, so the data shifts one position to the right per clock. After 4 clocks, the 4-bit word is fully loaded and read in parallel.

Shifting serial data 1101 (LSB first, i.e. order 1,0,1,1 applied at serial input):

Assume serial input sequence applied per clock = 1, 1, 0, 1 (entering so that final pattern appears). Tracking $Q_0Q_1Q_2Q_3$ starting from 0000:

After 4 clock pulses the register holds the shifted data $Q_0Q_1Q_2Q_3 = 1011$, now available in parallel.

Timing waveform (described): The clock is a square wave. The serial-input waveform shows the bit sequence. Each $Q$ waveform is a one-clock-delayed copy of the stage before it, so $Q_0$ follows serial-in by one clock, $Q_1$ lags $Q_0$ by one clock, and so on — illustrating the right-shift of data through the register.

MOD-10 Asynchronous (Ripple) Counter using JK Flip-flops

A MOD-10 (decade) counter counts 0000 → 1001 (0–9) and resets to 0000 on the 10th pulse. It needs 4 JK flip-flops ($Q_0$=LSB).

Ripple connections: All J,K tied HIGH (toggle mode). $Q_0$ is clocked by the input clock; each following flip-flop is clocked by the output of the previous stage (for a negative-edge counter, $Q_n$ drives the clock of stage $n{+}1$).

Reset logic: The counter must clear at count $10 = 1010_2$, i.e. when $Q_3=1$ and $Q_1=1$. A NAND gate detects this:

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

When the count momentarily reaches $1010$, $Q_3Q_1=11$, the NAND output goes LOW and is fed to the active-LOW asynchronous CLEAR of all flip-flops, instantly resetting the counter to $0000$.

Logic diagram (described):

CLK -> [JK0] Q0 -> clk[JK1] Q1 -> clk[JK2] Q2 -> clk[JK3] Q3
  J=K=1 on all.   Q3,Q1 -> NAND -> CLR (active-low) of all FFs

Count sequence:

Timing waveforms (described): $Q_0$ toggles every clock pulse (÷2), $Q_1$ toggles every 2 pulses (÷4), $Q_2$ every 4, $Q_3$ every 8 — but the $1010$ glitch is detected and the count is forced back to 0000, so the sequence repeats every 10 clocks. Thus the counter resets at ten via the asynchronous CLEAR triggered when $Q_3=Q_1=1$.

RAM vs ROM

Implementing a Combinational Circuit with ROM

A ROM with $n$ address lines and $m$ data lines stores a complete truth table: the $n$ inputs form the address, and the stored $m$-bit word is the output. Internally a ROM is a fixed AND array (full decoder) + programmable OR array, so it directly realizes any combinational function of $n$ variables.

Example: 3-bit binary → its square

Input $A_2A_1A_0$ (0–7); output is the square (0–49), needing 6 output bits. So a $2^3 \times 6$ = $8\times6$ ROM.

Operation: The 3 input bits address one of the 8 ROM locations; the stored 6-bit word at that location is the binary square, produced directly at the output. No gate-level minimization is needed — the ROM "looks up" the answer, making it a simple and flexible way to implement combinational logic such as code converters and look-up tables.

PLA vs PAL

Both are programmable logic devices with two arrays (AND then OR).

Block diagrams (described): Inputs (with their complements) feed an AND-plane producing product terms. In a PLA both the input-to-AND connections and the AND-to-OR connections are programmable fuses. In a PAL the AND-plane is programmable but each OR gate is hard-wired to a fixed subset of product terms.

PLA Implementation

$$F_1(A,B,C)=\sum m(0,1,3,4), \qquad F_2(A,B,C)=\sum m(1,2,3,4,5)$$

Simplify with K-maps:

$F_1$: minterms 0,1,3,4.

$$F_1 = A'B' + A'C + B'C' \;\Rightarrow\; \text{minimal: } F_1 = A'B' + A'C + B'C'$$

Checking: $A'B'$ (0,1), $A'C$ (1,3), $B'C'$ (0,4). Covers 0,1,3,4. ✓

$F_2$: minterms 1,2,3,4,5.

$$F_2 = A'C + AB' + BC'$$

Checking: $A'C$ (1,3), $AB'$ (4,5), $BC'$ (2). Covers 1,2,3,4,5. ✓

Shared product terms: Both functions use $A'C$, so the PLA shares it.

Product terms used: $P_1=A'B'$, $P_2=A'C$ (shared), $P_3=B'C'$, $P_4=AB'$, $P_5=BC'$.

PLA Programming Table

(– = don't-connect; a 1 in the $F$ columns marks the OR-array fuse left intact.) Thus 5 product terms realize both outputs, sharing $A'C$.

Analog vs Digital Signals

• Analog signal: a continuous signal that can take any value within a range and varies smoothly with time (e.g., a sine wave, microphone voltage).
• Digital signal: a discrete signal that takes only a finite set of levels — typically two (LOW = 0, HIGH = 1) — changing in steps (e.g., a clock pulse train).

Universal Gate

The NAND gate (and equally the NOR gate) is a universal gate because any Boolean function — and hence NOT, AND, OR — can be built using only NAND gates.

NOT (tie both inputs together):

$$\overline{A\cdot A} = \overline{A}$$

AND (NAND followed by 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 them — DeMorgan):

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

Use two NANDs as inverters to get $\overline{A},\overline{B}$, then a NAND of these gives $A+B$.

Since NOT, AND and OR (a functionally complete set) are all realizable with NAND alone, the NAND gate is universal.

2-bit Magnitude Comparator

Compares $A = A_1A_0$ and $B = B_1B_0$, giving three outputs: $G$ ($A>B$), $E$ ($A=B$), $L$ ($A<B$).

Truth table (16 rows; summarized by relation):

Simplified output expressions:

Equality — both bit pairs equal:

$$E = (A_1\odot B_1)\,(A_0\odot B_0) = \overline{(A_1\oplus B_1)}\;\overline{(A_0\oplus B_0)}$$

Greater than — compare MSB first, then LSB:

$$G = A_1\overline{B_1} + (A_1\odot B_1)\,A_0\overline{B_0}$$

Less than — by complement / symmetry:

$$L = \overline{A_1}B_1 + (A_1\odot B_1)\,\overline{A_0}B_0$$

Note $G+E+L=1$ always (exactly one output is high). The circuit uses XNOR gates for bit equality plus AND/OR gates for the $G$ and $L$ terms.