In this milestone, we’ll solve the problem generated by the recording of the signal emitted by our speakers that is captured by our microphone, generating an unpleasant feedback that difficults our conversation (using InterCom). First, we’ll formalize the problem and then we will explore different solutions, with varying effectiveness and computational requirements.
One of the first problems we encounter with the use of the buffer.py module1 is that, if we don’t use headphones, the sound that comes out of our PC’s (loud)speaker some time later reaches our mic(rophone), and more some time later, that sound reaches our interlocutor (the “far-end” ... in the system we are the “near-end”) in the form of an echo (signal) of its own voice, which is reproduced by his/her speaker, which can be captured again (some time later) by his/her mic and sent it back to us ... and so on, generating a rather unpleasant feedback signal.
To formalize the problem, let’s define:
In this situation, we have that
where \(m(t)\) is the analog audio signal that makes the membrane of our microphone oscillate.
Our problem here is to minimize the energy of \(s(t)\), i.e., to make
Use a headset. In this case,
because \(s(t)\approx 0\).
Decrease the gain of the amplifier of your speaker to do (the energy of) \(s(t)\) as small as possible. Unfortunately, this also decreases the volume of the far-end signal (the voice of our interlocutor) :-/
Lets \(\mathbf m\) the digital version of \(m(t)\), and \({\mathbf m}[t]\) it’s \(t\)-th sample3. In this solution, we send
where \(a\) is an attenuation (scalar) value, and \(d\) represents the delay4 (measured in sample-times) required to propagate the sound waves from our speaker to our mic. We define
as the estimated5 feedback signal that reaches our microphone at the same instant of time that the sample \({\mathbf n}[t]\) would have been captured in the ausence of the feedback.
Notice that it have been used the notation \(\tilde {\cdot }\) to highlight that \(\tilde {\mathbf n}\) is an approximation of \(\mathbf n\) (our sampled true-voice signal), and the notation \(\hat {\cdot }\) to emphasize that \(\hat {\mathbf s}\) is a registered6 prediction for \(s\) reaching our microphone. Notice also that, if \({\mathbf s}[0]\) is the first sample of a chunk (\(c\)-th chunk), the sample \({\mathbf s}[-d]\) could belong to a previous chunk (the \((c-1)\)-th chunk).
Finally, \(a\) should be choosen considering that under ausence of voice in each end, \(s(t)\approx 0\). For example, Skype estimates \(d\) and \(a\) using a “call-signal” (a sequence of more-or-less tonal sounds). \(d\) is determined measuring the propagation time of the call-signal between our speaker and our mic.
This algorithm is ineffective because:
We can improve the performance of the previous feedback cancellation solution if we take also into consideration that the feedback signal that finally reaches our microphone is (at least in part) the convolution of \(s(t)\) and a signal \(h(t)\) that represents the echo response of our local audioset (speaker, mic, walls, monitor, keyboard, our body, ...) to an impulse signal \(\delta (t)\).7 In other words, we can modify Eq. \eqref{eq:simplest} to compute
where \(\ast \) represents the (digital) convolution between (in our case of) digital signals, and \(\mathbf h\) is the digitalized version of \(h(t)\).
The convolution of digital signals in the time domain can be expensive (with computational complexity \(O^2\), where \(O\) is the number of elements to process) if the number of samples or/and filter coefficientsis is high. Fortunately, thanks to the convolution theorem [3, 4], the convolution can be replaced by the dot product (with complexity \(O\)), when we consider the signals in the frequency domain. Thanks to this, we can rewrite the Eq. \eqref{eq:using_convolution} as
where \(\mathbf S\) is the (digital) Fourier transform8 of \(\mathbf s\), \(\mathbf H\) is the Fourier transform9 of \(\mathbf h\), and \({\mathcal F}^{-1}\) represents the inverse (digital) Fourier transform. Notice that all these transforms are applied to digital signals, and there exist fast algorithms (with complexity \(O\log _2O\)).
Unfortunately, even when we expect that this improved feedback supression algorithm is going to perform better than the previous one, the computation of the filter weights \(\mathbf h\) requires emitting impulses that can be heard by the user.
The LMS algorithm [2, 1] was invented by professor Bernard Widrow and his first Ph.D. student, Ted Hoff, to train the ADALINE artificial neural “network”.10 Using LMS, ADALINE is able to distinguish two (different) patterns, even using (only a part of11) a single neuron.
LMS finds \(\mathbf {h}\) without using impulses. Considering that the signal that we should send to the far-end is
LMS minimizes
using the update rule
where \(\mu \) is the learning rate12 and \(i\) represents the \(i\)-th update iteration. These equations can be found13 using the (steepest) gradient descend algorithm.
Yes, unfortunately we only can compute \(\mathbf {h}\) if we have \(\hat {\mathbf {s}}\) (the signal played by the speaker that is recorded by our mic), i.e., me must be silent when updating. Therefore, the performance of this algorithm depends on the performance of other auxiliar technique which should determine whether in the near-end there is some source of sound.
Lets recap. Our problem is that, without a headset, we have that the signal that we send is
where \(\hat {\mathbf {s}}\) is a aproximated-and-delayed version of \(\mathbf {s}\), the signal played by our speaker(s). And if we were able to make \(\hat {\mathbf {s}}=\mathbf {0}\), our feedback problem would vanish, ... at least, theoretically.
But wait ..., as a polite person, if I don’t speak when I am listening to my interlocutor, I could set \(\hat {\mathbf {s}}=\mathbf {0}\) when I am speaking because my interlocutor should do the same (be silent when I speak)!
Therefore, this solution (like the previous one) does need some technique to detect when I’m speaking. The advantage here is that we only need to switch off (or at least decrease enough the) volume of our speaker, something that does not consume computational resources. Notice that the “voice detector” algorithm can run in a separate thread/process.