Notes

pretty sure multilevel is slower.
 the more levels, the slower?
 so better to flatten out by repeating the same calculations?
 that’s basically the idea behind carrylookahead adders right?

Decimal to binary conversion.

Binary logic
 Logic variables: similar to algebraic, but only two values (0, 1).
 Logic functions:
 Similar to algebraic functions, but return either 0 or 1.
 Represented using algebraic expressions, truth tables and circuits.
 Truth table is a unique representation, while there may exist multiple algebraic/circuit representations.
 Logic operators:
 AND: $x⋅y$
 OR: $x+y$
 NOT: $xˉ,x′$

Emulating logic gates using electrical circuits: everything’s implemented physically after all.
 AND: switches is series. All switches must be closed for the circuits to be closed.
 OR: switches in series. Any one switch needs to be closed for the circuit to be closed.
 NOT: switch in parallel to the resistor such that when the switch is closed, it shortcircuits so that the resistor (light) does not turn on.

$2_{n}$ rows in a table with $n$ input variables.

Boolean algebra: similar but kinda different to regular algebra.

Easy to convert function representation to truth table, but we wanna do the other way too.
Synthesis of circuits
Converting a truth table to algebraic expression. So we can find the most efficient circuits which still does the same thing as the original function.
 Circuit efficiency/cost: number of (nontrivial) logic gates + number of inputs.
 Minterms $m_{i}$:
 It is the product of a series of input variables (or their complements) that evaluates to 1 for that row.
 Each minterm expression is 1 only for that row (that combination of inputs).
 Maxterms $M_{i}$:
 Opposite (include variable if 0, include complement if 1) and sum them all up.
 Maxterm expression is 0 only for that row.
 $m_{i}′=M_{i}$  both terms are true together.
 Synthesizing circuits: canonical sum of products (SOP)
 Take logical OR of all minterms where the actual function evaluates to 1.
 This is the canonical SOP; for it to be canonical, the RHS must only contain the sum of minterms, no other operator.
 If there’s a simpler expression, we can simplify into that. Hence reducing our circuit cost.
 Starts with a layer of NOTs, then ANDs, then OR.
 Synthesizing circuits: canonical product of sums (POS)
 Logical AND of all maxterms where function evaluates to 0.
 Starts with a layer of NOTs, then ORs, then AND.
 How synthesizing works:
 Each minterm (or maxterm) corresponds to a specific combination of inputs that evaluate to 1 (or 0 for maxterm).
 When we take the OR, we are combining all these combinations. Each segment of the combination is triggered only for that row. We exclude the rows where it’s f = 0 cuz we don’t want to trigger those rows.
 When we take AND of the maxterms, the product ensures that the expression will become 0 when any of the f = 0 rows is triggered. We don’t take maxterms when f = 1, cuz then we want it to be 1.
 Implicant: product term that causes function to be 1 $(p⟹f)$
 Eg: terms in a SOP are implicants.
 Prime Implicant: if an implicant cannot be merged with another implicant which has a fewer number of literals (more squares in kmap) in the product term, then it is a prime implicant.
 If the meaning of the implicant would change if any literal is deleted, then it is a prime implicant.
 Cover: set of implicants that account for all evaluations that give f = 1.
 The set of minterms where f = 1 is a valid (but inefficient) cover.
 The set of all implicants is a good cover.
 The set of only prime implicants is lowest cost cover.
 Essential Prime Implicant: a prime implicant which covers a square (kmap) which no other prime implicant is able to.
 Without EPI, the meaning of function would change.
 Minimizing Cost: set of EPIs + set of nonessential PIs to cover all evaluations of $f$.
Tabular Method
 Write minterms in a table, order them based on number of bits in each minterm, so that similar bits (Hamming distance) end up close.
 Then compare between (grouped) rows
Combinational Logic
Multiplexers
 Kinda like if statements but implemented in hardware.
 The ith input is redirected as the output.
 i is the binary encoded decimal inputted via the select pin(s).
Shannon’s Expansion
 A mathematical way to represent a logic function using smaller functions with preset values.
Decoders

Only one output is active at a time.

The ith output line is activated.

i is the binary encoded decimal inputted via the input pins.

Used in memory blocks.
ROM based synthesis
 Use decoders to select memory blocks.
 Store desired function output in memory blocks.
 So based on the input, system will select n return certain memory blocks, those blocks contain the actual function output.
DeMultiplexers
 Opposite of multiplexers.
 Works somewhat similar to decoders.
 Connects input to a specific output line.
 With decoders that output line will always be 1.
 For demux the selected output line depends on the input.
Encoders
 Opposite of decoders.
 Only one input is active.
 The ith input line is activated.
 Then i in binary encoded decimal is outputted.
 Multiple outputs are active.
Priority Encoders
 Similar to encoders.
 But multiple inputs can be high.
 The input with most priority is considered.
 Highest priority = most significant input (?).
Numeric Circuits
 Sign + magnitude representation.
 1’s complement  flip everything.
 Equivalent to subtracting the number from $2_{n}−1$
 2’s complement  flip everything and add one.
 Equivalent to subtracting the number from $2_{n}$.
Operations on 2’s complements
 We use 2s cuz everything works naturally here.
 Overflows works to our advantage here.
 When we have to add two numbers where the positive is bigger than the negative, we have to somehow get rid of the sign bit.
 Because of the way 2s complement works, the carry from the lower bits ripples into the sign bit, overwriting it–beautifully making it a positive number.
 We just have to ignore the carryout from the sign bit, which is easy cuz sign bit is MSB, we have no more bits to store the carry out of the sign bit.
 So carryout from the lower bits ripples into the sign bit, overwriting it appropriately.
Arithmetic Overflow
 We allot a certain amount of space for a number, say 16 bits.
 While doing operations on the number, we may end up with a number that requires more spaces to be represented.
 We don’t have enough bits to represent it, we have overflow.
 The overflowed bit is ignored, hence the value we end up storing/returning is not the actual result of the computation.
Detecting overflows
 All that’s valid, but how do we detect overflow?
 The two cases where overflow occur:
 Adding two positives, the result ends up negative cuz the magnitude bits overflow into the sign bit, setting it 1.
 The sign bits are originally 0, hence the overflow from the magnitude bits is absorbed by the sign bit.
 Adding two negatives, the result ends up positive cuz the magnitude bits overflow into the sign bit, overwriting it.
 Here both the sign bits are 1, so the sign bit itself may end up overflowing, resetting it to 0. Even though the result is obv negative and hence requires a sign bit.
 Adding two positives, the result ends up negative cuz the magnitude bits overflow into the sign bit, setting it 1.
 In the case of opposite sign this doesn’t happen:
 When + > : the carry out from the lower bits is good because it overwrites the sign bit. Here the overflow from the sign bit is ignored.
 When  > +: theres no carry out from the value bits, hence the sign remains negative.
 So basically actual overflow happens the carryin and carryout of the sign bit are different.
 $overflow=carry in⊕carry out$ of sign bit
Half Adder
 Looking at the truth table of addition we can see that the sum bit is the xor of the two input bits and the carry bit is the and of the two input bits.
 Does not take carry input, hence halfadder. Can only be used to sum the LSB.
Full Adder
 Similar to HA, but takes in a
carry_in
input hence this can be used to sum any bit position.  Can be implemented using two HAs + gates.
RippleCarry Adder
n
FAs chained together. The carry out from the previous stage is the carry in for the next stage.
 Calculation of the nth bit (and it’s carry) relies on the carry out of the previous bit. This makes it slow since the bits have to ripple through the segments.
CarryLookahead Adder
 We use an alternate circuit to calculate the carry out of the previous stage instead of relying on the previous stage FA.
 The bit pair generates if both the bits are 1. This is called generate cuz this will generate a carry out whether or not there is a carry in. $g_{i}=x_{i}⋅y_{i}$
 The bit pair propagates the previous carry if one of the bits is 1. $p_{i}=x_{i}⋅y_{i}$
 These two contribute to the net carry out of the $ith$ stage: $c_{i+1}=g_{i}+p_{i}⋅c_{i}$
 The advantage over ripple adder comes in when we expand each of the previous carryins.
 So the carry of each stage can be calculated in parallel without waiting for the previous stage to arrive.
 Each of the carryins is basically a two level expression: OR of ANDS.
 Constant time (ignoring wire delay, fan in issues) since each carry goes through the same number of gates.
Sequential Logic
 Has a memory/storage element to keep track of state.
 State influences circuit output.
 Uses clock.
Basic Latch with NAND
 Recursion in hardware!?
 Two NANDs crosscoupled.
 When both S and R are on, the circuit’s output is same as it was in the previous step. It shows memory.
 For nand, 0 is the dominant input. If an input is 0, the output will definitely be 1. When an input is 1, only then we actually have to check the value of the other input.
 So to determine the stable value of each input pair, we start with the 0 input, determine that gate’s output, then pass it into the other gate.
 When S = 1, Q = 1.
 When R = 1, Q = 0.
 When S = R = 1; no change.
 Since the nochange input for NAND latch is 11, it’s nicer to think of setting a value as turning off the R input; or turning off S for resetting an input. Small difference.
 S and R cannot both be equal to zero. Since 0 is the dominant input, both the nand gates will yield 1. But their input into the other gate will not change the outputs. Moving from 00 to 11, we cannot be sure of the circuit’s stable value.
Basic Latch with NOR
 The main difference is that the dominant input for nor is 1. If an input is 1, the output will be 0 regardless of the other input.
 Both set and reset cannot be 1.
 The actual problem arises when we turn off both S, R at the same time.
 When they were both on, both the Qa, Qb had output 0.
 So the other input of each of the NOR gates were 0 (nondominant ⇒ waits for the other input before outputting).
 This wasn’t a problem since the other inputs were both 1 (S and R).
 Now when both of them are off, each of the NOR gates is gonna produce a 1.
 Now each of these 1s is gonna be fed into each of the NOR gates.
 Since 1 is dominant, both the NORs are gonna flip to 0.
 If the propagation delay in all paths is equal, then the circuits will oscillate between 0 and 1.
 Basically, when 11→00, what should the circuit remember.
 NAND SR latches have the same problem, but we can’t go from 00 → 11.
Gated Latch
 Enable input.
 Only when enable is on do the S/R inputs to the latch set/reset the latch.
 ANDing the SR inputs with CLK.
 NANDing also works (cheaper), we just need to flip the order (cuz not and) and put S on the top instead of R.
Flip Flops
DFF
 Chain two gated latches where the clock to the second is inverted.
 Alt: use an edge detecter circuit with a regular gated latch to shorten the duration for which the enable signal is on, turning the leveltriggered latch into an edge triggered ff.
TFF
 When T = 0; Q(t+1) = Q(t)
 When T = 1; Q(t+1) = !Q(t)
JKFF
 When j = k ⇒ Tff and J = T
 When j != k ⇒ Dff and j = D
Finite State Machines  Synchronous Sequential Circuits
 We have some flip flops to represent state.
 We have some combinational logic to determine how the state is set and how it affects output.
Describing FSMs
 Spec.
 State diagram.
 State table.
 State assigned table.
 Logic expressions for output bits.
 Circuit.
Moore Machine
 A special case of an FSM where the output can be described as a function of current state.
 Since state changes (in a flip flop) are synchronous, the output of a Moore machine also changes at clock edges.
State Diagram
 Nodes represent circuits states and output at that state.
 Arcs represent transitions.
 $2_{n}$ arcs can originate from a node, where $n$ is the number of inputs.
Mealy Machine
 A special case of an FSM where the output can be describe as a function of current state and current input.
 While the state is clocked, the input can change anytime (asynchronously) and thereby changing the output of the FSM.
 Hence, a Mealy machine’s output can change asynchronously.
State Diagram
 The diagram is slightly different.
 Nodes still represent state.
 Since output depends on state and input, the arcs denote output.
 $f(s,i)$  each arc denotes the output at current input and current state (node from which the arc is originating).
Common between Moore and Mealy
State Table / Transition Table
 Basically tabulating the state diagram.
 Cols: present state, next state as a function of input, output.
State Assigned Table
 Assigning binary values to each state.
 We use this to then compute boolean expressions for the next state and output.
 We can choose what pattern of binary represents which state.
 This will change the logical expression and can result in a cheaper circuit.
Onehot State Encoding
 We use as many state variables as there are states in a circuit.
 Each state variable is on only for when it’s respective state is achieved.
 Requires more flip flops (state vars), but can be nice.
State Minimization
Two states are equivalent iff:
 For each input pattern, both states produce the same output.
 For each input pattern, both states produce the same (or equivalent) next state.
Partitioning

A partition is basically a grouping of states that we think may be equivalent.

States in different blocks are definitely not equivalent.

States in the same block may be equivalent (we’re testing if they’re equiv).

For each partition, we group them into blocks based on the output and the value of the next state.

Let’s say we have $(AB)(CD)$ and the next states: $A→B,B→C,C→D,D→C$ when input = 0.
 Here $C,D$ can be considered equivalent because their next states are also in the same block (i.e. equivalent). Since their next states are equivalent, these two remain in the same block.
 But for A→B; B → C; B, C are definitely not equivalent. Since the next states of A, B are not equivalent, A, B are also not equiv ⇒ (A)(B)(CD)

Here we have only evaluated the 0successors of each of the states, to be certain we must evaluate the 1successor of each state. (we may have even more successors based on the number of inputs: 00, 11, 01, 10).

Unspecified states are treated as don’t cares, so we may combine them with anything.
Choice of Flip Flops
 So far we’ve used DFFs to store state.
 It’s simple and obvious.
 The boolean expression for the input to FF (D) is the value we want to store in the FF.
 We can also use TFFs, JKFFs to store state.
 But the boolean expressions for the input into the FF will not be the value we wanna store.
 They’ll have to derived from the FF excitation table.
Excitation Table
 Expanded characteristic table, showing current inputs, state that excite the next outputs.
 Example excitation tables: 06  5 FF choices, page 3
 For JKFFs think of the shortform tables backwards:
 If current state = 0 and we want it to remain in 0:
 J = 0
 K = *
 if K = 0, then it’s a TFF with T = 0 (no flip); if K = 1, then it’s a DFF with D = 0
 If current state = 1 and we want it to flip to 0:
 K = 1
 J = *
 If J = 1, then we have a TFF with T = 1 (flip to 0); if J = 0, then we have a DFF with D = 0
 If current state = 0 and we want it to flip to 1:
 J = 1
 K = *
 If K = 1, then we have TFF with T = 1 (flip to 1); if K = 0, we have DFF with D = 1.
 If current state = 1 and we want it to remain 1:
 K = 0
 J = *
 If J = 1, then we have a DFF with D = 1; if J = 0, we have a TFF with T = 0 (no flip).
 If current state = 0 and we want it to remain in 0:
 Given the stateassignment table for a circuit, we derive the corresponding excitation table for a specific FF we choose.
 Basically, given current state and next state, we must figure out the inputs to the FFs such that the output matches next state.
 Figuring out the values, gives us the excitation table from which we can figure out the bool expressions for input into the FF.
Analysis of circuits
 Look at circuit diagram and figure out the rest.
 Start by writing the logic expressions for Y, z in terms of y and w.
 Then write the excitation table for the chosen FFs.
 Write the state assigned table from that.
Asynchronous Sequential Circuits
 No clock $⟹$ no flip flops
 Instead, we have combinational circuits with feedback path to emulate memory; similar to SR latches.
Assumptions
 Circuit eventually stabilizes.
 Fundamental mode:
 Inputs change only after circuit is stable.
 Only one input changes at a time.
 Delay element:
 All gates have some delay associated with them.
 For simplicity, we assume no gate delay.
 Instead, we collect all the delay into a single delay element, added to the feedback path.
 Useful to distinguish current and next state.
Analysis
 Look at circuit diagram and figure out the rest.
 Start by writing the logic expressions for Y, z in terms of y and w.
 For clarity, cut and insert a delay element into the feedback path(s).
 The right side is the current state ($y$), the left side is the input into the next state ($Y$).
 Then write the excitation/transition table.
 Write the flow table (state table) from that. Mark stable states.
State Reduction
Partitioning
 Similar to partitioning states in synch circuits.
 But here we also match unspecified states.
 For two states to be equivalent, any unspecified entries must be in the same next state column.
 Combining equivalent states does not get rid of don’t cares.
Merging
 We merge compatible state.
 Both states have same output wherever specified.
 For each input (one of the following needs to be true):
 Both states have the same successor.
 Both states are stable.
 The successors of one (or both) of the states is unspecified.
State Assignment in Asynchronous Sequential Circuits
 Hamming distance: number of bits that must be flipped to go between numbers. Less is better.
 Plot states as coordinates and try to keep each state transition on a single axis.
Method 1: additional states
 If transitions are diagonal, use additional states to transition through them.
 Those additional states are gonna be unstable for all inputs.
 We can leave some input combinations unspecified for the unstable state if we know that it’s not gonna be evaluated at that.
 The output of the unstable state must match the output of either the original or destination state.
Method 2: duplicate states
 If a state needs to be accessible (for transition) to multiple other states, clone this state so that it can connect to each of the states it needs to transition to/from.
Method 3: onehot encoding
 Each of our stable states in a onehot encoded state.
 We make up transition states that make it easy to transition between stable states.
Hazards
 Glitches during transition when the wrong output is generated by the circuit for a short period of time.
Static Hazards

When an output is supposed to be $C$ but flips to $Cˉ$ temporarily.

Happens when different parts of the circuit are combined to generate the net output.

When the output of two different states is same, but the subcircuits which ends up generating the output for each of the different states is different.

Propagation delays.

We fix it by ensuring adjacent 1s (for sop, and 0s for pos) have a shared expression.
Dynamic Hazards
 Using 2level circuits (without static hazards) prevents these.
 Hard to fix when more levels.