3
$\begingroup$

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...).

$\endgroup$

migrated from stackoverflow.com Aug 8 '14 at 6:57

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ What is your goal? Are you trying to reduce the amount of data sent over the communication channel? Increase the reliability of the transmission, to tolerate errors in the communication channel? If the latter, what can you say about the nature of errors (is it a binary symmetric channel? do you have burst errors? etc.). I had difficulty extracting that from the question. Also, what research have you done into error-correcting codes that might be suitable for this situation? Most likely Bloom filters are not the right tool, and existing error-correcting codes will suffice. $\endgroup$ – D.W. Aug 17 '14 at 15:36
  • $\begingroup$ The goal is to use the Bloom filter to transmit data since that's the capability of the library I'm using. The scenario is quite contrived otherwise since I'm trying to reliably send data using an unreliable "encoding" (the Bloom filter) which gets sent over a reliable channel. So I agree Bloom filters don't make sense here but this is all I have to work with. $\endgroup$ – ide Aug 21 '14 at 19:05
  • $\begingroup$ Yeah, well, I think this is a situation where you have a hammer and you're trying to use it in screw in a screw... and the best answer is going to be "no, don't use a hammer for that, use a screwdriver". The best solution is probably going to be "use an error-correcting code; don't try to force this to use Bloom filters". $\endgroup$ – D.W. Aug 21 '14 at 21:29
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ The OP is suggesting adding error-correcting bits, so there is no information theoritic problem. $\endgroup$ – Yuval Filmus Aug 16 '14 at 13:34
  • $\begingroup$ The error-correcting bits would need to be encoded in the same Bloom filter in my setup so this answer is right. I'll pursue another technique for my problem. I did find work on ECC for Z-channels and learned about some smart techniques (e.g. non-uniform codes that differ in length based on the number of 1-bits in the original message) though. $\endgroup$ – ide Aug 17 '14 at 6:42
  • $\begingroup$ @YuvalFilmus, OK, if so, this answer is not relevant. I had a difficulty extracting that from the question. Perhaps the original author will edit the question to clarify their goals, in that case. $\endgroup$ – D.W. Aug 17 '14 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.