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

Multiplexer (MUX)

A multiplexer is a combinational circuit that selects one of $2^n$ input data lines and routes it to a single output line, controlled by $n$ select (control) lines. It is also called a data selector because the binary value applied to the select lines decides which input is connected to the output. A MUX performs parallel-to-serial conversion and can also implement any Boolean function.

4-to-1 Multiplexer

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$.

Selection table:

Boolean expression:

Logic diagram (described): Four 3-input AND gates, each fed by one data input and the appropriate combination of $S_1, S_0$ (true/complemented via inverters). The four AND-gate outputs feed a single 4-input OR gate whose output is $Y$.

Implementing $F(A,B,C)=\sum(1,2,6,7)$ with an 8-to-1 MUX

An 8-to-1 MUX has 8 data inputs $I_0\ldots I_7$ and 3 select lines. Connect the three variables directly to the select lines:

The MUX passes input $I_i$ whenever the minterm $i$ is selected, so set each data line to 1 if its minterm is present in $F$, else 0:

Connections: $I_1 = I_2 = I_6 = I_7 = 1$ (connect to logic HIGH) and $I_0 = I_3 = I_4 = I_5 = 0$ (connect to logic LOW). The output of the MUX then equals $F(A,B,C)=\sum(1,2,6,7)$.

Ripple Counter

A ripple counter (also called an asynchronous counter) is a counter in which only the first flip-flop is clocked by the external clock, and each subsequent flip-flop is clocked by the output of the preceding flip-flop. Because the clock 'ripples' through the chain from one stage to the next, the flip-flops do not change state simultaneously; this propagation gives the counter its name.

4-bit Binary Ripple Counter

It uses four T flip-flops (or JK flip-flops with $J=K=1$) connected in cascade. All flip-flops are held in toggle mode.

Construction (negative-edge triggered, up counter):

• External clock $\to$ clock of FF0 (output $Q_0$, LSB).
• $Q_0 \to$ clock of FF1 (output $Q_1$).
• $Q_1 \to$ clock of FF2 (output $Q_2$).
• $Q_2 \to$ clock of FF3 (output $Q_3$, MSB).

Working: Each flip-flop toggles on the falling edge of its clock. FF0 toggles on every clock pulse (divide-by-2). FF1 toggles each time $Q_0$ falls (1$\to$0), i.e. every 2 pulses. Similarly $Q_2$ toggles every 4 pulses and $Q_3$ every 8. The outputs $Q_3Q_2Q_1Q_0$ thus count in binary from $0000$ to $1111$ (0 to 15) and then roll over.

Count sequence:

Timing diagram (described): Draw four waveforms aligned to the clock. $Q_0$ is a square wave at half the clock frequency, $Q_1$ at one-quarter, $Q_2$ at one-eighth, and $Q_3$ at one-sixteenth. Each output transitions only on the falling edge of the waveform above it, so successive transitions appear slightly delayed (the ripple delay).

Note: Because the clock ripples through the stages, the total settling delay is $n \times t_{pd}$, which limits the maximum counting speed compared to a synchronous counter.

3-to-8 Line Decoder

A decoder is a combinational circuit that converts an $n$-bit binary input into one of $2^n$ unique output lines. A 3-to-8 decoder has 3 inputs ($A, B, C$) and 8 outputs ($D_0\ldots D_7$). For each input combination exactly one output is active (HIGH for active-high), and that output corresponds to the minterm of the inputs.

Output equations (active-high):

Truth table:

Logic diagram (described): Three input lines $A,B,C$ each pass through an inverter to provide both true and complemented forms. Eight 3-input AND gates each take a distinct combination of the (true/complemented) inputs; each AND gate produces one output $D_i$ equal to its minterm.

Implementing a Full Adder using the 3-to-8 Decoder

For a full adder with inputs $A, B, C_{in}$:

Apply $A, B, C_{in}$ to the decoder select inputs (as $A,B,C$). Each decoder output $D_i$ equals minterm $i$. OR together the minterm outputs belonging to each function:

So connect $D_1, D_2, D_4, D_7$ to a 4-input OR gate to obtain Sum, and $D_3, D_5, D_6, D_7$ to another 4-input OR gate to obtain Carry-out. This realizes a complete full adder using one 3-to-8 decoder and two OR gates.

Convert $(1011.011)_2$ to Decimal and Hexadecimal

To Decimal: weight each bit by its positional power of 2.

Integer part: $1\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = 8+0+2+1 = 11$

Fractional part: $0\cdot2^{-1} + 1\cdot2^{-2} + 1\cdot2^{-3} = 0 + 0.25 + 0.125 = 0.375$

To Hexadecimal: group the bits into fours from the binary point, padding with zeros.

Integer part: $1011 = B_{16}$

Fractional part: $011 \to 0110$ (pad right) $= 6_{16}$

Final answers: $(1011.011)_2 = (11.375)_{10} = (B.6)_{16}$.

Absorption Law of Boolean Algebra

Statement: The absorption law has two dual forms:

A variable 'absorbs' the term that contains it together with another variable.

Proof of (i): $A + AB = A$

Proof of (ii): $A(A+B) = A$

Hence both forms of the absorption law are proved.

Simplify $F(A,B,C)=\sum(0,2,4,5,6)$ using a K-map

Three-variable K-map (rows = $A$; columns = $BC$ in Gray order 00, 01, 11, 10):

Grouping:

• Group 1 (quad): minterms 0, 2, 4, 6 — the two outer columns ($BC=00$ and $BC=10$). Here $C=0$ in all four cells, so this group simplifies to $\bar C$.
• Group 2 (pair): minterms 4, 5 — bottom row, columns $00$ and $01$. Here $A=1, B=0$, so this group gives $A\bar B$.

Simplified expression:

This is the minimal Sum-of-Products form (two product terms).

Full Adder

A full adder is a combinational circuit that adds three 1-bit inputs — the two bits to be added ($A$, $B$) and a carry-in ($C_{in}$) from the previous stage — and produces two outputs: the Sum ($S$) and the Carry-out ($C_{out}$).

Truth table:

Boolean expressions (simplified):

Working / circuit (described): A full adder is built from two half adders and an OR gate. The first half adder adds $A$ and $B$ giving a partial sum $A\oplus B$ and a carry $AB$. The second half adder adds this partial sum to $C_{in}$, giving the final $S = A\oplus B\oplus C_{in}$ and a second carry $(A\oplus B)C_{in}$. The two carries are OR-ed to give $C_{out}$. The sum is HIGH when an odd number of inputs are 1, and the carry is HIGH when two or more inputs are 1.

Realizing NOT, AND, OR using only NOR gates

The NOR gate is a universal gate; any logic function can be built from NOR gates alone. NOR is defined as $\overline{A+B}$.

1. NOT gate — tie both inputs of a NOR gate together (or tie one input to 0):

So a NOR gate with both inputs $= A$ produces $\bar A$.

2. OR gate — OR is the complement of NOR, so feed the NOR output into a NOR-inverter:

Use one NOR gate to get $\overline{A+B}$, then a second NOR (as inverter) to get $A+B$. (2 NOR gates)

3. AND gate — using De Morgan's theorem $A\cdot B = \overline{\bar A + \bar B}$:

• Invert $A$ with a NOR-inverter $\to \bar A$
• Invert $B$ with a NOR-inverter $\to \bar B$
• Feed $\bar A$ and $\bar B$ into a NOR gate: $\overline{\bar A + \bar B} = A\cdot B$

Thus AND requires 3 NOR gates (two as inverters, one as the final NOR).

Summary: NOT = 1 NOR, OR = 2 NOR, AND = 3 NOR — proving NOR is a universal gate.

Combinational vs. Sequential Logic Circuits

In short: a combinational circuit produces an output that is purely a function of its current inputs, whereas a sequential circuit also stores information, so its output depends on the sequence of past inputs as well as the present ones.

D (Data / Delay) Flip-Flop

The D flip-flop has a single data input $D$ and a clock input. On the active clock edge it transfers the value at $D$ to the output $Q$; otherwise $Q$ holds its previous value. It is widely used to store one bit of data and to eliminate the invalid (forbidden) state of the SR flip-flop.

Construction: It is obtained from an SR (or JK) flip-flop by connecting $D$ to $S$ (or $J$) and $\bar D$ to $R$ (or $K$) through an inverter, so $S$ and $R$ can never both be 1.

Characteristic / truth table:

Characteristic equation:

Working: When the clock edge arrives, if $D=0$ the flip-flop resets ($Q=0$); if $D=1$ it sets ($Q=1$). Between clock edges the output is latched and unaffected by changes on $D$. Because the output simply follows the input one clock later, it is also called a delay flip-flop. It is commonly used in registers, data buffers, and shift registers.

Synchronous Mod-4 Up Counter

A mod-4 counter counts through 4 states ($0 \to 1 \to 2 \to 3 \to 0$), requiring 2 flip-flops ($2^2 = 4$). In a synchronous counter all flip-flops share the same clock, so they change state simultaneously. We use two JK flip-flops ($Q_1$ = MSB, $Q_0$ = LSB).

State / count sequence:

Flip-flop inputs (from JK excitation):

• $Q_0$ must toggle on every clock pulse $\Rightarrow J_0 = K_0 = 1$.
• $Q_1$ must toggle only when $Q_0 = 1 \Rightarrow J_1 = K_1 = Q_0$.

Design equations:

Circuit (described): Both flip-flops are clocked by the common clock. FF0's $J_0,K_0$ are tied to logic 1 (so $Q_0$ toggles every pulse). FF0's output $Q_0$ is connected to both $J_1$ and $K_1$ of FF1, so $Q_1$ toggles only when $Q_0=1$. The outputs $Q_1Q_0$ then count $00\to01\to10\to11\to00\ldots$, giving a synchronous mod-4 up counter.

Serial-In Serial-Out (SISO) Shift Register

A shift register is a group of cascaded flip-flops used to store and move binary data. In a Serial-In Serial-Out (SISO) register, data is entered one bit at a time through a single serial input and is read out one bit at a time from a single serial output.

Construction: It consists of $n$ D flip-flops connected in cascade, all driven by a common clock. The serial data is applied to the $D$ input of the first flip-flop; the output $Q$ of each flip-flop feeds the $D$ input of the next stage.

Working: On each clock pulse, the stored bits shift by one position towards the output. To load an $n$-bit word and read it back, $n$ clock pulses are needed to shift the data in and a further $n$ pulses to shift it out. For example, in a 4-bit register, the data byte $1011$ entered serially appears at the output after the appropriate number of clock pulses, one bit per clock.

Key points:

• Requires $n$ clock pulses to load/unload $n$ bits (slowest data transfer mode).
• Acts as a time-delay device, delaying data by $n$ clock periods.
• Can shift left or right depending on the connection direction.
• Applications: serial data transfer, temporary data storage, and time delay.