LOGIC MANUAL 2013-2014 Student Copy PDF

Chapter 1 Digital systems can process, store, and transmit data more efficiently but can only DIGITAL FUNDAMENTALS assign discrete values to each point. Digital...

Chapter 1 Digital systems can process, store, and transmit data more efficiently but can only DIGITAL FUNDAMENTALS assign discrete values to each point. Digital circuits operate in the binary mode where Introduction each input and output voltage is either 1 or 0. 1 and 0 designations represent the logical Digital Logic is the basis of state which has a pre-defined voltage ranges. computers, and computers are intrinsically at the heart of digital systems. Analog and Digital Systems Digital computers have made Many systems use a mix of analog and possible many applications in scientific, digital electronics to take advantage of each industrial, and commercial advances that technology. A typical CD player accepts would have been impossible for humans to digital data from the CD drive and converts do. Computers are used in scientific it to an analog signal for amplification. calculations, commercial and business data processing, air traffic control, space guidance and many other areas. Characteristic of a digital system is its manipulation of discrete elements of information. Such discrete elements may be electric impulses, the decimal digits, an alphabet, arithmetic operations or any other set of meaningful symbols. Discrete elements of information are represented in a digital system by physical quantities called signals. Electrical signals Figure 1.2 Sample of Digital system to Analog such as voltages and currents are the most output common. The signals in all electronic digital systems have only two discrete values and are said to be binary. Binary Digits and Logic Levels Digital electronics uses circuits that have two states, which are represented by Analog Quantities two different voltage levels called HIGH and LOW. The voltages represent numbers in Most natural quantities that we see the binary system. are analog and vary continuously. Analog systems can generally handle higher power In binary, a single number is called a bit (for than digital systems. binary digit). A bit can have the value of either a 0 or a 1, depending on if the voltage is HIGH or LOW. Digital Waveforms Digital waveforms change between the LOW and HIGH levels. A positive going pulse is one that goes from a normally LOW logic level to a HIGH level and then back Figure 1.1 Sample of Analog Quantities 1 again. Digital waveforms are made up of a Periodic pulse waveforms are series of pulses. composed of pulses that repeats in a fixed interval called the period. The frequency is the rate it repeats and is measured in hertz. 1 f = T 1 T= f The clock is a basic timing signal that is an example of a periodic wave. Sample Problem What is the period of a repetitive wave if f = 3.2 GHz? Ans: 313ps Figure 1.3 Digital Waveform Rising and Falling Edge Pulse Definitions Pulse Definitions Actual pulses are not ideal but are described by the rise time, fall time, In addition to frequency and period, amplitude, and other characteristics. repetitive pulse waveforms are described by the amplitude (A), pulse width (tW) and duty cycle. Duty cycle is the ratio of tW to T. Figure 1.4 Actual Digital Pulse Figure 1.5 Pulse Width and Period of a Digital Signal Periodic Pulse Waveforms 2 DUTY CYCLE Duty cycle is the fraction of time that BASIC LOGIC FUNCTIONS a system is in an “active” state. It is also the proportion of time during which a All logic circuit combinations are component, device, or system is operated. based on the three major types of logic gates. Figure 1.6 Sample Timing Diagram Timing Diagrams AND A timing diagram is used to show True only if all input the relationship between two or more conditions are true. digital waveforms, A diagram like in figure 1.6 can be observed directly on a Digital Signal Analyzer. This type of diagram can be an OR output of logic circuit combinations. True only if one or more input conditions are true. NOT Indicate the opposite condition. 3 Basic System Functions Integrated Circuits And, or, and not elements can be combined to form various logic functions. A DIP chips and surface mount chips few examples are: The comparison function DIP SOIC Dual-In-Line Package(DIP) Small Outline IC (SOIC) Programmable Logic Basic arithmetic functions Programmable logic devices (PLDs) are an alternative to fixed function devices. The logic can be programmed for a specific purpose. In general, they cost less and use less board space that fixed function devices. A PAL device is a form of PLD that uses a combination of a programmable AND array and a fixed OR array: The encoding function The decoding function Figure 1.7 Programmable Logic Controllers 4 Summary programmed to perform specified functions. Analog: Being continuous or having continuous values. Digital: Related to digits or discrete quantities; having a set of discrete values. Binary: Having two values or states; describes a number system that has a base of two and utilizes 1 and 0 as its digits. Bit: A binary digit, which can be a 1 or a 0. Pulse: A sudden change from one level to another, followed after a time, called the pulse width, by a sudden change back to the original level. Clock: A basic timing signal in a digital system; a periodic waveform used to synchronize actions. Gate: A logic circuit that performs a basic logic operations such as AND or OR. NOT: A basic logic function that performs inversion. AND: A basic logic operation in which a true (HIGH) output occurs only when all input conditions are true (HIGH). OR: A basic logic operation in which a true (HIGH) output occurs when when one or more of the input conditions are true (HIGH). Fixed-function logic: A category of digital integrated circuits having functions that cannot be altered. Programmable logic: A category of digital integrated circuits capable of being 5 Chapter 2 The LSD in a number is the digit that has least effect on that number. NUMBER SYSTEM The following value number below shows Number System means the way to the MSD and LSD. represent the various types of numbers. Each of the number systems is built around the following components: the UNIT, NUMBER, and BASE (Radix). UNIT By definition the unit is a single object. e.g. a book; a day NUMBER A number is a symbol representing a NOTE: unit or a quantity. e.g. 4, 2, 5, 23, I, III, M, X 6 3 7 8. 0 3 1 BASE (Radix) Radix point The base, or radix, of a number system tells you the number of symbols used in that system. Sample Problem 2.1 The base of any system is always expressed in decimal numbers. (NBASE) What are the MSD and LSD of the following numbers? Sample Decimal Octal Hexadecimal Binary (a) 420.0 610 78 A18B16 11001112 (b) 1045.06 BASE or RADIX of a number (c) 0.0024 (d) 247.0001 SIGNIFICANT DIGITS Most Significant Digit (MSD) – Left Most Digit The MSD in a number is the digit that has greatest effect on that number. Least Significant Digit (LSD) – Right Most Digit 6 TYPES of NUMBER SYSTEM COMMON NUMBER SYSTEM 1. Positional Number System 1. Decimal System Positional notation is a 2. Binary System system where the value of a number 3. Octal System is defined not only by the symbol but 4. Hexadecimal System by the symbol’s position. DECIMAL SYSTEM Characteristics Decimal system is the most commonly This system uses only a few symbols used number system. Our present system of called digits. numbers has 10 separate symbols namely 0, These symbols represent different 1, 2, 3, 4, 5, 6, 7, 8 and 9, which are called values depending upon the position Arabic numerals. We would be forced to they occupy in the number. stop at 9 or to invent more symbols if it were The maximum value of a single digit not for the use of positional notation. is equal to one less than the value of base. The digit of a number system is a symbol, which represents an integral quantity. Sample of positional number system: The base or radix of a number system is defined as the number of different digits, 3 5 2.5 which can occur in each position in the This represents ½ units number system. The decimal system has This represents 2 units a base or radix of 10. Ex. This represents 50 units 1. 26810 This represents 300 units 2. 583910 If you exchange the positions of the 2 3. 2010 and the 5, then the value will change. 2. Non-Positional Number System BINARY NUMBER SYSTEM Characteristics Digital computers use the binary Use symbols such as I for 1, II for 2, number system, which has only two III for 3,IIII for 4, etc. symbols: 0 and 1. The numbers in binary Each symbol represents the same system are represented as combinations of value regardless of its position in the these two symbols. The decimal system uses number system. radix of 10 and binary system uses radix of 2. The symbols are simply added to The binary digit is also referred to as find out the value of the number Bit (the acronym for Binary Digit). A string concerned. of 4 bits is called a nibble and a string of 8 bits is called a byte. A byte is the basic unit of data in computers. The number 125 actually means 1(102) + 2(101) + 5(100) 7  In binary system, the same number HEXADECIMAL NUMBER SYSTEM (125) is represented as 1111101 meaning When the machine is handling numbers in binary but in groups of four 1(26) + 1(25) + 1(24) + 1(23) + 1(22) + 0(21) + digits, it is convenient to have a code for 1(20) representing each of these sets of four digits. Since 16 possible different numbers can be Table 2.1 List of Decimal Numbers and its represented, the digits 0 through 9 will not Equivalent Binary suffice. So the letters A, B, C, D, E and F are also used. Hexadecimal numbers are strings of these digits. The numbers in decimal, binary and hexadecimal is shown in the table 1.3. It is the simplest method of expressing value represented by binary numerals. Table 2.3 List of Decimal Binary and its Equivalent in Hexadecimal Number OCTAL NUMBER SYSTEM The octal number system has a base, or radix as 8: eight different symbols are used to represent numbers. These are commonly 0,1,2,3,4,5,6,7. We show the first 20 octal numbers and their decimal equivalents in the table 1.2. It is the shorthand method for preparing groups of binary digits by a single octal digit to reduce the number of digit required in representing any number. Table 2.2 List of Decimal Numbers and its Equivalent in Octal Number 8 NUMBER SYSTEM CONVERSIONS 32 16 8 4 2 1. ½ ¼ 1 0 0 1 0 1. 0 1 BACKGROUND and HISTORY 32 + 4 + 1 + ¼ The abacus, developed by the Ans. 37¼ Chinese, is one of the earliest known calculators. It is still in use in some parts of the world. DECIMAL TO BINARY CONVERSION 1642 - Blaise Pascal (French) invented the You can convert a decimal whole first adding machine. number to binary by reversing the procedure. Write the decimal weight of each 1660s - Sir Samuel Moreland, developed a column and place 1’s in the columns that more compact device that could multiply, sum to the decimal number. add, and subtract. Sample Problem 2.3 1672 - Gottfried Wilhelm von Leibniz (German) perfected a machine that could Convert the decimal number 4910 to binary. perform all the basic operations (add, Solution: The column weights double in each subtract, multiply, divide), as well as extract position to the right. Write down column weights the square root. until the last number is larger than the one you Modern electronic digital computers still use want to convert. von Liebniz's principles. 26 25 24 23 22 21 20. 64 32 16 8 4 2 1. BINARY CONVERSIONS 0 1 1 0 0 0 1. BINARY TO DECIMAL CONVERSION The decimal equivalent of a binary You can convert a decimal fraction to number can be determined by adding the binary by repeatedly multiplying the column values of all of the bits that are 1 fractional results of successive and discarding all of the bits that are 0. multiplications by 2. The carries form the binary number. Sample Problem 2.2 Sample Problem 2.4 Convert the binary number 100101.01 Convert the decimal fraction 0.188 to binary by to decimal. repeatedly multiplying the fractional results by Solution: Start by writing the column weights; 2. then add the weights that correspond to each 1 in the number. 25 24 23 22 21 20. 2-1 2-2 9 Solution: BINARY TO OCTAL CONVERSION Binary number can easily be 0.188 x 2 = 0.376 carry = 0 MSB converted to octal by grouping bits 3 at a time and writing the equivalent octal 0.376 x 2 = 0.752 carry = 0 character for each group. 0.752 x 2 = 1.504 carry = 1 Sample Problem 2.6 0.504 x 2 = 1.008 carry = 1 Express 1 001 011 000 001 1102 in octal: 0.008 x 2 = 0.016 carry = 0 Solution: Group the binary number by 3-bits starting from the right, then solve for equivalent Answer = 0.00110 (for five significant digits) digit of the number in each group. You can convert decimal to any other base by repeatedly dividing by the base. For 001| 001 | 011 | 000 | 001 | 1102 binary, repeatedly divide by 2: 4 2 1| 4 2 1 | 4 2 1 | 4 2 1 | 4 2 1 | 4 2 1 Sample Problem 2.5 1 | 1 | 3 | 0 | 1 | 6 Convert the decimal number 49 to binary by repeatedly dividing by 2. Thus the answer is 1130168 Solution: You can do this by “reverse division” OCTAL TO DECIMAL CONVERSION and the answer will read from left to right. Put Octal is also a weighted number quotients to the left and remainders on top. system. The column weights are powers of 8, which increase from right to left. 49 ÷ 2 = 24 carry = 1 …… 83 82 81 80. 8-1 8-2 24 ÷ 2 = 12 carry = 0 …… 512 64 8 1. 1/8 1/64 12 ÷ 2 = 6 carry = 0 Sample Problem 2.7 6 ÷2=3 carry = 0 Express 37028 in decimal. 3 ÷2=1 carry = 1 1 ÷2=0 carry = 1 MSB Solution: Start by writing the column weights: Ans. 110001 512 64 8 1 OCTAL NUMBER CONVERSION 3 7 0 28 3(512) + 7(64) + 0(8) + 2(1) Octal uses eight characters the numbers 0 through 7 to represent numbers. Ans. 198610 There is no 8 or 9 character in octal. 10 NOTE: HEXADECIMAL TO DECIMAL You can convert from OCTAL CONVERSION numbers to DECIMAL numbers by taking the Hexadecimal is a weighted number BINARY equivalent of the OCTAL then system. The column weights are powers of convert the binary to DECIMAL numbers. 16, which increase from right to left. Sample Problem 2.9 Express 1A2F16 in decimal. HEXADECIMAL NUMBER CONVERSION Solution: Start by writing the column weights: Hexadecimal uses sixteen characters to represent numbers: the numbers 0 4096 256 16 1 through 9 and the alphabetic characters A 1 A 2 F16 through F. 1(4096) + 10(256) + 2(16) + 15(1) BINARY TO HEXADECIMAL CONVERSION Ans. 670310 Large binary number can easily be converted to hexadecimal by grouping bits NOTE: 4 at a time and writing the equivalent hexadecimal character. You can convert from HEXADECIMAL numbers to ANY numbers Sample Problem 2.8 by taking the BINARY equivalent of the HEXADECIMAL then convert the binary to Express 1001 0110 0000 11102 in hexadecimal. ANY number that you want. Solution: Group the binary number by 4-bits starting from the right. 1001 | 0110 | 0000 | 11102 8 4 2 1|8 4 2 1|8 4 2 1 |8 4 2 1 9 | 6 | 0 | E Thus the answer is 960E16 11 Chapter 3 DECIMAL ADDITION Before we proceed to octal addition DIGITAL ARITHMETIC it is important to examine the actual process of decimal addition. Let us consider the BINARY ADDITION following example. The rules for binary addition are 0+0=0 0 Sum = 0, carry = 0 Sample problem 3.1 0+1=1 0 Sum = 1, carry = 0 Perform the decimal addition of the 1+0=1 0 Sum = 1, carry = 0 following 37610 and 46110. 1+1=1 0 Sum = 0, carry = 1 Solution 1: When an input carry = 1 due to a previous Step 1: Add the first digit result, the rules are 3 7 610 1 + 0 + 0 = 01 Sum = 1, carry = 0 4 6 110 1 + 0 + 1 = 10 Sum = 0, carry = 1 → 6 + 1 = 710(the answer is 1 + 1 + 0 = 10 Sum = 0, carry = 1 1 + 1 + 1 = 11 Sum = 1, carry = 1 not greater than 10) Problem 3.1 Add the binary numbers 00111 and Step 2: Add the second digit 10101 and show the equivalent decimal addition. 3 7 610 4 6 110 Problem 3.2 710 Add 1000110101 + 100111001 + 7 + 6 = 1310 (13>10) 1100111 + 11001010 A answer is greater than 10 Since the N you need to subtract 10 to 13. S Step 3: :Then count the number of times you subtract0 10 from answer and that will serve 0 as the remainder for the next digit. 1 0 1310 - 10 0 10 = 310 (2 digit of the answer) nd 1 No of times: 1 (this will serve as remainder) 1 3 7 6101 14 6 1 10 1 3 710 12 Step 4: Perform the addition for the next bit. Step 3: Since the answer is 13, 3 will be left 1 behind and 1 will serve as remainder for the 3 7 610 next digit of the given. 4 6 110 1 3 710 3 7 610 Since the sum of the 3rd digit is 8, 4 6 110 which is less than 10, you don’t need to 3 710 subtract 10 from 8. Step 4: Perform the addition for the next bit. 1 3 7 610 1 3 7 610 4 6 110 4 6 110 8 3 710 3 710 Therefore the answer is 83710 Since the sum of the 3rd digit is 8. 1 3 7 610 Other Solution: 4 6 110 Step 1: Add the first digit 8 3 710 3 7 610 Therefore the answer is 83710 4 6 110 → 6 + 1 = 710 OCTAL ADDITION You just only need to put the answer Octal addition procedure is almost under the first digit. similar addition in decimal. In decimal, the maximum symbol that can be seen is 9 if the answer exceeds 9, let say 10, zero will be left Step 2: Add the second digit behind and one will be carried to the 3 7 610 following bit. The following procedure let you understand the octal addition. 4 6 110 710 Sample problem 3.2 7 + 6 = 1310 Add 658 and 168 The answer is greater than 10. You just need to be sure that both the answer and the given must be same type of number Solution 1: system. Step 1: Add the first digit 13  1 1 6 58 6 58 + 1 68 + 1 68 In decimal: 5 + 6 = 1110 1 0 38 (the answer is greater than The same will do for the next bit. Therefore the answer for 658 + 168 is equal to 1038 11>8) Step 2: Since the answer is greater than 8, subtract 8 from the answer. Other Solution Then count the number of times you Step 1: First perform the decimal subtract 8 from the answer and that will serve as the remainder for the next digit. addition on the first digit. 6 58 11 - 8 = 3 + 1 68 No of times: 1 (this will serve In decimal: 5 + 6 = 1110 as remainder) 1 6 58 Step 2: Next is to convert the decimal + 1 68 answer to octal number. 38 1110 → 138 Step 4: Perform the addition for the next bit. 1 6 58 1 6 58 + 1 68 + 1 68 38 38 In decimal: 1+ 6+1 Step 3: For the next bit, perform the = 810 decimal addition then convert the Step 5: Since the answer is equal to 8, you answer to octal. also need to subtract 8) then count the 810 → 108 number of times you subtract 8 from the answer. 8- 8 = 0 1 1 6 58 No of times: 1 (this will serve as + 1 68 remainder) 1 0 38 Therefore the answer for 658 + 168 is equal to 1038 14 Problem 3.3 HEXADECIMAL ADDITION Find the sum of 6428 and 768 Hexadecimal addition procedure is the same as octal addition but instead of converting the answer to octal equivalent the answer must be converted to hexadecimal equivalent. You can select from the two solutions that was discuss earlier. The following procedure let you understand the hexadecimal addition. Sample problem 3.3 Problem 3.4 Add 1E16 and 1F16 Find the sum of 74718 , 5228 , 338 Solution: Step 1: First perform the decimal addition on the first digit. 1 E16 + 1 F16 In decimal: E + F = 14 + 15 = 2910 Step 2: Next is to convert the decimal answer to hexadecimal number. 2910 → 1D16 The “D” will be left behind while “1” will be the carry for the next bit. 1 1 E16 + 1 F16 D16 15 Step 3: Again perform the decimal addition SUBTRACTION of NUMBER SYSTEM then convert the answer to hexadecimal. BINARY SUBTRACTION 310 → 316 The rules for binary subtraction are 1 1 E16 0-0=0 + 1 F16 1-1=0 3 D16 1-0=1 Therefore the answer for 1E16 + 1F16 is equal 0 - 1 = 1 with a borrow of 1 to 3D16 Sample Problem 3.4 Problem 3.5 Subtract the binary number 00111 from 10101 and show the equivalent decimal Find the sum of 4B216 and 2B16 subtraction. (ANS: 4DD16) Solution: 01 22 1 /0 1/ 0/ 1 → 21 00111 → -7 01110 → 14 Step 1: For the first digit the answer is 0 (12- 12) but for the second digit zero minus one Problem 3.6 is equal to one because we borrow 1 from the next digit. Find the sum of 97A16 , E0716 (ANS: 178116) Since we borrow 1 from the next digit, we add “2” to the bit that borrows. In order to understand further, let us examine the subtraction in decimal system. In decimal, let us consider 34 minus 16. 3 4 1 6 Since 4 is less than 6, we need to borrow from the next bit. Then we add “10” to the bit that borrows. In this case, 4 become 14. 16  2 14 ONE’S COMPLEMENT FORM 3/ 4/ 1 6 The 1’s complement of a binary number is just the inverse of the given binary digits. To form the 1’s complement, change Then we can continue the process of all 0’s to 1’s and all 1’s to 0’s. subtraction. Since we borrow “1” from 3 the 3 becomes 2. For example, the 1’s complement of 11001010 is 2 14 00110101 3/ 4/ 1 6 In digital circuits, the 1’s complement 8 is formed by using inverters. Thus, NOTE: 2 14 3/ 4/ Inverter is a logic gate that performs the 1 6 inversion of the input signal. 1 8 SYMBOL: A Ā The answer is 1810 We can apply the discussed operation for binary system but instead of adding 10, we TWO’S COMPLEMENT FORM add “2” to the bit that borrows. The 2’s complement of a binary number is Problem 3.7 formed by taking the 1’s complement of the given binary number and adding 1 to the Subtract the given binary: least-significant bit position. 11012 – 1102 For example, the 2’s complement of 11001010 is 00110101 - 1’s complement form +1 - add 1 00110110 - 2’s complement form SIGNED BINARY NUMBERS There are several ways to represent signed binary numbers. In all cases, the MSB in a signed number is the sign bit, that tells you if the number is positive or negative. Computers use a modified 2’s complement for signed numbers. Positive numbers are stored in true form (with a 0 for the sign bit) and negative numbers are stored in complement form (with a 1 for the sign bit). 17  NEGATION Sample problem 3.5 It is the operation of converting a The positive number 58 is written positive number to its negative equivalent or using 8-bits as a negative number to its positive equivalent. + 58 = 00111010 (true form). Sample problem 3.7 Start with +9 Sign bit (+) True Binary equivalent +9 01001 (Magnitude bits) 2’s complement (negate) -9 10111 Negative numbers are written as the 2’s complement of the corresponding Negate again number. Then sign bit will also be place on +9 01001 the MSB of the 2’s complement form. Sample problem 3.6 The negative number - 58 is written ADDITION IN TWO’S COMPLEMENT as: FORM 5810 → 0 1 1 1 0 1 0 - true binary 1 0 0 0 1 0 1 - 1’s complement CASE 1: Two Positive Number 1 1 0 0 0 1 1 0 - 2’s complement +9 - 0 1001 +4 - 0 0100 -58 =11000110 +13 0 1101 2’s complement equivalent Sign bit (+) Sign bit (-) (Magnitude bits) CASE 2: Positive Number and Smaller Negative Number Problem 3.8 +9 - 0 1001 Represent each signed decimal number - 4 - 1 1100 as a signed binary number in two’s complement +5 1 0 0101 form. Discarded Sign bit (+) 1. +13 (excess bit) 2. – 9 3. +3 Convert – 4 in 2’s complement 4. – 2 5. – 8 -4 → 0100 1011 1’s complement 1 1100 2’s complement After getting the 2’s complement form of “-4”, you can now add the two binary form. 18 CASE 3: Positive Number and Larger Negative Number -9 - 1 0111 Convert – 9 in 2’s complement +4 - 0 0100 -5 1 1011 -9 → 1001 Sign bit “1” 0110 1’s complement means negative 1 0111 2’s complement If the answer is negative the magnitude must be converted to 2’s complement form. (Negate 1011 → 0101 = 5 CASE 4: Two Negative Numbers -9 - 1 0111 Convert – 9 in 2’s complement -4 - 1 1100 - 13 1 1 0011 -9 → 1001 Sign bit “1” 0110 1’s complement means negative 1 0111 2’s complement If the answer is negative the Convert – 4 in 2’s complement magnitude must be converted to 2’s complement form. (Negate -4 → 0100 0011 → 1101 = 13 1011 1’s complement 1 1100 2’s complement CASE 5: Equal and Opposite Number -9 - 1 0111 Convert – 9 in 2’s complement +9 - 0 1001 0 0 0000 -9 - 1001 0110 1’s complement 1 0111 2’s complement Problem 3.9 Perform the binary addition. Express the given number using 8-bits equivalent. 1. -13 + 5 2. 21 – 7 3. -12 – 13 4. +31 +15 5. 46 – 9 – 6 19