Reduction of signal processing requirements in a 2B1Q-code echo canceller or equalizer
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to telecommunications systems and, in particular, to a method for simplifying the signal processing requirements for transmission of 2B1Q coded signals. 
     2. Discussion of the Prior Art 
     In high-speed data transmission applications over telephone twisted pair cable, the requirement for a low error rate is essential to the stable operation of the communications channel. When digital data is transmitted at a high rate over a telephone line, the main impairments are attenuation, dispersion and crosstalk noise. In addition, when signal transmission is fully duplex, the echo signal originating from the transmitter interferes with the data being received. 
     An example of a high speed data transmission application is the digital subscriber loop in the evolving Integrated Services Digital Network (ISDN). 
     The required data transmission rate over digital subscriber lines in the ISDN is 160 kbits/sec. To improve ISDN data transmission performance against the impairments mentioned above, the data to be transmitted is coded into a bandwidth-reducing format before it is transmitted. 
     Different modulation techniques can be employed to reduce the bandwidth of a transmitted signal. The modulation technique adopted in the United States by the American National Standards Institute (ANSI) for use over the digital subscriber line is called 2B1Q line coding. 2B1Q coding is a technique whereby a binary input sequence is transformed into a quaternary sequence by amplitude modulating pairs of bits in the binary stream of data. 
     According to the 2B1Q coding technique, successive pairs of binary data B=(0,1) are one-to-one mapped onto corresponding units of quaternary symbols Q=(-3, -1, +1, +3) and then transmitted as a corresponding voltage level at half the rate of the binary sequence. Therefore, an incoming binary data stream B with a bit rate of 160 kbit/sec is converted into a quaternary bit stream Q with a symbol rate of 80 kbit/sec and then transmitted. The conventional mapping rule from the binary data format to the 2B1Q data format is provided in Table 1 below. 
     
                       TABLE 1                                                     
______________________________________                                    
       Binary                                                             
             Quaternary                                                   
       B     Q                                                            
______________________________________                                    
       00    +1                                                           
       01    +3                                                           
       10    -1                                                           
       11    -3                                                           
______________________________________                                    
 
    
     The signal processing that is performed on a 2B1Q transmission in the data detection process is intended to remove echo interference in the received signal that is generated by the transmitter and to remove the distortion in the received signal itself. The former filtering task is referred to as echo cancellation and the latter is known as equalization. 
     Both echo cancellation and equalization filtering functions utilize a similar structure in that they can be performed by the same hardware configuration. One such configuration is the linear transversal filter. The following discussion of both the conventional method for performing echo cancellation/equalization and of the data coding technique of the present invention is based on the assumption that equalization is essentially the same as echo cancellation, but with a different input signal to its filter. 
     In the ISDN, the transmitted signal couples to the telephone twisted pair cable via a transformer, while the same transformer couples the twisted pair cable and the receiver. Therefore, an interference path exists between the transmitter and the receiver that causes every symbol that is transmitted to &#34;echo&#34; back into the receiver. Hence, the term &#34;echo path&#34; is used to identify the transfer function from the transmitter to the receiver at the same end of the digital subscriber line. 
     A conventional non-adaptive linear transversal filter of the type shown in FIG. 1 can be used to model the echo path. It performs the convolution between the transmitted signal, e.g. 2B1Q symbols q(n), where Q=(-3, -1, +1, +3), and the filter&#39;s individual tap gain coefficients a j , to arrive at an output y(n), where ##EQU2## and where the coefficients a j  are samples of the echo pulse response of length N+1. 
     As shown in FIG. 1, a conventional non-adaptive linear transversal filter consists of a delay line which is tapped at intervals corresponding to the symbol width. Each tap along the delay line is connected through an amplifier to a summing device that provides the filter output y(n). The tap gains, or coefficients a j , are set to subtract the effects of interference from symbols that are adjacent in time to the desired symbol. As stated above, this transversal filter structure can be used as an echo canceller, acting as an echo predictor and cancelling the transmitter-to-receiver coupling. 
     In practice, due to the slow time variability of the echo path, and more importantly, due to the unknown initial values for the tap gain coefficients a j , an adaptive filter is required for echo cancellation and equalization. 
     Adaptive filters are frequently constructed as transversal, or tapped delay-line filters. A typical adaptive filtering application, shown in FIG. 2, involves driving a channel with an unknown impulse response with a known input signal q(n). The output of the channel at time n is given by the convolution sum y(n). In adaptively tracking the channel output, the adaptive filter produces an output x(n) which is the result of the summing of the tapped delay line outputs. Being time variable, the adaptive filter tap gain coefficients a j  are iteratively updated based on a convergence algorithm which operates on the channel output y(n) and the filter output x(n) to develop an error feedback signal Ke(n) to the adaptive filter. Through a number of iterations, convergence of the channel output x(n) and the filter output y(n) is brought within acceptable limits. 
     In the case of both non-adaptive and adaptive filtering, the transfer function performs the convolution between the transmitted 2B1Q signals q(n) and the filter&#39;s delay line tap gains a j  to arrive at the filter output y(n), where ##EQU3## 
     Because the symbols q(n-j) equal the transmitted 2B1Q code Q=(-3, -1, +1, +3), every multiplication operation in the convolution summation can potentially involve either a +3a j  term or a -3a j  term. Implementing multiplication of these terms requires splitting the product 3a j  =2a j  +a j . Thus, compared with 2a j  multiplication for example, which is a basic left shift in binary arithmetic, implementation of 3a j  multiplication requires either more clock cycles or a faster clock with an associated increase in power consumption. 
     SUMMARY OF THE INVENTION 
     The present invention provides an efficient signal processing technique for removing echo interference and/or distortion from a received 2B1Q coded signal. According to the preferred technique, the received 2B1Q signal Q=(-3, -1, +1, +3) is shifted one bit to the left to generate a corresponding shifted symbol alphabet S=(-2, 0, +2, +4). The shifted symbols are then processed through a transversal filter. That is, the shifted signal is provided to a delay line which is tapped at intervals corresponding to the symbol width of the received signal. Each tap along the delay line is connected through an amplifier to a summing device that provides an output y(n), where ##EQU4## The tap gains, or coefficients a j , are set to subtract the effects of interference from symbols that are adjacent in time to the desired symbol. 
     In an adaptive embodiment of the invention, the output y(n) results from the convolution between the transmitted symbols s(n) and the gain coefficients a j . The output of the transmission channel and the filter output y(n) are then processed in accordance with a convergence algorithm to develop an error feedback signal which is used to iteratively update the tap gain coefficients a j  until the convergence of the channel output and the filter output is brought within acceptable limits. 
     By shifting the conventionally coded 2B1Q to provide a new symbol alphabet comprising powers-of-two numbers, the multiplication operation in the convolution summation involves only 2a j  terms, rather than the potential ±3a j  terms normally associated with 2B1Q signal processing. 
     To compensate for the symbol shifting, an additional DC tap is added to the filter. The additional tap is multiplied by a gain of 1 and subtracted from the shifted symbol convolution result to arrive at the desired result. 
     Therefore, the present invention provides faster processing of 2B1Q signals with negligible additional overhead. 
     These and other features and advantages of the present invention will be understood and appreciated by reference to the following detailed description of the invention which should be considered in conjunction with the accompanying drawings. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic block diagram illustrating a conventional non-adaptive transversal filter for operation on a conventional 2B1Q signal. 
     FIG. 2 is a schematic block diagram illustrating a conventional adaptive transversal filter for operation on a conventional 2B1Q signal. 
     FIG. 3 is a schematic block diagram illustrating an adaptive transversal filter for operation on a 2B1Q symbol alphabet shifted by +1 in accordance with the present invention. 
     FIG. 4 is a schematic block diagram illustrating an example of full duplex communication where adaptive transversal filters are used. 
     FIG. 5 is a schematic block diagram illustrating a non-adaptive transversal filter for operation on a 2B1Q symbol alphabet shifted by +1 in accordance with the present invention. 
     FIG. 6 is a schematic block diagram illustrating an implementation of a multiplier unit for the transversal filters shown in FIGS. 1 and 2 where the 2B1Q symbols are not shifted. 
     FIG. 7 is a schematic block diagram illustrating an implementation of a multiplier unit for the transversal filters shown in FIGS. 3 and 5 where the 2B1Q symbols are shifted. 
     FIG. 8 is a graph illustrating simulated convergence of adaptive DFE with DC-shifted 2B1Q symbols. 
     FIG. 9 is a graph illustrating measured convergence of adaptive DFE with DC-shifted 2B1Q symbols. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In a non-adaptive linear transversal filter of the type shown in FIG. 1, the conventional echo path transfer function performs the convolution between transmitted 2B1Q coded signals q(n) and the filter&#39;s delay line tap gain coefficients a j  to arrive at an output y(n) according to the following summation ##EQU5## where the coefficients a j  are samples of the echo pulse response of length N+1. 
     If the echo canceller structure is non-adaptive, as is the case on the FIG. 1 embodiment, then optimal performance can be achieved only when its tap gain coefficients are equal to those of the echo path Since, for 2B1Q signals, the symbols q(n-j) equal the transmitted 2B1Q code Q=(-3, -1, +1, +3), then every multiply operation in the convolution summation can involve either a +3a j  term or a -3a j  term. Implementing multiplication of these terms requires splitting the product into an addition as follows, 
     
         3a.sub.j =a.sub.j +2a.sub.j.                               (2) 
    
     In the multiplication process, the 2a j  term involves only a 1-bit left shift and can be considered negligible overhead in the product. Therefore, if the 2a j  term were the only one that needed to be considered, then an N+1 coefficient filter that has N+1 multiply operations and N+1 add operations would be equivalent to 2(N+1) add operations. 
     Thus, in accordance with the present invention, to eliminate the multiplication by 3 typically associated with 2B1Q signal processing, the following equations should be considered: ##EQU6## Thus, every symbol s(n-j) is shifted in level by 1. Therefore, let ##EQU7## where &#34;d&#34; is the DC component of the echo path. If the receiver includes a high-pass filter, and since it is part of the echo path, then d=0. 
     With the new symbols s(n-j), ##EQU8## 
     The structure of a non-adaptive filter in accordance with the present invention is shown in FIG. 3. It comprises the conventional transversal filter delay line tapped at intervals corresponding to the symbol width. Each tap along the delay line is connected through an amplifier to a summing device that provides the filter output. Additionally, as discussed in greater detail below, the delay line includes an additional DC tap to compensate for the symbol shift. 
     Thus, in accordance with the present invention, a new symbol alphabet S is provided that consists of a &#34;0&#34; symbol and powers-of-two symbols. The mapping rule from conventional 2B1Q coded data to the new symbol alphabet S is provided in Table 2 below. 
     
                       TABLE 2                                                     
______________________________________                                    
Binary       Quaternary                                                   
                       Shifted Symbol                                     
B            Q         S                                                  
______________________________________                                    
00           +1        +2                                                 
01           +3        +4                                                 
10           -1        0                                                  
11           -3        -2                                                 
______________________________________                                    
 
    
     Utilizing this new coding alphabet, every multiply operation in the convolution process is now either a do-nothing (0), a 1-bit left shift (symbols -2 and 2) or a 2-bit left shift (symbol 4). The shift operation has negligible overhead on the signal processing. An additional DC tap in the delay line is multiplied by a constant coefficient of 1 and, therefore, also has negligible overhead as a multiply operation. This results in a convolution process that only requires N+2 additions. Furthermore, if a high-pass filter is included in the receiver, i.e., d=0, then only N+1 additions are needed. 
     It should be understood that the shifting of the symbols is not physically performed by adding a &#34;1&#34; to each new symbol entering the echo canceller EC. Rather, each of these &#34;new&#34; symbols is interpreted as a &#34;-2&#34; if its transmitted value is -3, as a &#34;0&#34; if its transmitted value is -1, as a &#34;2&#34; if its transmitted value is 1, or as a &#34;4&#34; if its transmitted value is +3. The modifications to the conventional filter architecture that are required so that the filter interprets the conventional 2B1Q signals as the shifted symbols S will be obvious to those skilled in the art. 
     That is, as shown in FIG. 4 in dashed lines, an imaginary adder forces the echo canceller EC to &#34;see&#34; the conventional 2B1Q symbols as shifted by 1, i.e. as the symbols S. Consequently, the conventional data manipulation shown in FIG. 6 is replaced with that shown in FIG. 7. 
     Since the symbol shifter is imaginary, whereas the re-arrangement of the data manipulation, as shown in a comparison of FIGS. 6 and 7, is real, the intended convolution result between the symbols and the coefficients is incomplete. The resulting error is the quantity d in Equation (5) above. To obtain the correct result, the quantity d is subtracted from the convolution result, as shown in Equation (6) and in FIG. 3. 
     Thus, considerable simplification in the signal processing requirements is achieved by allowing the echo canceller EC to interpret the symbol values as (-2, 0, 2, 4) instead of (-3, -1, 1, 3). As stated above, inside the echo canceller EC, a DC-shifting effect occurs, since the expected value of the symbol values is now 0.25(-2+0+2-4)=0.25×4=1; this DC-shifting effect is cancelled by the DC-tap. 
     The practical implementation of a full duplex communications device at 160 kbit/sec over a twisted pair cable requires both adaptive echo cancelation and equalization. As stated above, and as described by B. Widrow, &#34;Adaptive Filters, I: Fundamentals&#34;, Stanford Electron. Lab., Stanford Univ., Palo Alto, Calif., Tech. Rep. 6764-6, December 1966, an adaptive filter `adapts` its coefficients in a controlled manner with the objective of emulating a given channel response. 
     Referring to FIG. 4, the function of an echo canceller EC is to adaptively emulate the echo path, that is, the signal flow from point 1 to point 2. An adaptive decision feedback equalizer DFE emulates the far end signal path, that is, the signal flow from point 3 to point 2. The echo canceller EC and the decision feedback equalizer DFE have similar architectures and signal processing behavior. Therefore, the following discussion is restricted to the echo canceller EC. 
     Adaptive filters have been extensively studied. Their most critical aspect is convergence, meaning the ability to reach a stable steady state where the coefficients of the filter are as close as is desired to the coefficients of the channel being emulated. Conditions for and proof of convergence are given by Widrow (see above) and by R. R. Bitmead, &#34;Persistence of Excitation Conditions and the Convergence of Adaptive Schemes&#34;, IEEE Trans. Information Theory, Vol. IT-30, No. 2, March 1984. 
     For a conventional filter at time n, the channel&#39;s (echo path) output is given by Equation 1 above. The channel output in the case of the shifted 2B1Q coding technique in accordance with the present invention is provided in Equation 6 above. 
     Let the adaptive filter (echo canceller) output be given by, ##EQU9## where the s(n-j) terms are the data symbols S shifted in accordance with the present invention, the b j  (n) terms are the time variable filter coefficients and c(n) is the time variable DC coefficient of the filter. 
     When convergence is achieved, a j  =b j  (n) for all j and n, and d=c(n) for all n. 
     The echo canceller output cancels the channel output x(n), resulting in a cancellation error e(n), where ##EQU10## 
     In Equations 13 to 19, the &#39; character denotes transposition, and all the vectors are 1×(N+2). From the Widrow Algorithm (see reference above) for updating the tap gain coefficients, 
     
         Ω(n+1)=Ω(n)-k e(n) S(n)                        (21) 
    
     where k is a positive constant chosen to control stability of convergence and steady state residual error e(n). The error e(n) 
     
         e(n)=Ω&#39;(n) S(n)=S&#39;(n)Ω(n)                      (22) 
    
     from Eqn. 21 and 22, ##EQU11## where I is the identity matrix. Equation 23 is in a form identical to the adaptive filter convergence problem described by Widrow and Bitmead and conditions on k for convergence of Ω(n) to 0 as n tends to infinity are derived there. ##EQU12## which means that the average correction or update to the DC-tap is independent of d, which is a fictitious quantity in the channel anyway, but depends only on the error between the canceller DC and the canceller DC-tap. Therefore, the canceller DC-tap tracks and cancels the DC introduced by the convolution of the DC-shifted data s(n-j) with the canceller taps and has very little to do with the channel DC. 
     The convergence proof of this algorithm is no different than the regular least mean squares (LMS) algorithm that does not use DC shift in the data. This is because Equation 23 satisfies the criterion that the (N+2)×(N+2) matrix M=(I-k S(n)S&#39;(n)) has one eigenvalue λ=(I-KS&#39;(n)S(n)) with eigenvector S(n), and (N1) eigenvalues λ=1 with eigenvectors forming the basis for the null space of S&#39;(n). Therefore, for convergence stability, with adequate choice of k such that matrix product M&#39;M is positive, definite and contractive, the contraction from Ω(n) to Ω(n+1) is in the direction of S(n) and orthogonal to S&#39;(n). The details of the proof are provided by Bitmead (see reference above). 
     As an example of this last point, consider a 3-tap echo canceller. Let s(n)=4, s(n-1)=-2 and let k=1/32. Then ##EQU13## 
     Note that the DC shift of the symbols could be a -1 instead of the +1, as proposed. The analysis for this case is similar to the +1 case except that every DC coefficient is inverted in sign and the shifted symbol alphabet is (2,0,-2,-4). 
     Architectures for a non-adaptive filter using an un-shifted symbol alphabet and one using the shifted alphabet in accordance with the present invention are shown in FIGS. 1 and 3, respectively. For the adaptive implementation, the architectures are shown in FIGS. 2 and 5, respectively. 
     As discussed above, an additional tap always appears in the filters using the shifted alphabet. The input of this tap is fixed at level s=1. Primarily, the shifted-data symbols implementation of the present invention gains an advantage in complexity and speed due to the construction of its multiplier units. Examples of these multipliers for a conventional 2B1Q filter and a shifted-alphabet filter are shown in FIG. 6 and FIG. 7, respectively. 
     Referring to FIG. 6, let the coefficient α j  be divided into a sign bit sα j  and M magnitude bits mα j . Assume sign-magnitude notation. If q 0  =0, then the latch output is 0 and the shift register SR shifts by 0 places. The coefficient magnitude mα j  is unchanged. If q 0  =1, then the output of the latch equals its input and the shift register SR output equals its input shifted by 1 bit left. The adder then adds (2mα j  +mα j )=3mα j . 
     Referring to FIG. 7, the multiplexer alternately selects s 1 , then s 0  and shifts if either is 1. 
     
         ______________________________________                                    
When s.sub.1 s.sub.0 = 01                                                 
                level 4, there are two left shifts.                       
When s.sub.1 s.sub.0 = 10                                                 
                level 0, there are no shifts.                             
When s.sub.1 s.sub.0 = 00 or 11                                           
                level 2 or -2, there is 1 left                            
                shift.                                                    
______________________________________                                    
 
    
     FIG. 8 shows a simulated signal to noise ratio (SNR) vs. time plot. FIG. 9 is a measured eye opening chronogram. Both situations utilize a 30-coefficient echo canceller and a 25 coefficient decision feedback equalizer. 
     It should be understood that the invention is not intended to be limited by the specifics of the above-described embodiment, but rather defined by the accompanying claims.