Computer Organization and Architecture PDF

Computer Organization and Architecture COMPUTER ORGANIZATION AND ARCHITECTURE MODULE 1 DIGITAL COMPUTERS 1.1 INTRODUCTION The digital computer is a digital system that performs various computational ta...

Computer Organization and Architecture COMPUTER ORGANIZATION AND ARCHITECTURE MODULE 1 DIGITAL COMPUTERS 1.1 INTRODUCTION The digital computer is a digital system that performs various computational tasks. The word digital implies that the information in the computer is represented by variables that take a limited number of discrete values. These values are processed internally by components that can maintain a limited number of discrete states. The decimal digits 0, 1, 2,..., 9, for example, provide 10 discrete values. The first electronic digital computer was developed in the late 1940s and was used primarily for numerical computations. Digital computers use the binary number system, which has two digits: o and 1. A Binary digit is called a bit. In computers, information is represented in “Group of bits”. 1.1.1 COMPUTER SYSTEM A computer system is sometimes subdivided into two functional entities: Hardware Software Hardware: The hardware of the computer consists of all the electronic components and electromechanical devices that comprise the physical entity of the device. The hardware of the computer is usually divided into three major parts, as shown in Fig. 1-1. The Central Processing Unit (CPU) contains an arithmetic and logic unit for manipulating data, a number of registers for storing data, and control circuits for fetching and executing instructions. The memory of a computer contains storage for instructions and data. It is called a Random-Access Memory (RAM) because the CPU can access any location in memory at random and retrieve the binary information within a fixed interval of time. The Input and Output Processor (IOP) contains electronic circuits for communicating and controlling the transfer of information between the computer and the outside world. School of Engineering and Technology, Sapthagiri NPS University Page 1 Computer Organization and Architecture The input and output devices connected to the computer include keyboards, printers, terminals, magnetic disk drives, and other communication devices. Figure 1.1 - Block diagram of a digital computer Software: Computer software consists of the instructions and data that the computer manipulates to perform various data-processing tasks. The system software of a computer consists of a collection of programs whose purpose is to make more effective use of the computer. The programs included in a systems software package are referred to as the Operating System. Application Software: It is software that performs specific tasks for an end-user. For example, A High-level language program written by user to solve particular data processing needs is an Application Program. The compiler that translates the high-level language program to machine language is a System Program. 1.1.2 COMPUTER ORGANIZATION Computer Organization is concerned with the way the hardware components operate and the way they are connected together to form the computer system. The various components are assumed to be in place and the task is to investigate the organizational structure to verify that the computer parts operate as intended. 1.1.3 COMPUTER DESIGN Computer Design is concerned with the hardware design of the computer. Once the computer specifications are formulated, it is the task of the designer to develop hardware for the system. School of Engineering and Technology, Sapthagiri NPS University Page 2 Computer Organization and Architecture 1.1.4 COMPUTER ARCHITECTURE Computer Architecture is concerned with the structure and behaviour of the computer as seen by the user. It includes the information formats, the instruction set, and techniques for addressing memory. The Architectural Design of a computer system is concerned with the specifications of the various functional modules, such as processors and memories, and structuring them together into a computer system. 1.2 DATA REPRESENTATION: It refers to the form in which data is stored, processed, and transmitted. Devices such as smartphones, iPods, and computers store data in digital formats that can be handled by electronic circuitry (motherboard). It refers to the symbols that represent people, events, things, and ideas. Data can be a name, a number, the colors in a photograph, or the notes in a musical composition. The term “data” refers to factual information used for analysis or reasoning. Registers are made up of flip-flops and flip-flops are two-state devices that can store only 1’s and 0’s. There are many methods or techniques which can be used to convert numbers from one base to another. Decimal to Other Base System Other Base System to Decimal Other Base System to Non-Decimal Shortcut method−Binary to Octal Shortcut method−Octal to Binary Shortcut method−Binary to Hexadecimal Shortcut method−Hexadecimal to Binary School of Engineering and Technology, Sapthagiri NPS University Page 3 Computer Organization and Architecture Decimal to Other Base System Steps Step1 −Divide the decimal number to be converted by the value of the new base. Step 2− Get the remainder from Step 1 as the rightmost digit (least significant digit) of new base number. Step3−Divide the quotient of the previous divides by the new base. Step4−Record the remainder from Step3 as the next digit (to the left ) of the new base number. Repeat Steps 3 and 4, getting remainders from right to left, until the quotient becomes zero in Step 3. The last remainder thus obtained will be the Most Significant Digit (MSD) of the new base number. Example: Decimal number: 2910 Calculating Binary Equivalent As mentioned in Steps 2 and 4, the remainders have to be arranged in the reverse order so that the first remainder becomes the Least Significant Digit (LSD) and the last remainder becomes the Most Significant Digit (MSD). Decimal number : 2910 Binary number : 111012 Other Base System to Decimal System Steps Step 1− Determine the column (positional) value of each digit (this depends on the position of the digit and the base of the number system). Step2−Multiply the obtained column values (inStep1) by the digits in the School of Engineering and Technology, Sapthagiri NPS University Page 4 Computer Organization and Architecture corresponding columns. Step3−Sum the products calculated in Step2.The total is the equivalent value in decimal. Example Binary Number – 111012 Calculating Decimal Equivalent− Binary Number−111012=Decimal Number−29 10 Other Base System to Non-Decimal System Steps: Step 1: Convert the original number to a decimal number (base10). Step 2 : Convert the decimal number obtained to the new base number. Example Octal Number−258 Calculating Binary Equivalent− Step 1 − Convert to Decimal Octal Number−258=Decimal Number−2110 Step 2 – Convert Decimal to Binary School of Engineering and Technology, Sapthagiri NPS University Page 5 Computer Organization and Architecture Decimal Number−2110=Binary Number−101012 Octal Number − 258= Binary Number – 101012 Shortcut method –Binary to Octal Steps: Step1−Divide the binary digits in to groups of three (starting from the right). Step2−Convert each group of three binary digits to one octal digit. Example Binary Number − 10101 Calculating Octal Equivalent – Binary Number−101012 = Octal Number – 258 Shortcut method-Octal to Binary Steps Step 1− Convert each octal digit to a 3 digit binary number (the octal digits may be treated as decimal for this conversion). Step 2− Combine all the resulting binary groups (of 3 digits each) into a single binary number. Example Octal Number−258 Calculating Binary Equivalent− School of Engineering and Technology, Sapthagiri NPS University Page 6 Computer Organization and Architecture Octal Number − 258 = Binary Number − 101012 Shortcut method – Binary to Hexadecimal Steps Step1 − Divide the binary digits into groups of four (starting from the right). Step2 − Convert each group of four binary digits to one hexadecimal symbol. Example Binary Number−101012 Calculating hexadecimal Equivalent− Binary Number −101012 = Hexadecimal Number−1516 Shortcut method – Hexadecimal to Binary Steps Step 1− Convert each hexadecimal digit to a 4 digit binary number (the hexadecimal digits may be treated as decimal for this conversion). Step 2− Combine all the resulting binary groups (of 4 digits each) into a single binary number. Example Hexadecimal Number – 1516 School of Engineering and Technology, Sapthagiri NPS University Page 7 Computer Organization and Architecture 1.2.1 DATA TYPES: The data types found in the registers of digital computers may be classified as being one of the following categories: 1. Numbers used in arithmetic computation, 2. Letters of the alphabet used in data processing, 3. Other discrete symbols used for specific purposes. Data are numbers and other binary-coded information that are operated on to achieve required computational results. All types of data, except binary numbers, are represented in binary-coded form. 1.2.2 COMPLEMENTS Complements are used in the digital computers in order to simplify the subtraction operation and for the logical manipulations. For each radix-r system (radix r represents base of number system) there are two types of complements. School of Engineering and Technology, Sapthagiri NPS University Page 8 Computer Organization and Architecture As the binary system has base r = 2. So the two types of complements for the binary system are 2's complement and 1's complement. 1's complement The 1's complement of a number is found by changing all 1's to 0's and all 0's to 1's. This is called as taking complement or 1's complement. For example: +9 will be represented as 00001001 in eight-bit notation and -9 will be represented as 11110110, which is the 1’s complement of 00001001. Example 2's complement The 2's complement of binary number is obtained by adding 1 to the Least Significant Bit (LSB) of 1's complement of the number. 2's complement = 1's complement + 1 Example of 2's Complement is as follows School of Engineering and Technology, Sapthagiri NPS University Page 9 Computer Organization and Architecture Binary Arithmetic Binary arithmetic is essential part of all the digital computers and much other digital system. School of Engineering and Technology, Sapthagiri NPS University Page 10 Computer Organization and Architecture Binary Multiplication 1.2.3 FIXED POINT REPRESENTATION Positive integers and zero can be represented by unsigned numbers Negative numbers must be represented by signed numbers since + and – signs are School of Engineering and Technology, Sapthagiri NPS University Page 11 Computer Organization and Architecture not available, only 1’s and 0’s are Signed numbers have msb as 0 for positive and 1 for negative – msb is the sign bit Two ways to designate binary point position in a register ❖ Fixed point position ❖ Floating-point representation Fixed point position usually uses one of the two following positions ❖ A binary point in the extreme left of the register to make it a fraction ❖ A binary point in the extreme right of the register to make it an integer ❖ In both cases, a binary point is not actually present The floating-point representations uses a second register to designate the position of the binary point in the first register When an integer is positive, the msb, or sign bit, is 0 and the remaining bits represent the magnitude When an integer is negative, the msb, or sign bit, is 1, but the rest of the number can be represented in one of three ways ❖ Signed-magnitude representation ❖ Signed-1’s complement representation ❖ Signed-2’s complement representation Consider an 8-bit register and the number +14 the only way to represent it is 00001110 Consider an 8-bit register and the number –14 ❖ Signed magnitude: 1 0001110 ❖ Signed 1’s complement: 1 1110001 ❖ Signed 2’s complement: 1 1110010 Typically use signed 2’s complement Addition of two signed-magnitude numbers follow the normal rules ❖ If same signs, add the two magnitudes and use the common sign ❖ Differing signs, subtract the smaller from the larger and use the sign of the ❖ larger magnitude ❖ Must compare the signs and magnitudes and then either add or subtract Addition of two signed 2’s complement numbers does not require a comparison or Subtraction – only addition and complementation School of Engineering and Technology, Sapthagiri NPS University Page 12 Computer Organization and Architecture ❖ Add the two numbers, including their sign bits ❖ Discard any carry out of the sign bit position ❖ All negative numbers must be in the 2’s complement form If the sum obtained is negative, then it is in 2’s complement form Subtraction of two signed 2’s complement numbers is as follows ❖ Take the 2’s complement form of the subtrahend (including sign bit) ❖ Add it to the minuend (including the sign bit) ❖ A carry out of the sign bit position is discarded An overflow occurs when two numbers of n digits each are added and the sum occupies n + 1 digits Overflows are problems since the width of a register is finite Therefore, a flag is set if this occurs and can be checked by the user Detection of an overflow depends on if the numbers are signed or unsigned For unsigned numbers, an overflow is detected from the end carry out of the msb For addition of signed numbers, an overflow cannot occur if one is positive and one is negative both have to have the same sign An overflow can be detected if the carry into the sign bit position and the carry out of the sign bit position are not equal The representation of decimal numbers in registers is a function of the binary code used to represent a decimal digit A 4-bit decimal code requires four flip-flops for each decimal digit This takes much more space than the equivalent binary representation and the circuits required to perform decimal arithmetic are more complex School of Engineering and Technology, Sapthagiri NPS University Page 13 Computer Organization and Architecture Representation of signed decimal numbers in BCD is similar to the representation of signed numbers in binary Either signed magnitude or signed complement systems The sign of a number is represented with four bits ❖ 0000 for + ❖ 1001 for – To obtain the 10’s complement of a BCD number, first take the 9’s complement and then add one to the least significant digit Example: (+375) + (-240) = +135 1.2.4 FLOATING POINT REPRESENTATION The floating-point representation of a number has two parts ❖ The first part represents a signed, fixed-point number – the mantissa ❖ The second part designates the position of the binary point – the exponent ❖ The mantissa may be a fraction or an integer Example: the decimal number +6132.789 is ❖ Fraction: +0.6123789 ❖ Exponent: +04 ❖ Equivalent to +0.6132789 x 10+4 A floating-point number is always interpreted to represent m x r Example: the binary number +1001.11 (with 8-bit fraction and 6-bit exponent) ❖ Fraction: 01001110 ❖ Exponent: 000100 ❖ Equivalent to +(.1001110)2 x 2+4 A floating-point number is said to be normalized if the most significant digit of the mantissa is nonzero The decimal number 350 is normalized, 00350 is not The 8-bit number 00011010 is not normalized School of Engineering and Technology, Sapthagiri NPS University Page 14 Computer Organization and Architecture Normalize it by fraction = 11010000 and exponent = -3 Normalized numbers provide the maximum possible precision for the floating- point number. Other Alphanumeric codes: EBCDIC In 1964, BCD was extended to an 8-bit code, Extended Binary-Coded Decimal Interchange Code (EBCDIC). EBCDIC was one of the first widely-used computer codes that supported upper and lowercase alphabetic characters, in addition to special characters, such as punctuation and control characters. EBCDIC and BCD are still in use by IBM mainframes today. ASCII ASCII: American Standard Code for Information Interchange. In 1967, a derivative of this alphabet became the official standard that we now call ASCII. Unicode Both EBCDIC and ASCII were built around the Latin alphabet. In 1991, a new international information exchange code called Unicode. Unicode is a 16-bit alphabet that is downward compatible with ASCII and Latin-1 character set. School of Engineering and Technology, Sapthagiri NPS University Page 15 Computer Organization and Architecture Because the base coding of Unicode is 16 bits, it has the capacity to encode the majority of characters used in every language of the world. Unicode is currently the default character set of the Java programming language. Table - Unicode Codespace The Unicode codespace is divided into six parts. The first part is for Western alphabet codes, including English, Greek, and Russian. The lowest-numbered Unicode characters comprise the ASCII code. The highest provide for user-defined codes. Error Detection and Correction Codes No communications channel or storage medium can be completely error-free. Cyclic Redundancy Check: Cyclic redundancy check (CRC) is a type of checksum used primarily in data communications that determines whether an error has occurred within a large block or stream of information bytes. Arithmetic Modulo 2The rules are as follows: 0+0=0 0+1=1 1+0=1 1+1=0 1.3 COMPUTER ARITHMETIC Arithmetic instructions in digital computers manipulate data to produce results necessary for the solution of computational problems. These instructions perform arithmetic calculations and are responsible for the bulk of activity involved in processing data in a computer. The four basic arithmetic operations are addition, subtraction, multiplication, and division. School of Engineering and Technology, Sapthagiri NPS University Page 16 Computer Organization and Architecture The arithmetic operation in the digital computer manipulate data to produce results. It is necessary to design arithmetic procedures and circuits to program arithmetic operations using algorithm. The algorithm is a solution to any problem and it is stated by a finite number of well-defined procedural steps. The algorithms can be developed for the following types of data. 1. Fixed point binary data in signed magnitude representation 2. Fixed point binary data in signed 2’s complement representation. 3. Floating point representation 4. Binary Coded Decimal (BCD) data 1.3.1 ADDITION AND SUBTRACTION WITH SIGNED MAGNITUDE Consider two numbers having magnitude A and B. When the signed numbers are added or subtracted, there can be 8 different conditions depending on the sign and the operation performed as shown in the table below: From the table, we can derive an algorithm for addition and subtraction as follows: Addition (Subtraction) Algorithm: When the signs of A & B are identical, add the two magnitudes and attach the sign of A to the result. School of Engineering and Technology, Sapthagiri NPS University Page 17  Computer Organization and Architecture When the sign of A & B are different, compare the magnitude and subtract the smaller number from the large number. Choose the sign of the result to be same as A if A > B, or the complement of the sign of A if A < B. If the two numbers are equal, subtract B from A and make the sign of the result positive. Figure 1.2 - Hardware for signed magnitude addition and subtraction The hardware consists of two registers A and B to store the magnitudes, and two flipflops As and Bs to store the corresponding signs. The results can be stored in the register A and As which acts as an accumulator. The subtraction is performed by adding A to the 2’s complement of B. The output carry is transferred to the flip-flop E. The overflow may occur during the add operation which is stored in the flip-flop When m = 0, the output of E is transferred to the adder without any change along with the input carry of ‘0". The output of the parallel adder is equal to A + B which is an add operation. When m = 1, the content of register B is complemented and transferred to parallel adder along with the input carry of 1. Therefore, the output of parallel is equal to A + B’ + 1 = A – B which is a subtract operation. Hardware Algorithm As and Bs are compared by an exclusive-OR gate. If output=0, signs are identical, if 1 signs are different. For Add operation, identical signs dictate addition of magnitudes and for operation identical signs dictate addition of magnitudes and for subtraction, different magnitudes dictate magnitudes be added. Magnitudes are added with a micro-operation EA. School of Engineering and Technology, Sapthagiri NPS University Page 18 Computer Organization and Architecture Two magnitudes are subtracted if signs are different for add operation and identical for subtract operation. Magnitudes are subtracted with a micro-operation EA = B and number (this number is checked again for 0 to make positive 0 [As=0]) in A is correct result. E = 0 indicates A < B, so we take 2’s complement of A. Figure 1.3 - Flowchart for add and subtract operations 1.3.2 MULTIPLICATION Hardware Implementation and Algorithm Generally, the multiplication of two final point binary number in signed magnitude representation is performed by a process of successive shift and ADD operation. The process consists of looking at the successive bits of the multiplier (least significant bit first). If the multiplier is 1, then the multiplicand is copied down otherwise, 0’s are School of Engineering and Technology, Sapthagiri NPS University Page 19 Computer Organization and Architecture copied. The numbers copied down in successive lines are shifted one position to the left and finally, all the numbers are added to get the product. But, in digital computers, an adder for the summation (∑) of only two binary numbers are used and the partial product is accumulated in register. Similarly, instead of shifting the multiplicand to the left, the partial product is shifted to the right. The hardware for the multiplication of signed magnitude data is shown in the figure below. Figure 1.4 - Hardware for multiply operation Initially, the multiplier is stored q register and the multiplicand in the B register. A register is used to store the partial product and the sequence counter (SC) is set to a number equal to the number of bits in the multiplier. The sum of A and B form the partial product and both shifted to the right using a statement “Shr EAQ” as shown in the hardware algorithm. The flip flops As, Bs & Qs store the sign of A, B & Q respectively. A binary ‘0” inserted into the flip-flop E during the shift right. Hardware Algorithm School of Engineering and Technology, Sapthagiri NPS University Page 20 Computer Organization and Architecture Figure 1.5 -Flowchart for multiply algorithm Booth Algorithm The algorithm that is used to multiply binary integers in signed 2’s complement form is called booth multiplication algorithm. It works on the principle that the string 0’s in the multiplier doesn’t need addition but just the shifting and the sting of 1’s from bit weight 2k to 2m can be treated as 2k+1 – 2m (Example, +14 = 001110 = 23=1 – 21 = 14). The product can be obtained by shifting the binary multiplication to the left and subtraction the multiplier shifted left once. According to booth algorithm, the rule for multiplication of binary integers in signed 2’s complement form are: The multiplicand is subtracted from the partial product of the first least significant bit is 1 in a string of 1’s in the multiplicand. The multiplicand is added to the partial product if the first least significant bit is 0 (provided that there was a previous 1) in a string of 0’s in the multiplier. The partial product doesn’t change when the multiplier bit is identical to the previous multiplier bit. School of Engineering and Technology, Sapthagiri NPS University Page 21 Computer Organization and Architecture This algorithm is used for both the positive and negative numbers in signed 2’s complement form. The hardware implementation of this algorithm is in figure below: Figure 1.6 - Hardware for Booth algorithm. The flowchart for booth multiplication algorithm is given below: Figure 1.7 - Booth algorithm for multiplication of signed,2's complement numbers. Numerical Example: Booth algorithm BR=10111(Multiplicand) QR=10011(Multiplier) School of Engineering and Technology, Sapthagiri NPS University Page 22 Computer Organization and Architecture Array Multiplier The multiplication algorithm first check the bits of the multiplier one at time and form partial product. This is a sequential process that requires a sequence of add and shift micro-operation. This method is complicated and time consuming. The multiplication of 2 binary numbers can also be done with one micro-operation by using combinational circuit that provides the product all at once. Example: Consider that the multiplicand bits are b1 and b0 and the multiplier bits are a1 and a0. The partial product is c3c2c1c0. The multiplication two bits a0 and a1 produces a binary 1 if both the bits are 1, otherwise it produces a binary 0. This is identical to the AND operation and can be implemented with the AND gates as shown in figure. Figure 1.8 - 2-bit by 2-bit array multiplier 1.3.3 DIVISION ALGORITHM The division of two fixed point signed numbers can be done by a process of successive compare shift and subtraction. When it is implemented in digital computers, instead of shifting the divisor to the right, the dividend or the partial remainder is shifted to the left. The subtraction can be obtained by adding the number A to the 2’s complement of number B. The information about the relative magnitudes of the information about the relative magnitudes of numbers can be obtained from the end carry. School of Engineering and Technology, Sapthagiri NPS University Page 23 Computer Organization and Architecture The divisor is stored in register B and a double length dividend is stored in register A and Q. the dividend is shifted to the left and the divider is subtracted by adding twice complement of the value. If E = 1, then A >= B. In this case, a quotient bit 1 is inserted into Qn and the partial remainder is shifted to the left to repeat the process. If E = 0, then A > B. In this case, the quotient bit Qn remains zero and the value of B is added to restore the partial remainder in A to the previous value. The partial remainder is shifted to the left and approaches continues until the sequence counter reaches to 0. The registers E, A & Q are shifted to the left with 0 inserted into Qn and the previous value of E is lost as shown in the flow chart for division Algorithm. Figure 1.9 - Flowchart for divide operation This algorithm can be explained with the help of an example. Consider that the divisor is 10001 and the dividend is 01110. School of Engineering and Technology, Sapthagiri NPS University Page 24 Computer Organization and Architecture Figure 1.10 - Example of binary division with digital hardware Arithmetic Operations on Floating-Point Numbers The rules apply to the single-precision IEEE standard format. These rules specify only the major steps needed to perform the four operations. Intermediate results for both mantissas and exponents might require more than 24 and 8 bits, respectively & overflow or an underflow may occur. These and other aspects of the operations must be carefully considered in designing an arithmetic unit that meets the standard. If their exponents differ, the mantissas of floating-point numbers must be shifted with respect to each other before they are added or subtracted. Consider a decimal example in which we wish to add 2.9400 x to 4.3100 x. We rewrite 2.9400 x as 0.0294 x and then perform addition of the mantissas to get 4.3394 x. The rule for addition and subtraction can be stated as follows: Add/Subtract Rule The steps in addition (FA) or subtraction (FS) of floating-point numbers (s1, eˆ, f1) fad {s2, eˆ 2, f2) are as follows. 1. Unpack sign, exponent, and fraction fields. Handle special operands such as zero, infinity, or NaN(not a number). 2. Shift the significand of the number with the smaller exponent right by bits. School of Engineering and Technology, Sapthagiri NPS University Page 25 Computer Organization and Architecture 3. Set the result exponent er to max (e1, e2). 4. If the instruction is FA and s1= s2 or if the instruction is FS and s1 ≠ s2 then add the significands; otherwise subtract them. 5. Count the number z of leading zeros. A carry can make z = -1. Shift the result significand left z bits or right 1 bit if z = -1. 6. Round the result significand, and shift right and adjust z if there is rounding overflow, which is a carry-out of the leftmost digit upon rounding. 7. Adjust the result exponent by er = er - z, check for overflow or underflow, and pack the result sign, biased exponent, and fraction bits into the result word. Multiplication and division are somewhat easier than addition and subtraction, in that no alignment of mantissas is needed. Decimal Arithmetic Unit Decimal arithmetic unit refers to a digital function that does decimal micro-operations. This function adds or subtracts decimal numbers by forming 9’s or 10’s complement of the subtrahend. This decimal arithmetic unit first accepts coded decimal numbers and then generates output in the binary form. Since four bits are necessary to represent every coded decimal digit, a single stage decimal arithmetic unit comprises nine binary input variables and five binary output variables. Every stage has to comprise four sets of input for the augend digit, four sets of input for the addend digit, and an input-carry. The output comprises four terminals for the sum digit and one for the output-carry. School of Engineering and Technology, Sapthagiri NPS University Page 26 Computer Organization and Architecture BCD Adder BCD adder refers to a 4-bit binary adder that can add two 4-bit words of BCD format. The output of the addition is a BCD-format 4-bit output word, which represents the decimal sum of the addend and augend and a carry that is generated in case this sum exceeds a decimal value of 9. Therefore, BCD adders can perform decimal addition. Let us examine an arithmetic operation consisting of two decimal digits in BCD, along with a possible carry from a previous stage. The output of the arithmetic operation cannot be more that 9 + 9 + 1 = 19, because no input digit exceeds 9. In case two BCD numbers are applied to a 4-bit binary adder, the adder forms the sum in binary and gives an output ranging from 0 to 19. Here, 1 refers to an output carry. Table discusses the construction of a BCD adder, wherein the binary numbers are labelled using symbols K, Z8, Z4, Z2, and Z1. Table 1.1 - Derivation of BCD Adder In the above table, K is the carry. The subscripts below the letter Z represent the weights. The weights, according to the table, are 8, 4, 2, and 1. These weights can be allotted to the four bits in BCD code. The first column contains the binary sum as in the outputs of a 4-bit binary adder. The second column contains of the output sum of two decimal numbers that is School of Engineering and Technology, Sapthagiri NPS University Page 27 Computer Organization and Architecture represented in BCD. Now, a simple rule is essential to convert the binary numbers in the first column to the correct BCD digit representation in the second column. It is evident from table 10.1 that if the binary sum is less than or equal to 1001, then the corresponding BCD number is identical and therefore, there is no need for conversion. However, in case the binary sum is more than 1001, a non-valid BCD representation is obtained. Therefore, the binary 6 (0110) has to be added to the binary sum to convert it to the correct BCD representation and to produce an output carry. The decimal numbers in BCD are added by employing one 4-bit binary adder and by performing arithmetic operation one digit at a time. To produce a binary sum, first addition is performed on the low-order pair of BCD digits. In case the output is equal to or greater than 1010, it can be set right by adding 0110 to the binary sum. This would produce an output-carry automatically for the next pair of significant numbers. Then, the subsequent high-order pair of numbers along with input-carry is added to produce their binary sum. In case this output is greater than or equal to 1010, it is set right by adding 0110. This process is repeated until every decimal digit is added. The entries in table 10.1 help derive the logic circuit that detects the required corrections. When the binary sum has an output carry K = 1, a correction is required. The other six combinations starting from 1010 to 1111 that require corrections have a 1 in position Z8. To differentiate them from binary 1000 and 1001, which also have a 1 in position Z8 , it is specified that either Z4 or Z2 must have a 1. The following Boolean function is used to express the condition for a correction and an output carry: In case C = 1, 0110 is added to the binary sum and an output-carry is provided for the next stage. School of Engineering and Technology, Sapthagiri NPS University Page 28 Computer Organization and Architecture Figure below depicts a BCD adder circuit to add two BCD numbers in parallel and to produce a sum digit, which is also in BCD. The internal construction of the BCD adder must include the correction logic. Figure 1.11 - Block diagram of BCD adder As depicted in figure, a second 4-bit binary adder is used to add 0110. To produce the binary sum, the two decimal digits along with the input-carry are added in the top 4-bit binary adder. In case the output-carry is equal to 0, no binary number is added to the binary sum. However, in case the output-carry is equal to 1, binary number 0110 is added to the binary sum through the 4- bit binary adder on the left side of figure. The output-carry that is generated from the binary adder on the left side of figure can be ignored, because it provides information that is already present in the output-carry terminal. A decimal parallel-adder adding n decimal numbers requires n BCD adder stages along with the output-carry from one stage connected to the input-carry of the next-higher order stage. BCD adders comprise the required circuits for carry look-ahead to achieve shorter propagation delays. It should be noted that the adder circuit for correction may not require all four full- adders. It is also possible to optimize the adder circuits. School of Engineering and Technology, Sapthagiri NPS University Page 29 Computer Organization and Architecture BCD Subtraction A subtractor circuit is required to perform a subtraction operation on two decimal numbers. BCD subtraction is slightly different from BCD addition. Performing subtraction operation by taking the 9’s or 10’s complement of the subtrahend and adding it to the minuend is economical. It is not possible to obtain the 9’s complement by complementing every bit in the code because the BCD is not a self- complementing code. The 9’s complement has to be formed by a circuit that subtracts Notes every BCD number from 9. The 9’s complement of a decimal digit that is represented in BCD can be obtained by complementing the bits in the coded representation of the digit. However, it is essential that a correction is included. There are two methods of correction. They are: 1. First Method: The binary 1010 is added to every complemented digit. The carry is discarded after performing the addition. 2. Second Method: The binary 0110 is added before the digit is complemented. For instance, the 9’s complement of BCD 0111 is calculated by complementing every bit to get 1000. The value 0010 is obtained by adding binary 1010 and ignoring the carry. Using the second method, 0110 and 0111 can be added to obtain 1101. The required output, that is, 0010 can be obtained by complementing every bit. Complementing every bit of a 4-bit binary digit N is the same as subtracting the digit from 1111. When the decimal equivalent of 10 is added, the value obtained is 15 - N + 10 = 9 - N + 16. However, the digit 16 signifies the carry that is discarded, hence, the result equals to 9 - N as required. Adding and then complementing the binary equivalent of decimal 6 provides 15 - (N + 6) = 9 - N as needed. A combination circuit can also be used to obtain the 9’s complement of a BCD digit. When this combination circuit is attached to a BCD adder, it results in a BCD adder or subtractor. Consider that the subtrahend digit is denoted by the four binary variables B8, B4, B2 and B1. Also consider M to be a mode bit that controls add or subtract operation. Therefore, when M = 0, the two digits are added and when M = 1, the digits are subtracted. Consider the binary variables x8 , x4 , x2 and x1 to be the outputs of the 9’s complementer circuit. According to the truth table for circuits: 1. B1 needs to be complemented at all times. School of Engineering and Technology, Sapthagiri NPS University Page 30 Computer Organization and Architecture 2. B2 is the same every time in 9’s complement as in original number. 3. x4 is 1 if the exclusive OR of B2 and B4 is 1. 4. x8 is 1 if B8B4B2 = 000. For the 9’s complement circuit, the Boolean functions are as follows: 1. X1 = B1M1 + B11M 2. X2 = B2 3. X4 = B4M1 + (B14B2 + B4B12) M 4. X8 = B8M1 + B18B14B12M In the above equations it can be observed that x = B if M= 0. If M = 1, the x outputs produce the 9’s complement of B. Decimal Arithmetic Operation Algorithms that are used for arithmetic operations with decimal data and binary data are alike. If the micro-operations symbol is interpreted correctly the same flowchart can be used for both multiplication and division. The decimal numbers in BCD are stored in groups of four bits in the computer registers. When performing decimal micro-operations, every 4-bit group represents a decimal digit and has to be taken as a group. For convenience, the same symbol can be used for binary and decimal arithmetic micro- operations with different interpretation. Table depicts symbols for decimal arithmetic micro- operations. Table 1.2 - Decimal Arithmetic Microoperation Symbols In table above, we can see a bar over the symbol for the register letter. This refers to the 9’s complement of decimal number that is stored in the register. When 1 is added to the 9’s complements the 10’s complement is produced. Therefore, the symbol for decimal digits denotes, transfer of decimal sum that was formed by adding the original content A to the 10’s complement of B. It may be confusing to use similar symbols for 9’s complement and 1’s School of Engineering and Technology, Sapthagiri NPS University Page 31 Computer Organization and Architecture complement in case both types of data are used in the same system. Therefore, it would be better to implement a different symbol for the 9’s complement. In case only one type of data is taken into consideration, the symbol would apply to the type of data used. Consider that a register A holds a decimal 7860 in BCD. The bit pattern of the 12 flip- flops equal to: 0111 1000 0110 0000. The micro-operation dshr A moves the decimal number one digit to the right to provide 0786. This shift is over the four bits and as such, changes the content of register to 0000 0111 1000 0110. School of Engineering and Technology, Sapthagiri NPS University Page 32