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

Types of Number Systems

A number system defines how numeric values are represented using a fixed set of symbols and a base (radix).

• Decimal: the everyday system used by humans.
• Binary: used internally by digital systems since transistors have two stable states.
• Octal and Hexadecimal: compact shorthand for long binary strings (1 octal digit = 3 bits, 1 hex digit = 4 bits).

Conversion of $(2AF.C)_{16}$

(a) Hexadecimal → Decimal

Multiply each digit by its positional weight (powers of 16):

(b) Hexadecimal → Binary

Replace each hex digit by its 4-bit binary equivalent:

• $2 = 0010$, $A = 1010$, $F = 1111$, $C = 1100$

(c) Hexadecimal → Octal

Easiest via the binary result. Group the binary into 3-bit sets from the binary point:

Integer part 1010101111 → 001 010 101 111 = 1257

Fraction part 11 → 110 = 6

Final Results

Simplifying $F(A,B,C,D)=\sum(0,1,2,4,5,6,8,9,12,13,14)$

Step 1 — Plot the K-map

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

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

• Group 1 (column CD=00, all four rows = 8 cells with CD=01 too): cells where $C=0$. Minterms 0,1,4,5,8,9,12,13 form an octet → $C'$.
• Group 2 (quad): minterms 0,2,4,6 ($A=0, D=0$) extends with 12,14 → 4,6,12,14 and 0,2... The quad 0,4,12,8 (CD=00, i.e. $C'D'$)... use a clean quad: minterms 2,6,14 and 4,... Choose quad {4,6,12,14} = $BD'$.
• Group 3 (quad): minterms {0,2,8,...}: cells $A=0,D=0$ → {0,2,4,6} = $A'D'$.

Step 3 — Minimal cover

The simplest valid cover is:

Check: $C'$ covers 0,1,4,5,8,9,12,13. Remaining 1s are 2,6,14 (all have $D=0,C=1$). $A'D'$ covers 2,6; $BD'$ covers 6,14. Together with overlap they cover 2,6,14. All eleven minterms covered, no extra terms.

Step 4 — NAND implementation

Apply DeMorgan's theorem to the SOP. Each product term becomes a NAND, and the final OR becomes a NAND of the term-NANDs (two-level NAND–NAND):

Circuit (two-level NAND–NAND):

• NAND-1 input: $C$ (acts as inverter giving $C'$).
• NAND-2 inputs: $A', D'$ → output $\overline{A'D'}$.
• NAND-3 inputs: $B, D'$ → output $\overline{BD'}$.
• Final NAND combines the three outputs to give $F$.

Inverters ($A', D'$) are themselves built from single-input NAND gates, so the whole function is realised using NAND gates only.

Synchronous Mod-8 Up Counter using JK Flip-Flops

A mod-8 counter has $2^3 = 8$ states (000 → 111), so three JK flip-flops (FF0=LSB, FF1, FF2=MSB) are needed. In a synchronous counter all flip-flops receive the same clock simultaneously.

Step 1 — Excitation logic

A JK flip-flop toggles when $J=K=1$ and holds when $J=K=0$. Each bit toggles when all lower-order bits are 1:

Step 2 — Circuit description

• All three flip-flops wired in toggle mode, with a common clock line.
• $J_0=K_0$ tied to logic 1.
• $J_1=K_1$ connected to $Q_0$.
• $J_2=K_2$ connected to the output of an AND gate fed by $Q_0$ and $Q_1$.
• Outputs $Q_2Q_1Q_0$ give the count.

Step 3 — Count sequence

Step 4 — Timing diagram (described)

All flip-flops change on the same active clock edge.

• Q0 toggles on every clock pulse — highest frequency, $f_{clk}/2$.
• Q1 toggles once for every two Q0 toggles — $f_{clk}/4$.
• Q2 toggles once for every four Q0 toggles — $f_{clk}/8$.

CLK : _|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_
Q0  : __|‾‾|__|‾‾|__|‾‾|__|‾‾|__   (÷2)
Q1  : ____|‾‾‾‾|____|‾‾‾‾|____    (÷4)
Q2  : ________|‾‾‾‾‾‾‾‾|________  (÷8)

This confirms the counter advances 0→7 and rolls over to 0, i.e. a mod-8 synchronous up counter.

1's and 2's Complement Representations

1's Complement

The 1's complement of a binary number is obtained by inverting every bit (0→1, 1→0).

Example: 1's complement of $0101$ is $1010$.

In signed 1's complement representation the MSB is the sign bit (0 = positive, 1 = negative). A drawback is that it has two representations of zero ($0000$ = +0 and $1111$ = −0).

2's Complement

The 2's complement is obtained by taking the 1's complement and adding 1 to the LSB:

Example: 2's complement of $0101$ = $1010 + 1 = 1011$.

Advantages of 2's complement:

• Unique representation of zero.
• Subtraction is performed by addition, so the same adder hardware works for both.
• It is the standard representation of signed integers in computers.

Comparison

Postulates of Boolean Algebra (Huntington Postulates)

Boolean algebra is defined over the set $B=\{0,1\}$ with operations OR ($+$), AND ($\cdot$) and NOT ($'$):

1. Closure — For any $A,B\in B$, both $A+B$ and $A\cdot B$ belong to $B$.
2. Identity elements — $A+0 = A$ (0 is identity for OR); $A\cdot 1 = A$ (1 is identity for AND).
3. Commutative law — $A+B = B+A$ and $A\cdot B = B\cdot A$.
4. Distributive law — $A\cdot(B+C) = A\cdot B + A\cdot C$ and $A+(B\cdot C) = (A+B)\cdot(A+C)$.
5. Complement (inverse) — For every $A$ there exists $A'$ such that $A+A' = 1$ and $A\cdot A' = 0$.

From these, basic identities follow: $A+A=A$, $A\cdot A=A$, $A+1=1$, $A\cdot0=0$, and De Morgan's theorems $(A+B)'=A'B'$, $(A\cdot B)'=A'+B'$.

1-to-4 Demultiplexer (DEMUX)

A demultiplexer is a combinational circuit that takes a single data input and routes it to one of several outputs, selected by control (select) lines. It performs the reverse function of a multiplexer.

A 1-to-4 DEMUX has:

• 1 data input $D$
• 2 select lines $S_1, S_0$ ($2^2 = 4$ outputs)
• 4 outputs $Y_0, Y_1, Y_2, Y_3$

Working

The select lines decide which output the input $D$ is connected to; all other outputs stay at 0.

Boolean expressions

Circuit: four 3-input AND gates; each AND gate receives the data $D$ and the proper combination of select lines (true/complemented). A DEMUX is widely used for data distribution and as a decoder (when $D=1$).

Encoder and Priority Encoder

Encoder

An encoder is a combinational circuit that converts an active input line (one of $2^n$) into an $n$-bit binary code. It is the reverse of a decoder. For example, an 8-to-3 encoder has 8 inputs and 3 output lines.

A limitation of an ordinary encoder is that if two or more inputs are active at the same time, the output is invalid/ambiguous.

Priority Encoder

A priority encoder solves this problem by assigning a priority to each input. If multiple inputs are active simultaneously, it outputs the binary code of the highest-priority (usually highest-numbered) active input and ignores the others.

Example — 4-to-2 priority encoder (input $D_3$ has highest priority):

Here $x$ = don't care and V is a valid output bit (1 when at least one input is high). Output equations:

SOP vs POS

SOP (Sum of Products): a Boolean expression written as the OR (sum) of AND (product) terms. Each product term (minterm) corresponds to a row where the output is 1.

• Example: $F = A'B + AB' + AB$

POS (Product of Sums): a Boolean expression written as the AND (product) of OR (sum) terms. Each sum term (maxterm) corresponds to a row where the output is 0.

• Example: $F = (A+B)(A+B')$

Differences

Both represent the same function; one is the dual/complement-derived form of the other and either can be obtained from the truth table.

JK Flip-Flop and Race-Around Condition

Working of a JK Flip-Flop

The JK flip-flop is a refinement of the SR flip-flop that removes the forbidden ($S=R=1$) state. It has inputs J and K, a clock, and outputs $Q$ and $Q'$. Characteristic behaviour on the active clock edge:

Characteristic equation: $Q_{n+1} = J\,Q_n' + K'\,Q_n$.

The key advantage: the previously invalid state now produces a useful toggle action.

Race-Around Condition

In a level-triggered JK flip-flop, when $J=K=1$ and the clock pulse width is larger than the propagation delay of the flip-flop, the output keeps toggling repeatedly ($Q\to Q'\to Q\dots$) for as long as the clock stays high. This uncontrolled multiple toggling within one clock pulse is the race-around condition, and the final output state becomes uncertain.

Remedies

• Make the clock pulse width smaller than the propagation delay (impractical).
• Use edge-triggering, or a Master–Slave JK flip-flop, where the master accepts data while the clock is high and the slave updates the output only on the falling edge — so the output changes only once per clock pulse, eliminating the race-around condition.

Magnitude Comparator and 1-Bit Comparator

Magnitude Comparator

A magnitude comparator is a combinational circuit that compares two binary numbers $A$ and $B$ and produces three outputs indicating whether $A>B$, $A=B$, or $A<B$.

1-Bit Comparator

For two single-bit inputs $A$ and $B$, the truth table is:

Output equations

Circuit: the $A=B$ output is an XNOR gate, the $A>B$ output is an AND gate with $B$ inverted, and the $A<B$ output is an AND gate with $A$ inverted. These outputs are mutually exclusive (exactly one is 1 at a time).

Latch vs Flip-Flop

Both are 1-bit memory (bistable) elements, but they differ in how/when they respond to inputs.

• A latch is level-triggered — its output follows the input as long as the enable/control signal is at its active level (it is transparent during that level).
• A flip-flop is edge-triggered — its output changes only at the rising or falling edge of the clock, regardless of how long the clock stays high.

Comparison

In short, a flip-flop can be built from latches (e.g. master–slave or two latches in series); edge-triggering makes flip-flops better suited to synchronous sequential circuits.

Tri-State Logic

Tri-state (three-state) logic is a type of digital output that can take three states instead of the usual two:

1. Logic 0 (low)
2. Logic 1 (high)
3. High-impedance (Hi-Z) — the output is effectively disconnected from the bus, presenting very high impedance and neither driving high nor low.

Control

A tri-state buffer has a data input, an output, and an enable (E) control line:

• When E = 1 (active): output = input (normal buffer, logic 0 or 1).
• When E = 0 (disabled): output = high-impedance (Hi-Z).

Applications

• Bus systems: many devices share a common data bus; only one is enabled at a time while others are in Hi-Z, preventing conflicts.
• Used in microprocessors, memory chips, and bidirectional I/O ports.
• Allows wired bus sharing without additional multiplexing logic.