The Design-Methods Comparison Project

Copyright © 1998, Institute of Electrical and Electronics Engineers (IEEE), Reprinted, with permission. From A. Terry Bahill, fellow IEEE, Mack Alford, K. Bharathan, John Clymer, Douglas L. Dean, Jeremy Duke, Greg Hill, Ed LaBudde, Eric Taipale, and A. Wayne Wymore, "The Design Methods Comparison Project," IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 28, No. 1, pp. 80-103, 1998.

This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by sending a blank e-mail message to info.pub.permission@ieee.org.

By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

This paper has been discussed on the International Council on Systems Engineering (INCOSE) discussion site. Click here to read a summary of this discussion. As this discussion unfolded Bahill wrote the following comments.

First we tried very hard to present a very restricted problem statement. We also restricted each author to two page solutions. Yet we got tremendous variability in responses. There is a lesson to be learned here.

Second, we did not provide figures of merit to determine the "Best" solution, because we did not want our authors to design their solutions to fit our criteria. We let each of our authors do their best and we let the journal readers decide which methods "seem" the best. There is a lesson to be learned here, too.

Third, Systems Engineering is expensive. The published paper is 24 pages long and includes a dozen design methods. The Systems Engineering solutions that were generated were not included, because they were 25 pages each! And we would have had to pay mandatory page charges of $175 per page. We all know that expense is a problem with Systems Engineering.

Fourth, length will not be a problem for web solutions. So, for those who want to see Systems Engineering solutions, please write some, give me the URL and I will link them. For people who cannot post their own solutions, because of fire walls, lack of web access, or other reasons, I will provide a site.

I am going to group the solutions according to Sarah Sheard's categorization of the 12 Systems Engineering roles .

The first group will assume the Life-Cycle Roles, which include Requirements Engineers, System Architects, Validation and Verification Engineers, Logistics and Operations Engineers, and Systems Analysts. I will call them Systems Engineering.

Our first Systems Engineering solution, by James Sanchez, is right here Sanchez's Solution and Jack Ring has one here Ring's Solution. Brian Mar and Barney Morais have contributed this one Mar and Morais' Solution. Finally Sten Dahlberg, et al. contributed one of our most through solutions, but unfortunately the link to it has disappeared.

The second group takes on Sarah's Program Management Roles, such as Technical Management, Information Management, Coordination, and Customer Interface. John Nallon submitted a solution representative of this group Nallon's Solution.

The last group includes the Design Engineers, which constitute solutions published in the IEEE SMC journal that are contained in the rest of this html file.

Abstract-- Early in the system design process, a design method must be chosen. This choice is usually dictated by what methods the designer has previously used, not by an open selection process. In this paper we provide descriptions of some available design methods and examples of their use. In this project we will develop benchmark problems that will be solved by a variety of design methods. We will identify characteristics of problems that might make one system design method more or less appropriate. The top-level question we wish to answer is "For which type of problem is each method best?"

If a system is to be built, then the system must ultimately be described as a collection of state machines. However, these state machines are often not created by the systems engineers. The systems engineers use some method to create a high-level abstraction of the desired system. Then they turn this abstraction over to the specialty engineers who actually reduce it to a collection of state machines. In this paper, we present solutions for a simple design problem using the following 11 high-level system-design methods: State Transition Diagrams, Algorithmic State Machine Notation, Model-Based System Engineering, Graphical Description Language, RDD-100, Structured Analysis (using Entity Relationship Diagrams, Data Flow Diagrams, and State Transition Diagrams with Ward-Mellor notation), Functional Decomposition, Object-Oriented Analysis with Shlaer/Mellor Notation, Object-Oriented Analysis and Design with Booch Notation, an Operational Evaluation Modeling Directed Graph, and IDEF0. Each method was used by an expert user of that method. The solutions presented make it obvious that the choice of a design method greatly effects the resulting system design.

Index Terms -- Architecture, Design methodology, Logic design, Object oriented methods

FOOTNOTES

Manuscript received: September 19, 1996.

A. Terry Bahill is with Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721-0020, terry@sie.arizona.edu

Mack Alford, 548 Old Huntsville Rd, Fayetteville, TN 37334-6029, alford@netcom.com

K. Bharathan is with the Department of Surgery, University of Arizona, Tucson, AZ 85721, bhara@sie.arizona.edu

John Clymer is with California State University at Fullerton, 1631 Roanoke St., Placentia, CA 92670, jclymer@fullerton.edu

Douglas L. Dean is with the Center for the Management of Information, University of Arizona, Tucson, AZ 85721, ddean@bpa.arizona.edu

Jeremy Duke is with Intel, 3174 W. Tyson Pl., Chandler, AZ 85226, jeremy_duke@ccm.ch.intel.com

Greg Hill is with IBM Corp., Dept. 65E, Building 41, Tucson, AZ 85744, hill@vnet.IBM.com

Ed LaBudde is with LaBudde Systems Inc., 1768 Upper Ranch Rd., Westlake Village, CA 91362, elabudde@pobox.com

Eric Taipale is with Lockheed Martin Tactical Defense Systems, 3333 Pilot Knob Road, Eagan, MN 55121, eric.taipale@lmco.com

A. Wayne Wymore is with SANDS, 4301 N. Camino Kino, Tucson AZ 85718, wayne@sie.arizona.edu

An earlier version of this paper was published in the Proceedings of the IEEE International Conference on Systems Man and Cybernetics, Beijing, China, October 14-17, 1996 [1].

Early in the design process, engineers must choose a method for designing the system. This choice is usually dictated by the methods that the systems engineer's boss has previously used, not by an open selection process. In this paper we provide descriptions of available design methods and examples of their use in order to help systems engineers select an appropriate design method.

In engineering the two general types of systems are called static and dynamic. To a first approximation, a small bridge is described with methods of statics, whereas a pendulum is described with methods of dynamics. A typical equation of statics is

M = Fr,

which expresses the concept that a moment is equal to the force times the moment arm. Whereas, dynamic systems are typically described with state equations like these

x(k+1) = Ax(k) + Bu(k)

and

y(k) = C(k) + Du(k).

But, of course, the distinction between static and dynamic systems is artificial, being created for heuristic purposes. We study statics first, then we build on that to study dynamic systems. Therefore, we can consider statics to be a subset of dynamics.

In the literature about computers, these two types of systems are called respectively combinatorial and sequential. Static systems are synonymous with combinatorial systems and dynamic systems are synonymous with sequential systems. For combinatorial systems the output depends only on the present inputs, whereas for sequential systems the output depends on the present inputs and the state of the system. The state of the system depends upon the starting state and the history of the inputs. But, once again, the distinction between combinatorial and sequential logic systems is artificial. We study combinatorial systems first, and then use this knowledge to study sequential systems. Therefore, we can consider combinatorial systems to be a subset of sequential systems. So, without loss of generality, we can discuss only sequential logic systems, which is what we will do in this paper.

In 1936 Turing [29] stated that all solvable sequential logic problems could be solved with a Turing machine (a state machine). Therefore all buildable systems are state machines. So, for the last six decades, system designers have focused their attention on designing state machines. But designing state machines for big, complex systems can be difficult. So, engineers and computer scientists have invented methods to help design state machines. This paper compares and contrasts many of these methods.

If a system is to be actually built, then the system must ultimately be described as a collection of state machines. However, these state machines are often not created by the systems engineers. The systems engineers use some method (or tool) to create a high-level abstraction of the desired system. Then they turn this abstraction (or design) over to the specialty (component) engineers who actually reduce it to a collection of state machines. In this paper, most of our authors stopped with the high-level abstraction.

Two approaches have been taken for describing system designs: (1) describe many systems and many design methods [20] and (2) describe one problem and many design methods [24], which is what this paper will do. In this project a variety of methods will be used to solve several benchmark problems. Therefore, a big part of the project is developing these benchmark problems. Examples of benchmark problems are on the World Wide Web [12], [25]. The top-level question we wish to answer is "For which type of problem is each method best?"

This paper presents the beginning of a long project. We intend to enlarge the project by including more methods and more complex problems. Note that the problem presented in this paper does not do justice to big tools like RDD-100, the Graphical Description Language [17], and object-oriented design, all of which were created for large, complex systems. It will seem as if these tools are cracking a walnut with a sledgehammer.

In this paper we present one problem. Then our 11 authors use 11 different methods to design solutions for this problem. The purpose is to provide a comparison of these methods.

Nomenclature. Most of these methods use data inputs, functions, states, control inputs, and objects. Data or material inputs are transformed into outputs by functions. For example, burning paper transforms it into ash. Functions are usually named with verb phrases. Functions are called processes with some methods and activities with others. The state of the system captures the history of the system. The present state and the sequence of future inputs allow computation of future states of the system. States should be named with historical statements. States are called modes with some methods. Control inputs turn functions on and off and trigger transitions between states. Objects are people, places, things or transactions that share common attributes and perform common functions. Objects are usually named with adjectives and nouns. Objects are called entities with some methods and mechanisms with others.

There is an intersection between a seldom-used farmroad and a busy highway. A farmer has difficulty getting across the highway, so we are to install a traffic-light system, as illustrated in Fig. 1. Design a controller for this traffic-light system.

Fig. 1. The farmroad-highway intersection.

Normally, the highway light shall be green and the farmroad light shall be red. When a sensor signals that a tractor is on the farmroad, the highway light shall change to yellow. After a short-time interval (STI, nominally 10 seconds) the highway light shall change to red and the farmroad light shall change to green. The farmroad light shall stay green until the tractor clears the sensor or after a long-time interval (LTI, nominally 50 seconds), whichever comes first. Then the farmroad light shall become yellow. After a short time interval the farmroad light shall become red and the highway light shall become green. The system shall stay in that state for a least a long time interval. After a long time interval the highway light shall be switched when the sensor detects a tractor. A timer that produces output signals after short time intervals and long time intervals will be available. It can be restarted at anytime. Table I suggests some abbreviations. This problem is based on Mead and Conway [16] and Katz [19].

TABLE I. Convenient abbreviations.

The following states are sufficient for this controller:

Highway-green commands the highway green and the farmroad red lights to be on,

Highway-yellow commands the highway yellow and the farmroad red lights to be on,

Farmroad-green commands the farmroad green and the highway red lights to be on,

Farmroad-yellow commands the farmroad yellow and the highway red lights to be on.

This Finite State Machine solution begins with a state transition diagram where each oval represents a state. The name of the state is in the top of the oval and the values of the outputs are in the bottom. For the state transition diagram of Fig. 2, the six output numbers represent the values for, respectively, CHWG, CHWY, CHWR, CFRG, CFRY, and CFRR. All possible state transitions are not shown: only those that are expected to occur are shown. A bar on top of an input abbreviation symbolizes negation. A dot (·) represents the Boolean AND function and a plus sign (+) represents the Boolean OR function.

Fig. 2. A state transition diagram.

Typical state machines have either level outputs or pulse outputs. This state machine is unusual, because it has both. When the system is in the state Highway-green the output command highway green light on and the output command farmroad red light on are both 1 (on). The other light commands are 0 (off). These are level outputs: these outputs are associated with the states. State machines with level outputs are sometimes called Moore machines. The output reset and start the timer is a pulse output: it is associated with the transitions between states. It is only valid for a short time interval, a pulse. State machines with pulse outputs are sometimes called Mealy machines [16].

We will now show two more views of this finite state machine traffic-light controller. Use of these extra views enhances the probability of completeness, aids creation of a detailed design by specialty engineers, and provides a way to validate the design.

We wish to implement and validate the controller with TTL circuitry and two JK flip-flops, which will be named A and B. First, we transform the state transition diagram into the state table shown in Table II. Each row of the table contains a transition from one state to another. Therefore, there will be one row in the table for each arrow in the diagram: except arrows labeled with Boolean OR functions require two rows.

TABLE II. A state transition table.

Note: dc stands for don't care. It makes no difference whether these entries are 1 or 0, because they would not effect a change of state or output.

Now we can write the Boolean equations for the flip-flop inputs and for the outputs we are controlling.

Fig. 3. Implementation of the finite state machine.

Now that we have built a circuit, we can validate it. We do this by applying a multitude of input trajectories and looking to see that the system produces appropriate output trajectories. For example, Table III shows one correct input-output pair. Time runs from top to bottom. Many input/output trajectories, such as this one, would be used to prove that the circuit performs correctly.

TABLE III. A Sample Input/Output Trajectory

Where dc represents a don't care condition.

After the technology was selected, this design was passed off to the specialty design engineers. They implemented the state transition diagram of Fig. 2 with the hardware shown in Fig. 3. In doing so, they did not change the design, but they did require a clarification of whether the timer produced level or pulse outputs. Mixing of pulse and level outputs also caused some complication.

The strong point of state transition diagrams is that they conveniently show the inputs, outputs and states in a manner that it well suited for human visualization. They can be built incrementally using input/output trajectories as shown in Table III.

Algorithmic state machine (ASM) notation builds on the foundation of state transition diagrams by providing a means to express the state trajectory as a conditional flow [13]. This is accomplished by incorporating conditions, or decision points, and distinct output points within the ASM charts. ASM charts are composed of multiple ASM blocks, each block with exactly one state, at least one output, and exit conditions. ASM blocks have a single entry point, but can have multiple exit paths. There is an unambiguous exit path (state transition arrow) for each combination of inputs. Fig. 4 shows an example ASM block. Outputs are listed in the state box or inside the ovals depending on whether they are associated with the state or with the transition between states. The specified exit condition is checked on each clock cycle to determine the next state.

Fig. 4. An Algorithmic State Machine Block.

Figure 5 shows the ASM chart for the traffic-light controller. In ASM charts, H.output means the specified output will be asserted high in the given state or transition. For example in the state Highway-green the outputs CHWG and CFRR are asserted high, meaning these lights are turned on. The unmentioned outputs are, by implication, not asserted, meaning they are low or off. The Boolean function of LTI AND Sen is continually checked. If it is logic 0, then the machine stays in state Highway-green. If it is logic 1, then the machine goes to the state Highway-yellow and the output Restart is asserted high during this transition.

Fig. 5. An ASM chart for the Traffic-Light Problem.

This solution is very similar to the previous state transition diagram. However, ASM charts have some advantages over state transition diagrams. ASM charts concentrate on the paths and conditions for exiting a state. These exit conditions can be built up incrementally and later combined into a single Boolean condition. It is easy to understand the resulting design as an algorithm. ASM charts also partition the algorithms into fundamental building blocks, defining interfaces between these blocks. This partitioning makes it easier to design more complex systems. This method transitions easily into Hardware Description Languages such as VHDL that are used to design computers [16].

The traffic-light controller can be described as

Z = (SZ, IZ, OZ, NZ, RZ) [5], [31], [32], where

SZ = {Highway-green, Highway-yellow, Farmroad-green, Farmroad-yellow},

IZ = I1Z × I2Z × I3Z × I4Z, where

OZ = O1Z × O2Z × O3Z × O4Z × O5Z × O6Z × O7Z, where

NZ = {((Highway-green, ()) Highway-green),

((Highway-green, ()), Highway-yellow),

((Highway-yellow, ()), Highway-yellow),

((Highway-yellow, ()), Farmroad-green),

((Farmroad-green, ()), Farmroad-green),

((Farmroad-green, ()), Farmroad-yellow),

((Farmroad-yellow, ()), Farmroad-yellow),

((Farmroad-yellow, ()), Highway-green),

((ANY-state, (Initialize)), Highway-green)},

RZ = {(Highway-green, (CHWG, CFRR, Restart)), (Highway-yellow, (CHWY, CFRR, Restart)), (Farmroad-green, (CHWR, CFRG, Restart)), (Farmroad-yellow, (CHWR, CFRY, Restart))}.

This design might fail depending on whether the timer is triggered on the leading or trailing edge. This implementation has difficulty handling both level outputs (Moore machines) and pulse outputs (Mealy machines). In this example the light commands (e.g., CHWG) are level outputs whereas the Restart signal is a pulse output, but the notation does not distinguish between them.

Some advantages of this notation are that (1) it works for problems with a large number of states, (2) its designs can be implemented with a very simple text processor, a typewriter or even HTML, and (3) it is mathematically rigorous so its designs can be verified by computer.

The traffic-light controller can be described as

Z = (SZ, IZ, OZ, NZ, RZ) where

SZ = {Highway-green-initial, Highway-green-wait, Highway-green, Highway-green-transition,

Highway-yellow, Highway-yellow-transition, Farmroad-green, Farmroad-green-transition,

Farmroad-yellow, Farmroad-yellow-transition},

IZ = I1Z × I2Z × I3Z × I4Z,

where IkZ = {0,1} for every k Î {1, 2, 3, 4},

OZ = O1Z × O2Z × O3Z × O4Z × O5Z × O6Z × O7Z,

where OkZ = {0,1} for every k IJS[1, 7],

Outputs from O7Z are commands to the timer, 1 means reset and restart. */

/* If the highway green or highway yellow lights are on, then the farmroad red light should be on. Similarly, if the farmroad green or farmroad yellow lights are on, the highway red light should be on. These conditions will be reflected in the definition of RZ below. */

/* The next state function lists the transitions between states. In this function p represents a particular value for one of the input ports and x represents a particular value for the state. Thus the fifth line in the following table can be read as, The next state is Highway-green, if x (the present state) is Highway-green-wait AND LTI(p) (the present value of LTI) is logic 1. */

If p Î IZ, p = (Initialize(p), Sen(p), STI(p), LTI(p)), and x Î SZ then NZ(x, p) =

RZ = {(Highway-green-initial, (1,0,0,0,0,1,1)),

(Highway-green-wait, (1,0,0,0,0,1,0)),

(Highway-green, (1,0,0,0,0,1,0)),

(Highway-green-transition, (1,0,0,0,0,1,1)),

(Highway-yellow, (0,1,0,0,0,1,0)),

(Highway-yellow-transition, (0,1,0,0,0,1,1)),

(Farmroad-green, (0,0,1,1,0,0,0)),

(Farmroad-green-transition, (0,0,1,1,0,0,1)),

(Farmroad-yellow, (0,0,1,0,1,0,0)),

(Farmroad-yellow-transition, (0,0,1,0,1,0,1))}.

This solution with Model-Based Systems Engineering notation [31] handles the so-called "pulse" output simply by inserting a "transition" state during which the "pulse" output is generated. This way, the advantages of the Moore machine can be enjoyed (Moore machines are absolutely essential for a useful theory of system coupling) and the fiction of the egregious, gratuitous "pulse" output is properly represented. With the Model-Based Systems Engineering notation, systems with a large number, even an infinite number, of states can be defined and manipulated efficiently [5], [31], [32].

E. Solution via Graphical Description Language;

1) Basic Concepts of the Method: The method uses five orthogonal graphical views of the system design [17].

Block Diagram View (Fig. 6). This is a modification of a popular concept that relates inputs, outputs, and transfer functions. Two special additions are included. First, all changes in functional behavior that are logic-dependent must be shown with the use of a switch; the switch must show how functionality is changed. Second, it is assumed that all control logic elements are separated from the process functions and are located in a finite state machine controller. The controller executes the logic operations that change functionality.

Fig. 6. Block diagram view.

Mode Matrix View (Fig. 7). The mode matrix view requires that every valid combination of switch settings be given a name and called a mode. Both lock step and concurrent (parallel) modes are represented this way. The switch setting for every mode must be contained in the matrix.

State Diagram View (Fig. 7). The state diagram view requires a bubble for every mode (state) in the mode matrix table. In this paper we will make no distinction between a mode and a state. A transition arrow for each possible transition between states is also required. Each transition arrow is labeled with the control conditions that must be true to enable that transition.

Timeline View (Fig. 7). The timeline view shows the events that trigger changes in modes. Each event is a transition arrow in the state diagram. The timeline must show which mode occurs after the event and any responses that the system generates. The timeline denotes the required sequence of events or inputs/outputs and any time requirements between objects in the diagram. For every path through the state diagram, a timeline exists.

Fig. 7. Mode matrix, state diagram, and timeline.

Fig. 8. Mission phases.

Performance View (not shown in any figure). Performance requirements are numerical requirements and can be applied to any object in any other view. Thus, inputs, outputs, processes, modes, logic, and timing may all possess performance requirements. Performance requirements are usually derived by the use of math models. The math model is visualized with a performance tree. The performance tree displays how requirements are either decomposed into lower requirements (flow down) or how lower-level requirements roll up to higher-level requirements (flow up). Performance trees show how the requirements are decomposed into parameters that are displayed in the other views.

2) Physical Decomposition: These five views are used in all levels of the system hierarchy. In the Mission Level (Fig. 8) the mission phases and scenarios are used to define user and system interfaces. The System Level shows all the interactions between elements used to create a system. The Element Level shows all the interactions between the subsystems used to create an element. The Subsystem Level shows all the interactions between functions used to create a subsystem. The Function Level shows all the interactions between sub-functions used to create a function. The Sub-function Level view shows all the interactions between components used to create a sub-function.

3) Functional to Physical: The views are used to create both a functional description (what it does and how it works) and a physical description (how it is made). The hand-off between the system engineer and the design engineer usually happens at the function level. The design engineer translates a function into an assembly. The design engineer then uses the same diagrams to define the physical assembly. Consequently, there is a requirement to make a functional-to-physical translation map. This is usually done by defining which functional elements are allocated to which physical entity. It is at this level where the hardware and software allocations are usually made.

This process means two parallel representations of the system at the same level may exist (functional and physical). The system engineer maintains the functional and the design engineer maintains the physical, with the translation map showing trace-ability.

4) Hierarchical Decomposition. A totally top-down decomposition is not always possible or necessary. The use of orthogonal views and a hierarchy of decomposition allows the system development to be created with many parallel activities. The views define how the components interact and allow for items at any level to be integrated into the system descriptions. This means that bottom-up development can easily be integrated into top-down or horizontal structures with complete traceability.

Block diagrams, mode matrices, state diagrams, and performance trees are hierarchical. This means that it is possible to replace a black box view of an object with a lower-level functional view (gray box) without going outside the boundary of the higher-level black box. If it is necessary to go outside the boundary, the views make it obvious that there is a functional problem with the higher level.

The timeline cannot be hierarchical. However, more details are created at lower levels. Timelines can diverge along concurrent (parallel operation) paths at lower levels. Unfortunately, there can be an explosion of the timelines at lower levels due to all possible combinations of states and concurrency, but this problem can be contained by the use of some rules in identifying the critical time paths and to minimize interactions.

5) Functional Decomposition: Our method requires the decomposition to begin with the mission level. Here all phases of the system utilization must be laid out. The Phase Analysis must show the life cycle of the mission. A sample Phase Diagram is shown in Fig. 8.

In each Phase there can be more than one "Scenario." A Scenario must show details of the interface between all Systems and Users employed in each phase. A sample Scenario diagram is shown in Fig. 9.

Fig. 9. Operating phase scenario.

In this scenario we can see that there is considerable interaction between the various Systems and many Interface Control Documents will be required to specify all the interface requirements. One of the obvious requirements is specifying the Short Time Interval (STI). Here we can see that the response time of the highway user is critical (shown in the timeline in Fig. 7). The Operating Phase Scenario illustrates the need to specify (1) Power system requirements, (2) Environmental conditions, (3) User response characteristics, (4) Vehicle characteristics, (5) Road characteristics, and (6) Traffic-light optical properties. When these items are specified, then the time intervals can be determined. The sample problem ignores all of these requirements.

System Level - After the scenario is defined, the Systems that are identified in the scenario are decomposed into Elements. The Transportation system has Elements of Highway (H/W), Farmroad (F/R), and Traffic Lights.

Element Level - The Traffic-Light Element view is shown in Fig. 6 and Fig. 7. The Block Diagram, Mode Matrix, State Diagram and Timeline are shown. There are no Performance Trees for this problem because of the lack of suitable higher level details in the problem statement. Because of the lack of problem statement detail (and to save space) the diagrams shown in Figs. 8 and 9 are functional only and do not show all the required Sub-Systems such as power supply, mechanical structure, cooling, interconnection, and similar items.

Functional to Physical - There are unlimited ways to implement the functional requirements, diode-relay logic, digital electronics, microcomputer and firmware, and so on. In the interest of space, we will not show the functional to physical translation for this sample problem. If we did it would show the physical circuits, devices, and hardware/software partition and traceability to the functional design.

This system design methodology makes clear the missing requirements in the sample problem and identifies how to rectify the problem statement. The method is a true system design tool, not tied to any specific design implementation (manufacturing technology), and ensures complete, accurate, and unambiguous statement of requirements. Additionally, the method is substantially more robust than the existing systems and software representations, and it ensures that all requirements are captured and tracked. Not only is it easy to learn and use, but it can be implemented with low-cost commercial office automation software.

F. Solution via RDD-100

The RDD-100ä model of the Traffic-Light Problem shown in Fig. 10 uses the points in time at which signals change as "trigger" messages that propagate through the model. The model uses a separate process for the sensor, the controller, the timer, the highway light, and the farm light; these are shown as columns in Fig. 10, which are "concurrent branches" of a graph.

To help explain this model let us walk through a few steps in one sequence of events. A tractor crosses the sensor, so the "tractor arrives" box in the upper left corner sends a signal "sen=1" to the "wait for tractor box." The controller is thus released from this box and goes to the "turn highway red, farmroad green" box. During the transition, the CHWY=1 signal is sent to the highway light releasing it from the "show HG" box and allowing it to move to the "show HY’ box. At the same time a "start=1’ signal goes to the timer releasing it from the "wait for timer reset box." Etc.

The sensor iterates by sending Sen = 1 and Sen = 0 messages; for simulation purposes, one specifies the number of iterations, after which the sensor process delays, terminates, and then kills off all other processes.

Fig. 10. The RDD-100 model.

The timer process is a loop that waits until a reset arrives, then delays until the STI = 1 is sent; it then waits until either LTI = 1 is sent or a reset arrives. This cycles twice for every time the controller cycles once. The farm and highway lights loop through their green-yellow-red sequences as commanded by the controller.

The controller loops through the sequence of commanding the lights. The Sen = 1 message results in CHWY = 1 and reset of the timer. The CFRG = 1 and CHWR = 1 are sent when either Sen = 0 or STI = 1 arrive. All further Sen = 0 messages are then ignored. The timer is reset, the CFRY = 1 is sent, CFRR = 1 is sent when STI = 1 arrives, and the cycle repeats when LTI = 1 arrives. This model is executable, and when executed yields timelines and a demonstration of dynamic consistency of inputs and outputs. To ensure that all of the requirements have been satisfied, each requirement is "traced to" some function that implements it. This verification process revealed one possible ambiguity in the following requirement: "When a sensor signals that a tractor is on the farmroad, the highway light shall change to yellow." What is to occur when the tractor does not move, and hence the Sen = 0 signal is never sent—should the system cycle again? If so, the behavior would have to be modified to reflect this decision.

The RDD-100 design was the first design of those presented in this paper to be validated. This was done by running a simulation and observing the input/output behavior. This highlights a very significant facet of systems engineering design methods: ease of validation. RDD-100 has validation tools built into the design tool.

There are three principal model views in most flavors of structured analysis [3], [9], [30]. Each of these views will be illustrated for the Traffic-Light Problem. The first view of the system is the entity relationship diagram. This view depicts the principal tangible or logical entities in the problem domain, along with their relationships to each other. Relationships are usually of the types has-a, uses, is-a, performs, documents, controls, etc. The diagram may also contain cardinality information. In the entity relationship diagram of Fig. 11, a single entity, Controller, represents the solution to the traffic-light controller. (At this stage, decomposing the solution into more than one entity may suggest a preconceived design solution.) The entity relationship diagram shows the relation the system will have with the entities external to it in the problem domain. For instance, the Controller entity uses one Timer and two Sensors: it controls two HWLights and two FRLights. If no line exists between two entities, then those two entities need know nothing about one another. Partitioning relationships in this manner makes the system design much easier.

The problem statement usually serves as the top-level function [10], [22]. At the top level, the vocabulary of the problem domain, not of a particular solution dominates. For the Traffic-Light Problem the top-level function might be "Control the traffic lights at the intersection." This function is then decomposed into smaller subfunctions. The decomposition process is hierarchical; each of the subfunctions may be further decomposed into subsubfunctions until all functions represent tractable design problems of appropriate scope, a condition defined by the systems engineering team. Functional decomposition generates a block diagram of the functions performed by a system as shown in Fig. 14.

Fig. 14. Level 1 Functional block diagram.

Arrowheads indicate that something, such as data or a signal, passes from the output of one function into the input of the next. Vertical lines between the centers of two function boxes indicate that the upper box function must start before the lower box function can start. Vertical lines extending downward from the right side of a box indicate that the lower function begins after the top function has completed. Vertical lines extending upwards from the left side of a box indicate that the top function begins concurrently with the bottom function (This figure has no such lines.). In general, the control flow moves from left to right and top to bottom.

Each of the functions in this figure can be decomposed into subfunctions. Functions that have been decomposed are indicated with an asterisk (*) after the function number. For example the INIT function 1.* is decomposed in Fig. 15. The INIT function performs the initialization routines the system needs prior to entering operational status. The numbering of the functions shows the parent-child relationships as well as the level of the decomposition.

Fig. 15. Level 2 functional block diagram for the INIT function.

The level 2 decomposition of the INIT function shows the subfunctions of INIT. It also shows something the top-level diagram did not: an error condition. If INIT can accomplish its subfunctions successfully, the function flow moves from left to right, as in the level 1 decomposition. If a subfunction fails, however, INIT will branch into a subfunction called Signal ERROR. Note that nothing flows out of Signal ERROR, it is a control sink. If the system moves into Signal ERROR, function INIT will never be completed and the system will not begin operational mode.

After the level 2 decomposition it is again appropriate to determine whether another level of decomposition is necessary for each of the new subfunctions. For example, the subfunctions involved in the INIT function are good candidates for further decomposition. The function Obtain controller hardware-OK signal might be decomposed as in Fig. 16.

Fig. 16. Level 3 functional block diagram for the function Obtain controller hardware-OK signal.

The level 2 decomposition of another function, Command HW light yellow, would proceed as shown in Fig. 17. Although this decomposition is trivial, it points out something interesting in the design. The lines are vertical, indicating that no signal ever passes to the controller to indicate whether the lights actually turned off or on. Early in the design this decomposition has already pointed out a potential flaw.

Fig. 17. Level 2 functional block diagram for the function Command HW light yellow.

Determining when functions have been sufficiently decomposed is a matter left to the discretion of the systems engineer. In some cases, a third level decomposition of the problem might be adequate. In other cases, the systems engineer might wish to continue the process until subfunctions resemble lines of pseudocode or simple human or machine operations.

Functional decomposition became popular as a software method when software systems were generally of much smaller size than the systems of today. It is perhaps for this reason that functional decomposition most effectively manages systems of small to moderate complexity. It scales to this small problem nicely, in contrast to more formal methodologies that would impose far more rigor (and effort) for marginal additional benefits. While it is clear that had the decomposition of each function into subfunctions taken place, a large number of diagrams would have been necessary, there is not much overhead information included in the notation that is not absolutely essential to the operation of the system.

On the other hand, in the absence of such overhead, there is little information to reveal relationships and similarities between functions and the entities that perform those functions. For this reason, the functional decomposition process tends to become more unwieldy when systems become large and complex. We have found functional decomposition to be the most difficult of the system design methods we have used.

For the given problem statement, I will show a solution based on the Shlaer-Mellor [26], [27] flavor of Object Oriented Analysis (OOA). My solution includes just some of the key parts of Shlaer-Mellor OOA, which are quite sufficient for dealing with the complexity of this problem.

First I will construct an information model (IM). The IM identifies the real-world objects involved, subtype-supertype hierarchy, relationships, and cardinality. From the problem statement we can identify the objects as follows: highway light, farmroad light, tractor, sensor, and timer. (Objects were called entities in the structured analysis section.) Since the sensor and timer provide identical inputs (STI, LTI, and Sen) to both the highway light and farmroad light, I can generalize a supertype object of traffic-light, for which the highway light and the farmroad light are subtypes. We show the relationships common to both lights as relationships with the traffic-light supertype object. The relationships are shown as lines connecting two objects, and are identified by a <r> symbol containing a unique number, such as <r2>. Text on each side of the <r> symbol identifies the meaning of the relationship and the number of arrowheads indicates the cardinality. Figure 18 contains an example where one P sees many Q objects, or many Q’s are seen by one P, and Fig. 19 contains the IM for the Traffic-Light Problem.

Fig. 18. Example Information Model Diagram.

Fig. 19. Information Model for the Traffic-Light Problem.

The purpose of the IM is to ensure that no real-world objects were omitted in the analysis, and that every object included in the IM really is an essential part of the system, i.e. no unrelated islands. Using the IM as a checklist, we evaluate each object to determine if it is an active or passive object. Active objects have life cycles in which they pass through various states, and their behavior can be represented in a state model or state machine. Passive objects have no life cycle.

For each non-trivial active object in the IM, we need to show the state model behavior as a state machine. We also need to determine if a single state machine for a supertype object will correctly represent the behavior of all its subtypes. If not, then a separate state machine is needed for each subtype object.

From the problem statement, we know that the highway light and the farmroad light do not have identical behavior. Therefore, we must have a separate state machine for each, rather than a single state machine for traffic light. Also from the problem statement, we know that a tractor is either present or absent in the eyes of the sensor, but since the sensor does all the work of detecting, we can consider the tractor to be a passive object, and so it needs no state machine. The sensor can be either a trivial active object or a passive object. As a trivial active object it passes back and forth between the two states of detecting presence and detecting absence of a tractor. As a passive object, it is merely the owner of the global Sen input signal. In either case, it needs no state machine since the highway light and the farmroad light both get all the information they need about the sensor by recognizing the Sen input signal. Similarly, the timer needs no state machine since the highway light and the farmroad light both get all the information they need about the timer from recognizing the STI and LTI input signals. However, we must be sure that highway light state machine and the farmroad light state machine both make correct use of the Sen, STI, and LTI input signals.

The state model behavior of the highway light and farmroad light are shown in Figs. 20 and 21. In each state machine, states are shown as boxes, and transitions are shown as arrows from a source state to a destination state. The only exception to this (an arrow with no source state) is used to identify an initial entry-point or starting state in the state machines. The state boxes contain a state-name, followed by the activities that are executed when the object enters that state. At the conclusion of the activities, the object sits idle until an event occurs that causes a transition to the next state. The event is identified near each arrow that shows a state transition. The notion of activities happening within states follows the theory of Moore machines, whereas another theory (Mealy machines) has the activities associated with the transitions or arcs.

Fig. 20. State model for the Farmroad Light.

Fig. 21. State model for the Highway Light.

In the state machines of Figs. 20 and 21, the action "Restart" means that we toggle the output named Restart so that the timer starts counting over from zero. The action "signal X/Y to the other machine" means that we use some intermediate input/output signal to communicate between the state machines. For example, this intermediate signal could be a toggle action on X or Y in these state machines.

If the introduction of new intermediate signals (X and Y) for inter-state machine communication is not possible then we could use the existing signals CHWG and CFRG as input/output signals to accomplish the same thing. If the CHWG and CFRG signals cannot be used as input signals for inter-state machine communication, then we need to reduce the two state machines into a single state machine, which avoids the need for inter-state machine communication. Although these state machines can be reduced to a single state machine with five states, this trivializes the problem to a much simpler level. Not all problems reduce to one state machine so easily. One of the strengths of the Shlaer/Mellor flavor of OOA is its ability to handle more complex problems by using concurrently running state machines that signal events to each other as the sole means of inter-state machine communication.

Object-oriented analysis and design (OOA/OOD) attempt to describe a system from a different perspective than the more traditional functional design methodologies. The OO approach defines the relationship between things (the objects) in the problem domain with objects in the solution domain, then defines the behaviors of these objects [4], [15], [23], [26], [27].

An object-oriented analysis often begins with recognizing the different classes of objects in the problem domain. Table IV describes some of the classes that might be found in the Traffic-Light Problem.

TABLE IV. Classes in the Solution Domain

These classes can be graphically related in a class diagram, as in Fig. 22. Class diagrams can show inheritance relationships between classes. Inheritance allows the designer to express commonality between classes. For example, a lion and a tiger are related in that they are both mammals. Inheritance also allows the designer to present information in one place and let it be used in many other places. For example in the description of the class Light we can specify the voltage, current, luminance, and heat produced. Then lights of any color would inherit these properties. This figure uses the notation of Booch [4] wherein a line with an arrow represents the inheritance relationship; e.g. a Red Light inherits all the properties defined for the class Light, etc. This notation represents a uses relationship with a line with an open circle, e.g. the Controller uses the Timer, the Pair Router and the Sensor. A line with a solid circle represents the has-a relationship, e.g. a Traffic Light has-a Red Light, has-a Green Light, and has-a Yellow Light.

Object-oriented design offers a great deal of scalability that can be useful in large-scale systems design. The scalability is available through the good definition of classes, allowing the design to be composed of modular, hierarchical elements that can have a one-to-one relationship with the physical elements in the solution domain.

1. A.T. Bahill, et al., "The systems engineering design tools analysis project," Proceeding of the 1996 IEEE Systems Man and Cybernetics Conference, Beijing China, pp. 2370-2385 and 2392-2393, October 14-17, 1996.
2. A.T. Bahill, B. Bentz, and F.F. Dean, Discovering System Requirements. SAND96-1620 UC-706. Albuquerque, NM: Sandia National Laboratories, 1996. This paper is also available at http://www.sie.arizona.edu/sysengr/requirements.
3. N.C.C. Blackwell, Structured Systems Analysis and Design Method (SSADM) Specification, 1990.
4. G. Booch, Object-Oriented Analysis and Design. Benjamin Cummings, 1994.
5. W.L. Chapman, A.T. Bahill, and A.W. Wymore, Engineering Modeling and Design. Boca Raton: CRC Press, 1993.
6. J.R. Clymer, P.D. Corey, and N. Nili, "Operational evaluation modeling," In Simulation, San Diego, CA: the Society of Computer Simulation International, pp. 261-270, Dec. 1990.
7. J.R. Clymer, " Role of reductionism and expansionism in system design and evaluation," Proceedings-Fourth annual International Symposium, National Council on Systems Engineering, San Jose, CA, pp. 323-332, August 10-12, 1994.
8. J.R. Clymer, "Expansionist/context sensitive methodology: engineering of complex adaptive systems," IEEE Transactions on Aerospace and Electronic Systems, vol. 33, no. 2, April 1997.
9. T. DeMarco, Structured Analysis and System Specification, New York, Yourdon Press, 1979.
10. E.W. Dijkstra, "Structured Programming," Classics in Software Engineering, Edited by Edward N. Yourdon, New York, Yourdon Press, pp. 43 – 48, 1979.
11. P.A. Fishwick, Simulation Model Design and Extraction. Prentice Hall, 1995.
12. B. Fox, and M. Ringer, "Planning & scheduling benchmarks," http://www.neosoft.com/~benchmrx/default.html, Nov. 1996.
13. D. Green, Modern Logic Design. Addison-Wesley, 1986.
14. Integration Definition for Function Modeling (IDEF0). Federal Information Processing Standards Publication 183: Computer Systems Laboratory, National Institute of Standards and Technology, 1993.
15. I. Jacobson, M. Ericsson, and A. Jacobson, The Object Advantage: Business Process Reengineering with Object Technology. New York: Addison-Wesley, 1995.
16. R.H. Katz, Contemporary Logic Design. Benjamin Cummings, 1994.
17. E.V. LaBudde, Graphical Description Languageä A Solution For The System-Software Interface Problem, 1996.
18. D.A. Marca and C.L. McGowan, IDEF0/SADT: Business Process and Enterprise Modeling. San Diego: Eclectic Solutions, Inc., 1993.
19. C. Mead, and L. Conway, Introduction to VLSI Systems, Reading MA, Addison-Wesley, 1980.
20. J.A. Moody, W.L. Chapman, F.D. Van Voorhees, and A.T. Bahill, Metrics and Case Studies for Evaluating Engineering Designs. Prentice Hall, 1997.
21. D.T. Ross, "Douglas Ross talks about Structured Analysis," IEEE Computer, pp. 80-88, July 1985.
22. D.T. Ross, J.B. Goodenough, C.A. Irvine, "Software Engineering: Process, Principles, and Goals," IEEE Computer, Vol. 8, No. 5, pp. 17 – 27, May 1975.
23. J. Rumbaugh, M. Blaha, W. Premerlani, F. Eddy, and W. Lorenson, Object-Oriented Modeling and Design. Prentice Hall, 1991.
24. M. Shaw, "Comparing architectural design styles," IEEE Software, pp. 27-41, Nov. 1995.
25. M. Shaw, "Model Problems in Software Architecture," http://www.cs.cmu.edu/~Compose/html/ModProb/index.html, Nov. 1996.
26. S. Shlaer, and S. Mellor, Object-Oriented Systems Analysis: Modeling the World in Data. Englewood Cliffs: Prentice Hall, 1988.
27. S. Shlaer, and S. Mellor, Object Lifecycles: Modeling the World in States. Englewood Cliffs: Prentice Hall, 1992.
28. B. Stroustrup, The C++ Programming Language, Second Edition. New York: Addison-Wesley, 1993.
29. A. Turing, "On computable numbers with an application to the Entscheidungsproblem," Proc. London Math. Soc., XLII, pp. 239-265, 1936, with a correction in ibid. XLIII, pp. 544-546. 1937.
30. P.T. Ward and S.J. Mellor, Structured Development for Real-Time Systems, Volumes 1-3, New York, Yourdon Press, 1985.
31. A.W. Wymore, Model-Based Systems Engineering. Boca Raton: CRC Press, 1993.
32. A.W. Wymore, System Functional Analysis. Boca Raton: CRC Press, 1998.

A. Terry Bahill (S'66-M'68-SM'81-F'92) has been a Professor of Systems Engineering at the University of Arizona in Tucson since 1984. He received a BSEE from the University of Arizona in 1967, an MSEE from San Jose State University in 1970 and a Ph.D. in electrical engineering and computer science from the University of California, Berkeley, in 1975. His research interests are in the fields of systems engineering, modeling physiological systems, eye-hand-head coordination, validation of knowledge-based systems, quality improvement, business process redesign, and systems design. He has tried to make the public appreciate engineering research by applying his scientific findings to the sport of baseball.

Bahill is the author of Bioengineering: Biomedical, Medical, and Clinical Engineering, Prentice-Hall, 1981, Keep Your Eye on the Ball: The Science and Folklore of Baseball, (with R.G. Watts), W.H. Freeman, 1990, Verifying and Validating Personal Computer-Based Expert Systems, Prentice-Hall, 1991, Linear Systems Theory, (with F. Szidarovszky), CRC Press, 1992, Engineering Modeling and Design, (with W.L. Chapman and A.W. Wymore), CRC Press, 1992, and Metrics and Case Studies for Evaluating Engineering Designs, (with J.A. Moody, W.L. Chapman and D.F. Van Voorhees), Prentice Hall, 1997. For the Systems, Man, and Cybernetics Society he has served as vice president, as associate editor, as Program Chairman for the 1985 conference in Tucson, and as Conference Co-chairman for the 1988 conference in Beijing and Shenyang, China. He served as an associate editor for the Computer Society's magazine, IEEE Expert. He holds U.S. patent number 5,118,102 for the Bat Chooser, a system that computes the Ideal Bat Weight for individual batters. He is a registered professional engineer and the Editor of the CRC Press Series on Systems Engineering.

Mack Alford received a BA with honors in Mathematics in 1962, an MA in Mathematics and Statistics at UCLA in 1966, and performed graduate work at UCLA in Computer Science as a TRW Fellow from 1969 to 1974. He spent 25 years with TRW, and was the founding technologist for Ascent Logic Corp., which builds the RDD-100 System Designer. He is now an independent consultant, and can be reached at (615) 438-2807 or alford@netcom.com

K. Bharathan (M'93) is a Research Assistant Professor of Surgery at the University of Arizona Medical Center. Bharathan was born in Madras, India, on January 22, 1951. He received a B.A. (Honours) in economics from the University of Delhi, India, in 1973, an M.A. in economics from Jawaharlal Nehru University, New Delhi in 1975, an M.Phil. in economics from the University of Madras, India, in 1979, a Ph.D. in economics from the University of Madras, in 1990 and an M.S. in systems engineering from the University of Arizona, Tucson in 1991. He was on the faculty of the Madras Christian College, India from 1976 through 1978, and thereafter on the faculty of the Madras Institute of Development Studies until 1988. He was a Systems Engineer at Bahill Intelligent Computer Systems in Tucson from 1992 till 1996. His research interests include systems engineering theory; the design, verification and validation of expert systems; the knowledge extraction process; and Object Oriented Systems Engineering. Dr. Bharathan is a member of the IEEE Computer society the IEEE Systems, Man, and Cybernetics society, and the American Medical Informatics Association.

John R. Clymer is a professor of electrical engineering at California State University Fullerton (CSUF) and consults in the area of systems engineering using simulation and artificial intelligence. In addition, to consulting he presents intensive short courses on systems engineering and simulation at various locations around the United States and Taiwan. His research interest currently is intelligent, complex adaptive system architectures such as multi-agent systems. Topics include simulation, adaptive-fuzzy expert system controller, machine learning, evolutionary programming, and general problem solvers and planners. He is a founding member of the Applied Research Center for Systems Science (ARCSS) at CSUF, and is a member of IEEE, SCS, and INCOSE.

Douglas L. Dean is a Research Scientist at the Center for Management Information at the University of Arizona. He received his Master of Accountancy with an emphasis in Information System Consulting from Brigham Young University in 1989 and his Ph.D. in MIS from the University of Arizona in 1995. He provides consulting and research services on a number of topics including electronic meeting systems (EMS), collaborative business process reengineering methods, and collaborative systems analysis and design methods. Dr. Dean has helped develop group-enabled activity and data modeling software to support technical and non-technical users. He also developed structured meeting methods for use with these tools. The activity model software has since been made commercially available through Ventana Corporation (Tucson Arizona). Dr. Dean’s research interests include electronic meeting support of process and data modeling, business process re-engineering, systems analysis and design, and group elicitation of information systems requirements.

Jeremy Duke received his B.S. in Systems (Software) Engineering in 1994, and an M.S. in Systems Engineering in 1996, both from the University of Arizona. He is currently working as a project leader and software engineer at Intel Corporation writing requirements for, designing, and implementing real-time, mission critical station controllers in the Assembly/Test area of manufacturing. His current interests are in software testing and requirements validation techniques.

Greg Hill (M'80) earned the B.S. degree in Nuclear Engineering in 1976 and the M.S. degree in Computer Science in 1978, both from the University of Arizona in Tucson. He is currently an Advisory Engineer at the IBM Tucson Laboratory. He has been employed there since 1978. At IBM he has held a variety of technical assignments in the planning, analysis, design, and implementation of software tools, microcode development and analysis tools, and project management tools. His latest assignments were in the development of tape device microcode and storage control unit microcode. He is a member of the ACM and the IEEE Computer Society.

Edward V. LaBudde (Member IEEE, INCOSE and SPIE) received a BSEE from Michigan State University in 1968 and an MBA from Alabama A&M in 1978. He has over 30 years of experience in advanced development and has extensive experience in entrepreneurial leadership roles for product and organizational development projects. He holds over 30 patents and has published numerous papers on various engineering topics.

Eric J. Taipale (S'93-M'97) earned a BEE degree from the University of Minnesota, Twin Cities in 1994 and an MS degree in Systems Engineering from the University of Arizona in 1996. He is currently a staff engineer in the Advanced Programs group at Lockheed Martin Tactical Defense Systems in Eagan, Minnesota. His current interests are automated signal feature extraction and target classification systems.

A. Wayne Wymore earned BS and MS degrees at Iowa State University, and the Ph.D. at the University of Wisconsin, all in mathematics. He is Professor Emeritus of Systems Engineering at the University of Arizona where he was the first Chairman of the Department of Systems Engineering and first Director of the Computing Center. While managing, teaching, researching and consulting internationally, he authored A Mathematical Theory of Systems Engineering: The Elements, 1967, Systems Engineering Methodology for Interdisciplinary Teams, 1976, and Model-Based Systems Engineering, 1993. System Functional Analysis and System Design, Phase 2 of Model-Based Systems Engineering is forthcoming.