Combined Array Processing and Space-Time Coding

This invention relates to communication, and primarily to wireless communication.

Physical limitations of wireless channels present a fundamental technical challenge to reliable communication. Bandwidth limitations, propagation loss, time variance, noise, interference, and multipath fading make the wireless channel a narrow "pipe" that does not easily accommodate the flow of data. Further challenges come from power limitation, size, and speed of devices that are employed within portable wireless apparatus. Employing multiple transmit antennas at both the base and the remote stations increases the capacity of wireless channels, and information theory provides a measure of this increase. The standard approach to exploit this capacity is linear processing at the receiver, as described, for example, by J. Winters, J. Salz and R. D. Gitlin, in "The impact of antenna diversity an the capacity of wireless communication systems" IEEE Trans. Communications, Vol. 42. No. 2/3/4, pp. 1740-1751, Feb/March/April 1994. Transmit diversity has been explored by Wittneben in "Base station modulation diversity for digital SIMULCAST," Proc. IEEE'VTC, pp. 505-511, May 1993, and by Seshadri and Winters in "Two signaling schemes for improving the error performance of frequency-division-duplex (FDD) transmission systems using transmitter antenna diversity," International Journal of Wireless Information Networks, Vol. 1, No. 1, 1994. The Wittneben and Seshadri et al papers approach transmit diversity from a signal processing point of view.

Space-time codes combine signal processing at the receiver with coding techniques appropriate to multiple transmit antennas. See, for example, V. Tarokh, N. Seshadri, and A. R. Calderbank in "Space-Time Codes For High Data Rate Wireless Communication: Performance Analysis and Code Construction," IEEE Trans. Info. Theory, Vol. 44, No. 2, pp. 744-765, March 1998. The space-time approach provides significant gain over the aforementioned prior art. Specific space-time codes designed for 2-4 transmitting antennas perform well in slowly varying fading environments (such as indoor transmission) and come with in 2-3 dB of the theoretical outage capacity. Outage capacity is described, for example, by J. Foschini, Jr. and M. J. Gans, "On limits of wireless communication in a fading environment, when using multiple antennas," Wireless Personal Communication, Vol. 6, No. 3, pp. 311-335, March 1998. The bandwidth efficiency of the codes described in the Tarokh et al paper is about 3-4 times that of the current systems. The most important contributor to the improved performance is diversity, which may be thought of as providing a number of replicas of the transmitted signal to the receiver, with some replicas being less attenuated by fading. The space-time codes presented in the Tarokh et al paper provide an optimized trade-off between constellation size, data rate, diversity gain, and trellis complexity

When the number of transmit antennas is fixed, decoding complexity (measured by the number of trellis states in the decoder) increases exponentially with transmission rate. This can be refined to some extent by designing space-time codes with a multi-level structure and adopting multi-stage decoding, as described by Tarokh et al. For a moderate number of transmit antennas (3-6), this method provides higher data rates while reducing the decoding complexity. However, there is a penalty to be paid for simplified decoding. Multi-stage decoding is sub-optimal, due in part to magnification in the error coefficient, and this performance penalty means that alternative solutions are needed for achieving very high data rates.

In order to achieve very high data rates on narrowband wireless channels, many antennas are needed at both the transmitter and the receiver. Consider a wireless communication system employing n transmit and m receive antennas, where the subchannel between each transmit and receive antenna is quasi-static Rayleigh, flat, and independent of others. If n is fixed, then the capacity increases logarithmically with m. On the other hand, if m is fixed then intuition suggests that there must come a point where adding more transmit antennas will not make much difference. Indeed, this can be seen in the mathematics of outage capacity, shown by Foschini and Gans in the aforementioned paper. Thus, it turns out that, in the presence of one receive antenna, little can be gained in terms of outage capacity by using more than 4 transmit antennas. A similar argument shows that if there are two receive antennas, using 6 transmitting antennas provides almost all of the capacity increase that can be obtained.

If n increases and m.gtoreq.n, then information theory shows that the capacity of the system increases at least linearly as a function of n. Thus, it makes sense to increase the number of antennas at both receiver and transmitter in order to obtain higher capacities. Employing many antennas at both transmitter and receiver create a multiple-input multiple-output system where the number of degrees of freedom is given by the product of the number of transmit and receive antennas.

Foschini considered such a system in "Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas," Bell Labs Technical Journal, Vol. 1, No. 2, Autumn 1996. He proposed a multi-layered structure that, in principle, can achieve a tight lower bound on the capacity. If n transmit and n receive antennas are used, then at the receiver the transmitted signal from transmit antenna 1 is treated as the desired signal, while the signals transmitted from other transmit antennas are treated as interference. Linear processing is then used to suppress the interfering signals using n receive antennas, providing a diversity gain of one. Once the signal transmitted from antenna 1 is correctly detected, the signal transmitted from antenna 2 is treated as the desired signal while the signals transmitted from transmit antennas 3, 4, . . . , n are treated as interference. The contribution of the signal transmitted from antenna 1, now that it has been detected, is subtracted from the signal received at receiver antennas 1 through n. Thereafter, detection of the signal transmitted by antenna 2 proceeds with linear processing that is applied to suppress the interfering signals from antennas 3 through n. This provides a diversity gain of two. This process is repeated until all the transmitted signals are detected. Clearly, the worst case diversity in this architecture is one. For such a system, long frames of data combined with powerful coding techniques are needed to achieve the lower bound on outage capacity.

We realized that the Foschini approach described above is purely a signal processing one, and that enhanced performance can be realized by employing a perspective that combines array signal processing with channel coding. Specifically, in accordance with our invention, antennas at the transmitter are partitioned into small groups, and individual space-time codes are used to transmit information from each group of antennas. At the receiver, an individual space-time code is decoded by a linear array processing technique that suppresses signals transmitted by other groups of antennas by treating them as interference. The contribution of the decoded signal to other received signal is then subtracted from those received signals. What results is a simple receiver structure that provides diversity and coding gain over uncoded systems with a given diversity gain. This combination of array processing at the receiver and coding techniques for multiple transmit antennas provides reliable and very high data rate communication over wireless channels. One advantage of the group interference suppression method over the Foschini architecture is that the number of receive antennas can be less than the number of transmit antennas.

This disclosure contemplates a wireless communication system with n antennas at the base and m antennas at the mobile station. As indicated above, such a system can be viewed as a multiple-input multiple-output system where the number of degrees of freedom is given by the product of the number of transmit and receive antennas. The approach disclosed here is to employ a small fraction of these degrees of freedom for improving the performance while using the remaining degrees of freedom to achieve higher data rates. This leads to a combination of space-time coding at the transmitter and array processing at the receiver, which achieves high data rates and operates close to the limits given by outage capacity.

In prior art arrangements where n transmitting antennas are employed, data to be transmitted by the base station is encoded using a channel code, is passed through a serial to parallel converter (or a multiplexing switch) and is divided into streams of data. Each stream of data is used as the input to a pulse shaper, and the output of each shaper is modulated and transmitted out. At each time slot, t, the output of antenna i is a signal c.sub.t.sup.i (1.ltoreq.i .ltoreq.n). It should be emphasized that the n signals are transmitted simultaneously, each from a transmitting antenna of a different modulator, and that all these signals have the same transmission period T.

The signal at each of the m receiver antennas is a superposition of the n transmitted signals, corrupted by noise and fading. Specifically, the signal r.sub.t.sup.i received by antenna j at time t is given by ##EQU1##

The coefficients .alpha..sub.i,j is the path gain from transmit antenna i to receive antennas j, and these coefficients capture the transfer characteristics between transmit and receive antennas. The noise on the channel between transmit antenna i and receive antenna is represented by .eta..sub.t.sup.j. The .alpha..sub.i,j coefficients are modeled as samples of independent complex Gaussian random variables with mean zero and variance 0.5 per dimension. This results from the assumption that signals transmitted from different antennas undergo independent Rayleigh fades. The noise quantities .eta..sub.t.sup.j are samples of independent complex Gaussian random variable with mean zero. It is also assumed that the .alpha..sub.i,j coefficients are constant during a frame data, but may vary from one frame to another (some artisans call this "quasi-static" fading). A "frame" of data is a collection of a present number of consecutively arriving data bits, where the collection is considered as a unit.

Equation (1), which describes the signal of one receiver antenna, can be expanded to cover all of the receiver antennas. Using conventional vector notations, equation (1) can be written as

where

and ##EQU2## Combined Array Processing and Space-Time Coding

The space-time product encoder employed herein apportions a frame of incoming stream of bits into time slots of duration T, accepts a block of B input bits in each time slot t, and divides the accepted bits into q strings of lengths B.sub.1, B.sub.2, . . . , B.sub.q ##EQU3## Moreover, in accordance with the present disclosure, the n transmitting antennas are partitioned into q groups G.sub.1, G.sub.2, . . . , G.sub.q, with each group G.sub.k having n.sub.k antennas ##EQU4## and each of the q strings B.sub.k, k=1, 2, . . . , q, is assigned to a different one of the q transmitting antenna groups. More specifically, each string B.sub.k is encoded by a space-time encoder C.sub.k, which develops n.sub.k symbols, and the encoded signal is transmitted by group G.sub.k of the transmitting antennas. This gives a total of n sequences of constellation symbols that are transmitted simultaneously from the n transmitting antennas.

We view a space-time product encoder of the type described above as a set of q space-time encoders that are the component codes, operating in parallel on the same wireless communication channel. Each of the encoders C.sub.k uses n.sub.k transmit and m receive antennas for k=1, 2, . . . , q. The complete product code is denoted by C.sub.1 .times.C.sub.2 .times., . . . , .times.C.sub.q.

Receiver Side

The task on the receiver side is to recover the transmitted data. One approach is to jointly decode all transmitted codewords, but shear complexity is the major difficulty with such an approach. If a diversity of r.times.m is required, where r.ltoreq.min(n.sub.k), then the complexity of the trellis of C.sub.k is at least 2.sup.B.sbsb.k.sup.(r-1) states, and the complexity of the product code is at least 2.sup.B(r-1) states. This means that if B is very large, the comprehensive joint decoding approach may be too complex to implement.

Hence, the novel approach of this disclosure employs the notion of group interference suppression. The idea is to decode each code C.sub.k separately while suppressing signals from other component codes. This approach has a much lower complexity but achieves a lower diversity order than the full diversity order m.times.n of transmit and receive antennas. More specifically, the receive antennas are divided into q groups, and the signals of each group of antennas are handled as a collection of signals from which one of the encoded signals transmitted by a group of transmitting antennas is decoded.

To describe group interference suppression method, without loss of generality, the following the signal decoding carried out by the first group of receiving antennas, where the signal encoded with C.sub.1 is decoded. In this case, there are n-n.sub.1 interfering signals. Equation (4) can be decomposed into

where ##EQU5## and one can observe that .LAMBDA.(C.sub.1) has a rank less than or equal to the number of its columns.

Thus, R[.LAMBDA.(C.sub.1)].ltoreq.n-n.sub.1, where R [.LAMBDA.(C.sub.1)] denotes the rank of .LAMBDA.(C.sub.1).

It is known that N ,the null space of this matrix, is the set of all row vectors x such that x.LAMBDA.(C.sub.1)=(0,0, . . . ,0). It is also known that

Since R [.LAMBDA.(C.sub.1)].ltoreq.n-n.sub.1, it follows that dim(N).ltoreq.m-n+n.sub.1. Therefore, a set of orthonornal vectors {V.sub.1, V.sub.2, . . . , V.sub.m-n+n.sub.1 } can be computed in N (though not necessarily a unique set). Algorithms for computing V.sub.k, k=1,2, . . . , m-n+n.sub.1 are well known. See, for example, Gilbert Strang, Linear Algebra and Its Applications.

Setting ##EQU6## and multiplying both sides of the Equation (2) by .THETA.(C.sub.1) yields

Replacing .OMEGA. by its equivalent from equation (5), and noting that .THETA.(C.sub.1).LAMBDA.(C.sub.1)=0 is the all zero matrix, equation (7) can be written as

which can be rewritten as

where

and

This is an equation where all the signal streams out of antennas n.sub.1 +1, n.sub.1 +2, . . . , n are suppressed.

The Receiver

In the following discussion, it is assumed that .LAMBDA.(C.sub.1) and .THETA.(C.sub.1) are known through some means (for example, through a sending of a known signal from one transmitting antenna at a time, measuring results, and determining therefrom the values of .alpha..sub.i,j), and that the receiver outputs a set of orthonormal vectors {V.sub.1, V.sub.2, . . . , V.sub.m-n+n.sub.1 }. Letting

results in .OMEGA..sub.ij =v.sub.i w.sub.j, where w.sub.j is the j-th column of .OMEGA.(C.sub.1). The random variable .OMEGA..sub.ij has zero mean, given the characteristics of .LAMBDA.(C.sub.1). Moreover,

where .delta. is the Kronecker delta function given by .delta..sub.rs =0 if r.noteq.s. Hence, the elements of the (m-n+n.sub.1).times.n.sub.1 matrix .OMEGA..sub.ij are independent complex Gaussian random variables of variance 0.5 per real dimension. Similarly, the components of the noise vector .eta..sub.t, t=1,2, . . . ,l are independent Gaussian random variables of variance N.sub.o /2 per real dimension.

Assuming that all the codewords of C.sub.1 are equi-probable and given that group interference suppression is performed, the proposed receiver for C.sub.1 decides in favor of the codeword

if it minimizes the decision metric ##EQU7##

This means that following the execution of group interference suppression, the decoder of C.sub.1 treats the vector r.sub.t as the received word at time t and the matrix .OMEGA. as the matrix of path gains.

If the code C.sub.1 is a space-time trellis code, then the branch metric for a branch labeled with c.sub.t.sup.1 c.sub.t.sup.2. . . c.sub.t.sup.n.sbsb.1 at time t is .vertline.r.sub.t -.OMEGA.c.sub.t.sup.1 .vertline..sup.2.

It can be shown that, under the assumptions made so far, the probability of error in a system that uses n transmit antennas and m receive antennas (m.gtoreq.n-n.sub.k +1), for C.sub.1 using the group interference suppression method, is the same as the probability of error in a system that comprises n.sub.k transmit antennas and m-n+n.sub.k receive antennas (for the same average power).

This fact reduces code design code design for a multiple antenna communication system with n transmit and m receive antennas to that of designing codes for communication systems with n.sub.k transmit antennas and in m-n+n.sub.k receive antennas, where ##EQU8## and n.sub.k .gtoreq.n-m+1. Using this insight, a multi-layered space-time coded modulation embodiment can be designed. The idea, behind such a system is multistage detection and cancellation.

Suppose that C.sub.1 is decoded correctly using combined array processing and space-time coding. From the above, it can be observed that the space-time code C.sub.1 affords a diversity gain of n.sub.1 .times.(m-n+.sub.1). After decoding C.sub.1, we may subtract the contribution of these codewords to signals received at different antennas. This gives a communication system with n-n, transmit and m receive antennas. We next use combined array processing and space-time coding to decode C.sub.2. The space-time code C.sub.2 affords a diversity gain of n.sub.2 .times.(m-n+n.sub.1 +n.sub.2). Proceeding in this manner, we observe that by subtracting the contribution of previously decoded code streams C.sub.j, j.ltoreq.k-1 to the received signals at different antennas, the space-time code C.sub.k affords a diversity gain of n.sub.k .times.(m-n+n.sub.1 +n.sub.2 +. . . +n.sub.k).

We can choose space-time codes C.sub.i, 1.ltoreq.i.ltoreq.q to provide these diversity gains, such that the sequence

be an increasing sequence. Assuming there was no decoding error in steps 1,2, . . . , k-1, then at decoding step k, the probability of error for the component code C.sub.k is equal to the probability of error for C.sub.k when employed in a communication system using n.sub.k transmit and m-n+n.sub.1 +n.sub.2 +. . . +n.sub.k receive antennas.

Since the diversity in each decoding stage k is more than that of the previous decoding stage k-1, the transmit power out of each antenna at level k can be substantially less than that of the previous layer. Thus the transmitter should divide the available transmit power amongst different antennas in an unequal manner. Power allocation for this scenario is straightforward. In fact powers at different levels could be allocated based on the diversity gains. In this way, the allocated powers can be engineered to decrease geometrically in terms of the diversity gains.

Alternatively, to speed operations, the detection of all stages can be performed simultaneously for each code C.sub.k.

The FIG. 1 presents an embodiment where q=3, the number of transmitting antennas in groups 1, 2, and 3, is 2, 3, and 1, respectively, and the number of receiving antenna is 2 in each of the three receiver groups. More specifically, incoming frames of B bits are applied to serial to parallel converter 100 (or multiplexing switch), and the converter creates q collections (q=3) of B.sub.k bits each such that ##EQU9## The first collection is applied to encoder 110, the second collection is applied to encoder 120, and the third collection is applied to encoder 130. Encoder 110 encodes the signal in accordance with C.sub.1 and develops two symbols for each collection of B bits; encoder 120 encodes the signal in accordance with C.sub.2 and develops three symbols for each collection of B bits; and encoder 130 encodes the signal in accordance with C.sub.3 and develops one symbol for each collection of B bits. The symbols of encoders 110-130 are modulated in transmitters 110-1, 110-2, 120-1, 120-2, 120-3, and 130-1 and transmitted through their respective antennas.

The receiver side of the figure includes three groups, with each group containing two receiver sections. Thus, the figure shows receiver 210-1 and 210-2, receivers 220-1 and 220-2, and receivers 230-1 and 230-2. The outputs of each of the receivers in each group is applied to a respective processing unit (210, 220, and 230), and the outputs of processing units 210, 220, and 230 are applied to a processing unit 250 which develops the received output frame. The receiver of FIG. 1 is of the type where the receivers employ knowledge gained from other receivers. Accordingly, processing unit 220 is responsive to the output of processing unit 210, and processing unit 230 is responsive to the outputs of processing units 210 and 220.

The operation of encoders 110-130 is conventional. Illustratively, the C.sub.1, C.sub.2, and C.sub.3 codes are trellis codes that develop 2 symbols, 3 symbols, and 1 symbol, respectively and form the component codes of a product code. Trellis code encoders are conventional.

The processing carried out in processor 210 follows the above teachings. Having knowledge of the .alpha..sub.i,j values (through conventional means that form no part of this invention), the matrix .LAMBDA.(C.sub.1) (equation (7)) is constructed in processor 210, a set of vectors {v.sub.1, v.sub.2, . . . , v.sub.m-n+n.sub.1 } is calculated, and the matrix .THETA.(C.sub.1) is thus constructed. The signal received by receivers 210-1 and 210-2 is multiplied by .THETA.(C.sub.1) to yield r.sub.tt of equation (12). Forming the product matrix .OMEGA.=.THETA.(C.sub.1).OMEGA.(C.sub.1) allows processor 210 to select the codeword c.sub.t.sup.1 that minimizes equation (17).

The processing carried out in processor 220 and 230 can be identical in form to the processing carried out in processor 210 (with coding, .theta.(C.sub.2) and .THETA.(C.sub.3), and {v.sub.1, v.sub.2, . . . , v.sub.m-n+n.sub.2 } and {v.sub.1, v.sub.2, . . . , v.sub.m-n+n.sub.3 }, respectively. Alternatively, as discussed above, after decoding C.sub.1, the contribution of these codewords to signals received at different antennas can be subtracted and, to that end, the FIG. 1 embodiment shows a connection from the output of processor 210 to processors 220 and 230, and a connection from the output of processor 220 to processor 230.

The above disclosure presented the principles of our inventions, but it should be appreciated that various modifications can be employed without departing from the spirit and scope of this invention. For example, the embodiments describe realize diversity in the spatio-temporal domain. However, other means for creating diversity, such as utilizing the frequency domain, are also possible.