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

Conversion of 725.625

Split the number into integer part 725 and fractional part 0.625.

(a) Decimal to Binary

Integer part (repeated division by 2):

Reading remainders bottom-to-top: $725 = 1011010101_2$.

Fractional part (repeated multiplication by 2):

• $0.625 \times 2 = 1.25 \rightarrow 1$
• $0.25 \times 2 = 0.50 \rightarrow 0$
• $0.50 \times 2 = 1.00 \rightarrow 1$

So $0.625 = 0.101_2$.

$$725.625_{10} = 1011010101.101_2$$

(b) Decimal to Octal

Group the binary in 3 bits from the binary point:

001 011 010 101 . 101 = $1\,3\,2\,5\,.\,5$

$$725.625_{10} = 1325.5_8$$

(Check: $1\cdot512 + 3\cdot64 + 2\cdot8 + 5 = 725$; $5/8 = 0.625$.)

(c) Decimal to Hexadecimal

Group the binary in 4 bits from the binary point:

0010 1101 0101 . 1010 = $2\,D\,5\,.\,A$

$$725.625_{10} = 2D5.A_{16}$$

(Check: $2\cdot256 + 13\cdot16 + 5 = 725$; $A/16 = 10/16 = 0.625$.)

BCD Code

Binary Coded Decimal (BCD) represents each decimal digit by its 4-bit binary equivalent (8421 weighted code). Only the codes 0000–1001 are valid; 1010–1111 are unused.

Example: $725_{10}$ in BCD = 0111 0010 0101 (7 = 0111, 2 = 0010, 5 = 0101). Note this differs from pure binary.

Gray Code

Gray code is a non-weighted (reflected binary) code in which only one bit changes between two successive values, which minimizes errors in transmission and in mechanical encoders.

Conversion: $g_i = b_i \oplus b_{i+1}$ (MSB unchanged).

Example (binary → Gray):

For 0101 (binary): Gray = $0,\,0\oplus1,\,1\oplus0,\,0\oplus1 = 0111$.

De Morgan's Theorems

Theorem 1: The complement of a sum equals the product of complements.

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

Theorem 2: The complement of a product equals the sum of complements.

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

Proof by Truth Table (Theorem 1)

Columns $\overline{A+B}$ and $\bar{A}\bar{B}$ are identical, proving Theorem 1.

Proof by Truth Table (Theorem 2)

Columns $\overline{A\cdot B}$ and $\bar{A}+\bar{B}$ match, proving Theorem 2.

Simplification of F = A'B + AB' + AB using K-map

The three minterms are: $A'B = m_1$, $AB' = m_2$, $AB = m_3$.

2-variable K-map:

Grouping the cells:

• The bottom row (A=1) pair gives A.
• The right column (B=1) pair gives B.

$$\boxed{F = A + B}$$

(This is the OR function; only the input combination A=0, B=0 gives output 0.)

Logic Circuit

The simplified function $F = A + B$ is realized by a single 2-input OR gate with inputs A and B and output F. (Diagram: inputs A and B feed an OR gate whose output is F.)

Flip-Flop

A flip-flop is a bistable sequential logic element (1-bit memory cell) that stores a single binary digit. It has two stable states (0 and 1) and changes state in response to control inputs, usually synchronized by a clock pulse. It is the basic building block of registers and counters.

(a) SR Flip-Flop

Inputs S (Set) and R (Reset). The condition S=R=1 is forbidden (invalid/indeterminate).

Characteristic equation: $Q(t+1) = S + \bar{R}\,Q$, with constraint $S \cdot R = 0$.

(b) JK Flip-Flop

Refines the SR flip-flop: the forbidden state J=K=1 is defined as toggle.

Characteristic equation: $Q(t+1) = J\bar{Q} + \bar{K}Q$.

(c) D Flip-Flop

Single data input D; output simply follows the input at the clock edge. Used for data storage and delay.

Characteristic equation: $Q(t+1) = D$.

(d) T Flip-Flop

Single input T (Toggle); obtained by tying J=K together in a JK flip-flop.

Characteristic equation: $Q(t+1) = T \oplus Q = T\bar{Q} + \bar{T}Q$.

T flip-flops are widely used in counters.

Let $A = 1101_2 = 13$ and $B = 1011_2 = 11$ (using a 5-bit signed representation to hold the carry/sign).

Binary Addition

   1101
 + 1011
 -------
  11000

Step by step: $1+1=10$ (write 0, carry 1); $0+1+1=10$ (0, carry 1); $1+0+1=10$ (0, carry 1); $1+1+1=11$ (1, carry 1).

$$1101 + 1011 = 11000_2 = 24_{10}$$

(which equals $13 + 11 = 24$). ✓

Binary Subtraction using 2's Complement (A − B = 13 − 11 = 2)

Use 5 bits: $A = 01101$, $B = 01011$.

Step 1 — 2's complement of B:

• 1's complement of $01011$ = $10100$
• Add 1: $10100 + 1 = 10101$

Step 2 — Add A and the 2's complement of B:

   01101
 + 10101
 --------
  100010

Step 3 — Discard the end carry (the leftmost 1): result = $00010$.

A positive result (carry out = 1, discarded) means the answer is positive:

$$1101 - 1011 = 00010_2 = 2_{10}$$

✓ (since $13 - 11 = 2$).

Half Adder

A half adder adds two single-bit binary numbers A and B, producing a Sum (S) and a Carry (C). It cannot accept a carry-in from a previous stage.

Equations: $S = A \oplus B$, $\;C = A \cdot B$.

Circuit: one XOR gate (Sum) and one AND gate (Carry).

Full Adder

A full adder adds three bits: A, B and a carry-in $C_{in}$, producing Sum (S) and Carry-out ($C_{out}$). It can be cascaded to add multi-bit numbers.

Equations: $S = A \oplus B \oplus C_{in}$, $\;C_{out} = AB + (A \oplus B)C_{in}$.

Circuit: A full adder can be built from two half adders and one OR gate.

Multiplexer

A multiplexer (MUX) is a combinational circuit that selects one of several input data lines and routes it to a single output line. With $n$ select lines it can choose among $2^n$ inputs; it is also called a data selector and performs many-to-one (parallel-to-serial) routing.

4-to-1 Multiplexer

It has 4 data inputs ($I_0, I_1, I_2, I_3$), 2 select lines ($S_1, S_0$) and 1 output Y.

Selection table:

Boolean expression:

$$Y = \bar{S_1}\bar{S_0}I_0 + \bar{S_1}S_0 I_1 + S_1\bar{S_0}I_2 + S_1 S_0 I_3$$

Block/Logic diagram (described): Four 3-input AND gates each receive one data input plus the appropriate combination of $S_1, S_0$ (true or complemented via NOT gates). The four AND-gate outputs feed a single OR gate whose output is Y. Externally it is drawn as a trapezoidal block with inputs $I_0$–$I_3$ on the left, select lines $S_1, S_0$ at the bottom, and output Y on the right.

Combinational vs Sequential Circuits

In short: a combinational circuit produces an output that is a pure function of its current inputs, whereas a sequential circuit's output depends on both current inputs and the stored internal state, requiring memory and (typically) a clock.

Implementing F(A,B,C) = Σ(1,3,5,7)

Step 1 — Sum-of-products from minterms:

Notice that C = 1 in every minterm where F = 1.

Step 2 — Simplify (K-map):

The entire C=1 column groups together, eliminating A and B:

$$\boxed{F = C}$$

Step 3 — Implementation with basic gates:

The minimized function is simply $F = C$, so the output equals input C directly — no gate is required (a plain wire/buffer from C to F).

If the question expects the un-simplified form, the canonical SOP is:

$$F = \bar{A}\bar{B}C + \bar{A}BC + A\bar{B}C + ABC$$

which uses three NOT gates, four 3-input AND gates and one 4-input OR gate. However, the simplified and correct realization is F = C (a single connection/buffer), demonstrating the value of minimization.

Decoder

A decoder is a combinational circuit that converts an $n$-bit coded input into a maximum of $2^n$ unique output lines, with exactly one output active (HIGH) for each input combination and the rest inactive. It performs the reverse operation of an encoder and is used in memory address selection, data demultiplexing and code conversion.

3-to-8 Line Decoder

It has 3 inputs (A, B, C), 8 outputs ($D_0$–$D_7$), and (usually) an enable line. For each 3-bit input only the corresponding output goes HIGH.

Truth table (Enable = 1):

Output equations (active-high):

$$D_0 = \bar{A}\bar{B}\bar{C},\quad D_1 = \bar{A}\bar{B}C,\quad D_2 = \bar{A}B\bar{C},\quad D_3 = \bar{A}BC,$$ $$D_4 = A\bar{B}\bar{C},\quad D_5 = A\bar{B}C,\quad D_6 = AB\bar{C},\quad D_7 = ABC.$$

Circuit (described): three inputs A, B, C and their complements (via NOT gates) feed eight 3-input AND gates; each AND gate produces one output line, so the gate that matches the applied input combination drives its output HIGH.

Register

A register is a group of flip-flops (n flip-flops store an n-bit word) used to store binary data temporarily inside a digital system. Each flip-flop stores one bit, and all share a common clock. Registers are used for data storage and data movement in CPUs.

Shift Register

A shift register is a register that, in addition to storing data, can shift its contents left or right by one bit position on each clock pulse. It is built by cascading flip-flops so that the output of one feeds the input of the next.

Types (by data entry/exit)

1. SISO – Serial-In Serial-Out
2. SIPO – Serial-In Parallel-Out
3. PISO – Parallel-In Serial-Out
4. PIPO – Parallel-In Parallel-Out
5. Bidirectional / Universal shift register (shifts both directions, with parallel load)

Working (4-bit SISO example)

Four D flip-flops (FF0→FF1→FF2→FF3) are connected in series. Data is applied serially at the input of FF0. On every clock pulse each bit moves one stage to the right, so after 4 clock pulses a 4-bit word has been fully loaded; it then appears serially at the output of FF3.

Applications: serial-to-parallel and parallel-to-serial conversion, temporary data storage, delay lines, and in counters (e.g. ring and Johnson counters).

Ripple (Asynchronous) Counter

A ripple counter is an asynchronous sequential counter in which the flip-flops are not clocked simultaneously. Only the first (LSB) flip-flop receives the external clock; each subsequent flip-flop is triggered by the output of the preceding one. The clock effect thus ripples through the chain.

Construction (3-bit up-counter example)

• Three JK (or T) flip-flops connected in toggle mode ($J=K=1$, or $T=1$).
• External clock drives FF0 (LSB).
• $Q_0$ drives the clock of FF1, and $Q_1$ drives the clock of FF2 (MSB).

Working

Each flip-flop toggles its output on the falling (or rising) edge of its clock input. FF0 toggles on every input clock pulse; FF1 toggles when $Q_0$ changes from 1→0; FF2 toggles when $Q_1$ changes from 1→0. This makes the outputs $Q_2 Q_1 Q_0$ count in binary 000, 001, 010, …, 111 and then roll over.

Count sequence (3-bit): 000 → 001 → 010 → 011 → 100 → 101 → 110 → 111 → 000 …

Characteristics

• Advantage: simple, requires minimal hardware.
• Disadvantage: propagation delay accumulates (ripples), so it is slower and can produce transient glitches; not suitable for high-speed applications. Synchronous counters overcome this by clocking all flip-flops together.

Universal Gates

NAND and NOR gates are called universal gates because any other logic gate (NOT, AND, OR, XOR, etc.) — and hence any digital circuit — can be built using only NAND gates or only NOR gates. This reduces inventory and simplifies IC fabrication.

NAND Gate

Output = $\overline{A \cdot B}$ (AND followed by NOT). Output is 0 only when all inputs are 1.

Realizing other gates with NAND:

• NOT: tie both inputs together → $\overline{A \cdot A} = \bar{A}$
• AND: NAND followed by a NAND-inverter → $\overline{\overline{A\cdot B}} = A\cdot B$
• OR: invert both inputs, then NAND → $\overline{\bar{A}\cdot \bar{B}} = A + B$ (by De Morgan)

NOR Gate

Output = $\overline{A + B}$ (OR followed by NOT). Output is 1 only when all inputs are 0.

Realizing other gates with NOR:

• NOT: tie both inputs → $\overline{A + A} = \bar{A}$
• OR: NOR followed by a NOR-inverter → $A + B$
• AND: invert both inputs, then NOR → $\overline{\bar{A} + \bar{B}} = A\cdot B$ (by De Morgan)

Significance: because the entire set of Boolean functions is functionally complete using NAND alone or NOR alone, digital ICs are economically mass-produced using a single gate type.