2 * SpanDSP - a series of DSP components for telephony
4 * echo.c - A line echo canceller. This code is being developed
5 * against and partially complies with G168.
7 * Written by Steve Underwood <steveu@coppice.org>
8 * and David Rowe <david_at_rowetel_dot_com>
10 * Copyright (C) 2001, 2003 Steve Underwood, 2007 David Rowe
12 * Based on a bit from here, a bit from there, eye of toad, ear of
13 * bat, 15 years of failed attempts by David and a few fried brain
16 * All rights reserved.
18 * This program is free software; you can redistribute it and/or modify
19 * it under the terms of the GNU General Public License version 2, as
20 * published by the Free Software Foundation.
22 * This program is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU General Public License for more details.
27 * You should have received a copy of the GNU General Public License
28 * along with this program; if not, write to the Free Software
29 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
31 * $Id: echo.c,v 1.20 2006/12/01 18:00:48 steveu Exp $
36 /* Implementation Notes
40 This code started life as Steve's NLMS algorithm with a tap
41 rotation algorithm to handle divergence during double talk. I
42 added a Geigel Double Talk Detector (DTD) [2] and performed some
43 G168 tests. However I had trouble meeting the G168 requirements,
44 especially for double talk - there were always cases where my DTD
45 failed, for example where near end speech was under the 6dB
46 threshold required for declaring double talk.
48 So I tried a two path algorithm [1], which has so far given better
49 results. The original tap rotation/Geigel algorithm is available
50 in SVN http://svn.rowetel.com/software/oslec/tags/before_16bit.
51 It's probably possible to make it work if some one wants to put some
54 At present no special treatment is provided for tones, which
55 generally cause NLMS algorithms to diverge. Initial runs of a
56 subset of the G168 tests for tones (e.g ./echo_test 6) show the
57 current algorithm is passing OK, which is kind of surprising. The
58 full set of tests needs to be performed to confirm this result.
60 One other interesting change is that I have managed to get the NLMS
61 code to work with 16 bit coefficients, rather than the original 32
62 bit coefficents. This reduces the MIPs and storage required.
63 I evaulated the 16 bit port using g168_tests.sh and listening tests
64 on 4 real-world samples.
66 I also attempted the implementation of a block based NLMS update
67 [2] but although this passes g168_tests.sh it didn't converge well
68 on the real-world samples. I have no idea why, perhaps a scaling
69 problem. The block based code is also available in SVN
70 http://svn.rowetel.com/software/oslec/tags/before_16bit. If this
71 code can be debugged, it will lead to further reduction in MIPS, as
72 the block update code maps nicely onto DSP instruction sets (it's a
73 dot product) compared to the current sample-by-sample update.
75 Steve also has some nice notes on echo cancellers in echo.h
80 [1] Ochiai, Areseki, and Ogihara, "Echo Canceller with Two Echo
81 Path Models", IEEE Transactions on communications, COM-25,
84 http://www.rowetel.com/images/echo/dual_path_paper.pdf
86 [2] The classic, very useful paper that tells you how to
87 actually build a real world echo canceller:
88 Messerschmitt, Hedberg, Cole, Haoui, Winship, "Digital Voice
89 Echo Canceller with a TMS320020,
90 http://www.rowetel.com/images/echo/spra129.pdf
92 [3] I have written a series of blog posts on this work, here is
93 Part 1: http://www.rowetel.com/blog/?p=18
95 [4] The source code http://svn.rowetel.com/software/oslec/
97 [5] A nice reference on LMS filters:
98 http://en.wikipedia.org/wiki/Least_mean_squares_filter
102 Thanks to Steve Underwood, Jean-Marc Valin, and Ramakrishnan
103 Muthukrishnan for their suggestions and email discussions. Thanks
104 also to those people who collected echo samples for me such as
105 Mark, Pawel, and Pavel.
108 #include <linux/kernel.h> /* We're doing kernel work */
109 #include <linux/module.h>
110 #include <linux/kernel.h>
111 #include <linux/slab.h>
113 #include "bit_operations.h"
116 #define MIN_TX_POWER_FOR_ADAPTION 64
117 #define MIN_RX_POWER_FOR_ADAPTION 64
118 #define DTD_HANGOVER 600 /* 600 samples, or 75ms */
119 #define DC_LOG2BETA 3 /* log2() of DC filter Beta */
121 /*-----------------------------------------------------------------------*\
123 \*-----------------------------------------------------------------------*/
125 /* adapting coeffs using the traditional stochastic descent (N)LMS algorithm */
129 static void __inline__ lms_adapt_bg(struct oslec_state *ec, int clean, int shift)
140 factor = clean << shift;
142 factor = clean >> -shift;
144 /* Update the FIR taps */
146 offset2 = ec->curr_pos;
147 offset1 = ec->taps - offset2;
148 phist = &ec->fir_state_bg.history[offset2];
150 /* st: and en: help us locate the assembler in echo.s */
154 for (i = 0, j = offset2; i < n; i++, j++)
156 exp = *phist++ * factor;
157 ec->fir_taps16[1][i] += (int16_t) ((exp+(1<<14)) >> 15);
161 /* Note the asm for the inner loop above generated by Blackfin gcc
162 4.1.1 is pretty good (note even parallel instructions used):
173 A block based update algorithm would be much faster but the
174 above can't be improved on much. Every instruction saved in
175 the loop above is 2 MIPs/ch! The for loop above is where the
176 Blackfin spends most of it's time - about 17 MIPs/ch measured
177 with speedtest.c with 256 taps (32ms). Write-back and
178 Write-through cache gave about the same performance.
183 IDEAS for further optimisation of lms_adapt_bg():
185 1/ The rounding is quite costly. Could we keep as 32 bit coeffs
186 then make filter pluck the MS 16-bits of the coeffs when filtering?
187 However this would lower potential optimisation of filter, as I
188 think the dual-MAC architecture requires packed 16 bit coeffs.
190 2/ Block based update would be more efficient, as per comments above,
191 could use dual MAC architecture.
193 3/ Look for same sample Blackfin LMS code, see if we can get dual-MAC
196 4/ Execute the whole e/c in a block of say 20ms rather than sample
197 by sample. Processing a few samples every ms is inefficient.
201 static __inline__ void lms_adapt_bg(struct oslec_state *ec, int clean, int shift)
211 factor = clean << shift;
213 factor = clean >> -shift;
215 /* Update the FIR taps */
217 offset2 = ec->curr_pos;
218 offset1 = ec->taps - offset2;
220 for (i = ec->taps - 1; i >= offset1; i--)
222 exp = (ec->fir_state_bg.history[i - offset1]*factor);
223 ec->fir_taps16[1][i] += (int16_t) ((exp+(1<<14)) >> 15);
227 exp = (ec->fir_state_bg.history[i + offset2]*factor);
228 ec->fir_taps16[1][i] += (int16_t) ((exp+(1<<14)) >> 15);
234 struct oslec_state *oslec_create(int len, int adaption_mode)
236 struct oslec_state *ec;
239 ec = kzalloc(sizeof(*ec), GFP_KERNEL);
244 ec->log2taps = top_bit(len);
245 ec->curr_pos = ec->taps - 1;
247 for (i = 0; i < 2; i++) {
248 ec->fir_taps16[i] = kcalloc(ec->taps, sizeof(int16_t), GFP_KERNEL);
249 if (!ec->fir_taps16[i])
253 fir16_create(&ec->fir_state,
256 fir16_create(&ec->fir_state_bg,
261 ec->xvtx[i] = ec->yvtx[i] = ec->xvrx[i] = ec->yvrx[i] = 0;
264 ec->cng_level = 1000;
265 oslec_adaption_mode(ec, adaption_mode);
267 ec->snapshot = kcalloc(ec->taps, sizeof(int16_t), GFP_KERNEL);
273 ec->Ltxacc = ec->Lrxacc = ec->Lcleanacc = ec->Lclean_bgacc = 0;
274 ec->Ltx = ec->Lrx = ec->Lclean = ec->Lclean_bg = 0;
275 ec->tx_1 = ec->tx_2 = ec->rx_1 = ec->rx_2 = 0;
276 ec->Lbgn = ec->Lbgn_acc = 0;
277 ec->Lbgn_upper = 200;
278 ec->Lbgn_upper_acc = ec->Lbgn_upper << 13;
283 for (i = 0; i < 2; i++)
284 kfree(ec->fir_taps16[i]);
289 EXPORT_SYMBOL_GPL(oslec_create);
291 void oslec_free(struct oslec_state *ec)
295 fir16_free(&ec->fir_state);
296 fir16_free(&ec->fir_state_bg);
297 for (i = 0; i < 2; i++)
298 kfree(ec->fir_taps16[i]);
302 EXPORT_SYMBOL_GPL(oslec_free);
304 void oslec_adaption_mode(struct oslec_state *ec, int adaption_mode)
306 ec->adaption_mode = adaption_mode;
308 EXPORT_SYMBOL_GPL(oslec_adaption_mode);
310 void oslec_flush(struct oslec_state *ec)
314 ec->Ltxacc = ec->Lrxacc = ec->Lcleanacc = ec->Lclean_bgacc = 0;
315 ec->Ltx = ec->Lrx = ec->Lclean = ec->Lclean_bg = 0;
316 ec->tx_1 = ec->tx_2 = ec->rx_1 = ec->rx_2 = 0;
318 ec->Lbgn = ec->Lbgn_acc = 0;
319 ec->Lbgn_upper = 200;
320 ec->Lbgn_upper_acc = ec->Lbgn_upper << 13;
322 ec->nonupdate_dwell = 0;
324 fir16_flush(&ec->fir_state);
325 fir16_flush(&ec->fir_state_bg);
326 ec->fir_state.curr_pos = ec->taps - 1;
327 ec->fir_state_bg.curr_pos = ec->taps - 1;
328 for (i = 0; i < 2; i++)
329 memset(ec->fir_taps16[i], 0, ec->taps*sizeof(int16_t));
331 ec->curr_pos = ec->taps - 1;
334 EXPORT_SYMBOL_GPL(oslec_flush);
336 void oslec_snapshot(struct oslec_state *ec) {
337 memcpy(ec->snapshot, ec->fir_taps16[0], ec->taps*sizeof(int16_t));
339 EXPORT_SYMBOL_GPL(oslec_snapshot);
341 /* Dual Path Echo Canceller ------------------------------------------------*/
343 int16_t oslec_update(struct oslec_state *ec, int16_t tx, int16_t rx)
349 /* Input scaling was found be required to prevent problems when tx
350 starts clipping. Another possible way to handle this would be the
351 filter coefficent scaling. */
353 ec->tx = tx; ec->rx = rx;
358 Filter DC, 3dB point is 160Hz (I think), note 32 bit precision required
359 otherwise values do not track down to 0. Zero at DC, Pole at (1-Beta)
360 only real axis. Some chip sets (like Si labs) don't need
361 this, but something like a $10 X100P card does. Any DC really slows
364 Note: removes some low frequency from the signal, this reduces
365 the speech quality when listening to samples through headphones
366 but may not be obvious through a telephone handset.
368 Note that the 3dB frequency in radians is approx Beta, e.g. for
369 Beta = 2^(-3) = 0.125, 3dB freq is 0.125 rads = 159Hz.
372 if (ec->adaption_mode & ECHO_CAN_USE_RX_HPF) {
375 /* Make sure the gain of the HPF is 1.0. This can still saturate a little under
376 impulse conditions, and it might roll to 32768 and need clipping on sustained peak
377 level signals. However, the scale of such clipping is small, and the error due to
378 any saturation should not markedly affect the downstream processing. */
381 ec->rx_1 += -(ec->rx_1>>DC_LOG2BETA) + tmp - ec->rx_2;
383 /* hard limit filter to prevent clipping. Note that at this stage
384 rx should be limited to +/- 16383 due to right shift above */
385 tmp1 = ec->rx_1 >> 15;
386 if (tmp1 > 16383) tmp1 = 16383;
387 if (tmp1 < -16383) tmp1 = -16383;
392 /* Block average of power in the filter states. Used for
393 adaption power calculation. */
398 /* efficient "out with the old and in with the new" algorithm so
399 we don't have to recalculate over the whole block of
401 new = (int)tx * (int)tx;
402 old = (int)ec->fir_state.history[ec->fir_state.curr_pos] *
403 (int)ec->fir_state.history[ec->fir_state.curr_pos];
404 ec->Pstates += ((new - old) + (1<<ec->log2taps)) >> ec->log2taps;
405 if (ec->Pstates < 0) ec->Pstates = 0;
408 /* Calculate short term average levels using simple single pole IIRs */
410 ec->Ltxacc += abs(tx) - ec->Ltx;
411 ec->Ltx = (ec->Ltxacc + (1<<4)) >> 5;
412 ec->Lrxacc += abs(rx) - ec->Lrx;
413 ec->Lrx = (ec->Lrxacc + (1<<4)) >> 5;
415 /* Foreground filter ---------------------------------------------------*/
417 ec->fir_state.coeffs = ec->fir_taps16[0];
418 echo_value = fir16(&ec->fir_state, tx);
419 ec->clean = rx - echo_value;
420 ec->Lcleanacc += abs(ec->clean) - ec->Lclean;
421 ec->Lclean = (ec->Lcleanacc + (1<<4)) >> 5;
423 /* Background filter ---------------------------------------------------*/
425 echo_value = fir16(&ec->fir_state_bg, tx);
426 clean_bg = rx - echo_value;
427 ec->Lclean_bgacc += abs(clean_bg) - ec->Lclean_bg;
428 ec->Lclean_bg = (ec->Lclean_bgacc + (1<<4)) >> 5;
430 /* Background Filter adaption -----------------------------------------*/
432 /* Almost always adap bg filter, just simple DT and energy
433 detection to minimise adaption in cases of strong double talk.
434 However this is not critical for the dual path algorithm.
438 if ((ec->nonupdate_dwell == 0)) {
443 f = Beta * clean_bg_rx/P ------ (1)
445 where P is the total power in the filter states.
447 The Boffins have shown that if we obey (1) we converge
448 quickly and avoid instability.
450 The correct factor f must be in Q30, as this is the fixed
451 point format required by the lms_adapt_bg() function,
452 therefore the scaled version of (1) is:
454 (2^30) * f = (2^30) * Beta * clean_bg_rx/P
455 factor = (2^30) * Beta * clean_bg_rx/P ----- (2)
457 We have chosen Beta = 0.25 by experiment, so:
459 factor = (2^30) * (2^-2) * clean_bg_rx/P
462 factor = clean_bg_rx 2 ----- (3)
464 To avoid a divide we approximate log2(P) as top_bit(P),
465 which returns the position of the highest non-zero bit in
466 P. This approximation introduces an error as large as a
467 factor of 2, but the algorithm seems to handle it OK.
469 Come to think of it a divide may not be a big deal on a
470 modern DSP, so its probably worth checking out the cycles
471 for a divide versus a top_bit() implementation.
474 P = MIN_TX_POWER_FOR_ADAPTION + ec->Pstates;
475 logP = top_bit(P) + ec->log2taps;
476 shift = 30 - 2 - logP;
479 lms_adapt_bg(ec, clean_bg, shift);
482 /* very simple DTD to make sure we dont try and adapt with strong
486 if ((ec->Lrx > MIN_RX_POWER_FOR_ADAPTION) && (ec->Lrx > ec->Ltx))
487 ec->nonupdate_dwell = DTD_HANGOVER;
488 if (ec->nonupdate_dwell)
489 ec->nonupdate_dwell--;
491 /* Transfer logic ------------------------------------------------------*/
493 /* These conditions are from the dual path paper [1], I messed with
494 them a bit to improve performance. */
496 if ((ec->adaption_mode & ECHO_CAN_USE_ADAPTION) &&
497 (ec->nonupdate_dwell == 0) &&
498 (8*ec->Lclean_bg < 7*ec->Lclean) /* (ec->Lclean_bg < 0.875*ec->Lclean) */ &&
499 (8*ec->Lclean_bg < ec->Ltx) /* (ec->Lclean_bg < 0.125*ec->Ltx) */ )
501 if (ec->cond_met == 6) {
502 /* BG filter has had better results for 6 consecutive samples */
504 memcpy(ec->fir_taps16[0], ec->fir_taps16[1], ec->taps*sizeof(int16_t));
512 /* Non-Linear Processing ---------------------------------------------------*/
514 ec->clean_nlp = ec->clean;
515 if (ec->adaption_mode & ECHO_CAN_USE_NLP)
517 /* Non-linear processor - a fancy way to say "zap small signals, to avoid
518 residual echo due to (uLaw/ALaw) non-linearity in the channel.". */
520 if ((16*ec->Lclean < ec->Ltx))
522 /* Our e/c has improved echo by at least 24 dB (each factor of 2 is 6dB,
523 so 2*2*2*2=16 is the same as 6+6+6+6=24dB) */
524 if (ec->adaption_mode & ECHO_CAN_USE_CNG)
526 ec->cng_level = ec->Lbgn;
528 /* Very elementary comfort noise generation. Just random
529 numbers rolled off very vaguely Hoth-like. DR: This
530 noise doesn't sound quite right to me - I suspect there
531 are some overlfow issues in the filtering as it's too
532 "crackly". TODO: debug this, maybe just play noise at
533 high level or look at spectrum.
536 ec->cng_rndnum = 1664525U*ec->cng_rndnum + 1013904223U;
537 ec->cng_filter = ((ec->cng_rndnum & 0xFFFF) - 32768 + 5*ec->cng_filter) >> 3;
538 ec->clean_nlp = (ec->cng_filter*ec->cng_level*8) >> 14;
541 else if (ec->adaption_mode & ECHO_CAN_USE_CLIP)
543 /* This sounds much better than CNG */
544 if (ec->clean_nlp > ec->Lbgn)
545 ec->clean_nlp = ec->Lbgn;
546 if (ec->clean_nlp < -ec->Lbgn)
547 ec->clean_nlp = -ec->Lbgn;
551 /* just mute the residual, doesn't sound very good, used mainly
557 /* Background noise estimator. I tried a few algorithms
558 here without much luck. This very simple one seems to
559 work best, we just average the level using a slow (1 sec
560 time const) filter if the current level is less than a
561 (experimentally derived) constant. This means we dont
562 include high level signals like near end speech. When
563 combined with CNG or especially CLIP seems to work OK.
565 if (ec->Lclean < 40) {
566 ec->Lbgn_acc += abs(ec->clean) - ec->Lbgn;
567 ec->Lbgn = (ec->Lbgn_acc + (1<<11)) >> 12;
572 /* Roll around the taps buffer */
573 if (ec->curr_pos <= 0)
574 ec->curr_pos = ec->taps;
577 if (ec->adaption_mode & ECHO_CAN_DISABLE)
580 /* Output scaled back up again to match input scaling */
582 return (int16_t) ec->clean_nlp << 1;
584 EXPORT_SYMBOL_GPL(oslec_update);
586 /* This function is seperated from the echo canceller is it is usually called
587 as part of the tx process. See rx HP (DC blocking) filter above, it's
590 Some soft phones send speech signals with a lot of low frequency
591 energy, e.g. down to 20Hz. This can make the hybrid non-linear
592 which causes the echo canceller to fall over. This filter can help
593 by removing any low frequency before it gets to the tx port of the
596 It can also help by removing and DC in the tx signal. DC is bad
599 This is one of the classic DC removal filters, adjusted to provide sufficient
600 bass rolloff to meet the above requirement to protect hybrids from things that
601 upset them. The difference between successive samples produces a lousy HPF, and
602 then a suitably placed pole flattens things out. The final result is a nicely
603 rolled off bass end. The filtering is implemented with extended fractional
604 precision, which noise shapes things, giving very clean DC removal.
607 int16_t oslec_hpf_tx(struct oslec_state *ec, int16_t tx) {
610 if (ec->adaption_mode & ECHO_CAN_USE_TX_HPF) {
613 /* Make sure the gain of the HPF is 1.0. The first can still saturate a little under
614 impulse conditions, and it might roll to 32768 and need clipping on sustained peak
615 level signals. However, the scale of such clipping is small, and the error due to
616 any saturation should not markedly affect the downstream processing. */
619 ec->tx_1 += -(ec->tx_1>>DC_LOG2BETA) + tmp - ec->tx_2;
620 tmp1 = ec->tx_1 >> 15;
621 if (tmp1 > 32767) tmp1 = 32767;
622 if (tmp1 < -32767) tmp1 = -32767;
629 EXPORT_SYMBOL_GPL(oslec_hpf_tx);
631 MODULE_LICENSE("GPL");
632 MODULE_AUTHOR("David Rowe");
633 MODULE_DESCRIPTION("Open Source Line Echo Canceller");
634 MODULE_VERSION("0.3.0");