Class Notes (836,246)
Canada (509,715)
CMPT 150 (6)
Lecture 2

week 2.pdf

10 Pages
Unlock Document

Computing Science
CMPT 150
Anthony Dixon

A.H.Dixon CMPT 150: Week 2 (Sept 11 - 16) 5 2.1 Function Tables A function table (or truth table if the input and output alphabets are binary) is a listing of the output sequence expected for every valid input sequence. There are a ▯nite number of functions (and therefore devices), since there are a ▯nite number of bits in the input and output sequences. For input sequences of length, m, and output sequences of length, n, the number of distinct digital systems having this number of inputs and outputs can be counted: 1. The number of distinct binary sequences of length k is because each of the k positions in the sequence can be assigned one of two values \0" or \1". 2. Each row of a function table describes what the output will be for one possible input m sequence. Therefore, when the input sequences are of length k = m there are 2 rows in the function table. 3. Since there are 2rows and each can be assigned 2 outputs (0 or 1), the number of distinct function tables (and therefore number of distinct digital systems) with m inputs and n outputs is: 2 2 EXAMPLE 1: 1-input, 1-output: four possible functions - m0, m1, m2, m3: x m0 m1 m2 m3 0 0 0 1 1 1 0 1 0 1 NOTE: This table actually represents 4 distinct function (truth) tables: m0, m1, m2, and m3. Since they all have the same set of possible input sequences, these need only be expressed once on the left-hand side with the understanding that this is the left-hand side for each output column. EXAMPLE 2: 2-input, 1-output: sixteen possible functions - p0 through p15: x1 x0 p0 p1 p2 p3 p4 p5 p6 p7 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 x1 x0 p8 p9 p10 p11 p12 p13 p14 p15 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 3 GATES Some entities occur so frequently in applications that, by convention, they are given special graphical symbols that uniquely represent them. Associated with each unique entity is a speci▯c function table. This saves the need to include the function table explicitly with A.H.Dixon CMPT 150: Week 2 (Sept 11 - 16) 6 the symbol whenever the symbol is used in a logic diagram. Figure 1 provides examples of the graphic symbols for the entities representing the \2 input And", \2 input Or", and \Inverter (Not)" functions. Figure 1: The Basic Gate Entities The function tables associated with these entities are given in the tables above, speci▯- cally: ▯ BUFFER : function table is given by m1. ▯ NOT : function table is given by m2. ▯ 2-input AND : function table is given by p1. ▯ 2-input OR : function table is given by p7. ▯ 2-input NAND : function table is given by p14. ▯ 2-input NOR : function table is given by p8. ▯ 2-input XOR: function table is given by p6. 4 STRUCTURAL DESCRIPTIONS A behavioral description formally de▯nes what the digital system is supposed to do, but does not say anything about how the behavior is to be achieved. There are many possible ways to obtain that behavior, and each way is referred to as a \realization" or structural description of the digital system. A structural description identi▯es the components required to implement the digital system and how they are interconnected in order to achieve the desired behavior. One way to provide this description is with a logic diagram or schematic. Therefore, the terms \logic diagram" and "schematic" are often used as synonyms for \structural description." The following is an example of a structural description: A.H.Dixon CMPT 150: Week 2 (Sept 11 - 16) 7 x y f z The purpose of \digital design" is to obtain a structural description from a behavioral one. In contrast, the purpose of \digital analysis" is to obtain a behavioral description from a structural one, and then possibly ▯nd a meaningful interpretation for the behavioral description obtained. Among the important techniques in the design or analysis of gate level circuits are: ▯ Transform a symbolic representation to a function table; ▯ Transform a schematic to its corresponding symbolic representation; ▯ Transform the symbolic representation of a digital system; to a di▯erent but equiva- lent symbolic representation; ▯ Transform a function table to a symbolic representation. 4.1 Function Tables from Schematics One way to determine the behaviour of a digital system (i.e., determine what it does) is to construct its function table by analyzing the schematic (logic diagram). The technique consists of the following steps: 1. Label all components and signal lines in the schematic. Signal lines connected to port symbols are labelled by the port labels. Internal signal lines (those that connect an output port of one component to one of the input ports of another component) are assigned arbitrary labels. For example, the diagram above can be labelled as follows: x a A1 y OR1 f b c A2 z N1 2. Construct a table with columns for the outputs observed at each gate in the schematic. The entries under each column are determined by applying the function table for the given gate to the values observed on the input ports of the gates. These inputs are de▯ned by other columns in the table. 3. The leftmost columns that identify the values on the input ports together with the rightmost column that de▯nes the resulting value(s) on the output port(s) speci▯es A.H.Dixon CMPT 150: Week 2 (Sept 11 - 16) 8 the function table for the schematic. For example, from the schematic above, the following table can be derived: x y z c = z a = x ▯ y b = y ▯ c f = a + b 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 4.2 Symbolic Representation The equations used in the table headings above to represent the functions performed by the gates illustrate that the behavior of a gate can be described by a symbolic expression using a unique symbol to characterize the operation performed by the gate and labels to de▯ne the operands (inputs). By convention the following symbolic expressions de▯ne the basic gates. The behavior of these operations are de▯ned by the corresponding function tables given previously: ▯ NOT = x (or x )0 ▯ AND = x ▯ y (or simply xy) ▯ OR = x + y ▯ NAND = x " y ▯ NOR = x # y ▯ XOR = x ▯ y A.H.Dixon CMPT 150: Week 2 (Sept 11 - 16) 9 4.3 Schematic to Symbolic Representation One of the advantages of representing a behavioral description with a function table is that is easy to identify the equivalence of two systems. Two digital systems are equivalent if and only if they have the same function table. However, function tables are impractical if there are more than a few inputs since the number of rows in the table doubles with each additional input. A symbolic representation provides a more compact way of representing the functional speci▯cation of a digital system but makes it more di▯cult to compare two systems for equivalence. To obtain the symbolic representation of a given logic diagram, proceed as follows: 1. Assign labels to all internal signal lines as was done in constructing the function table. The external signal lines are labelled by the external input labels and output label. 2. Each signal line except the inputs is an output from some gate. Use the symbolic expression for that gate to de▯ne that signal line as a function of the inputs to the corresponding gate. These inputs may be either external inputs, or internal signal lines. In either case, they will have a label. 3. Proceeding left to right determine a symbolic expression for the output of each gate in terms of its inputs using the symbolic expressions for each gate. 4. If the operand of any expression includes the labels of internal signals, then t
More Less

Related notes for CMPT 150

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.