Note: Descriptions are shown in the official language in which they were submitted.
CA 02314219 2006-02-28
TITLE OF THE INVENTION
ECHO CANCELLER HAVING IMPROVED NON-LINEAR
PROCESSOR
CROSS-REFERENCE TO RELATED APPLICATIONS
The following applications, filed on even date herewith, are referred to:
Canadian Patent Application No. 2,307,845, "Echo Canceller Employing Dual-H
Architecture Having Improved Coefficient Transfer"; Canadian Patent
Application
No. 2,307,653, "Echo Canceller Employing Dual-H Architecture Having
Improved Double-Talk Detection"; Canadian Patent Application No. 2,307,651,
"Echo Canceller Employing Dual-H Architecture Having Improve Non-Linear
Echo Path Detection"; Canadian Patent Application No. 2,307,657, "Echo
Canceller Employing Dual-H Architecture Having Variable Adaptive Gain
Settings"; Canadian Patent Application No. 2,307,678, "Echo Canceller
Employing Dual-H Architecture Having Split Adaptive Gain Settings."
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
-~-
BACKGROUND OF THE INVENTION
Long distance telephone facilities usually comprise four-wire transmission
circuits between switching offices in different local exchange areas, and two-
wire
circuits within each area connecting individual subscribers with the switchinQ
office.
A call between subscribers in different exchan-e areas is carried over a two-
wire
circuit in each of the areas and a four-wire circuit between the areas. with
conversion of speech energy between the two and four-wire circuits being
effected
bv hybrid circuits. Ideally, the hybrid circuit input ports perfectly match
the
impedances of the two and four-wire circuits, and its balanced network
impedance
perfectlv matches the impedance of the two-wire circuit. In this manner, the
sionals
transmitted from one exchange area to the other will not be reflected or
returned to
the one area as echo. Unfortunately, due to impedance differences which
inherently
exist between two and four-wire circuits, and because impedances must be
matched
at each frequency in the voice band, it is virtuallv impossible for a2iven
hvbrid
circuit to perfectiy match the impedances of anv particular two and four-wire
transmission circuit. Echo is, therefore. characteristically part of a lona
distance
telephone system.
Although undesirable, echo is tolerable in a telephone system so lona as the
time delay in the echo path is relatively short, for example, shorter than
about 40
milliseconds. However. lonQer echo delays can be distractina or utterlv
confusing
to a far end speaker, and to reduce the same to a tolerable level an echo
canceller
mav be used toward each of the path to cancel echo which otherwise would
return to
the far end speaker. As is known, echo cancellers monitor the signals on the
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
.i -
receive channel of a four-wire circuit and eenerate estimates of the actual
echos
expected to return over the transmit channel. The echo estimates are then
applied to
a subtractor circuit in the transmit channel to remove or at least reduce the
actual
echo.
In simplest form, generation of an echo estimate comprises obtaining
individual samples of the signal on the receive channel, convolving the
samples with
the impulse response of the system and then subtracting, at the appropriate
time, the
resulting products or echo estimates from the actual echo on the transmit
channel.
In actual practice generation of an echo estimate is not nearly so
straightforward.
Transmission circuits, except those which are purely resistive, exhibit an
impulse response that has amplitude and phase dispersive characteristics that
are
frequency dependent, since phase shift and amplitude attenuation vary with
frequency. To this end, a suitable known technique for aenerating an echo
estimate
contemplates manipulating representations of a plurality of samples of
siLynals which
cause the echo and samples of impulse responses of the svstem through a
convolution process to obtain an echo estimate which reasonablv represents the
actual echo expected on the echo path. One such system is illustrated in FIG.
1.
In the system illustrated in FIG. 1. a far end signal x from a remote
telephone system is received locally at line 10. As a result of the previously
noted
imperfections in the local system. a portion of the signal x is echoed back to
the
remote site at line 15 along with the sianal v from the local telephone
svstem. The
echo response is illustrated here as a siQnal s correspondinQ to the following
equation:
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PC"T/US98/24346
-4- _
s = z * h
where h is the impulse response of the echo characteristics. As such, the
signal
sent from the near end to the far end, absent echo cancellation, is the signal
y,
which is the sum of' the telephone sianal v and the echo signal s. This signal
is
illustrated as y at line 15 of FIG. 1.
To reduce and/or eliminate the echo signal component s from the signal y,
the system of FIG. l. uses ari echo canceller having an impulse response
filter h that
is the estimate of the impulse echo response h. As such, a further signal -
representing an estiinate of the echo sisznal s is generated by the echo
canceller in
accordance with the followinQ equation:
s = X * h
The echo cariceller subtracts the echo estimate signal s from the s4:ynal v to
Qenerate a siQnal e at line 2.0 that is returned to the far end telephone
system. The
signal e thus corresponds to the following equation:
e =s+l'-S ;Z: ly
As such. the signal returneci to the far end station is dominated by the
siQnal v of
the near end telephone system. As the echo impulse response h more closely
correlates to the actual echo response h, then s more closely approximates s
and
thus the magnitude of the echo signal component s on the signal e is more
substantially reduced.
The echo impulse response model h may be replaced bv an adaptive digital
filter havina an impulse response h. Generally, the tap coefficients for such
an
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCTIUS98/24346
-5
adaptive response filter are found usinLx a technique known as Normalized
Least
Mean Squares adaptation.
Although such an adaptive echo canceller architecture provides the echo
canceller with the ability to readily adapt to changes in the echo path
response h, it
is highly susceptible to aeneratinQ sub-optimal echo cancellation responses in
the
presence of double: talk" (a condition that occurs when both the speaker at
the far
end and the speakei- at the near end are speaking concurrently as determined
from
the viewpoint of the echo canceller).
To reduce this sensitivity to double-talk conditions, it has been suaQested to
use both a non-adaptive response and an adaptive response filter in a sinizle
echo
canceller. One such echo canceller is described in USPN 3,787,645, issued to
Ochiai et al on January 22, 1974. Such an echo canceller is now commonly
referred to as a dual.-H echo canceller.
Another problem confrontina echo canceller circuits is the possibility that
the
echo path response is non-linear. Such non-linear echo paths are often present
in,
for example, cellular telephone systems. The echo canceller must not only
detect
the non-linear echo response condition, it must also be able to reduce the
effects of
the non-linear response. The present inventors have recognized that the dual-H
architecture may itself be employed to assist in detecting a non-linear echo
path to
thereby signal the echo canceller of the condition so that the echo canceller
may
respond in the appropriate manner. Further. the effects of the non-linearities
are
substantially reduced using a unique non-linear processor. The non-linear
processor
counters echo due to non-liiiear echo paths. Further. it also eliminates
residual echo
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98l24346
-6-
due to limitations of' the system (e.g., quantization error) and minor
inhibitors (e.a.,
low levels of background noise).
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98124346
-7- _
BRIEF SUMMARY.OF THE INVENTION
A non-linear processor for use in an echo canceller is set forth. The non-
linear processor includes a center clipping digital filter receivincl, an echo
compensated signai. The non-linear processor provides a center clipped output
signal having non-linear thresholds at values of + T".,. and - T",.. The value
of Tõr
is dynamicallv dependent, at least in part, on echo return loss measurements.
To
limit the processor's susceptibility to corruption from double-talk
conditions. the
non-linear processor inhibits the dynamic setting of the T,,,= value when a
double-
talk condition is present. Additionally, or in the alternative, the non-linear
processor locks the value of the echo return loss measurement after a
predetermined
number of consecutive echo return loss measurements have values fallina within
a
predetermined range of one another. Such locking further reduces the
susceptibility
of the non-linear pi-ocessor to corruption from double-talk conditions.
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
-8-
BRIEF DESCRIPTION OF THE SEVERAL
V'IEWS OF THE DRAWINGS
Figure 1 is a block diagram of a conventional canceller.
Figure 2 is a schematic block diaaram of an echo canceller that operates in
accordance with one embodiment of the present invention.
Figure 3 is a flow chart illustratinQ one manner of carrvina out coefficient
transfers in accordance with one embodiment of the present invention.
Fiaure 4 is a flow chart illustratinQ a further manner of carryina out
coefficient transfers in accordance with a further embodiment of the present
invention.
Fi2ure 5 illustrates the input and output of a filter that may be used to
assist
in measurin2 transfer density.
Figure 6 illustrates one manner of implementing non-linear echo path
detection in the ectio canceller operations previously described in connection
with
Fieure 4.
Figure 7 illustrates tap coefficient time dispersion for the adaptive filter
when
responding to a linear echo path.
Figure 8 illustrates tap coefficient time dispersion for the adaptive filter
when
respondine to a non-linear echo path.
Fi2ure 9 illustrates one manner of implementina a non-linear detector using
time dispersion as applied to the echo canceller operations of Fiaure 4.
Figure 10 is a graph of an input siRnal to the output siQnal of one
embodiment of the non-linear processor.
SUBSTITUTE SHEET (RULE 25)
CA 02314219 2000-06-09
WO 99l26403 PCT/US98/24346
-9- _
Figures 11a and llb illustrate the response of the non-linear processor to
small signal and large signal inputs respectively.
Figure 12 illustrates various quantities from which T,,.= may be calculated.
Figure 13 illustrates one manner of implementin-2 a double talk detector in
the non-linear processor.
Figure 14 ilhlstrates a signal input e' and the corresponding output signals
from filters S,;L1 , and L of Figure 13.
Figure 15 illustrates one manner of implementing an echo canceller svstem
employing the preserit invention.
SUBSTtTUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCTIUS98/24346
10-
DETAILED DESCRIPTION OF THE INVENTION
Figure 2 illustrates one embodiment of a dual-h echo canceller suitable for
use in implementir,cg the present invention. As illustrated, the echo
canceller, shown
generally at 25. iricludes both a non-adaptive filter Iz and an adaptive
filter h to
model the echo response h. Each of the filters h and h are preferably
implemented as digital ftlters, such as finite impulse response (FIR) filters
comprising a plurality of taps each having a corresponding tap coefficient.
This
concept may be extended to IIR filters as well. If FIR filters are used. the
duration
of each of the FI:R filters should be sufficient to cover the duration of the
echo
response of the channel in which the echo canceller 25 is disposed.
The output of the rion-adaptive frlter h is available at the line 30 while the
output of the adaptive filte;r h is available at line 35. Each of the signals
at lines 30
and 35 are subtracted frorn the signal-plus-echo signal of line 40 to aenerate
echo
compensated signals at lir-es 50 and 55. respectively. A switch 45, preferably
a
software switch. rnay be used to selectively provide either the output signal
at the
line 50 or the output signal at line 55 to the echo canceller output at line
60. The
switch 45 may be; used to provide the echo compensation based on the h filter
during com=ergenc:e and then be switched to provide the echo compensation
based
on the h filter after coveraence. Further. the switch 45 is directed to
provide the
echo compensation based on the h filter in response to the detection of a
double-talk
condition.
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99126403 PCT/US98/24346
-11- _
A transfer controller 65 is used to transfer the tap coefficients of filter h
to
replace the tap coefficients of filter h. As illustrated, the transfer
controller 65 is
connected to receive a number of system input signals. Of particular import
with
respect to the present invention, the transfer controller 65 receives the
signal-plus-
echo response i= and each of the echo canceller signals c and e at lines 50
and 55,
respectively. The transfer controller 65 is preferably implemented in the
software
of one or more digital signal processors used to implement the echo canceller
25..
As noted above. the art is substantially deficient of teachings with respect
to
the manner in which and conditions under which a transfer of tap coefficients
from
h to h is to occur. The present inventors have implemented a new process and,
as
such, a new echo canceller in which tap coefficient transfers are only made by
the
transfer controller 65 when selected criterion are met. The resultin2 echo
canceller
25 has substantial advantages with respect to reduced double-talk sensitivity
and
increased double-talk detection capability. Further. it ensures a monotonic
improvement in the estimates h.
The foregoing system uses a parameter known as echo-return-loss-
enhancement (ERLE) to measure and keep track of system performance. Two
ERLE parameter values are used in the determination as to whether the transfer
controller 65 transfers the tap coefficients from li to 17 . The first
parameter. E, is
defined in the follolving manner:
L=
~
e
Similarly. the parameter E is defined as follows:
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
-12-
v
~
e
Each of the values E and E may also be averaged over a predetermined number of
samples to arrive at averaQed E and E values used in the svstem for the
transfer
determinations.
Figure 3 illustrates one manner of implementinQ the echo canceller 25 using -
the parameters E and E to control tap coefficients transfers between filter h
to h.
As illustrated, the echo canceller 25 provides a default h set of coefficients
at step
80 durina the initial portions of the call. After the tap coefficients values
for h
have been set, a rrieasure of E is made at step 85 to measure the performance
of the
tap coefficient values of filter h.
After the initialization sequence of steps 80 and 85, or concurrent therewith,
the echo canceller 25 begins and continues to adapt the coefficients of h to
more
adequately match the echo response h of the overall system. As noted in Figure
3.
this operation occurs at step 90. Preferably, the adaptation is made usina a
Normalized Least Mean Squares method. although other adaptive methods may also
be used (e.g., LMS and RLS).
After a period of time has elapsed, preferably. a predetermined minimum
period of time, the echo canceller 25 makes a nieasure of E at step 95.
Preferablv,
this measurement is an averaaed measurement. At step 100, the echo canceller
25
compares the value of E with the value of E. If the value of E is greater than
the
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98124346
-13-
value of E, the tap coefficients of filter h are transferred to replace the
tap
coefficients of filtei- h at step 105. If this criterion is not met. however,
the echo
canceller 25 will continue to adapt the coefficients of the adaptive filter Ir
at step
90, periodically measure the value of E at 95, and make the comparison of step
100
until the condition is met.
Although not illustrated. other transfer conditions may be imposed in
addition to the foregoing. For example, the echo canceller may impose a
requirement that a far end sianal exist before a transfer may occur.
Additionally,
transfers may be inhibited during a double-talk condition. Further conditions
may
also be imposed based on system requirements.
If the echo canceller 25 finds that E is greater than E- , the above-noted
transfer takes place. Additi:onaliv, the echo canceller 25 stores the value of
E as a
value Emax . This operation is depicted at step 110 of the Figure 3. The value
of
E ina, is thus the maximum value of ERLE that occurs over the duration of the
call
and at which a transfer has taken place. This further value is used
thereafter. in
addition to the E and E comparison, to control whether the tap coefficients of
h
are transferred by the transfer controller 65 to replace the tap coefficients
of 11 .
This further process is illustrated that steps 115. 120. and 125 of Figure 3.
In each
instance, the tap coefficient transfer only occurs when both of the following
two
conditions are met: 1) E is areater than the current E, and 2) E is greater
than
E. . Each time that both criteria are met, the transfer controller 65 of echo
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
-14-
canceller 25 executes the tap coefficient transfer and replaces the previous E
ma.
value with the current E value for future comparison.
Requiring that E be 2reater than any E value used over the course of the
call before the coefficient transfer takes place has two beneficial and
desirable
effects. First, each transfer is likely to replace the prior tap coefficients
of filter h
with a better estimate of the echo path response. Second. this transfer
requirement
increases the double-talk pr=otection of the echo canceller system. Although
it is
possible to have positive ERLE E during double-talk. the probabilitv that E is
2reater than Ei ,. durinQ double-talk decreases as the value of E,. increases.
Thus an undesirable coefficient transfer durina double-talk becomes
increasingly
unlikely as the value: of E iõix increases throughout the duration of the
call.
The echo canceller 25 may impose both an upper boundary and a lower
boundary on the value of Em,, For example. E,,,,, may have a lower bounded
value of 6 dB and an upper bounded value of 24 dB. The purpose of the lower
bound is to prevent normal transfers during double-talk conditions. It has
been
shown in simulations usinQ speech inputs that durina double-talk. a value of
areater
than 6 dB ERLE was a veiy low probability event. thus making it an appropriate
value for the initial value of E n,z. . The upper bound on Ei,,:,x is used to
prevent a
spuriouslv high measuremerlt from setting E -,a.\ to a value at which further
transfers
become impossible.
The value of E i,t,,. should be set to. for example. the lower bound value at
the beginning of each call. Failure to do so will prevent tap coefficient
transfers on
a new call until the echo cancellation response of the echo canceller 25 on
the new
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
- 15-
call surpasses the quality of the response existing at the end of the prior
call.
However, this criterion may never be met durin-2 the subsequent call thereby
causing the echo canceller 25 to operate using sub-optimal tap coefficients
values.
Resettina the E m,: value to a lower value increases the likelihood that a tap
coefficient transfer will take place and. thereby, assists in ensuring that
the li filter
uses tap coefficients for echo cancellation that more closely correspond to
the echo
path response of the new call.
One manner of implementing the E in,. value change is illustrated in the echo
canceller operations flow-chart of Figure 4. When all transfer conditions are
met
except E greater than E' m,. . and this condition persists for a predetermined
duration of time, the echo canceller 25 will reset the E m,. value to. for
example,
the lower bound value. In the exemplary operations shown in Figure 4, the echo
canceller 25 deterniines whether E is areater than the lower bound of E n,s,
at step
140 and less than the current value of Et,s,, at step 145. If both of these
conditions
remain true for a predetermined period of time as determined at step 150. and
all
other transfer criterion have been met. the echo canceller 25 resets the E m,c
value
to a lower value, for example, the lower bound of the E ,,,,, value, at step
155. This
lowerina of the Emax value increases the likelihood of a subsequent tap
coefficient
transfer .
Choosing values for the lower and upper bound of E,,,.,, other than 6 dB and
24 dB. respectively, is also possible in the present system. Choosing a lower
bound
of E m,, smaller than 6 dB provides for a relatively prompt tap coefficient
transfer
after a reset operation or a new call. but sacrifices some double-talk
protection. A
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
16-
value greater than 6 dB, however, inhibits tap coefficient transfer for a
longer
period of time, but increases the double-talk immunity of the echo canceller.
Similarly, varyina the value of the predetermined wait time T before which E
ma, is
reset may also be used to adjust echo canceller performance. A shorter
predetermined wait time T produces faster reconvergence transfers, but may
sacrifice some double-talk immunity. The opposite is true for larger
predetermined
wait time values.
A further modification of the foreQoinQ echo canceller system relates to the
value stored as E,,,ax at the instant of tap coefficient transfer. Instead of
setting
E ri.a, equal to the E value at the transfer instant. Emar may be set to a
value equal
to the value of E minus a constant value (e.g., one, three. or 6 dB). At no
time,
however. should the Et,,,, value be set to a value that is below the lower
bound
value for E rt,,. . Additionally, a further condition mav be imposed in that a
new
softened E max is not less than the prior value of E .n.. . The foreaoing
"softening"
of the Em,, value increases the number of transfers that occur and. further,
provides
more decision-making weiQht to the condition of E beinR larger than E.
As will be readilv recoanized. the echo canceller of the present invention
may be implemented in a'wide ranQe of manners. Preferably. the echo canceller
svstem is implemented usiria one or more digital siQnal processors to carrv
out the
filter and transfer operations. Digital-to-analog conversions of various
sianals are
carried out in accordance with known techniques for use by the digital signal
processors.
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98124346
-17-
There are some circumstances when the foregoing transfer criterion should
be defeated. For example. the transfer criterion is preferably defeated when
1) the
long-term ERLE remains low, and 2) a small but measurable performance
advantage
of h over h is sustained over a long period of time.
One case in which it should be defeated is when the steady-state ERLE
remains below the lower value of &,z.. . Such a case may occur when there is a
hiah-level. constanrt, background noise enterina from the near-end which may
lower
the measured ERLE considerably. Since the foregoinQ process prevents transfers
from occurring unless the ERLE is Lyreater than the lower bound of E ms. . no
transfers are possible in low ERLE situations. Since the h mav contain the
solution
to a previous call at the start of a new, low ERLE call, defeating the
foregoing
transfer criterion is preferable in some cases.
The first condition f'or defeating the foregoing transfer criterion is a
sustained
low ERLE measurement over a relatively long period of time (e.g., 150 to 500
msec) of adaptation. Since a fow ERLE call will tend to have a smaller
difference
between the ERLEs of h and h(a 1 dB difference may be the largest difference
observed), the required E= difference between h and h for a transfer to occur
should be reduced (e.g. to 0 or I dB) once the long-term ERLE is confirmed to
be
low. To compensate. a requirement may be imposed whereby the small ERLE
difference between h and h is maintained for a long period of time (e.g. 75 to
200
msec) before the tr=ansfer is allowed.
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2006-02-28
-18-
Each of the filters h and h preferably include one or more D.C. taps to
compensate for non-linearities in the echo path response. The result is that
the
filters can model a D.C. shift quite accurately, and high ERLE can be achieved
despite the presence of a D.C. non-linearity.
More complex non-linearities in the echo path response generally require
more complex non-linear processing. One manner in which the echo canceller 25
can process such non-linearities is set forth in Canadian Patent Application
No.
2,307,651, titled "Echo Canceller Employing Dual-H Architecture Having Split
Adaptive Gain Settings". A further manner in which the echo canceller may
compensate for non-linearities is by directing switch 45 to use the h filter
to cancel
the echo. This is due to the fact that the h filter is more time responsive to
the
non-linearities since the NLMS adaptation process attempts to find the best
short
term solutions for the non-linearities in the echo path so as to maximize ERLE
even where the short term solutions diverge from the long-term linear
response.
The present inventors have recognized that a difference in the number of
coefficient transfers from h to h occurs depending on whether or not the echo
path
has a non-linear component. When the echo path has an entirely linear
response,
the tap coefficients of h generally reflect the linear impulse response of the
echo
path. In a non-linear echo path having a non-linear residual echo signal, the
residual echo will tend to increase when compared to the linear response. In
an
attempt to reduce this residual echo, the tap coefficients of h move, for
short
periods of time, away from the linear impulse response to maximize the short-
term
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
- 19-ERLE. This occurs since the tap coefficients are adapted using a Least
Mean
Squares adaptation process which constantly tries to minimize the short term
ERLE.
As the non-linearity of the echo signal increases, the effect of the tap
coefficients
moving away from their original linear position to gain short term
improvements
becomes more pronounced.
For linear echo paths., the operational logic of the echo canceller 25 assumes
that a number of ti-ansfers will occur at the beginning of the call as the
echo
canceller 25 adjusts the tap,s to the model echo path response and transfers
that
model to the h filter. After the initial convergence period, the expected
number of
transfers per unit time will become small if the echo path is truly non-
linear.
Conversely, the best cancellation solution varies with time for non-linear
calls when
using a linear echo canceller. As a result, the non-adaptive taps of the h
filter
quickly become sub-optimal when compared to the E value of the h filter
response. For example. the h coefficients may become sub-optimal as compared
to
h within about 50 millisecor-ds. As a result. the transfer densitv. i.e. the
number of
transfers per unit time. becomes large and continues to stay large throuahout
the
entire call.
With fore2oina in mind, the echo canceller 25 measures the transfer density
after a converaence period to determine whether the echo path response is
linear or
non-linear. To this end, the echo canceller 25 is progranuned to store a
transfer
density threshold value TDT. The echo canceller 25 maintains a count of the
number of transfers TC that occur over a known period of time. This count is
compared to the transfer density threshold value TDT. If this count TC, and
thus
SUHSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99126403 PCT/US98/24346
-20-
the transfer density., exceeds the transfer density threshold value TDT, the
echo
canceller 25 declares the presence of a non-linear echo path response and
executes
the appropriate operations needed to cancel the echo signal. If the count TC,
and
thus the transfer deiisity, is below the threshold value TDT, the echo
canceller 25
handles the echo cancellation as a linear echo cancellation.
The value of TC may be calculated in a number of different manners. It
may be calculated using a software counter that is read on a predetermined
periodic
basis at intervals T and that it is reset immediately after being read. The
resultinc,
count may be directly used and compared to the transfer density threshold
value
TDT. In such instances, the value of the transfer density threshold value TDT
is
selected based on the period used to read the software counter.
In a more complicate:d process for determining the value of TC, the time at
which a software counter is read and the correspondina counter value are
stored in
memorv. Durina a subsequent reading of the counter value, both the counter
value
and the time at which the counter is subsequently read are noted. The value of
TC
may then be calculated as the difference between the initial and final counter
values
divided by the difference between the initial and final time values.
The value of'TC may also correspond to an averaaed transfer densitv value.
In such instances, the value TC mav be calculated using a diaital filter which
calculates a movina avera2e of the number of transfers per unit time. Such a
filter
preferably has, for example. a slow attack time constant and fast decay time
constant. although this is ncit mandatorv. A value of 1 is supplied to the
averagina
filter each tirne a transfer takes place during a frame having a predetermined
period.
SUBSTtTUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
-21 -
A value of 0 is supplied to the averaging filter each time a transfer does not
take
place durin, the frame. When the output of the averaQinQ filter exceeds the
threshold value TDV, a non-linear condition is declared.
Such a situation is ill'ustrated in Figure 5. As shown, a value of 1 is
applied
to the filter input during each frame in which a transfer has taken place. A
value of
0 is provided to the filter input if no transfer has taken place during the
frame. The
input value is illustrated at line 175 while the output value is illustrated
at line 180.
When this output value exceeds the threshold value TDV, designated at line
185. a
non-linear conditioii is declared. The foregoing filter configuration may be
implemented in hardware. However, it is preferably implemented in the software
of
one or more digital signal processors used to implement the echo canceller 25.
One manner of incorporating the foregoing threshold detection process in the
operations of the process of FiQure 4 is illustrated in Figure 6. As
illustrated, the
averaainR filter is notified at: step 190 that a transfer has taken place. The
resulting
filtered value is reti-ieved at. step 195 and compared to the threshold value
at step
200. If the threshold value TDV is exceeded, the Ema, value is checked at step
205
to ensure that it is above a threshold value (e.g.. 12dB) before a non-linear
echo
path condition is declared. l:f E,n,, is below this value. no such declaration
is made.
This check to ensure that the Em1 value is areater than a predetermined value
assists in ensuring that a non-linear echo path condition is not declared
durinz
periods of converaence and reconvergence of the adaptive filter. If Em,, is
above
this vaiue. a non-linear echo path response is declared at step 210.
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCTIUS98/24346
A further rnanner for detecting non-linearities usina one or more
characteristics of the filter h is illustrated in connection with Figures 7
and 8. In
accordance with this further rnanner, the time dispersion of the tap
coefficient values
is used to determine whether the echo path is linear or non-linear.
A graph of th.e tap coefficients of the h filter with respect to the time
delay
associated with each tap is illustrated in Fiaure 7 for a linear echo path
response.
As shown. the h response is comprised of a small number of larae maQnitude
taps
(shown here as those taps numbered 0 to 100) and many taps that are near 0
(shown
here as taps numbered 101 to 511). Other linear echo paths (zenerally yield
similar
results wherein a small percentaae of the total number of taps are used to
model the
echo response and a large number of taps have coefficients that are
approximately
equal to 0. As such, the h coefficients have a generally small time dispersion
value
(i.e., the majority of the ener=Qv of the h coefficients is confined to a
small window
of time).
FiQure 8 illustrates the coefficient values of ii when attemptinQ to model the
echo response of a rion-linear echo path. In this case. the ratio of the
number of
taps havina larQe tap coefficients to the number of taps havina low value tap
coefficients is not as large as it was in the iinear case of Figure 7. The
energy of
the taps of h is more wideiy dispersed amona the taps. The relatively lower
value
tap coefficients are much lar2er in the non-linear case since thev are playing
an
active role in findin; short-terzn solutions for cancelinQ the non-linear
components
of the echo. As such. the h coefficients have a aenerallv larQe time
dispersion
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98l24346
23 -
value when attempting to :model a non-linear echo path (i.e.. the tap energy
is
dispersed over a large number of taps).
In view of the foregoing characteristics recognized by the present inventors,
the echo canceller 25 calculates the time dispersion of the tap coefficients
of the h
filter to determine whether the echo path is linear or non-linear. The time
dispersion value is compared to a threshold. The threshold depends on the
method
of measuring the tirne dispersion and can be chosen experimentally. When the
time
dispersion value moves above the threshold. a non-linear echo path is
declared.
Otherwise, the echa path is assumed to be linear. Hysteresis can be used in
making
this determination.
The time dispersion value can be calculated in many ways. In accordance
with one manner, the echo canceller may find the inverse of the fraction of
the total
tap energy which can be attributed to the largest 111 taps, where iVI is a
small
number compared to the total number of taps in the h filter. In accordance
with a
further manner of calculating time dispersion. the echo canceller may measure
the
ratio of the L lowest tap coefficients to the number 1V of the largest tap
coefficients. However it is measured, the time dispersion will be larger for
non-
linear calls than for linear calls.
The time di<.;persion process of the echo canceller 25 can be auQmented with
a few other processes to improve its accuracy. For example, the echo canceller
25
may require that the time dispersion value remain above the threshold for a
predetermined period of time before a non-linear echo path is declared. Such a
requirement assists in preventing a period of converQence and reconverQence.
which
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2006-02-28
-24-
also might be characterized with large time dispersion values, from falsely
tripping
the non-linear detector process. Still further, the echo canceller may require
that a
measurement of the background noise be made prior to the declaring a non-
linear
echo path. High levels of background noise may increase the time dispersion
thereby causing a false indication of non-linearity. The echo canceller 25 may
be
programmed to require both a low background noise condition and a high time
dispersion value above the threshold before declaring the presence of a non-
linear
echo path.
One manner of implementing the time dispersion process in the process
shown in Figure 4 is illustrated in Figure 9.
When a non-linear echo path is detected, the echo canceller 25 preferably
enters a time varying mode. In this mode, the output decision logic is biased
to
use the h filter to compensate for the echo response. This may be
accomplished,
for example, by transferring switch 45 so that the h output is consistently
used for
the echo compensation. Alternatively, this bias may be accomplished by varying
the h to h transfer criterion discussed above so as to make the transfers more
likely
to occur. Additionally, the adaptation gain used to adapt the tap coefficients
of h
is preferably lowered so as to reduce the rate at which the tap coefficients
change
and prevent overshoot of short term solutions. Further, any split adaptation
of the
tap coefficients is inhibited in time varying mode. Such split adaptation is
shown
and described in Canadian Patent Application No. 2,307,845, titled "Echo
Canceller Employing Dual -H Architecture Having Split Adaptive Gain Settings,"
filed on even date herewith.
A further manner of detecting non-linearities based on the adapted
coefficients is to monitor the variance of each of the taps over time. A large
tap
CA 02314219 2006-02-28
-25-
variance indicates non-linearities while a low tap variance indicates a linear
echo
path response.
Irrespective of the manner used to declare the presence of a non-linear echo
path response in the channel, some manner of canceling non-linearities in the
echo
response is needed. To this end, the echo canceller 25 is provided with a non-
linear processor, shown generally at 300 of FIG. 2.
The NLP 300 works by reducing small input signals to zero while leaving
larger input signals relatively unchanged. To accomplish this, the NLP 300
includes a center clipping filter. To output of the NLP 300 as a function of
the
input thereto is illustrated in Figure 10. An input signal having an amplitude
less
than or greater than a calculated NLP threshold TNLP will be reduced to zero
at the
output of the NLP 300. Larger amplitude signals are modified only near their
zero
crossings. Alternatively, the NLP 300 may be designed in accordance with the
response of the non-linear processor of USPN 5,274,705, titled "Nonlinear
Processor for an Echo Canceller".
Figure 11a illustrates a small signal input to the NLP 300 at 305 and the
resulting output signal at 310. Similarly, Figure 1 lb illustrates a large
signal input
to the NLP 300 at 315 and the resulting output signals at 320. Note that the
resulting output signal is clipped at amplitudes between - TNLP and + TNLP.
To be generally effective, the NLP 300 should set TNLP larger than the
amount of non-cancellable echo. This provides the end user with the experience
of
CA 02314219 2000-06-09
WO 99/26403 PCTIUS98/24346
-26-
"echo-free" performance. However, the value of T,+=i.r should not be set to a
value
any greater than necessary so as to minimize distortion of larger sianals.
The value of T.w.r may be obtained by estimating the power of 6 e' from
measurable echo canceller quantities (note that G c' = powe(e' )). Such
quantities
are set forth in Fiaure 12 in connection with a standard linear echo
canceller. To
this end, the echo canceller 25 measures the power of the X, G x signal and
subtracts the difference in power across lines 340 from the measured
quantities
(e.g., the echo returri loss or "ERL"). The echo canceller 25 then subtracts
the
power decrease due to the echo canceller 25. which is ERLE, from the
calculated
difference. The result is an estimate of 6 e' , which is expressed as 6 e'
(note that
,
e' = pow(e)) far. This coi-responds to the following equations:
G ~,_ (assuminL v = O)
G 6
u i
ERL-' ERL-'
or in terms of dB
(in dB) = G (in dB - ERL (in dB) - ERLE (in dB)
e x
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2006-02-28
-27-
Once the estimate 6? has been made, the echo canceller 25 may then set
e
the value of TNCP equal to or slightly higher tha~ 6?. Assuming that TNLP is
set
e
to slightly overbound 62 , the far-end user should hear no residual echo with
e
only minimal distortion to the near end speech.
It is possible, but not necessary to use EMAX-' as an estimate of ERLE-' in
determining 6?. In calculating ERL , it is possible, but not necessary to
instead
e
calculate ERL using the following equation:
ERL = pow(x max) lpowty)
where x,,.x is the maximum value of x over the last L seconds, where L is a
constant.
- , will likely be
Measurements of ERL and ERLE and, thus, 62
e
erroneous if a double-talk condition exists when these measurements are taken.
During periods of double-talk, the measured ERLE -z~0 dB and the measured
ER.L is very small, perhaps :iegative. The resulting a ? would be much larger
e
than desired, thus setting TNLP too high and causing severe distortion cf the
near-
end speaker's voice as perceived at the far-end.
Steps are taken to ensure that the TNLP value is not modified during double-
talk. Preferably, double-talk detection is implemented in accordance with the
teachings of Canadian Patent Application No. 2,307,653, titled "Echo Canceller
Employing Dual-H Architecture Having Improved Double-Talk Detection," filed
on even
CA 02314219 2000-06-09 PCTIUS 4 3 4 6
r~
1PER'S r.ov 1999
12001 WO01 -28-
date herewith. Even more preferably, the double-talk detection is implemented
in
the manner set forth iri Figure 13.
The double-talk detector 400 compares long-term and short-term averages
of the error power. The long-term average is computed in such a way that it
can be
considered a steady-state measure of the residual error. When the short-term
measure of the error power noticeably exceeds the long term measure (e.g., by
3 or
6 dB), it is assumed that e' signal no longer contains only residual echo, but
in
addition, near-end speech. This event this triggers a double talk event.
As illustrated in Figure 13, the double-talk detector 400 employs at least
two measurements of the average echo power that are compared with one another
wherein each measurement corresponds to a different averaging time. In the
illustrated enibodiment, three measurements of the average echo power are
employed, ea.ch using a different window of time in which it performs its
averaging fuiiction. From an implementation standpoint, it is convenient to
translate these various averaging windows translate into longer time
constants. To
this end, the double-talk detector 400 errr..,ys a short time constant filter
S, a
medium time constant filter M, and a long time constant filter L.
The S filter simply uses a short time constant, e.g., 2 to 7 msec, to average
e' which is supplied at input line 405. The M filter uses a medium time
constant,
e.g., 12 to 36 msec, to average e'. The computation of L is slightly more
complex. In the illustrated embodiment, L aver3ges M, not e' directly. When
M<_ L, L averages M with a very long time constant (e.g., 500-2000 msec).
WEND'ED SHEET
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
-29-
When M< L, then L averages M with a much smaller time constant. The net
effect is that L and Ivi form a dual time constant. filter in which the output
of L
increases very slowly but decreases verv quicklv. The resultinQ filter is a
"slow
attack, fast decay" average of M.
Figure 14 illustrates a signal input e' and the corresponding output sianals
from filters S. iV1 , and L.'The output signals of filters S and L are
provided to
the input of comparator 410. The output of filter L serves to maintain the
lower
bound of e'. When the comparator 410 detects that the output signal of filter
S is
noticeably larger than the output signal of filter L. a double-talk condition
is
declared.
The foregoing double-talk detector is preferably implemented in software
code of one or more digital signal processors used to implement the echo
canceller
25. When a double-talk condition is declared, the T,,= value is preferably
locked
and no further modifications thereof are made until the double-talk condition
is no
lonoer present.
As noted above, the echo return loss ERL measurement is used to ultimately
arrive at a value for T,f.,= . However, this measurement may be significantly
corrupted during a double-talk condition thereby impacting the value of T",-.
To
further reduce the likelihood of such corruption, the non-linear processor 300
of the
echo canceller 25 preferably locks the ERL value without further calculation
thereof
once the processor 300 has determined that the ERL is at a generally static
value.
One method that may be used to measure ERL involves mappina the
measured value to a magnitucie in a look-up table. The maanitude of the x
sianal is
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98/24346
-30-
divided by the magnitude of the y signal. This ratio is then quantized to the
closest
member of a pre-defined set by way of the look-up table. For example, let the
pre-
~ ~
defined set by {0. 3, 6, 9. ..., 30} dB, and let 7.1 dB. Then the
x y
measured ERL wouici map to the set member 6 dB. On the next instance, let
~ _
6~/ 6 = 5.61 dB. This too would map to 6 dB.
x y
Now consider the situation where several consecutive amplitude ratios map
to the same value. If this continues for a period of time. the echo canceller
25 may
accept that the estimate of the ERL is valid for the remainder of the call.
Locking in
this estimate of ERL means that future instances of double-talk cannot corrupt
the
estimate of ERL, and thus TVLP is. less likely to be corrupted durina double-
talk.
To this end, a counter is incremented if the current table look-up produces
the same result as the previous look-up. This counter is cleared if any of the
following conditions occur: 1) a different look-up result occurs: 2) the far-
end goes
silent for a substantial period of time; 3) double-talk is detected (e. a. ,
by the
averaging filter comparison above); or 4) other conditions are detected that
will
likely skew the ERL rneasurement.
If the counter reaches a predetermined large value (e.g., 500 to 2000 msec),
an ERL Lock conditi.on is declared and the current ERL estimate is used
without
further look-ups or calculations thereof. The ERL Lock is lifted if an endpath
switch is detected by the echo canceller indicatina that a call has
terminated.
Figure 15 illustrates one embodiment of an echo canceller system, shown
aenerally at 700, that mavbe used to cancel echos in multi-channel
communication
SUBSTITUTE SHEET (RULE 26)
CA 02314219 2000-06-09
WO 99/26403 PCT/US98124346
-31 - _
transmissions. As illuistrated, the system 700 includes an input 705 that is
connected
to receive a multi-channel communications data, such as a T1 transmission. A
central controller 71C) deinterleaves the various channels of the transmission
and
provides them to respective convolution processors 715 over a data bus 720. It
is
within the convolution processors 715 that a majority of the foregoing
operations
take place. Each convolution processor 715 is designed to process at least one
channel of the transmission at: line 730. After each convolution processor 715
has
processed its respective channei(s), the resulting data is placed on the data
bus 720.
The central controller 710 multiplexes the data into the proper multichannel
format
(e.g., T1) for retransmission at line 735. User interface 740 is provided to
set
various user programunable parameters of the system.
Numerous modifications may be made to the foregoinQ system without
departing from the basic teachinas thereof. Although the present invention has
been
described in substantial detail with reference to one or more specific
embodiments,
those of skill in the art will recognize that changes may be made thereto
without
departing from the scope and spirit of the invention as set forth in the
appended
claims.
SUBSTITUTE SHEET (RULE 26)
