State Representations

Binary Counting vs. One Hot Encoding

Two of the extremes in state encoding are binary encoding (counting states from 0 to $n$) 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. A pseudo-code form of 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

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.

Provide rough guidance for when someone who wants to minimize space used may want to pick binary encoding.

And 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, 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

Estimate the propagation delay by considering the path from D through to Q, including one potential “loop” for each latch. Round that up to the nearest 100 and consider it to be a safe value for the clock cycle.

Test your work. Confirm that you can store both a 1 and a 0.

Describe any unusual behavior at the start of the simulation.

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}$

Test your estimate:

1. Create a test case that initializes the flip flop in the first 500 units of time. For example, include updates in both D and Clock that set the output to a known value.
2. After your setup phase, use an until clause on both D and Clock to wait until 500 units of time. For example, the clock may: start at 0, go to 100, go back to 0, and then 0 until 500 to wait (at value 0) until $t=500$.
3. Construct an experiment starting at $t=500$ to change the value of the flip flop. Confirm your $t_{cq}$ value.
4. Update your experiment: If it set Q to a 1 after time 500, change it to set it to a 0.

Are the $t_{cq}$ times for changing-to-1 and changing-to-0 the same or not? Explain the behavior and timing.

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.