4 ms·

Could someone explain why XORing the outputs of the two sources isn't optimal?

• tlb 10y ago
  Suppose both sources are 90% zeros. Their XOR will be mostly (82%) zeros too.
  • caf 10y ago
    And in terms of Shannon entropy, the original two bits have 0.469 bits of entropy each, and the resulting XORd bit has 0.68 bits of entropy. So this extractor is far from ideal.
    • caf 10y ago
      (Actually for the "90% zero" sources, OR would be a slightly better extractor than XOR, yielding a resulting bit with 0.70 bits of entropy).
  • wfunction 10y ago
    I guess what I'm wondering is, how could you possibly expect to do better? You told me why the result is bad, but gave no intuition on why I should expect better (I don't).
    • tlb 10y ago
      The simple trick is to take pairs of bits. If you get 01, output 0. If you get 10, output 1. Otherwise, output nothing. Even if the source is biased (as long as successive bits are uncorrelated), you get an unbiased 50:50 output. But obviously you get fewer bits out than you put in. The construction in the paper is basically a more efficient version of this.