Recently I have been experimenting with two prototype echo canceller algorithms. This post describes the prototypes and results so far. This post is pretty hard core DSP – it may not be of interest unless you already have a fair idea of how echo cancellers work. I am writing it mainly to help me clear my own head on progress so far. Part 1 and Part 2 of this series provide a gentler introduction.
If anyone wants further explanation please feel free to post a question or email me directly. The code is available via SVN.
The G168 Standard
This was an excellent suggestion – thanks Steve. Steve also pointed me at a prototype echo canceller and code he has developed to test the echo canceller against the G168 requirements, part of his very impressive spandsp DSP library. So I have been working with Steve’s software, adding to the echo canceller code and automating some of the tests.
I have been using a simulation of the echo canceller rather than a real time implementation. This means that rather than talking into a telephone saying “1..2..3..” and listening for good/bad echo I am running a command line program that simulates the effect of the telephone hardware to generate and measure the echo. This makes it much easier to experiment – for example I can dump internal states of the code at any time and generates objective results with automated pass/fail results. Once I am happy with the non-real time simulation the idea is to run the same code in real time.
Here is a sample run of the simulation code:
Performing test 2A(a) - Convergence with NLP enabled
test model ERL time Max Rin Max Sin Max Sout Result
2aa 1 -10.0 11.20s -14.98 -24.55 -100.00 PASS
This means that for G168 test 2A part (a) with echo model 1 and an Echo Return Loss (ERL) of 10dB we passed. The Rin (Receive In), Sin (Send In), Sout (Send Out) ports are the signal levels on various ports of the echo canceller in dBm0. Sout = -100 dBm0 basically means the echo is at a very low level by the end of this test. Wish that were true for all tests
G168 has about 20 basic tests that are repeated with a bunch of different permutations. It specifies the types of signals used to test the echo canceller and the expected results. The standard is available for free download (I use the 2004 version). Steve had already implemented much of the test code – this has been very helpful. I have been concentrating on automating the tests and trying to get the prototype echo cancellers to pass.
The two prototypes vary in how they control adaption. One uses an innovation on the Geigel Double Talk Detection (DTD) algorithm suggested to me by Steve called Tap Rotation, the other a Dual Path method from an early paper by Ochiai which was kindly pointed out to me by Ramakrishnan Muthukrishnan.
Geigel & Tap Rotation
The Geigel part of straight out of the classic Messerschmitt paper from Texas Instruments. The tap rotation algorithm works like this:
- Instead of having one set of N filter taps we have three sets of N filter taps.
- Every 1600 samples (200ms), we rotate to the next bank of taps, for example if we are using set 2, we start using set 3. This gives us a record of the previous state of the filter taps, for example if we are using set 3 then set 1 will be the oldest set.
- If we detect double-talk (using the Geigel algorithm), we replace the current set of taps with the oldest set.
This algorithm protects us from failures of the Geigel DTD. For example it may take the Geigel DTD a few 10s of ms to detect double talk. In this time it is possible for the taps to diverge significantly. Tap rotation effectively tosses out the latest taps and replaces them with an older version, well before the DT started. This is like giving us 200-400ms of “pre-hangover” – we prevent adaption 200-400ms before DT. Combined with the hangover of the Geigel algorithm, it means we prevent adaption anywhere near the DT in both the positive and negative time directions.
Here is a plot of the algorithm in action (click for a larger version):
In the initial 5 second period the echo canceller is allowed to converge, then it gets blasted by high level near end speech for 5 seconds. Then there is a final 5 second segment where we look to see if the echo canceller has diverged. In this case it is doing a good job, you can see the echo level in the final 5 second section is similar to the first 5 second section.
The small green line at the bottom is the Double Talk Detector (DTD). You can see that it fires in the DT areas. On each “rising edge” of this signal the taps are reset to previous values.
As I have currently implemented it (and I freely admit I may have messed up somewhere), the Geigel/Tap Rotation Algorthim has a few problem areas:
- At low ERLs (e.g 6-8 dB) the DTD fires a lot, even when there isn’t double talk, as the high echo levels mimic near end speech. So we don’t converge fast enough in the 1s allowed for the convergence test.
- It struggles with near-end background noise (G168 Test 2c). The noise gets mistaken for near-end speech, and the taps get reset back to previous values all the time by the tap rotation logic. So it adapts very slowly and can’t converge within 1s.
- It also diverges a bit too much with low levels of near end speech (e.g. Test 3b part (b)) during double talk. It’s OK for double talk with high near end speech levels, such as the plot above (Test 3B part (a)).
Dual Path Algorithm
The second prototype has two filters to model the echo, a foreground and background filter. The background filter adapts continuously with only mininimal protection from double talk. When the background filter is performing better than the foreground, it’s taps are copied to the foreground filter. See the Ochiai paper for more information.
This algorithm passes the cases described above where the Giegel/Tap Rotation Algorithm is struggling. However it still fails several boundary cases like very low ERL & levels, but these fails are close calls (for example slightly slower convergence time than required) rather than complete failures of the algorithm.
For more information see the echo.c source code.
I have automated pass/fail evaluation of a 5 test subset of Steve’s G168 test code, here is a sample output:
test ERL Max Rin Max Sin Max Sgen Max Sout Result
2aa -10 -14.98 -24.55 -100.00 -100.00 PASS
2ca -10 -14.98 -24.55 -30.01 -31.97 PASS
3a -10 -14.98 -24.55 -29.87 -51.32 PASS
3ba -10 -14.98 -24.55 -14.86 -53.44 PASS
3bb -10 -14.98 -24.55 -20.86 -53.46 PASS
2a (a) Basic convergence test
2c (a) Convergence test with near end noise
3a Convergence test with low levels of near end speech
3b (a) Double talk divergence with high levels of near end speech
3b (b) Double talk divergence with low levels of near end speech
Rin (receive in) Sin (Send in) etc are the nomenclature used in G168. Sgen (Send generator) is the near end speech/noise signal. I have used some different names for the same signals in earlier posts, these two figures explain:
So in Test 2c (a) the maximum near end (Sgen) signal (which is noise in this case) was -30 dBm0. The maximum echo signal (Sin) was -24.55dBm0 when the system was driven by a -14.98dBm0 (Rin) signal. If you look at the difference between Sin & Rin the ERL is actually more like 9.57dB.
Many of the G168 tests are very similar, so I have built up a bunch of C code functions as a sort of “test language” to make life a bit easier:
print_title("Performing test 2A(a)\n");
/* initial zero input as reqd by G168 */
/* Now test convergence */
The Octave script echo_dump.m is used to plot internal states of the echo canceller – this is really helpful in letting me drill down to the problems in the algorithm.
Testing on Real World Signals
The G168 tests are conducted with synthetic speech signals. As a sanity check I have run the two prototypes with echo signals sampled from a real phone line:
The canceller takes a little longer to converge in this case, as the speech segments “1..2..3..4” are short followed by long-ish pauses. However you can see that the echo (blue line) is removed.
You can even listen to the output. This is the echo signal before cancellation, this is the signal after cancellation using the Dual Path algorithm. You can hear the echo signal gradually decreasing as the canceller converges. It would be nice to speed up convergence – an ideal echo canceller would cancel almost immediately and the “after cancellation” file would just contain silence.
Next Steps and Help Wanted
I am enouraged by the progress so far, however there is still plenty to do:
- Test in real time on x86 and Blackfin. This is the reason for all this work in the first place. All I really want is to connect my shiny new embedded IP-PBX up to a FXO line without echo!
- Lots more G168 tests to implement and automate.
- Chase down current fail cases.
- Convert some float code to fixed point.Done
- Convert NLP to use comfort noise rather than muting.
- Make the canceller and sampling software hardware-agnostic. For Asterisk it should really integrate with Zaptel rather than the hardware driver.
- Implement algorithms to provide robustness (non divergence) with tones. I am not sure if this feature is strictly needed for my application (FXO port for an IP-PBX) but robustness for narrow band signals is required for G168 compliance.
- It would be interesting to run some other open source echo canceller algorithms through the G168 test framework. For example there are several echo cancellers in Zaptel, and Jean-Marc Valin’s acoustic echo canceller used in Speex.
Anyway if you are interested in working on an open source echo canceller you are very welcome to help out. Just send me an email. A lot of this work doesn’t require specialised DSP skills (for example integration and testing in real time on an x86 Asterisk system), so there is something here for everyone. Due to the automated tests, this project would also make a great project for learning DSP and echo cancellation – if you make an error the tests will let you know.
The core echo canceller development is tough and challenging work! As I suspected So after hammering away for the last few weeks I felt a bit stale and took a few days off to go camping with my kids. We went to the Murray River National Park, about 180km from were I live in Adelaide, South Australia. I now feel a little more balanced, amazing what a few days off can do!
As a next step I might do some real time testing, just to make sure I haven’t missed anything obvious with the G168 tests. My first milestone is a “workable” echo can for my home phone (FXO) line, I should be getting close now I think
Thanks to Steve Underwood for all the excellent spandsp code he has written, and to Steve, Jean-Marc Valin, and Ramakrishnan Muthukrishnan for their comments and help with this work.
The Open Source Line Echo Canceller (Oslec) has progressed a great deal since this initial (Part 1) post was written:
Oslec Home Page
Part 1 – Introduction
Part 2 – How Echo Cancellers Work
Part 3 – Two Prototypes
Part 4 – First Calls
Part 5 – Ready for Beta Testing
Geschichten Interrassisch Sex HahnereiMÃ¤dchen Russisch Behaarteteen pics ass Kostenlos minderjÃ¤hrigePissing DemÃ¼tigunghentai Ãœbersetzt Comicsinterrassisch Alexandra nice pornheiÃŸen Freunde Meine cee mrs momkostenlos pics Russisch nudeNackt Desi babesOutdoor peeing Verzweifeltenentertainment absolute barringtonringtone to v170 motorola phone addringtones alcatel in fijikyocera ringtones slider remix addtimes amc barrington movietheater barrington amcalexis harringtonorrington s 80 me Mapaccredited loans education distanceloan acoustic homeby consolidation administered loansfor affordable loans studentsmember family agreement loan formloans grants agriculture youngair consolidation debt travel loan tipadvance alabama and loans cash payday Maprich credit american commercial services adamscolorado accreditationcorrespondence colleges accreditedaccreditation center childcarecard offers credit adhesivecapital credit one activateaccreditation of in usa the universitiesaccredited articles health Mapachat mp3 fi chaine hifool mp3 actamp3 brasil ache paranaueachha mp3 jiacting mp3 tipsachhe mp3 lagtemp3 mefaridze achidoar tine activ mp3 cu Mapsample movie lesbianmovies hardcoregirls ebony movies buttsybian clips moviehomemade sex moviesmovie stars nudemovie samples hot xxxhandjob movies free Maptorrent porn bit sitesat work pornsite bitchesbiting pornpirates porn bittorentporn and bittorrentbittorrent search porntrailers bizar pornbizarre adult pornography Map