Synchronising audio in realtime without knowledge of original signal

Question

Was doubting whether this is the right SE forum to ask my (elaborate) question, so don’t hesitate to let me know if it’s not. Also, if anyone knows of a better way to title the question, feel free to alter.

Background

The setup is the following: two computers stand in a room. One has a speaker (TX), one has a microphone (RX).

TX gets some bits as input, picks a .wav file out of the files it has stored (e.g. of a song), and alters its samples using the echo data hiding method (more on that here; the basic idea is that a signal is split into segments of equal length – one for every bit to be hidden into the signal –, after which an echo is embedded into every segment with a delay of $\delta_0$ or $\delta_1$ depending on whether the segment should represent a 0 or a 1 respectively). Finally, TX plays the result over the speaker at an unknown time; humans in the room only notice the music, but don’t notice the embedded echoes.

RX keeps refreshing a buffer of microphone samples, and analyses it continuously. On a certain mark, RX starts recording the incoming microphone data into long-term storage. On a second mark, it stops, and starts decoding the signal.

To decode echo-hidden bits, a decoder has to analyse each of the original segments (this is done using “cepstral” analysis, which transforms each segment into a function relating delay time to echo prominence by taking the FFT of the logarithm of the magnitude of the FFT of the segment; by comparing the prominence for $\delta_0$ and $\delta_1$, the decoder knows which bit was most likely embedded). If such a decoder doesn’t start its analysis in a very near region of the start of a segment, it has a high likelihood of misinterpreting the chunks of samples it thinks are segments, and gets the data wrong. I've tried drawing a visual of this below:

The givens

I have written an encoder and a decoder in Python. When passing TX’s signal to RX digitally and (so, when the decoder knows that the signal starts at the first sample), the decoder is able to flawlessly reconstruct the encoded data.

The issue

Here’s the big issue: I have no idea how TX can precisely indicate to RX where the ambient noise stops and the played signal begins. This effectively means RX can’t decode TX’s signal at all.

Starting bits can’t be used at first glance, since to detect those, RX would have to know where they start. Using an indicative frequency violates inaudibility, and using ultrasonic sounds is not possible given the hardware. (To further add to why an indicative frequency is not desirable: ideally, I’d want multiple starting and ending indicators spaced throughout TX’s signal, so that RX can still chime in to the same signal if it wasn’t yet powered on at the start. That would mean multiple “beeps”.)

Attempts at finding a solution

One solution I’ve thought about is sliding a pretend-segment through the microphone buffer, sample-by-sample, whilst applying the decoder to that segment, trying to detect a starting bit. Problems with that: the pretend-segment would be about 2000 samples, and the decoder is fairly resource-intensive (1 ms per decoding, so 2 s to slide through a 2000-sample buffer, which means it’d fall behind easily for a microphone recording at 44100 samples per second). Secondly, you’d need some kind of cepstrum threshold for deciding whether or not the pretend-segment is not just noise. Such a criterium would have to consider the power of the incoming signal, which I have no experience with.

Another solution I’ve considered is using such a pretend-segment and cross-correlation with an expected pattern, which takes only a few µs or less to execute. The problem with that, is that RX doesn’t know what TX’s signal will sound like, since TX has a whole database of .wav files to choose from and alters the chosen one with unknown data. Cross-correlating the incoming signal to a shift of itself to detect echoes, is something I’ve attempted, but failed at so far.

Related sources

I’ve been thinking about this for two weeks now (and have been working on the entire steganographic system for two months, when I first came into contact with the concept of signal processing), yet I’m out of ideas trying to solve this synchronisation problem. I’ve scoured SE for help, but most synchronisation threads assume RX receives a readily interpretable stream of bits, which is not the case here. The most closely related question on RX synchronisation I’ve found is this one, but it uses radio frequency modulation, which is not relevant to this problem. The amount of papers describing echo hiding that also discuss synchronisation is next to 0, and the ones that do, are too vague to be interpreted well.

Apologies for the wall of text. Any ideas, POVs, leads to techniques etc. would be helpful; programming a solution I could manage, if I knew what solution!

Answer 1

You may be working the wrong problem here: echo data hiding seems like a sub-optimal choice for an acoustic channel (speaker -> microphone).

Transmitting data acoustically in a room is very hard. The channel is quite complicated and difficult to deal with: Loudspeakers tend to be very non-flat and have a fair bit of non-linear distortion. Microphones are often noisy and many computers have poor sound cards and pre-amplifiers. But the most difficult might be the room itself: a typical residential room has a reverb time of about 300ms and generates many thousands of reflections. You need to make sure that your decoder can reliably detect the difference between a encoded echo and an echo created by the room.

I would first make a recording of your received signal with the room and harware you have in mind, synchronize it manually and then check if your decoder can actually deal with the channel problems. If yes, you can move on to the synchronization problem. If no, you need to rethink your approach.

Back to the actual question. Typically this is done by sending an preamble or a unique marker of sorts. An easy marker would be a short tone burst at, say 19 kHz. That's inaudible but fairly easy to detect if you hardware is good enough.