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

(a) Number conversions

(i) $(1011.101)_2$

To decimal:

$$1\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 + 1\cdot2^{-1} + 0\cdot2^{-2} + 1\cdot2^{-3}$$ $$= 8 + 0 + 2 + 1 + 0.5 + 0 + 0.125 = (11.625)_{10}$$

To octal (group bits in 3s from the binary point):

$$\underbrace{001}_{1}\ \underbrace{011}_{3}\,.\,\underbrace{101}_{5} = (13.5)_8$$

So $(1011.101)_2 = (11.625)_{10} = (13.5)_8$.

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

To binary (each hex digit -> 4 bits):

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

To decimal:

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

(b) Subtraction $(110100)_2 - (10111)_2$ by 2's complement

Make both 6 bits: minuend $=110100$, subtrahend $=010111$.

2's complement of $010111$: 1's complement $=101000$, add 1 $\Rightarrow 101001$.

Add:

$$110100 + 101001 = 1\,011101$$

There is a carry-out of the MSB, so the result is positive and we discard the carry:

$$\text{Result} = (011101)_2 = (29)_{10}$$

Verification: $(110100)_2 = 52$, $(10111)_2 = 23$, and $52 - 23 = 29$. Confirmed.

(c) Weighted code, BCD encoding, Gray code

A weighted code is one in which each bit position is assigned a fixed weight, and the decimal value equals the weighted sum of the bits (e.g. BCD 8-4-2-1).

BCD (8421) of $(5290)_{10}$ — encode each digit in 4 bits:

$$5=0101,\ 2=0010,\ 9=1001,\ 0=0000$$ $$(5290)_{10} = (0101\,0010\,1001\,0000)_{BCD}$$

Gray code for shaft encoders: Gray code is preferred because only one bit changes between any two consecutive values. On a rotating shaft this prevents large transient errors that would occur if several bits changed at once and were read at slightly different instants, eliminating spurious ambiguous readings.

(a) De Morgan's theorems and simplification

Statements:

1. $\overline{A + B} = \bar A \cdot \bar B$ (complement of a sum = product of complements)
2. $\overline{A \cdot B} = \bar A + \bar B$ (complement of a product = sum of complements)

Proof by truth table (Theorem 1):

Columns $\overline{A+B}$ and $\bar A\bar B$ are identical, proving Theorem 1. Theorem 2 follows by the same method (columns $\overline{AB}$ and $\bar A+\bar B$ match).

Simplification:

$$F = AB + A(B+C) + B(B+C)$$ $$= AB + AB + AC + BB + BC$$ $$= AB + AC + B + BC \quad (AB+AB=AB,\ BB=B)$$ $$= AB + AC + B(1 + C) = AB + AC + B$$ $$= B(1 + A) + AC = B + AC$$ $$\boxed{F = B + AC}$$

(b) Karnaugh-map minimization

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

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

(Cell 3 = m3 is 0; minterm 7 sits at AB=01,CD=11.)

Groups:

• Column CD=01 all four cells (m1,5,13,9) = $\bar C D$
• Column CD=00 all four cells (m0,4,12,8) = $\bar C\bar D$ → combine the two columns: $\bar C$ (CD = 0x, i.e. C=0): covers m0,1,4,5,8,9,12,13.
• Remaining 1s: m2 ($00\,10$) groups with m0 ($00\,00$): $\bar A\bar B\bar C$ (already in $\bar C$). m2 is covered by $\bar C$? m2 has C=1, so NOT in $\bar C$. Group m0,m2 = $\bar A\bar B\bar D$.
• m7 ($01\,11$) and m15 ($11\,11$) group: $BCD$.

Minimal SOP:

$$F = \bar C + \bar A\bar B\bar D + BCD$$

(Here $\bar C$ covers all eight C=0 minterms; $\bar A\bar B\bar D$ covers m2; $BCD$ covers m7, m15.)

NAND-only implementation: convert by double-negation and De Morgan:

$$F = \overline{\overline{\bar C}\cdot\overline{\bar A\bar B\bar D}\cdot\overline{BCD}}$$

• First level: a NAND used as inverter to form $\bar C$; 3-input NANDs produce $\overline{\bar A\bar B\bar D}$ and $\overline{BCD}$.
• Second level: a 3-input NAND combines the three terms. All gates are NAND, giving a two-level NAND-NAND realization equivalent to the SOP.

(a) Mealy sequence detector for 1011 (overlapping)

States (track longest matched prefix):

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

Output $Z=1$ (on the transition) when the 4th bit completes 1011; overlap means after detecting 1011 the trailing "1" can begin a new match (go to $S_1$, and the "...11" path).

State diagram (described): transitions labelled input/output.

• $S_0$: on 1 → $S_1/0$; on 0 → $S_0/0$
• $S_1$: on 1 → $S_1/0$; on 0 → $S_2/0$
• $S_2$: on 1 → $S_3/0$; on 0 → $S_0/0$
• $S_3$: on 1 → $S_1/\mathbf{1}$ (1011 done, trailing 1 = new prefix); on 0 → $S_2/0$

State table:

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

Transition/excitation table (JK: from present $Q$ to next $Q$):

Excitation equations (K-map reduction of the columns):

$$J_1 = \bar Q_1 Q_0 \bar X, \qquad K_1 = \bar Q_0\bar X + Q_0 X$$ $$J_0 = X, \qquad K_0 = \bar X$$ $$Z = Q_1 Q_0 X$$

(Here $J_0=X,\ K_0=\bar X$ make $Q_0$ follow $X$; $J_1,K_1,Z$ are read from the table.)

(b) Moore vs Mealy machine

Diagram (described): In a Moore diagram each state circle carries its output (e.g. $S/Z$); in a Mealy diagram each arrow carries input/output (e.g. $X/Z$).

(a) $F(A,B,C)=\sum m(1,3,5,6)$ using an 8:1 MUX

Use $A,B,C$ as the select lines $S_2S_1S_0$. Each minterm drives the corresponding data input to 1; others to 0.

Connection diagram (described): an 8:1 MUX with selects $S_2=A,\ S_1=B,\ S_0=C$. Tie $I_1,I_3,I_5,I_6$ to logic 1 ($V_{CC}$) and $I_0,I_2,I_4,I_7$ to logic 0 (GND). The MUX output $Y=F$.

(b) 3-to-8 decoder and cascading to 4-to-16

3-to-8 decoder: inputs $A_2A_1A_0$, enable $E$, eight active-high outputs $D_0\ldots D_7$ where

$$D_i = E\cdot(\text{minterm } i),\quad e.g.\ D_0=E\bar A_2\bar A_1\bar A_0,\ \ D_7=E A_2 A_1 A_0$$

Each output is a 4-input AND gate fed by the appropriate true/complement input lines plus $E$; three inverters generate the complements.

Cascading to 4-to-16: use two 3-to-8 decoders sharing inputs $A_2A_1A_0$. The 4th (MSB) input $A_3$ acts as the enable selector:

• Decoder-0 enabled when $A_3=0$ → produces outputs $D_0$–$D_7$ (use $\bar A_3$ on its enable).
• Decoder-1 enabled when $A_3=1$ → produces outputs $D_8$–$D_{15}$ (use $A_3$ on its enable).

At any time only one decoder is active, so exactly one of the 16 outputs is high, giving a complete 4-to-16 line decoder.

(a) Full adder

Inputs: $A,B$ and carry-in $C_{in}$. Outputs: $SUM$ and $C_{out}$.

Simplified expressions:

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

(b) 4-bit parallel adder and carry-propagation limitation

Cascade four full adders FA0–FA3. The carry-out of each stage is wired to the carry-in of the next:

A0 B0        A1 B1        A2 B2        A3 B3
 |  |         |  |         |  |         |  |
[FA0]--C1-->[FA1]--C2-->[FA2]--C3-->[FA3]--> C4 (final carry)
  |           |           |           |
  S0          S1          S2          S3

Carry-in of FA0 is 0 (or used for subtraction). Outputs $S_3S_2S_1S_0$ with final carry $C_4$.

Limitation — carry-propagation (ripple) delay: Each full adder must wait for the carry from the previous stage before it can produce a correct sum and carry. The carry therefore ripples through all four stages, so the worst-case settling time grows linearly with the number of bits ($\approx n \times$ gate delay of one stage). This makes the ripple-carry adder slow for large word lengths; it is overcome by carry-look-ahead logic.

(a) JK flip-flop

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

Characteristic table:

Characteristic equation:

$$Q_{n+1} = J\bar Q_n + \bar K Q_n$$

Race-around condition: When $J=K=1$ and the clock pulse width $t_p$ is greater than the propagation delay of the flip-flop, the output toggles repeatedly during the single high level of the clock. The final state becomes unpredictable. This is the race-around problem of a level-triggered JK flip-flop.

Master-slave elimination: Two latches are connected in series. The master is enabled when the clock is HIGH and accepts the inputs; the slave is enabled when the clock is LOW (it uses the inverted clock) and copies the master's output. Because input and output sections are never enabled at the same instant, the output can change at most once per clock cycle, eliminating race-around.

(b) D flip-flop to T flip-flop

For a T flip-flop, $Q_{n+1} = T \oplus Q_n$. For a D flip-flop, $Q_{n+1} = D$. Equating:

$$D = T \oplus Q_n$$

So connect an XOR gate whose inputs are $T$ and the flip-flop output $Q$, and feed its output to the $D$ input. The clock is common.

(a) MOD-6 synchronous up counter using T flip-flops

Counts $000 \to 101$ (0–5) then back to 000. Three flip-flops $Q_2Q_1Q_0$.

State / excitation table (T = 1 where the bit changes):

Excitation equations (K-map reduction, states 6 and 7 are don't-cares):

$$T_0 = 1$$ $$T_1 = Q_0\bar Q_2$$ $$T_2 = Q_1 Q_0 + Q_2 Q_0$$

(With don't-cares for 110,111: $T_0=1$; $T_1 = Q_0\bar Q_2$; $T_2 = Q_0(Q_1+Q_2)$.)

Timing diagram (described): All flip-flops share one clock.

• $Q_0$ toggles every clock (square wave, period = 2 clocks).
• $Q_1$ toggles when $Q_0=1$ and $Q_2=0$.
• $Q_2$ goes high after count 3 and resets after count 5. The waveforms repeat every 6 clock cycles; the count sequence read top-down is 0,1,2,3,4,5,0,...

(b) Synchronous vs ripple counter

4-bit Serial-In Parallel-Out (SIPO) shift register

Structure: Four D flip-flops (FF0–FF3) in cascade, all driven by a common clock. Serial data enters $D$ of FF0; the output of each flip-flop feeds the $D$ input of the next.

Din -> [D Q]FF0 -> [D Q]FF1 -> [D Q]FF2 -> [D Q]FF3
         |Q0        |Q1        |Q2        |Q3
         v          v          v          v
      (parallel outputs Q0 Q1 Q2 Q3 read together)

Working: On each clock edge every flip-flop loads the value at its $D$ input, so the bit pattern shifts one position to the right. After four clock pulses a 4-bit serial word has been fully shifted in and is available simultaneously on the four parallel outputs $Q_0Q_1Q_2Q_3$.

Example (input bits 1,0,1,1 LSB first):

Thus serial data is converted to parallel form.

Two applications of shift registers:

1. Serial-to-parallel (and parallel-to-serial) data conversion in communication interfaces such as UART/SPI.
2. Temporary data storage and delay, ring/Johnson counters, and sequence generators.

(a) Canonical SOP of $F=(A+B)(A+C)$

First simplify/expand:

$$F = (A+B)(A+C) = A + BC \quad(\text{distributive law})$$

Expand to all three variables $A,B,C$ by inserting missing variables:

$$A = A(B+\bar B)(C+\bar C) = ABC + AB\bar C + A\bar BC + A\bar B\bar C$$ $$BC = (A+\bar A)BC = ABC + \bar ABC$$

Combine and drop duplicate $ABC$:

$$F = \bar ABC + A\bar B\bar C + A\bar BC + AB\bar C + ABC$$

In minterm form:

$$F = \sum m(3,4,5,6,7)$$

(b) Universal gates and EX-OR using NOR only

Universal gates: NAND and NOR are called universal because any Boolean function (AND, OR, NOT) can be implemented using only that single gate type.

EX-OR with NOR gates: $A\oplus B = A\bar B + \bar A B$. A standard 5-NOR realization:

G1 = NOR(A,B)            = (A+B)'
G2 = NOR(A,G1)           = (A + (A+B)')'  = A'(A+B) = AB'
G3 = NOR(B,G1)           = (B + (A+B)')'  = B'(A+B) = A'B
G4 = NOR(G2,G3)          = (AB' + A'B)'
G5 = NOR(G4,G4) = inverter -> (AB' + A'B) = A XOR B

So five NOR gates (G5 acting as an inverter) produce $A\oplus B$.

(a) BCD-to-seven-segment decoder, segment 'a'

Inputs are BCD digits $A B C D$ ($A$=MSB), driving a common-cathode display (segment ON = 1). Codes 10–15 are invalid → don't-care (X).

Truth table for segment 'a' (a is OFF only for digits 1 and 4):

K-map simplification (with don't-cares):

$$a = A + C + BD + \bar B\bar D$$

(b) Encoder vs decoder

(a) BCD addition $(0101)_{BCD} + (0110)_{BCD}$

$0101 = 5$, $0110 = 6$.

Binary sum:

$$0101 + 0110 = 1011\ (=11)$$

The result $1011$ is an invalid BCD code (greater than 9). Apply the correction factor +6 ($0110$):

$$1011 + 0110 = 1\,0001$$

So the BCD result is $0001\ 0001 = (11)_{BCD}$ — i.e. digit 1 with a carry of 1 to the next decade.

Why correction is needed: BCD uses only 0000–1001 (0–9); the six combinations 1010–1111 are unused. Whenever a 4-bit sum exceeds 9 or produces a carry out of the group, adding 6 skips over those six illegal codes and restores a valid BCD digit plus the proper decimal carry.

(b) Parity bit and error detection

A parity bit is an extra bit appended to a binary word to make the total number of 1s either even (even parity) or odd (odd parity).

Use: The transmitter computes the parity bit; the receiver recomputes parity on the received word. If the parity no longer matches, a transmission error is flagged. A simple parity bit can detect any single-bit (odd number of) error but cannot detect an even number of errors and cannot correct errors.