Title of Invention	A METHOD OF EQUALIZATIION FOR MULTICARRIER COMMUNICATION SYSTEMS
Abstract	A method and apparatus for equalization in multicarrier high-speed data transmission systems is proposed. A TDE (Time Domain Equalizer) is used to reduce the length of the channel impulse response. An SNR based method is proposed for initialization of the TDE to values based estimated inverse of the channel response and the estimator to an impulse. Variants of this method involve convolving either the TDE or the estimator with a filter to obtain a desired frequency response. Another variant involving higher sampling rate for specific out of band frequency response with selected to higher zero to reduce computation is also proposed. Incomplete equalization results in ISI (Inter Symbol Interference) between symbols causing degradation in SNR at the FEQ output. A method to partitoning and decoding of subcarrier outputs to improve the performance is detailed.

Title of Invention

A METHOD OF EQUALIZATIION FOR MULTICARRIER COMMUNICATION SYSTEMS

Abstract

A method and apparatus for equalization in multicarrier high-speed data transmission systems is proposed. A TDE (Time Domain Equalizer) is used to reduce the length of the channel impulse response. An SNR based method is proposed for initialization of the TDE to values based estimated inverse of the channel response and the estimator to an impulse. Variants of this method involve convolving either the TDE or the estimator with a filter to obtain a desired frequency response. Another variant involving higher sampling rate for specific out of band frequency response with selected to higher zero to reduce computation is also proposed. Incomplete equalization results in ISI (Inter Symbol Interference) between symbols causing degradation in SNR at the FEQ output. A method to partitoning and decoding of subcarrier outputs to improve the performance is detailed.

Full Text	FIELD OF INVENTION "This invention pertains to high speed data transmission systems using multiple number of carriers and more particularly, the art of equalizing the distortion effects introduced by the transmission medium in order-to retrieve the transmitted signal accurately. BACKGROUND OF THE INVENTION A multi carrier transmission system is one which employs FDM (frequency division multiplexed) sub-carriers for transmission. A typical multicarrier system is depicted in Fig. 1. It shows serial input data coming in the form of bits being converted by a serial to parallel converter 100, which also possibly encodes the frame of data (a data frame consists of a sequence of bits). The encoded data is modulated by the multicarrier modulator 200 to bring the signal to be transmitted within the desired pass-band of the channel. In most multicarrier systems, the preferred method of modulation is Inverse Fast Fourier Transform, IFFT. In these systems, data are generated as a serial stream of bits. But, prior to modulation, the system must determine the number of bits that can be assigned to each sub-carrier, as there will be several parallel sub-channels. A serial to parallel converter takes the input bit stream and distributes those bits over several sub-carriers. The parallel to serial block 300 performs the reverse operation (the notion of cyclic prefix will be explained in the body of the invention). The modulated data is converted to analog signal by a Digital to Analog converter (DAC) 400. filtered and input to the channel 500. The noise added during the passage of the signal through the channel is depicted by block 600. At the receiver, the received signal is filtered, sampled using an Analog to Digital Converter 700 and passed through the Time Domain Equalizer (TDE) 750. After cyclic prefix removal and serial to parallel conversion 800, the signal is demodulated using the Fast Fourier Transform (FFT) technique; the demodulator is indicated by block 850. The demodulated frame of samples is passed through a Frequency domain Equalizer 900, decoded and passed through a parallel to serial converter 950 to obtain the transmitted bits. The transmitted data, while passing through the channel 500, suffers various distortions. This is because a channel, in general, attenuates and delays different frequencies by different amounts. A data symbol can be defined as a modulated waveform lasting over a definite period (symbol period) of time and represents a combination of complex points in the signal constellation on different sub-carriers. The distortion caused in a symbol due to overlap by previous and subsequent symbols is known as Inter Symbol Interference (ISI) and the distortion in data on one carrier due to data on the other carriers is called Inter Carrier Interference (ICI). Further distortions in transmitted data result due to thermal and crosstalk noise. The decoder, in the presence of these distortions, will make incorrect decisions leading to data errors. Decision made by the decoder is a complex signal constellation point. In presence of noise and ISI, the decoded point might be different from the transmitted point. In order to achieve large data transmission rates with low data errors, it is necessary to compensate for the distortions introduced by the channel. A method of compensating for ISI and ICI is to perform equalization of the received data. Equalization is the process of undoing linear distortions pirated by the channel on the transmitted data signal. The noise effects are taken care off by providing sufficient minimum distance between the decoded constellation points. In multicarrier systems where the symbol lengths are much longer than the duration of impulse response of the channel, it is sufficient to perform Frequency Domain Equalization (FEQ) 900 of the demodulated data. This framer renders DMT system less susceptible to time domain impulsive noise as it gets averaged out over a long symbol period. However, very long symbols require large memories and computation. In addition, they generate large latency between the data input to the transmitter and data availability at the output of the decoder, as the decoder must process a very large amount of information to retrieve the transmitted symbol. In order to avoid large symbol lengths, but still achieve an effect of reduced impulse response length, it is customary to use a Time Domain Equalizer (TDE) 750 before the demodulator of Fig. 1. In general, TDE is a digital Finite Impulse Response (FIR) filter whose purpose is to undo the effect of the channel and consequently, the combined impulse response of the channel and TDE has much shorter length compared to that of the channel alone. The TDE, which is also referred to as the pre-equalizer in the literature, is trained such that the effective channel response, as observed at the output of the TDE (i.e., the combined impulse response length), is limited to L samples, where L is predestinated. If the transmitted symbol has length N, it becomes necessary to have L additional samples as part of the transmit frame. The L distorted samples at the output of TDE could be discarded and the remaining samples demodulated and equalized by the FEQ for ISI and ICI compensation. L distorted samples come from the fact that the combined impulse response of the channel and TDE is limited to L samples and hence residual ISI is also limited to L samples. In general L and N are chosen in such a way that N » L. A preferred method of addition of L samples is known as prefixing, where the last L samples of the transmit frame are duplicated and prepended to the frame. The throughput of the system would thus be N/(N+L). The receiver has to wait for L extra samples for each frame before performing a demodulation. This strategy is known as the guard period or cyclic prefix strategy. The TDE strategy combined with cyclic prefix achieves a good compromise between minimization of latency and the amount of signal i processing and memory required, and maximization of data throughput efficiency. The use of cyclic prefix and the employment of TDE to reduce the effective impulse response to at most the length of the cyclic prefix for ISI and ICi compensation are well known. The technique implies that the TDE should be trained in such a manner that it actually achieves this goal. The training involves updating the filter taps using the error in the filter output. A preferred method of doing this is to consider an effective or target response of the channel, which is limited to L samples. The filter generating die target response is referred to as an estimator. The input to the target response is the same as the input to the channel but suitably delayed to take the channel delay into account. The TDE should be trained in such a manner that the TDE output is the same as the output of the target response. It is possible to fix the target response a priori, and adapt the TDE to match the TDE output with the target output. But for severely distorted channels, a chosen target response could mm out to be sub-optimal. This situation is avoided by adapting the target response also. in one conventional embodiment for simultaneous adaptation of TDE and the estimator, (see J. Chow and J. Coffin, "Method for equalizing a multicarrier , signal in a multicarrier communication system", United States Patent number 5285474, Feb., 1994), the adaptation is performed in the frequency domain combined with a rectangular windowing in the time domain. The procedure training is as follows; the transmitter of the first modem repeatedly transmits a frame of known pseudorandom sequence over the channel. The second modem, on receipt of the frame, uses it as the input to the TDE, which is represented in frequency domain. The reference signal (the same pseudorandom sequence transmitted by the transmitter, which is known to the receiver) for training is generated by the receiving modem, using which, the TDE and the estimator are updated. This process, however, does not ensure that the time response of the estimator is limited to L samples. It is also desirable to limit the time response of the TDE to a small number of taps, since during data mode, filtering of the cyclic prefixed data will have to be carried out in the time domain. The time response of TDE is limited to M samples, where M could be much smaller than N. The choice of M depends very much on the computing power of the processor being used for processing received data signal. In general, M is chosen to be some power of 2 for efficient implementation of the filtering process using FFT techniques. To constrain the number of time domain samples, the frequency domain samples of both estimator and TDE are transformed to time domain after each update. For each filter in the time domain, L samples for the estimator and M samples for the TDE, the samples that have the highest energy are chosen and the rest of the samples are set to zero. This process is known as windowing. The modified samples are again transformed into the frequency domain and used for filtering the next frame of channel output and reference signals. One of the problems associated with the approach described above is due to windowing. Unless the number of significant time-domain samples (samples having high energy) is much smaller than the length (L samples for the estimator and M samples for the TDE) of TDE or estimator, the abrupt truncation caused by windowing could result in dips in the spectrum, leading to sub-optimal performance. In this case, windowing means multiplying (TDE or estimator) by a rectangular waveform with M (for TDE) or L (for estimator) non-zero samples in time domain. Fourier transform (FT) of this rectangular window is a sine with spectral nulls (zeros of FT). Multiplication of TDE (or estimator) in time domain by the rectangular window is equivalent to convolving FT of the TDE with that of the window in frequency domain. The spectral nulls appear in the FT of the windowed TDE, if TDE taps have not sufficiently died down (insignificant or have energy very close to zero) at the beginning and end of the windowed waveform. Appearance of spectral nulls indicates that SNR (signal to noise ratio) win be very low at those frequency bands rendering them unsuitable for data transmission. This problem can be avoided by an intelligent choice of initial values of the TDE and estimator followed by complete time domain training. Additional smoothing (by multiplying with a non-rectangular window) of the taps ensures that the number of significant samples is much smaller than L, so that the ratio of energy inside the range of the estimator to the energy outside its range is maximized to avoid residual ISI. A significant problem with time domain training using the Least Mean Square (LMS) algorithm is that it could be time consuming and good convergence is not always assured, as the search space is non-convex (in general). Another problem associated with this method occurs during the initial stages of the algorithm, since the best L samples of the estimator and the best M samples of the TDE are chosen and the chosen TDE taps are shifted to make them the first M taps. This, in effect, leads to a variable delay (since the location of the best M taps changes from iteration to iteration initially) which may cause oscillatory behaviour during the initial stages. Therefore, what is needed is a system and method for time domain training that is efficient and accurate, and converges to a good solution by means of proper initialization of the taps. There are several methods of initialization that provide good equalization. Specific choices of initialization are made depending on other constraints of the problem. These will be further elaborated up on in the body of the invention. SUMMARY OF THE INVENTION This invention proposes the maintenance of TDE and estimator in time domain, with lengths M and L, respectively. In order to obtain the best set of TDE and estimator taps, a frequency-domain-based method for channel delay estimation is proposed. The method also yields good starting points for the time-domain adaptation, which enable faster convergence to a low Mean Square Error (MSE) solution. The TDE and estimator taps are constrained during training in order to get a desired frequency response for the TDE. The advantage of the proposed scheme is that it ensures explicit constraining of the TDE and estimator to a finite number of taps by maintaining and updating them completely in the time domain. By choosing the starting point of the adaptation properly and by computing an accurate estimate of the channel delay, along with constraining the taps, faster convergence to a good solution is ensured. Fast convergence results in reduced training time. Proper estimation of the channel delay also ensures fiexibiUty in the phase response of the estimator (i.e., the estimator need not be minimum phase as is the case with conventional decision feedback equalizers). After the TDE and the estimator are sufficiently trained, the final phase of training with the pseudorandom periodic sequence is carried out. In this phase, the TDE is fixed and the FEQ is trained. The input to FEQ training is the FFT of TDE output, while the reference is the pseudorandom periodic sequence that earlier was used as the input to the estimator. The FEQ training involves running N single-tap Least Mean Square (LMS) algorithms, with one complex tap per channel. ■Finally, reQ and TDE taps are jointly adapted using a known aperiodic, cyclic-prefixed pseudorandom sequence in order to converge to the solution that actually minimizes the MSE for random data. The same procedure can be used to adapt TDE and FEQ during data mode, thus facilitating efficient handling of time varying channels. More specifically, this invention proposes a complete time domain training of the TDE and channel estimator for muJticarrier communication systems. In accordance with the present invention, the system computes the estimate of the channel delay using the channel output and the reference signal. The estimate is computed based on the required confidence level and the SNR at the channel output. The system also computes a good starting point for the adaptation of TDE and estimator in time domain. The choice of the starting point is problem dependent. In one embodiment, the starting values of the TDE taps are obtained by using a sub-space projection method, which ensures that the projected taps are the best approximation of the original estimate in the means squared sense. The system determines optimal adaptation step sizes using the channel output, in order to facilitate fast training, and constrains TDE and estimator taps to converge to a desired solution. In a further embodiment, a weighting scheme for the taps in order to maximize the ratio of energy within the estimator band to the energy outside it and to avoid dips in the spectmm is disclosed, using a suitable Gaussian windo.w for weighting. Finally, the present invention provides shortened training .time due to proper delay estimation, proper starting point and step sizes and improvements in training procedure. The present invention also proposes further training of TDE and FEQ using a cyclic prefixed aperiodic pseudorandom sequence. Specifically, a method is disclosed for simultaneous adaptation of TDE taps in the time, domain and FEQ taps in the frequency domain, where the TDE is fixed and a filter of small length is trained. The new filter is used to refine the TDE, and is used in data mode to facilitate the adaptation of TDE and FEQ to time varying channels. BRIEF DESCRIPTION OF THE DRAWINGS ^J^ Figure 1 is a block diagram of a multicarrier communication system ,\ ^ ., Figure 2 is a block diagram of circuitry for implementing time domain equalizer and estimator training in accordance with the present invention. Figure 3 is a flow chart illustrating the process of time domain equalizer and estimator training in accordance with the present invention. Figure 4 is a block diagram of circuitry for implementing TDE and FEQ training in accordance with the present invention. Figure 5 is a flowchart for channel delay estimation. Figure 6 depicts the TDE and estimator initialization procedure. Figure 7 is a flow diagram of TDE and estimator training. Figure 8 is a flow chart of TDE and FEQ training. DETAILED DESCRIPTION OF THE INVENTION The following is a detailed description of the preferred embodiment of the invention. In the sequel, lower case letters denote time domain quantities while corresponding frequency domain quantities are denoted by capital letters. The time domain training of TDE and estimator is first described. This is followed by the procedure for simultaneous adaptation of TDE and FEQ using aperiodic pseudorandom data. The block schematic of TDE and estimator training in time domain is shown in Figure 2. The pseudorandom periodic signal of length N samples, denoted by x(n), is input to the channel lOOO through a digital to analog converter (DAC). The output of the channel is sampled at Nyquist rate by an analog to digital converter (ADC) to produce sampled signal y(n), which is input to the TDE 1100. The TDE output, denoted by z(n), is input to the adder 1200. The reference signal, which is the same as x(n); is generated at the receiver and passed through a delay unit 1300, which introduces a delay of D. This delay is introduced to compensate for the delay introduced by the channel and TDE. The delayed reference signal is then filtered (discrete convolution with the estimator, which is an FIR filter) by the estimator 1400 to generate the output c(n). The TDE tap vector at instant n is denoted by a(n) and the estimator taps at instant n denoted by b(n). The output of the estimator, c(n), is fed to the adder 1200, but with the opposite sign. The output of the adder 1200 is the error e(n), which is used to update the tap vectors a(n) and b(n) using LMS algorithm. The internal states of TDE and estimator is represented by 3^(n) and x(n), respectively. The flow diagram of the TDE and estimator training is provided in Figure 3. The receiver, when it is known that the periodic pseudorandom training sequence is being received, enters the delay estimation phase 1500. The procedure for delay estimation is described later. Once the delay estimation is complete, the receiver enters the TDE and estimator training phase 1600. During this phase, the error between the TDE and estimator outputs is used to adapt the two filters. The procedure of adaptation is described in detail later. The normalization phase 1700 involves performing suitable scaling of the filter taps in order to achieve a prefixed energy level. During the weighting phase 1800, the estimator is windowed by a pre-determined Gaussian in order to limit the number of non-zero samples of the estimator. Each of the phases of Figure 3 is described below. Estimation of channel delay and initialization of taps The delay estimation process is started when a pseudorandom periodic signal is received at the receiver. Several frames (each frame comprising N samples) of the channel output and the reference signal are used for the estimation process. Each frame of channel output and the reference signal are accumulated and transformed to the frequency domain using an N point FFT algorithm. The FFT of the reference signal frame is denoted by X and that of channel output by Y. Sampled channel output y(n) is related to the sampled channel input x(n) by convolution : y{n) = 2; h(n)x(n -i) . (1) i = 0 where h(n) is the sampled (at the same sampling rate as that of the signals) impulse response of the channel. Y(k,i) and X{k,i) are FFT coefficients of x(n) and y(n) respectively corresponding to the i-th data frame. To obtain a good starting point. we start with an N point FIR filter he(n) which equalizes the channel h(n). The starting point is found out in frequency domain by minimizing the error E measured over Me data frames. M, -1 E= 5;(X(k,i)-He(k)Y(k,i)}{X(k,i)-He(k)Y(k,i)l* . (2) i=0 where He(k:) is the FFT coefficient of he(n) and * indicates complex conjugation. Minimization of E yields: M,-1 X Y(k,i)X(k,i) He(k) - ^^ , Vk = 0,l N-1. (3) M^ -1 5^ Y{k,i)Y(k,i) i=0 The starting point he(n) is obtained from N point IFFT of He(k) and choosing M contiguous samples of of he(n) having maximum energy. Clearly, he(n) belongs to the discrete Hilbert space ( V ) of dimension N. To set the starting taps of TDE, he(n) is truncated to M samples by projecting it orthogonally onto a subspace of V ( V, ) such that vectors belonging to V, have only M contiguous non-zero elements. The taps are multiplied by a Gaussian window to get better time and frequency localization. These windowed M samples are TDE starting taps for adaptation. It is obvious to those skilled in the art that there are other methods of initialization that are effective in specific situations. For example, in certain applications, equalization is required in only a certain frequency band of interest. In such cases, the requirement is to suppress the undesirable out of band signals since they also affect the equalizer performance. The TDE taps computed as specified above are convolved with a suitable filter and used for initialization. Equivalently, the He(k) can be multiplied by the desired filter frequency response and then transformed to the time domain. An altemative method of initialization is to set the estimator to the channel and set the TDE taps to a filter that is designed to suppress the out of band signals. The expression for the initial estimator taps can be similarly derived.-Convolution of the estimator with a suitable filter for suppression of out of band signals can also be carried out in a similar way. Delav Estimation The channel frequency response H(.) can be estin^ted in a similar way. The slope of H(.) gives an estimate of the net delay of the channel. If the channel is linear phase, the angles of H(.) form a ramp. However, whenever the channel is nonlinear phase, the slope of the angles of the elements of vector H gives an estimate of the equivalent average group delay imparted by the channel. This can be used as a good starting point for further delay estimation (which is done automatically in fime domain adaptation). A straight line fit can be carried out for the angles of H(k) and the slope of this fit used to give an estimate of the channel NXwEi]Q[.] Och = -^ (4) delay. Another possible method is to use the noise statistics in each subchannel to compute the optimal slope estimate, given by where Q[.] are the angles of H[.] and Dch is the estimated channel delay. Tlie weights W[.] are based on the SNR in each subchannel and are given by i"R"^i.^"R""iV-(l"R""/^)^ 1=[1,1,...,1]^ ; A^=[0,1....,N-1]" (5a) where R is the autocorrelation matrix of the noise corrupting unwrapped angles and Derivation of this optimal linear estimator is detailed in K. Barman and M. T. Arvind, "A minimum variance single frequency estimator using recursive least squares estimate of^ n4i6e(:^atadsti(^"!LMidwest^ on Ciri^is and Systems, 1998. In this case, phase noise in different subchannels is normally and independently distributed with variance l/(2SNRi), where SNRj is the SNR of i-th subchannel on linear scale. Consequently, R becomes Instead of using the channel frequency response H(.) for delay estimation, the equalizer frequency response He(.) can be used for delay estimation. Direct estimation of the angle of H is susceptible to wrapping effects. That is, when an angle is computed, its principal value (a value lying between -Hi to -TI) results and anything falling outside will be translated to get an equivalent value within this range leading to improper computation of the slope of the angle. This problem is remedied by doing phase unwrapping after the angle values are computed. Whenever the channel delay is approximately N/2, the angle estimate is close to +/- 71. In such cases, phase wrapping is likely to occur and phase unwrapping might fail. The above delay estimation procedure may not yield the right value. A rough value of the delay is obtained by the location of the peak tap of h(.). If this value is close to N/2, the received frame is further delayed by a suitable amount. The delay estimation is then carried out in the normal fashion. For very long channels, the number of contiguous channels over which the SNR is greater than 6dB might be very small. If the channel estimate is computed over a very small number of samples, it will not be reliable. This problem is avoided by computing the H vector as an average of several frames of I^FT of channel output; the length of averaging chosen based on the SNR in the channels and the number of samples required to obtain a reliable estimate of the channel delay. A pseudocode for delay estimation is described below (Figure 5): 1. Estimate the SNR in each channel using a predesignated number of channel output frames (block 510). 2. Consider only those sub-channels for which SNR is above 6dB (good sub-channels) (block 515). 3. Average FFT coefficients of the channel outputs over the number of frames decided in 2 (block 520). 4. Compute the H vector as described above using the averaged frame. For low SNR subchannels, obtain value of H(k) by extrapolation (block 525). 5. Compute h(n) by taking IFFT of H(.) (block 530). If the peak tap of h(.) is close to N/2, shift the received frame and recompute H (blocks 535, 540, 545). 6. Compute weight vector W[.] for optimal slope estimation (block 550). 7. Compute the delay estimate D^h as indicated above (block 555). TDE and Estimator training The TDE and estimator training involve several phases, each of which is described below. Training Initialization Before the training is started, the TDE internal state vector x of length (M-1) is set to 0. Similarly the estimator internal state y of length L-1 is also set to 0. The TDE and estimator are FIR filters. Their outputs depend not only on the present inputs, but on the past inputs also. Output of an FIR filter of length M depends on past M-1 inputs, which are known as the internal states of the filter. The TDE and estimator taps a and b are set to a{0) and b(0) which are computed as described below. The adaptation step sizes for the TDE and estimator, ml and m2, respectively, are also fixed. The procedure for fixing the step sizes could involve computation of the largest eigenvalues of the correlation matrices of the TDE and estimator inputs. In one embodiment, the signal power is computed, which is an upper bound for the largest eigenvalue. The following procedure is used to obtain the starting values of the TDE and estimator taps (Figure 6): 1. He(.) is computed only for those sub-channels where SNR is more than 6dB (block 610). In those sub-channels where SNR is less than 6dB, He(k:) is computed by interpolation or extrapolation (block 615) depending on the position of the sub-channel. One possible way of computing He is by fitting a curve of low order using the values in channels with good SNR. 2. The best M contiguous taps (having maximum energy) of the IFFT of He (block 620) are found. These taps are multiplied by a suitable Gaussian window with M taps (block 625) to get better time and frequency localization of the truncated IFFT. 3. The equalizer starting taps a(0) are initialized to the windowed M taps computed in step 2 (block 630). 4. The estimator b(0) is initialized to a unit vector, with unity in its central position (a delayed discrete impulse), (block 635). The estimator is then normalized (block 640) to a specified energy level so that the estimator and TDE outputs have same energy level. 5. The pseudorandom periodic sequence that forms the input to the estimator is rotated by a pure delay element, which introduces a delay of D samples. D is computed (block 645) from the equation: L 2 D -D^h +Deq-- " (^" where Dgq is the delay introduced by the TDE starting taps a(0) and 172 is the delay of b(0). Adaptation of TDE and Estimator taps The adaptation of TDE and estimator taps is performed at every sample. At any instant n, the TDE output z(n) and the estimator output c(n) are computed and the error e(n) is computed as e(n) = z(n) - c(n). Using this error and the filter inputs at instant n, the taps are adapted by means of the well-known LMS algorithm 15], The TDE and estimator training is depicted in Figure 7. The reference signal for a!daptation is generated (block 710) and passed through the delay unit 715 to obtain a delay of D samples. The output of the delay unit is passed through the estimator 720. The received signal is sampled 725, filtered by the TDE 730. The TDE and estimator outputs are used to compute the error e (735); the taps updated using the error and the filter states (740). Normalization of TDE and Estimator The normalization of the filters to pre-specified energy levels is carried out after each update. Alternatively, the normalization could be carried out only when either of the filter energies drops below the pre-specified energy level. Normalization is performed to avoid convergence of the taps to the trivial zero solution, i.e., both the TDE and estimator taps will die down to zero. Weighting the Estimator taps Once every frame or every few frames, weighting of the estimator window could be carried out in order to limit the significant number of non-zero taps of the estimator. If the number of taps of the estimator is not well contained to within L samples, the estimator output will have significant spectral nulls at every N/L - th sub-carrier, rendering those channels unusable for data transmission as SNR in those channels will be very low. In the preferred embodiment of the invention, the weighting is carried out using a Gaussian window. The variance the Gaussian window is chosen based on the tradeoffs between decreased signal to error levels due to windowing and increased number of spectral nulls due to non-windowing. Once the training with periodic pseudorandom sequence is completed, the next phase of the training, viz., simultaneous adaptation of TDE and FEQ using a known aperiodic pseudorandom sequence, is started. TDE and FEQ training using pseudorandom sequence This phase involves initialization of the FEQ taps using the estimator and subsequent training using a known aperiodic cyclic prefixed pseudorandom sequence. Initialization of the FEQ The starting values of the FEQ taps are computed using the estimator taps learnt during time domain training. The FFT of the estimator is computed and the i-th FEQ tap is set to the reciprocal of the i-th FFT coefficient of the estimator. If some of the FFT coefficients of the estimator turn out to be very small, the corresponding FEQ tap could be set to some suitable starting value. Optionally, the FEQ can also be trained for some time using the periodic pseudorandom sequence earlier used for TDE and estimator training, before entering the following phase. Training TDE and FEQ Figure 4 is a block schematic of the TDE and FEQ training. The inputs x are passed through the channel 2000 and the vector of (N+L) channel outputs y (corresponding to frame length N and cyclic prefix length L) is passed through the TDE taps a 2100 to obtain the TDE output vector z. The ith channel output of a frame is denoted by y(i). N column vectors, y[l], y[2],...,y[N], are formed, where the entries of y[i] are y(i), y(i+l),..., y(i+L-l). Below, the matrix formed by yll], y[2],...,y[N] is denoted by Y and the FFT operation is denoted by the complex matrix P 2200. The B matrix in Fig. 4 is the diagonal matrix formed by the FEQ taps B[1],...,B[N]; 2300. X[.] is the vector of the transmitted pseudorandom sequence without the cyclic prefix, forming the reference signal for adaptation; e[i] is the error measured in the ith channel and e is the vector formed by these errors. In the preferred embodiment of the invention, the error measure for minimization is the sum of squares of errors in each channel. In order to obtain the — = {YP"B"BPY")a-Ke{yP"B"x) 8a update for a and B, partial derivatives of the error measure are computed and the conventional LMS algorithm is used. The partial derivative with respect to a is given by For performing the one-tap LMS for updating the each of the FEQ taps, the procedure for computing partial derivatives is straightforward and is not detailed here. Note that the update equation for TDE taps involves M FFT operations for each frame. However, since the successive rows of the Y matrix are obtained by one right shift followed by a new element in the left most position, the number of operations can easily be reduced further. The TDE and FEQ training is depicted in Figure 8. The sampled receive signal 810 is passed through the TDE 815 and fed to the FFT module 820. The FFT outputs are multiplied with corresponding FEQ taps 825. The reference signal for adaptation of FEQ taps is generated 830. The matrices B and Y are computed 835 and used to update the TDE and FEQ taps 840. A compromise solution, which involves fewer computations, can also be achieved as follows: The TDE could be fixed and a new filter, whose length Ml is much smaller than M, could be placed at the output of the TDE. The Ml unknown taps of this filter can be found using the same algorithm that is used to modify the TDE taps. The order of computation now reduces a multiple of MI, which is much smaller than M. Finally, once the filter is trained, it can be convolved with the original TDE and the new TDE obtained by taking the best M contiguous taps of this filter. The proposed procedure facilitates simultaneous adaptation of TDE and FEQ even during data mode. It is thus possible to adapt to time varying channels, leading to improved performance and long term connectivity. Although an aperiodic pseudorandom sequence is referred to throughout, the procedure is equally valid for pseudorandom sequences, which are periodic, but with period large compared to the frame length N. Incomplete Equalization In certain situations, a given length of the equalizer may not be sufficient to constrain the effective impulse response to L taps. During training of FEQ, the perfommnce deteriorates due to residual ISI. One possible method of compensating this is as follows. Partition the set of subchannels in to two subsets with the following properties. One of the sets (set A) contains signals that are orthogonal to each other over a length of samples less than N (say Nl). Designate the other set as B. The FFT of the TDE output (after removal of cyclic prefix) is computed. The outputs of the subchannels in set B are decoded to obtain the constellation symbols. Reconstruct the time domain samples corresponding to the decoded symbols of set B and subtract them from the TDE output frame. The resulting time domain samples now correspond to those of set A and the transient. Doing an FPT over NI samples will recover the symbols of set A. These Nl samples can be chosen such that the transient part is avoided. For example, set A could consist of all the subchannels with even indices, periodic with length Nl = N/2. Set B would consist of the odd subchannels. Those skilled in the art would easily recognize that there are several minor variants of the preferred embodiment, both algorithmic as well as implementational, which would lead to similar results. These include • A frame by frame adaptation of taps instead of a sample by sample adaptation. This would reduce the number of tap updates and the error measure minimized. For frame by frame update, taps could be maintained in time domain, while error could be computed in the frequency domain. N • The TDE may be trained and may operate at a higher sampling rate than the minimum required. This helps avoiding the effects of aliasing. However, the number of TDE taps may increase because of the higher sampling rate. In such cases, intermittent taps of TDE or estimator could be forced to zero in order to minimize computation and training time. For example, if alternate taps of TDE are set to zero, the frequency response is constrained to be symmetric about one-fourth of the sampling rate. Complete implementation in software or hardware or partial hardware/software implementation. Instead of the conventional LMS algorithm, some of its variants could be employed for stability reasons. Further, the LMS objective function could itself be altered to avoid the trivial zero solution and some gradient descent procedure used to solve it; which would avoid the need for normalization. Variations in the above described delay estimation procedure, wiiich could involve averaging of the channel output frames for improving the SNR, or employing the correlation information to confute a delay estimate. If the correlation information is not known, it could be recursively computed using the channel outputs over a few frames. Variants of the procedure for computing the starting values of the taps for adaptation: The projection mechanism employed for computing the required L taps from the available N taps could also be different. Further, in order to obtain a smooth profile for the starting value of the taps, windowing by non-Gaussian kernels could also be employed. Other methods of constraining the TDE and estimator starting values, based on the given problem, can also be employed. These include initializing TDE or estimator to some desired filter. Weighting by a Gaussian window may be made optional depending on the energy of edge taps in comparison with the energy in the taps towards the center. We claim: 1. A method for estimating channel error and delay in a plurality of channels for a multi-carrier communication system using frequency division multiplexing, in which a training mode is used, wherein estimating channel error comprises the steps of: receiving a signal output from the channel; receiving a reference signal; sampling an impulse resporise of the channel; transforming the reference signal, impulse channel response, and charier output into frequency domain; estimating a starting set taps tux a time domain equalizer designed to remove distortions from the charnel, the estimation being determined responsive to the frequency domain transformation of the reference signal, impulse channel response, and channel output. 2. The method as claimed in claim 1 wherein estimating a starting point comprises: minimizing an error value of a logical combination of he frequency domain transformation of the reference signal, the frequency domain transformation of the chaimels output, and the frequency domain transformation of the channel response. 3. The method as claimed in claim 2 wherein minimized error value is determined by: where H{k) is the Fast Fourier Transform (FFT) coefficient of an N-point finite impulse response filter for equalizing the channel, Y(k,i) is a FFT coefficient of a sampled output signal of tiie channel, wherein the sampled output signal is sampled N times, X(k,i) is the FFT coefficient of a sampled output signal of the channel, wherein the sampled output signal is sampled N times, X{k,i) is the FFT coefficient of a reference signal, and indicates complex conjugation and *indicates complex conjugation. 4. The method as claimed in claim 3 comprising: transforming the minimized error value into time domain; designating the estimated starting point as the transformed time domain representation of the minimized error value. 5. The method as claimed in claim 3 comprising: transforming the minimized error value into time domain; projecting the time domain transformation orthogonally onto a subspace of a discrete Hilbert space of a predetermined dimension. 6. The method as claimed in claim 5 comprising: selecting contiguous samples of tiie transformed minimized error value having a highest energy value. 7. The method as claimed in claim 6 comprising: windowing the selected contiguous samples. 8. The method as claimed in claim 6 wherein M contiguous samples are selected, wherein M is a value much less than a symbol period of the channel output signal. 9. The method as claimed in claim 3 comprising: computing an angle for H(k); and estimating channel delay responsive to the computed angle. 10. A method for estimating chaimel error and delay in a plurality of channels for a multi-carrier communication system as claimed in claim 1, wherein estimating delay comprises: estimating a signal-to-noise ratio in each channel; selecting sub-channels having an estimated signal-to-noise ratio above a predetermined threshold; averaging fast fourier transform coefficients of the channel outputs over a number equal to the selected sub-channels; computing a vector representing a fast fourier coefficient of a normalized channel output (H(k)), wherein the normalized channel output is determined responsive to the averaged fast fourier transform coefficients of the channel output; computing a vector (Q(k)) representing phase angles of H(k); computing a weighting window responsive to the computed Q{k) vector; and determining an estimate of the delay of the channel responsive to the computed weighting window. claimed in claim 1 to recover a signal distorted by transmission through a channel, comprising: receiving output signal from the channel; trar\smitting the output signal from the channel through the time domain equalizer; to obtain a TDE output vector; transforming the TDE output vector into a frequency domain to obtain frequency equalization taps; generating a matrix from the frequency equalization taps; receiving a reference signal; determining an error generated by the channel responsive to comparing the received reference signal and the matrix generated from the frequency equalization taps; and minimizing the distortion introduced by the channel responsive to the determined error. 16. The method as claimed in claim 15 wherein the reference signal is a pseudorandom sequence. 17. The method as claimed in claim 16 wherein the determined error is determined as the sum of squares of errors generated from a plurality of channels in the system. 18. An apparatus for receiving data transmitted from a remote site, and for compensating the received data for errors introduced during transmission of the data as claimed in claim 15 comprising: a reference signal generator, for generating a reference signal equivalent to a test signal transmitted to the time domain equalizer; a delay unit, coupled to the reference signal generator, for adding a delay to the reference signal, wherein the delay is selected to approximate delay introduced during transmission of tiie test signal an estimator filter, coupled to the delay unit, for filtering the delayed reference signal to compensate for the delay introduced by the delay imits; a time domain equalizer filter, coupled to receive test signals and data signals, for equalizing errors introduced during the transmission of the data signal in time domain; a comparator, coupled to the time domain equalizer filter and the estimator filter to receive the output of the time domain equalizer filter and the output of the estimator filter, for determining a filter error, wherein the filter error is determined as a difference between the output of the estimator filter and the output of the time domain equalizer filter; and coefficient an adaptor, coupled to the comparator, for adjusting taps of the time domain equalizer filter and tie estimator filter responsive to the filter error.

Full Text

FIELD OF INVENTION
"This invention pertains to high speed data transmission systems using multiple number of carriers and more particularly, the art of equalizing the distortion effects introduced by the transmission medium in order-to retrieve the transmitted signal accurately.
BACKGROUND OF THE INVENTION
A multi carrier transmission system is one which employs FDM (frequency division multiplexed) sub-carriers for transmission. A typical multicarrier system is depicted in Fig. 1. It shows serial input data coming in the form of bits being converted by a serial to parallel converter 100, which also possibly encodes the frame of data (a data frame consists of a sequence of bits). The encoded data is modulated by the multicarrier modulator 200 to bring the signal to be transmitted within the desired pass-band of the channel. In most multicarrier systems, the preferred method of modulation is Inverse Fast Fourier Transform, IFFT. In these systems, data are generated as a serial stream of bits. But, prior to modulation, the system must determine the number of bits that can be assigned to each sub-carrier, as there will be several parallel sub-channels. A serial to parallel converter takes the input bit stream and distributes those bits over several sub-carriers. The parallel to serial block 300 performs the reverse operation (the notion of cyclic

prefix will be explained in the body of the invention). The modulated data is converted to analog signal by a Digital to Analog converter (DAC) 400. filtered and input to the channel 500. The noise added during the passage of the signal through the channel is depicted by block 600. At the receiver, the received signal is filtered, sampled using an Analog to Digital Converter 700 and passed through the Time Domain Equalizer (TDE) 750. After cyclic prefix removal and serial to parallel conversion 800, the signal is demodulated using the Fast Fourier Transform (FFT) technique; the demodulator is indicated by block 850. The demodulated frame of samples is passed through a Frequency domain Equalizer 900, decoded and passed through a parallel to serial converter 950 to obtain the transmitted bits.
The transmitted data, while passing through the channel 500, suffers various distortions. This is because a channel, in general, attenuates and delays different frequencies by different amounts. A data symbol can be defined as a modulated waveform lasting over a definite period (symbol period) of time and represents a combination of complex points in the signal constellation on different sub-carriers. The distortion caused in a symbol due to overlap by previous and subsequent symbols is known as Inter Symbol Interference (ISI) and the distortion in data on one carrier due to data on the other carriers is called Inter Carrier Interference (ICI). Further distortions in transmitted data result due to thermal and crosstalk

noise. The decoder, in the presence of these distortions, will make incorrect decisions leading to data errors. Decision made by the decoder is a complex signal constellation point. In presence of noise and ISI, the decoded point might be different from the transmitted point. In order to achieve large data transmission rates with low data errors, it is necessary to compensate for the distortions introduced by the channel.
A method of compensating for ISI and ICI is to perform equalization of the received data. Equalization is the process of undoing linear distortions pirated by the channel on the transmitted data signal. The noise effects are taken care off by providing sufficient minimum distance between the decoded constellation points. In multicarrier systems where the symbol lengths are much longer than the duration of impulse response of the channel, it is sufficient to perform Frequency Domain Equalization (FEQ) 900 of the demodulated data. This framer renders DMT system less susceptible to time domain impulsive noise as it gets averaged out over a long symbol period. However, very long symbols require large memories and computation. In addition, they generate large latency between the data input to the transmitter and data availability at the output of the decoder, as the decoder must process a very large amount of information to retrieve the transmitted symbol. In order to avoid large symbol lengths, but still achieve an effect of reduced impulse response length, it is customary to use a Time Domain

Equalizer (TDE) 750 before the demodulator of Fig. 1. In general, TDE is a digital Finite Impulse Response (FIR) filter whose purpose is to undo the effect of the channel and consequently, the combined impulse response of the channel and TDE has much shorter length compared to that of the channel alone. The TDE, which is also referred to as the pre-equalizer in the literature, is trained such that the effective channel response, as observed at the output of the TDE (i.e., the combined impulse response length), is limited to L samples, where L is predestinated. If the transmitted symbol has length N, it becomes necessary to have L additional samples as part of the transmit frame. The L distorted samples at the output of TDE could be discarded and the remaining samples demodulated and equalized by the FEQ for ISI and ICI compensation. L distorted samples come from the fact that the combined impulse response of the channel and TDE is limited to L samples and hence residual ISI is also limited to L samples. In general L and N are chosen in such a way that N » L. A preferred method of addition of L samples is known as prefixing, where the last L samples of the transmit frame are duplicated and prepended to the frame. The throughput of the system would thus be N/(N+L). The receiver has to wait for L extra samples for each frame before performing a demodulation. This strategy is known as the guard period or cyclic prefix strategy. The TDE strategy combined with cyclic prefix achieves a good compromise between minimization of latency and the amount of signal

i processing and memory required, and maximization of data throughput efficiency.
The use of cyclic prefix and the employment of TDE to reduce the effective impulse response to at most the length of the cyclic prefix for ISI and ICi compensation are well known. The technique implies that the TDE should be trained in such a manner that it actually achieves this goal. The training involves updating the filter taps using the error in the filter output. A preferred method of doing this is to consider an effective or target response of the channel, which is limited to L samples. The filter generating die target response is referred to as an estimator. The input to the target response is the same as the input to the channel but suitably delayed to take the channel delay into account. The TDE should be trained in such a manner that the TDE output is the same as the output of the target response. It is possible to fix the target response a priori, and adapt the TDE to match the TDE output with the target output. But for severely distorted channels, a chosen target response could mm out to be sub-optimal. This situation is avoided by adapting the target response also.
in one conventional embodiment for simultaneous adaptation of TDE and
the estimator, (see J. Chow and J. Coffin, "Method for equalizing a multicarrier ,
signal in a multicarrier communication system", United States Patent number 5285474, Feb., 1994), the adaptation is performed in the frequency domain combined with a rectangular windowing in the time domain. The procedure
training is as follows; the transmitter of the first modem repeatedly transmits a frame of known pseudorandom sequence over the channel. The second modem, on receipt of the frame, uses it as the input to the TDE, which is represented in frequency domain. The reference signal (the same pseudorandom sequence transmitted by the transmitter, which is known to the receiver) for training is generated by the receiving modem, using which, the TDE and the estimator are updated. This process, however, does not ensure that the time response of the estimator is limited to L samples. It is also desirable to limit the time response of the TDE to a small number of taps, since during data mode, filtering of the cyclic prefixed data will have to be carried out in the time domain. The time response of TDE is limited to M samples, where M could be much smaller than N. The choice of M depends very much on the computing power of the processor being used for processing received data signal. In general, M is chosen to be some power of 2 for efficient implementation of the filtering process using FFT techniques. To constrain the number of time domain samples, the frequency domain samples of both estimator and TDE are transformed to time domain after each update. For each filter in the time domain, L samples for the estimator and M samples for the TDE, the samples that have the highest energy are chosen and the rest of the samples are set to zero. This process is known as windowing. The modified samples are again transformed into the frequency domain and used for filtering the

next frame of channel output and reference signals.
One of the problems associated with the approach described above is due to windowing. Unless the number of significant time-domain samples (samples having high energy) is much smaller than the length (L samples for the estimator and M samples for the TDE) of TDE or estimator, the abrupt truncation caused by windowing could result in dips in the spectrum, leading to sub-optimal performance. In this case, windowing means multiplying (TDE or estimator) by a rectangular waveform with M (for TDE) or L (for estimator) non-zero samples in time domain. Fourier transform (FT) of this rectangular window is a sine with spectral nulls (zeros of FT). Multiplication of TDE (or estimator) in time domain by the rectangular window is equivalent to convolving FT of the TDE with that of the window in frequency domain. The spectral nulls appear in the FT of the windowed TDE, if TDE taps have not sufficiently died down (insignificant or have energy very close to zero) at the beginning and end of the windowed waveform. Appearance of spectral nulls indicates that SNR (signal to noise ratio) win be very low at those frequency bands rendering them unsuitable for data transmission. This problem can be avoided by an intelligent choice of initial values of the TDE and estimator followed by complete time domain training. Additional smoothing (by multiplying with a non-rectangular window) of the taps ensures that the number of significant samples is much smaller than L, so that the

ratio of energy inside the range of the estimator to the energy outside its range is maximized to avoid residual ISI.
A significant problem with time domain training using the Least Mean Square (LMS) algorithm is that it could be time consuming and good convergence is not always assured, as the search space is non-convex (in general).
Another problem associated with this method occurs during the initial stages of the algorithm, since the best L samples of the estimator and the best M samples of the TDE are chosen and the chosen TDE taps are shifted to make them the first M taps. This, in effect, leads to a variable delay (since the location of the best M taps changes from iteration to iteration initially) which may cause oscillatory behaviour during the initial stages. Therefore, what is needed is a system and method for time domain training that is efficient and accurate, and converges to a good solution by means of proper initialization of the taps.
There are several methods of initialization that provide good equalization. Specific choices of initialization are made depending on other constraints of the problem. These will be further elaborated up on in the body of the invention.
SUMMARY OF THE INVENTION
This invention proposes the maintenance of TDE and estimator in time domain, with lengths M and L, respectively. In order to obtain the best set of TDE

and estimator taps, a frequency-domain-based method for channel delay estimation is proposed. The method also yields good starting points for the time-domain adaptation, which enable faster convergence to a low Mean Square Error (MSE) solution. The TDE and estimator taps are constrained during training in order to get a desired frequency response for the TDE.
The advantage of the proposed scheme is that it ensures explicit constraining of the TDE and estimator to a finite number of taps by maintaining and updating them completely in the time domain. By choosing the starting point of the adaptation properly and by computing an accurate estimate of the channel delay, along with constraining the taps, faster convergence to a good solution is ensured. Fast convergence results in reduced training time. Proper estimation of the channel delay also ensures fiexibiUty in the phase response of the estimator (i.e., the estimator need not be minimum phase as is the case with conventional decision feedback equalizers).
After the TDE and the estimator are sufficiently trained, the final phase of training with the pseudorandom periodic sequence is carried out. In this phase, the TDE is fixed and the FEQ is trained. The input to FEQ training is the FFT of TDE output, while the reference is the pseudorandom periodic sequence that earlier was used as the input to the estimator. The FEQ training involves running N single-tap Least Mean Square (LMS) algorithms, with one complex tap per channel.

■Finally, reQ and TDE taps are jointly adapted using a known aperiodic, cyclic-prefixed pseudorandom sequence in order to converge to the solution that actually minimizes the MSE for random data. The same procedure can be used to adapt TDE and FEQ during data mode, thus facilitating efficient handling of time varying channels.
More specifically, this invention proposes a complete time domain training of the TDE and channel estimator for muJticarrier communication systems. In accordance with the present invention, the system computes the estimate of the channel delay using the channel output and the reference signal. The estimate is computed based on the required confidence level and the SNR at the channel output. The system also computes a good starting point for the adaptation of TDE and estimator in time domain. The choice of the starting point is problem dependent. In one embodiment, the starting values of the TDE taps are obtained by using a sub-space projection method, which ensures that the projected taps are the best approximation of the original estimate in the means squared sense. The system determines optimal adaptation step sizes using the channel output, in order to facilitate fast training, and constrains TDE and estimator taps to converge to a desired solution. In a further embodiment, a weighting scheme for the taps in order to maximize the ratio of energy within the estimator band to the energy outside it and to avoid dips in the spectmm is disclosed, using a suitable Gaussian

windo.w for weighting. Finally, the present invention provides shortened training .time due to proper delay estimation, proper starting point and step sizes and improvements in training procedure.
The present invention also proposes further training of TDE and FEQ using a cyclic prefixed aperiodic pseudorandom sequence. Specifically, a method is disclosed for simultaneous adaptation of TDE taps in the time, domain and FEQ taps in the frequency domain, where the TDE is fixed and a filter of small length is trained. The new filter is used to refine the TDE, and is used in data mode to facilitate the adaptation of TDE and FEQ to time varying channels.
BRIEF DESCRIPTION OF THE DRAWINGS
^J^ Figure 1 is a block diagram of a multicarrier communication system

,\ ^
., Figure 2 is a block diagram of circuitry for implementing time domain equalizer and estimator training in accordance with the present invention.
Figure 3 is a flow chart illustrating the process of time domain equalizer and estimator training in accordance with the present invention.
Figure 4 is a block diagram of circuitry for implementing TDE and FEQ training in accordance with the present invention.
Figure 5 is a flowchart for channel delay estimation.

Figure 6 depicts the TDE and estimator initialization procedure.
Figure 7 is a flow diagram of TDE and estimator training.
Figure 8 is a flow chart of TDE and FEQ training. DETAILED DESCRIPTION OF THE INVENTION
The following is a detailed description of the preferred embodiment of the invention. In the sequel, lower case letters denote time domain quantities while corresponding frequency domain quantities are denoted by capital letters. The time domain training of TDE and estimator is first described. This is followed by the procedure for simultaneous adaptation of TDE and FEQ using aperiodic pseudorandom data.
The block schematic of TDE and estimator training in time domain is shown in Figure 2. The pseudorandom periodic signal of length N samples, denoted by x(n), is input to the channel lOOO through a digital to analog converter (DAC). The output of the channel is sampled at Nyquist rate by an analog to digital converter (ADC) to produce sampled signal y(n), which is input to the TDE 1100. The TDE output, denoted by z(n), is input to the adder 1200. The reference signal, which is the same as x(n); is generated at the receiver and passed through a delay unit 1300, which introduces a delay of D. This delay is introduced to compensate for the delay introduced by the channel and TDE. The delayed reference signal is then filtered (discrete convolution with the estimator, which is an FIR filter) by the

estimator 1400 to generate the output c(n). The TDE tap vector at instant n is denoted by a(n) and the estimator taps at instant n denoted by b(n). The output of the estimator, c(n), is fed to the adder 1200, but with the opposite sign. The output of the adder 1200 is the error e(n), which is used to update the tap vectors a(n) and b(n) using LMS algorithm. The internal states of TDE and estimator is represented by 3^(n) and x(n), respectively.
The flow diagram of the TDE and estimator training is provided in Figure 3. The receiver, when it is known that the periodic pseudorandom training sequence is being received, enters the delay estimation phase 1500. The procedure for delay estimation is described later. Once the delay estimation is complete, the receiver enters the TDE and estimator training phase 1600. During this phase, the error between the TDE and estimator outputs is used to adapt the two filters. The procedure of adaptation is described in detail later. The normalization phase 1700 involves performing suitable scaling of the filter taps in order to achieve a prefixed energy level. During the weighting phase 1800, the estimator is windowed by a pre-determined Gaussian in order to limit the number of non-zero samples of the estimator. Each of the phases of Figure 3 is described below. Estimation of channel delay and initialization of taps
The delay estimation process is started when a pseudorandom periodic signal is received at the receiver. Several frames (each frame comprising N samples) of the

channel output and the reference signal are used for the estimation process. Each frame of channel output and the reference signal are accumulated and transformed to the frequency domain using an N point FFT algorithm. The FFT of the reference signal frame is denoted by X and that of channel output by Y. Sampled channel output y(n) is related to the sampled channel input x(n) by convolution :
y{n) = 2; h(n)x(n -i) . (1)
i = 0
where h(n) is the sampled (at the same sampling rate as that of the signals) impulse response of the channel. Y(k,i) and X{k,i) are FFT coefficients of x(n) and y(n) respectively corresponding to the i-th data frame. To obtain a good starting point.
we start with an N point FIR filter he(n) which equalizes the channel h(n). The starting point is found out in frequency domain by minimizing the error E measured over Me data frames.
M, -1
E= 5;(X(k,i)-He(k)Y(k,i)}{X(k,i)-He(k)Y(k,i)l* . (2)
i=0
where He(k:) is the FFT coefficient of he(n) and * indicates complex conjugation.

Minimization of E yields:
M,-1
X Y*(k,i)X(k,i)
He(k) - ^^ , Vk = 0,l N-1. (3)
M^ -1
5^ Y*{k,i)Y(k,i) i=0
The starting point he(n) is obtained from N point IFFT of He(k) and choosing M contiguous samples of of he(n) having maximum energy. Clearly, he(n) belongs to the discrete Hilbert space ( V ) of dimension N. To set the starting taps of TDE, he(n) is truncated to M samples by projecting it orthogonally onto a subspace of V ( V, ) such that vectors belonging to V, have only M contiguous non-zero elements. The taps are multiplied by a Gaussian window to get better time and frequency localization. These windowed M samples are TDE starting taps for adaptation.
It is obvious to those skilled in the art that there are other methods of initialization that are effective in specific situations. For example, in certain applications, equalization is required in only a certain frequency band of interest. In such cases, the requirement is to suppress the undesirable out of band signals since they also affect the equalizer performance. The TDE taps computed as

specified above are convolved with a suitable filter and used for initialization. Equivalently, the He(k) can be multiplied by the desired filter frequency response and then transformed to the time domain.
An altemative method of initialization is to set the estimator to the channel and set the TDE taps to a filter that is designed to suppress the out of band signals. The expression for the initial estimator taps can be similarly derived.-Convolution of the estimator with a suitable filter for suppression of out of band signals can also be carried out in a similar way.
Delav Estimation
The channel frequency response H(.) can be estin^ted in a similar way. The slope of H(.) gives an estimate of the net delay of the channel. If the channel is linear phase, the angles of H(.) form a ramp. However, whenever the channel is nonlinear phase, the slope of the angles of the elements of vector H gives an estimate of the equivalent average group delay imparted by the channel. This can be used as a good starting point for further delay estimation (which is done automatically in fime domain adaptation). A straight line fit can be carried out for the angles of H(k) and the slope of this fit used to give an estimate of the channel
NXwEi]Q[.]
Och = -^ (4)

delay. Another possible method is to use the noise statistics in each subchannel to compute the optimal slope estimate, given by
where Q[.] are the angles of H[.] and Dch is the estimated channel delay. Tlie weights W[.] are based on the SNR in each subchannel and are given by
i"R"^i.^"R""iV-(l"R""/^)^
1=[1,1,...,1]^ ; A^=[0,1....,N-1]" (5a)
where R is the autocorrelation matrix of the noise corrupting unwrapped angles
and
Derivation of this optimal linear estimator is detailed in K. Barman and M. T.
Arvind, "A minimum variance single frequency estimator using recursive least
squares estimate of^ n4i6e(:^atadsti(^"!LMidwest^ on Ciri^is and
Systems, 1998. In this case, phase noise in different subchannels is normally and independently distributed with variance l/(2*SNRi), where SNRj is the SNR of i-th subchannel on linear scale. Consequently, R becomes

Instead of using the channel frequency response H(.) for delay estimation, the equalizer frequency response He(.) can be used for delay estimation.
Direct estimation of the angle of H is susceptible to wrapping effects. That is, when an angle is computed, its principal value (a value lying between -Hi to -TI) results and anything falling outside will be translated to get an equivalent value within this range leading to improper computation of the slope of the angle. This problem is remedied by doing phase unwrapping after the angle values are computed.
Whenever the channel delay is approximately N/2, the angle estimate is close to +/- 71. In such cases, phase wrapping is likely to occur and phase unwrapping might fail. The above delay estimation procedure may not yield the right value. A rough value of the delay is obtained by the location of the peak tap of h(.). If this value is close to N/2, the received frame is further delayed by a suitable amount. The delay estimation is then carried out in the normal fashion.
For very long channels, the number of contiguous channels over which the SNR is greater than 6dB might be very small. If the channel estimate is computed over a very small number of samples, it will not be reliable. This problem is avoided by computing the H vector as an average of several frames of I^FT of channel output;

the length of averaging chosen based on the SNR in the channels and the number of samples required to obtain a reliable estimate of the channel delay. A pseudocode for delay estimation is described below (Figure 5):
1. Estimate the SNR in each channel using a predesignated number of channel output frames (block 510).
2. Consider only those sub-channels for which SNR is above 6dB (good sub-channels) (block 515).
3. Average FFT coefficients of the channel outputs over the number of frames decided in 2 (block 520).
4. Compute the H vector as described above using the averaged frame. For low SNR subchannels, obtain value of H(k) by extrapolation (block 525).
5. Compute h(n) by taking IFFT of H(.) (block 530). If the peak tap of h(.) is close to N/2, shift the received frame and recompute H (blocks 535, 540, 545).
6. Compute weight vector W[.] for optimal slope estimation (block 550).
7. Compute the delay estimate D^h as indicated above (block 555).
TDE and Estimator training
The TDE and estimator training involve several phases, each of which is described below.

Training Initialization
Before the training is started, the TDE internal state vector x of length (M-1) is set to 0. Similarly the estimator internal state y of length L-1 is also set to 0. The TDE and estimator are FIR filters. Their outputs depend not only on the present inputs, but on the past inputs also. Output of an FIR filter of length M depends on past M-1 inputs, which are known as the internal states of the filter. The TDE and estimator taps a and b are set to a{0) and b(0) which are computed as described below. The adaptation step sizes for the TDE and estimator, ml and m2, respectively, are also fixed. The procedure for fixing the step sizes could involve computation of the largest eigenvalues of the correlation matrices of the TDE and estimator inputs. In one embodiment, the signal power is computed, which is an upper bound for the largest eigenvalue.
The following procedure is used to obtain the starting values of the TDE and estimator taps (Figure 6):
1. He(.) is computed only for those sub-channels where SNR is more than 6dB (block 610). In those sub-channels where SNR is less than 6dB, He(k:) is computed by interpolation or extrapolation (block 615) depending on the position of the sub-channel. One possible way of computing He is by fitting a curve of low order using the values in

channels with good SNR. 2. The best M contiguous taps (having maximum energy) of the IFFT of He (block 620) are found. These taps are multiplied by a suitable Gaussian window with M taps (block 625) to get better time and frequency localization of the truncated IFFT.
3. The equalizer starting taps a(0) are initialized to the windowed M taps computed in step 2 (block 630).
4. The estimator b(0) is initialized to a unit vector, with unity in its central position (a delayed discrete impulse), (block 635). The estimator is then normalized (block 640) to a specified energy level so that the estimator and TDE outputs have same energy level.
5. The pseudorandom periodic sequence that forms the input to the estimator is rotated by a pure delay element, which introduces a delay of D samples. D is computed (block 645) from the equation:

L
2
D -D^h +Deq-- " (^"

where Dgq is the delay introduced by the TDE starting taps a(0) and
172 is the delay of b(0).

Adaptation of TDE and Estimator taps
The adaptation of TDE and estimator taps is performed at every sample. At any instant n, the TDE output z(n) and the estimator output c(n) are computed and the error e(n) is computed as e(n) = z(n) - c(n). Using this error and the filter inputs at instant n, the taps are adapted by means of the well-known LMS algorithm 15], The TDE and estimator training is depicted in Figure 7. The reference signal for a!daptation is generated (block 710) and passed through the delay unit 715 to obtain a delay of D samples. The output of the delay unit is passed through the estimator 720. The received signal is sampled 725, filtered by the TDE 730. The TDE and estimator outputs are used to compute the error e (735); the taps updated using the error and the filter states (740). Normalization of TDE and Estimator
The normalization of the filters to pre-specified energy levels is carried out after each update. Alternatively, the normalization could be carried out only when either of the filter energies drops below the pre-specified energy level. Normalization is performed to avoid convergence of the taps to the trivial zero solution, i.e., both the TDE and estimator taps will die down to zero. Weighting the Estimator taps
Once every frame or every few frames, weighting of the estimator window could be carried out in order to limit the significant number of non-zero taps of the

estimator. If the number of taps of the estimator is not well contained to within L samples, the estimator output will have significant spectral nulls at every N/L - th sub-carrier, rendering those channels unusable for data transmission as SNR in those channels will be very low. In the preferred embodiment of the invention, the weighting is carried out using a Gaussian window. The variance the Gaussian window is chosen based on the tradeoffs between decreased signal to error levels due to windowing and increased number of spectral nulls due to non-windowing.
Once the training with periodic pseudorandom sequence is completed, the next phase of the training, viz., simultaneous adaptation of TDE and FEQ using a known aperiodic pseudorandom sequence, is started. TDE and FEQ training using pseudorandom sequence
This phase involves initialization of the FEQ taps using the estimator and subsequent training using a known aperiodic cyclic prefixed pseudorandom sequence. Initialization of the FEQ
The starting values of the FEQ taps are computed using the estimator taps learnt during time domain training. The FFT of the estimator is computed and the i-th FEQ tap is set to the reciprocal of the i-th FFT coefficient of the estimator. If some of the FFT coefficients of the estimator turn out to be very small, the corresponding FEQ tap could be set to some suitable starting value. Optionally,

the FEQ can also be trained for some time using the periodic pseudorandom sequence earlier used for TDE and estimator training, before entering the following phase. Training TDE and FEQ
Figure 4 is a block schematic of the TDE and FEQ training. The inputs x are passed through the channel 2000 and the vector of (N+L) channel outputs y (corresponding to frame length N and cyclic prefix length L) is passed through the TDE taps a 2100 to obtain the TDE output vector z. The ith channel output of a frame is denoted by y(i). N column vectors, y[l], y[2],...,y[N], are formed, where the entries of y[i] are y(i), y(i+l),..., y(i+L-l). Below, the matrix formed by yll], y[2],...,y[N] is denoted by Y and the FFT operation is denoted by the complex matrix P 2200. The B matrix in Fig. 4 is the diagonal matrix formed by the FEQ taps B[1],...,B[N]; 2300. X[.] is the vector of the transmitted pseudorandom sequence without the cyclic prefix, forming the reference signal for adaptation; e[i] is the error measured in the ith channel and e is the vector formed by these
errors.
In the preferred embodiment of the invention, the error measure for minimization is the sum of squares of errors in each channel. In order to obtain the
— = {YP"B"BPY")a-Ke{yP"B"x) 8a

update for a and B, partial derivatives of the error measure are computed and the conventional LMS algorithm is used. The partial derivative with respect to a is
given by
For performing the one-tap LMS for updating the each of the FEQ taps, the procedure for computing partial derivatives is straightforward and is not detailed here. Note that the update equation for TDE taps involves M FFT operations for each frame. However, since the successive rows of the Y matrix are obtained by one right shift followed by a new element in the left most position, the number of operations can easily be reduced further.
The TDE and FEQ training is depicted in Figure 8. The sampled receive signal 810 is passed through the TDE 815 and fed to the FFT module 820. The FFT outputs are multiplied with corresponding FEQ taps 825. The reference signal for adaptation of FEQ taps is generated 830. The matrices B and Y are computed 835 and used to update the TDE and FEQ taps 840.
A compromise solution, which involves fewer computations, can also be achieved as follows: The TDE could be fixed and a new filter, whose length Ml is much smaller than M, could be placed at the output of the TDE. The Ml unknown taps of this filter can be found using the same algorithm that is used to modify the TDE taps. The order of computation now reduces a multiple of MI, which is much

smaller than M. Finally, once the filter is trained, it can be convolved with the original TDE and the new TDE obtained by taking the best M contiguous taps of this filter.
The proposed procedure facilitates simultaneous adaptation of TDE and FEQ even during data mode. It is thus possible to adapt to time varying channels, leading to improved performance and long term connectivity.
Although an aperiodic pseudorandom sequence is referred to throughout, the procedure is equally valid for pseudorandom sequences, which are periodic, but with period large compared to the frame length N.
Incomplete Equalization
In certain situations, a given length of the equalizer may not be sufficient to constrain the effective impulse response to L taps. During training of FEQ, the perfommnce deteriorates due to residual ISI. One possible method of compensating this is as follows. Partition the set of subchannels in to two subsets with the following properties. One of the sets (set A) contains signals that are orthogonal to each other over a length of samples less than N (say Nl). Designate the other set as B. The FFT of the TDE output (after removal of cyclic prefix) is computed. The outputs of the subchannels in set B are decoded to obtain the

constellation symbols. Reconstruct the time domain samples corresponding to the decoded symbols of set B and subtract them from the TDE output frame. The resulting time domain samples now correspond to those of set A and the transient. Doing an FPT over NI samples will recover the symbols of set A. These Nl samples can be chosen such that the transient part is avoided. For example, set A could consist of all the subchannels with even indices, periodic with length Nl = N/2. Set B would consist of the odd subchannels.
Those skilled in the art would easily recognize that there are several minor variants of the preferred embodiment, both algorithmic as well as implementational, which would lead to similar results. These include
• A frame by frame adaptation of taps instead of a sample by sample adaptation. This would reduce the number of tap updates and the error measure minimized. For frame by frame update, taps could be maintained in time domain, while error could be computed in the frequency domain. N
• The TDE may be trained and may operate at a higher sampling rate than the minimum required. This helps avoiding the effects of aliasing. However, the number of TDE taps may increase because of the higher sampling rate. In such cases, intermittent taps of TDE or estimator could be forced to zero in order to minimize computation and training time. For example, if alternate taps of TDE are set to zero, the frequency response is constrained to be

symmetric about one-fourth of the sampling rate.
Complete implementation in software or hardware or partial hardware/software implementation.
Instead of the conventional LMS algorithm, some of its variants could be employed for stability reasons. Further, the LMS objective function could itself be altered to avoid the trivial zero solution and some gradient descent procedure used to solve it; which would avoid the need for normalization. Variations in the above described delay estimation procedure, wiiich could involve averaging of the channel output frames for improving the SNR, or employing the correlation information to confute a delay estimate. If the correlation information is not known, it could be recursively computed using the channel outputs over a few frames.
Variants of the procedure for computing the starting values of the taps for adaptation: The projection mechanism employed for computing the required L taps from the available N taps could also be different. Further, in order to obtain a smooth profile for the starting value of the taps, windowing by non-Gaussian kernels could also be employed. Other methods of constraining the TDE and estimator starting values, based on the given problem, can also be employed. These include initializing TDE or estimator to some desired filter.

Weighting by a Gaussian window may be made optional depending on the energy of edge taps in comparison with the energy in the taps towards the center.

We claim:
1. A method for estimating channel error and delay in a plurality of
channels for a multi-carrier communication system using frequency
division multiplexing, in which a training mode is used, wherein
estimating channel error comprises the steps of:
receiving a signal output from the channel;
receiving a reference signal;
sampling an impulse resporise of the channel;
transforming the reference signal, impulse channel response, and charier output into frequency domain;
estimating a starting set taps tux a time domain equalizer designed to remove distortions from the charnel, the estimation being determined responsive to the frequency domain transformation of the reference signal, impulse channel response, and channel output.
2. The method as claimed in claim 1 wherein estimating a starting
point comprises:
minimizing an error value of a logical combination of he frequency domain transformation of the reference signal, the frequency domain transformation of the chaimels output, and the frequency domain transformation of the channel response.
3. The method as claimed in claim 2 wherein minimized error value is
determined by:
where H{k) is the Fast Fourier Transform (FFT) coefficient of an N-point finite impulse response filter for equalizing the channel, Y(k,i) is a FFT coefficient of a sampled output signal of tiie channel, wherein the sampled output signal is sampled N times, X(k,i) is the FFT coefficient of a sampled output signal of the channel, wherein the sampled output signal is sampled N times, X{k,i) is the FFT coefficient of a reference signal, and * indicates complex conjugation and *indicates complex conjugation.
4. The method as claimed in claim 3 comprising:
transforming the minimized error value into time domain;
designating the estimated starting point as the transformed time
domain representation of the minimized error value.

5. The method as claimed in claim 3 comprising:
transforming the minimized error value into time domain;
projecting the time domain transformation orthogonally onto a
subspace of a discrete Hilbert space of a predetermined dimension.
6. The method as claimed in claim 5 comprising:
selecting contiguous samples of tiie transformed minimized error value having a highest energy value.
7. The method as claimed in claim 6 comprising:
windowing the selected contiguous samples.
8. The method as claimed in claim 6 wherein M contiguous samples
are selected, wherein M is a value much less than a symbol period of the
channel output signal.
9. The method as claimed in claim 3 comprising:
computing an angle for H(k); and
estimating channel delay responsive to the computed angle.
10. A method for estimating chaimel error and delay in a plurality of
channels for a multi-carrier communication system as claimed in claim 1,
wherein estimating delay comprises:
estimating a signal-to-noise ratio in each channel;
selecting sub-channels having an estimated signal-to-noise ratio above a predetermined threshold;
averaging fast fourier transform coefficients of the channel outputs over a number equal to the selected sub-channels;
computing a vector representing a fast fourier coefficient of a normalized channel output (H(k)), wherein the normalized channel output is determined responsive to the averaged fast fourier transform coefficients of the channel output;
computing a vector (Q(k)) representing phase angles of H(k);
computing a weighting window responsive to the computed Q{k) vector; and
determining an estimate of the delay of the channel responsive to the computed weighting window.

claimed in claim 1 to recover a signal distorted by transmission through a channel, comprising:
receiving output signal from the channel;
trar\smitting the output signal from the channel through the time domain equalizer; to obtain a TDE output vector;
transforming the TDE output vector into a frequency domain to obtain frequency equalization taps;
generating a matrix from the frequency equalization taps;
receiving a reference signal;
determining an error generated by the channel responsive to comparing the received reference signal and the matrix generated from the frequency equalization taps; and
minimizing the distortion introduced by the channel responsive to the determined error.
16. The method as claimed in claim 15 wherein the reference signal is a pseudorandom sequence.
17. The method as claimed in claim 16 wherein the determined error is determined as the sum of squares of errors generated from a plurality of channels in the system.
18. An apparatus for receiving data transmitted from a remote site, and for compensating the received data for errors introduced during transmission of the data as claimed in claim 15 comprising:
a reference signal generator, for generating a reference signal equivalent to a test signal transmitted to the time domain equalizer;
a delay unit, coupled to the reference signal generator, for adding a delay to the reference signal, wherein the delay is selected to approximate delay introduced during transmission of tiie test signal
an estimator filter, coupled to the delay unit, for filtering the delayed reference signal to compensate for the delay introduced by the delay imits;
a time domain equalizer filter, coupled to receive test signals and data signals, for equalizing errors introduced during the transmission of the data signal in time domain;
a comparator, coupled to the time domain equalizer filter and the estimator filter to receive the output of the time domain equalizer filter and the output of the estimator filter, for determining a filter error, wherein the filter error is determined as a difference between the output of the estimator filter and the output of the time domain equalizer filter; and

coefficient an adaptor, coupled to the comparator, for adjusting taps of the time domain equalizer filter and tie estimator filter responsive to the filter error.

Documents:

873-mas-1999 abstract-duplicate.pdf

873-mas-1999 abstract.pdf

873-mas-1999 claims-duplicate.pdf

873-mas-1999 claims.pdf

873-mas-1999 correspondences-others.pdf

873-mas-1999 correspondences-po.pdf

873-mas-1999 drawings-duplicate.pdf

873-mas-1999 drawings.pdf

873-mas-1999 form-1.pdf

873-mas-1999 form-19.pdf

873-mas-1999 form-26.pdf

873-mas-1999 form-3.pdf

873-mas-1999 form-5.pdf

873-mas-1999 description (complete)-duplicate.tif

873-mas-1999 description (complete).pdf

« Previous Patent

Next Patent »

Patent Number

216224

Indian Patent Application Number

873/MAS/1999

PG Journal Number

13/2008

Publication Date

31-Mar-2008

Grant Date

10-Mar-2008

Date of Filing

02-Sep-1999

Name of Patentee

SILICON AUTOMATION SYSTEMS LTD.

Applicant Address

3008, 12TH B MAIN, 8TH CROSS, HAL, 2ND STAGE, INDIRANAGAR, BANGALORE - 560 008,

Inventors:

#	Inventor's Name	Inventor's Address
1	VERMA AMIT	SILICON AUTOMATION SYSTEMS LTD., 3008, 12TH B MAIN, 8TH CROSS, HAL, 2ND STAGE, INDIRANAGAR, BANGALORE - 560 008,
2	AGARWAL RAJEEV	SILICON AUTOMATION SYSTEMS LTD., 3008, 12TH B MAIN, 8TH CROSS, HAL, 2ND STAGE, INDIRANAGAR, BANGALORE - 560 008,
3	BARMAN KAUSHIK	SILICON AUTOMATION SYSTEMS LTD., 3008, 12TH B MAIN, 8TH CROSS, HAL, 2ND STAGE, INDIRANAGAR, BANGALORE - 560 008,
4	ARVIND MANDAYAM TIRUNARAYANA	SILICON AUTOMATION SYSTEMS LTD., 3008, 12TH B MAIN, 8TH CROSS, HAL, 2ND STAGE, INDIRANAGAR, BANGALORE - 560 008,
5	SUBRAMANIAN CHANDRASEKARAPURAM ANANTHARAMAN	SILICON AUTOMATION SYSTEMS LTD., 3008, 12TH B MAIN, 8TH CROSS, HAL, 2ND STAGE, INDIRANAGAR, BANGALORE - 560 008,

PCT International Classification Number

H03 M 13/01

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	60/099,255	1998-09-04	U.S.A.