Numbers and Boolean Algebra N

Computer Organization
By
Dr. M. Khamis
Mrs. Dua’a Al Sinari
Computer Organization
 The course is aimed at designing the different computer
components (circuits) and connecting these components
in a way to achieve the goals of a specific architectures.
 Computer (hardware) consists of processor, memory and I/O
units.
 Processor itself consists of Arithmetic Logic Unit (ALU) and
Control unit.
All the above units are designed using primitive logic circuits.
Course Objectives
 Understanding the basic Laws of Boolean algebra.
 Designing and using the basic logic devices.
 Understanding the operation of the main computer
units and their design.
 Interconnecting the various computer units to achieve
the specific architecture.
 Presenting the attributes of the different architectures.
 Programming specific architecture using its instruction
set (machine instruction).
 Explaining the Interaction between Computer hardware
and the operating system.
Course outline
 The course will consist of two parts:
 The first part is Logic design: in which
the primitive
components, by which the different devices are designed, are
presented.
 The second part is intended for interconnecting the
components presented in first part in a way to build a logical
system (computer organization).
Part 1: Logic Design
 Introduction to number systems and arithmetic
operations in binary system.
 Combinational circuits:
 Logic Gates (AND, OR, NOT, NOR, NAND and XOR), in this
regards we will give the truth tables and symbols for each .
 Laws of Boolean algebra, deriving logical expression and
simplification.
 Karnaugh maps and its use for simplification .
 half and full adders and binary coded decimal adders
Part 1: Logic Design
 devices include:
Decoder.
 Encoder.
 Multiplexers/ De-multiplexer.
 Comparator.
 Sequential circuits include :
 Flip/Flops and counter
 Design Mealy and MOORE machines.
Part 2: Computer Organization
 chapter 3: computer system
 chapter 7: Input/output
 chapter 8: Operating System Support.
 chapter 9: Computer Arithmetic
 chapter 10: Instruction Sets.
 chapter 11: :Instruction Sets: Addressing Modes and
Format.
 chapter 12: CPU structure
 chapter 16 : Control Unit
 chapter 17: Micro Programmed Control Unit.
NUMBERS AND BOOLEAN
ALGEBRA
Author: Abhinav Bhatele

Revised By: Dr. M. Khamis
FAll 2008
NUMBER SYSTEMS
June 10th, 2008

 To get started, we’ll discuss one of the fundamental concepts
underlying digital computer design:
Number Systems and Boolean Algebra

Deep down inside, computers work with just 1s and 0s.
 Computers use voltages to represent information. In modern
CPUs the voltage is usually limited to 1.6-1.8V to minimize
power consumption. Volts
1.8
 It’s convenient for us to translate these analog
voltages into the discrete, or digital, values 1 and 0. 1
 But how can binary system be useful for anything?
 First, we’ll see how to represent numbers with 0
just 1s and 0s. 0
 Then we’ll introduce special operations
for computing with 1s and 0s, by treating them as 9
the logical values “true” and “false.”
TODAY’S LECTURE
June 10th, 2008

 Number systems
 Review of binary number representation

 How to convert between binary and decimal representations
 Octal and Hex representations
 Basic boolean operations

 AND, OR and NOT
 The idea of “Truth Table”
 Boolean functions and expressions
 Truth table for Boolean expressions
10
DECIMAL REVIEW
June 10th, 2008

 Numbers consist of a bunch of digits, each with a weight
1 6 2 . 3 7 5 Digits
100 10 1 1/10 1/100 1/1000 Weights

 These weights are all powers of the base, which is 10.
We can rewrite this:
1 6 2 . 3 7 5 Digits
102 101 100 10-1 10-2 10-3 Weights
 To find the decimal value of a number, multiply each
digit by its weight and sum the products.
(1 x 102) + (6 x 101) + (2 x 100) + (3 x 10-1) + (7 x 10-2) + (5 x 10-3) = 162.375
11
CONVERTING BINARY TO DECIMAL
June 10th, 2008

 We can use the same trick to convert binary, or base 2, numbers to
decimal. This time, the weights are powers of 2.
 Example: 1101.01 in binary

1 1 0 1 . 0 1 Binary digits, or bits
23 22 21 20 2-1 2-2 Weights (in base 2)
 The decimal value is:
(1 x 23) + (1 x 22) + (0 x 21) + (1 x 20) + (0 x 2-1) + (1 x 2-2) =
8 + 4 + 0 + 1 + 0 + 0.25 = 13.25
Powers of 2: Useful abbreviations:

20 = 1 24 = 16 28 = 256 K = 210 = 1,024
21 = 2 25 = 32 29 = 512 M = 220 = 1,048,576
22 = 4 26 = 64 210 = 1024 G = 230 = 1,073,741,824 12
23 = 8 27 = 128
CONVERTING DECIMAL TO BINARY
June 10th, 2008

 To convert a decimal integer into binary, keep dividing by 2 until the
quotient is 0. Collect the remainders in reverse order.
 To convert a fraction, keep multiplying the fractional part by 2 until
it becomes 0. Collect the integer parts in forward order.

 Example: 162.375:
162 / 2 = 81 rem 0 0.375 x 2 = 0.750

81 / 2 = 40 rem 1 0.750 x 2 = 1.500
40 / 2 = 20 rem 0 0.500 x 2 = 1.000
20 / 2 = 10 rem 0
10 / 2 =5 rem 0
5/2 =2 rem 1
2/2 =1 rem 0
1/2 =0 rem 1
13
 So, 162.37510 = 10100010.0112
WHY DOES THIS WORK?
June 10th, 2008

 This works for converting from decimal to any base
 Why? Think about converting 162.375 from decimal
to decimal.

162 / 10 = 16 rem 2
16 / 10 = 1 rem 6
1 / 10 = 0 rem 1
 Each division strips off the rightmost digit (the
remainder). The quotient represents the remaining
digits in the number.
 Similarly, to convert fractions, each multiplication
strips off the leftmost digit (the integer part). The
fraction represents the remaining digits.
14
0.375 x 10 = 3.750
0.750 x 10 = 7.500
0.500 x 10 = 5.000
BASE 16 IS USEFUL TOO
June 10th, 2008

Decimal
Decimal Binary
Binary Hex
Hex
 The hexadecimal system uses 16 digits: 00 0000
0000 00
11 0001
0001 11
0123456789ABCDEF 22 0010
0010 22
33 0011
0011 33

 You can convert between base 10 and base 44 0100
0100 44
16 using techniques like the ones we just 55 0101
0101 55
showed for converting between decimal 66 0110
0110 66
77 0111 77
and binary. 88
0111
1000 88
1000
 For our purposes, base 16 is most useful as 99 1001
1001 99
a “shorthand” notation for binary 10
10 1010
1010 AA
11
11 1011
1011 BB
numbers. 12 1100 CC
12 1100
 Since 16 = 24, one hexadecimal digit is 13
13 1101
1101 DD
equivalent to 4 binary digits. 14
14 1110
1110 EE
 It’s often easier to work with a number like B4 15
15 1111
1111 FF
instead of 10110100.
 Hex is frequently used to specify things like 15
32-bit IP addresses and 24-bit colors.
BINARY AND HEXADECIMAL CONVERSIONS
June 10th, 2008

 Converting from hexadecimal to binary is easy: just replace each hex digit
with its equivalent 4-bit binary sequence.
261.3516 = 2 6 1 . 3 516

= 0010 0110 0001 . 0011 01012
 To convert from binary to hex, make groups of 4 bits, starting from the
binary point. Add 0s to the ends of the number if needed. Then, just
convert each bit group to its corresponding hex digit.
10110100.0010112 = 1011 0100 . 0010 11002
= B 4 . 2 C16
Hex Binary Hex Binary Hex Binary Hex Binary

0 0000 4 0100 8 1000 C 1100
1 0001 5 0101 9 1001 D 1101
2 0010 6 0110 A 1010 E 1110 16
3 0011 7 0111 B 1011 F 1111
2’s complement
 Binary number can be represented using sign and
magnitude. If N bits are used to represent the number,
then the last bit is used to hold the sign of the number
while the other (N-1) bits are used to represent the
value.
 0 is used for –ve sign and 1 is used for +ve sign.
 To get the 2’s complement for any number follow the
following two steps:
1. Convert each bit in the value into its complement (1 to 0
and vice versa)
2. Add 1 to the result of step 1.
Binary addition & subtraction
 If the number is +ve keep it in sign and magnitude form,
otherwise represent the number (magnitude only) using
its 2’s complement.
 Add the binary numbers in the ordinary way as the
decimal numbers.
 The addition in decimal makes carry 1 for the next digit
for each 10 collected in the sum, and the reset which
will be less than 10 is left as result of the addition of
corresponding bits.
 This operation continues until adding all of the
corresponding bits in the numbers.
Binary addition & subtraction (Continued)
 The addition in binary is exactly the same as decimal
with only one difference, which is, carry 1 is taken for
the next digit for each 2 collected in the sum, and the
reset which is less than 2 is left as result of the addition
of corresponding bits.
 The addition is continued for all bits including the sign
bit, and in order to get correct answer the number must
be represented in enough number of bits.
 Any carry after the sign bit is discarded.
 The value of the negative result is represented in the 2’s

complement (i.e. the actual value is the 2’s complement
of the result once again).
NUMBER SYSTEMS SUMMARY
June 10th, 2008

 Computers are binary devices.
 We’re forced to think in terms of base 2.
 Today we learned how to convert numbers between binary, decimal

and hexadecimal.
 Also, we have seen:
 We use 0 and 1 as abstractions for analog voltages.
 We showed how to represent numbers using just these two signals.
 Next we’ll introduce special operations for binary values and show how
those correspond to circuits.
20
BOOLEAN OPERATIONS
June 10th, 2008

 So far, we’ve talked about how arbitrary numbers can be
represented using just the two binary values 1 and 0.

 Now we’ll interpret voltages as the logical values “true”
and “false” instead. We’ll show:
 How logical functions can be defined for expressing
computations
 How to build circuits that implement our functions in
hardware
21
BOOLEAN VALUES
June 10th, 2008

 Earlier, we used electrical voltages to represent
two discrete values 1 and 0, from which binary numbers
can be formed.

 It’s also possible to think of voltages as representing
two logical values, true and false. Volts
1.8
 For simplicity, we often still write digits instead:
True
1 is true
 0 is false
False
 We will use this interpretation along with special 0
operations to design functions and hardware for doing
arbitrary computations.
22
FUNCTIONS
June 10th, 2008

 Computers take inputs and produce outputs, just like functions in math!
An expression is A function table is

finite but not unique unique but infinite
f(x,y) = 2x + y x y f(x,y)
 Logical functions can= bex expressed
+ x + y in two ways: 0 0 0
= 2(x + y/2)
 A finite, but non-unique Boolean expression. … … …
 A truth table, which will turn out to be unique and finite. 2 2 6
= ... … … …
23 41 87
… … …
 We can represent logical functions in two analogous ways too: 23

 A finite, but non-unique Boolean expression.
 A truth table, which will turn out to be unique and finite.
BASIC BOOLEAN OPERATIONS
June 10th, 2008

 There are three basic operations for logical values.

Operation: AND (product) OR (sum) of NOT (complement)
of two inputs two inputs on one input
Expression: xy, or xy x+y x’
Truth table: x y xy x y x+y x x’

0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
24
BOOLEAN EXPRESSIONS
June 10th, 2008

 We can use these basic operations to form more complex expressions:
f(x,y,z) = (x + y’)z + x’

 Some terminology and notation:
 f is the name of the function.
 (x,y,z) are the input variables, each representing 1 or 0. Listing the
inputs is optional, but sometimes helpful.
 A literal is any occurrence of an input variable or its complement. The
function above has four literals: x, y’, z, and x’.
 Precedences are important, but not too difficult.
 NOT has the highest precedence, followed by AND, and then OR.
 Fully parenthesized, the function above would be kind of messy:
f(x,y,z) = (((x +(y’))z) + x’)

25
TRUTH TABLES
June 10th, 2008

 A truth table shows all possible inputs and outputs of a function.
 Remember that each input variable represents either 1 or 0.
 Because there are only a finite number of values (1 and 0), truth tables

themselves are finite.
 n
A function with n variables has 2 possible combinations of inputs.
 Inputs are listed in binary order—in this example, from 000 to 111.
f(x,y,z) = (x + y’)z + x’
x y z f(x,y,z)
0 0 0 1
0 0 1 1
f(0,0,0) = (0 + 1)0 + 1 =1
0 1 0 1
f(0,0,1) = (0 + 1)1 + 1 =1
f(0,1,0) = (0 + 0)0 + 1 =1 0 1 1 1
f(0,1,1) = (0 + 0)1 + 1 =1 1 0 0 0
f(1,0,0) = (1 + 1)0 + 0 =0 1 0 1 1
f(1,0,1) = (1 + 1)1 + 0 =1 1 1 0 0 26
f(1,1,0) = (1 + 0)0 + 0 =0 1 1 1 1
f(1,1,1) = (1 + 0)1 + 0 =1
PRIMITIVE LOGIC GATES
June 10th, 2008

 Each of our basic operations can be implemented in
hardware using a primitive logic gate.

 Symbols for each of the logic gates are shown below.
 These gates output the product, sum or complement of their
inputs.
Operation: AND (product) OR (sum) of NOT (complement)

of two inputs two inputs on one input
Expression: xy, or xy x+y x’
Logic gate:
27
EXPRESSIONS AND CIRCUITS
June 10th, 2008

 Any Boolean expression can be converted into a circuit by
combining basic gates in a relatively straightforward way.
 The diagram below shows the inputs and outputs of each gate.

 The precedences are explicit in a circuit. Clearly, we have to make
sure that the hardware does operations in the right order!
(x + y’)z + x’
28
CIRCUIT ANALYSIS SUMMARY
June 10th, 2008

 After finding the circuit inputs and outputs, you can come up with either an
expression or a truth table to describe what the circuit does.
 You can easily convert between expressions and truth tables.

Find the circuit’s
inputs and outputs
Find a Boolean
Find a truth table
expression
for the circuit
for the circuit
29
BOOLEAN OPERATIONS SUMMARY
June 10th, 2008

 We can interpret high or low voltage as representing true or false.
 A variable whose value can be either 1 or 0 is called a Boolean variable.
 AND, OR, and NOT are the basic Boolean operations.

 We can express Boolean functions with either an expression or a truth
table.
 Every Boolean expression can be converted to a circuit.
 Next, we’ll look at how Boolean algebra can help simplify expressions,
which in turn will lead to simpler circuits.
30
BOOLEAN ALGEBRA
June 10th, 2008

 Last time we talked about Boolean functions, Boolean expressions, and
truth tables.
 Now we’ll learn how to how use Boolean algebra to simplify Booleans

expressions.
 Last time, we saw this expression and converted it to a circuit:
(x + y’)z + x’
Can we make this circuit “better”?

• Cheaper: fewer gates
• Faster: fewer delays from inputs to
outputs
31
EXPRESSION SIMPLIFICATION
June 10th, 2008

 Normal mathematical expressions can be simplified using the laws of
algebra
 For binary systems, we can use Boolean algebra, which is superficially

similar to regular algebra
 There are many differences, due to
 having only two values (0 and 1) to work with
 having a complement operation
 the OR operation is not the same as addition
32
FORMAL DEFINITION OF BOOLEAN ALGEBRA
June 10th, 2008

 A Boolean algebra requires
 A set of elements B, which needs at least two elements (0 and 1)
 Two binary (two-argument) operations OR and AND

 A unary (one-argument) operation NOT
 The axioms below must always be true (textbook, p. 42)
 The magenta axioms deal with the complement operation
 Blue axioms (especially 15) are different from regular algebra
1. x+0=x 2. x1=x
3. x+1=1 4. x0=0
5. x+x=x 6. xx=x
7. x + x’ = 1 8. x  x’ = 0
9. (x’)’ = x
10. x+y=y+x 11. xy = yx Commutative
12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative
14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive
16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’s 33
COMMENTS ON THE AXIOMS
June 10th, 2008

 The associative laws show that there is no ambiguity about a term such as x
+ y + z or xyz, so we can introduce multiple-input primitive gates:

 The left and right columns of axioms are duals
 exchange all ANDs with ORs, and 0s with 1s
 The dual of any equation is always true
1. x+0=x 2. x1=x
3. x+1=1 4. x0=0
5. x+x=x 6. xx=x
7. x + x’ = 1 8. x  x’ = 0
9. (x’)’ = x
34
16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’s
ARE THESE AXIOMS FOR REAL?
June 10th, 2008

 We can show that these axioms are valid, given the definitions of AND, OR
and NOT
x y xy x y x+y x x’

0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
 The first 11 axioms are easy to see from these truth tables alone. For
example, x + x’ = 1 because of the middle two lines below (where y = x’)
x y x+y
0 0 0
0 1 1
1 0 1 35
1 1 1
PROVING THE REST OF THE AXIOMS
June 10th, 2008

 We can make up truth tables to prove (both parts of) DeMorgan’s law
 For (x + y)’ = x’y’, we can make truth tables for (x + y)’ and for x’y’

x y x+y (x + y)’ x y x’ y’ x’y’
0 0 0 1 0 0 1 1 1
0 1 1 0 0 1 1 0 0
1 0 1 0 1 0 0 1 0
1 1 1 0 1 1 0 0 0
 In each table, the columns on the left (x and y) are the inputs. The columns
on the right are outputs.
 In this case, we only care about the columns in blue. The other “outputs”
are just to help us find the blue columns.
 Since both of the columns in blue are the same, this shows that (x + y)’ and 36
x’y’ are equivalent
SIMPLIFICATION WITH AXIOMS
June 10th, 2008

 We can now start doing some simplifications
x’y’ + xyz + x’y

= x’(y’ + y) + xyz [ Distributive; x’y’ + x’y = x’(y’ + y) ]
= x’1 + xyz [ Axiom 7; y’ + y = 1 ]
= x’ + xyz [ Axiom 2; x’1 = x’ ]
= (x’ + x)(x’ + yz) [ Distributive ]
= 1  (x’ + yz) [ Axiom 7; x’ + x = 1 ]
= x’ + yz [ Axiom 2 ]
1. x+0=x 2. x1=x
3. x+1=1 4. x0=0
5. x+x=x 6. xx=x
7. x + x’ = 1 8. x  x’ = 0
9. (x’)’ = x
37
16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’s
LET’S COMPARE THE RESULTING CIRCUITS
June 10th, 2008

 Here are two different
but equivalent circuits.
 In general the one

with fewer gates is
“better”:
 It costs less to
build
 It requires less
power
 But we had to do
some work to find
the second form
38
SOME MORE LAWS
June 10th, 2008

 Here are some more useful laws. Notice the duals again!
1. x + xy = x 4. x(x + y) = x
2. xy + xy’ = x 5. (x + y)(x + y’) = x

3. x + x’y = x + y 6. x(x’ + y) = xy
xy + x’z + yz = xy + x’z (x + y)(x’ + z)(y + z) = (x + y)(x’ + z)
 We can prove these laws by either
 Making truth tables:
x y x’ x’y x + x’y x y x+y
0 0 0 0 0
0 1 0 1 1
1 0 1 0 1
1 1 1 1 1
 Using the axioms: x + x’y = (x + x’)(x + y) [ Distributive ]

= 1  (x + y) [ x + x’ = 1 ] 39
=x+y [ Axiom 3 ]
THE COMPLEMENT OF A FUNCTION
June 10th, 2008

 The complement of a function always outputs 0 where the original function
outputted 1, and 1 where the original produced 0.
 In a truth table, we can just exchange 0s and 1s in the output column(s)

f(x,y,z) = x(y’z’ + yz)
x y z f(x,y,z) x y z f’(x,y,z)
0 0 0 1 0 0 0 0
0 0 1 1 0 0 1 0
0 1 0 1 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 1 1 1 0 0
1 1 1 0 1 1 1 1 40
COMPLEMENTING A FUNCTION
ALGEBRAICALLY
June 10th, 2008

 You can use DeMorgan’s law to keep “pushing” the complements inwards
f(x,y,z) = x(y’z’ + yz)

f’(x,y,z) = ( x(y’z’ + yz) )’ [ complement both sides ]
= x’ + (y’z’ + yz)’ [ because (xy)’ = x’ + y’ ]
= x’ + (y’z’)’ (yz)’ [ because (x + y)’ = x’ y’ ]
= x’ + (y + z)(y’ + z’) [ because (xy)’ = x’ + y’, twice]
 You can also take the dual of the function, and then complement each
literal
 If f(x,y,z) = x(y’z’ + yz)…
 … the dual of f is x + (y’ + z’)(y + z)…
 … then complementing each literal gives x’ + (y + z)(y’ + z’)…
 … so f’(x,y,z) = x’ + (y + z)(y’ + z’)
41
SUMMARY SO FAR
June 10th, 2008

 So far:
 A bunch of Boolean algebra trickery for simplifying expressions and
circuits

 The algebra guarantees us that the simplified circuit is equivalent to the
original one
 Next:
 Introducing some standard forms and terminology
 An alternative simplification method
 We’ll start using all this stuff to build and analyze bigger, more useful,
circuits
42
Parity Checking
 Parity checking is used to check the correctness or
erroneous of data.
 Circuit used to raise 1 on its output when its input data
contain even number of 1’s is called even parity circuit,
otherwise it called odd parity circuit.
 Parity checking is used with memory to ensure the read
data is exactly as written one or otherwise, it interrupts
the main processor. Also, it is used within the modem to
ensure the correct arrival of the received data.
Parity Checking with the Main Memory
Parity RAM
Data RAM
Parity cct
To interrut processor
Parity cct
How is parity circuits detect the error?
Original Correct defected

Data circuit circuit
Odd odd even
Even odd even
 The table depicts the expected output of the parity

checking during reading data (yellow circuit).
 Note that the output will be always1 when memory is
defected, otherwise, it will be 0.
Design parity checking for 3-inputs
 For sake of simplicity 3-inputs are x y z F
considered. The truth table will be
as shown. The output (F) of the 1 1 1 0
even parity circuit is 1 when the
1 1 0 1
number of the 1’s in the inputs are
even. 1 0 1 1
 F= xyz’ + xy’z + x’yz + x’y’z’
1 0 0 0
 (Draw the corresponding circuit for 0 1 1 1
the above logic expression to get
the odd parity circuit for 3-inputs) 0 1 0 0
0 0 1 0
0 0 0 1
How to add binary numbers
 Consider adding two 1-bit binary numbers x and y
 0+0 = 0
 0+1 = 1 x y Carry Sum
 1+0 = 1
 1+1 = 10
0 0 0 0
0 1 0 1
1 0 0 1
 Carry is x AND y 1 1 1 0
 Sum is x XOR y
 The circuit to compute this is called a half-adder
The half-adder
 Sum = x XOR y
 Carry = x AND y
x x
y y Sum
Sum
Carry
Carry
Using half adders
 We can then use a half-adder to compute the sum of
two Boolean numbers
1 0 0
1 1 0 0
+1 1 1 0
? 0 1 0
How to fix this
 We need to create an adder that can take a carry bit as an
additional input
 Inputs: x, y, carry in x y c carry sum
 Outputs: sum, carry out
1 1 1 1 1
 This is called a full adder
 Will add x and y with a half-adder 1 1 0 1 0
 Will add the sum of that to the
1 0 1 1 0
carry in
 What about the carry out? 1 0 0 0 1
 It’s 1 if either (or both): 0 1 1 1 0
 x+y = 10
 x+y = 01 and carry in = 1 0 1 0 0 1
0 0 1 0 1
0 0 0 0 0
The full adder
 The “HA” boxes are half-adders
cc X
X HA
HA S
S
s
Y
Y C
C
xx X
X HA
HA S
S
c
yy
Y
Y C
C
The full adder
 The full circuitry of the full adder
c
s
x
y
c
Adding bigger binary numbers (4 bits parallel
binary adder)
 This design is available with IC 7483
x0 X HA S
s0
y0 Y C
x1
C
X
FA S
s1
y1 Y C
x2
C
X
FA S
s2
y2 Y C
x3
C
X
FA S
s3
y3 Y C
c
Seven Segment
 Example
 Seven-segment display used to display binary values visually
 To do so it needs a driver to convert from 4 bit binary to 7-segments
output.
d’ output of the driver (decoder to 7 segment)
Simplified expression of “d”
Karnaugh Map Method
Don’t cares simplify the expression a lot
Using decoder to 7-segment to display the
output of the 4-bits adder on 7-segment
 All output of the decoder to 7-segments is calculated in
similar way (IC 7447 performing the function of the
decoder to 7-segments).
Adding bigger binary numbers
 A half adder has 4 logic gates
 A full adder has two half adders plus a OR gate
 Total of 9 logic gates
 To add n bit binary numbers, you need 1 HA and n-1 FAs
 To add 32 bit binary numbers, you need 1 HA and 31 FAs
 Total of 4+9*31 = 283 logic gates
 To add 64 bit binary numbers, you need 1 HA and 63 FAs
 Total of 4+9*63 = 571 logic gates
More about logic gates
 To implement a logic gate in hardware, you use a
transistor
 Transistors are all enclosed in an “IC”, or integrated
circuit
 The current Intel Pentium IV processors have 55 million
transistors!
Summary: Digital Logic Basics
 Hardware consists of a few simple building blocks
 These are called logic gates
AND, OR, NOT, …

 NAND, NOR, XOR, …
 Logic gates are built using transistors
 NOT gate can be implemented by a single transistor
 AND gate requires 3 transistors
 Transistors are the fundamental devices
 Pentium consists of 3 million transistors
 Compaq Alpha consists of 9 million transistors
 Now we can build chips with more than 100 million
transistors
Basic Concepts
 Simple gates
 AND
 OR
 NOT
 Functionality can be
expressed by a truth table
 A truth table lists output
for each possible input
combination
 Precedence
 NOT > AND > OR
 F=AB+AB
= (A (B)) + ((A) B)
Basic Concepts (cont.)
 Additional useful gates
 NAND
 NOR
 XOR
 NAND = AND + NOT
 NOR = OR + NOT
 XOR implements exclusive-
OR function
 NAND and NOR gates
require only 2 transistors
 AND and OR need 3
transistors!
 Basic building block:
 Transistor
 Three connection points

 Base
 Emitter
 Collector
 Transistor can operate

 Linear mode
 Used in amplifiers
 Switching mode
 Used to implement
digital circuits
 Number of functions
 With N logical variables, we can define
N
22 functions
 Some of them are useful
 AND, NAND, NOR, XOR, …

 Some are not useful:
 Output is always 1
 Output is always 0
 “Number of functions” definition is useful in proving

completeness property
 Complete sets
 A set of gates is complete
 If we can implement any logical function using
only the type of gates in the set
You can uses as many gates as you want

 Some example complete sets

 {AND, OR, NOT} Not a minimal
complete set
 {AND, NOT}
 {OR, NOT}
 {NAND}
 {NOR}
 Minimal complete set

 A complete set with no redundant elements.
 Proving NAND gate is universal
 NAND gate is called universal gate
 Proving NOR gate is universal
 NOR gate is called universal gate
Logic Chips
Logic Chips (cont.)
 Integration levels
 SSI (small scale integration)
 Introduced in late 1960s
 1-10 gates (previous examples)
 MSI (medium scale integration)

 10-100 gates
 LSI (large scale integration)

 Introduced in early 1970s
 100-10,000 gates
 VLSI (very large scale integration)

 More than 10,000 gates
Logic Functions
 Logical functions can be expressed in several ways:
 Truthtable
 Logical expressions
 Graphical form
 Example:
 Majority function
 Output is 1 whenever majority of inputs is 1
 We use 3-input majority function
Logic Functions (cont.)
3-input majority function  Logical expression form
A B C F F=AB+BC+AC
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Logical Equivalence
 All three circuits implement F = A B function
Logical Equivalence (cont.)
 Proving logical equivalence of two circuits
 Derive the logical expression for the output of each
circuit
 Show that these two expressions are equivalent
 Two ways:
 You can use the truth table method
 For every combination of inputs, if both expressions yield the
same output, they are equivalent
 Good for logical expressions with small number of variables
 You can also use algebraic manipulation

 Need Boolean identities
 Derivation of logical expression from a circuit
 Trace from the input to output
 Write down intermediate logical expressions along the
path
 Proving logical equivalence: Truth table method
A B F1 = A B F3 = (A + B) (A + B) (A + B)
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1
Logic Circuit Design Process
 A simple logic design process involves
 Problem specification
 Truth table derivation
 Derivation of logical expression
 Simplification of logical expression
 Implementation
Deriving Logical Expressions
 Derivation of logical expressions from truth tables
 sum-of-products (SOP) form
 product-of-sums (POS) form
 SOP form
 Writean AND term for each input combination that
produces a 1 output
 Write the variable if its value is 1; complement
otherwise
 OR the AND terms to get the final expression
 POS form
 Dual of the SOP form
Deriving Logical Expressions (cont.)
 3-input majority function  SOP logical expression
A B C F  Four product terms
 Because there are 4 rows
0 0 0 0 with a 1 output
0 0 1 0
0 1 0 0
0 1 1 1 F=ABC+ABC+
1 0 0 0 ABC+ABC
1 0 1 1
1 1 0 1
1 1 1 1
Deriving Logical Expressions (cont.)
 3-input majority function  POS logical expression
A B C F  Four sum terms
 Because there are 4 rows
0 0 0 0 with a 0 output
0 0 1 0
0 1 0 0
0 1 1 1 F = (A + B + C) (A + B + C)
1 0 0 0 (A + B + C) (A + B + C)
1 0 1 1
1 1 0 1
1 1 1 1
Logical Expression Simplification
 Two basic methods
 Algebraic manipulation
 Use Boolean laws to simplify the expression
Difficult to use

 Don’t know if you have the simplified form
 Karnaugh map (K-map) method

 Graphical method
 Easy to use
 Can be used to simplify logical expressions with a few
variables
Algebraic Manipulation
 Majority function example Added extra
ABC+ABC+ABC+ABC =
ABC+ABC+ABC+ABC+ABC+ABC
 We can now simplify this expression as
BC+AC+AB
 A difficult method to use for complex expressions

Karnaugh Map Method
Note the order
Karnaugh Map Method (cont.)
Simplification examples
First and last columns/rows are adjacent
Minimal expression depends on groupings
No redundant groupings
 Example
 Seven-segment display
 Need to select the right LEDs to display a digit
Don’t cares simplify the expression a lot
Implementation Using NAND Gates
 Using NAND gates
 Get an equivalent expression
AB+CD=AB+CD
 Using de Morgan’s law
AB+CD=AB.CD
 Can be generalized
 Majority function
A B + B C + AC = A B . BC . AC
Idea: NAND Gates: Sum-of-Products, NOR Gates: Product-of-Sums

Implementation Using NAND Gates (cont.)
 Majority function
Introduction to Combinational Circuits
 Combinational circuits
 Output depends only on the current inputs
 Combinational circuits provide a higher level of

abstraction
 Help in reducing design complexity
 Reduce chip count
 We look at some useful combinational circuits

Multiplexers
 Multiplexer
 2n
4-data input MUX
data inputs
 n selection inputs
 a single output
 Selection input
determines the
input that should
be connected to
the output
Multiplexers (cont.)
4-data input MUX implementation
MUX implementations
Example chip: 8-to-1 MUX
Efficient implementation: Majority function
Demultiplexers (DeMUX)
 Demultiplexer
a single input
 n selection inputs
 2n outputs
Decoders
 Decoder selects one-out-of-N inputs
Decoders (cont.)
Logic function implementation
Comparator
 Used to implement comparison operators (= , > , < ,  , )
A=B: Ox = Ix (x=A<B, A=B, & A>B)
Comparator (cont.)
4-bit magnitude comparator chip
Comparator (cont.)
Serial construction of an 8-bit comparator
1-bit Comparator
x>y
CMP x=y
x<y
x y
x y x>y x=y x<y

8-bit comparator
xn>yn x>y
xn=yn CMP x=y
xn<yn x<y
x y
Adders
 Half-adder
 Adds two bits
 Produces a sum and carry

 Problem: Cannot use it to build larger inputs
 Full-adder
 Adds three 1-bit values
 Like half-adder, produces a sum and carry

 Allows building N-bit adders
 Simple technique
 Connect Cout of one adder to Cin of the next
 These are called ripple-carry adders
Adders (cont.)
Adders (cont.)
A 16-bit ripple-carry adder
Adders (cont.)
 Ripple-carry adders can be slow
 Delay proportional to number of bits
 Carry lookahead adders
 Eliminate the delay of ripple-carry adders
 Carry-ins are generated independently
C0 = A0 B0
C = A B A + A B B + A B
1 0 0 1 0 0 1 1 1
 ...
 Requires complex circuits
 Usually, a combination carry lookahead and
ripple-carry techniques are used
Programmable Logic Arrays
 PLAs
 Implement sum-of-product expressions
 No need to simplify the logical expressions

 Take N inputs and produce M outputs
 Each input represents a logical variable

 Each output represents a logical function output
 Internally uses
 An AND array
 Each AND gate receives 2N inputs
 N inputs and their complements
 An OR array
Programmable Logic Arrays (cont.)
A blank PLA with 2 inputs and 2 outputs
Implementation examples
Simplified notation
1-bit Arithmetic and Logic Unit
Preliminary ALU design
2’s complement
Required 1 is added via Cin
1-bit Arithmetic and Logic Unit (cont.)
Final design
Arithmetic and Logic Unit (cont.)
16-bit ALU
Arithmetic and Logic Unit (cont’d)
4-bit ALU
Introduction to Sequential Circuits
 Output depends on current as well as past inputs
 Depends on the history
 Have “memory” property
 Sequential circuit consists of

 Combinational circuit
 Feedback circuit
 Past input is encoded into a set of state variables
 Uses feedback (to feed the state variables)

 Simple feedback
 Uses flip flops
Introduction (cont.)
Main components of a sequential circuit
Clock Signal
Clock Signal (cont.)
 Clock serves two distinct purposes
 Synchronization point
 Start of a cycle
 End of a cycle
 Intermediate point at which the clock signal
changes levels
 Timing information
Clock period, ON, and OFF periods


 Propagation delay
 Time required for the output to react to changes in the
inputs
Clock Signal (cont.)
Latches
 Can remember a bit
 Level-sensitive (not edge-sensitive)
A NOR gate implementation of SR latch

Latches (cont.)
 SR latch outputs follow inputs
 In clocked SR latch, outputs respond at specific instances
 Uses a clock signal
Latches (cont.)
 D Latch
 Avoids the SR = 11 state
Flip-Flops
 Edge-sensitive devices
 Changes occur either at positive or negative edges
Positive edge-triggered D flip-flop

Flip-Flops (cont.)
 Notation
 Not strictly followed in the literature
 We follow the following notation for latches and flip-flops
Latches Flip-flops
Low level High level Positive edge Negative

edge
Flip-Flops (cont.)
Example Sequential Circuits (cont.)
74164 shift
Register chip
Memory Design with D Flip Flops
Require separate data in and out lines

Numbers and Boolean Algebra N

Uploaded by

Copyright:

Available Formats

Numbers and Boolean Algebra N

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Numbers and Boolean Algebra N

Uploaded by

Copyright:

Available Formats

Computer Organization

Author: Abhinav Bhatele

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

 Basic boolean operations

June 10th, 2008

Number Systems and Boolean Algebra

(1 x 102) + (6 x 101) + (2 x 100) + (3 x 10-1) + (7 x 10-2) + (5 x 10-3) = 162.375

June 10th, 2008

Number Systems and Boolean Algebra

Powers of 2: Useful abbreviations:

June 10th, 2008

Number Systems and Boolean Algebra

162 / 2 = 81 rem 0 0.375 x 2 = 0.750

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

Hex Binary Hex Binary Hex Binary Hex Binary

 The value of the negative result is represented in the 2’s

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

An expression is A function table is

Number Systems and Boolean Algebra

 We can represent logical functions in two analogous ways too: 23

June 10th, 2008

Number Systems and Boolean Algebra

Expression: xy, or xy x+y x’

Truth table: x y xy x y x+y x x’

June 10th, 2008

Number Systems and Boolean Algebra

f(x,y,z) = (((x +(y’))z) + x’)

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

Operation: AND (product) OR (sum) of NOT (complement)

Expression: xy, or xy x+y x’

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008

Number Systems and Boolean Algebra

Can we make this circuit “better”?

June 10th, 2008

Number Systems and Boolean Algebra

June 10th, 2008