Digital Systems Flashcards
1
Q
positional numbering system
A
- position of a digit in the number determines that digit’s contribution to the total value of the number
2
Q
base, r
A
- also known as the radix
- determined by the position of the digit
3
Q
radix point
A
separates the integer part of a number from the fractional part
4
Q
expansion method
A
method of calculating an equivalent decimal value from a base-r number
5
Q
binary number system
A
- base- 2 number system
- only 2 binary digits (bits)L 0 and 1
- number consist of string of bits
6
Q
counting in base-r
A
each time:
- count up one
- increment the least significant digit
7
Q
carry
A
if the least significant digit reaches the base, r, it is reset to zero and a carry is generated into the next LSD
8
Q
Binary bit addition
A
bits can be added, subtracted, multiplied and divided
only digits 0 and 1 are allowed in the results
9
Q
octal number system
A
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
10
Q
hexadecimal number system
A
- 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
11
Q
converting base 10 numbers to base-r
A
- 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
12
Q
radix (base) complement, R(M)
A
- 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
13
Q
diminished radix complement
A
- 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
14
Q
computer representation of negative numbers
A
- 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
15
Q
1’s complement
A
- obtained by inverting each bit of the number, M
- ideal for forming a negative number,
21 = 0001 0101
-21 = 1110 1010
16
Q
2’s complement
A
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
17
Q
Boolean algebra
A
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
18
Q
logic gate
A
- implements logic operators digitally
- has one or more inputs and a single output
- dot (“bubble”, or small circle) designates use of NOT operation
19
Q
truth tables
A
represents results of Boolean function for all combinations of the input variables
20
Q
order of operations
A
- defines order of precedence for which digital calculations are performed
- analogous to the order of operations for mathematical operations
21
Q
binary digit
A
also known as bit, or scalar
22
Q
binary scalar, B
A
- typically takes on value of either 0 or 1
- represents one bit of information
- Boolean states are associated with bit values
23
Q
n-tuple
A
- 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
24
Q
cell
A
- smallest information storage unit
- often referred to as a word or byte
25
register
- ordered collection of cells
- when ordering values of binary variables, leftmost is most significant bit ( MSB) , rightmost is least significant bit (LSB)
26
logical 1
- indicates a true condition
| - typically associated with high voltage in an electronic circuit
27
logical 0
- indicates a false condition
| - typically associated with a lower voltage
28
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
29
fan-out
number of logic gates that can be driven from a single output
30
fundamental logic operations
set of simple boolean functions from which all other digital functions can be derived
31
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
32
unary operation
logic operator involving a single variable or operand
33
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
34
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)
35
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 )
36
canonical sum-of-product (SOP) forms
logical OR combinations (summation) of minterms
37
canonical product of sums (POS) forms
logical AND combinations (products) of maxterms
38
implementation
- any given truth table can be implemented with many different logical expressions
- each expression corresponds to a different digital circuit
39
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
40
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
41
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
42
grouping types
cells can be circled in the center, along any row or column, and across the edges
43
group overlap
groupings may (and should if they can) overlap each other
44
don't care
- condition that is never used or that is irrelevant to the expression
- indicated by the letter "X"
45
encoding
the assignment of a digital number associated with the input asserted
46
input/outputs
N outputs in order to encode 2^N inputs
47
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
48
decoding
- opposite operation to encoding
| - takes an encoded input and asserts the associated output line
49
no disallowed states
for every possible combinations of inputs, the output is defined
50
logic equation
for each output, equal to the corresponding miniterm of the input
51
multiplexer (mux)
selects from a number of available inputs and copies the input to the output
52
inputs
2^N inputs for N selector lines
53
output
current selected input. For a 4-input multiplexer
54
demultiplexed (demux)
- performs the opposite function to the multiplexer
| - feeds the input signal onto any one of the outputs based on the selector switch
55
output logic equation
equal to the zero unless selected in which case it is the equal to the input
56
multiplexer logic
can be used to implement any logical function, sometimes very efficiently
57
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
58
comparator
compares two binary numbers numbers indicating which is greater
59
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.
60
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
61
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
62
n-bit binary word adder
made by combining n full adders
63
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
64
propagation delay, td
time needed by a logic gate from when an input changes to when the output responds
65
critical path
longest or worse case propagation delay
66
static hazard
a situation in which, after the input changes, the output temporarily fluctuates to the wrong value before settling to the right one
67
static hazard correction
- static hazard occurs due to adjacent grouping of terms
| - solution is to add a redundant grouping across the 2 adjacent groups
68
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
69
binary network (binary device)
- restricted to two states, 0 and 1
| - correspond to high and low voltage
70
sequential logic
- logic designs whose output will depend on the sequence of the inputs
- occurs when digital system has memory
71
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
72
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
73
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
74
asynchronous memory device
- device whose output does not depend on a clock signal
| - can be triggered by a change in the input signal
75
clock pulse
- rectangular pulse having fixed clock width (duration)
| - well-defined rising and falling edges
76
clocked device
- device metered( controlled) by a clock
| - triggered by a clock pulse
77
transparent device
- does not depend on a clock to initiate state transitions
| - changes state in accordance with other inputs
78
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
79
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
80
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
```
81
Set-reset (SR) Flip Flops
- set signal S
- -> sets output Qn +1 to 1
* reset signal, R
- -> sets output Qn +1 to 0
82
level-sensitive SR flip-flop
created with an asynchronous SR flip-flop
83
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
84
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
85
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
86
finite state machine (FSM)
possesses a finite number of states where the state transition occurs at discrete points in time
87
current state
condition or value of all the memory elements in the system
88
next state
the next state is a function of the current state and the current inputs to the system
89
Moore type state machine
outputs are only a function of the current state
90
Mealy type state machine
outputs are a function of the current state and the current inputs
91
state diagram
depicts the operation of an FSM
92
next state
indicated by current state and the inputs
93
outputs
indicated either on the state or the transitions
94
binary system
N flip-flops provides for 2^N possible states
95
state table
provides the next state information and output in tabular form
96
reduction
standard methods can then be used to determine logic equations and implementation
97
counter
- clocked sequential device
| - progression through a series of predefined states is interpreted as a progression of numbers
98
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
99
asynchronous counter (ripple counter)
each flip flop Qn is set to toggle on rising edge of Qn-1
| 0011-->0010-->0001-->0000-->1111
100
down/up
can be switched depending on whether clocks are driven from Q or Q'
101
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
102
timing for memory elements
the two major timing constraints are setup time and hold time
103
setup time, tsetup
time that input D must remain stable before the clock is triggered
104
hold time, thold
time that the input D must remain stable after clock is triggered
105
propagation delay tCLK-Q
- time required for the output state to change after the clock trigger
- similar timing constraints for all flip-flops
106
standard implementation
FSM hardware shown below
107
minimum clock period
```
tmin= tcrit + tCLK-Q + tsetup
fmax= 1/ tmin
```
