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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

base, r

A
  • also known as the radix

- determined by the position of the digit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

radix point

A

separates the integer part of a number from the fractional part

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

expansion method

A

method of calculating an equivalent decimal value from a base-r number

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

counting in base-r

A

each time:

  • count up one
  • increment the least significant digit
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Binary bit addition

A

bits can be added, subtracted, multiplied and divided

only digits 0 and 1 are allowed in the results

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

truth tables

A

represents results of Boolean function for all combinations of the input variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

binary digit

A

also known as bit, or scalar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

cell

A
  • smallest information storage unit

- often referred to as a word or byte

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

register

A
  • ordered collection of cells
  • when ordering values of binary variables, leftmost is most significant bit ( MSB) , rightmost is least significant bit (LSB)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

logical 1

A
  • indicates a true condition

- typically associated with high voltage in an electronic circuit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

logical 0

A
  • indicates a false condition

- typically associated with a lower voltage

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

voltage range

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

fan-out

A

number of logic gates that can be driven from a single output

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

fundamental logic operations

A

set of simple boolean functions from which all other digital functions can be derived

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

combinational logic

A

logic of processing information by combining with and comparing to other information so the output depends only on the value of the inputs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

unary operation

A

logic operator involving a single variable or operand

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

function set

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

miniterm, m

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

maxterm, M

A
  • 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 )
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

canonical sum-of-product (SOP) forms

A

logical OR combinations (summation) of minterms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

canonical product of sums (POS) forms

A

logical AND combinations (products) of maxterms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

implementation

A
  • any given truth table can be implemented with many different logical expressions
  • each expression corresponds to a different digital circuit
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

minimization

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

De Morgan’s theorems

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Karnaugh map (K-map)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

grouping types

A

cells can be circled in the center, along any row or column, and across the edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

group overlap

A

groupings may (and should if they can) overlap each other

44
Q

don’t care

A
  • condition that is never used or that is irrelevant to the expression
  • indicated by the letter “X”
45
Q

encoding

A

the assignment of a digital number associated with the input asserted

46
Q

input/outputs

A

N outputs in order to encode 2^N inputs

47
Q

multiple asserted inputs

A

a disallowed state: only one input may be asserted at any given time. For all other combinations of inputs, the output is undefined

48
Q

decoding

A
  • opposite operation to encoding

- takes an encoded input and asserts the associated output line

49
Q

no disallowed states

A

for every possible combinations of inputs, the output is defined

50
Q

logic equation

A

for each output, equal to the corresponding miniterm of the input

51
Q

multiplexer (mux)

A

selects from a number of available inputs and copies the input to the output

52
Q

inputs

A

2^N inputs for N selector lines

53
Q

output

A

current selected input. For a 4-input multiplexer

54
Q

demultiplexed (demux)

A
  • performs the opposite function to the multiplexer

- feeds the input signal onto any one of the outputs based on the selector switch

55
Q

output logic equation

A

equal to the zero unless selected in which case it is the equal to the input

56
Q

multiplexer logic

A

can be used to implement any logical function, sometimes very efficiently

57
Q

procedure

A
  • 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
Q

comparator

A

compares two binary numbers numbers indicating which is greater

59
Q

comparator logic

A
  • 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
Q

full adder, FA

A
  • 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
Q

carry look ahead

A

precalculates the carry input so that the next adders do not have to wait for the carry-in from the previous adders

62
Q

n-bit binary word adder

A

made by combining n full adders

63
Q

carries

A

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
Q

propagation delay, td

A

time needed by a logic gate from when an input changes to when the output responds

65
Q

critical path

A

longest or worse case propagation delay

66
Q

static hazard

A

a situation in which, after the input changes, the output temporarily fluctuates to the wrong value before settling to the right one

67
Q

static hazard correction

A
  • static hazard occurs due to adjacent grouping of terms

- solution is to add a redundant grouping across the 2 adjacent groups

68
Q

sequential network (sequential device)

A
  • 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
Q

binary network (binary device)

A
  • restricted to two states, 0 and 1

- correspond to high and low voltage

70
Q

sequential logic

A
  • logic designs whose output will depend on the sequence of the inputs
  • occurs when digital system has memory
71
Q

flip-flop

A
  • 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
Q

memory device

A
  • 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
Q

synchronous memory device

A
  • device whose output is only updated when triggered by a clock signal
  • as long as device is not triggered, previous state is held
74
Q

asynchronous memory device

A
  • device whose output does not depend on a clock signal

- can be triggered by a change in the input signal

75
Q

clock pulse

A
  • rectangular pulse having fixed clock width (duration)

- well-defined rising and falling edges

76
Q

clocked device

A
  • device metered( controlled) by a clock

- triggered by a clock pulse

77
Q

transparent device

A
  • does not depend on a clock to initiate state transitions

- changes state in accordance with other inputs

78
Q

level-sensitive synchronous memory

A
  • 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
Q

edge-triggered synchronous memory

A
  • 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
Q

transition table

A
- 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
Q

Set-reset (SR) Flip Flops

A
  • set signal S
  • -> sets output Qn +1 to 1
  • reset signal, R
  • -> sets output Qn +1 to 0
82
Q

level-sensitive SR flip-flop

A

created with an asynchronous SR flip-flop

83
Q

transparency

A
  • 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
Q

JK flip flop

A
  • 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
Q

D flip flop

A
  • 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
Q

finite state machine (FSM)

A

possesses a finite number of states where the state transition occurs at discrete points in time

87
Q

current state

A

condition or value of all the memory elements in the system

88
Q

next state

A

the next state is a function of the current state and the current inputs to the system

89
Q

Moore type state machine

A

outputs are only a function of the current state

90
Q

Mealy type state machine

A

outputs are a function of the current state and the current inputs

91
Q

state diagram

A

depicts the operation of an FSM

92
Q

next state

A

indicated by current state and the inputs

93
Q

outputs

A

indicated either on the state or the transitions

94
Q

binary system

A

N flip-flops provides for 2^N possible states

95
Q

state table

A

provides the next state information and output in tabular form

96
Q

reduction

A

standard methods can then be used to determine logic equations and implementation

97
Q

counter

A
  • clocked sequential device

- progression through a series of predefined states is interpreted as a progression of numbers

98
Q

binary counter

A
  • made up of n identical flip flops

- “count” at any given time is determined by one of the possible states in the sequence

99
Q

asynchronous counter (ripple counter)

A

each flip flop Qn is set to toggle on rising edge of Qn-1

0011–>0010–>0001–>0000–>1111

100
Q

down/up

A

can be switched depending on whether clocks are driven from Q or Q’

101
Q

synchronous counter

A
  • designed just like any arbitrary digital system
  • clock pulse toggles all flip flops simultaneously
  • all flip flops change state at the same time
102
Q

timing for memory elements

A

the two major timing constraints are setup time and hold time

103
Q

setup time, tsetup

A

time that input D must remain stable before the clock is triggered

104
Q

hold time, thold

A

time that the input D must remain stable after clock is triggered

105
Q

propagation delay tCLK-Q

A
  • time required for the output state to change after the clock trigger
  • similar timing constraints for all flip-flops
106
Q

standard implementation

A

FSM hardware shown below

107
Q

minimum clock period

A
tmin= tcrit + tCLK-Q + tsetup
fmax= 1/ tmin