the basics of logic design Flashcards
the basics of logic design
electronics inside a modern computer are ___________
digital
digital electronics
operate with only two voltage levels of interest: high and low
signals are logically either:
asserted: true or 1
deasserted: false or 0
values 0 and 1 are
complements/inverses
combinational logic blocks
don’t contain memory
output: depends on the current input
logic blocks with memory
output: can depend on both the input and the state
state of the logic block
value stored in memory
logic block with n entries will have a truth table with ___ entries
2^n
OR operator
logical sum
A + B
AND operator
logical product
A · B
unary operator NOT
Ā
identity law
A + 0 = A and A · 1 = A
zero and one laws
A + 1 = 1 and A · 0 = 0
inverse laws
A + Ā = 1 and A · Ā = 0
commutative laws
A + B = B + A and A · B = B · A
associative laws
A + (B + C) = (A + B) + C and A · (B · C) = (A · B) · C
distributive laws
A · (B + C) = (A · B) + (A · C) and A + (B · C) = (A + B) · (A + C)
DeMorgan’s laws
(i) (A ∪ B)’ = A’ ∩ B’
(ii) (A ∩ B)’ = A’ ∪ B’
gates
implement basic logic functions
all logic functions can be constructed with only a single gate type, if that
gate is inverting
NOR and NAND gates
inverting gates
decoders
type of logic blocks used in building larger components
most common type of decoder
has an n-bit input and 2^n outputs, where only one output is asserted for each input combination
encoder
preforms the inverse function of a decoder
multiplexor
basic logic function
also called selectors because the output is one of the inputs selected by a control
multiplexor has __ inputs and they are:
3
two data values + selector
selector value
or control value
determines which of the inputs becomes the output
a multiplexor with n inputs will need ________ selector inputs
log…?
multiplexor consists of __ parts which are:
3
a decoder that generates n signals
an array of n AND gates
a single large OR gate
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
In a multiplexor, what is the purpose of the OR gate?
incorporates the outputs of the AND gates
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
two-level representation
logic function written in canonical form
types of two-level representation
sum of products: logical sum of products (terms using the AND operator)
product of sums: the opposite
only those truth table entries for which the function is true generate terms in the equation
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
in a logic table each column represents a different ____________
logic function
programmable logic array (PLA)
a structured logic element composed of a set of inputs and corresponding input complements and two stages of logics
stages of logic in PLAs
- generates product terms of the inputs and input complements -> an array of AND gates that form a set of minterms
- 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
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
AND plane
size of the AND gate array
OR plane
size of the OR gate array
a row in the PLA corresponds to _______
each entry where the output is true, because it requires a product term
each output =
a potential row of OR gates in the second stage
the number of OR gates =
the number of truth table entries for which the output is true
the total size of a PLA =
AND plane + OR plane
PLA characteristics that make it an efficient way to implement a set of logic functions
- only the truth table entries that produce a true value for at least one output have any logic gates associated with them
- each different product term will have only one entry in the PLA, even if the product term is used in multiple outputs
PALs
PLA-like structures that can be programmed when needed
ROM
read-only memory
a memory whose contents are designated at creation time, after which contents can only be read
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
Why is ROM called a memory?
it has a set of locations that can be read
PROM
programmable ROM
it can be programmed when a designer knows its contents
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
ROM height
number of addressable entries
2^m -> m input lines
ROM width
the number of bits in each addressable entry = number of output bits
the total number of bits in ROM=
height + width
shape of the ROM
the height and the width
a ROM can encode a collection of logic functions directly from the truth table
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
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
a ROM is fully decoded means
it contains a full output word for every possible input combination
as the number of inputs grows, the number of entries in the ROM …
grows exponentially
advantage of PLAs
for real logical functions, the number of product terms grows much slower than exponentially
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
Why are small collections of gates preferred for small logic functions?
they have less overhead than ROM and PLA
don’t cares
situations where we do not care what the value of the output is
types of don’t cares
output and input
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
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
Karnaugh maps
represent the truth table graphically, so that the product terms that may be combined are easily seen
logic minimisation
critical to achieving efficient implementations
highly mechanical
can be preformed by design tools
the tools take advantage of the don’t cares
array of logic elements
represented by showing that a given operation will happen to an entire collection of inputs
bus
a collection of data lines that is treated together as a single logical signal
What chooses the bus?
a multiplexor
most buses are __ bits wide
32
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
1-bit ALU
the logical operations are easiest, because they map directly onto the hardware
components
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
addition
an adder must have two inputs for the operands and a single-bit output for the sum
full adder
or (3,2) adder
3 inputs, 2 outputs
half-adder or
(2,2) adder
32-bit ALU
created by connecting adjacent black boxes
ripple carry adder
created by directly linking the carries of 1-bit adders
slt
clock
a free running signal with a fixed cycle time
clock frequency - inverse of the cycle time
clock cycle
divided into two portions: high and low
edge-triggered clocking
a clocking scheme in which all state changes occur on a clock edge
one clock edge is active and causes changes
Why are state elements implemented with clocks?
so that the contents of the state elements only change on the active clock edge
clocking methodology
the approach used to determine when data is valid and stable relative to the clock
state elements
memory element
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
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
constraints in a clock system
the signals that are written into state elements must be valid when the active clock edge occurs
When a signal valid?
when it is stable (not changing) and its value will not change again until the inputs change
since combinational circuits cannot have feedback, if the inputs to a combinational logic unit are not changed, the outputs will eventually become valid
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
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
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
unlocked elements
simplest type of memory elements
don’t have a clock input
flip-flops, latches
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
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
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
What the function of flip-flops and latches in computer applications?
to store a signal
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
outputs in a D flip-flop
the value of the internal state (Q) and its complement (|Q)
inputs in a D flip-flop
the data b value to be stored (D) and a clock signal (C)
What does the clock signal in a D flip-flop indicate?
when the latch should read the value on D and store it
open latch
C is asserted => Q becomes D
closed latch
C is deasserted => Q is whatever value was stored last
transparent latch
when it’s open Q changes as D changes
Are flip-flops transparent?
no, they change only on the edges
