Introduction to Digital: Combinational Logic and Systems Design

Introduction to Digital: Combinational Logic and Systems Design So far we have been discussing the generation, transmission and processing of signals whose amplitude (voltage, current) varies continuously in time and can in principle take any value. At a certain instant of time we may represent a signal by displaying its amplitude in an analog form or in a digital format. The graphics below demonstrate the familiar representation of the two forms. Both displays are asked to display the number 4.7. In this case the digital display on the left has the required resolution to represent the number exactly. If we try to display the number 4.76, this digital display, with its ability to display only 2 digits will have to round off the number, representing it either as 4.7 or 4.8, depending on how the system processes the numerics. Our reading of the number off the analog display requires some interpolation of the value but in principle the resolution is only limited by our ability to identify the position of the measuring needle. In general the characteristics of the digital display correspond to the digital signal which is required to generate the digital display in the first place. If we now consider an analog signal which varies continuously in time, see Figure 2a, then if we sample the signal at discrete times (τ, 2τ, 3τ, κλπ) we will obtain the values indicated by the solid circles on Figure 2b. Furthermore, if we consider the quantization of the signal at these discrete sampling times we obtain the signal indicated on Figure 2c which is a digital signal. The analog signal is also shown on Figure 2c to emphasize the relationship between it and its digital representation. 6.071/22.071 Spring 2006, Chaniotakis and Cory 1 Signal (V) Signal (V) 8 8 6 6 4 2 4 2 0 τ 2τ 3τ 4τ 5τ 6τ 7τ (a) Time Signal (V) Level Level Level Level Level Level Level 0 τ 2τ 3τ 4τ 5τ 6τ 7τ (b) Time 7 6 5 4 3 2 1 0 τ 2τ 3τ 4τ 5τ 6τ 7τ Time (c) Figure 2. Schematic representation of analog and digital signals. This review should have motivated us to ask a few questions about these signals and in particular about the digital signal shown on Figure 2c. Some of these questions are: 1. How is the information embodied by the digital signal represented? 2. How is the signal generated? a. How is the sampling frequency selected and how is it related to the “quality” of signal representation? b. How is the amplitude quantization achieved? 3. What are the advantages and disadvantages of generating the digital signal? For example, how does it perform in a. Accuracy b. Transmission c. Noise immunity d. Information storage e. Computation In the next few classes we will answer these questions and explore the fundamental issues associated with the design of digital circuits. 6.071/22.071 Spring 2006, Chaniotakis and Cory 2 Numbering Systems Binary Code. In digital electronics the signals are formed with only two voltage values, HI and LOW, or level 1 and level 0 and it is called binary digital signal.1 Therefore, the information contained in the digital signal is represented by the numbers 1 and 0. In most digital systems the state 1 corresponds to a voltage range from 2V to 5V while the state 0 corresponds to a voltage range from a fraction of a volt to 1 volts. Digital operations are performed by creating and operating on binary numbers. Binary numbers are comprised of the digits 0 and 1 and are based on powers of 2. Each digit of a binary number, 0 or 1, is called a bit, an abbreviation for binary digit. Four bits together is a nibble, 8 bits is called a byte. (8, 16, 32, 64 bit arrangements are also called words) The rightmost bit is called the Least Significant Bit (LSB) while the leftmost bit is called the Most Significant Bit (MSB). The schematic below illustrates the general structure of a binary number and the associated labels. MSB 1010 N 1101 0110 1010 nibble   byte word LSB 1 In addition to binary digital systems and its associated binary logic, multivalued logic also exists but we will not consider it in our discussion. 6.071/22.071 Spring 2006, Chaniotakis and Cory 3 Binary to Decimal Conversion. The conversion of a binary number to a decimal number may be accomplished by taking the successive powers of 2 and summing for the result. For example let’s consider the four bit binary number 0101. The conversion to a decimal number (base 10) is illustrated below. 0 1 0 1 ↓ ↓ ↓ ↓ 3 0x2 N 2 + 1x2 N 1 + 0x2 N 0 + 1x2 N + + + ⇓ ⇓ 0 4 ⇓ 0 ⇓ 1 = 510 For this four bit binary number the range of powers of 2 goes from 0, corresponding to the LSB, to 3, corresponding to the MSB. The number 5 is shown as 510 to indicate that it is a decimal number (power of 10). The signal represented on Figure 2c has a value of 5 V at time=6τ. The binary representation of that value is 0101 and it is shown on Figure 3 replacing Level 4. We will see more of this later when we consider the fundamentals of the device which converts the analog signal to a digital signal. Signal (V) Level 7 Level 6 Level 5 0101 Level 3 Level 2 Level 1 0 τ 2τ 3τ 4τ 5τ 6τ 7τ Time Figure 3. In the next few examples we will use the subscript 2 to indicate a binary number but the subscripts will be omitted after that. 6.071/22.071 Spring 2006, Chaniotakis and Cory 4 Examples: Verify the Binary to Decimal conversion 11112 = 1510 1111 00002 = 24010 1111 11112 = 25510 1101 10112 = 21910 0001 0101 10112 = 34710 1001 0101 10112 = 239510 Decimal to Binary Conversion. The conversion of a decimal number to a binary number is accomplished by successively dividing the decimal number by 2 and recording the remainder as 0 or 1. Here is an example of the conversion of decimal number 125 to binary. 125 2 62 2 31 2 15 2 7 2 3 2 1 2 ⎫ = 62 + 1 ⎪ LSB ⎪ = 31 + 0 ⎪ ⎪ ⎪ = 15 + 1 ⎪ ⎪ ⎪ = 7 + 1 ⎪ ⎬ ⇒ 0111 1101 ⎪ = 3 + 1 ⎪ ⎪ ⎪ = 1 + 1 ⎪ ⎪ = 0 + 1 ⎪⎪ MSB ⎪ ⎪⎭ Practice number conversion by verifying the conversions from decimal to binary: Decimal 69 299 756 Binary 0100 0101 0001 0010 1011 0010 1111 0100 6.071/22.071 Spring 2006, Chaniotakis and Cory 5 Representation of fractions and signed numbers. A fractional number may be represented as a binary fraction by simply extending the procedure used in representing integer numbers. For example, 13.7510 = 1101.11002 The procedure is clearly visualized by considering the following mapping 23 8 22 4 21 20 2 1 1 1 0 1 13 2−1 2−2 2 −3 2−4 0.5 0.25 0.125 0.0625 . . 1 75 1 0 0 Signed binary numbers may be represented by assigning the MSB to indicate the sign. A 0 is used to indicate a positive number and a 1 is used to indicate a negative number. For example, an 8 bit signed binary number represents the decimal numbers from -128 to +127. Two’s complement is used to represent negative numbers. The use of 2’s complement simplifies the operation of subtraction since the circuit is only required to perform the operation of addition since X – Y = X + (-Y). The 2’s complement of a binary number is obtained by subtracting each digit of the binary number from digit 1. This is equivalent to replacing all 1’s by 0’s and all 0’s by 1’s. Negative numbers of 2’s compliment can then be found by adding 1 to the complement of a positive number. For example, the 2’s complement of the 8 bit binary number 0000 1110 is 1111 0001 = 1010 The negative number of this 2’s complement representation is 1111 0110 = -1010 The procedure is outlined in the following 0 0 0 0 1 1 1 1 1 0 1 0 binary number (1010 ) 0 1 0 1 2's complement + 1 1 1 1 1 0 1 1 0 −1010 6.071/22.071 Spring 2006, Chaniotakis and Cory 6 By adding the two numbers the result is zero as shown below. 0000 1110 (+10) + 1111 0110 (-10) 0000 0000 (0) The table below shows the 2’s complement representation of a few numbers. Fill in the empty spaces. Decimal 0 -1 -2 -3 -4 -10 -15 -27 -80 -110 2’s complement 0000 0000 1111 1111 1111 1110 1111 1101 1111 1100 1111 0110 Binary Coded Decimal. BCD Code BCD is a code used to represent each digit of a decimal number (0 to 9) as a 4 bit binary. For example, the decimal number 260 corresponds to the BDC number 0010 0110 0000. 2N 6N ⇓ 0N ⇓ Decimal ⇓ 0010 0110 0000 BDC This code is used to drive the 7 segment led displays. a b f g e c d For example, the BCD number 0010 corresponds to decimal 2 and is used to drive the segments a,b,d,e,g of the display. Similarly the number 0110 corresponds to number 6 and it is used to drive segments a,c,d,e,f,g. BCD 0000 corresponds to decimal 0 and it drives 6.071/22.071 Spring 2006, Chaniotakis and Cory 7 segments a,b,c,d,e,f. Special logic ICs are available for driving the led segments from a BCD number. Numbers with other bases. The octal system, with base 8 and digits 0,1,2,3,4,5,6,7, and the hexadecimal system with base 16 and digits 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F are also used in digital electronics. Octal and Hex representation is more compact, consider the conversion of the decimal number 1132 in binary, Octal and Hex shown below, and it is used in assembly language programming of microcontrollers. 113210 = 0100 0110 11002 = 21548 = 46C16 6.071/22.071 Spring 2006, Chaniotakis and Cory 8 Fundamental Digital Devices: The inverter. The fundamental digital circuit for performing binary operations is the one which will convert from a logic 1 to a logic 0 and vise-versa. In our discussions we will use the positive logic convention which implies that the logic level 1 will correspond to the higher voltage level and the logic level 0 will correspond to the lower voltage level. Such a fundamental is shown on Figure 4. VCC R Vo Vi 3 terminal device Figure 4. Fundamental inverter circuit. The ideal voltage transfer characteristic of this circuit is shown on Figure 5. Vo Vcc 0 Vtr Vi Figure 5. Ideal inverter voltage transfer characteristic When the input voltage exceeds the transition value Vtr, the output switches. 6.071/22.071 Spring 2006, Chaniotakis and Cory 9 It will become useful to familiarize ourselves with time evolution of digital signals. Such representation is called timing diagram which is used extensively in representing the operation of digital circuits. For our idealized inverter circuit, also called “inverter gate” a timing diagram would look like Vo 1 1 1 0 1 Vi 0 1 0 0 1 0 1 0 1 0 0 time Figure 6. Ideal inverter timing diagram. We thus see that the inverter is a voltage controlled digital switch. In practice the behavior of the inverter is not ideal. The output could assume a low value which will be in a range of voltages and a high value which also encompasses a range of voltage values. In addition the transition occurs with a time delay. The inverter circuit may be constructed with active devices such as the Field Effect Transistor (FET) or the Bipolar Junction Transistor (BJT). The inverter circuit arrangements for these fundamental devices are shown on Figure 7. VC VC VC VC Vi R Vo M Mp Vo Id Vi Ic Vi Vi Vo Q1 Mn Inverter Implementation with a FET Vo R Inverter Implementation with a BJT 2 Inverter symbol showing high (Vc) and low (ground) levels Vi Vo CMOS inverter Inverter Symbol Figure 7. Inverter circuits and inverter symbol 2 The Complementary Metal-Oxide Semiconductor (CMOS) inverter incorporates an n-channel and a pchannel MOSFET. 6.071/22.071 Spring 2006, Chaniotakis and Cory 10 The output voltage is the inverse of the input and the switching from one state to another state happens when the input voltage crosses a certain value Vtr. An inverter with supply voltages Vc and Ve and the corresponding voltage transfer characteristic is, Vo Vc VH VC Vi Vo VL Ve Vtr Ve Ve Vc Vi When Vi is less than the voltage Vtr (i.e when Vi is low) the output is VH (high). As the input voltage exceeds Vtr, (Vi is now high) the output switches to VL (low). Note that the values for VH and VL are not the same as the supply rails of the device. The actual values of VH and VL depend on the particular technology used in the construction of the inverter circuit. For each design and for the particular semiconductor technology used the supply voltages Vc and Ve are well defined. A familiar power supply for digital systems is the Vc=+5V and Ve=0V. Supply systems with, Vc, voltage levels ranging from 1.5V to 5V are available. Vo Vc VH VL Ve Ve Vtr Vi=low (0) Vc Vi Vi=high (1) In practical circuits the transition from one state to another does not happen abruptly. The transition is gradual and there is not a single value at which the transitions happen but 6.071/22.071 Spring 2006, Chaniotakis and Cory 11 rather a range of values that correspond to the transition as well as to the high and low states. This is a desirable situation since it allows for the design of robust systems with considerable noise immunity. In addition there is a range of values which correspond to a certain logic level. Figure 8 shows a generic representation of the logic levels. Logic Level 1 VH(min) Indeterminate Forbidden Region VL(max) Logic Level 0 Figure 8. Logic gate levels Any value less than VH(min) and greater than VL(max) falls in the forbidden region and its state is indeterminate. The values for VH(min) and VL(max) are different for the input and output of a gate. It is important to pay particular attention to these voltage levels since when one gate drives another, the input and output of each should fall within the specified level values. When one gate drives another as in the graphic shown on Figure 9, the various voltage levels are defined as follows: VHin(min): The minimum voltage level required for a logic level 1 at the input of a gate. VLin(max): The maximum voltage level required for a logic 0 at the input of a gate. VHout(min): The minimum voltage level required for a logic level 1 at the output of a gate. VLout(max): The maximum voltage level required for a logic 0 at the output of a gate. 6.071/22.071 Spring 2006, Chaniotakis and Cory 12 Logic Level 1 VHout(min) Logic Level 1 Noise margin HI(VNMH) VHin(min) Indeterminate Indeterminate VLin(max) Noise margin LO(VNML) VLout(max) Logic Level 0 Logic Level 0 Figure 9. Logic gate input and output voltage levels As can be seen from Figure 9, the presence of noise at the output of a certain gate may result in a voltage level which may be recognized as an appropriate state at the input of the following gate. The maximum voltage deviations due to noise that can be accepted by the logic gate inputs are defined as the HI and LO voltage noise margins, VNMH = V1out(min) – V1in(min) VNML = V0in(max) – V0out(max) These voltage levels are summarized on Figure 10. 1 VH out Noise margin H VH in Sender Indeterminate VLin VLout 1 Receiver Noise margin L 0 0 Figure 10. Voltage levels for sender and receiver. The actual values of the minimum and maximum voltage values at the input and output of the logic gates depend on the type of device used to construct the logic gate. Currently there are two dominant logic families. They are the Transistor to Transistor Logic (TTL) based on the BJT inverter shown on Figure 7 and the Complementary Metal-Oxide Semiconductor (CMOS), based on the MOS families. Besides differences in speed and power consumption, these logic families are also different in the acceptable logic voltage levels for the gates. These differences should be taken into consideration when the design involves interfacing between TTL and CMOS circuits. 6.071/22.071 Spring 2006, Chaniotakis and Cory 13 Table I provides a general comparison of the two families. TTL 5 2 0.8 2.4 0.4 0.4 0.4 Supply voltage (V) V1in(min) V0in(max) V1out(min) V0out(max) VNMH VNML CMOS 5 3.5 1.5 4.5 0.1 1.0 1.4 Table I. Comparison of TTL and CMOS logic family parameters. A few words on power consumption. Let’s consider the inverting gate, VC R Vo Vi C The capacitor C represents the wiring capacitance as well as the capacitance of the gatesource junction of the following gate. Let’s calculate the average power for an input signal Vi has the form Vi T1 T2 T 6.071/22.071 Spring 2006, Chaniotakis and Cory time 14 During time T1 the FET is on and the equivalent circuit is R Vc Vo Ron C 0 Where Ron is the on resistance of the FET. The Thevenin equivalent circuit is RTH Vo VTH C Ron R (Ron) and RTH = . By assuming that time T1>> (RTH C) R+Ron R+Ron the energy dissipated during T1 is (The details of the calculation are left as an exercise for the student) Where VTH = Vc Vc 2 T1 VTH 2C Vc 2 T1 Vc 2 R 2C E1 = + = + R+Ron  2 R+Ron 2(R+Ron) 2    Static Dynamic Static Dynamic During time T2 the equivalent circuit is R Vo Vc C During this time interval the capacitor will discharge starting from the voltage VTH reached during time T1. The energy dissipated during T2 is then (assuming T2>>RC) 6.071/22.071 Spring 2006, Chaniotakis and Cory 15 E2 = Vc 2 R 2C 2(R+Ron) 2  Dynamic The total power dissipated during one period (T), assuming that T1 = T2 is Vc 2 Vc 2 R 2C P= + 2(R+Ron) (R+Ron) 2T   Static Dynamic Since R>>Ron (usually) the total power is P= Vc 2 Vc 2C Vc 2 2 + = + Vc  f C 2 R T 2 R N N N Dynamic Static Dynamic Static The static power is independent of frequency (f=1/T). The dynamic power is proportional to frequency and the supply voltage Vc. Aw an example lets consider a digital device (chip) which incorporates 109 gates operating at a frequency of 1GHz. Typical values are: R = 10 kΩ C = 0.1 fF Vc = 5V Total power is, ⎛ 25 ⎞ Pt = 109 ⎜ + 25 x 10−16 x 109 ⎟ ⎝ 20000 ⎠ = 1250  kW + 2.5  kW Static power Dynamic power Well… something has to be done. Indeed the static power can be practically reduced to zero by the CMOS design which basically eliminates the path to ground through resistor Ron. The Dynamic power can be reduced by decreasing Vc. By going from Vc=5 V to Vc=1 V the dynamic power is reduced from 2500 W to 100 W. Not bad. 6.071/22.071 Spring 2006, Chaniotakis and Cory 16 Signal Conversion. Analog to Digital Conversion The electrical signals (voltage or current) generated by a transducer is an analog signal. The amplitude of the signal corresponds to the value of the physical phenomenon that the transducer detects. The signal values are continuous in time. The processing of the signal by a digital system requires the conversion of the analog signal to a digital signal. The analog to digital conversion is not a continuous process but it happens at discrete time intervals. Furthermore the magnitude of the digital signal at the time of conversion should correspond to the magnitude of the analog signal. The analog to digital converter (ADC) is a device that receives as its input the analog signal along with instructions regarding the sampling rate (how often is a conversion going to be performed) and scaling parameters corresponding to the desired resolution of the system. The output of the ADC is a binary number at each sampling time. The following schematic shows the basic structure of an 8 bit ADC. Reference Voltage Signal (V) 8 6 Analog Signal 4 8 Bit ADC 3 4 5 6 7 8 9 1100 1010 1100 1000 1000 0010 0101 1010 0100 1000 MSB 2 1010 0001 LSB 1 0111 1000 Pulses 0101 1111 D7 D6 D5 D4 D3 D2 D1 D0 0011 0011 Sampling signal 2 The selection of an 8 bit ADC sets the resolution of our conversion and the selection of the scale for the analog signal determines the measurement resolution for our ADC. In our example the 8 bit ADC implies 28 = 256 different levels within the maximum signal range. Since we are measuring a voltage with possible values between 0V and 10V, our 8 bit ADC 10 is not able to resolve voltages smaller than 8 mV = 39mV. 2 If this ADC has a resolution of 16 bits, like the one that you have in your laboratory, the 10 resolution, for the same measurement range, would be 16 mV=0.15mV. 2 6.071/22.071 Spring 2006, Chaniotakis and Cory 17 The table below summarizes the conversion process Pulse Signal Value 1 2 2 3.7 3 4.7 4 6.3 5 7.9 6 7.8 7 5.1 8 3.5 Level 2 256 = 51 10 3.7 256 = 95 10 4.7 256 = 120 10 6.3 256 = 161 10 7.9 256 = 202 10 7.8 256 = 200 10 5.1 256 = 130 10 3.5 256 = 90 10 Binary number 0011 0011 0101 1111 0111 1000 1010 0001 1100 1010 1100 1000 1000 0010 0101 1010 The sampling frequency must be larger than the highest frequency of the analog signal to be converted. In fact as stated by the “Sampling Theorem” The sampling frequency must be at greater than 2 times the bandwidth of the input signal. Problem: You would like to design a thermistor based thermometer with a resolution of 0.1o Celcius in the range of 0 to 100 degrees Celsius. Let’s assume that your thermistor (RT) has an accuracy of 0.001 Degrees Celsius and that the analog signal is generated by the standard voltage divider network, Design your instrument by appropriately selecting resistor R1 and the resolution of the ADC. 6.071/22.071 Spring 2006, Chaniotakis and Cory 18 Digital Logic: Boolean Algebra Boolean algebra is a special symbolic mathematical language used to carry out logic operations. Boolean algebra was developed in the mid 1800s by George Boole (1815-1864) an English mathematician, for the purpose of performing “Logic and Probability Calculations”. In Boolean algebra variables have only two possible values, 1 or 0 and it is the language used for performing binary logic operations. The basic logic operations and their corresponding Boolean representation and associated symbols are given on Table II. The variables A and B are the inputs to the functions (Gates) and can assume the value 0 or 1. The variable Y represents the output of the logic operation or equivalently the output of the logic gate and its value is also either 0 or 1. Logic Operation NOT Boolean Representation AND Y = A • B = AB OR Y=A+B NAND Y = A • B = AB NOR Y= A+B Y=A Logic Symbol (Gates) A Y A Y B A Y B A Y B A Y B Table II. Basic logic operations and their Boolean representation The NOT operation (inversion) is performed by the inverter discussed earlier and it has one input and one output. The number of inputs to the AND, OR, NOR, NAND logic gates can be greater than two. For example the Boolean representation of the 3 input NOR gate is Y = A + B + C and the corresponding logic gate is, A B C 6.071/22.071 Spring 2006, Chaniotakis and Cory Y 19 The rules associated with each logic operation (function) may be represented in a useful tabular form by the Truth Table. The Truth Tables for the basic logic operations listed on Table II are: NOT A A 0 1 Y 1 0 A Y A Y A 0 0 1 1 B 0 1 0 1 Y 0 0 0 1 A 0 0 1 1 A Y B 0 1 0 1 Y 0 1 1 1 A 0 0 1 1 A Y B B B B NOR NAND OR AND Y B 0 1 0 1 Y 1 1 1 0 A 0 0 1 1 B 0 1 0 1 Y 1 0 0 0 The designer of logic circuits and systems must optimize the design for maximum performance (i.e low power, speed, etc) and for the lowest cost. The simplification of logic expressions results in a simplified digital logic circuit. Logic expressions may be simplified by making use of the following Boolean identities. Boolean Identities A+0=A A • 1=A A+B=B+A AB=BA A + (B + C) = (A + B) + C A(BC) = (AB)C A + BC = (A +B)(A + C) A(B+C) = AB + AC A+A=A A • A = 0 A+1=1 A•A= A A • 0=0 A+ A = 1 A + AB = A A(A +B)=A (A + B) (A + C) = A + B C A + A B = A+B AB = A + B A+B = A • B The identities AB = A + B and A+B = A • B are also called DeMorgan’s Theorems and are of particular importance in logic analysis and design. The fundamental consequence of DeMorgan’s theorems is that: Any logic function may be implemented by using only OR and NOT gates or only AND and NOT gates. 6.071/22.071 Spring 2006, Chaniotakis and Cory 20 A very important consequence of Boolean algebra is the sum of products or the product of sums representation of any Boolean expression. To illustrate the usefulness of the procedure let’s consider the logic function represented by the following truth table, A 0 0 1 1 B 0 1 0 1 Y 0 1 1 0 The information in this truth table might represent the logic associated with a certain digital process that we would like to model, or it might represent the operational characteristics of a certain digital circuit that we would like to construct. The Boolean representation of the logic function is the first step in achieving a robust and efficient design. In order to construct the sum of products we proceed as follows. Identify the rows for which the result (Y in our case) is 1 (TRUE). For our 1. example these are rows 2 and 3. A 0 0 1 1 2. B 0 1 0 1 Y 0 1 1 0 Use these cases to construct the sum of products by using the uncomplemented representation of the variable that has the value of 1 and the complemented representation of the variable that has the value of 0 A 0 0 1 1 B 0 1 0 1 Y 0 1 1 0 A•B A•B ( ) ( And by taking the “sum of the products” we obtain: Y = A • B + A • B 3. ) The resulting Boolean function represents the entire logic sequence as can be verified by constructing the corresponding truth table. 6.071/22.071 Spring 2006, Chaniotakis and Cory 21 The product of sums method may also be used in order to realize the Boolean representation of the logic presented by the previous truth table. The construction of products of sums proceeds as follows. 1. Identify the rows for which the result (Y in our case) is 0 (FALSE). For our example these are rows 1 and 4. A 0 0 1 1 B 0 1 0 1 Y 0 1 1 0 2. Use these cases to construct the products of sums by using the uncomplemented representation of the variable that is 0 and the complemented representation of the variable that is 1 A 0 0 1 1 ( B 0 1 0 1 ) Y= A+B • Y 0 1 1 0 A+B A+B ( A + B) 3. The resulting Boolean function represents the entire logic sequence as can be verified by constructing the corresponding truth table. Also by manipulating the expression obtained from the application of the product of sums we obtain: ← (product of sums) A+ B • ( A + B ) = ( ) ( AB ) • ( A + B) = ( AB ) •A + ( AB ) •B= ( A+B) •A + ( A+B) •B= ( A+B) •A + ( A+B) •B= ( A•A+B•A ) + ( A•B+B•B) = ( 0+B•A ) + ( A•B+0) = ( B•A ) + ( A•B) = ( A•B) + ( A•B) 6.071/22.071 Spring 2006, Chaniotakis and Cory ← sum of products 22 The two methods are equivalent. The choice of which method to use is based on the details of the logic function to be implemented. For example, is we are considering a 3 input logic sequence for which the result is true (1) for 2 out of the eight (23) possible cases then the reduced algebraic complexity associated with the use of the sum of products approach will be advantageous. A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y1 0 1 0 0 0 1 0 0 A•B•C A•B•C Work with Sum of Products Y1= A•B•C + A•B•C ( ) ( ) A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y2 0 1 1 1 0 1 1 1 A+B+C A+B+C Work with Products of Sums Y2= ( A+B+C ) • A+B+C ( ) Two additional useful gates: XOR and XNOR The gate represented by the truth table A B Y 0 0 0 0 1 1 1 0 1 1 1 0 Is very useful and it is called Exclusive OR (XOR). The symbol of this gate is A B Y A B Y Another useful gate is the Exclusive NOR gate (XNOR). The truth table and the symbol for this gate are A B Y 0 0 1 0 1 0 1 0 0 1 1 1 6.071/22.071 Spring 2006, Chaniotakis and Cory 23 For the laboratory As an example lets design an adder which is able to add two 1 bit digital numbers. This is called a 1 bit adder and schematically has the form A B ci 1 bit adder Ci+1 S A and B are the digits to be added. Ci is the carry from the previous addition and Ci+1 is the carry after the addition. The basic rules for binary addition are: 1 + 1 = 0, Carry = 1 1 + 0 = 1, Carry = 0 0 + 1 = 1, Carry = 0 0 + 0 = 0, Carry = 0 The first thing to do is construct the truth table for this procedure. A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 Ci 0 1 0 1 0 1 0 1 S 0 1 1 0 1 0 0 1 Ci+1 0 0 0 1 0 1 1 1 As part of your laboratory you will design and then built this 1 bit full adder circuit using fundamental gates. Download the instrument called adder.vi from the class web site. Take a minute to familiarize yourself with the instrument. Your goal is to construct the circuit by using the 6.071/22.071 Spring 2006, Chaniotakis and Cory 24 gates provided and then run it to see the results. You may also view the results on the ELVIS leds by wiring DO0 - DO4 to LED0 - LED4. Try simplifying your circuit by using the XOR or the XNOR gates. 6.071/22.071 Spring 2006, Chaniotakis and Cory 25 With this as your basic 1 bit adder circuit you will then built and test an adder circuit for two 4 bit binary numbers. The structure of the circuit is A3 B3 1 bit adder C3 A2 B2 1 bit adder C2 S3 A1 B1 1 bit adder C1 S2 A0 B0 1 bit adder C0 S1 S0 This circuit will add numbers A0A1A2A3 and B0B1B2B3 by propagating the carry bit 6.071/22.071 Spring 2006, Chaniotakis and Cory 26