Introduction to Computing Systems PDF

Need for Digital Systems A system is a group of elements or components that are integrated to achieve a specific goal. A signal is a way of conveying some information. It refers to any time-varying voltage, current, or electromagnetic wave that carries information. Information...

Need for Digital Systems A system is a group of elements or components that are integrated to achieve a specific goal. A signal is a way of conveying some information. It refers to any time-varying voltage, current, or electromagnetic wave that carries information. Information could be in the form of an image, sound, temperature, etc. There are two types of signals: analog signals digital signals. Analog signals are continuous signals, and they vary with respect to time. Digital signals are discrete signals that are present only at discrete instants of time. Based on the type of signal that the system handles, there are two types of systems: analog digital. Analog systems process analog signals Since analog signals involve continuous signals, it requires huge memory to store the collected information. Also, designed systems cannot be easily modified in real-time. Digital systems process digital signals in the form of discrete signals, which are obtained by sampling analog signals. A signal sampler is a kind of high-speed switch that takes an analog signal as an input and produces discrete signals at predefined time intervals. This kind of digital signal has only two amplitudes or voltage levels, namely high voltage level and low voltage level. Digital systems are popular because of the advantages it offers, some of which are given as follows: Easy to design and implement Cost-effective More flexible design Easy data storage, compression, and encryption More reliable—the impact of noise interference and distortion is very less Since digital signals are obtained by sampling analog signals, the accuracy of the digital signal obtained depends on the sampling rate. If the sampling rate is low, sampled information will be irreversibly lost, and the original signal will not be represented correctly. A higher sampling rate provides better accuracy but will have an impact on storage capability and the amount of time it takes to process the information. There is always a compromise between sampling rate, processing time, and storage. Introduction to Number System A number system defines how a number can be expressed. These numbers are represented using distinct digits and or symbols in a consistent manner. In general, the value of any digit in a number can be determined by: The digit or a symbol Its position in the number The base or radix value of the number system Non-positional number system uses symbols to represent any number. Hence, it is also known as the “Symbolic” number system. For example, the Roman number system uses only seven symbols I, V, X, L, C, D, and M in decimal. Roman number system. As the name indicates, in a positional number system, the position of a symbol determines the value it represents. Examples of number systems include decimal, binary, octal, and hexadecimal. In general, any number N(b) in the positional number system is divided into two parts: integer part fractional part. These two parts are separated by a radix or a decimal point. General representation of a number in the positional number system. N represents the number, b represents the radix or base of a number, small n represents the number of digits in the integer portion m is the number of digits in the fractional portion. The commonly used number system is shown in below. In binary, bi means 2. The binary number system uses only two symbols or digits 0 and 1. In the octal number system, oct means 8. Base of the octal number system is 8 and uses eight symbols 0 to 7. In the decimal number system, deci means 10. The base of the decimal number system is 10 and uses ten symbols from 0 to 9. Hex in a hexadecimal number system means 6, and deci means 10. The hexadecimal number system uses a base value of 16 and uses 16 distinct symbols to represent a number. It uses 0 to 9 and A to F symbols. Decimal Number System The decimal number system has a base value of 10 and uses ten symbols from 0 to 9. Consider 1248.84 as an example. Every digit has a position number. The integer part has a positive position number, whereas the fractional part has a negative number. Each digit is associated with a weight and is equal to 10 power position numbers. Advantages of the decimal number system are : They are easy to represent, read, and manipulate. Hence, it is most used in daily life. However, decimal number representation cannot be employed in computers for the following reasons: Hard to store: This is because each digit in a number is made of ten symbols. The first electronic computer ENIAC used ten vacuum tubes per digit, and the computer design was very bulky. Hard to transmit: Encoding ten different symbols requires ten signal levels so that it can be transmitted over a single wire. Also, to minimize the errors, high-precision encoding is needed. Complex design and implementation: Design requires handling ten signal levels. Hence, it complicates the implementation of various arithmetic and logic functions, such as addition and multiplication. Binary Number System The binary number system uses only two possible values, 0 or 1, for each digit in a number. This number system is used in every digital system because of easy storage, easy transmission, and easy implementation of required functions. In such systems, everything is represented by either the presence or absence of a signal. The presence of a signal is usually interpreted as digit 1, and the absence of a signal as digit 0. Each digit in a binary number is known as a bit. The rightmost bit is known as the least significant bit, LSB The leftmost bit is known as the most significant bit, MSB. In a digital system, MSB is the bit that has the largest weight in a binary number, whereas LSB has the least weight. Since a binary number system is a positional number system, each bit has a positional value and weight associated with it. Usually, programming languages use a standard number of bits while organizing data storage and access. A Nibble 4 bits A Byte 8 bits A Word 16 bits or 2 bytes A D-word 32 bits or 4 bytes A Q-word 64 bits or 8 bytes Decimal to Binary Conversion While converting from decimal to binary, integer and fractional parts are converted separately. For converting the integer part to binary, the successive division method is used For converting the fractional part, successive multiplication is used. For both division and multiplication, the target number system’s base, which is base 2, is considered. In general, while converting the integer part, first divide the integer part of the decimal number by 2. The first remainder that is obtained will be the LSB of the binary number. If the quotient is zero, the conversion is complete. If the quotient is not zero, then the quotient will be divided by 2. The new remainder is the next most significant bit of the binary number. This continues until the quotient becomes 0. For fractional part conversion, multiply the fractional part by 2. The carry generated is kept aside, and the fraction will then be multiplied by 2.This process is continued until the fractional part is zero or the required accuracy is attained. Binary to Decimal Conversion To convert binary to decimal, the following steps are followed. Step 1: Multiply each bit of the binary number by its corresponding bit-weighting factor. Step 2: Sum up all the products to get the decimal number. Bit Permutation In a binary number system, if a number sequence has n bits, then we can have 2n possible combinations or permutations Octal Number and Hexadecimal Number System The base of the octal number system is 8. To convert decimal numbers to octal numbers, the integer part and fractional part are treated separately. The integer part is divided by eight until the quotient becomes 0. The remainder that is generated by the process of division will give a decimal equivalent of the octal integer part. To convert the fractional part to decimal, successive multiplication is used. To convert from an octal number to a decimal, weighted multiplication is used. The example where the decimal number 156.32(10) is converted to an octal number. To convert decimal to octal, Conversion of 156.32(10) to octal number. Binary to Octal Conversion There are two methods to convert a binary number to an octal number. Method 1: First, convert the binary number to decimal number and then to octal number. Example: (1111100.101)2 (124.625)10 (174.5)8 Method 2: Make 3 bits group. For integers, part bits are grouped from right to left For the fractional part, bits are grouped from left to right. Octal to Binary: There are two methods to convert an octal number to binary. Method 1: Convert octal to decimal and then to binary. Example: (524.6)8 -> (340.75)10 -> (101010100.110)2 Method 2: Convert individual octal digits to binary. Hexadecimal Number System Hexadecimal number system uses 16 symbols: 0 to 9 and A to F. Software developers widely use hexadecimal numbers as they provide a human-friendly representation of binary-coded values. It is shorter and easier to read than binary and octal. Each hexadecimal digit represents one nibble, which is four binary bits. Binary to Hexadecimal Conversion There are two ways of converting binary to hexadecimal. Method 1: Convert from binary to decimal and then decimal to hexadecimal. Method 2: Group four bits and then convert those four bits to equivalent hexadecimal digits. For the binary number integer part, the four-bit group is formed from right to left For the fractional part, four-bit groups are formed from left to right. Hexadecimal to Binary Conversion To convert from hexadecimal to binary, individual hexadecimal digits are converted to binary. Operations on Binary Bitwise Addition A logic circuit is an essential building block of a logic system that will have several inputs and outputs. In any logic system design, the truth table plays an important role. The truth table lists all possible combinations of input binary variables and the corresponding outputs of a logic system. When the number of input binary variables is one, there are only two possible input combinations: "0” and “1.” If the number of inputs is two, there can be four possible input combinations, that is, 00, 01, 10, and 11. Similarly, the number of possible input combinations for three input binary variables becomes eight. So, if a logic circuit has n binary inputs, its truth table will have 2n possible input combinations. Consider two inputs A and B. There are two outputs, Sum and Carry. Since there are two inputs, there are four possible combinations. 1’s Complement There are two types of complements: 1’s complement 2’s complement. In 1’s complement operation, we flip or invert all the bits in a number that is, change 0 to 1 and 1 to 0. Ex: 1’s complement of 1100 is 0011. 2’s Complement 2’s complement is 1’s complement of a number + 1. Shortcut method. Copy bits from right to left until (and including) the first 1, and then flip all the remaining bits. Unsigned and Signed Magnitude Representation Data type specifies the type of data variable holds and what is the size requirement. These data types could be integer, floating point, or character type. There are various ways of representing an integer. The classification of binary integer representation is shown below. In unsigned number representation, there are only zero and positive values. If there are n bits in a number, using which we can represent 2n values. Out of 2n values, one value represents zero, and the remaining 2n-1 values represent positive numbers. The 3-bit binary number combinations and corresponding unsigned values. Since there are three bits, there are eight combinations. The first combination, 000, represents 0, and the remaining combinations represent values from +1 to +7. There are three ways to represent negative numbers along with positive numbers: Signed magnitude representation 1’s complement representation 2’s complement representation In signed magnitude representation, both positive and negative numbers are represented.  In this representation, the MSB, that is, the most significant bit, is used to represent the sign of a number. If MSB is 0, then the number is positive. Otherwise, it is negative. Below image shows the signed magnitude representation of 3-bit numbers. With n bits, there are 2n distinct combinations, out of which 1 through 2n-1-1 positive numbers, and -2n-1-1 through -1 negative numbers. This leaves two values: one for +0 and the other for -0. Addition of Signed Magnitude Numbers Three cases of signed magnitude number addition are evaluated to check the suitability of signed magnitude representation for digital computers. While representing the numbers, the above table in is referred. Case 1: Perform 1 + 2 +1 001 +2 010 +3 011 The addition result+3 in signed magnitude representation is 011, which matches with the answer, which is obtained after the binary addition. Hence, it is correct. Case 2: Perform2 + (-3) +2 0 1 0 -3 111 -1 1 0 0 1 Ignore the carry generated after binary addition. When decimal numbers +2 and -3 are added, the result obtained is -1. But the result of binary addition is 001, which is equal to +1. Hence it is incorrect. Case 3: Perform 3 + (-3) +3 0 1 1 -3 111 +0 1 0 1 0 -0 When decimal addition of +3 and -3 is performed, the result obtained is 0, which can be represented as either +0 or -0. But the result obtained after adding binary numbers is 010, which is equal to +2. Hence it is incorrect. it comes with the following two major drawbacks, which makes it unsuitable for computer arithmetic: Addition yields incorrect answers for some input combinations. There are two representations for 0. Hence, wastage of one-bit pattern. Complement Representation 1’s complement representation is used to represent zero, positive, and negative numbers. The representation of positive numbers is similar to that of signed magnitude representation. That is, the most significant bit is zero for positive numbers. A negative number is represented by flipping all the bits of the corresponding positive number. For example, + 3 is represented as 011. But to represent -3, the following procedure needs to be followed. Step 1: Consider the magnitude of the negative number and convert it to its binary representation. The magnitude of -3 is +3, and its representation in binary is 011. Step 2: Flip all the bits. So, 1’s complement representation of -3 is 100. Below Figure shows the 1’s complement number representation compared to the signed magnitude representation. Numbers are represented using three bits b2, b1, and b0. In 1’s complement representation also, there are two representations for 0, that is, +0 and -0. There are three positive numbers and three negative numbers. In both the signed magnitude representation and 1’s complement representation, +0 and positive numbers have the same bit pattern. But the representation for -0 and negative numbers are different.  For the n-bit number, the number of positive numbers is 2n- 1-1, the number of negative numbers is 2n- 1-1, and there are two representations for 0. The range of numbers that can be represented is given by -2n- 1-1 to +2n- 1-1. Addition of 1’s Complement Numbers Four cases of 1’s complement number addition are evaluated to check the suitability of 1’s complement representation for digital computers. While representing the numbers, the table in Figure 4 is referred to. Case 1: Perform 1 + 2 +1 0 0 1 +2 0 1 0 +3 011 +3 in binary is 011, which matches the answer obtained after the binary addition. Hence, the addition operation is correct. Case 2: Perform 2 + (-3) +2 0 1 0 -3 100 -1 110 When +2 and -3 are added, the result obtained is -1. The result of binary addition is 110, which is also equal to -1. Hence, the addition operation is correct. Case 3: Perform 3 + (-3) +3 0 1 1 -3 100 0 111 When decimal addition of +3 and -3 is performed, the result obtained is 0, which can be represented as either +0 or 0. The result obtained after adding binary numbers is 111, which is equal to -0. Hence, the addition operation is correct. Case 4: Perform 3 + (-2) +3 0 1 1 -2 101 1 1000 Ignoring the carry results in 000, which is equal to +0. But when +3-2 is performed, the result obtained is 1, which does not match the result obtained after binary addition.Hence, the addition operation is incorrect. But there is a way to correct this, that is, adding carry to the result obtained. After adding carry, the result will be 001, which matches the result of decimal addition. The main advantage of 1’s complement representation is that it can be used for arithmetic operations. But whenever there is a final carry generated out of MSB, it needs to be added to the number. The disadvantage is that the representation is not very easy to understand. When there is a carry, it needs to be handled properly to get the right answer. 2’s Complement Representation 2’s complement representation is used to represent both positive and negative numbers. While representing the positive number, convert the given number to a binary number. Hence, positive number representation is the same for signed magnitude representation, 1’s complement representation, and 2’s complement representation. For negative number representation, take the magnitude of the number and convert it into binary, and then apply 2’s complement operation on the number. For example, to represent -15 using 8 bits, the following steps are followed. Step 1: Take the magnitude of -15. The magnitude of -15 is+ 15 and then convert + 15 into binary. + 15 = 0 0 0 0 1 1 1 1 Step 2: Find 1’s complement of binary and add 1 to it.  It can be observed that the 2’s complementation has one representation for 0. Positive number representation is the same as that of other representations. There are four negative numbers. The combination 100, which represents -4, is called a weird number. It is called a weird number because inverting 100 and adding 1 to it results in 100 itself. Hence, this negative number has no positive counterpart. But for all other negative numbers, there is a positive counterpart. Addition of 2’s Complement Numbers Four cases of 2’s complement number addition are evaluated to check the suitability of 2’s complement representation for digital computers. While representing the numbers, the table is referred to. Case 1: Perform 1 + 2 +1 001 +2 010 +3 011 +3 in binary is 011, which matches the answer obtained after the binary addition. Hence, the addition operation is correct. Case 2: Perform 2 + (-3) +2 0 1 0 -3 101 -1 111 When +2 and -3 are added, the result obtained is -1. The result of binary addition is 111, which is also equal to -1. Hence, the addition operation is correct. Case 3: Perform 3 + (-3) +3 0 1 1 -3 101 0 1000 When the decimal addition of +3 and -3 is performed, the result obtained is 0, which can be represented as either +0 or 0. The result obtained after adding binary numbers is 1000. Ignoring the carry, we obtain 000, which is equal to +0. Hence, the addition operation is correct. Case 4: Perform 3 + (-2) +3 0 1 1 -2 1 1 0 1 1001 When the decimal addition of +3 and -2 is performed, the result obtained is 1. Ignoring the carry results in 001, which is equal to +1. Hence, the addition operation is correct. All these four cases show that 2’s complement representation is suitable for digital computers. Arithmetic Operation: Addition and Subtraction For the addition of two numbers, bitwise addition is performed from LSB to MSB. Sum and carry will be generated per the truth table shown. Subtraction is performed using addition. Example: A - B can be written as A + (-B). That is, -B and A are added where -B is obtained by 2’s complement operation. In the following section, four cases of addition are shown. Assume, A = 5 and B = 4. Case 1: A + B + 5 using 8-bit representation = 0 0 0 0 0 1 0 1 + 4 using 8-bit representation = 0 0 0 0 0 1 0 0 A+B The decimal equivalent of 0000 1001(2) is +9. When two positive numbers are added, the result should always be positive. Case 2: A - B A - B = A + (-B) + 5 in 8-bit representation = 0 0 0 0 0 1 0 1 - 4 in 8-bit representation A +(-B ): Ignore carry. The decimal equivalent of 00000001(2) is +1. Since A is greater than B, the result should be positive. Case 3: -A + B - 5 in 8-bit representation + 4 in 8-bit representation:0 0 0 0 0 1 0 0 -A + B The decimal equivalent of 1 1 1 1 1 1 1 1(2) is -1. The magnitude of -5 is 5, which is more than 4. Hence, the result will have a sign of 5, which is negative in this case. Case 4: -A - B -A - B = - A + (-B) - 5 in 8-bit representation = 1 1 1 1 1 0 1 1 - 4 in 8-bit representation = 1 1 1 1 1 1 0 0 -A + (-B): Ignore carry. The decimal equivalent of 1 1 1 1 0 1 1 1(2) is -9. Since -5 and -4 are negative numbers, the result will also have a negative sign. Arithmetic Operation: Sign Extension and Overflow Sign extension, short known as sext, is the operation in the computer system. Using sign extension, number of bits of the binary number is increased while preserving the value of the number. While adding two binary numbers, care must be taken to ensure that two numbers’ sign bits are aligned. Failing which may result in erroneous results. The original number 1 0 0 0 1 has five bits.  This number needs to be extended to eight bits. Five bits of the original number are copied as it is, and the remaining three bits are filled with the sign of the number. The new number is the sign-extended version of the original number. Another issue in computer arithmetic is the overflow condition. Consider two numbers A = +10 and B = +8. These two numbers are represented using 5-bit 2’s complement representation. Adding these two numbers will result in the following. The result obtained is -14 instead of +18. The main reason behind this is that it is unable to accommodate +18 using five bits. The range of numbers that can be represented using five bits is -16 to +15. Hence, the result has overflowed the capacity of the representation. When two 2’s complement numbers are added, and they both have the same sign (both positive or both negative), then overflow occurs if and only if the result has the opposite sign. Logical Operation: AND, OR, NOT, NAND, NOR, EXOR, and EXNOR A logic gate is an electronic circuit that acts as a building block for all digital circuits. These circuits perform logical operations. There are three basic logic gates, namely the OR gate, the AND gate, and the NOT gate. Other logic gates that are derived from these basic gates are the NAND gate, the NOR gate, the EXCLUSIVE-OR gate, and the EXCLUSIVE-NOR gate. AND Gate: The output of an AND gate is 1 only when all its inputs are in the 1 state. For all other input combinations, the output is 0. The logic expression is given by Y = A AND B = A·B  = AB OR Gate: The output of an OR gate is 0 only when all its inputs are at 0. For all other possible input combinations, the output is 1. Logic expression for two input OR gate is written as Y = A OR B =A+B NOT Gate: A NOT gate is a one-input, one-output logic circuit whose output is always the complement of the input. That is, 0 input produces 1 output, and 1 input produces 0 output. Logic expression for NOT gate is given by Y = A’ =A EXOR Gate: For a two-input XOR gate, when both the inputs are the same, the output is 0. But when inputs are different, the output is 1. The logic expression of X-OR is given by  Y = A EXOR B. Y=A B. The output of a multiple-input EX-OR logic function is a logic 1 when the number of 1s in the input sequence is odd. For an even number of 1s, the output will be 0. NAND Gate: It is equivalent to an AND gate followed by a NOT gate. The truth table for the NAND gate is obtained from the truth table of an AND gate by complementing the output entries. The output of a NAND gate is a logic 0 when all its inputs are a logic 1.For all other input combinations, the output is a logic 1. NAND gate operation is logically expressed as Y = A NAND B = (AB)’ NOR Gate: NOR stands for NOT OR. NOR gate is equivalent to an OR gate followed by a NOT gate. The output of a NOR gate is a logic 1 when all its inputs are logic “0.” For all other input combinations, the output is a logic 0. The output of a two-input NOR gate is logically expressed as Y = A NOR B = (A + B)’  : Three domains where computers are highly utilized, and their presence is strongly felt are : Education Business Medical : The four main structural components of a computer are 1) Central Processing Unit (CPU) 2) Memory 3) Input/Output System 4) System Bus A CPU has four main structural components, namely 1) Control Unit (CU) 2) Arithmetic and Logic Unit (ALU) 3) Registers 4) Internal Bus The phrase Functions of a Computer denotes the collective outcome, or the result of the operations performed collaboratively by the different components of the computer. These functions are divided into the following four main categories: 1) Data Processing 2) Data Storage 3) Data Movement 4) Control A Computer System is divided into two parts: 1) denotes the computer system’s physical components that are easily visible to us. Central Processing Unit , Memory, I/O Devices 2) is a set of instructions that enable the hardware components to perform one or more specific tasks. It also categories into two parts: Software used to manage computer resources, for example, the CPU, Memory, I/O devices, etc., fall under the category of System Software. Examples : operating systems, editors, compilers, and assemblers. Software used to perform general or specific tasks inside a computer. A computer is a digital device in which a processor understands instructions written in the form of a binary code. Assembly language enables writing the instruction in a simpler form which is further converted into Machine Language using a special tool called the Assembler. Before execution by the computer, this high-level language software program is converted to Assemble Language using a special tool called the Compiler. Before a computer can solve a problem, different transformations happen across multiple levels, as shown below:  1. Problems are generally specified in natural languages, like English, An algorithm is a step-by-step procedure that a computer can carry out. 2. The next step is to translate it into a computer program using a high-level language since it is simpler to code and easier to debug for any errors. 3. Using compilers, when a software program written using a particular programming language, is converted into machine instructions that the processor can understand. 4. The next transformation level involves Microarchitectures, which involves implementing the computer’s Instruction Set Architecture (ISA). 5. Once the microarchitecture of a computer is designed, we need to implement each sub-part of this design. 6. Each element of the microarchitecture gets implemented using simple logic circuits, which comprise the basic building blocks called the devices. Charles Babbage invented the first computer. Here is the further generation-wise development of computers. Mechanical Calculating Machines Wilhelm Schikard – “Calculating Clock” Blaise Pascal – “Pascaline” “Lightning Portable adder” and “Addometer” Vacuum Tubes Computers, EDVAC, ENIAC IBM 7000 and DEC-PDP1 IBM 360 Apple 1, Apple 2, IBM PC Based on the number of devices that the IC can accommodate, semiconductors can be classified as follows: Small-scale integration (SSI) 1-100 devices Medium-scale integration (MSI) 100-3,000 devices Large-scale integration (LSI) 3,000 - 100,000 devices Very large-scale integration 100,000 - 100,000,000 (VLSI) devices Ultra large-scale integration Over 100,000,000 devices (ULSI) 1. It includes the most important features of the well-known computer systems available in the market. 2. These represent the different types of arithmetic, logic, and control operations that the LC-3 can perform. : The three important parts of LC-3 are memory, the Input and Output System, and the Control and Processing Unit (CPU). The Processor Bus or the System Bus connects the different parts, transferring information to and from each component. Here, the CPU consists of the following key blocks: 1) Finite State Machine (FSM), 2) Arithmetic and Logic Unit (ALU), and 3) Register File or the Register Set.  Kilo- (K) = 1 thousand = 103 and 210 Mega- (M) = 1 million = 106 and 220 Giga- (G) = 1 billion = 109 and 230 Tera- (T) = 1 trillion = 1012 and 240 Peta- (P) = 1 quadrillion = 1015 and 250 The base unit for the measurement of speed is. Hertz stands for clock cycles per second, which is also a unit of frequency. So, when we measure the speed of operation of any component in the computer system, we look at the number of processing cycles the component can execute per second time. The basic unit of storage in a computer system is a byte. A byte consists of 8 bits, where each bit can take two values - a 0 or a 1. Kilo Bytes or Mega Bytes or Giga Bytes are other units to measure the capacity of storage units. The main memory in a computer system, also called the RAM or the Random Access Memory, is usually measured in Mega Bytes. On the other hand, disk storage is measured in Giga Bytes for small systems and in Tera Bytes for large systems. Milli- (m) = 1 thousandth = 10-3 Micro- (μ) = 1 millionth = 10-6 Nano- (n) = 1 billionth = 10-9 Pico- (p) = 1 trillionth = 10-12 Femto- (f) = 1 quadrillionth = 10-15 Introduction to K-Map Method Complex logic expressions can be simplified using well-known Boolean algebra, which is composed of several useful Boolean Postulates and theorems. But this method comes with two main drawbacks. Complex Boolean expressions require several time-consuming steps for simplification. ○ There are no specific rules to guide us on which theorems should be applied and when. ○ Also, when a theorem or a postulate is applied, it is difficult to determine whether the simplest form has been achieved or not. This technique is error-prone. There are chances that one may end up making mistakes. The simplified expression will have a minimum number of terms with the least number of literals in each term. A K-map is a collection of cells or squares. Each cell represents a minterm or a maxterm. The group of these cells represents the output values of a given Boolean function. These cells are arranged such that the adjacent cells differ in the value of one variable. This is a condition for cell adjacency. An n – variable K-map will have 2n cells. For example, a 2-variable K map has four cells. A 3-variable K map has 23, that is, eight cells. Similarly, the 4 variable K map has 16 cells and so on. This technique can be employed for any number of variables. But, it is generally used up to six variables. Beyond six variables, it becomes very complex. Representation of SOP and POS on K-Map The main objective of the K-Map is to simplify the Sum of Products and the Product of Sums expressions. Based on this, K- maps can be classified into two types. Minterm K – Map Maxterm K – Map Minterm K-map is used to represent the Sum of Product expressions. Maxterm K-map is used to represent the Product of Sum expressions. Representation of Minterms on the K-Map The truth table for some function with two variables, X, and Y. With two variables, we can have four minterms m0, m1, m2, and m3. Note that while writing minterms lower case ‘m’ is used.  These four minterms are mapped to 2 variable K-map with four cells. These four cells are numbered as cell 0, 1, 2, and 3. To determine the position of minterms on this K-Map, write X and Y on the K-map. These two variables can take values 0 and 1. Note that variable X is MSB, and Y is LSB. Minterms for different values of X and Y are given below: ○ X = 0, Y = 0 , m0 = X’Y’ ○ X = 0, Y = 1 , m1 = X’Y ○ X = 1, Y = 0 , m2 = XY’ ○ X = 1, Y = 1 , m3 = XY Minterm m0 corresponds to x = 0 and y = 0 and is placed in the 0th cell. Minterm m1 corresponds to x = 0 and y = 1 and is placed in the 1st cell. The 0th cell and 1st cell are adjacent cells, and they differ in the value of one variable, i.e., for these two cells, X is 0, Y is 0 for the first cell, and Y is 1 for the second cell. Minterm m2 corresponds to X = 1 and Y = 0 and is placed in the 2nd cell. 0th and 2nd cells are adjacent cells, and they differ in the value of the X variable. The value of the Y variable for both these cells is 0. Minterm m3 corresponds to X = 1 and Y = 1 and is placed in the 3rd cell. 1st and 3rd cells are adjacent cells and 2nd and 3rd cells are adjacent cells. In the case of a minterm K-map, logic ‘1’ is placed in all those cells for which the output is ‘1’, and ‘0’ is placed in all those cells for which the output is ‘0’. For minterm m0, the output is 1. Enter 1 in the 0th cell. For minterm m1, the output is 0. Enter 0 in 1st cell. For minterm m2, the output is 1. Enter 1 in the 2nd cell. For minterm m3, the output is 0.Enter 0 in the 3rd cell. To simplify a Boolean expression, we have to systematically group these 1’s in the K-map. Representation of Max Terms on the K-Map There are four Maxterms M0, M1, M2, and M3, corresponding to four input combinations. In max term representation, we write X when X = 0, and X’ when X = 1. Minterms for different values of X and Y are given below: X = 0, Y = 0 , M0 = X + Y X = 0, Y = 1 , M1 = X + Y’ X = 1, Y = 0 , M2 = X’ + Y X = 1, Y = 1 , M3 = X’ + Y’ The placement of Maxterms in K-map is similar to that of minterm placement. In the case of a Maxterm K-map, ‘0’ is placed in all those cells for which the output is ‘0’. ‘1’ should be placed for input entries corresponding to a ‘1’ output. Procedure for Boolean Expression Simplification Following is the general Procedure for Boolean Expression Minimization using K- Map. 1. Generate K – map. To generate a K-map, figure out the number of variables in the given Boolean expression. The number of cells in the K-Map depends on the number of variables. For n variables, there will be 2n cells. For example: for a 2-variable Boolean expression, 4 cell K-Map is needed. For three variables, 23 = 8 cells K-map is needed. If Minterm K-map is used, then enter 1 in K-map cells, only for the minterm whose output is 1. But if Maxterm K-map is used, then enter 0 only for the Maxterm whose output is 0. 2. Group all adjacent 1’s (0s, in the case of Maxterm K-map). The number of 1’s in a group must be a power of 2. A group of 1 cell, 2 cells, 4 cells, etc. can be formed. But a group with 3 cells or 5 cells cannot be formed because they are not a power of two. 3. Write a Boolean expression. Once groups are formed, the next step is to write the product (in case of Minterm K-map) / sum (in case of Maxterm K-map) terms. Identify the variables common in a group. Also, identify 1s (0s in case of Maxterms) that are not part of any groups and write expressions for the same which will contain all the variables. 4. Write SOP or POS terms obtained in step 3. Boolean Functions: Standard and Canonical Forms Logical functions are expressed in terms of logical variables. The values assumed by the logical functions and the logical variables are in binary form. There are two ways of expressing Boolean expressions. 1. Sum of products form (SOP) 2. Product of sums form (POS) Consider the logic circuit given in Figure. The logic circuit output is given by F = WX + YZ The logic circuit shown is called an AND-OR circuit because input AND gates drive an output OR gate. The output equation is referred to as a sum-of-products equation. Note that the AND-OR network of gates always produces the sum of products, in short, known as SOP. The terms in SOP expression are known as minterms. The logic circuit shown is called an OR-AND circuit because an output AND gate is driven by input OR gates. Note that the final output is the product of sums, in short, known as POS. OR-AND circuits always produce product of sums.  The terms in POS expression are known as maxterms. Canonical Form and Standard Form In canonical form, each term of Boolean expression contains all input variables either in normal form or in complement form. For example: F(X,Y) = XY + XY’ Both terms contain all the variables. On the other hand, standard form terms can contain one variable, two variables, or any number of variables in normal and complement form. For example: F(X,Y) = X + XY’ Here, F(XY) contains two terms. The first term has one variable and the second term has two variables. Deriving SOP and POS Expression from a Truth Table There are two ways of representing Boolean expressions. Sum of products, SOP expression Product of sums, POS expression Consider a three-variable truth table , with three variables, X, Y, and Z, and can have eight combinations. Each combination represents one product term. For example, when X = 0, Y = 0, Z = 1, the product term is X’Y’Z’. The eight product terms are known as minterms and are denoted as m0, m1, m2 to m7. Note that minterms are denoted by lowercase “m.” Two-variable truth tables will have four minterms, whereas four-variable truth tables will have 16 minterms. The sum of product expression for the given truth table is f = X’Y’Z + X’YZ + XYZ’ + XYZ. Sometimes Boolean expression is expressed in terms minterms and is given by f = m1 + m3 + m6 + m7 = ∑ m (1, 3, 6, 7) Below picture showst he product of sums expression for the given truth table. The product of sums expression is one in which different “sum” terms from inputs are “ANDed” together. A variable whose value is zero is represented in normal form, and if its value is one, it is represented in complement form. That is, if the value of X is zero, then it is represented as X and if the value of X is 1, then it is represented as X’. For x = 0, y = 0, and z = 0, the sum term is written as x + y + z For x = 0, y = 0, and z = 1, the sum term is written as x + y + z’. The sum terms are known as maxterms. Maxterms are represented as M0, M1, M2 to M7. Note that M should be written in uppercase. To write the product of sums form of a Boolean expression, first, identify the max terms for which the output is zero. As seen in the truth table, there are four places where the output is zero. The final Boolean expression will contain these four max terms. POS expression is given by f = (X+Y+Z) * (X+Y’+Z) * (X’+Y+Z) * (X’+Y+Z’). = M0.M2.M4.M5 = M(0,2,4,5) Boolean Algebra Theorems Idempotent Theorem The idempotent first law states that adding a variable to the same variable will result in the same variable. X+X=X The implementation uses an OR gate. When X equals 0, zero plus zero will be equal to zero. When X equals 1, one plus one will be equal to one. So, X plus X equals X itself. By applying the principle of duality, the second idempotent Law is obtained and is given by X.X = X The second idempotent law states that ANDing a variable with itself yields the variable itself. AND gate exhibits idempotence.. When X equals 0, zero AND zero is equal to zero. When X equals 1, one AND one is equal to one. So, X AND X equals X itself. Annulment Theorem The first law of annulment states that a variable that is ORed with 1 gives a 1. That is, X+1 = 1. When X equals 0, zero OR one is equal to one, and when X equals 1, one OR one will be equal to one. Hence, X OR 1 equals one. By applying the principle of duality, that is, changing OR to AND, and 1 to 0, one more law of annulment is obtained. X.0 = 0 Involution Theorem Involution law is also known as double complement law. This law states that the double complement of a variable gives the same variable. That is, (X’)’ = X When X equals zero, X’ is one and (x’)’ is zero. Similarly, when X equals one, X’ is zero and (x’)’ one. Hence, (X’)’ equals X. Associative Theorem The associative theorem allows the removal of brackets from an expression and regrouping of the terms. This theorem states that the operation can be performed in any order when the variable's priorities are the same. There are two laws under this:  1. OR associative law 2. AND associative law One law can be obtained by applying the principle of duality to the other law. OR associative law is also known as the law of addition. For three variables X, Y, and Z, OR associativity is written as X + (Y + Z) = (X + Y) + Z These two implementations yield the same output for different combinations of input variables, which can be verified using the truth table method. By applying the principle of duality, AND associative law is obtained. AND associative law is also known as the law of multiplication. For three variables, it can be written as, X.(YZ) = (XY).Z Here also, both implementations yield the same output for different input combinations. Absorption Theorem This theorem enables a reduction in a complicated expression to a simpler one by absorbing like terms. Here is the first theorem under the absorption theorem. X+XY=X Proof: LHS = X + XY X (1 + Y) X.1 [1 + Y = 1 annulment law]  X [X.1 = X] By applying the principles of duality, another absorption theorem is obtained and is given by, ▪ X(X + Y) = X Proof: LHS = X (X + Y) XX + XY [Apply Distributive Law] X + XY [XX X] X [Apply Absorption Law] DeMorgan’s Theorem DeMorgan’s first theorem states that, when two or more input variables are ANDed and complemented, they are equivalent to the OR of the complements of the individual variables. Consider two variables, X and Y, then (X.Y)’ = X’ + Y’ The left-hand side logic expression can be implemented using a AND-NOT logic gates or using a standard NAND gate with inputs X and Y. The right-hand side gate arrangement first inverts the two inputs producing X’ and Y’. These then become the inputs to the OR gate. Therefore, the output from the OR gate becomes X’+Y’. So, NAND gate is equivalent to bubbled OR gate. The truth table proves that both left-hand and right-hand expressions yield the same output for different input combinations. According to the second theorem, when two or more input variables are ORed and complemented, they are equivalent to AND of the complements of the individual variables. (X + Y)’ = X’.Y’ The left-hand side logic expression can be implemented using an OR NOT logic gate or using a standard NOR gate with inputs X and Y. The right-hand side gate arrangement first inverts the two inputs producing X’ and Y’. These then become the inputs to the AND gate. Therefore, the output from the AND gate becomes X’Y’. The truth table proves that both left-hand and right-hand expressions yield the same output for different input combinations. Summary of Boolean Algebra – Postulates and Theorems The list of postulates and theorems is tabulated in two tables. Universal Gates: A universal gate is a gate that can implement any Boolean function without the need to use any other gate type. NAND and NOR gates are known as universal gates. NOR and NAND gate implementation of NOT, OR, and AND gates is shown below. Exercise: Given the Boolean function: F = XY + X’Z a) Implement it with AND, OR, and NOT gates b) Implement it with only NAND gates c) Implement it with only NOR gates Solution: a) AND, OR, and NOT gate implementation b) NAND gate implementation c) NOR gate implementation IC requirement is as follows: Postulates of Boolean Algebra While proving theorems, certain assumptions are made. These assumptions are known as postulates. A postulate is a statement that is assumed to be true without proof. In Boolean algebra also, there are postulates or laws and theorems. Logical inverse refers to complementation. The complement of 0 is 1, and 1 is 0. Logically, it is represented as an inverter, which is shown below. In general, duality is a principle using which one can obtain a true statement from another by merely interchanging two words. Dual of the Boolean function is obtained by interchanging the logical OR operator with the logical AND operator and zeros with ones. For example, the Boolean expression X + 1 = 1. This expression X + 1 always yields one irrespective of the value of X. The dual of this expression can be obtained by replacing OR with AND, 1 with 0. So, the expression will be X. 0 = 0. There are four postulates or laws used in Boolean algebra. Identity postulate Complement postulate Commutative postulate Distributive postulate Every postulate has two laws based on the principle of duality. Identity Postulate The identity postulate has two expressions. The first expression is X + 0 = X. That is, the sum of a variable, and 0 is the variable itself. This expression is implemented using an OR gate. This postulate can be proved using a Truth table shown below.  When X = 0, 0 + 0 is equal to 0, and when X = 1, 1 + 0 will be 1. As you can see, the output is equal to input X. The second expression is obtained by applying the principle of duality X.1 = X. This expression can be implemented using AND gate. The expression can be verified using a truth table, When X = 0, 0 dot 1 is 0, whereas when X = 1, 1 dot 1 is 1. As you can see, the output equals input, X. Postulates of Boolean Algebra Complement Postulate: The complement postulate states that ORing a variable with its complement always yields a logic 1, that is, X + X’ = 1 This law is implemented using an OR gate. When X equals 0, since X’ is 1, the output will be 1. When X equals 1, the output is 1. Therefore, irrespective of the value of X, the output is always 1. By applying the principle of duality, another law is obtained and given by X.X’ = 0 This law is implemented using AND gate.  As indicated in the truth table, irrespective of input X's value, the output is zero. Commutative Postulate The commutative postulate states that interchanging the order of operands in a Boolean equation does not change its result. For example, X + Y = Y + X. Both LHS and RHS expressions yield the same output. Both expressions can easily be verified using the truth table. When X = 0 and Y = 0, both expressions yield 0. When either of the input is one or both inputs are 1, the output is 1. By changing OR to AND, another law is obtained and is given by, X.Y = Y.X Here, LHS and RHS expressions are implemented using AND gate. When one of the inputs or both of the inputs are 0, the output is 0. When both the inputs are one, the output is 1. This is valid for both LHS and RHS expressions. Example 1: Prove that AB + BC + B’C = AB + C Solution: LHS = AB + BC + B’C AB + C (B + B’) AB + C.1 [B + B’ = 1] AB + C [C. 1 = C] Example 2: Simplify the expression x’ y + x y + x’ y’ + y’ x Solution: LHS = x’ y + x y+ x’ y’ + y’ x y (x’ + x) + x’ y’ + y’ x y (1)+ x’ y’ + y’ x[x’ + x = 1] y + x’ y’ + y’ x [y.1 = y] y + y’ (x’ + x) y + y’ (1)[x’ + x = 1] y + y’[y’.1 = y’] 1 [y + y’ = 1] Postulates of Boolean Algebra: Part 3 Distributive Postulate The distributive law states that ORing several variables and ANDing the result with a single variable is equivalent to ANDing the result with a single variable with each of the several variables and then ORing the products.  For example, X. (Y + Z) = X.Y+ X.Z The left-hand side of the expression is implemented using one OR gate and one AND gate The right-hand side of the expression is implemented using two AND gates and one OR gate. The second one is obtained by applying the principle of duality. That is, by changing OR to AND, AND to OR. Introduction to Boolean Algebra A computer consists of several logic circuits, which will help process the data. Each logic circuit represents one or more logic functions that are implemented using logic circuit elements. Boolean algebra is one of the techniques that are useful while simplifying and analyzing logic functions. Boolean algebra is the branch of algebra in which the values of the variables are the truth values. It is much simpler than general algebra as it deals with only two binary bits, 0 and 1. Boolean algebra is also known as the algebra of logic or switching algebra. This well-known algebra deals with the rules by which logical operations are carried out. A digital circuit is represented by a set of input and output symbols, and the function is expressed as a set of Boolean relationships between these symbols. Boolean algebra is supported by several postulates and theorems that help simplify Boolean functions. The basic operations of Boolean algebra are conjunction, disjunction, and negation. These Boolean operations are expressed with the corresponding binary operators AND, OR, and the unary operator NOT, and these are collectively referred to as Boolean operators. Important Boolean Algebra Terms The following are terms that are used in Boolean algebra. Boolean Value Boolean variables hold values that are known as Boolean values or truth values. The Boolean value can be either true or false. In binary notation. Binary number 1 denotes TRUE value, whereas binary 0 denotes FALSE value. The Boolean function describes how the Boolean output is derived from Boolean inputs. Arguments and results of a Boolean function assume values from a two-element set, zero and one. For example, F(X,Y) = X’Y F(X, Y) is a function of two Boolean variables X and Y, and X, Y can assume values 0 or 1. Since there are two variables, four combinations of inputs are possible. The right-hand side of the Boolean function is the Boolean expression. Boolean expression is a logical statement that can yield either a TRUE or False value.  Boolean expression is obtained by combining binary variables, the constants 0 and 1, and logical operators, AND, OR, and NOT operators. For example, F(X, Y) = 1 + X. Y+ Y’ F(X, Y) is the Boolean function with two variables X and Y. 1 is a constant. Dot is an AND operator. Plus is an OR operator. And finally, a dash is a NOT operator. Usually, the dot is not written while writing the Boolean expression. Truth Table A truth table is a table that shows the relationship between inputs and outputs. For example, F(X, Y) is a function with two variables, X and Y, and the Boolean expression is given by F(X,Y) =XY + Y’. Since there are two variables, four input combinations are possible, that is 00, 01, 10, and 11. The function produces Logic 1 only when X AND Y is 1 or Y’ is one. The Rule of Precedence Consider the following example, where Boolean expression is expressed using three variables X, Y, and Z. F(X,Y, Z) = XY + Y (X’ + Z) In Boolean algebra, the precedence rule is also needed to avoid ambiguity in the simplification.. Following is the precedence order: 1. Brackets 2. NOT 3. AND 4. OR Tautology and Fallacy If the result of a Boolean expression is always TRUE or 1, it is called a tautology. If the result of a Boolean expression is always FALSE or 0, it is called a fallacy. BCD and ASCII Code Computer processes the data which is in the form of text, image, number, audio, or video. These are represented, collected, stored, and transmitted using a group of symbols called binary codes. BCD code, ASCII code, Excess-3 Code, and Gray code are some of the important codes used in a computer system. BCD Code The full form of BCD is binary coded decimal. In this code, each decimal digit in a number is coded with four binary bits. Hence, this code is also known as 8421 code Notice that there is no difference between binary and BCD codes for numbers from 0 to 9. The binary equivalent of decimal 10 is 1010, but the same code cannot be used as BCD code. While writing BCD code for decimal 10, each digit is coded separately. That is, the BCD code for 1 is 0001, and for 0, it is 0000. Example: Convert decimal number 345 to BCD. BCD representation of 3 is 0011, 4 is 0100, and 5 is 0101. 3 4 5 -> 0011 0100 0101 To convert BCD to decimal, make four bits group from LSB and then convert it to decimal. Example: Convert BCD number 0111 0101 1001 to decimal. 0111 is 7, 0101 is 5, and 1001 is 9. 0111 0101 1001 -> 7 5 9  Most modern computers use byte-oriented memory, in a sense, each location of the memory is capable of storing 1 byte or 8 bits of information. Based on how many digits can be accommodated in each location, there are two types: ○ 1) unpacked BCD ○ 2) packed BCD. In unpacked BCD representation, one BCD digit per byte is used. For example, to represent 48, 2 bytes are needed. Digit 8 is represented using two nibbles. The lower nibble is 1000, and the upper nibble is set to all zeros. Similarly, 4 is represented using two nibbles. The lower nibble is 0100, and the upper nibble is set to all zeros. In both bytes, the upper nibble is redundant. It is as good as representing 0408 in BCD. To utilize memory efficiently, packed BCD representation is used. In this method, in one byte of memory, two digits are packed. For example, decimal number 48, where 8 is represented as 1000 and is stored in the lower nibble and 4 is represented as 0100 is stored in the upper nibble. ASCII Code Another very popular code that is used in every digital computer and internet is ASCII, i.e., American Standard Code for Information Interchange. This code is developed by American National Standards Institute, ANSI. ASCII provides a character encoding format for text data, which is represented by eight bits. Out of these eight bits, the lower seven bits are used to represent the code, and most significant bit is used as a parity bit.  This parity bit is used to indicate a single-bit error in the code. Characters in ASCII encoding include uppercase and lowercase letters A through Z, numerals 0 through 9, and basic punctuation symbols. BCD Arithmetic BCD Addition Procedure for the addition of two BCD numbers: Add the two BCD numbers (binary addition). If 4-bit result is equal to or less than 9, then it is a valid BCD number. If 4-bit result is greater than 9 or if there is a carry out of the 4-bit then add 6 (0110) to the result. If there is a carry generated after addition, then simply add that carry to the next BCD bit group. Example: Find the sum of two BCD numbers A and B, where: A = 0011 1001 0101 = (3 9 5)10 B = 0100 0001 0011 = (4 1 3)10  When two BCD numbers are added, the result obtained should be equivalent to decimal number eight hundred and eight. Start from the lower nibble. Add first nibbles. The result obtained is 1000, which is equal to 8 in decimal and is less than 9. Hence, it is a valid BCD number. Add second nibbles, and the result obtained is 1010, which is equal to 10 in decimal. Since 10 is greater than 9, it is not a valid BCD number. Now, add 0110 to 1010. The answer obtained is 0000 with carry 1. 0000 is a valid BCD number. The carry that is generated should be added to the next nibble. Add the last nibbles with carry, and the result obtained is 1000. 1000 is equal to 8 in decimal and is less than 9. Hence, it is a valid BCD number. The final result obtained is 1000 0000 1000, which is equivalent to 808(10). BCD Subtraction While performing binary subtraction, 2’s complement operation is used. Similarly, in BCD subtraction, 10’s complement is used. 10’s complement is 9’s complement + 1. Example 1: Obtain 10’s complement of BCD number 432. First, find out 9’s complement by subtracting each BCD digit by 9. Then, add 1 to it to get 10’s complement. 999 (-)432 567 ⇒ 9’s complement (+) 1 568 ⇒ 10’s complement Example 2: Perform A - B where A = 475 and B = 239. BCD representation of A ⇒ 0100 0111 0101 BCD representation of B ⇒ 0010 0011 1001 Represent -B using 10’s complement.  9’s complement 999 ⇒ 1001 1001 1001 BCD number (-) 239 ⇒ (-) 0010 0011 1001 760⇒ 0111 0110 0000 10’s complement (+) 1 ⇒ 761 761 ⇒ 0111 0110 0001 Now add A and -B. A ⇒ 0100 0111 0101 -B ⇒ 0111 0110 0001 0010 0011 0110 ⇒ 236 Half Subtractor Subtractor is a combinational circuit that is used to perform the subtraction of two bits. Similar to the adder, the main application of the Subtractor is in ALU. It is also used while accessing the table, computing memory addresses, etc. There are two types of Subtractors. 1)Half Subtractor 2) Full Subtractor. For example, while performing X-Y, the subtractor accepts two inputs, X and Y, where X is minuend and Y is subtrahend. It produces two outputs, B and D, where B is a borrow and D is a difference. While designing the half subtractor, four steps are followed. Step 1: Identify the input and output variables. Two input variables, X and Y, can take truth values 0 or 1. Two output variables, Difference D and Borrow B. Both D and B can be 0 or 1. Step 2: Draw the Truth Table. Above Figure shows the truth table of a half subtractor. When X = 0, Y = 0, the difference D is 0, and borrow B is 0. When X = 0, Y = 1, D is 1, with a B equals 1. When X = 1, Y = 0, D is 1 and B is 0. When X = 1, Y = 1, D is 0 and B is 0. Step 3: Determine the Boolean expression. B output is 1 only when X = 0 and Y = 1. This can be expressed as,  B = X’Y. Difference D output is at one for two input combinations. That is, when X = 0, Y= 1, and when X= 1, Y= 0. The behavior of the D output is the same as that of an EXOR gate. So, the Boolean expression for D output is, D =X⊕Y. Step 4: Draw the logic circuit. Above Figure shows the logic circuit of a half subtractor. Implementation of a half subtractor requires three gates. The output of the exclusive OR gate is D output. The borrow part of the subtractor is implemented using NOT and AND gates. Like a half adder, a half subtractor is also designed to work with two single bits. Hence, it is not suitable for implementing a multi-bit subtractor where we need to consider the borrow part as well. Full Subtractor A full subtractor is a combinational circuit designed to eliminate the limitation of a half subtractor. It has three inputs and two outputs. A full subtractor, shown in below, is designed in four steps. Step 1: Identify the input and output variables.. X and Y are the two input variables. X is minuend and Y is subtrahend.  The third input is a borrow, Bin, which is generated during the subtraction operation on the previous least significant bits. D and Bout are two outputs generated by the subtractor. D is the difference output generated as a result of X – Y – Bin. Bout is the borrow output. Step 2: Draw a truth table. Bout and Sum for different values of X, Y, and Bin are shown below. In the truth table, three columns are for inputs X, Y, and Bin, and two columns are for outputs D and Bout. When X = 0, Y = 0 and Bin = 0, D = 0.Since the borrow is not taken, Bout is zero. When X = 0, Y = 0, and Bin = 1, to compute D, we perform X-Y- Bin, that is, 0 – 0 – 1.This results in a difference D = 1 with the help of borrow. Hence, Bout is equal to 1. When X = 0, Y = 1 and Bin = 0, D = 1. In this case also a borrow is taken. Hence, Bout is 1. When X = 0, Y = 1 and Bin = 1, D = 0 and Bout =1. Bout and sum for other values of X, Y, and Bin are shown below. Step 3. Determine the Boolean expression for Bout and D. Since there are three inputs, three variables K-Map is used for simplification. For Bout, m3, m5, m6, and m7 are the minterms and their position in the K-Map is as shown  Boolean expression for Bout is given by, Bout = X’Bin + X’Y + YBin For D output, minterms are m1, m2, m4, and m7. The K-Map for D output is shown. There will be four terms and each term will have all three variables.The final expression forD output is, D= XY’Bin’ + X’Y’Bin + XYBin + X’YBin’ D = X⊕ Y ⊕Bin Step 4: Draw a logic diagram. The logic circuit implementation of full adder is shown below. To implement Bout, 2 NOT gates, 3 AND gates, and one OR gate is needed, whereas to implement D, three input XOR gate is needed. Magnitude Comparator A magnitude comparator is a combinational circuit that takes two numbers as input in binary form and determines whether one number is greater than, less than, or equal to another number. The device has two inputs and three outputs.Below Figure shows a 1-bit magnitude comparator.. The design requires four steps to follow. Step 1: Identify the input and output variables. There are two input variables, X and Y, and three output variables, X>Y, XY is 1 when X = 1 and Y = 0. For other combinations of X and Y, the output X>Y is 0. The output X=Y is 1 when X and Y are the same. The XY output is 1 for X = 1 and Y = 0. The Boolean expression is X>Y = XY’. The output is X = Y is 1 when X and Y are zero, and X and Y are 1. So, the Boolean expression is given X=Y => (X’Y’ + XY). The output X Y function is implemented using NOT and AND gates. NOT gate is used to complement Y input. The logic diagram for X=Y output uses two AND gates, two NOT gates, and one OR gate. The output of the first AND gate is X’Y’. The output of the second AND gate is XY. Finally, the OR gate gives X’Y’ + XY. The logic diagram is for X