BSc CSIT (TU) Science Digital Logic (BSc CSIT, CSC116) Question Paper 2079 Nepal

(i) $(375)_8$ to binary

Replace each octal digit by its 3-bit binary equivalent:

(ii) $(1AF)_{16}$ to decimal

Use positional weights of base 16 (with $A=10,\ F=15$):

(iii) $(101101)_2$ to Gray code

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

• $g_5 = 1$
• $1\oplus0=1,\ 0\oplus1=1,\ 1\oplus1=0,\ 1\oplus0=1,\ 0\oplus1=1$

(iv) Decimal 89 to BCD

Encode each decimal digit in 4-bit BCD:

Step 1: Plot the K-map

$F(A,B,C,D)=\sum m(0,1,2,3,5,7,8,9,11,14)$. Using rows $AB$ and columns $CD$ in Gray order ($00,01,11,10$):

Step 2: Group the 1s (largest possible groups)

1. Quad $A'B'$ (top row, m0,m1,m3,m2) $\Rightarrow A'B'$
2. **Quad $C'D$ + ... ** group m1,m3,m5,m7 (where $A'D=1$) — cells m1,m3,m7,m5 all have $A'D \Rightarrow A'D$
3. Quad $B'C$ : m1,m3,m9,m11 $\Rightarrow B'C$
4. **Quad $B'D'$? ** Use m0,m2,m8,m10? m10 is 0, so instead pair m8,m9 with m0,m1: m0,m1,m8,m9 share $B'C'$ $\Rightarrow B'C'$
5. Single covering m14: m14 ($ABCD'=1110$) — pair with m6? (0). Pair with m10?(0). Pair with m12?(0). It is isolated, so cover as the pair m14,m6? not available — take it with the only adjacent 1. Adjacent cells m6,m10,m12,m15 are all 0, so m14 is an essential single term $ABCD'$.

Minimal cover:

(Note: $B'C'$ from group 4 is already covered by $A'B'$ and $B'C$, so it is redundant.)

Verification: this SOP reproduces exactly the listed minterms.

Step 3: Simplified expression

Step 4: Logic diagram (described)

• AND gate 1: inputs $A'$ (A through inverter) and $B'$ $\rightarrow$ $A'B'$
• AND gate 2: inputs $A'$ and $D$ $\rightarrow$ $A'D$
• AND gate 3: inputs $B'$ and $C$ $\rightarrow$ $B'C$
• AND gate 4 (4-input): inputs $A,B,C,D'$ $\rightarrow$ $ABCD'$
• OR gate (4-input): combines the four AND outputs to give $F$.
• Inverters generate $A',B',D'$ from $A,B,D$.

Sequential circuit

A sequential circuit is a digital circuit whose output depends not only on the present inputs but also on the past history of inputs, i.e. on the present internal state stored in memory elements (flip-flops). It is built from a combinational logic block plus memory (flip-flops), with feedback from the state outputs back into the logic. A clocked synchronous sequential circuit changes state only at active clock edges.

Design procedure of a clocked synchronous sequential circuit

1. State diagram / word description — derive the required behaviour as a state diagram.
2. State table — list present state, input, next state and output.
3. State assignment — assign binary codes to states; reduce states first if possible.
4. Choose flip-flop type (D, JK, T) and determine the number of flip-flops ($n$ flip-flops for up to $2^n$ states).
5. Excitation table — using the flip-flop excitation table, find the required flip-flop inputs for each state transition.
6. K-map simplification — derive minimal Boolean expressions for each flip-flop input and for the outputs.
7. Draw the logic diagram — combinational logic + flip-flops + clock.

Example: 2-bit synchronous up counter (using JK flip-flops)

States: $00\to01\to10\to11\to00$. Let state = $Q_1Q_0$.

Excitation (T-style with JK): For an up counter $Q_0$ toggles every clock, $Q_1$ toggles when $Q_0=1$.

• $J_0=K_0=1$
• $J_1=K_1=Q_0$

Logic diagram (described): Two JK flip-flops share a common clock. FF0 has $J_0=K_0=1$ (toggles each clock). FF1 has $J_1=K_1=Q_0$. Output $Q_1Q_0$ counts $00,01,10,11$ repeatedly.

This illustrates every design step: behaviour → state table → flip-flop choice → excitation → simplified inputs → circuit.

Excess-3 (XS-3) code

Excess-3 is a non-weighted, self-complementing BCD code in which each decimal digit is represented by its 4-bit binary value plus 3 (i.e. 0011).

Examples: decimal $0\to0011$, $5\to1000$, $9\to1100$.

Self-complementing property: the 1's complement of an XS-3 code equals the XS-3 code of the 9's complement of that digit (e.g. $4 = 0111$, complement $1000 = 5 = 9-4$).

Applications

• BCD arithmetic / subtraction: the self-complementing property makes 9's-complement subtraction easy, simplifying decimal adders/subtractors.
• Error detection in older digital systems, since the codes $0000$ and ... are unused/forbidden, helping detect invalid states.
• Used in some arithmetic units and calculators for simplified decimal addition.

Simplify $F = (A+B)(A+C)$

Using the distributive law $(X+Y)(X+Z) = X + YZ$ with $X=A$:

Step-by-step proof (expanding):

Half subtractor

A half subtractor is a combinational circuit that subtracts two single-bit binary numbers $A$ (minuend) and $B$ (subtrahend), producing a Difference (D) and a Borrow (Bo). It does not consider a borrow from a previous stage.

Truth table

Boolean expressions

Working / logic

• The Difference output is the XOR of the two inputs.
• The Borrow is generated only when $A=0$ and $B=1$ (subtracting a larger bit from a smaller one), giving $B_o = \bar{A}B$.

Circuit: one XOR gate produces $D$; one AND gate with input $A$ inverted (i.e. $A'$) and $B$ produces $B_o$.

EX-OR using NAND gates only

The XOR function is $Y = A\oplus B = A\bar{B} + \bar{A}B$. It can be realized with four 2-input NAND gates.

Construction (4 NAND gates)

1. NAND 1: inputs $A,B$ $\Rightarrow$ $G_1 = \overline{AB}$
2. NAND 2: inputs $A, G_1$ $\Rightarrow$ $G_2 = \overline{A\cdot\overline{AB}} = \overline{A\bar{B}}$
3. NAND 3: inputs $B, G_1$ $\Rightarrow$ $G_3 = \overline{B\cdot\overline{AB}} = \overline{\bar{A}B}$
4. NAND 4: inputs $G_2, G_3$ $\Rightarrow$ $Y = \overline{G_2 \cdot G_3}$

Proof that $Y = A\oplus B$

(by De Morgan's theorem, $\overline{\bar X \cdot \bar Z} = X + Z$).

Verification: outputs $1$ only when $A\ne B$ — exactly the XOR truth table.

Diagram (described): $A$ and $B$ feed NAND 1; its output $G_1$ feeds back as the second input of NAND 2 (with $A$) and NAND 3 (with $B$); outputs $G_2,G_3$ feed NAND 4 whose output is $Y$.

8-to-1 Multiplexer

A multiplexer (MUX) is a combinational circuit that selects one of several input lines and routes it to a single output line, controlled by select lines. An 8-to-1 MUX has:

• 8 data inputs: $I_0$ to $I_7$
• 3 select lines: $S_2, S_1, S_0$ (since $2^3 = 8$)
• 1 output: $Y$
• (often an Enable input)

Working

The 3-bit binary value on $(S_2 S_1 S_0)$ selects exactly one data input to appear at $Y$. For example, $S_2S_1S_0 = 101$ (decimal 5) connects $I_5$ to $Y$.

Boolean expression

Selection table

Structure: eight 4-input AND gates (each gated by a data input and the decoded select combination) feeding one 8-input OR gate. Used for data routing, parallel-to-serial conversion and implementing Boolean functions.

Register vs Counter

Summary: A register is a set of flip-flops used to store $n$-bit data, whereas a counter is a special register that automatically cycles through a predetermined sequence of states on successive clock pulses.

Conversion of JK flip-flop into D flip-flop

We convert a JK flip-flop so that it behaves like a D flip-flop, where $Q_{next} = D$.

Step 1: Conversion table

(Required next state $Q_{next}=D$; $J,K$ obtained from the JK excitation table.)

Step 2: Derive $J$ and $K$ (K-map / inspection)

From the table:

Step 3: Circuit

Connect the external input $D$ directly to $J$, and connect $D$ through an inverter (NOT gate) to $K$:

Verification:

• $D=1 \Rightarrow J=1,K=0 \Rightarrow Q_{next}=1$
• $D=0 \Rightarrow J=0,K=1 \Rightarrow Q_{next}=0$

Thus the JK flip-flop with $J=D,\ K=\bar{D}$ functions exactly as a D flip-flop.

Ring counter

A ring counter is a circular shift register in which the output of the last flip-flop is fed back to the input of the first flip-flop, so that a single bit (or pattern) circulates around the ring. With $n$ flip-flops it has $n$ distinct states (a mod-$n$ counter) using a one-hot pattern.

Operation (4-bit example)

Four D flip-flops ($Q_3 Q_2 Q_1 Q_0$) are connected in series with $Q_0$ fed back to the input of $Q_3$. It is preset to a single 1, e.g. $1000$. On each clock pulse the 1 shifts one position:

Key points

• Number of states = number of flip-flops ($n$), so it is less efficient than a binary counter but needs no decoding logic (each state already a one-hot output).
• Applications: sequencing, generating timing/control signals, and as a clock-pulse distributor.

Hazards in combinational circuits

A hazard is an unwanted, momentary (transient) change in the output of a combinational circuit caused by unequal propagation delays along different signal paths, even though the steady-state output should remain unchanged. Hazards produce glitches that can cause malfunction in circuits driven by these outputs (especially asynchronous logic).

Types of hazards

1. Static hazard — the output should stay constant but momentarily changes.
   • Static-1 hazard: output should remain $1$ but briefly drops to $0$ (occurs in SOP / AND-OR circuits).
   • Static-0 hazard: output should remain $0$ but briefly rises to $1$ (occurs in POS / OR-AND circuits).
2. Dynamic hazard — the output should change once ($0\to1$ or $1\to0$) but instead changes multiple times (e.g. $0\to1\to0\to1$) before settling. It occurs in multi-level circuits with several paths.

Cause

When a single input changes and it can reach the output through two paths with different delays, the two terms (e.g. adjacent minterm groups in a K-map) momentarily both go inactive.

Elimination

Add redundant (consensus) terms so that adjacent groups in the K-map overlap. Including the consensus term keeps the output covered during the transition, removing the glitch. Other techniques: balancing path delays, using a synchronizing clock (latch the output).