US 2007/0105595 A1Application

JOINT SCHEDULING AND GROUPING FOR SDMA SYSTEMS

Publication Date:2007-05-10

•11 Claims

•13 Drawing Sheets

Abstract

A joint scheduling and grouping technique for throughput maximization is disclosed for an uplink space-division multiple access (SDMA) system under proportional fairness constraints, when the receiver employs successive group decoding. We consider a slow-fading narrowband MIMO multiple access channel (MAC) in which multiple users, each equipped with multiple transmit antennas, communicate to a receiver equipped with multiple receive antennas. The users are unaware of the channel state information (CSI) whereas the receiver has perfect CSI and employs a successive group decoder (SGD). For an open-loop system, achievable outage probabilities are obtained for the case where an outage must be declared simultaneously for all users (common outage) as well as the case where outages can be declared individually for each user (individual outage). We then derive the optimum successive group decoder (OSGD) that simultaneously minimizes the common outage probability and the individual outage probability of each user, over all SGDs of permissible decoding complexity. For each channel realization, the OSGD is also shown to maximize the error exponent of the decodable set of users. An adaptive SGD is derived which not only retains the outage optimality of the OSGD but also minimizes the expected decoding complexity. Asymptotically tight (in the limit of high SNR) affine approximations are then obtained for the weighted sum common and individual outage capacities and the symmetric outage capacities. Limiting expressions for the relevant capacities as the number of users and the number of receive antennas approach infinity are also obtained and it is shown that the SGD yields symmetric capacity gains commensurate with the decoding complexity allowed. Simulation results with practical LDPC outer codes show that the OSGD offers significantly improved performance at low decoding complexity.

Metadata

Inventors

Narayan Prasad
Xiaodong Wang
Mohammad Madihian

Application Information

Application Number:US 11/554,957

Filing Date:2006-10-31

Priority Date:2005-10-31

Classifications

IPC:

H04B1/02H04B1/06H04M1/00

Patent Drawings (13 sheets)

Description

Cross Reference to Related Applications

[0001] This application claims the benefit under 35 U.S.C. § 119 of U.S. Provisional Application No. 60/731,884, filed Oct. 31, 2005, U.S. Provisional Application No. 60/732,870, filed Nov. 2, 2005, and U.S. patent application Ser. No. 11/428,386 filed on Jul. 1, 2006, the entire contents and file wrappers of which are hereby incorporated by reference for all purposes into this application.

Field of the Invention

[0002] The present invention relates to the field of wireless communications, particularly cellular wireless communications employing space-division multiple access (SDMA).

Background Information

[0003] Over a wireless multiple-input-multiple-output (MIMO) multiple access channel (MAC), several users (mobiles) communicate simultaneously to a common receiver, known in cellular communications as the base-station. Uplink space-division multiple access (SDMA), where multiple users of the same sector/cell share the same set of resources at a given time, coupled with advanced receiver processing at the base-station can lead to a dramatic increase in system throughput. Traditionally, strictly orthogonal (non-SDMA) uplink systems such as TDMA/FDMA have been preferred since the simple, albeit sub-optimal, match filter receivers employed at base-stations so far are not suitable for SDMA. The advent of multiple receive antennas at the base-station, however, and improvements in technology have made possible the use of advanced receiver processing and hence SDMA. Consequently, quasi-orthogonal OFDMA and IFDMA, where subsets of users are allocated the same resources, are being proposed to accommodate ambitious future throughput requirements. A challenge is to design scheduling and receiver processing algorithms that garner most of the throughput increase promised by SDMA but with practically feasible complexities.

[0004] SDMA is also being considered to obtain throughput improvements in downlink systems where the transmitter (base-station) as well as each user have multiple antennas. Multi-stream MIMO schemes have been proposed, where over each resource block, the base-station transmits multiple independent streams to the intended user. Note that there is a direct analogy between independent single-antenna users in the SDMA uplink and the independent multiple streams in the downlink. The role of the base-station in the uplink is assumed by the intended multiple-receive-antenna user in the downlink. A challenge again is to obtain the throughput increase promised by SDMA with practically feasible complexities.

[0005] Other studies have looked into the scheduling (i.e. rate-assignment) problem for minimum mean square error (MMSE)-based successive interference cancellers (SIC). Although in theory, a MMSE-SIC decoder is (sum) capacity achieving for an SDMA configuration, in practice, a more advanced receiver such as an MMSE-based successive group decoder (SGD) may considerably increase throughput. In a practical system, the transmission rate for each user is chosen from a finite set of limited granularity, therefore, for each channel realization, the number of possible rates for a general successive group decoder is greater because its capacity region is larger than that of MMSE-SIC. As a result, a rate-assignment having a higher sum can be chosen and fed back to the users.

[0006] On a flat-fading MAC, due to stringent delay-constraints, each transmitted codeword experiences just one (or few) fading realization(s). Outage probability has emerged as a useful tool for such non-ergodic (slow-fading) settings. For a MAC where only the receiver has perfect channel state information (CSI), an outage can be declared simultaneously for all users if the rate vector containing the information rates of all (active) users lies outside the instantaneous achievable rate region, which in turn is a function of the instantaneous channel state and the decoder used. Occurrence of this outage event, henceforth referred to as the common outage, indicates that a joint error event (i.e., event that at least one user is decoded erroneously) is very likely and the common outage probability, denoted by Pr( custom character

), represents an achievable joint or frame error probability (FEP). Pr( custom character

) was derived in D.N.C. Tse et al. “Diversity-multiplexing tradeoff in multiple-access channels,” IEEE Trans. Inform. Theory, vol. 50, no. 9, pp. 1859-1874, September 2004 for the case where the receiver employs the optimum joint decoder, and in N. Prasad et al., “Outage based analysis for MultiaccessNV-BLAST architecture over MIMO block Rayleigh fading channels,” Proc. Allerton Conf. on Comm., Control, and Comput., Monticello, Ill., October 2003, University of Illinois where the receiver employs successive decoders.

[0007] A finer outage formulation, in which an individual outage can be declared for each user, was developed in L. Li, N. Jindal et al., “Outage capacities and optimal power allocation for fading multiple-access channels,” IEEE Trans. Inform. Theory, vol. 51, no. 4, pp. 1326-47, April 2005 for the scenario where in addition to the receiver, each transmitting user has perfect CSI. Unfortunately, the absence of CSI at the user end considerably complicates the individual outage formulation. Essentially, the receiver should declare an individual outage for each user that it deems cannot be reliably decoded for the current channel state. Declaring a common outage for all users is very conservative since the receiver does not wish to make even a single error. On the other hand, an aggressive approach may yield a set of individual (per-user) outage probabilities that is not achievable (i.e., error probabilities arbitrarily close to these outage probabilities cannot be attained) and hence of little use. Obtaining a “good” set of achievable individual outage probabilities, where many if not all are smaller than the common outage probability, is difficult for the successive decoder due to the intractability of precisely modeling error propagation and is not known for the maximum likelihood (ML) decoder.

[0008] Successive group decoders (SGDs) were introduced in M. K. Varanasi, “Group detection for synchronous gaussian code-division multiple-access channels,” IEEE Trans. Inform. Theory, vol. 41, no. 4, pp. 1083-1096, July 1995, for the uncoded Gaussian CDMA channel, and are an extension of the conventional successive decoder in that at each decoding stage a subset of users can be jointly decoded instead of just one. The useful feature of such decoders is that they provide the system designer with a broad choice, spanning from the low-complexity successive decoder to the high-complexity ML decoder. Moreover, they are inherently better suited to a MAC (as opposed to the MIMO point-to-point system) since coding across transmitters (users) is not possible.

[0009] A SISO point-to-point channel is considered in S. A. Jafar et al., “Throughput maximization with multiple codes and partial outages,” in Proc. IEEE Global Telecommun. Conf., San Antonio, Tex., 2001 (hereinafter “Jafar et al.), where the transmitter employs multiple codes and the receiver uses the successive decoder. The successive decoder in Jafar et al. stops decoding at the first instance when an outage occurs, i.e., when the effective (scalar) channel cannot support the rate, and outages are declared for the current and remaining codes.

[0010] A joint decoder for a two-user symmetric MAC is proposed in S. Shamai et al., “A broadcast approach for a single-user slowly fading MIMO channel,” IEEE Trans. Inform. Theory, vol. 49, no. 10, pp. 2617-2635, October 2003, which works as follows. It first determines if both users can be decoded reliably via the ML decoder, if not it checks if any one of the users can be decoded reliably via either one of the two successive decoders (defined by decoding orders { 1,2} and {2,1 }, respectively) after treating the other user as a Gaussian interferer. Outage is declared for users deemed undecodable.

Summary of the Invention

[0011] In an exemplary embodiment, the present invention provides outage formulations for successive group decoders (SGDs) and parallel group decoders (PGDs) over an open-loop SDMA uplink. Using these formulations, the achievable common and individual outage probabilities for SGDs and PGDs are obtained and an optimal SGD (OSGD) as well as an optimal PGD (OPGD) are derived which simultaneously minimize these probabilities and maximize the error exponent over all SGDs and PGDs, respectively, of permissible decoding complexities.

[0012] In an aspect of the present invention, a greedy algorithm which determines the OSGD is obtained which drastically reduces the complexity of determining the optimal partition. Two other exemplary greedy algorithms are proposed which further reduce the complexity and yield SGDs which are optimal with respect to the common and individual outage probabilities.

[0013] An adaptive SGD is derived which is optimal with respect to the common and individual outage probabilities and also minimizes the expected (average) decoding complexity.

[0014] An exemplary embodiment of the present invention is directed to a joint scheduling and grouping technique for throughput maximization for an uplink SDMA system under proportional fairness constraints in which the receiver (e.g., a base-station) employs successive group decoding. The receiver is equipped with multiple receive antennas and can communicate with each user via a limited capacity downlink channel, a situation which is typical of emerging cellular base-stations. The maximum tolerable decoding complexity and the (uplink) channel realizations (of all users) can be specified as inputs. The optimal set of user rates can then be determined along with a successive group decoder of permissible decoding complexity.

[0015] In a further aspect of the present invention, two near-optimal greedy techniques of greatly reduced complexity are disclosed which result in negligible loss in throughput. As a consequence of the analogy between the SDMA uplink and multi-stream MIMO downlink mentioned above, the optimal and near optimal approaches can be extended to the latter schemes as well. Notably, the techniques can be extended beyond the context of an SDMA uplink.

[0016] The present invention provides optimal as well as near-optimal scheduling and grouping techniques suitable for emerging SDMA-based cellular uplink as well as multi-stream MIMO downlink schemes. Scheduling and grouping techniques in accordance with the present invention result in substantial throughput improvements while satisfying specified decoding complexity constraints.

[0017] As mentioned above, other work has considered scheduling (rate-assignment) and ordering algorithms for a MMSE-SIC decoder which is an extreme case (having the lowest complexity) of a SGD, as considered herein. However developing an optimal grouping and scheduling algorithm for the general case requires an entirely new formulation. Moreover, allowing for a slight increase in decoding complexity allows for dramatic throughput gains in practical systems where each user has only a small number of codebooks of distinct rates.

[0018] Finally, asymptotically tight (in the limit of high SNR) affine approximations to the performance metrics relevant for the OSGD are obtained. These bounds capture the effects of relevant channel parameters and decoding complexity constraints. Limiting expressions for the relevant capacities when the number of users and the number of receive antennas approach infinity are obtained and it is shown that an SGD yields symmetric capacity gains commensurate with the decoding complexity allowed. [00019] The aforementioned and other features and aspects of the present invention are described in greater detail below.

Brief Description of the Drawings

[0019] FIG. 1 is a schematic representation of a communications system comprising an SDMA uplink channel in which the receiver employs throughput-maximizing scheduling and grouping in accordance with an embodiment of the present invention.

[0020] FIG. 2 is a chart of throughput versus signal-to-noise-ratio (SNR) for a six-user multiple access channel with six receive antennas at a base-station employing exemplary joint scheduling and grouping algorithms.

[0021] FIG. 3 is a chart of outage probability versus SNR for an ML decoder and OSGD under various rates and group sizes in an open-loop symmetric MAC with six users and a base-station with six receive antennas.

[0022] FIG. 4 illustrates the performance of an exemplary adaptive SGD (for an open-loop symmetric MAC) which adapts the maximum group size parameter (u*) based on the channel realizations and then selects the optimal partition which satisfies the maximum group size constraint, with FIG. 4 plotting the number of channel realizations for which a particular value of u* (from the set { 1,2,3}) was selected.

[0023] FIG. 5 is a chart of outage probability and frame error probability (FEP) versus SNR for an ML decoder and an OSGD in an open-loop symmetric MAC with four users and a base-station with four receive antennas.

[0024] FIG. 6 is a chart of frame error probability (FEP) versus SNR for a SGD and an OSGD operating with group sizes of one and two in an open-loop symmetric MAC with four users and a base-station with four receive antennas.

[0025] FIG. 7 is a chart of frame error probability (FEP) versus SNR for a SGD and an OSGD operating with group sizes of one and two in an open-loop symmetric MAC with four users and a base-station with four receive antennas.

[0026] FIG. 8 is a chart of frame error probability (FEP) versus SNR for a soft interference canceller and an OSGD operating with group sizes of one and two in an open-loop symmetric MAC with four users and a base-station with four receive antennas.

[0027] FIG. 9 is a chart of symmetric outage capacity versus SNR for an ML decoder, an SGD and an OSGD operating with different group sizes.

[0028] FIG. 10 is a chart of the symmetric common outage capacity asymptotes corresponding to an OSGD with μ_max=2 and an SGD with a fixed partition {{ 1, 2}1,3} for ε=0.01 and ε=0.1, respectively.

[0029] FIG. 11 is a chart of symmetric outage capacity versus number of antennas for an SGD and an OSGD with μ_max=1 and ε=0.1 and ε=0.01.

[0030] FIG. 12 is a chart of symmetric capacity versus SNR for an SGD with various group size parameter (δ) values.

Detailed Description

1 Introduction

[0031] FIG. 1 provides a schematic representation of a communications system 100 comprising an SDMA uplink channel. The system 100 comprises one or more user equipment (UE)110.1-110.K, and a base station 120. Each UE 110 has a transmitting antenna 111 and the base station 120 has multiple receiving antennas 121.1-121.N coupled to a receiver 125. The base station 120 also includes a channel estimator 135, a scheduling and grouping element 145, and a successive group decoder (SGD) 155. The system employs a scheduling and grouping technique in accordance with an exemplary embodiment of the present invention to be described in greater detail.

[0032] As shown in FIG. 1, one or more feedback channels may be provided from the base station 120 to the one or more UE 110. In existing systems, any such feedback channels are typically limited in bandwidth. The absence of feedback channels results in an open- loop system. In an exemplary open-loop SDMA system, the UE transmit using constant rate codebooks.

[0033] In an exemplary embodiment of the present invention, channel estimator 135 provides an estimate of the uplink channel to the scheduling and grouping element 145. The scheduling and grouping element 145 also receives decoding complexity constraints as inputs. These inputs can be specified, for instance, as the maximum number of users that can be jointly decoded at each stage in the SGD. Based on these inputs, an optimal rate vector along with a partition of active UEs for successive group decoding can be determined. The optimal rate vector is a vector containing the rate assignment of each UE 110. The rate assigned to each UE 110 is one of a finite set of distinct rates at which the UE can transmit on the uplink to the base station 120. Each UE 110 is informed of the rate assigned to it over the current scheduling block via the limited capacity feedback channel. A UE 110 assigned a rate of zero is not scheduled for the current scheduling block and is deemed inactive. In open-loop systems, all users are active and the rate vector is constant. In this case, the scheduling and grouping element is only a grouping element and only a partition of UEs for either successive group decoding or parallel group decoding is determined.

[0034] The SGD 155 (specified by the partition of active users selected), always satisfies the imposed complexity constraints. Consider a system with four UEs indexed by (1,2,3,4). A partition of (1,2,3,4) is a collection of disjoint subsets whose union is (1,2,3,4). For example {(1,2),(3,4)} is a partition. Further, the SGD using the partition {(1,2),(3,4)} would jointly decode users (1,2) first followed by users (3,4). Note that the order of subsets in the partition is important for an SGD but not for a PGD.

[0035] In an exemplary embodiment of the present invention, the scheduling and grouping element 145 is implemented in accordance with exemplary, near-optimal greedy scheduling and grouping schemes. The schemes are described below in greater detail.

[0036] To illustrate, consider a system with four UEs indexed by (1,2,3,4). If each UE can communicate using only one rate, then feedback of one bit per UE is needed for each scheduling block and the scheduling process corresponds to a simple on-off scheduling. If the decoding complexity is constrained by allowing only partitions having maximum group size |G|_max=2, there are 42 possible partitions of all four users (such as ({1,2},{3,4}), ({3,4},{1,2}), etc.) Since each user can be assigned a rate of zero or a single positive rate, there are 16 possible rate allocations for each partition.

[0037] In accordance with a derived metric, an optimal scheduling and grouping approach will pick the optimal rate-allocation and the partition among these 16×42 possibilities. The aforementioned greedy scheduling and grouping schemes will pick a near-optimal rate allocation and partition after evaluating only a significantly reduced set of possibilities. The SGD employed by the base-station for that block is uniquely defined by the optimal partition of active users and satisfies the decoding complexity constraint. Note that the partition used by the SGD can change dynamically based on the channel realizations.

[0038] FIG. 2 is a graph of throughput versus signal-to-noise-ratio (SNR) which shows the performance of exemplary joint scheduling and grouping algorithms in accordance with the present invention and that of an exemplary optimal grouping algorithm, which is described below. The exemplary optimal grouping algorithm was designed for an open-loop system where there are no feedback channels and is also optimal for systems in which the base-station employs a simple round-robin scheduler having one bit of feedback from the base-station to each user per-transmission frame.

[0039] FIG. 2 plots the two throughputs yielded by the exemplary open-loop grouping algorithm (+signs and circles) where “all-or-none” indicates the throughput obtained when the base-station declares a common outage and discards all packets even if one packet is in error (decoded incorrectly) and “partial-out” indicates the throughput obtained when only the packets deemed to be in error by the base-station are discarded and individual outages are declared for corresponding users. Also plotted in FIG. 2 is the throughput obtained with an exemplary optimal scheduling and grouping algorithm with only one-bit per user feedback (triangles). In all cases, the decoding complexity is constrained by setting the maximum group size to 2. The throughput obtained with an exemplary greedy scheduling and grouping algorithm is also plotted (squares). It is seen from FIG. 2 that even a one bit per-user feedback results in dramatic gains and the performance of the exemplary greedy scheduling and grouping algorithm of the present invention is indistinguishable from that of the optimal scheduling and grouping algorithm.

[0040] More detailed descriptions of an SGD, an optimal SGD (OSGD) and a joint scheduling and grouping algorithm in accordance with the present invention are provided below.

2 Successive Group Decoder (SGD)

[0041] 2.1 MIMO MAC Model

[0042] A discrete-time model of a slow-fading narrowband multiple access channel (MAC) is first considered. As shown in FIG. 1, the base-station 120 has N≦1 receive antennas and communicates with K users over the MAC 115. The k^thuser has m_k≦1 transmit antennas. The channel output is as follows:
Y=HQ^1/2X+V. (1)

[0043] The random matrix H=[H₁, . . . , H_K] stays constant for custom character

symbol intervals (the coherence interval) after which it switches to an independent value. It is assumed H is known perfectly to the receiver 120 but is unknown to the transmitters 110. Y is the N× custom character

received signal matrix and the (effective) fading is described by the N× custom character

Σ_k=1^Km_k custom character

matrix H drawn from some continuous distribution. In the presence of inter-cell interference, typically modeled as a spatially colored Gaussian vector, (1) models the output post whitening.

[0044] The N× custom character

matrix V represents additive noise at the receiver and is assumed to have i.i.d. CN (0,1) elements. Q=diag{Q₁, . . . ,Q_K} is a block-diagonal matrix with tr(Q_k) representing the average transmit power used by the k^thuser.

[0045] The (Σ_k=1^Km_k)× custom character

matrix X can be partitioned as X=[X₁^T, . . . , X_K^T]^Tand the m_k× custom character

matrix Q_k^1/2X_krepresents the input from the k^thuser and is transmitted over custom character

consecutive symbol intervals. In particular, X_kis drawn equiprobably from a Gaussian codebook of rate R_kand covariance I_m_k.

[0046] 2.2 SGD Model

[0047] The successive group decoder (SGD) is an extension of the standard successive decoder in that at each stage a subset of users is jointly decoded after treating the transmissions of the remaining users as Gaussian interference. Formally, to define group decoders we introduce a bounding function ƒ(.) whose purpose is to impose the decoding complexity constraints. Let custom character

denote the set of all non-empty subsets of {1, . . . , K}. Then we define a function ƒ: custom character

→{0,1}, such that for any subset custom character

∈

, ƒ(

)=1 means that at any decoding stage, the users in custom character

can be jointly decoded, whereas ƒ( custom character

)=0 means that at no stage is the joint decoding of custom character

allowed. We further impose the reasonable restriction on ƒ(.) that if ƒ( custom character

)=1 then ƒ( custom character

)=1, {0

⊂

. Examples of bounding functions include:

f (𝒥) = {\begin{matrix} 1, & \langle 𝒥 \rangle \leq μ_{\max}, \\ 0, & otherwise, \end{matrix}

corresponding to size control, and

f (𝒥) = {\begin{matrix} 1, & \sum_{j \in 𝒥} R_{j} \leq r_{sum}, \\ 0, & otherwise, \end{matrix}

corresponding to sum rate control.

[0048] Next, for a given bounding function ƒ(.), an ordered partition ={ custom character

₁, . . . , custom character

_p} of {1, . . . , K} is deemed valid if ƒ( custom character

_k)=1,1≦k≦p. Let be the set of all valid ordered partitions and define {tilde over (H)} custom character

HQ^1/2. For any subset A⊂{1, . . . , K}, let Rdenote the vector of rates of users with indices in custom character

. Then, for any two disjoint subsets custom character

and

of {1, . . . , K}, let custom character

({tilde over (H)}, custom character

) denote the instantaneous achievable-rate region for users in custom character

decoded using an ML decoder, after assuming users in custom character

to be additive Gaussian interferers. In particular, denoting {tilde over (H)} custom character

[{tilde over (H)}_j]_j∈, we have that:

\begin{matrix} 𝒞 (\tilde{H}, 𝒜, ℬ) = {r \in ℝ_{+}^{\langle 𝒜 \rangle} : \sum_{j \in 𝒟} r_{j} < I (x_{𝒟}; y | x_{𝒜 \ 𝒟}), \forall 𝒟 \subseteq 𝒜}, where : I (x_{𝒟}; y | x_{𝒜 \ 𝒟}) = \log \langle I + {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle . & (2) \end{matrix}

[0049] Then for any valid ordered partition { custom character

₁, . . . , custom character

_p}, an exemplary embodiment of an SGD operates as follows:

[0050] 1. Initialize with inputs: k=1, {tilde over (H)}, R, { custom character

₁, . . . , custom character

_p}. 2. Check condition R_k∈ custom character

({tilde over (H)}, custom character

_k, ∪_j=k+1^p custom character

_j).

[0051] 3. If check is true,

- [0052] a) Compute Σ_k=I+Σ_j=k+1^p{tilde over (H)}_j{tilde over (H)}_j{tilde over (H)}_j^†and decode users in _kaccording to $\begin{matrix} {\hat{X}}_{𝒢_{k}} = \arg \min_{X_{𝒢_{k}}} { \sum_{𝒢_{k}}^{- \frac{1}{2}} (Y - {\tilde{H}}_{𝒢_{k}} X_{𝒢_{k}}) }^{2} . & (3) \end{matrix}$
- [0053] b) Update Y=Y−{tilde over (H)}_k{tilde over (X)}_kand k=k+1.
- [0054] c) If k=p+1 stop, else go to step 2.

[0055] 4. If check is false, declare individual outages for all users in ∪_j=k^p custom character

_jor a common outage for every user.

[0056] Thus, with this exemplary embodiment, a common outage for all users, denoted by custom character

, occurs if the following holds true:
∪_k=1^p custom character

R_k∉

({tilde over (H)}, custom character

_k, ∪_j=k+1^p custom character

_j)

, (4)
whereas an individual outage for user k∈ custom character

_q, denoted by custom character

_k, occurs if
∪_j=1^q custom character

R_j∉

({tilde over (H)}, custom character

_j, ∪_s=j+1^p custom character

_s)

, (5)
holds true. From (4) and (5) it is evident that both outage events depend strongly on the chosen ordered partition. For the given rate-tuple R and a bounding function ƒ(. ), the exemplary SGD can employ any valid ordered partition. Note that as opposed to other SGDs, with the exemplary SGD, only the users not in outage are decoded. This is a desirable feature since an outage should be declared for a user if the likelihood of decoding it incorrectly is high, and in that event it makes sense to not expend system resources in decoding that user.

[0057] A special case arises when there is only one group {1, . . . K} and for this case it is clear that the individual and common outage events are identical, i.e., when R∉ custom character

({tilde over (H)}, {1, . . . , K}, φ), a common outage as well as an individual outage is declared for all users. Henceforth, we refer to the SGD corresponding to this partition as the ML decoder since the decoding (done under the non-outage event) is maximum likelihood. Although the decoder is not ML for channels in outage, it represents a natural counterpart of the true ML decoder within our framework of decoding only users not in outage.

[0058] Another special case is when the SGD uses an ordered partition with all groups of size 1. This decoder is a counterpart of the standard MMSE successive interference canceler (MMSE-SIC) decoder within the framework of decoding only users not in outage. As opposed to the standard MMSE-SIC decoder, however, the exemplary successive decoder stops decoding at the first instance that a user is found in outage. This allows defining outage events without making any simplifying assumptions about the nature of error propagation and, as a consequence, it is possible to rigorously prove the achievability of the resulting outage probabilities.

[0059] Note that the policy of not continuing to decode beyond the first user in outage is not too pessimistic. This follows since it is very likely that a decoding error occurs for the first user in outage and if that erroneous decision is fed back, the likelihood of making decoding errors for subsequent users also becomes high.

[0060] It is desirable to determine the optimal grouping (partitioning) function, which for every channel realization returns a valid ordered partition such that the resulting outage probabilities are minimized. Since the number of valid ordered partitions can be very large, it would be very useful if the optimal channel dependent partition(s) could be efficiently determined. For instance, with a maximum group size constraint, the cardinality of can be determined using standard combinatorial results to be:

\begin{matrix} \langle \rangle = \sum_{\underset{\sum_{i = 1}^{μ_{\max}} {ib}_{i} = K}{{b_{i} \in ℤ_{+}}_{i = 1}^{μ_{\max}}}} \frac{(\sum_{i = 1}^{μ_{\max}} b_{i})! K!}{b_{1}! \dots b_{μ_{\max}}! {(1!)}^{b_{1}} \dots {(μ_{\max}!)}^{b_{μ_{\max}}}} . & (6) \end{matrix}

[0061] For the unconstrained case, letting T_Kdenote the cardinality of all possible ordered partitions of K users, we have the recursion formula:

\begin{matrix} T_{K} = \sum_{i = 0}^{K - 1} (\begin{matrix} K \\ i \end{matrix}) T_{i}, T_{0} = 1. & (7) \end{matrix}

Note that {T_k, k=0,1, . . . } can also be determined using the exponential generating function:

\begin{matrix} \sum_{k} \frac{T_{k}}{k!} x^{k} = \frac{1}{2 - \exp (x)} . & (8) \end{matrix}

[0062] 2.3 Error Exponent for SGD

[0063] An optimal SGD that maximizes the error exponent among all SGDs is described below. For practical systems, the choice of maximizing the error exponent is more appropriate than optimizing the outage performance alone. Moreover, this choice also leads to optimality in terms of outage probabilities and is a particularly useful metric for non-symmetric systems with different rates as opposed to other common measures that are independent of the users' rates, such as signal to interference plus noise ratio (SINR).

[0064] For any two disjoint subsets custom character

and

of {1, . . . , K}, let custom character

_r({tilde over (H)}, custom character

) denote the (multi-access) Gaussian random coding error exponent for joint decoding of users in custom character

by assuming users in custom character

to be additive Gaussian interferers. custom character

_r({tilde over (H)}, custom character

) is given by:

\begin{matrix} ɛ_{r} (\tilde{H}, 𝒜, ℬ) = \min_{𝒟 \subseteq 𝒜} \max_{ρ \in [0, 1]} ρ (\log \langle I + \frac{1}{1 + ρ} {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle - \sum_{j \in 𝒟} R_{j}) . & (9) \end{matrix}

[0065] The following lemmas state two important properties of the error exponents that will be subsequently used.

[0066] Lemma 1: For any two disjoint subsets custom character

∈

such that

≢φ,

_r({tilde over (H)}, custom character

)≧0 (10)
with equality if and only if R∉ custom character

({tilde over (H)}, custom character

[0067] The proof of Lemma 1 is as follows. For any subset custom character

⊂

, it can be shown that:

\begin{matrix} \max_{ρ \in [0, 1]} ρ (\log \langle I + \frac{1}{1 + ρ} {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle - \sum_{j \in 𝒟} R_{j}) = 0 \Leftrightarrow \log \langle I + {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle \leq \sum_{j \in 𝒟} R_{j}, \max_{ρ \in [0, 1]} ρ (\log \langle I + \frac{1}{1 + ρ} {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle - \sum_{j \in 𝒟} R_{j}) > 0 \Leftrightarrow \log \langle I + {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle > \sum_{j \in 𝒟} R_{j} & (11) \end{matrix}

Then using (11) with (2) and (9), we can conclude that (10) must hold. We set custom character

_r({tilde over (H)}, custom character

)=∞, when

=φ.

[0068] Lemma 2: For all subsets custom character

⊂

and {tilde over ( custom character

)}⊂

_r({tilde over (H)}, custom character

)≦

_r({tilde over (H)}, {tilde over ( custom character

)}) (12)

[0069] The proof of Lemma 2 is a follows. From (9) it is evident that since {tilde over ( custom character

)}⊂

_r({tilde over (H)}, custom character

)≦

_r({tilde over (H, custom character

)},

). (13)
Moreover, since {tilde over (B)}⊂ custom character

, I+{tilde over (H)}{tilde over (H)}^†≧I+{tilde over (H)}{tilde over (H)}^†, where ≧ denotes positive semi-definite ordering, so that:
{tilde over (H)}^†(I+{tilde over (H)}{tilde over (H)}^†)⁻¹{tilde over (H)}≦{tilde over (H)}^†(I+{tilde over (H)}{tilde over (H)}^†)⁻¹{tilde over (H)}, (14)
which implies that for all ρ≧0:

\begin{matrix} I + \frac{1^{†}}{1 + ρ} {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} ⪯ I + \frac{1}{1 + ρ} {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{\tilde{ℬ}} {\tilde{H}}_{\tilde{ℬ}}^{†})}^{- 1} {\tilde{H}}_{𝒟} . & (15) \end{matrix}

(12) follows directly from (13) and (15).

[0070] For any valid ordered partition ={ custom character

₁, . . . , custom character

_p}∈, let

_r({tilde over (H)}, ) denote the error exponent, i.e.,

\begin{matrix} ɛ_{r} (\tilde{H}, \underline{𝒢}) = \min_{1 \leq k \leq p} {ɛ_{r} (\tilde{H}, 𝒢_{k}, ⋃_{j = k + 1}^{p} 𝒢_{j})} . & (16) \end{matrix}

[0071] Note that using (16) with Lemma 1, we have that custom character

_r({tilde over (H)}, )=0 implies that for some 1≦k≦p, R_k∉ custom character

({tilde over (H)}, custom character

_k, ∪_j=k+1^p custom character

_j) so that a common outage is declared for the ordered partition .

[0072] The following lemma proves the common outage optimality of the ML decoder.

[0073] Lemma 3: The ML decoder minimizes the common outage probability, Pr( custom character

), over all SGDs.

[0074] Lemma 3 can be proven by showing that for any ordered partition ={ custom character

₁, . . . , custom character

_p}:

_r({tilde over (H)}, ∪_j=1^p custom character

_j, φ)=0→

_r({tilde over (H)}, )=0 (17)

[0075] To prove (17) we first show that for any two disjoint subsets custom character

∈

, we have

_r({tilde over (H)}, custom character

∪

, φ)=0→min custom character

_r({tilde over (H)}, custom character

, φ)

=0 (18)
Note that:

\begin{matrix} ɛ_{r} (\tilde{H}, 𝒜, ℬ) = \underset{𝒟 \subseteq 𝒜 ρ \in [0, 1]}{\min \max} ρ (\log \langle I + \frac{1}{1 + ρ} {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle - \sum_{j \in 𝒟} R_{j}), ɛ_{r} (\tilde{H}, 𝒜, ϕ) = \underset{𝒟 \subseteq ℬ ρ \in [0, 1]}{\min \max} ρ (\log \langle I + \frac{1}{1 + ρ} {\tilde{H}}_{𝒟}^{†} {\tilde{H}}_{𝒟} \rangle - \sum_{j \in 𝒟} R_{j}), ɛ_{r} (\tilde{H}, 𝒜 ⋃ ℬ, ϕ) = \underset{𝒟 \subseteq 𝒜 ⋃ ℬ ρ \in [0, 1]}{\min \max} ρ (\log \langle I + \frac{1}{1 + ρ} {\tilde{H}}_{𝒟}^{†} {\tilde{H}}_{𝒟} \rangle - \sum_{j = 𝒟} R_{j}) . & (19) \end{matrix}

[0076] Next for any custom character

⊂

\begin{matrix} \log \langle I + {\tilde{H}}_{𝒟}^{†} {\tilde{H}}_{𝒟} \rangle - \sum_{k ε 𝒟} R_{k} \leq 0 \Rightarrow \log \langle I + {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle - \sum_{k ε𝒟} R_{k} \leq 0, & (20) \end{matrix}

whereas for any custom character

⊂

∪

such that

∩

and

∩

are both non-empty, using the chain-rule for mutual information, we have that:

\begin{matrix} \log \langle I + {\tilde{H}}_{𝒟}^{†} {\tilde{H}}_{𝒟} \rangle = \log \langle I + {\tilde{H}}_{𝒟 ⋂ ℬ}^{†} {\tilde{H}}_{𝒟 ⋂ ℬ} \rangle + \log \langle I + {{\tilde{H}}_{𝒟 ⋂ 𝒜}^{†} (I + {\tilde{H}}_{𝒟 ⋂ ℬ} {\tilde{H}}_{𝒟 ⋂ ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟 ⋂ 𝒜} \rangle, so that {\log \langle I + {\tilde{H}}_{𝒟}^{†} {\tilde{H}}_{𝒟} \rangle - \sum_{k \in 𝒟} R_{k} \leq 0} \Rightarrow {{\log \langle I + {\tilde{H}}_{𝒟 ⋂ ℬ}^{†} {\tilde{H}}_{𝒟 ⋂ ℬ} \rangle - \sum_{k \in 𝒟_{ℬ}} R_{k} \leq 0} ⋃ {\log \langle I + {{\tilde{H}}_{𝒟 ⋂ 𝒜}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟 ⋂ 𝒜} \rangle - \sum_{k \in 𝒟 ⋂ 𝒜} R_{k} \leq 0}} & (21) \end{matrix}

[0077] Using (21) and (20) with (11) and (19), we see that (18) must be true. Thus, we have that:

\begin{matrix} ɛ_{r} (\tilde{H}, ⋃_{j = 1}^{p} 𝒢_{j}, ϕ) = 0 \Rightarrow \min {ɛ_{r} (\tilde{H}, 𝒢_{1}, ⋃_{j = 2}^{p} 𝒢_{j}), ɛ_{r} (\tilde{H}, ⋃_{j = 2}^{p} 𝒢_{j}, ϕ)} = 0 \Rightarrow \min {ɛ_{r} (\tilde{H}, 𝒢_{1}, ⋃_{j = 2}^{p} 𝒢_{j}), ɛ_{r} (\tilde{H}, ⋃_{j = 3}^{p} 𝒢_{j}) ɛ_{r} (\tilde{H}, ⋃_{j = 3}^{p} 𝒢_{j}, ϕ)} = 0 \Rightarrow ⋮ \Rightarrow ɛ_{r} (\tilde{H}, \underline{𝒢}) = 0 & (22) \end{matrix}

[0078] For completeness, letting custom character

and {

_k}_k=1^Kdenote the joint and per-user error events, respectively, we have the following theorem which states that the outage probabilities defined for any SGD (optimal or otherwise) are simultaneously achievable without making any perfect feedback assumption. The latter fact is crucial since for any partition, the outage events were themselves defined (in (4) and (5)) after assuming perfect feedback from preceding groups.

[0079] Theorem 1: For any ε>0, a set of per-user block (codeword) error probabilities, {Pr( custom character

_k)}, satisfying Pr( custom character

_k)≦Pr(

_k)+ε, 1≦k≦K along with a joint error probability Pr(ε)≦Pr( custom character

)+ε are simultaneously achievable for a sufficiently long block-length.

[0080] The proof of Theorem 1 is provided in Appendix 1.

3 Optimal Successive Group Decoder (OSGD)

[0081] An exemplary greedy algorithm which determines the optimal grouping function includes the following steps:

[0082] 1. Initialize: custom character

={1, . . . , K} and _opt=φ.

[0083] 2. Among all ordered partitions of custom character

into two groups {{ custom character

}} with ƒ( custom character

)=1 and

≢φ, select { custom character

*} having the highest value of the metric custom character

_r({tilde over (H)}, custom character

[0084] 3. Update custom character

* and _opt={_opt, custom character

*}.

[0085] 4. If custom character

=φ then stop, else go to Step 2.

[0086] An SGD which employs the ordered partition determined by the above greedy algorithm, will be referred to herein as an optimal SGD (OSGD). Note that when the bounding function ƒ(.) is the maximum group size constraint with μ_max=1, the optimal grouping algorithm reduces to the optimal ordering algorithm. Further, if all user rates are also equal, it can be verified that the exemplary optimal grouping algorithm becomes identical to the optimal V-BLAST ordering. (See P. W. Wolniansky et al., “V-BLAST: An architecture for realizing very high data rates over the rich-scattering wireless channel,” in Proc. of the ISSSE, Pisa, Italy, September 1998; and B. Hassibi, “An efficient square-root algorithm for BLAST,” submitted to IEEE Trans. Signal Processing., January 2000.) Thus the optimality properties that are proven herein for the general case, also bring out several hitherto unrecognized optimalities of the V-BLAST ordering.

[0087] Techniques similar to those used for V-BLAST ordering can result in considerable computational savings in implementing the exemplary greedy algorithm. (See, e.g., B. Hassibi, “An efficient square-root algorithm for BLAST,” submitted to IEEE Trans. Signal Processing., January 2000.) For a given group size constraint μ_max, since at each stage the number of partitions examined is upper bounded by custom character

(K^μ^max) and since there can be at-most K stages, the total number of partitions examined is upper bounded by custom character

(K^μ^max⁺¹)

[0088] 3.1 Optimalities of OSGD

[0089] For the given realization {tilde over (H)}, let _opt={ custom character

₁*, . . . , custom character

_p*,} be the ordered partition yielded by the greedy algorithm. We offer the following theorem.

[0090] Theorem 2: The greedy algorithm determines the ordered partition that maximizes the error exponent among all valid ordered partitions

\begin{matrix} {\underline{𝒢}}_{opt} = \arg \max_{\underline{𝒢} \in \underline{𝒬}} {ɛ_{r} (\tilde{H}, \underline{𝒢})} & (23) \end{matrix}

[0091] The proof of Theorem 2 is given in Appendix 2. Theorem 2 also leads to the following theorem.

[0092] Theorem 3: The OSGD minimizes the common outage probability over all SGDs.

[0093] To prove Theorem 3, suppose for the given realization {tilde over (H)}, custom character

_r({tilde over (H)}, _opt)=0. From Theorem 2, for any valid ordered partition ( custom character

₁, . . . , custom character

_p)∈Q,

_r({tilde over (H)}, )=0. Thus, if the SGD declares a common outage for the ordered partition _opt, it will declare a common outage for every other valid ordered partition.

[0094] A consequence of Theorem 3 is that the unconstrained OSGD for which all ordered partitions are valid yields the minimum common outage probability. According to Lemma 3, however, the ML decoder minimizes the common outage probability. It can thus be concluded that the common outage probabilities of the unconstrained OSGD and the ML decoder are identical and the minimum possible.

[0095] For a given channel {tilde over (H)} and bounding function ƒ(.), a subset U_opt⊂{1, . . . , K} is defined to be the optimal undecodable set, if {0 custom character

⊂U_opt,

≢φ such that ƒ( custom character

)=1,

_r({tilde over (H)}, custom character

, U_opt

)=0, and there exists an ordered partition { custom character

₁, . . . , custom character

_k} satisfying

\begin{matrix} ⋃_{q = 1}^{k} 𝒢_{q} = 𝒰_{opt}^{c} = {1 \dots, K} \ 𝒰_{opt}, and \min_{1 \leq q \leq k} {ɛ_{r} (\tilde{H}, 𝒢_{q}, (⋃_{m = q + 1}^{k} 𝒢_{m}) ⋃ 𝒰_{opt})} > 0 & (24) \end{matrix}

The set U_opt^cwhich is the complement of μ_opt, is referred to as the optimal decodable set.

[0096] Theorem 4: For a given channel {tilde over (H)} and bounding function ƒ(.), the optimal undecodable set is unique.

[0097] The proof of Theorem 4 is as follows. Suppose U and custom character

are two optimal undecodable subsets in custom character

such that U≢ custom character

. Then by definition, there exits an ordered partition { custom character

₁, . . . , custom character

_k} of

^csatisfying

\begin{matrix} \min_{1 \leq q \leq k} {ɛ_{r} (\tilde{H}, 𝒢_{q}, (⋃_{m = q + 1}^{k} 𝒢_{m}) ⋃ 𝒦)} > 0 & (25) \end{matrix}

Let

_ibe the first group for which custom character

_i∩U≢φ. Then from (25) and Lemma 2:
custom character

_r({tilde over (H)}, custom character

_i∩U, [∪_m=i+1^k custom character

_m)∪

]∩U)>0 (26)
Since U custom character

(∪_m=i^k

_m)∪

, (26) is a contradiction because U is an optimal undecodable set.

[0098] Thus from Theorem 4, it can be inferred that for a given {tilde over (H)} and any valid ordered partition ∈, individual outages will at least be declared for all users in the unique optimal undecodable set U_opt. In fact letting U() denote the undecodable set corresponding to the partition , we have that U_opt=∩_∈QU(). Hence the optimal ordered partition is one which ensures that no outage is declared for any user in the (unique) decodable set U_ocp^cand all of them are decoded by the SGD. This insight leads to the following theorem.

[0099] Theorem 5: The OSGD simultaneously minimizes the individual outage probabilities of all users.

[0100] To prove Theorem 5, in the ordered partition returned by the greedy algorithm, _opt={ custom character

₁*, . . . , custom character

_p*}, let

_k+1* be the first group in outage, i.e., the first group with custom character

_r({tilde over (H)}, custom character

_k+1*, ∪_m=k+2^p* custom character

_m*)=0. From the construction of the greedy algorithm, it can be verified that for all non-empty subsets custom character

⊂∪_m=k+1^p* custom character

_m*, with ƒ( custom character

)=1,

_r({tilde over (H)}, custom character

, ∪_m=k+1^p* custom character

_m*

)=0, (27)
which implies that ∪_m=k+1^p* custom character

_m* is the unique optimal undecodable set U_opt. Thus in the partition _optan outage is declared for user k (or equivalently the event O_kis true) if and only if k∈U_opt. Moreover, since k∈U_optimplies that custom character

_kis true for each partition in , we can conclude that the OSGD simultaneously minimizes the individual outage probabilities of all users over all valid SGDs.

[0101] Note that if there is no group in outage, the optimal undecodable set is the empty set. Thus the greedy algorithm always partitions the set of users into a decodable set U_opt^c∪_q=1^k custom character

_q* and and an optimal undecodable set U_opt=∪_q=k+1^p* custom character

_q*, where _opt={ custom character

₁*, . . . , custom character

_p*.} for some 1≦k≦p* . In fact, if the set U_optwas known beforehand and the greedy algorithm were run on U_opt^cby treating users in μ_optas Gaussian interferers, the resulting ordered partition would be { custom character

₁*, . . . , custom character

_k*}. To see this let {{tilde over ( custom character

)}₁, . . . , {tilde over ( custom character

)}_q} be the ordered partition of U_opt^cresulting from the latter greedy algorithm. Recall that since U_optis the optimal undecodable set,

\begin{matrix} \max_{\underset{f (𝒢) = 1, 𝒢 ⋂ 𝒰_{opt} \neq ϕ}{𝒢 \subseteq {1, \dots, K}}} ɛ_{r} (\tilde{H}, 𝒢, 𝒢^{c}) = 0, & (28) \end{matrix}

which using the fact that

\begin{matrix} \max_{\underset{f (𝒢) = 1}{𝒢 \subseteq {1, \dots, K}}} ɛ_{r} (\tilde{H}, 𝒢, 𝒢^{c}) = \max {\max_{\underset{f (𝒢) = 1, 𝒢 ⋂ 𝒰_{opt} \neq ϕ}{𝒢 \subseteq {1, \dots, K}}} ɛ_{r} (\tilde{H}, 𝒢, 𝒢^{c}), \max_{\underset{f (𝒢) = 1}{𝒢 \subseteq 𝒰_{opt}^{c}}} ɛ_{r} (\tilde{H}, 𝒢, 𝒢^{c})} & (29) \end{matrix}

leads to

\begin{matrix} {\tilde{𝒢}}_{1} = \arg \max_{\underset{f (𝒢) = 1}{𝒢 \subseteq 𝒰_{opt}^{c}}} ɛ_{r} (\tilde{H}, 𝒢, 𝒢^{c}) = 𝒢_{1}^{*} = \arg \max_{\underset{f (𝒢) = 1}{𝒢 \subseteq [1, \dots, K}}} ɛ_{r} (\tilde{H}, 𝒢, 𝒢^{c}) & (30) \end{matrix}

Similarly, it follows that q=k and {tilde over ( custom character

)}_j=

_j*, 2≦j≦q=k. This fact along with Theorem 2 results in the following theorem.

[0102] Theorem 6: The greedy algorithm determines the ordered partition that also maximizes the error exponent for the decodable set U_opt^cover all its valid ordered partitions.

[0103] 3.2 OSGD Achieves Minimum Outage Probabilities

[0104] We now examine if a better (i.e., smaller) set of achievable outage probabilities than those derived for the OSGD, can be obtained under the specified bounding function. We first consider the unconstrained OSGD and then focus on the constrained case.

[0105] An important property of the unique optimal undecodable set U_optthat will be used, is stated in the following lemma.

[0106] Lemma 4: For all valid non-empty subsets custom character

⊂U_opt

\begin{matrix} \log \langle I + {{\tilde{H}}_{𝒢}^{†} (I + {\tilde{H}}_{𝒰_{opt} \ 𝒢} {\tilde{H}}_{𝒰_{opt} \ 𝒢}^{†})}^{- 1} {\tilde{H}}_{𝒢} \rangle < \sum_{k \in 𝒢} R_{k} & (31) \end{matrix}

[0107] To prove Lemma 4, consider any valid subset custom character

⊂U_opt. Since U_optis optimally undecodable, ∃ custom character

⊂

such that

\log \langle I + {{\tilde{H}}_{𝒜}^{†} (I + {\tilde{H}}_{𝒰_{opt} \ 𝒢} {\tilde{H}}_{𝒰_{opt} \ 𝒢}^{†})}^{- 1} {\tilde{H}}_{𝒜} \rangle < \sum_{k \in 𝒜} R_{k} .

This follows from the fact that R∉ custom character

({tilde over (H)}, custom character

, U_opt

). Moreover since custom character

⊂U_opt, R∉ custom character

({tilde over (H)}, custom character

, U_opt[

]) so that ∃ custom character

such that

\log \langle I + {{\tilde{H}}_{ℬ}^{†} (I + {\tilde{H}}_{𝒰_{opt} \ 𝒢} {\tilde{H}}_{𝒰_{opt} \ 𝒢}^{†} + {\tilde{H}}_{𝒜} {\tilde{H}}_{𝒜}^{†})}^{- 1} {\tilde{H}}_{ℬ} \rangle < \sum_{k \in ℬ} R_{k} .

Combining these two observations yields the following:

\begin{matrix} \log \langle I + {{\tilde{H}}_{𝒜}^{†} (I + {\tilde{H}}_{𝒰_{opt} \ 𝒢} {\tilde{H}}_{𝒰_{opt} \ 𝒢}^{†})}^{- 1} {\tilde{H}}_{𝒜} \rangle + \log \langle I + {{\tilde{H}}_{ℬ}^{†} (I + {\tilde{H}}_{𝒰_{opt} \ 𝒢} {\tilde{H}}_{𝒰_{opt} \ 𝒢}^{†} + {\tilde{H}}_{𝒜} {\tilde{H}}_{𝒜}^{†})}^{- 1} {\tilde{H}}_{ℬ} \rangle \underset{(a)}{=} \log \langle I + {{\tilde{H}}_{𝒜 ⋃ ℬ}^{†} (I + {\tilde{H}}_{𝒰_{opt} \ 𝒢} {\tilde{H}}_{𝒰_{opt} \ 𝒢}^{†})}^{- 1} {\tilde{H}}_{𝒜 ⋃ ℬ} \rangle < \sum_{k \in 𝒜 ⋃ ℬ} R_{k} & (32) \end{matrix}

where (a) follows from the chain rule for mutual information and the fact that custom character

and

are disjoint subsets of custom character

. Continuing the argument with {tilde over ( custom character

)}=

∪

, we see that since the valid subset custom character

{tilde over ( custom character

)}

U_opt, we must have that ∃{tilde over ( custom character

)}

{tilde over ( custom character

)} such that

\log \langle I + {{\tilde{H}}_{\tilde{ℬ}}^{†} (I + {\tilde{H}}_{𝒰_{opt} \ 𝒢} {\tilde{H}}_{𝒰_{opt} \ 𝒢}^{†} + {\tilde{H}}_{\tilde{𝒜}} {\tilde{H}}_{\tilde{𝒜}}^{†})}^{- 1} {\tilde{H}}_{\tilde{ℬ}} \rangle < \sum_{k \in \tilde{ℬ}} R_{k} .

Combining this with (32) and proceeding so on, the lemma can be proven.

[0108] Let us first consider the unconstrained OSGD (where all ordered partitions are valid). The common outage event for this decoder is identical to that defined here for a ML decoder. Given this event, a joint error event (where at least one user is decoded in error) is very likely, so the common outage event definition is well justified and the resulting common outage probability, Pr( custom character

), is hard to improve upon. Next, let us look at the individual outage probabilities. Let U_opt, denote the unique undecodable set for the unconstrained OSGD. Invoking Lemma 4 we have that

\log \langle I + {\tilde{H}}_{𝒰_{opt}}^{†} {\tilde{H}}_{𝒰_{opt}} \rangle < \sum_{k \in 𝒰_{opt}} R_{k} .

From the discussion in R. G. Gallager, “A perspective on multiaccess channels,” IEEE Trans. Inform. Theory, vol. 31, pp. 124-142, March 1985, we can conclude that if we attempted to decode all users in U_opt, jointly (after users in U_opt^chave been perfectly canceled) a type-U_opterror—where an error occurs for each user in U_opt—is very likely. Hence, declaring individual outages for this set of users is well justified and obtaining a simultaneously achievable set of individual outage probabilities lower than those derived here, seems intractable.

[0109] Next, consider the constrained OSGD and again since the common outage probability is well motivated, we focus on the individual outage probabilities. Suppose ( custom character

₁, . . . , custom character

_q) is some valid ordered partition of the unique undecodable set U_optfor a given channel realization and the preceding users in U_opt^chave been perfectly cancelled. If we attempt to decode custom character

₁after treating the remaining users as Gaussian interferers, from Lemma 4 we can conclude that with high probability, an error occurs for each user in custom character

₁. We could still proceed to decode custom character

₂without subtracting custom character

₁and treating { custom character

₁,

₃, . . . , custom character

_q} as Gaussian interferers. Lemma 4, however, indicates that errors would be very likely for all users in custom character

₂. Thus, there is little chance of decoding even one user, in the first group decoded, correctly. Under this fact and in the absence of a precise modeling of feedback errors (which seems intractable), declaring individual outages for all users in U_optis well justified and the resulting individual outage probabilities obtained with the exemplary OSGD are the best achievable.

3.3 Adaptive SGD

[0110] Two exemplary adaptive greedy grouping algorithms will now be described where the bounding function is channel dependent. For convenience, it is assumed that the bounding function corresponds to the maximum group size constraint. Let U_opt({tilde over (H)},μ_max) denote the optimal undecodable set yielded by the greedy algorithm for channel realization {tilde over (H)} and maximum group size μ_max. Our objective is to achieve the same outage probabilities as those of the OSGD with μ_max=u (for some specified u ) but with the smallest maximum group size possible. To do so, we leverage the uniqueness of the optimal undecodable set for a given group size. Note that for each realization the minimum group size needed for outage optimality is
μ*=min{k:k≦u and U_opt({tilde over (H)}, k)=U_opt({tilde over (H)}, u)} (33)

[0111] In either of the two adaptive algorithms discussed below, a valid ordered partition having at least one group of size μ* in (33) is chosen.

[0112] In the first exemplary adaptive grouping algorithm, the exemplary greedy algorithm described above is initiated with group size one. Every time an outage is encountered, processing starts anew, i.e., processing of all users starts again after incrementing the current group size by 1. This approach yields the optimal ordered partition corresponding to group size μ* without having to pre-compute μ*. It thus allows achieving the minimum possible outage probabilities and the maximum error exponent among all ordered partitions valid for 1≦μ_max≦μ*. There is, however, a potential loss in the error exponent of the decodable set compared to that yielded by the optimal ordered partition with μ_max=u, but a substantial reduction in decoding complexity makes up for it.

[0113] The second exemplary adaptive grouping algorithm also retains the outage optimality of the previously described greedy algorithm. At each stage, the algorithm picks the smallest group size from the set {1, . . . , u} that can avoid outage. In other words, at each step starting from group size 1, the algorithm determines if the best group (in terms of error exponent) of the current group size can avoid outage. If yes, that group is selected and the algorithm proceeds to the remaining users and resets the initial group size to one. Otherwise, the current group size is incremented by one and the process is repeated. The computational cost of determining the ordered partition for this adaptive grouping algorithm is in general less than that of the first adaptive grouping algorithm but its error exponent is also poorer.

3.4 Alternative Metrics for the Greedy Algorithm

[0114] We now present two other metrics that can be used instead of the error exponent metric in the greedy algorithm to obtain a valid ordered partition for each channel realization. Both metrics are simpler to compute and as shown below, the SGDs employing the resulting partitions also minimize the common as well as the individual outage probabilities. However, these metrics do not provide an additional optimality yielded by the error exponent metric.

[0115] For any two disjoint subsets custom character

and

of {1, . . . , K} and a given channel realization {tilde over (H)}. we define

\begin{matrix} 𝒞_{1} (\tilde{H}, 𝒜, ℬ) \overset{Δ}{=} \min_{𝒟 \subseteq 𝒜} {{(\log \langle I + {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle - \sum_{j \in 𝒟} R_{j})}^{+}} and & (34) \\ 𝒞_{2} (\tilde{H}, 𝒜, ℬ) \overset{Δ}{=} \min_{𝒟 \subseteq 𝒜} {{[\log \langle I + {{\tilde{H}}_{𝒟}^{†} (I + {\tilde{H}}_{ℬ} {\tilde{H}}_{ℬ}^{†})}^{- 1} {\tilde{H}}_{𝒟} \rangle / (\sum_{j \in 𝒟} R_{j})]}^{+}} & (35) \end{matrix}

respectively, where (x)⁺ custom character

max {0,x} and [x]⁺ custom character

min {1,x}. Note that
custom character

_r({tilde over (H)}, custom character

)=0

₁({tilde over (H)}, custom character

)=0

₂({tilde over (H)}, custom character

)=1 (36)

[0116] Next, analogous to (16), for any valid ordered partition =( custom character

₁, . . . , custom character

_p)∈, we define:

\begin{matrix} 𝒞_{1} (\tilde{H}, \underline{𝒢}) \overset{Δ}{=} \min_{1 \leq k \leq p} {𝒞_{1} (\tilde{H}, 𝒢_{k}, ⋃_{j = k + 1}^{p} 𝒢_{j})}, and & (37) \\ 𝒞_{2} (\tilde{H}, \underline{𝒢}) \overset{Δ}{=} \min_{1 \leq k \leq p} {𝒞_{2} (\tilde{H}, 𝒢_{k}, ⋃_{j = k + 1}^{p} 𝒢_{j})} . & (38) \end{matrix}

[0117] Note that a common outage is declared for the ordered partition if and only if custom character

₁({tilde over (H)}, )=0 and if and only if custom character

₂({tilde over (H)}, )=1.

[0118] Using the arguments made to prove Theorem 2, it follows that employing custom character

₁({tilde over (H)}, custom character

) and

₂({tilde over (H)}, custom character

) as the cost metrics in the greedy algorithm, respectively, will yield arg

\max_{\underline{𝒢} \in \underline{𝒬}} {𝒞_{1} (\tilde{H}, \underline{𝒢})} and \arg \max_{\underline{𝒢} \in \underline{𝒬}} {𝒞_{2} (\tilde{H}, \underline{𝒢})}

as the resulting partitions, respectively. Moreover, it can be verified that the (unique) undecodable sets obtained with these metrics are identical and coincide with the set U_optobtained with the error exponent metric. As a consequence, SGDs employing the partitions yielded by these metrics simultaneously minimize the common as well as the individual outage probabilities. Thus, it is clear that multiple partitioning rules and their corresponding SGDs can be outage optimal. In fact, for any partitioning rule to be outage optimal, for all channel realizations except a set of measure zero, its undecodable set must coincide with the set U_optobtained with the error exponent metric. The advantage of using the error-exponent metric is that the resulting OSGD also simultaneously minimizes the achievable joint and per-user error probabilities, over all the outage optimal SGDs (cf. Theorem 1). It can thus be expected that with well-designed multi-user codes, the OSGD yields error probabilities that are close to their corresponding outage probabilities even for moderate block lengths.

[0119] 3.5 Simulation Results

[0120] For convenience, in the following simulations we assume i.i.d. Rayleigh fading and that all users employ a single transmit antenna (m_k=1, {0 k) and transmit at the same rate with identical average powers. In FIG. 3 we consider a symmetric MAC with six users (K=6 ) where the base-station is equipped with six receive antennas (N=6 ). The first set of curves, where each user transmits with rate R=2 bits per channel use, contains the common outage probabilities of the ML decoder and two OSGDs with μ_max=1 and μ_max=2, respectively. Notice that even the SGD with μ_max=1 yields a near-optimal outage probability in spite of a significantly reduced decoding complexity. The second set of curves shown in FIG. 3 contains the common outage curves for R=4.

[0121] FIG. 3 indicates that the maximum group size parameter μ_maxcan be chosen to balance the conflicting requirements of good performance and low decoding complexity. To demonstrate the complexity reduction provided by the adaptive SGD, FIG. 4 shows a bar plot in which 50,000 channel realizations are considered for each of the three SNR values. As in FIG. 3, a symmetric MAC with six users (K=6) and a base-station with six receive antennas (N=6) is assumed. At each SNR, the adaptive SGD (with u=3 in (33)) yields the same outage performance as the OSGD with μ_max=3 and R=4 but the average group sizes needed are just 1.4570, 1.3329, and 1.0998, respectively, for the three SNR values. Moreover, it is seen that a substantial fraction of channels require just μ*=1 in (33) and rarely is μ*=3 needed.

[0122] In FIG. 5 we consider a symmetric MAC with N=K=4, R=1 and plot the frame error probabilities (FEPs) obtained with particular outer codes. Each user employs a (2048,1024) rate-½ IRA LDPC outer code with QPSK modulation. (See, e.g., G. Yue et al., “Optimization of Irregular Repeat Accumulate codes for MIMO systems with iterative receivers,” IEEE Trans. Wireless Commun., vol. 4, no. 6, pp. 2843-2855, November 2005.) The decoding is done using the OSGD with μ_max=2 and μ_max=1, respectively. Also plotted are their respective common outage probabilities along with that of the ML decoder. For each channel realization, the users within a group were decoded using joint detection and iterative decoding (6 iterations between decoders and detector were allowed). For larger group sizes, sphere decoder based strategies can be incorporated to reduce the complexity of the MIMO demodulation stage. (See B. M. Hochwald et al., “Achieving near-capacity on a multiple-antenna channel,” IEEE Trans. Commun., vol. 51, no. 3, pp. 389-399, March 2003.) As promised by the outage probability results, the optimal grouping offers considerable gains. At a FEP of 10⁻³the SGD with optimal grouping and μ_max=1 is only about 1 dB away from the best achievable FEP limit, i.e., the common outage curve of the ML decoder. Significantly, the optimal grouping is determined once at the start of each frame and only adds a small overhead since the cost of determining the optimal grouping is negligible in comparison to the complexity of decoding outer codes.

[0123] The gains due to a larger group size are more pronounced for asymmetric multi-user systems with fewer receive antennas than the number of users and/or systems operating at high (sum) rates. To illustrate this point, in FIG. 6 we consider a MAC with N=3 receive antennas and K=4 users, each transmitting at rate R=2 bits per channel use. Each user employs a 16-QAM modulation and rate-½ IRA LDPC outer code. FIG. 6 shows the FEPs achieved by the OSGDs with μ_max=2 and μ_max=1, respectively. Also plotted are the FEPs achieved by SGDs with fixed partitions given by {{1,2,}, {3, 4} } and {{1}, {2}, {3}, {4}}, respectively. Note that both the SGD with fixed groups of size 1 and the corresponding OSGD have error floors, but the OSGD (with optimal ordering in this case) provides a very large coding gain. On the other hand, the OSGD with μ_max=2 yields a gain of about 13 dB over its fixed-order counterpart with no increase in decoding complexity.

[0124] In FIG. 7, we consider a MAC with N=K=4. Each user transmits at rate R=3 bits using 16-QAM modulation and

rate - \frac{3}{4}

IRA LDPC outer code. FIG. 7 plots the FEPs of the OSGDs with μ_max=2 and μ_max=1, respectively. Also plotted are the FEPs of the SGDs with fixed partitions, with the partitions being identical to those used in the previous example. Note that a larger group size provides a considerable gain and at a FEP of 10⁻³, for example, the OSGD with μ_max=2 yields a gain of about 7 dB over its counterpart with μ_max=1.

[0125] Recall that in the present framework, the outage-optimal OSGDs are derived assuming joint-ML decoding of users within a group. In fact in the examples presented above, near-optimal point) decoding of users within a group was achieved by iterative joint MIMO detection and single user channel decoding, i.e., turbo processing. However, as will be seen in the following example, the optimal grouping rule is robust in the sense that it results in performance improvements even when no iterations are allowed between the decoders and the detector, while decoding users within a group. This aspect makes the OSGD particularly appealing for practical systems with strict complexity and delay constraints.

[0126] FIG. 8 considers the system in the previous example (illustrated in FIG. 7) and plots the corresponding FEPs when no iteration is allowed. Also plotted is the FEP yielded by the soft interference canceller (see X. Wang et al., “Iterative (Turbo) soft interference cancellation and decoding for coded CDMA,” IEEE Trans. Commun., vol. 46, no. 7, pp. 1046-1061, July 1999), which, however, was allowed six decoder-detector iterations. It is seen that at a FEP of 10⁻³, the OSGD with μ_max=2 yields a gain of more than 6 dB over its counterpart with μ_max=1 as well as the soft interference canceller.

4 Asymptotic Analysis

[0127] In this section, several relevant performance metrics associated with the OSGD in the high SNR regime as well as in the large array regime are considered. For convenience, a maximum group size constraint is assumed. In particular, for any given vector of non-negative weights or priorities θ=[θ₁, . . . , θ_K]^T, and assuming, without loss of generality, that Σ_k=1^Kθ_k=1, the weighted sum common outage capacity is given by:

\begin{matrix} 𝒞 (θ, ɛ) = \sup {\sum_{k = 1}^{K} θ_{k} R_{k} : \Pr (O) \leq ɛ}, ɛε (0, 1), & (39) \end{matrix}

and the weighted sum individual outage capacity, given by:

\begin{matrix} 𝒞 ℐ (θ, ɛ) = \sup {\sum_{k = 1}^{K} θ_{k} R_{k} : \Pr (O_{k}) \leq ɛ_{k}, 1 \leq k \leq K}, ɛ = {[ɛ_{1}, \dots, ɛ_{K}]}^{T} {ε (0, 1)}^{K} . & (40) \end{matrix}

[0128] Other metrics considered here are the symmetric common outage capacity, which is the maximum identical rate that can be simultaneously achieved for all users subject to a constraint on the common outage probability, i.e.,
custom character

^sym(ε)=sup{R:Pr( custom character

)≦ε} (41)
and the individual symmetric outage capacity
custom character

^sym(ε)=sup {R:Pr( custom character

_k)≦ε, 1≦k≦K} (42)

[0129] The individual and common outage formulations also allow us to define the corresponding throughputs. For each outage formulation we consider two notions of throughput which are mathematically identical. The first notion of throughput is for a delay-sensitive system where the receiver simply drops all packets of users in outage. The resulting common-outage throughput is then given by [1−Pr( custom character

)]Σ_k=1^KR_k, whereas the individual-outage throughput is given by Σ_k=1^KR_k[1−Pr( custom character

_k)]. Next, consider a reliability-constrained system where the receiver keeps sending retransmission requests to each user in outage until it enters the non-outage state, after which the user starts transmitting a new packet. The underlying idea is that a user cannot remain in outage (i.e., experiencing deep fade) forever.

[0130] Here we focus on one such simple system where each transmitted packet experiences independent fading and due to complexity constraints the receiver uses only the current (most-recent) received signal matrix to decode all the users. For this system, we can readily extend the analysis for the MIMO point-to-point case (as described in N. Ahmed et al., “Throughput measures for delay-constrained communication systems in fading channels,” Proc. Allerton Conf on Comm. Control, and Comput., October 2003) and show that the throughput obtained for user k is equal to R_k/ custom character

{S_k} where custom character

{S_k} is the average service time for that user. Thus, the system throughput is equal to Σ_k=1^KR_k/ custom character

{S_k}. In the common outage formulation, custom character

{S_k}=[1−Pr( custom character

)]⁻¹, 1≦k≦K and in the individual outage formulation, custom character

{S_k}=[1−Pr( custom character

_k)]⁻¹, 1≦k≦K. Hence mathematically for either outage formulation, the two notions of throughput are identical. Thus, in the common outage formulation, the weighted throughput maximization problem reads

\begin{matrix} 𝒯 (θ) = \sup {[1 - \Pr (O)] \sum_{k = 1}^{K} θ_{k} R_{k}}, & (43) \end{matrix}

whereas in the individual outage case it becomes

\begin{matrix} 𝒯 ℐ (θ) = \sup {\sum_{k = 1}^{K} θ_{k} R_{k} [1 - \Pr (O_{k})]} . & (44) \end{matrix}

[0131] 4.1 High SNR Asymptotes

[0132] We assume that the channel matrix of user k can be modeled as H_k= custom character

_kA_kH_k^wB_kwhere H_k^wis an N×m_kmatrix with i.i.d. custom character

(0,1) elements and A_k, B_krepresent the transmit and receive correlation matrices of user k, respectively, as described in W. Rhee et al., “On the capacity of multiuser wireless channels with multiple antennas,” IEEE Trans. Inform. Theory, vol. 49, no. 10, pp. 2580-2595, October 2003. { custom character

_k} represent the set of independent shadow-fading coefficients which capture the effect of large-scale or macroscopic fading and are log-normal distributed. We take {Q_k=ρ{tilde over (Q)}_k}_k=1^K, where {{tilde over (Q)}_k} are positive semi-definite and fixed arbitrarily and define {tilde over (H)} custom character

=[H_k{tilde over (Q)}_k^1/2]_k∈and let ρ→∞. Our objective here is to determine asymptotically tight affine approximations for the capacities (39)-(42). These approximations reveal the correct scaling of the corresponding capacities with SNR, are simpler to compute than their respective true capacities, and also capture the effect of relevant channel parameters such as correlations and the like. The scaling factors can be computed for the two throughputs (43) and (44). The following two lemmas (which are proved in Appendix 3) are used for this.

[0133] Lemma 5: For each custom character

∈

, we have rank({tilde over (H)})=βwith probability one, for some positive integer β.

Letting b: custom character

→

₊, be a non-negative integer valued set function such that b( custom character

)=β, we have the following result.

[0134] Lemma 6: The region

\begin{matrix} ℛ (b) \overset{Δ}{=} {r \in ℝ_{+}^{K} : \sum_{k \in 𝒥} r_{k} \leq b (𝒥), \forall 𝒥 \in 𝒮} & (45) \end{matrix}

is a polymatroid with rankfunction b(.)

[0135] Thus a solution to the problem

\begin{matrix} \max_{r \in ℛ (b)} {θ^{T} r}, & (46) \end{matrix}

lies on a vertex (or corner point) and can be determined as
r_ψ(1)*=b(ψ(1)),
r_ψ(k)*=b({ψ(j)}_j=1^k)−b({ψ(j)}_j=1^k-1),2≦k≦K, (47)
where ψ(.) is any permutation such that θ_ψ(1)≧θ_ψ(2). . . ≧θ_ψ(K). (See D. N. C. Tse et al. “Multiaccess fading channels-part i: Polymatroidal structure, optimal resource allocation and throughput capacities,” IEEE Trans. Inform. Theory, vol. 44, no. 2, pp. 2696-2815, November 1998.)

[0136] We first consider the weighted sum common outage capacity (39) and define g({tilde over (H)}{tilde over (H)}⁵⁵⁴, b( custom character

)) as the product of the b( custom character

) largest eigenvalues of {tilde over (H)}{tilde over (H)}^†. Next, consider an ordered partition ( custom character

₁, . . . , custom character

_p). For each custom character

_k, let P_k^⊥denote the orthogonal projection whose range is the orthogonal complement of range of [{tilde over (H)}_j]_j=k+1^p. Then as a consequence of Lemma 5 we have that the rank of P_k^⊥{tilde over (H)}_kequals some constant with probability one. Let h( custom character

_k,

_k) denote this rank and note that h( custom character

_k,

_k)=b(

_k∪

_k)−b(

_k). The following theorem provides an asymptotically tight affine approximation to the weighted sum common outage capacity. The proof is given in Appendix 4.

[0137] Theorem 7: An asymptotically tight affine approximation to custom character

(θ, ε) given in (39), denoted by {tilde over ( custom character

)}(θ, ε), is of the form

\begin{matrix} \tilde{𝒞} (θ, ɛ) = \log (ρ) \sum_{k = 1}^{K} θ_{k} r_{k}^{*} + O (1) & (48) \end{matrix}

and satisfies

\begin{matrix} \lim_{ρ \to \infty} (𝒞 (θ, ɛ) - \tilde{𝒞} (θ, ɛ)) = 0. & (49) \end{matrix}

[0138] For the ML decoder, the custom character

(1) term in (48) is of the form log(γ_∞^ML(θ, ε)),
where

\begin{matrix} γ_{\infty}^{ML} (θ, ɛ) \overset{Δ}{=} \sup {\prod_{k = 1}^{K} y_{k}^{^{θ} k} : \Pr (⋃_{b (𝒥) = \sum_{k \in 𝒥}^{𝒥 \in 𝒮} r_{k}^{*}} {g ({\tilde{H}}_{𝒥} {\tilde{H}}_{𝒥}^{†}, b (𝒥)) < \prod_{k \in 𝒥} y_{k}}) \leq ɛ}, & (50) \end{matrix}

and for the OSGD the custom character

(1) term is of the form log(γ_∞^OSGD(θ, ε)) where:

\begin{matrix} γ_{\infty}^{OSGD} (θ, ɛ) \overset{Δ}{=} \sup {\prod_{k = 1}^{K} y_{k}^{θ_{k}} : \Pr (⋂_{\underline{𝒢} \in \underline{𝒬}} {⋃_{k = 1}^{p} {⋃_{\underset{h (𝒥, {\overline{𝒢}}_{k}) \leq \sum_{k \in 𝒥} r_{k}^{*}}{𝒥 \subseteq 𝒢_{k}}} {g ({\tilde{H}}_{𝒥}^{†} P_{𝒢_{k}}^{⊥} {\tilde{H}}_{𝒥}, \sum_{k \in 𝒥} r_{k}^{*}) < \prod_{k \in 𝒥} y_{k}}}}) \leq ɛ}, & (51) \end{matrix}

[0139] Note that there can be multiple solutions {r_k*} to (46) all yielding the same tight affine approximation. For instance, when all of the weights {θ_i} are equal, i.e., all users have equal priorities, all K! corner points of the polymatroid custom character

(b) are solutions. In this case, an interesting effect referred to as the antenna pooling effect is discussed in the following lemma.

[0140] Lemma 7: Consider the ML decoder and let θ_i=1, 1≦i≦K. Then if ∃r∈ custom character

(b) such that

\begin{matrix} \sum_{j \in 𝒥} r_{j} < b (𝒥), \forall 𝒥 \in 𝒮 and \langle 𝒥 \rangle < K, \sum_{j = 1}^{K} r_{j} = b ({1, \dots, K}), & (52) \end{matrix}

then the asymptotically tight affine approximation to the sum capacity simplifies to
custom character

^ML(1, ε)=b({1, . . . ,K})log(ρ)+log(γ_∞^ML(1, ε)), (53)
γ_∞^ML(1, ε)=sup{z:Pr(g({tilde over (HH)}^†, b({1, . . . , K}))<z)≦ε}. (54)
Thus at high SNR, in terms of sum capacity, the multi-user system behaves like its corresponding MIMO point-to-point system with N receive and Σ_k=1^Km_ktransmit antennas.

[0141] The proof of Lemma 7 is as follows. For this case with equal user priorities, note that

\begin{matrix} 𝒞^{ML} (1, ɛ) = \sup {\sum_{k = 1}^{K} R_{k} : \Pr (⋃_{𝒥 \in 𝒮} {\log \langle I + ρ {\tilde{H}}_{𝒥} {\tilde{H}}_{𝒥}^{†} \rangle < \sum_{k \in 𝒥} R_{k}}) \leq ɛ} . & (55) \end{matrix}

Suppose r∈ custom character

(b) satisfies (52). Setting R_k=r_klog(ρ)+log(y_k) in (55) and proceeding along the lines of Appendix 4, we see that since

\begin{matrix} \lim_{ρ \to \infty} \Pr (⋃_{𝒥 \in 𝒮} {\log \langle I + ρ {\tilde{H}}_{𝒥} {\tilde{H}}_{𝒥}^{†} \rangle < \sum_{k \in 𝒥} [r_{k} \log (ρ) + \log (y_{k})]}) = \Pr (g (\tilde{H} {\tilde{H}}^{†}, b ({1, \dots, K})) < \prod_{k = 1}^{K} y_{k}) & (56) \end{matrix}

the asymptotically tight approximation to custom character

^ML(1, ε) is given by (53). Next, note that the outage capacity for the corresponding point-to-point system with coding across transmit antennas, is given by
custom character

^ML-pt(ε)=sup{R:Pr(log|I+p{tilde over (HH)}^†|<R)≦R)≦ε}. (57)

[0142] Setting R=b({1, . . . , K})log(ρ)+log(y) in (57), it can be shown that the asymptotically tight approximation to custom character

^ML-Pt(ε) is also given by (53). As a consequence

\begin{matrix} \lim_{ρ \to \infty} (𝒞^{ML - pt} (ɛ) - 𝒞^{ML} (1, ɛ)) = 0, & (58) \end{matrix}

so that the multi-user capacity behaves like its corresponding MIMO point-to-point counterpart at high SNR.

[0143] The following theorem provides asymptotically tight affine approximations to the symmetric common outage capacity (41).

[0144] Theorem 8: For the ML decoder an asymptotically tight affine approximation to custom character

^sym(ε) in (41) is given by

\begin{matrix} {\tilde{𝒞}}^{ML - sym} (ɛ) = r_{ML}^{*} \log (ρ) + \log (γ_{\infty}^{ML - sym} (ɛ)), with & (59) \\ r_{ML}^{*} = \min_{𝒥 \in 𝒮} {b (𝒥) / \langle 𝒥 \rangle} and & (60) \\ γ_{\infty}^{ML - sym} (ɛ) = \sup {γ : \Pr (⋃_{\underset{b (𝒥) = \langle 𝒥 \rangle r_{ML}^{*}}{𝒥 \in 𝒮}} {g ({\tilde{H}}_{𝒥} {\tilde{H}}_{𝒥}^{†}, b (𝒥)) < y^{\langle 𝒥 \rangle}}) \leq ɛ} . & (61) \end{matrix}

[0145] For the OSGD an asymptotically tight affine approximation to custom character

^sym(ε) is given by

\begin{matrix} {\tilde{𝒞}}^{OSGD - sym} (ɛ) = r_{OSGD}^{*} \log (ρ) + \log (γ_{\infty}^{OSGD - sym} (ɛ)), with & (62) \\ r_{OSGD}^{*} = \max_{(𝒢_{1}, \dots, 𝒢_{p}) \in \underline{𝒬}} {\min_{1 \leq k \leq p} {\min_{𝒥 \subseteq 𝒢_{k}} {h (𝒥, {\overline{𝒢}}_{k}) / \langle 𝒥 \rangle}}} and & (63) \\ γ_{\infty}^{OSGD - sym} (ɛ) = \sup {γ : \Pr (⋂_{\underline{𝒢} \in \underline{𝒬}} {⋃_{k = 1}^{p} {⋃_{\underset{h (𝒥, {\overline{𝒢}}_{k}) \leq \langle 𝒥 \rangle r_{OSGD}^{*}}{𝒥 \subseteq 𝒢_{k}}} {g ({\tilde{H}}_{𝒥}^{†} P_{𝒢_{k}}^{⊥} {\tilde{H}}_{𝒥}, \langle 𝒥 \rangle r_{OSGD}^{*}) < y^{\langle 𝒥 \rangle}}}}) \leq ɛ} & (64) \end{matrix}

[0146] To prove Theorem 8, we first consider the ML decoder for which
custom character

^ML-sym(ε)=sup custom character

R:Pr∪_≢φlog|I+ρ{tilde over (H)}{tilde over (H)}^†|<|R≦ε. (65)
Setting R=rlog(ρ)+log(y) and invoking (108) in Appendix 4, we see that the optimal scaling equals

r_{ML}^{*} \overset{Δ}{=} \min_{𝒥 \in 𝒮} [b (𝒥) / \langle 𝒥 \rangle} .

Using this and proceeding as before we can obtain an asymptotically tight approximation given in (61). To obtain an asymptotically tight approximation on the symmetric common outage capacity of the OSGD, we first need to determine the optimal scaling. Unlike the weighted common outage capacity case, here the scaling factor is in general less than that of the ML decoder. For any ordered partition ( custom character

₁, . . . , custom character

_p) the maximum symmetric scaling can be determined as follows. Setting R_k=rlog(ρ)+log(y), we see from (112) in Appendix 4 that for this ordered partition the common outage event in the limit ρ→∞ is identical to the event

\begin{matrix} ⋃_{k = 1}^{p} {⋃_{\underset{h (𝒥, {\overline{𝒢}}_{k}) \leq \langle 𝒥 \rangle r}{𝒥 \subseteq 𝒢_{k}}} {g ({\tilde{H}}_{𝒥}^{†} P_{𝒢_{k}}^{⊥} {\tilde{H}}_{𝒥}, \langle 𝒥 \rangle r) < y^{\langle 𝒥 \rangle}}} & (66) \end{matrix}

[0147] From (66) we see that the maximum scaling supported by the ordered partition is

\begin{matrix} \min_{1 \leq k \leq p} {\min_{𝒥 \subseteq 𝒢_{k}} {h (𝒥, {\overline{𝒢}}_{k}) / \langle 𝒥 \rangle}} . & (67) \end{matrix}

The OSGD will achieve the maximum symmetric scaling over all valid ordered partitions that is given in (63). Note that r_OSGD* in (63) itself can be determined via a greedy algorithm similar to our previous greedy grouping one but where at each stage,

\min_{𝒥 \subseteq 𝒢} {h (𝒥, \overline{𝒢}) / \langle 𝒥 \rangle}

is maximized over valid ordered partitions of the form { custom character

}. With r_OSGD* in hand, we can set R=r_OSGD* log(ρ)+log(y) and determine that for the OSGD the common outage event in the limit ρ→∞ is identical to the event

\begin{matrix} ⋂_{\underline{𝒢} \in \underline{Q}} {⋃_{k = 1}^{p} {⋃_{\underset{h (𝒥, {\overline{𝒢}}_{k}) \leq \langle 𝒥 \rangle r_{OSGD}^{*}}{𝒥 \subseteq 𝒢_{k}}} {g ({\tilde{H}}_{𝒥}^{†} P_{𝒢_{k}}^{⊥} {\tilde{H}}_{𝒥}, \langle 𝒥 \rangle r_{OSGD}^{*}) < y^{\langle 𝒥 \rangle}}}} & (68) \end{matrix}

The asymptotically tight approximation given in (63) follows from (68).

[0148] Using the arguments in the proof given above, we can readily show that an asymptotically tight affine approximation to the symmetric common outage capacity of an SGD which employs a fixed partition { custom character

₁, . . . , custom character

_p} is given by

\begin{matrix} {\tilde{𝒞}}^{SGD - sym} (ɛ) = r_{OSGD}^{*} \log (ρ) + \log (γ_{\infty}^{SGD - sym} (ɛ)) with & (69) \\ r_{SGD}^{*} = \min_{l \leq k \leq p} {\min_{𝒥 \subseteq 𝒢_{k}} {h (𝒥, {\overline{𝒢}}_{k}) / \langle 𝒥 \rangle}} and & (70) \\ γ_{\infty}^{SGD - sym} (ɛ) = \sup {y : \Pr (⋃_{k = 1}^{p} {⋃_{\underset{h (𝒥, {\overline{𝒢}}_{k}) \leq \langle 𝒥 \rangle r_{SGD}^{*}}{𝒥 \subseteq 𝒢_{k}}} {g ({\tilde{H}}_{𝒥}^{†} P_{𝒢_{k}}^{⊥} {\tilde{H}}_{𝒥}, \langle 𝒥 \rangle r_{SGD}^{*}) < y^{\langle 𝒥 \rangle}}}) \leq ɛ} & (71) \end{matrix}

[0149] For the OSGD under the individual outage formulation we offer the following theorem. The proof is given in Appendix 5.

[0150] Theorem 9: The asymptotically tight affine approximations to custom character

(θ, ε) in (40) and custom character

^sym(ε) in (42) are given respectively by

\begin{matrix} \tilde{𝒞ℐ} (θ, ɛ) = \log (ρ) \sum_{k = 1}^{K} θ_{k} r_{k}^{*} + O (1) and & (72) \\ {\tilde{𝒞ℐ}}^{sym} (ɛ) = r_{OSGD}^{*} \log (ρ) + O (1) . & (73) \end{matrix}

[0151] The following result determines the scaling of the throughput expressions in (43) and (44) with SNR.

[0152] Theorem 10: custom character

(θ) in (43) as well as custom character

(θ) in (44) satisfy

\begin{matrix} \lim_{ρ -> \infty} \frac{𝒯 (θ)}{\log (ρ)} = \lim_{ρ -> \infty} \frac{𝒯ℐ (θ)}{\log (ρ)} = \sum_{k = 1}^{K} θ_{k} r_{k}^{*}, & (74) \end{matrix}

where {r_k*} is given in (47).

[0153] To prove Theorem 10, we first note that custom character

(θ),

(θ) can be alternatively expressed as:

\begin{matrix} \begin{matrix} 𝒯 (θ) = \sup_{ɛ \in (0, 1)} {(1 - ɛ) 𝒞 (θ, ɛ)}, \\ and 𝒯ℐ (θ) = \sup_{\in {(0, 1)}^{K}} {𝒞ℐ ((1 - ɛ) \cdot θ, ɛ)} \end{matrix} & (75) \end{matrix}

where (1−ε).θ custom character

[(1−ε₁)θ₁, . . . , (1−ε_K)θ_K]. Consider custom character

(θ). Using (75) and the asymptotically tight affine approximation for (,ε) in (48), we can infer that at high SNR

\begin{matrix} 𝒯 (θ) \geq (1 - ɛ) \log (ρ) \sum_{k = 1}^{K} θ_{k} r_{k}^{*} + (1 - ɛ) \log (γ_{\infty} (θ, ɛ)), and 𝒯 (θ) \leq \log (ρ) \sum_{k = 1}^{K} θ_{k} r_{k}^{*} + \sup_{ɛ \in (0, 1)} {(1 - ɛ) \log (γ_{\infty} (θ, ɛ))}, ɛ \in (0, 1) . & (76) \end{matrix}

[0154] Since the terms independent of ρ in the LHS and RHS of (76) are finite, we can conclude that

\begin{matrix} (1 - ɛ) \sum_{k = 1}^{K} θ_{k} r_{k}^{*} \leq \lim_{ρ -> \infty} \frac{𝒯 (θ)}{\log (ρ)} \leq \sum_{k = 1}^{K} θ_{k} r_{k}^{*}, \forall ɛ \in (0, 1) . & (77) \end{matrix}

From (77) it follows that the scaling of custom character

(θ) is equal to Σ_k=1^Kθ_kr_k*. A similar argument works for custom character

(θ) also.

[0155] 4.2 Large Array Regime

[0156] In this section we consider the SGD with the group size constraint and characterize the limiting capacity behavior [corresponding to (39), (40), (41) and (42)] as well as the limiting throughput behavior [corresponding to (43) and (44)], as both the number of users and the number of receive antennas grow to infinity. For simplicity, we consider a symmetric MAC (SMAC) where all users have an identical number (equal to m ) of transmit antennas and we assume that all fading coefficients are i.i.d. random variables with zero-mean and unit variance. We keep m fixed and let K, N→∞ such that B=mK/N is constant. Also, each user's input covariance matrix is set as

\frac{ρ}{Km} I,

so that the total transmit power in the system remains fixed at ρ. It is a well-known result (see, e.g., A. Lozano, “Capacity-approaching rate function for layered multiantenna architectures,” IEEE Trans. Wireless Commun., vol. 2, no. 4, pp. 616-620, July 2003 and the references therein) that due to the almost sure convergence of the singular values of H, the mutual-information random variables tend to their deterministic (ergodic) limits (a.k.a. channel hardening effect). As a consequence, asymptotically--in the large array regime—the channel-dependent grouping algorithm is irrelevant and there is no difference between the common and individual outage formulations. Successive group decoding, however, can still yield capacity gains commensurate with the maximum group size allowed.

[0157] We first consider the weighted sum capacity (39) or (40). As a result of the channel hardening effect and the fact that MMSE-SIC achieves the corner point of the (ergodic) MAC capacity region, we can conclude that an asymptotically optimal solution to (39) or (40) for any OSGD is identical and the optimal rate allocation corresponds to the comer-point determined by the non-increasing order of user priorities. Further, since the outage probabilities tend to indicator functions (which equal to one if the rate is greater than the corresponding deterministic capacity and zero otherwise) both the common as well as individual throughput, given by (43) and (44) respectively, are asymptotically identical to the (common or individual) outage capacity.

[0158] Now let us consider the more involved case of symmetric outage capacity. We first consider the ML decoder from which we note that the limiting sum capacity (per receive antenna) can be expressed as the following integral

\begin{matrix} \begin{matrix} 𝒞_{\infty} (β, ρ) \overset{△}{=} \lim_{N -> \infty} \frac{1}{N} \log \langle I + \frac{ρ}{Km} {HH}^{†} \rangle \\ = \int_{0}^{β} \log (1 + ρ / β - F (x, ρ / β)) ⅆ x \\ = \log (1 + ρ - F (β, ρ / β)) + β \log (1 + ρ / β - F (β, ρ / β)) - \\ β \frac{\log (ⅇ)}{ρ} F (β, ρ / β) \end{matrix} with & (78) \\ F (x, y) \overset{△}{=} {\frac{1}{4} [\sqrt{1 + {y (1 + \sqrt{x})}^{2}} - \sqrt{1 + {y (1 - \sqrt{x})}^{2}}]}^{2} . & (79) \end{matrix}

See A. Lozano, “Capacity-approaching rate function for layered multiantenna architectures,” IEEE Trans. Wireless Commun., vol. 2, no. 4, pp. 616-620, July 2003.

[0159] To extend this result to the symmetric capacity, we offer the following theorem whose proof is given in Appendix 6.

[0160] Theorem 11: The limiting symmetric capacity of any SGD (optimal or otherwise), denoted by custom character

_∞^sym-SGD(β, ρ), is given by

\begin{matrix} \begin{matrix} 𝒞_{\infty}^{sym - SGD} (β, ρ) = \frac{1}{δ} \int_{β - m δ}^{β} \log (1 + ρ / β - F (x, ρ / β)) ⅆ x \\ = \frac{1}{δ} [𝒞_{\infty} (β, ρ) - 𝒞_{\infty} (β - m δ, ρ (β - m δ) / β)], \end{matrix} & (80) \end{matrix}

where

δ \overset{Δ}{=} \lim_{N \to \infty} \frac{\langle 𝒢_{1} \rangle}{N}

represents the asymptotic ratio of the number of users jointly decoded in the first group to the number of receive antennas.

[0161] The limiting symmetric capacities of the special cases of the SGD are given in the following corollary.

[0162] Corollary 1: The limiting symmetric capacities of the ML and the unconstrained SGD in the large array regime are identical and given by

\begin{matrix} C_{\infty}^{sym - ML} (β, ρ) = \frac{m}{β} C_{\infty} (β, ρ), & (81) \end{matrix}

whereas that of the MMSE-SIC equals to
custom character

_∞^sym-SIC(β, ρ)=mlog(1+ρ/β-F(β, ρ/β)). (82)

[0163] Note that in (80) since log(1+ρ/β−F(x, ρ/β,)) is non-increasing in x when x∈(0, β), the symmetric capacity of the SGD monotonically increases with the group size parameter δ. Also note that the symmetric capacity operating point is no longer sum capacity optimal and the loss (per receive antenna) can be quantified as

\begin{matrix} C_{\infty} (β, ρ) - \frac{K}{N} C_{\infty}^{sym - SGD} (β, ρ) = \frac{β}{m δ} C_{\infty} (β - m δ, ρ (β - m δ) / β) - (\frac{β}{m δ} - 1) C_{\infty} (β, ρ) . & (83) \end{matrix}

[0164] It is insightful to examine the large array symmetric capacity asymptote in the high SNR regime. To do so we first determine the high SNR behaviour of custom character

_∞(β, ρ) in (79) to be

\begin{matrix} C_{\infty} (β, ρ) = {\begin{matrix} \log (ρ / e) - (β - 1) \log (1 - 1 / β) + O (1 / ρ), & β \geq 1, \\ β \log (ρ / (β e)) - (1 - β) \log (1 - β) + O (1 / ρ), & β \leq 1. \end{matrix} & (84) \end{matrix}

[0165] Using (80) and (84), we can readily obtain the high SNR behavior of custom character

_∞^sym-SGD(β, ρ) as follows, where we drop the custom character

(1/ρ) terms:

\begin{matrix} C_{\infty}^{sym - SGD} (β, ρ) ~ {\begin{matrix} \frac{1}{δ} [m δlog (ρ / (β e)) - (1 - β) \log (1 - β) + (1 + m δ - β) \log (1 + m δ - β)], & β \leq 1, \\ \frac{1}{δ} [(1 - β + m δ) \log (ρ (1 + m δ - β)) + (β - m δ) \log (β e) - \log (e) \\ - (β - 1) \log (1 - 1 / β)] & β \in [1, 1 + m δ], \\ \frac{1}{δ} [- (β - 1) \log (β - 1) + β \log (β) + (β - m δ - 1) \log (β - m δ - 1) \\ - (β - m δ) \log (β - m δ)], & β \geq 1 + m δ . \end{matrix} & (85) \end{matrix}

[0166] Note that there is no growth of the symmetric capacity with log(ρ) in the case of β≧1+mδ, i.e., when

m \frac{K - \langle 𝒢_{1} \rangle}{N} > 1

in the large array limit. This happens because users decoded in the first group become the bottleneck since they see too much interference from remaining users and can only support a constant (common) rate in the high SNR regime. Note that (85) also provides us with the limiting expressions for the custom character

(1) terms in the affine approximations to the symmetric capacities computed above, in the limit of large array sizes and when custom character

_k=1, A_k=I, B_k=I, B_k=I, k=1, . . . , K .

[0167] 4.3 Numerical Results

[0168] For convenience, in the following simulations we assume i.i.d. Rayleigh fading and that all users transmit with identical average powers. Our focus is on the symmetric outage capacities. In order to compute the high-SNR asymptotes we must first determine the optimal scaling factors r_ML*, r_OSGD* and r_SGD* given in (60), (63) and (70), respectively. From the formulae, we see that we need to determine b( custom character

)=rank({tilde over (H)}) for all non-empty subsets, custom character

∈S. (Recall that h( custom character

_k)=b(

_k)−b(

_k). ) Invoking Lemma 5, which says that for any custom character

∈

, rank({tilde over (H)}) equals a constant with probability one, we can determine {b( custom character

)} by generating one realization of {tilde over (H)} and computing the ranks of all {{tilde over (H)}}. However in the following examples, since {tilde over (H)} has i.i.d. zero-mean complex normal elements, we have that b( custom character

)=rank({tilde over (H)})=min{N, Σ_k∈m_k}, {0 custom character

∈

[0169] In FIG. 9 we plot the asymptotically tight high SNR affine approximations (asymptotes) on the symmetric outage capacity obtained in Theorems 8 and 9, for a MAC with N=K=4, m_k=1, {0 k and ε=0.1. We plot the individual symmetric outage capacity high-SNR asymptote for the unconstrained (i.e., μ_max=4) OSGD (73) and the common symmetric outage capacity high-SNR asymptotes ((59), (62) and (69)) for the rest. The SGD considered here uses a fixed ordered partition {{1, 2}, {3, 4}} for every channel realization. In this example we can analytically verify that r_ML*=r_OGSD*=r_SGD*=1. In each case the custom character

(1) terms involved in the affine asymptotes were computed through Monte-Carlo simulations. As shown in FIG. 9, the unconstrained OSGD improves only marginally on the ML decoder, highlighting the fact, however, that the common outage capacity of the ML decoder is not the best achievable. Note that even the OSGD with μ_max=1 improves upon the SGD with a fixed ordered partition of higher complexity.

[0170] FIG. 10 plots the symmetric common outage capacity asymptotes for a MAC with N=4, K=3 and

m_{k} = 2, {\tilde{Q}}_{k} = \frac{1}{6} I \forall k .

The asymptote corresponding to the OSGD with μ_max=2 (62) and that of an SGD with a fixed partition {{1, 2}, 3} (69) for ε=0.01 and ε=0.1, respectively, are plotted. It can be verified that r_OSGD*=r_SGD*=1. The optimal grouping is seen to provide a gain of about 1.8 dB for ε=0.01 and about 1.5 dB ε=0.1. Using (59) we can also verify that the ML decoder yields , r_ML*= 4/3 whereas the OSGD with μ_max=1 and hence any SGD with μ_max=1 yield r_OSGD*=r_SGD*=0. Moreover from (69) we can also infer that the SGDs corresponding to (fixed) partitions {1,{2, 3}}, {2, {1,3}} and {3, {1,2}} all yield r_SGD*=0.

[0171] In FIG. 11 we consider the limiting (large array) symmetric outage capacity. We set N=K with m_k=1, {0 k and fix the total transmit power in the system at ρ=16 dB. We plot the simulated symmetric common outage capacities of the SGD and the OSGD with μ_max=1 and ε=0.1 and ε=0.01 (41), along with the capacity obtained in the limit K→∞ with β=1 (82), which for our choice of parameters equals 2.77 bits per channel use. The symmetric outage capacity of the SGD is monotonically increasing towards its limiting value. Note that although the OSGD and the SGD have identical limiting capacity since grouping (ordering) is asymptotically irrelevant, as seen from the figure the rate of convergence is very slow. This implies that for all practical MIMO MAC configurations, optimal grouping results in substantial gain in terms of the outage capacity.

[0172] In FIG. 12 we again consider the limiting (large array) symmetric outage capacity and set N=K with m_k=2, {0 k so that β=2. FIG. 12 plots custom character

_∞^sym-SGD(β, ρ) (given in (80)) versus ρ for several values of δ along with its large ρ approximation given in (85). From the plot it is seen that the high SNR approximation becomes tight even at moderate SNRs. In this example for any asymptotic group size δ∈[0,1/2], the symmetric capacity approaches an upperbound (given by (85)) with increasing SNR, so its scaling factor with log(ρ) is zero. On the other hand, for δ∈[1/2,1], the scaling factor equals

2 - \frac{1}{δ}

and monotonically increases with δ.

[0173] An optimal successive group decoder (OSGD) that simultaneously minimizes the common and individual outage probabilities as well as maximizes the error exponent has been disclosed. An adaptive SGD has been proposed which retains the outage optimality of the OSGD but minimizes the average decoding complexity. Asymptotically tight affine approximations have been obtained for the relevant performance metrics. Limiting expressions for the relevant capacities as the number of users and the number of receive antennas approach infinity show that SGD yields symmetric capacity gains commensurate with the decoding complexity allowed.

[0174] It is understood that the above-described embodiments are illustrative of only a few of the possible specific embodiments which can represent applications of the invention. Numerous and varied other arrangements can be made by those skilled in the art without departing from the spirit and scope of the invention.

Appendices

1. Proof of Theorem 1

[0175] As mentioned earlier an SGD can use any partitioning rule that returns a valid ordered partition. Further, for a given channel realization H and a specified covariance matrix Q let {tilde over (H)}=HQ^1/2 and suppose a partition { custom character

₁, . . . , custom character

_p} is used. From our definitions of the outage events [(4) and (5)], we see that is custom character

_q+1is the first group in outage, then the set of users {1, . . . , K} is divided into a decodable set U^c custom character

∪_j=1^q

_jand an undecodable set U custom character

∪_j=q+1^p

_j, and both of which do not depend on the choice of particular codebooks. Let custom character

be the ensemble of multi-user Gaussian codebooks satisfying the covariance constraints. Then letting custom character

_u, denote the joint error event for the decodable set, by Tonelli's theorem [21] we have that
custom character

_{{tilde over (H)}} custom character

X(U^c≢φ)Pr( custom character

_uc|{tilde over (H)}) custom character

_{{tilde over (H)}} custom character

X(U^c≢φ) Pr( custom character

_Uc|{tilde over (H)}) custom character

. (86)
Note that custom character

_Uc=∪_m=1^q custom character

_m, where

_mis the event that any one of the users is custom character

_mis decoded incorrectly. Let custom character

_m^gbe the event that any on of the users in custom character

_mis decoded incorrectly in the genic-aided decoder which always has perfect feedback from preceding groups and note that the events ∪_m=1^q custom character

_mand ∪_m=1^gare identical [4]. Therefore
custom character

_{{tilde over (H)}} custom character

X(U^c≢φ)Pr( custom character

_uc|{tilde over (H)}) custom character

_{{tilde over (H)}} custom character

X(U^c≢φ)Pr custom character

∪_m=1^q

_m^g|{tilde over (H)} custom character

, (87)
so that
custom character

_{{tilde over (H)}} custom character

X(U^c≢φ)Pr( custom character

_uc|{tilde over (H)}) custom character

≦

_{{tilde over (H)}} custom character

X(U^c≢φ)Σ_m=1^qPr custom character

_m^g|{tilde over (H)} custom character

, (88)
Letting custom character

_m^g|{tilde over (H)} custom character

and Pr(

_Uc|{tilde over (H)}) denote the respective averages over the ensemble of multi-user Gaussian codes, we note that [9]
Pr( custom character

_m^g|{tilde over (H)})≦[2^|m|exp custom character

{tilde over (H)}, _m, ∪_j=m+1^p custom character

]⁺, (89)
pg,45

Claims

What is claimed is:

1. A group decoding method for an open-loop uplink space-division multiple access (SDMA) system with multiple users employing a codebook of a fixed rate and a receive with a plurality of receive antennas, the method comprising:

simultaneously minimizing a common outage probability and an individual outage probability; and

maximizing an error exponent over all group decoders of permissible decoding complexities, respectively.

2. The method of claim 1, wherein the group decoders are successive group decoders.

3. The method of claim 1, wherein the group decoders are parallel group decoders.

4. The method of claim 1, wherein the group decoding method is an optimal group decoding method.

5. The method of claim 4, wherein the optimal group decoding method is determined using a greedy algorithm.

6. The method of claim 1, wherein the group decoding method is an adaptive successive group decoding method.

7. A joint scheduling and grouping method for throughput maximization for an uplink space-division multiple access (SDMA) system operating under proportional fairness constraints, the uplink SDMA system including a receiver that employs successive group decoding, has multiple receive antennas, and can communicate with each of a plurality of users via a downlink channel, the method comprising:

specifying a decoding complexity constraint;

determinining a plurality of uplink channel realizations;

determining an optimal set of user rates and a group decoder of permissible decoding complexity satisfying the decoding complexity constraint for each of a set of uplink channel realizations; and

communicating the user rates to the plurality of users using the downlink channel.

8. The method of claim 7, wherein the downlink channel is of limited capacity.

9. The method of claim 7, wherein the group decoder is a successive group decoder.

10. The method of claim 7, wherein the group decoder is a parallel group decoder.

11. The method of claim 7, wherein the uplink SDMA system employs Hybrid ARQ.