Picking the right system design methodology for your embedded apps: Part 2 - Embedded.com

Picking the right system design methodology for your embedded apps: Part 2

Before designing a system, we need to know what we are designing. In this context, the terms “requirements” and “specifications” are used in a variety of ways – some people use them as synonyms, while others use them as distinct phases. They are used here to mean related but distinct steps in the design process.

Requirements are informal descriptions of what the customer wants, while specifications are more detailed, precise, and consistent descriptions of the system that can be used to create the architecture. Both requirements and specifications are, however, directed to the outward behavior of the system, not its internal structure.

The overall goal of creating a requirements document is effective communication between the customers and the designers. The designers should know what they are expected to design for the customers; the customers, whether they are known in advance or represented by marketing, should understand what they will get.

We have two types of requirements: functional and nonfunctional. A functional requirement states what the system must do, such as compute an FFT. A nonfunctional requirement can be any number of other attributes, including physical size, cost, power consumption, design time, reliability, and so on. A good set of requirements should meet several tests:

Correctness: The requirements should not mistakenly describe what the customer wants. Part of correctness is avoiding over-requiring—the requirements should not add conditions that are not really necessary.

Unambiguousness: The requirements document should be clear and have only one plain language interpretation.

Completeness: All requirements should be included.

Verifiability: There should be a cost-effective way to ensure that each requirement is satisfied in the final product. For example, a requirement that the system package be “attractive” would be hard to verify without some agreed upon definition of attractiveness.

Consistency: One requirement should not contradict another requirement.

Modifiability: The requirements document should be structured so that it can be modified to meet changing requirements without losing consistency, verifiability, and so forth.

Traceability: Each requirement should be traceable in the following ways:

1) We should be able to trace backward from the requirements to know why each requirement exists.

2) We should also be able to trace forward from documents created before the requirements (e.g., marketing memos) to understand how they relate to the final requirements.

3) We should be able to trace forward to understand how each requirement is satisfied in the implementation.

4) We should also be able to trace backward from the implementation to know which requirements they were intended to satisfy.

How do you determine requirements? If the product is a continuation of a series, then many of the requirements are well understood. But even in the most modest upgrade, talking to the customer is valuable. In a large company, marketing or sales departments may do most of the work of asking customers what they want, but a surprising number of companies have designers talk directly with customers.

Direct customer contact gives the designer an unfiltered sample of what the customer says. It also helps build empathy with the customer, which often pays off in cleaner, easier-to-use customer interfaces. Talking to the customer may also include conducting surveys, organizing focus groups, or asking selected customers to test a mock-up or prototype.

Developing more formal system specifications
Available to the embedded systems developer are a number of advanced techniques for formal system specification. They fall into two broad categories: (1) control-oriented specification languages familiar to embedded systems developers such as the SDL Language, statecharts, and AND/OR tables; and (2) advanced system specification methodologies such as those used in safety-critical systems design.

An example of a widely used state machine specification language, the SDL Language for specifying control in UML was developed by the communications industry for specifying communication protocols, telephone systems, and so forth.

As illustrated in Figure 9.6 below , SDL specifications include states, actions, and both conditional and unconditional transitions between states. SDL is an event-oriented state machine model since transitions between states are caused by internal and external events.

Figure 9.6: The SDL specification language

Other techniques can be used to eliminate clutter and clarify the important structure of a state-based specification. The Statechart is one well-known technique for state-based specification that introduced some important concepts.

The Statechart notation uses an event-driven model. Statecharts allow states to be grouped together to show common functionality. There are two basic groupings: OR and AND. Figure 9.7 below shows an example of an OR state by comparing a traditional state transition diagram with a Statechart described via an OR state.

Figure 9.7: An OR state in Statecharts.

The state machine specifies that the machine goes to state s4 from any of s1, s2, or s3 when they receive the input i2 . The Statechart denotes this commonality by drawing an OR state around s1, s2, and s3 (the name of the OR state is given in the small box at the top of the state).

A single transition out of the OR state s123 specifies that the machine goes into state s4 when it receives the i2 input while in any state included in s123 .The OR state still allows interesting transitions between its member states. There can be multiple ways to get into s123 (via s1 or s2 ), and there can be transitions between states within the OR state (such as from s1 to s3 or s2 to s3 ).The OR state is simply a tool for specifying some of the transitions relating to these states.

Figure 9.8 below shows an example of an AND state specified in Statechart notation as compared to the equivalent in the traditional state machine model. In the traditional model, there are numerous transitions between the states; there is also one entry point into this cluster of states and one exit transition out of the cluster.

Figure 9.8: An AND state in Statecharts

In the Statechart, the AND state sab is decomposed into two components, sa and sb. When the machine enters the AND state, it simultaneously inhabits the state s1 of component sa and the state s3 of component sb . We can think of the system's state as multidimensional. When it enters sab, knowing the complete state of the machine requires examining both sa and sb .

The names of the states in the traditional state machine reveal their relationship to the AND state components. Thus, state s1-3 corresponds to the Statechart machine having its sa component in s1 and its sb component in s3 , and so forth. We can exit this cluster of states to go to state s5 only when, in the traditional specification, we are in state s2-4 and receive input r .

In the AND state, this corresponds to sa in state s2, sb in state s4 , and the machine receiving the r input while in this composite state. Although the traditional and Statechart models describe the same behavior,each component has only two states,and the relationships between these states are much simpler to see.

Another state machine format, the AND/OR table , can be used to describe similar relationships between states. An example AND/OR table and the Boolean expression it describes are shown in Figure 9.9 below .

Figure 9.9: An AND/OR table

The rows in the AND/OR table are labeled with the basic variables in the expression. Each column corresponds to an AND term in the expression. For example, the AND term (cond2 and not cond3 ) is represented in the second column with a T for cond2 , an F for cond3 , and a dash (don't-care) for cond1 ; this corresponds to the fact that cond2 must be T and cond3 F for the AND term to be true.

We use the table to evaluate whether a given condition holds in the system. The current states of the variables are compared to the table elements. A column evaluates to true if all the current variable values correspond to the requirements given in the column.

If any one of the columns evaluates to true, then the table's expression evaluates to true, as we would expect for an AND/OR expression. The most important difference between this notation and Statecharts is that don't-cares are explicitly represented in the table, which was found to be of great help in identifying problems in a specification table.

More advanced specifications
Excellent examples of advanced specification methodologies are the ones developed for designing safety-critical systems for use in aircraft. Typical of such specifications is the one developed for the TCAS II (Traffic Alert and Collision Avoidance System), a collision avoidance system (CAS) in aircraft.

The specification techniques developed to ensure the correctness and safety of this system can also be used in many applications, particularly in systems where much of the complexity goes into the control structure.

Based on a variety of information, a TCAS unit in an aircraft keeps track of the position of other nearby aircraft. If TCAS decides that a mid-air collision may be likely, it uses audio commands to suggest evasive action—for example, a prerecorded voice may warn “DESCEND! DESCEND!” if TCAS believes that an aircraft above poses a threat and that there is room to maneuver below.

TCAS makes sophisticated decisions in real time and is clearly safety critical. On the one hand, it must detect as many potential collision events as possible (within the limits of its sensors, etc.). On the other hand, it must generate as few false alarms as possible, since the extreme maneuvers it recommends are themselves potentially dangerous.

I won't cover the entire specification here, but just enough to provide its flavor. The TCAS II specification was written in the RSML language. It used a modified version of State-chart notation for specifying states, in which the inputs to and outputs of the state are made explicit. The notation is illustrated in the Figure below .

They also use a transition bus to show sets of states in which there are transitions between all (or almost all) states. In the following example, there are transitions from a, b, c, or d to any of the other states:

The top-level description of the CAS is shown below:

This diagram specifies that the system has Power-off and Power-on states. In the power-on state, the system may be in Standby or Fully operational mode. In the Fully operational mode, three components are operating in parallel, as specified by the AND State: the own-aircraft subsystem, a subsystem to keep track of up to 30 other aircraft, and a subsystem to keep track of up to 15 Mode S ground stations, which provide radar information. Shown below is a specification of the Own-Aircraft AND state.

Once again, the behavior of Own-Aircraft is an AND composition of several subbehaviors. The Effective- SL and Alt-SL states are two ways to control the sensitivity level (SL) of the system, with each state representing a different sensitivity level.

Differing sensitivities are required depending on distance from the ground and other factors. The Alt-Layer state divides the vertical airspace into layers, with this state keeping track of the current layer. Climb-Inhibit and Descent-Inhibit states are used to selectively inhibit climbs (which may be difficult at high altitudes) or descents (clearly dangerous near the ground), respectively.

Similarly, the Increase-Climb-Inhibit and Increase-Descend-Inhibit states can inhibit high-rate climbs and descents. Because the Advisory-Status state is rather complicated, its details are not shown here.

Turning specifications & requirements into a design
So far, we have discussed a number of techniques for making specific decisions. Now, in this section we look at how to get a handle on the overall system architecture. The CRC card methodology is a well-known and useful way to help analyze a system's structure.

It is particularly well suited to object-oriented design since it encourages the encapsulation of data and functions. The acronym CRC stands for the following three major items that the methodology tries to identify:

Classes define the logical groupings of data and functionality.
Responsibilities describe what the classes do.
Collaborators are the other classes with which a given class works.

The name CRC card comes from the fact that the methodology is practiced by having people write on index cards. (In the United States, the standard size for index cards is 3 inch by 5 inch, so these cards are often called 3 x 5 cards.) An example card is shown in Figure 9.10 below .

Figure 9.10: Layout of a CRC card.

It has space to write down the class name,its responsibilities and collaborators, and other information. The essence of the CRC card methodology is to have people write on these cards, talk about them, and update the cards until they are satisfied with the results.

This technique may seem like a primitive way to design computer systems. However, it has several important advantages. First, it is easy to get non-computer people to create CRC cards.

Getting the advice of domain experts (automobile designers for automotive electronics or human factors experts for PDA design, for example) is very important in system design.

First, the CRC card methodology is informal enough that it will not intimidate non-computer specialists and will allow you to capture their input. Second, it aids even computer specialists by encouraging them to work in a group and analyze scenarios.

The walkthrough process used with CRC cards is very useful in scoping out a design and determining what parts of a system are poorly understood. This informal technique is valuable to tool-based design and coding. If you still feel a need to use tools to help you practice the CRC methodology, software engineering tools are available that automate the creation of CRC cards.

Before going through the methodology, let's review the CRC concepts in a little more detail. We are familiar with classes—they encapsulate functionality. A class may represent a real-world object or it may describe an object that has been created solely to help architect the system. A class has both an internal state and a functional interface; the functional interface describes the class's capabilities.

The responsibility set is an informal way of describing that functional interface. The responsibilities provide the class's interface, not its internal implementation. Unlike describing a class in a programming language, however, the responsibilities may be described informally in English (or your favorite language). The collaborators of a class are simply the classes that it talks to, that is, classes that use its capabilities or that it calls upon to help it do its work.

The class terminology is a little misleading when an object-oriented programmer looks at CRC cards. In the methodology, a class is actually used more like an object in an OO programming language – the CRC card class is used to represent a real actor in the system. However, the CRC card class is easily transformable into a class definition in an object-oriented design.

CRC card analysis is performed by a team of people. It is possible to use it by yourself, but a lot of the benefit of the method comes from talking about the developing classes with others.

Before becoming the process, you should create a large number of CRC cards using the basic format shown in Figure 9.10. As you are working in your group, you will be writing on these cards; you will probably discard many of them and rewrite them as the system evolves.

The CRC card methodology is informal, but you should go through the following steps when using it to analyze a system:

1. Develop an initial list of classes: Write down the class name and perhaps a few words on what it does. A class may represent a real-world object or an architectural object. Identifying which category the class falls into (perhaps by putting a star next to the name of a real-world object) is helpful.

Each person can be responsible for handling a part of the system, but team members should talk during this process to be sure that no classes are missed and that duplicate classes are not created.

2. Write an initial list of responsibilities and collaborators: The responsibilities list helps describe in a little more detail what the class does. The collaborators list should be built from obvious relationships between classes. Both the responsibilities and collaborators will be refined in the later stages.

3. Create some usage scenarios: These scenarios describe what the system does. Scenarios probably begin with some type of outside stimulus, which is one important reason for identifying the relevant real-world objects.

4. Walk through the scenarios: This is the heart of the methodology. During the walk-through, each person on the team represents one or more classes. The scenario should be simulated by acting: people can call out what their class is doing, ask other classes to perform operations, and so on.

Moving around, for example, to show the transfer of data,may help you visualize the system's operation. During the walk-through, all of the information created so far is targeted for updating and refinement, including the classes, their responsibilities and collaborators, and the usage scenarios.

Classes may be created, destroyed, or modified during this process. You will also probably find many holes in the scenario itself.

5. Refine the classes, responsibilities, and collaborators: Some of this will be done during the course of the walkthrough, but making a second pass after the scenarios is a good idea.The longer perspective will help you make more global changes to the CRC cards.

6. Add class relationships: Once the CRC cards have been refined, subclass and superclass relationships should become clearer and can be added to the cards.

Once you have the CRC cards, you need to somehow use them to help drive the implementation. In some cases, it may work best to use the CRC cards as direct source material for the implementors; this is particularly true if you can get the designers involved in the CRC card process.

In other cases, you may want to write a more formal description, in UML or another language,of the information that was captured during the CRC card analysis, and then use that formal description as the design document for the system implementors.

To read Part 1, go to “Why use design methodologies?”
Next in Part 3: Quality Assurance .

This series of three articles is based on material printed with permission from Morgan Kaufmann, a division of Elsevier, Copyright 2008 from ” Computers as Components, Second Edition” by Wayne Wolf. For more information about this title and other similar books, please visit www.elsevierdirect.com.

Wayne Wolf is currently the Georgia Research Alliance Eminent Scholar holding the Rhesa “Ray” S. Farmer, Jr., Distinguished Chair in Embedded Computer Systems at Georgia Tech's School of Electrical and Computer Engineering (ECE). Previously a professor of electrical engineering at Princeton University, he worked at AT&T Bell Laboratories. He has served as editor in chief of the ACM Transactions on Embedded Computing and of Design Automation for Embedded Systems .

Leave a Reply

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