Alternative FSK decoding?

[aquila12]

I was having some problems decoding a very clean FSK test signal - it's fine at low baud rates, but struggles at higher ones.

I notice the code appears to be using FFTs to compare the relative power of the mark and space frequencies, and I did a bit of experimentation with an alternative algorithm, which also splits out the sampling of the output bitstream - essentially as you would do in hardware.

This is for info / comments, as I've not yet implemented it in C to test it out.

The algorithm I've tested out in Octave is relatively straightforward, and I'll hopefully find some time to implement it soon, if there's interest. It goes something like this:

• Maintain two quadrature oscillators (these can be precalculated in buffers) for the mark and space frequencies, running at the sample rate.
• Multiply these oscillators each onto the input stream (sample to sample - mixing, not convolving) as it arrives, producing two I/Q signal pairs.
• Run four moving average filters of length N, where N is the number of samples per symbol. Feed them with each element of the I/Q pairs
• Calculate the magnitude of the I/Q signals after the MAFs
• Take the difference of the magnitudes
• Run the difference through a fifth MAF of the same length
• Take the sign of the output MAF to determine the current output state. (Note, this can be improved to perform better with selective fading by running envelope detectors against the I/Q magnitude signals. Noise performance might be improved by adding some hysteresis rather than just taking the sign, but this does add a delay).

This forms a very clean output running at the sample rate. The advantage of using MAFs is that they are very cheap to process - only the newest and oldest value need be processed for a given output sample. Variation in the oscillator frequencies doesn't seem much of an issue. Noise doesn't seem to cause many problems, but does affect the output bitstream (less baudrate margin). The above is a little sensitive to transients - a stepped sine wave can take a short time to settle.

To sample the data, the following algorithm can be used (performing 3x oversampling):

• Wait for a mark-to-space edge (edge of a start bit)
• Delay 1/6th of a symbol period
• Sample, delay 1/3rd of a symbol period; repeat 3 times
• Take the majority vote of the three samples - if this is a 'space', set up a bit counter to read the frame; else, return to waiting for a negative edge (false-trigger)
• For each bit, delay 1/3rd of a symbol period then sample - 3 times per bit taking the majority, decrementing the bit counter each time
• After the bit counter gets to zero, return to waiting for a negative edge.

This algorithm seems to work quite nicely, though I've not performed extensive testing of it. It's quite simple to implement. It copes with a bit of baud-rate variation, depending on noise. For 1200 baud, I had it working from ~1105 - 1305 with no noise. The acceptable range narrows as noise increases.

The downside to this algorithm is that it is greedy with respect to the start of frames. If it detects the wrong bit as a start bit, it might take a while to realign. This could be worked around by buffering and looking ahead the appropriate number of bits to ensure it sees a corresponding stop bit in the right place; though this makes the implementation a bit more complicated.

I'll have a go at implementing the above when I get time. In the meantime, if you have any comments on the above I'd be glad to hear them.

[aquila12]

An improvement in the above algorithm, on the bit sampling side - this replaces the triple-sampling with a continuous integrate-and-dump with initial edge trigger:

• Wait for a mark-to-space edge (edge of start bit)
• Start integrating for one symbol period
• At the end of the period, check the sign of the result; if it's a space, set a bit counter to read the frame; otherwise, return to wait for the next mark-to-space edge.
• For each bit, start integrating for one symbol period
• At the end of each period, check the sign of the result and use this to assign a mark or space bit into the output; also decrement the bit counter
• When the bit counter reaches zero, return to wait for the next mark-to-space edge.

The has better baud rate error performance than the algorithm above, with and without noise.

[aquila12]

Once more managed to improve upon the bit sampling - essentially changing the way it works a bit so it's sensitive to all edges for timing correction, and is capable of free-running (though it has no sort of gate for when there's no input):

• Set up a counter with the number of samples per symbol to wait
• Set up another MAF against the binary stream, to use as a continuous form of integrate-and-dump filter
• Each sample: decrement the counter
• If an edge is detected, take the amount of time left until we're next due to sample, and determine the closest expected bit edge
• Correct the counter by this amount, and continue
• If the counter reaches zero, take the output of the MAF and make the zero/one decision, then add the symbol period onto the counter

This operates in a similar manner to the above, but will self-align to bits even in the middle of a frame.

To turn the output into detected frames, just run the raw binary stream through a buffer, and wait until it looks like 10xxxxxxxx1 (idle, start bit, data, stop bit). Once one is found, wait at least N bits before attempting again, so we don't accidentally double-read frames erroneously.

[dthierbach]

@aquila12: That sounds very interesting, have you put up the code for this somewhere?

[aquila12]

Apologies, I haven't got round to it. I'll try and remember to dig it out... think it was a bunch of scripts for Octave for the time being. It shouldn't be difficult to write the C code though.

On 30 September 2016 at 09:06, Dirk Thierbach notifications@github.com wrote:

@aquila12 https://github.com/aquila12: That sounds very interesting, have you put up the code for this somewhere?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/kamalmostafa/minimodem/issues/14#issuecomment-250684902, or mute the thread https://github.com/notifications/unsubscribe-auth/AF1XJrL9QrqHgq0fdJVeENZ_fSuVbGDyks5qvMMOgaJpZM4EPUwD .

[aquila12]

OK, so I finally had a week off and time to revisit what I was doing. I have (with moderate effort) translated my Octave scripts into some real code, and it seems to work nicely (having ironed out the integer overflows). See aquila12/v23 for the code (/sim contains the Octave scripts I wrote to test the idea out).

There may be better choices for MAF lengths to position the zeroes at more tactical frequencies. It works quite nicely, but has no level gate. It's fine with a carrier, but with silence it will tend to generate erroneous data. I've yet to add proper audio IO (you can test with a .raw or pipe arecord to it), but I'll likely make it into a standalone application for what I need. Feel free to reuse anything you can from it, though - the frame detection / alignment stuff should be useful anyway for all of Minimodem's frame formats.