Redundancy algorithm for reading noisy bitstream

I'm reading a lossy bit stream and I need a way to recover as much usable data as possible. There can be 1's in place of 0's and 0's in palce of 1's, but accuracy is probably over 80%.

A bonus would be if the algorithm could compensate for missing/too many bits as well.

The source I'm reading from is analogue with noise (microphone via FFT), and the read timing could vary depending on computer speed.

I remember reading about algorithms used in CD-ROM's doing this in 3? layers, so I'm guessing using several layers is a good option. I don't remember the details though, so if anyone can share some ideas that would be great! :)

Edit: Added sample data

Best case data:
 in: 0000010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111
out: 0010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111011

Bade case (timing is off, samples are missing):
out: 00101010000101101001011011001110000001001001011011001110000001001000011000000100001011101010011011001
 in: 00111101001011111110010010111111011110000010010000111000011101001101111110000110111011110111111111101

Edit2: I am able to controll the data being sent. Currently attempting to implement simp开发者_JS百科le XOR checking (though it won't be enough).

If I understand you correctly, you have two needs:

1. Modulate a signal into sound and then demodulate it.
2. Apply error correction since the channel is unreliable.

Modulation and demodulation is a wellknown application, with several ways to modulate the information.

Number two, error correction also is wellknown and have several possibilities. Which one is applicable depends on the error rate and whether you have duplex operation so that you can request resends. If you have decent quality and can request resends an approach like the one TCP is using is worth exploring.

Otherwise you will have to get down to error detection and error correction algorithms, like the one used on CDROMs.

Edit after the comment

Having the modulation/demodulation done and no resend possibilities narrows the problem. If you are having timing issues, I would still recommend that you read up on existing (de)modulation methods, as there are ways to automatically resynchronize with the sender and increase signal-to-noise ratio.

Down to the core problem; error correction you will have to add parity bits to your output stream in order to be able to detect the errors. Starting with the forward error correction article @Justin suggests, an scheme that looks quite simple, but still powerful is the Hamming(7,4) scheme.

You need to use forward error correction. An XOR parity check will only detect when an error occurs. A simple error correction algorithm would be to send each chunk of data multiple times (at least 3) and make a majority decision.

The choice of algorithm depends on several factors:

• Channel utilization (if you have lots of free time, you don't need an efficient coding)
• Error types: are the bad bits randomly spaced or do they usually occur in a row
• Processing time: code complexity is limited if data transmission needs to be fast

There are lot of possibilities, see : http://en.wikipedia.org/wiki/Error_detection_and_correction

This can help you with changed bits, but may be unsuitable to check whenever you have all the bits.

In the end, it will probably take much more than few lines of simple code.