8 ms·

Awesome read! It's great to see someone faced with tech challenge and not back down. We need more of that. For anyone interested, here are some links to the de

Awesome read! It's great to see someone faced with tech challenge and not back down. We need more of that. For anyone interested, here are some links to the details of error-correcting codes (ECC) used on CD-ROM: - http://www.usna.edu/Users/math/wdj/_files/documents/reed-sol.htm http://www.usna.edu/Users/math/wdj/_files/documents/reed-sol... - http://www.multimediadirector.com/help/technology/cd-rom/cdrom_spec.htm http://www.multimediadirector.com/help/technology/cd-rom/cdr... - http://bat8.inria.fr/~lang/hotlist/cdrom/Documents/tech-summary.html http://bat8.inria.fr/~lang/hotlist/cdrom/Documents/tech-summ... But I think CDDA possibly uses different (less) ECC... so info in links might not be 100% relevant. It's a shame this cool tech is not being used anymore. As an information theorist, I used to be able to point to optical disks as an application of my field, and be like "see all that math is useful for something," but now I don't have anything shiny to point to anymore :(

dylan604 8y ago
While it might not be shiny, could you not point to the math involved in encryption used in day to day usage like HTTPS, OTR, cryptocurrencies, etc? ECC is still used in RAM, and bitwise math is still used in RAID arrays. Again, not shiny, but still valid examples.
taneq 8y ago
> As an information theorist, I used to be able to point to optical disks as an application of my field, and be like "see all that math is useful for something," but now I don't have anything shiny to point to anymore :( Surely there's some forward error correction built into, well, pretty much any physical media these days? I can't imagine BluRay would need less of it than a CD.
- Cthulhu_ 8y ago
  I'm sure pretty much all storage media (SSD's and such) have it, as well as internet protocols and digital media (now that having storage locally is becoming less cool)
  - dooglius 8y ago
    High-bandwidth Ethernet uses forward error correction, but I'm not aware of any higher-than-physical internet protocols that do, unless you count erasure codes a la QUIC
    - waterhouse 8y ago
      IP, TCP, and UDP all have checksums, though (a) that's less powerful than error correction and (b) the above are weaker than the Ethernet checksum (Ethernet is 32 bits while the others are 16 bits, and also I think these three are all addition- or XOR-based instead of a polynomial CRC).
kroeckx 8y ago
A CDDA has 2352 bytes of main data and 96 byte of sub-channel data per sector, so a total of 2448 bytes per sector. A sector is made up of 98 sub-frames. Each such sub-frame has 24 bytes of main data, 4 bytes of C1 error correction and 4 bytes of C2 error correction, and 1 "byte" of sub-channel data. The first 2 sub-frames have a special pattern in the sub channel data to recognize the start of the sector, leaving 96 bytes of sub-channel data available for other things. The error correction only covers the main data, the sub channel data just has a CRC. The standard API to talk to the CD-ROM does not have a way to get the C1 and C2 error correction data. There is only a way to get 1 bit for each of the 2352 main data bytes after the C2 error correction to indicate that there was an error with it or not. But getting that data doesn't actually seem to be useful on the drives I tested it with, they all seem to have weird firmwares.
- voltagex_ 8y ago
  I think you need a certain Plextor drive. https://github.com/saramibreak/DiscImageCreator https://github.com/saramibreak/DiscImageCreator is kinda the gold standard for this.
zkms 8y ago
> As an information theorist, I used to be able to point to optical disks as an application of my field, and be like "see all that math is useful for something," but now I don't have anything shiny to point to anymore I strongly disagree, there's many shiny things you can point towards. Point to a smartphone (and also the relevant sections of the LTE/HSPA/UMTS/WCDMA/GSM / 802.11 standards documents); there's a literal panoply of coding/error-correction maths that's crucial to every single one of those standards. You can actually go to the ETSI website and find the LTE standard and get free PDFs with the exact parameters of all the codes they use, in enough detail to reimplement them yourself. In those standards, there's all sorts of lovely little state machines for coping with errors, like LTE's "HARQ loop" where your phone will tell the cell base station that it didn't receive a chunk of data correctly; at which point the tower will resend a differently punctured version of the chunk of data, and your phone's modem will try to soft-decode the data with both versions to work with. Oh, and that exchange (including processing on both ends and radio transmission latency) takes under 10 milliseconds to complete -- the standard places an exigent and strict deadline on how long your phone has to respond with its acknowledgement/request. Also hard-drive platters are extremely shiny (more so than optical disks) and those also use error-correcting codes, as do SSDs. Did you know that bit cells in modern SSDs are so small that the number of electrons it takes to affect a measurable voltage difference for the sense amplifiers is less than 100 (https://twitter.com/whitequark/status/684018629256605696 https://twitter.com/whitequark/status/684018629256605696)? All your data lives in those differences of tens of electrons per bit cell; no wonder there's ECC machinery hard at work in SSDs!
- exikyut 8y ago
  > ...like LTE's "HARQ loop" where your phone will tell the cell base station that it didn't receive a chunk of data correctly; at which point the tower will resend a differently punctured version of the chunk of data, and your phone's modem will try to soft-decode the data with both versions to work with. Cooool. I googled "HARQ loop" and because I visit HN so much the first result was https://news.ycombinator.com/item?id=11151232 https://news.ycombinator.com/item?id=11151232, so I learned that the data-processing portion (where the decode attempt is retried) must complete within 3ms! I've been wondering for some time about good (bandwidth-efficient) ways to do error correction/recovery in the area of general-purpose high-efficiency byte transports, and just in case, wanted to put this here in case you're/anyone is interested. How good would it be to throw TCP's "flood of ACKs" out the window and instead compare frame checksums (is CRC32 good?) of every say 32 frames, and send a bitmask (in this case 8 bytes) every n frames noting which were correct and which aren't? This would send ~32 times less data (and I just learned a TCP ACK is approx. 74 bytes! https://stackoverflow.com/questions/5543326/what-is-the-total-length-of-pure-tcp-ack-sent-over-ethernet https://stackoverflow.com/questions/5543326/what-is-the-tota...) (My interest/focus is within the domain of good ideas lacking widepread implementation/uptake. I've found that these always seem to be hiding in the woodwork.)
pmarreck 8y ago
> As an information theorist, I used to be able to point to optical disks as an application of my field, and be like "see all that math is useful for something," but now I don't have anything shiny to point to anymore QR codes, dude. ;)

dylan604 8y ago

While it might not be shiny, could you not point to the math involved in encryption used in day to day usage like HTTPS, OTR, cryptocurrencies, etc? ECC is still used in RAM, and bitwise math is still used in RAID arrays. Again, not shiny, but still valid examples.

taneq 8y ago

> As an information theorist, I used to be able to point to optical disks as an application of my field, and be like "see all that math is useful for something," but now I don't have anything shiny to point to anymore :( Surely there's some forward error correction built into, well, pretty much any physical media these days? I can't imagine BluRay would need less of it than a CD.

Cthulhu_ 8y ago
I'm sure pretty much all storage media (SSD's and such) have it, as well as internet protocols and digital media (now that having storage locally is becoming less cool)
- dooglius 8y ago
  High-bandwidth Ethernet uses forward error correction, but I'm not aware of any higher-than-physical internet protocols that do, unless you count erasure codes a la QUIC
  - waterhouse 8y ago
    IP, TCP, and UDP all have checksums, though (a) that's less powerful than error correction and (b) the above are weaker than the Ethernet checksum (Ethernet is 32 bits while the others are 16 bits, and also I think these three are all addition- or XOR-based instead of a polynomial CRC).

kroeckx 8y ago

A CDDA has 2352 bytes of main data and 96 byte of sub-channel data per sector, so a total of 2448 bytes per sector. A sector is made up of 98 sub-frames. Each such sub-frame has 24 bytes of main data, 4 bytes of C1 error correction and 4 bytes of C2 error correction, and 1 "byte" of sub-channel data. The first 2 sub-frames have a special pattern in the sub channel data to recognize the start of the sector, leaving 96 bytes of sub-channel data available for other things. The error correction only covers the main data, the sub channel data just has a CRC. The standard API to talk to the CD-ROM does not have a way to get the C1 and C2 error correction data. There is only a way to get 1 bit for each of the 2352 main data bytes after the C2 error correction to indicate that there was an error with it or not. But getting that data doesn't actually seem to be useful on the drives I tested it with, they all seem to have weird firmwares.

voltagex_ 8y ago
I think you need a certain Plextor drive. https://github.com/saramibreak/DiscImageCreator https://github.com/saramibreak/DiscImageCreator is kinda the gold standard for this.

zkms 8y ago

> As an information theorist, I used to be able to point to optical disks as an application of my field, and be like "see all that math is useful for something," but now I don't have anything shiny to point to anymore I strongly disagree, there's many shiny things you can point towards. Point to a smartphone (and also the relevant sections of the LTE/HSPA/UMTS/WCDMA/GSM / 802.11 standards documents); there's a literal panoply of coding/error-correction maths that's crucial to every single one of those standards. You can actually go to the ETSI website and find the LTE standard and get free PDFs with the exact parameters of all the codes they use, in enough detail to reimplement them yourself. In those standards, there's all sorts of lovely little state machines for coping with errors, like LTE's "HARQ loop" where your phone will tell the cell base station that it didn't receive a chunk of data correctly; at which point the tower will resend a differently punctured version of the chunk of data, and your phone's modem will try to soft-decode the data with both versions to work with. Oh, and that exchange (including processing on both ends and radio transmission latency) takes under 10 milliseconds to complete -- the standard places an exigent and strict deadline on how long your phone has to respond with its acknowledgement/request. Also hard-drive platters are extremely shiny (more so than optical disks) and those also use error-correcting codes, as do SSDs. Did you know that bit cells in modern SSDs are so small that the number of electrons it takes to affect a measurable voltage difference for the sense amplifiers is less than 100 (https://twitter.com/whitequark/status/684018629256605696 https://twitter.com/whitequark/status/684018629256605696)? All your data lives in those differences of tens of electrons per bit cell; no wonder there's ECC machinery hard at work in SSDs!

exikyut 8y ago
> ...like LTE's "HARQ loop" where your phone will tell the cell base station that it didn't receive a chunk of data correctly; at which point the tower will resend a differently punctured version of the chunk of data, and your phone's modem will try to soft-decode the data with both versions to work with. Cooool. I googled "HARQ loop" and because I visit HN so much the first result was https://news.ycombinator.com/item?id=11151232 https://news.ycombinator.com/item?id=11151232, so I learned that the data-processing portion (where the decode attempt is retried) must complete within 3ms! I've been wondering for some time about good (bandwidth-efficient) ways to do error correction/recovery in the area of general-purpose high-efficiency byte transports, and just in case, wanted to put this here in case you're/anyone is interested. How good would it be to throw TCP's "flood of ACKs" out the window and instead compare frame checksums (is CRC32 good?) of every say 32 frames, and send a bitmask (in this case 8 bytes) every n frames noting which were correct and which aren't? This would send ~32 times less data (and I just learned a TCP ACK is approx. 74 bytes! https://stackoverflow.com/questions/5543326/what-is-the-total-length-of-pure-tcp-ack-sent-over-ethernet https://stackoverflow.com/questions/5543326/what-is-the-tota...) (My interest/focus is within the domain of good ideas lacking widepread implementation/uptake. I've found that these always seem to be hiding in the woodwork.)

pmarreck 8y ago