Given small computational resources, how was navigation implemented? (Not samples of old guidance software)

Question

Update 2 : The youtube vidoe How did NASA Steer the Saturn V answers this question and then some, a must watch.

Update: I really wanted to know how spacecraft navigation (not guidance) computers worked, given small computational resources. I have asked in another question and edited this question to limit answers to examples of old guidance software source code, For those interested in samples of old guidance software please refer to Samples of old guidance software using computational resources on Earth implementing navigation in space instead. Leaving the original (incorrect question below as it was in order to not make the responses look irrelevant).

In an article I came across the something like "X used hardware programme for Venus mission with 65 KB (not sure if this number is correct?) memory".

I am a software developer and with all the resources available today I cannot fathom where one could even start such an endeavour.

Is there an archive (museum) of old/antique software that was written (hard or soft) for interplanetary missions? if something at a higher level than assembly or the equivalent in today's Java, Pascal, C#, etc. programming languages with no consideration for memory and disk usage then that would be even better.

From what little I understood it seems a task equivalent to construction of pyramids with primitive tools. Are there any simulation or tools to get a today's simpleton programmer a glimpse and appreciation of what those giants did?

Answer 1

In many of the early probes, up until close to Apollo there were not true computers on space probes. All computing was done on Earth and the onboard electronics was known as a sequencer, for Pioneer 10 it had 222 possible commands 5 of which could be readied. Early Venus probes sent data by mechanically switching different sensors to modulate a CW transmitter in turn and sorting it all apart on Earth.

This also applied to much of the Apollo launch process, where the hardware in the launch platform did not run true software but a sequence (from here) of 'wait, activate this, wait, measure that and if out of bounds hold else continue'.

Along with the AGC code link by Ludo you can look at the abort controller as a smaller scale example of how things were done (fixed loop of known steps and timing).

Even today it is very rare to send code to a space craft that does not boil down to a sequence of very specific instructions to be run in order. Curiosity has some autonomous navigation and photo taking capability but generally branching code is there to trigger fallback/fail safe 'oops stop, solve antenna pointing problem and call home for instructions' rather than AI or learning code.

In general terms code was made to fit the same way people program for microcontrollers today:

Not having any form of user interface in code (Apollo DSKY was largely hardware)

Using approximation or integer math over floating point (lots of things are possible where pi = 3) or precompute constants on Earth and upload when required (say gravity or engine performance)

Custom designing supporting hardware like star trackers to be preloaded with constants from Earth and to output pre formatted and bound checked for the next processing step. In fact, bounds check only once, where data is sourced and ensure no following step can overflow it.

Design algorithms to work in register(s) rather than memory locations (which makes horrible source since you do not have variables) but means you can avoid lots of moving values in and out of memory.

Avoid general problems for the specific, for space craft this was all about navigation, reporting sensor/instrument states and pointing. All of these could have carefully crafted code that worked well over a specific range of inputs (Though see).

Trust your data (in security sense) (though nature can still get you)

Answer 2

(originally answered to "Samples of old guidance software")

The first that comes to mind is the Github repository of the Apollo 11 Guidance Computer (AGC). The repository has both Command Module and Lunar Module software, but note that it is transcribed from hardcopies, so it might not be fully complete (yet). You can find a simulator of the AGC on the Virtual AGC website (there's a ton of other references there also).

Answer 3

I am a software developer and with all the resources available today I cannot fathom where one could even start such an endeavour.

There are plenty of computer-based systems to this day that have to live with such limitations. There are plenty of embedded systems where 2^16 (65536) bytes of memory remains a luxury. After all, on machines that use 16 bit memory addresses (plenty of which still exist and are plenty of which are still manufactured to this day), there's no point in having over 65636 bytes of memory. And just as there's no problem with a computer with 64 bit addresses having less than 18+ exabytes of memory, there's no problem with a computer that uses 16 bit addresses having less than 2^16 bytes of memory.

There are many ways to start with such an endeavor. The number one rule is to eschew the use of an operating system. Many (most?) embedded systems are bare machines. There's no OS, and there's only one program running, ever. Your microwave oven has a computer operating as an embedded system, and it has no operating system. If your car was manufactured in the last 25+ years, it has lots of embedded systems running in it. If your car is anywhere close to modern, it has several dozens of microcontrollers that collectively run several million lines of code.

Many of the microcontrollers in a modern car are not subject to the 64K (2^16, or 65536) address limit. Back in the day, that was a very common limit, and it inherently limited the size of memory. But it did not limit storage. The problem of having disk size exceed address limitations was solved in the 1950s and 1960s. A common solution was to use memory overlays. This technique, one I'm glad to have (mostly) forgotten about, remains common to this day in embedded systems programming.

Another widely used technique was and is to have the embedded machine follow a Harvard architecture as opposed to a von Neumann architecture. There is no distinction between code and data in a Von Neumann machine. Code and data are very different things in a Harvard architecture machine, possibly with different word sizes. Your laptop or desktop machine most likely is a von Neumann architecture machine, at least on the surface. Deep under the hood it looks more like a Harvard machine, with separate caches for code and data.

Answer 4

The way it was implemented in the ICBM world was that you had six fellows sitting around a table designing the mathematical routines and overall architecture, the program component's detailed coding, and the computer hardware all at the same time. Five lines of code per day was considered a good day's work. Most of the time was spent arguing about whether to do something with hardware or software. Integrated circuits had advanced to the point of four-bit registers being available. They were used for the cpu's two registers.

There was no addressable memory in the system I worked on. Just a disk with a bunch of fixed heads. The code was clocked to the disk. There was an upper and lower bus and two registers of one word length, but it was a big word.

There ended up being four programs that could be swapped using remote data change. Only one was for flight, the others were ground programs.

Hardware did most of the work, things like 3 x 3 matrix math were done with a few microcode instructions that resulted in a new matrix replacing an old one in the same location on the disk.

The cpu often had areas that weren't being used during these longer intructions, so they could sneak little additions/subtractions/multiplications/divisions in the middle. These intructions only switched small pieces of the cpu, and there were LOTS of instructions available. You just had to make sure everything was in the right place on the disk so that it was available when there was a bit of free time. They had five different instructions for dividing two numbers, differing only in the route and timing of the process within cpu to avoid colliding with other ongoing computations. A lot of the bookkeeping functions got done this way.

The really fun part was that you could start a long instruction before you had all the numbers to complete it. While it was grinding on the front end, you could initiate an addition operation and leave it in a register for the long instruction to find later. You might even be able to write it to the disk. These were a real joy to trace and debug.

The nav computer had to drive three output signals to steer the rocket. It knew nothing about staging or anything else. It had a table that said it should see accelerometer counts of x,y,z at time t (accumulated pulses equaled accelerometer axis velocity). It compared the actual counts to the preprogrammed table and calculated new steering signals.

The bottom line is that the programmers had a pretty limited goal and had a complete map of the cpu in their head and could follow the entire cpu operation in their head as the program components were executed.

I wasn't in on the design phase, but was trained on the cpu and microcode by one of the guys that sat at the table.

Answer 5

Check out the FORTH language. It makes no distinction between user code and the code in the (tiny) OS kernel. It was used in the firmware of early satellites. A good description is here: https://en.wikipedia.org/wiki/Forth_(programming_language)

Answer 6

You might want to read this book: https://www.goodreads.com/book/show/7754526-the-apollo-guidance-computer

The first half is a detailed description of the hardware architecture of the Apollo Guidance Computer and the software that ran on it. There are some fascinating discussions of the limitations of the hardware and what the designers did to overcome those limitations.