COMP3222/9222 Digital Circuits & Systems 21T3 L01 - Introduction Course website: www.cse.unsw.edu.au/~cs3222 Oliver Diessel O: K17-501B E: [email protected] P: 9385 7384 Introduction What you will learn in this class • Introduction to the design of digital logic circuits – Boolean algebra, logic minimization, combinational logic components, sequential circuits, simple systems • Principles of creating digital circuit designs – using VHDL hardware description language – simulation techniques to verify the correct working of designs – logic compilers to synthesize hardware – implementing and testing designs using programmable hardware 20T3 COMP3222/9222 L01/S2 Introduction What is logic design? • What is design? – given a specification of a problem, come up with a way of solving it choosing appropriately from a collection of available tools, techniques and components – while meeting certain performance criteria for size, cost, power, beauty, elegance, etc. • What is logic design? – determining the collection of digital logic components and the interconnections between them to perform a specified data gathering, processing, storage, control and/or communication function – which logic components to choose? – there are many implementation technologies, with differing costs/benefits – the design may need to be optimized and/or transformed to meet design constraints 20T3 COMP3222/9222 L01/S3 Introduction Applications of logic design • Computer hardware & systems – design of processors, CPUs, systems, accelerators, custom chips, buses, interfaces, memories, peripherals • Communications & networks – I/O devices, phones, switches, routers, base stations, satellites • Embedded systems – consumer electronics, appliances, entertainment devices, IoT, medical devices, security, transport, robotics, mining, agriculture and manufacturing equipment • Scientific instruments & equipment – simulation, testing, sensing, logging, reporting, analyzing • Challenge: – Which human activities (a) don’t yet, and (b) won’t ever involve digital technology? 20T3 COMP3222/9222 L01/S4 Introduction Why study logic design? • Obvious reasons – fundamental abstraction for implementing all digital devices – to study the digital design process – this course is part of the CompEng requirements • Other important reasons – it’s an important counterpart to software design – it’s essential to furthering our understanding of the efficient implementation of computation – the inherent parallelism in hardware provides exposure to real parallelism on a large, fine-grained scale 20T3 COMP3222/9222 low cost high performance L01/S5 COMP3222/9222 details • Lectures, Weeks 1 – 10 – Mon 16-18 Colombo Th B – Wed 14-16 Ainsworth G02 • Labs, Weeks 1 – 10 – 2 hr Labs: Tue 12-14, Wed 16-18, Wed 18-20, Thu 10-12, Thu 12-14 in K17 Lyre lab – Pick up take-home lab kit during first lab (this week) • Tutes, Weeks 2 – 10 – 1 hr Tutes: Tue 14-15, Tue 15-16 Quad G045, Thu 14-15, Thu 15-16 Quad G031 21T3 COMP3222/9222 Introduction L01/S6 5, 7-10 Recordings availa le on website for asynchronous viewing • I assume you have viewed the relevant recording before the synchronous meetings – see the Lecture schedule on the course website – Synchronous meetings to review main points, discuss questions and work through exercises: Mon 14–16 & Wed 16–18 • Labs, Weeks 1 – 10 – Lab exercises and resources available on website – 3 hr official online drop-in session where you can obtain help and ask questions of demostrators: Wed 12–15 – 2 hr optional online drop-in sessions: Tue 14–16, Thu 12–14 – Submissions due roughly each week on Mondays at 23:59 COMP3222/9222 assessment • Assessment: – 7 lab exs (due the week after they are scheduled): 40% total – 4 fortnightly quizzes on theory in Weeks 3, 5, 7 & 9: 15% total – 1 hr Final Theory Test: 15% – 2 hr Final Practical Test: 30% (need to score >40% in Prac Exam to pass course) • Supplementaries – Only one eligibility criterion: 1. Need to score >45% overall and >36% in Practical Test ⇒ final score = 50% if supp passed 2. Certified medical excuse ⇒ final score calculated as if sitting normal exam – Note: there is no supp for missing the lab submission deadlines or quizzes 21T3 COMP3222/9222 Introduction L01/S7 Introduction COMP3222/9222 text • Brown & Vranesic, Fundamentals of Digital Logic with VHDL Design, 3ed, McGraw-Hill – out of print, so not available at bookshop – available for short loan from the Library – exercises drawn from text – extracts of Ch 1 & 2 provided on course website – text is designed to be used with the FPGA board you will be using • contains tutorials on loading & using the CAD tools • provides a detailed reference on VHDL • will be an invaluable aid in the follow-on computer architecture & design project courses 21T3 COMP3222/9222 L01/S8 Introduction Acknowledgement • Most of the slides in this course are modified from the current text (Brown & Vranesic), or from Katz, Contemporary Logic Design, 2ed, Pearson • The material provided by these authors is gratefully acknowledged 20T3 COMP3222/9222 L01/S9 Introduction Digital circuits • The study of digital logic circuits is primarily motivated by their use in digital computers • Logic circuits perform operations on digital signals and are usually implemented as electronic circuits in which the signal values are restricted to a few discrete values – In binary logic circuits, there are only two values, 0 and 1 – Decimal logic circuits would have 10 values • In contrast, in analog circuits, signals may take on continuous values between maximum and minimum levels • We will only consider binary digital circuits – These are dominant because of their simplicity – The simplest binary element is a switch that has two states 20T3 COMP3222/9222 L01/S10 Introduction • We say the switch is controlled by input variable x, and that the switch is open if x = 0 and closed if x = 1 x 1 = x 0 = (a) Two states of a switch S x (b) Symbol for a switch A binary switch 20T3 COMP3222/9222 open closed L01/S11 • The state of the light L is dependent on the state of the switch • The light is on, L = 1, if the switch is closed, x = 1, and vice versa • Thus L(x) = x • li t i , 1, if the switch is closed, x = 1, and vice versa • Thus L(x) = x Introduction (a) Simple connection to a battery S (b) An equivalent circuit using a ground connection as the return path Battery Light Power supply S Light x x A light controlled by a switch 20T3 COMP3222/9222 L01/S12 Introduction (a) The logical AND function (series connection) S Power supply S S Power supply S (b) The logical OR function (parallel connection) Light Light x1 x2 x1 x2 Two basic functions • In a series connection, both switches need to be closed for the light to be on • Thus, L(x1, x2) = x1 ∙ x2 20T3 COMP3222/9222 L01/S13 • In a parallel connection, either one of the switches need to be closed for the light to be on • Thus, L(x1, x2) = x1 + x2 Introduction S Power supply S Light S X1 X2 X3 A series-parallel connection L(x1, x2, x3) = ? 20T3 COMP3222/9222 L01/S14 Which function determines the output of the light? How many possible states are there for this circuit? How many of these have the light on? Introduction • Since the switch, when it is closed, short-circuits the potential difference across the light: L(x) = x, where L = 1 if x = 0 and L = 0 if x = 1 • The complement op, NOT, is expressed in many ways: x = x’ = !x = ~x = NOT x S Light Power supply R x Inversion 20T3 COMP3222/9222 L01/S15 Introduction Truth tables for the AND, OR and NOT operations 20T3 COMP3222/9222 L01/S16 AND OR NOT x 1 x 2 x n x 1 x 2 … x n + + + x 1 x 2 x 1 x 2 + x 1 x 2 x n x 1 x 2 x 1 x 2 ∙ x 1 x 2 … x n ∙ ∙ ∙ (a) AND gates (b) OR gates x x (c) NOT gate Basic gate symbols • Each logic operation can be implemented electronically with transistors, resulting in a circuit element called a logic gate • Each logic gate has one or more inputs and one output that is a function of its inputs • A logic circuit is often described by drawing a circuit diagram, or schematic, consisting of graphical symbols representing the logic gates 20T3 COMP3222/9222 L01/S17 Introduction • A larger circuit is implemented by a network of gates • Such circuits are called logic networks or logic circuits • The complexity of a given network (in terms of the gate count & number of gate inputs) has a direct impact on its cost • In order to reduce manufactured cost, we seek ways to implement logic circuits as inexpensively as possible – Smaller (simpler) circuits are also faster and less susceptible to failure x 1 x 2 x 3 f x 1 x 2 + ( ) x 3 ∙= The function from L01/S14 20T3 COMP3222/9222 L01/S18 Introduction Analyzing a logic network x 1 x 2 f 1 0 1 0 0 1 0 1 0 ® ® ® 0 0 1 ® ® ® 1 0 1 ® ® ® 0 1 ® ® ® 1 0 1 ® ® ® A B 1 0 1 0 1 0 1 0 1 0 x 1 x 2 A B f Time (c) Timing diagram/waveform (a) Network that implements f = A + B 1 1 0 0 ® ® ®0 0 1 1 ® ® ® 1 1 0 1 ® ® ®0 1 0 1 ® ® ® g x 1 x 2 (d) Network that implements g x1 x2+ = Note that g implements the same function as f but at a lower cost! 20T3 COMP3222/9222 x 1 x 2 f x 1 x 2, ( ) 0 1 0 1 0 0 1 1 1 1 0 1 (b) Truth table A B 1 1 0 0 0 0 0 1 L01/S19 x 1 x 1 x 2∙+ = Introduction Axioms and theorems of Boolean algebra The theory underlying the simplification of logic expressions and their cir- cuit realization is founded on the axioms and theorems of Boolean algebra • identity 1. X + 0 = X • null 2. X + 1 = 1 2D. X • 0 = 0 • idempotency: 3. X + X = X 3D. X • X = X • involution: 4. (X’)’ = X • complementarity: 5. X + X’ = 1 5D. X • X’ = 0 • commutativity: 6. X + Y = Y + X 6D. X • Y = Y • X • associativity: 7. (X + Y) + Z = X + (Y + Z) 7D. (X • Y) • Z = X • (Y • Z) Dual X is a Boolean variable with two possible values: true = 1 or false = 0 20T3 COMP3222/9222 1D. X • 1 = X L01/S20 Introduction Axioms and theorems of Boolean algebra • distributivity: 8. X • (Y + Z) = (X • Y) + (X • Z) 8D. X + (Y • Z) = • uniting: (X + Y) • (X + Z) 9. X • Y + X • Y’ = X 9D. (X + Y) • (X + Y’) = X • absorption: 10. X + X • Y = X 10D. X • (X + Y) = X 11. (X + Y’) • Y = X • Y 11D. (X • Y’) + Y = X + Y • factoring: 12. (X + Y) • (X’ + Z) = 12D. X • Y + X’ • Z = X • Z + X’ • Y (X + Z) • (X’ + Y) • consensus: 13. X • Y + X’ • Z + Y • Z = 13D. (X + Y) • (X’ + Z) • (Y + Z) = X • Y + X’ • Z (X + Y) • (X’ + Z) 20T3 COMP3222/9222 L01/S21 • de Morgan’s: 14. (X + Y + ...)’ = X’ • Y’ • ... 14D. (X • Y • ...)’ = X’ + Y’ + ... • generalized de Morgan’s: 15. f(X1,X2,...,Xn,0,1,+,•) = f(X1,X2,...,Xn,1,0,•,+) • establishes relationship between • and + Example: f = x2 + x1x3 Þ f = x2 + x1x3 = x2 • x1x3 = x2 • (x1 + x3) = x2 • (x1 + x3) Introduction Axioms and theorems of Boolean algebra 20T3 COMP3222/9222 L01/S22 Introduction Axioms and theorems of Boolean algebra • Duality – a dual of a Boolean expression is derived by replacing • by +, + by •, 0 by 1, and 1 by 0, and leaving variables unchanged – any theorem that can be proven is thus also proven for its dual! – is a “meta-theorem” (a theorem about theorems) • duality: 16. X + Y + ... Û X • Y • ... • generalized duality: 17. f (X1,X2,...,Xn,0,1,+,•) Û f(X1,X2,...,Xn,1,0,•,+) • Differs from deMorgan’s Law – Duality is a statement about theorems – Duality is not a way of manipulating (re-writing) expressions 20T3 COMP3222/9222 L01/S23 Introduction Axioms and theorems of Boolean algebra • Proofs of the axioms and theorems of Boolean algebra can be established in various ways – For example, the absorption theorem (X + X • Y = X) may be proven deductively, exhaustively or using set theory LHS = X + X • Y LHS = X • 1 + X • Y by identity LHS = X • (1 + Y) by distributivity LHS = X • 1 by null LHS = X by identity 20T3 COMP3222/9222 L01/S24 X Y X • Y X + X • Y 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 X Y Using set theory, the surrounding box represents the universe, logical AND is given by the intersection of sets, and logical OR is given by the union of sets Introduction Precedence of operations • In the absence of parentheses, operations in a logic expression must be performed in the order: NOT, AND, and then OR • Thus x1∙x2 + x1∙x2 has the same effect as (x1∙x2) + ((x1)∙(x2)) • Also, to simplify the appearance of logic expressions it is customary to omit the ∙ operator when there is no ambiguity – The preceding expression can therefore be written as x1 x2 + x1 x2 20T3 COMP3222/9222 L01/S25 Introduction f (c) Minimal-cost realization x 2 x 1 f (b) Canonical sum-of-products realization x 1 x 2 (a) Function to be realized Synthesizing digital logic circuits using AND, OR and NOT gates f(x1,x2) = x1x2 + x1x2 + x1x2 f(x1,x2) = x1x2 + x1x2 + x1x2 + x1x2 f(x1,x2) = x1(x2 + x2) + (x1 + x1)x2 f(x1,x2) = x1∙1 + 1∙x2 f(x1,x2) = x1 + x2 20T3 COMP3222/9222 x1 x2 f(x1, x2) 0 0 1 0 1 1 1 0 0 1 1 1 L01/S26 idempotency distributivity complementarity identity Introduction Evaluating circuit cost • The primary contributor to circuit cost is the number of transistors used • #(Transistors used) ≈ circuit (chip) area • Circuits with fewer gates and gates with fewer wires (inputs) require fewer transistors ⇒ less chip area – Important: the lowest level of abstraction we will use to design digital circuits is the GATE LEVEL (we will only look at how gates are implemented using transistors at the end of the course) • Unless stated otherwise, we will use the sum of the number of gates and the total number of gate inputs within a circuit as a measure of circuit cost – With this metric, circuit (b) on the previous slide has a cost of 17, whereas circuit (c) has a cost of 5 20T3 COMP3222/9222 L01/S27 Introduction Synthesis technique for logic circuits 1. Add a product (AND) term for each row in the truth table with function value f = 1 2. Form the sum (OR) of these terms to produce the function f 3. Simplify the expression using Boolean algebraic manipulation 4. Draw the circuit, complementing inputs where necessary, using AND gates for the product terms and ORing these together 20T3 COMP3222/9222 L01/S28 Minterms • For a function of n variables, a product term in which each of the n variables, xi, appears exactly once is called a minterm – The variables may appear in a minterm either in uncomplemented or complemented form – For a given row of the truth table, the minterm is formed by including xi if xi = 1 and by including xi if xi = 0 – Note that mi=1 in row i • Three-variable minterms Introduction20T3 COMP3222/9222 Note that minterms are numbered according to which variables appear in uncomplemented form of the truth table and mi=0 in all other rows L01/S29 The result of ANDing variables together Introduction20T3 COMP3222/9222 Sum-of-Products form • A function f can be represented by an expression that is written as a sum of minterms, where each minterm is ANDed with the value of f for the corresponding valua- tion of input variables • For example, for the function of slide L01/S26, f(x1, x2) = m0∙1 + m1∙1 + m2∙0 + m3∙1 = m0 + m1 + m3 = x1x2 + x1x2 + x1x2 • A logic expression consisting of product (AND) terms that are summed (ORed) is said to be in the sum-of-products (SOP) form. • If each product term is a minterm, then the expression is called a canonical sum-of-products for the function f – Every Boolean fn has just ONE canonical SOP representation = Σ(m0, m1, m3) = Σm(0, 1, 3) x1 x2 f(x1, x2) 0 0 1 0 1 1 1 0 0 1 1 1 L01/S30 Introduction Example 2.3 • Consider the function f(x1, x2, x3) = Σm(2, 3, 4, 6, 7) • The canonical SOP expression is given using minterms f(x1, x2, x3) = m2 + m3 + m4 + m6 + m7 = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 • The expression can be simplified using algebraic manipulation: f = x1x2(x3 + x3) + x1(x2 + x2)x3 + x1x2(x3 + x3) = x1x2 + x1x3 + x1x2 …SOP form = (x1 + x1)x2 + x1x3 …Not in SOP form = x2 + x1x3 …SOP form 20T3 COMP3222/9222 L01/S31 Introduction Maxterms • The principle of duality suggests that if it is possible to synthesize a function f by considering the rows in the truth table for which f = 1, then it should be possible to synthesize f by considering the rows for which f = 0 • This alternative approach uses the complements of minterms, which are called maxterms 20T3 COMP3222/9222 L01/S32 Introduction Three-variable minterms and maxterms 20T3 COMP3222/9222 Observe the value of the example minterm m0 and maxterm M0 for each valuation of the variables x1, x2, and x3 Note that maxterm Mi=0 in row i of the truth table and Mi=1 for all other rows m0 1 0 0 0 0 0 0 0 M0 (m0) 0 1 1 1 1 1 1 1 L01/S33 (derived using DeMorgan) M0 = m0 = x1x2x3 = x1 + x2 + x3 Introduction Product-of-Sums form • If a given function f is specified by a truth table, then its complement f can be represented by a sum of minterms for which f = 1, which are the rows of f where f = 0. • For example, for the L01/S26 function, f(x1,x2) = Σm(0,1,3), f(x1,x2) = m2 = x1x2 • If we complement this expression using DeMorgan’s theorem, the result is f = f = x1x2 = x1 + x2 = M2 • The key point is that f = m2 = M2 • A logic expression consisting of sum (OR) terms that are factors of a logical product (AND) is said to be of the product-of-sums (POS) form • If each sum term is a maxterm, then the expression is called a canonical product-of-sums for the given function = Π(M2) = ΠM(2) 20T3 COMP3222/9222 L01/S34 Introduction Example 2.4 • Consider again the function of Example 2.3. Instead of using the minterms, we can specify this function as a product of maxterms for which f = 0, namely, f(x1, x2, x3) = ΠM(0, 1, 5) • Then the canonical POS expression is given by: f(x1, x2, x3) = M0∙M1∙M5 = (x1 + x2 + x3)(x1 + x2 + x3)(x1 + x2 + x3) • A simplified POS expression can then be derived as: f = ((x1 + x2) + x3)((x1 + x2) + x3)(x1 + (x2 + x3))(x1 + (x2 + x3)) = ((x1 + x2) + x3x3)(x1x1 + (x2 + x3)) = (x1 + x2)(x2 + x3) … by the uniting theorem • And note that use of the distributive property leads to: f = x2 + x1x3 20T3 COMP3222/9222 f(x1, x2, x3) = Σm(2, 3, 4, 6, 7) L01/S35 What’s the cost of this expression? Is this expression in SOP or POS form? What’s its cost? Introduction Exercise for you to do 1. Derive canonical SOP and POS expressions for the three-valued function below. 2. Minimize each expression and sketch the resulting circuits. 3. Compare the costs of all designs Row Number x1 x2 x3 f(x1, x2, x3) 0 0 0 0 0 1 0 0 1 1 2 0 1 0 0 3 0 1 1 0 4 1 0 0 1 5 1 0 1 1 6 1 1 0 1 7 1 1 1 0 L01/S36 Summary so far 1. Logic design is concerned with finding the cheapest implementation of combinational (a.k.a. combinatorial) logic functions – Circuit cost is measured by summing the number of gates and the total number of gate inputs 2. The laws of Boolean algebra can be used to minimize the cost of a combinational logic function – Typically, these are applied one at a time with the objective of eliminating one or more variables from a term or whole terms from the function 3. There are two canonical representations of combinational logic functions: – Canonical sum-of-products represents a function as a sum (OR) of minterms – Canonical product-of-sums represents a function as a product (AND) of maxterms Introduction20T3 COMP3222/9222 L01/S37 A typical CAD flow for logic design • HDL is similar to a computer programming language except that it is used to describe hardware; NOT to be executed on a processor – Similar to a markup language • We focus on one of two IEEE standard languages that are supported by virtually all vendors that provide digital design technology – We study VHDL (Very High Speed Integrated Circuit HDL) – The other is Verilog Introduction Design conception Hardware description languageSchematic capture DESIGN ENTRY Design correct? Functional simulation No Yes No Synthesis Physical design Chip configuration Timing requirements met? Timing simulation 20T3 COMP3222/9222 Computer Aided Design Hardware Description Language L01/S38 VHDL • In comparison to schematic capture, use of a hardware description language, such as VHDL, to capture a design’s intent offers a number of advantages – VHDL source code is plain text, which means it can easily be edited, copied and searched; the designer can also easily include documentation explaining how the design works – Being a standard language, VHDL provides design portability – a design specified in VHDL can be implemented in different types of chips and with CAD tools from different vendors – Portability is useful because digital circuit technology changes rapidly – by using a standard language, the designer can focus on the functionality of the circuit without being overly concerned with the details of the implementation technology – Together with its wide use, these features encourage code sharing and reuse, which aids productivity Introduction20T3 COMP3222/9222 Use of a graphical tool to provide a logic circuit diagram L01/S39 A little VHDL history • Developed in the 1980s, when integrated circuit technology was rapidly advancing, as a standard means of documenting complex digital circuits • Became IEEE standard 1076 in 1987, and was revised in 1993 as IEEE 1164. Updates occurred in 2000 and 2002, as well as most recently, in 2008. • Originally conceived for documenting circuits, and for modelling circuit behaviour, which allowed it to be used as input to programs for simulating circuit operation • More recently, it has become popular to use it as a design entry method for CAD tools that synthesize hardware implementations • VHDL is quite complex; we will restrict ourselves to the study of that subset of the language used for synthesis Introduction20T3 COMP3222/9222 L01/S40 A simple logic fn and its VHDL entity declaration • A VHDL entity declaration expresses what the design unit “looks like” to the outside world, i.e., describes its interface Introduction f x3 x1 x2 ENTITY example1 IS PORT ( x1, x2, x3 : IN BIT ; f : OUT BIT ) ; END example1 ; Signals of type BIT can assume values 0 and 1 The “mode” of a signal indicates its direction Valid identifiers start with a letter, and comprise alpha-numeric and underscore characters 20T3 COMP3222/9222 example1 L01/S41 A simple logic fn and its VHDL architecture • The architecture of a VHDL design unit describes what the design “looks like” on the inside i.e. what its behaviour and/or structure is Introduction f x3 x1 x2 ARCHITECTURE LogicFunc OF example1 IS BEGIN f <= (x1 AND x2) OR (NOT x2 AND x3) ; END LogicFunc ; Here, the functionality of the circuit is expressed using a simple signal assignment statement In VHDL, all statements need to be terminated by a semi-colon (;) Note that in VHDL, the Boolean operators all have the same precedence, hence we must use parentheses to indicate the intended meaning 20T3 COMP3222/9222 example1 L01/S42 Introduction Complete VHDL design entity f x3 x1 x2 In our code we’ll use capital letters to represent KEYWORDS in the code; obviously these can’t be used as identifiers Note that VHDL is not case sensitive 20T3 COMP3222/9222 L01/S43 Introduction Four-input example Note that simple signal assignment statements are examples of concurrent assignment statements – they are all “evaluated” at the same time when a signal on the RHS changes value; therefore the order the statements are listed in does not matter 20T3 COMP3222/9222 L01/S44 Introduction 1 0 1 0 1 0 1 0 x 1 x 2 Time x 3 f Exercise for you to attempt • For the timing diagram depicted below, synthesize the function f(x1, x2, x3) in the simplest SOP form and describe your implementation using VHDL • A good rule of thumb for writing clear VHDL: Can you visualize the circuit that should be synthesized from your VHDL code? 20T3 COMP3222/9222 L01/S45
欢迎咨询51作业君