Digital Systems Flashcards
positional numbering system
- position of a digit in the number determines that digit’s contribution to the total value of the number
base, r
- also known as the radix
- determined by the position of the digit
radix point
separates the integer part of a number from the fractional part
expansion method
method of calculating an equivalent decimal value from a base-r number
binary number system
- base- 2 number system
- only 2 binary digits (bits)L 0 and 1
- number consist of string of bits
counting in base-r
each time:
- count up one
- increment the least significant digit
carry
if the least significant digit reaches the base, r, it is reset to zero and a carry is generated into the next LSD
Binary bit addition
bits can be added, subtracted, multiplied and divided
only digits 0 and 1 are allowed in the results
octal number system
base-8 number system
alternative to working with long binary numbers
uses digits 0 through 7
(2)^3 = 8 so three binary digits can be represented by a singe octal
hexadecimal number system
- shorter method of representing the value of four binary digits at a time, (2)^4 =16
- requires 16 unique characters
- generally uses capital letter A through F for digits 10 through 15
converting base 10 numbers to base-r
- remainder method used
- repeated division by base, r, until quotient is zero
- base-r number found by taking remainders in reverse order in which they were found
radix (base) complement, R(M)
- given M, an N-bit, base-r argument, R(M) is the number which when added to M results in a sum of r^N
- R(M) depends on the machine being used. N is the maximum number of digits used by the machine to store an integer
diminished radix complement
- also called r - 1 complement
- equal to R(M) - 1
for example, if working in base-10 R(M) is the ten’s complement and one less than this is the nine’s complement
computer representation of negative numbers
- the typical representation of a negative number ( a minus sign) is not possible in a machine
- one N digit, usually the MD is reserved for sign representation
- this reduces the machine’s capacity to represent numbers N -1 bits per number
- it is arbitrary whether the sign bit for negative numbers is 0 or 1, as long as the MSD is different for positive and negative numbers
1’s complement
- obtained by inverting each bit of the number, M
- ideal for forming a negative number,
21 = 0001 0101
-21 = 1110 1010
2’s complement
for an N-bit binary integer, M, the 2’s complement is
R(M) = 2^N - M
An alternative way to calculate this to take the 1’s complement and add 1.
21= 0001 0101 -21= 1110 1011
Boolean algebra
a system for representing and evaluating logical variables (Boolean variable) and their combinations
- logical variables are typically represented by uppercase letters (A, B, and so on)
- in a digital environment, Boolean variables are confined for two values representing true and false, typically 1 and 0, respectively
logic gate
- implements logic operators digitally
- has one or more inputs and a single output
- dot (“bubble”, or small circle) designates use of NOT operation
truth tables
represents results of Boolean function for all combinations of the input variables
order of operations
- defines order of precedence for which digital calculations are performed
- analogous to the order of operations for mathematical operations
binary digit
also known as bit, or scalar
binary scalar, B
- typically takes on value of either 0 or 1
- represents one bit of information
- Boolean states are associated with bit values
n-tuple
- grouping of n binary scalars
- represented by [ A1, A2, A3, .. An]
- value of n is called word length
- total number of values that can be represented is N =2^N
cell
- smallest information storage unit
- often referred to as a word or byte
register
- ordered collection of cells
- when ordering values of binary variables, leftmost is most significant bit ( MSB) , rightmost is least significant bit (LSB)
logical 1
- indicates a true condition
- typically associated with high voltage in an electronic circuit
logical 0
- indicates a false condition
- typically associated with a lower voltage
voltage range
- practical real logic devices provide a range of voltage levels which are interpreted as logical 1 or 0.
- for example, transistor-transistor logic (TTL) allows a voltage range 0 - 0.8 V for a logical 0, AND 2.0 - 5.0 V for a logical 1
fan-out
number of logic gates that can be driven from a single output
fundamental logic operations
set of simple boolean functions from which all other digital functions can be derived
combinational logic
logic of processing information by combining with and comparing to other information so the output depends only on the value of the inputs
unary operation
logic operator involving a single variable or operand
function set
- the set of all possible mappings from input to output
- for N binary inputs, there are 2^N possible input combinations and 2^2^N possible functions
miniterm, m
- term that consists of the product of every variable in the function without duplication of any variables
- associated with conditions where the output is true (logical 1)
maxterm, M
- term that consist of the sum of every variable in the function without duplication of any variables
- associated with conditions where the output is false (logical 0 )
canonical sum-of-product (SOP) forms
logical OR combinations (summation) of minterms
canonical product of sums (POS) forms
logical AND combinations (products) of maxterms
implementation
- any given truth table can be implemented with many different logical expressions
- each expression corresponds to a different digital circuit
minimization
process of reducing the logical equation in order to minimize hardware resources for the circuit
minimization method:
- Boolean algebra and Karnaugh maps
- removes redundancy, simplifies logic, and improves speed
De Morgan’s theorems
- give equivalent functional representation for NAND gates and NOR gates
- can be extended to any AND/OR gate
- rule is change the AND gate to an OR gate (or vice versa) and invert the bubbles on the gate
Karnaugh map (K-map)
- graphical representation of a Boolean function (truth table)
- each cell in the map represents a miniterm or maxterm
- adjacent rows or columns change by one variable only
- two cells next to each other eliminate one variable
grouping types
cells can be circled in the center, along any row or column, and across the edges
group overlap
groupings may (and should if they can) overlap each other
don’t care
- condition that is never used or that is irrelevant to the expression
- indicated by the letter “X”
encoding
the assignment of a digital number associated with the input asserted
input/outputs
N outputs in order to encode 2^N inputs
multiple asserted inputs
a disallowed state: only one input may be asserted at any given time. For all other combinations of inputs, the output is undefined
decoding
- opposite operation to encoding
- takes an encoded input and asserts the associated output line
no disallowed states
for every possible combinations of inputs, the output is defined
logic equation
for each output, equal to the corresponding miniterm of the input
multiplexer (mux)
selects from a number of available inputs and copies the input to the output
inputs
2^N inputs for N selector lines
output
current selected input. For a 4-input multiplexer
demultiplexed (demux)
- performs the opposite function to the multiplexer
- feeds the input signal onto any one of the outputs based on the selector switch
output logic equation
equal to the zero unless selected in which case it is the equal to the input
multiplexer logic
can be used to implement any logical function, sometimes very efficiently
procedure
- generate the truth table for the logic function
- hardcore, the logical inputs to the multiplexer, matching the truth table
- selector switches of the truth table
comparator
compares two binary numbers numbers indicating which is greater
comparator logic
- logic can be derived by heuristic thinking
- if c’s MSB is greater, than c is greater, else is MSBs are equal and c’s next MSB is greater then c is greater, etc.
full adder, FA
- adds 2 binary bits plus a carry in, cin
- produces two outputs, a sum and a carry out, cout
- can be daisy chained together to add binary n-tuples or binary numbers
carry look ahead
precalculates the carry input so that the next adders do not have to wait for the carry-in from the previous adders
n-bit binary word adder
made by combining n full adders
carries
each carry out is connected to the next adders carry in. In this regard, the carry out ripples out from the least significant full adder to the most significant full adder
propagation delay, td
time needed by a logic gate from when an input changes to when the output responds
critical path
longest or worse case propagation delay
static hazard
a situation in which, after the input changes, the output temporarily fluctuates to the wrong value before settling to the right one
static hazard correction
- static hazard occurs due to adjacent grouping of terms
- solution is to add a redundant grouping across the 2 adjacent groups
sequential network (sequential device)
- a circuit that has at least one input and one internal state variable
- output may depend on the present and past states of the inputs
binary network (binary device)
- restricted to two states, 0 and 1
- correspond to high and low voltage
sequential logic
- logic designs whose output will depend on the sequence of the inputs
- occurs when digital system has memory
flip-flop
- basic unit of memory
- stores single bit of information, 0 or 1
- has 2 or 3 inputs
set or preset, S
reset or clear, R
clock, CLK
memory device
- device whose output depends on previous output in time
- current output can be changed or held indefinitely
- output of the memory defines the memory state
synchronous memory device
- device whose output is only updated when triggered by a clock signal
- as long as device is not triggered, previous state is held
asynchronous memory device
- device whose output does not depend on a clock signal
- can be triggered by a change in the input signal
clock pulse
- rectangular pulse having fixed clock width (duration)
- well-defined rising and falling edges
clocked device
- device metered( controlled) by a clock
- triggered by a clock pulse
transparent device
- does not depend on a clock to initiate state transitions
- changes state in accordance with other inputs
level-sensitive synchronous memory
- device is sensitive to inputs as long as clock signal remains high
- if clock signal is low, memory device is insensitive to further changes in input
- device retains its state until clock goes high again
edge-triggered synchronous memory
- device updates on rising (positive) edge or falling (negative) edge of clock or both
- when triggered, changes to the next output condition depending on the current input
- at other times, device retains old value
transition table
- shows possible transitions for sequential devices (flip-flops) with inputs needed for transition to occur four possible state transitions 0 --> 0 0 --> 1 1 --> 0 1 --> 1
Set-reset (SR) Flip Flops
- set signal S
- -> sets output Qn +1 to 1
- reset signal, R
- -> sets output Qn +1 to 0
level-sensitive SR flip-flop
created with an asynchronous SR flip-flop
transparency
- when clock is high, set and reset signals are transmitted through AND gates; flip-flop acts like an SR latch
- when clock is low, both S and R are zero; flip-flop holds regardless of the input signal
JK flip flop
- similar to SR flip-flop, except both inputs can be used simultaneously
- interprets each combination of inputs as a command to set the output to a specific value
D flip flop
- synchronous flip-flop in which the next-state output is always equal to the input at a specific time in the clock’s style
- stores the value of input D when triggered
- initiating input (delay) D
finite state machine (FSM)
possesses a finite number of states where the state transition occurs at discrete points in time
current state
condition or value of all the memory elements in the system
next state
the next state is a function of the current state and the current inputs to the system
Moore type state machine
outputs are only a function of the current state
Mealy type state machine
outputs are a function of the current state and the current inputs
state diagram
depicts the operation of an FSM
next state
indicated by current state and the inputs
outputs
indicated either on the state or the transitions
binary system
N flip-flops provides for 2^N possible states
state table
provides the next state information and output in tabular form
reduction
standard methods can then be used to determine logic equations and implementation
counter
- clocked sequential device
- progression through a series of predefined states is interpreted as a progression of numbers
binary counter
- made up of n identical flip flops
- “count” at any given time is determined by one of the possible states in the sequence
asynchronous counter (ripple counter)
each flip flop Qn is set to toggle on rising edge of Qn-1
0011–>0010–>0001–>0000–>1111
down/up
can be switched depending on whether clocks are driven from Q or Q’
synchronous counter
- designed just like any arbitrary digital system
- clock pulse toggles all flip flops simultaneously
- all flip flops change state at the same time
timing for memory elements
the two major timing constraints are setup time and hold time
setup time, tsetup
time that input D must remain stable before the clock is triggered
hold time, thold
time that the input D must remain stable after clock is triggered
propagation delay tCLK-Q
- time required for the output state to change after the clock trigger
- similar timing constraints for all flip-flops
standard implementation
FSM hardware shown below
minimum clock period
tmin= tcrit + tCLK-Q + tsetup fmax= 1/ tmin
