false

Study Guides
(248,518)

Canada
(121,606)

University of Toronto St. George
(8,305)

Computer Science
(187)

CSC258H1
(8)

Steve Engels
(5)

Unlock Document

Computer Science

CSC258H1

Steve Engels

Winter

Description

LOGIC DEVICES o Half Adders
Building up from gates A 2-input, 1-bit width binary adder that performs the following
computations:
o Some common and more complex structures
Multiplexers (MUX)
Adders (half and full)
Subtractors
Comparators
Decoders A half adder adds two bits to produce a two-bit sum
Seven-segment decoders The sum is expressed as a sum bit S and a carry bit C
o Certain structures are common to many circuits, and have block Half Adder Implementation
elements of their own
Equations and circuits for half adder units are easy to
Karnaught map review – moved to jan18ce define (even w/o k-maps)
Multiplexers (MUX) C = X ∙ Y S = X ∙ Y + X ∙ Y = X⨁Y
o Behavior:
output is X if S = 0; otherwise output is Y if S = 1
o Full Adders
Similar to half-adders, but with another input Z, which
represents a carry-in bit
o Multiplexer design
X Y S M M Y ∙ S Y ∙ S Y ∙ S Y ∙ S C and Z are sometimes labels asoutand Cin
When Z is 0, the unit behaves exactly like a half adder
0 0 0 0 X 0 0 1 0 When Z is 1, the full adder performs the following computations
0 0 1 0 X 1 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1 M = Y ∙ S + X ∙ S
1 0 1 0
1 1 0 1
1 1 1 1
Full Adder Design
X Y S C S C Y ∙ Z Y ∙ Z Y ∙ Z Y ∙ Z
0 0 0 0 0 X 0 0 1 0
0 0 1 0 1 X 0 1 1 1
0 1 0 0 1
0 1 1 1 0 S Y ∙ Z
Adders Y ∙ Z Y ∙ Z Y ∙ Z
o Also known as binary adders 1 0 0 0 1 X 0 1 0 1
1 0 1 1 0 X 1 0 1 0
Small circuits devices that add two digits together 1 1 0 1 0
Combind together to create interative combinational circuits
o Types of adders 1 1 1 1 1
Half Adders (HA)
C = X ∙ Y + X ∙ Z + Y ∙ Z
Like an OXR for sum (s) and AND for carry (c) = X ∙ Y + X⨁Y ∙ Z
Full Adders (FA) S = X⨁Y⨁Z
Ripple Carry Adder
Carry-Look-Ahead Adder (CLA) Then let carry generate G = X ∙ Y
o Binary Math review And let carry propagate P = X⨁Y
Each digit of a demical number represents a power of 10: Resultant circuit
258 = 2*10 + 5*10 x+ 8*10 0
Each digit of a binary number represents a power of 2: o Ripple-Carry Binary Adder
01101 2 0*24 + 1*23 + 1*22 + 0*21 + 1*20
Full adder units chained together in order to perform operations
= 13 10 on singal vectors
Binary Addition example
27 + 53 95 + 181
27 = 00011011 95 = 01011111
53 = 00110101 181 = 10110101
o The role of in
Why can’t we judt have a half-adder for the smallest (right-
most) bit?
We could, if we were only interested in addition. But the last bit
allows use to do subtraction as well. Subtractors Ex. an 8-bit binary number, there at 256 possible
o Subtractors are an extension of adders values that can be stored. One of them is 0, there are
Basically, perform addition on a negative number
128 negative values (11111111 to 10000000) and
o Negative binary numbers, 2 versions 127 positive values (00000001 to 01111111)
Unsigned = a separate bit exists for the sign o Subtraction circuit
Data bits store the positive version of the number
Signed = all bits used to store a Two’s Complement negative #
o Two’s Complement
First obtain One’s Complement
n
Given number X with n bits, take (2 -1)-X
Result: negates each individual bit (a bitwise NOT op.)
Two’s Complement = (1’s Complement + 1)
Note: adding a 2’s complement number to the original
number produces a result of zero Note: Sub(XOR)Y inverts Y if Sub is high, else Y unchanged
Sub Y Result
0 0 0
0 1 1
1 0 1
o Unsigned Subtraction 1 1 0
1. Get the Two’s Complement of the subtrahend
Comparators
(term being subtracted, i.e. usually the smaller value) o A circuit that takes in two input vectors and determines if the first is
2. Added that value to the minuend
greater than, less than or equal to the second
(term being subtracted from, i.e. usually the larger value) o Basic comparators
3a. If there is an end carry (out is high), the final result is Consider two binary numbers A and B, both are 1-bit long.
positive and does not change The circuits for this would be:
3b. If there is no end carry (Coutis low), get the 2’s complement
A == B: A ∙ B + A ∙ B
of the result and add a negative sign to it (or set the sign bit A > B: A ∙ B
high)
A < B: A ∙ B
Ex. 53 – 27 27 - 53 What if A and B are two bits long? The terms for this circuit for
have to expand to reflect the second signal.
A == B, need to check the values of both bit-1 and
bit-0 are the same.
(A 1 B 1 A ∙ 1 ) 1 (A ∙ 0 + A0∙ B 0 0
A > B:
A 1 B 1 (A ∙ 1 + 1 ∙ B 1 ∙ 1A ∙ B 0 0
A < B:
A 1 B 1 (A ∙ 1 + 1 ∙ B 1 ∙ 1A ∙ B 0 0
Note in A > B and A < B the first term check if bit-1
o Signed Subtraction satisfies condition, if not the second term check that the
Negative numbers are generally stored in Two’s Complement first bits are equal and then do the bit-0 comparison
notation Also note the sections in common between the three
Reminder: One’s Complement bits are the bitwise NOT
comparators
of the equivalent positive value o General Comparators
Two’s Complement one more than One’s Complement The general circuit for comparators requires you to define

More
Less
Related notes for CSC258H1

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.