GTU BE03000071 Digital Fundamentals Summer 2026 Solved Paper & Solutions

XOR (Exclusive OR) gate: the output is 1 when the inputs are different.

XNOR (Exclusive NOR) gate: the output is 1 when the inputs are the same. It is the complement of XOR.

Uses: XOR in adders, parity generators and comparators; XNOR as an equality detector.

Decimal to hexadecimal

Method: divide the number repeatedly by 16 and write the remainders; read them from bottom to top. Remainders 10 to 15 are written A to F.

Example: $(450)_{10}$

Check: $1 \times 256 + 12 \times 16 + 2 = 450$.

Hexadecimal to octal

Method: convert each hex digit to 4-bit binary, then regroup the bits in groups of 3 from the right, and write each group as an octal digit.

Example: $(1C2)_{16}$

Regroup in threes from the right: $000\;111\;000\;010$

Check: $7 \times 64 + 0 \times 8 + 2 = 450$, the same number. Going through binary works because 16 and 8 are both powers of 2: one hex digit is exactly 4 bits and one octal digit is exactly 3 bits.

An error correcting code adds extra (redundant) bits to the data so that the receiver can not only detect an error but also find and correct it. The most common is the Hamming code.

Parity bits needed

For $m$ data bits, the number of parity bits $p$ must satisfy $2^p \ge m + p + 1$. For 4 data bits, $p = 3$, giving a 7-bit code.

Positions

Parity bits are at positions 1, 2 and 4 (powers of 2):

• P1 checks positions 1, 3, 5, 7.
• P2 checks positions 2, 3, 6, 7.
• P4 checks positions 4, 5, 6, 7.

Example: send data 1011 (even parity)

$D_1 D_2 D_3 D_4 = 1\,0\,1\,1$.

• P1: positions 3, 5, 7 = 1, 0, 1 (two 1s), so P1 = 0.
• P2: positions 3, 6, 7 = 1, 1, 1 (three 1s), so P2 = 1.
• P4: positions 5, 6, 7 = 0, 1, 1 (two 1s), so P4 = 0.

Code sent: 0 1 1 0 0 1 1

Correcting an error

The receiver gets 0110001 (bit 6 changed). It recomputes the checks:

• $C_1$ (1, 3, 5, 7) = 0, 1, 0, 1: even, so $C_1 = 0$.
• $C_2$ (2, 3, 6, 7) = 1, 1, 0, 1: odd, so $C_2 = 1$.
• $C_4$ (4, 5, 6, 7) = 0, 0, 0, 1: odd, so $C_4 = 1$.

Error position $= C_4C_2C_1 = 110_2 = 6$. Bit 6 is flipped back to 1, giving 0110011, and the data 1011 is recovered. If all checks are 0, there is no error.

Other codes

• Parity bit: detects a single error but cannot correct it.
• SEC-DED Hamming code: an extra overall parity bit also detects double errors.
• CRC and Reed-Solomon codes: used in networks, CDs and QR codes.

In Gray code, only one bit changes between two successive values.

• 1 bit: 0, 1
• 2 bit: 00, 01, 11, 10
• 3 bit: 000, 001, 011, 010, 110, 111, 101, 100
• 4 bit: 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000

Rule (reflection): each list is made by writing the previous list, then the same list in reverse order, and adding a 0 before the first half and a 1 before the second half.

A 4-variable Karnaugh map has $2^4 = 16$ cells, one for each minterm of A, B, C, D. Rows are AB and columns are CD, both in Gray code order (00, 01, 11, 10), so adjacent cells differ by only one variable.

Example: simplify $F = \sum m(0, 2, 5, 7, 8, 10, 13, 15)$.

Groups:

• Four corners (0, 2, 8, 10): B = 0 and D = 0, giving $\overline{B}\,\overline{D}$. Corners are adjacent because the map wraps around.
• Centre quad (5, 7, 13, 15): B = 1 and D = 1, giving $BD$.

Rules: group 1s in sizes of 1, 2, 4, 8 or 16; make groups as large as possible; use as few groups as possible; groups may overlap and wrap around the edges.

Excess-3 code is obtained by adding 3 (0011) to the BCD code. The converter has 4 inputs A B C D (BCD, A is the MSB) and 4 outputs W X Y Z (Excess-3).

Truth table

Inputs 1010 to 1111 are not valid BCD, so they are don't cares (X).

K-map simplification

W = Σm(5, 6, 7, 8, 9) + d(10 to 15):

X = Σm(1, 2, 3, 4, 9) + d(10 to 15):

Y = Σm(0, 3, 4, 7, 8) + d(10 to 15):

Z = Σm(0, 2, 4, 6, 8) + d(10 to 15):

Circuit

• W: two AND gates (BC, BD) and a 3-input OR gate with A.
• X: AND gates for $\overline{B}C$, $\overline{B}D$ and $B\overline{C}\,\overline{D}$, and a 3-input OR gate.
• Y: an XNOR gate of C and D.
• Z: an inverter on D.

Check: for BCD 0110 (6): $W = 0 + 1 + 0 = 1$, $X = 0 + 0 + 0 = 0$, $Y = \overline{1 \oplus 0} = 0$, $Z = 1$, so WXYZ = 1001 = 9 = 6 + 3. Correct.

Use: Excess-3 is a self-complementing code, which makes decimal subtraction easy.

A 2-bit magnitude comparator compares $A = A_1A_0$ with $B = B_1B_0$ and gives three outputs. Let $x_i = \overline{A_i \oplus B_i}$ (1 when the bits are equal).

The MSBs are compared first; only if they are equal do the LSBs decide. Example: A = 10, B = 01: $A_1\overline{B_1} = 1$, so $A > B$. It needs XNOR gates for $x_1$, $x_0$ and AND-OR gates for the outputs.

Half subtractor

Subtracts two bits, $A - B$, giving the difference D and the borrow $B_o$.

Circuit: one XOR gate, one NOT gate and one AND gate.

Full subtractor

Subtracts three bits, $A - B - B_{in}$, where $B_{in}$ is the borrow from the previous stage.

Here a borrow is needed when A is smaller than what is subtracted from it. A full subtractor can be made from two half subtractors and an OR gate: the first finds $A - B$, the second subtracts $B_{in}$, and the OR combines their borrows. Full subtractors in a chain subtract multi-bit numbers.

A synchronous counter has one common clock for all flip-flops, so they change state at the same time. A 3-bit up counter counts 000 to 111 (0 to 7) and repeats.

Design with T flip-flops

A T flip-flop toggles when T = 1. In binary counting:

• Q0 toggles on every clock: $T_0 = 1$.
• Q1 toggles when Q0 = 1: $T_1 = Q_0$.
• Q2 toggles when Q1 = Q0 = 1: $T_2 = Q_1Q_0$.

From the table: $T_0 = 1$, $T_1 = Q_0$, $T_2 = Q_1Q_0$.

Circuit

With JK flip-flops, tie J = K: $J_0 = K_0 = 1$, $J_1 = K_1 = Q_0$, $J_2 = K_2 = Q_1Q_0$.

Timing

On each clock edge, all flip-flops that should change do so together. The outputs go 000, 001, 010, ..., 111, 000. Q0 has half the clock frequency, Q1 a quarter and Q2 an eighth.

Features

• Fast: the delay is one flip-flop delay plus one AND gate, not a ripple through all stages. So the maximum clock frequency does not fall much as more bits are added.
• No glitches when the outputs are decoded, since all bits change at the same instant.
• Needs more gates than a ripple counter as the number of bits grows.

A D (Data or Delay) flip-flop has one data input D and a clock. On the active clock edge, the output Q takes the value of D, and holds it until the next edge.

Construction: it is made from an SR (or JK) flip-flop with an inverter, so that $S = D$ and $R = \overline{D}$. This removes the invalid state S = R = 1 of the SR flip-flop.

Truth table:

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

Uses: registers and memory (each flip-flop stores one bit), shift registers, and delay of a signal by one clock period.

A 2-bit ripple down counter counts downward: 3, 2, 1, 0, 3, ... (11, 10, 01, 00). It uses 2 flip-flops in asynchronous (ripple) mode.

Circuit (negative edge triggered T flip-flops)

• Both flip-flops have T = 1 (or J = K = 1), so they toggle on each active clock edge.
• The external clock drives FF0.
• For a down counter with negative edge triggered flip-flops, FF1 is clocked by $\overline{Q_0}$ (not by $Q_0$, as in an up counter).

Working

• FF0 toggles on every falling clock edge.
• FF1 toggles when $\overline{Q_0}$ goes from 1 to 0, which is when Q0 goes from 0 to 1.

On clock 1, Q0 goes 0 → 1, so $\overline{Q_0}$ falls and FF1 also toggles (0 → 1), giving 11. On clock 2, Q0 goes 1 → 0 ($\overline{Q_0}$ rises, no trigger), giving 10. And so on.

Waveforms

Other ways

• Positive edge triggered flip-flops: clock FF1 with Q0 instead.
• An up/down counter uses a control signal and gates to choose between $Q_0$ and $\overline{Q_0}$.

Delay: the change of Q1 comes after Q0 changes, so the delays ripple; for 2 bits this is small.

SRAM is used where speed matters; DRAM where large capacity is needed at low cost.

A Content Addressable Memory (CAM), also called associative memory, is a memory that is accessed by its content (data), not by an address.

Working:

1. The data to be searched (the search word) is placed in an argument register.
2. A key (mask) register chooses which bits of the word are compared.
3. The search word is compared with all stored words at the same time (in parallel), using comparison logic in every cell.
4. Every word that matches sets a bit in the match register. The address or associated data of the matching word is then read.

Advantages: very fast searching, in one memory cycle, whatever the size.

Disadvantages: expensive and uses more power and chip area, because each cell has its own comparison logic.

Uses: cache tag and TLB (translation look-aside buffer) lookup in processors, network routers and switches (MAC address and IP routing tables), and pattern matching.

Programmable Array Logic (PAL) is a programmable logic device that has a programmable AND array followed by a fixed OR array. It implements Boolean functions in sum of products (SOP) form.

Structure

• Each input and its complement go to all AND gates through fuses (or programmable links).
• The user blows the fuses that are not needed, so each AND gate gives the wanted product term.
• Each OR gate is permanently connected to a fixed group of AND gates (for example 3 or 8 product terms per output).

Example

Implement with a PAL that has 3 product terms per output:

All other fuses in each AND gate are blown. An unused AND gate is made 0 by keeping both a variable and its complement (such as $A\overline{A} = 0$), so it does not affect the OR.

PAL compared with PLA and PROM

Features

• Faster and cheaper than a PLA, because only one array is programmable.
• Limit: the number of product terms per output is fixed, so a function with more terms needs another output fed back.
• Registered PALs have flip-flops at the outputs for sequential circuits (for example 16R8). GAL is an erasable version.