Sequence Enumeration - Embedded.com

Sequence Enumeration



To read original PDF of the print article, click here.

Sequence Enumeration

Rob Oshana

Sequence enumeration is a technique for analyzing systems. It can be used to turn a complex set of requirements into an easily implemented state machine.

The criticality of correct, complete, and testable requirements is a fundamental tenet in software engineering. Both functional and financial success are affected by the quality of requirements. So what is a requirement? It may range from a high-level abstract statement of a service or of a system constraint to a detailed mathematical and functional specification. Requirements are needed for several reasons:

  • To specify external system behavior
  • To specify implementation constraints
  • To serve as reference tool for maintenance
  • To predict future changes
  • To characterize responses to unexpected events

The system designer must understand requirements and be able to organize them. A technical background and an understanding of the user are both required. Before design can start, each requirement must be understood in terms of significance and priority in the solution strategy. Because both the developer and the customer must understand the requirements, they are usually written in natural language. But natural language is a poor medium for communicating requirements.

The use of natural language to specify complex requirement has at least two problems: those of ambiguity and inaccuracy. Many words and phrases have dual meanings and can be altered depending on the context in which they are used. A word that means one thing to one person can mean something entirely different to someone else. For example the interpretation of the word “bridge” can be completely different depending on whether you are a dentist, a civil engineer, an electrical engineer, or someone who just retired early.

Other disciplines require a more exact language for communicating specifications. For example, an architectural blueprint or a circuit board schematic are formal specifications that define what is needed but not necessarily the implementation details of how to get there. Software requirements should be the same way. A software requirements specification should not contain implementation details. These specifications should describe in sufficient detail what the software will do, but not how. A good set of requirements should be:

  • Correct-it meets the need
  • Unambiguous-have only one possible interpretation
  • Complete-it covers all the requirements
  • Consistent-there should be no conflicts between requirements
  • Ranked for importance
  • Verifiable- a test case can be written
  • Traceable-referring to requirements should be easy
  • Modifiable-it should be easy to add new requirements

Trying to define a large multidimensional capability for a complex embedded system within the limitations of the linear two-dimensional structure of a document becomes almost impossible. At the other end of the scale, the use of a programming language is too detailed. This is nothing more than “after the fact specification” which is just documenting what was implemented rather than what was requiredDeveloping a good set of requirements to specify a system can be difficult. In many cases the stakeholders don't know what they really want. The various stakeholders also tend to express requirements in their own terms and may have conflicting requirements that need to be resolved. Organizational and political factors may also influence the system requirements. Requirements may also change during the analysis process as new stakeholders emerge. The term “requirements engineering” has emerged to address the transformation by which vague and, often unrelated, customer requirements are transformed into the detailed and precise requirements needed for system implementation.

Successful designs are usually the result of significant rethinking and reworking. Several iterations of design is the norm, rather than the exception. Design alternatives should be considered. In general, designs should get simpler rather than more complex.

It can be difficult to specify the total behavior of a complex system because of the total number of possible uses of the system. But this is precisely what needs to be done in order to ensure completeness and consistency in our designs.

The hard part is being able to determine all the possible types of interaction with the system. One common technique for describing the system behavior is use cases. Use cases are textual narrative descriptions of the processes in an enterprise or system. They are used to explore and elicit requirements and can help determine which types of interaction to expect between the actors (external stimuli to the system) and the system. But use cases may not always combine to describe complete and consistent behavior.

Use cases can be used to explore the problem domain and to perform front-end domain analysis. Other techniques can then be used to fully specify the solution strategy. One technique that has worked well in our embedded system project is called sequence enumeration.

Sequence enumeration
Sequence enumeration is a theoretically sound and highly practical approach to describing the external (or black box) behavior of a system. Sequence enumeration is a way of specifying and mapping stimuli and responses of an embedded system. This approach considers all permutations of input stimuli. Sequence enumerations consist of a list of prior stimuli and current stimuli as well as a response for that particular stimuli given the prior history. Equivalent histories are used to map certain responses. This technique maps directly to a state machine implementation. The strength of sequence enumerations is that the technique requires the developer to consider the obscure sequences that are usually overlooked.

Figure 1: Simple Soda Machine


Click on image to enlarge.

As an example, I will consider the simple soda machine shown in Figure 1. A set of natural language requirements for this system is shown in Figure 2.

  1. The soda machine will produce a soda after 75 cents has been entered. The machine will only accept quarters.
  2. When the “Change Return” button is pressed, the available change in the input tray is returned.
  3. When there is no more soda in the machine, the “Sold Out” light will be illuminated.

Figure 2: Natural language requirements for the soda machine

To start with, a use case can be developed that describes one type of interaction with the system. A use case is a story about the usage of a system told from the end user's perspective. It consists of:

  • Preconditions-what must be available and done before the performance of the use case
  • Description-the story
  • Exceptions-exceptions in the normal flow of the story
  • Illustrations-figures to help understand the use case
  • Postconditions-the state of the system and actors after the use case has been performed

Use cases are desirable because they:

  • Analyze and improve functional requirements
  • Model the functionality of the system as soon as possible
  • Allow the customer to understand the operation of the system

Use cases must specify the most important functional requirements. A use case depicts a typical way of using the system but nothing more. In general, a use case should not try to define all possible ways of performing a task. Certain important exception conditions are described in “secondary” use cases or in exceptions within a use case. A simple use case for the soda machine can be as follows:

  • Precondition: Machine is ON and there is one soda in the machine
  • Description: A user walks up to the machine and deposits two quarters. He then presses the soda button. Nothing comes out because three quarters are required to get a soda. The user hits the change return to get his change. He then leaves to get another quarter. He returns with three quarters, deposits the quarters and selects a soda. This is the last soda in the machine so the “Sold Out” light comes on
  • Exceptions: None
  • Postconditions: There is no soda left in the machine and the “Sold Out” light is ON

Other use cases can be developed depending on the various business cases for this system. Once we have a general idea of what the system should do (something use cases are helpful for determining), we can then perform a sequence enumeration to more completely map all possible combinations of stimuli to responses.


Click on image to enlarge.


Click on image to enlarge.

To start with, it's a good idea to represent the system as a “black box,” showing the stimuli and the responses that are possible. The black box for the soda machine is shown in Figure 3. Table 1 lists the abbreviations used for each stimulus and response in the system enumeration.


Click on image to enlarge.

A sequence enumeration can be done in a spreadsheet. Enumeration starts by evaluating a single stimulus to the system and determining the appropriate response for each stimulus. Table 2 shows the first level enumeration for the system. As the table shows, each stimulus is separately evaluated. The table shows that if the Initialize stimulus (I) occurs (the power is applied and the system is initialized), the Power on light response (LIGHT) is produced, as required by requirement 4. If any other stimulus occurs, the response is null and it is considered an illegal sequence (you cannot select a soda if the power is not on, for example). The result from performing this first level enumeration is that the system must be initialized (the I stimulus has occurred) before anything else can be done. We must remember that this event occurred. Therefore, the I stimulus is used in the next level of enumeration.


Click on image to enlarge.

The level 2 enumeration uses all stimulus sequences that were not illegal or did not have a shorter equivalent sequence in the previous enumeration level than the first stimulus in the sequence. So, as Table 3 shows (lines 6 through 10), the first stimulus is I and the second stimulus is an enumeration of each of the possible stimuli to the system).

As an example, line 6 states that if the system receives an Initialize stimulus (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 sequence 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 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.


Click on image to enlarge.

This process continues until all 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 terminates in lines 26 through 30. Line 28 describes the condition where the Initialize stimulus, followed by three Quarter stimuli, followed by a Soda Select stimulus (I Q Q Q SS) will produce the Soda Deposited response (SD). This sequence also has 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 effectively starts again from the Initialize state.

  • D1: Selecting a soda before the correct change has been entered will result in no response from the soda machine.
  • D2: A “Sold Out” stimulus before the last soda is selected will cause the “Sold Out” light
  • to be illuminated.
  • D3: Whenever the “Sold Out” light is illuminated, any change deposited into the machine will automatically be returned.
  • D4: The soda select button will be ignored whenever the “Sold Out” light is on or whenever correct change has not been received.

Figure 4: Derived requirements for the soda machine

You may have noticed that the enumeration tables have a “Requirement” column that is used to trace the requirement as we define the behavior. This is a simple easy way to trace all requirements to behavior. You will also notice the derived requirements (indicated as D1, D2, and so on). A derived requirement is a lower level requirement that is determined to be necessary for a higher level requirement to be met. In general, a derived requirement is more specific and directed toward some sub-element of the project. Derived requirements often occur through the process of analysis. The derived requirements for this system 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 considered, in effect, every possible combination of stimuli to the system for an infinite length of possible stimuli. This ensures that we have considered every possible behavior condition. The requirement trace also ensures that we have covered all possible requirements
  • Consistent: because we have considered every combination of stimuli only once, we have ensured consistency. In other words we have not mapped a stimuli combination to more than one possible output sequence
  • Correct: the mapping from stimuli to responses have been properly specified in the judgement of the domain expertsImplementation

Canonical Sequences (five states)II QI SOI Q QI Q Q Q

Figure 5: Canonical sequencesfor the soda machine

State DataSYS_STATUS	Bool {ON, OFF}COIN_COUNT	Enum {0, 1, 2, 3}SODA_AVAIL	Bool {TRUE, FALSE}

Figure 6: State data for the soda machine

Once the sequence enumeration is complete, it is a fairly 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 illegal and do not have equivalent sequences. These are referred to as the canonical sequences. In Table 4, these are lines 1, 7, 10, 12, and 22. These are also listed in Figure 5. State data can be invented that will encapsulate the behavior described in these canonical sequences. Figure 6 shows the state data that I invented to encapsulate this system's behavior.


Click on image to enlarge.

Based on the state data and the behavior described by the enumeration sequences, the state machine for the soda machine is easily produced (Figure 7). Notice the five states corresponding to the five canonical states produced during the enumeration process.The technique of sequence enumeration can be scaled to larger systems by using abstractions for the stimuli 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 done is define a rule for a function for this software system. This process is rooted in the mathematics of function theory, which maps a domain (valid inputs or stimuli to a system) to a range (the correct responses) within a co-domain (all possible responses). See Figure 8.


Click on image to enlarge.

Referring back to the use case described earlier, you will notice that we can map the behavior from this use case to parts, but not all, of the enumeration. Certain parts of the enumeration describe the story being told by the use case. The sequence enumeration goes a step further, defining the complete behavior that was originally described in the story told in the use case. This is where the synergy between use cases and sequence enumeration becomes apparent. Use cases and scenarios are an effective tool to decide what we have to do for the various stakeholders of the system. The sequence enumeration drives home the completeness and consistency that will give your developers a clear picture of what to do in all circumstances of use, as well as resolve any inconsistencies between the stakeholders.

Rob Oshana is an engineering manager in the Software Development Systems group at Texas Instruments. He has over 18 years of experience in the management and development of real-time embedded systems. He also teaches requirements and design courses at Southern Methodist University. His e-mail address is .

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.