Section 3.8  Exclusive-OR Function    103
3.8    EXCLUSIVE-OR FUNCTION 
The exclusive-OR (XOR), denoted by the symbol    {,    is a logical operation that performs 
the following Boolean operation: 
x{xy′+ xy   
The exclusive-OR is equal to 1 if only  x  is equal to 1 or if only  y  is equal to 1 (i.e.,  x  and  y  
differ in value), but not when both are equal to 1 or when both are equal to 0. The exclusive-
NOR, also known as equivalence, performs the following Boolean operation: 
(x{y)′ =xy xy   
The exclusive-NOR is equal to 1 if both  x  and  y  are equal to 1 or if both are equal to 0. 
The exclusive-NOR can be shown to be the complement of the exclusive-OR by means 
of a truth table or by algebraic manipulation: 
(x{y)′= (xy′ +xy)′= (x′ + y)(xy′) = xyxy   
The following identities apply to the exclusive-OR operation: 
x{0 = x   
x{1= x   
x{= 0   
x{x′= 1   
x{y′= x′{y= (x{y)′ ′    
Any of these identities can be proven with a truth table or by replacing the    {    operation 
by its equivalent Boolean expression. Also, it can be shown that the exclusive-OR oper-
ation is both commutative and associative; that is, 
A{B{   
and 
(A{B){CA{(B{C) = A{B{C
This means that the two inputs to an exclusive-OR gate can be interchanged without 
affecting the operation. It also means that we can evaluate a three-variable exclusive-OR 
operation in any order, and for this reason, three or more variables can be expressed 
without parentheses. This would imply the possibility of using exclusive-OR gates with 
three or more inputs. However, multiple-input exclusive-OR gates are difficult to fabri-
cate with hardware. In fact, even a two-input function is usually constructed with other 
types of gates. A two-input exclusive-OR function is constructed with conventional gates 
using two inverters, two AND gates, and an OR gate, as shown in  Fig.   3.30   (a).   Figure  3.30   (b) 
shows the implementation of the exclusive-OR with four NAND gates. The first NAND 
gate performs the operation    (xy)′= = (x′ + y′).    The other two-level NAND circuit 
produces the sum of products of its inputs: 
(x′ + y′)x+ (x′+ y′)=xy′ + xx{y    
Convert pdf to powerpoint online - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf to powerpoint online no email; create powerpoint from pdf
Convert pdf to powerpoint online - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
pdf to ppt converter; convert pdf file to ppt online
104    Chapter 3  Gate-Level Minimization
Only a limited number of Boolean functions can be expressed in terms of exclusive-OR 
operations. Nevertheless, this function emerges quite often during the design of digital 
systems. It is particularly useful in arithmetic operations and error detection and correc-
tion circuits. 
Odd Function 
The exclusive-OR operation with three or more variables can be converted into an 
ordinary Boolean function by replacing the   {    symbol with its equivalent Boolean 
expression. In particular, the three-variable case can be converted to a Boolean expres-
sion as follows: 
A{B{= (AB′+ AB)C′ + (AB AB′)C
ABC′+ ABC′+ ABC +ABC
= ∑(1, 2, 4, 7)   
The Boolean expression clearly indicates that the three-variable exclusive-OR function is 
equal to 1 if only one variable is equal to 1 or if all three variables are equal to 1. Contrary 
to the two-variable case, in which only one variable must be equal to 1, in the case of three 
or more variables the requirement is that an odd number of variables be equal to 1. As a 
consequence, the multiple-variable exclusive-OR operation is defined as an  odd function.  
(a) Exclusive-OR with AND–OR–NOT gates
x
y
x⊕ y
(b) Exclusive-OR with NAND gates
x⊕ y
x
y
FIGURE 3.30 
Exclusive-OR implementations     
Online Convert PowerPoint to PDF file. Best free online export
Online Powerpoint to PDF Converter. Download Free Trial. Convert a PPTX/PPT File to PDF. Just upload your file by clicking on the blue
convert pdf file to powerpoint presentation; convert pdf to ppt
VB.NET PDF - Convert PDF Online with VB.NET HTML5 PDF Viewer
RasterEdge. PRODUCTS: ONLINE DEMOS: Online HTML5 Document Viewer; Online XDoc.PDF Word to PDF; Convert Excel to PDF; Convert PowerPoint to PDF; Convert Image
change pdf to powerpoint online; change pdf to ppt
Section 3.8  Exclusive-OR Function    105
The Boolean function derived from the three-variable exclusive-OR operation is 
expressed as the logical sum of four minterms whose binary numerical values are 001, 010, 
100, and 111. Each of these binary numbers has an odd number of 1’s. The remaining four 
minterms not included in the function are 000, 011, 101, and 110, and they have an even 
number of 1’s in their binary numerical values. In general, an  n -variable exclusive-OR 
function is an odd function defined as the logical sum of the    2
n
>2    minterms whose binary 
numerical values have an odd number of 1’s. 
The definition of an odd function can be clarified by plotting it in a map.  Figure   3.31   (a) 
shows the map for the three-variable exclusive-OR function. The four minterms of the 
function are a unit distance apart from each other. The odd function is identified from 
the four minterms whose binary values have an odd number of 1’s. The complement of 
an odd function is an even function. As shown in  Fig.   3.31   (b), the three-variable even 
function is equal to 1 when an even number of its variables is equal to 1 (including the 
condition that none of the variables is equal to 1). 
The three-input odd function is implemented by means of two-input exclusive-OR 
gates, as shown in  Fig.   3.32   (a). The complement of an odd function is obtained by replac-
ing the output gate with an exclusive-NOR gate, as shown in  Fig.   3.32   (b). 
Consider now the four-variable exclusive-OR operation. By algebraic manipulation, 
we can obtain the sum of minterms for this function: 
A{B{C{=(AB′ +AB){(CD′ + CD)
= (AB′+ AB)(CD CD′) + (ABAB′)(CD′ +CD)
= ∑(1, 2, 4, 7, 8, 11, 13, 14)   
0
1
00
01
11
10
C
(a) Odd function F= A ⊕ B C
(b) Even function F= (ABC)′
A
BC
A
m
0
m
4
m
5
m
7
m
6
m
1
m
3
m
2
m
0
m
4
m
5
m
7
m
6
m
1
m
3
m
2
1
1
1
1
0
1
00
01
11
10
B
A
BC
1
1
1
1
B
A
C
FIGURE 3.31 
Map for a three-variable exclusive-OR function       
(
a
)
3
-
i
n
p
u
t
o
d
d
f
u
n
c
t
i
o
n
(
b
)
3
-
i
n
p
u
t
e
v
e
n
f
u
n
c
t
i
o
n
A
C
B
A
C
B
FIGURE 3.32 
Logic diagram of odd and even functions       
C# HTML5 PDF Viewer SDK to convert and export PDF document to
RasterEdge. PRODUCTS: ONLINE DEMOS: Online HTML5 Document Viewer; Online XDoc.PDF Word to PDF; Convert Excel to PDF; Convert PowerPoint to PDF; Convert Image
how to convert pdf into powerpoint slides; pdf to powerpoint
XDoc.HTML5 Viewer for .NET, Zero Footprint AJAX Document Image
View, Convert, Edit, Sign Documents and Images. Online Demo See the HTML5 Viewer SDK for .NET in powerful & profession imaging controls, PDF document, image to
convert pdf back to powerpoint; chart from pdf to powerpoint
106    Chapter 3  Gate-Level Minimization
There are 16 minterms for a four-variable Boolean function. Half of the minterms 
have binary numerical values with an odd number of 1’s; the other half of the minterms 
have binary numerical values with an even number of 1’s. In plotting the function in the 
map, the binary numerical value for a minterm is determined from the row and column 
numbers of the square that represents the minterm. The map of  Fig.   3.33   (a) is a plot of 
the four-variable exclusive-OR function. This is an odd function because the binary 
values of all the minterms have an odd number of 1’s. The complement of an odd func-
tion is an even function. As shown in  Fig.   3.33   (b), the four-variable even function is equal 
to 1 when an even number of its variables is equal to 1. 
Parity Generation and Checking 
Exclusive-OR functions are very useful in systems requiring error detection and cor-
rection codes. As discussed in Section 1.6, a parity bit is used for the purpose of 
detecting errors during the transmission of binary information. A parity bit is an extra 
bit included with a binary message to make the number of 1’s either odd or even. The 
message, including the parity bit, is transmitted and then checked at the receiving end 
for errors. An error is detected if the checked parity does not correspond with the 
one transmitted. The circuit that generates the parity bit in the transmitter is called 
 parity generator.  The circuit that checks the parity in the receiver is called a  parity 
checker.  
As an example, consider a three-bit message to be transmitted together with an 
even-parity bit.  Table   3.3    shows the truth table for the parity generator. The three 
bits— x, y and  z —constitute the message and are the inputs to the circuit. The parity 
bit  P  is the output. For even parity, the bit  P  must be generated to make the total 
number of 1’s (including  P ) even. From the truth table, we see that  P  constitutes an 
00
01
11
10
00
01
11
10
C
AB
CD
(a) Odd function F= A  B C  D
(b) Even function F= (A  B C  D)
1
1
1
1
1
1
1
1
m
0
m
4
m
12
m
8
m
9
m
11
m
10
m
13
m
15
m
14
m
5
m
7
m
6
m
1
m
3
m
2
m
0
m
4
m
12
m
8
m
9
m
11
m
10
m
13
m
15
m
14
m
5
m
7
m
6
m
1
m
3
m
2
00
01
11
10
00
01
11
10
B
AB
CD
A
D
1
1
1
1
1
1
1
1
C
D
A
B
FIGURE 3.33 
Map for a four-variable exclusive-OR function       
C# PDF Convert to Jpeg SDK: Convert PDF to JPEG images in C#.net
NET library to batch convert PDF files to jpg image files. Turn multiple pages PDF into single jpg files respectively online.
change pdf to powerpoint; converter pdf to powerpoint
VB.NET PDF Convert to Jpeg SDK: Convert PDF to JPEG images in vb.
RasterEdge. PRODUCTS: ONLINE DEMOS: Online HTML5 Document Viewer; Online XDoc.PDF Word to PDF; Convert Excel to PDF; Convert PowerPoint to PDF; Convert Image
how to convert pdf to ppt; adding pdf to powerpoint slide
Section 3.8  Exclusive-OR Function    107
odd function because it is equal to 1 for those minterms whose numerical values have 
an odd number of 1’s. Therefore,  P  can be expressed as a three-variable exclusive-OR 
function: 
x{y{   
The logic diagram for the parity generator is shown in  Fig.   3.34   (a).  
The three bits in the message, together with the parity bit, are transmitted to their 
destination, where they are applied to a parity-checker circuit to check for possible 
errors in the transmission. Since the information was transmitted with even parity, the 
four bits received must have an even number of 1’s. An error occurs during the trans-
mission if the four bits received have an odd number of 1’s, indicating that one bit has 
changed in value during transmission. The output of the parity checker, denoted by 
C , will be equal to 1 if an error occurs—that is, if the four bits received have an odd 
number of 1’s.  Table   3.4    is the truth table for the even-parity checker. From it, we see 
that the function  C  consists of the eight minterms with binary numerical values hav-
ing an odd number of 1’s. The table corresponds to the map of  Fig.   3.33   (a), which 
(
a
)
3
-
b
i
t
e
v
e
n
p
a
r
i
t
y
g
e
n
e
r
a
t
o
r
(
b
)
4
-
b
i
t
e
v
e
n
p
a
r
i
t
y
c
h
e
c
k
e
r
x
y
x
y
z
z
P
P
C
FIGURE 3.34 
Logic diagram of a parity generator and checker       
Table 3.3 
Even-Parity-Generator Truth Table 
Three-Bit Message 
Parity Bit 
 
 
 
 
C# HTML5 PDF Viewer SDK to view PDF document online in C#.NET
RasterEdge. PRODUCTS: ONLINE DEMOS: Online HTML5 Document Viewer; Online XDoc.PDF Word to PDF; Convert Excel to PDF; Convert PowerPoint to PDF; Convert Image
convert pdf to editable ppt online; how to convert pdf to ppt using
VB.NET PDF Convert to HTML SDK: Convert PDF to html files in vb.
Convert PDF to HTML. |. Home ›› XDoc.PDF ›› VB.NET PDF: PDF to HTML. Convert PDF to HTML in VB.NET Demo Code. Add necessary references:
changing pdf to powerpoint file; add pdf to powerpoint
108    Chapter 3  Gate-Level Minimization
represents an odd function. The parity checker can be implemented with exclusive-
OR gates: 
x{y{z{   
The logic diagram of the parity checker is shown in  Fig.   3.34   (b). 
It is worth noting that the parity generator can be implemented with the circuit of  
Fig.   3.34   (b) if the input  P  is connected to logic 0 and the output is marked with  P . Thisis 
because    z{0 0 =z,    causing the value of  z  to pass through the gate unchanged. Theadvan-
tage of this strategy is that the same circuit can be used for both parity generation and 
checking. 
It is obvious from the foregoing example that parity generation and checking circuits 
always have an output function that includes half of the minterms whose numerical  values 
have either an odd or even number of 1’s. As a consequence, they can be  implemented 
with exclusive-OR gates. A function with an even number of 1’s is the complement of an 
odd function. It is implemented with exclusive-OR gates, except that the gate associated 
with the output must be an exclusive-NOR to provide the required complementation.   
3.9    HARDWARE DESCRIPTION LANGUAGE 
Manual methods for designing logic circuits are feasible only when the circuit is small. 
For anything else (i.e., a practical circuit), designers use computer-based design tools. 
Coupled with the correct-by-construction methodology, computer-based design tools 
Table 3.4 
Even-Parity-Checker Truth Table 
Four Bits 
Received 
Parity Error 
Check 
 
 
 
 
 
Section 3.9  Hardware Description Language    109
leverage the creativity and the effort of a designer and reduce the risk of producing a 
flawed design. Prototype integrated circuits are too expensive and time consuming to 
build, soall modern design tools rely on a hardware description language to describe, 
design, and test a circuit in software before it is ever manufactured. 
 hardware description language  (HDL) is a computer-based language that describes 
the hardware of digital systems in a textual form. It resembles an ordinary computer 
programming language, such as C, but is specifically oriented to describing hardware 
structures and the behavior of logic circuits. It can be used to represent logic diagrams, 
truth tables, Boolean expressions, and complex abstractions of the behavior of a digital 
system. One way to view an HDL is to observe that it describes a relationship between 
signals that are the inputs to a circuit and the signals that are the outputs of the circuit. 
For example, an HDL description of an AND gate describes how the logic value of the 
gate’s output is determined by the logic values of its inputs. 
As a  documentation  language, an HDL is used to represent and document digital 
systems in a form that can be read by both humans and computers and is suitable as 
an exchange language between designers. The language content can be stored, 
retrieved, edited, and transmitted easily and processed by computer software in 
an efficient manner. 
HDLs are used in several major steps in the design flow of an integrated circuit: 
design entry, functional simulation or verification, logic synthesis, timing verification, 
and fault simulation. 
Design entry  creates an HDL-based description of the functionality that is to be 
implemented in hardware. Depending on the HDL, the description can be in a variety 
of forms: Boolean logic equations, truth tables, a netlist of interconnected gates, or an 
abstract behavioral model. The HDL model may also represent a partition of a larger 
circuit into smaller interconnected and interacting functional units. 
Logic simulation  displays the behavior of a digital system through the use of a com-
puter. A simulator interprets the HDL description and either produces readable output, 
such as a time-ordered sequence of input and output signal values, or displays wave-
forms of the signals. The simulation of a circuit predicts how the hardware will behave 
before it is actually fabricated. Simulation detects functional errors in a design without 
having to physically create and operate the circuit. Errors that are detected during a 
simulation can be corrected by modifying the appropriate HDL statements. The stimu-
lus (i.e., the logic values of the inputs to a circuit) that tests the functionality of the design 
is called a  test bench.  Thus, to simulate a digital system, the design is first described in 
an HDL and then verified by simulating the design and checking it with a test bench, 
which is also written in the HDL. An alternative and more complex approach relies on 
formal mathematical methods to prove that a circuit is functionally correct. We will focus 
exclusively on simulation. 
Logic synthesis  is the process of deriving a list of physical components and their 
interconnections (called a  netlist ) from the model of a digital system described in an 
HDL. The netlist can be used to fabricate an integrated circuit or to lay out a printed 
circuit board with the hardware counterparts of the gates in the list. Logic synthesis is 
similar to compiling a program in a conventional high-level language. The difference is 
110    Chapter 3  Gate-Level Minimization
that, instead of producing an object code, logic synthesis produces a database describing 
the elements and structure of a circuit. The database specifies how to fabricate a physi-
cal integrated circuit that implements in silicon the functionality described by statements 
made in an HDL. Logic synthesis is based on formal exact procedures that implement 
digital circuits and addresses that part of a digital design which can be automated with 
computer software. The design of today’s large, complex circuits is made possible by 
logic synthesis software. 
Timing verification  confirms that the fabricated, integrated circuit will operate at a 
specified speed. Because each logic gate in a circuit has a propagation delay, a signal 
transition at the input of a circuit cannot immediately cause a change in the logic value 
of the output of a circuit. Propagation delays ultimately limit the speed at which 
a circuit can operate. Timing verification checks each signal path to verify that it is 
not compromised by propagation delay. This step is done after logic synthesis specifies 
the actual devices that will compose a circuit and before the circuit is released for 
production. 
In VLSI circuit design,  fault simulation  compares the behavior of an ideal circuit with 
the behavior of a circuit that contains a process-induced flaw. Dust and other particu-
lates in the atmosphere of the clean room can cause a circuit to be fabricated with a 
fault. A circuit with a fault will not exhibit the same functionality as a fault-free circuit. 
Fault simulation is used to identify input stimuli that can be used to reveal the difference 
between the faulty circuit and the fault-free circuit. These test patterns will be used to 
test fabricated devices to ensure that only good devices are shipped to the customer. 
Test generation and fault simulation may occur at different steps in the design process, 
but they are always done before production in order to avoid the disaster of producing 
a circuit whose internal logic cannot be tested. 
Companies that design integrated circuits use proprietary and public HDLs. In the 
public domain, there are two standard HDLs that are supported by the IEEE: VHDL 
and Verilog. VHDL is a Department of Defense–mandated language. (The  V  in VHDL 
stands for the first letter in VHSIC, an acronym for very high-speed integrated circuit.) 
Verilog began as a proprietary HDL of Cadence Design Systems, but Cadence trans-
ferred control of Verilog to a consortium of companies and universities known as Open 
Verilog International (OVI) as a step leading to its adoption as an IEEE standard. 
VHDL is more difficult to learn than Verilog. Because Verilog is an easier language than 
VHDL to describe, learn, and use, we have chosen it for this book. However, the Verilog 
HDL descriptions listed throughout the book are not just about Verilog, but also serve 
to introduce a design methodology based on the concept of computer-aided modeling 
of digital systems by means of a typical hardware description language. Our emphasis 
will be on the modeling, verification, and synthesis (both manual and automated) of 
Verilog models of circuits having specified behavior. The Verilog HDL was initially 
approved as a standard HDL in 1995; revised and enhanced versions of the language 
were approved in 2001 and 2005. We will address only those features of Verilog, includ-
ing the latest standard, that support our discussion of HDL-based design methodology 
for integrated circuits. 
Section 3.9  Hardware Description Language    111
Module Declaration 
The language reference manual for the Verilog HDL presents a syntax that describes 
precisely the constructs that can be used in the language. In particular, a Verilog 
model is composed of text using keywords, of which there are about 100. Keywords 
are predefined lowercase identifiers that define the language constructs. Examples of 
keywords are  module, endmodule, input, output, wire, and, or,  and  not.  For clarity, 
keywords will be displayed in boldface in the text in all examples of code and wher-
ever it is appropriate to call attention to their use. Any text between two forward 
slashes ( // ) and the end of the line is interpreted as a comment and will have no effect 
on a simulation using the model. Multiline comments begin with /   *    and terminate 
with    *   /. Blank spaces are ignored, but they may not appear within the text of a key-
word, a user-specified identifier, an operator, or the representation of a number. Ver-
ilog is case sensitive, which means that uppercase and lowercase letters are 
distinguishable (e.g.,  not  is not the same as NOT). The term  module  refers to the text 
enclosed by the keyword pair  module  . . .   endmodule.  A module is the fundamental 
descriptive unit in the Verilog language. It is declared by the keyword  module  and 
must always be terminated by the keyword  endmodule 
Combinational logic can be described by a schematic connection of gates, by a set of 
Boolean equations, or by a truth table. Each type of description can be developed in 
Verilog. We will demonstrate each style, beginning with a simple example of a Verilog 
gate-level description to illustrate some aspects of the language. 
The HDL description of the circuit of  Fig.   3.35    is shown in HDL  Example   3.1   . The 
first line of text is a comment (optional) providing useful information to the reader. The 
second line begins with the keyword  module  and starts the declaration (description) of 
the module; the last line completes the declaration with the keyword  endmodule.  The 
keyword  module  is followed by a name and a list of ports. The name ( Simple_Circuit  in 
this example) is an identifier. Identifiers are names given to modules, variables (e.g., a 
signal), and other elements of the language so that they can be referenced in the design. 
In general, we choose meaningful names for modules. Identifiers are composed of alpha-
numeric characters and the underscore (_), and are case sensitive. Identifiers must start 
with an alphabetic character or an underscore, but they cannot start with a number. 
A
w1
B
C
D
E
G1
G2
G3
FIGURE 3.35 
Circuit to demonstrate an HDL       
112    Chapter 3  Gate-Level Minimization
The  port list  of a module is the interface between the module and its environment. 
In this example, the ports are the inputs and outputs of the circuit. The logic values of 
the inputs to a circuit are determined by the environment; the logic values of the outputs 
are determined within the circuit and result from the action of the inputs on the circuit. 
The port list is enclosed in parentheses, and commas are used to separate elements of 
the list. The statement is terminated with a semicolon (;). In our examples, all keywords 
(which must be in lowercase) are printed in bold for clarity, but that is not a requirement 
of the language. Next, the keywords  input  and  output  specify which of the ports are 
inputs and which are outputs. Internal connections are declared as wires. The circuit in 
this example has one internal connection, at terminal  w1 , and is declared with the key-
word  wire.  The structure of the circuit is specified by a list of (predefined)  primitive  
gates, each identified by a descriptive keyword ( and, not, or ). The elements of the list 
are referred to as  instantiations  of a gate, each of which is referred to as a  gate instance . 
Each  gate instantiation  consists of an optional name (such as  G1, G2 , etc.) followed by 
the gate output and inputs separated by commas and enclosed within parentheses. The 
output of a primitive gate is always listed first, followed by the inputs. For example, the 
OR gate of the schematic is represented by the  or  primitive, is named  G3 , and has out-
put  D  and inputs  w1  and  E . ( Note : The output of a primitive must be listed first, but the 
inputs and outputs of a module may be listed in any order.) The module description ends 
with the keyword  endmodule.  Each statement must be terminated with a semicolon, but 
there is no semicolon after  endmodule.  
It is important to understand the distinction between the terms  declaration  and  instan-
tiation . A Verilog module is declared. Its declaration specifies the input–output behavior 
of the hardware that it represents. Predefined primitives are not declared, because their 
definition is specified by the language and is not subject to change by the user. Primitives 
are used (i.e., instantiated), just as gates are used to populate a printed circuit board. 
We’ll see that once a module has been declared, it may be used (instantiated) within a 
design. Note that  Simple_Circuit  is not a computational model like those developed in 
an ordinary programming language: The sequential ordering of the statements instanti-
ating gates in the model has no significance and does not specify a sequence of compu-
tations. A Verilog model is a  descriptive  model.  Simple_Circuit  describes what primitives 
form a circuit and how they are connected. The input–output behavior of the circuit is 
HDL Example 3.1 (Combinational Logic Modeled with Primitives) 
// Verilog model of circuit of Figure 3.35. IEEE 1364–1995 Syntax
module  Simple_Circuit (A, B, C, D, E);
output 
D, E;
input 
A, B, C;
wire 
w1;
and 
G1 (w1, A, B); // Optional gate instance name
not 
G2 (E, C);
or 
G3 (D, w1, E);
endmodule
Documents you may be interested
Documents you may be interested