1007ICT / 1807ICT / 7611ICT Computer Systems & Networks
3C. Digital Logic and Digital Circuits
Dr. Sven Venema Dr. Vallipuram Muthukkumarasamy
Last Lecture:
Topics Covered:
• Logic unit, Selection logic, Decoder logic
• Multiplexing and Demultiplexing
• Half and Full adders
Lecture Content
Learningobjectives
Arithmeticlogicunit
Binarymultiplicationanddivision
Shifting
SequentialLogic
Datalatches,S-RLatch
Clocksandsynchronisation
Registers,Buses,Computermemory
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 3
Learning Objectives
At the end of this lecture you will have gained an understanding of:
Arithmetic logic unit
Binary multiplication and division
Shifting
Sequential Logic
Data latches, S-R Latch
Clocks and synchronisation
Registers, Buses, Computer memory
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 4
ALU – Arithmetic Logic Unit (Section 7.2)
The ALU is a general processing element
It puts everything we have learnt together
ALUs are combined in parallel for multi-bit versions
AB
AND
OR
XOR
Select Cin Cout
1 bit ALU
Select
Cout
A2 B2 A1
ALU ALU
B1 A0 B0
ALU
Cin
Full Adder
Output
3 bit ALU
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 5
Output
Multiplication and Division By 2
To multiply by 2 in binary, shift bits left and insert a zero at the right hand side.
Carry out
0
To divide by 2 in binary, shift bits right and insert a zero at the left hand side.
0 Carry out
(ignored)
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 6
00012 = 110 00102 = 210 01002 = 410
01112 = 710 00112 = 310 00012 = 110
Shifters
Wecanusemultiplexorstoshiftbitsleftandright.
Weneedtoselecteachoutputbittobetheinputbit
on its left or right side
Inputs
D4
D3
D2
D1
D0
Shift Left
Outputs
X3
X3
X2
X1
X0
Inputs
D4
D3
D2
D1
D0
Shift Right
Outputs
X3
X3
X2
X1
X0
Sign or 0 Left / Right
4 bit shifter
D3 D2 D1 D0
0
X3 X2 X1 X0
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 7
Shifters
What if we also want the shifter to not shift or to set the output to zero? Use a 4-input multiplexor
D3 D2 D1 D0
SEL
Out
00
Zero
01
Right
10
Left
11
Thru
TLRZ TLRZ TLRZ TLRZ
Sign or 0 SEL
0
X3 X2 X1 X0
Page 8
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Arbitrary Multiplication
TomultiplybyothernumberssayA*B–wecouldaddAto itself B times, but it’s faster to use shifts and adds like this…
The powers of 2 you need to add to get the multiplicand determines the number combination of shifts and addition we need to perform on the multiplier (ie the 1s in its binary value)
Let << denote the binary left shift operator:
10x5=(10x4)+(10x1)=1100102
Mult.
Shifts
Binary
Hex
10 x 4 10 x 1
1010 << 2 1010 << 0
101000
001010
28 0A
5 = 1012
= 1002 + 12 =4+1
10x7=(10x4)+(10x2)+(10x1)=10001102
Mult.
Shifts
Binary
Hex
10 x 4 10 x 2 10 x 1
1010 << 2 1010 << 1 1010 << 0
101000
010100
001010
28 14 0A
7 = 1112
=1002 +102 +12 =4+2+1
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 9
Multiplication Example
Multiply SumA x B
Check every bit position of B so that if:
bitposition0ofBis1,addAtothesum.
bitposition1ofBis1,addA<<1tothesum. bitposition2ofBis1,addA<<2tothesum. bitposition3ofBis1,addA<<3tothesum. etc..
10 × 13 = 130 10102 x 11012
Note: 10102 << 1 is not added as bit position 1 of 11012 is 0.
10102 <<0 10102 <<2 10102 <<3
10102 1010002 + 10100002 +
100000102 = 130 © Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 10
Arbitrary Division
Forarbitrarydivisionwecanusebasicbinarylong division.
84 21 2 1
13 / 3 = 1 1 0 1 / 1 1 = 4 Remainder 1
1 0 0 Answer: 4 1 1 1 1 01
-1 1
0 0 1 Remainder: 1
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 11
Sequential Logic (Section 2.5)
Previously we looked at
which produces an output as some combination of the input values.
Sequential logic produces an output that depends not only on the inputs but on previous inputs as well.
combinatorial logic
Input
Output
Logic Function
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 12
Feedback
Memory Cell
Data Latches
Noneofthelogicfunctionswesawbeforecanstore any data... bits come in and go straight out again.
A
Considerthefollowinglogic:
Latch is a logic function that can store bits
in
Thiscanstorea‘1’bitbutnota‘0’bit.Weneed another input to tell it to store a ‘0’bit, like this.
Q
OR
set reset
OR
Q
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 13
S-R Latch (RS-Bistable)
Let’srearrangethelogicabitasfollowsusingthe rules of logic (using DeMorgan’s Theorem) :
SQSQ RR
TheresultiscalledtheSR-latch(orRS-Bistable) BothinputsarenormallyOFF(at0)
TheSinputsetsthedatastateto1 TheRinputsetsthedatastateto0 HavingbothtoONatonceisillegal
WhenbothareOFFthelatchisstable EitherQ=0andQ=1
Or Q=1andQ=0
S
Q
R Q
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 14
Clocks and Synchronisation
Themainproblemwithlatchesisthataftertheinputs change the output is unstable for a short time.
Ifwedirectlyconnecttheoutputofalatchtotheinput of another circuit then the circuit may be unstable
Aclocksignalcancontrolwhenalatchcanloadits inputs after they are stable (ie when the clock is high)
Q
Q
10 S Clk
10
10 R
Clockedlatchesaresometimescalled
Thefastertheclock–thefasterthatdatacanbe
stored/read into a latch
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 15
Flip
Flops;
-
Data Latch (Level-Triggered D-Type bistable)
WecanuseDeMorgan’sTheoremagaintoconvertthe Latch to use NAND gates that is set using OFF inputs.
BothinputsarenormallyON
SettingStoOFFsetsthedatastateto1 SettingRtoOFFsetsthedatastateto0 HavingbothtoOFFatonceisillegal
S R
-
Q
Q
Q Q
WhenbothareONthelatchis
Asimplemodificationoftheclockedversionletsus
stable
create the useful
D
D
FlipFlop
Latch or D
Clk
-
Symbol
DQ
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 16
Bits / Bytes / Words
Ifcomputermemorywasonlyaddressedonebitata time, it would take quite a long time to retrieve enough data to any serious processing.
Mostcomputersdonotprocessindividualbitsbut instead group them together into multiples of 8 eg 8, 16, 32, 64 etc.
Thesegroupsaredescribedas
length varies depending on the machine.
An8bitwordiscalleda
words, but word
Byte.
Nibble so 1 byte = 2 nibbles
A4bitwordiscalleda
Therearenospecialnamesforothersizedwords.
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 17
Registers
Data Latches (Level-Triggered D-Type bistables) allow us to store 1 bit of information but we can group them in parallel
This is called a of multiple bits.
register to store data consisting wordsize is the number of bits a register
The
can store
Clk
D3 D2 D1 D0
Q3 Q2 Q1 Q0
Simple 4 bit register using D-Latches
D Q
D Q
D Q
D Q
7
6
5
4
3
2
1
0
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 18
8 bit register
Buses
Wecanconnectlogicgatestogetherwithlinesthat convey single bits of information between them.
Withregisterswehavemultipleinputandoutput lines to convey N-bits of data to and from the register
Abusisasetoflinesthatsimultaneouslyconveysa set of bits between components.
Twotypesofbusesarecommonincomputer systems: point-to-point, and multipoint buses.
Register A
Point to Point Bus
Shared Bus (Multipoint)
Register B
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 19
Reg A
ALU
Reg B
Multipoint Buses use special gates with “tristate” outputs that can be connected together
Computer Memory (Section 3.3)
Wecanuseanarrayofregistersinseriestocreate a memory bank.
Everyregisterlocationinthememorybankisgiven a unique address that is used so that we can select it and access the data stored in it.
An8bitmachinewoulduseabankof8bitregisters and access 8 bit words from memory at a time.
Location Bit
43
7
0
6
5
0
0
2
0
0
1
1
0
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
005
Fetching word at address 003 004
would return the value 011001002 = 6416 = 10010
003 002 001
000
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 20
Computer Memory
A memory bank needs some way of selecting memory addresses
A special register called a memory address register (
is internal to the CPU contains the physical location of the next memory address that will be selected for reading/writing.
Another internal register called the Memory Buffer Register (
MAR) which
MBR) MDR)] holds the value that was read
[or Memory Data Register (
/written to the selected memory address.
Location Bit
7
0
6
5
0
0
2
0
0
1
1
0
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
Read/Write control
005
004
003
002
001
000
43
0
0
1
1
0
1
1
0
0
1
0
0
MAR
MBR (MDR)
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 21
Summary
Have considered:
Arithmetic logic unit
Binary multiplication and division
Shifting
Sequential Logic
Data latches, S-R Latch
Clocks and synchronisation
Registers, Buses, Computer memory
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 22
Next....
Processors
© Ruben Gonzalez. Revised and updated by Sven Venema, Vallipuram Muthukkumarasamy, and Wee Lum Tan
Page 23