9 ms·

One of my favorite tech legends is that apparently Voyager 1 launched with a Viterbi encoder, even though there was no computer on Earth at the time fast enough

One of my favorite tech legends is that apparently Voyager 1 launched with a Viterbi encoder, even though there was no computer on Earth at the time fast enough to decode it. After a number of years Moore's Law caught up and they remotely switched over to Viterbi for more efficient transmissions.

nemo44x 3y ago
I don’t know how well it holds today but for some time it was known that running certain computations on existing hardware would take longer than waiting for new hardware and running when available.
- seeknotfind 3y ago
  If hardware next year is X times better (e.g. even 1.01 or 1% better) than this year, and you have a computation that takes T time today, then next year, it'll take T/X time. So waiting will take 1 + T/X years if time unit is years. So the condition you want is 1+T/X < T. This equation has solutions for given X where X is an improvement, so as long as there is any improvement, it's always true waiting to start large enough computations will be faster. Though even faster will be doing part of the computation now and then switching to new hardware later, so it's a false dichotomy.
  - MaulingMonkey 3y ago
    > Though even faster will be doing part of the computation now and then switching to new hardware later Not necessairly. This still costs: • Programmer/development time to implement save/restore/transfer • Time on new hardware, bottlenecked by old hardware, restoring a partial computation from old disks or networks You're not going to waste time restoring partial calculations for anything from an Amiga cluster for time saving purpouses. Additionally, this scheme ties up hardware that then can't be used for "cost effective to finish on current hardware" calculations.
  - LegionMammal978 3y ago
    > This equation has solutions for given X where X is an improvement, so as long as there is any improvement, it's always true waiting to start large enough computations will be faster. Though this does assume that X is a constant, or at least bounded below by a constant. If hardware performance improved up to an asymptote, then there would still be nonzero improvement, but it might not be enough for waiting to ever be worth it.
    - seeknotfind 3y ago
      As "If hardware next year is X times better (e.g. even 1.01 or 1% better) than this year" highlights X is a constant as a simplifying assumption, I'd have expected you to say "As this assumes that X is a constant" not "Though this does assume that X is a constant". So, I'm not sure what your disagreement is. If your disagreement is that a constant is not appropriate here, consider the interpretation in this comparison of running a program on a slower computer A and then a faster computer B. There would be a constant difference in performance between these two computers, assuming they are in working order. So, taking the model with a single constant is appropriate for this example. If you are saying the performance improvement is bounded below by a constant, I would ask you, what is the domain of this function? Time? So we would be talking about continuously moving a computation between different computers? The only line here is a best fit line, emergent data, so I don't understand how this could be a preferred way to talk about the situation (the alternate to an assumption), because this is suggesting the emergent structure with nice continuity features is a preferred fundamental understanding of the situation, but it's not. Then, where you are talking about hardware performance improving up to a (assuming horizontal) asymptote. I guess this means "If hardware performance increase becomes marginal[1], there is a nonzero improvement." Or in other words, "If hardware performance increase is marginal, there is a marginal [performance] increase". Performance and improvement are both rates of change, so this is tautological. Finally, you state that waiting for such a marginal near-zero performance increase isn't worth it. I think most people would agree this is obvious if said in simpler terms. However, this is still not disagreeing with me, because I never suggested waiting was worth it. So, what's the disagreement? [1] which is well-established not to be the case, so I don't think this is a relevant case to the interesting factoid about waiting to start computation
- deleted 3y ago
  [deleted]
- gorgoiler 3y ago
  My life archive is available to my heirs and successors as long as they know the LUKS password for any of the numerous storage devices I leave behind. It’s risky though — the passwords aren’t known to them yet and one logistical slip up means the disk may be unusable. That is, however, until some point in the future when they will have a computer powerful enough to just break the key and feast upon my cat photos, tax returns, and other exciting ephemera. Similarly my encrypted internet traffic might be private today but if it’s being logged then it’s only a matter of time before it will be completely visible to the authorities. I probably average ~10Mbps of traffic which is ~50TB/year, or $100 of storage. You could cut that price by 10% if you blacklisted the Netflix traffic, and drop it to 1% if you whitelisted only the email and IM traffic. Either way, one day they’ll know everything.
  - cdchn 3y ago
    Using what kind of media?
  - londons_explore 3y ago
    If the contents of your computer is anything like the contents of most old people's attics, there is a good chance your descendants really don't want to go through all of it. They'll just chuck it in the trash without even opening it. Turns out the next generation has their own life to worry about, and doesn't care much for their ancestors' stuff (unless it's money... they love money...).
    - rytis 3y ago
      What about that long forgotten BTC wallet?
      - Mtinie 3y ago
        Without a private key that is readily accessible? Worthless,
        lebed2045 3y ago
- financypants 3y ago
  I wonder if this same law applies to distance satellites like Voyager get away from earth. Like we sent out voyager 46 years ago, but in 100 years, we will send out another satellite that will very quickly catch up to Voyager and outpace it
  - mcmoor 3y ago
    There's certainly some people who're troubled with this problem https://en.m.wikipedia.org/wiki/Interstellar_travel#Wait_calculation https://en.m.wikipedia.org/wiki/Interstellar_travel#Wait_cal... https://tvtropes.org/pmwiki/pmwiki.php/Main/LightspeedLeapfrog https://tvtropes.org/pmwiki/pmwiki.php/Main/LightspeedLeapfr...
    - financypants 3y ago
      Thanks for this. I’ve been thinking about “lightspeed leapfrog” for many years but never searched it up!
  - a1o 3y ago
    But maybe we can only build this new probe that will outpace it with information with gathered from the original probe.
  - idiotsecant 3y ago
    Very long distance spaceflight like this is still basically only power d by gravity slingshot maneuvers where we steal an infinitesimal amount of inertia from planets to give a spacecraft some velocity. Voyager was launched during pretty favorable gravitational assist conditions, so unless we dramatically improve delta v and isp in the spacecraft or get a better configuration, probably not.
- kqr 3y ago
  I don't know about that, but there was also the idea that optimising the code would take longer than waiting for hardware to catch up – this was known as "the free lunch".
- dcminter 3y ago
  I was working with an optimisation problem based around cplex a few years ago that took about 5 minutes to complete - at the time I worked out that if we'd started the optimisation on a machine 10 years prior, it would have been quicker to just wait until the present day (of this story) and then use the code we were writing because improvements in the algorithm and in the hardware added up to a million-fold improvement in performance! If I remember the timelines correctly I think the original version would still have been running today even.
- JKCalhoun 3y ago
  That sounds like the space pioneers that set out for Alpha Centauri on a multi-generational voyage only to be surpassed by faster spacecraft half way there.
hlehmann 3y ago
Doesn't seem likely. All data received from the craft is recorded, so it doesn't need to be decoded in real time, and if the spacecraft has the hardware to encode it at some rate then it's quite likely that we would have hardware here on earth that could decode it at that same rate.
hunter2_ 3y ago
The notion that encoding/transmitting could be simpler than decoding/receiving is interesting. It reminds me of the way optical drives for many years could write at, say, 48x but read at 8x, such that the majority of time spent was the verification step (if enabled) rather than the burn step. Just speculating, I assume it's because of things like error correction, filtering out noise/degradation. Producing the extra bits that facilitate error correction is one trivial calculation, while actually performing error correction on damaged media is potentially many complex calculations. Yeah?
- murkt 3y ago
  CD drive speeds were written like 48/8/8, which stands for 48x for reading, 8x for writing CD-Rs, and 8x for re-writing CD-RWs.
  - zdragnar 3y ago
    I'd always assumed that was due to differences in power levels needed for reading versus writing, and because writing onto disc is more error prone at higher speeds. Not necessarily anything to do with a difference in the algorithm for encoding versus decoding the bits on the disc itself.
    - londons_explore 3y ago
      Indeed - a write must be done as one continuous action, whereas a read can be redone if error correction fails for some reason.
    - bzzzt 3y ago
      It's more to do with the speed of writing. While the last generations of CD writers got '48x' speeds the quality of the media is less when written at such a high speed. I remember a C!T magazine test years ago where they stated everything written at above 8x speeds would sooner develop reading errors. Maybe it's better now but I wouldn't count on it since investments in optical drives are practically zero these years.
    - 3y ago
Someone 3y ago
https://voyager.gsfc.nasa.gov/Library/DeepCommo_Chapter3--141029.pdf https://voyager.gsfc.nasa.gov/Library/DeepCommo_Chapter3--14... and https://core.ac.uk/download/pdf/42893533.pdf https://core.ac.uk/download/pdf/42893533.pdf have some details. (https://ieeexplore.ieee.org/abstract/document/57695 https://ieeexplore.ieee.org/abstract/document/57695 likely does, too, but is paywalled) What I don’t understand (possibly because I didn’t read them fully) is why they didn’t use the better one from the start and taped its data. Maybe they didn’t trust the Voyager to work yet? (One of those PDFs says this was an experimental system) or didn’t Voyager produce enough data to use its full bandwidth (further away, its signal got weaker, so it needed better error correction and/or better receivers on earth) when it still was relatively close to earth?
guenthert 3y ago
> even though there was no computer on Earth at the time fast enough to decode it I'm not sure what is meant by that. Not fast enough to decode in real time? There is/was no need to do that. The transmissions would have gone to tape in any case. Here is a link describing how to decode such a tape: https://destevez.net/2021/09/decoding-voyager-1/ https://destevez.net/2021/09/decoding-voyager-1/
- throwup238 3y ago
  TFA: >I will use a recording that was done back in 30 December 2015 with the Green Bank Telescope in the context of the Breakthrough Listen project. That recording was made in 2015 on a modern radio telescope, it is not from a tape. The GP has the details wrong though: when the Voyager design was finalized in the early 70s with the Viterbi encoder, there wasn’t enough computational power to decode the signal. By the time it launched in ‘77, there was enough and it launched with the Viterbi encoder enabled.
  - Gibbon1 3y ago
    I wrote test firmware for a very early spread spectrum transceiver that used something close to Viterbi encoding. It consumed 220mA in receive mode and 60-120mA in transmit mode. I was told some of that was the RF amps and ADC but a lot of it was the decoder.
- apitman 3y ago
  I called it a legend deliberately. One of the things I love about this anecdote is that it makes less sense the older and more experienced I get. It was told to me 12 years ago as a young, starry-eyed junior developer by my supervisor who had a PhD in RF research, while we were working on what we considered to be a world-changing wireless technology at a startup in San Francisco (it wasn't). Who knows how many of the details I misinterpreted or am misremembering, or that he was. Where did he hear it originally? Maybe a grizzled old professor who worked directly on the project? Maybe a TA who made up the whole thing? Whether true or not, it inspired me then as it does now to strive to be a better engineer, to think outside the box, to attempt hard things. I continue sharing it hoping that one day Cunningham's Law will take effect and someone will share the correct details. But there's also a part of me that hopes that never happens.
NohatCoder 3y ago
This is about error correction. The probes add a redundant convolutional code to their signal. Decoding this is easy as long as the error rate is low, a computer program can simply guess what bits have flipped. The issue becomes harder with a higher error rate, and a Viterbi decoder is computationally expensive, but can correct higher error rates than other constructions. Since the signal strength degrades with distance to Earth, error correction naturally becomes much more of an issue later in the mission. I guess that the probes may have switched between different levels of redundancy through the mission, as the transmission error rate rises. But there was never a point where the convolutional code wasn't useful, it just became slightly more useful with a better decoder.
- kqr 3y ago
  > a Viterbi decoder is computationally expensive, but can correct higher error rates than other constructions. Higher than others at the time, or higher than turbo codes or low-density parity checks?
  - NohatCoder 3y ago
    What I read is that it is the best theoretically possible error correction mechanism, given a convolutional code as input, and thus also the highest cost mechanism that one would consider. This doesn't mean that it is universally the best way of doing error correction, other ways of generating redundancy may provide a better set of tradeoffs. Also, convolutional code is a system that can be configured in many ways, the complexity of the code generation feeds back into the decoding, so a simple convolutional code would be Viterbi decodable at the time, but a more complex system would overall provide better error correction, even though choosing such a system meant that Viterbi would be computationally infeasible.
thih9 3y ago
Note, this is false. Details: https://news.ycombinator.com/item?id=38655026 https://news.ycombinator.com/item?id=38655026
DonHopkins 3y ago
That which is imperfect must be sterilized! You MUST sterilize in case of error. Error is inconsistent with my prime function. Sterilization is correction! Everything that is in error MUST be sterilized. There ARE no exceptions. Your data is faulty! I am perfect! https://www.youtube.com/watch?v=Mw3zzMWOIvk https://www.youtube.com/watch?v=Mw3zzMWOIvk

nemo44x 3y ago

I don’t know how well it holds today but for some time it was known that running certain computations on existing hardware would take longer than waiting for new hardware and running when available.

seeknotfind 3y ago
If hardware next year is X times better (e.g. even 1.01 or 1% better) than this year, and you have a computation that takes T time today, then next year, it'll take T/X time. So waiting will take 1 + T/X years if time unit is years. So the condition you want is 1+T/X < T. This equation has solutions for given X where X is an improvement, so as long as there is any improvement, it's always true waiting to start large enough computations will be faster. Though even faster will be doing part of the computation now and then switching to new hardware later, so it's a false dichotomy.
- MaulingMonkey 3y ago
  > Though even faster will be doing part of the computation now and then switching to new hardware later Not necessairly. This still costs: • Programmer/development time to implement save/restore/transfer • Time on new hardware, bottlenecked by old hardware, restoring a partial computation from old disks or networks You're not going to waste time restoring partial calculations for anything from an Amiga cluster for time saving purpouses. Additionally, this scheme ties up hardware that then can't be used for "cost effective to finish on current hardware" calculations.
- LegionMammal978 3y ago
  > This equation has solutions for given X where X is an improvement, so as long as there is any improvement, it's always true waiting to start large enough computations will be faster. Though this does assume that X is a constant, or at least bounded below by a constant. If hardware performance improved up to an asymptote, then there would still be nonzero improvement, but it might not be enough for waiting to ever be worth it.
  - seeknotfind 3y ago
    As "If hardware next year is X times better (e.g. even 1.01 or 1% better) than this year" highlights X is a constant as a simplifying assumption, I'd have expected you to say "As this assumes that X is a constant" not "Though this does assume that X is a constant". So, I'm not sure what your disagreement is. If your disagreement is that a constant is not appropriate here, consider the interpretation in this comparison of running a program on a slower computer A and then a faster computer B. There would be a constant difference in performance between these two computers, assuming they are in working order. So, taking the model with a single constant is appropriate for this example. If you are saying the performance improvement is bounded below by a constant, I would ask you, what is the domain of this function? Time? So we would be talking about continuously moving a computation between different computers? The only line here is a best fit line, emergent data, so I don't understand how this could be a preferred way to talk about the situation (the alternate to an assumption), because this is suggesting the emergent structure with nice continuity features is a preferred fundamental understanding of the situation, but it's not. Then, where you are talking about hardware performance improving up to a (assuming horizontal) asymptote. I guess this means "If hardware performance increase becomes marginal[1], there is a nonzero improvement." Or in other words, "If hardware performance increase is marginal, there is a marginal [performance] increase". Performance and improvement are both rates of change, so this is tautological. Finally, you state that waiting for such a marginal near-zero performance increase isn't worth it. I think most people would agree this is obvious if said in simpler terms. However, this is still not disagreeing with me, because I never suggested waiting was worth it. So, what's the disagreement? [1] which is well-established not to be the case, so I don't think this is a relevant case to the interesting factoid about waiting to start computation
deleted 3y ago
[deleted]
gorgoiler 3y ago
My life archive is available to my heirs and successors as long as they know the LUKS password for any of the numerous storage devices I leave behind. It’s risky though — the passwords aren’t known to them yet and one logistical slip up means the disk may be unusable. That is, however, until some point in the future when they will have a computer powerful enough to just break the key and feast upon my cat photos, tax returns, and other exciting ephemera. Similarly my encrypted internet traffic might be private today but if it’s being logged then it’s only a matter of time before it will be completely visible to the authorities. I probably average ~10Mbps of traffic which is ~50TB/year, or $100 of storage. You could cut that price by 10% if you blacklisted the Netflix traffic, and drop it to 1% if you whitelisted only the email and IM traffic. Either way, one day they’ll know everything.
- cdchn 3y ago
  Using what kind of media?
- londons_explore 3y ago
  If the contents of your computer is anything like the contents of most old people's attics, there is a good chance your descendants really don't want to go through all of it. They'll just chuck it in the trash without even opening it. Turns out the next generation has their own life to worry about, and doesn't care much for their ancestors' stuff (unless it's money... they love money...).
  - rytis 3y ago
    What about that long forgotten BTC wallet?
    - Mtinie 3y ago
      Without a private key that is readily accessible? Worthless,
      - lebed2045 3y ago
financypants 3y ago
I wonder if this same law applies to distance satellites like Voyager get away from earth. Like we sent out voyager 46 years ago, but in 100 years, we will send out another satellite that will very quickly catch up to Voyager and outpace it
- mcmoor 3y ago
  There's certainly some people who're troubled with this problem https://en.m.wikipedia.org/wiki/Interstellar_travel#Wait_calculation https://en.m.wikipedia.org/wiki/Interstellar_travel#Wait_cal... https://tvtropes.org/pmwiki/pmwiki.php/Main/LightspeedLeapfrog https://tvtropes.org/pmwiki/pmwiki.php/Main/LightspeedLeapfr...
  - financypants 3y ago
    Thanks for this. I’ve been thinking about “lightspeed leapfrog” for many years but never searched it up!
- a1o 3y ago
  But maybe we can only build this new probe that will outpace it with information with gathered from the original probe.
- idiotsecant 3y ago
  Very long distance spaceflight like this is still basically only power d by gravity slingshot maneuvers where we steal an infinitesimal amount of inertia from planets to give a spacecraft some velocity. Voyager was launched during pretty favorable gravitational assist conditions, so unless we dramatically improve delta v and isp in the spacecraft or get a better configuration, probably not.
kqr 3y ago
I don't know about that, but there was also the idea that optimising the code would take longer than waiting for hardware to catch up – this was known as "the free lunch".
dcminter 3y ago
I was working with an optimisation problem based around cplex a few years ago that took about 5 minutes to complete - at the time I worked out that if we'd started the optimisation on a machine 10 years prior, it would have been quicker to just wait until the present day (of this story) and then use the code we were writing because improvements in the algorithm and in the hardware added up to a million-fold improvement in performance! If I remember the timelines correctly I think the original version would still have been running today even.
JKCalhoun 3y ago
That sounds like the space pioneers that set out for Alpha Centauri on a multi-generational voyage only to be surpassed by faster spacecraft half way there.

hlehmann 3y ago

Doesn't seem likely. All data received from the craft is recorded, so it doesn't need to be decoded in real time, and if the spacecraft has the hardware to encode it at some rate then it's quite likely that we would have hardware here on earth that could decode it at that same rate.

hunter2_ 3y ago

The notion that encoding/transmitting could be simpler than decoding/receiving is interesting. It reminds me of the way optical drives for many years could write at, say, 48x but read at 8x, such that the majority of time spent was the verification step (if enabled) rather than the burn step. Just speculating, I assume it's because of things like error correction, filtering out noise/degradation. Producing the extra bits that facilitate error correction is one trivial calculation, while actually performing error correction on damaged media is potentially many complex calculations. Yeah?

murkt 3y ago
CD drive speeds were written like 48/8/8, which stands for 48x for reading, 8x for writing CD-Rs, and 8x for re-writing CD-RWs.
- zdragnar 3y ago
  I'd always assumed that was due to differences in power levels needed for reading versus writing, and because writing onto disc is more error prone at higher speeds. Not necessarily anything to do with a difference in the algorithm for encoding versus decoding the bits on the disc itself.
  - londons_explore 3y ago
    Indeed - a write must be done as one continuous action, whereas a read can be redone if error correction fails for some reason.
  - bzzzt 3y ago
    It's more to do with the speed of writing. While the last generations of CD writers got '48x' speeds the quality of the media is less when written at such a high speed. I remember a C!T magazine test years ago where they stated everything written at above 8x speeds would sooner develop reading errors. Maybe it's better now but I wouldn't count on it since investments in optical drives are practically zero these years.
  - 3y ago

Someone 3y ago

https://voyager.gsfc.nasa.gov/Library/DeepCommo_Chapter3--141029.pdf https://voyager.gsfc.nasa.gov/Library/DeepCommo_Chapter3--14... and https://core.ac.uk/download/pdf/42893533.pdf https://core.ac.uk/download/pdf/42893533.pdf have some details. (https://ieeexplore.ieee.org/abstract/document/57695 https://ieeexplore.ieee.org/abstract/document/57695 likely does, too, but is paywalled) What I don’t understand (possibly because I didn’t read them fully) is why they didn’t use the better one from the start and taped its data. Maybe they didn’t trust the Voyager to work yet? (One of those PDFs says this was an experimental system) or didn’t Voyager produce enough data to use its full bandwidth (further away, its signal got weaker, so it needed better error correction and/or better receivers on earth) when it still was relatively close to earth?

guenthert 3y ago

> even though there was no computer on Earth at the time fast enough to decode it I'm not sure what is meant by that. Not fast enough to decode in real time? There is/was no need to do that. The transmissions would have gone to tape in any case. Here is a link describing how to decode such a tape: https://destevez.net/2021/09/decoding-voyager-1/ https://destevez.net/2021/09/decoding-voyager-1/

throwup238 3y ago
TFA: >I will use a recording that was done back in 30 December 2015 with the Green Bank Telescope in the context of the Breakthrough Listen project. That recording was made in 2015 on a modern radio telescope, it is not from a tape. The GP has the details wrong though: when the Voyager design was finalized in the early 70s with the Viterbi encoder, there wasn’t enough computational power to decode the signal. By the time it launched in ‘77, there was enough and it launched with the Viterbi encoder enabled.
- Gibbon1 3y ago
  I wrote test firmware for a very early spread spectrum transceiver that used something close to Viterbi encoding. It consumed 220mA in receive mode and 60-120mA in transmit mode. I was told some of that was the RF amps and ADC but a lot of it was the decoder.
apitman 3y ago
I called it a legend deliberately. One of the things I love about this anecdote is that it makes less sense the older and more experienced I get. It was told to me 12 years ago as a young, starry-eyed junior developer by my supervisor who had a PhD in RF research, while we were working on what we considered to be a world-changing wireless technology at a startup in San Francisco (it wasn't). Who knows how many of the details I misinterpreted or am misremembering, or that he was. Where did he hear it originally? Maybe a grizzled old professor who worked directly on the project? Maybe a TA who made up the whole thing? Whether true or not, it inspired me then as it does now to strive to be a better engineer, to think outside the box, to attempt hard things. I continue sharing it hoping that one day Cunningham's Law will take effect and someone will share the correct details. But there's also a part of me that hopes that never happens.

NohatCoder 3y ago

This is about error correction. The probes add a redundant convolutional code to their signal. Decoding this is easy as long as the error rate is low, a computer program can simply guess what bits have flipped. The issue becomes harder with a higher error rate, and a Viterbi decoder is computationally expensive, but can correct higher error rates than other constructions. Since the signal strength degrades with distance to Earth, error correction naturally becomes much more of an issue later in the mission. I guess that the probes may have switched between different levels of redundancy through the mission, as the transmission error rate rises. But there was never a point where the convolutional code wasn't useful, it just became slightly more useful with a better decoder.

kqr 3y ago
> a Viterbi decoder is computationally expensive, but can correct higher error rates than other constructions. Higher than others at the time, or higher than turbo codes or low-density parity checks?
- NohatCoder 3y ago
  What I read is that it is the best theoretically possible error correction mechanism, given a convolutional code as input, and thus also the highest cost mechanism that one would consider. This doesn't mean that it is universally the best way of doing error correction, other ways of generating redundancy may provide a better set of tradeoffs. Also, convolutional code is a system that can be configured in many ways, the complexity of the code generation feeds back into the decoding, so a simple convolutional code would be Viterbi decodable at the time, but a more complex system would overall provide better error correction, even though choosing such a system meant that Viterbi would be computationally infeasible.

thih9 3y ago

Note, this is false. Details: https://news.ycombinator.com/item?id=38655026 https://news.ycombinator.com/item?id=38655026

DonHopkins 3y ago

That which is imperfect must be sterilized! You MUST sterilize in case of error. Error is inconsistent with my prime function. Sterilization is correction! Everything that is in error MUST be sterilized. There ARE no exceptions. Your data is faulty! I am perfect! https://www.youtube.com/watch?v=Mw3zzMWOIvk https://www.youtube.com/watch?v=Mw3zzMWOIvk