Reference no: EM131317157

In this classic problem, you are to design a single finite-state machine S that will be connected in an arbitrarily long one-dimensional string as follows:

Each FSM in the string is connected by k wires to its left and right neighbors; the wires can carry information in both directions between each pair. All FSMs share a common clock and make state transitions on active edges based on their current state and signals from their left and right neighbors. Connections to the left and right ends are such that the leftmost and rightmost FSMs can recognize their special positions. Each FSM has a red light that is on only when the FSM is in a designated "fire" state; initially, the lights are all off. During some clock cycle, a start signal is applied to the inputs of the leftmost S module. The required behavior of the system is that the lights are all to remain off until some subsequent clock cycle, when all lights go on simultaneously and remain on. Note that the delay between the start signal and the "firing" of the FSMs can be arbitrarily long; it may, for example, depend on the number of modules in the string. However, all modules must be identical; their design (and the number of states) is independent of the length of the string. This is a challenging problem. Unless you are unusually ambitious, you should stop short of a detailed design, which is tedious; just develop a convincing argument that your approach will work.