My proposal for an ultra compact 4-bit FSM fitting in one Spartan-6 CLB only, by using dynamic reconfiguration. The overall state machine being itself dynamically reconfigured, allowing to create or remove states, or change transitions or state output...
Important limitation: so as to make it fit in one CLB only, the current state feedback is reduced from 4 bits to 2 bits, hence allowing autonmous (reconfiguration-free) processing among 4 states only. When a state ouside the 2-bit range is reached, the output signal ready goes to low, and a reconfiguration of the input logic and the state encoding is required.
In this example state machine, the FPGA configuration would only be valid for 4 active states and 12 exit states at a time. Once an exit state is reached, e.g., 0111, the state machine is not ready anymore and requires a dynamic partial reconfiguration. In this case the entry state could be reinitialized to 0000 (even though it is not mandatory) as shown in this example.
Advantages of this solution
Since each new 4-state FSM is reconfigured from "outside", the overall state machine can have the following features:
- be generated on-the-fly,
- be adaptative and change over time, allowing try-and-error heuristic strategies
- have more than 16 states and be infinite
How the 4-state FSM "transition" would work
When the ready signal goes to low, the state machine should not be used anymore since the transition logic (input logic) is missing for the current state. Using partial reconfiguration, the following blocks have to be updated (the letters in bold refer to circled locations in the first drawing):
- At C, the interconnection network is temporarily modified to route the current state 4-bit value as output (remplacing the actual output). The reconfiguration agent can then read the current state, in this example, 0111, and the interconnection network is configured back to the initial routing (with output register as output).
- A and D LUT equations are updated according to the new 4-state FSM.
- E can be updated if the overall state machine has more than 16 states.
- if the initial state is not the same as the previous 4-state FSM, B initial state (on reset) is updated.
- if the initial state is different from the current value, a "slice reset" is triggered.
The ready signal goes to low, and processing can be resumed.
Note: if the 4 active states always remain 0000, 0001, 0010, and 0011, then the current state encoding LUT (at D) could be dropped, and the unknown state detector would just be an OR gate between the two highest bits of the current state register.
By using several CLB (each containing one chunk of 4 states of the overall state machine) acting as a kind of "buffer", the reconfiguration time penality could be reduced or even hidden in best case.