Note: Descriptions are shown in the official language in which they were submitted.
08~Sl : ~
This is a division of Canadian Patent Application -
Serial No. 280,166, Filed June 9, 1977.
~'
BACKGROUND OF THE INVENTION :
The present invention is in the field of echo
cancellers and in particular is an improved echo canceller
, . - .
using a logarithmic format to simplify the hardware of the ;
canceller.
It is well known that hybrid circuits connecting
two-wire to four-wire circuits in long distance communications
networks do not provide echo free coupling between the send
and receive lines of the four-wire circuit. A portion of
the signal on the received line will pass to the send line
and appear as a echo signal. When the four-wire system is
used for very long distance communication, the echo signal
can be particularly disturbing.
For round trip, delays (tRD) encountered, e,g., in
east to west coast connections (tRD ~ 70 ms~ or satellite
communications (tRD ~ 500 ms), an additional echo suppressing
and/or cancelling device becomes a necessity for commercial
use. Therefore, in the last 45 years considerable research ;
.:
bm~
. ~ .
51
" .
and development effort has been spent on designing the
so-called echo suppressors, The echo suppressors are
relatively simple electro~lechanical or electronic voice
activated switches which disconnect the echo path according
to the direction of the signal in the 4-wire section.
In spite of great improvements in echo suppression
technique and technology, these devices can fail to provide
adequate quality for 2-way communication mainly under the
following adverse conditions:
(a) when both parties are trying to talk
simultaneously, i.e,, during the so-called
double talk period;
(b) when there is a substantial difference in the
sent-out signal level between the two
communicating telephone sets assuming nominal
loss in the circuit otherwise;
(c) when the echo return loss is less than 9dB.
All of these conditions increase their adverse effects with
increasing round trip delay, not only because of the long
propagation time between communicating parties but also
because the long round trip delay connection usually
interconnects two telephone networks built and maintained by
different standards where the average echo return loss ~HL
and standard deviation of this loss ~HL have different, ; -~
usually less favorable, values than U.S. networks.
bm: ~~
' ,' -:
- '' ' . .
: : . , . - , . ... . .
-: . . . , .:.. : .
1~81851
. . ' '
In order to overcome these problems, an "echo
canceller" was originally suggested by J.L. Kelly, Jr., and
the implementation of this idea is described in an article by
M.J. Sondhi, "An Adaptive Echo Canceller", Bell System Tech-
nical Journal, Volume 46, No. 3, March 1967, pp. 497 to 511.
This particular design uses an analog technique, in other words,
an analog delay line develops a replica of the echo
signal which is then subtracted from the received signal.
However, analog delay lines are difficult to implement where
roudtrip delays of several tens of milliseconds are involved.
The problem associated with the analog techniques
were overcome by the so-called digital "echo canceller" using
digital techniques inside the operational loop. This design
was described in an article by S.J. Campanella et al, "Analysis
of an Adaptive Impulse Response Echo Canceller", COMSAT Tech-
nical Review, Volume 2, No. 1, Spring 1972, pp. 1 to 38.
While the basic approach of the digital echo canceller is sound,
it is a highly complex and very expensive system. The principle
reason for the complexity and high cost of the digital echo
canceller is the broad dynamic range of the speech and the
long roundtrip delay 2tE between the hybrid and the echo cancelling
device. For acceptable results with different levels of
signals, the speech must be sampled, quantized and processed with
11 to 12 bits of precision. The delay of echo 2tE in some
telephone networks can ~e as long as 50 milliseconds. With 8KHz
sampling rates, the digital echo canceller must therefore be able
to store lK to 2K bytes and process these bytes in parallel
with a clock rate greater than 3MHz. As a result, the
digital echo canceller is nearly two orders of magnitude more
-4-
~(381~Sl
-
complicated (and expensive) than the most sophisticated echo
suppressor.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention
to simplify the hardware required in e~ho cancellers while
at the same time retaining the advantages of the digital
approach.
It is more specifically an object of the invention
to redesign the digital echo canceller so that its complexity,
size and cost are at least comparable to those of echo
suppressors.
These and other objects of the invention are
achieved by:
(a) The signal in receive and send paths is
processed analogically in order not to restrain
the choice of the canceller's internal digitial
code.
(b) The speech and pulse response samples are
encoded in pseudologarithmic format in order
to save memory space. An analog-to-digital
converter for direct conversion in nonlinear
code is used.
(c) The multiplication in the convolution processor
is performed as an addition of the logarithms
(base 2) of speech and impulse response samples.
(d) In the cross-correlation processor, the impulse
response is updated by multiplication by a
constant instead of by addition of an increment.
This fast converging algorithm simplifies the
design of the error detector and makes the
canceller less sensitive to "phase roll" and
difficult "double talk" condition.
-5-
bm:~
-
.
.. : . :` .. . : , ::
8185~
(e~ The cross-correlator's feedback loop is stablized
by nonlinear damping and by adapting the sensitivity
of the error detector to varying signal conditions.
(f) The residual echo signal is removed by a continuously
adaptive center clipper with distortion reduced
below the detectable level.
(g) The difficult problem of the digital-to-analog
cross-talk is solved by dividing every convolution
cycle lnto analog and digital pêriods. ~-
More specifically, the speech samples xi are encoded
in a quasi-logarithmic format. ~he 7-digit A-law encoding is
chosen. A description of the A-law encoding is provided on
pages 579 to 583 of Transmissions Systems for Communications,
Fourth Edition, published by Bell Telephone Laboratories, Inc.,
February 1970. This digital format gives an adequate signal-to-
noise ratio (better than 30dB) in a dynamic range of 40dB and
saves approximately 35 percent of the X-register size in com-
parison to an ll-bit linear code necessary for the same signal-
to-noise ratio. The H-register word is stored also in a quasi-
logarithmic format with a 3-bit exponent and a 4-bit mantissa.
With the sign bit, the hi word is 8-bits long, which represents
a 27 percent reduction of H-register size. The greatest hard-
ware saving,however, is achieved in the multiplier design~
Because both xi words and hi words are in the logarithmic format,
the multiplication xi hi is performed as the addition of
log2(xi) + log2(hi). The large ll-bit by ll~bit:parallel
multiplier normally used in digital echo cancellers is thus
replaced by an adder. I~ew algorithms are used for the
" '~
-6- `
, :
- . - ~ , ;
''. ' ' ' . , .' ' . . :
851
computation of an average or pseudo rms value of speech samples
Xi stored in the X-register. In one er~odiment, an average
value is computed; however, instead of adding all absolute values
of the stored samples Xi every sampling period, the oldest
sample is subtracted and then a new sample ¦xi~n~l¦ is used to
update the existing contents of the average value memory. Thus,
the number of additions in every sampling period is reduced
making it possible to use relatively simple circuitry. Alter-
natively, a pseudo rms value is generated by adding only the
absolute value of samples ¦xi~jl which are greater than a certain
threshold to the contents of a pseudo rms memory. In this
manner, the number of bits in the rms processor is reduced, and
the parallel 16-bit adder-accumulator normally used for this
prupose in digital echo cancellers can be replaced by a simple ;
adder and overflow counter.
Analog subtraction of simulated (i.e., computed) echo
is used in the return path, and also analog comparators are
used for ~h correction instead of digital circuits. With in-
expensive integrated circuit operational amplifiers ana com-
parators, this technique not only simplifies the circuit by
eliminating one analog-to-digital converter and one digital-to- ;
analog converter in the canceller, but also eliminates quan-
tization noise and distortion in the return signal path. The
digital signal is used only inside the echo canceller processor
and does not need to be in compliance with different voice channels
standards as, for example, A-law which is standardized by C.C.I R.
while another companding characteristic, the so-called ~-law,
has been chosen by the Bell System.
-7-
- .
8~851
The e~ficiency of the echo canceller can be
substantially improved by the use of a so-called adaptive
center clipper in the return path. By using the adaptive
center clipper and a pre-emphasis and de-emphasis technique,
the distortion introduced by the center clipper can be
substantially reduced. A~simple hybrid analog-digital
circuit permits automatic adjustment of the clipping level
to the optimum value in accordance with the echo producing
signal level.
- 10 One aspect of the present invention relates to
the afore generally described digital echo canceller.
Another aspect of the persent invention is directed to a
pseudo rms value circuit comprising: meanæ for receiving
a plurality of digital signals, a pseudo rms value register,
accumulator means for adding and accumulating each digital
signal having a value exceeding a predetermined absolute
value, and counter means connected to count the overflows
from the accumulator means, the contents of the counter
means being stored in the pseudo rms value register.
~ -8-
bm:p
,
' ` : :
~L081851
.. ,'. .. '
BRIEF DESCRIPTION OF THE DE~AWINGS
.~ .
The specific nature of the invention, as well as . . .
other objects, aspects, uses and advantages thereof.will ~..... .
clearly appear from the following description and from the ; : ..
accompanying drawing in which: -
Figure 1 is a system diagram of the present state of .
the art of digital echo cancellers; . .. :.;
Figure 2 is a system diagram of the logarithmic :~
echo canceller according to the present invention;
Figure 3 is a block diagram of the convolution processor
used in the system shown in Figure 2; . .
Figure 4 is a block diagram of the average value pro- :
cessor which may be us~d in the cross-correlator of one embodiment
: of the system shown in Figure 2;
Figures S and 6 are graphs showing the approximations ::.
of y=X2 and z- ~ , respectively, used in the digital root mean .
square processor according to an alternative embodiment of the
invention; and . :, :
Figure 7 is a block diagram of the digital root mean .. :
square processor which forms part of the cross-correlator used
..
'~' . ,', ' .,
: :.''' .
. -.
- 8a - `
'.'
.~
. . ,.. , . .. . . . ~ .
-''
, . ~ ,. , .. : . , .. ~ . - . .
51
:
in the alternative embodiment of the system shown in Figure
2.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
Referring first to Figure 1 which illustrates the
present state of the art of hardware implementation in digital
echo cancellers, the incoming telephone signal X(t) is
amplified in a switched compressor amplifier 102 in order to
adjust the signal level and protect the system from overload-
ing. The output of amplifier 102 is applied on the one hand
via blocking amplifier 101 to the input of 4-wire to 2-wire
hybrid 103, and on the other hand to the input of sample and
hold cixcuit 104. The output of the sample and hold circuit
104 X(iT) is converted into an ll-bit digital code by the
analog-to-digital converter 105. The ll-bit code includes
one sign bit and 10 bits of amplitude. The ll-bit conversion
is necessary to cover the 40dB dynamic range of the input
telephone signal with acceptable signal to quantization noise
ratio. The digital sample Xn+l is multiplexed in a
multiplexer 106 and then retained in the X-register 107. The
X-register must be able to store n x ll-bits, where n is a
function of the expected delay of the telephone circuit and
of the sampling frequency of the sample and hold circuit 104,
Usually the number n is in the range of 100 < n < 500 for
8kHz (125 ~s) sampling rate. As it has been explained in the
article by S.J. Campanella et al, supra, every ll-bit sample
must be multiplied by one of the h coefficients stored in the
H-register 108 during every sampling period, For this
purpose, a parallel multiplier 109 capable of multiplying
ll-bits by ll-bits must be used.
_g_
bm:f~
.
~l0~31851
The products hi xi+j are added with the proper sign
in the accumulator 110 which must have a capacity of at least
20+tl+1Og2n] bits. The sum of the products is then divided by
n, and another ll-bit word representing the predicted echo
sample is stored in the register 111. The multiplier 109 and ~
the accumulator 110 form the convolution processor of the~. :
digital echo canceller. The echo signal is also sampled in the
sample and hold circuit 112 which is connected to an output
of the 4-wire to 2-wire hybrid 103. The echo signal sampled by :
the sample and hold circuit 112 is converted to an ll~bit
digital code in the analog-to-digital converter 113, and this
ll-bit code is subtracted in the subtractor 114 from the pre-
dicted echo sample from register 111. The difference ~j is
converted to an analog signal E(t) by the digital-to-analog :
converter ll5 to drive the return line by an analog voice
signal. :
By digital cross-correlation techniques, the contents
of the H-register 108 are continuously updated. The absolute
values of the digital signal from the analog-to-digital con-
. verter 105 via the multiplexer 106 are added to the contentsof the accumulator 116 which must have a capacity of lO~[l~log2n]
bits. This sum is divided by n in the divider 117, and this
average value of the n samples of the signal X(t) is stored
. in a 10-bit memory 118. ~very sample in the X-register 107. ~.
is compared in a digital comparator ll9-against the average
value stored in the memory 118, and from the process a binary
correction signal ~i is determined. This signal commands the --
continuous updating process of the contents of the H-register
--10--
`
~8185
108 ~y adding or subtracting in adder/subtractor 120 a 3-bit
signal ~h to dif~erent coefficients hi. The ~h signal is
generated in an ll-bit digital comparator 121 which receives
the output ~j of subtractor 114.
The theory of the operation of the digital echo ~'
canceller will now be described. The H-register 108 stores n
samples, hi, of the unit impulses echo response in digital form.
The X-register 107 stores n ,recent speech samples, xi~j, from -
the analog-to-digital converter 105. During the jth sampling
period the jth estimate of the echo rj is computed in the con-
vo~ution processor: -
.. .
m
r~ 0 hi xi+j = h~ x(j) (1)
`3 This estimate is subtracted from the true echo yj, and at the ,
; output of the subtractor 114 there is an error signal, i.e.,
a residual echo, ,~
= yj - rj (2)
, The residual echo j iS detected-and nonlinearly ~uantized into '
'~ , Q(~j); a correction ~hi j for eve~y sample hi is computed by
, using a modified Widrow-Hoff least mean-square (LMS) algorithm:
- i,j Qt~j)f ¦ ~ ¦ = Q(~j) Sg(x~ j)~i j (3)
,' , whexe
~i+j = for ¦xi+j¦ c X
~i+j = 1 for ¦xi+j¦ ~ Xj
Sg(xi+j) is the sign of the xi+; and Xj is a guantity propo~rtional
to the rms value of the'n recent speech signal samples:
'
--11--
~81~51 ~ ~
.. ..
X; ~ o xi+i (4)
The correction ~hi j is added with the proper sign to every
corresponding sample hi so that its new value is
; i i,j (5)
.:
These updated values of h' as used to compute the next (j~l)th
estimate rj~l for a new set of xi~j~l samples of speech. The
new error value ~j+l is then used to compute another set of
corrections ~hi j+l By using this simple interactive correla-
tion process, the impulse response is built up in the H-
register and continuously updated when changes occur.
Campanella et al and Widrow have shown that this algorithm is
converge~t, i.e., Ej ~ O by the method of steepest descent,
and they have derived the stability criteria of this process.
i Under the worst case condition, i.e., for the "hybrid's"
echo return loss < 5 dB, the digital echo canceller must
attenuate the incoming echo signal yj by more than 26 dB to
achieve the reguired loss~ ~RL > 30 dB. This means that the
relative value of error signal according to Equation (2) must be
, .
< 0.05 < 2-4 (6)
Both hi and xi~j samples must therefore be quantized
with > 6-bit precision. However, the dynamic range of the speech
is about 40 dB and the amplitude range of the impulse response
is the same as the possible range of echo return loss, i.e.,
> 24 dB. Therefore, to obtain the required echo attentuation
in the whole dynamic range, the quantization of spcech samples
xi+j must be 12-bits, and ~he quantization of impulse response
samples hi must be at least 9-bits.
-12-
81~Sl
. ~:
The delay tE in the 4-wire section between the
; hybrid and the echo canceller is usually in the range of 0
< tE ~ 16 ms; the impulse reponse can therefore be delayed
as much as 2tE = 32 ms. For telephone speech, a sample
period TS ~ 125 ~s must be used. To cover the possible
range of delays at least n samples, where
n > E = 3225 = 256 (7)
must be stored in the H- and X-registers~ i.e., 256 x (12+9) -
= 5376 bits.
To compute the echo estimate rj according to
Equation (1), 256 multiplications and 256 additions of those ~-
products must therefore be performed during every sampl ng
period TS = 125 ~s. This requires parallel processing in the
multiplier which represents twith the memories) the greatest
part of the hardware and therefore the cost of the digital
echo canceller.
In the present invention~ the following steps have
been taken to reduce the hardware complexity:
(a) In both the receive- and send-paths the signals
are processed analogically; then the choice of
an internal digital code for the digital echo
canceller is not limited by any communications
network standards.
tb) The speech samples xi+j are encoded in the 13-
segment pseudo-logarithmic 7-bit format (A-law)
which has the same minimum resolution and
dynamic range as an ll-bit linear code. The
impulse response samples hi are encoded in a
similar ll-segment format by 8-bits, which is
equivalent to a 10-bi~ linear code, This
coding saves more
-13-
bm i,l~
~ ~ 1851 :: ~
than 28 percent of the memory space.
(c) With both samples xi+j and hi in a logarithmic
format, the multiplication of xi+j hi in the
convolution processor (see Equation 1) is performed
as an addition of the logarithms of xi+j and hi.
- Thus, the whole multiplication is performed by
two 4-bit adders, a 512-bit ROM and a 4-bit
multiplexer. This reduces the component count of
the convolution processor to less than one-tenth.
(d) The logarithmic code permits a simple implementation
of a new fast adaptive cross-oorrelation algorithm. The existing
! impulse response samples hi are updated by multi- -
' plication by a constant <1 or >1, in contrast to
~.
what was done previously by addition of ahi j
according to Equation (5), i.e., the Widrow-Hoff
algorithm. The impulse response buildup time in the
.
i~ H-register is thus less dependent on the absolute -
value of samples ¦hi¦ than with all other algorithms.
(e) The fast convergence makes the present desiqn less
sensitive to the so-called "phase-roll" in the echo
path than echo cancellers using much more sophisti-
cated and "expensive" cross-correlation algorithms~
~; The performance is even comparable to that of
devices using the so-called double convolution. .~' '.!1
~; ~f) The xapid hi buildup time also simplifies the design
;j . . .
of the double-talk detector because a partially
distorted impulse response hi can be corrected in a
few milliseconds, e.g., during the shortest period
- . :.
;. :
-14-
.
.', ' ""'' .
1~818Sl
of "single talk". The affirmative "yeah" is
usually sufficient to fully regenerate the distorted
impulse response.
(g) In one embodiment, a new algorithm is used for the
computation of the average value of speech samples
Xi stored in the X-register. ~1
(h~ In an alternative embodiment, the pseudo-rms value
Xj of the stored speech samples is computed simply
by counting the number of overflows of a 4-bit
accumulator with carryout.
(i) The value Xj is also used as a reference voltage
for the adaptive center clipper which further re-
~ duces the residual echo signal ~j below the system
i noise level.
(j) Xj is also used as a reference in the error sensorto adjust its sensitivity. This and nonlinear
damping" by a digital "inert zone" have made it
possible to increase the gain in the correlation
` feedback loop while retaining the utmost circuit
' simplicity.
lk) Last, but not least, a careful study has been made
to determine which operations are more effectively
done digitally and which analogically and the
- methods have been chosen accordingly. Such a
"hybrid" system is always sensitive to crosstalk
between the digital part with pulses having amplitudes
of several volts and between the analog part with
millivolt signals. The sampling interval, TS = 125 ~s~
is thcrefore time-shared; all digital operations arc
-
--15--
,
: . ,.............. '; : :~
performed, for example, in the first 100 ~s; then
-the clock is stopped and within the remaining 25 ~s
all analog processing takes place. This makes it
possible for both parts of the system to work with-
out interference and elaborate shielding.
;~ In spite of all these simplifications, the digital echo
canceller according to the invention, attenuates the echo signal
by ~22 dB without the center clipper. With the center clipper,
an additional attentuation of >8 dB is achieved; i.e.,
0-03 (8
'
(see Equation (6) for comparison). The convergence time of ~j
is always shorter than 250-ms. These properties are practically
invariant over the dynamic range of ~28 dB and under a "phase-
.~ roll" of 6 radians/s.
; The echo canceller according to the present invention
is illustrated in Figure 2 and represents a considerable savings
in hardware while at the same time retaining the advantages of -~
the digital echo canceller. The incoming voice signal is passed
- through an amplifier 201 with switched compressor-which attenuates
strong signals which can cause overload in the echo canceller
processing-loop. The blocking amplifier 202 assures unidirectivity
of the signal as previously described.
The incoming signal is sampled in a sample and hold
circuit 203. The sign of the signal Sg(xi) is sensed and the
absolute value ¦x(i'l')¦ of the signal is converted directly in a
special analog-to-digital converter 20~ into a compandea A-law
signal with 3 bit exponent and 3 bit mantissa, corresponding
~-to a 13 segment A-law curve. The A-law format has the advantage
. .
.
, ' - . ' -
:
~8~851
that it can be very sirnply converted to logarithms mod. 2 and
to the linear ll-bit format. The whole digitized sample x
is multiplexed in multiplexer 205 and then stored in seven
parallel connected n bit shift registers 206. These shift
registers constitute the X-register. The register length n
must ~e 200 < n < 520 bits long, the exact ~alue of n being a
function of the expected delay 2tE in the telephone circuit.
As in the digital echo canceller shown in Figure 1, the
latest samples are used to update the contents of the average
value or pseudo rms value stored in processor 207. The contents
of register 206 is compared with the value stored in processor
207 in a digital comparator 208 which generates a control signal
~j to control adder/subtractor 209 in the impulse function
correction process. This process will be described in more detail
hereinafter. The value stored in processor 207 is also converted
in a digital~to-analog converter 210 into a reference voltage
used to bias the adaptive analog center clipper 211 and the
analog comparator 212. A bandpass filter 213 and a pre-emphasis
circuit 214 are connected in series at the input of the center
clipper 211, while a de-emphasis circuit 215 is connected to
the output of the adaptive center clipper 211. The bandpass
filter 213, the pre-emphasis circuit 214, and the de-emphasis
circuit 215 reduce the harmonic distortion caused by the center
clipper 211 and linearize the frequency characteristic of the
return pat:h to a prescribed value.
The samples xi and hi stored in the X~register 206
and the H-register 216, respectively, are fed into a logarithmic
multiplier ~17. In order to use the ~-law encoded xi and hi values
-17-
8~851
directly without further A-law/linear conversion, the
multiplication is performed in three different ways
corresponding to the three possible conditions of the
exponents as being zero or non-zero. When both exponents
are zero, the mantissas are directly multiplied in a
multiplier. In the case when both exponents are non-zero,
addition of exponents e and mantissas m in two adders takes
-place and output of the mantissa adder is multiplied by 2e in
the multiplier. When one exponent is non-zero and the other
exponent is zero, both mantissas are directly multiplied in
the multiplier and the mantissa having the zero exponent is
added to the partial product output of the multiplier. This
rather complicated algorithm, which will be explained in more
detail with reference to Figure 3, makes it possible to
implement the multiplier with a minimum number of commerically
standard integrated circuits. The result hi x xi+j from
logarithmic multiplier 217 is then added to or subtracted from
the contents of a 20-bit accumulator 218. The multiplier and
the accumulator together form the convolution processor for 20 computing an estimate of the echo. Eleven most significant
bits plus sign bits are then converted in a digital-to-analog
.
converter 219 into an analog voltage which is subtracted in a -
differential amplifier 220 from the echo signal at the output
branch of the 4-wire to 2-wire hybrid 221.
The analog difference voltage from the differential ;
amplifier 220 is sampled in sample and hold circuit 222, and
this difference voltage is compared against the reference VREF
by a group of analog comparators 212. From the state of the
digital output of the analog
" .
-18-
bm:p~
. - . . . . .
~, '' ' , :` .
~ 818S~
:
~ comparators and from the sign Sg(xi) of the corresponding
.' sample xi, the sign Sg(~H) an'd the correction signal ~H is
,j determined. This digital signal is then ed to the adder/sub-
tractor 209 where the value ~H is added to or subtracted from,
~,i according.to the sign Sg(hH)~ the mantissa of the hi values
stored in the H-register 216. Because.the H-register,216 is l-bit
longer (n+l) than the X-register 206, after every cycle the
~ relative position of xi samples and the hi values shifts when the
; "oldest" sample xi is replaced by the new sample xi+n+l. This
is necessary for computation of the next echo estimate supplied
to the differential amplifier 220 by the digital-to-analog con-
~,~ . verter 226. This extra register stage also gives the necessary
~' time to correct the stored impulse res~onse before it enters
'~ the convolution processor.
~I The convolution processor will be described in more
,
., detail with reference to Figure 3 of the drawings. During every
,',,;' sampling period TS - 125 ~s, the convolution processor computes
,~. the jth echo estimate rj, which is, according to Equation (1),
: . . n n
', r. = ~ h. x. . - ~ P,
O 1 1+~ i=O
That is, it accumulates n products Pi = hi Xi~; Of the samples
stored in the X and II registers 206 and 217,.respectively, and at
, the end of the cycle it stores rj in a register 301 ~7hich drives
~;'' a digital-to analog converter 302 as shown in FicJure 3. The
.
, analog value rj is then subtracted from tIIe echo signal yj (see
, Figure 2). Because both samples arc in the ~-law forma~, for
.,~ .
i,, zero exponents ex ~ eh = ~ their absolute value is
. - .
-19-
. ~ , '
; ' ' .
.,
: . . .. ~ ': ,.. .:. . ': , .. ..
~ 8~851
¦x¦ = mX X 2 x qx = 2 x mx
(12)
Ihl = mh x 2 x qh = 2 x mh
where ~x and qh are digital-to-analog scaling factors (quantiza-
tion steps) which can be chosen as qx ~ qh - 1 to si~plify the
follo~ing considerations. For ex > and eh > 0, the value of
the sample is
;, e
xl = 2 x ( 1 + mx)
(13)
-~ ¦h¦ = 2 h (1 ~ mh)
;~ . - . . .. .
where by definition the mantissas are mx, mh < 1. There are
therefore four possible combinations of sample formats entering
the convolution processor's multiplier. Four different algorithms
~ .
are used to form the product Pi = Xi+; hi.
If ex = eh = and the numbers ¦x¦ and ¦h¦ are only
, . . . .
three bits wide (see Equation (12)), the product is
ii = 2 x mx x mh
~" The product ¦Pi¦ 2t the output of multiplier 303 may be generated
in a loo~-up table, i.e., in a 4 x 26 = 256-bit read only memory
which is inexpensive and readily available.
If either ex = ~ eh > l, or ex > 1, eh ~ 0, then the
, product ¦Pi¦ , for the latter case, is
.,~ .
e e +l
~` ¦Pi¦ = 2 x (1 +~mx) 2 mh = 2 x (mh+mX mh) (15)
~........................................................... .
Also in this case the partial product mx x mh is read from the
read on]y memory multiplier 303 and added to the mantissa which
. ;~ .
has the zero exponent. More specifically, the partial product
is read out o~ multiplier 303 via multiplexer 30~ under control
o~ decoder 305 to adder 306. In addition, the mantissa wllich has
- ~20-
. ~
:-
,-, .. - , - ~ . , . - . . .
" . ' , " ~ ' ."' :
L8Sl
the zero exponent is coupled via multiplexer 304 under control
of decoder 305 to adder 306 to form the product ¦Pi¦. The
sum mh + mx mh is only < 5 bits wide and a simple 4-bit
medium scale integrated circuit adder can be used in this
operation.
If both ex > 1 and eh ~ 1, then the product ¦Pi¦ is
computed as
log2¦Pi¦ = ex + log2(1+m) + eh + 1og2(1+mh) tl6)
(see Equation (13) for comparison). For 0 < mx, mh < 1, these
approximate expressions hold
log2(1 + m) = m ' (17)
, 2 = 1 + m (18)
Equation'(16) can be simplified to yield
g2¦Pi¦ ex,+ eh + mx + mh = Ei + Mi (19)
where the exponent Ei is the whole part of the sum of Equation
, ( ), i.e., Ei (ex + eh + mx + mh) and the mantissa Mi is
'~ the remainder of Equation (19) or Mi = ex + eh + mx + mh ~ Ei.
The product ¦Pil is then
,, ¦Pi¦ = antilog2~Ei + Mi) = 2 i (1 + Mi + ~M) (20)
where ~M is a correction which is a function of mx and mh,
i.e., ~M = f(mxr,mh) and always such that ~M ~ 2 3, therfore
~maller than the least significant bits of mx and mh. Equations,
(19) and (20) can be implemented by two adders, adder 307 for
j the exponent and adder 306 for the mantissa.
-, Multiplication of the product of mantissas by 2 i,
, where Ei is an integer Ei ~{2, .... , 14} (see Equations (14),
~ (15) and (19)), is equivalent to shifting the partial products
,', by Ei binary places before entering the accumulator 308. This
can be done by a read only memo,ry or! as sho,~ sc~,tic~ in Figu~e
' 30 3, a static shif,ter 309. The static shifter 3Q9 is cont~o~led by,a
.
, ' ~ '. :
., . ,,: .
-21-
bm: ~h
~L~ 8S~
shift control 310 which, in turn is responsive to the sum of
the exponents as decoded in decoder 311. To complete the
description of Figure 3, a NOR gate 312 receives the sign bits
Sg(x) and Sg(h) and controls the add/substract mode of
accumulator 308.
There are two main reasons for using this seemingly
complicated multiplication scheme:
(a) Speed: Under all conditions the multiplication ,
is performed by reading from the read only
memory 301 and performing a single addition, so
that the whole operation of multiplying x~ hi
and adding the product into the accumulator 308
can be done in one clock period Tc, even when
transistor-transistor logic and the longest
storage registers with n = 512 bits are used,
i.e., when TC = 200 ns.
tb) Simplicity: The whole multiplier consists of a
small read only memory for multiplier 303, two
adders 306 and 307, and a few gates because all
'- 20 of the algorithms above are relatively easy to
~ implement in hardware; e.g., the decoder 311
: ; must only detect whether exponents e = 0 or e > 1,
etc.
j Referring back to Figure 2, the cross-correlator
will be discussed in more detail. The cross-correlator
algorithm has already been described. According to Equation
(3), the hi samples are corrected by addition of ~hi,j (see
Equation (5)) if and only if the following conditions are met:
~a) The error voltage ~j is greater than a certain
multiple of the basic quantization step.
.
-22-
bm~
, .
. , . ~.: ,
, .... . . .. . ~.
851
(b) The corresponding sample ¦xi+j ¦ is greater than
Xj which is proportional to the rms value of
samples stored in the X-register (~i+j function).
(c) There are several other internal and/or external
conditions inhibiting the correction process.
~The most important is the "double talk condition"
when both echo yj and a send-speech signal are
f present in the echo path.)
Every hi sample is also encoded into an 8-bit A-law
format and stored in the H-register 216 as Sg(hi) + eh + mh'
where the most significant bit is sign Sg(hi) followed by a
3-bit exponent which is an integer eh ~ f ~, . . ., 6} and a 4-bit
mantissa O<mh~l. The least significant bit, i.e,, the fourth
bit of mh, i.e,, 2 4, does not enter the convolution processor.
Since it is used only in the cross-correlation process, as will
now be described.
If eh Z ~ i.e., in the linear segment of the A-law
code, the correlation formula is the same as that given by
ff Equation (5), i.e,, the Widrow-Hoff least mean square
~ 20 algorithm,
'A,~ hi'= hi + ~hi j = Sg(hi) mh i,j (21)
(see Equation (12)). If eh~> 1 and hi,i << 1, then according
to Equation (17), the process of adding ahi j is according to
; Equation (17) approximately equivalent to
'~ ~ h h Qhl,j - eh + log2(1 + mh) + log2 (1 + ahi j)
f (22)
The right-hand side of Equation (22) is, according to Equation
~Og2lhil + log2(1 + ~hi,j) = 1g21hL ¦ ~23)
.
-23-
:; ~ " : - .
bm.
.
, ,~
-- ~81851
The corrected sample hi is therefore the antilog of Equation
(23); i.e.,
hi = h~ hi,j (24)
The sam~le is thus multiplied by a multiplier >1 or <1 according
to the sign of ~hi j. The time constant TCR iS therefore inde~
pendent of the amplitude of hi and is
IcR - 5 x 2 m TS (25)
where bm is the number of bits in the mantissa and TS is the
sampling period, i.e., TS ~ 125 ~s. For a 4-bit ~antissa
TCR = 1.25 ms.
Thus, TCR iS more than one order of magnitude shorter
than the time constant of a similar cross-correlator using
Widrow-Hoff algorithm. The same is true of the convergence time
, i.e., the time at which the echo return loss enhancement
(ERLE) in the circuit reaches a point 1 dB below the steady
state value of ERLE. This time is a function of the circuit
echo return loss, the signal statistics and amplitude, etc.,
and can be determined only by experiment. This high-speed
algorithm makes it possible to substantially simplify the cross- -
correlator:
(a) Only two quantization leve~s are used for the
error signal E j -
Q(Ej)~{+2 , 0, -2 4} (26)
(b) The correction ~hi j therefore has only one fixed
value ~hi j = 2~4, which is equivalent to the least
significant bit of the mantissa mh.
.
-24-
.
:: : , ~.. , . ~ , ..
' ' .. . ~ ~. ' .' ,. .. : ' , .
: -:
.. . . . . . . .
^` ~ 851
(c) The error sensox reference voltage V ~ supplied
to comparator 212 is dependent on Xj.
The detector is less sensitive in the presence of
higher level receive-in signals and vice versa.
' This keeps the echo attenuation (> 23 dB) fairly
independent of receive-in speech signal levels over
dynamic range of more than 23 dB. With white noise,
which as a different amplitude distribution than
I speech, the range is only 21 dB.
~d) As described above, the correction ~hi j is added
' to the least significant of hi, i.e., to the fourth
mantissa bit which does not enter the convolution
, . . .
processor's multiplier. This is analogous to the
"inert zone" stabilization of nonlinear feedback
control systems. This technique, along with that
-
described in (c) holds the digital echo canceller's
`
feedback loop stable even when its internal gain,
i.e., the "hybrid's" return loss, changes by more
tha~ 24 dB~ ' ~
(e) Proper functioning of the digital echo cancellor -
with high return loss and low level receive-in
signals is made possible by the high peaks contai'ned
in the speech signal. They have an amplitude >15 dB '
higher than the rms value during a syllabic period
- Tsp - 125 ms and can therefore activate the cross-
correlator's error sensor even when the feedback -~
loop's internal gain is low.
,'': .,:
""
~8~851
As previously described (see Equation (3)), the func-
~ tions of the analog comparator 212, adder/subtractor 209! and
- the center clipper 211 are dependent on a quantity Xj which is
proportional to the average value or pseudo rms value of the ~-
speech samples stored in the X-register:
n
XAVR = n 1 IXil
n 1/2
Xj = q 1 ~ Xi ~27)
~., ' . .
where q is a proportionality constant. Because neither of the
R
, above mentioned func$ions of XAvR or Xj requires higher precision,
;~ three simple approximations are used in computing Xj.
The average value XAvR can be computed in the average
value processor shown in Figure 4. According to the algorithm
implemented by this processor, the latest sample ¦xi+n+l¦ is added
I to the contents of the AVR register 401 and the "oldest" sample
j ¦xi¦ is subtracted. Both of these sarnples are first converted
;1 in an A-law linear converter 402 and temporarily stored in the
shift registers 403 and 404, respectively. Then, in one continuo~us ~ -
serial operation the arithmetic unit 405 adds the value ¦xi+n+l¦
to and subtracts the value ¦xi¦ from the contents of the AVR
register 401. The converter 402 also converts every sample
¦xi+l¦ to ¦xi+n~l¦ into a linear format, and then the samples are
compared in a di~ital comparator 406, (corre5ponding to comparator
208) with the stored average value X~vR in the AVR register 401.
If the sample is yreater than XAvR in register 401, the signal
-26-
' ' '
.
. , . : , ~ .. ~ .
, - ~ ., , . ' ' ~' ,: ',. .
,: , ' , , ' ' . ~
8Sl
~j enables the correction process, i.e., to add or subtract the
correction ~H to the existing value hi. The new value is then
stored in the H-register 216. The average value XAvR in AVR
register 401 is also converted in c.;gi~al-to-analog converter 407
(corresponding to converter 210) into a reference voltage VREF
for the analog comparator 212 and the adaptive center clipper 211.
In the alternative, the pseudo rms value Xj (see
Equation (27)) can be computed. Instead of squaring, adding and
taking the square root, approximations and a new algorithm are
used.
For the parabola Xi+j a 3-segment linear approximation
as illustrated in Figure 5 may be used, i.e.,
n i-0 Xi~i ~ n i~0 ~(Xi+i) (28)
where
`~ ~\(Xi,~,j) a O ~ il O
~(Xi~j) = a¦Xifj¦ - b, elsewhere (29)
and a and b are constants. A similar 2-sesment approximation
may be used for the square root function as shown in Figure 6.
The whole circuit for generation of Xj, ~j and the
reference voltage VREF is shown in Figure 7. Only the 3-bit
exponent ex and the two successively higher significant ~its
(M2, Ml) of mantissa ~x of the (A-law encoded) sample xi~j enter
the decoder 601 and static shift register 602, respectively.
This digital signal is con~erted to 8-bit linear format accord-
ing to Equations (12) and (13), i.e., by shifting (1 ~ mx) by ex
binary places with the static shift register 602 schelllatically
-27-
.
.. .. - . . .. . , . - , . . .. , .: . . : . . . . . ~ .
~11851
,
illustrated by the switches Sl + S2. From this 8-bit linear
format, only the four most significant bits are added to the
4-bit accumulator 603; hence; the function ~(xi+j) according to
Equation (28) is generated. The number of accumulator over-
flows (COUt) are counted by a binary counter 604 whose number
of stages is chosen according to the number n of bits stored
in the X-register 206. Hence, the approximate sum of n-samples
and also the division by n is performed (see Equation (27)).
At the end of the convolution cycle, the eight significant
bits of X; are stored in a static memory 605. This stored
signal drives the overflow/underflow detector 606 which
inhibits the cross-correlator during a strong signal which has
different statistical properties than speech (e.g., burst
noise) and when the stored signal is below threshold yO (see
Figure 6). It is also converted to the reference voltages
VREF by digital-to-analog converter 607 (corresponding to
converter 210).
In the following convolution cycle every xi+j sample
entering the pseudo rms processor is compared with the stored
value Xj in an 8-bit digital comparator 608 (corresponding to
comparator 208) and so the cross-correlator function ~j is
generated (Equation (13)). ~he three inhibit signals ~m yO
and overflow are combined in an AND gate 609 into ~j which
controls the ~hi j adder 209.
It will be apparent that the embodiment shown is `
only exemplary and that various modifications can be made in
~l construction and arrangement within the scope of the invention
; as defined in the appened claims.
.
.
-28-
bm:~
g~
' . , .
