CS302 — Midterm Summary (Lectures 1–22)

📘 Lecture 01 — An Overview & Number Systems

📖 Overview: This foundational lecture introduces the fundamental difference between analogue and digital quantities, explains the rationale for digital processing, and establishes the binary number system as the core of digital logic design. It covers the basic building blocks of digital systems—logic gates, combinational and sequential circuits—and culminates in a formal treatment of number systems, including decimal, binary, and a hypothetical base-5 system, to illustrate how any radix can represent values using positional notation.

🗂️ Topics Covered

The lecture begins by contrasting analogue and digital quantities, illustrating how digital systems use discrete samples to represent continuous signals. It then explains the electronic processing of these signals, introducing the binary number system as the foundation of digital values. The advantages of the digital domain are enumerated, followed by an overview of digital components including logic gates, combinational circuits, sequential circuits, programmable logic devices (PLDs), memory, and A/D-D/A converters. The lecture concludes with a detailed analysis of number systems, using the decimal and a hypothetical caveman base-5 system to explain the binary number system and the representation of integer and fractional values through positional weights.

📝 Lecture Summary

Analogue versus Digital

Most measurable quantities in nature, such as the intensity of light during the day, the rise and fall in temperature over a 24-hour period, and the velocity of a car, are continuous. These values change gradually over a range with a minimum and maximum. In contrast, digital quantities are not continuous but represent values measured at discrete intervals. A continuous signal can be sampled at fixed, equal intervals to produce a set of discrete values (e.g., 15 samples like 1, 2, 4, 7, 18, 34, etc.). The reconstructed signal from these samples only approximates the original; under-sampling (e.g., using only 7 samples) causes missing peaks and dips. A more accurate representation requires increasing the number of samples.

💡 Why this matters: The accuracy of a digital representation of the real world depends directly on the rate at which the continuous signal is sampled.

Electronic Processing of Continuous and Digital Quantities

Continuous quantities or their digital representations must be converted into voltages for electronic processing. There are two fundamental types of systems: Analogue Electronic Systems accept and process continuous signals converted by transducers into continuous voltage/current signals. Digital Electronic Systems process discrete samples. Digital systems do not represent discrete samples as unique voltage values (e.g., 39 mV for the number 39) because large numbers would require impractically high voltages. Instead, they use two voltage values: +5 volts (logic high/logic 1) and 0 volts (logic low/logic 0). The Binary Number System is used to represent more than two values by combining these binary digits (bits).

Digital Systems and Digital Values

Digital systems are designed to work with two voltage states, which can represent binary values like ‘0’/‘1’, ‘on’/‘off’, or ‘hot’/‘cold’. To represent a wider range of values, digital systems use the Binary Number System, which is based on two values (0 and 1). A single bit can represent only two values, but by combining bits, any quantity can be represented. For example, a palette of four colours can be represented by combinations of two bits (00, 01, 10, 11), and a temperature of 39°C is represented digitally as the binary number 100111. The number of digits used is proportional to the range of values to be represented. The binary number 100111 is stored electronically as +5v, 0v, 0v, +5v, +5v, +5v.

Advantages of working in the Digital Domain

Handling information digitally offers several advantages: Storing and processing data is more efficient (e.g., a CD stores vast amounts of data vs. analogue tapes). Transmission of data is more reliable, as it is less prone to errors, and errors are easier to detect and correct. Data can be easily and precisely reproduced, leading to superior digital video and audio quality. Digital systems are easy to design and implement, as the simple two-state circuitry allows for powerful systems. Finally, digital circuits occupy small space, with powerful computers fitting on a small motherboard.

Information Processing by a Digital System

A digital system, such as a computer, can handle all kinds of information, all represented as binary numbers. This includes numbers (integers, fractions), text (using standards like ASCII), drawings and pictures, and music and sound.

Digital Components and their internal working

These specialized circuits are known as Logic Gates, the basic building blocks of any digital circuit. Common gates include the AND gate, OR gate, Inverter (NOT) gate, NOR, NAND, XOR, and XNOR gates. Each performs a unique logical or Boolean operation on input information. These gates are implemented using technologies like CMOS and TTL, which determine operational characteristics.

Combinational Logic Circuits and Functional Devices

A single logic gate is not very useful on its own. When gates are combined to perform a useful operation, such as adding numbers, they form Combinational Logic Circuits. An example is a 1-bit Full-Adder, which adds two binary numbers and produces a Sum and Carry output. Instead of building complex circuits from individual gates, functional devices like Comparators, Decoders, Encoders, Multiplexers, and Demultiplexers are available as Integrated Circuits (ICs).

Sequential logic and implementation

Some digital circuits generate an output based on both the current input and previously saved information. These are Sequential circuits. A digital down-counter, for example, stores a current count value. When it receives an external pulse, it decrements the stored value to produce a new count. Sequential circuits are a combination of combinational circuits and a memory element, called a flip-flop.

Programmable Logic Devices (PLDs)

A modern trend is using configurable hardware that can be programmed by the end user. A PLD for a washing machine controller reduces the need for a large inventory of components and can be easily reprogrammed for design changes, reducing cost and implementation time.

Memory

Memory is critical in digital systems. Read-Only Memory (ROM) stores data permanently and allows only reading. Random Access Memory (RAM) is volatile—data is lost when power is turned off—and allows both reading and writing.

Analogue to Digital and Digital to Analogue conversion and Interfacing

Because the real world is continuous, two conversions are needed. An Analogue to Digital (A/D) Converter converts an analogue voltage into an equivalent digital representation. A Digital to Analogue (D/A) Converter converts the digital output back to a continuous voltage. This is illustrated by a digitally controlled industrial heater where a temperature sensor's voltage is converted to a digital value, processed, and then converted back to control a heater valve.

Number Systems and Codes

Decimal Number System

The decimal number system has ten unique digits (0-9). It is a positional number system, meaning the position of a digit represents its true magnitude. For example, in 275, the '2' represents 200 and the '7' represents 70. The expression for 275 is: 📐 Formula: 2 × 10² + 7 × 10¹ + 5 × 10⁰ = 200 + 70 + 5 = 275. Here, 10 is the base (or radix), and 10², 10¹, 10⁰ are the weights.

Fractions in Decimal Number System The integer part is left of the decimal point (weights 10⁰, 10¹, 10²...), and the fraction part is right of the decimal point (weights 10⁻¹, 10⁻², 10⁻³...). 📐 Formula: 382.91 = 3 × 10² + 8 × 10¹ + 2 × 10⁰ + 9 × 10⁻¹ + 1 × 10⁻² = 382.91.

Caveman number system

A hypothetical Base-5 number system with five distinct symbols (∑, ∆, >, Ω, ↑) representing decimal 0 to 4. This system is used to illustrate that any base can represent numbers. 🔑 Definition — Base (Radix): The number of unique digits (including zero) in a number system. 📌 Example: The caveman number ∆↑ is equivalent to: = ∆ × 5¹ + ↑ × 5⁰ = (1 × 5) + (4 × 1) = 9. 📌 Example: The caveman number ∆Ω↑∑ is: = (1 × 125) + (3 × 25) + (4 × 5) + (0 × 1) = 220.

Binary Number System

Digital systems use the Binary number system, which is a Base-2 number system with only two numbers, 0 and 1. A binary digit (0 or 1) is known as a 'Bit'. Counting in binary is similar to other systems, where a value larger than 1 requires more digits.

Any binary number can be expressed in decimal by using the base value 2 and weights 2⁰, 2¹, 2², etc. 📌 Example: The binary number 10011₂ (subscript ₂ indicates binary) is: = (1 × 2⁴) + (0 × 2³) + (0 × 2²) + (1 × 2¹) + (1 × 2⁰) = 16 + 0 + 0 + 2 + 1 = 19.

Fractions in Binary Number System In a binary number, a decimal point separates the integer and fraction parts. The integer's weights are 2⁰, 2¹, 2²..., and the fraction's weights are 2⁻¹, 2⁻², 2⁻³... 📌 Example: The binary number 1011.101₂ is: = (1 × 2³) + (0 × 2²) + (1 × 2¹) + (1 × 2⁰) + (1 × 2⁻¹) + (0 × 2⁻²) + (1 × 2⁻³) = 8 + 0 + 2 + 1 + 0.5 + 0 + 0.125 = 11.625.

💡 Why this matters: While computers handle numbers like 11.625, they use a specialized representation (Floating-Point Numbers) instead of the binary format shown here.

⭐ Key Takeaways

The defining characteristic of digital versus analogue is that digital quantities are discrete, not continuous, and their accuracy depends on the sampling rate. At the hardware level, digital systems are based on a simple two-voltage state system (e.g., +5V and 0V), which represents the binary digits 0 and 1. The binary number system is a base-2 positional number system, and any binary number (integer or fractional) can be converted to its decimal equivalent using an expression of powers of 2. All digital systems, from simple logic gates to complex functional devices, operate on binary numbers, making the binary number system the absolute foundation of the entire field.

🧠 Quick Revision Questions

1. What is the fundamental difference between an analogue quantity and a digital quantity?
2. Why don't digital electronic systems represent discrete sample values as their equivalent voltage values (e.g., 39V for the number 39)?
3. Explain the concept of a "positional number system" using the number 275 in decimal as an example.
4. Convert the binary integer 11010₂ to its decimal equivalent.
5. Convert the binary fraction 1101.101₁ to its decimal equivalent.

📘 Lecture 02 — NUMBER SYSTEMS

📖 Overview: This lecture covers the fundamental methods for converting between Binary and Decimal number systems, including techniques for both integers and fractions. It also introduces binary arithmetic operations and explains how signed numbers are represented in digital systems using sign-magnitude and 2's complement forms, which are essential for understanding digital logic design.

🗂️ Topics Covered

Binary to Decimal conversion using Sum-of-Weights and Sum-of-non-zero terms methods; Decimal to Binary conversion using Sum-of-Weights and Repeated Division-by-2 for integers, and Sum-of-Weights and Repeated Multiplication-by-2 for fractions; Binary arithmetic operations including addition, subtraction, multiplication (including shift method), and division (including shift method); Signed and unsigned binary numbers; 1's and 2's complement representations; Addition and subtraction with signed binary; Range of signed and unsigned binary numbers.

📝 Lecture Summary

Binary to Decimal conversion

Most real-world quantities are represented in the Decimal Number System, while Digital Systems are based on the Binary Number System. Therefore, when converting from the Digital Domain to the real-world, Binary numbers must be represented in terms of their Decimal equivalents.

1. Sum-of-Weights Method The Sum-of-Weights method sums the weights of the Binary Digits (bits) of a Binary number to represent it in Decimal. An extended expression is written in terms of the Binary Base Number 2 and the weights of the binary bits. The weights correspond to each binary bit which are multiplied by the corresponding binary value. Binary bits having the value 0 do not contribute any value towards the final sum expression.

🔑 Definition — Sum-of-Weights method: A conversion method where the decimal equivalent of a binary number is found by multiplying each binary digit by its positional weight (power of 2) and summing the results.

📐 Formula: Decimal = Σ (bit × 2^position) for each bit position, where position starts at 0 from the rightmost (least significant) bit.

📌 Example: Binary number 10110₂ 10110₂ = 1 × 2⁴ + 0 × 2³ + 1 × 2² + 1 × 2¹ + 0 × 2⁰ = 16 + 0 + 4 + 2 + 0 = 22

2. Sum-of-non-zero terms The Sum-of-non-zero terms method is a quicker method to determine decimal equivalents of binary numbers without writing an expression. The weights of non-zero binary bits are summed, as the weights of zero binary bits do not contribute. The weights of binary bits starting from the rightmost least significant bit is 1, then 2, 4, 8, 16, 32, etc. towards the left. In binary number system, weights of successive bits increase by a factor of 2 towards the left and decrease by a factor of 2 towards the right.

📌 Example: 10011₂ = 16 + 2 + 1 = 19

📌 Example: 1011.101₂ = 8 + 2 + 1 + ½ + 1/8 = 11 + 5/8 = 11.625

Decimal to Binary conversion

Conversion from Decimal to Binary number system is essential to represent real-world quantities in terms of Binary values.

1. Sum-of-Weights The Sum-of-Weights method for decimal-to-binary conversion requires finding the highest weight included in the sum representing the decimal equivalent. A Binary 1 is marked to represent the bit that contributed its weight, and the weight is subtracted from the sum. This process repeats until the sum term becomes zero. The binary 1s and 0s represent bits that contributed their weight and bits that did not, respectively.

📌 Example: Converting 411 to Binary

Result: 411 = 110011011₂

📌 Example: Converting 392 to Binary

Result: 392 = 110001000₂

2. Repeated Division-by-2 The Repeated Division-by-2 method allows decimal numbers of any magnitude to be converted into binary. The decimal number is repeatedly divided by 2 (the Base number). A quotient and a remainder are generated at each step. The remainder values are noted, and the quotient is divided again by 2. The process stops when the quotient value becomes zero. The remainders, read from bottom to top, give the binary equivalent.

📌 Example: Converting 392 to Binary using Repeated Division-by-2

Reading remainders from bottom to top: 110001000₂

Converting Decimal fractions to Binary

1. Sum-of-Weights for Fractions The Sum-of-Weights method applied to decimal fractions works by finding the highest weight (negative power of 2) included in the decimal fraction.

📌 Example: Converting 0.625 to Binary

Result: 0.625 = 0.101₂

2. Repeated Multiplication-by-2 Method The Repeated Multiplication-by-2 method converts decimal fractions to binary. The number is repeatedly multiplied by the Base Number (2). A new number having an Integer part and a Fraction part is generated after each multiplication. The Integer part is noted down, and the fraction part is multiplied by 2 again. The process repeats until the fraction term becomes zero. Reading the Integer column from top to bottom gives the binary equivalent.

📌 Example: Converting 0.625 to Binary using Repeated Multiplication-by-2

Reading Integer column from top to bottom: 0.101₂

Binary Arithmetic

Digital systems use the Binary number system to represent numbers and must perform standard arithmetic operations.

1. Binary Addition Binary Addition is identical to Decimal Addition. Adding two binary bits generates a Sum bit and a Carry bit. Four possibilities exist when two single bits are added together.

📌 Single Bit Addition Table:

The fourth addition (1+1) results in 2, which is 10₂ in binary, requiring two digits: Sum=0, Carry=1.

📌 Example: Adding multiple binary numbers

    1 1 0 1  (Carry row)
      1 0 1 1  (11)
        1 1 0  (06)
      1 0 0 0  (08)
          1 1  (03)
    ----------
    1 1 1 0 0  (28)

2. Binary Subtraction Binary Subtraction is identical to Decimal Subtraction. Subtracting two single bit binary numbers results in a Difference bit and a Borrow bit.

📌 Single Bit Subtraction Table (second number subtracted from first):

When subtracting 1 from 0, a Borrow is required to make the first digit equal to 2, giving a Difference of 1.

3. Binary Multiplication Binary Multiplication is similar to Decimal multiplication. Four possible combinations of two single bit binary numbers exist:

📌 Example: 1101 × 101

    1101
  ×   101
    -----
    1101   (1st product term)
   0000    (2nd product term)
  1101     (3rd product term)
  -----
  1000001

4. Binary Multiplication by Shifting Left Binary Multiplication by shifting left: A left shift by a single bit is equivalent to multiplication by 2. A left shift by two bits is equivalent to multiplication by 4. The multiplication factor is determined by 2^n where n is the number of bit shifts.

📌 Example:

• 00011 (3) original binary number
• 00110 (6) shifted left by 1 bit (×2)
• 01100 (12) shifted left by 2 bits (×4)
• 11000 (24) shifted left by 3 bits (×8)

5. Binary Division Division in binary follows the same procedure as decimal division.

📌 Example: 1101 ÷ 101

     10
101 | 1101
     101
     ---
      011
      000
      ---
       11

Result: 10₂ with remainder 11₂

6. Binary Division by Shifting Right Binary Division by shifting right: A right shift by a single bit is equivalent to division by 2. A right shift by two bits is equivalent to division by 4. The division factor is determined by 2^n where n is the number of bit shifts.

📌 Example:

• 10100 (20) original binary number
• 01010 (10) shifted right by 1 bit (÷2)
• 00101 (5) shifted right by 2 bits (÷4)

Signed and Unsigned Binary Numbers

Digital systems handle both positive and negative numbers. In a digital system that uses the Binary number system, positive and negative signs are represented in terms of binary 0 and 1. The digital system sets aside the most significant digit (bit) to represent the sign:

• MSB set to 1 indicates a negative number
• MSB set to 0 indicates a positive number

Thus +13 and -13 are represented as 01101 and 11101 respectively. This representation is known as the Signed-Magnitude representation.

Digital systems also handle Unsigned numbers, which are assumed to be positive and do not have the most significant sign bit. Thus 11101₂ represents -13 in signed binary and 29 in unsigned binary. A digital system must be notified beforehand whether to treat a binary number as signed or unsigned.

1's & 2's complement

A better way to handle signed numbers is to represent negative signed numbers in their 2's complement form. This allows direct manipulation of positive as well as negative numbers without having to worry about setting the MSB for sign.

🔑 Definition — 1's complement: Obtained by simply inverting all the bits of a binary number.

🔑 Definition — 2's complement: Obtained by first taking the 1's complement of a number and then adding a 1.

📌 Example: Obtaining 2's complement of 13

01101    The number 13
10010    1's complement of 13 (invert all bits)
+    1
10011    2's complement of 13

In a 2's complement number system, all negative numbers are represented in their 2's complement form, and all positive numbers are represented in their actual form. Negative numbers can be identified by their MSBs which are set to 1. Thus +13 is 01101 and -13 is 10011.

💡 Why this matters: Using 2's complement allows addition and subtraction to be performed by the same circuit, simplifying digital system design.

📌 Example: +13 + (-13) = 0

01101   (+13)
10011   (-13 in 2's complement)
-----
100000  (carry discarded, result is 00000 = 0)

📌 Example: +7 + (-13) = -6

10011   (-13 in 2's complement)
00111   (+7)
-----
11010   (result = -6 in 2's complement)

To find the magnitude of 11010:

11010    Original number
00101    1's complement
+    1
00110    2's complement = 6

Addition and Subtraction Operations with Signed Binary

An additional benefit of using 2's complement representation is that both add and subtract operations can be performed by addition.

Four cases of adding/subtracting numbers using 2's complement:

Both numbers are positive:

0101  (+5)
0010  (+2)
-----
0111  (+7)

Both numbers are negative:

1011  (-5)
1110  (-2)
-----
11001 (-7, carry from MSB discarded)

One number positive, its magnitude larger than the negative number:

0101  (+5)
1110  (-2)
-----
10011 (+3, carry from MSB discarded)

One number positive, its magnitude smaller than the negative number:

1011  (-5)
0010  (+2)
-----
1101  (-3)

These examples demonstrate that add and subtract operations can be carried out by an adder circuit if numbers are represented in their 2's complement form. A separate circuit to perform subtractions is not required.

Range of Signed and Unsigned Binary Numbers

Three different types of Binary representations have been discussed: Unsigned Binary (only positive numbers), Sign-Magnitude (both positive and negative), and 2's complement signed (both positive and negative). Each representation can represent a certain range of binary numbers determined by the total number of bits used.

A 3-bit unsigned binary number can have values ranging between 000 and 111. Adding 100 and 111 results in 1011 (out of range for 3 bits). A 4-bit sign magnitude number can handle numbers between -7 and +7. A 4-bit 2's complement signed number range is between -8 to +7.

📌 Range of values represented by 4-bit Binary representations:

Range Formulas (where n = number of bits):

• Signed Magnitude: Range is (2^n-1 - 1) to -(2^n-1 - 1)
• 2's complement signed: Range is (2^n-1 - 1) to -(2^n-1)
• Unsigned: Range is 0 to (2^n - 1)

⭐ Key Takeaways

The two primary methods for binary-to-decimal conversion are Sum-of-Weights (writing out powers of 2) and Sum-of-non-zero terms (adding only weights where binary digits are 1). For decimal-to-binary conversion of integers, use Repeated Division-by-2 (reading remainders bottom-to-top), and for fractions use Repeated Multiplication-by-2 (reading integer parts top-to-bottom). Binary arithmetic operations follow identical rules to decimal, but multiplication and division can be efficiently performed by shifting left or right by the appropriate number of bits. Signed binary numbers require special handling, and the 2's complement representation is the most efficient method because it allows both addition and subtraction to be performed using only an adder circuit. Remember the range limitations: for n bits, unsigned numbers range from 0 to 2^n-1, signed magnitude ranges from -(2^n-1-1) to +(2^n-1-1), and 2's complement ranges from -(2^n-1) to +(2^n-1-1).

🧠 Quick Revision Questions

1. Convert the binary number 11011.011₂ to its decimal equivalent using the Sum-of-Weights method.
2. Convert the decimal number 57 to binary using the Repeated Division-by-2 method.
3. Convert the decimal fraction 0.4375 to binary using the Repeated Multiplication-by-2 method.
4. What is the 2's complement representation of -9 using 5 bits, and what is the decimal value represented by the 2's complement number 10110?
5. What are the valid number ranges for a 5-bit unsigned number, a 5-bit sign-magnitude number, and a 5-bit 2's complement number?

📘 Lecture 3 — NUMBER SYSTEMS

📖 Overview: This lecture examines number representation and arithmetic in digital systems, focusing on overflow conditions in binary addition, floating-point number formats for representing very large and very small values, and the hexadecimal number system as a compact notation for binary strings. Understanding these concepts is essential for designing reliable digital circuits and correctly interpreting computational results.

🗂️ Topics Covered

The lecture begins by defining overflow conditions in binary arithmetic and determining overflow for 2's complement numbers through example analysis. It then introduces floating-point numbers, explaining decimal and binary floating-point formats, biased exponent representation, and arithmetic operations on floating-point numbers. The 64-bit double-precision format is briefly covered. Finally, the hexadecimal number system is presented, including counting, conversions between binary, decimal, and hexadecimal, and hexadecimal addition and subtraction.

📝 Lecture Summary

Range of Numbers and Overflow

When arithmetic operations such as Addition, Subtraction, Multiplication and Division are performed on numbers, the results generated may exceed the range of values specified by the Binary representations. The values that exceed the specified range cannot be correctly represented and are considered as Overflow values.

For example, a 3-bit Unsigned representation can correctly represent Unsigned Binary values in the range 0 to 2³-1 (0 to 7). Adding 3-bit Unsigned 010 (2) to another 3-bit Unsigned 111 (7) results in 1001 (9) which exceeds the 3-bit unsigned range and is considered to be an Overflow. Similarly, 1011 (-5) and 1100 (-4) values represented in 4-bit 2's complement form when added together result in 10111 (-9) which exceeds the 4-bit 2's complement range of values (2⁴⁻¹-1) and -(2⁴⁻¹) (7 to -8) and is considered as an Overflow.

Determining Overflow Conditions for 2's Complement Numbers

The Overflow condition can be easily determined when two numbers represented in 2's Complement form are added together. Analysis of the four addition operations indicates that Overflow conditions can be determined by looking at the most significant sign bits of the two numbers to be added together and the most significant sign bits of the sum result.

In examples where an Overflow has occurred, the sign bits of both the numbers are the same, indicating both numbers to be positive or negative respectively. The sign bit of the sum term in both cases is opposite to the signs of the two numbers being added together, which can never be. Thus the erroneous sign bits indicate the Overflow conditions.

Case 1: Both numbers are positive 0101 (+5) + 0100 (+4) = 1001 (-7) 🔑 Definition — Overflow Condition for 2's Complement Addition: When both numbers have the same sign and the result has the opposite sign, an overflow has occurred.

Case 2: Both numbers are negative 1011 (-5) + 1100 (-4) = 10111 (discard carry → +7) The result indicates a positive number as the most significant bit is 0, which is incorrect.

Case 3: Positive number magnitude larger than negative number magnitude 0101 (+5) + 1100 (-4) = 10001 (discard carry → +1) — Correct result.

Case 4: Negative number magnitude larger than positive number magnitude 1011 (-5) + 0100 (+4) = 1111 (-1) — Correct result.

💡 Why this matters: Being able to detect overflow is critical for ensuring the correctness of arithmetic operations in processors and digital systems.

Floating-Point Numbers

Modern computers can handle large binary numbers such as 64-bit unsigned numbers; the maximum decimal number that can be represented using the 64-bit unsigned representation is 2⁶⁴-1, which is nearly equal to 1.84 × 10¹⁹.

The floating-point number system, based on scientific notation, is capable of representing very large and very small numbers without having to increase the number of bits. Numbers having an integer part and a fraction part are also easily represented using the Floating-Point representation.

Floating point numbers are defined using certain standards. The ANSI/IEEE Standard 754 defines a 32-bit Single-Precision Floating Point format for binary numbers.

32-bit Single-Precision F.P. Format:

• S (1 bit) — Sign bit (0 = positive, 1 = negative)
• Exponent (8 bits) — Represents the exponent
• Mantissa (23 bits) — Represents the magnitude of the number

Decimal Number Floating-Point Format

A 15-digit decimal floating point format uses:

• Sign (1 digit) — +/-
• Exponent (2 digits)
• Mantissa (12 digits)

The number 6918.3125 can be written as 6.9183125 × 10³. The decimal point is moved to the extreme left of the number (normalized) so that the magnitude is represented by a fraction part. The number 0.69183125 × 10⁴ is represented in decimal f.p. notation as: + 04 691831250000

Using this 15-digit notation, the largest number that can be represented is 0.999,999,999,999 × 10⁹⁹.

Representing Negative Exponent Values

The 15-digit decimal floating-point format does not allow negative exponents. Two options are available:

1. Increase the Exponent field by one digit to allow for the sign
2. Use a Biased Exponent scheme — add the value 50 to the exponent and write the result in the exponent field

Using this biased scheme, the maximum positive exponent value that can be represented is 49 (49 + 50 = 99). The smallest exponent that can be represented is -50 (-50 + 50 = 0). The range of decimal numbers becomes 0.999,999,999,999 × 10⁴⁹ to 0.999,999,999,999 × 10⁻⁵⁰.

Representing Zero and Infinity Values

The number zero can be represented by setting all Mantissa digits to 0. The solution to represent infinity is to set aside a biased exponent value. By allowing numbers having the maximum and minimum exponent values to be 49 and -48 instead of 49 and -50, and selecting 49 as the biased number: Biased exponent values range between 98 (49+49) and 01 (-48+49). The biased exponent value 00 can be used to represent zero, and 99 can be used to represent infinity.

Representing a Decimal fraction number in 32-bit Single-Precision Floating Point format

The 32-bit Single Precision Floating Point format represents the Exponent value as a Biased Number, reserving the exponent values 0 and 255 to represent the value zero and infinity respectively. The range of exponent value is from +127 to -126.

Stepwise representation of decimal number 6918.3125:

1. Convert Decimal to Binary: 6918.3125₁₀ = 1101100000110.0101₂
2. Normalize: 1.1011000001100101 × 2¹²
3. Represent exponent in Biased-127: 12 + 127 = 139 = 10001011₂

Result: 0 10001011 10110000011001010000000

The Mantissa is 10110000011001010000000 instead of 11011000001100101000000 because all binary numbers that are normalized always have a leading 1. In the f.p. format the leading 1 is not written, however it is taken into account in all calculations. The leading 1 which is not written is known as a hidden 1.

Arithmetic Operations on Floating Point Numbers

Arithmetic operations can be directly performed on floating point numbers by manipulating the mantissa and exponent parts.

Addition/Subtraction: Two floating point numbers can be added by adding together their mantissas, ensuring that the exponent parts of both numbers are the same. If the exponents are not equal, the decimal point has to be adjusted for one number.

Multiplication: Performed by multiplying the mantissas together and adding their corresponding exponents.

Division: Performed by dividing the mantissa parts and subtracting the corresponding exponents.

Examples:

• 723 + 134 = exponent 2, mantissa 8.57
• 723 (exp 2, mantissa 7.23) + 2015 (exp 3, mantissa 2.015): Adjust first number to exp 3, mantissa 0.723 → result exp 3, mantissa 2.738
• 723 × 34 = exponent 3, mantissa 24.582
• 697 ÷ 41 = exponent 1, mantissa 1.7

64-bit Double-Precision Floating Point format

The 32-bit Single precision floating point representation can represent the largest positive or negative number of the order of 2¹²⁷ and the smallest of the order of 2⁻¹²⁶. To represent larger numbers, 64-bit Double Precision floating point format is used. It sets aside 11 bits to represent the exponent as Biased-1023 and a mantissa of 52 bits, with a single bit for the sign.

Hexadecimal Numbers

The Hexadecimal number system is a base 16 number system and therefore has 16 digits and is used primarily to represent binary strings in a compact manner. Hexadecimal is not used by a Digital System but for our convenience. Each Hexadecimal digit can represent a 4-bit Binary Number.

Counting in Hexadecimal

Counting in Hexadecimal is similar to other number systems. The maximum value represented by a single Hexadecimal digit is F (decimal 15). Decimal 16 is represented as 10₁₆ or 10H.

Binary to Hexadecimal Conversion

The Binary string is divided into small groups of 4-bits starting from the least significant bit. Each 4-bit binary group is replaced by its Hexadecimal equivalent.

Example: 11010110101110010110₂ → 1101 0110 1011 1001 0110 → D6B96₁₆

Binary strings which cannot be exactly divided into a whole number of 4-bit groups have 0's appended in the most significant bits to complete a group.

Example: 1101100000110₂ → 0001 1011 0000 0110 → 1B06₁₆

Hexadecimal to Binary Conversion

Each digit of the Hexadecimal number is replaced by an equivalent binary string of 4-bits.

Example: FD13₁₆ → 1111 1101 0001 0011₂

Decimal to Hexadecimal Conversion

Method 1 (Indirect): Convert decimal to binary, then binary to hexadecimal.

Method 2 (Repeated Division-by-16): The decimal number is continuously divided by 16.

Example: Converting 2096₁₀ to Hexadecimal:

• 2096 ÷ 16 = 131 remainder 0
• 131 ÷ 16 = 8 remainder 3
• 8 ÷ 16 = 0 remainder 8 Result: 830₁₆

Hexadecimal to Decimal Conversion

Method 1 (Indirect): Convert hexadecimal to binary, then binary to decimal.

Method 2 (Sum-of-Weights): A Hexadecimal number can be directly converted into Decimal by using the sum of weights method.

Example: CA02₁₆ = (C × 16³) + (A × 16²) + (0 × 16¹) + (2 × 16⁰) = (12 × 4096) + (10 × 256) + (0 × 16) + (2 × 1) = 49152 + 2560 + 0 + 2 = 51714₁₀

Hexadecimal Addition and Subtraction

Numbers represented in Hexadecimal can be added and subtracted directly without converting them into decimal or binary equivalents.

Hexadecimal Addition Example:

    1 ← Carry
    2 A C 6
+   9 2 B 5
-----------
    B D 7 B

Hexadecimal Subtraction Example:

  1 1 1 ← Borrow
    9 2 B 5
-   2 A C 6
-----------
    6 7 E F

⭐ Key Takeaways

Overflow in 2's complement addition is detected when the sign bits of both operands are the same but the result's sign bit is opposite. Floating-point representation using a sign bit, biased exponent, and mantissa with a hidden 1 allows computers to handle a vast range of numbers including fractions and extremely large/small values. The IEEE 754 standard defines single-precision (32-bit, 8-bit exponent biased by 127) and double-precision (64-bit, 11-bit exponent biased by 1023) formats. Hexadecimal (base-16) provides a compact human-readable notation for binary strings, with each hex digit exactly representing four binary bits. Arithmetic operations on floating-point numbers require exponent alignment for addition/subtraction, while multiplication adds exponents and division subtracts them.

🧠 Quick Revision Questions

1. How can you detect an overflow condition when adding two 2's complement numbers?
2. What is the purpose of using a biased exponent in floating-point representation, and what bias value is used for 32-bit single precision?
3. What is a "hidden 1" in the IEEE 754 floating-point format, and why is it not explicitly stored in the mantissa?
4. Convert the binary number 1101100000110 to its hexadecimal equivalent.
5. Describe the steps to perform floating-point addition when the two numbers have different exponents.

📘 Lecture 4 — NUMBER SYSTEMS & CODES

📖 Overview: This lecture covers the Octal number system (base 8), its conversions to and from binary and decimal, and arithmetic operations. It then explores alternate binary representations including Excess Code, BCD Code, Gray Code, Alphanumeric Codes (ASCII), and introduces the Parity Method for error detection.

🗂️ Topics Covered

The lecture begins by introducing the Octal number system and counting in Octal. It then details methods for Binary to Octal, Octal to Binary, Decimal to Octal, and Octal to Decimal conversions, followed by Octal addition and subtraction. The discussion shifts to different binary representations and alternate forms like Excess Code, BCD Code (and BCD addition), Gray Code (and its application in shaft encoders). Finally, it covers Alphanumeric Codes including ASCII and Extended ASCII, and concludes with the Parity Method for error detection.

📝 Lecture Summary

Octal Numbers

The Octal Number System is a base-8 system with digits ranging from 0 to 7. It was used in earlier digital systems to provide a convenient way to represent long strings of binary numbers. Each Octal digit can represent a 3-bit Binary Number.

🔑 Definition — Octal Number System: A base-8 number system using digits 0-7, where each digit represents a 3-bit binary number.

Counting in Octal Number System

Counting in Octal is similar to other number systems. The maximum value for a single digit is 7. For larger values, multiple digits are used. For example, decimal 8 is represented as 10₈.

🔑 Definition — Counting in Octal: Uses a combination of digits (0-7), where 10₈ represents decimal 8.

Binary to Octal Conversion

Converting Binary to Octal is simple: divide the binary string into groups of 3 bits starting from the least significant bit (LSB). Replace each 3-bit group with its Octal equivalent. If the binary string cannot be divided exactly, append 0's to the most significant bits.

📐 Formula: Binary → Binary groups of 3 bits (from LSB) → Replace with Octal digit

📌 Example: Convert binary 111010110101110010110 to Octal.

1. Divide into 3-bit groups: 111 010 110 101 110 010 110
2. Replace each group: 7 2 6 5 6 2 6
3. Result: 7265626₈

📌 Example: Convert binary 1101100000110 to Octal.

1. Divide into 3-bit groups: 1 101 100 000 110
2. Append 0's to complete the group: 001 101 100 000 110
3. Replace each group: 1 5 4 0 6
4. Result: 15406₈

Octal to Binary Conversion

Converting from Octal to Binary is also simple: replace each Octal digit with its equivalent 3-bit binary string.

📌 Example: Convert Octal 1726₈ to Binary.

1. Replace each digit: 1→001, 7→111, 2→010, 6→110
2. Result: 001111010110

Decimal to Octal Conversion

There are two methods:

1. Indirect Method: Convert decimal to binary first, then binary to Octal.
2. Repeated Division-by-8 Method: Continuously divide the decimal number by 8 (the base of Octal). The remainders, read in reverse order, give the Octal equivalent.

📌 Example: Convert decimal 2075 to Octal using Repeated Division-by-8.

Octal to Decimal Conversion

Two methods:

1. Indirect Method: Convert Octal to binary first, then binary to decimal.
2. Sum-of-Weights Method: Multiply each Octal digit by 8 raised to its positional power.

📐 Formula: Digit_n * 8^n + ... + Digit_1 * 8^1 + Digit_0 * 8^0

📌 Example: Convert Octal 4033₈ to Decimal. 4 x 8³ + 0 x 8² + 3 x 8¹ + 3 x 8⁰ = (4 x 512) + (0 x 64) + (3 x 8) + (3 x 1) = 2048 + 0 + 24 + 3 = 2075₁₀

Octal Addition and Subtraction

Octal numbers can be added and subtracted directly using rules similar to decimal or binary arithmetic. This allows large binary numbers to be quickly processed.

📌 Octal Addition Example:

  1      (Carry)
  7 6 0 2
+ 5 7 7 1
-----------
1 5 5 7 3

📌 Octal Subtraction Example:

  1      (Borrow)
  7 6 0 2
- 5 7 7 1
-----------
1 6 1 1

Working with different Binary representations

Four ways of representing binary numbers have been discussed:

• Unsigned binary
• Signed-Magnitude form
• 2’s Complement form
• Floating point notation

Different representations help in processing. For example, 2's complement helps handle positive and negative numbers. Floating point handles numbers with integer and fraction parts. Digital systems generally process data of the same type, so the system must be informed of the data type before processing.

💡 Why this matters: When writing computer programs, variables and their data types are declared. During execution, the computer knows the data type and the operations that can be performed on it.

Alternate forms of Binary representations

Many alternate binary representations support specific applications:

• Biased Code or Excess Code: Used by floating point numbers to represent positive and negative exponent values.
• Gray Code: Used by shaft encoders to read angular position.
• BCD Code: Used to display decimal digits on 7-Segment Display Panels.

The Excess Code

The Excess Code (or Biased Code) is useful because positive and negative numbers in 2's complement form are not on a uniformly increasing scale, making magnitude comparison difficult. The Excess-8 code assigns 0000 to -8 (the lowest number in the range) and 1111 to +7 (the highest number). It is obtained by adding 8 (a bias) to all decimal numbers in the range.

🔑 Definition — Excess Code: A representation where a fixed bias (e.g., 8) is added to the lowest number in the range so that its code is all zeros, creating a uniformly increasing scale.

📌 Example: For the range +7 to -8, Excess-8 code uses 0000 for -8, 1000 for 0, and 1111 for +7.

The BCD Code

Binary Coded Decimal (BCD) is a 4-bit binary code used to represent decimal digits 0-9. Only the first 10 combinations (0000 to 1001) are valid. The remaining 6 combinations (1010 to 1111) are invalid.

🔑 Definition — BCD Code: A 4-bit code where each decimal digit (0-9) is represented by its 4-bit binary equivalent.

📌 Example: Decimal 17 is represented in BCD as 0001 0111 (two separate 4-bit groups for 1 and 7), not as 10001 in unsigned binary.

BCD Addition: Multi-digit BCD numbers can be added. If the sum of two BCD digits exceeds 9 or generates a carry, 6 (0110) is added to the invalid number.

📌 Example: Add 23 + 48 in BCD.

1. 0010 0011 + 0100 1000 = 0110 1011
2. LSB sum 1011 (11) is invalid BCD.
3. Add 6: 1011 + 0110 = 1 0001 (carry 1)
4. Add carry to next digit: 0110 + 0100 + 1 = 0111
5. Result: 0111 0001 → 71

The Gray Code

The Gray Code is not a positional code and has no weights assigned to its bit positions. Its key feature is that successive values differ by only one bit.

🔑 Definition — Gray Code: A non-positional binary code where consecutive numbers differ in only a single bit position.

📌 Example: Decimal 2 is 0010 in binary but 0011 in Gray Code. Decimal 3 is 0011 in binary but 0010 in Gray Code.

Gray Code Application (Shaft Encoder): In a shaft encoder, a rotating disk has conducting and non-conducting areas detected by brushes. With binary encoding, brush misalignment can cause incorrect transient readings (e.g., 1→3→2 instead of 1→2). Gray Code eliminates this error because only one bit changes per step, so even with misaligned brushes, the output is correct.

💡 Why this matters: Gray Code based shaft encoders allow angular position to be determined accurately even when sensing brushes are misaligned.

Alphanumeric Codes

Digital systems process text information as well as numbers. Alphanumeric codes represent letters, punctuation, and numbers in textual form.

ASCII Code: The American Standard Code for Information Interchange is a 7-bit code representing 128 unique codes.

• Codes 011 0000 (30h) to 011 1001 (39h): Numbers 0-9
• Codes 100 0001 (41h) to 101 1010 (5Ah): Upper case A-Z
• Codes 110 0001 (61h) to 111 1010 (7Ah): Lower case a-z
• Codes 000 0000 (0h) to 001 1111 (1Fh): 32 Control characters

Extended ASCII Code: An 8-bit code giving 256 unique codes. The extended 128 codes represent graphic symbols.

Parity Method

The Parity Method uses a parity bit (an extra bit appended to data) to detect errors during storage or transmission. Two schemes are used:

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

🔑 Definition — Parity Bit: An extra bit appended to binary data for error detection, set to make the total count of 1's either even (Even Parity) or odd (Odd Parity).

📌 Example: Data = 10001101. In Even Parity, there are 4 ones (even), so parity bit = 0. Transmitted 9-bit message: 100011010. If received as 101011010, the number of ones is 5 (odd), indicating an error. The receiver cannot locate the error and must request retransmission.

💡 Why this matters: A single parity bit can only detect an odd number of bit errors. If an even number of bits are corrupted (e.g., 2 bits), the error goes undetected.

⭐ Key Takeaways

The Octal number system provides a convenient shorthand for representing long binary strings, with each Octal digit corresponding to a 3-bit binary group. Conversion between binary and Octal is straightforward using grouping. For decimal-to-Octal conversion, the repeated division-by-8 method is direct. The Excess Code is essential for uniformly representing signed numbers in contexts like floating point exponents. BCD is critical for decimal display systems, requiring specific addition rules (adding 6 for invalid sums). Gray Code is vital in electromechanical applications like shaft encoders to prevent transient errors from sensor misalignment. ASCII code is the universal standard for representing text in digital systems, and the Parity Method introduces the fundamental concept of error detection using a single additional bit.

🧠 Quick Revision Questions

1. Convert the binary number 11010110 to its Octal equivalent.
2. Convert decimal 1563 to Octal using the repeated division-by-8 method.
3. Add the following BCD numbers: 35 + 47. Show the steps if a correction is needed.
4. Why is Gray Code preferred over standard binary for shaft encoders?
5. In Even Parity, data 10110110 is transmitted. What should the appended parity bit be, and how would the receiver detect a 1-bit error?

📘 Lecture 05 — LOGIC GATES

📖 Overview: This lecture introduces the fundamental building blocks of digital systems—Logic Gates. It explains how these gates perform basic operations on binary information, including their symbolic representation, function tables, timing diagrams, and practical applications. Understanding these gates is essential for designing and analyzing complex digital circuits.

🗂️ Topics Covered

The lecture covers the three fundamental logic gates (AND, OR, NOT) and their operation, function tables, timing diagrams, and practical applications. It then introduces the NAND and NOR gates, their function tables and timing diagrams, the concept of alternate symbolic representations for AND and OR gates, and the use of the NAND gate as a universal gate capable of implementing AND, OR, and NOT functions.

📝 Lecture Summary

AND Gate

The AND Gate performs a logical multiplication function. It has multiple inputs and a single output, with two-input AND gates being the most common. The output is 1 only when all inputs are at logic level 1; for all other input combinations, the output is 0.

🔑 Definition — AND Gate: A logic gate that produces a HIGH (1) output only when all its inputs are HIGH (1). 📐 Formula: F = A . B (where '.' is the AND operator) → The output is the logical product of inputs A and B. 📌 Example: With inputs A=1 and B=1, the output F = 1 . 1 = 1. If A=0 and B=1, the output F = 0 . 1 = 0.

💡 Why this matters: A key application of the AND gate is to enable or disable signals. For example, a counter can be stopped from counting by connecting its clock input through an AND gate. Setting the enable/disable input to 0 forces the AND gate output to 0, blocking the clock pulses. Setting it to 1 allows the clock signal to pass through to the counter.

OR Gate

The OR Gate performs a Boolean add function. It has multiple inputs and a single output. The output is 1 when any one input is at logic level 1; the output is 0 only when all inputs are 0.

🔑 Definition — OR Gate: A logic gate that produces a HIGH (1) output if at least one of its inputs is HIGH (1). 📐 Formula: F = A + B (where '+' is the OR operator) → The output is the logical sum of inputs A and B. 📌 Example: With inputs A=0 and B=1, the output F = 0 + 1 = 1. With A=0 and B=0, the output F = 0 + 0 = 0.

💡 Why this matters: A practical application is a car door alarm system. If any door is open, the corresponding door circuit outputs a 1. These signals are fed into a 4-input OR gate, which outputs a 1 if any or all doors are open, activating the alarm.

NOT Gate

The NOT Gate, also known as an Inverter, performs an inversion function. It has a single input and a single output. The input signal is inverted at the output.

🔑 Definition — NOT Gate (Inverter): A logic gate that produces an output that is the logical complement of its single input. 📐 Formula: F = A̅ (where the bar indicates the inverse of A) → The output is the opposite value of the input. 📌 Example: If input A = 1, output F = 0. If input A = 0, output F = 1.

💡 Why this matters: The NOT gate is used to generate the 1's complement of a binary number by inverting all its bits. An 8-bit number can be inverted using a circuit with 8 NOT gates.

AND & OR Gate Alternate Symbols

The AND gate and the OR gate can be represented by complementary symbols. The AND gate can be represented by its complementary OR gate symbol with inverted inputs and output (bubbles). The OR gate can be represented by its complementary AND gate symbol with inverted inputs and output (bubbles).

NAND Gate

The NAND Gate performs a function equivalent to an AND gate followed by a NOT gate (AND-NOT). It has multiple inputs and a single output. The output is 0 only when all inputs are 1s; for all other combinations, the output is 1.

🔑 Definition — NAND Gate: A logic gate that produces a LOW (0) output only when all its inputs are HIGH (1); it is the complement of the AND gate. 📐 Formula: F = A̅．B̅̅ → The output is the inverse of the logical product of inputs A and B. 📌 Example: With inputs A=1 and B=1, the output F = 1 . 1 = 0. With A=0 and B=1, the output F = 0 . 1 = 1.

NAND Gate as a Universal Gate

The NAND gate can be used to implement the functions of AND, OR, and NOT gates.

1. NOT Gate Implementation: A NOT gate is implemented by connecting both inputs of a NAND gate together, reducing its function table to that of a NOT gate.
2. AND Gate Implementation: An AND gate is implemented by connecting a NOT gate (made from a NAND gate) to the output of a NAND gate, canceling the inherent inversion.
3. OR Gate Implementation: An OR gate is implemented using a combination of three NAND gates, based on the alternate symbolic representation of the OR gate.

NOR Gate

The NOR Gate performs a function equivalent to an OR gate followed by a NOT gate (OR-NOT). It has multiple inputs and a single output. The output is 1 only when all inputs are 0s; for all other combinations, the output is 0.

🔑 Definition — NOR Gate: A logic gate that produces a HIGH (1) output only when all its inputs are LOW (0); it is the complement of the OR gate. 📐 Formula: F = A̅ + B̅̅ → The output is the inverse of the logical sum of inputs A and B. 📌 Example: With inputs A=0 and B=0, the output F = 0 + 0 = 1. With A=1 and B=0, the output F = 1 + 0 = 0.

⭐ Key Takeaways

The three fundamental logic gates are AND, OR, and NOT, each defined by a unique function table and expression. The NAND and NOR gates are derived from these fundamentals by adding an inverter. The NAND gate is considered a universal gate because it alone can be used to construct AND, OR, and NOT circuits. Logic gates are not just theoretical concepts; they have direct practical applications such as enabling/disabling clock signals with an AND gate and implementing an alarm system with an OR gate.

🧠 Quick Revision Questions

1. What is the output of a two-input AND gate when its inputs are 1 and 0?
2. Which logic gate can be used to generate the 1's complement of a binary number?
3. State the conditions under which a two-input NAND gate produces an output of 0.
4. How can a NOT gate be implemented using only a NAND gate?
5. What is the Boolean expression for a two-input NOR gate?

📘 Lecture 06 — LOGIC GATES & OPERATIONAL CHARACTERISTICS

📖 Overview: This lecture explores the use of NOR and NAND gates as universal gates, demonstrates how to implement fundamental logic gates using them, and introduces practical applications. It also covers the operational characteristics, integrated circuit technologies, and performance parameters of digital logic gates, providing a bridge from theoretical logic to real-world circuit design.

🗂️ Topics Covered

The lecture begins by demonstrating how a NOR gate can be used as a universal gate to implement NOT, OR, and AND gates. It then extends this concept to show how NAND and NOR gates can be used to implement each other. Practical applications for NAND and NOR gates are presented through real-world examples like exhaust fan failure detection and washing machine control. The lecture introduces the Exclusive-OR (XOR) and Exclusive-NOR (XNOR) gates, including their function tables, timing diagrams, and applications in parity detection. Finally, the lecture covers the operational characteristics of digital circuits, including transistor-level implementations (BJT and CMOS), integrated circuit technologies (CMOS, TTL, ECL, etc.), common IC logic gate types, and key performance parameters like DC supply voltage, noise margin, power dissipation, propagation delay, and fan-out.

📝 Lecture Summary

NOR Gate as a Universal Gate

The NOR gate can be used as a Universal Gate because it can be combined to perform the functions of AND, OR, and NOT gates. This is a key concept in digital design, as it allows complex circuits to be built using only one type of gate.

4. NOT Gate Implementation

A NOT gate can be implemented using a NOR gate by connecting both of the NOR gate's inputs together. This makes the combinations with dissimilar inputs redundant, reducing the NOR gate's function table to that of a NOT gate.

🔑 Definition — NOR Gate Implementation of a NOT Gate: A NOR gate with both inputs tied together acts as a NOT gate because the only possible input states are 00 or 11, which invert the input.
📌 Example: If input A is 0, the NOR gate has inputs (0,0), producing an output of 1. If input A is 1, the inputs are (1,1), producing an output of 0.

5. OR Gate Implementation

A NOR gate performs the OR-NOT function. To get an OR gate, the NOT part at the output must be cancelled. This is done by connecting a NOT gate (implemented using another NOR gate) to the output of the first NOR gate. The two NOT gates cancel each other out.

🔑 Definition — NOR Gate Implementation of an OR Gate: Two cascaded NOR gates, where the second NOR gate is configured as an inverter, produce the OR function.
📌 Example: An OR gate is implemented by connecting the output of NOR gate 1 to the input of a second NOR gate (2) which is wired as an inverter.

6. AND Gate Implementation

An AND gate can be implemented using a combination of three NOR gates. The implementation is based on the alternate symbolic representation of an AND gate, which is an OR gate with bubbles (inverters) at its inputs and output.

🔑 Definition — NOR Gate Implementation of an AND Gate: Three NOR gates are used: the first two (1 & 2) act as inverters on the inputs, and the third (3) acts as a NOR gate, creating the final AND function.
📌 Example: Inputs A and B are each inverted by two separate NOR gates (1 and 2). These inverted signals are then fed into a third NOR gate (3), whose output is the AND function of A and B.

NAND-NOR Universal Gates

Both NAND and NOR gates are considered universal gates. A NAND gate can be used to implement a NOR gate, and a NOR gate can be used to implement a NAND gate.

1. NAND gate Implementation using NOR gates

A NAND gate is implemented by first creating an AND gate (using three NOR gates) and then adding an inverter (NOT gate) at the output. The NOT gate is also implemented using a NOR gate.

🔑 Definition — NAND Gate from NOR Gates: A NAND gate can be built using four NOR gates; three for the AND function and one for the final inverter.
📌 Example: NOR gates 1, 2, and 3 create the AND function. NOR gate 4 is configured as an inverter and placed at the output of the AND gate to create the NAND function.

2. NOR gate Implementation using NAND gates

A NOR gate is implemented by first creating an OR gate (using three NAND gates) and then adding an inverter (NOT gate) at the output. The NOT gate is also implemented using a NAND gate.

🔑 Definition — NOR Gate from NAND Gates: A NOR gate can be built using four NAND gates; three for the OR function and one for the final inverter.
📌 Example: NAND gates 1, 2, and 3 create the OR function. NAND gate 4 is configured as an inverter and placed at the output of the OR gate to create the NOR function.

NAND and NOR Gate Applications

The unique output properties of NAND and NOR gates make them useful for detecting specific conditions in a system.

• NAND Gate: The output is 0 only when all inputs are 1.
• NOR Gate: The output is 1 only when all inputs are 0.

🔑 Definition — NAND Gate Application (Exhaust Fan Failure): A NAND gate can be used to activate an alarm when any fan fails. If fans are working, they output a 1, and the NAND gate outputs a 0. If a fan fails (outputs 0), the NAND gate output becomes 1, activating the alarm.
📌 Example: A warehouse with three fans has sensors that output 1 when a fan is working. These three outputs are connected to a 3-input NAND gate. The output is 0 when all fans work, but becomes 1 if any one fan fails, triggering an alarm.

🔑 Definition — NOR Gate Application (Washing Machine Controller): A NOR gate can be used to shut down a system when any error condition occurs. When all sensors indicate a safe condition (output 0), the NOR gate outputs a 1. If any sensor detects an error (output 1), the NOR gate output becomes 0, which can turn off the machine.
📌 Example: A washing machine has sensors for lid open, low water, and overload. These sensors output a 1 when an error is detected. The outputs are fed into a 3-input NOR gate. In normal operation (all 0s), the NOR output is 1. If any error occurs (one or more 1s), the NOR output becomes 0, switching off the washing machine.

Exclusive-OR and Exclusive-NOR Gates

The XOR (Exclusive-OR) and XNOR (Exclusive-NOR) gates are fundamental building blocks in digital logic. They are used to compare inputs and detect specific patterns of bits, particularly for parity detection.

1. Exclusive-OR (XOR) Gate

The XOR gate performs a function that is equivalent to a combination of NOT, AND, and OR gates, but it is commonly available as a basic IC component. The output of a two-input XOR gate is 1 when the inputs are dissimilar and 0 when the inputs are the same.

🔑 Definition — XOR Gate: A digital logic gate whose output is 1 if the number of 1s at its input is odd (for multiple inputs). The Boolean expression for a two-input XOR gate is F = A ⊕ B.
📐 Formula: F = A ⊕ B (for 2 inputs) or F = A ⊕ B ⊕ C ⊕ ... N (for multiple inputs).
📌 Example (Function Table): For a two-input XOR gate:

• Input (0,0) → Output 0
• Input (0,1) → Output 1
• Input (1,0) → Output 1
• Input (1,1) → Output 0

2. Exclusive-NOR (XNOR) Gate

The XNOR gate is the complement of the XOR gate. The output of a two-input XNOR gate is 1 when the inputs are the same and 0 when the inputs are dissimilar.

🔑 Definition — XNOR Gate: A digital logic gate whose output is 1 if the number of 1s at its input is even (for multiple inputs). The Boolean expression is F = A ⊕ B.
📐 Formula: F = A ⊕ B (for 2 inputs) or F = A ⊕ B ⊕ C ⊕ ... N (for multiple inputs). The overline indicates the complement of the XOR function.
📌 Example (Function Table): For a two-input XNOR gate:

• Input (0,0) → Output 1
• Input (0,1) → Output 0
• Input (1,0) → Output 0
• Input (1,1) → Output 1

XOR and XNOR Gate Applications (Parity Detection)

The ability of XOR and XNOR gates to detect dissimilar or similar inputs is used to build parity detection circuits. A parity bit is an extra bit added to a binary number to make the total number of 1s either odd (odd parity) or even (even parity).

🔑 Definition — Odd Number of 1s Detector: A circuit built from XOR gates that outputs a 1 if the input binary number has an odd number of 1s.
📌 Example: A 4-bit odd detector uses three XOR gates. For the input 1011 (three 1s), the output is 1, indicating an odd number of 1s. For 0011 (two 1s), the output is 0.

🔑 Definition — Even Number of 1s Detector: A circuit built from two XOR gates and one XNOR gate that outputs a 1 if the input binary number has an even number of 1s.
📌 Example: For the input 0000 (zero 1s, an even number), the output is 1. For the input 1011 (three 1s, an odd number), the output is 0.

Digital Circuits and Operational Characteristics

Theoretical logic gates have practical limitations. Real-world circuits have constraints related to voltage levels, current sourcing/sinking, and frequency response. For example, an inverter cannot drive an unlimited number of gates because the total current required by the load gates exceeds the current the inverter can provide. Also, the voltage representing a logic 1 or 0 is not always exact (e.g., +3V might be an ambiguous level). High-frequency signals may cause the circuit to behave unpredictably if it can't switch fast enough. Power consumption is another critical factor, especially in battery-powered devices.

TTL/CMOS NOT Gate Operation

Logic gates are implemented using transistors configured as switches. Two common technologies are BJT (Bipolar Junction Transistor) and CMOS (Complementary Metal-Oxide Semiconductor).

• BJT Implementation: A NOT gate can be built with a BJT. When a voltage is applied to the base, the transistor turns on, shorting the output to ground (0V). When the base is at 0V, the transistor is off, and the output is at Vcc (e.g., 5V).
• CMOS Implementation: A NOT gate uses a P-type MOSFET and an N-type MOSFET. When the input is high (+V), the P-MOSFET is off, and the N-MOSFET is on, pulling the output to ground. When the input is low (0V), the P-MOSFET is on, and the N-MOSFET is off, pulling the output to Vdd.

Integrated Circuit Technologies

Different IC technologies are used to implement digital gates, each with trade-offs in speed, power consumption, and density.

• CMOS: Most common. Low power consumption, high input impedance, high chip density. It can be sensitive to static charge.
• TTL (Transistor-Transistor Logic): Fast switching speed, high power consumption. Offers a wide variety of functional devices.
• ECL (Emitter-Coupled Logic): Used in specialized, very high-speed applications (e.g., supercomputers, high-speed data transmission).
• PMOS & NMOS: Used in LSI (Large Scale Integration) for high density and low power, such as in early microprocessors and large memories.
• E²CMOS: A combination of CMOS and NMOS, used for programmable logic devices (PLDs).

Types of IC Logic Gates

Logic gates are available in standardized Integrated Circuit (IC) packages, often identified by a 74XX code.

• 74XX00: Quad 2-input NAND Gate
• 74XX02: Quad 2-input NOR Gate
• 74XX04: Hex Inverter (6 NOT gates)
• 74XX08: Quad 2-input AND Gate
• 74XX32: Quad 2-input OR Gate
• 74XX86: Quad 2-input XOR Gate
• 74XX266: Quad 2-input XNOR Gate A common package is a 14-pin DIP (Dual Inline Package). For example, a 7408 IC has 4 AND gates; pins 7 (GND) and 14 (Vcc) provide power.

Performance Characteristics and Parameters

Key parameters determine the suitability of an IC for a given application:

• DC Supply Voltage: The operating voltage for the gate.
• Noise Margin: The voltage range that is interpreted as a valid logic 0 or 1. A higher noise margin means the gate can tolerate more electrical interference.
• Power Dissipation: The power consumed by the gate, which varies with the switching frequency.
• Frequency Response and Propagation Delay: The time it takes for a gate to change its output after receiving a new input. This delay limits the maximum speed of the system.
• Fan-Out: The number of logic gate inputs that can be safely connected to a single output. 💡 Why this matters: These parameters are critical for a designer. Choosing a gate with the right propagation delay, fan-out, and power dissipation is essential for building a functional, reliable, and efficient digital system.

⭐ Key Takeaways

The central idea of this lecture is the universality of NAND and NOR gates, showing that any logic function can be constructed from either gate type alone. The XOR and XNOR gates are distinct components with unique functions used for comparison and parity detection, which is fundamental for error checking in digital systems. The lecture emphasizes that theoretical logic has real-world limitations, introducing critical parameters like propagation delay, fan-out, and noise margin that dictate a circuit's performance and reliability. Understanding these parameters is crucial for moving from a logic diagram to a working physical circuit. Finally, familiarity with standard IC part numbers (e.g., 7408, 7432) and their packages is essential for practical implementation of digital designs.

🧠 Quick Revision Questions

1. How can a NOR gate be configured to function as a NOT gate?
2. What is the key difference between the function of an XOR gate and an XNOR gate?
3. What is the purpose of a parity detection circuit, and which type of gate is primarily used to build an odd number of 1s detector?
4. Explain the concept of "Fan-Out" and why it is an important consideration when designing a digital circuit.
5. Which two Integrated Circuit (IC) technologies are most commonly discussed, and what are the primary trade-offs between them in terms of power consumption and speed?

📘 Lecture 7 — Digital Circuits and Operational Characteristics

📖 Overview: This lecture examines the operational characteristics that define digital logic families, specifically TTL and CMOS technologies. It covers critical parameters such as DC supply voltages, logic levels, noise margins, power dissipation, propagation delay, speed-power product, and fan-out, which are essential for selecting and designing reliable digital systems. Understanding these characteristics allows engineers to predict circuit behavior, ensure signal integrity, and optimize performance for specific applications.

🗂️ Topics Covered

The lecture covers DC supply voltage specifications for TTL (5V) and CMOS (5V and 3.3V) families, detailed logic level definitions for input and output voltages, noise margin calculations for each family, power dissipation characteristics of TTL (constant) and CMOS (frequency-dependent), propagation delay times (t_PHL and t_PLH), the speed-power product as a performance metric, and fan-out/loading considerations for both TTL and CMOS technologies, including unit loads and capacitive effects.

📝 Lecture Summary

1. DC Supply Voltage

TTL-based devices operate with a dc supply of +5 Volts. TTL offers fast switching speed and immunity from electrostatic discharge damage, but its power consumption is higher than CMOS. The TTL family has six device types characterized by different power dissipation and switching speeds: 74 Standard TTL, 74S Schottky TTL, 74AS Advanced Schottky TTL, 74LS Low-Power Schottky TTL, 74ALS Advanced Low-Power Schottky TTL, and 74F Fast TTL. The Standard TTL is the slowest and consumes more power, while the Advanced Low-Power Schottky has the fastest switching speed and low power requirements.

CMOS technology is the dominant technology today, used in large-scale ICs and microprocessors. It is characterized by low power dissipation with slow switching speeds. There are two categories based on dc supply voltage: +5 V CMOS (74HC/74HCT High-Speed, 74AC/74ACT Advanced CMOS, 74AHC/74AHCT Advanced High Speed) and 3.3 V CMOS (74LV Low voltage, 74LVC Low-voltage, 74ALVC Advanced Low voltage). The 3.3 V CMOS series has faster switching speeds and very low power dissipation compared to the 5 V CMOS series.

2. Logic Levels and Noise Margin

TTL and CMOS circuits are designed to accept voltages within specific ranges for logic 1 and 0. The V_IH and V_IL indicate acceptable input voltage ranges for logic high and low, while V_OH and V_OL indicate acceptable output voltage ranges.

a) TTL Logic Levels

For TTL input levels: V_IH (input voltage range for logic high) is 2 to 5 volts, with V_IH(min) = 2 volts. V_IL (input voltage range for logic low) is 0 to 0.8 volts, with V_IL(max) = 0.8 volts. For TTL output levels: V_OH (output voltage range for logic high) is 2.4 to 5 volts, with V_OH(min) = 2.4 volts. V_OL (output voltage range for logic low) is 0 to 0.4 volts, with V_OL(max) = 0.4 volts.

b) CMOS 5 Volt Series Logic Levels

For CMOS 5V input levels: V_IH is 3.5 to 5 volts, with V_IH(min) = 3.5 volts. V_IL is 0 to 1.5 volts, with V_IL(max) = 1.5 volts. For CMOS 5V output levels: V_OH is 4.4 to 5 volts, with V_OH(min) = 4.4 volts. V_OL is 0 to 0.33 volts, with V_OL(max) = 0.33 volts.

c) CMOS 3.3 Volt Series Logic Levels

For CMOS 3.3V input levels: V_IH is 2 to 3.3 volts, with V_IH(min) = 2 volts. V_IL is 0 to 0.8 volts, with V_IL(max) = 0.8 volts. For CMOS 3.3V output levels: V_OH is 2.4 to 3.3 volts, with V_OH(min) = 2.4 volts. V_OL is 0 to 0.4 volts, with V_OL(max) = 0.4 volts.

Valid output voltages for logic high and low are confined to certain ranges. Output voltages outside specified ranges can cause logic circuits to malfunction. For example, a low-power 3.3V CMOS AND gate accepts 2.1 volts as a valid logic high input, but 1.9 volts is unacceptable as input voltages between 0.8-2.0 volts give unpredictable results.

Noise is unwanted voltage induced in circuits due to high-frequency electromagnetic radiation from adjacent conductors. The effect of noise on a CMOS AND gate is demonstrated: with input B at logic high (V_IH = 4.2V), a noise dip to 3 volts (below V_IH(min) of 3.5V) causes an output logic low for a short interval. In a circuit with two AND gates, noise bringing V_OH from 4.6V down to 3.4V (below the second gate's V_IH(min) of 3.5V) causes malfunction.

Noise Margin is a measure of the circuit’s immunity to noise. The high-level and low-level noise margins are represented by V_NH and V_NL.

🔑 Definition — Noise Margin: The amount of noise voltage that a logic circuit can tolerate without malfunctioning. It is the voltage margin between the output level of a driving gate and the input level requirement of a driven gate.

📐 Formulas:

• V_NH = V_OH(min) – V_IH(min) (High-level noise margin)
• V_NL = V_IL(max) – V_OL(max) (Low-level noise margin)

📌 Example — Noise Margin Calculations:

• CMOS 5V: V_NH = 4.4 – 3.5 = 0.9 V; V_NL = 1.5 – 0.33 = 1.17 V
• CMOS 3.3V: V_NH = 2.4 – 2.0 = 0.4 V; V_NL = 0.8 – 0.4 = 0.4 V
• TTL 5V: V_NH = 2.4 – 2.0 = 0.4 V; V_NL = 0.8 – 0.4 = 0.4 V

💡 Why this matters: Higher noise margins mean circuits are more immune to noise. CMOS 5V has a high-level noise margin of 0.9V compared to 0.4V for TTL and CMOS 3.3V, making CMOS 5V series perform better in noisy environments. CMOS 5V and 3.3V series cannot be mixed.

3. Power Dissipation

Logic gates consume varying amounts of power during operation. Ideally, they should consume minimal power. Advantages of low power consumption include battery operation for portable devices and less heat dissipation, allowing circuits to be packed tightly. TTL and CMOS have fundamentally different power dissipation characteristics.

a) Power Dissipation of TTL Devices

When a TTL logic gate output is logic high, it sources current (I_CCH, typically 1.5 mA at V_CC=5V). When the output is logic low, it sinks current (I_CCL, typically 3.0 mA at V_CC=5V). The power dissipated differs for high and low outputs. The average power dissipation is determined based on a 50% duty cycle.

📐 Formula — Average Power Dissipation for TTL: P_D = V_CC (I_CCH + I_CCL) / 2

Power dissipation in TTL circuits is constant over its range of operating frequencies. For example, an LS TTL gate has a constant power dissipation of 2.2 mW.

b) Power Dissipation of CMOS Devices

CMOS logic uses transistors that present a capacitive load instead of the resistive load in TTL. Each time a CMOS gate switches, current is supplied to the capacitive load. As frequency increases, more current spikes occur per second, increasing the average current drawn. Power dissipation in CMOS circuits is frequency dependent.

📐 Formula — Total Dynamic Power Dissipation for CMOS: P_D = P_T + P_L, where P_T is internal power dissipation and P_L is external power dissipation due to the external capacitive load.

The detailed formula is: P_D = (C_PD + C_L) × V_DD² × f, where C_PD is internal power dissipation capacitance, C_L is external load capacitance, V_DD is supply voltage, and f is the transition frequency.

📌 Example: The power dissipation of an HCMOS gate is 2.75 μW under static conditions and 170 μW at 100 KHz, illustrating frequency-dependence.

4. Propagation Delay

When a signal passes through a gate, it experiences a delay. The output is delayed with respect to the input, known as Propagation Delay. This delay limits the frequencies at which the gate can work. Higher propagation delay means lower operating frequency, and smaller delay means higher operating frequency. A gate with a 3 nsec delay is faster than one with a 10 nsec delay.

There are two specified propagation delay times:

• t_PHL: The time between a reference point on the input pulse and the corresponding point on the output pulse when the output changes from high to low.
• t_PLH: The time between a reference point on the input pulse and the corresponding point on the output pulse when the output changes from low to high.

The delay time is measured at the 50% transition mark. Generally, t_PLH and t_PHL are the same.

💡 Why this matters: The effect can be compared to spectators entering a stadium through gates with different clearance times. If guards at Gates A, B, and C take 1, 1.5, and 2 minutes respectively, Gate C forms the longest queue after 30 minutes because it has the longest "Propagation Delay."

5. Speed-Power Product (SPP)

Speed-Power Product (SPP) is an important parameter used as a measure of performance of a logic circuit, taking into account both propagation delay and power dissipation.

📐 Formula — Speed-Power Product: SPP = t_P × P_D, expressed in Joules (J), the unit of energy. Lower the SP product, better the performance.

6. Fan-Out and Loading

Fan-out is the maximum number of inputs of the same series in an IC family that can be connected to a gate’s output while maintaining output voltage levels within specified limits. Fan-out is primarily associated with TTL technology. CMOS circuits have very high impedance, so fan-out is very high but depends on frequency due to capacitance effects.

Fan-out is specified in terms of unit loads. A unit load for a logic gate equals one input to a like circuit.

🔑 Definition — Unit Load: The current required by one standard input of a given logic family.

📌 Example — Unit Load Calculation for 7400 NAND Gate:

• At logic high: I_OH = 400 μA (output source), I_IH = 40 μA (input current)
• At logic low: I_OL = 16 mA (output sink), I_IL = 1.6 mA (input current)
• Unit Loads = I_OH / I_IH = I_OL / I_IL = 400 μA / 40 μA = 16 mA / 1.6 mA = 10 unit loads

As more loads are connected, total current increases, causing V_OH to decrease (due to internal voltage drop). If V_OH drops below V_OH(min), the high-level noise margin is reduced. Similarly, increased sink current causes V_OL to increase, reducing the low-level noise margin.

CMOS loading is different because the transistors present a capacitive load. When the output is high, the input capacitance of the load gate is charging; when low, it is discharging. Adding more loads increases input capacitance (capacitances in parallel), increasing charging/discharging time and reducing the maximum operating frequency. The fan-out of a CMOS gate depends upon the maximum frequency of operation.

📌 Example — Performance Ratings from Table 7.1:

• TTL 74ALS has propagation delay of 4 ns, power dissipation of 1.2 mW, SPP of 4.8 pJ, max clock rate of 70 MHz, and fan-out of 20.
• CMOS 74AHC has propagation delay of 3.7 ns, static power dissipation of 0.00275 mW, dynamic power dissipation at 100 kHz of 0.0625 mW, SPP at 100 kHz of 0.23 pJ, and max clock rate of 170 MHz.
• CMOS 74ALVC (3.3 V) has propagation delay of 3 ns, static power dissipation of 0.0008 mW, and max clock rate of 150 MHz.

⭐ Key Takeaways

Students must understand the fundamental differences between TTL and CMOS logic families, including their DC supply voltages (TTL: 5V; CMOS: 5V or 3.3V), and be able to interpret and apply logic level specifications (V_IH, V_IL, V_OH, V_OL) for each family. The concept of noise margin is critical: students must calculate V_NH and V_NL using the formulas V_NH = V_OH(min) – V_IH(min) and V_NL = V_IL(max) – V_OL(max), and understand that higher noise margins (e.g., CMOS 5V at 0.9V) provide better noise immunity. Power dissipation must be understood as constant for TTL (calculated using P_D = V_CC (I_CCH + I_CCL)/2) and frequency-dependent for CMOS (calculated using P_D = (C_PD + C_L) × V_DD² × f). Finally, students must grasp propagation delay, the speed-power product (lower is better), and how fan-out and loading affect circuit operation differently in TTL (current-based limits) and CMOS (capacitive load limits).

🧠 Quick Revision Questions

1. What are the six types of TTL chips, and which one has the fastest switching speed and lowest power consumption?
2. Calculate the high-level and low-level noise margins for the CMOS 5V series. Why does this family perform better in noisy environments compared to TTL?
3. Compare the power dissipation characteristics of a TTL gate and a CMOS gate operating at a high frequency. Which dissipates more power and why?
4. Define propagation delay and explain the difference between t_PHL and t_PLH. A gate has a propagation delay of 10 ns; is it faster or slower than a gate with a 3 ns delay?
5. How does loading affect a TTL gate's output voltage V_OH when sourcing current? How does loading a CMOS gate affect its maximum operating frequency and why?

📘 Lecture 08 — BOOLEAN ALGEBRA AND LOGIC SIMPLIFICATION

📖 Overview: This lecture introduces Boolean algebra as the mathematical foundation of digital systems. It covers essential definitions, laws, rules, and theorems used to represent and simplify logic circuits. Understanding these concepts is crucial for analyzing and minimizing complex digital circuits to reduce gate count and cost.

🗂️ Topics Covered

The lecture begins with fundamental Boolean algebra definitions (variable, complement, literal) and operations (Boolean addition and multiplication). It then explains the three basic laws (commutative, associative, distributive) followed by twelve rules of Boolean algebra. DeMorgan’s theorems are introduced along with their application. The lecture concludes with Boolean analysis of logic circuits, simplification using Boolean algebra, and the standard forms of Boolean expressions (SOP and POS) with their implementations.

📝 Lecture Summary

Boolean Algebra Definitions

A variable is a symbol (usually an uppercase letter) used to represent a logical quantity and can have a value of 0 or 1. A complement is the inverse of a variable, indicated by a bar over the variable (e.g., complement of X is X̅); if X=0 then X̅=1, and if X=1 then X̅=0. A literal is a variable or the complement of a variable.

Boolean Addition is performed by an OR gate and results in a sum term. A sum term is 1 when any one literal is 1, and 0 when all literals are 0. Examples of sum terms: A+B, A̅+B, A+B+C̅.

Boolean Multiplication is performed by an AND gate and results in a product term. A product term is 1 when all literal terms are 1, and 0 when any one literal is 0. Examples of product terms: A·B, A̅·B, A·B·C.

Laws of Boolean Algebra

1. Commutative Law for Addition and Multiplication

• Commutative Law for Addition: A + B = B + A
• Commutative Law for Multiplication: A·B = B·A

The ordering of literals at the input of OR and AND gates does not affect the result. This law holds true for any number of literals.

2. Associative Law for Addition and Multiplication

• Associative Law for Addition: A + (B + C) = (A + B) + C
• Associative Law for Multiplication: A·(B·C) = (A·B)·C

The grouping of literals for Boolean Addition and Multiplication does not change the result. Adding B and C first, then adding A to the result, is the same as adding A and B first, then adding C. Similarly for multiplication.

3. Distributive Law

• A·(B + C) = A·B + A·C

Adding literals B and C and then multiplying the result with A is the same as multiplying A with B and adding that to the product of A and C. This law holds true for any number of literals.

Rules of Boolean Algebra

These rules can be proved by substituting literals with Boolean values 0 and 1.

1. A + 0 = A
2. A + 1 = 1
3. A·0 = 0
4. A·1 = A
5. A + A = A
6. A + A̅ = 1
7. A·A = A
8. A·A̅ = 0
9. A̿ = A (Double complement)
10. A + A·B = A — (Proof: A·(1+B) = A·1 = A)
11. A + A̅·B = A + B — (Proof: A(B+1) + A̅·B = AB + A + A̅·B = B(A+A̅) + A = B + A)
12. (A+B)·(A+C) = A + B·C — (Proof: AA+AC+AB+BC = A(1+C+B) + BC = A + BC)

💡 Why this matters: These rules are the essential tools for simplifying Boolean expressions, leading to simpler and more cost-effective digital circuits.

DeMorgan’s Theorems

DeMorgan’s First Theorem states: The complement of a product of variables is equal to the sum of the complements of the variables. 🔑 Definition — DeMorgan’s First Theorem: A̅·B̅ = A̅ + B̅ 📐 Formula: A·B = A̅ + B̅ → The complement of the AND of two variables equals the OR of their complements.

DeMorgan’s Second Theorem states: The complement of a sum of variables is equal to the product of the complements of the variables. 🔑 Definition — DeMorgan’s Second Theorem: A̅+B̅ = A̅·B̅ 📐 Formula: A + B = A̅·B̅ → The complement of the OR of two variables equals the AND of their complements.

DeMorgan’s theorems prove the equivalency of NAND and negative-OR gates, and NOR and negative-AND gates respectively. These theorems can be applied to expressions with any number of variables:

• X·Y·Z = X̅ + Y̅ + Z̅
• X + Y + Z = X̅·Y̅·Z̅

Example: Applying DeMorgan’s Theorem to (A + B·C)·(A·C + B): = (A + B·C)̅ + (A·C + B)̅ = A̅·(B·C)̅ + (A·C)̅·B̅ = A̅·(B̅ + C̅) + (A̅ + C̅)·B̅ = A̅·B̅ + A̅·C̅ + A̅·B̅ + B̅·C̅ = A̅·B̅ + A̅·C̅ + B̅·C̅

Boolean Analysis of Logic Circuits

Boolean algebra provides a concise way to represent the operation of a logic circuit. The function of a logic circuit can be determined by evaluating the Boolean expression using different input combinations.

For the circuit represented by the expression (AB + C̅)D:

• Starting from the left input side, the AND gate provides AB.
• The OR gate adds AB and complement C to get (AB + C̅).
• The AND gate on the right multiplies (AB + C̅) with D.

The expression output is 1 if both D = 1 and (AB + C̅) = 1. The term (AB + C̅) = 1 only if AB = 1 or C = 0. Therefore, the expression equals 1 when: D=1 AND (C=0 OR AB=1).

Analysis of the function table (16 possible input combinations) shows output F=1 for input combinations: 0001, 0101, 1001, 1101, and 1111.

Simplification using Boolean Algebra

Boolean expressions can be simplified using laws, rules, and theorems to result in fewer variables and a simpler circuit.

Example: Simplify AB + A(B+C) + B(B+C) = AB + AB + AC + BB + BC (Distributive Law) = AB + AC + B + BC (BB = B using rule 7) = AB + AC + B (B+BC = B using rule 10) = B + AC (B+AB = B using rule 10)

The simplified expression B+AC results in a simpler circuit with fewer gates compared to the original.

Standard Form of Boolean Expressions

All Boolean expressions can be converted into one of two standard forms: Sum-of-Products (SOP) or Product-of-Sums (POS).

1. Sum-of-Products (SOP) Form When two or more product terms are summed by Boolean addition, the result is a SOP expression. The domain of an SOP expression is the set of all variables (complemented and un-complemented) contained in the expression. Examples: AB + ABC, ABC + CDE + BCD, AB̅ + ABC̅ + AC̅

• A SOP expression cannot have a term with an overbar extending over the entire term.

2. Product-of-Sums (POS) Form When two or more sum terms are multiplied by Boolean multiplication, the result is a POS expression. Examples: (A+B)(A+B+C), (A+B+C)(C+D+E)(B+C+D), (A+B̅)(A+B+C̅)(A̅+C)

Implementation of SOP and POS Expressions

An SOP expression can be implemented by an AND-OR combination of gates. Product terms are implemented by AND gates, and the OR gate combines the outputs of the AND gates.

A POS expression can be implemented by an OR-AND combination of gates. Sum terms are implemented by OR gates, and the AND gate combines the outputs of the OR gates.

Conversion of a General Expression to SOP Form

Any logical expression can be converted into SOP form by applying Boolean algebra techniques:

• AB + B(CD + EF) = AB + BCD + BEF
• (A+B)(B+C+D) = AB + AC + AD + B + BC + BD = AC + AD + B
• (A+B)̅ + C = (A̅·B̅) + C = (A̅·B̅) + C (using DeMorgan's Theorem, this is already in SOP form)

⭐ Key Takeaways

Boolean algebra is the essential mathematical foundation for analyzing and simplifying digital logic circuits. The student must master the three basic laws (commutative, associative, distributive) and the twelve rules of Boolean algebra, as these are the primary tools for simplification. DeMorgan’s theorems are critical for understanding the equivalency between NAND/NOR gates and their negative-gate counterparts, and for manipulating complemented expressions. All Boolean expressions can be expressed in either Sum-of-Products (SOP) or Product-of-Sums (POS) standard forms, with SOP implemented using AND-OR gate networks and POS using OR-AND networks. The ultimate goal is to use Boolean algebra to minimize expressions, thereby reducing the number of gates required to implement a logic circuit, saving cost and complexity.

🧠 Quick Revision Questions

1. State DeMorgan’s First Theorem and apply it to simplify the expression (X·Y·Z)̅.
2. Using Boolean algebra rules, simplify the expression A + A̅·B and show the steps.
3. Convert the expression (A+B)·(B+C) into its Sum-of-Products (SOP) form.
4. For the Boolean expression (AB + C̅)D, determine all input combinations (A, B, C, D) that produce an output of 1.
5. Explain the difference between Sum-of-Products (SOP) and Product-of-Sums (POS) forms, and describe how each is implemented with logic gates.

📘 Lecture 9 — Boolean Algebra and Logic Simplification

📖 Overview: This lecture focuses on the practical application of Boolean algebra to analyze, simplify, and represent logic circuits. It demonstrates how a complex logic circuit's Boolean expression is evaluated, simplified using Boolean theorems, and verified through truth tables. The lecture also introduces standard Sum-of-Products (SOP) and Product-of-Sums (POS) forms, their conversion, and the concepts of Minterms and Maxterms for canonical representation.

🗂️ Topics Covered

This lecture covers Boolean analysis of logic circuits through two detailed examples, including finding the Boolean expression, evaluating it, creating truth tables, and simplifying the expression using DeMorgan's theorems and Boolean rules. It further explains the conversion of non-standard SOP and POS expressions into their standard forms, defines Minterms and Maxterms, and demonstrates how to convert between standard SOP and POS forms, as well as how to map SOP and POS expressions to truth tables.

📝 Lecture Summary

Boolean Analysis of Logic Circuits, evaluating of Boolean expressions, representing the operation of Logic circuits and Boolean expressions in terms of Function tables and representing Boolean expressions in SOP and POS forms

The lecture begins by establishing the interrelationship between Boolean Analysis of Logic Circuits, evaluating Boolean expressions, representing them in function tables (truth tables), and representing them in SOP (Sum-of-Products) and POS (Product-of-Sums) forms. Boolean laws, rules, and theorems are the tools used to change between these forms.

Example 1

1. Finding the Boolean Expression The first example analyzes a logic circuit (Figure 9.1) composed of NOT, AND, NAND, and NOR gates. The Boolean expression is derived by working from the left side of the circuit. The output of the first NOT gate is B, and the second NOT gate is A. The output of a two-input AND gate for A and B is A.B. Another AND gate for C and D gives C.D. A three-input NAND gate combines the outputs of the first AND gate and the C.D product, resulting in A.B.C.D. Finally, a two-input NOR gate produces the final expression: A.B + A.B.C.D. 🔑 Definition — Logic Circuit Analysis: The process of deriving a Boolean expression from a logic circuit diagram.

2. Evaluating the Expression The expression is evaluated by letting X = A.B and Y = A.B.C.D, so the output is X + Y (X NOR Y). The output of a NOR gate is 1 only when both inputs are 0 (X=0 and Y=0). X=0 when either A=0 or B=1. Y=0 when A.B.C.D = 1, which requires A=0, B=0, C=1, D=1. Therefore, the overall expression is 1 only when A=0, B=0, C=1, and D=1.

3. Putting the Results in Truth Table Format A truth table (Table 9.1) with 16 input combinations for variables A, B, C, and D is created. The output F is 1 for only the input combination (A=0, B=0, C=1, D=1) and 0 for all other 15 combinations.

4. Simplification of Boolean Expression The expression is simplified using DeMorgan's theorem. Applying DeMorgan's second theorem (A + B = A.B) to the NOR expression gives (A.B).(A.B.C.D). Then, applying DeMorgan's first theorem to (A.B) and Rule 9 (A = A) to the second term yields (A + B).(A.B.C.D). Using the distributive law and Rule 8 (A.A = 0), the expression simplifies to A.B.C.D. The simplified expression is 1 when A=0, B=0, C=1, and D=1. 📐 Formula: A + B = A.B (DeMorgan's Second Theorem) 📌 Example: Given AB + ABCD, applying DeMorgan's theorem yields (A+B).(ABCD).

5. Putting the result in Truth Table format The truth table (Table 9.2) for the simplified expression A.B.C.D is identical to the truth table for the original expression (Table 9.1), verifying that the simplification is correct.

6. Implementing Logic Circuit from Simplified Boolean expression The simplified expression F = A.B.C.D is a product term with four literals. It is implemented using NOT gates for A and B and a single 4-input AND gate (Figure 9.2). This is a much simpler circuit than the original.

Example 2

1. Finding the Boolean Expression The second example circuit (Figure 9.3) has three NOT gates, a three-input AND gate, a two-input OR gate, and a NAND gate. The outputs are A, C, A.B.C, and C + D. The NAND gate output is the final expression: (A.B.C).(C + D).

2. Evaluating the Expression Let X = A.B.C and Y = C + D, so the output is X.Y (X NAND Y). The output of a NAND gate is 1 when either input is 0 (X=0 or Y=0). X=0 when A=1, B=0, or C=1. Y=0 when C=1 and D=0. The expression output is 1 when (A=1 OR B=0 OR C=1) OR (C=1 AND D=0).

3. Putting the Results in Truth Table Format The truth table (Table 9.2) shows that variable D has no effect on the output. The table can be reduced to a three-variable truth table (Table 9.3) for A, B, and C.

4. Simplification of Boolean Expression Applying DeMorgan's first theorem (A.B = A + B) to the expression gives (A.B.C) + (C + D). Applying DeMorgan's theorems again yields (A + B + C) + (C.D). Applying Rule 9 results in (A + B + C) + (C.D). Finally, factoring C gives A + B + C(1 + D), which simplifies to A + B + C. The simplified expression is 1 when A=1, B=1, or C=1. 📐 Formula: A.B = A + B (DeMorgan's First Theorem) 📌 Example: Given (ABC)(C+D), applying DeMorgan's theorem yields (A+B+C)(CD).

5. Putting the result in Truth Table format The truth table for the simplified expression A + B + C (Table 9.4) is identical to the reduced truth table (Table 9.3), verifying the simplification. 💡 Why this matters: When D has no effect on the output, it is a "don't care" condition, and the circuit can be simplified by removing the logic associated with D.

6. Implementing Logic Circuit from Simplified Boolean expression The simplified expression F = A + B + C is a sum term with three literals. It is implemented using a single NOT gate for B and a 3-input OR gate (Figure 9.4).

Standard SOP form

A standard SOP form contains product terms that include all the variables in the domain of the expression. For example, the SOP expression AC + BC is not standard for a domain of A, B, C. A non-standard SOP is converted into standard SOP by using the rule A + A = 1 to multiply each term by the missing variable(s). 📐 Formula: A + A = 1 📌 Example: AC + BC becomes ABC + ABC + ABC + ABC, which simplifies to ABC + ABC + ABC.

Standard POS form

A standard POS form contains sum terms that include all the variables in the domain of the expression. A non-standard POS is converted into a standard POS by using the rule AA = 0 to add the missing variable(s) to each sum term. 📐 Formula: AA = 0 📌 Example: (A+B+C)(A+B+D) becomes (A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D).

Converting to Standard SOP and POS forms

Converting to standard forms is crucial because any logic circuit can be implemented using either SOP (AND-OR) or POS (OR-AND) gate combinations. Converting between standard SOP and standard POS is straightforward and helps in choosing the implementation with the minimum number of gates. Furthermore, standard forms are essential for simplifying expressions using Karnaugh maps and for programming PLDs (Programmable Logic Devices).

Minterms and Maxterms

In standard SOP, the product terms are called Minterms. In standard POS, the sum terms are called Maxterms. A Minterm is equal to 1 for only one specific combination of input variables, and a Maxterm is equal to 0 for only one specific combination. Table 9.5 shows the relationship between variable values, Minterms, and Maxterms.

Binary representation of a standard Product term or Minterm

A standard product term (Minterm) is equal to 1 for only one combination. For instance, ABC = 1 only when A=1, B=1, C=0. An SOP expression is 1 when one or more of its product terms are 1.

Binary representation of a standard Sum term or Maxterm

A standard sum term (Maxterm) is equal to 0 for only one combination. For instance, (A+B+C+D) = 0 only when A=0, B=1, C=0, D=1. A POS expression is 0 when one or more of its sum terms are 0.

Converting Standard SOP into Standard POS

To convert from standard SOP to standard POS, list all the binary values of the product terms in the SOP (these are the "1" outputs). The missing binary values are the "0" outputs, which correspond to the sum terms in the standard POS. The expression is often written using Canonical Sum (Σ) and Canonical Product (Π) notation. 📐 Formula: Canonical Sum = Σ(minterm numbers); Canonical Product = Π(maxterm numbers) 📌 Example: Σ(0,2,3,5,7) = ABC + ABC + ABC + ABC + ABC. The missing values are 1, 4, and 6, so the equivalent POS is Π(1,4,6) = (A+B+C)(A+B+C)(A+B+C).

Verifying POS expression is equivalent to SOP expression

The equivalence of the SOP and POS expressions is verified by algebraically expanding the POS expression and simplifying it back into the original SOP form.

Boolean Expressions and Truth Tables

All standard Boolean expressions can be easily converted into truth table format, and standard SOP or POS expressions can be determined from a truth table.

Converting SOP expression to Truth Table format

To map an SOP expression to a truth table, first write the expression in standard SOP form. Then, for each Minterm present in the standard SOP, set the output to 1. 📌 Example: For domain A, B, C, the SOP expression AB + BC is converted to standard SOP: ABC + ABC + ABC + ABC. This corresponds to Minterms 3, 4, 5, and 7 (binary 011, 100, 101, 111). In the truth table, F=1 for these combinations.

Converting POS expression to Truth Table format

To map a POS expression to a truth table, first write the expression in standard POS form. Then, for each Maxterm present in the standard POS, set the output to 0. 📌 Example: For domain A, B, C, the POS expression (A+B)(B+C) is converted to standard POS: (A+B+C)(A+B+C)(A+B+C)(A+B+C). This corresponds to Maxterms 1, 2, 3, and 5 (binary 001, 010, 011, 101). In the truth table, F=0 for these combinations.

⭐ Key Takeaways

For the exam, you must be able to systematically analyze a logic circuit to derive its Boolean expression, then evaluate it by understanding the behavior of basic gates (AND, OR, NAND, NOR, NOT). You must be skilled at applying DeMorgan's theorems and Boolean rules (like Rule 8 A·A=0, Rule 9 A=A, and the OR form of Rule 9 A+A=1) to simplify complex expressions. The most critical skill is verifying simplification by showing that the original and simplified expressions have identical truth tables. You must also be comfortable converting between non-standard and standard SOP/POS forms, using the A+A=1 and AA=0 rules, and understanding how to convert a standard SOP into a standard POS (and vice-versa) using Minterm and Maxterm numbers with Σ and Π notation.

🧠 Quick Revision Questions

1. For the logic circuit expression F = (A.B) + (C.D), what is the equivalent simplified form after applying Boolean theorems if it were derived from a NAND-NOR combination?
2. Convert the non-standard POS expression (A+B)(B+C) into its standard POS form for a domain of three variables.
3. If a standard SOP expression has the Canonical Sum Σ(0, 2, 4, 6), what is the equivalent Canonical Product (Π) for the same function?
4. Explain the key difference in how Minterms and Maxterms are used when mapping an SOP expression versus a POS expression to a truth table.
5. Simplify the Boolean expression (X+Y) · (X+Z) and explain which Boolean rule or theorem you used.

📘 Lecture 10 — Karnaugh Map & Boolean Expression Simplification

📖 Overview: This lecture introduces the Karnaugh Map (K-Map) as a systematic graphical method for simplifying Boolean expressions, overcoming the limitations of algebraic simplification using laws and theorems. It covers the structure and organization of 2, 3, and 4-variable K-Maps, the process of mapping Standard and non-Standard SOP expressions, grouping adjacent cells, and simplification techniques. The lecture also explains how to handle "Don't Care" conditions and map directly from function tables for practical digital circuit design.

🗂️ Topics Covered

The lecture covers the organization of the 3-variable Karnaugh Map in column and row forms, and the 4-variable Karnaugh Map. It explains the concept of grouping adjacent cells for simplification, including corner cells and powers-of-two groups. The process of mapping Standard and non-Standard SOP expressions to K-Maps is detailed through multiple examples. Simplification of SOP expressions using the K-Map is demonstrated with several 3 and 4-variable examples. Finally, the lecture covers mapping directly from a function table and the use of "Don’t Care" conditions to achieve further simplification.

📝 Lecture Summary

Karnaugh Map & Boolean Expression Simplification

Simplifying Boolean expressions using laws, rules and theorems does not guarantee the simplest form because some simplifications are not obvious. The Karnaugh Map (K-Map) provides a systematic array-based method for simplification. Adjacent cells in the array can be grouped to simplify expressions for 2, 3, 4, and 5 variables.

The 3-variable Karnaugh Map

A 3-variable K-Map contains 8 cells. These can be arranged in two forms: a column form (2 columns, 4 rows) where the left column represents AB values (00, 01, 11, 10) and the top row represents C values (0, 1); and a row form (2 rows, 4 columns) where the left column represents A (0, 1) and the top row represents BC values (00, 01, 11, 10). The numbers in the cells represent the Minterms or Maxterms. For example, cell 0 represents minterm 0 with binary value 000 for variables A, B, and C.

🔑 Definition — Minterm: A product term that includes all variables in the domain of the expression, either in complemented or un-complemented form, representing a single '1' output condition.

The 4-variable Karnaugh Map

A 4-variable K-Map has an array of 16 cells in a square format with 4 rows and 4 columns. The left column represents the binary values of variables A and B, while the top row represents the binary values of variables C and D. Cell 6 represents minterm 6 with binary value 0110 for A, B, C, and D. 💡 Why this matters: The K-Map's structure allows visual identification of adjacent terms that can be combined to eliminate variables.

Grouping and Adjacent Cells

The K-Map array is considered to be wrapped around, so all sides are adjacent. Groups of 2, 4, 8, 16, 32 etc. adjacent cells are formed. Adjacent cells can be row-wise, column-wise, the four corner cells, or row-column groups. Groups are formed based on 1s (Minterms) or 0s (Maxterms). A group should have the maximum number of cells possible, with the size being a power of 2. The goal is to form the minimal number of largest groups that uniquely cover all cells.

Mapping a standard SOP Expression

For a Standard SOP expression, a 1 is placed in the cell corresponding to each product term (Minterm) present. Cells without 1s contain 0s. For example, the expression ( \overline{A}BC + A\overline{B}C + AB\overline{C} ) (minterms 2, 4, 6) is mapped by placing a 1 in cells 2, 4, and 6 of a 3-variable K-Map. Similarly, a 4-variable expression with 7 minterms (1, 4, 5, 6, 8, 13, 14) is mapped by placing 1s in those corresponding cells.

Mapping a non-standard SOP Expression

Non-standard SOP expressions can be mapped directly without first converting to standard form. For example, the expression ( A + \overline{B}C ) is mapped by first marking all cells where A is present (minterms 4, 5, 6, 7), then marking cells where ( \overline{B}C ) is present (minterms 1, 5). The resulting K-Map shows the expression has five product terms. Similarly, expression ( \overline{A} + \overline{C} ) is mapped by marking cells for ( \overline{A} ) (minterms 0, 1, 2, 3) and then ( \overline{C} ) (minterms 0, 1, 4, 5). For 4 variables, expression ( \overline{D} + A\overline{C} + \overline{B}C ) is mapped term by term by marking cells where each term is present.

Simplification of SOP expressions using the Karnaugh Map

The first step is mapping the SOP expression on the K-Map. Next, groups of 1s are formed, starting with the largest group of size 2, 4, 8, 16, etc. Multiple unique groups are formed, each having at least one 1 not common to any other group. A single isolated 1 forms a group of one cell. Each group represents a product term with variables that occur in only one form.

For a 3-variable K-Map: a group of 1 cell yields a 3-variable term, 2 cells yields a 2-variable term, 4 cells yields a 1-variable term, and 8 cells yields a value of 1. For a 4-variable K-Map: 1 cell yields a 4-variable term, 2 cells yields a 3-variable term, 4 cells yields a 2-variable term, 8 cells yields a 1-variable term, and 16 cells yields a value of 1.

Example 1 & 2: A 3-variable expression with 5 minterms groups into three groups of 2: cells 2,6 → ( \overline{B}C ); cells 5,7 → ( AC ); cells 1,5 → ( B\overline{C} ). The simplified expression is ( \overline{B}C + AC + B\overline{C} ). Another expression with 4 minterms groups into one single cell (4 → ( A\overline{B}\overline{C} )) and two groups of 2 (cells 1,3 → ( \overline{A}C ); cells 2,3 → ( \overline{A}B )), simplifying to ( A\overline{B}\overline{C} + \overline{A}C + \overline{A}B ).

Example 3 & 4: A 3-variable expression with 5 minterms forms one group of 4 (cells 2,3,6,7 → ( B )) and one group of 2 (cells 5,7 → ( AC )), simplifying to ( B + AC ). Another expression with 5 minterms forms three groups of 2: cells 4,5 → ( A\overline{B} ); cells 3,7 → ( BC ); cells 2,3 → ( \overline{A}B ), simplifying to ( A\overline{B} + BC + \overline{A}B ).

Example 5: A 4-variable expression with 11 minterms forms three groups of 4: cells 8,9,12,13 → ( A\overline{C} ); cells 1,3,9,11 → ( \overline{B}D ); cells 6,7,14,15 → ( BC ). Simplified expression: ( A\overline{C} + \overline{B}D + BC ).

Example 6: An 8-minterm 4-variable expression forms one group of 2 (cells 8,12 → ( A\overline{C}\overline{D} )) and two groups of 4 (cells 3,7,11,15 → ( CD ); cells 6,7,14,15 → ( BC )), simplifying to ( A\overline{C}\overline{D} + CD + BC ).

Example 7: A 9-minterm 4-variable expression forms two groups of 4 (corner cells 0,2,8,10 → ( \overline{B}D ); cells 2,3,10,11 → ( \overline{B}C )) and two groups of 2 (cells 13,15 → ( ABD ); cells 2,6 → ( \overline{A}C\overline{D} )), simplifying to ( \overline{B}D + \overline{B}C + ABD + \overline{A}C\overline{D} ).

📐 Formula: Grouping Rule: Group adjacent 1s in powers of 2 (1, 2, 4, 8, 16...) to form circles, ensuring each cell is covered and at least one cell per group is unique.

📌 Example: For the 4-variable K-Map in Figure 10.12, cells 8,9,12,13 form a group of 4. A and B vary (0,1) and (0,1) while C is 0 and D varies. The variable that changes (D) is eliminated, leaving ( A\overline{C} ).

Mapping Directly from Function Table

In practice, a digital circuit's function is defined using a Function Table. The information is directly mapped to a K-Map, simplified, and the resulting expression is implemented with logic gates. For example, an Odd-Prime Number Checker circuit accepts 4-bit numbers (0-15). The function table shows output 1 for odd prime numbers (1, 3, 5, 7, 11, 13). Mapping this to a 4-variable K-Map and simplifying yields the expression ( AD + \overline{B}C\overline{D} + BC\overline{D} ).

Don’t Care Conditions

Don't Care conditions occur when certain input combinations never happen. Their corresponding outputs are marked as x (don't care) in the function table and K-Map. During grouping, x outputs can be considered as 0 or 1 to achieve maximal simplification. For the Odd-Prime Checker, if only inputs 0-9 occur (states 10-15 never occur), all don't care states can be considered 0s, simplifying the expression to ( AD ). If only inputs 0-8 occur, states 9-15 can be considered 1s to form a group of 8 cells, simplifying the expression to the single literal ( D ).

🔑 Definition — Don't Care Condition: An input combination that never occurs in a circuit, allowing its output to be assigned arbitrarily (0 or 1) during K-Map simplification to achieve a simpler expression.

📌 Example: In a 4-variable K-Map where cells 3, 10, and 15 are don't cares (assuming they never occur), they can be treated as 1s to form a larger group. As in Figure 10.17, the simplified expression becomes ( C + \overline{A}D ) instead of the original ( A\overline{B}C + CD + BC ).

⭐ Key Takeaways

The Karnaugh Map is a systematic graphical tool for simplifying Boolean expressions that overcomes the limitations of algebraic methods. You must be able to construct and interpret 3-variable (8 cells) and 4-variable (16 cells) K-Maps in both column and row forms. The core simplification process involves mapping SOP expressions, forming the largest possible groups of adjacent 1s (in powers of 2), and deriving the minimal product term for each group by eliminating variables that change within the group. The ability to directly map from a function table and strategically use Don't Care conditions (marked as 'x') by treating them as either 0 or 1 is critical for achieving maximum simplification. Remember that the K-Map wraps around on all sides, making corner cells and edge cells adjacent.

🧠 Quick Revision Questions

1. How many cells does a 4-variable Karnaugh Map have, and what is the binary representation of the cell marked '13'?
2. In the Odd-Prime Number Checker example, what was the simplified Boolean expression when only inputs 0 to 9 were considered (states 10-15 were don't cares)?
3. What is the relationship between the size of a group in a 4-variable K-Map (1, 2, 4, 8, or 16 cells) and the number of variables in its resulting product term?
4. What are the four types of adjacent cells that can be grouped in a K-Map?
5. In a 3-variable K-Map using row form, what do the binary values 0 and 1 in the left column represent, and what do the binary values 00, 01, 11, and 10 in the top row represent?

📘 Lecture 11 — Karnaugh Map & Boolean Expression Simplification

📖 Overview: This lecture extends Karnaugh Map techniques to simplify standard Product-of-Sums (POS) expressions, demonstrating how groups of 0s are used instead of 1s. It also covers converting between POS and SOP forms using the K-map, introduces 5-variable Karnaugh maps, and explains how to design multiple-output logic circuits using the example of a BCD to 7-Segment Decoder, including the use of don't care conditions for simplification.

🗂️ Topics Covered

Mapping a Standard POS Expression, Karnaugh Map simplification of POS expressions (with rules for sum-term reduction in 3-variable and 4-variable K-maps), worked examples (1–7) of POS simplification, converting between POS and SOP using the K-map, introduction to Five-Variable Karnaugh Maps (construction, mapping, grouping, and simplification), and Functions having multiple outputs exemplified by a BCD to 7-Segment Decoder (function tables, Karnaugh maps, and simplified expressions for each segment a–g).

📝 Lecture Summary

Mapping a Standard POS Expression

To map a standard POS expression on a K-map, place a 0 in the cell corresponding to each maxterm (sum term) present in the expression. All other cells receive a 1. For example, the standard POS expression (A + B + C)・(A + B + C)・(A + B + C)・(A + B + C) over a domain of three variables has maxterms 1, 2, 5, and 7, so 0s are placed at those locations and 1s elsewhere.

🔑 Definition — Maxterm: a sum term in a POS expression where each variable appears once, either complemented or un-complemented.

Karnaugh Map simplification of POS expressions

POS expressions are simplified on a K-map by grouping cells containing 0s (instead of 1s). The same rules for forming groups apply as for SOP simplification. After grouping, each group represents a simplified sum term where variables that appear in both complemented and un-complemented forms within the group are eliminated.

🔑 Definition — Sum Term (from a POS group): a term formed by variables that appear in only one form (complemented or un-complemented) within the group.

For a 3-variable K-map:

• A group of 1 cell yields a 3-variable sum term.
• A group of 2 cells yields a 2-variable sum term.
• A group of 4 cells yields a 1-variable sum term.
• A group of 8 cells yields a value of 0 for the expression.

For a 4-variable K-map:

• A group of 1 cell yields a 4-variable sum term.
• A group of 2 cells yields a 3-variable sum term.
• A group of 4 cells yields a 2-variable sum term.
• A group of 8 cells yields a 1-variable sum term.
• A group of 16 cells yields a value of 0 for the expression.

Example 1 & 2 (Figure 11.2)

A POS expression with 3 maxterms is mapped to a 3-variable column-based K-map. Two groups are formed:

• Group of cells 0 and 4 forms the sum term (B + C).
• Single cell 3 forms the sum term (A + B + C). The simplified expression is (B + C)・(A + B + C).

A POS expression with 4 maxterms forms three groups:

• Single cell 0: (A + B + C)
• Group of cells 5 and 7: (A + C)
• Group of cells 6 and 7: (A + B) The expression simplifies to (A + B + C)・(A + C)・(A + B).

Example 3 & 4 (Figure 11.3)

A POS expression with 3 maxterms forms two groups of two cells:

• Group of cells 0 and 1: (A + B)
• Group of cells 0 and 4: (B + C) Simplifies to (A + B)・(B + C).

Another 3-maxterm POS expression forms a group of 2 cells and a single cell:

• Group of cells 0 and 1: (A + B)
• Single cell 6: (A + B + C) Simplifies to (A + B)・(A + B + C).

Example 5 (Figure 11.4)

A POS expression with 5 maxterms is mapped to a 4-variable K-map. Three groups of two cells are formed:

• Group of cells 4 and 5: (A + B + C)
• Group of cells 0 and 4: (A + C + D)
• Group of cells 2 and 10: (B + C + D) Simplifies to (A + B + C)・(A + C + D)・(B + C + D).

Example 6 (Figure 11.5)

A POS expression with 8 maxterms is mapped to a 4-variable K-map. Groups formed:

• Group of cells 0, 1, 4, 5: (A + C)
• Group of cells 1, 5, 9, 13: (C + D)
• Group of cells 2 and 10: (B + C + D) Simplifies to (A + C)・(C + D)・(B + C + D).

Example 7 (Figure 11.6)

A POS expression with 6 maxterms forms:

• Group of cells 4 and 5: (A + B + C)
• Group of cells 5 and 7: (A + B + D)
• Group of cells 1 and 9: (B + C + D)
• Single cell 14: (A + B + C + D) Simplifies to (A + B + C)・(A + B + D)・(B + C + D)・(A + B + C + D).

Converting between POS and SOP using the K-map

On a K-map that already has 0s and 1s plotted, grouping the 1s produces the SOP expression. Grouping the 0s produces the POS expression. For example, from the K-map in Figure 11.7, grouping 1s yields the SOP expression BD + BC + ABC + ABD + ACD.

Five-Variable Karnaugh Map

A 5-variable K-map is constructed by stacking two 4-variable K-maps. Cells 0–15 lie in the map for variable A=0, and cells 16–31 lie in the map for A=1. Groups can span across both maps, forming groups of 2, 4, 8, 16, or 32 cells.

Simplification of 5-Variable Karnaugh Map (Figure 11.9)

Two 4-variable K-maps (A=0 and A=1) are used. Groups are formed:

• Cells 1, 5, 17, 21: group of 4 → BDE
• Cell 2 (A=0): single cell → ABCDE
• Cells 10, 11, 26, 27: group of 4 → BCD
• Cells 11, 14, 26, 30: group of 4 → BDE
• Cells 16, 17, 20, 21 (A=1): group of 4 → ABD
• Cells 25, 27 (A=1): group of 2 → ABCDE

Functions having multiple outputs

Practical logic circuits often have multiple inputs and multiple outputs. Each output is represented by its own function table (or a combined table). The BCD to 7-Segment Decoder is an example: it has 4 inputs (A, B, C, D) and 7 outputs (segments a, b, c, d, e, f, g). For each BCD digit (0–9), specific segments light up. Since only 10 of 16 input combinations are valid, the remaining 6 are don't care conditions (x), which help simplify the Boolean expressions for each segment.

Seven function tables (Figure 11.12a–g) define output 1 or 0 for each input combination. Using seven 4-variable K-maps (Figure 11.13a–g), the simplified expressions are:

🔑 Definition — Don't Care Condition: input combinations that never occur and can be treated as either 0 or 1 to achieve the simplest possible logic expression.

• a = A + C + BD + BD
• b = B + CD + CD
• c = C + D + B
• d = A + BD + BC + CD + BCD
• e = BD + CD
• f = B + CD + BC + BD
• g = A + BC + CD + BC

📐 Formula (simplified segment a): a = A + C + BD + BD → A OR C OR (B AND NOT D) OR (NOT B AND D) 📐 Formula (simplified segment b): b = B + CD + CD → B OR (C AND D) OR (C AND NOT D) 📐 Formula (simplified segment c): c = C + D + B → C OR NOT D OR NOT B

💡 Why this matters: Using don't care conditions dramatically reduces circuit complexity. Without them, expressions for segments like 'a' would require many more gates, increasing cost, power, and propagation delay.

⭐ Key Takeaways

For exam success, remember that POS simplification on a K-map uses groups of 0s (not 1s), and the size of the group determines how many variables are eliminated from the sum term. Converting between POS and SOP is simply a matter of grouping 0s or 1s on the same map. Five-variable K-maps are built from two stacked 4-variable maps where groups can cross between them. Finally, when dealing with multiple-output circuits like a BCD-to-7-segment decoder, don't care states (from unused input combinations) are critical tools for obtaining the simplest possible Boolean expressions for each output.

🧠 Quick Revision Questions

1. In a 3-variable K-map, what is the size of the sum term produced by a group of 2 cells containing 0s?
2. A POS expression mapped on a 4-variable K-map has groups of 0s covering cells 0, 1, 4, 5 and cells 2, 10. What are the two simplified sum terms?
3. How do you convert a mapped POS expression into its equivalent SOP form?
4. For a 5-variable K-map, how many cells are in the map for A=0, and how do you form a group that spans both sub-maps?
5. In the BCD to 7-Segment decoder, why are don't care conditions (x) used, and how do they affect the simplified expression for segment 'a'?

📘 Lecture 12 — COMPARATOR

📖 Overview: This lecture introduces comparator circuits that compare two binary numbers and produce three outputs indicating whether one is greater than, equal to, or less than the other. It then transitions to the Quine-McCluskey simplification method, a program-based approach that overcomes the limitations of Karnaugh maps when dealing with more than four variables, making it essential for handling larger digital logic problems.

🗂️ Topics Covered

The lecture covers the design and function table of a 2-bit comparator circuit with its three outputs (A>B, A=B, A<B) and corresponding Karnaugh map simplifications. It then introduces the Quine-McCluskey simplification method as a systematic alternative to K-maps, explaining the problem of redundant terms in K-map grouping. Two detailed examples demonstrate the full Quine-McCluskey process of finding Prime Implicants through exhaustive search and selecting minimal Prime Implicants. The lecture concludes with applications to larger comparator circuits (3-bit and 6-bit) and an Odd-Prime Number Detector circuit for 5-bit numbers.

📝 Lecture Summary

COMPARATOR

A comparator circuit compares two numbers and sets one of its three outputs to 1, indicating the result of the comparison operation. A comparator circuit has multiple inputs and three outputs. A 2-bit Comparator circuit compares two 2-bit numbers A and B. The comparator circuit has three outputs: it sets the A>B output to 1 if A>B, sets the A=B output to 1 if A=B, and sets the A<B output to 1 if A<B.

The output A>B is set to 1 when the input combinations are 01 00, 10 00, 10 01, 11 00, 11 01 and 11 10. The output A=B is set to 1 when the input combinations are 00 00, 01 01, 10 10 and 11 11. The output A<B is set to 1 when the input combinations are 00 01, 00 10, 00 11, 01 10, 01 11 and 10 11.

The circuit has 4-bit input (2-bits represent A and 2-bits represent B) and a 3-bit output representing A>B, A=B and A<B. To represent the function of a Comparator circuit, three function tables are required for each of the three outputs. A single function table is drawn with three outputs (Table 12.1).

Each of the three outputs, A>B, A=B and A<B are mapped separately using three 4-variable Karnaugh maps. The Karnaugh Maps and the simplified expressions for the three outputs are:

(A > B) = A₁B̄₁ + A₀B̄₁B̄₀ + A₁A₀B̄₀

(A = B) = Ā₁Ā₀B̄₁B̄₀ + Ā₁A₀B̄₁B₀ + A₁A₀B₁B₀ + A₁Ā₀B₁B̄₀

(A < B) = Ā₁B₁ + Ā₁Ā₀B₀ + Ā₀B₁B₀

Quine-McCluskey Simplification Method

The Karnaugh map method becomes difficult to manage when numbers of variables exceed 4. Even with a 4-variable K-map, grouping of 1s or 0s depends on the ability of the user to detect optimum groups. Sometimes some redundant groups are included which adds a product term or a sum term which is not required, and thus the expression is not the simplified version.

In a 4-variable K-map, 6 groups of 4 cells each can be formed, producing six terms AB, AC, AD, BC, CD and BD. Out of these six terms, three terms are redundant, and the essential terms required are AC, BC and BD. Finding redundant terms is not very obvious.

The Quine-McCluskey approach of simplifying Boolean expression is based on an exhaustive search where each minterm is compared with every other minterm in order to remove single variables. The exhaustive search is continued until only a few terms remain which do not share any common variable that can be eliminated. From these remaining terms, the minimal product terms are selected that represent the simplified form of Boolean expression.

Quine-McCluskey is a program-based method that is able to carry out the exhaustive search for removing shared variables. The Quine-McCluskey method is a two-step method which comprises of:

• Find Prime Implicants: Find by an exhaustive search all the terms that are candidates for inclusion in the simplified function. These terms are known as Prime Implicants.
• Selecting Minimal Set of Prime Implicants: Choose from amongst the Prime Implicants those that give expression with the least number of literals.

Example 1

A function is defined in Canonical Sum form as ΣA,B,C,D(1,3,6,7,8,9,11,12,13,14,15). As the first step to find the Prime Implicants through an exhaustive search, all the Minterms are listed in a tabular form (Table 12.2). The Table of Minterms is reorganized and the Minterms are arranged in groups of minterms having 0, 1, 2, 3 and 4 1s (Table 12.3). Four groups of Minterms are formed:

• Minterms 1 and 8 have only single 1s
• Minterms 3, 6, 9 and 12 have two 1s each
• Minterms 7, 11, 13 and 14 have three 1s each
• Minterm 15 has 4 1s.

When comparing minterms, the rule is to compare each minterm in one group with each minterm in the other group. Minterms 1 and 8 are compared with each of the 4 minterms 3, 6, 9 and 12. Each of the 4 minterms 3, 6, 9 and 12 are compared with minterms 7, 11, 13 and 14. Finally, each of the minterms 7, 11, 13 and 14 are compared with minterm 15.

The results of the comparisons between two minterms are represented in a separate table (Table 12.4). Terms 1 and 3 form a single term eliminating variable C, forming the product term ĀB̄D. Terms 1 and 9 form a single term eliminating variable A, forming the product term B̄C̄D. Terms 8,9 eliminate variable D, terms 8,12 eliminate variable B, terms 3,7 eliminate variable B, and so on. A total of 16, three-variable product terms are formed.

The three-variable terms in table 12.4 are compared to eliminate another single variable (Table 12.5). Terms 1,3 and terms 9,11 form the product term B̄D eliminating variable A. Terms 1,3 and 9,11 are different in a single variable A only. In table 12.5, there are 6 product terms of two variables each: BD, AC, CD, BC, AD and AB. If the terms in table 12.5 are compared, none form pairs to eliminate a variable, so all 6 terms are Prime Implicants.

In the second step, the essential and minimal Prime Implicants are found (Table 12.6). The Prime Implicants are listed in the left column and all original minterms in the top row. In each cell, an x is marked indicating that the Prime Implicant covers the minterm. Circles are marked in cells having x which represent minterms covered by only a single Prime Implicant. Minterms 1, 6 and 8 are covered by only the Prime Implicants B̄D, AC and BC respectively. These three Prime Implicants are the three essential Prime Implicants that cover all the minterms. The simplified expression is:

B̄D + AC + BC

Example 2

A function is defined as ΣA,B,C,D(1,5,6,7,11,12,13,15). The minterms are written in tabular form (Table 12.7) and reorganized in terms of groups of 1s (Table 12.8):

• Minterm 1 has a single 1
• Minterms 5, 6 and 12 have two 1s each
• Minterms 7, 11 and 13 have three 1s each
• Minterm 15 has 4 1s.

Minterm 1 is compared with minterms 5, 6 and 12. Each of minterms 5, 6 and 12 are compared with minterms 7, 11 and 13. Finally, each of minterms 7, 11 and 13 are compared with minterm 15 (Table 12.9). Terms 1 and 5 form a single term eliminating variable B, forming the product term ĀC̄D. Terms 5 and 7 form a term eliminating variable C, forming product term ĀB̄D. Terms 5,13 eliminate variable A, terms 6,7 eliminate variable D, terms 12,13 eliminate variable D, and so on. A total of 8, three-variable product terms are formed.

Terms 5,7 and 13,15 compare to form product term BD eliminating variable A (Table 12.10). No more comparisons take place. The five Prime Implicants are: ĀC̄D, ĀB̄C, AB̄C, ACD and BD.

In the second step (Table 12.11), the Prime Implicant ĀC̄D covers minterms 1 and 5. Circles are marked for minterms covered by only a single Prime Implicant. Minterms 1, 6, 11 and 12 are covered by only ĀC̄D, ĀB̄C, AB̄C and ACD respectively. The simplified expression is:

ĀC̄D + ĀB̄C + AB̄C + ACD

Comparator Circuit

A 2-bit Comparator circuit that compares two 2-bit numbers A and B has been discussed earlier. A comparator circuit that compares two 3-bit numbers A and B instead of 2-bit numbers has an input of 6-bits, representing an input combination of 64. Writing a truth table and simplifying the three expressions using 6-variable Karnaugh maps becomes unmanageable. A program-based Quine-McCluskey method can easily handle expressions of 6 variables represented in the Canonical form ΣA,B,C,D,E,F(8,16,17,24,...).

Odd-Prime Number Detector

A circuit that detects Odd Prime numbers between 0 and 9 has been considered earlier. The circuit is to be improved to detect Odd Prime numbers for a decimal number range represented by 5-bit binary numbers (decimal numbers 0 to 31). Writing out a function table for 32 input combinations and simplifying using a 5-variable K-map takes considerable time.

The Quine-McCluskey method can be used to easily simplify the 5-variable Boolean expression represented in Canonical Sum form as ΣA,B,C,D,E(1,3,5,7,11,13,17,19,23,29,31). The minterms 1, 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31 represent the 5-bit input combinations which are Odd and Prime numbers.

⭐ Key Takeaways

The comparator circuit is a fundamental building block that compares two binary numbers and activates exactly one of three outputs (A>B, A=B, A<B). For 2-bit comparators, 4-variable Karnaugh maps provide manageable simplification, yielding the Boolean expressions for all three outputs. However, the Quine-McCluskey method becomes essential when dealing with more than four variables, as K-map grouping becomes impractical and prone to redundant terms. The Quine-McCluskey process involves two critical steps: first, an exhaustive search to find all Prime Implicants by systematically eliminating variables through pairwise comparison of minterms, and second, selecting the minimal set of essential Prime Implicants that cover all original minterms. This method is program-based and scales effectively to handle 5-variable and 6-variable problems like the Odd-Prime Number Detector and larger comparator circuits.

🧠 Quick Revision Questions

1. What are the three outputs of a comparator circuit, and what does each output indicate?
2. How does the Quine-McCluskey method differ from the Karnaugh map method when simplifying Boolean expressions?
3. In Example 1, what was the final simplified Boolean expression, and which Prime Implicants were identified as redundant?
4. When comparing minterms in the exhaustive search phase, what is the rule for determining which groups of minterms should be compared against each other?
5. In Example 2, why were the Prime Implicants ĀC̄D, ĀB̄C, AB̄C and ACD considered essential, while BD was not?

📘 Lecture 13 — ODD-PRIME NUMBER DETECTOR

📖 Overview: This lecture completes the Quine-McCluskey method for simplifying Boolean expressions with five variables using the Odd-Prime Number Detector example. It then introduces Combinational Logic circuits, explaining how to implement and simplify circuits using SOP and POS forms, and covers active-high/active-low inputs and outputs through the Adjacent 1s Detector and Odd-Parity Generator examples.

🗂️ Topics Covered

The Quine-McCluskey method is applied step-by-step to minimize the Odd-Prime Number Detector function with five variables, finding Prime Implicants and essential Prime Implicants. Combinational Logic is introduced, explaining how individual gates combine to form useful circuits. The SOP and POS implementation architectures are explained with three-level gate diagrams. The Adjacent 1s Detector is designed and implemented from its function table using both SOP and POS forms, simplified via Karnaugh maps, and then converted to NAND-only and NOR-only implementations. Active-low and active-high inputs and outputs are discussed, and the Odd-Parity Generator circuit is introduced as a design example.

📝 Lecture Summary

ODD-PRIME NUMBER DETECTOR

The lecture begins with the Odd-Prime Number Detector which has five input variables (A, B, C, D, E). The function is defined by 11 minterms: 1, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31 (Table 13.1). These minterms are reorganized into groups based on the number of 1s in each minterm (Table 13.2): minterm 1 has one 1; minterms 3, 5, and 17 have two 1s each; minterms 7, 11, 13, and 19 have three 1s each; minterms 23 and 29 have four 1s; minterm 31 has five 1s.

In the first step of the Quine-McCluskey method, minterms are compared to eliminate single variables. Minterm 1 is compared with minterms 3, 5, and 17 in the next group. Minterms 3, 5, and 17 are compared with minterms 7, 11, 13, and 19. Minterms 7, 11, 13, and 19 are compared with minterms 23 and 29. Minterms 23 and 29 are compared with minterm 31.

🔑 Definition — Quine-McCluskey method: A systematic tabular method for minimizing Boolean expressions, particularly useful when the number of variables exceeds 4, where Karnaugh maps become impractical.

🔑 Definition — Prime Implicant: A product term that cannot be further combined with any other term to eliminate a variable.

The results of comparisons produce 14 four-variable product terms (Table 13.3). For example, terms 1 and 3 eliminate variable D, forming product term ĀB̄CĒ. Terms 1 and 5 eliminate variable C, forming ĀB̄D̄Ē. The comparison continues, and in Table 13.4, terms 1, 3, 5, and 7 form a single term eliminating variables C and D, forming ĀB̄Ē. Terms 1, 3, 17, and 19 eliminate variables A and D, forming B̄C̄Ē.

Eight Prime Implicants are found: three from Table 13.4 and five from Table 13.3. These are represented by product terms: ĀC̄D̄E, ĀCDĒ, BC̄DĒ, AC̄D̄E, AB̄C̄Ē, ĀB̄Ē, B̄C̄Ē, and B̄DĒ.

In the second step, essential and minimal Prime Implicants are found using a Prime Implicant table (Table 13.5). Each Prime Implicant is listed in the left column, and all original minterms are listed in the top row. An "x" in a cell indicates that the Prime Implicant covers that minterm. Circles are marked in cells having "x" that represent minterms covered by only a single Prime Implicant. Minterms 11 and 17 are covered by only ĀCDĒ and B̄C̄Ē respectively. The other essential implicants with minimum variables covering all remaining minterms are BC̄DĒ, AC̄D̄E, and ĀB̄Ē.

📌 Example: The simplified expression is F = ĀCDĒ + BC̄DĒ + AC̄D̄E + ĀB̄Ē + B̄C̄Ē

The function can also be represented as: F = ĀC̄D̄E + ĀCDĒ + AB̄C̄Ē + B̄C̄Ē + B̄DĒ

In both cases, the number of product terms is the same with the same number of variables.

💡 Why this matters: The Quine-McCluskey method provides a systematic, algorithm-friendly approach to Boolean minimization that works for any number of variables, unlike Karnaugh maps which become unwieldy beyond 4-5 variables.

Combinational Logic

Individual gates (AND, OR, NOT, NAND, NOR, XOR, XNOR) in their individual capacity cannot perform any useful function. Logic gates must be connected together in different combinations to form Logic Circuits that perform useful operations like addition, comparison, etc. These combinations of gates that result in a circuit used to perform some function are known as Combinational Logic.

The function of any Digital Logic circuit is represented by Boolean expressions. Two forms of representing functions through Boolean expressions are the SOP (Sum of Products) and POS (Product of Sums) expressions. These two types of Boolean expressions are implemented using a combination of gates to form Combinational Logic Circuits.

Combinational Circuit Implementation based on SOP form

A standard way to express a Boolean expression is the SOP form. The expression has several product terms which are summed together through a single OR gate. The product terms can have variables and their complemented form. A SOP expression is implemented using a combinational circuit made up of many AND gates and a single OR gate (AND-OR gate combination). The inputs to the AND gates can be in the complemented form or the un-complemented form, requiring the use of NOT gates.

The implementation is based on three levels of gates (Figure 13.1):

• NOT gate level: Produces complemented literals
• AND gate level: Produces the product terms
• OR gate level: Sums all product terms through a single multiple-input OR gate

Combinational Circuit Implementation based on POS form

A standard way to express a Boolean expression is the POS form. The expression has several sum terms which are multiplied together through a single AND gate. The sum terms can have variables and their complemented form. A POS expression is implemented using a combinational circuit made up of many OR gates and a single AND gate (OR-AND gate combination).

The implementation is based on three levels of gates (Figure 13.2):

• NOT gate level: Produces complemented literals
• OR gate level: Produces the sum terms
• AND gate level: Multiplies all sum terms through a single multiple-input AND gate

Design and Implementation of Combinational Circuits

The design and implementation of a combinational circuit starts by defining the function of the Combinational circuit using a truth table or function table. Once the function table is defined, the combinational circuit can be directly implemented from the function table.

Direct implementation from the function table results in a circuit using maximum number of gates organized at three levels. This increases cost, size, power requirement, and propagation delay (order of three gates). Therefore, before implementing the circuit, the expression is simplified using Boolean Algebra rules, Karnaugh map method, or the Quine-McCluskey method if the number of variables exceeds 4.

Implementation of an Adjacent 1s Detector Circuit

A circuit that checks an input number and determines if it has two adjacent 1s is used as an example. The Adjacent 1s Detector accepts 4-bit inputs. If two adjacent 1s are detected in the input, the output is set to high. From the function table (Table 13.6), for input combinations 0011, 0110, 0111, 1011, 1100, 1101, 1110, and 1111, the output function F is 1.

1. SOP based Implementation of the Adjacent 1s Detector Circuit

Direct implementation from the function table based on the SOP form requires 8 AND gates for the 8 product terms with an 8-input OR gate (Figure 13.3). Total gate count: one 8-input OR gate, eight 4-input AND gates, and ten NOT gates.

The expression is simplified using a Karnaugh map (Figure 13.4). The simplified expression is: 📐 Formula: F = AB + CD + BC → Plain English: The output is 1 when A and B are both 1, OR when C and D are both 1, OR when B and C are both 1.

The simplified circuit (Figure 13.5) uses only four gates: one 3-input OR gate and three 2-input AND gates. This reduces cost, size, power requirement, and propagation delay to the order of two gates.

The simplified SOP circuit can be implemented using only NAND Gates (Figure 13.6). Bubbles (NOT gates) are placed at the outputs of the three AND gates, converting them to NAND gates. Three bubbles are also placed at the three inputs of the OR gate, resulting in an alternate symbol for a three-input NAND gate. Implementing using only NAND gates helps reduce circuit size and cost as Integrated Circuit packages multiple gates in a single package.

2. POS based Implementation of the Adjacent 1s Detector Circuit

The POS based circuit has 8 sum terms requiring 8 OR gates and a single 8-input AND gate (Figure 13.7). Total gate count: one 8-input AND gate, eight 4-input OR gates, and ten NOT gates.

Both SOP and POS based circuits give identical outputs for identical input combinations. In this example, both implementations use exactly the same number of gates (19) as there are equal numbers of minterms (8) and maxterms (8).

The POS expression is simplified using a Karnaugh map (Figure 13.8): 📐 Formula: F = (A + C)(B + C)(B + D) → Plain English: The output is 1 when (A OR C is 1) AND (B OR C is 1) AND (B OR D is 1).

The simplified POS circuit (Figure 13.9) uses only four gates: three 2-input OR gates and one 3-input AND gate. This can be implemented using only NOR Gates (Figure 13.10) by placing bubbles at the outputs of the three OR gates to convert them to NOR gates, and three bubbles at the three inputs of the AND gate to create an alternate symbol for a three-input NOR gate.

Operation of Adjacent 1s Detector Circuit

The operation can be verified by applying varying sets of input signals and comparing outputs with the function table. The timing diagram (Figure 13.11) shows inputs A, B, C, D changing over time intervals t0 to t8. At interval t0 with input 0000, all three OR gate outputs are 0 and output F is 0. At interval t3 with input 0011, OR gate outputs are 1, 1, 1 and output F is 1 (indicating adjacent 1s). At interval t6 with input 0110, OR gate outputs are 1, 1, 1 and output F is again 1.

Active low/high Inputs and Outputs

All circuits discussed so far have active-high outputs — normally at logic 0, set to 1 to indicate an active state. Combinational circuits can have active-high or active-low outputs. Converting from active-high to active-low requires inverting the output by connecting a NOT gate (adding a bubble). Circuits with bubbles at outputs are considered to have active-low outputs.

Circuits can also have active-high or active-low inputs. Active-low input circuits are activated on a logic 0 input and have bubbles connected to circuit inputs.

The four logic gates can be described in terms of input and output logic levels:

• AND gate: No bubbles at inputs or output; performs AND on two active-high inputs for active-high output
• OR gate: No bubbles at inputs or output; performs OR on two active-high inputs for active-high output
• NAND gate: Bubble at output; performs AND on two active-high inputs for active-low output
• NOR gate: Bubble at output; performs OR on two active-high inputs for active-low output

Figure 13.12 shows the SOP-based active-high circuit converted to active-low input and output by connecting NOT gates. The timing diagram (Figure 13.13) verifies operation. At interval t0, active-low input ABCD is 0000 (representing 1111), and active-low output F is 0 (indicating adjacent 1s detected). At intervals t1 to t4, active-low inputs represent 1110, 1101, 1100, and 1011 respectively, with output 0 indicating adjacent 1s.

Implementation of an Odd-Parity Generator Circuit

The Odd-Parity Generator circuit checks an 8-bit number and generates a parity bit to fulfill the Odd-Parity condition. The 8-bit data and parity bit are communicated to the receiver circuit, which checks both to determine if an error occurred. For simplicity, a 4-bit data with odd parity is assumed.

💡 Why this matters: Parity generation and checking is fundamental for error detection in digital communication systems, ensuring data integrity during transmission.

⭐ Key Takeaways

The Quine-McCluskey method provides a systematic algorithm for minimizing Boolean expressions with more than four variables by finding all Prime Implicants and then selecting essential ones using a Prime Implicant table. Combinational Logic circuits are built from gate combinations and their implementation depends on choosing between SOP and POS forms — the form with fewer minterms or maxterms yields a simpler circuit. The Adjacent 1s Detector demonstrates that Boolean expressions must be simplified (using K-maps or Quine-McCluskey) before implementation to reduce gate count, cost, power, and propagation delay. Any SOP circuit (AND-OR) can be converted to NAND-only implementation, and any POS circuit (OR-AND) can be converted to NOR-only implementation, which reduces IC package count. Active-low and active-high inputs/outputs don't change circuit logic but affect how signals are interpreted, requiring inversion through NOT gates when converting between them.

🧠 Quick Revision Questions

1. What are the essential Prime Implicants found for the Odd-Prime Number Detector function with five variables, and which minterms do they cover?
2. How does the Quine-McCluskey method differ from Karnaugh maps in terms of applicability and procedure?
3. What is the simplified SOP expression for the Adjacent 1s Detector, and how many gates does the simplified circuit use compared to the direct implementation?
4. How do you convert an AND-OR (SOP) combinational circuit into a NAND-only implementation, and what is the advantage of doing so?
5. What is the difference between active-high and active-low inputs/outputs, and how does the timing diagram change when converting a circuit from active-high to active-low?

📘 Lecture 14 — Implementation of an Odd-Parity Generator Circuit

📖 Overview: This lecture covers the implementation of an odd-parity generator circuit for error detection in digital data transmission, starting from a truth table and Karnaugh map simplification to the final logic circuit using XOR/XNOR gates. It also introduces combinational functional devices like half-adders and full-adders, and explores the critical issue of carry propagation in parallel binary adders and the use of look-ahead carry circuits to speed up addition.

🗂️ Topics Covered

This lecture begins with the design of an odd-parity generator for a 4-bit data system, including the function table and Karnaugh map simplification leading to a Boolean expression using XOR and XNOR gates. It then covers the operation and timing of the parity generator and an error detection circuit at the receiver end. The discussion then shifts to combinational functional devices, especially half-adders and full-adders, their logic circuits, and Boolean expressions. Finally, it explores parallel binary adders, the problem of carry propagation (ripple), and the solution provided by look-ahead carry generator circuits, concluding with MSI adder ICs like 74LS283.

📝 Lecture Summary

Implementation of an Odd-Parity Generator Circuit

The first step in implementing an odd-parity generator for an 8-bit data system (256 combinations) is too complex, so a simpler 4-bit data system is used. The function table for the odd-parity generator lists all 16 combinations of the 4-bit data (D3, D2, D1, D0) and the required parity bit (P). Since odd parity is used, the total number of 1s in the 4-bit data plus the parity bit must be odd. Therefore, the parity bit P is set to 1 when the data has an even number of 1s (including zero), making the total odd.

🔑 Definition — Odd-Parity: A parity scheme where the total number of 1s in a data word including the parity bit is odd. 📌 Example: For 4-bit data 0000 (even number of 1s), the odd-parity bit P is set to 1, making the total number of 1s (one) odd.

Karnaugh map of the Odd-Parity Generator Function

The information from the function table is mapped directly onto a four-variable K-map. None of the 1s in the K-map are adjacent to each other, which indicates that the function cannot be simplified using a K-map alone. However, using Demorgan's theorems and the rules of Boolean algebra, the expression can be simplified by recognizing the pattern of XOR and XNOR functions.

📐 Formula: The simplified Boolean expression for the odd-parity generator is P = (A ⊕ B) ⊕ (C ⊕ D). This means the parity bit is the XOR of all data bits. 📌 Example: For inputs A=0, B=0, C=0, D=0: (0⊕0) ⊕ (0⊕0) = 0 ⊕ 0 = 0. But the function table shows P=1 for 0000. This expression is for even parity. Wait, the lecture shows that for odd parity, the function is an XNOR of the XOR results, or equivalently, the XOR of all bits has to be inverted. The lecture's final circuit uses an XNOR gate. The lecture text states the final expression as (A ⊕ B) ⊕ (C ⊕ D) but the circuit uses an XNOR. Let's check the circuit description. The output P is the output of an XNOR gate whose inputs are the outputs of two XOR gates. So the function is P = (A ⊕ B) ✪ (C ⊕ D). This is the XNOR function. Therefore, the odd parity bit is the XNOR of all data bits. If the data bits are 0000, P = (0⊕0) ✪ (0⊕0) = 0 ✪ 0 = 1. This matches the function table. 💡 Why this matters: The XOR/XNOR structure allows the parity generator to be built using just two XOR gates and one XNOR gate instead of many AND/OR gates.

Operation of Odd-Parity Generator Circuit

The timing diagram shows the operation of the parity generator circuit. During different time intervals (t0 to t8), the 4-bit data values change (e.g., 0000, 0001, 0010, 0011, 0100, 1000). The circuit's output P changes accordingly to ensure odd parity. For example, during interval t0 (data=0000), the outputs of the two XOR gates are 0 and 0, so the output of the XNOR gate (P) is 1.

📌 Example: During interval t1 (data=0001), the outputs of the two XOR gates are 1 and 0, so the output of the XNOR gate (P) is 0. The 4-bit data 0001 has one 1 (odd), so the parity bit is 0, keeping the total number of 1s odd.

XOR and XNOR Gates

XOR and XNOR gates are used to implement the odd-parity generator circuit because they perform simple comparison functions. The XOR gate detects dissimilar inputs (outputs 1 when inputs are different), while the XNOR gate detects similar inputs (outputs 1 when inputs are the same). These gates are considered functional devices and are available as integrated circuits. The function table for the parity error detector at the receiver is identical to the XOR gate's truth table.

📐 Formula: The Boolean expression for an XOR gate is A'B + AB' (often written as A⊕B). The Boolean expression for an XNOR gate is AB + A'B' (often written as A✪B). 💡 Why this matters: XOR and XNOR gates are building blocks for many digital circuits, including comparators and arithmetic circuits.

Combinational Function Devices

Digital circuits are formed by combining logic gates. Most combinational circuits perform standard functions like addition, comparison, decoding, encoding, multiplexing, and de-multiplexing. Since implementing these functions from basic gates takes significant space, they are often implemented as MSI (Medium Scale Integration) chips. The simplest functional devices are NAND, NOR, XOR, and XNOR gates.

Half Adder and Full Adder

A single-bit binary adder circuit adds two bits and a carry bit from a previous addition. It has three inputs (bit A, bit B, and carry-in) and two outputs (sum and carry-out). A full adder has three inputs (including carry-in), while a half adder has only two inputs (A and B, no carry-in).

Half-Adder Function Table

The half-adder has a 2-bit input (A, B) and a 2-bit output (Sum, Carry Out).

🔑 Definition — Half-Adder: A combinational circuit that adds two single-bit binary numbers and produces a sum and a carry output. It has no provision for a carry input from a lower-order bit.

Half-Adder Sum & Carry Out Boolean Expressions

From the function table, the Boolean expressions for the half-adder are derived.

📐 Formula: Sum = A'B + AB' = A ⊕ B CarryOut = AB

Half-Adder Logic Circuit

The half-adder logic circuit can be directly implemented from its Boolean expressions: an XOR gate for the Sum and an AND gate for the Carry Out.

Full-Adder Function Table

The full adder has a 3-bit input (A, B, Carry In) and a 2-bit output (Sum, Carry Out).

🔑 Definition — Full-Adder: A combinational circuit that adds three single-bit binary numbers (A, B, and a carry-in) and produces a sum and a carry output.

Full-Adder Sum & Carry Out Boolean Expressions

From the function table, the Boolean expressions for the full-adder are derived and simplified.

📐 Formula: Sum = A ⊕ B ⊕ C (where C is the carry-in) CarryOut = AB + C(A ⊕ B) = AB + BC + AC 📌 Example: For inputs A=1, B=1, C=1: Sum = 1⊕1⊕1 = 0⊕1 = 1. CarryOut = (11) + 1(1⊕1) = 1 + 1*0 = 1. (1+1+1 = 11 in binary, correct).

Full-Adder Logic Circuit

The full-adder can be implemented directly from its Boolean expressions using XOR gates, AND gates, and OR gates.

Forming a Full-Adder using Half-Adders

A 1-bit full-adder can also be implemented by combining two half-adders and an OR gate. The first half-adder computes A⊕B and AB. The second half-adder computes (A⊕B) ⊕ Cin and (A⊕B)Cin. The final Carry Out is AB + (A⊕B)Cin.

Parallel Binary Adders

To add two 4-bit numbers, four single-bit full-adders are connected in series to form a 4-bit Parallel Adder. The two 4-bit numbers (A0-A3 and B0-B3) are applied to the circuit inputs, and the 4-bit sum (S0-S3) and a final carry-out (Cout) are produced. The carry-in (Cin) to the least significant adder is set to 0.

🔑 Definition — Parallel Binary Adder: A circuit that adds two binary numbers of multiple bits simultaneously by connecting full-adders in parallel, where the carry-out of one stage feeds the carry-in of the next.

Carry Propagation

While parallel adders are straightforward to implement, they suffer from a practical limitation called carry propagation or carry ripple. The most significant bit (MSB) adder cannot proceed until it receives the carry from the next lower bit adder, which in turn depends on the carry from the one below it, and so on. The carry must propagate through each full-adder before reaching the most significant stage.

📐 Formula: If each gate has a propagation delay of 10 nsec, a 1-bit full adder generates a carry out after 30 nsec. For a 4-bit parallel adder, the carry out from the most significant adder would be after 4 × 30 nsec = 120 nsec. 📌 Example: For an 8-bit, 16-bit, or 64-bit parallel adder, this delay becomes prohibitive (e.g., 64 × 30 nsec = 1920 nsec or 1.92 µsec for 64-bit), which is too slow for modern computers.

Look-Ahead Carry Circuits

To overcome the problem of carry propagation, look-ahead carry generator circuits are used. These circuits examine the bits to be added (A and B) and determine if a higher-order carry is to be generated, without waiting for the ripple. In a full-adder, the output P (from the XOR gate) is called Carry Propagate (P), and the output G (from the AND gate) is called Carry Generate (G).

🔑 Definition — Carry Propagate (P): P = A⊕B. If P=1, a carry from a lower stage will propagate through this stage. 🔑 Definition — Carry Generate (G): G = A·B. If G=1, this stage will generate a carry-out regardless of the carry-in.

📐 Formula: Sum = P ⊕ C CarryOut = CP + G

The carry outputs for a 4-bit adder can be written in terms of P and G: C1 = C0P0 + G0 C2 = G1 + P1G0 + P0P1C0 C3 = G2 + P2G1 + P1P2G0 + P0P1P2C0 C4 = G3 + P3G2 + P2P3G1 + P1P2P3G0 + P0P1P2P3C0

Where Pn = An ⊕ Bn and Gn = AnBn.

The look-ahead carry generator circuit produces all carry outputs (C1, C2, C3, C4) after only two gate delays once the P and G terms are available, significantly reducing the overall delay. For example, C1 is available after just two gate delays (one AND gate and one OR gate), and C2, C3, and C4 are also available after two gate delays. 💡 Why this matters: This drastically speeds up addition, making it feasible for 16-bit, 32-bit, and 64-bit adders used in modern processors.

MSI Adders

4-bit parallel adders with look-ahead carry circuitry are available as MSI (Medium Scale Integrated Circuit) chips. Two common ICs are 74LS83A and 74LS283 (functionally identical but not pin-compatible). The 16-pin package includes 4 pins for input A, 4 for input B, 4 for output Sum, 1 for Carry In, 1 for Carry Out, plus power and ground. These ICs can be cascaded to form 8-bit, 12-bit, or 16-bit parallel adders by connecting the Carry Out of one IC to the Carry In of the next.

⭐ Key Takeaways

The most critical concepts from this lecture include: (1) the odd-parity generator circuit can be efficiently implemented using XOR and XNOR gates, with the expression P = (A⊕B) ✪ (C⊕D) for 4-bit data; (2) a half-adder adds two bits (Sum = A⊕B, Cout = A·B), while a full-adder adds three bits (Sum = A⊕B⊕Cin, Cout = AB + Cin(A⊕B)); (3) parallel binary adders suffer from carry propagation delay, which increases linearly with the number of bits; (4) look-ahead carry generators solve this by producing carry outputs in parallel, after only two gate delays, using Carry Propagate (P = A⊕B) and Carry Generate (G = A·B) signals; and (5) MSI adder ICs like 74LS283 integrate this technology and can be cascaded for larger word sizes.

🧠 Quick Revision Questions

1. What is the simplified Boolean expression for a 4-bit odd-parity generator circuit, and which gates are used to implement it?
2. Explain the difference between a half-adder and a full-adder. What are their respective Boolean expressions for Sum and Carry Out?
3. What is the main problem with a ripple-carry parallel adder, and how does it affect performance for a 64-bit system?
4. Define the terms "Carry Propagate (P)" and "Carry Generate (G)" in the context of a full-adder. How are they used in a look-ahead carry generator?
5. How can MSI adder ICs like the 74LS283 be used to create a 12-bit binary adder?

📘 Lecture 15 — BCD ADDER

📖 Overview: This lecture covers BCD addition, where a 6 is added to invalid sums to produce correct BCD digits. It extends the concept to 2-digit BCD adders and then introduces subtraction using 2’s complement, showing how an adder can perform both addition and subtraction. Finally, it discusses the Arithmetic and Logic Unit (ALU) and its implementation, including group-carry look-ahead for efficient cascading.

🗂️ Topics Covered

The lecture begins with the BCD Adder, explaining the need for two 4-bit parallel adders and an invalid BCD detector circuit. It then details the design and function table of the invalid BCD detector, followed by its connection to a second adder. The construction of a 2-digit BCD adder by cascading single-digit adders is shown with examples. The topic then shifts to subtraction in digital systems using 2’s complement, leading to the design of a 4-bit adder/subtracter unit and its extension to an 8-bit unit. Finally, the lecture introduces the Arithmetic and Logic Unit (ALU), its variants, and the concept of group-carry look-ahead for cascading multiple ALUs.

📝 Lecture Summary

BCD ADDER

BCD binary numbers represent Decimal digits 0 to 9. A 4-bit BCD code is used to represent the ten numbers 0 to 9. Since the 4-bit Code allows 16 possibilities, the first 10 4-bit combinations are considered to be valid BCD combinations. The latter six combinations are invalid and do not occur. BCD Code has applications in Decimal number Display Systems such as Counters and Digital Clocks. BCD Addition is similar to normal Binary Addition except for the case when sum of two BCD digits exceeds 9 or a Carry is generated. When the Sum of two BCD numbers exceeds 9 or a Carry is generated, a 6 is added to convert the invalid number into a valid number. The carry generated by adding a 6 to the invalid BCD digit is passed on to the next BCD digit. Addition of two BCD digits requires two 4-bit Parallel Adder Circuits. A BCD Adder uses a circuit which checks the result at the output of the first adder circuit to determine if the result has exceeded 9 or a Carry has been generated. If the circuit determines any of the two error conditions, the circuit adds a 6 to the original result using the second Adder circuit. The output of the second Adder gives the correct BCD output. If the circuit finds the result of the first Adder circuit to be a valid BCD number (between 0 and 9 and no Carry has been generated), the circuit adds a zero to the valid BCD result using the second Adder.

🔑 Definition — BCD Adder: A digital circuit that adds two BCD digits, detecting and correcting invalid sums (greater than 9 or with a carry) by adding 6.

The Invalid BCD Detector Circuit

The circuit that checks if the output of the first Adder has exceeded 9 is a simple combinational circuit with a function table. The Boolean expression for the Invalid BCD Number Detector obtained from the Karnaugh Map which maps the function table is S₃S₂ + S₃S₁ = S₃(S₂ + S₁). The Invalid BCD Number is represented by two error conditions: either the BCD number is one of the invalid numbers or a Carry out has been generated. Therefore the complete expression for determining an incorrect BCD output is C_out1 + S₃(S₂ + S₁).

📐 Formula: Invalid BCD Detection: F = C_out1 + S₃(S₂ + S₁) → A logical 1 indicates an invalid BCD sum requiring correction. 📌 Example: If the first adder's output is S₃S₂S₁S₀ = 1010 (decimal 10), C_out1 = 0. The detection circuit computes 0 + 1(0+1) = 1, indicating an invalid sum.

Connection of Invalid BCD Detector Circuit to second Adder

Adding of 6 when error conditions are detected and adding a zero when error conditions are not detected is implemented by connecting the output of the Invalid BCD Number Detector circuit to bits B₁ and B₂ of the Adder. Bits B₀ and B₃ are permanently connected to 0. When an error condition is detected, the output of the circuit is set to logic 1, setting bits B₁ and B₂ to 1 and the 2nd Adder input B to 0110 (binary for 6). When the error condition is not detected, the circuit output is 0 and the 2nd Adder input B is set to 0000.

2-digit BCD Adder

Two single digit BCD Adders can be cascaded together to form a 2-digit BCD Adder. Four, 4-bit 74LS283 MSI chips are used. Two 74LS283s are required to directly add the two 2-digit BCD numbers and the remaining two 74LS283s are required to add a six to the result if any of the two digits add up to invalid BCD digits or generate a Carry. Two invalid BCD detector circuits are used.

📌 Example: Adding BCD numbers 99 and 99. The LSD addition (9+9+0) gives sum 0010 with Cout=1. The detector circuit sees Cout=1 (error condition), so the second LSD adder adds 0010 + 0110 = 1000 with a carry out of 0. The MSD addition (9+9+1) gives sum 0011 with Cout=1. The detector circuit sees Cout=1, so the second MSD adder adds 0011 + 0110 = 1001 with a carry out of 1. The final result is 1 1001 1000 (BCD 198). 📌 Example: Adding BCD numbers 99 and 66. The LSD addition (9+6+0) gives sum 1111 (15) with no carry. The detector circuit finds 1(1+1) = 1 (invalid), so the second LSD adder adds 1111 + 0110 = 0101 with a carry out of 1. The MSD addition (9+6+1) gives sum 0000 with Cout=1. The detector circuit sees Cout=1, so the second MSD adder adds 0000 + 0110 = 0110 with a carry out of 1. The final result is 1 0110 0101 (BCD 165).

Subtraction

Subtraction in Digital Systems is performed by taking the 2’s complement of the number to be subtracted (subtrahend) and adding it to the minuend. The 2’s complement of any number is obtained by taking the 1’s complement of a number and then adding a 1 to the 1’s complement.

📐 Formula: 2’s Complement: 2’s complement of X = 1’s complement of X + 1 📌 Example: To subtract 5 from 9, first find the 2’s complement of 5: (0101) → 1’s complement is 1010 → add 1 gives 1011. Then add: 1001 (9) + 1011 = 1 0100. Neglecting the carry bit, the 4-bit number 0100 represents decimal 4.

An Adder can be used to perform subtraction operations if the minuend is presented in its 1’s complemented form at the input of the adder circuit. The binary 1 that is added to the 1’s complement to convert it into 2’s complement is applied at the Carry In of the Adder Circuit.

A 4-bit Adder/Subtracter Unit

An Adder can be connected to perform Additions and Subtractions by applying the un-complemented and complemented data at one of the two inputs of the Adder respectively. The Carry In input has also to be connected to 0 or 1 respectively. The AND gate and OR gate implementation connected at the B input of the 4-bit Adder is used to allow Complemented or Un-Complemented B input to be connected to the Adder input. Adding of two 4-bit numbers A and B can be performed by selecting the Add/Subtract = 0. The AND gates marked U (un-complemented) are enabled allowing B₀₋₃ to be passed on to the OR gates and the B input of the Adder. Subtraction is performed by selecting the Add/Subtract = 1. The AND gates marked C (complemented) are enabled allowing complemented B₀₋₃ to be passed on to the OR gates and the B input of the Adder. The Carry In is also set to 1 when Add/Subtract is set to 1.

An 8-bit Adder/Subtracter Unit

Two 4-bit 74LS283 chips can be cascaded together to form an 8-bit Parallel Adder Unit. Each of the two 74LS283 ICs is connected to the 1’s Complement circuitry that allows either the un-complemented form for addition or the complemented form for subtraction to be applied at the B inputs. The Add/Subtract function select input are tied together. The Carry In of the 1st 4-bit Adder circuit is connected to the Add/Subtract function select input. The Carry Out of the 1st 4-bit Adder circuit is connected to the Carry In of the 2nd 4-bit Adder circuit.

📌 Example: Adding 103 (binary 0110 0111) and 67 (binary 0100 0011) with Add/Subtract=0. The LSD adder sums 0111 + 0011 = 1010 with Cout=0. The MSD adder sums 0110 + 0100 = 1010 with Cout=0 and Cin=0. The final sum is 1010 1010 (decimal 170). 📌 Example: Subtracting 67 from 103 with Add/Subtract=1. The B inputs are complemented. The LSD adder (1’s complement of 0011 is 1100) sums 0111 + 1100 + 1 = 1 0100 with Cout=1. The MSD adder (1’s complement of 0100 is 1011) sums 0110 + 1011 + 1 = 1 0010 with Cout=1. The final result is 0010 0100 (decimal 36).

Arithmetic and Logic Unit (ALU)

Microprocessors have Arithmetic and Logic Units, a combinational circuit that can perform any of the arithmetic operations and logic operations on two input values. The operation to be performed is selected by set of inputs known as function select inputs. Three commercially available 4-bit ALUs are:

• 74XX181: Has five function select inputs allowing 32 different Arithmetic and Logic operations.
• 74XX381: Has three function select inputs allowing only 8 different arithmetic and logic functions.
• 74XX382: Similar to the 74XX381, but provides ripple carry and overflow outputs instead of group-carry look-ahead outputs.

🔑 Definition — ALU: A combinational circuit that performs multiple arithmetic and logic operations on two input values based on function select inputs.

Implementing 16-bit ALU

A 16-bit ALU can be implemented by cascading together four 4-bit ALUs. These 4-bit ALUs have built in Look-Ahead Carry Generator circuits that eliminate the delay caused by carry bit propagating through the Parallel Adder circuit within the 4-bit ALU circuit. However, when a number of such units are cascaded together to implement large 16-bit and 32-bit ALU, the carry propagating between one unit to the next gets delayed due to the Carry rippling through multiple 4-bit units.

Group-Carry Look-Ahead

The Look-Ahead Carry Generator provides Carries C₁, C₂, C₃, and C₄ simultaneously after a gate delay of two. These terms are generated on the basis of P₀, P₁, P₂, and P₃ (the four Carry Propagate terms) and G₀, G₁, G₂, and G₃ (the four Carry Generate terms). These terms are used to generate Group-Carry Look-Ahead outputs that can be used to cascade together multiple units eliminating the problem of rippling carry. The G and P output pins of the 74XX381 provide the group-carry look-ahead outputs.

📐 Formula: Group-Carry Look-Ahead Outputs: G = G₃ + P₃G₂ + P₂P₃G₁ + P₁P₂P₃G₀ and P = P₀P₁P₂P₃ 💡 Why this matters: This allows multiple ALU chips to be cascaded for wider bit operations without the propagation delay of a ripple carry.

⭐ Key Takeaways

For BCD addition, the sum of two digits is invalid if it exceeds 9 or generates a carry, requiring a correction by adding 6 (binary 0110), which is implemented by an invalid BCD detector and a second adder. Subtraction in digital logic is achieved by taking the 2's complement of the subtrahend and adding it to the minuend, making an adder capable of both operations with a selectable complementing circuit. An Adder/Subtracter unit uses the Add/Subtract control line to select between un-complemented (addition) and complemented (subtraction) B inputs, while also setting the carry-in accordingly. An ALU is a universal combinational circuit that can perform multiple arithmetic and logic operations, with different MSI chips like the 74XX381 offering various function sets. Group-carry look-ahead is essential for cascading multiple ALUs to build wider units without performance degradation from ripple carry delays.

🧠 Quick Revision Questions

1. What are the two conditions that make a sum of two BCD digits invalid, and what correction is applied?
2. Derive the Boolean expression for the invalid BCD detector circuit from the Karnaugh map.
3. Explain how a single 4-bit adder can be used as an adder/subtracter unit, detailing the role of the Add/Subtract control and the complemented B inputs.
4. Why is group-carry look-ahead output (G and P) necessary when cascading multiple 4-bit ALUs to form a 16-bit or 32-bit unit?
5. Perform BCD addition for 55 and 59, showing the results of both the first and second adder stages for each digit.

📘 Lecture 16 — 16-BIT ALU

📖 Overview: This lecture covers the construction of a 16-bit ALU from four 4-bit ALU units using look-ahead carry generation to eliminate propagation delays. It also introduces comparators, including iterative circuit-based comparators and MSI comparators, and concludes with decoders, their applications, and the binary decoder circuit.

🗂️ Topics Covered

The lecture begins by explaining the carry propagation delay in cascaded 4-bit ALUs and how it is eliminated using group carry generate and propagate terms with a look-ahead carry generator. It then introduces comparator circuits, including their basic function, Boolean expressions for 2-bit comparators, cascading comparators, and iterative circuit-based comparators. Finally, it covers decoders, their applications in computer systems, the binary decoder, and the MSI 74LS139 decoder.

📝 Lecture Summary

16-BIT ALU

Consider four ALUs connected to form a 16-bit ALU without the Look-Ahead Carry circuit. The ALU1 will only generate an output and a Carry Out 8 when it has received an input at Carry In 4. Similarly, ALU2 will only generate an output and a Carry Out 12 when it has received Carry In 8. Finally, the Carry Out 16 is generated only when ALU3 has received Carry In 12. Thus, the Carry, instead of rippling through the 4-bits of the individual ALU circuit, has to propagate through four ALU units. The last ALU unit has to wait until it receives the Carry propagating through each of the three units.

The delay caused by the Carry propagating through the four units is eliminated by the Group Carry terms used by the 381 ALUs. Instead of the Carry Out, each ALU generates Group-Carry Generate and Propagate terms, which indicate if the most significant Carry is generated by the 4-bit ALU or otherwise. The Group Carry terms are connected to the Look-Ahead Carry Generator which generates the Carry bits C1, C2 and C3 which are connected to Cin4, Cin8 and Cin12 respectively. Thus, Carry no longer propagates through the ALU units.

The G output is activated if the 4-bit unit generates a Carry Out irrespective of Carry In. The P output is activated if the 4-bit unit generates a Carry Out if the Carry In is active. The Look-Ahead circuit implemented earlier is based on Logic Gates, where the Look-Ahead Carry Generator circuit has P0, P1, P2, and P3 Carry Propagate and G0, G1, G2, and G3 Carry Generate Inputs and C1, C2, C3, and C4 Carry Out outputs. The 74XX182 is the MSI version of the Look-Ahead Carry Generator, which provides identical inputs and outputs except for the C4 output which is available in the form of P and G output pins to allow a second level Cascading. The connection of four 74XX381 4-bit ALUs and a 74XX182 to implement a 16-bit ALU is shown. The inputs A, B and the output F of the four 4-bit ALUs 0, 1, 2 and 3 are connected to appropriate bits of the 16-bit inputs A, B and output F respectively. The Group-Carry Generate and Propagate outputs of the four ALUs are connected to the inputs of Look-Ahead Carry generator 74X182 respectively. The Carry outputs C1, C2 and C3 from the Look-Ahead Carry generator circuit are generated after a gate delay of 2 and are connected to the Carry in pins of ALUS 1, 2 and 3 respectively.

Comparators

The basic function of a Comparator is to compare two binary quantities and to determine if the two quantities are equal. If the quantities are not equal, then it has to determine which of the two quantities is greater than the other. Many Integrated Circuit Comparators have three outputs to indicate A=B, A>B and A<B.

🔑 Definition — Comparator: A digital circuit that compares two binary numbers and indicates their relationship (equal, greater than, or less than).

Earlier, simplified Boolean expressions for a 2-bit Comparator circuit were determined that compares two 2-bit numbers and sets one of its three outputs to indicate A=B, A>B or A<B. 📐 Formula (A>B): (A > B) = A1B1' + A0B1'B0' + A1A0'B0' 📐 Formula (A=B): (A = B) = A1'A0'B1'B0' + A1'A0B1'B0 + A1A0'B1B0' + A1A0B1B0 📐 Formula (A<B): (A < B) = A1'B1 + A1'A0'B0 + A0'B1B0

The 2-bit Comparator discussed earlier is considered to be a Parallel Comparator as all the bits are compared simultaneously. External Logic has to be used to Cascade together two such Comparators to form a 4-bit Comparator. The two most significant bits of 4-bit numbers A and B are compared by the Most Significant 2-bit Comparator M and the least significant two bits are compared by the Least Significant 2-bit Comparator L. If the two most significant bits of number A are greater than the two most significant bits of number B, the Most Significant Comparator indicates A>B and there is no need to compare the remaining two least significant bits. However, if the two most significant bits of numbers A and B indicates A=B then least significant two bits have to be compared. Thus the A=B output of the Most Significant 2-bit Comparator is used to enable three AND gates. An alternate method of implementing Comparators which allows the Comparators to be easily cascaded without the need for extra logic gates by Iterative Circuit based Comparators.

Iterative Circuit based Comparator

An Iterative circuit is implemented using identical modules each of which has Primary Inputs and Outputs and Cascading Inputs and Outputs. The Cascading inputs of the least significant module are connected to fixed logic inputs and the Cascading outputs are connected to the Cascading inputs of the next significant module. In the Iterative Circuit for A=B, the Cascading input of Module 0 is connected to logic 1. If input A0 is equal to input B0, the XNOR gate output in Module 0 is a 1 which is passed on to Module 1 through its Cascading input. The output A=B is 1 when input A1 is equal to B1. In the Iterative Circuit for A>B, the Cascading input of Module 0 is connected to Logic 0. The output of Module 0 is 1 when A0>B0. The Cascading output of Module 0 is connected to the Cascading input of Module 1. The output A>B of Module 1 is 1 if A1=B1 and Cascading input is 1, or if A1>B1. Similar Iterative Circuit for A<B allows multiple modules to be cascaded together to form multi-bit A<B unit.

MSI 74HC85 4-bit Iterative Circuit based Comparator allows multiple 74HC85s to be cascaded together to form Comparators N x 4-bit Comparators. Three Comparators are cascaded together: Comparator 1 compares the least significant bits 0 to 3, Comparator 2 compares bits 4 to 7 and Comparator 3 compares the most significant bits 8 to 11. The Cascading inputs of Comparator 1 are permanently connected to Ground and +5 volts: A<B in and A>B in are connected to ground and A=B in is connected to +5 Volts. The cascading outputs of Comparator 1 are connected to the respective cascading inputs of comparator 2, and so on. The final output of the 12-bit Comparator circuit is available at the cascading outputs of Comparator 3.

Decoders

A Decoder has multiple inputs and multiple outputs. The Decoder device accepts as an input a multi-bit code and activates one or more of its outputs to indicate the presence of the multi-bit code.

🔑 Definition — Decoder: A combinational circuit that converts binary information from n input lines to a maximum of 2^n unique output lines.

Basic Decoder: Consider an electronic door lock which unlocks the door when a 4-bit code 1011 is entered. The door is locked when another 4-bit combination 1001 is entered. The lock and unlock circuit is implemented using a combination of NOT and AND gates. The circuit is configured to activate the Lock output when the Door Lock code 1011 is applied at inputs ABCD. The Un-Lock output is activated when the Door Un-Lock code 1001 is applied. The decoder circuit can be expanded to have more Lock and Un-Lock outputs to Lock and Un-Lock different doors in a building.

Applications of decoders:

1. Selection of Peripheral Devices: Computers have different internal and external devices. Each of these different devices is selected by specifying different codes. A decoder is used to uniquely select or deselect the appropriate devices.
2. Instruction Decoder: Computer programs are based on instructions which are decoded by the Computer Hardware and implemented. Instruction codes are decoded by an Instruction Decoder to generate signals that control different logic circuits like the ALU and memory.

Binary Decoder: The simplest and most commonly used Decoders are the n-to-2^n Decoders. These Decoders have n inputs and 2^n outputs. Each n-bit input selects 1 out of 2^n output code. A 2-to-4 Decoder output O0 is activated to Logic 1 when the input is 00. Similarly for inputs 01, 10 and 11 the outputs O1, O2 and O3 are respectively activated.

MSI Decoder: The 74LS139 MSI chip has dual 2-to-4 Decoders. The 74LS139 has active-low outputs, thus the output which is activated is at logic 0 whereas the outputs that are not selected are at logic 1. A third active-low input G is the enable input, which when set to 0 enables all NAND gates. Setting the G input to 1 disables all NAND gates and all four outputs are at logic 1 (the in-active state). Extra NOT gates are placed at the inputs A and B. By having the extra NOT gates each input presents a single unit load.

⭐ Key Takeaways

The most critical concept is the use of group carry generate (G) and propagate (P) terms to eliminate carry propagation delays in multi-bit ALUs, allowing all ALU units to operate in parallel. Comparators can be built using either parallel comparison or iterative circuits, with iterative circuits allowing easy cascading without additional logic gates. The 74HC85 MSI comparator enables simple expansion to any N x 4-bit comparison by cascading chips with fixed logic on the least significant chip's cascading inputs. Decoders are fundamental for selecting peripheral devices and decoding instructions in computer systems, with n-to-2^n decoders being the most common form. The 74LS139 decoder uses active-low outputs and an enable input, with extra NOT gates to reduce input loading.

🧠 Quick Revision Questions

1. How does the group carry generate (G) and propagate (P) output of a 74XX381 ALU eliminate carry propagation delay when constructing a 16-bit ALU?
2. What are the three Boolean expressions for a 2-bit comparator's outputs (A>B, A=B, A<B)?
3. Why must the cascading inputs of the least significant comparator in an iterative circuit be connected to fixed logic values (e.g., A<B and A>B to ground, A=B to Vcc)?
4. What is the function of the enable input (G) in the 74LS139 2-to-4 decoder, and what does it mean for the outputs to be active-low?
5. In a 12-bit comparator built from three 74HC85s, which comparator's outputs provide the final comparison result?

📘 Lecture 17 — THE 74XX138 3-TO-8 DECODER

📖 Overview: This lecture covers the 74XX138 3-to-8 Decoder, its internal structure, enable inputs, and function table. It then explores how decoders can implement standard SOP and POS Boolean expressions, describes BCD-to-7-Segment and BCD-to-Decimal decoders, and introduces encoders—including binary and priority encoders—along with multiplexers.

🗂️ Topics Covered

The lecture begins with the 74XX138 3-to-8 Decoder, its function table and enable inputs, and how to cascade them to form larger decoders like 4-to-16. It then shows how to implement POS and SOP Boolean expressions using decoders with AND and NAND gates. Next, it covers BCD-to-7-Segment Decoders, including MSI 74LS47 with lamp test and blanking functions, and BCD-to-Decimal Decoder 74LS42. The second half introduces encoders, starting with binary 8-to-3 encoders and their drawback, then priority encoders and their cascading, followed by decimal-to-BCD encoder for keypads. Finally, multiplexers are explained, including the 4-to-1 and dual 4-input Multiplexer (74XX153).

📝 Lecture Summary

THE 74XX138 3-TO-8 DECODER

The 3-to-8, 74XX138 Decoder is commonly used in logical circuits. Similar to the 2-to-4 Decoder, it has active-low outputs and three extra NOT gates at the three inputs to reduce the four unit load to a single unit load. The 3-to-8 Decoder has three enable inputs: one is active-high and the remaining two are active-low. All three enable inputs must be activated for the Decoder to work.

🔑 Definition — Active-low output: An output that is normally at logic HIGH and goes LOW when activated. 📐 Function Table: For 74LS138, when G1=1, G2A=0, G2B=0 (all enables active), the outputs Y0-Y7 correspond to the binary value of inputs C(MSB), B, A(LSB). For invalid enable conditions, all outputs are HIGH. 📌 Example: When C=0, B=0, A=0 and enables are active, Y0=0 and all other outputs Y1-Y7=1.

Implementing Standard SOP and POS Boolean expressions

The function table of 3-to-8 Decoder is a table of maxterms. For example, when A,B,C is 0,0,0 the Y0 output is activated indicating the sum term or maxterm A+B+C. When A,B,C is 1,0,1, the Y5 output activates indicating A+B+C. The POS Boolean expression represented by a 3-variable Karnaugh Map can be implemented by the 3-to-8 Decoder using an AND gate to implement the product of sum terms. The 3-to-8 Decoder can also implement SOP expression by connecting the outputs of the Decoder to the input of a NAND gate. The three bubbles cancel out the three bubbles connected at the outputs representing the three minterms or product terms.

💡 Why this matters: This shows how decoders serve as universal logic building blocks—any Boolean function can be implemented using a decoder plus a single gate.

🔑 Definition — Maxterm: A sum term (OR) that includes every variable in its true or complemented form; corresponds to rows of the truth table where the output is 0. 🔑 Definition — Minterm: A product term (AND) that includes every variable; corresponds to rows where the output is 1. 📐 Formula: For SOP: Output = Σ(minterms) → Connect decoder outputs to NAND gate. For POS: Output = Π(maxterms) → Connect decoder outputs to AND gate. 📌 Example: Karnaugh Map for Π(0,1,3,5,7) is implemented using 3-to-8 Decoder with AND gate connected to Y0, Y1, Y3, Y5, Y7 outputs. For Σ(2,4,6), connect Y2, Y4, Y6 to NAND gate.

BCD to 7-Segment Decoder

BCD to 7-Segment Decoder is a specific type of decoder that converts a 4-bit BCD Code to a 7-Segment Code. Unlike Binary Decoders, it activates multiple but unique sets of outputs for each 4-bit BCD input combination. Each of the seven Boolean expressions for activating segments can be implemented using a combination of NOT-AND-OR gates. The implementations for segments a, b and g are shown.

📐 Formula: Segment a = A + C + BD + BD. Segment b = B + CD + CD. Segment g = A + BC + CD + BC. 📌 Example: For BCD input 0000 (decimal 0), segment a is activated (along with b, c, d, e, f but not g) to display "0".

MSI Seven-Segment Decoder

The 7-Segment Decoder circuit is available in MSI form as 74LS47. This IC has 4-bit BCD input ABCD and 7-bit active-low outputs for segments a through g. It also has three extra active-low inputs: LT (Lamp test), RBI (Ripple Blanking Input), and BI/RBO (Blanking Input/Ripple Blanking Output). When a LOW is applied to LT input and BI/RBO is HIGH, all seven segments turn on to test for burned-out segments. The Ripple Blanking Input and Blanking Input/Ripple Blanking Outputs are used to prevent display of leading and trailing zeros.

💡 Why this matters: These extra features (lamp test and blanking) are essential for practical digital displays where you need to test the display and suppress unnecessary leading zeros.

BCD-to-Decimal Decoder

The BCD-to-Decimal Decoder operates the same as a Binary 4-to-16 decoder, but has ten output pins instead of sixteen, and the input must be a valid BCD number (0000 to 1001). Invalid BCD codes (1010, 1011, 1100, 1101, 1110, 1111) do NOT activate any of the ten outputs. The commercially available MSI is the 74LS42, which has active-high inputs and active-low outputs.

Encoder

An Encoder performs the opposite operation of a Decoder. It accepts an active level at one of its inputs and generates a BCD or Binary output representing the selected input.

Binary Encoder

The simplest encoders are 2ⁿ-to-n encoders. For an 8-to-3 Binary Encoder, the I0 input is unconnected to any gate. If all inputs are inactive LOW, or I0 input is HIGH, the output is 000. The appropriate 3-bit output combination is activated for each input asserted HIGH. The Binary encoder has a drawback when more than one input is activated simultaneously—if I3 and I6 are both HIGH, the outputs become a combination (011 and 110), putting all three output pins at logic 1.

🔑 Definition — Binary Encoder: A circuit that converts an active input line into a binary code representing that line's position. 📌 Example: For 8-to-3 encoder, when I3=1 (and all others 0), output O2O1O0 = 011. When I6=1, output = 110. If both are 1 simultaneously, outputs conflict.

Priority Encoders

Priority Encoders solve the problem of multiple simultaneous inputs by having logic to activate outputs corresponding to the highest priority input. Boolean expressions for the three outputs O2, O1, O0 are derived using priority logic where I7 has highest priority and I0 has lowest.

🔑 Definition — Priority Encoder: An encoder that includes priority logic so that when multiple inputs are asserted, only the output corresponding to the highest-priority input is generated.

📐 Formula: O2 = I7 + I6 + I5 + I4 O1 = I7 + I6 + I5·I4·I3 + I5·I4·I2 O0 = I7 + I6·I5 + I6·I4·I3 + I6·I4·I2·I1

Cascading Priority Encoders

The 74XX148 Priority Encoder has active-low inputs and active-low outputs, plus an active-low enable input EI that enables/disables outputs. The Group Select GS active-low output is asserted when any input is asserted. The Enable output EO signal cascades multiple Encoders for larger configurations—EO connects to the EI input of the Encoder handling lower priority inputs. Two 8-input Priority Encoders can form a 16-input Priority Encoder.

💡 Why this matters: Cascading allows building priority encoders for more inputs (e.g., 16, 32, 64) using standard MSI chips.

Decimal-to-BCD Encoder

The Decimal-to-BCD Encoder has ten inputs (decimal digits 0-9) and four outputs for 4-bit BCD. The 74LS147 is a Decimal-to-BCD Priority Encoder with active-low inputs and outputs. It is used as a keypad encoder—a telephone keypad connects through pull-up resistors ensuring inputs are logic HIGH when no key is pressed. When a key is pressed, the encoder input connects to logic LOW and the BCD code is generated.

📌 Example: Pressing key "5" on a telephone keypad connects input I5 to LOW, and the encoder outputs the BCD code for 5 (0101).

Multiplexer

A Multiplexer (or Data Selector) is a digital switch with several inputs and a single output. It has select inputs that allow any one input to be connected to the output. In a computer, ALU combinational circuits use multiplexers to route contents from multiple registers to ALU inputs. For a 4-to-1 Multiplexer, when select inputs S1,S0 are 00, the top AND gate enables input I0 to reach output Z; when select is 10, the third gate enables I2.

🔑 Definition — Multiplexer: A combinational circuit that selects one of many inputs and routes it to a single output, controlled by select lines. 📐 Function Table: For 4-to-1 MUX: S1,S0=00 → Z=I0; 01→Z=I1; 10→Z=I2; 11→Z=I3. 📌 Example: In a CPU, register contents are routed to ALU through multiplexers to perform arithmetic on any two selected registers.

Dual 4-Input Multiplexer

The commercial 74XX153 IC has two 4-input multiplexers with common select inputs (A and B) but separate enable inputs (1G and 2G). Each multiplexer has active-high inputs (1C0-1C3 and 2C0-2C3) and active-high outputs (1Y and 2Y). Two extra NOT gates at select inputs reduce unit load from 5 to 1 each. Select lines enable one of four AND gates per multiplexer to route the corresponding input value through the OR gate to the output. The enable signals independently control each multiplexer's four AND gates.

⭐ Key Takeaways

The 74XX138 3-to-8 Decoder requires all three enable inputs (G1 HIGH, G2A and G2B LOW) to function, and its active-low outputs represent minterms/maxterms for implementing any Boolean function using a single AND or NAND gate. Priority encoders like the 74XX148 solve the problem of multiple simultaneous inputs by generating output for only the highest-priority input, and they can be cascaded using EO and EI pins to handle more inputs. Multiplexers serve as data selectors in systems like ALUs, with common select lines and independent enables, and the 74XX153 provides dual 4-input multiplexers in one package. BCD decoders (74LS42 and 74LS47) handle only valid BCD codes, with the 7-segment decoder featuring lamp test and blanking for practical displays. The Decimal-to-BCD Priority Encoder (74LS147) enables keypad encoding with active-low operation and pull-up resistors.

🧠 Quick Revision Questions

1. What are the three enable inputs of the 74LS138 3-to-8 Decoder, and what logic levels must each be at for the decoder to function?
2. How can a 3-to-8 Decoder be used to implement a POS Boolean expression given by Π(0,1,3,5,7)?
3. What is the difference between a Binary Encoder and a Priority Encoder in handling multiple simultaneous inputs?
4. Explain how two 8-input Priority Encoders (74XX148) can be cascaded to form a 16-input Priority Encoder, including the role of EI, EO, and GS pins.
5. For a 4-to-1 Multiplexer with select inputs S1=1, S0=0, which input (I0, I1, I2, or I3) is routed to the output Z?

📘 Lecture 18 — 2-INPUT 4-BIT MULTIPLEXER

📖 Overview: This lecture introduces the 2-input 4-bit multiplexer (74X157) and its functional operation. It then covers how to expand multiplexers to create larger configurations like 8-input, 16-input, and 2-input 8-bit multiplexers. Finally, it explores four key applications: data routing for 7-segment displays, parallel-to-serial conversion, logic function generation, and operation sequencing for industrial processes.

🗂️ Topics Covered

The lecture begins with the 2-input 4-bit multiplexer (74X157), its function table and circuit. It then explains how to expand multiplexers by connecting them to form 8-input, 16-input, and 2-input 8-bit multiplexers. The applications section covers data routing using a 2-digit 7-segment display circuit, parallel to serial conversion using an 8-to-1 multiplexer, logic function generation directly from a truth table, and operation sequencing for controlling manufacturing processes using a multiplexer and decoder.

📝 Lecture Summary

a) 2-INPUT 4-BIT MULTIPLEXER

The MSI 74X157 is a 2-input, 4-bit Multiplexer. It has two sets of 4-bit inputs (1A, 2A, 3A, 4A and 1B, 2B, 3B, 4B), a single select input (S), an active-low enable input (G), and 4-bit outputs (1Y, 2Y, 3Y, 4Y). When G is logic 1 (disabled), all outputs are 0. When G is logic 0 (enabled) and S is 0, the A inputs are routed to the Y outputs; when S is 1, the B inputs are routed. This enables four bits of data from two sources to be routed to the output.

🔑 Definition — Active-High Input/Output: An input or output where a logic 1 (high voltage) represents the active or TRUE state. In the 74X157, inputs 1A-4A and outputs 1Y-4Y are active-high.

📌 Example: If G=0, S=0, and inputs are 1A=1, 2A=0, 3A=1, 4A=0, then outputs will be 1Y=1, 2Y=0, 3Y=1, 4Y=0. If G=0, S=1, with 1B=0, 2B=1, 3B=0, 4B=1, then outputs become 1Y=0, 2Y=1, 3Y=0, 4Y=1.

Expanding Multiplexers

Multiple multiplexer ICs can be connected to form larger multiplexers for specific application requirements.

1. 8-Input Multiplexer A single dual 4-input multiplexer 74X153 can form an 8-input multiplexer. Two 4-input multiplexers (M1 and M2) are used. The two active-low enable inputs are connected together using a NOT gate to form the C (most significant) select input. Select inputs A and B are common. When C=0, M1 is enabled allowing its inputs 1C0-1C3 to be selected. When C=1, M2 is enabled. The two outputs are connected through an OR gate to produce the final output F.

🔑 Definition — 74X153: A dual 4-input multiplexer IC containing two independent 4-to-1 multiplexers with common select inputs but separate enable and output pins.

2. 16-Input Multiplexer Two 74X153 dual 4-input multiplexers can form a 16-input multiplexer. The select inputs A and B are common, selecting one of four inputs within each enabled multiplexer. The four active-low enable inputs are connected to the active-low outputs of a 2-to-4 decoder. The decoder inputs C and D enable one multiplexer at a time. All four outputs are connected through a 4-input OR gate. The G enable input of the decoder, when set to 1, disables the entire circuit.

🔑 Definition — 2-to-4 Decoder: A combinational circuit with 2 inputs and 4 outputs; for each input combination, exactly one output (active-low in this case) is asserted.

3. 2-Input, 8-bit Multiplexer Two 2-input, 4-bit multiplexers 74X157 can implement a 2-input, 8-bit multiplexer. The select inputs (S) of both multiplexers are tied together, so when S=0 both select the A inputs simultaneously, and when S=1 both select the B inputs. The active-low enable inputs (G) are also tied together, enabling or disabling both multiplexers simultaneously. The outputs combine to form an 8-bit output (1Y-4Y from the first IC, and 5Y-8Y from the second).

💡 Why this matters: Expanding multiplexers allows designers to create data selection circuits of any size using standard, off-the-shelf ICs, enabling flexible digital system design without custom chips.

Applications of Multiplexers

Multiplexers have a wide variety of applications, primarily for routing data from multiple sources to a single destination.

1. Data Routing A 2-digit 7-Segment Display can be implemented using a single BCD to 7-Segment Decoder and a multiplexer, instead of using two decoders. The BCD numbers for both digits are applied to inputs A and B of the multiplexer. The 4-bit multiplexer output feeds the BCD to 7-Segment Decoder, whose outputs connect to both Common Cathode displays. The MSD/LSD signal is connected to the select input of the multiplexer and, through a NOT gate, to the Common Cathode of the LSD.

🔑 Definition — Common Anode Display: All LED anodes are connected together; a segment lights when its cathode is connected to ground (0V). 🔑 Definition — Common Cathode Display: All LED cathodes are connected together; a segment lights when its anode is connected to +5V.

📌 Example: To display "29", BCD 0010 (MSD=2) is at Input A and BCD 1001 (LSD=9) is at Input B. When MSD/LSD=0, the multiplexer selects Input A, routes 0010 to the decoder, which drives both displays, but only the MSD display is enabled (its common cathode is at 0V). When MSD/LSD=1, Input B is selected, and the LSD display is enabled. By rapidly switching MSD/LSD between 0 and 1, both digits appear simultaneously due to persistence of vision.

2. Parallel to Serial Conversion Digital systems typically use parallel data (multiple bits simultaneously). For remote transmission, serial data (a sequence of single bits) is preferred because it requires only one wire instead of eight. An 8-to-1 multiplexer (74X151) converts 8-bit parallel data to serial form. The 8-bit data is applied to inputs I₀-I₇. A 3-bit counter (counting 0 to 7) drives the select inputs S₀, S₁, S₂. A clock pulses the counter every 1 millisecond. Initially, the counter is 000, selecting I₀. After 1ms, the counter becomes 001, selecting I₁, and so on. After 8ms, all 8 bits have been output serially.

🔑 Definition — Parallel Data: Multiple bits transmitted simultaneously on multiple wires (e.g., 8-bit byte on 8 wires). 🔑 Definition — Serial Data: Single bits transmitted sequentially on one wire.

💡 Why this matters: Serial transmission dramatically reduces wiring cost in long-distance communication systems (e.g., telephone lines, internet cables).

3. Logic Function Generator A multiplexer can implement any logic function directly from its truth table without simplification. The select inputs of the multiplexer become the function variables. The data inputs are connected to logic 1 or 0 to represent the function output for each input combination.

📌 Example: For a 3-variable function with truth table rows (ABC: 000→1, 001→1, 010→1, 011→0, 100→0, 101→1, 110→0, 111→1), an 8-to-1 multiplexer is used. Input I₀ (for 000) connects to 1, I₁ (001)→1, I₂ (010)→1, I₃ (011)→0, I₄ (100)→0, I₅ (101)→1, I₆ (110)→0, I₇ (111)→1. The select inputs A, B, C directly correspond to function inputs.

4. Operation Sequencing Many industrial processes require sequential operation where each step must complete before the next begins. A multiplexer and decoder control the sequence. A 2-bit counter (initially 00) drives both the multiplexer select inputs and the decoder inputs. The decoder output Y₀ activates Process 1. When Process 1 completes, it outputs logic 1, which is routed by the multiplexer (input I₀ selected) to the counter's clock input, incrementing it to 01. This selects I₁ and activates Y₁ to start Process 2. This continues through Process 4, after which the entire manufacturing process ends.

🔑 Definition — Operation Sequencing: A control method where each step of a process must complete before the next step is initiated, with completion signals from each step driving the sequence forward.

⭐ Key Takeaways

The 2-input 4-bit multiplexer (74X157) is a fundamental building block that selects between two 4-bit data sources. Multiplexers can be expanded to any size by cascading smaller multiplexers with decoders and OR gates, enabling 8-input, 16-input, and wider data path configurations. The four key applications are: data routing (e.g., reducing component count in 7-segment displays), parallel-to-serial conversion (essential for cost-effective long-distance data transmission), logic function generation (implementing any truth table without minimization), and operation sequencing (controlling multi-step industrial processes with completion-driven progression). The most critical concept is that the select inputs determine which data input is routed to the output, and by using counters, decoders, and feedback, multiplexers become versatile controllers in digital systems.

🧠 Quick Revision Questions

1. What are the functions of the G (enable) and S (select) inputs in the 74X157 2-input 4-bit multiplexer?
2. Explain how two 4-input multiplexers and a NOT gate can form an 8-input multiplexer. What is the role of the NOT gate?
3. In the 2-digit 7-segment display using a multiplexer, why does the MSD/LSD signal need to rapidly switch between 0 and 1?
4. Describe the steps involved in converting 8-bit parallel data to serial data using an 8-to-1 multiplexer and a 3-bit counter.
5. In the operation sequencing application, how does the completion signal from one process cause the next process to start?

📘 Lecture 19 — Demultiplexer

📖 Overview: This lecture introduces the Demultiplexer, a circuit that routes a single input to one of several outputs, and explores its applications such as ALU data routing and serial-to-parallel conversion. It then transitions into Programmable Logic Devices (PLDs), explaining their architecture based on programmable AND and OR arrays, and detailing the four main types: PROM, PLA, PAL, and GAL, including their programming and output configurations.

🗂️ Topics Covered

The lecture begins with the definition, circuit, and operation of a 1-to-4 Demultiplexer, comparing it to a decoder. It then covers two key applications: connecting an ALU output to registers and converting serial data to parallel. The second half introduces Programmable Logic Devices, their grid-based array structure with fusible links, and classifies them into PROM, PLA, PAL, and GAL. Finally, it details PAL circuit simplification, output types (combinational, I/O, programmable polarity), identification numbering, and provides a complete example of programming a 4 x 3 PLA device.

📝 Lecture Summary

Demultiplexer

A Demultiplexer (also called a Data Distributor) performs the opposite function of a Multiplexer. It has a single input and several outputs. The Demultiplexer selects one of the several outputs and routes the data at the single input to the selected output.

The circuit of a 1-to-4 Demultiplexer is very similar to a 2-to-4 Binary Decoder. The only difference is that the Decoder's enable input is used as the Demultiplexer's Data Input. With select inputs I₁ and I₀ set to 1 and 0, the O₂ output equals the Data input (1 if Data=1, 0 if Data=0). A Demultiplexer is not available as a standalone chip commercially; it is available as a Decoder/Demultiplexer chip that can be configured for either function.

Applications of Demultiplexer

First Application: ALU Output Routing The Demultiplexer is used to connect a single source to multiple destinations. At the output of an ALU circuit, the result must be stored in one of several registers. The Data input of the Demultiplexer is connected to the ALU output, and each Demultiplexer output is connected to a different register. By selecting the appropriate output, data from the ALU is routed to the correct register for storage.

Second Application: Serial to Parallel Converter The Demultiplexer reconstructs parallel data from an incoming serial data stream. Serial data arrives at the Data input at fixed time intervals. A counter attached to the Select inputs routes each incoming serial bit to successive outputs, where each bit is stored. When all bits have been stored, the data can be read out in parallel.

Programmable Logic Devices

Programmable Logic Devices (PLDs) are used to replace Logic gates and MSI chips, saving circuit space and reducing component cost. PLDs consist of arrays of AND gates and OR gates that can be programmed to perform specific functions.

Programmable Arrays of AND Gates and OR Gates

The array is a grid of conductors forming rows and columns, with a fuse connecting each column conductor to each row conductor. Fuses can be blown to disconnect a column from a row. Each column conductor represents a single variable or its complement. Each OR and AND gate is connected to each variable through horizontal conductors. When all fuses are intact, all variables are present at all gate inputs. Gates are configured by blowing away fuses.

An alternate implementation uses no fuses; instead, a specific column conductor is connected to a row conductor by shorting them. Both methods (blowing fuses or shorting) can only be done once, so the array cannot be reprogrammed.

PLDs are classified by their architecture, which determines whether one or both arrays are programmable:

1. Programmable Read-Only Memory (PROM): Has a fixed (non-programmable) AND array configured as a decoder and a programmable OR array. Used as a storage device, not as a logic device.
2. Programmable Logic Array (PLA): Has a programmable AND array and a programmable OR array. Also known as a Field-Programmable Logic Array (programmed by the user).
3. Programmable Array Logic (PAL): Has a programmable AND array and a fixed OR array. Designed to overcome longer delays and complex circuitry of the PLA.
4. Generic Array Logic (GAL): Has a reprogrammable AND array and a fixed OR array with programmable output logic. Uses E²CMOS technology (Electrically Erasable CMOS) instead of bipolar technology and fusible links.

All four PLD types use AND arrays followed by OR arrays, allowing implementation of Sum-of-Product (SOP) Boolean expressions.

PAL Circuit and Programming

A simplified PAL structure shows the AND array programmed to generate three product terms, which are added by the OR array. Because PALs have many inputs and outputs, circuit diagrams are simplified: input buffers produce the variable and its complement, multiple input lines to an AND gate are represented by a single line with a slash indicating the number of inputs, and crosses indicate fuses that are intact (connections).

PAL Outputs

PALs typically have 8 or more inputs and 8 or fewer outputs. Some have combined inputs and outputs programmable as either. The three output types are:

• Combinational Output: Used for an SOP function, available as active-high or active-low. Implemented by activating a tri-state buffer which inverts the OR gate output and passes it to the PAL output.
• Combinational Input/Output: Used when the output connects back to the PAL input or when the pin is used as an input. The tri-state buffer output connects to inverting and non-inverting buffers to feed the AND array. Deactivating the tri-state buffer configures the pin as an input.
• Programmable Polarity Output: Uses an XOR gate at the output. When the XOR's second input is grounded (fuse intact), output equals OR gate output. When the fuse is blown to set the input to logic high, the XOR inverts the OR gate output.

PAL Identification

PALs are identified by a unique number: prefix PAL, followed by two digits for the number of inputs, a letter (L for active-low, H for active-high, P for programmable polarity), and one or two digits for the number of outputs. Suffixes specify speed, package type, and temperature range. 🔑 Definition — PAL 10L8: A PAL with 10 inputs, 8 outputs, and active-low outputs.

PLA Circuit and Programming

A PLA has programmable AND and OR arrays and can implement any SOP expression, limited by:

• Number of inputs (n)
• Number of outputs (m)
• Number of product terms (p) Such a device is described as an n x m PLA device with p product terms.

📐 Formula: For a 4 x 3 PLA with 6 AND gates (product terms P1-P6) and 3 OR gates:

• Each AND gate has 8 inputs (4 variables and their complements).
• Each OR gate has 6 inputs (summing up to 6 product terms).

📌 Example: A programmed 4 x 3 PLA generates the following product terms: P₁ = I₁·I₂·I₄ P₂ = I₁·I₂·I₃ P₃ = I₁·I₂·I₃·I₄ P₄ = I₁·I₃·I₄ P₅ = I₂·I₄ P₆ = I₁·I₂·I₃·I₄

The three output sum-of-product expressions are: O₁ = P₁ + P₂ + P₃ + P₅ = I₁·I₂·I₄ + I₁·I₂·I₃ + I₁·I₂·I₃·I₄ + I₂·I₄ O₂ = P₂ + P₄ + P₆ = I₁·I₂·I₃ + I₁·I₃·I₄ + I₁·I₂·I₃·I₄ O₃ = P₁ + P₃ + P₄ + P₆ = I₁·I₂·I₄ + I₁·I₂·I₃·I₄ + I₁·I₃·I₄ + I₁·I₂·I₃·I₄

⭐ Key Takeaways

The Demultiplexer is a data distributor that routes one input to one of several outputs, functioning like a decoder with the enable line replaced by a data input. Its key applications include routing ALU outputs to registers and converting serial data to parallel data. Programmable Logic Devices (PLDs) use programmable arrays of AND and OR gates to implement Sum-of-Product logic, with four main types: PROM (fixed AND, programmable OR), PLA (both programmable), PAL (programmable AND, fixed OR), and GAL (reprogrammable AND, fixed OR with programmable output). PAL outputs can be configured as combinational, input/output, or programmable polarity. The size of a PLD is described by its number of inputs, outputs, and product terms, and PALs are identified by a standard numbering system (e.g., PAL10L8).

🧠 Quick Revision Questions

1. How does a 1-to-4 Demultiplexer circuit differ from a 2-to-4 Decoder circuit?
2. Describe how a Demultiplexer can be used as a serial-to-parallel converter. What component controls the select inputs?
3. What are the four main types of Programmable Logic Devices, and how do their AND/OR array configurations differ?
4. In a PAL, what are the three types of output configurations, and how does a programmable polarity output using an XOR gate work?
5. For a programmed 4 x 3 PLA, if the product terms are P₁=I₁·I₂, P₂=I₂·I₃, and P₃=I₁·I₃, and O₁ sums P₁+P₂, O₂ sums P₂+P₃, and O₃ sums P₁+P₃, what are the three Boolean output expressions?

📘 Lecture 20 — Implementing Constant 0s and 1s

📖 Overview: This lecture explores how Programmable Logic Arrays (PLAs) can be programmed to produce constant 0 or 1 outputs, and how they implement functions like Odd-Prime Number detection. It then introduces GAL (Generic Array Logic) architecture, its reprogrammable AND array, Output Logic Macro Cells (OLMCs), and programming methods including the GAL22V10 and the ABEL hardware description language.

🗂️ Topics Covered

The lecture covers implementing constant 0s and 1s using PLAs, implementing the Odd-Prime Number function in a 4×3 PLA, GAL operation including E²CMOS reprogrammable cells and OLMCs, the GAL22V10 architecture with its ten OLMCs and various configurations, tri-state buffers and their use, programming GAL22V10 for Boolean functions, and an introduction to ABEL (Advanced Boolean Expression Language) for PLD programming.

📝 Lecture Summary

IMPLEMENTING CONSTANT 0S AND 1S

The PLA can output constant 0 or 1. When all four inputs and their complements are connected to the first AND gate, the product term generated is 0 (P1 = 0). This is connected to the first OR gate, giving an output of 0. When inputs to the second AND gate are disconnected, the product term is 1 (P2 = 1), connected to the second OR gate, giving output 1. When no product term is connected to the third OR gate, its output is 0.

🔑 Definition — Constant 0/1 in PLA: Connecting all literals to an AND gate produces product term 0; disconnecting all inputs produces product term 1. 📐 Formula: P = 0 (all inputs connected) → P = 1 (all inputs disconnected) 📌 Example: In a 4×3 PLA, first AND gate with all four inputs connected gives P1 = 0 → OR1 output = 0; second AND gate with no inputs gives P2 = 1 → OR2 output = 1; third OR gate with no product terms gives output = 0.

Implementing Odd-Prime Number Function

The Odd-Prime Number generator is implemented in a 4×3 PLA with six product terms (six AND gates). Due to limitations, only the first six Odd-Prime numbers 1, 3, 5, 7, 11, and 13 can be detected. The six product terms P1–P6 represent minterms 1, 3, 5, 7, 11, and 13. The first OR gate sums all six minterms to output 1 when any of these Odd-Prime numbers appears at inputs I1–I4. The second OR gate sums minterms 1, 3, and 5. The third OR gate sums minterms 1, 3, and 13.

GAL Operation

GAL has a reprogrammable AND gate array and a fixed OR array. Instead of fuses, E²CMOS logic is used, which can be programmed to connect a column with a row. The E²CMOS cell at each column–row intersection is known as a cell. A cell in the ‘on’ state connects the column with the row; a cell in the ‘off’ state disconnects them.

A typical GAL has eight or more inputs to the reprogrammable AND array and eight or more input/outputs from its Output Logic Macro Cells (OLMCs). OLMCs can be programmed for Combinational Logic (for combinational circuits) or Registered Logic (for sequential circuits).

GALs are identified by a prefix GAL followed by a 2-digit number indicating inputs, then V for variable output configuration, followed by a number indicating the number of outputs. Example: GAL16V8 means 16 inputs, 8 outputs, variable configuration.

Programming of PLDs

PLDs are programmed with a computer running programming software, connected to a programmer socket. PLDs can also be programmed when installed on a circuit board (In-System Programming or ISP). The process involves entering the logic function as a Boolean equation, truth table, or state diagram. The software compiler processes and minimizes the logic, then tests it using test vectors (hypothetical inputs). After testing, a fuse map file is produced and downloaded to the programmer. ISP uses a standard 4-wire interface, allowing systems to be upgraded by reprogramming.

The GAL22V10

The GAL22V10 has twelve inputs and ten inputs/outputs, available as a low-voltage 3.3V version and an ISP version. It has ten OLMCs that receive different numbers of inputs from the programmable AND array: two OLMCs have 8 inputs, two have 10 inputs, two have 12 inputs, two have 14 inputs, and two have 16 inputs. Each OLMC can be programmed for active-high or active-low output, or as an input.

An OLMC contains a flip-flop (a sequential logic device storing the OR gate output). The output and complemented output of the flip-flop connect to two inputs of a 4-to-1 MUX. The remaining two MUX inputs come from the OR gate output and its complement. The MUX output drives a tri-state buffer. The output also connects to a 2-to-1 MUX, with the other input from the flip-flop’s complemented output. Select inputs S₀ and S₁ select appropriate routing.

The four OLMC configurations are:

• Combinational Mode with active-low output
• Combinational Mode with active-high output
• Registered Mode with active-low output
• Registered Mode with active-high output

OLMC Combinational Mode

When S₀ = 0 and S₁ = 1, the 4-to-1 MUX selects the OR gate output; the output is active-low due to inversion by the tri-state buffer. When S₀ = 1 and S₁ = 1, the MUX selects the complement of the OR gate output; the output is active-high due to double inversion.

Tri-State Buffers

A Tri-State Buffer is a NOT gate with a control line that disconnects the output from the input. When the control line is high, the buffer operates like a NOT gate. When the control line is low, the output is disconnected and high impedance is seen at the output. Tri-state buffers disconnect outputs of devices sharing a common output line.

Referring to the OLMC logic circuit: when the control input to the tri-state buffer is low, the output is set to high impedance, disconnecting the OLMC from the output pin, allowing the output pin to be used as an input pin.

The GAL22V10 Array

The GAL22V10 has 22 inputs organized as 44 lines (one for each input and its complement). Each AND gate has 44 inputs connected to these 44 input lines. The first OLMC has ten input product terms: eight connected to the OR gate, one to control the tri-state buffer, and one for reset in Registered mode for all OLMCs. Each OLMC ORs the product terms to give a single sum of product term. With ten OLMCs, a total of ten Sum-of-Product terms can be implemented.

Programming the GAL22V10

The GAL22V10 can be programmed for Boolean functions. For a six-variable function X = ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF, the six variables connect to six inputs. The first group of four vertical lines represents variable A and its complement; the remaining two lines receive un-complemented and complemented output from the OLMC. The Boolean expression has seven product terms. The first OLMC has eight input product terms, so it can program the expression. The output of the first AND gate generates the first product term, and the 2nd–7th AND gates generate the remaining six. The eight-input OR gate generates the sum of product terms. The last group of vertical lines controls the tri-state buffer; it is set high to connect the OLMC output to the GAL output pin.

💡 Why this matters: Understanding how to program GALs with specific Boolean functions enables efficient implementation of complex logic in a single chip.

Introduction to ABEL

ABEL (Advanced Boolean Expression Language) is a hardware description language used for implementing logic designs using PLDs. ABEL is a device-independent language that can program any type of PLD. ABEL runs on a computer connected to a PLD programmer. ABEL provides three text-based methods for describing and entering a logic design:

• Boolean Equations
• Truth Tables
• State Diagrams

Boolean Equations and Truth Tables are used for Combinational Logic Circuits. State Diagrams are used specifically for Sequential Logic Circuits. Boolean Equations and Truth Tables can also be used for describing Sequential Logic Circuits.

⭐ Key Takeaways

The most critical points from this lecture are: PLAs can generate constant 0 or 1 outputs by connecting all inputs (P=0) or disconnecting all inputs (P=1). The GAL architecture uses reprogrammable E²CMOS cells in an AND array with fixed OR array, where OLMCs can be configured for combinational or registered logic with active-high or active-low outputs. The GAL22V10 has 22 inputs (44 lines), ten OLMCs, and can implement ten Sum-of-Product terms, with tri-state buffers controlled by dedicated product terms. ABEL provides Boolean equations, truth tables, and state diagrams for PLD programming, with device-independent capability.

🧠 Quick Revision Questions

1. How can a PLA be programmed to output a constant 1?
2. What are the six Odd-Prime numbers that can be detected by a 4×3 PLA with six product terms?
3. What is the difference between combinational mode and registered mode in an OLMC?
4. How does a tri-state buffer function, and what is its purpose in an OLMC?
5. What are the three text-based methods provided by ABEL for describing logic designs?

📘 Lecture 21 — The GAL16V8

📖 Overview: This lecture covers the architecture and programming modes of the GAL16V8, a programmable logic device that can emulate most PALs. It introduces the ABEL hardware description language for implementing logic designs using Boolean equations, truth tables, and test vectors. This is foundational for understanding how to program PLDs in both combinational and sequential logic applications.

🗂️ Topics Covered

The lecture first examines the GAL16V8 architecture including its eight inputs, eight input/output pins, and OLMC structure with tri-state buffer control and feedback possibilities. It then explains the three programming modes: Simple Mode (combinational output, feedback, dedicated input), Complex Mode (combinational output and input/output with programmable tri-state control), and Registered Mode (sequential logic). The second half introduces ABEL as a hardware description language, covering Boolean equation notation, truth table representation, test vectors, and the structure of ABEL input files including declarations, logic descriptions, and documentation outputs.

📝 Lecture Summary

The GAL16V8

The GAL16V8 is a programmable device with eight inputs, two special function input pins, and eight pins configurable as inputs or outputs. Its architecture is similar to a PAL and it can be programmed in three modes: Simple, Complex, and Registered. The Simple and Complex modes are for Combinational Logic, while the Registered mode is for Sequential Logic.

The GAL16V8 has eight OLMCs (Output Logic Macro Cells), each connected to eight product terms. Each product term uses a 32-bit input AND gate, where the 32 inputs come from 16 complemented/un-complemented inputs of the 8 input pins and 16 complemented/un-complemented inputs of the 8 input/output pins.

OLMC for GAL16V8

The OLMC of the GAL16V8 is similar to the GAL22V10 with enhancements. Key aspects include:

Tri-state Buffer and OLMC output pin: The tri-state buffer connecting the OLMC output to the output pin is controlled through four different sources:

1. Connected to Vcc — output is always enabled
2. Connected to GND — output disabled, pin configured as input
3. Connected to external pin (11) — controlled externally by Vcc or GND
4. Connected to output of one of the eight AND gates — controlled by a logical expression

The feedback from the OLMC to the AND Gate array input: The OLMC can provide feedback in three ways:

1. Feedback signal line to the output of the OLMC — allows Sequential Logic circuits
2. Feedback signal line to the output of the adjacent OLMC — also allows Sequential Logic
3. Feedback signal line to a flip-flop — allows synchronized Sequential circuits

The output of the Sum of Product term: The OR gate output connects to the output pin through the tri-state buffer, which also connects to the flip-flop output. Either input can be selected. The OR gate output can be programmed for output polarity by configuring the XOR gate connected at the OR gate output.

Simple Mode

In the Simple Mode, the OLMC is configured as dedicated active combinational output or as dedicated input (limited to six). Three combinations exist:

Combinational Output (Figure 21.1): The OLMC gives an output that is either active-low or active-high, determined by the XOR input. The tri-state buffer control pin is set to logic high by connecting it to Vcc. The Sum-of-Product term has eight product terms.

Combinational Output with feedback to AND array (Figure 21.2): Similar to above, but the output signal connects back to the AND array input through a buffer providing inverting and non-inverting outputs. This feedback capability is limited to six OLMCs. OLMCs connected to input/output pins 15 and 16 do not have the feedback path, so they cannot be programmed with this configuration.

Dedicated Input (Figure 21.3): The tri-state buffer is configured in high impedance state by setting the control pin to low (GND). The output pin connects to an input signal passed to the AND Array input in complemented and un-complemented form by the buffer.

Complex Mode

In the Complex Mode, the tri-state control is formed by a logical expression, leaving seven product terms for the sum-of-product expression. Two combinations exist:

Combinational Output (Figure 21.4): The tri-state buffer is enabled by connecting the control input to the output of one of the AND gates, so the buffer is controlled by programming a product term.

Combinational Input/Output (Figure 21.5): Also implemented by connecting the tri-state buffer control input to the AND gate output. Only OLMCs with the feedback path connecting the output to the AND gate array input can be used in this mode.

Introduction to ABEL

ABEL (Advanced Boolean Expression Language) is a hardware description language for implementing logic designs using PLDs. It is device-independent and can program any type of PLD. ABEL runs on a computer connected to a PLD programmer.

ABEL provides three text-based methods for describing logic designs:

1. Boolean Equations — for Combinational Logic circuits
2. Truth Tables — for Combinational Logic circuits
3. State Diagrams — specifically for Sequential Logic circuits

Boolean Equations and Truth Tables can also be used for Sequential Logic circuits.

Boolean Operations and Boolean Notations

ABEL uses special symbols for logic operations:

Table 21.1 ABEL Symbols for logic operations

The operators have precedence in the order: !, &, #, $

Table 21.2 Boolean and equivalent ABEL Notations

Boolean Equations: Any letter or combination of letters and numbers can identify variables. ABEL is case-sensitive (variable 'A' ≠ variable 'a'). All ABEL equations must end with ';'.

📐 Formula: Boolean expression F = AB + AC + BD → ABEL expression F = A & !B # A & C # !B & !D;

🔑 Definition — Case-sensitive: ABEL treats uppercase and lowercase letters as different variables.

Multiple Inputs and Outputs

Multiple input and output variables can be grouped as a set to simplify equations. For example, D0, D1, and D2 can be defined as: D = [D0, D1, D2];

For a 4-input 4-bit Multiplexer:

Table 21.3 Truth Table of 4-input 4-bit MUX

💡 Why this matters: Using sets dramatically reduces the amount of code needed to describe complex circuits.

The ABEL notation can be simplified by defining sets:

A = [A3, A2, A1, A0];
B = [B3, B2, B1, B0];
C = [C3, C2, C1, C0];
D = [D3, D2, D1, D0];
Y = [Y3, Y2, Y1, Y0];
S = [S1, S0];
Y = (S = = 0) & A # (S = = 1) & B # (S = = 2) & C # (S = = 3) & D;

The '= =' is a relational operator.

Truth Table

ABEL accepts logic designs described as Truth Tables. The format includes a header and entries:

TRUTH_TABLE ( [A, B, C, D] → [X1, X2])

XOR Gate example:

TRUTH_TABLE ( [A, B] → [X])
[0, 0] → [0];
[0, 1] → [1];
[1, 0] → [1];
[1, 1] → [0];

Figure 21.10 ABEL representation of the Truth table of an XOR gate

2-bit Comparator example:

TRUTH_TABLE ( [A1, A0, B1, B0] → [G, E, L] )
[0, 0, 0, 0] → [0, 1, 0];
[0, 0, 0, 1] → [0, 0, 1];
...

Figure 21.11 ABEL representation of the Truth table of a 2-bit Comparator

The notation can be simplified by defining a set:

INPUT = [A1, A0, B1, B0];
TRUTH_TABLE ( INPUT → [G, E, L] )
0  → [0, 1, 0];
1  → [0, 0, 1];
...

Figure 21.12 ABEL representation using a set

Test Vectors

Test Vectors are used to verify the logic circuit design's operation. They specify inputs and corresponding outputs. The software simulates the circuit by applying the test vector and checking outputs. Test vectors are essentially the same as Truth Tables.

TEST_VECTORS ( [A1, A0, B1, B0] → [G, E, L] )
[0, 0, 0, 0] → [0, 1, 0];
[0, 0, 0, 1] → [0, 0, 1];
...

Figure 21.13 Test Vector of a 2-bit Comparator

The ABEL Input File

An ABEL input (source) file creates a module with three sections:

1. Declarations: Includes device declaration, pin declarations, and set declarations.

Decoder device 'P22V10';
A0, A1, A2, A3, PIN 1, 2, 3, 4;
INPUT = [A1, A0, B1, B0];

Figure 21.15 ABEL Input declarations

• 'Decoder' is a user-defined description
• 'device' is a reserved keyword (case-insensitive)
• 'P22V10' is the device name
• 'PIN' is a keyword (case-insensitive) defining variable-to-pin relationships
• 'INPUT' defines a set of elements

2. Logic Descriptions: Includes the three methods (Boolean equations, Truth Tables, State Diagrams).

3. Test Vectors: Used to simulate and verify the logic circuit.

The Documentation file

After processing an input file, ABEL generates a documentation file containing:

• Final reduced equations
• A JEDEC file
• A device pin diagram

The JEDEC file

The JEDEC file is downloaded to the PLD programmer to program the appropriate PLD device.

⭐ Key Takeaways

The GAL16V8 is a versatile PLD that can operate in Simple, Complex, or Registered modes, with its OLMC providing flexible tri-state buffer control through four sources and three feedback options. Understanding the three programming modes is essential—Simple mode for dedicated combinational or input functions, Complex mode for product-term-controlled tri-state buffers, and Registered mode for sequential circuits. ABEL is a powerful device-independent HDL that uses Boolean equations, truth tables, and state diagrams, with special symbols (!, &, #, $) for logic operations and sets for simplifying multiple variables. Test vectors function identically to truth tables for verifying circuit operation, and the ABEL input file structure (declarations, logic descriptions, test vectors) leads to a JEDEC file for programming the PLD.

🧠 Quick Revision Questions

1. What are the three programming modes of the GAL16V8, and which ones are associated with combinational versus sequential logic?
2. What are the four possible sources for controlling the tri-state buffer in the GAL16V8 OLMC?
3. In ABEL, what are the symbols for NOT, AND, OR, and XOR operations, and what is their order of precedence?
4. How would you write an ABEL expression for the Boolean function F = A'BC + AB'C + ABC'?
5. What are the three sections of an ABEL input file, and what is the purpose of the JEDEC file?

📘 Lecture 22 — ABEL INPUT FILE OF A QUAD 1-OF-4 MUX

📖 Overview: This lecture covers the design and implementation of a Quad 1-of-4 Multiplexer using ABEL input files and GAL20V8 devices. It then introduces sequential circuits by explaining why memory elements are essential, and provides a detailed analysis of S-R latches built with NAND and NOR gates, including their truth tables, timing diagrams, and active-low versus active-high behavior.

🗂️ Topics Covered

The lecture begins with the ABEL input file structure for a Quad 1-of-4 MUX, defining its pins, equations, and test vectors. It then explains why sequential circuits are needed due to the limitations of combinational logic lacking storage. Next, it focuses on latches as basic memory elements, specifically the NAND gate based S-R latch and the NOR gate based S-R latch, analyzing all four input combinations for each. Finally, it covers truth tables and timing diagrams for both active-low and active-high latches.

📝 Lecture Summary

ABEL INPUT FILE OF A QUAD 1-OF-4 MUX

A Quad 1-of-4 MUX contains four separate multiplexers, each with four inputs and a single output. All four multiplexers share two common select inputs, S1 and S0. The function table shows that for each combination of select inputs, a specific group of data inputs (e.g., A0, B0, C0, D0 for S1=0, S0=0) is routed to the corresponding outputs (Aout, Bout, Cout, Dout).

🔑 Definition — Quad 1-of-4 MUX: A single integrated circuit containing four independent 1-of-4 multiplexers, all sharing the same two select lines.

📌 Example — Function Table: When S1=0 and S0=0, outputs are: Aout = A0, Bout = B0, Cout = C0, Dout = D0. When S1=0 and S0=1, outputs become: Aout = A1, Bout = B1, Cout = C1, Dout = D1.

Implementation of Quad MUX

The Quad MUX uses a GAL20V8 PLD because it has enough pins: 12 inputs, 2 special function inputs, and 8 input/output pins. Four of the input/output pins are configured as inputs to handle the fourth multiplexer's data lines (D1, D2, D3) and the select input S0. Each multiplexer output is represented by a Sum-of-Product Boolean expression with four product terms, implemented using OLMCs (Output Logic Macrocells).

🔑 Definition — GAL20V8: A programmable logic device with 20 pins, 12 dedicated inputs, and 8 bidirectional input/output pins, used here because the GAL16V8 lacks sufficient pins.

📐 Formula for Aout: Aout = !S1 & !S0 & A0 # !S1 & S0 & A1 # S1 & !S0 & A2 # S1 & S0 & A3 → Selects one of four A-inputs based on S1 and S0.

Sequential Circuits

Sequential circuits differ from combinational circuits because they include memory elements that can store data. Combinational circuits handle only instantaneous inputs and cannot store outputs, which limits their use. An ALU adding numbers 2, 3, 4, and 5 requires temporary storage for numbers and partial results. Similarly, parallel-to-serial and serial-to-parallel conversions need memory elements. A counter cannot count to the next value without storing the previous count.

🔑 Definition — Sequential Circuit: A digital circuit that uses memory elements to store previous inputs or outputs, allowing it to have states and perform operations over time.

Latches and Flip-Flops

A latch is a temporary storage device with two stable states, having two inputs and two outputs: Q and its complement Q̅. The latch retains its state unless inputs change to set it to a new state.

The NAND gate based S-R (Set-Reset) Latch

This latch uses two cross-coupled NAND gates. The unconnected inputs are Set (S) and Reset (R). Analysis of all four input combinations:

1. S=0, R=0: Both outputs become 1, making Q=1 and Q̅=1. This is invalid because Q and Q̅ should be complements.
2. S=0, R=1: Q is set to 1, Q̅ is set to 0 (regardless of initial state).
3. S=1, R=0: Q is set to 0, Q̅ is set to 1 (regardless of initial state).
4. S=1, R=1: The previous output state is maintained.

🔑 Definition — NAND S-R Latch: A latch using two NAND gates where active-low inputs S̅ and R̅ set or reset the output, with S=0, R=0 being invalid.

📌 Example — S=0, R=1: If initial Q=1, Q̅=0, then S=0 forces Q to 1, and with Q=1 and R=1, gate 2 outputs Q̅=0. If initial Q=0, Q̅=1, S=0 forces Q to 1, and with Q=1 and R=1, gate 2 outputs Q̅=0. Result is always Q=1, Q̅=0.

💡 Why this matters: The NAND latch has active-low inputs, meaning the set or reset action occurs when the input is logic 0.

The NOR gate based S-R (Set-Reset) Latch

This latch uses two cross-coupled NOR gates with S and R inputs switched compared to the NAND version. Analysis:

1. S=0, R=0: The previous output state is maintained.
2. S=0, R=1: Q is set to 0, Q̅ is set to 1 (Reset action).
3. S=1, R=0: Q is set to 1, Q̅ is set to 0 (Set action).
4. S=1, R=1: Both outputs become 0, making Q=0 and Q̅=0. This is invalid.

🔑 Definition — NOR S-R Latch: A latch using two NOR gates where active-high inputs S and R set or reset the output, with S=1, R=1 being invalid.

📌 Example — S=1, R=0: If initial Q=1, Q̅=0, S=1 makes Q=0, then with Q=0 and R=0, gate 1 outputs Q̅=1. If initial Q=0, Q̅=1, S=1 makes Q=0, then with Q=0 and R=0, gate 1 outputs Q̅=1. Result is always Q=0, Q̅=1? No, wait: For case a, final Q=0, Q̅=1. For case b, final Q=0, Q̅=1. So Q=0, Q̅=1. When S=1 and R=0, the set action occurs, so Q should be 1, Q̅=0. Let's re-read: "setting S to 1 and R to 0 sets the Q and Q̅ outputs to 1 and 0 respectively." So the example should show Q=1, Q̅=0 after S=1, R=0. The text confirms this.

💡 Why this matters: The NOR latch has active-high inputs, meaning the set or reset action occurs when the input is logic 1.

S-R Latch Timing Diagrams

The timing diagram for the NAND based (active-low) latch shows that S=0 and R=0 are never applied. The timing diagram for the NOR based (active-high) latch shows that S=1 and R=1 are never applied. Both diagrams illustrate how changes in S and R inputs cause corresponding changes in the Q output over time.

⭐ Key Takeaways

A Quad 1-of-4 MUX requires the GAL20V8 PLD due to its 22-pin requirement, with each multiplexer output implemented as a sum-of-products expression with four product terms. Sequential circuits are essential for all practical digital systems because they include memory elements that can store data, enabling operations like multi-number addition, parallel-to-serial conversion, and counting. The NAND gate based S-R latch has active-low inputs, where S=0 sets Q to 1 and R=0 resets Q to 0, and the input combination S=0, R=0 is invalid. The NOR gate based S-R latch has active-high inputs, where S=1 sets Q to 1 and R=1 resets Q to 0, and the input combination S=1, R=1 is invalid. Both latches maintain their output state when neither set nor reset is active, and never allow both set and reset to be active simultaneously.

🧠 Quick Revision Questions

1. Why is the GAL20V8 used instead of the GAL16V8 for implementing the Quad 1-of-4 MUX?
2. What are the three input combinations for a NAND-based S-R latch and the corresponding output states?
3. How does an active-high S-R latch differ from an active-low S-R latch in terms of input levels?
4. Why is the input combination S=0, R=0 considered invalid for a NAND-based S-R latch?
5. In a NOR-based S-R latch, what happens to the Q and Q̅ outputs when S=1 and R=1 are applied?