Chapter 7. System Design

Table of Contents:


Chapters 1 to 6 of this book have presented embedded systems from an interfacing or component level. The remaining chapters will focus on systems level design.

7.1. Scheming and Teaming

7.1.1. Design steps

This section lists questions we must answer when starting a new design.

What problem are we trying to solve? One effective way to find problems is to immerse ourselves in the real world. You could travel, avoiding the tourist sites. You could learn a new language. You could learn a new skill. You could spend a day following an expert: doctor, truck driver, carpenter, farmer, etc. You must have domain experts on your team to create systems that truly transform the way things are done. You must learn the language/culture of the domain. These domain experts are then invited into all aspects of the design process.

How is the design to be tested? How is it to be evaluated? We begin every design at the end. We must understand what the system is to do, then we can plan how to test and evaluate it.

What are your inputs? We start with, "what the system needs to know?" We then select input devices to collect that information.

What are your outputs? We ask, "what does the system need to do?" We then select output devices to perform those operations.

How will the user interact with the system? We consider switches, LEDs, sound, touch screen displays, battery charging, and graphical displays.

How might the system fail? We identify risks and include a backup plan.

In summary, we write a requirements document, see Section 1.4.1. In this document we list constraints, requirements, timetable, budget, available parts, user interface, enclosure size/weight, power budget, and wireless capabilities. When writing technical documents use these three words very carefully.

Must: The verb 'must' denotes a mandatory requirement, legal, regulatory, or standard, that is imposed by an outside agency. Failure to achieve this requirement precludes commercialization of the system.

Shall: The verb 'shall' denotes mandatory requirements specified by the company.  Failure to achieve this requirement may preclude commercialization of the system.

Should: The verb 'should' denotes additional requirements that will be addressed by the development program if development time, development cost, and other constraints of the program allow.

There are two approaches to design.  The top-down approach starts with a general overview, like an outline of a paper, and builds refinement into subsequent layers. A top-down designer was once quoted as saying,

            "Write no software until every detail is specified"

Top-down provides a better global approach to the problem. Managers like top-down because it gives them tighter control over their workers. The top-down approach works well when an existing operational system is being upgraded or rewritten.

On the other hand, the bottom-up approach starts with the smallest detail, builds up the system "one brick at a time." The bottom-up approach provides a realistic appreciation of the problem because we often cannot appreciate the difficulty or the simplicity of a problem until we have tried it. It allows engineers to start immediately building and gives engineers more input into the design. For example, a low-level engineers may be able to point out features that are not possible and suggest other features that are even better. Some projects are flawed from their conception. With bottom-up design, the obvious flaws surface early in the development cycle.

I believe bottom-up is better when designing a complex system and specifications are open-ended. On the other hand, top-down is better when you have a very clear understanding of the problem specifications and the constraints of your computer system. One of the best systems I have ever been part of was actually designed twice. The first design was built bottom up and served only to provide a clear understanding of the problem, clarification of the features needed, and the limitations of the hardware and software. We literally threw all the source code and circuit designs, and we reengineered the system in a top-down manner.  

        Diagram of a device that has a speaker and a speaker AI-generated content may be incorrect.

Figure 7.1.1. Medical Device Identifier: original design and final device ready for FDA approval by DesignPlex Biomedical and Bridgesource Medical.  https://www.bridgesourcemedical.com/diagnostics

Arthur C. Clarke's Third Law: Any sufficiently advanced technology is indistinguishable from magic.

J. Porter Clark's Law: Sufficiently advanced incompetence is indistinguishable from malice.

: What is the importance of a domain expert in the initial stages of a design?

 

7.1.2. Modular Programming

The key to completing any complex task is to break it down into manageable subtasks. Modular programming or functional abstraction is a style of software development that divides the software problem into distinct and independent modules. The parts are as small as possible, yet relatively independent. Complex systems designed in a modular fashion are easier to debug because each module can be tested separately. Industry experts estimate that 50 to 90% of software cost is spent in maintenance. All five aspects of software maintenance are simplified by organizing the software system into modules.

       • Correcting mistakes

       • Adding new features

       • Optimizing execution speed

       • Reducing program size

       • Porting to new computers or operating systems

       • Reconfiguring the software to solve similar related programs
 

Observation: Modularity is improved by maximizing the number of modules, minimizing coupling, and maximizing cohesion. 

Modular programming is separating "what the function does" from "how the function works". We can think of it as the three I's:

•         Interface: specifying the function names, input parameters, and output parameters

•         Implementation: the code that makes the functions work

•         Invocation: calling the functions

 

We place function prototypes (interfaces) in the header file. In the header file, we describe "what it does." We place the function definitions (implementations) in the code file. In the code file, we describe "how it works." There is a third file, called testmain, into which we place example usage of the functions (invocations). In the testmain.c file, we also describe "how it was tested."

A module is a collection of functions that perform a well-defined set of tasks. The collection of serial port I/O functions can be considered one module. A collection of 32‑bit math operations is another example of a module. Modular programming involves both the definition of modules and the connection scheme by which the modules are connected to form the software system (call graph). While the module may be called from many locations throughout the system, there should be well-defined interfaces into the module, specified by the prototypes to public functions listed in the header file.

The overall goal of modular programming is to enhance clarity. The smaller the task, the easier it will be to understand.  Coupling is defined as the influence one module's behavior has on another module. To make modules more independent we strive to minimize coupling.

Obvious and appropriate examples of coupling are the input/output parameters explicitly passed from one module to another. On the other hand, information stored in shared global variables can be quite difficult to track. Like global variables, shared access to I/O ports can also introduce unnecessary complexity. Global variables and shared I/O cause coupling between modules that complicate the debugging process because now the modules may not be able to be separately tested. On the other hand, we must use global variables to pass information into and out of an interrupt service routine, and from one call to an interrupt service routine to the next call. Consequently, we create private permanently-allocated variables (declared as static) in one module so interactions can be managed. Similarly, we divide I/O into logical groups (e.g., ADC, Timer0, UART1) and place all access to each I/O group in a separate module. If we need to pass data from one module to another, we use a well-defined interface technique like a mailbox or first-in-first-out (FIFO) queue.

Assign a logically complete task to each module. The module is logically complete when it can be separated from the rest of the system and placed into another application. The interfaces are extremely important (the header file). The interfaces determine the policies of our modules. In other words, the interfaces define the operations of our software system. The interfaces also represent the coupling between modules. In general, we wish to minimize the amount of information passing between the modules yet maximize the number of modules. Of the following three objectives when dividing a software project into subtasks, it is only the first one that matters.

       • Make the software project easier to understand

       • Increase the number of modules

       • Decrease the interdependency (minimize coupling)


We can develop and connect modules in a hierarchical manner. Construct new modules by combining existing modules. In a hierarchical system the modules are organized into a tree-structured call graph. In the call graph, an arrow points from the calling routine to the module it calls. The I/O ports are organized into groups (e.g., all the serial port I/O registers are in one group). The call graph allows us to see the organization of the project. To make simpler call graphs on large projects we can combine multiple related functions into a single module. The main program is at the top and the I/O ports are at the bottom. In a hierarchical system the modules are organized both in a horizontal fashion (grouped together by function) and in a vertical fashion (overall policies decisions at the top and implementation details at the bottom). Since one of the advantages of breaking a large software project into subtasks is concurrent development, it makes sense to consider concurrency when dividing the tasks. In other words, the modules should be partitioned in such a way that multiple programmers can develop the subtasks as independently as possible. On the other hand, careful and constant supervision is required as modules are connected and tested.

Observation: If module A calls module B, and module B calls module A, then you have created a special situation that must account for these mutual calls. 

From a formal perspective, I/O devices are considered as global. This is because I/O devices reside permanently at fixed addresses.  From a syntactic viewpoint any module has access to any I/O device. To reduce the complexity of the system we will restrict the number of modules that actually do access the I/O device. It will be important to clarify which modules have access to I/O devices and when they are allowed to access it. When more than one module accesses an I/O device, then it is important to develop ways to arbitrate (which module goes first if two or more want to access simultaneously) or synchronize (make a second module wait until the first is finished.)

Information hiding is like minimizing coupling. It is better to separate the mechanisms of software from its policies. We should separate what the function does (the relationship between its inputs and outputs) from how it does it. It is good to hide certain inner workings of a module, and simply interface with the other modules through the well-defined input/output parameters. For example, we could implement a FIFO by maintaining the current number of elements in a global variable, Count. A good module will hide how Count is implemented from its users. If the user wants to know how many elements are in the FIFO, it calls a TxFifo_Size() routine that returns the value of Count. A badly written module will not hide Count from its users. The user simply accesses the global variable Count. If we update the FIFO routines, making them faster or better, we might have to update all the programs that access Count too. The object-oriented programming environments provide well-defined mechanisms to support information hiding. This separation of policies from mechanisms can be seen also in layered software.

The Keep It Simple Stupid approach tries to generalize the problem so that it fits an abstract model. Unfortunately, the person who defines the software specifications may not understand the implications and alternatives. Sometimes we can restate the problem to allow for a simpler (and possibly more powerful) solution. As a software developer, we always ask ourselves these questions:

                "How important is this feature?"

                "What alternative ways could this system be structured?"

                "How can I redefine the problem to make it simpler?"
 

We can classify the coupling between modules as highly coupled, loosely coupled, or uncoupled. A highly-coupled system is not desirable, because there is a great deal of interdependence between modules. A loosely-coupled system is optimal, because there is some dependence but interconnections are weak. An uncoupled system, one with no interconnections at all, is typically inappropriate in an embedded system, because all components should be acting towards a common objective. There are three ways in which modules can be coupled. The natural way in which modules are coupled is where one module calls or invokes a function in a second module. This type of coupling, called invocation coupling, can be visualized with a call graph, quantified as the number of calls per fixed time. A second way modules can be coupled is by data transfer. If information flows from one module to another, we classify this as bandwidth coupling.  Bandwidth, which is the information transfer rate, is a quantitative measure of coupling. Bandwidth coupling can be visualized with a data flow graph. The third type of coupling, called control coupling, occurs when actions in one module affect the control path within another module. For example, if Module A sets a global flag and Module B uses the global flag to decide its execution path. Control coupling is hard to visualize and hard to debug. Therefore, it is a poor design to have module interactions with control coupling.

Another way to categorize coupling is to examine how information is passed or shared between modules. We will list the mechanisms from poor to excellent. It is extremely poor design to use globals and allow Module A directly modify data or flags within Module B. Similarly poor design is to organize important data into a common shared global space and allow modules to read and write these data. It is ok to allow Module A to call Module B and pass it a control flag. This control flag will in turn affect the execution within Module B. It is good design to have one module pass data to another module. Data can be structured or unstructured (called primitive). Examples of structured data include

time (hour, minutes, seconds)

stamped (data, time of recording)

images (bmp, jpg, png)

vector drawing (svg)

sounds (wav, mp3)

 

Coupling defines inter-module connections. On the other hand, intra-module connections are also important. We need a way to describe how various components within a module interact with each other. For example, consider a system with 100 functions. How should one divide these functions into modules?

Cohesion is the degree of interrelatedness of internal parts within the module. In general, we wish to maximize cohesion. A cohesive module has all components of the module are directed towards and essential for the same task. It is also important to analyze how components are related as we design modules. Coincidental cohesion occurs when components of the module are unrelated, resulting in poor design. Examples of coincidental cohesion would be a collection of frequently used routines, a collection of routines written by a single programmer, or a collection of routines written during a certain time interval. It is a poor design to have modules with coincidental cohesion.

Logical cohesion is a grouping of components into a single module because they perform similar functions. An example of logical cohesion is a collection of serial output, LCD output, and network output routines into one module because all routines perform output. Organizing modules in this fashion is also poor design and results in modules that are hard to reuse. 

Temporal cohesion combines components if they are connected in time sequence.  If we are baking bread, we activate the yeast in warm water in one bowl, and then we combine the flour, sugar, and spices in another bowl. These two steps are connected only in the sense that we first do one, and then we do another when making bread. If we were making cookies, we would need flour, sugar, and spices but not the yeast. Temporal cohesion is poor design because when we want to mix and match existing modules to create new designs, we expect the sequence of module execution to change.

Another poor design, called procedural cohesion, groups functions together in order to ensure mandatory ordering. For example, an embedded system might have an input port, an output port, and a timer module. To work properly, all three must be initialized. It would be hard to reuse code if we placed all three initialization routines into one module.

We next present appropriate reasons to group components into one module. Communicational cohesion exists when components operate on the same data. An example of communicational cohesion would be a collection of routines that filter and extract features from the data.

Sequential cohesion occurs when components are grouped into one module, because the output from one component is the input to another component. Sequential cohesion is a natural consequence of minimizing bandwidth between modules. An example of sequential cohesion is a fuzzy logic controller. This controller has five stages: crisp input, fuzzification, rules, defuzzification, and crisp output. The output of each stage is the input to the next stage. The input bandwidth to the controller and the output bandwidth from the controller can be quite low, but the amount of information transferred between stages can be thousands of times larger. Executing machine learning models has this same sequential cohesion, because the output of one stage will be the input to the next.

The best kind of cohesion is functional cohesion, where all components combine to implement a single subsystem, and each component has a necessary contribution to the objective. I/O device drivers, which are a collection of routines for a single I/O device, exhibit functional cohesion.

Another way to classify good and bad modularity is to observe fan in and fan out behavior. In a data flow graph, the tail of an arrow defines a data output, and the head of an arrow defines a data input. The fan in of a module is the number of other modules that have direct control on that module. Fan in can be visualized by counting the number of arrowheads that terminate on the module in the data flow graph, shown previously in Figure 1.4.2. The fan out of a module is the number of other modules directly controlled by this module. Fan out can be visualized by counting the number of tails of arrows that originate on the module in the data flow graph. In general, a system with high fan out is poorly designed, because that one module may constitute a bottleneck or a critical safety path. In other words, the module with high fan out is probably doing too much, performing the tasks that should be distributed to other modules. High fan in is not necessarily a poor design, depending on the application.

Figure 1.4.2. A data flow graph showing how signals pass through a motor controller.

: What is the fan in and fan out of the Controller Software in Figure 1.4.2?

 

7.1.3. Clients and Coworkers

Good engineers employ well-defined design processes when developing complex systems. When we work within a structured framework, it is easier to prove our system works (verification) and to modify our system in the future (maintenance). As our systems become more complex, it becomes increasingly important to employ well-defined design processes. In this chapter, a very detailed set of software development rules will be presented. At first, it may seem radical to force such a rigid structure to software. We might wonder if creativity will be sacrificed in the process. True creativity is more about effective solutions to important problems and not about being sloppy and inconsistent. Because maintenance is a critical task, the time spent organizing, documenting, and testing during the initial development stages will reap huge dividends throughout the life of the project.

Observation: The easiest way to debug is to write software without any bugs.

We define clients as people who will use our software. Sometimes, the client is the end-user who uses the embedded system. Other times, we develop hardware/software components that plug into a larger system. In this case, the client develops hardware/software that will use our components. We define coworkers as engineers who will maintain our system. We must make it easy for a coworker to debug, use, and extend our system.

: Of the three I's which two are meant for the clients?

Developing quality systems has a lot to do with attitude. We should be embarrassed to ask our coworkers to make changes to our poorly written software or sloppy hardware designs. Since so much of a system's life involves maintenance, we should create components that are easy to change. In other words, we should expect each piece of our designs will be read by another engineer in the future, whose job it will be to make changes to our design. We might be tempted to quit a project once the system is running, but this short time we might save by not organizing, documenting, and testing will be lost many times over in the future when it is time to update the system.

Observation: Much of the engineering design that university professors require of their students is completely unrealistic. Professors give a lab assignment on day 1, expect the students to complete it with demo and report 7 days later, and then the professors grade it. Often, professors give passing grades for designs that only partially work. The design is then tossed in the trash never to be looked at again.

As project managers, we must reward good behavior and punish bad behavior. A company, to improve the quality of their software products, implemented the following policies.

"The employees in the customer relations department receive a bonus for every software bug that they can identify. These bugs are reported to the software developers, who in turn receive a bonus for every bug they fix."

: Why did the above policy fail horribly?

We should demand of ourselves that we deliver bug-free software to our clients.  Again, we should be embarrassed when our clients report bugs in our code. We should be ashamed when other programmers find bugs in our code. There are five steps we can take to facilitate this important aspect of software design.

Test it now. When we find a bug, fix it immediately. The longer we put off fixing a mistake the more complicated the system becomes, making it harder to find. Remember that bugs do not go away automatically, but we can make the system so complex that the bugs will manifest themselves in a mysterious and obscure fashion. For the same reason, we should completely test each module individually, before combining them into a larger system. We should not add new features before we are convinced the existing features are bug-free. In this way, we start with a working system, add features, and then debug this system until it is working again.

This incremental approach makes it easier to track progress. It allows us to undo bad decisions, because we can always revert to a previous working system. Adding new features before the old ones are debugged is very risky. With this sloppy approach, we could easily reach the project deadline with 100% of the features implemented but have a system that doesn't run. In addition, once a bug is introduced, the longer we wait to remove it, the harder it will be to correct. This is particularly true when the bugs interact with each other. Conversely, with the incremental approach, when the project schedule slips, we can deliver a working system at the deadline that supports some of the features.   

Maintenance Tip: Go from working system to working system.

Plan for testing. How to test should be considered at the beginning, middle, and end of a project. Testing should be included as part of the initial design. Our testing and the client's usage go hand in hand. How we test the software module will help the client understand the context and limitations of how our software is to be used. It often makes sense to explain the testing procedures to the client as an effort to communicate the features and limitations of the module. Furthermore, a clear understanding of how the client wishes to use our software is critical for both the software design and its testing. For example, after seeing how you tested the module, the client may respond, "That's nice, but what I really want it to do is ...". If this happens, it makes sense to rewrite the requirements document to reflect this new understanding of the client's expectation.

Maintenance Tip: It is better to have some parts of the system that run with 100% reliability than to have the entire system with bugs.

Get help. Use whatever features are available for organization and debugging. Pay attention to warnings, because they often point to misunderstandings about data or functions.  Misunderstanding of assumptions can cause bugs when the software is upgraded or reused in a different context than originally conceived. Remember that computer time is a lot cheaper than programmer time. It is a mistake to debug an embedded system simply by observing its inputs and outputs. We need to use both software and hardware debugging tools to visualize internal parameters within the system.

Maintenance Tip: It is better to have a system that runs slowly than to have one that doesn't run at all.

Divide and conquer. In the early days of microcomputer systems, software size could be measured in hundreds of lines of source code or thousands of bytes of object code. These early systems, due to their small size, were inherently simple. The explosion of hardware technology (both in speed and size) has led to a similar increase in the size of software systems. The only hope for success in a large software system will be to break it into simple modules. In most cases, the complexity of the problem itself cannot be avoided. E.g., there is just no simple way to get to the moon. Nevertheless, a complex system can be created out of simple components. A real creative effort is required to orchestrate simple building blocks into larger modules, which themselves are grouped.  We use our creativity to break a complex problem into simple components, rather than developing complex solutions to simple problems.

Observation: There are two ways of constructing a software design: one way is to make it so simple that there are obviously no deficiencies and the other way is make it so complicated that there are no obvious deficiencies. C.A.R. Hoare, "The Emperor's Old Clothes," CACM Feb. 1981.

Avoid inappropriate I/O. One of the biggest mistakes beginning programmers make is the inappropriate usage of I/O calls (e.g., screen output and keyboard input). An explanation for their foolish behavior is that they haven't had the experience yet of trying to reuse software they have written for one project in another project. Software portability is diminished when it is littered with user input/output. To reuse software with user I/O in another situation, you will almost certainly have to remove the input/output statements. In general, we avoid interactive I/O at the lowest levels of the hierarchy, rather return data and flags and let the higher-level program do the interactive I/O. Often we add keyboard input and screen output calls when testing our software. It is important to remove the I/O that not directly necessary as part of the module function. This allows you to reuse these functions in situations where screen output is not available or appropriate. Obviously, screen output is allowed if that is the purpose of the routine.

Common Error: Performing unnecessary I/O in a subroutine makes it harder to reuse at a later time.

 

7.1.4. Software Performance Metrics

Software development is like other engineering tasks. We can choose to follow well-defined procedures during the development and evaluation phases, or we can meander in a haphazard way and produce code that is hard to test and harder to change. The goal of the system is to satisfy the stated objectives such as accuracy, stability, and input/output relationships. Nevertheless, it is appropriate to separately evaluate the individual components of the system. Therefore, in this section, we will evaluate the quality of our software. There are two categories of performance criteria with which we evaluate the "goodness" of our software. Quantitative criteria include dynamic efficiency (speed of execution), static efficiency (ROM and RAM program size), and accuracy of the results. Qualitative criteria center on ease of software maintenance. Another qualitative way to evaluate software is ease of understanding. If your software is easy to understand then it will be:

Easy to debug, including both finding and fixing mistakes

Easy to verify, meaning we can prove it is correct

Easy to maintain, meaning we can add new features

 

Common error: Programmers who sacrifice clarity in favor of execution speed often develop software that runs fast but is error-prone and difficult to change. 

Golden Rule of Software Development: Write software for others as you wish they would write for you.

To evaluate our software quality, we need performance measures. The simplest approaches to this issue are quantitative measurements. Dynamic efficiency is a measure of how fast the program executes. It is measured in seconds or processor bus cycles. Because of the complexity of the Cortex-M, it will be hard to estimate execution speed by observing the assembly language generated by the compiler. Rather, we will employ methods to experimentally measure execution speed (see Section 1.11.4 Performance Debugging and see 1.11.5 Profiling). Static efficiency is the number of memory bytes required. Since most embedded computer systems have both RAM and ROM, we specify memory requirement in global variables, stack space, fixed constants, and program object code. The global variables plus maximum stack size must fit into the available RAM. Similarly, the fixed constants plus program size must fit into the available ROM. We can judge our software system according to whether it satisfies given constraints, like software development costs, memory available, and timetable. Many of the system specifications are quantitative, and hence the extent to which the system meets specifications is an appropriate measure of quality.

Qualitative performance measurements include those parameters to which we cannot assign a direct numerical value. Often in life the most important questions are the easiest to ask, but the hardest to answer. Such is the case with software quality. So therefore, we ask the following qualitative questions. Can we prove our software works? Is our software easy to understand? Is our software easy to change? Since there is no single approach to writing quality software, I can only hope to present some techniques that you may wish to integrate into your own software style.  In fact, we will devote most of this chapter to the important issue of developing quality designs. We will study self-documented code, abstraction, modularity, and layered software. These parameters indeed have a profound effect on the bottom-line financial success of our projects. Although quite real, because there is often not an immediate and direct relationship between software quality and profit, we may be tempted to dismiss its importance.

Observation: Most people get better with practice. So, if you wish to become a better programmer, I suggest you write great quantities of software.

: A common saying is it takes 10,000 hours of practice to reach expert status. Assume you can write a rate of 100 lines of good code per hour. How many lines of code will it take for you to become an expert? Don't be discouraged, the path to excellence is taken one step at a time.

To get a benchmark on how good a programmer you are, I challenge you to do two tests. In the first test, find a major piece of software that you have written over 12 months ago, and then see if you can still understand it enough to make minor changes in its behavior. The second test is to exchange with a peer a major piece of software that you have both recently written (but not written together), then in the same manner, if you can make minor changes to each other's software.

Observation: You can tell if you are a good programmer if 1) you can understand your own code 12 months later, and 2) others can make changes to your code.

7.1.5. Enhancing Team Skills

A team is a small number of people with complementary skills who are committed to a common purpose, performance goals, and approach for which they are mutually accountable.

When we form teams, we expect the following behaviors:

•         Be respectful of yourself and others

•         Listen attentively without judging and without criticism

•         Remove your ego from the discussions

•         Answer communication quickly, even if you need to say "I'll get back to you later"

•         Give constructive feedback

•         Agree on a time and place to meet

•         Team members form relationships, caring for each other

•         Put a time limit on meetings, start on time, end on time

 

Effective team checklist

•         Define and understand the common goal for the project

•         Make a list of tasks to be completed

•         Be dedicated to the goal with unified effort

•         Problems and changes are anticipated and accepted

•         Assign responsibility for all tasks and distribute them appropriately

•         Develop a timeline and stick to it, but allow for slippage

•         Develop and post a Gantt chart for the plan

•         Document key decisions and actions from all team meetings

•         Send reminders when deadlines approach

•         Send confirmation when tasks are completed

•         Collectively review the project output for quality

 

Skills to manage conflict

•         Acknowledge that the conflict exists and stay focused on the goal

•         Gain common ground

o    Seek to understand all angles: Let each person state his or her view briefly

o    Have neutral team members reflect on areas of agreement or disagreement

o    Explore areas of disagreement regarding specific issues

o    Have opponents suggest modifications to their points of view as well as others

o    If consensus is blocked, ask opponents if they can accept the team's decision

•         Attack the issue, not each other

•         Develop an action plan.

 

References

1.       Katzenbach, J.R. & Smith, D.K. (2015). The Wisdom of Teams: Creating the High-performance Organization. Boston: Harvard Business School.

2.       Breslow, L. Teaching Teamwork Skills, Part 2. Teach Talk,  

3.       High Performance Team Essential Elements. Penn State University

4.       https://www.tempo.io/blog/signs-strong-teamwork

 

 

7.2. Software Style Guidelines

One of the wonderful benefits of being project leader is the establishment of software style guidelines. These guidelines are not necessary for the program to compile or to run. Rather the intent of the rules is to make the software easier to understand, easier to debug, and easier to change. Just like beginning an exercise program, these rules may be hard to follow at first, but the discipline will pay dividends in the future.

Observation: There are many style guidelines from which you could select. It is not important to follow our guidelines, but rather it is important to follow some guidelines. 

7.2.1. Variables

Variables are an important component of software design, and there are many factors to consider when creating variables. Some of the obvious considerations are the allocation, size, and format of the data. However, an important factor involving modular software is scope. The scope of a variable defines which software modules can access the data. Variables with a restricted access are classified as private, and variables shared between multiple modules are public. We can restrict the scope to a single file, a single function, or even a single program block within a matching pair of braces, {}. In general, the more we limit the scope of our variables the easier it is to design (because the modules are smaller and simpler), to change (because code can be reused), and to verify (because interactions between modules are well-defined). However, since modules are not completely independent, we need a mechanism to transfer information from one to another. The allocation of a variable specifies where or how it exists. Because their contents are allowed to change, all variables must be allocated in registers or in RAM, but not in ROM. Constants can and should be allocated in ROM. Global variables contain information that is permanent and are usually assigned a fixed location in RAM. Global variables have public scope, in other words can be accessed by any software. Local variables contain temporary information and are stored in a register or allocated on the stack. Static variables have permanent allocation but restricted scope. Static variables can have scope restricted to one file, to one function or just within one brace.

A local variable has temporary allocation because we create local variables on the stack or in registers. Because the stack and registers are unique to each function, this information cannot be shared with other software modules. Therefore, under most situations, we can further classify these variables as private. Local variables are allocated, used, and then deallocated, in this specific order. For speed reasons, we wish to assign local variables to a register. When we assign local variable to a register, we can do so in a formal manner. There will be a certain line in the assembly software at which the register begins to contain the variable (allocation), followed by lines where the register contains the information (access or usage), and a certain line in the software after which the register no longer contains the information (deallocation). In C, we define local variables after an opening brace.

void MyFunction(void){ uint16_t i;     // i is a local

  for(i = 0; i < 10; i++){ uint32_t j; // j is a local

    j = i+100;

    UART_OutUDec(j);

  }

}
 

The information stored in a local variable is not permanent. This means if we store a value into a local variable during one execution of the module, the next time that module is executed the previous value is not available. Examples include loop counters and temporary sums. We use a local variable to store data that are temporary in nature. With a local variable only the program that created the local variable can access it. We can implement a local variable using the stack or registers. Some reasons why we choose local variables over global variables:

•         Dynamic allocation/release allows for reuse of RAM

•         Limited scope of access (making it private) provides for data protection

•         Since an interrupt will save registers and create its own stack frame, it works correctly if called from multiple concurrent threads (reentrant)

•         Since absolute addressing is not used, the code is relocatable

 

A global variable is allocated permanently in RAM and fixed location in RAM. A public global variable contains information that is shared by more than one program module. We must use parmanently allocated variables to pass data between the main program (i.e., foreground thread) and an ISR (i.e., background thread). Defining the variable as static, private to the file, reduces the scope making it easier to debug. Global and static variables are allocated at compile time and never deallocated. The information they store is permanent. Examples include time of day, date, calibration tables, user name, temperature, FIFO queues, and message boards. When dealing with complex data structures, pointers to the data structures are shared. In general, it is a poor design practice to employ public global variables. On the other hand, static variables are necessary to store information that is permanent in nature. In C, we define global variables outside of the function.

int32_t Count=0;  // Count is a global variable
void MyFunction(void){
  Count++;        // number of times function was called
}

: How do you create a local variable in C?

Sometimes we store temporary information in global variables out of laziness. This practice is to be discouraged because it wastes memory and may cause the module to work incorrectly if called from multiple concurrent threads (non-reentrant). Non-reentrant programs can produce very sneaky bugs, since they might only crash in rare situations when the same code called from different threads when the first thread is in a particular critical section. Such a bug is difficult to reproduce and diagnose. In general, it is good design to limit the scope of a variable as much as possible.

: How do you create a global variable in C?

In C, a static local has permanent allocation, which means it maintains its value from one call to the next. It is still local in scope, meaning it is only accessible from within the function. I.e., modifying a local variable with static changes its allocation (it is now permanent), but doesn't change its scope (it is still private). In the following example, count contains the number of times MyFunction is called. The initialization of a static local occurs just once, during startup.

void MyFunction(void){
static int32_t count=0;
  count++;     // number of times function was called
}

In C, we create a private global variable using the static modifier. Adding static to an otherwise global variable does not change its allocation (it is still permanent), but does reduce its scope. Regular globals can be accessed from any function in the system (public), whereas a static variable can only be accessed by functions within the same file. Static globals are private to that particular file. Functions can be static also, meaning they can be called only from other functions in the file. E.g.,

static int16_t myPrivateGlobalVariable; // accessed in this file only
void static MyPrivateFunction(void){    // accessed in this file only
// can access myPrivateGlobalVariable
}

In C, a const global is read-only. It is allocated in the ROM. Constants, of course, must be initialized at compile time. E.g.,

const int16_t Slope=21; 
const uint8_t SinTable[8]={0,50,98,142,180,212,236,250};
 

: How does the static modifier affect locals, globals, and functions in C? 

: How does the const modifier affect a global variable in C?

: How does the const modifier affect a function parameter in in C?

If you leave off the const modifier in the SinTable example, the table will be allocated twice, once in ROM containing the initial values, and once in RAM containing data to be used at run time. Upon startup, the system copies the ROM-version into the RAM-version.

Maintenance Tip: It is good practice to specify the units of a variable (e.g., volts, cm etc.). 

Maintenance Tip: It is good practice to reduce the scope as much as possible. 

In summary, there are three types of variables:

Globals (public scope, permanent allocation),

Statics (private scope, permanent allocation), and

Locals (private scope, temporary allocation).

 

7.2.2. Organization of a code file

One of the recurring themes of this software style section is consistency. Maintaining a consistent style will help us locate and understand the different components of our software, as well as prevent us from forgetting to include a component or worse, including it twice.

The following regions should occur in this order in every code file (e.g., file.c).

Opening comments. The first line of every file should contain the file name. Remember that these opening comments will be duplicated in the corresponding header file (e.g., file.h) and are intended to be read by the client, the one who will use these programs. If major portions of this software are copied from copyrighted sources, then we must satisfy the copyright requirements of those sources. The rest of the opening comments should include

•         The overall purpose of the software module

•         The names of the programmers

•         The creation (optional) and last update dates

•         The hardware/software configuration required to use the module

•         Copyright information
 

Including .h files. Next, we will place the #include statements that add the necessary header files. Normally the order doesn't matter, so we will list the include files in a hierarchical fashion starting with the lowest level and ending at the highest high. If the order of these statements is important, then write a comment describing both what the proper order is and why the order is important. Putting them together at the top will help us draw a call graph, which will show us how our modules are connected.  In particular, if we consider each code file to be a separate module, then the list of #include statements specify which other modules can be called from this module. Of course, one header file is allowed to include other header files. However, we should avoid having one header file include other header files. This restriction makes the organizational structure of the software system easier to observe. Be careful to include only those files that are absolutely necessary. Adding unnecessary include statements will make our system seem more complex than it is.

Including .c files. You should not include other code files, rather code files are listed in the project settings. Including code files confuses the overall structure of the software system.

Observation: Looking at the project window and the #include statements, one can draw the system call graph.

#define statements. Next, we should place the #define macros. These macros can define operations or constants. Since these definitions are located in the code file (e.g., file.c), they will be private. This means they are available within this file only. If the client does not need to use or change the macro operation or constant, then it should be made private by placing it here in the code file. Conversely, if we wish to create public macros, then we place them in the header file for this module.

struct union enum statements. After the define statements, we should create the necessary data structures using struct union and enum. Again, since these definitions are located in the code file (e.g., file.c), they will be private. If they need to be public, we place them in the header file.

Global variables, static variables, and constants. After the structure definitions, we should include the globals, statics, and constants. There are two aspects of data that are important. First, we can specify where the data is allocated. If it is a variable that needs to exist permanently, we will place it in RAM as a global or static. If it is a constant that needs to exist permanently, we will place it in ROM using const. If the data is needed temporarily, we can define it as a local. The compiler will allocate locals in registers or on the stack in whichever way is most efficient.

int32_t PublicGlobal;               // accessible by any module
static int32_t PrivateStatic;       // accessible in this file only
const int32_t Constant=1234567;     // in ROM
void function(void){
  static int32_t veryPrivateStatic; // accessible by this function only
  int32_t privateLocal;             // accessible by this function only
}

A global variable has permanent allocation and public scope. In the above examples, PublicGlobal PrivateGlobal and veryPrivateGlobal are global. Constant will be defined in ROM, and cannot be changed. We define a local variable as one with temporary allocation. The variable privateLocal is local and may exist on the stack or in a register.

The second aspect of the data is its scope. Scope specifies which software can access the data. Public variables can be accessed by any software. Private variables have restricted scope, which can be limited to the one file, the one function, or even to one {} program block. In general, we wish to minimize the scope of our data. Minimizing scope reduces complexity and simplifies testing. If we specify the global with static, then it will be private and can only be accessed by programs in this file. If we do not specify the global with static then it will be public, and it can be accessed any program. For example, the PublicGlobal variable can be defined in other files using extern and the linker will resolve the reference. However, the PrivateGlobal cannot be accessed from software outside of the one file in which this variable is defined. Again, we classify PrivateGlobal as private because its scope is restricted. We put all the globals together before any function definitions to symbolize the fact that any function in this file has access to these globals. If we have a permanent variable that is only accessed by one function, then it should be defined inside the function with static. For example, the variable veryPrivateGlobal is permanently allocated in RAM, but can only be accessed by the function.

Maintenance Tip: Reduce complexity in our system by restricting direct access to our data. E.g., make global variables static if possible.

Prototypes of private functions. After the globals, we should add any necessary prototypes. Just like global variables, we can restrict access to private functions by defining them as static. Prototypes for the public functions will be included in the corresponding header file. In general, we will arrange the code implementations in a top-down fashion. Although not necessary, we will include the parameter names with the prototypes. Descriptive parameter names will help document the usage of the function. For example, which of the following prototypes is easier to understand?

static void plot(int16_t, int16_t);

static void plot(int16_t time, int16_t pressure);

 

Maintenance Tip: Reduce complexity in our system by restricting the software that can call a function E.g., make functions static if possible.

Implementations of the functions. The heart of the implementation file will be, of course, the implementations. Again, private functions should be defined as static. The functions should be sequenced in a logical manner. The most typical sequence is top-down, meaning we begin with the highest level and finish with the lowest level. Another appropriate sequence mirrors the manner in which the functions will be used. For example, start with the initialization functions, followed by the operations, and end with the shutdown functions. For example:

Open

Input

Output

Close
 

Including .c files. If the compiler does not support projects, then we would end the file with #include statements that add the necessary code files. Since most compilers support projects, we should use its organizational features and avoid including code files. The project simplifies the management of large software systems by providing organizational structure to the software system. Again, if we use projects, then including code files will be unnecessary, and hence should be avoided.

Employ run-time testing. If our compiler supports assert() functions, use them liberally. Place assertions at the beginning of functions to test the validity of the input parameters. Place assertions after calculations to test the validity of the results. Place assertions inside loops to verify indices and pointers are valid. There is a secondary benefit to assertions; they provide inherent documentation of the assumptions.

7.2.3. Organization of a header file

Once again, maintaining a consistent style facilitates understanding and helps to avoid errors of omission. Definitions made in the header file will be public, i.e., accessible by all modules. As stated earlier, it is better to have permanent data stored as static variables and create a well-defined mechanism to access the data.  In general, nothing that requires allocation of RAM or ROM should be placed in a header file.

There are two types of header files. The first type of header file has no corresponding code file. In other words, there is a file.h, but no file.c. In this type of header, we can list global constants and helper macros.  Examples of global constants are data types (see integer.h), I/O port addresses (see tm4c123ge6pm.h), and calibration coefficients. Debugging macros could be grouped together and placed in a debug.h file. We will not consider software in these types of header files as belonging to a particular module.

The second type of header file does have a corresponding code file. The two files, e.g., file.h, and file.c, form a software module. In this type of header, we define the prototypes for the public functions of the module. The file.h contains the policies (behavior or what it does) and the file.c file contains the mechanisms (functions or how it works.) The following regions should occur in this order in every header file.

Opening comments. The first line of every file should contain the file name. This is because some printers do not automatically print the name of the file. Remember that these opening comments should be duplicated in the corresponding code file (e.g., file.c) and are intended to be read by the client, the one who will use these programs. We should repeat copyright information as appropriate. The rest of the opening comments should include

The overall purpose of the software module

The names of the programmers

The creation optional and last update dates

The hardware/software configuration required to use the module

Copyright information
 

Including .h files. Nested includes in the header file should be avoided. As stated earlier, nested includes obscure the way the modules are interconnected.

#define statements. Public constants and macros are next. Special care is required to determine if a definition should be made private or public. One approach to this question is to begin with everything defined as private, and then we shift definitions into the public category only when deemed necessary for the client to access in order to use the module. If the parameter relates to what the module does or how to use the module, then it should probably be public. On the other hand, if it relates to how it works or how it is implemented, it should probably be private.

struct union enum statements. The definitions of public structures allow the client software to create data structures specific for this module.

extern references. Extern definitions are how one file accesses global variables declared in another file. Since global variables should be avoided, externs should also be avoided. However, if you use global variables, declaring them in the header file will help us see how this software system fits together (i.e., is linked to) other systems. External references will be resolved by the linker, when various modules are linked together to create a single executable application. The following example shows how to create a global variable in ModuleA and access it in ModuleB. Notice the similarities in interface, implementation, invocation between the global variable x and the public function A_Init.

// ModuleA.h

extern uint32_t A_x;

void A_Init(void);

// ModuleA.c

#include "ModuleA.h"

uint32_t A_x;

void A_Init(void){

  A_x = 0;

}

// ModuleB.c

#include "ModuleA.h"

void FunB(void){

  A_x++;

}

 

: Where do we place the interfaces and implementations of globals?

Prototypes of public functions. The prototypes for the public functions are last. Just like the implementation file, we will arrange the code implementations in a top-down fashion. Comments should be directed to the client, and these comments should clarify what the function does and how the function can be used. Examples of how to use the module could be included in the comments.

Often, we wish to place definitions in the header file that must be included only once. If multiple files include the same header file, the compiler will include the definitions multiple times. Some definitions, such as function prototypes, can be defined then redefined. However, a common approach to header files uses #ifndef conditional compilation. If the object is not defined, then the compiler will include everything from the #ifndef until the matching #endif. Inside of course, we define that object so that the header file is skipped on subsequent attempts to include it. Each header file must have a unique object. One way to guarantee uniqueness is to use the name of the header file itself in the object name.

#ifndef __File_H__
#define __File_H__
struct Position{
  int bValid;    // true if point is valid
  int16_t x;     // in cm
  int16_t y;     // in cm
};
typedef struct Position Position_t;
#endif
 

7.2.4. Formatting

Make the software easy to read. I strongly object to hardcopy printouts of computer programs during the development phase of a project. At this time, there are frequent updates made by multiple members of the software development team. Because a hardcopy printout will be quickly obsolete, we should develop and debug software by observing it on the computer screen. To eliminate horizontal scrolling, no line of code should be wider than the size of the editor screen. If we do make hard copy printouts of the software at the end of a project, this rule will result in a printout that is easy to read.

Indentation should be set at 2 spaces. When transporting code from one computer to another, the tab settings may be different. So, tabs that look good on one computer may look ugly on another. For this reason, we should avoid tabs and use just spaces. Local variable definitions can go on the same line as the function definition, or in the first column on the next line.

Be consistent about where we put spaces. Similar to English punctuation, there should be no space before a comma or a semicolon, but there should be at least one space or a carriage return after a comma or a semicolon. There should be no space before or after open or close parentheses. Assignment and comparison operations should have a single space before and after the operation. One exception to the single space rule is if there are multiple assignment statements, we can line up the operators and values.  For example,

  voltage   =  1;
  pressure |=  100;
  status   &= ~0x02;
 

Be consistent about where we put braces {}. Misplaced braces cause both syntax and semantic errors, so it is critical to maintain a consistent style. Place the opening brace at the end of the line that opens the scope of the multi-step statement. The only code that can go on the same line after an opening brace is a local variable declaration or a comment. Placing the open brace near the end of the line provides a visual clue that a new code block has started.  Place the closing brace on a separate line to give a vertical separation showing the end of the multi-step statement. The horizontal placement of the close brace gives a visual clue that the following code is in a different block.   For example,

void main(void){ int i, j, k;
  j = 1;
  if(sub0(j)){
    for(i = 0; i < 6; i++){
      sub1(i);
    }
    k = sub2(i, j);
  }
  else{
    k = sub3();
  }
}
 

Use braces after all if, else, for, do, while, case, and switch commands, even if the block is a single command. This forces us to consider the scope of the block making it easier to read and easier to change. For example, assume we start with the following code.

  if(flag)
    n = 0;
 

Now, we add a second statement that we want to execute also if the flag is true. The following error might occur if we just add the new statement.

  if(flag)
    n = 0;
    c = 0;
 

If all our blocks are enclosed with braces, we would have started with the following.

  if(flag){
    n = 0;
  }
 

Now, when we add a second statement, we get the correct software.

  if(flag){
    n = 0;
    c = 0;
  }

7.2.5. Code Structure

Make the presentation easy to read. We define presentation as the look and feel of our software as displayed on the screen. If at all possible, the size of our functions should be small enough so the majority of a "single idea" fits on a single computer screen. We must consider the presentation as a two-dimensional object. Consequently, we can reduce the 2-D area of our functions by encapsulating components and defining them as private functions, or by combining multiple statements on a single line. In the horizontal dimension, we are allowed to group multiple statements on a single line only if the collection makes sense. We should list multiple statements on a single line, if we can draw a circle around the statements and assign a simple collective explanation to the code.

Observation: Most professional programmers do not create hard copy printouts of the software. Rather, software is viewed on the computer screen, and developers use a code repository like Git or SVN to store and share their software.

Another consideration related to listing multiple statements on the same line is debugging. The compiler often places debugging information on each line of code. Breakpoints in some systems can only be placed at the beginning of a line. Consider the following three presentations. Since the compiler generates the same code in each case, the computer execution will be identical. Therefore, we will focus on the differences in style. The first example has a horrific style.

void testFilter(int32_t start, int32_t stop, int32_t step){ int32_t x,y;

  initFilter();UART_OutString("x(n) y(n)"); UART_OutChar(CR);

  for(x=start;x<=stop; x=x+step){ y=filter(x); UART_OutUDec(x);

  UART_OutChar(SP); UART_OutUDec(y); UART_OutChar(CR);} }

 

The second example places each statement on a separate line. Although written in an adequate style, it is unnecessarily vertical.

void testFilter(int32_t start, int32_t stop, int32_t step){

int32_t x;

int32_t y;

  initFilter(); 

  UART_OutString("x(n) y(n)");

  UART_OutChar(CR);

  for(x = start; x <= stop; x = x+step){

    y = filter(x);   

    UART_OutUDec(x);

    UART_OutChar(SP);

    UART_OutUDec(y);

    UART_OutChar(CR);

  }

}

The following implementation groups the two variable definitions together because the collection can be considered as a single object. The variables are related to each other. Obviously, x and y are the same type (32-bit signed), but in a physical sense, they would have the same units. For example, if x represents a signal in mV, then y is also a signal in mV. Similarly, the UART output sequences cause simple well-defined operations.

void testFilter(int32_t start, int32_t stop, int32_t step){ int32_t x, y;

  initFilter(); 

  UART_OutString("x(n) y(n)"); UART_OutChar(CR);

  for(x = start; x <= stop; x = x+step){

    y = filter(x);   

    UART_OutUDec(x); UART_OutChar(SP); UART_OutUDec(y); UART_OutChar(CR);

  }

}

The "make the presentation easy to read" guideline sometimes comes in conflict with the "be consistent where we place braces" guideline. For example, the following example is obviously easy to read but violates the placement of brace rule.

 for(i = 0; i < 6; i++) dataBuf[i] = 0;
 

When in doubt, we will always be consistent where we place the braces. The correct style is also easy to read.

  for(i = 0; i < 6; i++){
    dataBuf[i] = 0;
  }
 

Employ modular programming techniques. Complex functions should be broken into simple components, so that the details of the lower-level operations are hidden from the overall algorithms at the higher levels. An interesting question arises: Should a subfunction be defined if it will only be called from a single place? The answer to this question, in fact the answer to all questions about software quality, is yes if it makes the software easier to understand, easier to debug, and easier to change.

Minimize scope. In general, we hide the implementation of our software from its usage. The scope of a variable should be consistent with how the variable is used. In a military sense, we ask the question, "Which software has the need to know?"  Global variables should be used only when the lifetime of the data is permanent, or when data needs to be passed from one thread to another. Otherwise, we should use local variables. When one module calls another, we should pass data using the normal parameter-passing mechanisms. As mentioned earlier, we consider I/O ports in a manner like global variables. There is no syntactic mechanism to prevent a module from accessing an I/O port, since the ports are at fixed and known absolute addresses. Processors used to build general purpose computers have a complex hardware system to prevent unauthorized software from accessing I/O ports, but the details are beyond the scope of this book. In most embedded systems, however, we must rely on the does-access rather than the can-access method when dealing with I/O devices. In other words, we must have the discipline to restrict I/O port access only in the module that is designed to access it. For similar reasons, we should consider each interrupt vector address separately, grouping it with the corresponding I/O module, even though there will be one file containing all the vectors.

Use types. Using a typedef will clarify the format of a variable. It is another example of the separation of mechanism and policy. New data types will end with _t. The typedef allows us to hide the representation of the object and use an abstract concept instead. For example,

typedef int16_t Temperature_t; 
void main(void){ Temperature_t lowT, highT;
}
 

This allows us to change the representation of temperature without having to find all the temperature variables in our software.  Not every data type requires a typedef. We will use types for those objects of fundamental importance to our software, and for those objects for which a change in implementation is anticipated. As always, the goal is to clarify. If it doesn't make it easier to understand, easier to debug, or easier to change, don't do it.

Prototype all functions. Public functions obviously require a prototype in the header file. In the implementation file, we will organize the software in a top-down hierarchical fashion. Since the highest-level functions go first, prototypes for the lower-level private functions will be required. Grouping the low-level prototypes at the top provides a summary overview of the software in this module. Include both the type and name of the input parameters. Specify the function as void even if it has no parameters. These prototypes are easy to understand:

void start(int32_t period, void(*functionPt)(void));
int16_t divide(int16_t dividend, int16_t divisor);
 

These prototypes are harder to understand:

start(int32_t, (*)());
int16_t divide(int16_t, int16_t);
 

Declare data and parameters as const whenever possible. Declaring an object as const has two advantages. The compiler can produce more efficient code when dealing with parameters that don't change. The second advantage is to catch software bugs, i.e., situations where the program incorrectly attempts to modify data that it should not modify. 

goto statements are not allowed.  Debugging is hard enough without adding the complexity generated when using goto.  A corollary to this rule is when developing assembly language software, we should restrict the branching operations to the simple structures allowed in C (if-then, if-then-else, while, do-while, and for-loop).

++ and -- should not appear in complex statements. These operations should only appear as commands by themselves. Again, the compiler will generate the same code, so the issue is readability. The statement

  *(--pt) = buffer[n++];
 

should have been written as

  --pt;
  *(pt) = buffer[n];
  n++;
 

If it makes sense to group, then put them on the same line.  The following code is allowed

  buffer[n] = 0; n++;
 

Be a parenthesis zealot. When mixing arithmetic, logical, and conditional operations, explicitly specify the order of operations. Do not rely on the order of precedence. As always, the major style issue is clarity. Even if the following code were to perform the intended operation (which in fact it does not), it would be poor style.

  if( x + 1 & 0x0F == y | 0x04)
 

The programmer assigned to modify it in the future will have a better chance if we had written

  if(((x + 1) & 0x0F) == (y | 0x04))
 

Use enum instead of #define or const. The use of enum allows for consistency checking during compilation, and enum creates easy to read software. A good optimizing compiler will create the same object code for the following four implementations of the same operation. So once again, we focus on style. In the first implementation, we needed comments to explain the operations. In the second implementation, no comments are needed because of the two #define statements.

// implementation 1
int Mode;  // 0 means error
void function1(void){
  Mode = 1; // no error
}
void function2(void){
if(Mode == 0){ // error?
    UART_OutString("error");
  }
}

// implementation 2
#define NOERROR 1
#define ERROR 0
int Mode;
void function1(void){
  Mode = NOERROR;
}
void function2(void){
  if(Mode == ERROR){
    UART_OutString("error");
  }
}

 

In the third implementation, shown below on the left, the compiler performs a type-match, making sure Mode, NOERROR, and ERROR are the same type.  Consider a fourth implementation that uses enumeration to provide a check of both type and value.  We can explicitly set the values of the enumerated types if needed.

// implementation 3
const int NOERROR = 1;
const int ERROR = 0;
int Mode;
void function1(void){
  Mode = NOERROR;
}
void function2(void){
  if(Mode == ERROR){
    UART_OutString("error");
  }
}

// implementation 4
enum Mode_state{ ERROR,
                 NOERROR};
enum Mode_state Mode;
void function1(void){
  Mode = NOERROR;
}
void function2(void){
  if(Mode == ERROR){
    UART_OutString("error");
  }
}

 

#define statements, if used properly, can clarify our software and make our software easy to change. It is proper to use size in all places that refer to the size of the data array.

#define SIZE 10
int16_t Data[SIZE];
void initialize(void){ int16_t j;
  for(j = 0; j < SIZE; j++)
    Data[j] = 0;
}
 

7.2.6. Naming convention

Choosing names for variables and functions involves creative thought, and it is intimately connected to how we feel about ourselves as programmers. Of the policies presented in this section, naming conventions may be the hardest habit for us to change. The difficulty is that there are many conventions that satisfy the "easy to understand" objective. Good names reduce the need for documentation. Poor names promote confusion, ambiguity, and mistakes. Poor names can occur because code has been copied from a different situation and inserted into our system without proper integration (i.e., changing the names to be consistent with the new situation.) They can also occur in the cluttered mind of a second-rate programmer, who hurries to deliver software before it is finished. 

Names should have meaning. If we observe a name out of the context of the place at which it was defined, the meaning of the object should be obvious. The object TxFifo is clearly a transmit first in first out circular queue. The function UART_OutString will output a string to the serial port. The exact correspondence is not part of the policies presented in this section, just the fact that some correspondence should exist. Once another programmer learns which names we use for which object types, understanding our code becomes easier. For example,

i,j,k are indices

n,m are numbers

letter is a character

p,pt,ptr are pointers

x,y is a location

v is a voltage
 

Avoid ambiguities.  Don't use variable names in our system that are vague or have more than one meaning. For example, it is vague to use temp, because there are many possibilities for temporary data, in fact, it might even mean temperature. Don't use two names that look similar but have different meanings. 

Give hints about the type. We can further clarify the meaning of a variable by including phrases in the variable name that specify its type. For example, dataPt, timePt, and putPt are pointers. Similarly, voltageBuf, timeBuf, and pressureBuf are data buffers. Other good phrases include

Flag is a Boolean flag

Mode is a system state

U16 is an unsigned 16-bit

L is a signed 32-bit

Index is an index into an array

Cnt is a counter

 

Use a prefix to identify public objects. In this style policy, an underline character will separate the module name from the function name. As an exception to this rule, we can use the underline to delimit words in all upper-case name (e.g., #define MIN_PRESSURE 10). Functions that can be accessed outside the scope of a module will begin with a prefix specifying the module to which it belongs.  It is poor style to create public variables, but if they need to exist, they too would begin with the module prefix. The prefix matches the file name containing the object. For example, if we see a function call, UART_OutString("Hello world");  we know this public function belongs to the UART module, where the policies are defined in UART.h and the implementation in UART.c. Notice the similarity between this syntax (e.g., UART_Init()) and the corresponding syntax we would use if programming the module as a class in object-oriented language like C++ or Java (e.g., UART.Init()). Using this convention, we can easily distinguish public and private objects.

Use upper and lower case to specify the allocation of an object. We will define I/O ports and constants using no lower-case letters, like typing with caps-lock on. In other words, names without lower-case letters refer to objects with fixed values. TRUE, FALSE, and NULL are good examples of fixed-valued objects. As mentioned earlier, constant names formed from multiple words will use an underline character to delimit the individual words. E.g., MAX_VOLTAGE, UPPER_BOUND, and FIFO_SIZE. Permanently allocated variables will begin with a capital letter but include some lower-case letters. Local variables will begin with a lower-case letter and may or may not include upper case letters. Since all functions are permanently allocated, we can start function names with either an upper-case or lower-case letter. Using this convention, we can distinguish constants, globals and locals. An object's properties (public/private, local/global, constant/variable) are always perfectly clear at the place where the object is defined. The importance of the naming policy is to extend that clarity also to the places where the object is used.

Use capitalization to delimit words. Names that contain multiple words should be defined using a capital letter to signify the first letter of the word. Creating a single name output of multiple words by capitalizing the middle words and squeezing out the spaces is called CamelCase. Recall that the case of the first letter specifies whether is the local or global. Some programmers use the underline as a word-delimiter, but except for constants, we will reserve underline to separate the module name from the variable name. Table 7.2.1 presents examples of the naming convention used in this book.

Type

Examples

Constants

CR SAFE_TO_RUN PORTA STACK_SIZE START_OF_RAM

Local variables

maxTemperature lastCharTyped errorCnt

Private global variable

MaxTemperature LastCharTyped ErrorCnt

Public global variable

DAC_MaxVoltage Key_LastCharTyped Network_ErrorCnt

Private function

ClearTime wrapPointer InChar

Public function

Timer_ClearTime RxFifo_Put Key_InChar

Table 7.2.1. Examples of names. Use underline to define the module name. Use uppercase for constants. Use CamelCase for variables and functions.

 

: How can you tell if a function is private or public?

: How can you tell if a variable is local or global?

 

7.2.7. Comments

Discussion about comments was left for last, because they are the least important aspect involved in writing quality software. It is much better to write well-organized software with simple interfaces having operations so easy to understand that comments are not necessary. The goal of this section is to present ideas concerning software documentation in general and writing comments in particular. Because maintenance is the most important phase of software development, documentation should assist software maintenance. In many situations the software is not static, but continuously undergoing changes. Because of this liquidity, I believe that flowchart and software manuals are not good mechanisms for documenting programs because it is difficult to keep these types of documentation up to date when modifications are made. Therefore, the term documentation in this book refers almost exclusively to comments that are included in the software itself.

The beginning of every file should include the file name, purpose, hardware connections, programmer, date, and copyright. For example, we could write:

// filename  adtest.c 
// Test of TM4C123 ADC
// 1 Hz sampling on PD3 and output to the serial port
// Last modified 2/27/25 by Jonathan W. Valvano
// Copyright 2025 by Jonathan W. Valvano
//    You may use, edit, run or distribute this file
//    as long as the above copyright notice remains
 

The beginning of every function should include a line delimiting the start of the function, purpose, input parameters, output parameters, and special conditions that apply. The comments at the beginning of the function explain the policies (e.g., how to use the function.) These comments, which are similar to the comments for the prototypes in the header file, are intended to be read by the client. For example, we could explain a function this way:

//-------------------UART_InUDec----------------------
// InUDec accepts ASCII input in unsigned decimal
//     and converts to a 32-bit unsigned number
//     valid range is 0 to 4294967295
// Input: none
// Output: 32-bit unsigned number
// If you enter a number above 2^32-1, it will truncate
// Backspace will remove last digit typed
 

Comments can be added to a variable or constant definition to clarify the usage. Comments can specify the units of the variable or constant. For complicated situations, we can use additional lines and include examples. E.g.,

int16_t V1;     // voltage at node 1 in mV,
                // range -5000 mV to +5000 mV
uint16_t Fs;    // sampling rate in Hz
int FoundFlag;  // 0 if keyword not yet found,
                // 1 if found
uint16_t Mode;  // determines system action,
// as one of the following three cases
#define IDLE 0
#define COLLECT 1
#define TRANSMIT 2

Comments can be used to describe complex algorithms. These types of comments are intended to be read by our coworkers. The purpose of these comments is to assist in changing the code in the future, or applying this code into a similar but slightly different application. Comments that restate the function provide no additional information and actually make the code harder to read. Examples of bad comments include:

  time++;    // add one to time
  mode = 0;  // set mode to zero

Good comments explain why the operation is performed, and what it means:

  time++;    // maintain elapsed time in msec
  mode = 0;  // switch to idle mode because no data

We can add spaces, so the comment fields line up. As stated earlier, we avoid tabs because they often do not translate from one system to another. In this way, the software is on the left and the comments can be read on the right.

Maintenance Tip: If it is not written down, it doesn't exist.

As software developers, our goal is to produce code that not only solves our current problem but can also serve as the basis of our future solutions. In order to reuse software, we must leave our code in a condition such that future programmers (including ourselves) can easily understand its purpose, constraints, and implementation. Documentation is not something tacked onto software after it is done, but rather it is a discipline built into it at each stage of the development. Writing comments as we develop the software forces us to think about what the software is doing and more importantly why we are doing it.  Therefore, we should carefully develop a programming style that provides appropriate comments. I feel a comment that tells us why we perform certain functions is more informative than comments that tell us what the functions are.

Common error: A comment that simply restates the operation does not add to the overall understanding. 

Common error: Putting a comment on every line of software often hides the important information. 

Good comments assist us now while we are debugging and will assist us later when we are modifying the software, adding new features, or using the code in a different context. When a variable is defined, we should add comments to explain how the variable is used. If the variable has units, then it is appropriate to include them in the comments. It may be relevant to specify the minimum and maximum values. A typical value and what it means often will clarify the usage of the variable. For example:

int16_t SetPoint;
// The desired temperature for the control system
// 16-bit signed temperature with resolution of 0.5C,
// The range is -55C to +125C
// A value of 25 means 12.5C,
// A value of -25 means -12.5C

When a constant is used, we could add comments to explain what the constant means. If the number has units, then it is appropriate to include them in the comments. For example:

  V = 999;  // 999mV is the maximum voltage
  Err = 1;  // error code of 1 means out of range

There are two types of readers of our comments. Our client is someone who will use our software incorporating it into a larger system. Client comments focus on the policies of the software. What are the possible valid inputs? What are the resulting outputs? What are the error conditions? Just like a variable, it may be relevant to specify the minimum and maximum values for the input/output parameters. Typical input/output values and what they mean often will clarify the usage of the function. Often, we include a testmain.c file showing how the functions could be used.

The second type of comments is directed to the programmer responsible for debugging and software maintenance (coworker). Coworker comments focus on the mechanisms of the software. These comments explain

How the function works,

What are the assumptions made, and

Why certain design decisions were taken.

 

Generally, we separate coworker comments from client comments. This separation is the just another example of "separation of policies from mechanisms". The policy is what the function does, and the mechanism is how it works. Specifically, we place client comments in the header file, and we place coworker comments in the code file.

Self-documenting code is software written in a simple and obvious way, such that its purpose and function are self-apparent. Descriptive names for variables, constants, and functions will go a long way to clarify their usage. To write wonderful code like this, we first must formulate the problem by organizing it into clear well-defined subproblems. How we break a complex problem into small parts goes a long way toward making the software self-documenting. The concepts of abstraction, modularity, and layered software, all presented later in this chapter, address this important issue of software organization.

Observation: The purpose of a comment is to assist in debugging and maintenance.

We should use careful indenting and descriptive names for variables, functions, labels, and I/O ports. Liberal use of #define provide explanation of software function without cost of execution speed or memory requirements. A disciplined approach to programming is to develop patterns of writing that you consistently follow. Software developers are unlike short story writers. When writing software, it is good design practice to use the same function outline over and over again.

Observation: It is better to write clear and simple software that is easy to understand without comments than to write complex software that requires a lot of extra explanation to understand. 

 

7.3. I/O Device Drivers

In this section we demonstrate modular programming as an effective way to organize our I/O software. There are three reasons for forming modules. First, functional abstraction allows us to reuse a software module from multiple locations. Second, complexity abstraction allows us to divide a highly complex system into smaller less complicated components. The third reason is portability. If we create modules for the I/O devices then we can isolate the rest of the system from the hardware details. Portability will be enhanced when we create a device driver or board support package.

7.3.1. Layered Software

As the size and complexity of our software systems increase, we learn to anticipate the changes that our software must undergo in the future. We can expect to redesign our system to run on new and more powerful hardware platforms. A similar expectation is that better algorithms may become available. The objective of this section is to use a layered software approach to facilitate these types of changes.

Figure 7.3.1 shows two ways to draw a call graph that visualizes software layers.  Figure 7.3.1 shows only one module at each layer, but a complex system might have multiple modules at each layer. A function in a layer can call a function within the same module, or it can call a public function in a module of the same or lower layer. Some layered systems restrict the calls only to modules in the most adjacent layer below it. If we place all the functions that access the I/O hardware in the bottom most layer, we can call this layer a hardware abstraction layer (HAL). This bottom-most layer can also be called a board support package (BSP) if I/O devices are referenced in an abstract manner. Each middle layer of modules only calls lower-level modules, but not modules at a higher level. Usually, the top layer consists of the main program. In a multi-threaded environment, there can be multiple main programs at the top-most level, but for now assume there is only one main program.

An example of a layered system is Transmission Control Protocol/Internet Protocol (TCP/IP), which consists of at least four distinct layers: application (http, telnet, SMTP, FTP), transport (UDP, TCP), internet (IP, ICMP, IGMP), and network layers (Ethernet).

A diagram of a computer system Description automatically generated with medium confidence

Figure 7.3.1. A layered approach to interfacing a printer. The bottom layer is the BSP.

To develop a layered software system we begin with a modular system. The main advantage of layered software is the ability to separate the modules into groups or layers such that one layer may be replaced without affecting the other layers. For example, you could change which microcontroller you are using, by modifying the low level without any changes to the other levels. Figure 7.3.1 depicts a layered implementation of a printer interface. In a similar way, you could replace the printer with a solid-state disk by replacing just the middle and lower layers. If we were to employ buffering and/or data compression to enhance communication bandwidth, then these algorithms would be added to the middle level. A layered system should allow you to change the implementation of one layer without requiring redesign of the other layers.

A gate is used to connect one layer to the next. Another name for this gate is application program interface or API. The gates provide a mechanism to link the layers. Because the size of the software on an embedded system is small, it is possible and appropriate to implement a layered system using standard function calls by simply compiling and linking all software together. We create a header file with prototypes to public functions. The following rules apply to layered software systems:

1. A module may make a simple call to other modules in the same layer.

2. A module may make a call to a lower level module only by using the gate.

3. A module may not directly access any function or variable in another layer without going through the gate.

4. A module may not call a higher level routine.

5. A module may not modify the vector address of another level's handler(s).

6. (optional) A module may not call farther down than the immediately adjacent lower level.

7. (optional) All I/O hardware access is grouped in the lowest level.

8. (optional) All user interface I/O is grouped in the highest level

      unless it is the purpose of the module itself to do such I/O.
 

The purpose of rule 6 is to allow modifications at the low layer to not affect operation at the highest layer. On the other hand, for efficiency reasons you may wish to allow module calls further down than the immediately adjacent lower layer. To get the full advantage of layered software, it is critical to design functionally complete interfaces between the layers. The interface should support all current functions as well as provide for future expansions.

7.3.2. Board Support Package

A device driver or firmware consists of software routines that provide the functionality of an I/O device. A device driver usually does not hide what type of I/O module it is. For example, in Section 7.3.3, we consider a device driver for a serial port. A board support package is like a device driver, except that there is more of an attempt to hide the details of the I/O device. A board support package provides a higher level of abstraction than a regular device driver. The driver consists of the interface routines that the operating system or software developer's program calls to perform I/O operations as well as the low-level routines that configure the I/O device and perform the actual input/output. The issue of the separation of policies from mechanisms is very important in device driver design. The policies of a driver include the list of functions and the overall expected results. In particular, the policies can be summarized by the interface routines that the OS or software developer can call to access the device. The mechanisms of the device driver include the specific hardware and low-level software that perform the I/O. As an example, consider the wide variety of mass storage devices that are available. Flash EEPROM hard drive, battery-backed RAM hard drive, magnetic hard drive, optical hard drive, ferroelectric RAM hard drive, and even a network can be used to save and recall data files. A simple mass storage system might have the following C-level interface functions, as explained in the following prototypes (in each case the functions return 0 if successful and an error code if the operation fails:

int eFile_Init(void);            // initialize file system

int eFile_Create(char name[]);   // create new file, make it empty

int eFile_WOpen(char name[]);    // open a file for writing

int eFile_Write(int8_t data);    // stream data into open file

int eFile_WClose(void);          // close the file for writing

int eFile_ROpen(char name[]);    // open a file for reading

int eFile_ReadNext(int8_t *pt);  // stream data out of open file

int eFile_RClose(void);          // close the file for reading

int eFile_Delete(char name[]);   // remove this file

 

Building a hardware abstraction layer (HAL) is the same idea as separation of policies from mechanisms. In the above file example, a HAL or BSP would treat all the potential mass storage devices through the same software interface. Another example of this abstraction is the way some computers treat pictures on the video screen and pictures printed on the printer. With the abstraction layer, the software developer's program draws lines and colors by passing the data in a standard format to the device driver, and the OS redirects the information to the video graphics board or color printer as appropriate. This layered approach allows one to mix and match hardware and software components but does suffer some overhead and inefficiency.

Low-level device drivers normally exist in the Basic Input/Output System (BIOS) ROM and have direct access to the hardware. They provide the interface between the hardware and the rest of the software. Good low-level device drivers allow:

1. New hardware to be installed;

2. New algorithms to be implemented

     a. Synchronization with busy wait, interrupts, or DMA,

     b. Error detection and recovery methods

     c. Enhancements like automatic data compression

3. Higher level features to be built on top of the low level

     a. OS features like blocking semaphores

     b. Additional features like function keys
 

and still maintain the same software interface. In larger systems like the personal computer (PC), the low-level I/O software is compiled and burned in ROM separate from the code that will call it, it makes sense to implement the device drivers as software interrupts or traps, e.g., the SVC instruction, and specify the calling sequence language-independent according to AAPCS. We define the "client programmer" as the software developer that will use the device driver.  In embedded systems like we use, it is appropriate to provide device.h and device.c files that the client programmer can compile with their application. In a commercial setting, you may be able to deliver to the client only the device.h together with the object file. Linking is the process of resolving addresses to code and programs that have been complied separately. In this way, the routines can be called from any program without requiring complicated linking. In other words, when the device driver is implemented with a software interrupt, the linking occurs at run time through the vector address of the software interrupt. In our embedded system however, the linking will be static occurring at the time of compilation. 

7.3.3. Serial Port Driver

The concept of a device driver can be illustrated with the following design of a serial port device driver. In this section, the contents of the header file (UART.h) will be presented, and the implementations can be found in the starter projects for the book. and explained in Appendix T.4. The device driver software is grouped into four categories. Protected items can only be directly accessed by the device driver itself, and public items can be accessed by other modules.

1. Data structures: static (permanently allocated with private scope) The first component of a device driver includes data structures. To be static means only programs within the driver itself may directly access these variables. If the user of the device driver (e.g., a client) needs to read or write to these variables, then the driver will include public functions that allow appropriate read/write functions. One example of a static variable might be an OpenFlag, which is true if the serial port has been properly initialized. static used in this way makes the variable private to the file, but does have permanent allocation. If the implementation uses interrupts, then it will need a FIFO queue, defined with private scope.

int static OpenFlag = 0;  // true if driver has been initialized
 

2. Initialization routines (public, called by the client once in the beginning) The second component of a device driver includes the public functions used to initialize the device. To be public means the user of this driver can call these functions directly. A prototype to public functions will be included in the header file (UART.h). The names of public functions will begin with UART_. The purpose of this function is to initialize the UART hardware.

//------------UART_Init------------

// Initialize Serial port UART

// Input: none

// Output: none

void UART_Init(void);
 

3. Regular I/O calls (public, called by client to perform I/O) The third component of a device driver consists of the public functions used to perform input/output with the device. Because these functions are public, prototypes will be included in the header file (UART.h). The input functions are grouped, followed by the output functions.

//------------UART_InChar------------

// Wait for new serial port input

// Input: none

// Output: ASCII code for key typed

char UART_InChar(void);

 

//------------UART_InString------------

// Wait for a sequence of serial port input

// Input: maxSize is the maximum number of characters to look for

// Output: Null-terminated string in buffer

void UART_InString(char *buffer, uint16_t maxSize);

 

 

//------------UART_InUDec------------

// InUDec accepts ASCII input in unsigned decimal format

// and converts to a 32-bit unsigned number (0 to 4294967295)

// Input: none

// Output: 32-bit unsigned number

uint32_t UART_InUDec(void);

 

//------------UART_OutChar------------

// Output 8-bit to serial port

// Input: letter is an 8-bit ASCII character to be transferred

// Output: none

void UART_OutChar(char letter);

 

//------------UART_OutString------------

// Output String (NULL termination)

// Input: pointer to a NULL-terminated string to be transferred

// Output: none

void UART_OutString(char *buffer);

 

//------------UART_OutUDec------------

// Output a 32-bit number in unsigned decimal format

// Input: 32-bit number to be transferred

// Output: none

// Variable format 1-10 digits with no space before or after

void UART_OutUDec(uint32_t number);

 

4. Support software (private) The last component of a device driver consists of private functions. Again, if interrupt synchronization were to be used, then a set of FIFO functions will be needed. Because these functions are private, prototypes will not be included in the header file (UART.h). We place helper functions and interrupt service routines in the category.

Notice that this UART example implements a layered approach, like Figure 7.3.1. The low-level functions provide the mechanisms and are protected (hidden) from the client programmer. The high-level functions provide the policies and are accessible (public) to the client. When the device driver software is separated into UART.h and UART.c files, you need to pay careful attention as to how many details you place in the UART.h file. A good device driver separates the policy (overall operation, how it is called, what it returns, what it does, etc.) from the implementation (access to hardware, how it works, etc.) In general, you place the policies in the UART.h file (to be read by the client) and the implementations in the UART.c file (to be read by you and your coworkers). Think of it this way: if you were to write commercial software that you wished to sell for profit and you delivered the UART.h file and its compiled object file, how little information could you place in the UART.h file and still have the software system be fully functional. In summary, the policies will be public, and the implementations will be private.

Observation: A layered approach to I/O programming makes it easier for you to upgrade to newer technology.  

Observation: A layered approach to I/O programming allows you to do concurrent development.

7.3.4. Abstract Output Device Driver

In the UART driver shown in the previous section, the routines clearly involve a UART. Another approach to I/O is to provide a high-level abstraction in such a way that the I/O device itself is hidden from the user. One example of this abstraction is the standard printf feature to which most C programmers are accustomed. For the TM4C123 and MSPM0 LaunchPad boards, we can send output to the PC using UART0, to a ST7735 color graphics LCD using SPI, or to a low-cost SSD1306 OLED using I2C. Even though all these displays are quite different, they all behave in a similar fashion.

In C with the Keil compiler, we can specify the output stream used by printf by writing a fputc function. The fputc function is a private and implemented inside the driver. It sends characters to the display and manages the cursor, tab, line feed and carriage return functionalities. The user controls the display by calling the following five public functions.

void Output_Init(void);  // Initializes the display interface.

void Output_Clear(void); // Clears the display

void Output_Off(void);   // Turns off the display

void Output_On(void);    // Turns on the display

void Output_Color(uint32_t newColor); // Set color of future output
 

The user performs output by calling printf. This abstraction clearly separates what it does (output information) from how it works (sends pixel data to the display over UART, SSI, or I2C). In these examples all output is sent to the display; however, we could modify the fputc function and redirect the output stream to other devices such as the USB, Ethernet, or disk. For the TM4C boards, implementation of printf for both Keil and CCS can be found in projects ST7735_4C123, SSD1306_4C123, Printf_Nokia_4C123, and Printf_UART_4C123, see starter projects for the book

 

7.4. Design Paradigms

Abstraction is when we define a complex problem with a set of basic abstract principles. If we can construct our software system using these building blocks, then we have a better understanding of the problem. This is because we can separate what we are doing from the details of how we are getting it done. This separation also makes it easier to optimize. It provides proof of the correct function and simplifies both extensions and customization.

A well-defined model or framework is used to solve our problem. The three advantages of abstraction are 1) it can be faster to develop because a lot of the building blocks preexist; 2) it is easier to debug (prove correct) because it separates conceptual issues from implementation; and 3) it is easier to change.

7.4.1. Finite State Machines

A good example of abstraction is the Finite State Machine (FSM) implementations. The abstract principles of FSM development are the inputs, outputs, states, and state transitions. If we can take a complex problem and map it into an FSM model, then we can solve it with simple FSM software tools. Our FSM software implementation will be easy to understand, debug, and modify. Other examples of software abstraction include Proportional Integral Derivative digital controllers, fuzzy logic digital controllers, neural networks, and linear systems of differential equations (e.g., PSPICE.)  In each case, the problem is mapped into a well-defined model with a set of abstract yet powerful rules. Then, the software solution is a matter of implementing the rules of the model.

Linked lists are lists or nodes where one or more of the entries is a (link) to other nodes of similar structure. We can have statically allocated fixed-size linked lists that are defined at assembly or compile time and exist throughout the life of the software. On the other hand, we implement dynamically allocated variable-size linked lists that are constructed at run time and can grow and shrink in size. We will use a data structure like a linked list called a linked structure to build a finite state machine controller. Linked structures are very flexible and provide a mechanism to implement abstractions.

An important factor when implementing finite state machines using linked structures is that there should be a clear and one-to-one mapping between the finite state machine and the linked structure. I.e., there should be one structure for each state.

We will present two types of finite state machines. The Moore FSM has an output that depends only on the state, and the next state depends on both the input and current state. We will use a Moore implementation if there is an association between a state and an output. There can be multiple states with the same output, but the output defines in part what it means to be in that state. For example, in a traffic light controller, the state of green light on the North road (red light on the East road) is caused by outputting a specific pattern to the traffic light.

On the other hand, the Mealy FSM has an output that depends on both the input and the state, and the next state also depends on input and current state. We will use a Mealy implementation if the output causes the state to change. In this situation, we do not need a specific output to be in that state; rather the outputs are required to cause the state transition. For example, to make a robot stand up, we perform a series of outputs causing the state to change from sitting to standing. Although we can rewrite any Mealy machine as a Moore machine and vice versa, it is better to implement the format that is more natural for the problem. In this way the state graph will be easier to understand.

: What are the differences between a Mealy and Moore finite state machine?

One of the common features in many finite state machines is a time delay. We will use timer interrupts so the FSM runs in the background. For simpler FSM implementations, see the ECE319K TM4C123 ebook Section 5.4 or the ECE319K MSPM0 ebook section 4.4.

 

Example 7.4.1. Design a line-tracking robot that has two drive wheels and two line-sensors using an FSM. The goal is to drive the robot along a line placed in the center of the road. The robot has two drive wheels and a third free turning balance wheel. Figure 7.4.1 shows that PF1 drives the left wheel and PF2 drives the right wheel. If both motors are on (PF2-1 = 11), the robot goes straight. If just the left motor is on (PF2-1 = 01), the robot will turn right. If just the right motor is on (PF2-1 = 10), the robot will turn left. The line sensors are under the robot and can detect whether they see the line. The two sensors are connected to Port F, such that:

 

                                 PF4,PF0 equal to 0,0 means we are lost, way off to the right or way off to the left.
                                 PF4,PF0 equal to 0,1 means we are off just a little bit to the right.
                                 PF4,PF0 equal to 1,0 means we are off just a little bit to the left.
                                 PF4,PF0 equal to 1,1 means we are on line.

Figure 7.4.1. Robot with two drive wheels and two line-sensors.

Solution: The QRB1134 LED emits light, which may or may reflect of the surface of the robot track. The QRB1134 sensor voltages, V1 V3, will be high if no reflect light is received or low if the sensor sees a reflective surface. The op amps in open loop mode will create a clean digital signal on V2 and V4 (see section 6.4.6.) The DC motor interface will be described in Section 8.xx (add link**).

 

To facilitate migration to other microcontrollers Program 7.4.1 presents a board support package, defining a low-level set of routines that perform input/output. For more information on configuring SysTick periodic interrupts see Section 1.9. The purpose of a board support package is to hide as much of the I/O details as possible. We implement a BSP when we expect the high-level system will be deployed onto many low-level platforms.  The BSP in Program 7.4.1 can be adapted to any microcontroller, any bus speed, and any GPIO pins.

 

// TM4C123 specific code

#define BUS 80000000

#define PF21 (*((volatile unsigned long *)0x40025018))

#define PF4 (*((volatile unsigned long *)0x40025040))

#define PF0 (*((volatile unsigned long *)0x40025004))

void Robot_Init(void){

  DisableInterrupts(); // disable during initialization

  PLL_Init(Bus80MHz);  // bus clock at 80 MHz

  SYSCTL_RCGCGPIO_R |= 0x20;      // 1) activate clock for Port F

  SysTick_Init(T10ms,2);          // initialize SysTick timer

  GPIO_PORTF_LOCK_R = 0x4C4F434B; // 2) unlock GPIO Port F

  GPIO_PORTF_CR_R = 0x1F;         // allow changes to PF4-0

  GPIO_PORTF_AMSEL_R = 0x00;      // 3) disable analog on PF

  GPIO_PORTF_PCTL_R = 0x00000000; // 4) PCTL GPIO on PF4-0

  GPIO_PORTF_DIR_R = 0x0E;        // 5) PF4,PF0 in, PF3-1 out

  GPIO_PORTF_AFSEL_R = 0x00;      // 6) disable alt funct on PF7-0

  GPIO_PORTF_DEN_R = 0x1F;        // 7) enable digital I/O on PF4-0

  EnableInterrupts(); // enable after initialization

}

uint32_t Robot_Input(void){

  return PF0+(PF4>>3);      // read sensors

}

void Robot_Output(uint32_t out){

  PF21 = out<<1;

}
void SysTick_Restart(uint32_t time){
  NVIC_ST_RELOAD_R = time;
  NVIC_ST_CURRENT_R = 0;
}

Program 7.4.1a. Board support package for the robot for TM4C123. Output pins on PF2 and PF1. Line sensor inputs on PF4 and PF0.

// MSPM0G3507 specific code
#define BUS 80000000
void Robot_Init(void){
  __disable_irq();
  Clock_Init80MHz(0);
  LaunchPad_Init();
  SysTick_Init(T10ms,2);
  IOMUX->SECCFG.PINCM[PB7INDEX] = 0x00040081;
  IOMUX->SECCFG.PINCM[PB6INDEX] = 0x00040081;
  IOMUX->SECCFG.PINCM[PB1INDEX] = 0x00000081;
  IOMUX->SECCFG.PINCM[PB0INDEX] = 0x00000081;
  GPIOB->DOE31_0 |= 0x03;
  __enable_irq();
}
void Robot_Output(uint32_t data){
  GPIOB->DOUT31_0 = (GPIOB->DOUT31_0&(~0x03))|data;
}
uint32_t Robot_Input(void){
  return (GPIO_PORTB_DATA_R&0xC0)>>6;
}
void SysTick_Restart(uint32_t time){
  SysTick->LOAD = time;
  SysTick->VAL = 0;
}

Program 7.4.1b. Board support package for the robot for MSPM0. Output pins on PB1 and PB0. Line sensor inputs on PB7 and PB6.

The first step in designing a FSM is to create some states. The outputs of a Moore FSM are only a function of the current state.  A Moore implementation was chosen because we define our states by what believe to be true, and we will have one action (output) that depends on the state. Each state is given a symbolic name where the state name either describes "what we know" or "what we are doing". We could have differentiated between a little off to the left and way off to the left, but this solution creates a simple solution with 3 states. See Figure 7.4.2.

A black background with a black border AI-generated content may be incorrect.

Figure 7.4.2. The sensor inputs for the three states.

 

The finite state machine implements this line-tracking algorithm.  Each state has a 2-bit output value, and four next state pointers. The strategy will be to:

 

       Go straight if we are on the line.

       Turn right if we are off to the left.

       Turn left if we are off to the right.

 

Finally, we implement the heuristics by defining the state transitions, as illustrated in Figure 7.4.3 and Table 7.4.1. If we used to be in the left state and completely lose the line (input 00), then we know we are left of the line. Similarly, if we used to be in the right state and completely lose the line (input 00), then we know we are right of the line. However, we used to be on the center of the line and then completely lose the line (input 00), we do not know we are right or left of the line. The machine will guess we went right of the line. In this implementation, we put a constant delay of 10ms in each state. Nevertheless, we put the time to wait into the machine as a parameter for each state to provide for clarity of how it works and simplify possible changes in the future. If we are off to the right (input 01), then it will oscillate between Center and Right states, making a slow turn left. If we are off to the left (input 10), then it will oscillate between Center and Left states, making a slow turn right.

 

Figure 7.4.3. Graphical form of a Moore FSM that implements a line tracking robot.

 

 

 

 

Input

State

Motor

Delay

00

01

10

11

Center

1,1

1

Right

Right

Left

Center

Left

1,0

1

Left

Right

Center

Center

Right

0,1

1

Right

Center

Left

Center

Table 7.4.1. Tabular form of a Moore FSM that implements a line tracking robot.

The first step in designing the software is to decide on the sequence of operations. When running the controller in the main program, we perform output, delay, input, next. The delay step in this approach is inefficient because the software does not do any useful work. If there are no other tasks to perform, it should at least go into low-power sleep mode.

 

            1) Initialize timer and directions registers
            2) Specify initial state
            3) Perform FSM controller in the main loop
                        a) Output to DC motors, which depends on the state
                        b) Delay, which depends on the state
                        c) Input from line sensors
                        d) Change states, which depends on the state and the input

To allow the main to do other work, we can run the controller in an interrupt service routine. The main program initializes the timer and GPIO pins, and then the main loop can perform other tasks or sleep. The ISR performs input, next, output, delay. The delay step does not actually wait, but rather it configures the periodic timer for when the next interrupt should occur.

                        c) Input from line sensors
                        d) Change states, which depends on the state and the input
                        a) Output to DC motors, which depends on the state
                        b) Delay, which depends on the state

The second step is to define the FSM graph using a data structure. Program 7.4.2 shows a table implementation of the Moore FSM. This implementation uses a table data structure, where each state is an entry in the table, and state transitions are defined as indices into this table. The four Next parameters define the input-dependent state transitions. The wait times are defined in the software as fixed-point decimal numbers with units of 0.01s. The label Center is more descriptive than the state number 0. Notice the 1-1 correspondence between the tabular form in Table 7.4.1 and the software specification of fsm[3]. This 1-1 correspondence makes it possible to prove the software exactly executes the FSM as described in the table.  

 

struct State{

  uint32_t Out;      // 2-bit output

  uint32_t Delay;    // time in bus cycles

  uint8_t Next[4];

};

typedef const struct State State_t;

#define Center 0

#define Left 1

#define Right 2

#define T10ms (BUS/100)

State_t fsm[3] = {

  {0x03, T10ms, { Right, Right,  Left,   Center }},  // Center of line

  {0x02, T10ms, { Left,  Right,  Center, Center }},  // Left of line

  {0x01, T10ms, { Right, Center, Left,   Center }}   // Right of line

};

uint32_t S;  // index to the current state

void SysTick_Handler(void){

uint32_t input, output;      // state I/O

  input = Robot_Input();     // read sensors

  S = fsm[S].Next[input];    // next depends on input and state

  output = fsm[S].Out;       // set output from FSM

  Robot_Output(output);      // do output to two motors

  SysTick_Restart(fsm[S].Delay); // set time for next interrupt

}

int main(void){

  S = Center;          // initial state

  Robot_Init();        // Initialize GPIO, SysTick

  while(1){

  }

}

Program 7.4.2. Table implementation of a Moore FSM.

Program 7.4.3 uses a linked structure, where each state is a node, and state transitions are defined as pointers to other nodes. Again, notice the 1-1 correspondence between Table 7.4.1 and the software specification of fsm[3]. 

 

struct State {

  uint32_t Out;      // 2-bit output

  uint32_t Delay;    // time in bus cycles

  const struct State *Next[4];
};

typedef const struct State State_t;

#define Center &fsm[0]

#define Left   &fsm[1]

#define Right  &fsm[2]

State_t *pt;   // state pointer

State_t fsm[3] = {

  {0x03, T10ms, { Right, Right,  Left,   Center }},  // Center of line

  {0x02, T10ms, { Left,  Right,  Center, Center }},  // Left of line

  {0x01, T10ms, { Right, Center, Left,   Center }}   // Right of line

};

void SysTick_Handler(void){

uint32_t input, output;      // state I/O

  input = Robot_Input();     // read sensors

  pt = pt->Next[input];      // next depends on input and state

  output = pt->Out;          // set output from FSM

  Robot_Output(output);      // do output to two motors

  SysTick_Restart(fsm[S].Delay); // set time for next interrupt

}

int main(void){

  pt = Center;          // initial state

  Robot_Init();        // Initialize GPIO, SysTick

  while(1){

  }

}

Program 7.4.3. Pointer implementation of a Moore FSM.

 

Observation: The table implementation requires less memory space for the FSM data structure, but the pointer implementation will run faster.

To add more output signals, we simply increase the precision of the Out field. To add more input lines, we increase the size of the next field. If there are n input bits, then the size of the next field will be 2n. For example, if there are four input lines, then there are 16 possible combinations, where each input possibility requires a Next value specifying where to go if this combination occurs.

 

Example 7.4.2. The goal is to design a finite state machine robot controller, as illustrated in Figure 7.4.4.  Because the outputs cause the robot to change states, we will use a Mealy implementation. The outputs of a Mealy FSM depend on both the input and the current state. This robot has mood sensors that are interfaced to PB7 and PB6. The robot has four possible conditions:

        00         OK, the robot is feeling fine
        01         Tired, the robot energy levels are low
        10         Curious, the robot senses activity around it
        11         Anxious, the robot senses danger

There are four actions this robot can perform, which are triggered by pulsing (make high, then make low) one of the four signals interfaced to Port B.

        PB3     SitDown, assuming it is standing, it will perform moves to sit down
        PB2     StandUp, assuming it is sitting, it will perform moves to stand up
        PB1     LieDown, assuming it is sitting, it will perform moves to lie down
        PB0     SitUp, assuming it is sleeping, it will perform moves to sit up

Solution: For this design we can list heuristics describing how the robot is to operate:

            If the robot is OK, it will stay in its current state.
            If the robot's energy levels are low, it will go to sleep.
            If the robot senses activity around it, it will awaken from sleep.
            If the robot senses danger, it will stand up.

Figure 7.4.4. Robot interface.

 

These rules are converted into a finite state machine graph, as shown in Figure 7.4.5. Each arrow specifies both an input and an output. For example, the "Tired/SitDown" arrow from Stand to Sit states means if we are in the Stand state and the input is Tired, then we will output the SitDown command and go to the Sit state. Mealy machines can have time delays, but this example just didn't have time delays.

 

 

Figure 7.4.5. Mealy FSM for a robot controller.

 

The first step in designing the software is to decide on the sequence of operations.

            1) Initialize directions registers
            2) Specify initial state
            3) Perform FSM controller
                        a) Input from sensors
                        b) Output to the robot, which depends on the state and the input
                        c) Change states, which depends on the state and the input

Program 7.4.4 presents the low-level software I/O functions for the robot. Separating low-level code into a board support package makes it easier to port this software to other microcontrollers.

// TM4C123

void Robot_Init(void){

volatile uint32_t delay;

  PLL_Init(Bus80MHz);

  SYSCTL_RCGCGPIO_R |= 0x02;

  delay = SYSCTL_RCGCGPIO_R;

  GPIO_PORTB_PCTL_R &= ~0xFF0000FF;

  GPIO_PORTB_DIR_R |= 0x03;

  GPIO_PORTB_DIR_R &= ~0xC0;

  GPIO_PORTB_AFSEL_R &= ~0xC3;

  GPIO_PORTB_DR8R_R |= 0x03; 

  GPIO_PORTB_DEN_R |= 0xC3;

}

void Robot_Output(uint32_t data){

  GPIO_PORTB_DATA_R =

   (GPIO_PORTB_DATA_R&(~0x03))|data;

}

uint32_t Robot_Input(void){

  return (GPIO_PORTB_DATA_R&0xC0)>>6;

}
#define None    0x00
#define SitDown 0x08 // pulse on PB3
#define StandUp 0x04 // pulse on PB2
#define LieDown 0x02 // pulse on PB1
#define SitUp   0x01 // pulse on PB0

// MSPM0G3507

void Robot_Init(void){

  Clock_Init80MHz(0);

  LaunchPad_Init();

  IOMUX->SECCFG.PINCM[PB7INDEX] = 0x00040081;

  IOMUX->SECCFG.PINCM[PB6INDEX] = 0x00040081;

  IOMUX->SECCFG.PINCM[PB1INDEX] = 0x00000081;

  IOMUX->SECCFG.PINCM[PB0INDEX] = 0x00000081;

  GPIOB->DOE31_0 |= 0x03;

}
 
 

 

void Robot_Output(uint32_t data){

  GPIOB->DOUT31_0 =

   (GPIOB->DOUT31_0&(~0x03))|data;

}

uint32_t Robot_Input(void){

  return (GPIOB->DIN31_0&0xC0)>>6;

}
#define None    0x00
#define SitDown 0x08 // pulse on PB3
#define StandUp 0x04 // pulse on PB2
#define LieDown 0x02 // pulse on PB1
#define SitUp   0x01 // pulse on PB0

Program 7.4.4. Low-level software for the robot.

 

The second step is to define the FSM graph using a linked data structure. Two possible implementations of the Mealy FSM are presented. The implementation in Program 7.4.5 defines the outputs as simple numbers, where each pulse is defined as the bit mask required to cause that action. The four Next parameters define the input-dependent state transitions.

 

struct State{

  uint32_t Out[4];             // outputs

  const struct State *Next[4]; // next

};

typedef const struct State State_t;

#define Stand &FSM[0]

#define Sit   &FSM[1]

#define Sleep &FSM[2]

#define None    0x00

State_t FSM[3]={

{{None,SitDown,None,None},   //Standing

  {Stand,Sit,Stand,Stand}},

{{None,LieDown,None,StandUp},//Sitting

  {Sit,Sleep,Sit,Stand }},

{{None,None,SitUp,SitUp},    //Sleeping

  {Sleep,Sleep,Sit,Sit}}

};

int main(void){ State_t *pt;    // current state

  uint32_t input;

  Robot_Init();  // clock and GPIO initialization

  pt = Stand;    // initial state

  while(1){

    input = Robot_Input();        // input=0-3

    Robot_Output(pt->Out[Input]); // pulse
    Robot_Output(None);

    pt = pt->Next[Input];  // next state

  }

}

Program 7.4.5. Outputs defined as numbers for a Mealy Finite State Machine.

 

 

Program 7.4.6 uses functions to affect the output. Although the functions in this solution perform simple output, this implementation could be used when the output operations are complex. Again proper memory allocation is required if we wish to implement a stand-alone or embedded system. The const qualifier is used to place the FSM data structure in flash ROM.

 

struct State{

  void *CmdPt[4];              // outputs are function pointers

  const struct State *Next[4]; // next

};

typedef const struct State State_t;

#define Stand &FSM[0]

#define Sit   &FSM[1]

#define Sleep &FSM[2]

void doNone(void){};

void doSitDown(void){

  Robot_Output(SitDown);

  Robot_Output(None); // pulse

}

void doStandUp(void){

  Robot_Output(StandUp);

  Robot_Output(None); // pulse

}

void doLieDown(void){

  Robot_Output(LieDown);

  Robot_Output(None); // pulse

}

void doSitUp(void) {

  Robot_Output(SitUp);

  Robot_Output(None); // pulse

}

State_t FSM[3]={

{{(void*)&doNone,(void*)&doSitDown,(void*)&doNone,(void*)&doNone},  //Standing

  {Stand,Sit,Stand,Stand}},

{{(void*)&doNone,(void*)doLieDown,(void*)&doNone,(void*)&doStandUp},//Sitting

  {Sit,Sleep,Sit,Stand }},

{{(void*)&doNone,(void*)&doNone,(void*)&doSitUp,(void*)&doSitUp},   //Sleeping

  {Sleep,Sleep,Sit,Sit}}

};

int main(void){ State_t *pt;  // current state

  uint32_t input;

  Robot_Init();  // clock and GPIO initialization

  pt = Stand;    // initial state

  while(1){

    input = Robot_Input();               // input=0-3

    ((void(*)(void))pt->CmdPt[Input])(); // function

    pt = pt->Next[input];                // next state

  }

}

Program 7.4.6. Outputs defined as functions for a Mealy Finite State Machine.

 

Observation: To make the FSM respond quicker, we could implement a time delay function that returns immediately if an alarm condition occurs. If no alarm exists, it waits for the specified delay. Similarly, we could return from the time delay on a change in input.

: What happens if the robot is sleeping then becomes anxious?

We can expand the syntax of a finite state machine to support sensor integration. A finite state machine uses inputs to affect state changes. These state changes depend on input values being a specific value. However, there are natural ways to combine sensor data to make state changes. Figure 7.4.6 shows an RSLK robot with many sensors.

A diagram of a device Description automatically generated

Figure 7.4.6. RSLK Robot with sensors and actuators

Let Ltach be the wheel speed measured by the left tachometer. Let bump be a four bit binary number read from the negative logic switches on the front of the robot. Let left be the distance to the left wall measured by the IR distance sensor. Let right be the distance to the right wall measured by another IR distance sensor. Let center be the distance to closest object in front of the robot measured by the TF Luna time of flight sensor Let Lpower be the actuator duty cycle value being delivered to the left motor. Let Rpower be the actuator duty cycle value being delivered to the right motor. First, consider state changes based on simultaneous sensor readings. Notice in each case the AND, signifying simultaneous condition. For example,

       • Go to Collision state if Ltach used to be above 1rps AND bump is not 0x0F
       • Go to OffLeft state if left is below 250mm AND center is above 200mm
       • Go to Stalled state if Ltach is below 1rps, Lpower is above 1000, AND bump is 0x3F
 

Next, consider state changes based on alternative sensor readings. Notice in each case the OR, signifying either condition. For example,

       • Go to Collision state if center is less than 10 mm OR bump is not 0x3F
       • Go to TurnRight state if left is below 200mm OR right is above 300mm
 

One of the challenging design decisions will be to create a data structure to support this sensor integration. A very flexible approach is to create a set of functions to implement the logic. In the following structure, pOutput is a pointer to a function that performs the output operation based on the state number. pInput is a pointer to a function that performs input. If the input condition is true, it will return a state number to go to. If the input condition is false, it will return -1. The functions are sorted in priority order such that the first input condition to trigger will be executed and the remaining input conditions will be skipped. If none of the input conditions trigger, then the machine will stay in the current state.

struct State{
  void (*pOutput)(void);
  uint32_t NumInputFunctions;
  int32_t (*pInput[10])(void);
};
typedef const struct State State_t;
 

 

Example 7.4.3. Redesign a traffic light controller orginally presented in Section 4.4.1 of Volume 1 using this function syntax. Figure 7.4.7 describes the state transition graph of this controller. Program 7.4.7 implements this traffic light controller.

A diagram of a device Description automatically generated

Figure 7.4.7. State transition graph for a simple traffic controller.

#define goN 0
#define waitN 1
#define goE 2
#define waitE 3
void GoNorth(void){
  TrafficOutput(0x21);    // lights green on north, red on east
  SysTick_Wait10ms(3000); // 3 sec
}
void WaitNorth(void){
  TrafficOutput(0x22);    // lights yellow on north, red on east
  SysTick_Wait10ms(500); // 0.5 sec
}
void GoEast(void){
  TrafficOutput(0x0C);    // lights green on east, red on north
  SysTick_Wait10ms(3000); // 3 sec
}
void WaitEast(void){
  TrafficOutput(0x22);    // lights yellow on east, red on north
  SysTick_Wait10ms(500); // 0.5 sec
}
uint32_t CS ; // Current State
int32_t CheckForEast(void){
  if(TrafficInput()&1){
    return waitN; // there are cars on east
  }
  return -1; // no cars on east
}
int32_t SwitchToEast(void){
  return goE; // there are cars on east
}
int32_t CheckForNorth(void){
  if(TrafficInput()&2){
    return waitE; // there are cars on north
  }
  return -1; // no cars on north
}
int32_t SwitchToNorth(void){
  return goN; // there are cars on north
}
State_t FSM[4]={
  {&GoNorth,  1,{&CheckForEast}},
  {&WaitNorth,1,{&SwitchToEast}},
  {&GoEast,   1,{&CheckForNorth}},
  {&WaitEast, 1,{&SwitchToNorth}}
};
int main(void){ int32_t next;
  Clock_Init80MHz(0);
  SysTick_Init();
  Traffic_Init();
  CS = goN;
  while(1){
    (*(FSM[CS].pOutput))(); // perform output
    for(int i=0; i<FSM[CS].NumInputFunctions;i++){
      next = (*(FSM[CS].pInput[i]))(); // Check input
      if(next >= 0){
        CS = next;
        break;
      }
    }
  }
}

Program 7.4.7. Table implementation of a Moore FSM using function pointers.

Observation The simple solutions presented in Section 4.4.1 of Volume 1 are much better code for this simple problem. This very complex solution to this very simple problem is includes to describe the process of implementing sensor fusion using the FSM structure.
 

7.4.2. Petri Nets

In the last section, we presented finite state machines as a formal mechanism to describe systems with inputs and outputs. In this section, we present two methods to describe synchronization in complex systems: Petri Nets and Kahn Process Networks. Petri Nets can be used to study the dynamic concurrent behavior of network-based systems where there is discrete flow, such as packets of data. A Petri Net is comprised of Places, Transition, and Arcs. Places, drawn as circles in Figure 7.4.8, can contain zero, one, or more tokens. Consider places as variables (or buffers) and tokens as discrete packets of data. Tokens are drawn in the net as dots with each dot representing one token. Formally, the tokens need not comprise data and could simply represent the existence of an event. Transitions, drawn as vertical bars, represent synchronizing actions. Consider transitions as software that performs work for the system. From a formal perspective, a Petri Net does not model time delay. But, from a practical viewpoint we know executing software must consume time. The arcs, drawn as arrows, connect places to transitions. An arc from a place to a transition is an input to the transition, and an arc from a transition to a place is an output of the transition. 

A diagram of a device Description automatically generated

Figure 7.4.8. Petri Nets are built with places, transitions and arcs. Places can hold tokens.

For example, an input switch could be modeled as a device that inserts tokens into a place. The number of tokens would then represent the number of times the switch has been pressed. An alphanumeric keyboard could also be modeled as an input device that inserts tokens into a place. However, we might wish to assign an ASCII string to the token generated by a keyboard device. An output device in a Petri Net could be modeled as a transition with only input arcs but no output arcs. An output device consumes tokens (data) from the net.

Arcs are never drawn from place to place, nor from transition to transition. Transition node is ready to fire if and only if there is at least one token at each of its input places. Conversely, a transition will not fire if one or more input places is empty. Firing a transition produces software action (a task is performed). Formally, firing a transition will consume one token from each of its input places and generate one token for each of its output places. Figure 7.4.9 illustrates an example firing. In this case, the transition will wait for there to be at least one token in both its input places. When it fires it will consume two tokens and merge them into one token added to its output place. In general, once a transition is ready to fire, there is no guarantee when it will fire. One useful extension of the Petri Net assigns a minimum and maximum time delay from input to output for each transition that is ready to fire.

A black and white image of a pair of eyes Description automatically generated

Figure 7.4.9. Firing a transition consumes one token at each input and produces one token at each output.

Figure 7.4.10 illustrates a sequential operation. The three transitions will fire in a strictly ordered sequence: first t1, next t2, and then t3.

A black and white image of a rectangular object with a black background Description automatically generated

Figure 7.4.10. A Petri Net used to describe a sequential operation.

Figure 7.4.11 illustrates concurrent operation. Once transition t1 fires, transitions t2 and t3 are running at the same time. On a distributed system t2 and t3 may be running in parallel on separate computers. On a system with one processor, two operations are said to be running concurrently if they are both ready to run. Because there is a single processor, the tasks must run one at a time.

A diagram of a diagram Description automatically generated with medium confidence

Figure 7.4.11. A Petri Net used to describe concurrent operations.

Figure 7.4.12 demonstrates a conflict or race condition. Both t1 and t2 are ready to fire, but the firing of one leads to the disabling of the other. It would be a mistake to fire them both. A good solution would be to take turns in some fair manner (flip a coin or alternate). A deterministic model will always produce the same output from a given starting condition or initial state. Because of the uncertainty when or if a transition will fire, a system described with a Petri Net is not deterministic. 

A diagram of a diagram of a diagram Description automatically generated with medium confidence

Figure 7.4.12. If t1 were to fire, it would disable t2. If t2 were to fire, it would disable t1.

Figure 7.4.13 describes an assembly line on a manufacturing plant. There are two robots. The first robot picks up one Part1 and one Part2, placing the parts together. After the robot places the two parts, it drills a hole through the combination, and then places the partial assembly into the Partial bin. The second robot first combines Part3 with the partial assembly and screws them together. The finished product is placed into the Done bin. The tokens represent the state of the system, and transitions are actions that cause the state to change.

The three supply transitions are input machines that place parts into their respective parts bins. The tokens in places Part1, Part2, Part3, Partial, and Done represent the number of components in their respective bins. The first robot performs two operations but can only perform one at a time. The Rdy-to-P&P place has a token if the first robot is idle and ready to pick and place. The Rdy-to-drill place has a token if the first robot is holding two parts and is ready to drill. The Pick&Place transition is the action caused by the first robot as it picks up two parts placing them together. The Drill transition is the action caused by the first robot as it drills a hole and places the partial assembly into the Partial bin.

A diagram of a drill Description automatically generated

Figure 7.4.13. A Petri Net used to describe an assembly line.

The first robot performs two operations but can only perform one at a time. The Rdy-to-P&P place has a token if the first robot is idle and ready to pick and place. The Rdy-to-drill place has a token if the first robot is holding two parts and is ready to drill. The Pick&Place transition is the action caused by the first robot as it picks up two parts placing them together. The Drill transition is the action caused by the first robot as it drills a hole and places the partial assembly into the Partial bin.

The second robot performs two operations. The Rdy-to-combine place has a token if the second robot is idle and ready to combine. The Rdy-to-screw place has a token if the second robot is holding two parts and is ready to screw. The Combine transition is the action caused by the second robot as it picks up a Part3 and a Partial combining them together. The Screw transition is the action caused by the second robot as it screws it together and places the completed assembly into the Done bin. The Ship transition is an output machine that sends completed assemblies to their proper destination.

: Assuming no additional input machines are fired, run the Petri Net shown in Figure 7.4.13 until it stalls. How many competed assemblies are shipped?

 

7.4.3. Kahn Process Networks

Gilles Kahn first introduced the Kahn Process Network (KPN). We use KPNs to model distributed systems as well as signal processing systems. Each node represents a computation block communicating with other nodes through unbounded FIFO channels. The circles in Figure 7.4.14 are computational blocks and the arrows are FIFO queues. The resulting process network exhibits deterministic behavior that does not depend on the various computation or communication delays. As such, KPNs have found many applications in modeling embedded systems, high-performance computing systems, and computational tasks.

Figure 7.4.14. A Kahn Process Network consists of process nodes linked by unbounded FIFO queues.

For each FIFO, only one process puts, and only one process gets. Figure 7.4.14 shows a KPN with four processes and three edges (communication channels). Processes P1 and P2 are producers, generating data into channels A and B respectively. Process P3 consumes one token from channel A and another from channel B (in either order), and then Process P3 produces one token into channel C. Process P4 is a consumer because it consumes tokens.

We can use a KPN to describe signal processing systems where infinite streams of data are transformed by processes executing in sequence or parallel. Streaming data means we input/analyze/output one data packet at a time without the desire to see the entire collection of data all at once. Despite parallel processes, multitasking or parallelism are not required for executing this model. In a KPN, processes communicate via unbounded FIFO channels. Processes read and write atomic data elements, or alternatively called tokens, from and to channels. The read token is equivalent to a FIFO get and the write token is a FIFO put. In a KPN, writing to a channel is non-blocking. This means we expect the put FIFO command to always succeed. In other words, the FIFO never becomes full. From a practical perspective, we can use KPN modeling for situations where the FIFOs never actually do become full. Furthermore, the approximate behavior of a system can still be deemed for systems where FIFO full errors are infrequent. For these approximations we could discard data with the FIFO becomes full on a put instead of waiting for there to be free space in the FIFO.

On the other hand, reading from a channel requires blocking. A process that reads from an empty channel will stall and can only continue when the channel contains sufficient data items (tokens). Processes are not allowed to test an input channel for existence of tokens without consuming them. Given a specific input (token) history for a process, the process must be deterministic so that it always produces the same outputs (tokens). Timing or execution order of processes must not affect the result and therefore testing input channels for tokens is forbidden.

To optimize execution some KPNs do allow testing input channels for emptiness as long as it does not affect outputs. It can be beneficial and/or possible to do something in advance rather than wait for a channel. In the example shown in Figure 7.4.14, process P3 must get from both channel A and channel B. The left side of Program 7.4.8 shows the process stalls if the AFifo is empty (even if there is data in the BFifo). If the first FIFO is empty, it might be efficient to see if there is data in the other FIFO to save time (right side of Program 7.4.8).

void Process3(void){

int32_t inA, inB, out;

  while(1){

    while(AFifo_Get(&inA)){};

    while(BFifo_Get(&inB)){};

    out = compute(inA,inB);

    CFifo_Put(out);

  }

}

   

void Process3(void){

int32_t inA, inB, out;

  while(1){

    if(AFifo_Size()==0){

      while(BFifo_Get(&inB)){};

      while(AFifo_Get(&inA)){};

    } else{

      while(AFifo_Get(&inA)){};

      while(BFifo_Get(&inB)){};

    }

    out = compute(inA,inB);

    CFifo_Put(out);

  }

}

Program 7.4.8. Two C implementations of a process on a KPN. The one on the right is optimized.

 

Processes of a KPN are deterministic. For the same input history, they must always produce the same output. Processes can be modeled as sequential programs that do reads and writes to ports in any order or quantity if the determinism property is preserved.

KPN processes are monotonic, which means that they only need partial information of the input stream to produce partial information of the output stream. Monotonicity allows parallelism. In a KPN there is a total order of events inside a signal. However, there is no order relation between events in different signals. Thus, KPNs are only partially ordered, which classifies them as an untimed model.

 

7.5. Design for Manufacturability

Using standard values for resistors and capacitors makes finding parts quicker. Standard values for 1% resistors range from 10 Ω to 2.2 MΩ. We can multiply a number in Tables 7.5.1, 7.5.2, 7.5.3, and 7.5.4 by powers of 10 to select a standard value resistor. For example, if we need a 5 kΩ 1% resistor, the closest number is 49.9*100, or 4.99 kΩ.

Sometimes we need a pair of resistors with a specific ratio. There are 19 pairs of resistors with a 2 to 1 ratio (e.g., 20/10). There is only one pair with a 3 to 1 ratio, 102/34. Similarly, there is only one pair with a 4 to 1 ratio, 102/25.5. There are 19 pairs of resistors with a 5 to 1 ratio (e.g., 100/20). There are 5 pairs of resistors with a 7 to 1 ratio (e.g., 93.1/13.3, 105/15, 140/20, 147/21, 196/28). There are no pairs with ratios of 6, 8, or 9.

Using standard values can greatly reduce manufacturing costs because parts are less expensive, and parts for one project can be used in other projects. Ceramic capacitors can be readily purchased as E6, E12, or E24 standards. Filters scale over a fairly wide range. If a resistor is increased by a factor of x and the capacitor is reduced by a factor of x, the filter response will remain unchanged. For example, the response of a filter that uses 100 kΩ and 0.1 µF will be the same as a filter with 20 kΩ and 0.5 µF. Resistors that are too low will increase power consumption in the circuit, and resistor values that are too high will increase noise.  1% resistors below 100 Ω and above 10 MΩ are hard to obtain. Precision capacitors below 10 pF and above 1 µF are hard to obtain. High-speed applications use lower values of resistors in the 100 Ω to 1 kΩ range, precision equipment operates best with resistors in the 100 kΩ to 1 MΩ range, while portable equipment uses higher values in the 100 kΩ to 10 MΩ range.

E12 standard values for 10% resistors range from 10 Ω to 22 MΩ. We can multiply a number in Table 7.5.1 by powers of 10 to select a standard value 10% resistor or capacitor. The E6 series is every other value and typically available in 20% tolerances.

10

12

15

18

22

27

33

39

47

56

68

82

Table 7.5.1. E12 Standard resistor and capacitor values for 10% tolerance.

E24 standard values for 5% resistors range from 10 Ω to 22 MΩ. We can multiply a number in Table 7.5.2 by powers of 10 to select a standard value 5% resistor. For example, if we need a 25 kΩ 5% resistor, the closest number is 24*1000, or 24 kΩ. Capacitors range from 10 pF to 10 µF, although ceramic capacitors above 1 µF can be quite large. The physical dimensions of a capacitor also depend on the rated voltage. You can also get 1% resistors and 1% capacitors in the E24 series.  For example, if you need a 0.05 µF capacitor, you can choose an 0.047µF E12, or a 0.051µF E24 capacitor.

10

11

12

13

15

16

18

20

22

24

27

30

33

36

39

43

47

51

56

62

68

75

82

91

Table 7.5.2. E24 Standard resistor and capacitor values for 5% tolerance.

Table 7.5.3 shows the E96 standard resistance values for 1 % resistors. Table 7.5.4 shows E192 standard resistance values for 0.5, 0.25, 0.1% tolerances. Tables 7.5.1 and 7.5.2 refer to both resistors and capacitors, but the E96 and E192 standards refer only to resistors.

10.0

10.2

10.5

10.7

11.0

11.3

11.5

11.8

12.1

12.4

12.7

13.0

13.3

13.7

14.0

14.3

14.7

15.0

15.4

15.8

16.2

16.5

16.9

17.4

17.8

18.2

18.7

19.1

19.6

20.0

20.5

21.0

21.5

22.1

22.6

23.2

23.7

24.3

24.9

25.5

26.1

26.7

27.4

28.0

28.7

29.4

30.1

30.9

31.6

32.4

33.2

34.0

34.8

35.7

36.5

37.4

38.3

39.2

40.2

41.2

42.2

43.2

44.2

45.3

46.4

47.5

48.7

49.9

51.1

52.3

53.6

54.9

56.2

57.6

59.0

60.4

61.9

63.4

64.9

66.5

68.1

69.8

71.5

73.2

75.0

76.8

78.7

80.6

82.5

84.5

86.6

88.7

90.9

93.1

95.3

97.6

Table 7.5.3. E96 Standard resistor values for 1% tolerance(resistors only, not for capacitors).

 

: Let R = 100 kΩ. Find an E24 capacitor such that 1/(2πRC) is as close to 1000 Hz as possible.

: Rather than using an E96 resistor, find two E24 resistors such that the series combination is as close to 127 kΩ as possible.

 

10.0

10.1

10.2

10.4

10.5

10.6

10.7

10.9

11.0

11.1

11.3

11.4

11.5

11.7

11.8

12.0

12.1

12.3

12.4

12.6

12.7

12.9

13.0

13.2

13.3

13.5

13.7

13.8

14.0

14.2

14.3

14.5

14.7

14.9

15.0

15.2

15.4

15.6

15.8

16.0

16.2

16.4

16.5

16.7

16.9

17.2

17.4

17.6

17.8

18.0

18.2

18.4

18.7

18.9

19.1

19.3

19.6

19.8

20.0

20.3

20.5

20.8

21.0

21.3

21.5

21.8

22.1

22.3

22.6

22.9

23.2

23.4

23.7

24.0

24.3

24.6

24.9

25.2

25.5

25.8

26.1

26.4

26.7

27.1

27.4

27.7

28.0

28.4

28.7

29.1

29.4

29.8

30.1

30.5

30.9

31.2

31.6

32.0

32.4

32.8

33.2

33.6

34.0

34.4

34.8

35.2

35.7

36.1

36.5

37.0

37.4

37.9

38.3

38.8

39.2

39.7

40.2

40.7

41.2

41.7

42.2

42.7

43.2

43.7

44.2

44.8

45.3

45.9

46.4

47.0

47.5

48.1

48.7

49.3

49.9

50.5

51.1

51.7

52.3

53.0

53.6

54.2

54.9

55.6

56.2

56.9

57.6

58.3

59.0

59.7

60.4

61.2

61.9

62.6

63.4

64.2

64.9

65.7

66.5

67.3

68.1

69.0

69.8

70.6

71.5

72.3

73.2

74.1

75.0

75.9

76.8

77.7

78.7

79.6

80.6

81.6

82.5

83.5

84.5

85.6

86.6

87.6

88.7

89.8

90.9

92.0

93.1

94.2

95.3

96.5

97.6

98.8

Table 7.5.4. E192 Standard resistor values for tolerances better than 1% (resistors only, not for capacitors).

 

7.6. Low-Power Design

To save energy, our parents taught us to "turn off the light when you leave the room." We can use this same approach to conserve energy in our embedded system. There are many ways to place analog circuits in low power mode. Some analog circuits have a low-power mode that the software can select. For example, the MAX5353 12-bit DAC requires 280 µA for normal operation, but the software can place it into shut-down mode, reducing the supply current to 2 µA. Some analog circuits have a digital input that the microcontroller can control placing the circuit in active or low-power mode. For example, the TPA731 audio amplifier has a CD pin, see Figure 7.6.1. When this pin is low, the amplifier operates normally with a supply current of 3 mA. However, when CD pin is above 2 V, the supply current drops down to 65 µA. So, when the software wishes to output sound, it sends a command to the MAX5353 to turn on and makes PB0 equal to 0. Conversely, when the software wishes to save power, it sends a shutdown command to the MAX5353 and makes PB0 high.

Figure 7.6.1. Audio amplifier that can be placed into low-power mode.

The most effective way to place analog circuit in a low-power state is to shut off its power. Some regulators have a digital signal the microcontroller can control to apply or remove power to the analog circuit. For example, when the OFF pin of the MAX604 regulator is high, the voltage output is regulated to +3.3 V, as shown in Figure 7.6.2. Conversely, when the OFF pin is low, the regulator goes into shut-down mode, and no current is supplied to the analog circuit. When the software wishes to turn off power to the analog circuit, it makes PB0 equal to 0. Conversely, when the software wishes enable the analog circuit, it makes PB0 high. The microcontroller itself always will be powered. However, most microcontrollers can put themselves into a low-power state.

Figure 7.6.2. Power to analog circuits can be controlled by switching on/off the regulator.

We can save power by designing with low-power components. Many analog circuits require a small amount of current, even when active. The MAX494 requires only 200 µA per amplifier. If there are ten op amps in the circuit, the total supply current will be 2 mA. For currents less than 8 mA, we can use the output port itself to power the analog circuit, as shown in Figure 7.6.3. To activate the analog circuit, the microcontroller makes the PB0 high. To turn the power to the analog circuit off, the microcontroller makes PB0 low.

Figure 7.6.3. Power to analog circuits can be delivered from a port output pin.

Considerable power can be saved by reducing the supply voltage. A microcontroller operating at 3.3 V requires less than half the power for an equivalent +5 V system. Power can be saved by turning off modules (like the timer, ADC, UART, and SSI) when not in use. Whenever possible, slowing down the bus clock with the PLL will save power. Many microcontrollers can put themselves into a low-power sleep mode to be awakened by a timer or external event.

: Why is running at 3.3V half the power of running at 5V?

There are many factors that affect the supply current to a microcontroller. The first important factor is bus frequency, as power increases linearly with bus frequency. A second important factor is activating sleep mode when there are no software tasks to perform. The TM4C has a sleep mode, a deep sleep mode, and a hibernate mode. Hibernate mode on the TM4C123 requires 5 µA. The MSPM0G3507 has many low power modes.

SLEEP: 458 µA at 4 MHz

STOP: 47 µA at 32 kHz

STANDBY: 1.5 µA with RTC and SRAM retention

SHUTDOWN: 78 nA with I/O wakeup capability

 

Hypothesis: Microcontroller power is linearly related to bus frequency.

Assumptions: Supply voltage (Vdd) is constant, independent of frequency. Almost no current flows into or out of the gate. Even though the input resistance is huge, there is a non-neglible effective capacitance, Ceff, which each output must drive.

Figure 7.6.4. Digital logic is made with P-channel and N-channel MOSFETs.

Proof: CMOS logic uses a totem pole configuration of P-channel on top of N-channel, see Figure 7.6.4. Since the gate currents are neglected, the current flow from Vdd to ground is determined by the drain-source currents. When the logic level is constant, one transistor is on, and the other is off. So, almost no current flows from Vdd to ground. When the output is low, there is no charge on Ceff. However, when the output changes from low to high, charge is loaded onto Ceff. Current flows from Vdd source to drain through the P channel MOSFET to charge Ceff. The energy stored in the capacitor is U=½Ceff*Vdd2. Unfortunately, when the output changes from high to low, Ceff is discharged, current flowing from drain to source across the N-channel MOSFET. The total energy lost is linearly related to the total number of transitions in the digital circuit. Therefore, the average power is linearly related to the bus frequency

Figure 7.6.5. Supply current versus bus frequency for an MSPM0G3507.

 

 

7.7. Design for Testability

Design for test (DFT) is important and should be incorporated at every stage of a design. We can greatly increase reliability by testing the device before it is used, while it is being used, and after it has been used. Having a plan for testing should be a part of every project. In software we can add verbose output, event logging, assertions, diagnostics, resource monitoring, test points, and fault injection hooks. The approach to hardware testing mimics the two important factors for software testing: visibility and control. Visibility allows the test engineer to observe system behavior, and control allows the test procedure to manipulate inputs to modules within the system. We need to observe the outputs, side effects and internal states. An important parameter is the intrusiveness of the observation. In other words, we need to be careful to not introduce delays that affect the dynamic behavior. Storing data into an array (software dump) at run time can usually be performed with delay overheads of less than 1 µs.

We can add hardware features to our system to facilitate testing. The first is the ability to quickly and reliable attach hardware test equipment to the device. For low production products we can add test points to the circuit to make it easy to attach oscilloscopes and voltmeters. For higher production projects we can add test connectors that directly connect to test equipment like logic analyzers or signal generators. Basically, we need to create known inputs, and record responses at strategic points in the system.

The verbose modes found in some compilers add debugging output along with data output. This approach may cause significant slowdown in dynamic behavior, so it will be important to measure timing behavior with and without verbose mode. For aspects of the system that are not real time, verbose is an excellent testing feature. When you add the "-v" switch with a command in Unix, the mail program will display its communication with the local mail server.

Logging or a software dump is an excellent tool for real-time systems. If you place the following dump at strategic places in your system, after a short while, the Buffer contains the last 256 times the debugging instrument was invoked. Subtracting "3" compensates for the time it takes to run the instrument up to the point at which it reads the SysTick timer. The entire instrument is 12 assembly instructions and runs in about 16 bus cycles. In most cases this will be minimally intrusive.

uint32_t Buffer[256];
uint8_t N=0;
__inline void RecordTime(void){
  Buffer[N] = NVIC_ST_CURRENT_R-3;
  N++;  // 8-bit variable goes 0 to 255
}
 

Fault injection is the ability to introduce error conditions to see if the system properly handles them. A monitor is a debugging mechanism to observe internal behavior. A good example of a monitor is configuring unused pins as outputs and writing strategic information to these pins during execution. If we connect the pins to a logic analyzer, we have a minimally intrusive debugging instrument. Other examples of monitors include streaming data out unused ports such as a UART, CAN, or SPI. We could log debug data onto flash drive. A testing interface is a hardware or software connection between the system and test procedure.

: Identify three design-for-test features on the PCB in Figure 7.7.1.

A close-up of a circuit board Description automatically generatedA green circuit board with wires Description automatically generated

Figure 7.7.1. Mockup and PCB for an audio player.

 

 

7.8. Lab 7. System Design

The two parts of Lab 7 for this course can be downloaded from these links Lab07A.docx and Lab07B.docx

Each part also has a report Lab07AReport.docx and Lab07BReport.docx

There is a bill of materials Lab7BOM.xlsx

There is a requirement document to edit RequirementsDocument.docx

 

 
This work is based on the course ECE445L taught at the University of Texas at Austin. This course was developed by Jonathan Valvano, Mark McDermott, and Bill Bard.

Reprinted with approval from Embedded Systems: Real-Time Interfacing to ARM Cortex-M Microcontrollers, ISBN-13: 978-1463590154

Creative Commons License
Embedded Systems: Real-Time Interfacing to ARM Cortex-M Microcontrollers by Jonathan Valvano is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.