BACKGROUND OF THE INVENTION A Direct-Sequence Code-Division Multiple Access (DS-CDMA) cellular communication system, such as the one described in IS-95, is a self interference system. In such a communication system, a number of mobiles and/or portables use the same spectrum in the same geographical area. The signals from the subscriber units are differentiated from each other based on their spreading code (i.e. the user long code PN sequence and the I and Q PN sequences). The capacity limit of such a system is dependent on the amount of self interference in the system. An analogy used to illustrate this point is a cocktail party conversation. If you are at a cocktail party speaking to the person next to you and no one else is in the room with you, you do not have to speak very loud to be heard. When several more people enter the room and start conversing, you have to speak louder to be heard.

In other words the self interference has increased and you have to increase your transmitter power to overcome the interference. As more and more people start talking in the room you have to speak louder and louder, and so do the other people in the room, in order to be heard. Eventually, you reach the point where it takes an infinite amount of power to be heard over the other people. That is the capacity limit.

Extending the cocktail analogy, if everyone in the room is hard of hearing you start with a higher level of interference from the other guests than if everyone has normal hearing. Thus, if everyone has

better hearing the number of simultaneous conversations that can occur increases, i.e. the system capacity increases. As a result there is a considerable advantage in increasing the receiver's sensitivity in a DS- CDMA system. Any increase in receiver sensitivity directly reduces the amount of transmitter power required and as a result the amount of self interference. Increasing a cellular systems capacity increases an operator's revenue and improves the service the subscriber receives.

The standard receiver in a DS-CDMA system non-coherently detects the transmitted signal. Non-coherent detection does not take into account the phase difference between two transmitted signals. The standard non-coherent receiver first despreads the received signal (i.e.

removes the I and Q PN sequences and the user's long code PN sequence) and accumulates a Walsh symbol of data. A Fast Hadamard Transform (FHT) is performed on the despread accumulated data. The FHT essentially correlates the despread signal against the sixty four possible Walsh symbols that could have been sent by the transmitter.

The receiver then selects the Walsh symbol with the highest energy (where the energy is determined by summing the square of the I and Q vectors). The non-coherent receiver is an energy detector and does not use the phase of the transmitted signal. It is well known (Sklar, Digital Communications, ISBN 0-13-211939-0, Prentice Hall 1988, p. 161-164) that the bit error rate (BER) performance of coherent demodulation is superior to non-coherent demodulation.

Certain modifications to the standard receiver in a DS-CDMA system have been proposed to essentially provide psuedo-coherent detection of the transmitted signal. For example, in "Near Maximum Likelihood Demodulation for M-ary Orthogonal Signals" by Rod Walton and Mark Wallace, IEEE Conf. on Vehicular Technology, pp. 5- 8, May 18-20, 1993, the authors propose the use of non-coherent ranks of individual symbols to improve the performance of the detector. The modification forms a near maximum likelihood sequence for symbols received and, based on the coherent energy of previous hypotheses, the unlikely hypotheses are discarded leaving a small number of survivors. As the symbols are processed, the surviving hypotheses tend to converge to the best estimate of the transmitted sequence. This

method, as described by the authors, is impractical to implement in real-time since most cycles available during the time period of a power control group are consumed by the algorithm during the calculation of the transitional energy metrics, the time period when the energy of each of the possible transitions between the surviving paths and each point of the new Walsh symbol for the fingers are being calculated.

Additionally, this method requires an impractical amount of memory for processing of the data in the receiver.

Thus there exists a need for a method and apparatus in a communication system receiver which overcomes the disadvantages of the prior art receivers.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 generally depicts a block diagram of a transmitter compatible with a DS-CDMA cellular telephone system.

FIG. 2 generally depicts a Walsh matrix implemented within a DS-CDMA cellular telephone system.

FIG. 3 generally depicts examples of transmissions of data at various rates within a CDMA time frame.

FIG. 4 generally depicts a block diagram of a receiver compatible with a DS-CDMA cellular telephone system which performs processing of data in accordance with the invention.

FIG. 5 generally depicts a trellis diagram of processing of data in accordance with the invention.

FIG. 6 generally depicts a hardware implementation of the channel estimator of FIG. 4 in accordance with the invention.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT An improved method and apparatus for processing data related to channel estimation in a communication system receiver is described herein in accordance with the invention. The receiver provides a first

and second set of Walsh domain values and adds one of the values in the first set to predetermined ones of the second set to form a first set of summed Walsh domain values. An energy value for each of the values of the first set of summed Walsh domain values is then determined and one of the summed vectors is selected based on its energy value. The process is repeated for all Walsh domain values within a power control group until a channel estimate is produced.

Stated generally, a method of processing data in a receiver of a communication system includes the steps of (a) providing a first set of demodulated data vectors and (b) providing a second set of demodulated data vectors. The method further includes the steps of (c) adding one of the demodulated data vectors in the first set to a plurality of demodulated data vectors of the second set to form a first set of summed vectors and (d) determining an energy value for each of the summed vectors of the first set of summed vectors. The method also includes the step of (e) selecting one of the summed vectors from the first set of summed vectors based on the energy value to provide a selected summed vector.

The steps (c)-(e) are repeated for each of the demodulated data vectors in the first set to form a set of selected summed vectors and steps (c)-(e) are implemented for each vector in the set of selected summed vectors and a third set of demodulated data vectors to provide a subsequent set of selected summed vectors. The steps (c)-(e) are implemented for each vector in the set of selected summed vectors and a fourth, fifth and sixth set of demodulated data vectors to provide a final set of selected summed vectors. The summed vector within the final set of selected summed vectors having the highest energy is used as a channel estimate.

In the preferred embodiment, the demodulated data vector is an estimate of one of a predetermined set of data symbols transmitted by a transmitter in the communication system, and is associated with a Walsh symbol. The sets of demodulated data vectors are provided by a Fast Hadamard Transform (FHT) within the receiver and are comprised of a plurality of individual receive path data vectors. Each individual receive path data vector is produced by one of a plurality of

receive fingers associated with the receiver and includes a real portion and an imaginary portion.

Stated differently, a method of estimating a channel in a receiver having a plurality of receive paths includes the steps of (a) initializing, for each receive path in the receiver, N state sequence metrics to the N Walsh domain values having the largest energies for a first Walsh symbol in a power control group and (b) storing the initialized state sequence metrics. The method further includes the steps of (c) adding, for each receive path in the receiver, N Walsh domain values having the largest energies for a second Walsh symbol in a power control group to the initialized state sequence to produce a summed result and (d) squaring the summed result to produce a squared summed result.

The method further includes the steps of (e) accumulating the squared summed result of each path of the receiver to produce a combined energy value, (f) comparing the combined energy value to a maximum combined energy for the current sequence state and (g) updating the maximum combined energy with the combined energy value based on the comparison. The method also includes the step of (h) adding the N Walsh domain values having the largest energies for a next Walsh symbol in a power control group and repeating steps (d)-(g) until the N Walsh domain values having the largest energies for six Walsh symbol in a power control group have been added to produce a final updated maximum combined energy representing the channel estimate.

A block diagram of a transmitter 10 compatible with a DS-CDMA cellular telephone system is generally depicted in FIG. 1. A voice signal or data signal 12 is input to a coding section 14, resulting in a coded signal 16. The coded signal 16 is mapped, preferably, six symbols at a time, to a unique 64-ary symbol by a 64-ary orthogonal modulator 18.

In the preferred embodiment, the 64-ary orthogonal modulator is a Walsh matrix, as shown in FIG. 2. The six coded symbols are mapped by the equation Co + 2C1 + 4C2 + 8C3 + 16C4 + 32C5 = i, where CO-5 are the coded symbols and i is the index of the output Walsh symbol.

Because the symbols are either 1 or 0 the equation uniquely maps the six symbols into one of the 64 Walsh symbols. The output of the 64-ary

modulator is a Walsh symbol, that is made up of 64 Walsh chips (a row in the Walsh matrix).

Connected to the modulator is an adder 20, that sums a long pseudorandom noise (PN) sequence 22 with the Walsh chips. The output of the adder 20 is split into an in-phase (I) channel 22 and a quadrature-phase (Q) channel 24. The I channel 22 has an adder 26, which sums the output of adder 20 with an I PN sequence 28. The Q channel 24 has an adder 38, that sums the output of adder 20 and a Q PN sequence 40. The adder 38 is connected to a delay element 42. The I and Q data are filtered by bandpass filters 30, 44, mixed in mixers 32, 46 and summed by summing node 38 to create the carrier frequency signal 37 which is transmitted to a mobile station (not shown) via an antenna 36. This results in offset QPSK modulation of the input data stream 12.

FIG. 3 depicts examples of transmissions of data at various rates within a CDMA Time Frame 100. If the input data 12 is comprised of speech data, the transmission rate can either be full rate (9600 bps) 104, half rate (4800 bps) 106, quarter rate (2400 bps) 108, or eighth rate (1200 bps) 110 as is shown in FIG. 3. The CDMA time frame 100 is made up of sixteen power control groups (PCGs) 102. The PCGs 102 are made up of six Walsh symbols 112 and each Walsh symbol 112 is defined by 64 Walsh chip values 114. Finally, each Walsh chip value 114 is spread by four PN chips 118. The incoming data rate, (full, half ) is determined by the voice activity of the far-end user. Periods where the user says little are encoded at eighth rate, while continuous speech might be encoded at full rate. Which PCGs are active during the CDMA time frame 100 is determined by the long code 22 and by the voice activity of the user.

A block diagram of a receiver 60 compatible with a DS-CDMA system and capable of implementing data processing in accordance with the invention is generally depicted in FIG. 4. In actual implementation, the receiver would be a four-path (or four-"finger") RAKE receiver, the general structure of which is well known in the art.

As shown in FIG. 4, the receiver 60 depicts only a single finger of the above-mentioned four-finger RAKE receiver for simplicity.

Referring to FIG. 4, an antenna 62 receives the signal 37 transmitted from the transmitter 10, and the signal is then input into a RF downconverter/sampler 63. The RF downconverter/sampler 63 processes the received signal 61 with well known techniques to obtain an oversampled (e.g. eight times oversampled) baseband representation 65 of the signal 37. The baseband representation 65 is input to a despreader 64 which reverses the Offset QPSK process using the long code PN sequence and the I and Q PN sequences as is well known in the art. The despread signal 67 is input into a Fast Hadamard Transform (FHT) 66, which correlates appropriate groups of sixty four received Walsh domain values against each of the sixty four possible Walsh domain values. The output of the FlIT 66 are sets of demodulated data vectors for each Walsh symbol (WSo-WS5) of a PCG 102. In a RAKE receiver implementation, an FlIT is performed independently for each receive path. This results in multiple groups of demodulated data vector sets, one group for each finger of the RAKE receiver. The individual receive path data vectors produced by corresponding fingers of the RAKE receiver include a real portion and an imaginary portion. A sorter 75 sorts through the 64 Walsh domain values to determine the N Walsh domain values which have the top combined energies. The sorter 75 calculates a combined energy associated with each Walsh index by summing together the Walsh domain energies of each finger of the RAKE receiver.

The channel estimator 69 shown in block 74 of FIG. 4 performs data processing in accordance with the invention. The channel estimator 69 estimates the transmitted Walsh symbol sequence from the Walsh domain values output from the FlIT 66 and sorted by sorter 75 and computes a channel estimate C (for each finger of the RAKE receiver). Within metric generation block 71, the channel estimate C is used to generate channel metrics related to the channel estimate C which are later used in the decoder 70. Assuming an accurate channel estimate C, the imaginary portion of each complex metric generated in metric generation block 71 consists of noise only. Thus, the real part of each complex metric output from metric generation block 71 is taken, and these values are then sent to deinterleaver 73 and convolutional

decoder 70. The decoder 70 reconstructs the information in the transmitted signal 37. The resulting data out 72 is the decoded channel information which is forwarded to the intended destination.

The idea of sequence estimation is to accumulate complex Walsh domain values over a period of time in which the channel is known to vary insignificantly. In the preferred embodiment, the time period is 1.25 milliseconds (msec.) which corresponds to the time period of a PCG 102. The Walsh domain values are accumulated to determine the most likely sequence of transmitted Walsh symbols.

This is the sequence which results in the highest accumulated energy.

The accumulated value of the Walsh symbols for this most likely sequence is an estimate of the communication channel C and, as such, can be used to coherently demodulate the received signal.

FIG. 5 generally depicts a trellis diagram of processing of data in accordance with the invention. As shown in FIG. 5, each PCG 102 consists of six Walsh symbols WSO-WS5 and thus the trellis diagram consists of only six time steps (t=0 through t=5). For each Walsh symbol WSo-WS5 received, sorter 75 computes the energy of each of the demodulated data vectors within a set of demodulated data vectors.

In the preferred embodiment, the demodulated data vectors are Walsh domain values. Sorter 75 then sorts the demodulated data vectors with the largest N into top energies 500 for the first set of demodulated data vectors associated with Walsh symbol WSo. This process is repeated for the demodulated data vectors in the second set of demodulated data vectors associated with Walsh symbol WS1 to produce the top energies 503 for the second set of demodulated data vectors.

Processing of data in accordance with the invention starts by first adding one of the demodulated data vectors from the first set of demodulated data vectors, and specifically from the top energies 500, to each of the demodulated data vectors of the second set, specifically from the top energies 503. As an example, demodulated data vector 506 is shown in FIG. 5 being added to each of the demodulated data vectors from the top energies 503 via line 509. The result is a set of summed vectors 518, and in this example, the first set of summed vectors 518. In accordance with the invention, the summed vector within the first set

of summed vectors 518 having the largest energy is selected. The process is repeated for each remaining demodulated data vector (2-N) within the top energies 500 until N different selected summed vectors are generated. At the end of this process, a set of selected summed vectors 521 is formed such that each of the selected summed vectors in the set 521 is subsequently added to top energies 524 from the third set of demodulated data vectors associated with Walsh symbol WS2 as described above to produce subsequent sets of selected summed vectors.

The above processing of data in accordance with the invention is repeated until a subsequent set of selected summed vectors is added (as described above) to the top energies from the sixth set of demodulated data vectors associated with Walsh symbol WSg (as described above) to produce a final set of selected summed vectors. At this point, the summed vector within the final set of selected summed vectors having the largest energy is used as the channel estimate C. One advantage, inter alia, to processing of data in accordance with the invention as described above is that, unlike prior art channel estimation techniques, there is no need to go back through the trellis to determine the best path to use as the channel estimate. By processing data in accordance with the invention, the result after processing data through the trellis is that the summed vector within the final set of selected summed vectors which has the largest energy is the channel estimate C itself; there is no need to go back through the trellis to determine the best path.

For simplicity, the description above has assumed a single receive path. For a RAKE receiver with multiple receive paths, the processing is similar to that described above. There is a demodulated data vector set and a summed vector set associated with each receive path. The data vectors are summed individually for each of the receive paths to produce the summed vector sets. However, the energies are computed by summing together the individual energies of each of the receive paths to produce a single combined energy for each summed data vector group. The surviving paths are thereby based upon information from all fingers of the RAKE receiver.

Mathematically, the steps for computing a channel estimate for a K-finger rake using the above described processing of data i n accordance with the invention is as follows. First, the combined energies of the K fingers of the rake receiver are determined: s = 0,1,...63 <BR> <BR> <BR> t= 0,1,2,...5 Then, the top N energies are sorted from the highest energy to the Nth highest energy to form E(n,t). Let n denote the rank of the Walsh domain value which created E(n,t). The top N Walsh domain values are then Wk(t). The sequence estimator state values are then initialized: n=1,2,...N <BR> <BR> <BR> k=1,2,...K Next, the maximum energy of each sequence state, i, summed with the N Walsh domain values at time t are found: Let nmaX(i) denote the rank, n, of the Walsh domain value which created Emax at estimator state, i. Then: i=l,2,...N <BR> <BR> <BR> t=1,2,...5 The largest combined energy of the N states, Es, is then found at t=5: and the state value associated with the largest combined energy is output as the channel estimate for finger K:

Data processing in accordance with the invention requires memory storage for only the N*K sequence state-metrics. The amount of processing required for the above-described data processing i n accordance with the invention is also substantially less than the N- MLSE method proposed by Walton and Wallace. FIG. 6 generally depicts a hardware implementation of the channel estimator 69 of FIG.

4 in accordance with the invention. The top N Walsh domain values are sorted in sorter 75, then placed into a memory buffer 68. With reference to FIG. 5, these top N Walsh domain values correspond to the top energies 500. The N state sequence metrics for each of the K fingers are next initialized to the values of the top N Walsh domain values for first Walsh symbol WSo in PCG 102 (i.e., top energies 500 from the first set), and these values are stored in a state metric RAM 200. For subsequent Walsh symbols WSI-WS5 in the PCG 102, each Walsh domain value is added at node 202 to a state sequence metric for each finger K. Since the Walsh domain value and the sequence metric are both complex values, two additions are required for each finger (one real, one imaginary). A squaring circuit 203 squares the result of the addition and feeds the product to an accumulator 204. The accumulator 204 sums the squared results of each finger to obtain a combined energy value 220 for the current sequence state transition.

For a four finger rake receiver, eight cycles (four real, four imaginary) are necessary for computing each combined energy value.

Next, the combined energy is compared by comparator 206 to the value stored in register 205 which is the maximum combined energy 221 for the current sequence state up to that time. The maximum combined register 205 is replaced with a newly computed energy if the new energy is greater than the current maximum energy value 221. In addition, if the new combined energy value is greater than the current combined energy value, each of the K complex sequence state metrics1 Wk(t), are stored in a set of registers 208. After the N combined energies have been computed for a given state, the stored sequence

state metrics 222 corresponding to the largest combined energy 221 replace the current state value contained within the state metric RAM 200. This continues for each of the N states and for each time step, up to time step 5 (t=5), the sixth received Walsh symbol WSs in the PCG 102. During the sequence estimation for this last Walsh symbol WSg, another comparator circuit 209 determines which of the N maximum combined energies 221 is the largest. The sequence state metrics 222 which are associated with this largest combined energy 223 are latched into a set of K complex-valued registers 210. When the sequence estimator is finished processing the last Walsh symbol WS5, these registers 210 contain the most likely channel estimate C for the K receive paths.

While the invention has been particularly shown and described with reference to a particular embodiment, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention. The corresponding structures, materials, acts and equivalents of all means or step plus function elements in the claims below are intended to include any structure, material, or acts for performing the functions in combination with other claimed elements as specifically claimed.

What I claim is: