FIT1047 – Week 2
hour 1
Introduction to computer systems, networks and security
Reference: https://www.alexandriarepository.org/syllabus/introduction-to-computer-systems-networks-and-security/
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett
FIT1047 Monash University
FIT1047 Monash University
FIT1047 Monash University
Boolean Algebra
● Boolean algebra is a mathematical system for the manipulation of variables that can have one of two values
○ In formal logic, these values are True/False
○ In digital systems, these values are on/off, 1/0 or high/low
● Boolean expressions are created by performing operations on Boolean variables
○ Common Boolean operators include AND, OR, NOT
FIT1047 Monash University
Truth Tables: AND
A Boolean operator can be completely described using a Truth Table
● Truth tables for the Boolean operators AND
● The AND operator can also be represented as a period (a full stop) or space, so X.Y or XY
AND
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Truth Tables: OR
A Boolean operator can be completely described using a Truth Table
● Truth tables for the Boolean operators OR
● The OR operator can also be represented as a + represented as X+Y
OR
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Truth Tables: NOT
● Truth table for the Boolean NOT operator
● The NOT operation is often designated by an overbar, a prime mark, an “elbow” or a “squiggle”, e.g.,
A’ A ~A
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
NOT
FIT1047 Monash University
Boolean Functions
A Boolean function has:
● At least one Boolean variable (x, y,..)
● At least one Boolean operator (and, or, not,..)
● At least one input from the set {0,1} or {T,F}
It produces an output that is also a member of the set {0,1} or {T,F}
FIT1047 Monash University
Boolean Functions and Truth Tables
● Truth table for the Boolean function
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
To make evaluation of the Boolean function easier, the truth table contains extra (shaded) columns to hold evaluations of subparts of the function
FIT1047 Monash University
Rules of Precedence
● The NOT operator has highest priority, followed by AND & then OR
○ This is how we chose the (shaded) function subparts in our table
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
●
Boolean Algebra
Digital computers contain circuits that implement Boolean functions
The simpler we can make a Boolean function, the smaller the circuit that will result
Simpler circuits are cheaper to build, consume less power, and run faster than complex circuits
With this in mind
○ We always want to reduce our Boolean functions to their simplest form
○ There are several Boolean identities that help us to do this
●
FIT1047 Monash University
FIT1047 Monash University
FIT1047 Monash University
(Inverse or Complement Law)
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
● Boolean Identities
Most Boolean identities have an AND
(product) form as well as an OR (sum) form
This group of Boolean identities should be
familiar to you from your study of algebra
This group of Boolean identities is perhaps the
most useful
● Optimization of Boolean functions
When realizing a function as circuit, one would
like to minimize gates. Boolean functions can
be minimized using the different laws.
However, determining the correct order of
applying the laws is sometimes difficult.
In addition, one would like to minimize the use
of different types of gates. Therefore,
normalized forms can be useful.
One generic approach for minimizing (smaller)
Boolean functions are Karnaugh maps or K- maps
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Simplifying a Function
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Simplifying using Karnaugh-Maps (K-map)
Provides a method for simplifying Boolean expressions.
It will produce the simplest Sums-Of-Products (SOP) and Product-Of-Sums (POS) expressions.
Works best for less than 6 variables.
Similar to a truth table it maps all possibilities.
A Karnaugh map is an array of cells arranged in a special manner.
The number of cells is 2n where n = number of variables
A 3-Variable Karnaugh Map:
A 4-Variable Karnaugh Map:
Note: The order of these values they are reverse of the usual order.
They are arranged this way so that only one variable changes at a time.
FIT1047 Monash University
Simplifying using Karnaugh-Maps (K-map)
=A.B
FIT1047 Monash University
Simplifying using Karnaugh-Maps (K-map)
•Find groups of 1s.
•The group of four 1s represents B=1. (Note: A=0/1, B=1, C=0/1 )
•The wrapped group represents A=1 AND C=0. (Note: A=1, While B = 0/1, C=0 )
FIT1047 Monash University
7 rules for working with Karnaugh-Maps (K-map)
Rule 1: No group can contain a zero.
Rule 2: Groups may be horizontal/vertical/square, but never diagonal.
Rule 3: Groups must contain 1, 2, 4, 8, 16, 32 ……(powers of 2) cells. Rule 4: Each group must be as large as possible.
Rule 5: Groups can overlap.
Rule 6: Each 1 must be part of at least one group.
Rule 7: Groups may wrap around the map.
Karnaugh-maps are useful for smaller Boolean functions. Automated algorithms for optimization are used for bigger functions.
Simplification example:
Simplifying using Karnaugh-Maps (K-map)
Simplifying using Karnaugh-Maps (K-map)
Simplification example:
F(A, B, C, D) ==
FIT1047 Monash University
Lecture 2 (Continued) Logic Gates and Truth Tables
FIT1047 Monash University
Logic Gates
● The logic gate is the building brick of digital logic
● A logic gate is an electronic device that produces a result based
on two or more input values
○ In reality, gates consist of one to six transistors, but digital designers think of them as a single unit
● Integrated circuits contain collections of gates suited to a particular purpose
FIT1047 Monash University
XOR
● The output of the XOR operation is True (1) only when the values of the inputs differ
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
NAND and NOR (I)
NAND and NOR gates have special properties:
1. NAND can be realised very efficiently.
2. All other gates can be build only using NAND gates.
NAND is = or NOR is = or
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
●
NAND and NOR (II)
Known as universal gates because they can be used to construct any gate
• Building NOT with NAND
gates
• Building AND with NAND gates
• Building OR with NAND gates
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Logic Gates: Inputs and Outputs
● Gates can have multiple inputs and more than one output ○ A second output can be provided for the complement of the operation
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Summarize topics of first 2 weeks
● A little bit of history
● Vacuum tubes and transistors
● bit, byte, word (8bit/16bit/32bit/64bit)
● Numbering systems (base 2, base 10, base 16)
● Conversion between numbering systems
● Signed integer representations (sign/magnitude, 1’s complement, 2’s
complement)
● Properties of 2’s complement, adding 2’s complement numbers
● Floating point representation
● Properties of floating point, precision, rounding
● Characters: ASCII and Unicode
● Error detection: Parity bits, Checksum, CRC
● Boolean Logic AND, OR, NOT, XOR, NAND, NOR
● Logic gates
● Simple logic circuits
● Boolean Algebra, Laws
● Karnaugh Maps/K-maps
FIT1047 Monash University
End of Lecture Week-2 Hour 1
FIT1047 – Week 2
hour 2
Introduction to computer systems, networks and security
Reference: https://www.alexandriarepository.org/syllabus/introduction-to-computer-systems-networks-and-security/
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett
FIT1047 Monash University
Logic Gates and Boolean Functions
● Combinations of gates implement Boolean functions Example
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Simplifying a Function
● Sometimes it is more economical to build a circuit using the complement of a function (and complementing its result) than it is to implement the function directly
DeMorgan’s law provides an easy way of finding the complement of a Boolean function
Recall DeMorgan’s law states
○
DeMorgan’s law can be extended to any number of variables
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Calculating the Complement of a Function
● Replace each variable by its complement and change all ANDs to ORs and all ORs to ANDs
● Example
○ Find the complement of:
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Canonical Form (I)
● There are numerous ways of stating the same Boolean expression
These “synonymous” forms are logically equivalent
Logically equivalent expressions have identical truth tables
In order to eliminate as much confusion as possible, designers express Boolean functions in standardized or canonical form
FIT1047 Monash University
Canonical Form (II)
There are two canonical forms for Boolean expressions ● Sum-of-products and product-of-sums
○ Recall the Boolean product is the AND operation and the Boolean sum is the OR operation ● Sum-of-products: ANDed variables are ORed together
○ For example: F(X,Y,Z) = XY + XZ + YZ
● Product-of-sums: ORed variables are ANDed together ○ For example: F(X,Y,Z) = (X+Y)(X+Z)(Y+Z)
FIT1047 Monash University
Converting to Sum of Products
We are interested in the values of the variables that make the function True (=1)
1. 2.
Using the Truth Table, make groups of ANDed variables (or negated variables), such that each group results in a True function value
OR together each group of variables
Converting to Sum of Products: Example
F(x,y,z) xyz xyz xy z xyz
xyz
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
Converting to Product of Sums
We are interested in the values of the variables that make the function False (=0)
1. Complement all the function values (function output)
2. Using the Truth Table, make groups of ANDed variables (or negated variables), such that each group results in a True value for
the complement of the function (False value for the function)
3. OR together each group of variables This yields the complement of the function
4. Take the complement of this complement This yields the function itself
Converting to Product of Sums: Example
F(x, y, z) x y z x y z xyz (x y z)(x y z)(xyz)
(x y z)(x y z)(x y z) Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
7 rules for working with Karnaugh-Maps (K-map)
Rule 1: No group can contain a zero.
Rule 2: Groups may be horizontal/vertical/square, but never diagonal.
Rule 3: Groups must contain 1,2,4,8,16,32 ……….(powers of 2) cells. Rule 4: Each group must be as large as possible.
Rule 5: Groups can overlap.
Rule 6: Each 1 must be part of at least one group.
Rule 7: Groups may wrap around the map.
Karnaugh-maps are useful for smaller Boolean functions. Automated algorithms for optimization are used for bigger functions.
FIT1047 Monash University
Converting to Sum of Products: Example
F(x,y,z) xyz xyz xy z xyz
xyz
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
FIT1047 TUTORIAL 2 (week-2)
METHOD – II : Using K-maps
1 1
1 1
=A𝐁+C
1
FIT1047 Monash University
FIT1047 TUTORIAL 2 (week-2)
METHOD – I : Using Boolean Identities
Reference: Linda Null, Julia Lobur. The essentials of computer organization and architecture. Fourth edition, 2015. Jones & Bartlett Learning.
FIT1047 Monash University
FIT1047 TUTORIAL 2 (week-2)
=A𝐁+C
Simulate using logisim
FIT1047 Monash University
Summarize topics of first 2 weeks
● A little bit of history
● Vacuum tubes and transistors
● bit, byte, word (8bit/16bit/32bit/64bit)
● Numbering systems (base 2, base 10, base 16)
● Conversion between numbering systems
● Signed integer representations (sign/magnitude, 1’s complement, 2’s
complement)
● Properties of 2’s complement, adding 2’s complement numbers
● Floating point representation
● Properties of floating point, precision, rounding
● Characters: ASCII and Unicode
● Error detection: Parity bits, Checksum, CRC
● Boolean Logic AND, OR, NOT, XOR, NAND, NOR
● Logic gates
● Simple logic circuits
● Boolean Algebra, Laws
● Karnaugh Maps/K-maps
FIT1047 Monash University
END of Lecture 2
FIT1047 Monash University
FIT1047 Monash University
FIT1047 Monash University