Global Positioning of Ada


Paul Pukite, DAINA, pukite@daina.com


Given the fascination the media has had with the Internet (aka the Information Superhighway), one could easily overlook the success of yet another government technology transfer project. The Global Positioning System (GPS) has clearly made the leap from serving primarily as a military defense tool to a product with a vast amount of commercial potential. From uses in aviation to outdoor recreational activities, we have already seen surprising new markets opening up.

If we look at the core of GPS technology, we find that Ada has played a significant role in its success. Although the DoD will not make available all of the details of the GPS architecture for security reasons, the commercial end-user applications have had a definite Ada flavor.

What is GPS?

The DoD developed the GPS as a worldwide, satellite-based radio- navigation system. Simply put, it allows accurate latitude/longitude and time measurements from anywhere on the earth. GPS provides two levels of service - a Standard Positioning Service (SPS) and a Precise Positioning Service (PPS).

The SPS gives commercial users horizontal positioning accuracy within 100 meters (at 95 percent probability) and 300 meters (99.99 probability), vertical positioning accuracy within 140 meters (95 percent probability), and timing accuracy within 340 nanoseconds (95 percent probability). The military uses the more-accurate PPS but apparently the DoD does grant access to qualified commercial users through special agreements.

You don't have to think too hard to come up with commercial applications for GPS. Civilian aviation companies have plans for incorporating GPS navigation aids on-board aircraft; thus improving logistics and air traffic control operations. The same possibilities hold true for marine navigation. And a huge opportunity exists for land applications. Besides the obvious commercial transport and dispatching uses, several novel uses come to mind; these include surveying, telecommunications and electric power synchronization, agriculture and forestry, census taking, meteorological radiosondes, and backpacking! (You can currently purchase a portable setup that "cookie-crumb" traces your travel route in real-time on PC mapping software.) Not surprisingly, the DoD notes that civil users already far outnumber military users.

The GPS partitions into three major segments: SPACE, CONTROL, and USER. The SPACE segment consists of the orbiting satellites which transmit continuous radio signals to the earth. The CONTROL segment resides across several worldwide monitoring stations and effectively controls the satellites orbits and radio signal content. The USER segment consists of receivers that provide positioning, velocity and precise timing to the end-user; this part we as users can get our hands on.

Where does Ada fit in?

You can imagine that the software for such a sophisticated system as GPS has become extensive in scope. And it all has to fit together with tight timing and reliability constraints. In a way, a portable GPS reminds me of a miniature, hand-held NASA mission control center.

First consider the SPACE segment. The embedded software on the satellites has to tolerate faults and work in real-time. The satellites must operate nearly autonomously, both in receiving data from the control center and sending data to the users. Richard Riehle describes satellite software requirements and implementations in an article Ada in Space Systems in Embedded Systems Programming magazine, November 1994. Based on the overall reliability of the code, Ada has certainly become a standard for satellite software.

The ground-based CONTROL code incorporates numerical laws of orbital mechanics and gravity, atmospheric models, atomic clocks, and cryptography. Altogether, hundreds of people put together more than a million lines of code over the course of several years to establish this segment. The GPS Operational Control Segment (OCS) runs on IBM mainframes with a combination of Jovial and Ada code (Federal Computer Week, 7-31-95). I have a suspicion that much of this work remains classified and can only speculate on implementation; but as GPS dates back to the 1970's, Jovial certainly played the early role, with Ada likely introduced later on. A tool called the Ada Simulation Development System (ASDS) has been used to model complete GPS simulation orbital applications. The WWW site at McDonnell Douglas gives more background on the orbital models used (and information describing how GPS and Ada is used during automated rendezvous and docking of the shuttle).

The United States Coast Guard Differential Global Positioning System has reportedly been developed using Ada. This uses land-based transmitters to improve the accuracy of conventional GPS.

Understandably, I have found more publicly-available information on the commercial USER segment of GPS. Several documents in the Ada Information Clearing House describe the implementation of GPS receivers and application software.

GPS receivers

Vendors sell GPS receivers starting at $300. Highly integrated, these receivers gather several of the analog radio signals and convert to the final digital data representation after suitable processing.

Rockwell Collins in Cedar Rapids, Iowa invented and developed a GPS satellite communications board with software written in Ada in the mid-1980's. They have installed the board in commercial airplanes, trains, as well as a demonstration van to show-off the technology to auto makers. In 1991, the Ada-run NavCoreV (now the MicroTracker) GPS modules were sold to OEM manufacturers for around $450. At the time, it was the world's smallest commercial 5-channel GPS module, providing position, velocity, and time data. The target, the Advanced Architecture Microprocessor II (AAMP2) includes 25,000 lines of Ada code. The market for the 2.5" x 5" module includes navigational systems for airplanes, commercial fishing boats, trains, yachts, etc. Currently, Rockwell uses the AAMP5 processor and 10 channel All In View GPS sensors to form an integrated very high performance inertial navigation system (INS). The GPS/INS system uses a DDC Ada 83 front end combined with an AAMP5 backend code generator.

On a different scale, the European Space Agency (ESA) contracted Alcatel-SEL to develop GPS receivers for various space applications. A specially qualified 5-channel unit has flown on a shuttle mission in 1993. The software targeted a Motorola 80385 using an Alsys cross-compiler. Notably, the application software relies on the real-time capabilities of the Ada kernel.

Avionics

Using GPS as a navigation aid aboard a commercial aircraft requires careful consideration. Whenever computers replace manual operation under a safety-comes-first policy, the reliability of the software becomes a primary concern.

For navigation and tracking, each aircraft needs a built-in GPS receiver (likely redundantly configured) connected to a fault-tolerant computer. To assure the same reliability of software, we can use formal methods during development. For example, a formal methods approach was applied to the navigation subsystem of the Boeing 777. The Honeywell navigation specification project gives an overview of the issues involved. The formal methods start with algorithmic definitions of signal processing and position determination. They then relate the mathematical model to Ada by partitioning the system into Ada package specifications, and annotating individual Ada functions and procedures with formal specifications. As with much of the software on board the 777, the final implementation will be in Ada (including GPS, Brakes, Axle steering and Power Management system) .

Recently the FAA approved such a GPS-based aircraft navigation system. As a cooperative effort among several airlines, Honeywell and Boeing, the FAA certified the Future Air Navigation System 1 (FANS-1), which Qantas introduced in 1995 on air routes over the Pacific. Certified on the 747-400, airliners equipped with the Ada-based FANS-1 will make primary use of Global Positioning System equipment for navigation and a data link for two-way satellite communication between pilots and air traffic controllers.

An Ada GPS Application

I briefly mentioned some of the civilian uses of GPS. As an example, hikers and backpackers have used hand-held GPS units to aid in navigation. The following application uses Digital Elevation Model (DEM) topographic maps obtained from the U.S. Geologic Survey to plot out hiking waypoints.

One type of USGS DEM data file has a 3 second resolution organized at integral degrees of latitude and longitude. In my application, a Microsoft Windows Ada program converts the DEM files to stereoscopic images that reproduce a three-dimensional perspective of the terrain. Then, waypoints stored in the Trimble GPS receiver are downloaded to the PC through a RS-232 serial port and overlayed onto the DEM map.

The following image is converted from a DEM of the Eau Claire West quadrangle in southeastern Minnesota. GPS readings were taken in the Trout Valley Unit of the Richard J. Dorer Memorial Hardwood State Forest (south of Wabasha along the Whitewater River). A scenic overlook waypoint is shown on the map with a rounded-off GPS reading. This overlooks the Upper Mississippi River National Wildlife and Fish Refuge with a view northeast across to Wisconsin. Due to the deep valleys and breathtaking views, this area is often called Minnesota's "little Switzerland".

In case you have not viewed a stereoscopic image before, the common technique is to cross your eyes until the images overlap and then let your eyes relax. The arrow points to the overlook.

While Ada has been widely known to be a success in embedded applications, it has clear advantages for desktop applications as well. I found that Ada used in the context of this PC mapping program is every bit as powerful as C++ and will become more widely used due to the popularity of 32-bit multithreading operating systems such as Windows NT/95 and OS/2.


Concluding remarks. I came across a reference to the complexity of GPS software where a letter-to-the-editor had questioned Niklaus Wirth's plea for lean software and using a strongly typed language. The letter writer said that Wirth vastly over-stated the need for a strongly typed language but then curiously asserted that most interesting programs (i.e. GPS) were large rather than lean anyway. I thought to myself that a complex system like GPS was probably the best case for a language like Ada (especially when specifications and modular integration are vital). Sure enough, after some reference searching, I came across several of the previously described Ada/GPS examples and coded a few of my own GPS mapping applications.

>From satellites and command and control systems to receivers and navigation software, Ada has played a vital role in the success of GPS. Unfortunately, I suspect that the typical users who connect their GPS unit to a portable laptop probably think that the software starts and ends with what you can buy in shrink-wrap at the store.


45N 2'35.5" 93W 14'46.4"

Columbia Heights, MN

This page is maintained by Paul Pukite, DAINA, pukite@daina.com.
It was last updated on 18 Oct 1995 at 10:06p.m.


The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.