# Automatic Configurable Hardware Code Generation for Software-Defined Radios+
## 6 Hardware Model Using Finite State Machines
### FSM Optimizations
#### 6.2.1 First Optimization  
The first optimization (_opt1_) aims to reduce the number of FSM states by exploiting what we refer to as _gaps_ and the periodicity of the schedule in Figure 2. A gap occurs where there are stalls in the execution of a sink actor, more specifically, this refers to where the output signal \(v=0\) and there is no sink actor schedule (i.e., \(\sigma(i,j,v)=\emptyset\)). The gap can be of the three types namely a _startup gap_ (SG), a _firing gap_ (FG) and an _iteration gap_ (IG). The SG occurs during the startup phase of the system and is computed as \(SG=\sigma(0,0,v)\) where \(\sigma(0,0,v)\) is the initial schedule of the sink actor. For example, in Figure 2 the \(SG=3\) and this occurs from clock cycle 1 to 3. FG is the time delay between two consecutive sink actor firings in one iteration and is determined as \(FG=\mu(v)-ET(v)\) where \(\mu(v)\) is the sink actor scheduling period and \(ET(v)\) represents the _execution time_ of the sink actor. FG is 0 in Figure 2 as \(\mu(v)\) is equal to \(ET(v)\). Moreover, IG refers to the time delay between two consecutive sink schedule iterations and can be computed using \(FG=T-(\mu(v)\times(RV(v)-1))+ET(v)\) where \(T\) is the schedule period and \(RV(v)\) is the repetition vector of the sink actor. In Figure 2, IG is 2 and this occurs at clock cycles 14 and 15. All the three gaps SG, FG and IG use respective counters \(sgc\), \(fgc\) and \(igc\) to create a timing delay. Another feature of the schedule to exploit is the periodicity of the output signal \(r\). The periodic sequence of \(r\) has the length that is equivalent to \(ET(v)\) and is repeated \(RV(v)\) times per iteration. Instead of creating \(ET(v)\times RV(v)\) states needed where the sink actor does not stall (i.e., where it executes), we reduce this the number of states to \(ET(v)\) states by using a counter \(jc\) for sink actor firings in a schedule iteration. \(jc\) is incremented at the end of each firing, therefore, enabling firing states (i.e., where there are no gaps) to be iterated \(RV(v)\) times. The five types of states which are used to implement the optimized version of the FSM \(M_{opt1}\) in this section are tabulated in Table 1. \(s_{0}\) is the initial state, \(s_{sg}\) is the state type that is used for startup gap, \(s_{k}\) realizes periodic firing sequences as defined using a 1-periodic schedule, \(s_{fg}\) state type is used for firing gap and lastly the \(s_{ig}\) implements the iteration gap. Please note that \(s_{0}\) and \(s_{sg}\) occur in the startup phase while \(s_{k}\), \(s_{fg}\) and \(s_{sg}\) constitute the periodic phase of the FSM. Each state type is associated with four properties namely time delay, multiplicity, whether it has a loop transition or not and the condition for the next state transition. The time delay specifies the number of clock ticks it takes for the present state of the particular state type to execute before the transition to the next state. To describe the types of vectors (i.e., single or two-dimensional vectors containing values of the output signals) corresponding to states per state type, the multiplicity that takes three forms is used. \(1..1\) specifies a one-dimensional vector of exactly one-clock delay. \([0..*]\) denotes a two-dimensional vector of output signals which may either be zero or many in a single state type. The last multiplicity of the form \([1..*]\) specifies a two-dimensional vector of output signals with at least one value. Figure 8 shows a generalized and optimized FSM \(M_{opt1}\) which optimizes FSM \(M\) example in Figure 7. The optimized version \(M_{opt1}\) begins with the state type \(s_{0}\) where the output signals \(r\) and \(v\) of its sub-states are deasserted. In our example, the loop transition occurs once when \(v=0\) resulting in a two-dimensional vector (i.e., \([000]\)). When \(v=1\), the FSM changes the state type to \(s_{sg}\) which creates a time delay of \(SG\) clock cycles. The sub-states of this state type have the output signals \(r\) and \(v\) all set to 0.