5 ms·

Don't you have to read all the bits first though?

dmurray 5y ago
No, you just have to read the first 3 bits, if the corruption is in those. But yeah, you can't detect a single-bit corruption if you haven't actually read that bit.
- ajb 5y ago
  You can't detect single bit corruption of the encoding without reading that bit. But what you care about is whether the encoding is sufficiently corrupted that you can't decode the original.
- dataflow 5y ago
  What if the corruption is in the last bit? Do you somehow magically know it's not in the first 3 without reading them?
  - cdtwigg 5y ago
    In this formulation I believe the last bit would also be repeated 3 times, and you’d have to read those three bits to detect corruption.
    - dataflow 5y ago
      Yes but how would you know that without reading all 6 bits first?
      - netizen-936824 5y ago
        You wouldn't, as long as the bits are received sequentially. I think the idea is that, depending on where the corruption is, you only need to read up to two bits past the corrupted one
tromp 5y ago
From https://en.wikipedia.org/wiki/Locally_testable_code https://en.wikipedia.org/wiki/Locally_testable_code : "Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) probes. To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits. This implies words of the code must be longer than the input strings by adding some redundancy."
- dataflow 5y ago
  I'm not sure I'm really following how that answers my question unfortunately. Are they assuming O(n) corruptions? Distributed randomly in the string?
mirekrusin 5y ago
No you don’t, you need to read at most 2 bits past corrupted one to detect it.
- dataflow 5y ago
  The question is how do you know which one is corrupted before reading all of them??
  - mirekrusin 5y ago
    You don't need to read 1 million bits to detect 5th being corrupted one, you will know it after reading 3 * 5 = 15 bits.
    - dataflow 5y ago
      Yeah and what if instead of being the 5th bit it was the 1 millionth bit that was corrupted?
      - mirekrusin 5y ago
        For 1 million bits message where millionth bit is corrupted last bit doesn't have to be read, in general in 3 replica coding, reading first 2 is enough if they are the same - reading last one will have no effect.
        dataflow 5y ago
        For heaven's sake... how in the world would you know it's the millionth bit that's corrupted without scanning all 999,999 other bits at least once?!?! Do you data streams always come magically tagged with sentences like "Hey, watch out for bits 999,998-1,000,000, but all my other bits are intact so you can skip them!" or something??! You somehow "know" the error is in the final 3 bits and not in the earlier 999,997 bits because... magic??
        5y ago

No, you just have to read the first 3 bits, if the corruption is in those. But yeah, you can't detect a single-bit corruption if you haven't actually read that bit.

ajb 5y ago
You can't detect single bit corruption of the encoding without reading that bit. But what you care about is whether the encoding is sufficiently corrupted that you can't decode the original.
dataflow 5y ago
What if the corruption is in the last bit? Do you somehow magically know it's not in the first 3 without reading them?
- cdtwigg 5y ago
  In this formulation I believe the last bit would also be repeated 3 times, and you’d have to read those three bits to detect corruption.
  - dataflow 5y ago
    Yes but how would you know that without reading all 6 bits first?
    - netizen-936824 5y ago
      You wouldn't, as long as the bits are received sequentially. I think the idea is that, depending on where the corruption is, you only need to read up to two bits past the corrupted one

tromp 5y ago

From https://en.wikipedia.org/wiki/Locally_testable_code https://en.wikipedia.org/wiki/Locally_testable_code : "Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) probes. To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits. This implies words of the code must be longer than the input strings by adding some redundancy."

dataflow 5y ago
I'm not sure I'm really following how that answers my question unfortunately. Are they assuming O(n) corruptions? Distributed randomly in the string?

mirekrusin 5y ago

No you don’t, you need to read at most 2 bits past corrupted one to detect it.

dataflow 5y ago
The question is how do you know which one is corrupted before reading all of them??
- mirekrusin 5y ago
  You don't need to read 1 million bits to detect 5th being corrupted one, you will know it after reading 3 * 5 = 15 bits.
  - dataflow 5y ago
    Yeah and what if instead of being the 5th bit it was the 1 millionth bit that was corrupted?
    - mirekrusin 5y ago
      For 1 million bits message where millionth bit is corrupted last bit doesn't have to be read, in general in 3 replica coding, reading first 2 is enough if they are the same - reading last one will have no effect.
      - dataflow 5y ago
        For heaven's sake... how in the world would you know it's the millionth bit that's corrupted without scanning all 999,999 other bits at least once?!?! Do you data streams always come magically tagged with sentences like "Hey, watch out for bits 999,998-1,000,000, but all my other bits are intact so you can skip them!" or something??! You somehow "know" the error is in the final 3 bits and not in the earlier 999,997 bits because... magic??
        5y ago