Write the first 20 digits of base-5.

Here, base = n = 5
Highest digit = (5 - 1) = 4
=(0, 1, 2, 3, 4)
Digits are
0, 1, 2, 3, 4, 01, 02, 03, 04, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30,

Advantage and Disadvantage of r's and (r-1)'s Complement.

r's Complement (e.g., 2’s complement, 10’s complement)

Advantages:

1. Unique Zero Representation – Only one representation for zero.

2. Simpler Subtraction – Subtraction becomes addition of complements.
3. Efficient in Digital Circuits – Particularly useful in binary (2’s complement) systems.
4. Handles Negative Numbers Well – Arithmetic operations are consistent for both
positive and negative numbers.
5. No End-Around Carry Needed – Makes the implementation easier in binary systems.

Disadvantages:

1. More Complex for Humans – Slightly harder to manually compute than (r–1)'s
complement.
2. Extra Step in Decimal Systems – In decimal, you have to add 1 after (r–1)’s
complement.

(r–1)'s Complement (e.g., 1’s complement, 9’s complement)

Advantages:

1. Easier to Understand and Compute – Just subtract each digit from (r–1).
2. Useful in Manual Calculations – Commonly used in traditional subtraction methods.
3. Conceptually Simple – No addition of 1 needed for complementing.

Disadvantages:

1. Two Representations of Zero – Both +0 and –0 exist, causing redundancy.

 2. Requires End-Around Carry – You must add carry-out to result, increasing
complexity.
3. Less Efficient in Circuits – Not ideal for hardware-level implementation.

General Rule of (r-1)'s Complement.

General Rule of (r – 1)'s Complement

The (r – 1)'s complement of a number is obtained by subtracting each digit of the number
from (r – 1), where r is the base of the number system.

General Formula:

If a number is represented as:

N = (dₙ₋₁ dₙ₋₂ ... d₁ d₀) in base r,
then the (r–1)'s complement is:
C = ((r–1) – dₙ₋₁, (r–1) – dₙ₋₂, ..., (r–1) – d₀)

For Common Bases:

In Binary (base r = 2):

 (2–1) = 1
 So, (1’s complement) is found by inverting each bit (0 → 1, 1 → 0).

In Decimal (base r = 10):

 (10–1) = 9
 So, (9’s complement) is found by subtracting each digit from 9.

Examples:

Binary Example:

Number = 1010
1’s complement = 0101 (invert each bit)

Decimal Example:

Number = 4567
9’s complement = 9999 – 4567 = 5432
Explain ASCII code?
Ans: Computers need to handle letters, numbers, and special symbols, not just numbers. To
do this, a binary code system like ASCII (American Standard Code for Information
Interchange) is used.

• ASCII uses 7 bits to represent 128 characters, including:

o 94 printable characters:

▪ 26 uppercase letters (A–Z)

▪ 26 lowercase letters (a–z)

▪ 10 digits (0–9)

▪ 32 special symbols (like $, %, *)

o 34 control characters: used for text formatting and communication (e.g.,

backspace, tab, start/end of text).
• Though ASCII uses 7 bits, most computers store each character in an 8-bit byte.

o The extra bit (8th bit) is often used for other purposes or to support extended
characters, like Greek letters or special fonts.

There are three types of ASCII control characters:

1. Format effectors (e.g., backspace, carriage return)

2. Information separators (e.g., file separator)

3. Communication controls (e.g., start/end of text)

Explain NOR implications
Ans:

The NOR gate is a universal gate, meaning any Boolean function can be implemented using
only NOR gates. It is the dual of the NAND gate and follows DeMorgan’s theorem.
• NOT: Achieved using a single-input NOR gate.

• OR: Implemented using two NOR gates.

• AND: Done by inverting inputs and using a NOR gate.

For a two-level NOR implementation, the Boolean function must be in Product of Sums
(POS) form. Then:

• OR gates become OR-invert NOR gates.

• The final AND gate becomes an invert-AND NOR gate.

• Any unmatched bubble (inversion) requires the input literal to be complemented.
In multilevel designs, convert each OR to an OR-invert and each AND to an invert-AND.
Adjust inputs as needed to match the logic.

Conclusion: Any Boolean function can be implemented using NOR gates if expressed in POS
form, with proper handling of bubbles and complemented inputs.

Inverter x x

x
OR x y
y

AND (x y ) xy

FIGURE : Logic operations with NOR gates

xx y(x y z) yxyz (x y z)

zz

(a) OR-invert (b) Invert-AND

FIGURE : Two graphic symbols for the NOR gate

A
B

C
F
D

FIGURE : Implementing F = (A + B)(C + D)E

A
B

F
A
B

C
D

FIGURE : Implementing F = (AB + AB)(C + D) with NOR gates

Explain Half Adder, Full Adder, Half Subtractor, and Full Subtractor with
Example
Ans:

Half Adder

A half adder is a basic digital circuit that adds two binary inputs (x and y) and produces two
outputs:

• Sum (S) – the least significant bit of the result

• Carry (C) – the carry-out bit

Truth Table Behavior:

• S = x'y + xy' → Sum is 1 when only one input is 1 (XOR operation)

• C = xy → Carry is 1 only when both inputs are 1 (AND operation)

Implementation:

• Can be built using basic gates (AND, OR, NOT) from sum-of-products expressions

• More commonly implemented using an XOR gate for S and an AND gate for C

This simple design is foundational, as two half adders are used together to build a full adder,
which handles three inputs.

Truth Table :Half Adder

FIGURE : Implementation of half adder

Full Adder:

A full adder is a combinational circuit used to add three binary bits: two data inputs (x and y)
and a carry input (z) from a previous addition. It has two outputs: Sum (S) and Carry (C). The
Sum represents the least significant bit, and Carry represents the overflow to the next bit. The
Boolean expressions are:

• S = x’y’z + x’yz’ + xy’z’ + xyz

• C = xy + xz + yz
It can be implemented using basic logic gates or using two half adders and an OR
gate. Full adders are essential for multi-bit binary addition.

Truth Table :Full Adder

x
y
z
x
y
x
y
z
x
S C
z
x
y
z
y
z
x
y
z

FIGURE :Implementation of full adder in sum-of-products form

x x y
(x y) z
y S

xy
(x y) z
(x y) z xy
C

FIGURE : Implementation of full adder with two half adders and an OR gate
Half-Subtractor

The Half-Subtractor, a combinational logic circuit that subtracts two binary bits, x (minuend)
and y (subtrahend), and produces two outputs:

• D (Difference)

• Bo (Borrow)

Key Concepts:

• The Difference (D) is the result of x − y.

• The Borrow (Bo) indicates whether a 1 needs to be borrowed from the next higher bit
for subtraction

A B Bo D
0 0 0 0
0 1 1 1
1 0 0 1
1 1 0 0

Truth table Implementation of Half subtractor

Boolean Expressions:

• D = A ⊕ B (XOR gate)

• B = A'B (NOT A AND B)

Full-Subtractor

A full-subtractor is a combinational logic circuit that performs binary subtraction of two bits
(x and y) while also accounting for a borrow-in (z) from a less significant bit. It outputs:

• D: The difference (A - B - Bin)

• Bout: The borrow-out, which signals if a borrow is needed for the next stage
Inputs and Outputs:

• Inputs:

o A: Minuend

o B: Subtrahend
o Bin: Borrow-in

• Outputs:

o D: Difference

o Bout: Borrow-out

Truth Table:

A B Bin Bout D
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 1 0
1 0 0 0 1
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
Implementation of Full subtractor

Explanation:

• When Bin = 0, the full-subtractor behaves like a half-subtractor

• Borrow is needed when A < B + Bin

• The truth table entries cover all possible input combinations (8 total)

Simplified Boolean Expressions:

• Difference (D):

D=A⊕B⊕Bin

or

D=a′B′Bin+A′BBin′+AB′Bin′+ABBin
• Borrow (Bout):

B=A′B+A′Bin+BBin
Parity bit as a Error Detection Code:
Binary information can be transmitted from one location to another by electric wires or other
communication medium. Any external noise introduced into the physical communication
medium may change some of the bits from 0 to 1 or vice versa. The purpose of an error-
detection code is to detect such bit-reversal errors. One of the most common ways to achieve
error detection is by means of a parity bit. A parity bit is an extra bit included with a message
to make the total number of 1’s transmitted either odd or even. A message of four bits and a
parity bit P are shown in Table. If an odd parity is adopted, the P bit is chosen such that the total
number of 1's is odd in the five bits that constitute the message and P. If an even parity is
adopted, the P bit is chosen so that the total number of 1’s in the five bits is even. In a particular
situation, one or the other parity is adopted, with even parity being more common.

The parity bit is helpful in detecting errors during the transmission of information from one
location to another. This is done in the following manner. An even parity bit is generated in the
sending end for each message transmission. The message, together with the parity bit, is
transmitted to its destination. The parity of the received data is checked in the receiving end. If
the parity of the received information is not even, it means that at least one bit has changed
value during the transmission. This method detects one, three, or any odd combination of errors
in each message that is transmitted. An even combination of errors is undetected. Additional
error-detection schemes may be needed to take care of an even combination of errors.

Odd parity
4 bit Parity Final output
massage bit (Data+parity)
0000 1 00001
0001 0 00010
0010 0 00100
0011 1 00111
0100 0 01000
0101 1 01011
0110 1 01101
0111 0 01110
1000 0 10000
1001 1 10011
1010 1 10101
1011 0 10110
1100 1 11001
1101 0 11010
1110 0 11100
1111 1 11111
Priority Encoder
A priority encoder is an encoder circuit that includes the priority function. The operation of the
priority encoder is such that if two or more inputs are equal to 1 at the same time, the input
having the highest priority will take precedence. The truth table of a four-input priority encoder
is given in Table 4.8 . In addition to the two outputs x and y , the circuit has a third output
designated by V ; this is a valid bit indicator that is set to 1 when one or more inputs are equal
to 1. If all inputs are 0, there is no valid input and V is equal to 0. The other two outputs are not
inspected when V equals 0 and are specified as don’t-care conditions. Note that whereas X ’s
in output columns represent don’t-care conditions, the X ’s in the input columns are useful for
representing a truth table in condensed form. Instead of listing all 16 minterms of four variables,
the truth table uses an X to represent either 1 or 0. For example, X 100 represents the two
minterms 0100 and 1100.

According to Table 4.8 , the higher the

subscript number, the higher the
priority of the input. Input D3 has the
highest priority, so, regardless of the
values of the other inputs, when this
input is 1, the output for xy is 11
(binary 3). D2 has the next priority
level. The output is 10 if D2=1,
provided that D3=0, regardless of the
values of the other two lower priority
inputs. The output for D1 is generated
only if higher priority inputs are 0,
and so on down the priority levels.
The maps for simplifying outputs x and y are shown in Fig. 4.22 . The minterms for the two
functions are derived from Table 4.8 . Although the table has only five rows, when each X in a
row is replaced first by 0 and then by 1, we obtain all 16 possible input com binations. For
example, the fourth row in the table, with inputs XX10, represents the four minterms 0010,
0110, 1010, and 1110. The simplified Boolean expressions for the priority encoder are obtained
from the maps. The condition for output V is an OR function of all the input variables. The
priority encoder is implemented in Fig. 4.23 according to the following Boolean functions:

x = D2 + D3

y = D3 + D1 D'2

V = D0 + D1 + D2 + D3

𝟐 × 𝟏 MULTIPLEXERS IMPLEMENTATION
A multiplexer is a combinational circuit that selects binary information from one of many input
lines and directs it to a single output line. The selection of a particular input line is controlled
by a set of selection lines. Normally, there are 2n input lines and n selec tion lines whose bit
combinations determine which input is selected. A two-to-one-line multiplexer connects one of
two 1-bit sources to a common desti nation, as shown in Fig. 4.24. The circuit has two data
input lines, one output line, and one selection line S. When S = 0, the upper AND gate is enabled
and I0 has a path to the output. When S = 1, the lower AND gate is enabled and I1 has a path
to the output. The multiplexer acts like an electronic switch that selects one of two sources.
The block diagram of a multiplexer is sometimes depicted by a wedge-shaped symbol, as
shown in Fig. 4.24(b). It suggests visually how a selected one of multiple data sources is
directed into a single destination.
The multiplexer is often labeled “MUX” in block diagrams. A four-to-one-line multiplexer is
shown in Fig. 4.25. Each of the four inputs, I0 through I3, is applied to one input of an AND
gate. Selection lines S1 and S0 are decoded to select a particular AND gate. The outputs of the
AND gates are applied to a single OR gate that provides the one-line output. The function table
lists the input that is passed to the output for each combination of the binary selection values.
To demonstrate the operation of the circuit, consider the case when S1 S0 = 10. The AND gate
associated with input I2 has two of its inputs equal to 1 and the third input connected to I2. The
other three AND gates have at least one input equal to 0, which makes their outputs equal to 0.
The output of the OR gate is now equal to the value of I2, providing a path from the selected
input to the output. A multiplexer is also called a data selector, since it selects one of many
inputs and steers the binary information to the output line. The AND gates and inverters in the
multiplexer resemble a decoder circuit, and indeed, they decode the selection input lines. In
general, a 2n -to-1-line multiplexer is constructed from an n -to-2 n decoder by adding 2n input
lines to it, one to each AND gate. The outputs of the AND gates are applied to a single OR gate.
The size of a multiplexer is specified by implied from the 2n data lines. As in decoders,
multiplexers may have an enable input to control the operation of the unit. When the enable
input is in the inactive state, the outputs are disabled, and when it is in the active state, the
circuit functions as a normal multiplexer. Multiplexer circuits can be combined with common
selection inputs to provide multiple-bit selection logic. As an illustration, a quadruple 2-to-1-
line multiplexer is shown in Fig. 4.26. The circuit has four multiplexers, each capable of
selecting one of two input lines. Output Y0 can be selected to come from either input A0 or input
B0. Similarly, output Y1 may have the value of A1 or B1, and so on. Input selection line S selects
one of the lines in each of the four multiplexers. The enable input
E must be active (i.e., asserted) for normal operation. Although
the circuit contains four 2-to-1-line multiplexers, we are more
likely to view it as a circuit that selects one of two 4-bit sets of
data lines. As shown in the function table, the unit is enabled
when E = 0. Then, if S = 0, the four A inputs have a path to the
four outputs. If, by contrast, S = 1, the four B inputs are applied
to the outputs. The outputs have all 0’s when E = 1, regardless of
the value of S.
X-NOR Design with CMOS

fig.01: X-NOR design by CMOS

Truth table of X-NOR

Show that, A ⊕ B ⊙ C = ¬ (A ⊕ B ⊕ C) with Boolean expression.

We are given the expression:

A⊕(B⊙C) = ¬(A⊕B⊕C)

Left Side:
We can write, A⊕(B⊙C) = A⊕(B⋅C)

We’ll expand XOR using Boolean algebra:

A⊕(B⋅C) =A(B⋅ C)′ +A′(B⋅C)

Right Side:

¬(A⊕B⊕C)

We know that:

A⊕B⊕C=(A⊕B)⊕C

By using Boolean algebra:

X⊕Y=XY′+X′Y

So:

A⊕B=AB′+A′B

Now apply XOR with C:

(A⊕B)⊕C=(AB′+A′B)⊕C

And ¬(A⊕B⊕C) means Even parity of (A, B, C)

BY using Truth table,

A B C B·C A ⊕ (B·C) A⊕B⊕C ¬(A⊕B⊕C)

0 0 0 0 0 0 1
0 0 1 0 0 1 0
0 1 0 0 0 1 0
0 1 1 1 1 0 1
1 0 0 0 1 1 0
1 0 1 0 1 0 1
1 1 0 0 1 0 1
1 1 1 1 0 1 0

Hence We can say , A ⊕ B ⊙ C = ¬ (A ⊕ B ⊕ C)

How the problem of normal encoder can be solved by priority encoder?

Normal Encoder:

A normal encoder converts one of 2ⁿ input lines to an n-bit binary code.

But it has a serious limitation:

If more than one input is high (1) at the same time, the output becomes ambiguous or incorrect.

For Example:

Suppose we have a 4-to-2 encoder:

Inputs (D3 D2 D1 D0) Output (A1 A0)

0001 00
0010 01
0100 10
1000 11
1100 ambiguous
If both D3 and D2 are 1, the encoder can't decide whether to output 11 (for D3) or 10 (for D2) —
this is the problem.

Using Priority Encoder:

A priority encoder solves this by:

Giving priority to the highest-order input.

So if multiple inputs are high, it only encodes the highest-priority one (e.g., D3 > D2 > D1 >
D0).

For Example (4-to-2 Priority Encoder):

D3 D2 D1 D0 Output (A1 A0)

0 0 0 1 00
0 0 1 x 01
0 1 x x 10
1 x x x 11

Even if multiple bits are 1, the encoder ignores lower ones.

So we can say ,A priority encoder solves the ambiguity problem of a normal encoder by
assigning priority to the highest active input, ensuring a clear, unambiguous output even when
multiple inputs are active at the same time.