Transcription
Introduction to Digital Electronicsby Agner Fog, 2019-10-30.Contents1. Number systems . 31.1.Decimal, binary, and hexadecimal numbers . 31.2.Conversion from another number system to decimal . 41.3.Conversion from decimal to another number system . 51.4.Addition of binary numbers . 61.5.Signed binary numbers . 71.6.Binary coded decimal numbers . 91.7.Exercises . 102. Boolean algebra . 122.1.Laws and rules . 132.2.Truth tables . 142.3.Reducing a Boolean expression . 152.4.Exercises . 163. Digital circuits . 183.1.How Boolean gates are made . 183.2.Gate symbols . 213.1.Exercises . 234. Commonly used Boolean circuits . 254.1.Decoders . 254.2.Encoders. 264.3.Seven segment decoders . 274.4.Multiplexers. 284.5.Adders . 294.6.Subtracting binary numbers . 304.7.Exercises . 325. Flip-Flops . 345.1.Basic feed back circuit . 345.2.SR flip-flop . 345.3.SR flip-flop with enable . 351
5.4.D latch. 365.5.Edge-triggered D flip-flop . 365.1.Edge-triggered D Flip-Flop with set and reset . 385.2.Toggle flip-flop . 395.1.Ripple counter . 405.2.Exercises . 416. State machines . 456.1.Synchronous design . 526.2.Exercises . 557. Interfacing digital circuits . 577.1.Pushbuttons . 577.2.Button with debouncing. 587.3.Automatic power-on reset . 617.4.LED output . 627.5.Relay output. 637.6.Optocouplers . 647.7.Digital-to-analog converters . 657.8.Analog-to-digital converters . 667.9.Exercises . 698. Microprocessors and microcontrollers . 708.1.Input ports and output ports . 718.2.Interrupt . 739. Appendix A: List of digital integrated circuits . 752
1. Number systems1.1. Decimal, binary, and hexadecimal numbersWe all know the decimal number system. For example, 2019 means 2*1000 0*100 1*10 9*1.The numbers 2, 0, 1, 9 are called the digits of the number 2019.If we want to describe this mathematically, we will call the rightmost digit d0, the next digit d1, etc. Ifthere are n digits: d0, d1, d2, . dn-1, then the value v can be calculated by the formula𝑛 1v 𝑑𝑖 10𝑖𝑖 0In the example of 2019, we have d0 9, d1 1, d2 0, d3 2, n 4. This gives v 2019.10 is the base or radix of the number system. The reason why we are using ten as the radix is thatthis makes it easy to use our ten fingers for counting. The name decimal comes from Latin decemwhich means ten. The word digit means finger.If we use a number system with radix r then the above formula becomes𝑛 1v 𝑑𝑖 𝑟 𝑖𝑖 0For example, if the radix r is sixteen then 2019 does not mean two thousand and nineteen. Insteadthe value becomes2019(base 16) 9*160 1*161 0*162 2*163 8217(base 10).1.1.1. Binary numbersComputers do not have ten fingers so the decimal number system is not the most efficient system touse in computers. Instead, the binary system with radix 2 is used. For example,1101(base 2) 1*20 0*21 1*22 1*23 13(base 10). The rightmost digit is the least significant digit withthe worth 20 1. We can call the least significant the 1's, the next digit from the right is the 2's. Nextcomes the 4's, the 8's, etc. The calculation is illustrated in this table:8's11*8 84's2's101*4 4 0*2 08 4 0 1 131's11*1 1Each digit in a binary number can have only two different values: 0 and 1. These are convenientlyrepresented in an electrical wire as two different voltages. The lower of the two voltages represents 0and the higher voltage represents 1. For example, we may choose 0V and 5V for the numbers 0 and1, respectively. A binary number with four digits, as in the example above, can be represented by fourwires, where each wire has either 0V or 5V.3
A binary digit is also called a bit. A bit can be 0 or 1. This is the smallest piece of information that youcan store in any system.1.1.2. Hexadecimal numbersThe hexadecimal number system has radix 16. The sixteen possible digits are written as 415For example 4AD1(base 16) 1*160 13*161 10*162 4*163 19153(base 10).The hexadecimal system is often used as a short way to represent binary numbers with many digits.Each hexadecimal digit corresponds to four binary digits, because 16 24. For example, the binarynumber 0100101011010001(base 2) is easily converted to the hexadecimal number 4AD1(base 16) bydividing the bits into groups of four:0100 1010 1101 0001︸ ︸ ︸ ︸4AD11.2. Conversion from another number system to decimalThere are two convenient ways to convert from any other number system to decimal. The first methodstarts with the rightmost digit (least significant digit) and multiplies by powers of the radix. We usedthis method above to convert the number 4AD1 from hexadecimal to decimal:4AD1(base 16) 1*160 13*161 10*162 4*163 19153(base 10).The second method starts with the leftmost digit (most significant digit). Multiply the leftmost digit bythe radix. Add the next digit. Multiply the result by the radix. Add the next digit, and so on. Stop afteradding the last digit. Do not multiply by the radix after adding the last digit.4
If we apply this method to the same example, we get:4AD1(base 16) ((4 * 16 10) * 16 13) * 16 1 19153(base 10).The second method is convenient to use with a pocket calculator.1.3. Conversion from decimal to another number systemThere are also two ways to convert from decimal to another number system. The first method givesthe rightmost digit (least significant digit) first: Divide the number repeatedly by the radix and get theinteger part of each result. Save the remainders from each division. The remainders represent theconverted number with the least significant digit first. This method is illustrated with the sameexample as above:Convert 19153 from decimal to hexadecimal:Number191531197744Division19153 / 16 1197, remainder 11197 / 16 74, remainder 1374 / 16 4, remainder 104 / 16 0, remainder 4Fraction11977440Remainder113104You get the result from the remainders in reverse order: 4 : 10 : 13 : 1 gives 4AD1(base 16).The second method gives the leftmost digit (most significant digit) first: Find the highest power of theradix that is not bigger than the number you want to convert. Divide by the highest power of the radixfirst. The result of the first division is the most significant digit of the result. Divide the remainder bythe next lower power of the radix, and so no. Our example gives these results:Convert 19153 from decimal to hexadecimal:Number1915327692091Division19153 / 163 4, remainder 27692769 / 162 10, remainder 209209 / 161 13, remainder 11 / 160 1, remainder 0Fraction410131Remainder276920910You get the result from the fractions: 4 : 10 : 13 : 1 gives 4AD1(base 16).You can choose the method you think is most logical or easiest to remember.1.3.1. Conversion from hexadecimal to binaryIt is easy to convert a number from hexadecimal to binary. Just convert each hexadecimal digit to fourbits. If any digit gives less than four bits then you must remember to put zeroes in front of the numberto get four bits.Converting 4AD1 from hexadecimal to binary:5
4AD1 0100 1010 1101 00010100 : 1010 : 1101 : 0001 gives 0100101011010001 100101011010001.1.3.2. Conversion from binary to hexadecimalTo convert from binary to hexadecimal, you divide the bits into groups of four. If the number of bits isnot divisible by four then add extra zeroes in front of the number. Remember that you can add zeroesto the left of the number without changing the value. You cannot add a zero to the right of the numberbecause this would multiply the number by two.To convert 100101011010001 from binary to hexadecimal, we divide it into groups of four. Theleftmost group has only three bits so we add a zero in the front:0100 1010 1101 0001︸ ︸ ︸ ︸4AD1It is easier to write 4AD1 than 100101011010001 and it is easy to convert between these two numbersystems. This is the reason why hexadecimal numbers are often used in digital systems.It is convenient to use the hexadecimal representation as an intermediate if you want to convert frombinary to decimal or from decimal to binary. The conversion: binary hexadecimal decimal iseasier than binary decimal. Likewise, the conversion: decimal hexadecimal binary is fasterthan decimal binary because you need fewer divisions.1.4. Addition of binary numbersAddition of binary numbers goes the same way as for decimal numbers, as we learned at school. Thisexample calculates 7 21, using binary numbers:11100111 10101111007 2128In the example above, we start with the 1's place which is the rightmost column. 1 1 2. Thenumber 2 in binary is 10, so we get zero and a carry which goes to the 2's place. The carries areindicated in red here. The second column from the right is the 2's place. Here we have 1 1 0 2.This gives a zero in the 2's place and a carry to the 4's place. The third column from the right is the4's place. Here we have 1 1 1 3. The binary code for 3 is 11, so we get 1 in the 4's place and a6
carry to the 8's place. There are no more carries, so the result is 00111 10101 11100, or indecimal: 7 21 28.1.5. Signed binary numbersThere are several different ways of representing negative numbers. Today, almost all computers usea system called two's complement for representing numbers that can be both positive and negative.We will explain this system shortly.A digital system typically has a fixed number of bits to represent a binary number. For example, if wehave four bits, we can have the numbers from 0 to 15We can add 1 by going one step down in this table. The maximum number we can have with four bitsis 15. If we try to add 1 to 15 we get the binary number 10000. Since we have only four bits in thisexample, we will not see the extra bit, but only 0000. In other words, if we add 1 to 15 in a four-bitsystem we get an overflow and the result will be 0. Likewise, if we try to subtract 1 from 0 we get anunderflow and we will see the result 15.This behavior is illustrated in the wheel on figure 1.1. You add one by going one step clockwise.When you pass 1111 (15) you will see the number overflow back to zero. The binary numbers areshown in black. The unsigned decimal numbers are shown in blue.The idea of the two's complement system is that we use the same number wheel with a fixed numberof bits and ignore overflow and underflow. We can find the representation of -1 by subtracting 1 from0. This will underflow and give the bits 1111. Now, we define that 1111 means -1 instead of 15. Wecan find -2 by subtracting 1 from -1. This gives 1110 as the representation for -2. We will use the lefthalf of the circle for negative numbers and the right half for positive numbers. We want to make iteasy to distinguish between positive and negative numbers, so we decide that the leftmost bit is 1 fornegative numbers and 0 for positive numbers. This bit is called the sign bit. Now, the positivenumbers go from 1 to 7, and the negative numbers go from -1 to -8. There are eight negative7
numbers but only seven positive numbers because the value zero also has the sign bit set to 0. Thesigned numbers are shown in red on the figure.The same bit pattern can be interpreted in two different ways now. The bit pattern 1111 means 15 ifwe interpret it as an unsigned number (blue numbers on the figure), but it means -1 if we interpret thisbit pattern as a signed number (red numbers on the figure). The values from 0000 to 0111 are thesame whether you use signed or unsigned numbers, while the values from 1000 to 1111 areinterpreted differently for signed and unsigned numbers. Some computer programming languages,such as C and C , allow you to specify whether a binary variable is interpreted as a signed or anunsigned number.Fig. 1.1. Two's complement number system8
1.5.1. How to change the sign of a numberYou cannot change the sign of a number just by inverting the sign bit. The rule is that you change thesign of a number by inverting all bits and then add 1. For example, if you want to find the two'scomplement representation of -5, you first find the binary representation of 5. Then invert all bits andadd 1:010110101011Binary representation of 5Invert all bitsAdd 1. This is the representation of -5We can also use this rule to find the value of a bit pattern, for example 1001. The sign bit is 1 so itmust be a negative number. We want to change the sign in order to find the corresponding positivenumber:100101100111We want to find out what this signed bit pattern meansInvert all bitsAdd 1. This means 7. Therefore, 1001 means -71.5.2. The ranges of signed and unsigned n-bit numbersIn the above example we used only four bits for the sake of simplicity. This gave us a quite limitedrange of possible values. Four bits gives us 24 16 different bit combinations, from 0000 to 1111. Wecan use these sixteen different bit combinations to represent either the unsigned numbers from 0 to15, or the signed numbers from -8 to 7. If we want higher numbers, then we need more bits.If we have eight bits then we have 28 256 different bit combinations, from 00000000 to 11111111.We can use these 256 different bit combinations to represent either the unsigned numbers from 0 to255, or the signed numbers from -128 to 127.In general, if we have n bits then we have 2n different bit combinations. We can use these 2n differentbit combinations to represent either the unsigned numbers from 0 to 2 n-1, or the signed numbers from-2n-1 to 2n-1-1.Modern computers typically use 8, 16, 32, or 64 bits for representing integer numbers. We cancalculate the ranges using these formulas.number of bits8163264nrange for unsigned numbers0 . 2550 . 655350 . 42949672950 . 1.8 10190 . 2n-1range for signed numbers-128 . 127-32768 . 32767-2147483648 . 2147483647-9.2 1018 . 9.2 1018-2n-1 . 2n-1-11.6. Binary coded decimal numbersWe prefer to use binary numbers in digital applications, but sometimes we have to use decimalnumbers in order to make the numbers easier to read for humans. For example, we may want adecimal number on a display, or a human operator may enter a decimal number on a keyboard. Wecan represent a decimal number in a digital system by using four bits for each decimal digit. Four bits9
gives us sixteen different combinations which is more than enough to represent the possible digitsfrom 0 to 9. We are using only ten of the sixteen possible bit combinations. This method is calledbinary coded decimal numbers (BCD).If you need, for example, a display that can show the numbers from 000 to 999 then you need threegroups of four wires each for the three digits. For example, the number 256 in binary code is100000000, while 256 in binary coded decimal is 0010 : 0101 : 0110.1.7. ExercisesExercise 1.1.The powers of 2 are used everywhere in digital systems. Write a table of the powers of 2 from 20 to210 in decimal, hexadecimal, and binary representation.Exercise 1.2.Convert these numbers from binary to decimal:11111100100Exercise 1.3.Convert these numbers from decimal to binary:711023Exercise 1.4.Convert these numbers from binary to hexadecimal:1001000111111000000001101Exercise 1.5.Convert the numbers in exercise 1.4 to decimal. Tip: It is easier to convert from hexadecimal todecimal than from binary to decimal.Exercise 1.6.Convert these numbers from hexadecimal to binary:2468ABCDExercise 1.7.Find the sum of the numbers in exercise 1.4 by binary or hexadecimal addition.Exercise 1.8.How many different binary numbers can you write with:10
4 bits5 bitsn bitsExercise 1.9.Write the number -4 in two's complement representation for a binary system with 16 bits.Exercise 1.10.We want to build a digital thermometer that can show the temperature up to 200 C without decimals.How many bits do we need to represent the temperature as a binary number if only positivetemperatures can be shown?How many bits do we need to represent the temperature if the thermometer can also show negativetemperatures, and the two's complement representation is used?How many bits do we need to represent the temperature in binary coded decimal (BCD)representation?11
2. Boolean algebraBoolean algebra is a branch of mathematics where variables can have only two possible values: falseand true, or 0 and 1. The basic operations in Boolean algebra are AND, OR, and NOT.These operators are defined in the following tables.A0011B0101A AND B0001A0011A01B0101A OR B0111NOT A10The AND operator gives 1 if both inputs are 1. The OR operator gives 1 if at least one input is 1. TheNOT operator gives the opposite of the input.Different people use different symbols for these operators. Mathematicians use the symbols forAND, OR, NOT. Software programmers use && ! in programming languages like C, Java, etc.Engineers often write AND as multiplication, OR as addition, and NOT as an overbar (A̅).OperatorANDORNOTMathematics Software&& !EngineeringA*BA BA̅It is clear that Boolean AND is the same as multiplication if you look at the table for the ANDoperation. It is less obvious why engineers write A B when they mean A OR B. The tables for ORand PLUS are slightly different:A0011B0101A B0111A B0112The reason why it is convenient to use the multiplication and addition signs for AND and OR is thatthe rules for multiplication and addition that we are used to from elementary algebra also apply toAND and OR in Boolean algebra, as we will see. We just have to remember that 1 1 1 when weare dealing with Boolean algebra.The normal rules for the precedence of operators apply. Multiplication comes before addition if thereis no parenthesis:12
A B * C A (B * C)This rule also applies if you use the other symbols or && .2.1. Laws and rulesI am sure you have learned the basic rules of elementary algebra in school, even if you do not knowthe names of these rules:Name of lawCommutative lawAssociative lawDistributive lawBoolean ANDA*B B*AA * (B * C) (A * B) * CA * (B C) (A * B) (A * C)Boolean ORA B B AA (B C) (A B) CA (B * C) (A B) * (A C)These laws are the same for elementary algebra and Boolean algebra, except the last one:A (B * C) (A B) * (A C)The latter law is valid for Boolean algebra, but not for elementary algebra.There are many other useful rules in Boolean algebra:A*0 0A*1 AA*A AA * A̅ 0A A̅*B A BA 1 1A 0 AA A AA A̅ 1A * (A̅ B) A * BA̿ AThese rules are easy to prove by inserting all possible values on the left hand side of the equationsign and see if you get the same values on the right hand side.One rule is particularly good to remember. It is called De Morgan's rule:𝐴̅ 𝐵̅ ̅̅̅̅̅̅̅̅𝐴 𝐵̅̅̅̅̅̅̅𝐴̅ 𝐵̅ 𝐴 𝐵De Morgan's rule can be expressed more generally for any Boolean expression: You can invert theoutput of a Boolean expression by inverting all the inputs, replace all AND operations by OR, andreplace all OR operations by AND. This rule is often used for simplifying digital circuits.All the tables above have two columns. The rules in the left column can be derived from the rules inthe right column, or vice versa, by applying de Morgan's rule. Let's try this for the commutative law:A*B B*ADefine X A̅ and Y B̅, and insert:X̅ * Y̅ Y̅ * X̅Use de Morgen's rule on both sides:̅̅̅̅̅̅̅̅𝑋 𝑌 ̅̅̅̅̅̅̅̅𝑌 𝑋13
Invert on both sidesX Y Y XThis is the result we want, just with different letters.2.2. Truth tablesA truth table is a table of the value of a Boolean expression for all possible values of the inputs. Forexample, this is a table for the expression F A * (B C).A00001111B00110011C01010101F A * (B C)00000111Sometimes, you want to build a digital circuit with a given functionality that is defined only by a truthtable. You can use the so-called sum-of-products method to find a Boolean expression thatcorresponds to a given truth table. This method works as follows:Find all the lines in the truth table for which the output is 1. Make one expression for each of theselines by AND'ing all the inputs and inverting those inputs that are 0 in that line. Each of theseexpressions is 1 in the corresponding line and 0 in the rest. The final result is the OR-combination ofall these expressions. Let's try this method with the example above.ABCF A * (B C)sum of products ̅*CA*B*C̅A*B*CNow we know that F A*B̅*C A*B*C̅ A*B*C.This is called a sum of products, even though the * and actually mean AND and OR.Now we have a valid expression for F, but not the simplest possible one. We may simplify thisexpression by using the laws and rules that we have learnt:14
A*B̅*C A*B*C̅ A*B*C A*B̅*C A*B*(C̅ C) A*B̅*C A*B*1 A*B̅*C A*B A * (B̅*C B) A * (B B̅*C) A * (B C)If there are many 1's and few 0's in the output column, then it is easier to invert the output and applythe sum-of-products method to the inverted output. This gives a simpler expression, but we mustremember to invert the result of the expression. We can use de Morgan's rule for converting theinverted sum of products to a "product of sums".2.3. Reducing a Boolean expressionIn the above example, we could reduce the expression by looking for common factors that we couldput outside of a parenthesis. This may be hard, but at least you can do it in simple cases with a littlepractice. Unfortunately, some cases are so tricky that you basically have to know the result inadvance in order to find a way to the result. I will give you one example here:G A*B A̅*C B*CIt is not obvious that this expression can be reduced, but look what happens when we use the ruleA A̅ 1:G A*B A̅*C B*C A*B A̅*C 1*B*C A*B A̅*C (A A̅)*B*C A*B A̅*C A*B*C A̅*B*C A*B A*B*C A̅*C A̅*C*B A*B*(1 C) A̅*C*(1 B) A*B*1 A̅*C*1 A*B A̅*CPure magic! The term B*C just disappeared. This is not the way forward if we want to reduce Booleanexpressions that may be more complicated than this example. There is a graphical method thatmakes this kind of reductions more intuitive. It is called a Karnaugh map (pronounced in French: Karnó map). The Karnaugh map shows geometrically that all input combinations covered by the termB*C in the above example are already covered by the two terms A*B and A̅*C.15
I will not teach you how to make a Karnaugh map because it takes some time and practice to learn,and it becomes quite difficult if there are more than four inputs. You may look up "Karnaugh map" onthe web if you are interested. However, we have software that does the complicated job of finding thesimplest possible expression for a given Boolean function. There is an online program atwww.32x8.com that does the job. There is also an open source program called Karnaugh MapMinimizer that you can download from https://sourceforge.net/projects/k-map/.Today, complicated digital circuits are designed with the use of a hardware description language,such as VHDL or Verilog. There is not much need for learning how to make Karnaugh mapsnowadays because the reduction of Boolean expressions comes automatically when you use suchdevelopment tools.2.4. ExercisesExercise 2.1.The distributive law for Boolean algebra looks like this:A * (B C) (A * B) (A * C)A (B * C) (A B) * (A C)Prove this by using truth tables.Exercise 2.2.Use the rules of Boolean algebra to reduce these expressions to the simplest possible:(1)A*B*C A̅*B A*B*C̅(2)X̅*Y*Z X*Z(3)̅̅̅̅̅̅̅̅̅̅(𝑋 𝑌) (𝑋̅ 𝑌̅)(4)X*Y X*(W*Z W*Z̅)(5)(B*C̅ A̅*D) * (A*B̅ C*D̅)(6)(X Y̅ Z̅) * (X̅ Z̅)Exercise 2.3.We want to implement a Boolean function F with the following truth table16
te the expression for F as a sum of products.Reduce the expression for F to the simplest possible by using the online program at www.32x8.comor the program "Karnaugh Map Minimizer" from https://sourceforge.net/projects/k-map.17
3. Digital circuits3.1. How Boolean gates are madeThe Boolean operations AND and OR can be made with simple switches, as shown here:AABBA*BANDfunction:The lamp will light when Aand B areboth on.A BOR function:The lamp will light when at least oneof Aand
3 1. Number systems 1.1. Decimal, binary, and hexadecimal numbers We all know the decimal number sys
![History of Electronics electricity [Read-Only]](/img/18/history-20of-20electronics-20-20electricity.jpg)
