Method and Apparatus for Reducing Multipath Distortion

The present invention generally relates to radio-frequency (RF) communications and more particularly relates to methods and apparatuses for equalizing multipath propagation characteristics in time-division multiple access (TDMA) signals and/or time-division multiplexing (TDM) signals.

A cellular radio system uses a grid of small service cells (or service zones) and a specific pattern of channel use within the group of service cells so that channels can be reused in a controlled way. A call in a cellular system is routed to a mobile unit via land-line trunks to a cell site (i.e., a stationary transmitter) in the vicinity of the mobile unit. Low-power RF transmission from the cell site is used for the last few miles. System logic locates an active user within the grid in order to hand off control of the call to the proper cell site as the signal strength of the active user changes.

TDMA is a communication technique used in cellular radio systems whereby users communicate with each other on the basis of non-overlapping transmission bursts through a common channel. Since there is no overlap, the same carrier frequency may be assigned to all users sharing the channel. Multiple access refers to techniques that allow a plurality of stations to communicate via a single channel. In TDMA, each interval of T.sub.F seconds, called a frame, is divided into discrete time slots. Each user may use one or more time slots.

The main impairments in received signals are the result of propagation effects. Multipath propagation due to scatter from obstructions within a few hundred feet of the receiving terminal, multipath propagation due to large echoes from distant but large reflectors, and shadowing of the direct path by intervening larger-scale features of the terrain each may contribute to the signal impairment. The effect of multipath propagation is a standing-wave pattern in space determined by the amplitude and phase relationships between the direct and reflected and/or scattered energy components. In a cellular system a vehicle moving through this standing wave pattern will experience short-term fluctuations in signal intensity, typically with a period of a fraction of a second. See, e.g., A. F. Inglis, Electronic Communications Handbook, Chapter 22-6, McGraw-Hill, Inc. (1988).

Multipath propagation interference significantly limits the maximum permissible data rate for a mobile RF channel. Multipath propagation in urban and suburban areas causes signal impairments that, if not counteracted, degrade signal reception and voice quality. The difficulty of dealing with these impairments is compounded by the fact that, due to the mobile nature of the application, the channel characteristics as perceived by the receiver are time-variant.

There are two major classes of impairments caused by multipath propagation: Flat (or frequency non-selective) fading and frequency selective fading. Flat fading is caused by multipath conditions in which the differential propagation delay between different paths is significant with respect to the carrier period but negligible compared to the symbol period (i.e., the duration of a transmitted symbol represented by a predefined number of bits) of the signalling scheme used. Frequency selective fading occurs when the differential propagation delay is a major fraction (>25%) of the signalling or symbol period, in which case the frequency characteristics of the channel vary Within the bandwidth of the transmitted signal.

Flat fading results, e.g., when digital data is transmitted at a rate of 5 ksps (5000 symbols per second) at a carrier frequency close to 900 MHz with differential propagation delays of 10 .mu.sec or less. The differential propagation delay in this case is much larger than the carrier period but only a small fraction (5%) of the symbol period; thus the amplitude and phase of the received signal continuously change when the receiver moves under these conditions. This is because the received signal is the vector sum of the direct and multipath signals, which constructively and destructively add due to the changing path lengths. However, because the differential propagation delay is only a small fraction of the symbol period, all the frequencies in the signal of interest spectrum are attenuated more or less by the same amount, hence the name flat fading. This kind of fading is present in almost all urban and suburban areas in which multipath propagation is caused by reflections from buildings and natural obstructions.

An example of frequency selective fading would result with the same parameters as above except that the signalling rate is increased to, e.g., 25 ksps. In that case the differential propagation delay is 25% of the symbol period and results in major degradation in the performance of the receiver due to time dispersion, i.e., smearing of the received signal pulses. Time dispersion causes intersymbol interference (ISI); that is, the signal at the decision points as viewed by the receiver is made up of a superposition of contributions from multiple symbols. Hence if the receiver attempts to make a decision based upon a single received symbol, i.e., without any further processing, its performance will degrade severely since adjacent symbols will interfere with the symbol on which the receiver is making a decision.

Digital adaptive equalizers are widely used to combat the effect of time dispersion in high speed communication channels. Equalization has been used for many years in high speed data modems over analog telephone lines. The introduction of high speed digital transmission over cellular and other radio channels has mandated the use of equalization or other similar techniques that can counteract the effects of time dispersion. The equalization problem in the mobile radio channel, however, is considerably more complex than that in telephone channels, mainly because the channel impulse response in the mobile radio channel is time variant and must be estimated by the receiver in real time. Thus the receiver must not only make decisions based upon the received signal, it must also adapt the equalizer parameters in response to the fast-changing channel conditions.

As fading rate approaches the TDMA block rate, both deep energy fading and minimum-to-maximum phase channel response transitions frequently occur in a frame duration, which result in a significant number of equalizer loss-of-locks. Since most equalizers have difficulty recovering from loss-of-lock, this greatly degrades the receiver performance and has raised worldwide interest. The phenomenon is especially pronounced in narrow band TDMA systems in a mobile, as opposed to portable or indoor, environment.

FIG. 1 depicts the processing performed by a Decision Feedback Equalizer (DFE). The DFE has a forward section 1 comprising a tapped delay line fed by samples of the received complex baseband signal and a feedback tapped delay line 3 fed by the output of a decision circuit 5. The input of the decision circuit is given by the equation ##EQU1## where v.sub.k-j represents samples of the received signal, c.sub.j represents the weights of the equalizer taps, I.sub.k-j represents the signal decisions made by the decision circuit, and K.sub.1 +1 and K.sub.2 represent the respective number of forward and feedback taps. The forward section may be either synchronous, i.e., clocked at the rate of one sample per received symbol, or fractionally-spaced, i.e., clocked at multiple (typically 2) times for each received symbol. The latter is the preferred approach since it provides sampling timing insensitivity, a significant advantage in a highly dispersive time-variant environment.

The adaptation of the DFE tap weights in an environment where their optimal values change significantly within a given time slot is the subject of the present invention. Fast adapting algorithms have been published in the technical literature and are generally of the Recursive Least Square (RLS) type. Several different variants (e.g., direct Kalman, Square-root Kalman, Lattice filter, MSE Lattice) may be used with the enhanced adaption method described below.

The adaption method known as the direct form Kalman update algorithm comprises a gain update section and a tap update section. The tap update section, described by equation 6 below, is similar to more widely used techniques derived through MSE-criterion based methods, except that the gain is a vector with a length equal to the equalizer length (sum of the number of forward and feedback section taps), rather than a single scaler parameter adjusted through experimentation. Moreover, the gain is calculated in real time based on the received signal samples. The equations governing these updates are summarized below:

Compute output:

Compute error:

Compute Kalman gain vector:

Update inverse of the correlation matrix: ##EQU3##

Update coefficients: ##EQU4## See J. Proakis, Digital Communications, McGraw Hill, 1989.

At the beginning of each TDMA slot in the Kalman technique the equalizer tap weights are all set to zero and the equalizer is trained, that is, the initial tap weight estimates are calculated. The tap weight calculations use a sync sequence sent by the transmitter and known in advance by the receiver. During the training period, the sync word symbols replace the decision symbols produced by the decision circuit and the adaptation algorithm described above is executed to generate updates of the tap weights, as described in equation 6. If the sync word is sufficiently long (e.g., greater than two times the equalizer length), the tap weights are adjusted to their correct values at the end of the training period, at which point the equalizer is ready to generate decisions based upon the received signal.

Processing of the signal in the reverse order from which it was received was recently introduced as a means of improving receiver performance under certain dispersive multipath conditions. A reverse processing algorithm is described in S. Ariyavisitakul, "Equalization of a Hard-Limited Slowly-Fading Multipath Signal Using a Fade Equalizer With a Time-Reversal Structure," 40th IEEE Vehicular Technology Conference, pages 520 to 526, May, 1990. That and other known algorithms, however, are incapable of working in an environment where there is a high probability of deep fade and minimum-to-maximum phase transition within a block duration. The known algorithms assume that the channel dispersion is fixed in a block duration and can be classified as either minimum phase or maximum phase. They choose either forward or reverse processing once per block by simply looking at the equalizer training status.

A TDMA communication system with adaptive equalization for reducing multipath propagation distortion is described in U.S. Pat. No. 4,852,090, which issued Jul. 25, 1989 and which is hereby incorporated by reference into the instant application. The reader is referred to the '090 patent for further background on the present invention.

A major goal of the present invention is to provide improved methods and apparatuses for reducing multipath propagation distortion.

Methods for reducing multipath propagation distortion in a signal in accordance with the present invention comprise the steps of sampling the signal to obtain a plurality of sampled symbols, equalizing the time delay characteristics of at least a first subset of the said sampled symbols by processing the first subset in a first direction until a first prescribed condition is detected, and equalizing the time delay characteristics of at least a second subset of the said sampled symbols by processing the second subset in a second direction until a second prescribed condition is detected.

In a preferred embodiment of the invention the first and second subsets comprise values from a data block that is bounded by first and second synchronization words.

Another embodiment of the invention further comprises the step of equalizing the time delay characteristics of a third subset of the sampled values by processing a first portion of the third subset in the first direction at least until a predefined point between the first and second subsets is reached and processing a second portion of the third subset in the second direction at least until the predefined point is reached.

In still another embodiment of the invention the predefined point is the midpoint between the first and second subsets.

In yet another embodiment of the invention the first and second prescribed conditions are detected by determining the mean square error (MSE) in the received symbols following equalization and determining when the MSE exceeds a predefined limit.

In another embodiment of the present invention the first condition is detected by detecting when the MSE exceeds the predefined limit over a first predefined majority of a first set of symbols and the second condition is detected by detecting when the MSE exceeds the predefined limit over a second predefined majority of a second set of symbols.

In still a further embodiment of the invention the equalizing steps employ a decision feedback equalization algorithm.

The present invention also encompasses methods for operating a communications system comprising the steps of interleaving a plurality of predefined synchronization words with a plurality of data words to form a user signal, transmitting the user signal, receiving the transmitted user signal, and processing the received user signal to reduce multipath propagation distortion by performing the steps of sampling the signal to obtain a plurality of sampled symbols, equalizing the time delay characteristics of at least a first subset of the sampled symbols by processing the first subset in a first direction until a first prescribed condition is detected, and equalizing the time delay characteristics of at least a second subset of the sampled symbols by processing the second subset in a second direction until a second prescribed condition is detected.

The present invention also encompasses apparatuses that comprise means for sampling a signal to obtain a plurality of sampled symbols, means for equalizing the time delay characteristics of at least a first subset of the sampled symbols, including means for processing the first subset in a first direction until a first prescribed condition is detected, and means for equalizing the time delay characteristics of at least a second subset of the sampled symbols, including means for processing the second subset in a second direction until a second prescribed condition is detected.

Another embodiment of the present invention provides an apparatus for reducing multipath propagation distortion in a sampled time domain signal that comprises a plurality of symbols, wherein the symbols comprise time delay characteristics. The apparatus comprises detector means for detecting a first prescribed condition among the said symbols; first means for equalizing the time delay characteristics of the symbols according to a first sequence; second means for equalizing the time delay characteristics of the symbols according to a second sequence; and select means, responsive to the detector means, for selectively storing the respective outputs of the first and second means.

In a preferred embodiment the detector means includes means for detecting a loss of lock condition and the select means includes means for storing outputs of the second means upon the detection of the loss of lock condition.

FIG. 1 is a block diagram of a Decision Feedback Equalizer.

FIG. 2 is a block diagram of a digital cellular telephone in accordance with the present invention.

FIG. 3 depicts the structure of a TDM/TDMA time slot.

FIG. 4 is a block diagram of a bidirectional equalizer in accordance with the present invention.

FIG. 5 is a more detailed depiction of the bidirectional control logic block (44) of FIG. 4.

FIG. 6 is a flow chart of a bidirectional equalization algorithm in accordance with the present invention.

FIG. 7 is a flow chart of the EQUALIZE FORWARD block (60) of FIG. 6.

FIG. 8 is a flow chart of the EQUALIZE BACKWARD block (64) of FIG. 6.

FIG. 9 is a flow chart of the COMBINE block (66) of FIG. 6.

FIG. 2 is a block diagram of a digital cellular telephone system, which is the preferred environment for the present invention. The cellular telephone system includes a radio transceiver 10, a digital demodulator 12, a bidirectional equalizer 14 (which is described in greater detail below), an error correction decoder 16, and a voice decoder 18, which are all coupled to the speaker portion of a handset 20. The system further comprises, coupled to the microphone portion of the handset 20, a voice encoder 22, error correction encoder 24 and digital modulator 26. The bidirectional equalizer 14 processes the demodulated digital signal to minimize the effect of multipath propagation.

FIG. 3 illustrates the structure of a TDM/TDMA signal block to be processed in accordance with the present invention. The signal block includes a plurality of synchronization words (SYNC #1, SYNC #2) interleaved with corresponding data blocks. A single user message is made up of a synchronization word and the data block that follows that synchronization word and is made up of N symbols. In a preferred embodiment, there are 14 synchronization symbols and 148 data symbols per user message, which is in accordance with the North American Digital Cellular (NADC) system. At 2 bits per symbol, the number of bits per user message is equal to 296 under the NADC system. The individual cellular telephone units are programmed to look for a particular synchronization word and to decode only the data blocks (i.e., messages) preceded by that synchronization word. The present invention employs both the preceding and trailing synchronization words in performing the equalization function.

FIG. 4 is a block diagram of the bidirectional equalizer 14 of FIG. 2. It should first be noted that the equalizer 14 is symmetrical and comprises a forward processing branch and a backward processing branch. At the center is a sample buffer 30 wherein received TDMA burst samples are temporarily stored.

The forward processing branch comprises the following components:

1. A synchronization word detector block 32a that detects the presence in the received signal of a first prescribed sync word (e.g., SYNC #1) by comparing the stored samples with a value stored in memory 36a.

2. The sync data word memory 36a.

3. A first equalizer 34a for processing the N symbols of each user message intended for the given telephone unit. This is described in greater detail below.

4. A delay block 38 a that compensates for the delay through the MSE filter 40a, 40b and the bidirectional control logic 44 in accordance with the MSE filter memory.

5. A mean square error (MSE) filter 40a that generates an estimate of the mean square error, i.e., computes the average of the squared differences between the respective symbols at the input and output of a decision circuit such as the decision circuit 5 of FIG. 1.

6. A loss-of-look detector 42a that declares equalizer loss-of-lock (the term loss-of-lock indicates that the signal physically changes too fast or by too large an amount for the equalizer to respond properly). In one embodiment of the invention the loss-of-lock detector compares the MSE computed by block 40a with a predefined threshold value (e.g., 0.35 assuming the signal decision points have been normalized to 1) and outputs a loss-of-lock signal L.sub.f if the MSE exceeds the predefined threshold value. In another embodiment of the invention the detector compares the MSE to the threshold over a set (such as five) of past symbols and declares loss-of-lock only if the MSE exceeds the threshold in the majority of symbols in that set.

7. Bidirectional control logic 44 (described below).

8. A bidirectional decision buffer 46.

The backward processing branch comprises a detector 32b for detecting the trailing sync word (SYNC #2) a memory 36b for storing the trailing sync word, an equalizer block 34b (described below), a delay block 38b, MSE filter 40b, and loss-of-lock detector 42b.

FIG. 5 depicts the operation of the bidirectional control logic 44. That logic receives the signals L.sub.f and L.sub.b from detectors 42a and 42b, respectively, and also receives two other signals, K.sub.f, K.sub.b. As explained below, K.sub.f and K.sub.b are initialized to zero and are set to the values of the respective running indices at the points where a loss-of-lock condition is declared. (The operation of the bidirectional control logic 44 is described in detail below in connection with the flow diagrams of FIGS. 6-9). The symbol value a.sub.k is stored in buffer 46 if either L.sub.f =0, which indicates that no loss-of-lock condition has occurred with respect to the first sync word (SYNC #1), or if both L.sub.f and L.sub.b =1 and ##EQU5## (Note that the value ##EQU6## represents the index k at the midpoint between K.sub.f and K.sub.b.) If none of the above conditions is satisfied, the symbol a.sub.N-k' is stored in buffer 46. This operation continues until k=N, k'=N or k'>V+N-K.sub.f, where V is an overlap parameter that depends on the MSE memory. For example, V is set to ten for an MSE filter with memory of six symbols (which is the preferred embodiment).

A flow chart of a computer program embodying the bidirectional equalization algorithm is depicted in FIGS. 6-9. Source code used in verifying the algorithm is listed in the appendix. FIG. 6 is a flow chart of a main program (MAIN) and FIGS. 7-9 are flow charts of subroutines invoked by the main program.

The main bidirectional equalization algorithm is started at step 50.

Next, a predefined number of TDMA slot samples are stored, step 52.

Next, the indices k, k', K.sub.f, K.sub.b, L.sub.f, L.sub.b are set to 0, step 54.

At decision step 56, a determination is made of whether the first sync word (SYNC #1) has been detected.

If SYNC #1 has been detected, the equalizer is trained in the forward direction, step 58.

Next, at step 60 the EQUALIZE FORWARD subroutine is called.

After returning from the EQUALIZE FORWARD subroutine, or if SYNC #1 was not detected at decision block 56, the equalizer is trained in the backward direction, step 62.

The EQUALIZE BACKWARD subroutine is called at step 64.

The COMBINE subroutine is called at step 66 after the EQUALIZE BACKWARD subroutine is executed. The COMBINE subroutine combines the results of the EQUALIZE FORWARD and EQUALIZE BACKWARD subroutines, as explained below.

The main program stops at step 68.

Referring to FIG. 7, the EQUALIZE FORWARD subroutine is entered at step 70.

The index k is incremented at step 72.

At step 74 the symbol a.sub.k corresponding to index k is equalized.

At step 76 a.sub.k is stored in the decision buffer 46.

At step 78 the mean squared error MSE.sub.f is computed.

At decision step 80 a determination is made of whether k is equal to N.

The program ends if k is equal to N, step 82.

If k is not equal to N, a determination is made at step 84 of whether MSE.sub.f is greater than a threshold value (e.g., 0.35 or 35% of the signal decision points).

The program loops to step 72 if no loss-of-lock has been detected (e.g., if MSE.sub.f is not greater than the threshold value).

If MSE.sub.f is greater than the threshold value, the variable L.sub.f is set equal to 1, step 86, the index K.sub.f is set equal to k, step 88, and control is returned to the main program, step 90.

Referring to FIG. 8, the EQUALIZE BACKWARD subroutine is entered at step 92.

At step 94 the symbol a.sub.N-k' is equalized.

At step 96 a.sub.N-k' is stored in the decision buffer 46.

At step 98 the index k' is incremented.

At step 100 the reverse mean square error (MSE.sub.b) is computed.

At decision step 102 a determination is made of whether k' is equal to N or k' is greater than V+N-K.sub.f.

If k' is equal to N or greater than V+N-K.sub.f the program ends, step 104.

If k' is not equal to N or greater than V+N-K.sub.f a determination is made at step 106 of whether MSE.sub.b is greater than the threshold value. If it is not, the program loops to step 94.

If MSE.sub.b is greater than the threshold value the variable L.sub.b is set equal to 1, step 108, the index K.sub.b is set equal to k', step 110, and control is returned to the main program, step 112.

Referring to FIG. 9, the subroutine COMBINE is entered at step 114.

At step 116 k' is incremented.

At decision step 118 a determination is made of whether K' is less than (N+K.sub.b -K.sub.f)/2.

If k' is less than (N+K.sub.b -K.sub.f)/2, the backward equalizer is run on the symbol a.sub.N-k', step 120, a.sub.N-k' is stored in the decision buffer 46, step 122, and the program loops to step 116.

If k' is not less than (N+K.sub.b -K.sub.f)/2, k is incremented, step 124, and a determination is made at step 126 of whether k is less than (N-K.sub.b +K.sub.f)/2.

If k is less than (N-K.sub.b +K.sub.f)/2, the forward equalizer is run on symbol a.sub.k, step 128, symbol a.sub.k is stored in the decision buffer 46, step 130, and the program loops to step 124.

If at decision step 126 k was greater than or equal to (N-K.sub.b +K.sub.f)/2, control is returned to the main program, step 132.

In summary, for every TDMA block the receiver operation starts with the forward processing procedure and operates on received samples in a first-in first-served order. The sync word detector 32a ensures the correct TDMA frame timing and starts the equalizer training. The detected data is stacked in the decision buffer 46. The adaptive equalizer 34a outputs the decision error signal, which is squared, filtered and threshold-compared to generate a latch-type loss-of-lock flag. Without loss-of-lock, the receiver works through to the last data symbol and the frame processing is finished. The forward processing is halted and the receiver switches to the backward processing branch (FIG. 4) if the receiver loses lock midway through the data block. The backward processing branch processes received samples from the input buffer in reverse order. The sync word detector 32b detects the reverse trailing sync word (SYNC #2) and recovers the TDMA symbol timing. The receiver then trains the equalizer and starts data processing in a reverse mode. The detected data is then stacked in the decision buffer 46, starting from the Nth symbol. The reverse loss-of-lock detector works the same as the forward loss-of-lock detector. The control logic, however, is modified such that backward processing works until either detected data overwrites a portion of the forward-processed data, or a loss-of-lock is declared. In the former case, the frame processing is finished. In the latter case, the midpoint between the two loss-of-lock points is calculated and, if needed, both processes are enabled toward the midpoint. The overlap in processing is required to cover the delay and uncertainty range of lock detections, so the overall performance is optimized.

An important aspect of the present invention is that the channel condition is detected from the equalizer tracking status, and the dividing point between forward and backward processing is optimized in an adaptive manner such that overhead is minimized and the effect of loss-of-lock is removed. The equalizer MSE estimate has been shown in computer simulations to be very reliable in reflecting the equalizer loss-of-lock status.

It should be noted that some of the methods cited in the background of the invention section of the instant application are much simpler than the algorithm of the present invention, however they are incapable of working in a fast fading environment where the probability of deep fade and minimum-to-maximum phase transitions inside a block is high. Those algorithms assume that the channel dispersion is fixed in a block duration and can be classified as either minimum phase or maximum phase In contrast, the present invention is based on the assumption of a highly dynamic channel that could change greatly within a block duration The algorithm of the present invention adapts in symbol resolution by utilizing the equalizer tracking status, which is a major reason why the bidirectionally-combined processing has significant advantages over the prior art.

The primary advantages offered by the present invention are that the error rate is greatly reduced, the modem maximum operational fading rate is increased by a factor of two and the efficiency can be increased above the efficiency achievable by using four training sequences per TDMA block. Further, the algorithm of the present invention will work on both TDM and TDMA signals with sub-frame structures that have one leading and one trailing sync word.

Finally, it should be noted that the present invention is not limited to the specific embodiments described above, as many variations of those embodiments will be within the true scope of the following claims. For example, a maximum likelihood sequence estimation (MLSE) algorithm or other known time dispersion mitigation technique could be used instead of the DFE in the above-described embodiments. ##SPC1##