Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 125 of 229

The technique of sequence enumeration can be scaled to larger systems by using abstractions for the stimuli and responses. Canonical Sequences (five states) I IQ I SO IQQ IQQQ or does not have a shorter equivalent sequence must be remembered and used in the next enumeration level. In this example, lines 7 and 10 must be remembered. This process continues until all FIGURE 6 State Data SYS_STATUS COIN_COUNT SODA_AVAIL Bool {ON, OFF} Enum {0, 1, 2, 3} Bool {TRUE, FALSE} meration of each of the possible stim- uli to the system) . As an example, line 6 states that if the system receives an Initialize stimu- lus (I) , followed by another Initialize stimulus, the system reacts as if only a single Initialize stimulus was applied. In this case, the Equivalence column is set to I to indicate that the sequence I I is equivalent to the sorter sequence I in terms of behavior. Line 7 describes that the equence of Initialize followed by the depositing of a single quarter (I Q) produces no response and has no equivalent sequence (another piece of behavior that the system needs to remember). Line 8 describes that the sequence of Initialize followed by a Soda Select stimulus (SS) produces no response and is equivalent to the sequence I in terms of behavior. In other words, if you press the soda select button after the power is applied and you have not entered the correct amount of money, your request will be ignored. Each sequence in this level that is not illegal behavior is eventually mapped to a shorter equivalent sequence (it must always end or the software system may never terminate). Table 4 shows the complete enumeration for the soda machine. The process finally tenni- nates in lines 26 through 30. Line 28 describes the condition where the Initialize timulus, followed by three Quarter stimuli, followed by a Soda Select stimulus (I Q Q Q SS) will pro- duce the Soda Deposited response (SD). This seq uence also h as an equivalent state of I, meaning that after a soda is deposited, the system does not need to remember that a soda has been deposited and effec- tively starts again from the Initialize state . You may have noticed that the enu- meration tables have a "Requirement" column that is used to trace the requirement as we define the behav- ior. This is a simple easy way to trace all requirements to behavior. You will also notice the derived requirements (indi- cated as D1, D2, and so on). A derived requirement is a lower level require- ment that is de(ermined to be neces- sary for a higher level requirement to be met. In general, a derived require- ment is more specific and directed toward some sub-element of the pro- ject. Derived requirements often occur through the process of analysis. The derived requirements for this sys- tem are shown in Figure 4. A couple of important conclusions ca be drawn from this process. We can say that this process produces a set of behaviors, that is: • Complete: the enumeration con- sidered, in effect, every possible 124 SEPTEMBER 2000 Embedded Systems Programming combination of stimuli to the sys- tem for an infinite length of possi- ble stimuli. This ensures that we have considered every possible behavior condition. The require- ment u·ace also ensures that we have covered all possible require- ments • Consistent: because we have con- sidered every combination of stim- uli only once, we have ensured con- sistency. In other words we have not mapped a stimuli combination to more than one possible output seq uence • Correct: the mapping from stimuli to responses have been properly specified in the judgement of the domain experts Implementation Once the sequence enumeration is complete, it is a fa irly simple step to develop the finite state machine that represents the specified behavior. To determine the number of states in the finite state machine, simply count the lines of enumeration that are not ille- gal and do not have equivale nt sequences. These are referred to as the canonical sequences. In Table 4, the e are lines 1, 7, 10, 12, and 22. These are also listed in Figure 5. State data can be invented that will encap- sulate the behavior described in the e canonical sequences. Figure 6 shows the state data that I inven ted to encap- sulate this system's behavior. Based on the state data and the behavior described by the enumera- tion sequences, the state machine for the soda machine is easily produced (Figure 7). Notice the five states cor- responding to the five canonical states produced during the enumeration process. The technique of sequence enu- meration can be scaled to larger sys- tems by using abstractions for the stim- uli and responses. These abstractions can be decomposed and expanded at lower levels of behavior definition, as more and more details of the system are exposed. In effect, what we have

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10