Logical Devices
We are here
Assembly Language Processors
Copyright By PowCoder代写 加微信 powcoder
Arithmetic Logic Units
Devices Circuits
Finite State Machines
Flip-flops
Gates Transistors
Building up from gates…
Somecommonandmorecomplexstructures:
Multiplexers(akamux)
Decoders
Seven-segment decoders
Adders(halfandfull) Subtractors
Comparators
These are all
combinational circuits
Combinational Circuits
CombinationalCircuitsareanycircuitswhere the outputs rely strictly on the inputs.
Everything we’ve done so far and what we’ll do today is all combinational logic.
Anothercategoryissequentialcircuitsthatwe will learn in the next few weeks.
More Karnaugh Maps
Karnaugh map review
K-mapsprovideanillustrationofacircuit’s minterms (or maxterms), and a guide to how neighbouring terms may be combined.
Y = A·B·C + A·B·C + A·B·C + A·B·C
Karnaugh map review
K-mapsprovideanillustrationofacircuit’s minterms (or maxterms), and a guide to how neighbouring terms may be combined.
Y = A·B·C + A·B·C + A·B·C + A·B·C
= B·C + A·C
Reminder on Reducing Circuits
EliminatingvariablesinK-Mapsbydrawing larger (>1 element) rectangular groupings
results in a circuit with a lower cost function. Theresultingexpressionisstillinsum-of-
products form.
But,ifsimplified,itisnolongerinsum-of-minterms
Note:Itisnotonlythenumberofgatesthat matters when reducing circuits, but also the number of inputs to each gate.
K-Maps – Different Notations A 3-variables map example
Important!
BC Using either notation is fine! 00 01 11 10
Y = B·C + A·C
Important!
_ _ _ _ BC BC BC BC
Helpful Hint
ABC00 01 11 10 0
More Examples w/ K-Maps
ABC00 01 11 10 0
ABC00 01 11 10 0
A BC 00 11
A BC 00 00
More Examples w/ K-Maps
ABC00 01 11 10 0
ABC00 01 11 10 0
A BC 00 11
A BC 00 00
Karnaugh map example
Createacircuitwith four inputs (A, B, C , D), and two outputs (X, Y):
The output X is high whenever two or more of the inputs are high.
The output Y is high when three or more of the inputs are high.
Karnaugh map example
Createacircuitwith four inputs (A, B, C , D), and two outputs (X, Y):
The output X is high whenever two or more of the inputs are high.
The output Y is high when three or more of the inputs are high.
Karnaugh map example
X = A·B + C·D + B·D + B·C + A·D + A·C
Karnaugh map example
X = A·B + C·D + B·D + B·C + A·D + A·C
Karnaugh map example
Y = A·B·D + B·C·D + A·B·C + A·C·D
Alternative for X: Maxterms X:
X = (A+C+D)·(B+C+D)·(A+B+C)·(A+B+D)
Alternative for X: Maxterms X:
X = (A+C+D)·(B+C+D)·(A+B+C)·(A+B+D)
Karnaugh map review
Note:Therearecaseswherenocombinations are possible. K-maps cannot help in these cases.
Example:Multi-inputXORgates.
Outputis1iffoddnumberofinputsis1.
Y = A·B·C + A·B·C + A·B·C + A·B·C
Multiplexers
Logic devices
Certainstructuresarecommontomany circuits, and have block elements of their own.
e.g.,Multiplexers(shortform:mux)
Behaviour:OutputisXifSis0,andYifSis1:
n specifies the number of bits.
S is the select input; X and Y are the data inputs. S
n Xn0S X0nM n
2-to-1 mux
Multiplexer design
M = Y·S + X·S
Multiplexer uses
Muxesareveryusefulwheneveryouneedto select from multiple input values.
Example:surveillance video monitors, digital cable boxes, routers.
Demultiplexers
Relatedtodecoders:demultiplexers.
Doesmultiplexeroperation,inreverse.
Example:modemsreceivingInternetdata.
n0Xn0nW MnM1nX
Mux + Demux
Source: https://upload.wikimedia.org/wikipedia/commons/e/e0/Telephony_multiplexer_ system.gif
Decodersareessentiallytranslators.
Translatefromtheoutputofonecircuittothe
input of another.
Thinkofthemasprovidingamappingbetween2 different encodings!
Example:Binarysignalsplitter
Activatesoneoffour
output lines, based on
a two-digit binary number.
7-segment decoder
Commonandusefuldecoderapplication. Translatefromabinarynumbertotheseven
segments of a digital display.
Eachoutputsegmenthasaparticular logic that defines it.
Example: Decimal number, segment 0 4
Activate for values: 0, 2, 3, 5, 6, 7, 8, 9.
In binary: 0000, 0010, 0011, 0101, 0110, 0111, 1000,
Firststep:BuildthetruthtableandK-map.
Segment0(topsegment)ishighwheneverthe input values are 0000, 0010, 0011, 0101, 0110, 0111, 1000 or 1001, and low whenever input number is 0001 or 0100.
Thiscreateatruthtableandmaplikethe following….
7-segment decoder
Thesesegmentsare“active-high”, meaning that setting it high turns it on.
Example: To display the digits 0-9
Assumeinputisa4-digitbinarynumber
7-segment decoder
HEX0 = X3·X2·X0 + X3·X2·X1 + X3·X2·X0 + X3·X1
Butwait…what about input values 1010 to 1111?
“Don’t care” values
Inputvaluesthatwillneverhappenorarenot meaningful in a given design, and so their output values do not have to be defined.
Recorded as ‘X’ in truth-tables and K-Maps.
IntheK-mapswecanthinkofthese“don’tcare”
values as either 0 or 1 depending on what helps us simplify our circuit.
Note: you do NOT replace X values with all 0s or 1s, you just include each X in groupings as needed.
“Don’t care” values
NewequationforHEX0:
HEX0 = X1 + X2·X0 +
Same number of terms, but fewer inputs = smaller gates
Again for segment 1
HEX1 = X1·X0 + X1·X0 + X2
Again for segment 2
HEX2=X2 + X1 + X0
The final 7-seg decoder
Decodersalllookthe same, except for the inputs and outputs.
Unlikeotherdevices, the implementation differs from decoder to decoder.
7-seg decoder
Another “don’t care” example
Climatecontrolfan:
(not related to decoders)
Thefanshouldturnon(F)ifthetemperatureis hot (H) or if the temperature is cold (C), depending on whether the unit is set to A/C or heating (A).
F = A·H + A·C
0 0 1 0 0 1 X X
Adder circuits
Alsoknownasbinaryadders.
Smallcircuitdevicesthataddtwodigitstogether.
Combinedtogethertocreateiterative combinational circuits.
Typesofadders: Halfadders(HA)
Fulladders(FA)
RippleCarryAdder
Review of Binary Math
Eachdigitofadecimalnumberrepresentsa power of 10:
258 = 2×102 + 5×101 + 8×100
Eachdigitofabinarynumberrepresentsa
power of 2:
011012 = 0x24 + 1×23 + 1×22 + 0x21 + 1×20 = 1310
Decimal to Binary Conversion
Let’ssayIgiveyounumber11indecimal. How would you represent this in binary?
Keepdividingby2andwritedownthe remainders!
Use the quotient from previous row.
11 in decimal is 1011 in binary!
Quotient = Number / 2
Remainder = Number % 2
Least Significant Bit
Most Significant Bit
Decimal to Binary Conversion
Let’ssayIgiveyounumber11indecimal. How would you represent this in binary?
Keepdividingby2andwritedownthe remainders!
Use the quotient from previous row.
11 in decimal is 1011 in binary!
Quotient = Number / 2
Remainder = Number % 2
Least Significant Bit
Most Significant Bit
Hexadecimal Numbers
Base16numbers,wherevalidvaluesare:
0 to 9 as in decimal, and
Hex numbers are typically expressed as 0x____
Writingabinarynumberinhex(-adecimal):
0000010111111010 = 0000 0101 1111 1010 = 0x05fa
Unsigned binary addition
27 = 00011011
53 = 00110101 111111
Unsigned binary addition
27 = 00011011
95+181 01011111
53 = 00110101 111111
With 8 bits we can only represent unsigned numbers 0 to255!
Half Adders
A2-input,1-bitwidthbinaryadderthatperforms the following computations:
X0011 +Y +0 +1 +0 +1
CS 00 01 01 10
A half adder adds two bits to produce a two-bit sum.
Thesumisexpressedasa sumbit SandacarrybitC.
Half Adder Implementation
Equationsandcircuitsforhalfadderunitsare easy to define (even without Karnaugh maps)
C = X·Y XY
X·Y + X·Y = XY
Half Adder Implementation
Equationsandcircuitsforhalfadderunitsare easy to define (even without Karnaugh maps)
C = X·Y XY
S = X·Y + X·Y = XY
Full Adders
Similartohalf-adders,but with another input Z, which
represents a carry-in bit.
CandZaresometimeslabeledasCoutandCin.
WhenZis0,theunitbehavesexactlylikea half adder.
WhenZis1:
+Y +0 +1 +0 +1
+Z +1 +1 +1 +1
CS 01 10 10 11
Full Adder Design
C = X·Y + X·Z + Y·Z S = X Y Z
Full Adder Design
TheCtermcanalsobe rewritten as:
C = X·Y + (X Y)·Z
Twotermscomefromthis: X·Y=carrygenerate(G).
XY=carrypropagate(P).
Resultsinthiscircuit
Adder Cin 4
X3Y3 X2Y2 X1Y1 X0Y0
Cout FA C3 FA C2 FA C1 FA Cin
Ripple-Carry Binary Adder
Fulladderunitsarechainedtogetherinorder to perform operations on signal vectors.
The role of Cin
Whycan’twejusthaveahalf-adderforthe smallest (right-most) bit?
Wecould,ifwewereonlyinterestedin addition. But the last bit allows us to do subtraction as well!
Timeforalittlefunwithsubtraction!
What is 11111111?
Assumeyouhavean8-bitbinarynumber.
Howdoyourepresentnegativenumbers? Forinstance,thenumber-1?
Add1to11111111andseewhathappens. 11111111
100000000 00000000
Therefore,11111111mustbe-1!
Subtractors
Subtractorsareanextensionofadders.
Basically,performadditiononanegativenumber.
Beforewecandosubtraction,needto understand negative binary numbers.
Twotypesofnumbers:
Unsigned=allnumbersarepositive.
Still use signed representation to perform subtraction
Signed=allbitsareusedtostorea2’scomplement negative number.
More common, and what we use for this course.
Two’s complement
Firststep:getting1’scomplement:
Given number X with n bits, take (2n-1)-X
Negates each individual bit (bitwise NOT).
01001101 10110010 11111111 00000000
2’scomplement=(1’scomplement+1)
Note:Addinga2’scomplementnumbertothe original number produces a result of zero.
01001101 10110011 11111111 00000001
Signed subtraction
Negativenumbersaregenerallystoredin2’s complement notation.
Reminder:1’scomplementbitsarethebitwise NOT of the equivalent positive value.
2’scomplementonemorethan1’scomplement value; results in zero when added to equivalent positive value.
Subtraction can then be performed by using the binary adder circuit with negative numbers.
Signed 3-Digit Numbers
Rules about signed numbers
When thinking of signed binary numbers, there are a few useful rules to remember:
The largest positive binary number is a zero followed by all ones.
The binary value for -1 has ones in all the digits.
The most negative binary number is a one followed by all zeroes.
There are 2n possible values that can be stored in an n-digit binary number.
2n-1 are negative, 2n-1-1 are positive, and one is zero.
For example, given an 8-bit binary number:
Thereare256possiblevalues
Oneofthosevaluesiszero
128arenegativevalues(11111111to10000000) 127arepositivevalues(00000001to01111111)
-1 to -128
Practicing 2’s complement
Assume4-bitsignednumbers,writethe following decimal numbers in binary:
2 => 0010
-1 0 8
Whatismaxpositivenumber? Whatisminnegativenumber?
=> Notpossibletorepresentin4digits! => 1000
=> 7 (or 24-1 -1) => -8 (or -24-1)
At the core of subtraction
Subtractionofanumberissimplythe addition of its negative value.
Where the negative value is found using the 2’s complement process.
7–3 = 7+(-3) -3–2 = -3+(-2)
Signed Subtraction example
7 – 3 0111
0100 = 410
-3 – 2 1101
1011 = -510
What about bigger numbers?
53 – 27 00110101
00110101 discarded +11100101 00011010
00011010 = 2610
27 – 53 00011011
11100110 = -2610
Subtraction circuit
4-bitsubtractor:X–Y
Xplus2’scomplementofY
Xplus1’scomplementofYplus1
Use NOT gates to get the 1’s complement of Y.
Y3 Y2 Y1 X3 X2 X1
FA C3 FA C2 FA C1 S3 S2 S1
Feed 1 as carry-in in the least significant adder.
Addition/Subtraction circuit
Y3 Y2 Y1 X3 X2 X1
FA C3 FA C2 FA C1 S3 S2 S1
If Sub is 0 => addition.
If Sub is 1 => subtraction.
The full adder circuit can be expanded to incorporate the subtraction operation.
Remember: 2’s complement = 1’s complement + 1 WeneedSubtoprovidethevalueforCin
Food for Thought
Whathappensifweaddthesetwopositivesigned binary numbers 0110 + 0011 (i.e., 6 + 3) ?
The result is 1001.
But that is a negative number (-7)!
Whathappensifweaddthetwonegativenumbers 1000 + 1111 (i.e., -8 + (-1))?
The result is 0111 with a carry-out.
Weneedtoknowwhentheresultmightbewrong.
This is usually indicated in hardware by the Overflow flag!
More about this when we’ll talk about processors.
Sign & Magnitude Representation
Instead of signed numbers, some (older) processors use sign and magnitude representation.
The sign part: one bit is designated as the sign (+/-). 0forpositivenumbers
1fornegativenumbers
The magnitude part: remaining bits store the positive (i.e., unsigned) version of the number.
Example: 4-bit binary numbers:
0110 is 6 while 1110 is -6 (most significant bit is the sign)
What about 0000 and 1000? => zero (two ways)
Sign-magnitude computation is more complicated.
2’s complement is what today’s systems use!
Acircuitthattakesin two input vectors, and determines if the first is greater than, less than or equal to the second.
Howdoesonemake that in a circuit?
Basic Comparators
B,whereAandBareonebitlong.
Thecircuitsforthiswouldbe:
A=B Comparator A>B AB:
A·B + A·B A·B
Basic Comparators
WhatifAandBaretwobitslong?
Thetermsforthiscircuitforhaveto
expand to reflect the second signal. Forexample:
AA BB 10 10
Comparator
Make sure that the values Make sure that the values of bit 1 are the same of bit 0 are the same
A==B: (A1·B1+A1·B1)·(A0·B0+A0·B0)
Basic Comparators
WhataboutcheckingifAisgreater or less than B?
A>B: Check if first bit
satisfies condition A
Thefirstnon-matchingbitsoccuratbiti,where
Ai=1 and Bi=0. All higher bits match. UsingthedefinitionforXifrombefore:
Case#3: A < B
Thefirstnon-matchingbitsoccuratbiti,where Ai=0 and Bi=1. Again, all higher bits match.
A>B = An·Bn + Xn·An-1·Bn-1 + … + A0·B0·Π Xk k=1
ACS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com