Geek Answers Handbook

Redundancy algorithm for reading a noisy bitstream

I am reading a lossy stream and I need a way to recover as much useful information as possible. There may be 1 instead of 0 and 0 in the palm of 1, but the accuracy probably exceeds 80%.

The bonus would be if the algorithm could compensate for the missing / too many bits.

The source that I am reading is an analogue of noise (microphone via FFT), and the reading time may vary depending on the speed of the computer.

I remember reading about the algorithms used on the CD-ROM, in this case? layers, so I assume using multiple layers is a good option. However, I don’t remember the details, so if someone could share some ideas, that would be great! :)

Edit: Added sample data

  Best case data:
  in: 000001010100001011010010110110011100000010010010010110110011100000010010000110000001000010111010100110110011100010111000000100111101100110011000000100100111011011011010101011100111011000100110000001000010010111
 out: 00101010000101101001011011001110000001001001001011011001110000001001000011000000100001011101010011011001110001010100000010011110110011001100000010010011101101101101010101110011101100010011000000100000010111011

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

Edit2: I can control the data sent. Currently trying to implement a simple XOR check (although this will not be enough).

+7
source share
3 answers

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

The choice of algorithm depends on several factors:

  • Using the channel (if you have a lot of free time, you do not need efficient coding)
  • Types of errors: erroneous bits of random intervals or usually they occur in a string
  • Processing time: code complexity is limited if data transfer should be fast.
+2
source

If you understand correctly, you have two needs:

  • Modulate the signal into sound and then demodulate it.
  • Apply error correction because the channel is not reliable.

Modulation and demodulation is a well-known application, several ways to modulate information.

Number two, error correction is also well known and has several features. Which one is applicable depends on the error rate and whether you have a duplex operation so that you can request retries. If you have decent quality and you can request retries, then the approach that TCP uses is worth exploring.

Otherwise, you will have to move on to error detection and error correction algorithms, such as those used on the CDROM.

Edit after comment

Performing modulation / demodulation and not being able to resend narrow the problem. If you have problems with synchronization, I would still recommend that you familiarize yourself with the existing (de) modulation methods, as there are ways to automatically synchronize with the sender and increase the signal-to-noise ratio.

To the main problem; To correct errors, you will need to add a parity bit to the output stream in order to be able to detect errors. Starting with the article with direct error correction, @Justin has proposed a scheme that looks pretty simple but still powerful is the Hamming scheme (7.4) .

+3
source

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

This may help you with the modified bits, but it may not be suitable for checking when you have all the bits.

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

+2
source

More articles:


All Articles