GTU BE03000071 Digital Fundamentals Winter 2025 Solved Paper & Solutions

Gray code is used in shaft encoders and K-maps.

Given: $F = x\bar y\bar z + yz + x\bar z$.

Step 1: the first and the third terms have the common factor $x\bar z$:

Step 2: so

Check by the truth table: both the original and the simplified function are 1 for $xyz$ = 100, 110, 011 and 111, and 0 for the others.

Circuit: an inverter on $z$, two AND gates and one OR gate.

These are the main characteristics of digital ICs. The values are for the standard TTL family.

1. Threshold voltage: the input voltage at which the output of the gate changes its state. For TTL it is about 1.4 V, and for CMOS it is about half of the supply voltage.
2. Propagation delay ($t_{pd}$): the time taken by the output to change after the input changes, measured at the 50% points. It is $t_{PLH}$ (low to high) and $t_{PHL}$ (high to low), and the average is taken. For standard TTL it is about 10 ns.
3. Noise margin: the largest noise voltage that the input can take without a wrong output. $NM_H = V_{OH(min)} - V_{IH(min)} = 2.4 - 2.0 = 0.4$ V and $NM_L = V_{IL(max)} - V_{OL(max)} = 0.8 - 0.4 = 0.4$ V.
4. Power dissipation: the power taken by the gate from the supply, $P = V_{CC}\times I_{CC}$. Standard TTL takes about 10 mW for a gate. CMOS takes very little power when it is not switching.
5. Fan-in: the number of inputs of a gate. A 3-input NAND has a fan-in of 3.
6. Fan-out: the number of gate inputs that one output can drive with no loss of the logic levels. Standard TTL has a fan-out of 10.
7. Speed-power product: the product of the propagation delay and the power dissipation, in picojoules (pJ). It is a measure of the quality of a logic family. For standard TTL, $10\ \text{ns}\times 10\ \text{mW} = 100$ pJ. A lower value is better.

A decoder can be used as a demultiplexer, with the enable input as the data input.

Sum of Products (SOP): a Boolean expression written as an OR of AND terms (product terms). The product terms that have all the variables are called minterms. The function is 1 for the given minterms.

Example: $F = AB + \bar A C$. The canonical SOP for 3 variables is $F = \sum m(1, 3, 6, 7)$, which is the sum of the minterms $\bar A\bar BC + \bar ABC + AB\bar C + ABC$.

Product of Sums (POS): an expression written as an AND of OR terms (sum terms). The sum terms that have all the variables are maxterms. The function is 0 for the given maxterms.

Example: $F = (A + B)(\bar A + C)$. The canonical POS is $F = \prod M(0, 2, 4, 5)$, which is the product of the maxterms $(A + B + C)(A + \bar B + C)(\bar A + B + C)(\bar A + B + \bar C)$.

A function can be written either way, and they are equal. SOP uses AND-OR (or NAND-NAND) gates, and POS uses OR-AND (or NOR-NOR) gates. In a canonical form, each term has all the variables.

Given: $F(A,B,C,D) = \sum m(0, 1, 3, 4, 7, 9, 11) + d(8, 10, 15)$.

• Quad of $m_1, m_3, m_9, m_{11}$ (columns 01 and 11 in rows 00 and 10): $B = 0$ and $D = 1$, so it gives $\bar BD$.
• Quad of $m_3, m_7, m_{11}, m_{15}$ (the column 11, rows 00, 01, 10, 11, with the don't care $m_{15}$): $C = 1$ and $D = 1$, so it gives $CD$.
• Pair of $m_0, m_4$ (the column 00 in rows 00 and 01): $A = 0$, $C = 0$ and $D = 0$, so it gives $\bar A\bar C\bar D$.

The don't care $m_{15}$ is used in the second group, and the don't cares $m_8$ and $m_{10}$ are not needed.

Gate count: 3 first level NAND gates (one 2-input for $\bar BD$, one 2-input for $CD$, one 3-input for $\bar A\bar C\bar D$), one 3-input NAND at the output, and 4 NAND gates used as inverters for $\bar A$, $\bar B$, $\bar C$ and $\bar D$.

Check: the function is 1 for the minterms 0, 1, 3, 4, 7, 9 and 11, and 0 for the other required minterms 2, 5, 6, 12, 13 and 14.

A look-ahead carry adder finds all the carries at the same time from the inputs, so it does not wait for the carry to ripple through each stage. This makes the addition much faster than in a ripple carry adder.

For each stage define generate $G_i = A_iB_i$ and propagate $P_i = A_i \oplus B_i$. Then the carry is

Expanding it: $C_1 = G_0 + P_0C_0$, $C_2 = G_1 + P_1G_0 + P_1P_0C_0$ and $C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$.

All these are two-level AND-OR circuits, so they have the same delay, and the sum is $S_i = P_i \oplus C_i$.

Given: $F(w,x,y,z) = \sum m(1, 3, 4, 5, 12, 13, 15)$. A 8 x 1 multiplexer has 3 select lines, so the variables $w, x, y$ are the select inputs ($w$ is the MSB), and the variable $z$ is used for the data inputs.

For each select combination $wxy$, look at the two minterms $2i$ (with $z = 0$) and $2i + 1$ (with $z = 1$):

Connections: $I_0 = I_1 = I_7 = z$, $I_2 = I_6 = 1$ (logic 1), $I_3 = I_4 = I_5 = 0$ (ground). The select lines are $S_2 = w$, $S_1 = x$ and $S_0 = y$.

A D (data) flip-flop has one data input $D$ and a clock. At the active clock edge, the output $Q$ takes the value of $D$. It removes the forbidden state of the SR flip-flop by making $R = \bar S$, so the two inputs are never 1 together. It is also called a delay flip-flop, as it delays the data by one clock pulse.

Characteristic table (the next state for a given $D$ and the present state $Q_n$):

Characteristic equation: $Q_{n+1} = D$.

Excitation table (the input $D$ needed for a change of state from $Q_n$ to $Q_{n+1}$):

Working:

1. When the clock is active and $D = 1$, the flip-flop is set, so $Q = 1$.
2. When the clock is active and $D = 0$, it is reset, so $Q = 0$.
3. Between the clock edges the output does not change, whatever the change in $D$.

Why it is used: the D flip-flop is the simplest to use, as it has only one data input and no illegal input combination. Four D flip-flops with a common clock make a 4-bit register, and a chain of D flip-flops makes a shift register.

Uses: data storage (registers), shift registers, delay circuits and as a one-bit memory.

A D flip-flop has $Q_{n+1} = D$, and a T flip-flop has $Q_{n+1} = T \oplus Q_n$. To make a D flip-flop work as a T flip-flop, the input $D$ must be

So an XOR gate is put before the D input. The inputs of the XOR are $T$ and the present output $Q$ (fed back). When $T = 0$, $D = Q$ and the state holds. When $T = 1$, $D = \bar Q$ and the output toggles at each clock pulse.

Mod-5 counter counts 0, 1, 2, 3, 4 and then returns to 0. It needs 3 flip-flops ($2^3 = 8 \ge 5$). The state is $Q_2Q_1Q_0$. The unused states 5, 6 and 7 are don't cares.

Self-starting check: from the unused states, 101 goes to 010, 110 goes to 010 and 111 goes to 000, so the counter returns to the valid sequence by itself.

Content Addressable Memory (CAM) is a memory in which data is found by its content, not by its address. The data to be searched is given as the input, and the CAM compares it with all the stored words at the same time (in parallel). It gives the address of the word that matches (or tells if it is there).

It is also called an associative memory. Each cell has a comparison circuit. The search is very fast (one clock cycle), but it is more costly and takes more power than a RAM. It is used in cache tag memory, network routers and the TLB.

A 2K x 8 ROM has $2K = 2048 = 2^{11}$ words, and each word has 8 bits.

• Address lines: 11 ($2^{11} = 2048$).
• Data (output) lines: 8.
• Storage: $2048\times 8 = 16384$ bits = 16 Kbits.

Internal representation:

1. The address decoder takes the 11 address bits and makes one of the 2048 word lines high.
2. The ROM array has 2048 rows and 8 columns of cells. Each cell stores one bit by a connection (a diode or a transistor), or no connection.
3. The selected word line puts the 8 stored bits on the 8 output lines.
4. Chip select (CS) and output enable (OE) control the output buffers, which give the data on the output lines only when the chip is selected.

In a real chip, the decoder is split into a row decoder and a column multiplexer to save area.

Given: $F_1 = \sum m(0, 1, 2, 4)$ and $F_2 = \sum m(0, 5, 6, 7)$. The PLA has 3 inputs ($A, B, C$), 4 product terms and 2 outputs.

$F_1 = \bar A\bar B + \bar A\bar C + \bar B\bar C$ has 3 product terms. But the complement is simpler:

Output $F_1$: the OR of terms 1, 2 and 3 is complemented (the output XOR is programmed with 1). Output $F_2$: the OR of terms 1, 2 and 4 (the output XOR is programmed with 0).

Check: all 8 input combinations were tested, and $F_1$ and $F_2$ give the required minterms.