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

Signed Number Representations

In an $n$-bit signed representation the MSB is the sign bit ($0$ = positive, $1$ = negative).

1. Signed Magnitude

The MSB stores the sign; the remaining $n-1$ bits store the magnitude in plain binary.

• $+25 = 0\,0011001$
• $-25 = 1\,0011001$ (8-bit)

Drawbacks: two representations of zero ($00000000$ and $10000000$) and complicated arithmetic.

2. One's Complement

A negative number is formed by inverting (complementing) every bit of its positive magnitude.

• $+25 = 00011001$
• $-25 = 11100110$ (invert all bits)

Still has two zeros ($00000000$ and $11111111$) and needs end-around carry in addition.

3. Two's Complement

A negative number = 1's complement + 1. Range for $n$ bits: $-2^{n-1}$ to $+2^{n-1}-1$.

• $+25 = 00011001$
• $-25$: invert $\rightarrow 11100110$, add $1 \rightarrow 11100111$

Single representation of zero; ordinary binary addition works directly, so it is used in modern computers.

Compute $(-25) + (15)$ in 8-bit 2's complement

Step 1 — Represent each operand

$+25 = 00011001 \Rightarrow -25 = 11100111$

$+15 = 00001111$

Step 2 — Add

  1 1 1 0 0 1 1 1   (-25)
+ 0 0 0 0 1 1 1 1   (+15)
-----------------
  1 1 1 1 0 1 1 0

Step 3 — Interpret result. MSB $=1$, so the result is negative. Take 2's complement to read magnitude: invert $11110110 \rightarrow 00001001$, add $1 \rightarrow 00001010 = 10$.

No overflow occurs (the carry out of the sign bit is discarded; signs of operands differ so overflow is impossible).

Simplify $F(A,B,C,D)=\sum m(1,3,7,11,15) + d(0,2,5)$

Step 1 — K-map (1 = minterm, X = don't-care)

Rows = $AB$, Columns = $CD$ (Gray order $00,01,11,10$):

Step 2 — Group the 1's (using don't-cares helpfully)

• Group 1 (column CD=11, all four cells m3,7,15,11 = 1): a quad where $C=1, D=1$ → term $CD$.
• Group 2 (cells m1, m3, plus don't-cares m0, m2 in row AB=00): a quad covering row $AB=00$ → term $\bar A\bar B$.

Minterm 5 (don't-care) and others are left as 0; not needed.

Step 3 — Simplified SOP

Step 4 — Implement using NOR gates only

NOR is functionally complete. Convert the SOP to NOR form. By De Morgan:

Express each AND term as a NOR. Since $CD = \overline{\bar C + \bar D}$ and $\bar A\bar B = \overline{A+B}$:

• $\bar A\bar B = \text{NOR}(A,B)$ directly (one NOR gate with inputs $A,B$).
• $CD = \overline{\bar C + \bar D} = \text{NOR}(\bar C,\bar D)$, where $\bar C,\bar D$ are obtained from single-input NOR (inverter) gates.

NOR-gate network (described):

1. NOR gate $G_1$: inputs $A, B$ → output $\bar A\bar B$.
2. Inverters (NOR used as NOT) produce $\bar C$ and $\bar D$.
3. NOR gate $G_2$: inputs $\bar C, \bar D$ → output $CD$.
4. Final OR-into-NOR stage: the OR of two terms in NOR logic is $\text{NOR}(\overline{G_1},\overline{G_2})$. Invert $G_1$ and $G_2$, then NOR them: $F = \overline{\overline{(\bar A\bar B)}+\overline{(CD)}}$.

This realizes $F=\bar A\bar B + CD$ entirely with NOR gates (a two-level OR–AND/NOR–NOR structure).

4-bit Universal Shift Register

A universal shift register can perform all basic register operations: parallel load, shift-left, shift-right, and hold (no change). A 4-bit version is built from four flip-flops (FF$_0$–FF$_3$) and four 4-to-1 multiplexers, one in front of each flip-flop's D input.

Mode-control inputs

Two select lines $S_1S_0$ choose the operation for every multiplexer simultaneously:

Block diagram (described)

          S1 S0 (common select to all MUX)
   SI_right -> [MUX0]->D Q0 -+--> [MUX1]->D Q1 -+--> [MUX2]->D Q2 -+--> [MUX3]->D Q3 -> SI_left
Parallel   I0      |        I1      |        I2      |        I3      |
inputs ----+-------+---------+------+---------+------+---------+------+
              CLK common to all flip-flops; outputs Q0 Q1 Q2 Q3

Each 4-to-1 MUX inputs (for FF$_i$): (00) $Q_i$ hold, (01) right-neighbour for shift-right, (10) left-neighbour for shift-left, (11) parallel data $I_i$. The MUX output drives the D flip-flop.

Working

On every active clock edge, each flip-flop loads whatever its MUX has selected:

• 00 Hold: $Q_i \leftarrow Q_i$, contents preserved.
• 01 Shift right: $Q_i \leftarrow Q_{i+1}$ (data moves toward LSB); serial-right input enters at $Q_3$ side / MSB end.
• 10 Shift left: $Q_i \leftarrow Q_{i-1}$ (data moves toward MSB); serial-left input enters at $Q_0$ end.
• 11 Parallel load: $Q_i \leftarrow I_i$, all four bits loaded in one clock.

Because one register supports serial-in/serial-out, parallel-in/parallel-out, and bidirectional shifting, it is called universal (e.g. the 74194 IC).

Convert $(101101.101)_2$

To Decimal — multiply each bit by its positional weight

Integer part:

Fraction part:

To Octal — group bits in 3s from the binary point

Integer part: $101\,101 \Rightarrow (101)=5,\ (101)=5 \Rightarrow 55$

Fraction part: $101 \Rightarrow 5$ (already a group of 3)

Check: $(55.5)_8 = 5\cdot8+5 + 5\cdot8^{-1} = 45 + 0.625 = 45.625$ ✓

Consensus Theorem

Statement (SOP form):

The redundant term $BC$ (the consensus of $AB$ and $\bar AC$, formed from the variables left after removing the complementary pair $A,\bar A$) can be eliminated.

Dual (POS form): $(A+B)(\bar A+C)(B+C) = (A+B)(\bar A+C)$.

Proof

The consensus term $BC$ is therefore logically redundant and is dropped to simplify expressions and remove static hazards.

2-to-4 Line Decoder

A decoder converts an $n$-bit binary code into one of $2^n$ active output lines. A 2-to-4 decoder has 2 inputs ($A_1,A_0$), an optional enable $E$, and 4 outputs ($D_0$–$D_3$); for each input combination exactly one output is asserted (active-HIGH here).

Truth table (active-HIGH, enabled)

Output equations

Working

Each output is the AND of the appropriate input literals (with the enable). Only the minterm that matches the input code is 1, so the decoder "selects" one of four lines. When $E=0$ all outputs are 0 (disabled). Implementation needs four 3-input AND gates plus two inverters that generate $\bar A_1,\bar A_0$. Decoders are used for memory address selection, demultiplexing, and to implement any Boolean function as a sum of minterms.

4-to-1 Multiplexer using Logic Gates

A MUX routes one of several data inputs to a single output, chosen by select lines. A 4-to-1 MUX has 4 data inputs ($I_0,I_1,I_2,I_3$), 2 select lines ($S_1,S_0$), and 1 output $Y$.

Function table

Boolean expression

Gate-level implementation

• Two inverters produce $\bar S_1$ and $\bar S_0$.
• Four 3-input AND gates, one per data input:
  • AND$_0$: $I_0,\bar S_1,\bar S_0$
  • AND$_1$: $I_1,\bar S_1,S_0$
  • AND$_2$: $I_2,S_1,\bar S_0$
  • AND$_3$: $I_3,S_1,S_0$
• One 4-input OR gate combines the four AND outputs to give $Y$.

S1 ->|>o- S1'      I0 -+
S0 ->|>o- S0'           [AND0]-+
                  I1 --[AND1]--+
                  I2 --[AND2]--+--[OR]--> Y
                  I3 --[AND3]--+

For any select code, only the matching AND gate passes its data input (others output 0), so $Y$ equals the selected input.

Moore vs Mealy Machines

Both are finite-state machine models for synchronous sequential circuits; they differ in how the output is generated.

Summary: A Moore machine's output is a function of state alone, giving stable, delayed outputs; a Mealy machine's output also depends on the input, giving faster response with fewer states but possible glitches. Any Moore machine can be converted to an equivalent Mealy machine and vice versa.

T (Toggle) Flip-Flop

The T flip-flop has a single input $T$ and a clock. It is obtained from a JK flip-flop by tying $J=K=T$.

Operation / characteristic table

• $T=0$: output holds its previous value, $Q_{n+1}=Q_n$.
• $T=1$: output toggles (complements) on each active clock edge, $Q_{n+1}=\bar Q_n$.

Characteristic equation:

Because it divides the clock frequency by 2 when $T=1$, the T flip-flop is the basic building block of ripple/asynchronous counters.

Excitation table

(Given a required $Q_n \to Q_{n+1}$ transition, what $T$ is needed?)

So $T = Q_n \oplus Q_{n+1}$: $T=1$ whenever the output must change, $T=0$ when it must stay the same.

BCD Adder

A BCD (Binary-Coded Decimal) adder adds two BCD digits (each a 4-bit code for decimal 0–9) and produces a valid BCD sum digit plus a decimal carry. It is needed because ordinary 4-bit binary addition can yield results that are not valid BCD (the codes 1010–1111) or produce a binary carry, both of which must be corrected.

Why correction is needed

Valid BCD digits are $0000$–$1001$ (0–9). If the binary sum of two BCD digits exceeds $9$, or generates a carry-out, the result is invalid in BCD.

Correction rule

Add $6\,(0110)$ to the 4-bit sum when:

• the sum $> 9$ (i.e. sum is 1010–1111), or
• a carry-out $C_{out}$ is generated from the first adder.

The correction-needed signal is:

($S_3S_2$ detects 12–15, $S_3S_1$ detects 10–11.)

Working / structure

1. A first 4-bit binary adder adds the two BCD digits $A+B+C_{in}$, giving sum $S_3S_2S_1S_0$ and carry $C_{out}$.
2. The detection logic computes $C$ above.
3. A second 4-bit adder adds $0110$ to the first sum when $C=1$ (adds $0000$ otherwise).
4. The output of the second adder is the corrected BCD sum digit; $C$ becomes the decimal carry to the next-higher BCD digit.

Example: $7+5=12$. Binary $0111+0101 = 1100$ ($=12>9$), so add $0110$: $1100+0110 = 1\,0010$ → carry 1, digit $0010 = 2$, i.e. $12$ in BCD ($0001\,0010$). ✓

Design of a Mod-5 Counter using JK Flip-Flops

A mod-5 counter counts $0 \to 1 \to 2 \to 3 \to 4 \to 0$, i.e. 5 states. It needs $\lceil\log_2 5\rceil = 3$ flip-flops ($Q_2Q_1Q_0$). States 101,110,111 are unused (don't-cares).

Step 1 — State / transition table with JK excitation

JK excitation: $0\to0:J0,K{\times}$; $0\to1:J1,K{\times}$; $1\to0:J{\times},K1$; $1\to1:J{\times},K0$.

Step 2 — Simplify (K-maps, using 101,110,111 as don't-cares)

Step 3 — Implementation

• FF0: $J_0=\bar Q_2$, $K_0=1$
• FF1: $J_1=K_1=Q_0$ (FF1 acts as a T flip-flop toggling on $Q_0$)
• FF2: $J_2=Q_1Q_0$ (one AND gate), $K_2=1$

All flip-flops share the common clock. When the count reaches $4\,(100)$, the equations force the next state to $000$, giving a clean modulo-5 cycle. (Alternatively, a 3-bit binary counter with a NAND gate decoding state $101$ to asynchronously clear all flip-flops also gives mod-5.)

Race-Around Condition

The race-around condition is a problem in a level-triggered JK (or SR) flip-flop when both inputs $J=K=1$ (the toggle case) and the clock pulse stays HIGH for longer than the propagation delay of the gates.

Cause

With $J=K=1$, the output should toggle once. But while the clock is HIGH the feedback path is enabled, so the output keeps toggling continuously ($0\to1\to0\to1\dots$) every gate-delay $t_{pd}$ as long as the clock remains HIGH. If the clock pulse width $t_p > t_{pd}$, the flip-flop changes state multiple times and the final output is unpredictable (depends on exactly when the clock goes LOW). This rapid oscillation is the race-around condition.

Remedies

1. Narrow clock pulse: make $t_p < t_{pd}$ so only one toggle occurs — hard to guarantee in practice.
2. Master-Slave JK flip-flop: two latches in series (master enabled when clock HIGH, slave when clock LOW). The output updates only once per clock cycle, eliminating the race.
3. Edge-triggered flip-flop: the device responds only at the rising/falling clock edge, so the output can change at most once per clock pulse.

Thus race-around is eliminated by master-slave or edge-triggered designs.