Non-Linear Echo Cancellation of Data Signals

The present invention relates to an echo cancellation circuit and method.

Data echo cancellers have received considerable attention in recent years in connection with digital subscriber loop modems and full-duplex voiceband data modems. With such modems, an inherent two-wire transmission facility is turned into an equivalent four-wire connection by using a hybrid circuit at each end. Data can then be transmitted simultaneously in both directions. However, the attenuation of the hybrid between its two four-wire inputs can be as low as approximately 10 dB. The purpose of an echo canceller is to remove the "near-end cross-talk" or "echo" signal which feeds through the hybrid into the local receiver, interfering with the data signal coming from a distant transmitter. Since the latter transmitted data signal may be highly attenuated (40 to 50 db), the required attenuation of the echo signal is consequently large (on the order to 50 to 60 db) in order to achieve an acceptable signal-to-echo interference ratio at the receiver input for the maximum expected line attenuation.

Most prior art echo canceller implementations completely neglect the effect of non-linear distortion in the echo path or in the echo replica. An exception to this uses an echo canceller with 2.sup.N taps to synthesize an impulse response of N samples, as described in more detail in IEEE Transactions on Communications, Vol. COM-29, 11, Nov. 1981 entitled "A New Digital Echo Canceller for Two-Wire Subscriber Lines." In this canceller, called a "memory compensation" or "table look-up" canceller, the echo canceller assigns an independent output to each possible combination of N transmitted bits, and thus is completely general as to the kind of nonlinearity that it can correct. The price paid for this generality is 2.sup.N taps rather than N, and requires a structure in which at each sample time only one tap weight can be updated. The consequences of this are that for large N the required memory becomes very large and the adaptation very slow.

Achieving a 50 to 60 dB cancellation in a monolithic echo canceller is further complicated by the inherent nonlinearities in monolithic A/D and D/A converters due to processing variations and component variations. These systems have to deal with small amounts of non-linear distortion, i.e., a channel which is "almost" linear. It would therefore be highly desirable to provide an improved echo cancellation circuit and method which can correct for small amounts of non-linear distortion without a large complexity penalty or adaptation speed penalty.

In view of the above background, it is an objective of the present invention to provide an improved echo cancellation circuit and method.

The present invention relates to an echo cancellation circuit and method for a full-duplex data transmission system, such as in digital subscriber loop modems and voiceband data modems.

In one embodiment, the invention comprises a linear echo cancellation circuit connected to receive an echo signal having both linear and non-linear components. The circuit includes N-linear tap weights for cancelling the linear components of the echo signal and M total taps, including M-N non-linear tap weights for cancelling the non-linear components of the echo signal. The number of non-linear taps (M-N) which are added depends on the degree of non-linearity which must be compensated. In a preferred embodiment, M is greater than or equal to N, but less than or equal to 2.sup.N.

The echo canceller can operate in spite of non-linearities in the echo channel or in the implementation of the echo canceller itself, such as with digital to analog converters. These non-linearities must be time-invariant or slowly time-varying, but need not be memoryless.

The improved echo canceller can be implemented by a relatively small number of taps added to a linear echo canceller (e.g., M.perspectiveto.2N), with substantial improvement in the cancellation results.

In accordance with the foregoing summary, the present invention achieves the objective of providing an improved echo cancellation circuit and method.

Other objects and features of the present invention will become apparent from the following detailed description when taken in conjunction with the accompanying drawings.

FIG. 1 depicts subscriber loop modems communicating on two wires.

FIG. 2 depicts alternative echo canceller configurations, in which FIG. 2a depicts a fully digital echo canceller and FIG. 2b depicts a digital transversal filter and analog concancellation.

FIG. 3 depicts an echo canceller configuration in which the D/A non-linearity is compensated by an adaption algorithm.

FIG. 4 depicts a binary tree representation of non-linear function in which FIG. 4a is a binary series expansion and FIG. 4b is a table lookup method.

FIG. 5 depicts a hardware implementation of non-linear function, in which FIG. 5a is a binary series expansion, FIG. 5b is a table lookup method, and FIG. 5c are linear and non-linear taps.

FIG. 6 depicts a linear echo canceller for multilevel transmitted signals.

FIG. 7 depicts a non-linear echo canceller for non-linear channel in which distortion introduced by the channel and by the D/A non-linearity d(.sup..) are both compensated.

FIG. 8 depicts a bipolar encoder.

FIG. 9 depicts an adaptation of tap weight coefficients, which is the same as for a linear canceller.

FIG. 10 depicts a digital to analog converter (DAC) using resistor string and capacitor array.

FIG. 11 depicts typical DAC transfer functions (a) f(x)=1.01333x-0.01333x.sup.3 (b) f(x)=x-0.005/x/.

FIGS. 12a and 12b residual error as a function of the number of taps.

FIG. 13 depicts a histogram showing the results of random +1% and -1% random perturbations in a resistor of the 12-bit DAC of FIG. 10, for 100 samples.

1. Introduction

Referring now to the drawings, FIG. 1 depicts subscriber loop modems 10,10' communicating on two wires 12. Proper echo cancellation techniques ensure full duplex transmission with adequate channel separation. Each modem circuit 10,10' of FIG. 1 includes a transmitter 14, a hybrid circuit 16, echo canceller circuit 20, summing circuit 18, and receiver 22. As will be described in more detail, each echo cancellation circuit 20 includes means to receive a first bit stream corresponding to a first transmitted data signal transmitted via transmitter 14 and hybrid circuit 16 over wires 12. Canceller 20 also includes means to receive a second transmitted data signal over wire 12. The second data signal includes an echo portion of the first bit stream having both linear and non-linear components.

The canceller 20 includes means for processing the first bit stream to generate a replica of the echo signal portion of the second data signal.

The canceller 20 includes means 18 for subtracting the echo replica from the second data signal to yield an echo-free (or substantially echo-free) replica of the second data signal.

As an example of the kinds of nonlinearity appearing in a practical system, consider the subscriber loop modem shown in FIG. 1. The following sources of nonlinear distortion can be identified:

A. Transmitted pulse symmetry.

When nominally balanced positive and negative pulses are transmitted, in practice there will be a slight imbalance which cannot be compensated for by a linear echo canceller. To achieve 50 dB or more of echo cancellation, a linear echo canceller would require that the uncompensated transmitted pulse symmetry be kept below some -60 dB, which can be achieved with careful circuit design at the cost of increased complexity.

B. Saturation in transformers.

This will lead to a slight nonlinearity which can be controlled by choice of a bulkier transformer.

C. Nonlinearity of data converters.

The echo canceller is typically implemented as a digital processor, since its input consists of an inherently digital bit stream. This suggests that the actual cancellation be done digitally, requiring A/D (analog to digital) conversion of the received signal (containing the echo), or the cancellation can be done in analog, requiring D/A (digital to analog) conversion of the canceller output. These data converters constitute the most important source of nonlinearity, particularly where monolithic converters without trimming are to be employed.

Examining the alternatives in the use of data converters in greater detail, FIG. 2 shows two possible configurations. In FIG. 2a, a purely digital echo canceller, using a front end A/D 34, is considered. S/H circuit 32 samples the second data signal at regular intervals and A/D 34 converts it to a digital format. For a digital subscriber loop with a bit rate of 80 kb/s and a minimum of 50 dB of echo cancellation, the A/D 34 needs a resolution of 12 or more bits with 1/2 LSB (least significant bit) integral linearity and a conversion time of 6 microseconds or less. Digital adaptive transversal circuit 30 generates a digital representation of the echo portion of the second data signal and digital circuit 36 provides means for subtracting the digital representation from the converted second data signal.

In FIG. 2b, the output of the echo canceller is converted to analog and the cancellation is performed in the analog domain. Digital adaptive transversal filter 40 provides means for generating a digital representation of the signal and echo signal and D/A converter 46 provides means for converting the digital signal to an analog representation or format. Analog circuit 44 provides means for subtracting the analog echo replica from the received data signal. The error signal needed by the digital processor echo canceller is converted to digital by a lower resolution (possibly only one bit) A/D converter. The required resolution is at least 12 bits with 1/2 LSB integral linearity in the D/A and as many as 8 bits in the A/D (which should be monotonic but not necessarily linear). The problem of the linearity of the data converters is a very important one in the context of an MOS (metal-oxide-semiconductor) monolithic implementation of these modems. Specifically, the configuration of FIG. 2b is particularly attractive, since D/A converters such as converter 46 of the required speed and resolution have already been demonstrated in MOS technology. However, the linearity requirements can only be achieved using self-correction or trimming, which are costly solutions. An alternative solution to the problem in which the transversal filter summation is done by analog circuitry and thus the adaptation can compensate for the D/A nonlinearity is shown in FIG. 3 and has also been demonstrated. (Details of the above are described in more detail in the cross-referenced application entitled "Echo Canceller Tolerant of Non-Linear Elements", Ser. No. 414,515, filed Sept. 2, 1982.) However, that solution cannot correct other sources of distortion, like pulse asymmetry or saturation in transformers. Furthermore, digital circuits benefit more from the shrinking design rules and are easier to design than their analog counterparts, and thus a technique amenable to digital implementation like the one presented here is likely to be preferred in the future.

The technique described here is also interesting in other respects. It leads to a systematic design procedure for using a binary transversal filter (where the delays are implemented by shift registers) even in the context of a multilevel transmitted signal and line codes with memory. The multilevel signal could have states "1" or "0", or states "+1" or "-1", or any other logical variation including three or more states. The design procedure can also take advantage of redundancies in the transmitted line code in the form of simplification of the echo canceller hardware. The technique is also applicable to the implementation of the decision feedback equalizer feedback filter, which has a structure very similar to that of the echo canceller, although the requirements on this filter are relatively relaxed and compensation for nonlinearities may not be required.

In Section 2, a method of expanding an arbitrary nonlinear function of a number of bits in a series with a finite number of terms is presented. This expansion serves as the basis for the nonlinear echo canceller design procedures described later. Then in Section 3 the application of this expansion to multilevel transmitted signals, redundancies in the line code, and nonlinearities in the echo channel and the canceller itself are considered. Section 4 gives simulation results for the types of nonlinearities typically encountered in MOS D/A converters. These results indicate that, depending on the number of bits in the D/A converter, a 20 dB or greater increase in echo attenuation can be obtained by incorporating compensation for the D/A nonlinearity with a modest increase in canceller complexity.

2. A Binary Series Expansion of a Nonlinear Function

Let f(B.sub.o, . . . ,B.sub.N-1) be an arbitrary (nonlinear) function of N bits, where B.sub.i assumes one of the values 0 or 1. Over all combinations of N bits this function assumes a total of 2.sup.N possible values (which are not necessarily distinct). It is now shown that this function can be represented as a series with a finite number of terms, ##EQU1## The general L-th order sum is over all combinations of L of the N indexes. Thus, for example, in the second order term, B.sub.1 B.sub.2 only appears once, and not as a separate B.sub.2 B.sub.1 term. To reduce the number of arguments, the subscripts of the missing bits have been used as arguments of the last N/2 coefficients f.sub.r (.sup..). The total number of terms can be obtained by observing the number of combinations of N bits taken L at a time is ##EQU2## Thus, the total number of terms in the representation is ##EQU3##

The proof that the expansion of (2.1) in general is simple by induction. Note first that

the function evaluated for all zeros, since all the higher order terms are zero. Then, evaluating the function for a single 1 in the argument at position k, all the second and higher order terms are zero and

where the single 1 is in position k. Similarly, when the function is evaluated for two ones in positions k.sub.1 and k.sub.2, all the third and higher order terms are zero and

Proceeding by induction, all the constants in the expansion can be evaluated. Not only does this prove the result, but it also elaborates a procedure by which the constants of the expansion can actually be evaluated for a given function of N bits.

Understanding of this expansion can perhaps be enhanced by a simple example. For a function of three bits f(B.sub.0, B.sub.1 B.sub.2) the expansion becomes ##EQU4## where there are 2.sup.3 =8 terms total. Interestingly, this expansion can be written in the form a form which generalizes to the general case of N bits. This latter form results in a tree of switches 52 and adders 50 as shown in FIG. 4a. The leaves of the tree are the values of the constants in the expansion, and the switches 52 closest to the leaves are closed when B.sub.0 =1 and are open when B.sub.0 =0, and similarly for the switches 50 in the other two levels of the tree. Note that in general a number of constants in the expansion contribute to the value of the function, from a minimum of one for the all-zeros case to a maximum of eight for the all-ones case. A number of summations have to be evaluated to determine the function, from a minimum of zero in the all-zeros case to a maximum of seven in the all-ones case.

An alternate representation for the function, also requiring eight constants, is shown in FIG. 4b. This tree also has three levels (or in general N levels for N bits) but in this case every branch has a switch 54. The convention is that the switches 54 are shown for the B=0 condition, and reverse for the B=1 condition. In FIG. 4b, when the function is evaluated, one and only one path through the tree has all the switches 54 closed. Thus, only one of the constants contribute to the function evaluation, and no summations are actually required. This method is of course simply a table look-up, in which the eight functional values are stored.

It might be asked what value the expansion of FIG. 4a has when it requires the storage of eight constants, the same as for the method of FIG. 4b but, unlike FIG. 4b, also requires summations. The answer is that in many practical situations not all of the terms in the series expansion need be retained. For example, if the function is "linear", then

and only three terms of the expansion of FIG. 4a need to be retained while all eight terms of the expansion of FIG. 4b are always required. This is of considerable importance when N is large and the function is linear or nearly linear. This utility will be demonstrated in Sections 3 and 4 for the application to echo cancellation of data streams.

Representations of these two methods in a form more appropriate for hardware realization are shown in FIG. 5. This figure assumes that the bits B.sub.k represent two states "0" and "1". In FIG. 5a, there are N linear multipliers 60-2, 60-3, 60-4 for multiplying the N tap weights f.sub.1 (0), f.sub.1 (1), f.sub.1 (2) with the N bits B.sub.0, B.sub.1, B.sub.2. In FIG. 5a, note that the products of bits B.sub.0, B.sub.1, and B.sub.2 are easily generated using "AND" gates 62. The logical function illustrated by AND gates 62 could be performed by other logic circuits, such as an exclusive-OR function, or any other type of logical circuits for different representations of the two states (as for example "1" and "-1"). There are M-N multipliers 60-1, 60-5, 60-6, 60-7 and 60-8 for multiplying the tap weights f.sub.0, f.sub.2 (2), f.sub.2 (1), f.sub.2 (0) and f.sub.3 with a logical "1" or nonlinear logical combinations of two or more of the bits B.sub.0, B.sub.1, or B.sub.2. Summing circuit 64 performs the summing function to form the output signal f(B.sub.0,B.sub.1,B.sub.2). While the representation of FIG. 5b for the table look-up method is not necessarily practical (simply storing the values in a RAM or ROM is more reasonable), this form is conceptually valuable when the adaptive filtering application is considered in the next Section. FIG. 5c depicts in more detail the circuitry needed to implement one of the linear or nonlinear taps in FIG. 5a. It specifically shows the circuitry which converts from a logical "0" or "1" representation to a two-state representation which can assume any of a multitude of pairs of values (for example "-1" and "+1").

In the case of a linear tap, the single input bit is converted into a two-state representation (for example "+1" and "-1") by the two-state generator 72. This is then multiplied by the tap weight value in multiplier 74.

One skilled in the art will recognize that if the values at the output of 72 are simply "+1" or "-1", that a true hardware multiplier is not required, but rather whether the output of 72 is added or subtracted in the summation 64 of FIG. 5a can simply be controlled. In the case of the nonlinear tap, there is an added logic circuit 70 which has at its input two or more logical signals and at its output a single logical signal.

For example, if the two states are "0" or "1", then 70 simply performs a logical AND of the input logical signals, and if the two states are "-1" and +1" then it performs a logical "exclusive-or", in each case in effect multiplying the corresponding two-state representations of the input logical signals. Also shown in FIG. 5c is an adaptation circuit not shown in FIG. 5a which provides means for adapting the tap weights to minimize the size of the residual echo at the output of the subtraction circuit 18 in FIG. 1. This adaptation circuit responds to the output of the two-state circuit 72 as well as the residual echo signal at the output of the substraction circuit 18 in FIG. 1 in a manner to be described in conjunction with FIG. 9.

2.1 Expansion of Incompletely Specified Functions

When the function f(B.sub.0, . . . , B.sub.N-1) is not specified for some particular N-bit sequences, a corresponding reduction in the number of terms in the expansion of (2.1) can be obtained. An application of this fact is given in Section 3.1.

Suppose that the function is specified for M<2.sup.N values of its arguments. Then no more than M terms in the expansion are required. To see this, the procedure to determine the expansion coefficients can be modified as follows. When the procedure reaches one of the N-bit sequences for which the value of the function is not specified, the value of the expansion is a "don't care" for this particular argument. Therefore, the expansion coefficient being determined can be set to any arbitrary value. In particular, a value of zero effectively eliminates one of the terms of the expansion. Setting to zero the coefficients of all the terms corresponding to bit patterns for which the function is not specified results in precisely (2.sup.N -M) zero coefficients, leaving a maximum of M non-zero coefficients. A natural application is to obtain an expansion such as (2.1) for a function f(C) where C assumes one of the M values. Then for N chosen such that 2.sup.N M, M different N-bit sequences can be assigned to each of the M values of C. An expansion of the form of (2.1) with a maximum of M terms then results. This procedure will be illustrated in Section 3.1 for a multilevel transmission application.

2.2 Expansion in Terms of Other Binary Variables

In some applications, it is desirable to obtain an expansion of the form of (2.1) in a set of variables which each assume two values, like B.sub.k but not the particular values 0 and 1. For example, in data transmission, it is common to transmit levels 1 and -1 rather than 0 and 1. The former values have the advantage, as will be seen later, of having statistical properties which are easier to handle.

Let the variable C.sub.k assume one of two values. Then it follows from (2.1) that

where B.sub.k assumes the values 0 and 1 and a and b are some appropriately chosen constants. It is shown below that an expansion of the form of (2.1) can be obtained with B.sub.k replaced by C.sub.k, 0.ltoreq.k.ltoreq.N-1. Further, a procedure is given which enables one to determine the coefficients of this expansion starting from the coefficients of (2.1).

The determination of the coefficients of the expansion is easily done as in Section 2.0 in terms of the B.sub.k which assume the values 0 and 1. However, it is of interest to transform the expansion to be in terms of a new variable C.sub.k, which assumes two different values. Substituting (2.9) directly into (2.1) results in an inordinate number of cross-terms, and is probably intractable. However, the new expansion can be determined as follows: Consider just the terms in (2.1) which contain B.sub.0 ; there are precisely 2.sup.N-1 of them. Factoring B.sub.0 out of these terms, the decomposition as set forth below is:

where f.sub.1 and f.sub.2 are each expansions identical in form with 2.sup.N-1 terms. Substituting for B.sub.0 in terms of C.sub.0,

where ##EQU5## Once all the terms of these two partial expansions have been determined as in 2.12 and 2.13, the two partial expansions can be combined to form a single expansion for f(C.sub.0,B.sub.1, . . . ,B.sub.N-1). When this procedure is repeated for B.sub.1 through B.sub.N-1, the expansion f(C.sub.0,C.sub.1, . . . ,C.sub.N-1) is complete.

3. Application to Echo Cancellation

The usual assumption in the design of an echo canceller for data transmission is that the echo signal consists of a linear superposition of N data symbols, ##EQU6## where e.sub.k is the current echo signal, C.sub.k is the current transmitted data symbol, assuming one of M possible values (M-ary transmission), and h.sub.0, . . . ,h.sub.N-1 are the impulse response samples of the echo channel. In this Section, the linearity is relaxed and it is shown how nonlinearities in the echo channel and in the echo canceller itself can be compensated in the canceller using the series expansion of (2.1). It will be shown that this method is considerably more attractive than the table look-up method, particularly when the number of bits N is large and the nonlinearities are mild.

In Section 3.1 the application of this expansion to multilevel data transmission will be discussed. Then in Section 3.2 the application to a nonlinear channel and/or a canceller which for implementation reasons is nonlinear will be explored. Section 3.3 explores the modifications which are desirable when typical line codes are employed. Section 3.4 derives an adaptive algorithm which can be used to "learn" the characteristics of the nonlinear channel and the nonlinearity of the canceller itself (this adaptation algorithm turns out to be essentially the same as for a linear canceller). Section 3.5 considers the truncation of expansion (2.1) to a relatively small number of terms, and describes a procedure for determining which terms to retain. Finally, Section 4 will give numerical results based on computer simultations for reasonable channel and canceller models to illustrate the viability of the techniques.

3.1 Multilevel Transmitted Signals With Linear Canceller

It has been pointed out in the prior art (i.e., see IEEE Transactions on Communications, Vol. COM-24, 9, September 1976, pp. 956-962, entitled "A New Digital Echo Canceller for Two-Wire Full Duplex Data Transmission") that an echo canceller for data transmission is particularly attractive to implement when the transmitted data bits are input directly to the canceller, resulting in a "binary transversal filter" in which the delay elements store individual bits rather than analog values and the need for multiples is eliminated. When the transmitted data symbols are multilevel, as is usually the case for example in voiceband data transmission, then this advantage would seem to be partially negated. For M transmitted levels, the transversal filters require the storage of M values at each stage and multiplies the tap weights by one of the transmitted data levels. For certain signal constellations, the latter values can be particularly inconvenient, as for example the square root of two.

In the instance of multilevel data the expansion (2.1) can be used to obtain a simpler implementation. Let L be an integer such that 2.sup.L .gtoreq.M. The transmitted level C.sub.k can be represented as a function of L bits,

which in turn can be expanded as in (2.1). As shown in Section 2.1, at most M terms are required in this expansion.

This result will now be illustrated for M=2 through M=5. For M=2 level transmission, L=1 and (2.1) becomes

for some constants a and b. Section 2 gives a procedure for finding the two constants, but in this case it is not necessary to find them since, as will be shown shortly, the adaptation of an adaptive canceller will automatically find the right constants without need for the designer to specify them.

For a three-level transmitted signal, let L=2 and assign the bit patterns 00, 01, and 10 to the three levels. Then in the expansion of (2.1) the term corresponding to the 11 bit pattern, which is f.sub.2, can be set to zero, resulting in an expansion of the form

where there are three constants. Alternatively, if the bit pattern 01 is not assigned, then the f.sub.1 (2) coefficient can be set to zero and

which is of a slightly different form but still has three constants. Similarly, there are two other possibilities for the expansion, corresponding to not assigning the 00 or 10 bit patterns.

When the number of transmitted levels is four, the expansion of (2.1) becomes directly of the form

for some constants (a,b,c,d). Finally, for M=5, choose L=3 and assign the bit patterns 000, 001, 010, 100, and 011 to the five levels. Then the expansion is of the form ##EQU7## where there are in this case 55 other ways in which the five levels can be assigned to patterns of three bits, each resulting in a different form of the expansion.

It should be emphasized that in any of these illustrative expansions one or more of the constants can be zero. In fact, one criterion is the number of non-zero terms which result for the particular transmitted levels.

Using these expansions, the received echo signal of (3.1) can be represented in a different form, in which the terms are represented in terms of binary rather than M-level data signals. For example, for the four-level signal of (3.6), (3.1) becomes ##EQU8## a representation of which is shown in FIG. 6. The echo response is represented as a transversal filter with 3N+1 taps, each of which needs to store only a single bit. The delay line can thus be implemented by a shift register 80 as i the binary transmission case, and the tap-weights do not require multiplies. The equivalent echo impulse response (g.sub.o, . . . ,g.sub.N+1) is a function of the actual channel impulse response as well as the constants (a,b,c,d). If an adaptive echo canceller is constructed from the model of FIG. 6, there is no need to explicitly incorporate these latter constants into the design, since the adaptation mechanism will automatically incorporate them. This should become clearer in Section 3.5 where adaptive filtering in the context of the expansion (2.1) will be elaborated.

When the transmission is two-level, then only one of the three shift registers 80-1, 80-2, 80-3 is required, so that there are N-1 total taps. For three-level transmission, only two of the shift registers 80-1, 80-2, 80-3 are required, so that there are 2N+1 total taps.

In general, for M-level transmission, the structure of a multiply-free binary transversal filter can be retained and the details of the multiple level transmitted signal can be left to the adaptation mechanism to sort out. In each case, a maximum of (M-1)N+1 taps are required in the binary transversal filter. This technique has two advantages. First, the implementation is simplified by incorporating the details of the multilevel signal into the tap weights. Second, in practice there will be some uncertainty in the transmitted levels due to component tolerances, etc., for which the canceller will automatically compensate. For example, a mismatch between a positive and negative transmitted level will have no adverse effect on the echo attenuation which can be achieved.

It should be emphasized that FIG. 6 pertains only to a linear echo signal. By the addition of nonlinear tops as described in Section 3.2, it can be easily modified for a nonlinear echo with multilevel transmitter signal.

3.2 Nonlinear Channel with Nonlinear Canceller

An interesting application of the expansion of Section 2 is to the compensation of nonlinear as well as linear effects in the channel, as well as in the canceller itself. The method by which this can be done will be considered in this Section.

Assume that the echo signal is not a linear superposition of data digits as in (3.1), bur rather that the echo is a general nonlinear function of the current and past N-1 data digits,

This model precludes the possibility of the function f being a function of k, and thus requires that the nonlinear echo channel be time-invariant. However, when the canceller is made adaptive as in Section 3.5, the canceller can compensate for a nonlinear echo channel which is a slowly varying function of time.

Further assume for simplicity that the data digits are binary, assuming one of two values. As was mentioned in Section 2.2, the expansion of (2.1) is valid for an arbitrary two-level signal C.sub.k as well as for a signal B.sub.k which assumes the values 0 and 1. It is convenient to write this expansion in a vector inner product notation. Toward this end, define a 2.sup.N -dimensional "augmented transmitted data vector" ##EQU9## where each term in the series representation of (2.1) is represented and the superscript T denotes transpose. The subscript k on c.sub.k reflects the fact that this vector is changing with time in accordance with the current and last N-1 bits of the data sequence.

In a similar way, deine a 2.sup.N -dimensional "augmented echo path vector"

which is a vector of coefficients of an expansion of the form (2.1) and in accordance with (3.9) is not a function of k. Then a more compact notation for expansion (2.1) is as an inner product of an augmented data vector with the augmented echo path vector

It is natural to assume that the canceller implements an expansion of the form of (3.12) with tap vector a

so that an arbitrary nonlinear echo can be exactly cancelled. A hardware realization of this canceller is shown in FIG. 7 for the case where C.sub.k assumes the values of 0 and 1. The AND gates 102, multipliers 104, and summing circuit 106 perform similar functions as for the corresponding components for FIG. 5a. Also included in FIG. 7 is a nonlinearity d(.sup..) 110 which models the undesired but unavoidable nonlinearity of the D/A converter at the canceller output in FIG. 2a. This nonlinearity follows an ideal D/A converter 108. Ignoring the quantization due to the D/A converter, the echo replica can be written as

The interesting question which arises is whether the incorporation of the augmented transmitted data vector into the canceller can compensate for the (D/A) nonlinearity d(.sup..) as well as the echo channel nonlinearity. To answer this question, note that since (3.14) is a (nonlinear) function of N bits, it follows from Section 2.2 that there exists a 2.sup.N -dimensional vector-valued function D[a] of a 2.sup.N -dimensional vector a such that

where D[a] is a 2.sup.N -dimensional vector-valued nonlinear transformation induced by the nonlinear function d(.sup..) on the coefficient vector a. Note that this relation is still linear in the augmented transmitted signal vector. As long as a vector can be found such that

for every signal vector c.sub.k then e.sub.k =e.sub.k and in principle the echo canceller can cancel the echo completely even in the face of the nonlinearities. A simple sufficient condition for (3.16) to be possible is that the inverse D/A nonlinearity d.sup.-1 (.sup..) exists, since then (3.16) becomes

Since the right side of (3.17) is a function of N-bits, Section 2.2 guarantees the existence of a vector a satisfying (3.17), and further gives a procedure for finding it. It is interesting to note from (3.17) that even when the echo channel is linear (all but the N linear taps of g are zero), the canceller needs more than the N linear taps in order to compensate for the D/A nonlinearity.

The addition of extra nonlinear taps should partially or entirely mitigate the effects of D/A nonlinearity, allowing the full resolution of the D/A to be useful. There are monolithic D/A converter realizations which are inherently monotonic, which is sufficient for the existence of d.sup.-1 (.sup..). Of course, in practice the quantization due to the D/A converter will prevent an exact cancellation of the echo.

The conclusion is that a linear canceller algorithm can still be used in the face of a nonlinear channel and nonlinear canceller implementation. What is necessary is to augment the N bits which are input to the canceller by the remaining bits in the augmented signal vector, resulting in a nonlinear canceller with 2.sup.N taps. Of course, the hope is that considerably fewer taps than this will be required in practice.

3.3 Line Codes with Memory

It is often desirable to use line codes which incorporate memory for the purpose of limiting d.c. wander, RFI, crosstalk, etc. A common example is the "bipolar" or "alternate mark inversion" line code, in which a binary signal is transmitted as a three-level signal. Each input data bit B.sub.k =0 is transmitted as C.sub.k =0, while B.sub.k =1 is transmitted alternately as C.sub.k =-1 and +1. This example is now used to illustrate how the presence of a line code can be incorporated into the canceller design.

Section 3.1 shows how the three-level C.sub.k could be represented by two bits B.sub.1,k and B.sub.2,k and the transmitted level could be represented as in (3.4). In the presence of a nonlinear echo channel, the received echo signal of (3.9) can be rewritten as a function of 2N bits, and an expansion with 2.sup.2N terms results. However, due to the fact that the signal is three-level, and due to the redundancy in the line code, many of these terms are unnecessary. For example, since B.sub.1,k-1 =B.sub.2,k-1 =1 can never occur in the transmitted signal, all terms in the expansion containing the product B.sub.1,k-1, B.sub.2,k-1, 0.ltoreq.1.ltoreq.N-1 can be eliminated. This will reduce the number of terms in the expansion to 3.sup.N. In addition, the memory in the line code will reduce the number of terms further. For example, since C.sub.k =1 cannot be preceded by C.sub.k-1 =1, and similarly for -1, the terms B.sub.1,k-1 B.sub.1,k and B.sub.2,k-1 B.sub.2,k can be eliminated. Elimination of all terms of this type will of course reduce the total number of terms to 2.sup.N, the number of possible input data sequences. The fact that 2.sup.N terms result by such a cumbersome procedure would lead one skilled in the art to ask if there is an easier approach, and indeed there is. The bipolar encoding can be accomplished by the circuit shown in FIG. 8. A modulo 2 accumulation of all the past input bits is first performed by XOR gate 120, resulting in the binary variable A.sub.k. The three-level C.sub.k is obtained by taking the difference in adder 122 of successive A.sub.k. All that is necessary is input to the canceller A.sub.k rather than C.sub.k, since the linear first difference filter 124 can then be thought of as being a part of the echo channel and can be easily compensated by the linear taps of the canceller. When the input data sequence is independent and equally likely, the A.sub.k are likewise independent and equally likely, and the operation of the canceller even when adaptive is not adversely affected. The canceller will require 2.sup.N taps as before, but with much less effort.

3.4 Adaptation algorithm

In this Section it is shown how the usual LMS adaptation algorithm can also be used in the presence of nonlinear distortion. From FIG. 9, the residual signal after echo cancellation is

where s.sub.k is the data signal coming from the remote transmitter and n.sub.k the noise term, both assumed to be uncorrelated with the echo. If the data digits C.sub.k are assumed to be uncorrelated and assume with values +1 and -1 with equal probability, it is easily verified that the elements of vector c.sub.k are uncorrelated (although not independent). Then the mean-squared residual can be calculated to be ##EQU10## is the total power of the remote data signal and noise.

Assume initially that the canceller does not have a nonlinear D/A, so that (.sup..) is the identify function. Then p is (3.19) is quadratic, and there is a unique global minimum which can be determined by setting the gradient of p with respect to the tap vector a to zero. This becomes ##EQU11## and the minimum p occurs as expected for equal augmented echo path vector and canceller tap vector a=g. To find this minimum adaptively, let the canceller tap vector a be a function of time a.sub.k and use the standard gradient algorithm,

This algorithm is illustrated in FIG. 9 for just one tap of the canceller. As usual, the parameter a is adjusted to obtain the desired tradeoff between convergence rate and asymptotic excess mean-square error. It is interesting that the presence of the nonlinearities in the channel has not affected the adaptation algorithm at all aside from the augmentation of the transmitted signal vector with nonlinear taps.

If there is a nonlinearity d(.sup..) in the echo replica path, the gradient of (3.21) becomes ##EQU12## If the Jacobian matrix .differential.D(a)/.differential.a is nonsingular, the unique minimum of p is obtained for

as in (3.16). In this case the gradient technique will also apply, since there will be no local minima in which the algorithm can get lost. The condition of nonsingularity of the matrix .differential.D(a)/.differential.a is a very mild one, since for the case of small nonlinearity (the case of interest here), .differential.D(a)/.differential.a differs from the identity matrix by only a small perturbation, and the small size of the perturbation ensures that the matrix is nonsingular. Further, since the function D(a) is not known by the adaptation algorithm, it is necessary that .differential.D(a)/.differential.a be replaced by the identity matrix. This is again justified for small perturbations from linearity, and results again in the standard LMS gradient algorithm of (3.22).

The speed of convergence and asymptotic residual echo can be predicted. Although the elements of the vector .sup.c k are not statistically independent, they are uncorrelated and zero-mean for the case where the data digits C.sub.k assume the values +1 and -1 with equal probability and are statistically independent. This condition is sufficient for the validity of the convergence analysis, yielding a ratio of asymptotic residual echo to uncancellable signal of ##EQU13## In (3.25) the number of elements in the augmented transmitted signal vector has been assumed to be M in anticipation of using only a small number of M of the 2.sup.N taps. Hence, in general M<<2.sup.N will be chosen, and the asymptotic error will be correspondingly smaller than for the table look-up canceller, where M=2.sup.N. Similarly, the speed of convergence can be measured by the rate constant of convergence, which is ##EQU14## The approximations in (3.25) are valid for practical values of a, which are very small. The convergence of the linear canceller, the nonlinear canceller described herein, and the table look-up canceller can be compared by setting the asymptotic residual errors of (3.25) equal for the three cases and then comparing the time constants of (3.25). The result is that the time constant of the nonlinear canceller described herein is M/N times as great as for the linear canceller, while it is 2.sup.N /N times as great for the table look-up canceller. Thus, a convergence time penalty is paid for the extra nonlinear taps (about a factor of two for the numerical examples of Section 4), but a much larger penalty for the table look-up canceller.

3.5 Truncation of the Series Expansion

In the preceding analysis, the full 2.sup.N -tap echo canceller has been considered. It is expected that under the conditions of (a) small nonlinearity, and (b) rapidly decaying echo path impulse response, most of the co-efficients of vector a are negligible and can be ignored. This will be established in Section 4 by simulation for typical nonlinearities encountered in MOS D/A converters. However, it is important to develop a methodology by which the non-negligible taps can be predicted, in order to develop insight and to avoid an inordinate number of simulations.

If only M taps are used, it is apparent that the M taps which are largest in absolute value should be chosen. This is confirmed in (3.19), for when D(a) is constrained to have only M non-zero elements, p will be minimized by choosing those elements for which g is largest in absolute value. For small deviations from linearity this will be the same as choosing the same M elements of a to be non-zero.

If the characteristics of the echo channel nonlinearity and D/A nonlinearity are known and fairly reproducible, then the taps which are important can be predicted. This will be illustrated by example. Suppose the echo channel can be modeled by an FIR filter followed by a memoryless nonlinearity q(.sup..). Then (3.1) becomes instead ##EQU15## Then the function q(.sup..) can be expanded in or at least approximated by a Taylor series expansion. Consider for example the square term in this expansion, which becomes ##EQU16## which can be simplified by eliminating the duplicated terms and noting from Section 2.2 that since C.sup.2.sub.k-j is a binary function it can be represented as

for some constants a and b. Then (3.28) becomes ##EQU17## From this relationship note that this square term contributes primarily to the second order terms in (2.1), but also to the first order term. Also note that the important terms will generally be those for which h.sub.j1 and h.sub.j2 are both large. From this one can conclude more generally that large n-th order terms in q(.sup..) will contribute most heavily to n-th order terms in the expansion of (2.1), and that generally the large nonlinear taps will be those containing C.sub.k-j corresponding to the larger h.sub.j.

When the D/A is nonlinear, and d.sup.-1 (.sup..) must be incorporated, it can be expanded in a Taylor series and a similar analysis can be applied to (3.17) to determine which taps in a are important. There are at least two methods for obtaining the Taylor series expansion for d.sup.-1 (.sup..). One method is to first find an analytical expression for d.sup.-1 (.sup..), and then expand it in the Taylor series. The second method is to do a Taylor series expansion of d(.sup..), and then directly find the Taylor series of its inverse. This latter procedure will be illustrated in Section 4.

Note that the validity of the expansion of (2.1) to echo cancellation does not depend on the existence of a Taylor series expansion of d(.sup..) or d.sup.-1 (.sup..), as can be seen from (3.17). When the function d(.sup..) is not analytic and a Taylor series does not exist (as for example when the function is piecewise linear), then it can be approximated to any desired accuracy by a polynomial (which is a truncated Taylor series) and the procedure is as before.

4. Cancellation MSE With MOS D/A Converter

In this section computer simulations of the performance of a nonlinear echo canceller in the configuration of FIG. 2b are studied. The operation of the adaptive echo canceller derived in Section 3.5 was simulated in the presence of certain nonlinearities inherent in MOS D/A converters. The purpose of simulating the canceller, rather than using the procedure described in Section 2 for finding the coefficients of the expansion, was to establish that the adaptive algorithm does indeed work properly in the presence of nonlinearities. The asymptotic mean-square echo cancellation residual error was noted as a function of the total number of taps implemented in the canceller. The particular taps which were implemented, and the order in which they were added, was determined by first running a program which calculates all the coefficients of the expansion in accordance with the procedure of Section 2 for the particular nonlinearity being studied. The taps were then added in the order of decreasing absolute value.

In order to make the numerical examples realistic, assume the D/A converter is to be implemented in MOS technology using the technique shown in FIG. 10. The four most significant bits are provided by a string of 16 diffused resistors and the remaining bits (from 6 to 9 in simulations) by a binary weighted capacitor array. Because of diffusion concentration gradients, voltage coefficient, and photolithographic mismatches, the resistors cannot be guaranteed to be equal to within one LSB unless laser trimming is used. Thus, in the absence of trimming, a nonlinear transfer characteristic results. This nonlinearity can have a systematic component due to concentration gradients, and a random component due to photolithographic mismatches.

Two of the most common kinds of systematic nonlinearity are shown in FIG. 11. Model the transfer characteristic of FIG. 11a by

where a=1.01333 and b=-0.01333, and the one in FIG. 11b by

where b=-0.005. For the characteristic of (4.1), the nature of the inverse can be determined by finding a power series expansion for d.sup.-1 (.sup..). Defining this power series as ##EQU18## and it is seen that the third-order nonlinearity predominates in d.sup.-1 (.sup..) as it does in d(.sup..). The even harmonics are missing since the characteristic of (4.1) has odd symmetry about the origin. Thus, it is expected that the important terms in the Volterra series expansion will be the first and third order terms. For the characteristic of (4.2), the easiest method is to find d.sup.-1 (.sup..) directly and approximate it by a polynomial. Since the nonlinear portion of this nonlinearity has even symmetry, the odd powers will be missing, and the important terms in the Volterra series will be the first and second order terms. These conclusions are confirmed by the simulations which follow.

The simple echo path impulse response assumed in all cases was

The effect of quantization was also included. Runs with 10, 11, 12 and 13 bits and with infinite resolution done, varying the number of taps from 1 to 26 in the case of FIG. 11a and from 1 to 17 for FIG. 11b. As previously mentioned, the taps were added in the order to decreasing absolute value as determined by another program. The resulting order is shown in Tables Ia and Ib together with the residual cancellation error in FIGS. 12a and 12b. Observe that in both cases many higher order taps are more important than the linear taps beyond the tenth. The importance of the nonlinear taps depends on the number of bits of quantization. With 10 bits there is no point to using nonlinear taps in FIG. 11a, whereas in FIG. 11b the nonlinear taps give about a 10 dB reduction in asymptotic residual error. For 13 bits of resolution, with a modest number of nonlinear taps, a 20 to 30 dB improvement can be obtained. In both cases, the number of taps is dramatically smaller than would be required in the table look-up method (1024 for a ten data bit cancellation).

The effect of random photolithographic mismatches in resistors was also simulated. Individual mismatches of either +1% or -1% (chosen randomly) were added to each of the 16 resistors of a string initially designed to implement a 12-bit D/A with the characteristic of (4.1). This level of mismatch is typical of what would be expected from an MOS process, although it is extremely unlikely that all the resistors would be simultaneously mismatched to this degree. This type of mismatch leads to a continuous piecewise linear characteristic in the D/A. In each simulation the same set of 26 taps shown in Table II were used (although many of them were very small). A histogram of the residual error in 100 randomly chosen mismatches is presented in FIG. 13. There is a considerable spread of 6 dB in the residual error, due to the choice of the same taps in each case (changing which taps were implemented for each random mismatch would presumably narrow this range and improve the cancellation). Table II shows the distribution of the maximum absolute values of the taps. Here a 0 in the intersection of column 0.001 and row C.sub.0 C.sub.1 C.sub.2 C.sub.3 means that the corresponding tap was smaller than 0.001 (in absolute value) for all the 100 samples.

5. Conclusions

A technique for compensating for nonlinearities in the echo channel and the echo canceller itself has been described. It has the desirable features of requiring a modest increase in canceller complexity for mild nonlinearities and not resulting in a significant slowing of convergence. For a relatively long echo impulse response and mild nonlinearities, it achieves a dramatic reduction of complexity and speedup of convergence relative to the table look-up approach. Initial computer simulations have indicated that the increase in the number of taps is indeed modest for the type of nonlinearities in typical MOS monolithic D/A converters, and that impressive echo attenuations can be obtained using this technique in conjunction with these converters.