4 ms·
> Are there other XOR tricks? Yes, error correction. You have some packets of data a, b, c. Add one additional packet z that is computed as z = a ^ b ^ c. Now
by danhau 6mo ago
> Are there other XOR tricks?
Yes, error correction.
You have some packets of data a, b, c. Add one additional packet z that is computed as z = a ^ b ^ c. Now whenever one of a, b or c gets corrupted or lost, it can be reconstructed by computing the XOR of all the others.
So if b is lost: b = a ^ c ^ z. This works for any packet, but only one. If multiple are lost, this will fail.
There are way better error correction algorithms, but I like the simplicity of this one.
- nsteel 6mo agoAlso to cheaply (area) create multi-port RAMs.
- pjc50 6mo agoHow does that work?
- nsteel 6mo agoIt's similar to RAID schemes but instead of drive failure it's port unavailability. There's a reference at [1] or an FPGA-centric one at [2], but it applies to anywhere where dual/single-port rams are readily available but anything more exotic isn't. [1] Achieving Multi-Port Memory Performance on Single-Port Memory with Coding Techniques - https://arxiv.org/abs/2001.09599 [2] https://people.csail.mit.edu/ml/pubs/fpga12_xor.pdf
- Terr_ 6mo agoSee also: RAID levels that use one disk for parity. Three disks is simplest, but technically you can do more if you trust that only one will go bad at a time. A few months ago, I had a rare occasion of trying to explain them to a relative who had just bought a fancy NAS and wanted help setting it up.
- amelius 6mo agoXOR is also great for storing copyrighted works without liability. a = the bits of some song or movie b = pure noise Store c = a^b. Give b to a friend. Throw away a. Now both you and your friend have a bit vector of pure noise. Together you can produce the copyrighted work. But nobody is liable.
- lelanthran 6mo agoThat's called encryption using a one time pad.
- amelius 6mo agoThat's one way of looking at it. Note that you can easily extend it to multiple people holding multiple keys, so that a=b^c^d^e, etc.
- lelanthran 6mo agoMy point was that encrypting a copyrighted work does not remove the copyright from it; the result is still copyright and not legally redistributable.
- amelius 6mo agoMaybe, but b and c are indistinguishable from pure noise.
- lelanthran 6mo ago> Maybe, but b and c are indistinguishable from pure noise. That's the whole point of encryption.
- morning-coffee 6mo agoRight. But the copyright was violated when you used 'a' to begin with.
- jagged-chisel 6mo agoI think the topic is “evidence of infringement is no longer readily available” not “suddenly, there is no infringement!”
- lelanthran 6mo ago
- throwaway2027 6mo agohttps://en.wikipedia.org/wiki/XOR_linked_list https://en.wikipedia.org/wiki/XOR_linked_list
- direwolf20 6mo agoImportant note: Only if you already know which one was corrupted.
- danhau 6mo agoTrue! Some checksums / parity bits might be needed.