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

Weighted vs Non-weighted Codes

Weighted codes: Each bit position carries a fixed weight, and the decimal value of a code word is the sum of the weights of the positions holding a 1.

• Examples: pure binary (weights $8,4,2,1$), BCD/8421, 2421, 5421.
• e.g. BCD $0101 = 4{\cdot}0 + 2{\cdot}1 + 1{\cdot}0 + 1 = 5$.

Non-weighted codes: No fixed positional weight is assigned, so the value cannot be obtained by a weighted sum. They are used for special properties such as single-bit change or error detection.

• Examples: Gray code (only one bit changes between successive values), Excess-3 (XS-3), ASCII.

Convert decimal 197

(a) Binary — repeated division by 2:

(b) Octal — group binary in 3s from the right: $\;011\;000\;101 \Rightarrow (3\,0\,5)$

Check: $3{\cdot}64 + 0{\cdot}8 + 5 = 192+5 = 197.$

(c) Hexadecimal — group binary in 4s: $\;1100\;0101 \Rightarrow (C\,5)$

Check: $12{\cdot}16 + 5 = 192+5 = 197.$

(d) BCD — each decimal digit (1, 9, 7) coded in 4-bit 8421:

Summary

Quine–McCluskey Minimization

Step 1 — Group minterms by number of 1s

Step 2 — Combine terms differing in one bit ($-$ = dropped bit)

Size-2 (pairs):

• $0,2 \to 00{-}0$ ✓ $\;0,8 \to {-}000$ ✓
• $2,3 \to 001{-}$ ✓ $\;2,10 \to {-}010$ ✓ $\;8,10 \to 10{-}0$ ✓
• $3,7 \to 0{-}11$ ✓ $\;3,11 \to {-}011$ ✓ $\;5,7 \to 01{-}1$ ✓ $\;10,11 \to 101{-}$ ✓ $\;10,14 \to 1{-}10$ ✓
• $7,15 \to {-}111$ ✓ $\;11,15 \to 1{-}11$ ✓ $\;14,15 \to 111{-}$ ✓

Size-4 (quads):

• $2,3,10,11 \to {-}01{-}$
• $3,7,11,15 \to {-}{-}11$
• $10,11,14,15 \to 1{-}1{-}$
• $5,7 \to 01{-}1$ stays a pair (cannot combine further)
• $0,2,8,10 \to {-}0{-}0$

Step 3 — Prime Implicants (terms not absorbed)

Step 4 — Prime Implicant Chart / Essential PIs

• 0 covered only by $P_1$ → $P_1=B'D'$ essential.
• 5 covered only by $P_5$ → $P_5=A'BD$ essential.
• 8 covered only by $P_1$ (confirms $P_1$).
• Remaining uncovered: 2,3,7,11,14,15. $P_4=AC$ covers 10,11,14,15; $P_3=CD$ covers 3,7,11,15. Together with $P_2=B'C$ covering 2,3 we cover all.

A minimal cover: $P_1 + P_5 + P_2 + P_3 + P_4$, where $P_2$ picks up minterm 2, and $P_3,P_4$ cover 7,14,15 (3,11 shared).

Final Minimized Expression

This is a valid minimal SOP covering all ten minterms. (Equivalent minimal forms exist, e.g. replacing $B'C$ by retaining only essential PIs plus the cheapest cover.)

Counter

A counter is a sequential circuit, made of flip-flops, that goes through a predetermined sequence of states (counts) in response to clock pulses. An $n$-flip-flop counter has up to $2^n$ states (a mod-N counter cycles through $N$ states).

Synchronous vs Asynchronous Counters

Design of a 3-bit Ripple (Asynchronous) Counter

Use three JK flip-flops wired in toggle mode ($J=K=1$), negative-edge triggered.

         +---+        +---+        +---+
CLK ---->|>FF0|  Q0-->|>FF1|  Q1-->|>FF2|
 J=K=1   +---+        +---+        +---+
          Q0           Q1           Q2  (outputs, Q0 = LSB)

• FF0 is clocked by the external CLK.
• FF1 is clocked by output $Q_0$.
• FF2 is clocked by output $Q_1$.
• Each FF has $J=K=1$, so it toggles on every active clock edge it receives.

Count Sequence (mod-8: 0 → 7 → 0)

$Q_0$ toggles every pulse, $Q_1$ toggles when $Q_0$ falls $1\to0$, and $Q_2$ toggles when $Q_1$ falls $1\to0$ — giving an up-count $0$ to $7$.

Standard (Canonical) SOP form of $F = AB + A'C$

The variables are $A,B,C$. A canonical SOP expands every term to contain all three variables, by AND-ing each deficient term with $(x+x')$ for the missing variable.

Term $AB$ (missing $C$):

Term $A'C$ (missing $B$):

Combine:

In minterm form (with order $A,B,C$): $ABC=m_7,\;ABC'=m_6,\;A'BC=m_3,\;A'B'C=m_1$.

Full Subtractor

A full subtractor subtracts three input bits — the minuend $A$, the subtrahend $B$, and a borrow-in $B_{in}$ from the previous stage — producing a Difference $D$ and a Borrow-out $B_{out}$.

Truth Table

Boolean Expressions

Working

The difference is 1 when an odd number of inputs are 1 (hence the 3-input XOR). A borrow is generated whenever the bits being subtracted from $A$ exceed $A$ — i.e. when $A=0$ and $B$ or $B_{in}$ is 1, or when both $B$ and $B_{in}$ are 1. It can be built from two half subtractors plus an OR gate, analogous to a full adder.

Full Adder using Two Half Adders

A half adder adds two bits $x,y$ giving $Sum = x \oplus y$ and $Carry = xy$. A full adder adds $A$, $B$, and carry-in $C_{in}$.

Construction

            HALF ADDER 1            HALF ADDER 2
 A ---+----[ XOR ]---- S1 ----+----[ XOR ]---- SUM
 B ---+----[ AND ]-- C1   Cin-+----[ AND ]-- C2
                       |                  |
                       +------[ OR ]------+---- COUT

• HA-1 adds $A$ and $B$: $S_1 = A \oplus B$, $C_1 = A B$.
• HA-2 adds $S_1$ and $C_{in}$: $SUM = S_1 \oplus C_{in}$, $C_2 = S_1 C_{in}$.
• An OR gate combines the two carries: $C_{out} = C_1 + C_2$.

Resulting Expressions

These match the standard full-adder truth table, confirming that two half adders and one OR gate implement a full adder.

4-to-1 Multiplexer

A multiplexer (MUX) is a combinational circuit that selects one of several data inputs and routes it to a single output, controlled by select lines. 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$.

Function Table

Boolean Expression

Operation

The two select bits form a binary address (0–3) that enables exactly one of four AND gates; the selected AND gate passes its data input through, and the outputs of all four AND gates are OR-ed to form $Y$. Thus the MUX acts as a digitally controlled switch and is widely used for data routing, parallel-to-serial conversion, and implementing logic functions.

PROM vs PAL vs PLA

All three are Programmable Logic Devices (PLDs) consisting of an AND array and an OR array; they differ in which arrays are fixed and which are programmable.

Summary: PROM = fixed AND + programmable OR; PAL = programmable AND + fixed OR; PLA = programmable AND + programmable OR (most flexible but costliest).

Master–Slave JK Flip-Flop

The master–slave JK flip-flop is built from two clocked JK (or SR) latches in cascade — a master and a slave — to eliminate the race-around problem of a basic JK flip-flop when $J=K=1$.

Structure

• The master latch is enabled when the clock is HIGH (CLK = 1).
• The slave latch is driven by the inverted clock, so it is enabled when the clock is LOW (CLK = 0).

Working

1. CLK = 1: the master responds to the $J,K$ inputs and updates its output, but the slave is disabled and holds the previous value (output unchanged).
2. CLK = 0: the master is now locked (cannot change), and the slave copies the master's stored value to the final output $Q$.

Because input is read on one clock level and output changes on the other, the output effectively updates on the clock edge and changes only once per clock pulse, preventing the race-around oscillation.

Characteristic Table

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

Parity Bit

A parity bit is an extra bit appended to a data word so that the total number of 1s becomes even or odd, used for single-bit error detection during data transmission/storage.

• Even parity: the parity bit is chosen so the total number of 1s (data + parity) is even.
• Odd parity: the parity bit is chosen so the total number of 1s is odd.

Parity Generator

For an $n$-bit data word $D_{n-1}\dots D_0$:

• Even parity generator: $P_{even} = D_0 \oplus D_1 \oplus \dots \oplus D_{n-1}$ (XOR of all data bits — equals 1 when the data has an odd count of 1s, making the overall count even).
• Odd parity generator: $P_{odd} = \overline{D_0 \oplus D_1 \oplus \dots \oplus D_{n-1}}$ (the complement, i.e. an XNOR of all bits).

Example (3-bit data 101)

Data has two 1s (even count).

• Even parity bit $= 1\oplus0\oplus1 = 0$ → transmitted word $0\,101$ (two 1s, even).
• Odd parity bit $= \overline{0} = 1$ → transmitted word $1\,101$ (three 1s, odd).

At the receiver a parity checker (XOR/XNOR of all received bits) flags an error if the parity is violated. A single parity bit detects all odd-numbered bit errors but cannot detect even-numbered errors or correct them.

Shift Registers: SISO and SIPO

A shift register is a cascade of flip-flops sharing a common clock, in which data is shifted one position per clock pulse. They are classified by how data enters and leaves.

SISO — Serial-In Serial-Out

• Data is entered one bit at a time at the input of the first flip-flop and is read out one bit at a time from the last flip-flop.
• After each clock pulse the bits shift one stage toward the output.
• For an $n$-bit SISO register it takes $n$ clock pulses to load and $n$ more to read out the data.
• Use: time delay, serial data transfer.

Din -->[FF0]-->[FF1]-->[FF2]-->[FF3]--> Dout   (one bit out per clock)
         all flip-flops share CLK

SIPO — Serial-In Parallel-Out

• Data is entered serially (one bit per clock) but all stored bits are available simultaneously at the parallel outputs $Q_0,Q_1,\dots,Q_{n-1}$.
• After $n$ clock pulses the $n$ bits are presented in parallel.
• Use: serial-to-parallel conversion (e.g. receiving serial data and reading it as a parallel word).

Din -->[FF0]-->[FF1]-->[FF2]-->[FF3]
         |      |      |      |
        Q0     Q1     Q2     Q3   (all outputs read at once)

Key difference: both load data serially, but SISO outputs serially (single line) while SIPO outputs all bits in parallel.

D Flip-Flop — Characteristic Table

The D (Data / Delay) flip-flop has a single data input $D$ and a clock. On the active clock edge the output simply takes the value of $D$; otherwise it holds. It has no invalid state, unlike SR.

Characteristic Table

This reduces to the simpler form:

Characteristic Equation

The next state equals the input $D$, independent of the present state $Q_n$ — hence the output is a one-clock delayed copy of the input. The D flip-flop is widely used in registers, data latches, and as the basic storage element in synchronous systems.