LMC Flashcards
(179 cards)
1
Q
components of LMC
A
- mailboxes: 3 digits –> 100 is max
- counter: 2 buttons- 1 increments and other resets to 00
- calculator: 3 digits: 0-9, +, - buttons, flag for -ve results
- input/output trays: input by user, output sent to user
2
Q
routine in LMC
A
- looks at counter for mailbox number
- increments counter by 1
- goes to mailbox + reads 3 digits
- completes action indicated by digits
- restarts…
3
Q
how do instructions work
A
3 digits: first is opcode (instructions), last digits are operand (mailbox number)
4
Q
opcode 1
A
add: go to specified mailbox, read 3 dig number at address, go to calculator and add number to that on calculator
5
Q
opcode 2
A
subtract: go to specified mailbox, read 3 dig number at address, go to calculator and subtract number from that on calculator
6
Q
opcode 3
A
store: go to calculator, read 3 dig value, go to specified mailbox and store value there (overriding currently stored value)
7
Q
opcode 5
A
load: go to mailbox specified in instruction, read in the 3 dig number, and enter into calculator (overriding current value)
8
Q
opcode 6
A
branch: set program counter to the 2 address specified in instruction, and start fetch of instruction
9
Q
opcode 7
A
branch on zero: check calculator, if value = 0, set program counter to address specified in instruction and start fetch else continue with next instruction as normal
10
Q
opcode 8
A
branch on positive: check calculator, if +ve (inc 0), set program counter to address specified in instruction and start fetch else continue with next instruction as normal
11
Q
instruction 901
A
input: go to IN tray, read 3 dig number there, go to calculator and enter value there. only read one input slip, then remove it, any others are used for future visits
12
Q
instruction 902
A
output: go to calculator, read 3 digit value there and leave slip with value on OUT tray
13
Q
opcode 0
A
break
14
Q
fetch
A
find the instruction to execute: reads program counter, goes to mailbox at that address in instruction, reads 3 dig value
15
Q
execute e.g. store
A
target address remembered. 3 digits in calculator read, 3 digits written in mailbox at target address. program counter incremented
16
Q
von neumann
A
- same memory for instructions and data
- memory is addressed linearly: there is a number for every mailbox
- memory addressed by location: contents is irrelevant
- instructions executed sequentially unless branch or reset
17
Q
harvard
A
-separate memory for instructions and data:
-avoids potential for malware and bugs from self-modifying code
-simpler to read and analyse code
-quicker to execute as can access instructions and data simultaneously
modern processors have split cache so best of harvard and VN
18
Q
five major components of a CPU
A
- memory (RAM)
- registers
- ALU
- control unit
- buses
19
Q
memory (RAM)
A
mailboxes
20
Q
registers
A
special memory locations that can be accessed very fast and are manipulated directly by the CU 1-128 bits: includes program counter (PC), instruction register (IR), accumulator
have a defined purpose and wired to perform that purpose
holds binary values temporarily for storage, manipulation, calculations
21
Q
ALU
A
calculator
22
Q
buses
A
bundles of tiny wires- electrical conductors i.e. lines carrying signals- that carry data between components: address, data, control, power
- -carries data between different points on CPU
- carries data between CPU and main memory/computer peripherals*
23
Q
control unit
A
responsible for directing flow of data and instructions within the CPU- compromised of multiplexor and decoder
24
Q
accumulator
A
register part of the ALU. holds data + interim and final results of calculations + data to be transferred between different memory locations + (I/O+memory)
25
registers int the CU
PC, IR, flags
26
PC
holds the address of the next instruction to be executed
27
IR
holds the instruction currently being executed
28
flags
1 bit memory to keep track of special conditions- grouped together in 1+ status registers
e.g. arithmetic carry, power failure, internal computer error, overflow
29
memory address register
holds address of the memory location to which data is to be written to
only written to
30
memory data register
holds value that is being stored to or retrieved from a memory location addressed by MAR
written to and from
31
types of bus
point to point- carries signal between specific source and specific destination
broadcast- carries signals to many different devices
bus interface bridges- allows communication between buses e.g. peripheral control interface bus, external bus, universal serial bus
32
translate cab.bc (subscript 3)
from units left then from radix right:
1*3^0 + 0* 3^1 + 2* 3^2
+ 1*3^-1 + 2*3^-2
(a = 0, b = 1, c = 2)
33
group of
| 4 bits, 8 bits, 16 bits, 32 bits, 64 bits
```
4 = nibble
8 = byte
16 = half word
32 = word
64 = double word
size of word = CPU dependent, some have 32/64 bit words
```
34
why hexadecimal
- more compact
- easier to read and write than binary
- easy to convert between binary and hex
35
converting dec to binary
```
repeatedly div by 2 until 0 or 2 is reached, the remainder is the binary digit (from radix point left)
e.g. 13(10) to binary:
13 div 2 = 6 rem 1
6 div 2 = 3 rem 0
3 div 2 = 1 rem 1
1 div 2 = 0 rem 1
therefore answer is 1101
```
36
converting dec fraction to binary
```
repeatedly multiply fractional part by 2 until fractional part = 0, if result >= 1 then binary digit = 1. (from radix point right)
e.g. 0.8125(10) to binary:
0.8125 * 2 = 1.625 (1)
0.625 * 2 = 1.25 (1)
0.25 *2 = 0.5 (0)
0.5 * 2 = 1 (1)
therefore = 0.1101(2)
```
37
overflow error
when a computer attempts to handle a value too large for it. triggers the status register, but can cause errors.
38
binary multiplication
- just like long multiplication for decimal numbers
| - efficiently achieved using left shifts and add operations
39
negative representation of numbers
sign and magnitude, ones complement, twos complement, adding a bias
40
sign and magnitude
left most bit is a flag bit, 1 = -ve, 0 = +ve
two representations for 0: 0000 0000, 1000 0000
binary arithmetic is messy
41
ones complement
flip all bits, left most bit is still a flag bit
two representations for 0: 0000 0000, 1111 1111
binary addition is a bit simpler
42
twos complement
flip all bits and add 1, left most bit is still a flag bit
one representation for 0 (1111 1111 = -1)
binary arithmetic is much simpler
43
adding a bias (negative binary representation)
add a bias of ((2^k-1) -1) then store in normal binary.
allows storage of numbers -((2^k-1) -1) --> (2^k-1)
higher order bit does not indicate sign
used for floating point storage
44
negative subtraction
twos complement the second number and add
| overflow is ignored
45
floating point representation
sign bit + exponent + mantissa
46
exponent
a number between -126 and 127, stored with a bias + 127 so number stored is between 0 and 255
47
0 and 255 special meanings
0 exponent + 0 mantissa = 0
0 exponent + non 0 mantissa = subnormal numbers
255 exponent + 0 mantissa = +/- infinity
255 exponent + non 0 mantissa = not a number
48
mantissa
e.g. 1.01.... binary number scaled so that leading 1 preceding radix point, don't store leading 1 (assume its there)
store only the 23 digits of the fractional part
49
e.g. translate 0 sign bit + 124 exponent + 1.25 mantissa
0 = +ve
124 - 127 = -3 exponent
1.25 mantissa
therefore overall = 1.25*2^-3 = 1.25/8 =0.15625
50
translate -12.375 to floating point representation
1100.011 (2)
for leading 1: 1.100011 * 2^3
mantissa: 100011000...
exponent: 3+127 = 130 (10) = 1000 0010
51
floating point issues.
rounding error- cannot represent all numbers e.g. 0.1
| have to limit to certain number of binary digits
52
floating point operations result in...
FP number closest to the answer
53
underflow/overflow level
underflow level = 2^-126 (-126 = smallest number that can be represented by exponent)
overflow level = (2-2^-23) * 2^127 (23 = number of digits of mantissa)
54
ariane 5 issue and how to overcome
overflow error, could not convert 64 bit FP to 16 bit signed integer
overcome by check if number outside range before conversion: if too large then set at a max value
55
transistor
electrically controlled switch: two ports (drain and source) are connected depending on voltage of a 3rd port (gate)
56
nMOS transistor
when g = 0, switch is OFF d is not connected to s
g = 1, switch is ON, d is connected to s
(see image L5)
57
pMOS transistor
when g = 0, switch is ON, s is connected to d
g = 1, switch is OFF, s is not connected to d
(see image L5)
58
most common transistor
MOSFET: metal oxide semiconductor field effect transistor
| element used is silicon
59
most common element used in MOSFET and why
silicon: semiconductor since conductivity changes over many orders of magnitude depending on small changes in levels of dopants
- poor conductor of electricity since all 4 outer electrons involved in bonding
60
dopants
impurities providing extra electrons or electron holes increasing conductivity
61
n-type silicon
overall negative charge, the dopant added is Arsenic, it has an extra electron not involved in bonding which can carry charge
62
p-type silicon
overall positive charge, the dopant added is boron- it is short an electron so leaves a positive electron hole which can move around the lattice
63
diode
at a junction between p-type and n-type silicon, current can only flow from p-type to n-type
64
what happens at a junction of n-type and p-type silicon
electrons in the n-type region and electron holes in the p-type region cancel each other out, creating a 'depletion region'
there are no mobile charge carriers in this region
65
how is binary addition implemented
using gates implementing boolean algebra
66
AND algebraic expression
Y = A . B (dot in centre)
67
OR algebraic expression
Y = A + B
68
NOT algebraic expression
Y = A- (line above A)
69
p-type and n-type junction:
| positive voltage applied to p and negative voltage applied to n
electron holes in p-type attracted towards n-type
electrons in n-type attracted towards p-type
depletion region squeezed out and current flows
70
p-type and n-type junction:
| negative voltage applied to p and positive voltage applied to n
electron holes in p-type repelled by the n-type and electrons in the n-type repelled by the p-type
depletion region expands and creates a barrier to current flow
71
issue at p -type and n-type junction trends
trends break down at sufficient voltage
72
capacitor
two pieces of conductive metal separated by an insulator.
if a positive voltage is applied to one side, it accumulates charge Q, and the other side the opposite charge -Q (not Q)
takes time and energy to charge/discharge a capacitor
73
nMOS transistor, when gate g is at V(DD)
capacitor effect draws electrons to the surface, and they create a temporary channel of n-type silicon, so current can then flow from source to drain
74
how to indicate 1s and 0s
high voltage = 1
low voltage = 0
voltages typically between 0V--> 5V with 0V = 0, 5V = 1, need to be able to tolerate noise though
75
V(DD)
- the high voltage, historically 5V
| - modern chips with smaller transistors have lower max voltages e.g.3.3V to save power and avoid overloading transistors
76
logic levels
defined to allow the mapping of continuous voltage to discrete 0 and 1 of the digital abstraction
77
noise margin high and low calculations
```
NM(H) = V(OH) - V(IH)
NM(L) = V(IL) - V(OL)
```
78
the ideal inverter
the ideal inverter would output V(DD) for inputs up to V(DD)/2 and 0 above this
79
reasonable choice of logic levels
on graph of V(A) vs V(Y), reasonable choice of logic levels are where slope = -1
80
static discipline
design restriction that you only allow circuit elements that all satisfy the same logic levels: means you can successfully apply digital abstraction and combine elements without concern about logic levels or analogue values
81
disadv of static discipline
reduces freedom to include arbitrary elements (but makes design simpler)
82
moores law
transistor density doubles every two years
83
graphical ways of representing boolean algebra
- linear truth table
- rectangular/coordinate table
- venn diagram
84
how many boolean operations on k inputs
2^2^k
85
why is NAND used as a universal gate
easier to make
86
NAND vs NOR, pMOS-wise
in NAND, the two pMOS are parallel and in NOR, the two pMOS are in series so NOR results in delays because of low mobility of holes
87
pMOS vs nMOS speed of operations
nMOS is faster.
| for pMOS to match this- size has to increase = more silicon = more expensive
88
what are digital design principles about
about managing complexity of huge numbers of interacting elements
89
list the digital design principles
- abstraction: hiding irrelevant details
- discipline: restricting design choices to make things easier to model, design+combine
- hierarchy: breaking into modules+submodules
- modularity: well-defined functions+interfaces for modules
- regularity: encouraging uniformity so can reuse+swap modules
90
circuit properties
- 1+ *discrete valued* input terminals
- 1+ *discrete valued* output terminals
- specification of relationship between input+output
- specification of delay between input received and output responding
91
circuit is made up of
elements- circuit with inputs, outputs and specs
| node-wire joining elements whose voltage conveys a discrete valued variable
92
why combinational + sequential logic
-arbitrary circuits lead to short circuits and instability
93
combinational logic rules
- individual gates are combinational circuits
- every circuit element must be a combinational circuit
- every node is either an input to the circuit or connected to exactly one output of a circuit element
- the circuit has no cyclic paths, every path through the circuit visits any node at most once
94
boolean algebra
algebra of 1/0 variables used to specify function of a combinational circuit
used to analyse and simplify circuits required to give a specified truth table
95
literals
AND of several literals are called...
OR of several literals are called...
- variables or their complements
- product/implicant
- sum/implicant
96
minterm
product involving all the inputs to a function
97
maxterm
sum involving all the inputs to a function
98
sum of products
every boolean expression can be written as minterms ORed together
99
product of sums
every boolean expression can be written as maxterms ANDed together
100
truth table to SOP
OR together the products of the literals that result in 1s
101
truth table to POS
AND the 0 values of the function, negating any literals which = 1, so each literal = 0
102
axioms dual
achieved by interchanging 1,0 and AND/OR
103
axiom: binary field
axiom: NOT
B = 1 if B!=0; B=0 if B!= 1;
| not 1 = 0; not 0 = 1
104
AND/NOT
0 . 0 = 0, 1 . 1 = 1
0 + 0 = 0, 1 + 1 = 1
0 + 1 = 1, 0 . 1 = 0
105
identity theorem
| null theorem
B . 1 = B; B + 0 = B;
| B + 1 = 1; B . 0 = 0;
106
idempotency theorem
involution theorem
complements theorem
B+B = B; B . B = B
not not B = B
B + not B = 1; B . not B = 0
107
prove B . 0 = 0
case B = 0:
0 . 0 = 0 (axiom)
case B = 1:
1 . 0 = 0 (axiom)
108
commutativity
associativity
distributivity
- swapping variables around
- moving brackets around
- distribution AND into an OR bracket or two OR brackets amongst each other
109
covering
combining
consensus
de morgans
B . (B + C) = B; B + (B . C ) =B;
(B . C) + (B . notC) = B; (B+C) . (B+ notC) = B
(B + C) . (notB + D) . (C + D) = (B + C) . (notB + D) (+ v.v. with + and . switched)
(already know de morgans)
110
why simplify boolean logic
represent the same thing with much less hardware
111
each cell in a karnaugh map represents...
a minterm
112
prime implicants
implicants that cant be combined with each other
113
7 segment display driver
4 inputs D(3:0), 7 outputs.
the inputs represent a decimal digit 0-9
each output is a segment.
create a circuit for each segment determining whether segment should be lit up based on 4 inputs
unspecified inputs (for numbers>9) can be represented as 1/0 depending on what reduces circuitry
114
difference between sequential and combinational circuit
combinational: output depends on input
sequential: output depends on state and input i.e. history of input
115
e.g. of combinational circuits
adders: adds contents of two registers
multiplexors: uses a binary digit to select an input
decoders: uses a binary digit to activate a single line
116
e.g. of sequential circuits
latches/flip-flops: basic memory element
117
decoder
N inputs, 2^N outputs. only one of the outputs is 1 at a time, the rest are 0. which output is activated depends on the input
118
larger decoders require
multi input AND gates requiring a lot of circuitry. instead can use deeper circuitry = less transistors but slower response time
119
multiplexor
has k selector inputs and 2^k data inputs. the selector represents a binary number, indexing the data to be outputted
120
how can 2:1 multiplexer be built
- using sum of products logic
| - using tristate buffers: tristate enables are arranged so that at all times, exactly one tristate buffer is active
121
how can a 4:1 multiplexer be implemented
-out of smaller 2:1 multiplexers
122
why cant you use a single transistor instead of a tristate buffer
the output of a single transistor isn't driven
123
inverting tristate: purpose of final pair of transistors
control transmission- aiding voltage drain
124
propogation delay
max delay before the output is stable
125
contamination delay
min time before output changes
126
delay is caused by
- resistance and capacitance in a circuit
| - speed of light limitation
127
why may t(pd) and t(cd) be different
- different raising and falling delays
- circuit may have multiple inputs and outputs, some of which are faster than others
- circuits slow down when hot and speed up when cold
128
critical path
longest path in a circuit, determining the propogation delay
129
short path
shortest path in a circuit, determining the contamination delay
130
glitch
output temporarily moving to an incorrect value before stabilising
131
tristate delays
different characteristics for selector and data change with different delays for each
132
gate delays in a full adder
3 gate delays, unless the first set of gates are pre-computed, in which case 2 gate delays once the C(in) comes in
133
ripple adder
computation of the carry bit ripples through the chained adders
134
how many gate delays for a k-bit ripple adder
3 + 2(k-1) = 2k + 1
135
two functions used in a carry look ahead adder
G(A,B) = generate function = A AND B
| P(A, B) = propagation function = A OR B
136
Cout in a carry look ahead adder
C(out) = G(A,B) + P(A,B) . Cin
keep breaking down Cin into G and P functions
e.g. Cout = G4 + P4 . C3
=G4 + P4 . (G3 + P3 . C2) ...etc
137
gate delays for computing Cout in a carry look ahead and overall sum
3 gate delays: one for Pi, Gi, one for AND and one for OR
| for overall sum, 4 gate delays
138
4-bit CLA propagates if..
if all subsequent bits propagate
139
4 bit CLA generates if...
if any bit generates and all subsequent bits propagate
140
CLA adding n-bit numbers in constant gate delay
require order n^2 gates and order n inputs: impractical for large n
141
more efficient CLA
chain 4 bit CLAs: carry ripples 4x faster
142
a block is said to generate a carry if
it produces a carry independent of the carry in
143
a block is said to propagate if
it produces a carry out whenever there is a carry in to the block
144
instead of letting carry ripple through the CLA...
precompute whether a carry would be generated or propagated by each CLA
145
4 bit CLA propagates if...
if all bits propagate, P = p4.p3.p2.p1
146
4 bit CLA generates if...
any bit generates, and all subsequent bits propagate: G= g4 + p4.g3 + p4.p3.g2 + p4.p3.p2.g1
147
each 4 bit block contains
a 4 bit ripple carry adder and some lookahead logic to compute the carry out given the carry in bit
148
gate delay for 16 bit 2-level CLA
1 gate delay for bit level Gs and Ps
2 gate delays for block level Gs and Ps
1 gate delay for sums
2 gate delays for carries
149
time order with 3 level CLA vs normal ripple adder
```
CLA O(logn)
ripple adder O(n) (grows faster, more gates required = more gate delays)
```
150
16 bit adders chained to give a gate delay of...
for an n bit adder: 2(n/16) + 4
151
sequential circuits can be modelled as
finite state machines
152
synchronous sequential circuits are made of
combinational components interleaved with banks of flip flops containing state of the circuit
153
SR: NOR latch
bistable: two stable states for a given input
the S and R inputs are both usually 0. Pulse on S -> output = 1 (or remains 1). Pulse on R -> output = 0 (or remains 0).
output remains even when the pulse is over
154
SR: NAND latch
bistable: two stable states for a given input
the S and R inputs are both usually 1. Pulse on S -> output = 0, Pulse on R -> output = 1
output remains even when the pulse is over
155
D-latch
a latch separating what and when.
CLK: indicates when to change state
D: data input, indicates what the new input should be
when clock = 1, latch is transparent: data flows onto the output
when clock = 0, latch is opaque: output is constant
156
register
bank of flip flops driven by the same clock
157
enabled flip flop
flip flop with an additional input (an enable) controlling whether or not data is loaded into the register
can control input using multiplexor or control the clock = gated clock
158
gated clocks issues
can cause glitches and timing errors
159
number of transistors for a D-type flip flop
NOR/NAND = 4
NOT = 2
AND = NAND + NOT = 6
D-Flip flop = 46 . but by direct design = 20
160
improved D latch
fewer gates = fewer transistors
| Q = CLK . D + notCLK . Qprev
161
issues with the improved D latch
- race conditions: behaviour depends on which of the two routes carries the signal fastest and the gate delays
- logically identical circuits may exhibit different behaviours depending on temperature and technicalities of gate construction
162
problems caused by loops or cyclic paths. how to overcome this?
- inserting registers into the cyclic paths: stores the state of the circuit and breaks the paths. synchronous with the clock, only update on an edge
- if clock is sufficiently slow so all inputs to all the registers have settled, race conditions can't arise
163
synchronous sequential circuits consist of elements such that
- every circuit element is either a register or combinational circuit
- at least one element is a register
- all registers receive the same clock signal
- theres a register in every cyclic path
164
a synchronous sequential circuit has
- a discrete set of states {S0...Sk-1}
- clock input, whose rising edge indicates when a state change occurs
- functional specification detailing next state and all outputs for each possible current state and set of inputs
165
dynamic discipline
restricts us to using circuit components satisfying time constraints allowing us to combine components
166
t(setup)
t(hold)
t(ccq)
t(pcq)
t(setup): time before rising edge during which inputs must be stable
t(hold): time after rising edge during which inputs must be stable
t(ccq): time after rising edge until output starts to change
t(pcq): time after rising edge until output has stabilised
167
how fast a computer operates is dependent on
clock frequency
168
overclocking
setting the clock speed higher than the manufacturer recommends
169
sequencing overhead
t(pcq) + t(setup)
| this is normally fixed, along with the clock speed.
170
clock speed ticks have to be at least...
min cycle time = t(pcq) + t(pd) + t(setup)
t(pd) time between last output stabilising and next input having stabilised
max clock freq = 1/ min cycle time in seconds
171
elements of combinational logic must work within
bounds on t(pd) in order for the circuit to be reliable.
| this is because clock and sequencing overhead is fixed
172
t(hold) min delay requirement
t(ccq) + t(cd) > t(hold)
t(cd) > t(hold) - t(ccq)
t(cd) time between last output starting to change and next input starting to change
to allow direct connections of flip flops: often t(hold) < t(ccq) (no t(cd) if no CL element)
173
hold time violations
find short path: if t(hold) > t(ccq) + t(cd) then input to flip flop may change before D value has reliably set its value to previous value
174
fixing time hold violations
add buffers, so add another t(cd) until total(t(cd)) + t(ccq) > t(hold)
175
metastable states: input D to a flip flop
If D is either 1/0 while the clock rises = stable state
if D changes state while clock is rising (between tsetup and thold) = metastable state = driven to 1/0 eventually but takes longer for state to stabilise
176
synchronisers
two flip flops can synchronise the input with the clock- if input to a register is not synchronised with the clock the output may be indeterminate
177
output of second register will be synchronised if..
resolution time of first register (time taken for output to stabilise) is small enough compared to clock rate
178
pipelining
improves throughput at the expense of latency
inserting more registers into a circuit, decreasing clock cycle time/increasing clock frequency/increasing throughput
but not necessarily splits clock cycle time in half, as added sequence overhead and circuit can't be divided exactly into two halves
179
latency
number of clock cycles/overall time
