Digital Logic Final Exam

Front 1

Duality of a function

Back 1

Change . <-> +

Change 0 <-> 1

Keep precedence (may need parentheses)

Front 2

DeMorgan's Equivalent

Back 2

Change AND <-> OR

Complements inputs and outputs

Front 3

DeMorgan's Complement (Inverse)

Back 3

Change AND <-> OR

Complement inputs

Front 4

Sum - of - Products (SOP)

Back 4

Output = 1

Prime 0 terms

OR all minterms

Front 5

Product - of - Sums (POS)

Back 5

Output = 0

Prime 1 terms

AND all maxterms

Front 6

Complete Logic Set

Back 6

Any logic function can always be constructed using only AND, OR & Inverter gates

Front 7

Static Hazards

Back 7

The output is supposed to stay at one value, but briefly assumes the other value

To fix: add an another PI to join all adjacent 1s

Front 8

Dynamic Hazard

Back 8

The outputs is supposed to change values, but oscillates briefly before settling down

Front 9

Minimal Sum for a function (SOP)

Back 9

Minimum number of products terms (AND gates), minimum number of literal inputs to the products

Front 10

Literal

Back 10

A variable or complemented variable

Front 11

Implicant

Back 11

A group of 1s on the K-Map

Front 12

Prime Implicant (PI)

Back 12

Biggest group of 1s on the K-Map

Front 13

Distinguished 1-Cell

Back 13

A 1 included in only one prime implicant (PI)

Front 14

Essential Prime Implicant (EPI)

Back 14

A prime implicant (PI) that contains a distinguished 1-cell

Front 15

Cover

Back 15

A group of implicants that include al 1s in F

Front 16

Incompletely Specified Function

Back 16

a circuit with one or more don't cares

Front 17

Dataflow Specification (Verilog)

Back 17

1. Specifies logic equation of the function

2. Represented as a set of concurrent assignment statements

(assign)

Front 18

Procedural Specification (Verilog)

Back 18

1. Specified the logic as a sequence of program statements

2. Employs all common logical & arithmetic operators

3. Executes statements sequentially

(always @)

Front 19

Parameter (Verilog)

Back 19

Defines a symbolic constant

(similar to #define in C)

Front 20

Concatenation Operator (Verilog)

Back 20

Having a bunch of signals you wish to "bundle" together

EX: Nerds = {Sheldon, Leonard, Raj};

Front 21

Propagation Delay

Back 21

Real digital circuits take time to switch states

Limit a system's temporal performance

Front 22

Fan-In

Back 22

Number of inputs (n) into a particular device

1. The bigger n is, the longer it takes to charge all the gates

2. Large fan-in (n) lengthens prop. delay

Front 23

Fan-Out

Back 23

Number of devices a given signal must drive, number of logic gates using this signal as inputs

1. As fan-out increases, the device takes longer to switch

Front 24

Rise & Fall Time

Back 24

Time it take signals to rise or fall from logic 0 to logic 1 (affected by fan-in and fan-out)

tr = rise time

tf = fall time

Front 25

Decimal

Back 25

Base 10

Representation: 613

Front 26

Binary

Back 26

Base 2

Representation: 0b1101

Front 27

Hexidecimal

Back 27

Base 16

Representation: 0x613

Front 28

Octal

Back 28

Base 8

Representation: 0613

Front 29

Convert anything to decimal

Back 29

Execute defining summation:

EX: Binary (0b1101) to decimal 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 11

EX: Octal (03602) to decimal 3*8^3 + 0*8^2 + 6*8^1 + 2*8^0 = 1586

EX: Hex (0x3062) to decimal 3*16^3 + 0*16^2 + 6*16^1 + 2*16^0 = 12,836

Front 30

Convert decimal to anything

Back 30

Repeatedly divide the decimal by r:

EX: Decimal (58) to hex 58/16=3 R10, 3/16 = 0 R3 -> 0x3A

Front 31

Convert Binary to Octal/Hex

Back 31

Octal: group bits into 3s, write down digits

Hex: group bits 4s, write down digits

Front 32

Convert Octal/Hex to Binary

Back 32

Octal: Expand each digit into three binary bits

Hex: Expand each digit into four binary bits

Front 33

Convert Hex <-> Octal

Back 33

Detour through binary:

1. Convert to Binary

2. Regroup bits

Front 34

Unsigned Binary Representation

Back 34

Cannot be negative numbers

EX: 0001 = 1

EX: 1001 = 11

EX: 1101 = 13

Front 35

Signed-Magnitude Representation

Back 35

All we do is add on a sign bit

EX: +5 = 0b0101

-5 = 0b1101

Easy for people to read and interpret

Front 36

1's Complement Representation

Back 36

To negate: invert all the bits (-X = X')

EX: +1 = 0001

-1 = 1110

Front 37

2's Complement Representation

Back 37

To negate: invert all the bits and add 1 (-X = X'+1)

EX: +5 = 0b0101

-5 = 0b1011 (-5 = 5'+1)

Very hard for people to read and interpret

Front 38

Sign Extension

Back 38

Simple "sign extend" the sign bit into the upper bits

EX: 0011 -> 0000,0011

EX: 1011 -> 1111,1011

Front 39

Unsigned Overflow

Back 39

Carry out of most significant bit (MSB)

Front 40

Unsigned Underflow

Back 40

No carry out of most significant (MSB)

Front 41

Excess Signed Notation

Back 41

Select some medial value (B) and define that as 0

Any number > B is positive

Any number < B is negative

Min value is always 000...000

Max value is always 111...111

Zero value is always at B

Front 42

Gray Code

Back 42

Any two adjacent bits differ in exactly one bit

EX: 0000, 0001, 0011, 0010

Front 43

Fixed - Point Fractions

Back 43

Insert a "binary point" to mark the fraction part of the number

EX: 1010.11 = 10.75

1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 . 1*2^-1 + 1*2^-2

Front 44

Floating Point Numbers

Back 44

Base 2 scientific notation

EX: 1001 = 1.001*2^3

Front 45

Floating Point normalized form

Back 45

(sign) (significand)*2^exponent

significand is written with one bit the left of the radix point

Front 46

ASCII Code

Back 46

American Standard Code for Info Interchange

Decimal digits: 0x30 & run contiguously

Upper case letters: 0x41 & run contiguously

Lower case letters: 0x61 & run contiguously

Front 47

Change upper case <-> lower case

Back 47

Upper and lower case only differ in bit 5

To change the case: invert bit 5

Front 48

Fault

Back 48

Physical defect or flaw in a component of the system

Front 49

Error

Back 49

Incorrect behavior caused by a fault

Front 50

Failure

Back 50

inability of system to correctly deliver its service

Front 51

Codeword

Back 51

Combined data and check bits

N = M + K (size of codeword)

M = dataword

K = check bits

Front 52

Hamming Distance

Back 52

Number of bits in which 2 codewords differ

EX: A 10011001

B 11001101

HD (A,B) = 3

Front 53

Code Distance

Back 53

Minimum hamming distance between any 2 valid codewords

Code distance must be > # of errors tolerated

Front 54

Programmable Logic Array (PLAs)

Back 54

Direct implementation of SOP equation

Amplifies signal currents, protects source from fan-out

2 output ports: one inverted, one not

Front 55

Tri-State Devices

Back 55

Outputs have a high impedance, "High-Z" state

Z-state is controlled by the enable pin

1. enabled: normal buffer

2. disabled: disconnected, high-z state

Front 56

Decoder

Back 56

Can generate all combinational logic functions

n data inputs

2^n outputs

enable inputs

Front 57

Complexity of Decoded Addresses

Back 57

2^n data rows (one word per row)

2^n select signals, decoded from n address bits

Front 58

Encoder

Back 58

Outputs the binary address of input line (assuming inputs are mutually exclusive)

2^n data inputs

n data ouputs

If not mutually exclusive: selection is based on priority - usually one with largest signal name

Front 59

Multiplexer (MUX)

Back 59

n data inputs (usually power of 2)

log2(n) select inputs

exactly one ouput

optional enable pin

Rotary switch to select which data inputs goes to the one & only output

Front 60

Demultiplexer (DeMUX)

Back 60

1 data input signal (G)

n input select signals

2^n output signals

Rotary switch to select with data output gets the one & only input

Front 61

Comparators

Back 61

Compares 2 unsigned numbers

A = B is easy

A < B or A > B is messy

Front 62

Carry-Lookahead Adder (CLA)

Back 62

gi = generate function in stage i

pi = propagate function in stage i

Front 63

Sequential Logic vs. Combinational Logic

Back 63

Sequential: current output depends on current input and previous device states

Combinational: current output depends on current inputs only

Front 64

Asynchronous

Back 64

Output changes as soon as input changes

Front 65

Level Gated

Back 65

Output changes only when enable/clock is active

(Latches)

Front 66

Pulsed

Back 66

Output changes only when enable/clock changes twice (after a completed pulse)

(Flip-Flops)

Front 67

Edge Triggered

Back 67

Output changes only at the edge of the clock

Front 68

Setup Time

Back 68

Minimum time that D must be stable before the rising edge of the clock

Front 69

Hold Time

Back 69

Minimum time that D must be stable after the rising edge of the clock

Front 70

Asynchronous Counter

Back 70

Each Flip-Flop is triggered by a state-change in previous FF (ripple-carry adder)

Front 71

Synchronous Counter

Back 71

Each Flip-Flop is triggered by the global clock (carry-lookahead adder)

Front 72

Moore Finite State Machine

Back 72

current_state = F(previous_state, inputs)

Q <= F(W,Q)

current_output = G(current_state)

Z = G(Q)

Outputs change synchronously - only on clock edge

Front 73

Mealy Finite State Machine

Back 73

current_state = F(previous_state, inputs)

Q <= F(W,Q)

current_output = G(current_state, inputs)

Z = G(W,Q)

Outputs change asynchronously - when either state or inputs change

Front 74

What does asynchronous mean?

Back 74

1. No clock pulse to synchronize circuits

2. No clocked flip-flops for state variables

3. States and outputs change when inputs change

4. There is stored state memory (behavior is history dependent)

5. Order in which inputs change, matters

Front 75

Fundamental Mode

Back 75

1. Just one input changes at a time

2. A 2nd input change does not occur until the state is stable