4 ms·

I wonder if re-transmission is the best solution to corrupt blocks. Some students that commuted to school on a train (MIT?) figured out if they transmitted ECC-

I wonder if re-transmission is the best solution to corrupt blocks. Some students that commuted to school on a train (MIT?) figured out if they transmitted ECC-style blocks combined with RAID-style parity blocks they could instead rebuild corrupt data. It all depends on the kind of corruption. Periodic spikes, white noise, blackouts - different problems need different solutions

sgtnoodle 4y ago
This is known as "forward error correction". If the nature of the corruption is known and predictable, then you can design a reasonably efficient scheme to mitigate it. Otherwise, I suspect some amount of acknowledgement and retransmission at the MAC layer or above is a good idea. It really depends on the latency of the link, though, and the probability of corruption. If a round-trip delay is larger than a reasonable window size, and corruption is frequent, then FEC would help a lot. It's the only option for one-way comms such as digital broadcast television.
- jpmattia 4y ago
  > This is known as "forward error correction". Fun factoid: Reed and Solomon were working at MIT Lincoln Laboratory (ie where the OP result is from) when they invented RS codes. ISTR they were also working on satellite comm, in which Lincoln has a long history. [Source: I spent a decade there myself and drank the kool aid.]
  - thehappypm 4y ago
    That’s super cool. Error correcting codes are truly amazing technology.
  - sizzle 4y ago
    Awesome, what are you up to nowadays? Anything interesting brewing you can share?
    - jpmattia 4y ago
      These days, most of my time is spent on video encoding and distribution for fun and profit: https://www.centaurdelivery.com https://www.centaurdelivery.com
- MayeulC 4y ago
  Which is exactly what Wi-Fi does, adjusting the amount of parity data depending on link loss, to keep retransmissions to a minimal.
  - sgtnoodle 4y ago
    Indeed. It's fun to look at the MCS table for something like 802.11ac. a lot of different rates are actually the same underlying modulation, but with varying amounts of overhead from forward error correction. 802.11 data frames also have an acknowledgement at the MAC layer. The radios dynamically ramp up the MCS rate until packets start dropping, then ramp the rate back down.
  - wongarsu 4y ago
    And still, wifi links are among the top sources of packet loss. Without sophisticated forward error correction it would probably be much worse, but it shows that this is not an either-or question. The correct answer is: do both.
- cycomanic 4y ago
  I think communications theorists would argue that retransmitting is essentially an FEC, and likely a suboptimal one for these links. That said, real-world constrains don't always match up with theory, while modern optical communication makes extensive use of FEC (however RS codes are not used much anymore, in long-haul it's LDPC codes) AFAIK FECs for these type of "intermittent" links are very underdeveloped. Moreover, if the probabilities of long outages is too high, one would need a lot of memory for the FEC which becomes difficult to do in real-time processing (remember we need to process at >100Gb/s).
sedatk 4y ago
You must have a retransmission mechanism anyway. You can always implement such mechanisms on top of a retransmitting protocol.
nonameiguess 4y ago
US geointelligence uses error-correcting codes, but beyond that, individual detectors on sensor arrays fail all the time, and you can't go up there to replace them and you don't want to bring down an entire satellite when it still mostly works, so ground processing needs to be robust to missing data anyway. It's fairly straightforward to just interpolate pixels, but the full process is a bit more sophisticated and also involves building overlay layers rating the quality of each pixel, so follow-on processing like object and change detection is able to take into account not just hey, what am I looking at, but also how reliable is each individual part of the scene. To a human looking at the final image, though, you'd never know the difference. I'm assuming most of what this would be used for is imagery collected from space. For whatever reason, other commenters seem to think this is for holding conversations, but it clearly says it's for data from science missions. Even if you were trying to talk to someone on the other end, though, it's rarely that big a deal if part of a word cuts out. That happens all the time with existing ground-based calls or even just two people in a loud room and the human brain knows how to handle it.
Kuinox 4y ago
That error correction, great video of 3blue1brown explaining how one such algorithm works: https://www.youtube.com/watch?v=X8jsijhllIA https://www.youtube.com/watch?v=X8jsijhllIA
pclmulqdq 4y ago
Another comment has pointed this out, but Reed-Solomon coding was invented as a method of forward error correction. It was only applied later to storage systems as an "erasure code" because it can detect and correct extremely long runs of bad bits. Comparatively, it can detect and correct many fewer random bad bits.

sgtnoodle 4y ago

This is known as "forward error correction". If the nature of the corruption is known and predictable, then you can design a reasonably efficient scheme to mitigate it. Otherwise, I suspect some amount of acknowledgement and retransmission at the MAC layer or above is a good idea. It really depends on the latency of the link, though, and the probability of corruption. If a round-trip delay is larger than a reasonable window size, and corruption is frequent, then FEC would help a lot. It's the only option for one-way comms such as digital broadcast television.

jpmattia 4y ago
> This is known as "forward error correction". Fun factoid: Reed and Solomon were working at MIT Lincoln Laboratory (ie where the OP result is from) when they invented RS codes. ISTR they were also working on satellite comm, in which Lincoln has a long history. [Source: I spent a decade there myself and drank the kool aid.]
- thehappypm 4y ago
  That’s super cool. Error correcting codes are truly amazing technology.
- sizzle 4y ago
  Awesome, what are you up to nowadays? Anything interesting brewing you can share?
  - jpmattia 4y ago
    These days, most of my time is spent on video encoding and distribution for fun and profit: https://www.centaurdelivery.com https://www.centaurdelivery.com
MayeulC 4y ago
Which is exactly what Wi-Fi does, adjusting the amount of parity data depending on link loss, to keep retransmissions to a minimal.
- sgtnoodle 4y ago
  Indeed. It's fun to look at the MCS table for something like 802.11ac. a lot of different rates are actually the same underlying modulation, but with varying amounts of overhead from forward error correction. 802.11 data frames also have an acknowledgement at the MAC layer. The radios dynamically ramp up the MCS rate until packets start dropping, then ramp the rate back down.
- wongarsu 4y ago
  And still, wifi links are among the top sources of packet loss. Without sophisticated forward error correction it would probably be much worse, but it shows that this is not an either-or question. The correct answer is: do both.
cycomanic 4y ago
I think communications theorists would argue that retransmitting is essentially an FEC, and likely a suboptimal one for these links. That said, real-world constrains don't always match up with theory, while modern optical communication makes extensive use of FEC (however RS codes are not used much anymore, in long-haul it's LDPC codes) AFAIK FECs for these type of "intermittent" links are very underdeveloped. Moreover, if the probabilities of long outages is too high, one would need a lot of memory for the FEC which becomes difficult to do in real-time processing (remember we need to process at >100Gb/s).

sedatk 4y ago

You must have a retransmission mechanism anyway. You can always implement such mechanisms on top of a retransmitting protocol.

nonameiguess 4y ago

US geointelligence uses error-correcting codes, but beyond that, individual detectors on sensor arrays fail all the time, and you can't go up there to replace them and you don't want to bring down an entire satellite when it still mostly works, so ground processing needs to be robust to missing data anyway. It's fairly straightforward to just interpolate pixels, but the full process is a bit more sophisticated and also involves building overlay layers rating the quality of each pixel, so follow-on processing like object and change detection is able to take into account not just hey, what am I looking at, but also how reliable is each individual part of the scene. To a human looking at the final image, though, you'd never know the difference. I'm assuming most of what this would be used for is imagery collected from space. For whatever reason, other commenters seem to think this is for holding conversations, but it clearly says it's for data from science missions. Even if you were trying to talk to someone on the other end, though, it's rarely that big a deal if part of a word cuts out. That happens all the time with existing ground-based calls or even just two people in a loud room and the human brain knows how to handle it.

Kuinox 4y ago

That error correction, great video of 3blue1brown explaining how one such algorithm works: https://www.youtube.com/watch?v=X8jsijhllIA https://www.youtube.com/watch?v=X8jsijhllIA

pclmulqdq 4y ago

Another comment has pointed this out, but Reed-Solomon coding was invented as a method of forward error correction. It was only applied later to storage systems as an "erasure code" because it can detect and correct extremely long runs of bad bits. Comparatively, it can detect and correct many fewer random bad bits.