1
$\begingroup$

The now-famous answer to How is stacking oranges in 24 dimensions related to receiving and decoding signals from the Voyagers? is worth stopping now here and going back and reading first.

Okay welcome back! @NgPh's comment under the question links to Channel Coding: The Road to Channel Capacity which is also very much worth reading. It says:

E. Reed-Solomon code implementations

The first major application of RS codes was as outer codes in concatenated coding systems for deep-space communications. For the 1977 Voyager mission, the Jet Propulsion Laboratory (JPL) used a (255, 223, 33), 16-error-correcting RS code over $\mathbb{F}_{256}$ as an outer code, with a rate-1/2, 64-state convolutional inner code (see also Section IV-D). The RS decoder used special-purpose hardware for decoding, and was capable of running up to about 1 Mb/s [27]. This concatenated convolutional/RS coding system became a NASA standard.

1980 saw the first major commercial application of RS codes in the compact disc (CD) standard. This system used two short RS codes over $\mathbb{F}_{256}$, namely (32, 28, 5) and (28, 24, 5) RS codes, and operated at bit rates of the order of 4 Mb/s [28]. All subsequent audio and video magnetic storage systems have used RS codes for error correction, nowadays at much higher rates.

[...] Linkabit Corp. was founded by Irwin Jacobs, Len Kleinrock, and Andy Viterbi in 1968 as a consulting company. In 1969, Jerry Heller was hired as Linkabit’s first full-time employee. Shortly thereafter, Linkabit built a prototype 64-state Viterbi algorithm decoder (“a big monster filling a rack” [60]), capable of running at 2 Mb/s [61].

  • [27]:R. W. McEliece and L. Swanson, “Reed-Solomon codes and the exploration of the solar system,” in Reed-Solomon Codes and Their Applications (S. B. Wicker and V. K. Bhargava, eds.), pp. 25–40. Piscataway, NJ: IEEE Press, 1994.
  • [28]:K. A. S. Immink, “Reed-Solomon codes and the compact disc,” in Reed-Solomon Codes and Their Applications (S. B. Wicker and V. K. Bhargava, eds.), pp. 41–59. Piscataway, NJ: IEEE Press, 1994.
  • [60]:D. Morton, “Andrew Viterbi, electrical engineer: An oral history,” IEEE History Center, Rutgers U., New Brunswick, NJ, Oct. 1999
  • [61]:J. A. Heller and I. M. Jacobs, “Viterbi decoding for satellite and space communication,” IEEE Trans. Commun. Tech., vol. COM–19, pp. 835–848, Oct. 1971.

But sources quoted in How is stacking oranges in 24 dimensions related to receiving and decoding signals from the Voyagers? and in comments below the question and the answer suggest Voyager used a Golay code, and the term Hamming is thrown around a lot as well.

So let's nail this down:

Question: Did the Voyager spacecraft use a Golay, a Reed-Solomon and/or a Hamming code for data transmission encoding for error correction?

$\endgroup$
3
  • 1
    $\begingroup$ In Error Correction Codes, it is always the decoder's complexity that is limiting. The encoder can be typically implemented with a few shift registers and binary adders. It could well be that Golay and RS codes were never use with Voyager in the direction of Earth to Spacecrafts. $\endgroup$
    – Ng Ph
    Jul 10 at 19:31
  • $\begingroup$ @NgPh yes, there's an inherent asymmetry in the link budgets for the two directions which is the ground transmitter is 10³ and in some cases 10⁴ times more powerful than the deep space probe's transmitter, so the S/N can be much better, lowering the requirements on error detection and correction. $\endgroup$
    – uhoh
    Jul 10 at 23:10
2
$\begingroup$

Question: Did the Voyager spacecraft use a Golay, a Reed-Solomon and/or a Hamming code for data transmission encoding for error correction?

Yes!

And there's a convolutional coder in there as well.


From DESCANSO Design and Performance Summary Series, Voyager Telecommunications, (2002):

The TMU [telemetry modulation unit] encodes the high rate data stream with a convolutional code having constraint length of 7 and a symbol rate equal to twice the bit rate (k=7, r=1/2)

[emphasis added]

The question only mentions block codes but the Voyagers used convolutional encoding. I'm certainly no expert but Brown, C. D. (2002). Elements of Spacecraft Design. United States: American Institute of Aeronautics & Astronautics. suggests that:

Convolutional coding is a newer type of coding that gives better bit error rate reduction than block coding for a given symbol-to-bit ratio. In addition, the encoder is simpler to implement in hardware than a block encoder.

Edit:

Found this table from DESCANSO that suggests Golay or Reed-Solomon encoding is used (w/ convolutional): Voyager Link Configurations

Brown, Elements of Spacecraft Design calls this concatenation:

When even greater error correction is needed it it possible to combine coding schemes, called concatenation. [...] the Reed-Solomon code being the outer layer and convolutional code being the inner layer. The data bits are first convolutionally coded. The output symbol stream from the convolutional coder is Reed-Solomon coded. This scheme provides significant increase in error protection and a significant increase in symbol rate.

Edit 2.0, Should have read the whole thing first, from DESCANSO:

The Golay encoding algorithm used at Jupiter and Saturn required the transmission of one overhead bit for every information bit transmitted (100% overhead). Voyager carried an experimental Reed-Solomon data encoder, expressly for the greater communication range of the Uranus and Neptune phase of the mission. The new Reed-Solomon encoding scheme reduced the overhead to about one bit in five (20% overhead) and reduced the bit-error rate in the output information from 5 × $10^{-3}$ to $10^{-6}$

Not only were Golay and Reed-Solomon ("a special subset of [Bose-Chadhuri-Hocquehem] codes" which are "a powerful class of Hamming code", Brown, Elements of Spacecraft Design) used, convolutional coding was also used.

$\endgroup$
5
  • 1
    $\begingroup$ Interesting! It seems that "symbol rate equal to twice the bit rate" matches "...a 24 bit long code word. From the total of 16 million code words, they only defined 4096 as valid. I.e. 12 Bits carry actual information and another 12 are used for error correction." from the [previous answer](). Does this correspond to "r=1/2" perhaps? I also wonder if the "k=7" corresponds to "3 error correcting, 7 error detecting" as well? $\endgroup$
    – uhoh
    Jul 10 at 2:49
  • 1
    $\begingroup$ @uhoh Yes it does, this is standard notation. $\endgroup$ Jul 10 at 13:56
  • 2
    $\begingroup$ @uhoh, "k=7": k is the so-called constraint length of a Convolutional Code (CC). Basically, it's the memory of the encoder. The higher k, the better, but the decoder complexity also increases correspondingly. NASA sometimes uses k=9, but k=7 is considered the right compromise between performance and complexity. $\endgroup$
    – Ng Ph
    Jul 10 at 19:24
  • 1
    $\begingroup$ This is excellent, thanks for the Edit 2.0! :-) $\endgroup$
    – uhoh
    Jul 10 at 23:13
  • $\begingroup$ this answer links to Voyager Image Data Compression and Block Encoding. I wonder if Figure 3 will be useful here? $\endgroup$
    – uhoh
    Jul 12 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.