Digital Systems Review (taken from Chap. 1)

boolean set

• B = set of the constants 0,1 and the operations you can do with boolean values (AND *, OR +, EQUIVALENCE =, etc)

boolean algebra axioms

algebraic identities of AND *

algebraic identities of OR +

demorgan’s thm

logic gates

minterms 

minterm: one product term functions 

• notice how each minterm contains all of the input variables once

• notice how each minterm only has one true entry (the true entry corresponding to the boolean values that would make the product term true)

canonical sum of products (SOP)

• completely unsimplified SOP

• each minterm in the function expression contains all the vars (A, B, C) → like A’B’C..

karnaugh map

graphical representation of a truth table of a logic function

• see “Summary of Chapter 1 - Digital Logic Circuit” note, page 1

karnaugh map - implicant

• product/minterm term that, if equal to 1, implies f (function output) = 1

• from the k-map’s pov, an implicant is a rectangular group of 1, 2, 4, 8 adjacent boxes (powers of 2’s)

karnaugh map - prime implicant

• an implicant that cannot be completely covered by another implicant (the largest possible rectangle that can cover the adjacent 1’s)

karnaugh map - essential prime implicant 

• a prime implicant that contains at least one “1" that no other prime implicant covers

demorgan’s thm with logic gates

NAND implementation of function in SOP form

see “Summary of Chapter 1” notes, page 2

NAND implementation of AND, OR and NOT

see “Summary of Chapter 1” notes, page 2

combinational circuit: defn

• set-up of a number of connected logic gates that implement the logic function between n input vars and m output vars

• time-INDEPENDENT, output does not depend on any other factor other than the inputs

• output is “recomputed” as soon as a change in the input(s) occurs and is presented as the output with a time delay

combinational circuit: visual

combinational circuit: design procedure

to design a combinational circuit:

1. define the problem and the inputs/outputs

2. assign variables (like A, B, x, y, et cetera) to inputs and outputs

3. derive the truth table defining the relationship between the inputs and the outputs → ask “which values of the inputs make the outputs 1?”)

4. obtain the SIMPLIFIED boolean expression for EACH output var

5. sketch the logic diagram of the circuit with the appropriate logic gates

6. see “Summary of Chapter 1” notes, page 3 for an example

sequential circuit: defn

• output of a sequential circuit is the logic function of the present state of external inputs

• it’s like a combinational circuit with memory of the previous state of inputs

• performs like a “feedback loop”

two types of sequential circuits

• synchronous → operate at time events determined by an additional control signal called “clock”

• asynchronous → operate at time events determined by a change in the input

sequential circuit: visual

state diagram

a graph connecting all possible states of a sequential circuit (could be written in binary, decimal, hex, octo, et cetera)

• each state points to their next state

• see image for example

two types of MEMORY elements

• latches (SR, D)

• flip-flops (D, JK, SR, T)

each latch/ff can be created from other latches/ff’s (ex: a JK ff can be made with a D ff)

how clock (the control signal) triggers a change in outputs 

• the outputs respond to changes in the input only when the clock pulse is at a specific edge (negative edge, positive edge) → “edge-triggered”

positive edge vs negative edge of a clock pulse

sequential circuit: design procedure

1. analyze the problem and create state diagram showing all the states that the finite state machine can be in (sequential circuits have a finite number of possible states) and how each state transitions from one to the other.

2. make a state table based on the state diagram showing all possible PRESENT STATES, the NEXT STATES that would proceed the present states, and the trigger of the present state to the next state

3. state assignment → remember that for n bits, you need n flip-flops to hold the bits

4. refer to the excitation tables of the specific flip-flop you are using (D, T, SR, JK) to fill in the inputs (0,1,X) you need for each ff input to transition to the next state

5. derive logic functions for each ff input using k-maps

6. Sketch the circuit

SEE “Summary of Chapter 1” NOTES FOR AN EXAMPLE (page 4)

sequential circuit: visual example

• this is the implementation of a 4-bit counter implementation with JK ff’s

• a typical sequential circuit has logic gates (combination circuit segment) to transition the present states into next states AND a row of flip-flops (state register) for the memory segment of the sequential circuit

• clock trigger (control signal “CLK” at the bottom) “pushes” the next state bits into the flip-flops to be stored in the flip-flops

exclusive-or equivalency

A xor B = A’B + AB’