Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
~298~38~
COEFFICIENT STO~AGE REDUCTION IN ADAPTIVE FILTERS IN ECHO
CANCELLERS OR DECISION FEED~ACK E~UALIZERS.
The invention relates to adaptlve filters for use in
equalizers and echo cancellers for digital transmission systems,
and to equal1zers and echo cancellers including such adaptive
filters.
In such systems, the length of time over which the adapt;ve
filter must operate is determined by the pulse tail length, i.e.
the time taken for the pulse tail to decay to an acceptably small
level. The part of the tail most distant from the main pulse
occurs later in time. Conversely, the tail is created by pulses
which occurred earlier in time. The adaptive filter must have
a sufficient number of taps to reach the point in time where the
tail has decayed by the desired amount.
If the line code used for the digital transmiss;on has a
high low-frequency contentil as is the case with 2B1Q (two binary,
one quaternary), the line code to be used in ISDN (Integrated
Services Digital Network) Basic Access, the amplitude of the
tail can still be substantial many symbol periods in time after
the main pulse occurred.
In a convent;onal equalizer or echo canceller, a long tail
requires a large number of taps, and hence faster storage access
time and arithmetic pr~cessing for calculating the echo est1mate
and updating the coefficients. Memory and processing speed
requ;rements increase still further if multiple samples per
symbol period, or multiple coefficients per tap, are required (as
for multilevel line codes). For a conventional transversal
. . ,:
'1 ' ~
~ . ~
-' ~2~888~1L
f;lter in which individual symbols are mul-tiplied by respecti~/e
coefficients, then summed, khe numbar o~ taps required for the
aforementioned long tails could result in excessive processing
speeds or circuit compl0xity. Likewise, for a memory-type
adaptive filter, the SiZ8 of memory would be prohibitive, even
if the memory were split, as disclosed by Kanesmasa et al in U.S.
patent number 4,605,826, issued August 12, 1986 and entitled
"Echo Canceller with Cascaded Filter Structure" and by M.
Koohgoli in Canadian patent No. 1,250,035 issued February 14,
1989 to Northern Telecom Limited and entitled "Split~Memory Echo
Canceller". The reader is directed to both oF these documents
for reference.
One common method of reducing circuit complexity while
handling long pulse talls is to use an Inflnite Impulse Response
(IIR) tap in the adaptive filter, as described in the papers by
C. Mogavero, ~. Norvu, G. Paschetta entitled "Mixed Recursive
Echo Canceller (MREC)", in Proc. Globecom 1986, December 1986,
pp 44-48, and by Takatori et al, enti'~led "Architecture for Fully
Integrated Echo Canceller LSI based on Digital Signal
Processing", in Proc. ICC 1987, June 1987, pp601-605. A
disadvantage of this approach, however, is that it requires the
decay time constant of the pulse tail to be precisely known in
advance.
An object of the present invention is to provide an adapt1ve
digital filter for an echo canceller or decision feedback
equalizer in a digltal data transmission system, wh~ch requires
less storage and lower arithmetic proceseing speed than the
9~884
adaptive filters discussed hereinbefore, and does not require a
precise knowledge of the pulse ta11 characterist;c.
According to one aspect of the present invent10n, an
adaptive digital filter for an echo canceller or decision
feedback equalizer in a digital data transmission system
comprises:-
storage means for storing a series of bits of a digital data
signal, said bits representing symbols;
first adaptive digital filter means for deriving from a
first group of said blts an estimate representing a portion
of a received signal, which portion is to be cancelled;
at least one second adaptive digital filter means for
deriving from a second group of said stored bits occurring
earlier in time than said first group an estimate
~S representing a further portion of said received signal,
wh;ch further portion is to be cancelled, the or each said
second adaptive filter means ~having summing means for
summing said second group of bits to generate a quantity
representing the cumulative sum of the symbols represented
in said second group, and means for multiplying said
quantity by a coefficlent to obtain an estimate for said
second group;
said adaptive digital filter further comprising second
summlng means for summing the estimates for the first and
second groups to provide an estimate sum for subtraction
from a received digital data signal.
,
,
~1.29l3~3~34
In an echo canceller embodying an adapttve digita1 filter
according to the inventlon, the storage means 1s arranged to
store bits of said digital data signal to be transmitted.
In a decision feedback equa1izer embodying an adaptive
filter according to the ;nvention, the storage means is arranged
to store bits derived from said received digital data signal
after data recovery has been effected.
In preferred embodiments, the adaptive digital filter
comprises a plurality of said second adaptive digital filter
means, each operative on a different group of bits of said
digital data s;gnal, said second summing means serving to sum the
respective outputs of said plurality of second adaptive digital
filter means. The first adaptive d;gital filter means may
comprise any suitable kind, such as a memory-type adaptive
digital filter or a transversal filter wh1ch treats every symbol
separately.
According to a second aspect of the invention, there is
provided a method of flltering a digital signal for equalization
or echo cancellation in a digital data transmission system,
comprising the steps of:-
storing a series of bits of a transmitted digital data
signal, said bits representing symbols being transmitted;
derivlng an estimate for a first group of said stored bits,
said estimate representing a portlon of a received signal,
which portion is to be cancelled;
deriving for a second group of said stored bits occurring
earlier in time than said first group an estimate
representing a further portion of said received signal,
129~3~384
which further portion is to be cancelled, said step of
deriving said estimate for said second group compris;ng
summing said second group of bits to generake a quantity
representing the cumulative sum of the symbols repr0sented
in said second group, and multiplying said quantity by a
coefficient to obtain said estimate for said second group;
said method further comprising summing said estimates for
said first and second groups and subtracting tha sum so
produced from said received dig;tal signal.
The invent;or-is predicated upon the later part of the tail,
i.e. the part most distant from the main pulse, being almost
hor;zontal wlth respect to time, i.e. decaying very slowly and
so of almost constant value. Assigning one coefficient to a
group of symbols, representing a sub~interval of the echo
cancellar time length, in essence subsamples the later, flatter,
portion of the tail. At the same time, the earlier part of the
signal, i.e. closer to the originating pulse, may have one or
more coefficients for each symbol, as is usual, effectively
sampling the more rapidly changing park of the signal at a higher
rate.
In some systems, a plurality of bits are used to represent
each symbol. For example, a 2BlQ signal ;s generated from dibits
comprising one bit for magnitude and a second bit for sign. In
such systems, embodiments of the invention will sum the groups
of bits in such a way that the flnal sum representing the
cumulative sum of the symbols preserves the magnitude and sign
information.
~Z9~3~3134
Embodiments of the inventlon w;ll now be descr;bed, by way
of example only, and with reference to the accompanying drawings,
;n which:-
Figure 1 ;s a block schematic d~agram of a transceiver
5 including an echo canceller embodying an adaptive digita1 filterfor use in a digital data transmission system;
Figure 2 is a detail block schematic diagram of a part of
the echo canceller; and
Figure 3 ls a representation of a typical echo waveform in
the digital data transmission system.
Figure 4 is a block schematic d1ayram corresponding to
Figure 1, but showing a decision feedback equalizer embodying an
adaptive digital f11-ter for use in a digital data transmission
system.
Figure 1 shows a transcelver which constitutes the user
interface of, for example, a central office switch in a telephone
system. The transceiver comprises a hybrid circuit 10. One
port of the hybrid circuit 10 is connected to a two-wire
subscriber loop 12 and the opposite port is connected to a
balancing network 14. The third port is connected to the output
of a power transmitter amplif~er 16, which may be of conventional
construction and so wlll not be described in detail. The input
of the power transmitter amplifier 16 is connected to the output
of an encoder 18 which takes a binary data stream applied to lts
;nput and encodes it as 2B1Q (two binary, one quaterr,ary) data
for transmission onto the subscriber loop 12.
In the 2B1Q signal, four levels +3, ~ 1, and -3 are
represented by dibits 10, 11, 01, and 00, respectively. In each
.
.
....
,.. .
~2~a~
dibit the first bit represents s;gn and the second bit represents
magnitude. The encoded signal supp1ied ta the power transmitter
amplif;er 16 is at half the rate of the lnput blnary data stream.
The encoder 18 supplles a correspondirlg signal to an echo
canceller 20, which comprises shlft register means 22, divided
into three segments 24, 26, and 28, respectively. Three echo
canceller stages 30, 32, and 34, are connected to the shift
register segments 24, 26, and 28, respéct~vely, and haYe their
outputs connected to a summer 36. The output from summer 36 is
the echo estimate ~ which a second summer 38 sums with the output
e o~ sampler 40. The lnput to sampler 40 is the digital data
signal received from the subscriber loop 12 and f11tered by pre-
emphasis and anti-aliasing filter 42 connected to the fourth port
of the hybrid circuit 10. The output from the sampler 40
actually consists of both the received signal and the echo
component e, but only the echo component e is correlated with the
transmitted signal. The echo cancaller 20 will not find
correlation wlth the received signal which therefore will be
ignored. The output of summer 38 is applied to all three stages
30, 32 and 34 of the echo canceller 20 as an updating signal ~
for updatln~ the coeffic1ents, by methods which are generally
l<nown and will not be elaborated upon -further. The output of
summer 38 is also appl1ed to a receiver 44 whlch converts the
echo-cancelled signal back to binary received data.
26 The segments 26 and 28 of the shift register 22 each have
five taps connected to summers 46 and 47, respectively. The
autputs of the summers 46 and 47 are applied to multipliers 48
and 50, respectively. Multipliers 48 and 50 alsa have inputs
~2988~34
connected to coefficient storage means 52 and 54, respectively.
Each of the coefficien~ storage means 52 and 54 stores a twenty-
four bit word which is multiplied by the output of the
corresponding one of summers 46 and 47 to provide echo est;mate
signals ~9l and ~gz, respectively. Each of the summers 46 and 47
generates a quantity representing the cumulative sum of the
symbols represented by the group of bits in the corresponding
segment of the shift register 22. Although only two shift-
register segments, each of five cells, are shown in Figure 1, to
simplify the drawing, a practical echo canceller might have many
more segments as deemed necessary.
It should be noted that the value at the output of each of
the summers 46 and 47, being the sum of all the values of the
five taps, can take a number of dlfferent values dspending on
the particular slgnal combinattons. For example, if all five
symbols are at the ~3 level for those five symbol per10ds, the
output will be +15. The three echo estimates, ê1, ê9~ and ê9z,
are summed by summer 36 ko glve the echo estimate ê, whlch is
subtracted from the output of the sampler 40 by summer 38.
The flrst echo canceller stage 30 may be a conventional
memory-type echo canceller, or a transversal filter echo
canceller, which will multlply a representat1en of each
individual symbol of the data stream by its own coef~lcient. The
length of this flrst stage, l.e. the number of shift register
taps it spans, will be chosen to suit the partlcular situation,
the intention belng that the first stage, with at least one
coefficient per tap, will be operatlve over the faster-changing
portion of the pulse waveform (see Figure 3)~ Stages 32 and 34
., ,. -. ~
' '
lZ98~38~
will then operate over the slowly-changing parts of the pulse
vls. the ta~l portion.
It should be appreciated that the shift register means 22
is not a single blnary shlft register since it must accommodate
four different states for a given tap. This is achieved by
providing two shift registers in parallel, as illustrated in
Figure 2, which also shows the first stage echo canceller 30 in
more detail. The shift register means 22 is shown to comprise
two parallel sh;ft registers 22A and 22B. Both are connected to
the encoder 18, each to receive an 80 kB/s bit stream. Shift
register 22A recelves sign informatlon X~ and shift register 22B
receives magnitude information Xm the corresponding cells 1n the
shift registers 22A and 22B representlng a dib;t, 11, 10, 01, or
00 as discussed prevlously. Each palr of cells of the shift
registers 22A and 22B thus form a single tap of the shift
register means 22. It should be appreciated that~ of the four
possible levels for the 2B1Q slgnal, only one will be attained
at any instant.
The first echo canceller stage 30 has the conventional
transversal fllter echo canceller form. Each pair of cells of the
shift reg;sters 22A and 22B are connected, in common, to
mult;pliers 60, 62 and 64 for multiplication by coeff;cients Cl,
C2, C3, respectively, der;ved from a corresponding plurality of
coefficient storage means 66, 68 and 70. It should be
apprec;ated that although only three coefficients are shown, in
practice there will be at least as many as there are taps.
In addition to its inputs connected to the corresponding
taps of the shift registers 22A and 22B, each of the multipliers
129~3~8~
60, 62, and 6~, has a third ;nput connacted to khe corresponding
one of coeffic;ent storage means 66, 6~ and 70. The ;nputs of
coefficient storage means 66, 68 and 70 are connected to
multipliers 72, 74 and 76, respectively. ~ach of khe multipliers
72, 74 and 76 multipl;es the value from the correspond;ng tap of
the sh;ft register means 22 by the updating signal ~ from summer
38 (Figure 1~, after scaling by scaling means 42.
Each coefficient storage means 66, 68 and 70 stores a
twenty-four bit word which is multiPlied by the output of the tap
of the shift register 22. A summer 80 sums the respective
outputs of the multipliers 60, 62 and 64 to give the echo
estimate ~1 for the f;rst stage 30. Because this first stage
has a coeffic;ent assigned to each tap, the early part of the
s;gnal, wh;ch ;s changing relat;vely rap;dly as shown ;n F;gure
3, is accurately mapped.
The est;mate ê1 for the f;rst stage ;s produced in
accordance w;th the general expression:-
ê1 = ~ X~ C~ [ 1 ]
where X~ ;s the value ~n the sh;ft register means 22 at tap
position i; and
C1 is the coefflc;ent correspond1ng to the same tap
position.
For each of the stages 32 and 34, w; th grouped taps, the
echo est;mate is derived ln accordance with the general
express;on:
~g~ = h~(~X1) [2]
where j ldent1fies the group;
' ~ ~
. .
,,
2~8131 34
h; ;s the single coefficient for that group;
89~ is the echo estimate for that group; and
~X~ is the representation of the summed values of the
symbols at taps i in group ~.
In the specific example, the final echo est;mate ê then is
~ = e1 ~ ês~ + êg2 [3]
For the second and third echo canceller stages 32 and 34 in
which each of the coefficients is applied to a group of taps, tha
updating will be in accordance with the algorithm:
oh~ = K~(~X~) t4]
h~(new) = h3(previous) ~ oh~
where oh~ is the value by which h~ is ko be updated
K is a multiplicative constant
~ is the error value from the output of summer 38; and
j, h3, and ~X~ are as defined above.
It should be noted that when each group contains only one
tap, the echo estimate and updating equations become the same as
the equations for the transversal filter.
Figure 3 illustrates pictorially how taklng the sum of the
2~ symbols in each group will yield a valld echo estimate.
Considering, for example, the tlme region of operation for
canceller 32, ;t can be seen that, for the three pulses shown,
the tail magnitude will be substantially three tlmes the
magnitude of the tail from a slngle pulse, due to superposition.
The coefficient h1 (Figure 1) represents the ma~nitude of the
.. . .
~ 9888~
single pulse tail in this region. Thus, h~ is multipl1ed by the
sum of the estimate of the total tail magnitude. Note that were
one of the pulses negative, the sum of the symbols in the group
would be +1, two tails would cancel, and the total tail height
would be equal to h~ instead of 3 x h~.
It should be appreciated that, to facilitate the
description, the mathematical terms have been simplif;ed. Thus
~n equation [2] and [4] ~X1 is a shor~hand way of expressing
"Sum of all the values X~ ln group j . More rigorously:-
For a group j comprising N tap positions, between shiftregister positions i = i~tæ~t(o and i = i~tArt(o + N-1~ inclusive,
i EltE~rt ( J ) ~N- 1
~X1 is reallY ~1X1 ~
~ tart t .5 )
where, clearly, the starting position igtart(;) is different for
different groups "j".
It should be noted that these equations apply generally to
both echo canceller and equalizer embodiments. In the former
case, the quantity X~ is the locally transmitted signal b;ts and
in the latter case the received signal bits after detection or
decoding.
Thus equation [2] would be:
êg~ - h~ ~X 19ta't(J)~N~1 [6
~tart (~ )
C 7 ]
1 ~t~rt ( 1 )
i start(2)+N-1
ê92 = h2~X1 [8
i = i~tart(2) etc.
where j = 1, 2, 3 .... refers to group.
12
.':
:: :
~.~9~38~3~
Equation r 4] would be:-
i = ~3t1rt(~)~N-1
oh~ = K~ ~X1 [9]
i ~t~rt (~ )
or;
1 0 ~ tart ~
oh1 = K~ ~Xl [10]
1 ~tRrt ( 1 )
i ~tart(2)+~
~h2 = K~ ~Xj [11]
i ~tart(2)
It should be noted that the number of taps N need not be the
same in each yroup i.e. different groups could comprise different
numbers of taps, as dictated by the application requirements. It
becomes clear that, i~ N = 1, each group is only one tap long,
and this is identical to the transversa1 filter.
The adaptive digital filter described above is not limited
in application to an echo canceller, but may be used in a
decislon feedback equallzer. Referring now to Figure 4, which
corresponds generally to Figure 1 but shows the transce;ver in
more deta;l, those components whlch are common to both
embodlments have the same reference numeral while those whlch
merely correspond are ldentified by a double prime. The
transceiver has an echo canceller 20 shown as a box since
lnternally it is as shown in Figure l. A decision feedback
equalizer 44 is simlar in construction to the echo canceller 20
and so will not be descrlbed ln detail. It will be apprec~ated
by one skilled in the art, however, that in the first stage,
identified as equal1zer stage 1 and referenced 30", there will
~9~!3 !38~
,
be no cancellation of the main pulse, since the equalizer seeks
to cancel everything but the main pulse~
In the rece;ver 44", the output of summer 38 ~Figures 1 and
4) is supplied to a summer 39, whlch subtracts from it the output
of the equalizer ~q'. The equalized output of summer 39 is then
supplied to data recovery or detector means 45.
It should be noted that, whereas the echo canceller ZO
derives its input, the outgoing or transmitted signal, from the
encoder l~, the equalizer derives its input, the recovered data
signal, from the output of the data recovery detector 45.
Various mod1fications and alternatives are comprehended by
the present invention. For example, the hybrid circuit 10 could
be a hybrid transformer or could be electronic. Although the
equalizer embodying the invention has been shown and described
in a transceiver which has an echo canceller also embodylng the
invention, it should be appreciated that it could be used
independently.
14
' ', :
' '
.
.
