Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

State Machine Theory

Field: Logic Design

Sequence of Expressions

Let SS be a finite set of states, II be a finite set of inputs, and Transition:S×I→S\text{Transition}: S \times I \to S be the transition function. The State Transition Diagram (STD) is formally defined by the tuple ⟨S,I,Transition⟩\langle S, I, \text{Transition} \rangle. A transition from state si∈Ss_i \in S to state sj∈Ss_j \in S upon input i∈Ii \in I is represented by the directed edge (si,i,sj)(s_i, i, s_j), such that sj=Transition(si,i)s_j = \text{Transition}(s_i, i). The set of all possible transitions is T={(si,i,sj)∣si,sj∈S,i∈I,sj=Transition(si,i)}\mathcal{T} = \{(s_i, i, s_j) \mid s_i, s_j \in S, i \in I, s_j = \text{Transition}(s_i, i)\}.
A Mealy Machine is defined by the tuple M=⟨S,I,O,s0,Transition,Output⟩M = \langle S, I, O, s_0, \text{Transition}, \text{Output} \rangle, where SS is the set of states, II is the input alphabet, OO is the output alphabet, s0∈Ss_0 \in S is the initial state, Transition:S×I→S\text{Transition}: S \times I \to S defines the next state, and Output:S×I→O\text{Output}: S \times I \to O defines the output. The output oo generated upon transitioning from state ss with input ii is given by the function: o=Output(s,i)o = \text{Output}(s, i)
A Moore Machine is defined by the tuple M=⟨S,I,O,s0,Transition,Output⟩M = \langle S, I, O, s_0, \text{Transition}, \text{Output} \rangle, where SS is the set of states, II is the input alphabet, OO is the output alphabet, s0∈Ss_0 \in S is the initial state, Transition:S×I→S\text{Transition}: S \times I \to S defines the next state, and Output:S→O\text{Output}: S \to O defines the output. The output oo generated upon reaching state ss is solely dependent on the current state: o=Output(s)o = \text{Output}(s)
The state machine behavior is defined by the transition function δ:S×I→S\delta: S \times I \to S and the output function λ:S×I→O\lambda: S \times I \to O. The State Table Representation systematically maps the input pair (s,i)(s, i) to the resulting state s′s' and output oo. This mapping is formalized as: StateTable(s,i)=(s′,o)\text{StateTable}(s, i) = (s', o) where s′=δ(s,i)s' = \delta(s, i) and o=λ(s,i)o = \lambda(s, i). The table structure is a set of ordered quadruplets: Ttable={(s,i,s′,o)∣s∈S,i∈I,s′=δ(s,i),o=λ(s,i)}\mathcal{T}_{table} = \{(s, i, s', o) \mid s \in S, i \in I, s' = \delta(s, i), o = \lambda(s, i)\}.
Let S={s1,s2,…,sn}S = \{s_1, s_2, \dots, s_n\} be the set of states, and I={i1,i2,…,im}I = \{i_1, i_2, \dots, i_m\} be the set of inputs. The next state variables Snext=⟨snext,1,snext,2,…,snext,n⟩S_{next} = \langle s_{next, 1}, s_{next, 2}, \dots, s_{next, n} \rangle are defined by a set of Boolean equations derived from the transition function δ:S×I→S\delta: S \times I \to S. For each state variable snext,ks_{next, k}, the equation is: snext,k=⋁j=1n⋁l=1mMk,j,l AND (sj AND il)s_{next, k} = \bigvee_{j=1}^{n} \bigvee_{l=1}^{m} \text{M}_{k, j, l} \text{ AND } (s_j \text{ AND } i_l) where Mk,j,l\text{M}_{k, j, l} is the Boolean value (1 or 0) indicating if the transition from state sjs_j to sks_k occurs upon input ili_l. This is often written compactly as snext,k=fk(s1,Input,s2,Input,...)s_{next, k} = f_k(s_1, \text{Input}, \text{s}_2, \text{Input}, \text{...}).