During the Apollo missions to the Moon, a critical task for NASA was determining the spacecraft's position. To accomplish this, they developed a digital ranging system that could determine the distance to the spacecraft, hundreds of thousands of kilometers away, with an accuracy of about 1 meter.
The basic idea was to send a radio signal to the spacecraft and determine how long it takes to return. Since the signal traveled at the speed of light, the time delay gives the distance. The main problem is that due to the extreme distance to the spacecraft, a radarlike return pulse would be too weak.2 The ranging system solved this in two ways. First, a complex transponder on the spacecraft sent back an amplified signal. Second, instead of sending a pulse, the system transmitted a long pseudorandom bit sequence. By correlating this sequence over multiple seconds, a weak signal could be extracted from the noise.1
In this blog post I explain this surprisinglycomplex ranging system. Generating and correlating pseudorandom sequences was difficult with the transistor circuitry of the 1960s. The ranging codes had to be integrated with Apollo's "Unified SBand" communication system, which used highfrequency microwave signals. Onboard the spacecraft, a special frequencymultiplying transponder supported Doppler speed measurements. Finally, communicating with the spacecraft required a complex network of ground stations spanning the globe.
The ranging system
The ranging system measured how long a signal takes to travel to the spacecraft and back.3 As shown below, the ranging system transmitted a pseudorandom bit sequence to the spacecraft. The spacecraft's transponder returned the signal to the ground receiver. The returned signal was correlated against the original signal to determine the time shift, and thus the distance. Meanwhile, a Doppler measurement (described later) provided the speed of the spacecraft.4
The key step was to correlate the transmitted and received signals to determine the time delay. When the two signals were aligned with the proper delay, the bits matched. Because the sequence is pseudorandom, if the two signals were misaligned, the bits didn't match (except randomly).5 Thus, by testing how many bits match (i.e. the correlation) for different delays, the proper delay could be determined. Since the signals could be correlated over long time intervals (multiple seconds), the range could be determined even if the signal was extremely weak and hidden by noise.
The code sequence needed to be very long in order to unambiguously determine the range; the system uses a pseudorandom sequence that is 5,456,682 bits long. Since the code is sent at 1 megahertz, it repeats every 5.46 seconds. A radio signal can travel 800,000 kilometers and back in this time, while the Moon is about 384,000 kilometers away, so the system can unambiguously measure over twice the distance to the Moon. Note that at one megahertz, one bit of the signal corresponds to 150 meters of range. The system achieved more accuracy by comparing the phase of the signals.
Conceptually, the transmitted and received sequences were shifted until they match, and the amount of shift gave the delay, and thus the distance. However, it's impractical to try 5 million different shifts to match the sequence, especially with the technology of the 1960s. To solve the matching problem, the sequence was constructed from several shorter codes, from 2 to 127 bits long. These "subcodes" were short enough that they could be matched by brute force. The overall delay could then be determined by the delays of the subcodes. The system used four subcodes—subcode A had a length of 31 bits, B was 63 bits, C was 127 bits, and X was 11 bits—along with a twovalued clock CL. Since these lengths are relatively prime, the combined sequence has an overall length equal to the product: 5,456,682. The important concept is that a very long code could be generated and matched using hardware, since the subcodes were short.
I made an interactive page that demonstrates how the subcode sequences were created. The subcode sequences of lengths 31, 63, and 127 were generated with a wellknown technique called the linearfeedback shift register (LFSR). In this technique, a shift register of length N holds bits. In each step, a new bit is generated from the exclusiveor of two bits in the shift register. The new bit is shifted in, and an old bit is shifted out, providing a code bit. This technique can generate a pseudorandom sequence of length 2^{N}1 with good statistical properties. In order to generate a subcode of length 11, the X codes were generated from a Legendre sequence.7
Combining the subcodes to form the overall code isn't as straightforward as you might think, since each subcode must be individually recognizable in the result.
The A, B, and C subcodes were combined with the majority function maj(A,B,C)
, which returns the most common bit out of the three inputs.6
The complete formula for the bit sequence was
(X·maj(A,B,C))⊕CL.
Construction of the ranging system
The ranging process was implemented by the "Mark I ranging subsystem" below. Although this was called a "specialpurpose binary digital computer", it's not really a computer in the modern sense, but more of a state machine that moved through the necessary steps. First, the ground station sent the code sequence to the spacecraft and synchronized to the received signal. Next, the ranging system tested the different offsets for the X subcode and found the offset with the best correlation. It repeated the process for the A, B, and C subcodes. The digital circuitry performed some tricky modulo arithmetic8 to compute the range from the subcode offsets. Finally, the Doppler subsystem determined the spacecraft's speed and constantly added this to the range to keep the range up to date as the spacecraft moved. I've made an interactive page that demonstrates these steps.
The ranging system was built from "TPac modules", boards that used transistors and other discrete components to build simple digital components such as logic gates and flip flops.9 The TPac modules were introduced by Computer Control Company in 1958 and were designed for quick and efficient implementation of a digital system, running at 1 MHz. Groups of 32 TPac cards were mounted in a "TBLOC" rackmounted chassis, and 10 TBLOCs were installed in two racks. The cards were connected by plugging wires and taper pins into a large grid.
One module was the TPac LE10 "logic element" module, below, implementing four AND gates. It cost $98 in 1961 (about $700 in current dollars), showing how expensive digital logic was at the time. The ranging system used about 300 digital modules, so the digital circuitry for ranging would have cost hundreds of thousands of (current) dollars, a cost repeated at each ground station.
Tasks that we nowadays consider trivial were difficult with the technology of the time. For instance, the range was stored as a 31bit binary value. But instead of a register, the value was stored in a magnetorestrictive delay line, as torsion pulses in a long nickel wire. To add a value to the range, the circuitry used a singlebit serial adder, adding bits one at a time as they exited the nickel wire, and then cycling the bits back into the wire.
One interesting circuit is the correlation level detector that tests for correlation between a particular subcode and the received signal. The correlation started as an analog voltage, which was converted to a digital value by a "Voldicon. The correlation was integrated over time by summing the binary values using another 31bit storage/adder circuit. The number of summed samples could range from 1 to 2^{19} samples, usersettable through "Digiswitch" thumbwheel switches. By integrating the correlation over a long time interval, an extremely weak signal could be detected in the presence of noise. The system kept track of the best offset, storing the value in another delay line. The total ranging time varied from 1.6 seconds for a strong signal to 30 seconds at lunar distance.
Determining the speed with Doppler
The ranging system could also measure the spacecraft's speed by measuring the Doppler shift of the returned signal. If the spacecraft was moving away from Earth, the waves would be stretched out, lowering the frequency. Conversely, the frequency would increase if the spacecraft was moving towards Earth.10 By measuring the frequency shift, the spacecraft's speed could be accurately determined.12
The Doppler measurement impacted the radio system's design in two ways. First, the spacecraft couldn't simply receive and retransmit the signal, because the Doppler shift from the upwards journey would be lost. Instead, a complex frequencymultiplying transponder system was used, so the downlink signal's frequency was exactly 240/221 times the received uplink frequency.11 Second, the spacecraft used phase modulation (PM) instead of the common frequency modulation (FM) for most communication: since frequency modulation changes the signal's frequency, it would have interfered with the Doppler measurements.
The Apollo radio system
Apollo used a complex radio system called the Unified SBand System that included voice, telemetry, scientific data, television, and the ranging data. These signals were combined and transmitted over a single carrier frequency in the Sband frequency range. The diagrams below show how the spectrum was allocated for the signal up to the spacecraft (transmitted at 2.10640625 GHz), and the downlink spectrum at 2.2875 GHz. These two frequencies are in the exact ratio of 240/221, which turns out to be important. Notice that the voice and data are on fairly narrow subcarriers, while the pseudorandom ranging data has a lower, but very wide spectrum. (The ranging signal looks a lot like white noise due to its randomness.) The wide spectrum makes the ranging signal easier to detect at low levels with noise. Even though the ranging spectrum overlaps with the voice and data subcarriers, they don't interfere too much because the ranging spectrum is spread out.
The transponder
The Sband transponder onboard the spacecraft had a critical role in both ranging and for communications in general. From the outside, the transponder (built by Motorola) is a plain bluegray box, weighing about 32 pounds. The connectors at the right linked the transponder to other parts of the radio system. Internally, the transponder was crammed full of radio circuitry: phase modulators for voice data, a detector for received uplink data, and an FM transmitter for video.14
The block diagram below shows the role of the transponder (red) in the communications system. Once the spacecraft was outside of VHF range (about 1500 miles), all communication used the Sband and went through the transponder. The transponder was connected to a travelingwave tube amplifier and then the spacecraft's antennas.
The photo below shows a closeup of the circuitry inside the transponder. The transponder is constructed of multiple modules, connected by tiny coaxial cables. The frequency multiplier, mixer, IF amplifier, and wide band detector modules are visible. Most of the modules are duplicated on the other side of the transponder to provide redundancy, since a failure of the transponder would jeopardize the mission.
The most complex part of the transponder is how it received the ranging data from Earth and echos it back. To avoid interference, the retransmitted data is at a different frequency from the received data. But in order to preserve the Doppler shift information, the transmitted frequency had to vary with the received frequency, so it couldn't be fixed. Instead, the transponder multiplied the received frequency by exactly 240/221 to generate the retransmission frequency, using a complex phaselocked loop circuit.
A phaselocked loop is a widelyused circuit that allows an oscillator to be locked to another frequency source, even in the presence of noise. It uses a voltagecontrolled oscillator whose output is compared to the input. If the output is falling behind, the oscillator is sped up. If the input is falling behind, the oscillator is slowed down. Eventually, the oscillator will lock onto the input signal and will track it. The transponder uses a more complex circuit, so the output frequency tracks a multiple of the input frequency, specifically the output frequency is 240/221× the input (uplink) frequency.15
The transponder was one of many electronics boxes crammed into the Command Module. The diagram below shows its position in the equipment racks.
The console of the Command Module (below) was extremely complicated, with many controls and switches. The astronauts used the highlighted switches to control the transponder and to turn ranging on and off.
Ground stations
Communication with Apollo required powerful ground stations with large antennas.17 These stations needed to be situated around the world to maintain constant communication with Apollo as the Earth rotated. The three main stations had 85foot (26meter) parabolic antennas and were located in Goldstone, California; Canberra, Australia; and Madrid, Spain, part of the Manned Space Flight Network (MSFN). Other stations had smaller 30foot antennas. Coverage gaps were filled by special ships with 30foot antennas as well as special Apollo Range Instrumentation Aircraft (ARIA), based on C135 cargo aircraft.
The block diagram below gives a hint of the complexity of a ground station, with signal processing equipment as well as computers16 and networking to Mission Control and other sites. The "Ranging Circuitry" block has the most relevance to this discussion, but I'd also like to point out the "angle channel receivers". The antennas were servopositioned to lock onto the spacecraft's signal. This provided an angle measurement of the spacecraft's position, which was combined with the range to yield the spacecraft's 3D position in space.
The photo below shows the ground station's transmitter/receiver cabinets that handled the unified SBand signals. These cabinets were the connection between the microwave equipment (amplifiers and antennas) and the radiofrequency subsystems for voice, data, instrumentation, ranging, and so forth. The photo zooms in on the ranging receiver control panel. This ranging circuitry performed the analog tasks: it demodulated the received ranging signal, tracked the frequency, extracted the clock and the Doppler signal, and measured the correlation. These signals were provided to the digital ranging subsystem described earlier.
Conclusion
The ranging system provided the distance to the spacecraft, the Doppler provided the spacecraft's (radial) velocity, and the position of the receiving antenna provided the spacecraft's angular position. The system provides a great deal of accuracy for distance and speed: 1.5meter range resolution and 0.1 meter/sec speed resolution. Because the angular measurement depended on the physical positioning of the antenna, angular resolution was much worse: 0.025°, which corresponds to over 150 kilometers at the distance of the Moon.
The ranging system illustrates the complexity of Apollo. Even though ranging was a small part of Apollo's navigation, it required complex racks of hardware distributed to sites around the world, specialized algorithms, and an advanced transponder onboard the spacecraft. Almost every part of Apollo has this sort of fractal complexity, where a seeminglysimple requirement such as finding the distance to the spacecraft required numerous innovations. The Sband communication system alone required a 1965 conference with 317 pages of proceedings.
The ranging system is hard to understand from a text description, so I've made two interactive pages that demonstrate it. The first page shows how linearfeedback shift registers (LFSR) and XOR gates generate the subcodes, and how the subcodes create the transmitted signal. The second page shows how the correlations are determined for the various subcodes and how the range is computed from these values.
I've implemented the ranging codes on a Teensy, so the next step is to transmit the codes through an actual Apollo transponder. I announce my latest blog posts on Twitter, so follow me @kenshirriff for updates. I also have an RSS feed. Thanks to Steve Jurvetson for providing the Sband transponder and the travelingwave tube amplifier. Thanks to Mike Stewart for extensive information on the Apollo hardware and CuriousMarc for driving the transponder restoration.
Notes and references

The ranging system has a lot in common with GPS. GPS also works by sending a pseudorandom bit sequence and using correlation to determine the signal's delay. There are several important differences though. First, ranging only determined distance, while GPS determines position in three dimensions and also the exact time. (This is why GPS requires visibility of at least four satellites.)
Second, the GPS signal is transmitted from a satellite and received on the ground, unlike the Apollo ranging signal which was both transmitted and received on the ground. As a result, the GPS receiver doesn't have the transmitted signal available, but must generate its own copy for comparison.
Third, GPS satellites are about 20,000 kilometers from Earth, while the Moon is 384,000 kilometers from Earth, making the Apollo signal much weaker. (Although Apollo did have the advantage of huge 26meter receiving antennas, rather than a GPS antenna that is a few centimeters long.)
Finally, GPS has the advantage of complex integrated circuits to determine the correlation, rather than racks full of transistor logic.
As far as I can tell, there isn't any direct connection between the Apollo ranging system and GPS. GPS grew out of the Transit (Naval Navigation Satellite System), the Timation satellite program, and USAF Project 621B (history). ↩

A radar signal was first bounced off the Moon in 1946 (details, p 25), but the distance accuracy was only ±1000 miles. The radar return from the spacecraft would be much smaller due to its size. ↩

There's a complicated history leading up to the Apollo ranging system. Development of Radar (RAdio Detection And Ranging) started in the 1920s. Radar became critically important in World War II, and to counteract jamming, spreadspectrum ideas were applied. The WHYN missile ranging system (1946) used correlation detection to determine the phase difference and thus range. The Federal Telecommunications Laboratories investigated noiselike signals for communication in 1948. This unusual system stored noise values optically on a rotating disk; curiously, the original source of random numbers was the Manhattan telephone directory. The NOMAC (NOise Modulation And Correlation) system (1952) explored thermal noise as a carrier for communication. The CODORAC (either COded DOppler Ranging And Command or COded Doppler RAdar Command) system at JPL (1952) used similar electronics and became the basis for the Deep Space Instrumentation Facility. It introduced a phaselocked loop (PLL) to cancel out Doppler variations, as well as linearfeedback shift register sequences for "pseudonoise". JPL's continuing research led to the ranging system used for Apollo, as well as the Space Ground Link Subsystem (SGLS) (1966), which is still used by the US Air Force. See The Origins of SpreadSpectrum Communications for more. ↩

One complication is that the spacecraft is moving very rapidly during the ranging process, up to 10,000 meters per second. This creates two problems. First, the distance measurement will be out of date by the time it is completed. Second, the bit alignment is shifting many times per second, which makes it hard to find the correlation. The solution was to use separate clocks for the sending and receiving circuitry. The receiver clock was locked onto the signal received from the spacecraft. (Due to Doppler shift, this frequency would be slightly different.) By generating the codes from this clock, the codes stayed exactly aligned even as the spacecraft moved. Integrating the difference between the two clocks provided the change in distance since the start of the measurement. Thus, the computed range remained locked to the distance at the start of the measurement, and the Doppler data gave the incremental distance change. Combining these provided the correct range, continuously updated. ↩

The pseudorandom sequence must be carefully designed so nonmatches can be clearly distinguished from matches, even in the presence of noise. Specifically, misalignments should have as many mismatched bits as possible. The LFSR and Legendre sequences provided this property. In contrast, the sequence 0000011111 would be a bad choice, since if it is shifted by 1, most of the bits still match. Moreover, the number of mismatches should be constant, regardless of the shift. Otherwise, the correlation may match against a local peak rather than the correct shift.
For more about the mathematics of correlating codes, see Sequences with Small Correlation ↩

The majority function
maj(A,B,C)
matches theA
value 75% of the time (and likewise forB
orC
), allowing the correlation to be detected. (In contrast,A⊕B⊕C
would be a bad choice since it only matchesA
50% of the time, so the correlation is essentially random.) For a quick analysis of the majority function, considermaj(A,B,C)
whereA
is 1 and the other inputs have four possibilities:maj(1,0,0)=0
,maj(1,0,1)=1
, maj(1,1,0)=1, and maj(1,1,1)=1
. The result matchesa
for all except the first case, i.e. 75% of the time. (Ifa
is 0, the analysis is similar.) The majority function can be expressed in Boolean logic asA·B+B·C+A·C
, i.e. true if any two inputs are set. ↩ 
The idea of the Legendre sequence is that some numbers have an integer "square root" modulo 11 (technically a quadratic residue), and some do not. For instance, 5^{2} = 25 ≡ 3 modulo 11, so in a sense 5 is the square root of 3. If you take the numbers 0 through 10 and assign 1 if the number has a "square root" and 0 otherwise, you get the X codes. (The ranging sequence is slightly different from the mathematical Legendre sequence, which uses 1 for a "quadratic nonresidue" instead of 0.) ↩

The modulo equations were solved using the Chinese remainder theorem, developed by the Chinese mathematician Sunzi Suanjing in the third century. The ranging system used precomputed numbers that canceled out for all except one subcode. For instance, 992124 is congruent to 1 modulo 11, but congruent to 0 modulo 31, 63, and 127. Multiplying this number by the X offset provides the X subcode's contribution to the range.
The Chinese remainder theorem constants are
992124 ≡ 1 (mod 11) for the X subcode
1408176 ≡ 1 (mod 31) for the A subcode
736219 ≡ 1 (mod 63) for the B subcode
2320164 ≡ 1 (mod 127) for the C subcode
These numbers are ≡ 0 modulo the other cases. Thus, the total offset T = 992124×X + 1408176×A + 736219×B + 2320164×C (mod 5,456,682).The numbers can be obtained by a straightforward algorithm, described in Appendix E of the NASA document. The numbers were hardcoded into the ranging hardware by a "Chinese Number Generator", logic gates that provided the numbers in serial form for serial addition. ↩

The Honeywell DDP116 minicomputer (1965) also used TPac modules. Honeywell acquired Computer Control Co., the manufacturer of TPacs, in 1966 to expand their digital capability. The earlier Honeywell DDP19 was a curious computer since it used 19bit words; it was built with SPac modules. The later ÂµPac modules used integrated circuits in place of transistors. ↩

Note that the Doppler system can only measure the spacecraft's velocity towards or away from Earth. Perpendicular motion would not show up. ↩

I haven't been able to find any explanation for the specific 240/221 frequency ratio between the transmitted and received frequencies. The two frequencies needed to be different so the transmitted signal doesn't overpower the received frequency. The ratio should be fairly close to 1, though, so the system can be optimized for a particular frequency band. The ratio should be reasonably small integers so frequency multipliers can be used. But the mystery to me is why 240/221 instead of, say, 12/11, which is almost the same but much easier to generate. My current theory is that the larger ratio avoided collisions between harmonics that would otherwise occur. (e.g. 12×f1 = 11×f2, which might distort the received signal?) ↩

The code delay and the Doppler shift aren't independent, but are really two aspects of the same thing. For example, suppose the spacecraft is moving away at 15 meters/second. This will stretch the radio waves, decreasing the frequency. The 1 MHz pseudorandom signal transmitted to the spacecraft will return with each 1microsecond interval stretched by 0.1 picoseconds.13 In 10 seconds, the ranging system will transmit 10 million pulses, so the Doppler stretching will cause the pulse train to be 1 microsecond longer, one pulse. The other way of looking at this is that after 10 seconds, the spacecraft will be 150 meters further away, increasing the roundtrip signal delay by 1 microsecond. The signal delay from the Doppler shift is the same as the signal delay from the change in range because they are both caused by the spacecraft's motion. ↩

Note that the signal transmitted from the ground will be Dopplershifted when received by the spacecraft, and then the spacecraft's signal will be Dopplershifted again when received on Earth, so the total Doppler shift is doubled. ↩

The block diagram below shows the main components of the transponder. It consists of two phasemodulation transmitter/receivers (for redundancy). At the bottom is the FM transmitter for television signals (not redundant). The VCO (voltagecontrolled oscillator) is phaselocked to the input signal, but multiplies the frequency by 240/221. This multiplication is done through several frequency multipliers and mixers. The ranging signal is extracted, phasemodulated at the new frequency, and sent to the antenna for transmission back to Earth.
Block diagram of the transponder. (Click for a larger version.) 
The transponder multiplies the received carrier frequency by 240/221. The Command Module used an uplink frequency of 2106.4 MHz, multiplied by 240/221 for the downlink frequency of 2287.5 MHz, although this can vary by ±120 kHz due to Doppler shift. The Lunar Module and Saturn rocket used an uplink carrier of 2101.8 MHz, multiplied by 240/221 for the downlink carrier of 2282.5 MHz.
The 240/221 ratio was obtained by a complex process of mixers and frequency multipliers, as shown in the block diagram above. A voltagecontrolled oscillator (VCO) in the transponder, ran at a frequency of approximately 19.0625 MHz and formed part of the phaselocked loop. The VCO signal was multiplied by 108 (12×9 in two steps) and mixed with the uplink signal received from Earth. The mixer yielded a signal whose frequency was the difference between the ground signal and the multiplied VCO signal, approximately 47.65625 MHz. A second mixer mixed this signal with two times the VCO frequency, yielding a signal at the difference frequency 9.53125 MHz. The VCO was then phaselocked to this signal to produce an output at twice its frequency, yielding the 19.0625 MHz VCO frequency. Putting this all into an equation:
(Uplink  108×VCO  2×VCO)×2 = VCO
which simplifies to VCO frequency = Uplink frequency * 2 / 221.Meanwhile, the transponder's transmitter multiplied the VCO frequency by 4 to yield a 76.25 MHz carrier. This was multiplied by 30 to yield the 2287.5 MHz downlink frequency. In other words, the VCO frequency was multiplied by 120 to transmit, so the transmitting frequency is 240/221 × Uplink frequency. Thus, the 240/221 frequency ratio is established by multiple frequency multipliers and mixers.
But how was frequency multiplication implemented? Based on other Apollo circuits, I think the signal was fed into a step recovery diode, a special diode with very fast switching. This turned each input cycle into a sharp pulse, full of harmonics at multiples of the input frequency. A resonant network concentrated the energy at the desired harmonic, and then a filter removed unwanted frequency sidebands. The frequency of the resulting signal was at the desired multiple of the input signal. This process is described in HewlettPackard application note 920 (1968). ↩

The ground stations used Univac 642B computers, a 30bit computer with 32kilowords of magnetic core storage. The computer was designed for military realtime applications. This computer was a key component of the Naval Tactical Data System, a groundbreaking 1960s system to manage combat information on US Navy ships.
The Univac 624B computer. From Apollo Unified SBand System. 
For details on the Sband system and ground stations, see Apollo Unified SBand System. See A study of the JPL Mark I ranging subsystem for a detailed discussion of the ranging hardware. ↩