Gates

†Gate: A simple electronic circuit (a system) that

realizes a logical operation.
„ The direction of information flow is from the input
terminals to the output terminal.
„ The number of input and output terminals is finite and they
carry binary-valued signals (i.e, 0 and 1).
„ The transformation of input signals to output signals can be
modeled as a logical operation.
†Reading assignment
„ Sections 2.1—2.5 from the text

X
Gate Z = f(X,Y)
Y

Elec 326 8 Gates and Logic Networks

†Truth Tables
„ Since there is a finite number of input signal combinations,
we can represent the behavior of a gate by simply listing all
of it possible input configurations and the corresponding
output signal. Such a list is called a truth table.
„ For example, the following gate could have the behavior
given by the following truth tables.
X Y Z X Y Z X Y Z
X L L L 0 0 0 1 1 1
GATE Z L H H 0 1 1 1 0 0
Y 1 0 1 0 1 0
H L H
H H H 1 1 1 0 0 0

„ The use of the symbols L and H usually correlates with the

high and low voltages.

Elec 326 9 Gates and Logic Networks

1
 †Some standard gates and their symbols and truth
tables: X
Z
X
Z
X Z X Z Y Y
X Y Z X Y Z
X Z X Z 0 0 0 0 0 0
0 0 0 1 0 1 0 0 1 1
1 1 1 0 1 0 0 1 0 1
a. Buffer b. Inverter 1 1 1 1 1 1
c. AND Gate d. OR Gate

X X
Z Z
Y X X
Y Z Z
or or Y Y
X X
Z Z
Y Y
X Y Z X Y Z
X Y Z X Y Z 0 0 1
0 0 0
0 0 1 0 0 1 0 1 1 0 1 0
0 1 1 0 1 0 1 0 1 1 0 0
1 0 1 1 0 0 1 1 0 1 1 1
1 1 0 1 1 0 g. Exclusive OR Gate h. Equivalence Gate
e. NAND Gate f. NOR Gate

Elec 326 3 Gates and Logic Networks

„ Gates with more than 3 inputs:

‹AND gates: The output is 1 if and only if … ?
‹OR gates: The output is 1 if and only if … ?
‹NAND gates: The output is 0 if and only if … ?
‹NOR gates: The output is 0 if and only if … ?
‹EXCLUSIVE OR gates: The output is 1 if and only if … ?
‹EQUIVALENCE gates: The output is 1 if and only if … ?

Elec 326 4 Gates and Logic Networks

2
 †Logical Expressions
„ We can also represent the behavior of gates with a logical
expressions constructed from variables and logical
operations symbols.
„ The following table gives the most common ones.

Connective Example Meaning

NEGATION C = A' C is 1 iff A is 0.
AND C = A•B C is 1 iff A is 1 and B is 1.
OR C = A+B C is 1 iff A is 1 or B is 1.
EXCLUSIVE OR C = A⊕B C is 1 iff A or B is 1, both not both.
NAND C = A↑B C is 1 iff It is not the case that A and B are both 1.
NOR C = A↓B C is 1 iff It is not the case that either A or B is 1.
EQUIVALENCE C = A≡B C is 1 iff Both A and B are 1 or both A and B are 0.

Elec 326 5 Gates and Logic Networks

„ Comments on the logical symbols

‹ The NAND and NOR symbols are not very useful.
‹ There are several different symbols that have been used for the logical
connectives.
AND : •, &, ∧
OR : +, |, ∨
NOT : ', , ~, ¬
† Exercise:
Determine how many different two-input gates there can be?
How many three-input gates?
n
N 22

2 16
3 256
4 65,536
5 4, 294,967,396
6 1.84 x 1019

Elec 326 6 Gates and Logic Networks

3
Gate Networks
†A gate network is a finite collection of interconnected
gates, network input terminals, and network output
terminals with the following restrictions:
„ No gate output terminal or network input terminal is
connected to another gate output terminal or network input
terminal.
„ Every network output terminal or gate input terminal is
wired (via one or more wires) to a constant value, a
network input terminal, or a gate output terminal.
†Example
A
X
Network B Network
Input Output
Terminals Terminals
Y
C

Elec 326 7 Gates and Logic Networks

† Types of networks
„ A combinational gate network is one in which the values of the signals
present on its input terminals uniquely determine the signal values at its
output terminals.
„ A gate network that is not combinational is called a sequential gate
network.
„ A loop in a gate network is a path that starts at a gate terminal, passes
along wires and through gates, does not pass any wire or gate more
than once, and terminates back at the starting gate terminal.

Loop

‹ Networks without loops are combinational.

z We call a gate network without loops a logic network, since we can describe
its behavior with a logical expression.
‹ Sequential networks have loops.
‹ Combinational networks may have loops.

Elec 326 8 Gates and Logic Networks

4
 †Exercise:
Which of the following networks are combinational and
which are sequential?

Net 1 Net 2

Net 3 Net 4

Elec 326 9 Gates and Logic Networks

Analysis & Synthesis of Logic Networks

†Overview
Synthesis Logic Analysis
Network
7 1 2 6

4
Truth 3 Logical
Table Expression
5

1. For a given logic network, find a truth table that describes its behavior.
2. For a given logic network, find a set of logical expressions that describes its behavior.
3. Transform a logical expression into the equivalent truth table representation.
4. Transform a truth table into an equivalent logical expression representation.
5. Transform a logical expression into an equivalent (and possibly simpler) logical
expression.
6. Design a logic network to have the behavior specified by a given set of logical
expressions.
7. Design a logic network to have the behavior specified by a given truth table.

Elec 326 10 Gates and Logic Networks

5
 †Analysis of Logic Networks
„ Logic Network
A Z1
1 Z4
4 6 X

B Z2
2

Z3 5 Y
3
C

„ Truth Table Behavioral Description

ABC Z1 Z2 Z3 Z4 X Y
0 0 0 1 0 0 1 0 0
0 0 1 1 0 0 1 0 0
0 1 0 1 1 0 1 0 0
0 1 1 1 1 0 1 0 0
1 0 0 1 1 0 1 0 0
1 0 1 1 1 1 1 0 1
1 1 0 0 0 0 0 1 0
1 1 1 0 0 1 0 1 0
Elec 326 11 Gates and Logic Networks

„ Logical Expression Behavioral Description

A Z1
1 Z4
4 6 X

B Z2
2

Z3 5 Y
3
C

X = Z4'
X = (Z1+Z2)'
X = ((A•B)'+(A⊕B))'

Y = Z2•Z3•Z4
Y = (A ⊕B)•(A•C)•(Z1+Z2)
Y = (A ⊕B)•(A•C)•((A•B)'+(A ⊕B))

Elec 326 12 Gates and Logic Networks

6
 „ Example

ABC X Y
0 0 0 0 0
A 0 0 1 0 0
X 0 1 0 0 0
B
0 1 1 0 0
1 0 0 0 0
Y 1 0 1 0 1
C
1 1 0 1 0
1 1 1 1 0
X = A•B
Y = A•B'•C

„ The networks in these two examples (slides 2.19 and 2.20) are equivalent
because they have the same truth table. The logical expressions for X and Y are
also equivalent, but very different structurally.
„ Graph levelization for analysis

Elec 326 13 Gates and Logic Networks

„ Notation: We can represent a truth table by simply listing

the indices of the rows that have value 1 or listing those
that have value 0.
‹Example ABC X Y
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
We will revisit the Σ and Π notations 0 1 1 0 0
when we look at sum-of-product and 1 0 0 0 0
product-of-sum representations 1 0 1 0 1
1 1 0 1 0
1 1 1 1 0

z List of 1’s:
X = Σ A,B,C (6, 7) Y = Σ A,B,C (5)
z List of 0’s:
X = ΠA, B, C (0, 1, 2, 3, 4, 5) Y = Π A,B,C (0, 1, 2, 3, 4, 6, 7)

‹The value of this notation is that it is a more compact way of

specifying a logical function than writing the truth table. It is useful
for specifying a function to be designed (e.g., in homework
problems).

Elec 326 14 Gates and Logic Networks

7
† Synthesis of Logic Networks
„ Example
A
Z = (A ⊕ B) + ((C + D)•B') B A⊕B
Z
B
C (C+D)•B'
A D
B
C (A⊕B) + ((C+D)•B') Z A
D B
C Z
D C+D
+ B B'

⊕ • A
A B + ' B
C Z
C D B D
B

Elec 326 15 Gates and Logic Networks

„ Example
X = ((Α ⊕ B) + C)'
Y = (B•C + D)'•E
Z = (A + D) + (B•C)

A
B X
C

D Y
E

Original Network
A A
B X B X
C C

Y Y
D D
E E
Z Z

First Simplification Second Simplification

Elec 326 16 Gates and Logic Networks

8
 „ Two level gate networks and logical expressions
‹Sum-of-Products (SOP) logical expressions
A•B + A•C’ + B•C’•A + C

‹Two level AND-OR Networks

A
B
C
Y

‹Product-of-Sums (POS) logical expressions

(A+B’)•(B+C’)•A

‹Two level OR-AND Networks

A
B
C Y

Elec 326 17 Gates and Logic Networks

NAND/NOR Networks
†This topic deals with designing combinational logic
networks using only NAND or NOR gates.
„ Approach: First design the network with AND, OR and
NOT gates. Then Transform it to an equivalent network of
NAND or NOR gates.
‹The following alternative NAND and NOR symbols are useful for
this.
A A
(A•B)' A' + B'
B B
A A
(A + B)' A' • B'
B B

Elec 326 18 Gates and Logic Networks

9
 „ One approach is to replace AND and OR gates by the
following equivalent NAND or NOR circuits:
A A
A•B A+B
B B

A A
NAND: B A•B
B
A+B

A A
NOR: A•B A+B
B B

„ NAND Network Example:

A' 4
A'
4 C'
C' 2
2 1
B 5 Z
5 1 Z B
D
A D
3 3
D A
AND-OR Network D
NAND Network

Elec 326 19 Gates and Logic Networks

„ NOR Network Example

A
B Z
C
D
E'
AND-OR Network

A
B Z

C
D
E'

NOR Network

Elec 326 20 Gates and Logic Networks

10
 † Example of Transformation to a NAND and a NOR Network:

B
Z
C

D
Original Network N1

B
Z
C

D
NAND Network N2

B
Z
C

D
NOR Network N2

Elec 326 21 Gates and Logic Networks

†Exercise:
„ Derive logical expressions, using only the logical
operations • , + and ', for the following two networks.

A B C D E

Net 1

A B C D E

Net 2

Elec 326 22 Gates and Logic Networks

11
An Introduction to Verilog
†Verilog is a programming language that was
developed for describing the behavior and structure
of digital systems. Languages such as this are called
Hardware Description Languages or HDL’s.
„ Verilog is an IEEE standard and widely used today.
„ Verilog is probably most useful for describing systems at a
high-level of abstraction, before the implementation details
of the systems are developed.
‹While HDL’s have been around for 30 years, it has only been with
the advent of large integrated circuits that they have become
popular with digital designers.
z Why?

Elec 326 23 Gates and Logic Networks

†Verilog Uses
„ Verilog can be viewed as a simulation modeling language
‹Enables digital designers to simulate and verify the behavior of
their systems before they design a detailed implementation.
z Verification of functional behavior
z Timing analysis
‹Verilog can also be used to specify test patterns for testing Verilog
simulation models. Verilog programs used for generating test
patterns are called test benches or test fixtures.
„ Verilog is also used to specify the input to synthesis tools
that produce implementations automatically.
‹When this is possible, the designer need not use the classical design
techniques.

Elec 326 24 Gates and Logic Networks

12
 †Verilog Modules
„ An elementary Verilog program is called a module.
‹A module corresponds to a digital circuit.
‹Modules have input and output ports that correspond to the input
and output terminals of a digital circuit.
‹The ports and variables used to represent internal signals are
declared at the beginning of the program.
‹Modules have other statements used to define how it transforms the
input signals to output signals.
„ Verilog modules can be used to specify the structure or the
behavior of a digital circuit.
‹Structural modules consist of a list of component modules (defined
elsewhere) and a list of wires used to interconnect the modules.
‹Behavior modules specify the output signals as functions of the
input signals. They need not give any indication of the structure of
the circuit.

Elec 326 25 Gates and Logic Networks

†Example of a behavioral Verilog module

„ Circuit:
E D C B A

„ Verilog module:
module circuit1b (A, B, C, D, E, X, Y, Z);
input A, B, C, D, E;
output X, Y, Z;
assign X = ~((A ^ B) | C);
assign Y = ~((B & C) | D) & E;
assign Z = A | D | (B & C);
endmodule

Elec 326 26 Gates and Logic Networks

13
 „ Comments on the module
‹Case matters in Verilog statements.
z The symbol string “Out”, “out”, and “OUT” represent three different
variables.
‹Individual signals (e.g., A, B, … in the previous example) can take
any of the following four values:
z 0 = logic value 0
z 1 = logic value 1
z z = tri-state (high impedance)
z x = unknown value
‹The unknown value is used by simulators to indicate that they do
not know how to determine a signals value (e.g., the user has not
specified a value for an input signal). The tri-state value means that
no signal is assigned to the variable.
‹The unknown value x can also be used to specify a don’t care
condition to the synthesis tools.
‹Note that ports must be listed in the module statement (first line)
and their direction (input or output) declared in the following
statements.

Elec 326 27 Gates and Logic Networks

‹The three assign statements are independent and can execute in any
order or concurrently.
z The right side of an assign statement is evaluated and its resulting value
assigned to the signal on the left side whenever one of the signals used in the
right side changes value.
 This type of assignment is also called a continuous assignment.
z This method of interpreting the execution of assign statements is quite different
from that use in conventional programming languages in the following ways:
 Two or more assignments can execute simultaneously. This is necessary to represent
the timing characteristics of hardware systems.
 An assignment executes whenever it is ready (i.e., has new data for the variables on
its right side)
 There is no concept of "locus of control" or “program counter” that determines the
next instruction to execute. Therefore, the order the assignments are written does not
matter
z This method of assignment statement execution is sometimes called
non-procedural or data-driven execution, where conventional
programming languages are said to be procedural.

Elec 326 28 Gates and Logic Networks

14
 †Behavioral vs. Structural Verilog Descriptions
„ The previous example is a behavioral descriptions because
it specifies the logical values of the circuit's outputs as
logical equations with no reference to how the gates in a
possible implementation might be interconnected.
„ It is also possible to specify a structural description in
Verilog that specifies explicitly how a set of smaller
components (e.g., gates) are interconnected to form a larger
system as shown on the following slide.
‹Note that the internal connections from gate outputs to gate inputs
are declared to be of type wire.
z These wire declarations could be omitted as long as the component modules
are simple gates. Verilog will assume that any gate output signal that is not
declared is of type wire.
‹Each gate is specified by its name (e.g., and, or, …) and a list of
ports or wires connected to its terminals. All gates have a single
output and it is always listed first in this list.

Elec 326 29 Gates and Logic Networks

module circuit1s (A, B, C, D, E, X, Y, Z);

input A, B, C, D, E;
output X, Y, Z;
wire T1, T2, T3, T4, T5, T6, T7;

xor(T1, A, B);
E D C B A
or(T2, T1, C);
T1 T2
not(X, T2); X
and(T3, B, C); T3 T4 T5
or(T4, T3, D); Y
not(T5, T4);
and(Y, T5, E); T6
Z
or(T6, A, D); T7
and(T7, B, C);
or(Z, T6, T7);

endmodule

Elec 326 30 Gates and Logic Networks

15
 †Always Blocks
„ A procedural block is a construct that contains statements
that are executed procedurally (i.e., in the order they are
written).
always @(sensitivity_list)
begin
procedural statements
end
„ The sensitivity list is a list of signals separated by or.
‹When any one of the signals in the sensitivity list changes value,
the always block wakes up, executes its procedural statements, and
then goes back to sleep.
„ The always block acts like a generalized assign statement
where the action that takes place can be specified by
sequential code.

Elec 326 31 Gates and Logic Networks

„ Example
module always_example(x, y, z);
input x, y;
output z;
reg z, s;

always @(x or y)
begin
s = x ^ y;
z = x & s;
end
endmodule

Elec 326 32 Gates and Logic Networks

16
 „ Variables declared as type reg hold their value until they
are assigned a new value. It is said that the assigned value
is registered in the variable
„ Whenever x or y changes value, the always block is
executed as follows:
‹First, the statement s = x^y executes and registers a new value in s
‹Next, the statement z = x & s executes using the new value of s that
it received when the first statement was executed.
‹Then the block stops executing and waits for either x or y to change
again.
„ Variables on the left side of a procedural statement must be
declared as type reg.
„ The main advantage of using always blocks to represent
combinational circuits is that you can use control
statements such as “if then else” as illustrated by the
following example

Elec 326 33 Gates and Logic Networks

module mux1 (x1, x2, s, y); module mux2 (x1, x2, s, y);
input x1, x2, s; input x1, x2, s;
output y; output y;
reg y;
assign y = (s & x1) | (~s & x2);
always @(x1 or x2 or s)
endmodule
if (s == 1)
y = x1;
else
y = x2;
endmodule

‹Modules mux1 and mux2 do exactly the same thing.

‹The control statements used in always blocks will be covered in
more detail in later chapters.

Elec 326 34 Gates and Logic Networks

17
 „ Exercise: Explain how the behaviors of the following two
modules differ.

module always_example(x, y, z, f); module assign_example (x, y, z, f);

input x, y, z; input x, y, z;
output f; output f;
reg f, s; wire s;

always @(x or y or z) assign s = x ^ y;

begin assign f = z & s;
s = x ^ y;
f = z & s; endmodule
end

endmodule

„ How would the behavior of each of these modules change if

the order of the two assignment statements is reversed?

Elec 326 35 Gates and Logic Networks

„ Conditions for combinational behavior of always blocks

‹The following conditions are necessary for an always block to
represent combinational logic (as opposed to sequential logic)
z All reg, wire and input signals that appear on the right side of an assignment
statement within the always block must appear in the sensitivity list
 We call a sensitivity list that satisfies this condition a complete sensitivity list.
z All signals in the sensitivity list must appear without edge specifiers
 Edge specifiers indicate that a signal is asserted by a change in value as opposed to its level (e.g.,
a rising edge or falling edge). They are introduced and utilized in later chapters on sequential
circuits.
z All output signals must be assigned a value every time the always block
executes
‹These conditions guarantee that the input signals uniquely
determine the output signals, which is the very definition of a
combinational circuit.
‹Some Verilog synthesizers (Including the one in the Xilinx ISE)
assume that if you omit one or more of the signals in the sensitivity
list, that you really meant to put them in, so it does it for you.
However, it will issue a warning message in this case.
‹A sensitivity list of the form @(*) is shorthand for a complete list.
z It is recommended that you use this notation for combinational always blocks.

Elec 326 36 Gates and Logic Networks

18
 „ Example (Incomplete sensitivity list)
module example1(a, b, c, f);
input a, b, c;
output f;
reg f;

always @(a, b)
if (a==1)
f = b;
else
f = c;
endmodule

‹The input c is missing from the sensitivity list

z According to the semantics of Verilog, this represents a sequential circuit.
Why?
z Xilinx ISE will assume you meant to put c in the sensitivity list and add it for
you, so a circuit it synthesizes from this module will be combinational.
z It is better to always use complete sensitivity lists. The easiest way to do this is
to replace @(a,b) by @(*).

Elec 326 37 Gates and Logic Networks

„ Example (Missing output signal in a control path)

‹A control path is a sequence of operations (possibly null) that can
be performed by an always block. It corresponds to a path from the
input node to the output node of a flow chart of the block.

module example2(a, b, c, f);

input a, b, c;
output f;
reg f;

always @(*)
if (a==1)
f = b&c;
endmodule
‹If a is 0 and b or c changes value, the always block executes but
does not execute an assignment to f, so f is not uniquely determined
by the static values of a, b, and c.
‹Xilinx ISE will synthesize this module as a sequential circuit.

Elec 326 38 Gates and Logic Networks

19