[Solved]: Error-correction code for transmission only with bit-flipping from 0 to 1

Problem Detail: 

I am using a transmission system that uses a Bloom filter (this part is out of my control). I want to send a small amount of data (32 bits) using this system.

For each bit [0,31], I add its index to the Bloom filter if the corresponding bit is set. The Bloom filter is then transmitted without error and the recipient tests the Bloom filter for each index [0,31] to reconstruct the 32 bits of data.

One problem is that the Bloom filter can have false positives, making it look like some bits are set when they shouldn't be. Another problem is that the Bloom filter may already have other entries in it, further making it look like more bits are set.

I wondered if error-correction codes could help here. The general idea would be to add more bits ([32,35] for example) the recipient could use to figure out the original 32 bits despite Bloom filter collisions.

---

After a little research I learned that Z-channels (or binary asymmetric channels) flip bits in one direction. Also I found that linear error-correction codes for Z-channels are often applicable to symmetric channels as well. So to exploit the asymmetry, the codes likely need to be non-linear. More info on the state of the art is appreciated (hoping for a simple algorithm...).

Asked By : ide

Answered By : D.W.

This is not possible. There's no free lunch. You are looking for a compression scheme that is guaranteed to compress 32 bits down to less than 32 bits. That's not possible in general, unless you have prior knowledge that lets you rule out some of the possible 32-bit values.

In particular, if you want to send 32 bits of information, and all $2^{32}$ possibilities are equally likely, and errors are not allowed, you'll have to send at least 32 bits over the communication channel. This is a basic theorem of information theory. No amount of error-correcting codes will get you past this.

If you want to avoid this, you'll either need prior knowledge on the 32-bit value (e.g., to rule out some as impossible, or less likely than others), or you'll need to accept lossy compression (where the recipient's received string might not exactly match what the sender wanted to send).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28993

3.2K people like this

 Download Related Notes/Documents