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

Methods of Binary Subtraction

There are three common methods to subtract one binary number from another:

1. Direct (borrow) method – subtract bit by bit just like decimal subtraction, generating a borrow of 2 from the next higher column when the minuend bit is smaller than the subtrahend bit. Simple for humans but awkward for hardware.
2. 1's complement method – take the 1's complement of the subtrahend, add it to the minuend, then add any end-around carry back to the LSB. If a final carry is produced the result is positive; otherwise the result is negative and is itself in 1's complement form.
3. 2's complement method – take the 2's complement of the subtrahend (1's complement + 1), add it to the minuend, and discard the final carry. If a carry-out is produced the result is positive (in true form); if no carry-out, the result is negative and stored in 2's complement form. This is the method used inside virtually all modern computers because subtraction reuses the same adder hardware used for addition.

Subtract 27 from 18 using 8-bit 2's complement

We compute $18 - 27 = -9$.

Step 1 – Represent the numbers in 8-bit binary:

Step 2 – Find the 2's complement of 27 (the subtrahend):

  27        = 0001 1011
  1's comp. = 1110 0100
  + 1       = 0000 0001
  2's comp. = 1110 0101   (= -27)

Step 3 – Add 18 and (-27):

   0001 0010   (+18)
 + 1110 0101   (-27)
 -----------
   1111 0111   (no carry-out)

Step 4 – Interpret the result. There is no final carry-out, so the answer is negative and is in 2's complement form. Take the 2's complement of 1111 0111 to read its magnitude:

  1111 0111
  1's comp. = 0000 1000
  + 1       = 0000 1001  = 9

Result: $1111\,0111_2 = -9_{10}$, i.e. $18 - 27 = -9$.

Minimize $F(A,B,C,D)=\sum m(0,2,4,6,8,10,12,14)$

Step 1 – Observe the minterms. Every listed minterm is an even number (0,2,4,6,8,10,12,14). An even minterm always has $D=0$. Hence the function is 1 exactly when $D=0$.

Step 2 – K-map. Placing 1's at all eight even cells:

The 1's form a single group of eight (the two columns where $D=0$).

Step 3 – Minimized expression:

Implementation using a multiplexer

Treat $A,B,C$ as the select lines of an 8-to-1 MUX and let $D$ be the data variable. For each combination of $ABC$ the two minterms differ only in $D$; both are 1 when $D=0$ and 0 when $D=1$. So every data input equals $\overline{D}$:

Thus one 8-to-1 MUX with select lines $S_2S_1S_0 = ABC$ and every data input tied to $\overline{D}$ realizes $F$.

Even simpler, because $F=\overline{D}$ depends on $D$ alone, a 2-to-1 MUX with select line $D$, $I_0=1$ and $I_1=0$ gives $F = \overline{D}\cdot 1 + D\cdot 0 = \overline{D}$.

Flip-Flops: Working, Truth Tables and Excitation Tables

A flip-flop is a 1-bit edge/level-triggered memory element with a present state $Q$ and a next state $Q^{+}$.

1. SR Flip-Flop

Set–Reset latch built from cross-coupled NOR/NAND gates. $S=1$ sets the output, $R=1$ resets it; $S=R=1$ is forbidden (indeterminate).

Characteristic eq.: $Q^{+}=S+\overline{R}\,Q$ (with $SR=0$).

2. D Flip-Flop

Obtained by tying $R=\overline{S}$ so the invalid state is removed. Output simply follows the data input on the clock edge.

Characteristic eq.: $Q^{+}=D$.

3. JK Flip-Flop

Refines SR by replacing the forbidden state with a toggle.

Characteristic eq.: $Q^{+}=J\overline{Q}+\overline{K}Q$.

4. T Flip-Flop

JK with $J=K=T$. $T=1$ toggles, $T=0$ holds. Useful in counters.

Characteristic eq.: $Q^{+}=T\oplus Q$.

Excitation Tables

These give the required inputs to cause a transition $Q \rightarrow Q^{+}$ (X = don't care).

Excitation tables are the inverse of characteristic tables and are the key tool when designing synchronous counters/sequential circuits.

Convert $(734.25)_8$ to hexadecimal

Step 1 – Octal to binary (each octal digit = 3 bits):

So $(734.25)_8 = (111011100.010101)_2$.

Step 2 – Group into 4-bit nibbles about the binary point (pad with 0's at the outer ends):

Integer part: 1 1101 1100 → 0001 1101 1100

Fraction part: 0101 01 → 0101 0100

Step 3 – Result:

Duality Principle of Boolean Algebra

The duality principle states that every valid Boolean identity remains valid (its dual) if we simultaneously:

• interchange the operators AND ($\cdot$) and OR ($+$), and
• interchange the identity elements 0 and 1,

leaving the variables and their complements unchanged.

Examples:

This principle is why Boolean theorems naturally come in pairs and is the basis of De Morgan's theorems.

Full Adder using a Decoder

A full adder has inputs $A,B,C_{in}$ and outputs Sum ($S$) and Carry ($C_{out}$):

Truth table:

Implementation. Use a 3-to-8 line decoder with $A,B,C_{in}$ as the three select/address inputs. The decoder activates exactly one of its eight outputs $D_0 \dots D_7$ for each input combination (one minterm per line).

• Feed outputs $D_1, D_2, D_4, D_7$ into an OR gate to generate Sum.
• Feed outputs $D_3, D_5, D_6, D_7$ into another OR gate to generate Carry.

(If the decoder has active-low outputs, replace the OR gates with NAND gates.) Thus one 3-to-8 decoder plus two OR gates implements a complete full adder.

4-to-2 Priority Encoder

A priority encoder converts $2^n$ inputs into an $n$-bit binary code, but unlike an ordinary encoder it resolves the case where several inputs are active simultaneously by giving precedence to the input of highest priority (usually the highest-numbered line, $D_3$).

For a 4-to-2 priority encoder: inputs $D_3,D_2,D_1,D_0$, outputs $Y_1Y_0$, plus a valid bit $V$ that is 1 whenever at least one input is active.

Truth table (X = don't care):

Output equations:

Because $D_3$ has the highest priority, whenever $D_3=1$ the output is $11$ regardless of the lower inputs; lower lines are encoded only when all higher lines are 0. The valid output $V$ distinguishes the all-zero input from a genuine $D_0=1$ encoding.

Difference between PLA and PAL

Both are Programmable Logic Devices that realize sum-of-products expressions, but they differ in which array is programmable.

Key point: In a PLA both the AND and OR planes are programmable, whereas in a PAL only the AND plane is programmable and the OR plane is fixed. This makes PLA more flexible but slower and costlier; PAL is faster, cheaper and more widely used.

PIPO Shift Register (Parallel-In Parallel-Out)

A PIPO register loads all data bits simultaneously in parallel and makes them available simultaneously in parallel at the outputs. It does not shift; it acts purely as a temporary parallel storage / buffer.

Construction. For an $n$-bit register, $n$ flip-flops (usually D flip-flops) share a common clock. Each input $D_i$ is wired directly to one flip-flop, and each output $Q_i$ is taken from that flip-flop. There are no interconnections between adjacent flip-flops, so no bit-shifting occurs.

Operation.

• On the active clock edge, every flip-flop captures its corresponding input bit at the same instant: $Q_i \leftarrow D_i$.
• All outputs $Q_0 \dots Q_{n-1}$ then present the loaded word at once and hold it until the next load.

Characteristics:

• Fastest mode of data transfer (one clock pulse loads the whole word).
• No serial path, so it is used mainly as a parallel data buffer/latch between functional blocks, not for serial communication.

For example, a 4-bit PIPO storing 1011: inputs $D_3D_2D_1D_0 = 1011$ appear at outputs $Q_3Q_2Q_1Q_0 = 1011$ after a single clock pulse.

Mod-10 (Decade) Counter Design

A mod-10 counter counts through 10 states (0000 to 1001) and then resets to 0000, ignoring the six unused states 1010–1111. It can be built as an asynchronous (ripple) or synchronous counter; a simple asynchronous design uses four JK flip-flops in toggle mode (all $J=K=1$).

Count sequence: $0000 \rightarrow 0001 \rightarrow \dots \rightarrow 1001 \rightarrow 0000$.

Design idea (asynchronous reset method):

1. Use four T/JK flip-flops ($Q_3Q_2Q_1Q_0$) connected as a 4-bit ripple counter; each flip-flop's output clocks the next.
2. The counter naturally counts 0–15. To make it stop at 9 we must force a reset on the count 1010 (decimal 10).
3. State 1010 is the first count where $Q_3=1$ and $Q_1=1$. Feed these into a NAND gate:

4. Connect the NAND output to the asynchronous CLEAR of all four flip-flops. The instant the count reaches 1010, $Q_3Q_1=1$ drives CLR low, immediately resetting the counter to 0000.

Result: the counter cycles through 0–9 (BCD) and rolls over, giving a modulus of 10. (A jam-free synchronous version uses the excitation table of JK flip-flops with K-maps for $J,K$ of each stage, but the asynchronous reset method above is the standard exam answer.)

Multiplexer vs Demultiplexer

Summary: A multiplexer is a data selector that combines many input lines onto one output line under control of select lines, while a demultiplexer is a data distributor that takes one input line and steers it to one of many output lines. They perform complementary (inverse) operations, and a DEMUX is functionally the same as a decoder with an enable input.

Look-Ahead Carry Generator

Problem it solves. In a ripple-carry adder each stage must wait for the carry from the previous stage, so the carry ripples through all $n$ stages, making the worst-case delay proportional to $n$. A carry look-ahead (CLA) generator computes all carries in parallel directly from the input bits, drastically reducing addition delay.

Generate and Propagate signals. For each bit position $i$ with inputs $A_i, B_i$:

Carry equations. Using $C_{i+1} = G_i + P_i C_i$, each carry can be expanded into a function of only the inputs and $C_0$:

Since every carry is a two-level (AND-OR) function of the inputs, all carries are available after a constant gate delay, independent of the word length.

Sum: $S_i = P_i \oplus C_i$.

Advantages / drawback: Much faster than ripple-carry (speed independent of $n$), but the logic grows complex for large $n$, so wide adders use block CLA stages.