Digital Electronics Part I – Combinational And Sequential .
Digital ElectronicsPart I – Combinational andSequential LogicDr. I. J. Wassell
Introduction
Aims To familiarise students with– Combinational logic circuits– Sequential logic circuits– How digital logic gates are built usingtransistors– Design and build of digital logic systems
Course Structure 11 Lectures Hardware Labs– 6 Workshops– 7 sessions, each one 3h, alternate weeks– Thu. 10.00 or 2.00 start, beginning week 3– In Cockroft 4 (New Museum Site)– In groups of 2
Objectives At the end of the course you should– Be able to design and construct simpledigital electronic systems– Be able to understand and apply Booleanlogic and algebra – a core competence inComputer Science– Be able to understand and build statemachines
Books Lots of books on digital electronics, e.g.,– D. M. Harris and S. L. Harris, ‘Digital Designand Computer Architecture,’ Morgan Kaufmann,2007.– R. H. Katz, ‘Contemporary Logic Design,’Benjamin/Cummings, 1994.– J. P. Hayes, ‘Introduction to Digital LogicDesign,’ Addison-Wesley, 1993. Electronics in general (inc. digital)– P. Horowitz and W. Hill, ‘The Art of Electronics,’CUP, 1989.
Other Points This course is a prerequisite for– ECAD (Part IB)– VLSI Design (Part II) Keep up with lab work and get it ticked. Have a go at supervision questions plusany others your supervisor sets. Remember to try questions from pastpapers
Semiconductors to Computers Increasing levels of complexity– Transistors built from semiconductors– Logic gates built from transistors– Logic functions built from gates– Flip-flops built from logic– Counters and sequencers from flip-flops– Microprocessors from sequencers– Computers from microprocessors
Semiconductors to Computers Increasing levels of abstraction:– Physics– Transistors– Gates– Logic– Microprogramming (Computer Design Course)– Assembler (Computer Design Course)– Programming Languages (Compilers Course)– Applications
Combinational Logic
Introduction to Logic Gates We will introduce Boolean algebra andlogic gates Logic gates are the building blocks ofdigital circuits
Logic Variables Different names for the same thing– Logic variables– Binary variables– Boolean variables Can only take on 2 values, e.g.,– TRUE or False– ON or OFF– 1 or 0
Logic Variables In electronic circuits the two values canbe represented by e.g.,– High voltage for a 1– Low voltage for a 0 Note that since only 2 voltage levels areused, the circuits have greater immunityto electrical noise
Uses of Simple Logic Example – Heating Boiler– If chimney is not blocked and the house is coldand the pilot light is lit, then open the main fuelvalve to start boiler.b chimney blockedc house is coldp pilot light litv open fuel valve– So in terms of a logical (Boolean) expressionv (NOT b) AND c AND p
Logic Gates Basic logic circuits with one or moreinputs and one output are known asgates Gates are used as the building blocks inthe design of more complex digital logiccircuits
Representing Logic Functions There are several ways of representinglogic functions:– Symbols to represent the gates– Truth tables– Boolean algebra We will now describe commonly usedgates
NOT GateSymbolaTruth-tableyay0110Booleany a A NOT gate is also called an ‘inverter’ y is only TRUE if a is FALSE Circle (or ‘bubble’) on the output of a gateimplies that it as an inverting (orcomplemented) output
AND GateSymbolabTruth-tableya by001100010101Booleany a.b y is only TRUE only if a is TRUE and b isTRUE In Boolean algebra AND is represented bya dot .
OR GateSymbolabTruth-tableya by001101110101Booleany a b y is TRUE if a is TRUE or b is TRUE (orboth) In Boolean algebra OR is represented bya plus sign
EXCLUSIVE OR (XOR) GateSymbolabTruth-tableya by001101100101Booleany a b y is TRUE if a is TRUE or b is TRUE (butnot both) In Boolean algebra XOR is represented byan sign
NOT AND (NAND) GateSymbolabTruth-tableya by001111100101Booleany a.b y is TRUE if a is FALSE or b is FALSE (orboth) y is FALSE only if a is TRUE and b isTRUE
NOT OR (NOR) GateSymbolabTruth-tableya by001110000101Booleany a b y is TRUE only if a is FALSE and b isFALSE y is FALSE if a is TRUE or b is TRUE (orboth)
Boiler Example If chimney is not blocked and the house iscold and the pilot light is lit, then open themain fuel valve to start boiler.b chimney blockedp pilot light litbcpc house is coldv open fuel valvev b .c. p
Boolean Algebra In this section we will introduce the lawsof Boolean Algebra We will then see how it can be used todesign combinational logic circuits Combinational logic circuits do not havean internal stored state, i.e., they haveno memory. Consequently the output issolely a function of the current inputs. Later, we will study circuits having astored internal state, i.e., sequentiallogic circuits.
Boolean AlgebraORa 0 aa a aa 1 1a a 1ANDa.0 0a.a aa.1 aa.a 0 AND takes precedence over OR, e.g.,a.b c.d (a.b) (c.d )
Boolean Algebra Commutation Associationa b b aa.b b.a( a b) c a (b c)( a.b).c a.(b.c) Distribution Absorptiona.(b c ) (a.b) (a.c) a (b.c. ) (a b).(a c). NEWa (a.c) aa.( a c) aNEWNEW
Boolean Algebra - ExamplesShowa.( a b) a.ba.( a b) a.a a.b 0 a.b a.bShowa (a .b) a ba (a .b) (a a ).(a b) 1.(a b) a b
Boolean Algebra A useful technique is to expand eachterm until it includes one instance of eachvariable (or its compliment). It may bepossible to simplify the expression bycancelling terms in this expanded forme.g., to prove the absorption rule:a a.b aa.b a.b a.b a.b a.b a.(b b ) a.1 a
Boolean Algebra - ExampleSimplifyx. y y.z x.z x. y.zx. y.z x. y.z x. y.z x. y.z x. y.z x. y.z x. y.zx. y.z x. y.z x. y.z x. y.zx. y.( z z ) y.z.( x x )x. y.1 y.z.1x. y y.z
DeMorgan’s Theorema b c a .b .c . a.b.c. a b c In a simple expression like a b c (or a.b.c )simply change all operators from OR toAND (or vice versa), complement eachterm (put a bar over it) and thencomplement the whole expression, i.e.,a b c a .b .c . a.b.c. a b c
DeMorgan’s Theorem For 2 variables we can show a b a .band a.b a b using a truth table.a b a b a.b a b001101011000111011001010a.b a b10001110 Extending to more variables by inductiona b c (a b).c (a .b ).c a .b .c
DeMorgan’s Examples Simplify a.b a.(b c) b.(b c) a.b a.b .c b.b .c (DeMorgan) a.b a.b .c (b.b 0) a.b (absorbtion)
DeMorgan’s Examples Simplify (a.b.(c b.d ) a.b).c.d (a.b.(c b d ) a b ).c.d(De Morgan) (a.b.c a.b.b a.b.d a b ).c.d(distribute) (a.b.c a.b.d a b ).c.d(a.b.b 0) a.b.c.d a.b.d .c.d a .c.d b .c.d(distribute) a.b.c.d a .c.d b .c.d(a.b.d .c.d 0) (a.b a b ).c.d(distribute) (a.b a.b).c.d(DeMorgan) c.d(a.b a.b 1)
DeMorgan’s in Gates To implement the function f a.b c.d wecan use AND and OR gatesabfcd However, sometimes we only wish touse NAND or NOR gates, since theyare usually simpler and faster
DeMorgan’s in Gates To do this we can use ‘bubble’ logicabxfcdyTwo consecutive ‘bubble’ (orcomplement) operations cancel,i.e., no effect on logic functionWhat about this gate?DeMorgan says x ySee AND gates arenow NAND gatesSois equivalent to x. yWhich is a NOTAND (NAND) gate
DeMorgan’s in Gates So the previous function can be builtusing 3 NAND gatesababfcdfcd
DeMorgan’s in Gates Similarly, applying ‘bubbles’ to the inputof an AND gate yieldsxyfWhat about this gate?DeMorgan says x . y SoWhich is a NOT OR(NOR) gatex yis equivalent to Useful if trying to build using NOR gates
Logic Minimisation Any Boolean function can be implementeddirectly using combinational logic (gates) However, simplifying the Boolean function willenable the number of gates required to bereduced. Techniques available include:– Algebraic manipulation (as seen in examples)– Karnaugh (K) mapping (a visual approach)– Tabular approaches (usually implemented bycomputer, e.g., Quine-McCluskey) K mapping is the preferred technique for up toabout 5 variables
Truth Tables f is defined by the following truth tablex y z f minterms0 0 0 1 x . y.z0 0 1 1 x . y.z0 1 0 1 x . y.z0 1 1 1 x . y.z1111001101010001x. y.z A minterm must containall variables (in eithercomplement oruncomplemented form) Note variables in aminterm are ANDedtogether (conjunction) One minterm for eachterm of f that is TRUE So x. y.z is a minterm but y.z is not
Disjunctive Normal Form A Boolean function expressed as thedisjunction (ORing) of its minterms is saidto be in the Disjunctive Normal Form (DNF)f x . y.z x. y.z x. y.z x . y.z x. y.z A Boolean function expressed as theORing of ANDed variables (not necessarilyminterms) is often said to be in Sum ofProducts (SOP) form, e.g.,f x y.zNote functions have the same truth table
Maxterms A maxterm of n Boolean variables is thedisjunction (ORing) of all the variables eitherin complemented or uncomplemented form.– Referring back to the truth table for f, we canwrite,f x. y.z x. y.z x. y.zApplying De Morgan (and complementing) givesf ( x y z ).( x y z ).( x y z )So it can be seen that the maxterms of f areeffectively the minterms of f with each variablecomplemented
Conjunctive Normal Form A Boolean function expressed as theconjunction (ANDing) of its maxterms is saidto be in the Conjunctive Normal Form (CNF)f ( x y z ).( x y z ).( x y z ) A Boolean function expressed as the ANDingof ORed variables (not necessarily maxterms)is often said to be in Product of Sums (POS)form, e.g.,f ( x y ).( x z )
Logic Simplification As we have seen previously, Booleanalgebra can be used to simplify logicalexpressions. This results in easierimplementationNote: The DNF and CNF forms are notsimplified. However, it is often easier to use atechnique known as Karnaugh mapping
Karnaugh Maps Karnaugh Maps (or K-maps) are apowerful visual tool for carrying outsimplification and manipulation of logicalexpressions having up to 5 variables The K-map is a rectangular array ofcells– Each possible state of the input variablescorresponds uniquely to one of the cells– The corresponding output state is written ineach cell
K-maps example From truth table to K-mapx y z f00001111001100110101010111110001yzzx00 01 11 100 1 1 1 11x 1yNote that the logical state of thevariables follows a Gray code, i.e.,only one of them changes at a timeThe exact assignment of variables interms of their position on the map isnot important
K-maps example Having plotted the minterms, how do weuse the map to give a simplifiedexpression? Group termszyzx00 01 11 100 1 1 1 11x 1xy.zy Having size equal to a power of2, e.g., 2, 4, 8, etc. Large groups best since theycontain fewer variables Groups can wrap around edgesand cornersSo, the simplified func. is,f x y.z as before
K-maps – 4 variables K maps from Boolean expressions– Plot f a .b b.c .dccda00 01 11 10ab0001 1 1 1 111 1b10d See in a 4 variable map:– 1 variable term occupies 8 cells– 2 variable terms occupy 4 cells– 3 variable terms occupy 2 cells, etc.
K-maps – 4 variables For example, plotf bf b .dcccdcd00 01 11 10ab00 1 1 1 101a111000 01 11 10ab100 101b111d1a1110b11d
K-maps – 4 variables Simplify, f a .b.d b.c.d a .b.c .d c.dccd00 01 11 10ab00101 1 1 1 11a 11110a.bdSo, the simplified func. is,f a .b c.dbc.d
POS Simplification Note that the previous examples haveyielded simplified expressions in theSOP form– Suitable for implementations using ANDfollowed by OR gates, or only NAND gates(using DeMorgans to transform the result –see previous Bubble logic slides) However, sometimes we may wish toget a simplified expression in POS form– Suitable for implementations using ORfollowed by AND gates, or only NOR gates
POS Simplification To do this we group the zeros in the map– i.e., we simplify the complement of the function Then we apply DeMorgans andcomplement Use ‘bubble’ logic if NOR onlyimplementation is required
POS Example Simplify f a .b b.c .d into POS form.ccdab0001a1110ccd00 01 11 101111d1b00 01ab00 0 0Group01 1 1zeros1 011a10 0 0ba.d11 1001000100df b a.c a.da.cb
POS Example Applying DeMorgans tof b a.c a.dfgives,f b.(a c ).(a d )f b.(a c ).(a d )acfadbacadbacfadb
Expression in POS form Apply DeMorgans and takecomplement, i.e., f is now in SOP form Fill in zeros in table, i.e., plot f Fill remaining cells with ones, i.e., plot f Simplify in usual way by grouping onesto simplify f
Don’t Care Conditions Sometimes we do not care about theoutput value of a combinational logiccircuit, i.e., if certain input combinationscan never occur, then these are knownas don’t care conditions. In any simplification they may be treatedas 0 or 1, depending upon which givesthe simplest result.– For example, in a K-map they are enteredas Xs
Don’t Care Conditions - Example Simplify the function f a .b .d a .c.d a.c.dWith don’t care conditions, a .b .c .d , a .b .c.d , a .b.c .dccd00 01 11 10ab00 X 1 1 XX 1011a 11110bSee only need to includeXs if they assist in makinga bigger group, otherwisecan ignore.c.da.bdf a .b c.d or,f a .d c.d
Some Definitions Cover – A term is said to cover a minterm if thatminterm is part of that term Prime Implicant – a term that cannot be furthercombined Essential Term – a prime implicant that covers aminterm that no other prime implicant covers Covering Set – a minimum set of primeimplicants which includes all essential terms plusany other prime implicants required to cover allminterms
Number Representation,Addition and Subtraction
Binary Numbers It is important to be able to representnumbers in digital logic circuits– for example, the output of a analogue to digitalconverter (ADC) is an n-bit number, where n istypically in the range from 8 to 16 Various representations are used, e.g.,– unsigned integers– 2’s complement to represent negative numbers
Binary Numbers Binary is base 2. Each digit (known as abit) is either 0 or 1. Consider these 6-bit unsigned numbers1 0 1 0 1 0 421032 16 8 4 2 1 Binary25 24 23 22 21 20 coefficientsMSBLSB 11100 0 1 0 1 132 16 8 4 2 1 Binary25 24 23 22 21 20 coefficientsMSBLSBMSB – mostsignificant bitLSB – leastsignificant bit
Unsigned Binary Numbers In general, an n-bit binary number, bn 1bn 2 b1b0has the decimal value,n 1 bi 2ii 0 So we can represent positive integers from0 to 2n 1 In computers, binary numbers are often 8bits long – known as a byte A byte can represent unsigned values from0 to 255
Unsigned Binary Numbers Decimal to binary conversion. Performsuccessive division by 2.– Convert 4210 into binary42 / 2 21 remainder 021 / 2 10 remainder 110 / 2 5 remainder 05 / 2 2 remainder 12 / 2 1 remainder 01 / 2 0 remainder 1 So the answer is 1010102 (reading upwards)
Octal: Base 8 We have seen base 2 uses 2 digits (0 & 1),not surprisingly base 8 uses 8 digits : 0, 1,2, 3, 4, 5, 6, 7.0 5 2 421064 8 1 Octal82 81 80 coefficientsMSBLSB To convert from decimal to base 8 eitheruse successive division, i.e.,42 / 8 5 remainder 25 / 8 0 remainder 5 So the answer is 528 (reading upwards)
Octal: Base 8 Or alternatively, convert to binary, dividethe binary number into 3-bit groups andwork out the octal digit to representeach group. We have shown that4210 1010102 So,1MSB051 01 028LSB 4210
Hexadecimal: Base 16 For base 16 we need 16 different digits.Consequently we need new symbols forthe digits to represent 10-1510102 1010 A1611012 1310 D1610112 1110 B1611102 1410 E1611002 1210 C1611112 1510 F160 2 A16 4210256 16 1 Hex162 161 160 coefficientsMSBLSB
Hex: Base 16 To convert from decimal to base 16 useeither use successive division by 16, i.e.,42 / 16 2 remainder A2 / 16 0 remainder 2 So the answer is 2A8 (reading upwards)
Hex: Base 16 Or alternatively, convert to binary, dividethe binary number into 4-bit groups andwork out the hex digit to represent eachgroup. We have shown that4210 1010102 So,0 0 12MSB010 1 0A16LSB 4210
Hex: Base 16 Hex is also used as a convenient way ofrepresenting the contents of a byte (an8 bit number), so for example 1110001021 1 1EMSB000 1 0216LSB E 216
Negative numbers So far we have only been able to representpositive numbers. For example, we haveseen an 8-bit byte can represent from 0 to255, i.e., 28 256 different combinations ofbits in a byte If we want to represent negative numbers,we have to give up some of the range ofpositive numbers we had before– A popular approach to do this is called 2’scomplement
2’s Complement For 8-bit numbers:00Hpositive127 1287 FH 80Hnegative 1FFH Note all negative numbers have theMSB set The rule for changing a positive 2’scomplement number into a negative 2’scomplement number (or vice versa) is:Complement all the bits and add 1.
2’s Complement What happens when we do this to an 8 bitbinary number x ?– Invert all bits: x (255 x)– Add 1: x (256 x) Note: 256 ( 100H) will not fit into an 8 bitbyte. However if we ignore the ‘overflow’ bit,then 256 x behaves just like 0 x That is, we can use normal binary arithmeticto manipulate the 2’s complement of x and itwill behave just like -x
2’s Complement Addition0 0 0 0 0 1 1 170 0 0 0 0 1 0 0 4(0) 0 0 0 0 1 0 1 1 11 To subtract, negate the second number, then add:70 0 0 0 0 1 1 11 1 1 1 1 0 0 1 7(1) 0 0 0 0 0 0 0 000 0 0 0 1 0 0 191 1 1 1 1 0 0 1 7(1) 0 0 0 0 0 0 1 02
2’s Complement Addition0 0 0 0 0 1 0 041 1 1 1 1 0 0 1 7( 0) 1 1 1 1 1 1 0 1 31 1 1 1 1 0 0 1 71 1 1 1 1 0 0 1 7(1) 1 1 1 1 0 0 1 0 14
2’s Complement Note that for an n-bit number bn 1bn 2 b1b0 ,the decimal equivalent of a 2’s complementnumber is,n 2 bn 1 2n 1 ib 2 ii 0 For example, 1 1 1 1 0 0 1 06 b7 27 bi 2ii 0 1 27 1 26 1 25 1 24 1 21 128 64 32 16 2 14
2’s Complement Overflow For example, when working with 8-bitunsigned numbers, we can use the‘carry’ from the 8th bit (MSB) to indicatethat the number has got too big. With signed numbers we deliberatelyignore any carry from the MSB,consequently we need a new rule todetect when a result is out of range.
2’s Complement Overflow The rule for detecting 2’s complementoverflow is:– The carry into the MSB does not equal thecarry out from the MSB. We will now give some examples.
2’s Complement Overflow0 0 0 0 1 1 1 1150 0 0 0 1 1 1 1 15(0) 0 0 0 1 1 1 1 0 30OK0 1 1 1 1 1 1 1 1270 0 0 0 0 0 0 1 1(0) 1 0 0 0 0 0 0 0 128 overflow
2’s Complement Overflow1 1 1 1 0 0 0 1 151 1 1 1 0 0 0 1 15(1) 1 1 1 0 0 0 1 0 30 OK1 0 0 0 0 0 0 1 1271 1 1 1 1 1 1 0 2(1) 0 1 1 1 1 1 1 1 127 overflow
Binary Coded Decimal (BCD) Each decimal digit of a number is codedas a 4 bit binary quantity It is sometimes used since it is easy tocode and decode, however it is not anefficient way to store numbers.124810 0001 0010 0100 1000BCD123410 0001 0010 0011 0100BCD
Alphanumeric Character Codes ASCII: American Standard Code forInformation Exchange:– Standard version is a 7 bit code with theremaining bit usually set to zero– The first 32 are ‘control codes’ originally usedfor controlling modems– The rest are upper and lower case letters,numbers and punctuation.– An extended version uses all 8 bits toprovide additional graphics characters
Alphanumeric Character Codes EBCDIC – a legacy IBM scheme, now littleused Unicode – a 16 bit scheme, includesChinese characters etc.
Binary Adding Circuits We will now look at how bina
design combinational logic circuits Combinational logic circuits do not have an internal stored state, i.e., they have no memory. Consequently the output is solely a function of the current inputs. Later, we will study circuits having a stored internal
Texts of Wow Rosh Hashana II 5780 - Congregation Shearith Israel, Atlanta Georgia Wow ׳ג ׳א:׳א תישארב (א) ׃ץרֶָֽאָּהָּ תאֵֵ֥וְּ םִימִַׁ֖שַָּה תאֵֵ֥ םיקִִ֑לֹאֱ ארָָּ֣ Îָּ תישִִׁ֖ארֵ Îְּ(ב) חַורְָּ֣ו ם
3.5 Combinational Circuits 138 Digital logic chips are combined to give us useful circuits. These logic circuits can be categorized as either combinational logic (Section 3.5) or sequential logic (Sec. 3.6). 3.5.1 Basic Concepts 138 The key concept in recognizing a combinational circu
The University of Texas at Arlington Sequential Logic - Intro CSE 2340/2140 – Introduction to Digital Logic Dr. Gergely Záruba The Sequential Circuit Model x 1 Combinational z1 x n zm (a) y y Y Y Combinational logic logic x1 z1 x n z m Combinational logic with n inputs and m switching functions: Sequential logic with n inputs, m outputs, r .
3 Introduction Logic circuits for digital systems may be – Combinational – Sequential A combinational circuit consists of logic gates whose outputs at any time are determined by the current input values, i.e., it has no memory elements A sequential circuit consists of logic gates whose outputs at any time are determi
An arithmetic circuit is a combinational circuit that performs arithmetic operations such as addition, subtraction, multiplication and division with binary numbers or with decimal numbers in a binary code. A combinational
Apr 03, 2020 · Combinational logic circuits 2. Sequential logic circuit. Compare combinational and sequential circuits (four points). Standard representation for logical functions: Boolean expressions / logic expressions / logical functions are expressed in terms of logical variables. Log
combinational logic. This is an ideal location to introduce the language because the reader has just learned about combinational logic theory inChap. 4. This allows the student to begin gainingexperience using the VHDL simulation tools on basic combinational
Adventure Tourism has grown exponentially worldwide over the past years with tourists visiting destinations previously undiscovered. This allows for new destinations to market themselves as truly .
