Abstract:
In a digital echo canceller using an impulse response filter, an interpolating and synchronizing circuit is used to couple the received digital signals from the four-wire circuit to the input of the filter. The interpolation and synchronization circuit generates signals having values between the values of received digital samples, and these interpolated valves are then sampled at the send signal rate and supplied to the impulse response filter.

Description:
BACKGROUND OF THE INVENTION 
     This invention is directed in general to signal processing devices which simultaneously process two digital signals which may be asynchronous. Although the invention is not limited thereto, it is specifically applicable to use in digital echo cancellers and will be described in that context. 
     It is conventional in long distance telephone circuits to utilize a hybrid coupling to interconnect the long distance four-wire line and the local two-wire line. As is well known, however, the coupling provided by the hybrid is not ideal, and a portion of the received signal will pass through the hybrid to the transmit line and will be returned to the speaker as an &#34;echo&#34;. An effective means for eliminating this echo is the &#34;echo canceller&#34; which is now quite well known in the art and is described, for example, in U.S. Pat. No. 4,064,379 to O. A. Horna entitled &#34;Logarithmic Echo Canceller&#34;, or in the article entitled &#34;Echo Canceller With Adaptive Transversal Filter&#34;, by O. A. Horna, Comsat Technical Review, Vol. 7, No. 2, Fall, 1977, pages 393-428. In principle, the echo canceller will monitor the incoming signal and predict the resulting echo, and this predicted echo is then subtracted from the signal present on the transmit line to hopefully cancel the echo signal. 
     FIG. 1 is a brief block diagram of a conventional echo cancellation system. The signal f si  received on line 10 is provided to the two-wire line 12 via the hybrid coupler 14 which includes an echo path by which a portion of the received signal f si  is passed to the transmit side of the hybrid and would thus be returned to the distant party over the transmit line 16. The echo canceller essentially comprises an adaptive finite impulse response filter (AFIRF) 18 which predicts the echo at any given time based upon recent samples of the received signal, and the predicted echo is subtracted in adder 20 from the output signal f so  of the hybrid. In the above-mentioned patent to Horna, the AFIRF receives its incoming signal input from amplifier 201 and its error signal input from sample-and-hold 222 and provides its output from D/A circuit 219. If the echo is correctly predicted, the subtraction of the echo prediction will eliminate entirely any echo component in the output signal f so . Assuming that the near talker 22 is silent, and further assuming an ideal noise-free communications channel, there should be no signal on line 16 at the output of adder 20, and any signal which is present at the output of adder 20 will be fed back to the AFIRF to adjust the prediction algorithm. In reality, the echo canceller may include circuitry for compensating for both noise and for handling &#34;double-talk&#34; situations, as is well known in the art, but a description of these features is not necessary for a complete understanding of the present invention. 
     The difference between the true and computed echo, i.e., the &#34;error&#34; is used to compute an improved model of the unit impulse response stored in the memory of the AFIRF. 
     In many applications, the signals on the input and output lines 10 and 16 are analog, and the signals are sampled and the samples converted to digital form within the AFIRF. The prediction signal processing is then carried out digitally and the predicted echo is then converted to analog form for subtraction from the true echo. In these cases, it is a simple matter to sample the receive and send lines synchronously with the internal clock of the digital portion of the AFIRF. 
     A significant problem arises, however, if the echo canceller is utilized in a circuit which carries digitally encoded signals. In such a case, circuits 203, 204 and 219 of the Horna patent would be dispensed with. The send and receive signals are in the form of digital bit streams, and ideally both would have the same bit rate. However, due to the influence of a long distance transmission media, e.g., doppler shift of a satellite circuit or frequency tolerances of local clocks of A/D encoders, the bit rate of the receive signal f si  can differ from the bit rate of the send signal f so  by as much as ±50 parts per million. With an 8 kHz sampling rate, the sampling rates seen on the send and receive lines can differ by 0.4 Hz which will manifest itself as a 0.8π/second &#34;phase roll&#34;. This phase roll can substantially reduce the effectiveness of the echo canceller, as is well known in the art and as is described in the above-cited paper by Horna. 
     Since digital systems may transmit not only digitally encoded speech and video signals but also computer data, the rate of the digital bit stream at either the receive or send side cannot be altered without risking data loss. This substantially limits the possible solutions to the problem of asynchronous data rates. One possible solution is described in U.S. Pat. No. 4,074,086 to Falconer et al entitled &#34;Joint Adaptive Echo Canceller and Equalizer for Two-wire Full-duplex Data Transmission&#34;. The technique disclosed therein is based on a special property of the equalizer, i.e., that the location of the most significant coefficients h in the coefficient memory can be fairly well predicted. When the receive and send bit stream are out of synchronism by nearly one-half of the sampling period, one least significant coefficient h is truncated or read twice from the memory to establish synchronism. This method is difficult to implement in a telephone echo canceller, since the location of the most significant coefficients changes with every connection. 
     SUMMARY OF THE INVENTION 
     It is an object of this invention to provide a method and apparatus for synchronizing two different bit streams in a signal processing device, and more particularly in a digital echo canceller. 
     It is a further object of this invention to provide such synchronization at a minimal cost and complexity. 
     It is a further object of this invention to provide a synchronization apparatus which can be implemented on a large scale integrated (LSI) chip. 
     Briefly, these and other objects are achieved in a first embodiment of the present invention by converting the incoming digital data to analog form, resampling the analog data with a clock synchronized to the send digital bit stream, and reconverting the sampled data to digital form for input to the AFIRF. In a second embodiment of the present invention, the necessity of the D/A conversion is eliminated by digitally interpolating the digital signal. This is accomplished by calculating the difference Δ between each presently received sample and the previous received sample, calculating an incremental value Δ/2 n , where n is a positive integer, adding this incremental value 2 n  times to the previous sample value and at a rate 2 n  times the sampling rate of the received digital signal f si . The addition results are continually maintained in an accumulator the output of which is sampled in synchronism with the f so  sampling rate, with the sampled output of the accumulator being supplied to the AFIRF for processing. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The invention will be more clearly understood from the following description in conjunction with the accompanying drawings wherein: 
     FIG. 1 is a brief block diagram, already described, of a conventional echo canceller configuration; 
     FIG. 2 is a block diagram of the essential components of the bit rate synchronizer according to the present invention; 
     FIG. 3 is a block diagram of an all-digital second embodiment of the bit synchronizer according to the present invention; and 
     FIG. 4 is a waveform diagram of the output of the accumulator in FIG. 3. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     A first embodiment of the present invention will be described with reference to FIG. 2 wherein similar components are designated by the identical reference numerals of FIG. 1. The incoming digital signal on line 10 is converted to analog form by a D/A converter 24 and passed through a low pass filter (LPF) 26. The output of the LPF 26 will thus be a smooth analog voltage representing the information of the digital input signal. This analog voltage is then sampled in sample-and-hold circuit 28, and the analog samples are converted back to digital form by A/D converter 30 and supplied to the AFIRF 18 for processing. 
     The sample-and-hold circuit 28 is clocked by the output from a clock recovery circuit 32 which generates a clock signal synchronized to the bit rate of the output signal f so . Accordingly, the bit rate at the output of A/D converter 30 will be synchronized to the bit rate of the output signal f so , so that the output of the converter 30 can be used directly as the receive input of the AFIRF without encountering the &#34;phase roll&#34; problem characteristic of conventional echo cancellers. The chain of components 24-32 thus works as an interpolator and synchronizer of the digital bit streams. Further, as is clear from FIG. 2, the echo canceller utilizing the bit synchronizer according to the present invention is similar to a conventional echo canceller in that it does not change the incoming signal and also does not change the outgoing signal when the AFIRF is disabled. 
     The specific internal circuit details of the components 24-32 do not constitute a part of the present invention and will not be described herein since a wide variety of suitable circuits are quite well known in the art. 
     A second embodiment of the invention will now be described with reference to FIGS. 3 and 4. A disadvantage of the synchronization circuitry shown in FIG. 2 is the dual D/A and A/D conversion which prevents the device of FIG. 2 from being implemented on a large scale integrated (LSI) chip. The second embodiment of the invention shown in FIG. 3 will achieve similar results by purely digital means, i.e. it does not at any time require the conversion of the digital input signal into analog form. 
     In FIG. 3, each new incoming digital signal sample is stored in a first register 40, with the previous contents of the first register 40 being passed to the second register 42 so that the first and second registers 40 and 42 will always contain the present and previous incoming digital samples, respectively. An adder 44 compares the two samples and provides at its output a difference signal Δ corresponding to the digital value difference between the two samples. This difference is then divided by 2 n , where n is a positive integer, to achieve an incremental value Δ/2 n  which is provided as an input to an accumulator 26. 
     A first clock recovery circuit 48 recieves the digital input signal f si  and generates a clock synchronized to the incoming bit rate. This clock signal is then provided to a multiplier 50 where it is multiplied by 2 n , and the 2 n  f i  clock signal is provided through a gate 52 to the clock input of the accumulator 46. Under the control of this 2 n  f si  clock signal, the incremental value Δ/2 n  is added to the accumulator contents until the comparator 54 indicates that the value in the accumulator is the same as the value of the present incoming digital sample in the first register 40, at which time the comparator 54 disables the gate 52 and interrupts the accumulation process. 
     Since the accumulation process continues until the contents of accumulator 46 and register 40 are equal, it will be understood that at the reception of the next incoming digital sample the first register contents are transferred to the second register 42. Thus, the value in accumulator 46 at this time will be the same as the previous incoming digital sample value now stored in register 42. In response to a difference between the present sample value in first register 40 and the previous sample value in accumulator 46, the comparator 54 will reopen gate 52 to begin incrementing the accumulator value toward the value now stored in the first register 40. 
     The output of the accumulator will be a digital signal having a level which changes in small amplitude steps Δ/2 n , and the duration of each amplitude step will be 2 n  times smaller than the duration of the sampling interval 1/f si  of the incoming digital signal. FIG. 4 illustrates a typical waveform at the output of the accumulator 46. In FIG. 4, s i , s i+1  and s i+2  represent three successive samples of the received digital signal f si . Instead of changing abruptly from one value to the next as is shown by the dotted line 60, the output of the accumulator changes in smaller steps. Note that for a given value of n, the step size will change in accordance with the difference Δ between successive samples. 
     The clock recovery circuit 32 in FIG. 3 is identical to that in FIG. 2 and generates a clock signal synchronized to the send signal f so . This clock signal is then used to sample the output of the accumulator 46, which samples will be supplied as the digital input signals to the AFIRF 18. As shown in FIG. 4, if the incoming and outgoing bit rates are out of synchronization and the accumulator output is sampled at times t j  and t j+1  in synchronism with the digital signal f so , the error caused by the lack of synchronization will be reduced by some factor less than or equal to 2 n . 
     As is the case in the embodiment of FIG. 2, the embodiment of FIG. 3 uses easily available conventional hardware components, and the internal circuit details of these components do not constitute a part of the present invention and need not be described in detail herein. As is well known, assuming that a common binary code is used, the division by 2 n  in divider 45 is tantamount to merely shifting the binary representation of Δ by n binary places to the right. Thus, the divider 45 could be implemented by a simple shift register. 
     The common principle employed in both embodiments of FIGS. 2 and 3 is that of interpolation and synchronization. In each case, a signal is generated which changes gradually between the values of successive samples of the input signal f si , in FIG. 2 this gradual changing, or &#34;interpolation&#34;, of the input signal being performed by the LPF 26 and in FIG. 3 the interpolation being performed by all of the components 40-52 with the interpolated signal being present at the output of accumulator 46. In each of the embodiments of FIGS. 2 and 3, the interpolated signal is then sampled in synchronism with the output signal f so  under control of the output from clock recovery circuit 32. 
     Theoretically, the embodiment of FIG. 3 is inferior to the analog approach of FIG. 2, since the interpolation between successive samples is linear in FIG. 3, but the advantage of the embodiment of FIG. 3 is that it can be implemented by common digital hardware in a LSI chip. The analog circuit of FIG. 2 will provide a higher order of interpolation, depending on the characteristics of the LPF, but is substantially more complex and, therefore, more sensitive to circuit tolerances and design limitations.