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
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:
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
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▯-
▯ 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
The purpose of \digital design" is to obtain a structural description from a behavioral
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
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:
y OR1 f
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
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
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