State Representations

Binary Counting vs. One Hot Encoding

Two of the extremes in state encoding are binary encoding (counting states from 0 to $n-1$) and the one-hot encoding. Consider a Moore-style machine with 10 states, a single input named input, and a single output named output:

How many bits, $k$, are needed for a binary state encoding?

Assume that the output’s value depends on being in one of three specific states, either state 0, state 6, or state 9. In pseudo-code form this could be described as output = in_state_0 + in_state_6 + in_state_9. Provide the complete equation for the output in terms of the state bits, $S_{k-1} \cdots S_0$.

How many bits, $l$, are needed for a one-hot state encoding?

Provide the complete equation for the output in terms of the state bits, $S_{l-1} \cdots S_0$.

Stating the Abstract

There are two major elements involved in all state machines:

• Storing the state
• Computing the next state (the arcs in the state diagram), which often relies on some circuit to detect the current state. That is, it’s necessary to decode the state bits to clearly identify which state the machine is in. For example, if a binary encoding is being used there will probably need to be some circuit that identifies if the machine is currently in state 0 or state 1, etc. (That process is very comparable to the equations you created in the prior part).

Assume you have more generic problem with $n$ states. We would really like to be able to identify how complicated the circuit is likely to be for different state encoding options, like binary vs. one-hot.

Based on how both flip-flops are constructed and how states are detected, complete the table below. Come up with formulas that describe the likely minimum number of basic logic gates needed for each encoding. That is, count the basic logic gates (like AND, OR, NOR, NAND, but you can ignore invertors). For each:

1. How many 2-input gates are required to store the state if each D-Flip Flop uses this implementation?
2. How many gates are needed to “decode” the state. For example, use summaries in terms of $n$, like: “$log_2(n) \times$ 2-input gates” or $n \times n$-input gates”, etc..
3. Identify the likely minimum number of gates needed for a state machine.

Complete the Table (in terms of $n$, the number of states)

The total space taken to construct circuits will largely depend on the number and the width (number of inputs) of gates being used. Try to estimate how the space needed to construct the circuits will differ. For example, you may start with the assumption that a $j$-input AND takes $\frac{j}{2}$ times more space than a 2-input AND and express the total space taken in terms equivalent to the total space that would be taken by 2-input gates.

This is really taking the table above: 1) representing everything in terms of 2-input gates (if there was anything bigger) and then 2) combining the total for the “storage” and the “decoding” parts to be a rough estimate of the space needed.

Provide rough guidance for when someone who wants to minimize space used may:

a) want to pick binary encoding.

b) when binary encoding and one-hot encoding may use nearly identical amounts of space (using these assumptions and models of gates/flip-flops).

And, finally, c) for when one-hot encoding may use less space.

There’s often a tradeoff between efficiency, and the time and effort required to design, test, debug, and verify a systems. When or why may an encoding style be easier for design/test/debugging?

Flip-Flop Timing: Empirical Measurements

In class we constructed an SR Latch from cross-coupled NOR gates. Then stacked some AND gates in front of the SR Latch to make the D-Latch. We then used two D Latches in sequence to create a D Flip-Flop, which has much more precise control of when data is captured. The two D Latches use opposite phases of the clock: The first D-Latch is transparent when the clock is low and captures the data value when the clock level is high. The second D-Latch is the opposite: it is transparent when the clock is high and captures the value when the clock is low.

Construct the following D-Flip-Flop Model in JLS:

Test Your Flop Flop

Run a test with both D and Q at 0. Explain the behavior you see.

Revise your test with a “setup phase”:
1. Add the total propagation delay of all gates in the circuit and then round up to the nearest 100. Let’s call this $t_{max}$.
2. Set D to 0 at the start of the simulation.
3. Start the Clock at 0, change it to 1 at $t_{max}$, then change it back to 0 at $2\cdot t_{max}$

Now do a “test” that stores a 1 sometime after the setup phase (after $2 \cdot t_{max}$).

Revise your work to initially set the flip-flop to 1 (before $2\cdot t_{max}$) and have the test case store a 0 (after $2\cdot t_{max}$).

Estimating and Empirically Testing Parameters

Based on inspection of the circuit, find $t_{cq}$, The propagation delay from a rising edge on Clock until a change in Q.

Empirically Testing $t_{cq}$

Try multiple test cases to confirm your estimate:

1. Flip-Flop is initialized to 0 and then a 1 is stored.
2. Flip-Flop is initialized to 0 and then a 0 is stored.
3. Flip-Flop is initialized to 1 and then a 1 is stored.
4. Flip-Flop is initialized to 1 and then a 0 is stored.

What were the four $t_{cq}$ values you observed? Explain any differences with your initial estimate.

Empirically Finding Setup Times & Influences

It may help to sketch out timing signals on a graph for the following problems

A flip-flop’s setup time ($t_{setup}$) is the amount of time the D value must be stable before a clock cycle to reliably store a value. Update your previous test cases to:

1. Again, set Q to a know value and wait until 500 units of time.
2. Pick a time for a rising edge of the clock, like $t=700$.
3. Have D change values near the rising edge of the clock (and be stable for quite a while - you may want to use a for clause, like 1 for 100 to hold the signal). Experiment to identify how much time may be needed to reliably store the correct value. For example, change the point when D changes to be closer and closer to the clock edge until the value of D is no longer successfully stored.
4. As before, update your experiment: if the stored value was a 1, update it to store a 0 and see if the $t_{setup}$ is consistent.

Explain your results. Based on your testing what does $t_{setup}$ appear to be for this flip-flop model and why does this make sense?

Empirically Finding HOLD Times & Influences

A flip-flop’s hold time ($t_{hold}$) is the amount of time the D value must be stable after a clock cycle to reliably store a value.

Do a variation on the prior part to determine the hold time required for your flip-flop model.

Aperture Time

The aperture time is the total amount of time the D value must be stable. What is the default aperture time for this flip-flop in JLS?

Wrapping Up

If you have extra time and didn’t finish Studio 3A, spend any remaining time completing it.