the basics of logic design Flashcards
the basics of logic design
1
Q
electronics inside a modern computer are ___________
A
digital
2
Q
digital electronics
A
operate with only two voltage levels of interest: high and low
3
Q
signals are logically either:
A
asserted: true or 1
deasserted: false or 0
4
Q
values 0 and 1 are
A
complements/inverses
5
Q
combinational logic blocks
A
don’t contain memory
output: depends on the current input
6
Q
logic blocks with memory
A
output: can depend on both the input and the state
7
Q
state of the logic block
A
value stored in memory
8
Q
logic block with n entries will have a truth table with ___ entries
A
2^n
9
Q
OR operator
A
logical sum
A + B
10
Q
AND operator
A
logical product
A · B
11
Q
unary operator NOT
A
Ā
12
Q
identity law
A
A + 0 = A and A · 1 = A
13
Q
zero and one laws
A
A + 1 = 1 and A · 0 = 0
14
Q
inverse laws
A
A + Ā = 1 and A · Ā = 0
15
Q
commutative laws
A
A + B = B + A and A · B = B · A
16
Q
associative laws
A
A + (B + C) = (A + B) + C and A · (B · C) = (A · B) · C
17
Q
distributive laws
A
A · (B + C) = (A · B) + (A · C) and A + (B · C) = (A + B) · (A + C)
18
Q
DeMorgan’s laws
A
(i) (A ∪ B)’ = A’ ∩ B’
(ii) (A ∩ B)’ = A’ ∪ B’
19
Q
gates
A
implement basic logic functions
20
Q
all logic functions can be constructed with only a single gate type, if that
gate is inverting
A
21
Q
NOR and NAND gates
A
inverting gates
22
Q
decoders
A
type of logic blocks used in building larger components
23
Q
most common type of decoder
A
has an n-bit input and 2^n outputs, where only one output is asserted for each input combination
24
Q
encoder
A
preforms the inverse function of a decoder
25
multiplexor
basic logic function
also called selectors because the output is one of the inputs selected by a control
26
multiplexor has __ inputs and they are:
3
two data values + selector
27
selector value
or control value
determines which of the inputs becomes the output
28
a multiplexor with n inputs will need ________ selector inputs
log...?
29
multiplexor consists of __ parts which are:
3
a decoder that generates n signals
an array of n AND gates
a single large OR gate
30
In a multiplexor, what is the purpose of the array of gates?
each gate combines one of the inputs with a signal from the decoder
31
In a multiplexor, what is the purpose of the OR gate?
incorporates the outputs of the AND gates
32
canonical form
every input is either true or a complemented variable, and there are only two levels of gates-AND and OR- with a possible inversion of the final output
33
two-level representation
logic function written in canonical form
34
types of two-level representation
sum of products: logical sum of products (terms using the AND operator)
product of sums: the opposite
35
only those truth table entries for which the function is true generate terms in the equation
36
we can use the relationship between a ___________ and a _____________
to generate a gate-level implementation of any set of logic functions
truth table
two-level representation
37
in a logic table each column represents a different ____________
logic function
38
programmable logic array (PLA)
a structured logic element composed of a set of inputs and corresponding input complements and two stages of logics
39
stages of logic in PLAs
1. generates product terms of the inputs and input complements -> an array of AND gates that form a set of minterms
2. generates sum terms of the product terms -> an array of OR gates, each of which forms a logical sum of any number of the product terms
40
minterms
a set of logic inputs joined by conjunction; the product terms from the first logic stage of the PLA; each product term can consist of any of the inputs or their complements
41
AND plane
size of the AND gate array
42
OR plane
size of the OR gate array
43
a row in the PLA corresponds to _______
each entry where the output is true, because it requires a product term
44
each output =
a potential row of OR gates in the second stage
45
the number of OR gates =
the number of truth table entries for which the output is true
46
the total size of a PLA =
AND plane + OR plane
47
PLA characteristics that make it an efficient way to implement a set of logic functions
1. only the truth table entries that produce a true value for at least one output have any logic gates associated with them
2. each different product term will have only one entry in the PLA, even if the product term is used in multiple outputs
48
PALs
PLA-like structures that can be programmed when needed
49
ROM
read-only memory
a memory whose contents are designated at creation time, after which contents can only be read
50
How is ROM used?
as structured logic to implement a set of logic functions by using the terms in the logic functions as address inputs and the outputs as bits in each word of the memory
51
Why is ROM called a memory?
it has a set of locations that can be read
52
PROM
programmable ROM
it can be programmed when a designer knows its contents
53
erasable PROMs
require a slow erasure process using UV light, and thus are used as read-only memories, except during the design and debugging process
54
ROM height
number of addressable entries
2^m -> m input lines
55
ROM width
the number of bits in each addressable entry = number of output bits
56
the total number of bits in ROM=
height + width
57
shape of the ROM
the height and the width
58
a ROM can encode a collection of logic functions directly from the truth table
59
if we have n functions with m inputs, we need a ROM with __ address lines and __ entries, with each entry being __ bits wide
m
2m
n
60
the entries in the input portion of the truth table represent the addresses of the entries in the ROM, while the contents of the output portion of the truth table constitute the contents of the ROM
61
a ROM is fully decoded means
it contains a full output word for every possible input combination
62
as the number of inputs grows, the number of entries in the ROM ...
grows exponentially
63
advantage of PLAs
for real logical functions, the number of product terms grows much slower than exponentially
64
advantage of ROMs
able to implement any logic function with the matching number of inputs and outputs => makes it easier to change if the function changes
65
Why are small collections of gates preferred for small logic functions?
they have less overhead than ROM and PLA
66
don't cares
situations where we do not care what the value of the output is
67
types of don't cares
output and input
68
output don't cares
arise when we don't care about the value of an output for some input combination
they appear as Xs in the output portion of the truth table
69
input don't cares
arise when an output depends on only some of the inputs
they appear as Xs in the input portion of the truth table
70
Karnaugh maps
represent the truth table graphically, so that the product terms that may be combined are easily seen
71
logic minimisation
critical to achieving efficient implementations
highly mechanical
can be preformed by design tools
the tools take advantage of the don't cares
72
array of logic elements
represented by showing that a given operation will happen to an entire collection of inputs
73
bus
a collection of data lines that is treated together as a single logical signal
74
What chooses the bus?
a multiplexor
75
most buses are __ bits wide
32
76
ALU
arithmetic logic unit
the brawn of the computer
device that performs the arithmetic operations or logical operations
a random number generator supplied with all computer systems
77
1-bit ALU
the logical operations are easiest, because they map directly onto the hardware
components
78
How does a 1- bit unit for AND and OR work?
multiplexor selects a AND b or a OR b, depending on whether the value of Operation is 0 or 1
79
addition
an adder must have two inputs for the operands and a single-bit output for the sum
80
full adder
or (3,2) adder
3 inputs, 2 outputs
81
half-adder or
(2,2) adder
82
32-bit ALU
created by connecting adjacent black boxes
83
ripple carry adder
created by directly linking the carries of 1-bit adders
84
slt
85
clock
a free running signal with a fixed cycle time
clock frequency - inverse of the cycle time
86
clock cycle
divided into two portions: high and low
87
edge-triggered clocking
a clocking scheme in which all state changes occur on a clock edge
one clock edge is active and causes changes
88
Why are state elements implemented with clocks?
so that the contents of the state elements only change on the active clock edge
89
clocking methodology
the approach used to determine when data is valid and stable relative to the clock
90
state elements
memory element
91
How does a clock edge work?
it acts as a sampling signal, causing the value of the data input to a state element to be sampled and stored in the state element
92
synchronous system
a memory system that employs clocks and where data signals are read only when the clocks indicates that the signal values are stable
93
constraints in a clock system
the signals that are written into state elements must be valid when the active clock edge occurs
94
When a signal valid?
when it is stable (not changing) and its value will not change again until the inputs change
95
since combinational circuits cannot have feedback, if the inputs to a combinational logic unit are not changed, the outputs will eventually become valid
96
How to ensure valid values on the active clock edges?
the clock must have a long enough period so that all the signals in the combinational logic block stabilise
97
advantage of edge-triggering
it is possible to have a state element that is used as both an input and an output to the same block
98
register files
a state element that consists of a set of registers that can be read and written by supplying a register number to be accessed
99
unlocked elements
simplest type of memory elements
don't have a clock input
flip-flops, latches
100
latch
a memory element in which the output is equal to the value of the stored state inside the element and the state is changed only on a clock edge
101
flip-flops
a memory element in which the output is equal to the value of the stored state inside the element and the state is changed whenever the appropriate inputs change and the clock is asserted
102
difference between latch and flip-flop
the point at which the clock causes the state to actually change
latch-whenever the appropriate inputs change
flip-flop-on a clock edge
103
What the function of flip-flops and latches in computer applications?
to store a signal
104
D flip-flop
a flip-flop with one data input that stores the value of that input signal in the internal memory when the clock edge occurs
has 2 input and 2 outputs
105
outputs in a D flip-flop
the value of the internal state (Q) and its complement (|Q)
106
inputs in a D flip-flop
the data b value to be stored (D) and a clock signal (C)
107
What does the clock signal in a D flip-flop indicate?
when the latch should read the value on D and store it
108
open latch
C is asserted => Q becomes D
109
closed latch
C is deasserted => Q is whatever value was stored last
110
transparent latch
when it's open Q changes as D changes
111
Are flip-flops transparent?
no, they change only on the edges
111
