0
$\begingroup$

I'm building an application that requires determining the arrival time of an audio signal with a very high degree of accuracy (within 1ms would be ideal) using commodity smartphone hardware. I found another user on this site who had the same requirements (minus the smartphones), and the answer given was truly excellent. That question is here:

How to send / receive a short impulse in an extremely noisy signal with high timing accuracy?

I've basically implemented what's recommended in that post... I generated some random binary data and used BPSK modulation to encode it. I used a 1600hz carrier, and 80 bits at 160 bits/second, so that the resulting audio snippet was 500ms long. (Forgive me if my terminology isn't 100% right, DSP is new to me.) Looks like this...

bpsk waveform

I've been playing this out using commodity smartphone hardware, and recording it on another smartphone. I've then been cross-correlating the original BPSK audio with the recorded audio file to find the exact time that the signal started (i.e., the time that the cross-correlation is highest).

I've found that, under very tightly controlled conditions where there's little opportunity for reverberations (e.g., outside in a field), I get highly accurate timing values. However, when I'm indoors, I find that the timings produced are almost always late. The recorded audio signal will look something like the following:

recorded bpsk

I've noticed several things about the recording:

  1. When the signal first starts to depart from background noise, it has several ms of "weirdness" before it starts to settle into the actual 1600hz waveform.
  2. When the signal switches phase 180 degrees, there will be several ms of "weirdness" again, rather than a clean switch from one phase to the other.
  3. The sound continues to reverberate around the room for 50-100ms after the end of the main signal.

When I compute the cross-correlation of the original signal with the recorded signal, I frequently get something like this around the onset time...

cross correlation output

Notice that the cross-correlation peaks on two separate occasions, and that those occasions are about 10ms apart. What I'm suspecting is that (in the pictured case) the sound is reflecting in the room and that the loudest reflection is arriving about 10ms behind the direct-path sound with nearly-equivalent (actually, slightly higher!) amplitude. This would explain why my timings are usually late - the cross-correlation is identifying a reflected signal rather than the direct-path signal. I'm also sure that the impulse response of the cheap smartphone speakers and microphones are not helping the situation - they probably have quite a bit of delay and distortion in them.

Is there anything I can/should be doing to help identify the direct-path sound and ignore the reflections? Unfortunately, I won't know the acoustics of the room in advance, so I can't convolve the original signal with the room impulse response. Is there anything else I can do to separate these arrival times?

The only idea I've had is a simple heuristic - if the cross-correlation values peak multiple times, those peaks are within X ms of each other, and the amplitude of those peaks is within Y% of each other, always choose the earlier one, assuming the later is a reflection.

Anything else I should be thinking about? Some sort of filtering?

EDIT IN RESPONSE TO telemeister's THOROUGH ANSWER:

  1. Auto-correlation for my BPSK signal looks good - one peak with two side lobes.

  2. The suggestion to use a higher frequency for better resolving power was helpful - switching from 1600hz to 6400 hz seemed to make things more accurate.

However, I'm still finding that the cross-correlation often peaks shockingly late. For example, take a look at this recording. This is a device recording itself playing a 6400hz BPSK signal. The position of the cursor in Audacity marks the place where the signal starts to deviate from background noise (at least, to the naked eye).

recording vs. background noise

However, take a look at the cross-correlation output, with the exact same moment marked by the cursor in Audacity.

impulse response in Audacity

What you'll notice is that the cross-correlation peaks ~100 samples after the audio recording starts to deviate from background noise. And, based on the cross-correlation, anyway, there doesn't seem to be any echo in this case - there's no follow-up spikes in the cross-correlation, whether weaker or stronger.

How should I interpret this, especially given that this is the device recording itself? It doesn't seem to be a reflection. Is it something else? Speaker or microphone taking a second to start fully representing the signal? Something getting up to a resonant frequency? Not sure if this even is answerable, but I'm curious to know if anybody has thoughts.

$\endgroup$
4
  • $\begingroup$ Do you just need to determine time of arrival or do you you need to transmit actual bits ? $\endgroup$ – Hilmar May 20 at 14:33
  • $\begingroup$ I just need the time of arrival. So, it'd also be acceptable to use a chirp or any other sound for this purpose. (Actually, I've been able to recover the bits quite easily despite the echo but, alas, that's not the need here.) $\endgroup$ – John Chrysostom May 20 at 14:37
  • $\begingroup$ Another question: time of arrival relative to what? Do you have some shared time reference between the two phones ? $\endgroup$ – Hilmar May 20 at 16:23
  • $\begingroup$ Thanks. Time of arrival relative to the start of the audio recording will suffice for my purposes. $\endgroup$ – John Chrysostom May 20 at 17:12
2
$\begingroup$

Your problem parallels exactly what we do in seismic exploration, although the scale is different. We also use sound waves, with frequencies of 0-100 Hz, and record times up to about 10 s. A few ideas which may help.

  1. Autocorrelation:

The correlation approach (matched filtering) is the way to go. First, suggest you look at the autocorrelation of your input reference signal. This will show you the pulse that will (in theory) appear at each "event" arriving at the receiver. For the type of reference that you are using (constant frequency with polarity flips -we call this a pseudo-random reference) the form of the pulse requires that the time positions of the flips obey strict rules. If you have got it right, the autocorrelation pulse will look like the BLUE pulse in this picture. That is, a central peak with just one side lobe on each side. pseudorandom and chirp autocorrelations.

If your pulse looks more complex, then the pseudo-random sequence may not be right. Let me know if you need more info on that.

  1. Resolution vs attenuation:

The resolving power of the pulse is linked directly to your carrier frequency. If you reduce this you will get a broader pulse, and hence poorer resolving power. The trade off is reduced attenuation

You can experiment with this effect by playing with autocorrelations in code. Once you get the pulse to your liking you can move onto looking at the received signal.

  1. Distortion in the received signal:

The distortion in your received signal is not unlike what we see at our scale. This can be caused by deficiencies/ coupling in the transducers, as you suggest. Fortunately correlation (against the reference signal) is remarkably powerful at detecting the underlying signal.

  1. Swept-frequency (CHIRP) reference:

This alternative is certainly more common in our work, and arguably simpler to implement. The basic equation is in Wikipedia ("chirp signal"), but again let me know if you need more info. In the above picture the RED wavelet is a typical autocorrelation pulse from a swept-frequency signal. It can be a little more ringy, but this can be controlled by tapering the leading and trailing edges of the reference. Again the frequency range is decided by considerations of resolution and attenuation. In our work our sweeps typically go from about 10 Hz to 100 Hz, and extend for about 10s. We then "Listen" for about another 10s following the 'transmission'. I imagine you would be about a factor of 10 up in frequency, and a factor of 10 down in record/listen times.

  1. Deconvolution / dereverb:

Once you get the basic system functioning you should be able to see a series of events in the correlated output. which as you say, represent various reflections, echoes etc. I would expect this to still look pretty complex, even after correlation. These is a rich literature in seismic deconvolution and the code is pretty simple. Happy to point you in that direction later if it is of interest. (If you are only interested in the direct wave, then the so-called "first arrival" will be what you want and it should be obvious.)

Hope this is useful to you.

ADDITIONAL NOTES FOLLOWING JOHN'S FEEDBACK:

Worth checking a couple of basic things first just to make sure. You've probably already checked these - if so my apologies!

CROSS_CORRELATION ASYMMETRY:

The cross correlation is asymmetrical about lag zero. We need to be sure we are looking at the positive lags - not the negative lags. It depends on your conventions. In my case we correlate the recorded signal (say R) against the reference signal or so-called Pilot (say P). If I do it in the frequency domain it is $R(\omega)\bar P(\omega)$ where the bar is conjugate. (If you do it backwards you are looking at the negative lags - not really meaningful.)

TIMING SYNCHRONISATION:

Sorry - I don't have a good feel for the mechanics of your problem. I'm thinking you have the transmitter and receiver separated by a reasonable distance and are trying to measure the travel time of the sound wave - perhaps to estimate the distance? Maybe you could explain briefly what the physical setup is.

Anyway, the timing at the Transmitter and Receiver obviously need to be synchronised exactly. Until recently we had to use a hard-wired connection, to avoid radio latency etc. Now we are able to use GPS timing pulses at each end.

Time zero is the time at which you start the transmission. The central peak in the crosscorrelation pulse then indicates the travel time of the sound wave.

SYSTEM LATENCY:

Again I dont understand exactly how the sound wave is being generated, or how it is being captured. Assuming maybe two devices, audacity+speaker at one end and microphone+audacity at the other. It is quite likely there will be some system latency (delay) in these processes (speaker, mic, operating system etc).

I would try a test with the transmitter and receiver very close together, so that the output correlation should peak at approx $\tau=0$.

Or separate them by 1m in which case the time should be around 3ms.

If you then plotted the correlation for negative and positive lags it would allow you to check this (and at the same time check that you have the positive lags - if not the pulse would be at negative time).

If repeated tests give the same system latency, this is good, and can just be subtracted. if it is not constant it would require more investigation.

For example you could eliminate the delays of speaker and mic by just running a cable direct from transmit-device-output to the receive-device-input.

Feel free to get back with some more feedback on the above - I'd be happy to ponder it some more! Cheers.

$\endgroup$
6
  • $\begingroup$ Thanks for this very thorough answer. It was helpful in several ways already. I'm willing to accept, though still working through stuff. I added some additional info to my question in response to this answer. Not sure if you have thoughts. Thank you! $\endgroup$ – John Chrysostom May 25 at 15:06
  • $\begingroup$ Oh... wow. I wonder if that "stuff" leading up to the beginning of the main signal is an audio compression artifact... That would explain so much. $\endgroup$ – John Chrysostom May 25 at 16:42
  • $\begingroup$ @John Good that was of some use. I've added a few more notes to my original answer. $\endgroup$ – telemeister May 27 at 5:12
  • $\begingroup$ Thanks again! The use case here is measuring distance. Unfortunately, there is unavoidable, randomly varying delay in the audio stack - there's no way to know when sound arrives, even if clocks were synced. So I have both devices play a sound and record. The difference between A hearing A and B hearing A is clock offset + time of flight, the difference between A hearing B and B hearing B is clock offset - ToF. Two equations, two variables, solve for time of flight. I've seen this be highly accurate in certain conditions, so I know the math is right, but echos and reverb often kill it. $\endgroup$ – John Chrysostom May 27 at 12:30
  • $\begingroup$ Went ahead and accepted this answer. It didn't magically solve all my problems, but it DID give me a ton of helpful information that's moved my project forward. Thank you. Also, thank you for your kindness in responding helpfully to this question. On many SE sites, I'm afraid this question would have been met with lots of downvoting and complaints that it was "too vague" or "didn't have one right answer." Thanks for the assistance and the warm welcome to somebody who's new to Signal Processing SE! $\endgroup$ – John Chrysostom Jun 1 at 12:40

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.