Project Summary
Download 129.87 Kb.
|
- Navigate this page:
- C. 2.2 Current state of research practice
- C. 2.3 Planned research
C. 2 Proposed ResearchC. 2.1 Overview of multiuser detectionThe multiuser detection of CDMA signals has received considerable attention for over a decade. A textbook on multiuser detection was recently written by Verdú [14]. Tutorial references on multiuser detection were presented by Verdú [15], Duel-Hallen et al. [16], and Moshavi [17] with extensive reference lists therein. Verdú [18][19] showed that the GML multiuser detector can achieve significant performance improvement over the conventional detector. However, its computational complexity grows exponentially with the number of active users. Unless the signal correlations have a special structure as was found for nonpositive correlations by Ulukus and Yates [20], the GML detector is impractical when the number of active users is large. To develop low-complexity suboptimal multiuser detectors, suboptimal tree-type maximum-likelihood sequence detectors were proposed for multiuser systems. Xie, Tushforth, and Short [21] considered the sequential detector, and later the breadth-first algorithms [22]. Wei and Schlegel [23] used the M-algorithm tree-search scheme preceded with a decorrelating noise whitening filter. Wei et al. [24] showed that combined with a decorrelating noise whitening matched filter, the M- and T- algorithms can provide near optimum performance at a low level of complexity compared with the GML detector. To develop linear suboptimum detector, Lupas and Verdú exploited a linear decorrelating detector [25] [7], which was initially proposed in [26]. The decorrelating detector has computational complexity significantly lower than that of the GML detector while provides substantial performance gain over the conventional detector. The most significant advantage of the decorrelating detector is that it achieves optimal performance of near-far resistance and needs no knowledge of interfering users’ powers. However, its performance is far from the optimality due to the noise enhancement of the matrix inverse. Xie, Short and Rushforth [27] applied the minimum mean-square error (MMSE) filter which compromises both multiple access inference suppression and background noise suppression. Viterbi [28] and Yoon, Kohno, and Imai [29] applied the idea of the successive interference cancellation (SIC). The SIC detector takes a serial approach to canceling interference. Duel-Hallen [30][31] used the decorrelating decision-feedback detector (DDFD). Klein, Kaleh, and Baier [32] proposed the zero-forcing decision-feedback detector. The DDFD performs linear preprocessing followed by a form of SIC detection. Varanasi [33] developed a systematic approach to the design of decision feedback detectors. The likelihood ascent search (LAS) detectors [8][9][10] to be developed as part of this project are mostly comparable with the parallel interference cancellation (PIC) detector and the EM based receivers. There has been considerable research on the multistage PIC detector since Varanasi and Aazhang [34][35] proposed its structure. A basic one stage PIC structure was proposed by Kohno, Imai and Hatori [36]. In the PIC detector, the multiple access inference is estimated based on the bit estimate from previous stage and is subtracted from received signal in parallel. This process can be repeated for multiple stages. In the early study, it was observed [34] that the performance of the PIC detector depends heavily on the initial data estimates. It was indicated [35] that it is the effect of interference doubling from users that are incorrectly detected at the penultimate stage, that ultimately limits the performance of the multistage detector. A number of variations on the PIC detector have been proposed for improved performance. Patel and Holtzman [37] indicated that soft-decision PIC is found to be superior in a well power-controlled channel. Giallorenzi and Wilson [38] proposed the use of the already detected bits at the output of the current stage to improve detection of the remaining bits in the same stage. Moshavi [39] considered the linear combination of the soft-decision outputs of different stages of the PIC detector. Divsalar, Simon, and Raphaeli [40] proposed a partial multiple access interference cancellation at each stage with the amount of cancellation increasing for each successive stage. More studies on the PIC detector can be found in literature such as Hegarty and Vojcic [41], Gray, Kocic, and Brady [42], Ghazi-Moghadam, Nelson, and Kaveh [43], Shi, Du, and Driessen [44], Buehrer and Woener [45], Zhang and Brady [46], and Beuhrer and Nicoloso [47]. The linear PIC (LPIC) detector that makes no hard decisions before the final stage has also been studied in literature (see [48] and references therein). The main drawback of the PIC and LPIC detectors is their instability. Verdú demonstrated [14] by a two-user channel that a limit cycle exists in the process of the PIC detector. Our preliminary study [9][10] gave a set of conditions on which the limit cycle exists for the PIC detector in a general CDMA system. Brown et al. [48] analyzed the diverge error probability of the LPIC detector. Nelson and Poor [49] developed several EM based receivers. Among them, the SAGE receiver has the same structure as the PIC detector but sequentially updates bits. This change of update mode makes the SAGE receiver monotonically increase likelihood and hence converge to a fixed point in a finite number of iterations. Raphaeli [50] proposed the application of an EM based algorithms to multiuser detection. This EM based algorithm can update any number of bits at a step. When only one bit is updated per step, it becomes the SAGE receiver. A deterministic annealing technique is then applied to the SAGE algorithm to produce soft and then gradually harder decision on bits. Wu and Wang [51] applied a local search algorithm that was originally proposed for solving quadratic binary programming problem. The local search algorithm presented in [51] employs 0/1 symbols. Actually, this algorithm is the SAGE receiver in the version of 0/1 bits. This applicant [63] applied a sequential algorithm of a family of modified Hopfield neural network based algorithms2 to multiuser detection. It turns out that this sequential algorithm is also identical to the SAGE algorithm. The eliminating-highest-error and the fastest-metric-descent criteria were proposed for adaptive choice of updated bit at each step and considerably reduce bit error rate and the total number of iterations. It is not surprising that all these researchers independently obtained the SAGE algorithm by application of quadratic optimization search algorithms in different areas to the multiuser detection. The reason is that the SAGE receiver employs the smallest-neighborhood local search (updates one bit per step), monotonically decreases metric, and achieves the local maximum likelihood solution with neighborhood size one. It is interesting to further view the PIC detectors, EM based receivers, and SAGE receiver in the framework of the family of linear-complexity LAS detectors. Although there have been many studies on the PIC detector in literature, we can apparently see the shortcomings in development of the PIC detectors and drawbacks of PIC detectors themselves. These drawbacks can be more easily seen in the framework of the linear-complexity LAS detectors [9][10]. The PIC detector is fundamentally a search detector. Given one demodulated vector at one stage, the PIC detector searches out another vector at next stage. The PIC detector was developed mainly based on the intuition motivated by interference cancellation in parallel rather than aiming at guaranteed likelihood ascent stage by stage. There is no indication about whether performance is improved at each stage, probably partly due to lack of an efficient method for the performance evaluation at every stage when the PIC detectors were developed. Nevertheless, it is the motivation to cancel all interference in parallel simultaneously that yields a “greedy” and malfunctioned PIC detector. Specifically, the size of search step in the PIC detector is too large, larger than the necessary size to guarantee the likelihood ascent at every step with probability one. Thus, the PIC detector enters a limit cycle with a nonzero probability. In addition to no guarantee of convergence, the existence of limit cycle of the PIC detector results in other three drawbacks. It is shown [9] that once trapped into a limit cycle, the PIC detector must decrease likelihood in some stages, which wastes computation time. On a limit cycle, the PIC detector can only achieve a likelihood lower than an LML which can be achieved by the SAGE receiver. Finally, there is no adequate criterion for the PIC detector to terminate its iterations/search. In contrast, the family of the LAS detectors [8][9][10] to be studied as part of this proposed project is developed by aiming at guaranteed likelihood ascent step by step, thus converging to a fixed point in a finite number of search steps with probability one. It is shown [8][9][10] that in the family of the LAS detectors there is a subfamily of wide-sense sequential LAS (WSLAS) detectors that achieve local maximum likelihood (LML) detection with neighborhood size one. Thus, they achieve the local minimum error probabilities with neighborhood size one. Many other good characteristics of the family of LAS detectors are proved in [9]. The SAGE receiver is a WSLAS detector. The family of LAS detectors also provides a framework for stability analysis of other iterative receivers. In the preliminary study [9], we obtain a set of conditions under which the PIC detector converges to some limit cycle. The condition under which the EM based algorithms with hard decision in [50] are stable are also obtained. C. 2.2 Current state of research practiceA. Previous study in image restoration and neural networks This applicant has long worked on image restoration and reconstruction, and neural networks. The problem of image restoration [5] has the same formulation and as multiuser detection. In image restoration, because of a large number of pixels and multiple intensity levels, the optimum solution in terms of maximum likelihood requires comparison of an astronomic number of metric values, say 28256256 for an ordinary image of size 256256 and a total of 256 intensity levels. To develop low computational complexity algorithms is an essential approach for image restoration. Motivated by parallel, massive, efficient computation with implementation on a neural network hardware, the Hopfield neural network (HNN) algorithms were applied to image restoration first by Zhou et al. [52]. However, their proposed HNN algorithms need to check metric change step by step to guarantee monotonic metric descent and thus is time-consuming. The modified Hopfield neural network (MHNN) models were proposed by Paik and Katsaggelos [53] for gray image restoration and by Sun (this applicant) and Yu [54] for binary image restoration and reconstruction. The essential difference between the MHNN and HNN is that even though the crosscorrelation matrix in a quadratic optimization problem is nonnegative definite, the MHNN guarantees stability by adding a threshold for each neuron, which is much simpler than check of metric change step by step. Sun and Yu then proposed [55][56] the eliminating-highest-error (EHE) criterion for MHNN. Many simulation results showed that under the EHE criterion the MHNN algorithms can converge to much more accurate solutions in much fewer iterations in both blind [57] and non-blind [58] situations. Sun [59][60] recently carried out a thorough comparison and analysis on various HNN based algorithms which indicates that the EHE criterion based MHNN algorithms perform much better than the other MHNN algorithms in all conditions. In particular, Sun [61][62] also developed a family of MHNN algorithms in a generalized framework in which any number of neurons (or bits in terminology of CDMA) can be updated and the network energy (or metric in terminology of CDMA) monotonically decreases. To CDMA multiuser detection, Sun [63][64] applied the sequential algorithm (same as the SAGE receiver) of this family of MHNN algorithms with the EHE and FMD criteria. It was demonstrated that the two sequential algorithms employing the EHE and FMD criteria considerably outperformed the original sequential algorithm (i.e. the SAGE receiver). Since the multiuser detection problem is also a quadratic optimization problem with binary support, this entire family of MHNN algorithms can be applied to multiuser detection. When applied to CDMA multiuser detection, this family of MHNN algorithms turn out to perform likelihood ascent search, and thus forming the family of linear-complexity LAS detectors [8][9][10]. B. Preliminary study on the families of LAS and LMLAS detectors This family of likelihood ascent search (LAS) detectors can be defined by the following generalized likelihood ascent search (GLAS) detector. GLAS detector: Given a sequence of bit index subsets L(t) {1, ..., K} for t 0 and an initial b(0) {1, 1}K, the bits are updated by where tk(t) is the threshold of the kth bit at step t, h(t) is the negative metric gradient with respect to b(t) which can be efficiently updated by where L’(t) L(t) is the subset of indices of bits that are flipped at step t and Wk is the kth column of W. If b(t) = bf for all t tf with some tf 0, bf is the finally demodulated vector. The family of LAS detectors has many good properties as analyzed in the preliminary study [9][10]: One produces a LAS detector by specifying a sequence of L(t), t 0 in the GLAS detector. Determined by L(t) a LAS detector can update any number of bits at each step. A LAS detector monotonically increases likelihood at every search step, and thus monotonically decreases error probability and converges to a fixed point in a finite number of steps. Following any initial detector, a LAS detector can reduce the error probability of the initial detector unless the initial detector is a fixed point of this LAS detector with probability one. For an arbitrary crosscorrelation matrix, the thresholds set up in the LAS detectors are optimum in the sense that the error probability achieves the minimum while the monotonic likelihood increase is guaranteed. A LAS detector achieves a maximum likelihood solution of a subset of hypotheses that it searched. The fewer the bits updated at each step (i.e. the smaller the |L(t)|), then the slower the convergence, the fewer the fixed points, the smaller the difference between the fixed point region (i.e. decision region) and the GML decision region, and the smaller the error probability. Among the LAS detectors, the wide-sense sequential LAS (WSLAS) detectors converge with probability one to local maximum likelihood (LML) points defined with neighborhood size one, and thus each achieves a local minimum error probability with neighborhood size one. A WSLAS detector can reduce the error probability of any detector to a local minimum if the detector does not achieve the LML detection with probability one. When L(t) = {i | i = (t mod K) +1}, it defines the SAGE receiver which is also a WSLAS detector. Except the GML detector (and the family of LMLAS detectors recently developed in [12]), none of other well-known detectors are known to achieve LML detection with probability one and thus can be improved by the WSLAS detectors. All linear detectors (including the conventional detector, decorrelating detector, linear MMSE detector), and most nonlinear detectors including the PIC detector, SIC detector, decorrelating decision feedback detector, MMSE-DF detector are not LML detectors and thus their error probability can be reduced by followed WSLAS detectors [9]. It has been shown that all LAS detectors have linear complexity. Many simulations showed that the highest computational complexity of any LAS detector is about 0.65K per demodulated bit with a random initial.  Another good characteristic of the LAS detectors is their high ratios of performance to complexity in fair large systems (more than fifty users). Shown in Fig. 1 (a) are bit error rates (BER) of a group-parallel LAS (GPLAS) detector with fixed group sizes (number of bits updated at each step) J = |L(t)| = 8, 4, 2, 1 (a WSLAS detector is with J =1 here), the SLAS detector (which is the same as the SAGE receiver here), the conventional detector, SIC detector, MMSE detector, MMSE-DF detector, and single user bound. The system employs random binary spreading sequences, equal power with SNR = 9 dB, and fixed ratio of number of users to processing gain K/M = 0.5. Shown in Fig. 1 (b) is the bit flip rate (BFR) of the LAS detectors, which is defined as average percentage of bits flipped in a search. Since each bit flip needs K additions, KBFR is the average number of additions per demodulated bit, which can be used as a computational complexity measure. As we can see, while the other detectors keep the fixed BERs, the LAS detectors monotonically decreases their BERs gradually close to the single user bound as the number of users increases. For K 50, the WSLAS and SLAS detectors (both are LML detector with neighborhood size one) have lower BERs than the MMSE-DF detector. As shown in Fig. 1 (b), all LAS detectors have an average number of additions per demodulated bit smaller than 0.62K which is linear and is lower than any linear receivers if spreading sequences are fixed (note that the computation for W = ARA, q = Ar, and h(0) = Wb(0) + q for the LAS detectors can be done once and be ignored in complexity account). For the random spreading sequences (which are similar to long spreading sequences), the LAS detectors need to increase the linear-complexity computation for W = ARA, q = Ar, and h(0) = Wb(0) + q. In contrast, the MMSE detector and the MMSE-DF detector need to increase the computation of inverse of matrix of size KK which is much more complex than linear. Consequently, we can conclude that the LAS detectors achieve much higher ratios of performance to computational complexity than the MMSE and MMSE-DF detectors in the simulated case for the system of more than fifty users. Fig. 1 (a) and (b) also show that the BER of LAS detectors decreases and their computational complexity increases as the number of bits updated in each step decreases, which provides a mechanism for the LAS detectors to achieve a different tradeoff between performance and computational complexity. The family of LAS detectors also provides a framework for stability analysis of other iterative receivers. The condition under which the EM based algorithms with hard decision in [50] are stable was not indicated in [50]. In the framework of the family of LAS detectors, the stability condition for these EM based algorithms can easily obtained [9]. In the framework of the LAS detectors, it is also easy to see that the well-known PIC detector is a malfunctioned parallel LAS (PLAS) detector. Specifically, the PIC detector operates exactly the same as the parallel LAS (PLAS) detector but its threshold is that of the SLAS detector. The thresholds set up in the PIC detector are too low, thus resulting in a nonzero probability region where the PIC detectors converges to a limit cycle. A set of conditions under which the PIC detector enters a limit cycle is given in [9]. In contrast, the PLAS detector (actually all the LAS detectors) converges to a fixed point in finite number of search steps with probability one. Inspired by the fact that the WSLAS detectors achieve LML detection with neighborhood size one and the GML detector achieves LML detection with neighborhood size equal to the total number of users, this applicant [11][12][13] recently proposed a new concept – local maximum likelihood (LML) multiuser detection with an arbitrary neighborhood size. Then a family of local-maximum-likelihood likelihood-ascent-search (LMLAS) detectors was developed. An LML detector with neighborhood size J is defined as [11] where Every solution in is an LML point with neighborhood size J. It is shown [11][12] that for r K, b {1, 1}K is an LML point with neighborhood size J if and only if for all L {1,…,K} such that 1 |L| J. Given r, defines a set of LML points. On the other hand, given b, defines an observation region – LML point region, which can be viewed as a decision region for the LML point b. In general, LML point regions with different bit vectors may be overlapped. An LML point region with neighborhood size J is specified by a total of To realize the LML detection with an arbitrary neighborhood size, we developed a family of LMLAS detectors [11][12][13] defined by the following generalized LMLAS (GLMLAS) detector. GLMLAS detector: Given an initial b(0) {1, 1}K and a sequence of bit index subsets L(t) {1, ..., K} such that 1 |L(t)| J for all t 0. For all t 0, repeat the following updates until termination. If where hi(t) is the ith component of the negative metric gradient h(t) evaluated at b(t), then the bits are updated by
and the negative metric gradient h(t) is updated by . If b(t) = bf for where NJ(bf) denotes the neighborhood of bf with neighborhood size J, then terminate with bf of the finally demodulated bit vector. One produces an LMLAS detector by specifying a sequence of L(t), t 0 and neighborhood size J in the GLMLAS detector. The family of LMLAS detectors also has many proved good properties [11][12][13]. Every LMLAS detector with J is shown to be an LML detector with neighborhood size J. An LMLAS detector increases likelihood monotonically step by step, and thus converges to an LML point in a finite number of search steps with probability one. Each LMLAS detector achieves a local minimum error probability with a corresponding neighborhood size. As the neighborhood size increases, the error probability of an LMLAS detector decreases while its computational complexity increases. By adjusting the neighborhood size, one can make a tradeoff between error performance and computational complexity. Following any detector, an LMLAS detector can reduce the error probability of the initial detector to a local minimum and otherwise not change it when the initial detector itself is an LML detector with the same or greater neighborhood size with probability one. Since the LMLAS detectors increases likelihood at each step, they also achieve high ratio of performance to computational complexity.
In summary, these two families of LAS detectors and LMLAS detectors span a broad spectrum of performance-complexity tradeoff with high ratio of performance to computational complexity. Local maximum likelihood (LML) points and their properties have never been studied in multiuser detection literature (and nor well studied in other areas). Our preliminary analysis shows interesting properties of the LML points and their relationship with the GML point. For example, consider LML regions defined with neighborhood size one for two-user systems (if neighborhood size two is considered, all LML points are also GML points). For the two-user system of R12 = 0.6, A1 = 1 and A2 = 0.5, Fig. 3 s  hows LML regions where (1,1), (1,1), (1,1), and (1, 1) are LML points, respectively. In the shaded region, both (1,1) and (1,1) are LML points, one of which is the GML point. As divided by the line segment in the shaded region, in the upper shaded triangle, (1,1) is the GML point, and in the lower shaded triangle, (1,1) is the GML point. The line segment that divides the shaded region into these two triangles is the decision boundary of the GML detector for hypotheses (1,1) and (1,1). By the GML detector, the upper shaded triangle is assigned to hypothesis (1,1), and the lower shaded triangle is assigned to hypothesis (1,1). All LML detectors may perform differently only inside the shaded region. Outside the shaded region where there is only the GML point, an LML detector performs equally well as the GML detector. Inside the shaded region, with some probability an LML detector may select a truly LML solution instead of the GML solution and therefore performs worse than the GML detector. This probability depends on the particular LML detector that makes the decision. Since all four noise-free signal points are outside the shaded region in Fig. 3, as 0, any LML detector performs asymptotically equally well as the GML detector. Because the observed noise-free signal is below r2 = 0 for (1,1), and above r2 = 0 for (1, 1), it is clear that as 0, the conventional detector is sure to make wrong decision on user 2 and suffers from the near-far problem. However, as we have seen, an LML detector does not suffer from the near-far problem in this near-far situation.  Fig. 4 shows the LML regions of the two-user system with R12 = 0.65, A1 = 0.8 and A2 = 0.8. Since the two noise-free signal points for (1,1) and (1,1) are inside the shaded region, as 0, an LML detector may suffer from the interference of the true LML point when a GML point was transmitted. Fig. 5 shows the LML regions of the two-user system with R12 = 0.5, A1 = 1 and A2 = 1. The two noise-free signal points for (1,1) and (1,1) are located at the boundary of shaded region. As 0, an LML detector may or may not suffer from the interference of true LML point in the neighborhood of the noise-free signal points.
Although only neighborhood size one is considered here, these two-user systems suggest rich structure of error probability of LML detectors with an arbitrary neighborhood size. C. 2.3 Planned researchWe will develop a family of linear-complexity LAS multiuser detectors in some combinations of the following conditions: wireless multipath fading channels, on-the-move (Doppler), known and unknown interference users (group blind), broadband and multirate data, power control, adaptive modulation, turbo coded data, space-time coding, and large systems in CDMA networks with direct sequence, frequency hopping, and multicarrier modulation. The family of LMLAS multiuser detectors achieving LML detection with an arbitrary neighborhood size will also be developed in the above various cases. The both families of LAS and LMLAS detectors with soft intermediate decision will be investigated. We will study strategies to determine the optimum order of bit update. Performance analysis will include the characterization of local maximum likelihood points with an arbitrary neighborhood size, the dynamical stability, monotonic likelihood ascent characterization, expected computational complexity, error probability, asymptotic multiuser efficiency, near-far resistance, optimum power control, and spectral efficiency. Although we have many research topics in the direction of this proposal, as a three-year project for one PI and one Ph.D. student, we will focus on the following topics.
A.Continued study on analysis of the family of LAS detectors In the preliminary study, many good analytical characteristics have been revealed for the family of LAS detectors. We will continue the analysis work in the following several aspects. The two conditions for bit flip in can be concisely rewritten as For the LAS detectors, the computational complexity changes from one observation to another because the operation of LAS detectors depends on noise samples (the same is true for other iterative algorithms). Then the average number of additions per demodulated bit is used as a computational complexity. Since the average number of additions per bit is equal to the bit flip rate (BFR) (defined as the ratio of average number of bit flips to the number of users) times the number of users, the BFR can also used as a computational complexity. It has been shown that all LAS detectors have linear complexity. Many simulations showed that the highest BFR of a LAS detector with random initial is about 0.65. In this project, we will rigorously analyze error probability, near-far resistance, and BFR of LAS detectors in two-user systems. We expect this analysis to reveal some insightful characteristics of LAS detectors. The preliminary study showed [9] that the threshold in is optimum in the sense that given the number of bits updated in a step, the threshold in guarantees the achievement of minimum error probability and monotonic likelihood increase (which guarantees convergence and wastes no computation time). It is expected that if the threshold is lower than the optimum, a LAS detector may enter a limit cycle. We will analyze and then obtain a set of general conditions and observation region with which a limit cycle exists. This conditions can be specified and applied to other iterative algorithms to determine existence of limit cycle. The direct application can be to the PIC detector and the EM-based algorithm with hard decision [50], both of which differ from the LAS detectors only by the thresholds. The initial detector affects the error probability and computational complexity of a LAS detector. We already knew in our preliminary study that the error probability of a LAS detector is never higher than the error probability of the initial detector. We expect that the error probability and the computational complexity of the LAS detector monotonically decrease as the error probability of the initial detector decreases. We will analyze it in this project. B.Analysis on characteristics of LML detector with an arbitrary neighborhood size As a brand new nonlinear detector, the characteristics of LML detector with an arbitrary neighborhood size has not been well studied yet. The following analysis will be carried out in the project. Except the GML detector, the decision regions (LML point region) of an LML detector may be overlapped as shown in Figs. 3-5. All LML detectors (including the GML detector) perform differently only in this overlapped region. Hence, determination and analysis of the region of multiple LML points are important problems and are the first steps for performance analysis of the LML detectors. For example, by examining inequality which determines the LML point region, we can see that the noise-free signal points are always inside the corresponding LML point region for any neighborhood size. This suggests the superior asymptotic performance of the LML detectors over the conventional detectors as 0. In fact, the LML point region has a rich structure as shown in Figs. 3-5. In the proposed project, we will investigate the LML point region and its properties. We will qualitatively analyze how the neighborhood size affects the error probability. Since multiple LML points exist in the overlapped region, we will consider an LML detector that equiprobably selects an LML point in the overlapped region. We expect an analytical result that the error probability of the LML detector monotonically decreases as the neighborhood size increases. C.Performance analysis (a) Error probability: As demonstrated by the two-user systems in Figs. 3-5, the LML region in various conditions presents rich structure for error probability analysis. Since the LML detectors perform differently from the GML detector only in the shaded region, the LML detectors must have a simple expression of the error probability in terms of the error probability of the GML detector. The performance of the GML detector is well studied by Verdú [14]. The analysis result of the GML detector can be borrowed by the analysis of the LML detectors. In the proposed project, the general formula of error probability of LML detectors with an arbitrary neighborhood size will be derived and its relationship with the error probability of the GML detector will be studied. The structure of the error probability of LML detectors will be analyzed with the help of existing analytical results of the GML detector. (b) Asymptotic performance analysis: Asymptotic performance analysis of the LML detectors as 0 is an interesting problem in theory and application. As demonstrated by the two-use systems in Figs. 3-5, the asymptotic performance of the LML detectors with an arbitrary neighborhood size is determined by the location of the noise-free signal points in observation space. If all noise-free signal points are outside the overlapped region, the performance of an LML detector is asymptotically the same as the performance of the GML detector. If some noise-free signal points are located at the boundary of the overlapped region and all other signal points are outside the overlapped region, the asymptotic behavior of the LML detector will be partly like but different from that of the GML detector. If some noise-free signal points are inside the overlapped region, the asymptotic performance of an LML detector will be dominated by the noise-free signal points that are inside the overlapped region. In the proposed project, the asymptotic performance analysis will be carried out in a general high-dimensional case for LML detectors with an arbitrary neighborhood size. (c) Multiuser efficiency and near-far resistance: Multiuser efficiency and near-far resistance are two figures of merit of a multiuser detector, which was proposed by Verdú [19]. The multiuser efficiency and near-far resistance of the GML detector was well studied by Verdú [19]. As demonstrated by the two-use systems in Figs. 3-5, the LML detectors present certain near-far resistance capability. In simulations of [12][63][64] the LML detectors with small neighborhood size in a moderate near-far situation demonstrated certain near-far resistant capability. A careful study of multiuser efficiency and near-far resistance for LML detector with an arbitrary neighborhood size will be performed in a general high-dimensional case for various LML detectors in this project. (d) Spectral efficiency: Verdú and Shamai [72] studied spectral efficiency of the GML detector, and several well-known linear detectors in large systems. In the proposed project, we will investigate the spectral efficiency of the LML detector with an arbitrary size.
In a large CDMA system, both the number of users and spreading gain trend to infinity while keeping their ratio a constant. The theory of large systems with random spreading sequence has been successfully applied to the analysis of performance of several well-known linear receivers and the GML detector and obtained fruitful results [72][73]. In the large systems, the output interference power of a linear receiver becomes deterministic, thus making the analysis mathematically tractable. The similar observation may be true for the LML detector. As we can see in , the boundary of an LML point region is determined by a summation involved with the crosscorrelation matrix. For large systems, the boundary may present some regularization and mathematical tractability, and thus simplifying analysis of characteristics of the LML detectors. We will thoroughly investigate possibilities of this kind in the project. In general, it is hard to analyze the throughput and packet delay for a random access CDMA network with packet combining and multiuser detection. However, our preliminary study showed [74][75][76] that the analysis becomes tractable for a large random access CDMA network with Poisson arrival, in which both the mean of arrival and spreading gain trend to infinity while keeping their ratio a constant. We observed that if the analysis of the LML detector for large systems is tractable, then the analysis of throughput and packet delay for large random access CDMA network employing the LML detector as means of multiuser detection is also tractable. We will also thoroughly investigate this issue in this project.
Since LML detectors asymptotically (as 0) perform equally well as the GML detector when all noise-free signal points are outside the overlapped region, it is interesting to find the condition regarding R and A that all noise-free signal points are outside the overlapped region. This condition is equivalent to the condition that with probability one there is only GML point as 0. In other words, under this condition an LML detector almost surely performs equally well as the GML detector. To find this condition is also significant in that under it LML detectors achieve the performance of the GML detector with as low as linear computational complexity (when neighborhood size is one) as 0. Moreover, given R and with this condition satisfied we can achieve optimum power control (distribution of Ak) in terms of lowest average power consumption while achieving low-complexity GML detection. In the project, this condition will be investigated for an LML detector with an arbitrary neighborhood size. Algorithm development and applications F.Soft intermediate decision In the current version, both families of LAS detectors and LMLAS detectors employ hard decisions in each step. In some practical systems that apply coding schemes, soft decision is necessary to provide for decoder. Raphaeli [50] demonstrated that soft and then gradually hard decision via the deterministic annealing technique can lead the SAGE receiver to overcome local minimum and considerably decrease bit error rate for both uncoded and coded data. The cost is the increased computational complexity. The SAGE receiver is one of the WSLAS detector. We believe that the same deterministic annealing technique can be successfully applied to the both families of LAS detectors and LMLAS detectors and considerably improve their performance. In the project, we will establish the two families of soft-intermediate-decision LAS detectors and LMLAS detectors. Their performance will be investigated. G.Blind and group-blind LML/LMLAS detectors For multipath frequency-selective channels, received CDMA signal is bit-asynchronous and effective signature waveforms are unknown due to distortion of time-varying channels. Development of blind low-complexity multiuser detectors without knowing signature waveforms is of interest in theory and practice. In an up-link scenario, basestation knows the spreading sequences of users in its cell and their effective signature waveforms can be estimated via subspace technique [67]. However, the basestation does not know the spreading sequences of users in other neighbor cells. In this case, the basestation needs to demodulate the intra-cell users with known signature waveforms and suppress the inter-cell users without knowing their signature waveforms. This is so called group-blind multiuser detection [67]. The decorrelating detector, the MMSE detector and the PIC detectors for group-blind multiuser detection are developed in [67][68]. Similarly, to achieve approximately maximum likelihood solution, Raheli et al. [69] proposed the per-survivor processing (PSP) for blind symbol detection of single-tone single-user channels. However, the PSP is infeasible in multiuser detection because it relies on the Viterbi algorithm which is exponentially complex. In the proposed project, we will consider the low-complexity blind and group-blind search detectors that monotonically increase the blind and group-blind likelihood functions by means of the families of LAS and LMLAS detectors. Specifically, considered is the combination of a least square (LS) filter with a LAS or LMLAS detector. This combination can achieve monotonic ascent of blind/group-blind likelihood function, which is justified as follows. Consider the blind case. Given an arbitrary SA (say SA = [I 0]T) and an initial sequence of bit vectors B (B is a matrix of bit vectors), a LAS/LMLAS detector searches out a new sequence of bit vectors that is guaranteed to have increased likelihood due to the likelihood ascent property of the LAS/LMLAS detector [9][12]. The new sequence of bit vectors is used to generate a new matrix SA by means of the LS projection. Since the noise before the matched filter bank is white Gaussian, the LS projection is in the maximum likelihood sense. Therefore, the LS projection also increases the likelihood. Hence, by repeating the alternate LAS/LMLAS and LS operations, a sequence of B and a sequence of SA are generated, which monotonically increases likelihood of SAB. It is clear that the monotonic likelihood ascent in both operations implies the convergence in a finite number of iterations with probability one. When the noise is severe, a minimum mean square error (MMSE) filter can be used to replace the LS filter to mitigate noise. In the group-blind case, part of SA is known and a similar likelihood ascent search detector can be designed. Our preliminary simulations demonstrated that this group-blind detector outperformed the decorrelating based group-blind detectors. Convergence in a finite number of iterations was also observed in simulations. Simple analysis suggests that the LMLAS/LS detector converges to an LML point defined by the group-blind likelihood function. The characteristics of the LML point defined by the group-blind likelihood function will also be studied in this project.
In the current version, both families of LAS detectors and LMLAS detectors are set up for Gaussian CDMA channels. They are applicable to “one-shot” data. For multipath fading channels, bit vectors are correlated and the “one-shot” signal model is invalid. If data block is small, an entire block of data can also be formed similarly to the “one-shot” model but with increased matrix size. In the case of long data stream, the LAS and the LMLAS detectors must be adaptively implemented. A consideration is to perform LAS or LMLAS search in a moving window. After a LAS/LMLAS detector converges to a fixed point for the data in the window, the window is moved by a bit period so that a bit period data is moved out and a bit period data is moved in the window. The moving size can also be greater than one bit period. We will study this adaptive implementation of both families of LAS and LMLAS detectors and investigate their performance in multipath fading channels. If further the channel is time-varying, joint data detection and channel estimation with a moving window can be considered. Similarly to G, a LAS/LMLAS detector demodulates bit vectors in the window, and an adaptive filter estimates the channel parameters based on the demodulated bit vectors. In this way, the LAS/LMLAS detector combined with the adaptive filter constructs an adaptive blind LAS/LMLAS detector for joint bit vector detection and channel estimation. There have been many adaptive filters [70] such as RLS algorithm which can be used in this approach. In the proposed project, the adaptive blind LAS/LMLAS detectors will be investigated and compared with the blind and group-blind LAS/LMLAS detectors in G. Semi-blind detectors of this kind with a few training bits will also be investigated.
From , we can see [12] that the regions of multiple LML points are small as demonstrated by the shaded regions in Figs. 3-5. In other words, most of the observation space yields only the GML point (i.e., there is no other LML point) where a low-complexity LAS/LMLAS detector can perform equally well as the NP-hard GML detector. Thus, the GML detection can be achieved with considerably reduced computational complexity if the GML detector operates inside the region of multiple LML points while an LML detector (like the LAS and LMLAS detectors) operates outside the region of multiple LML points. To further simplify computation a suboptimal tree-search detector such as M- and T-algorithms can be used instead of the GML detector to achieve near-optimum low-complexity detection. In the proposed project, we will find an easy way to roughly determine if an observation r is inside the region of multiple LML points. For example, consider the LML region defined with neighborhood size one. We can set up some thresholds for components of r based on known RA to determine the region. Preliminary study on the combinations of LML detectors and tree-search detectors [64] demonstrated promising results. J.Criteria for determination of more acceptable vector Given an initial bit vector, a LAS detector or an LMLAS detector can automatically search out a new bit vector with guaranteed increased likelihood. Repeating the search, the LAS/LMLAS detector generates a sequence of bit vectors with monotonic likelihood ascent. In general, in a search step there exist many bit vectors that have greater likelihood than the current bit vector. Different choice of these acceptable bit vectors leads the search along a different trajectory to a different finally demodulated bit vector. The eliminate-highest-error (EHE) and fastest-metric-descent (FMD) criteria [63][64] are examples of such criteria for the choice of acceptable bit vectors. The EHE and FMD criteria were originally proposed by this applicant in [55][56] for image restoration and then thoroughly studied in [59][60], and preliminarily applied to CDMA multiuser detection in [63][64] for sequential LAS detectors. Simulations therein demonstrated considerable improvement on error performance in all cases. However, its application to the entire family of LAS detectors and the family of LMLAS detectors has not been studied yet. In this project, the EHE and FMD criteria will be thoroughly analyzed in the framework of CDMA multiuser detection. Its application to the family of LAS detectors and the family of LMLAS detectors will be studied. Other similar criteria will also be developed and studied. It is possible to develop a criterion jointly with optimum power control in E. The criterion of demodulating bits according to the order of users’ powers and order of SNR which are used in the decision-driven detectors [14] will also be studied as comparison. K.Other implementation problems In the current version, the both families of LAS and LMLAS detectors are designed for symbol of 1’s. Raphaeli [50] demonstrated a set of EM based algorithms that employ QPSK symbols. The SAGE algorithm with the QPSK symbols is in this set. The SAGE algorithm is also a LAS detector. In this project, we will investigate the extension of the both families of LAS and LMLAS detectors from the symbol of 1’s to QPSK and other modulation symbols. In the current version, the family of LMLAS detectors is not optimized in terms of minimization of computational complexity though they achieve the LML detection with an arbitrary neighborhood size. This is why in Fig. 2 (b) the LMLAS detector with neighborhood size six is more complex than the GML detector which was optimized in computational complexity. This also suggests the potential to reduce the computational complexity of the LMLAS detectors. In this project, we will study the other search rules so that the ratio of performance to computational complexity is higher than the current version of the LMLAS detectors. The applications of the families of LAS and LMLAS detectors to OFDM, multicarrier CDMA, frequency-hop CDMA, broadband and multirate data, and space-time coded or turbo coded data will also be investigated. Directory: www -> web www -> Integer programming and game theory www -> Dsci 3870: Management Science www -> H1N1 Pandemic 21-393 Fall 2009 www -> Chapter 9 Integer Programming Learning Objectives www -> Mixed-Integer Nonlinear Programming Techniques for Process Systems Engineering www -> Ieor 4600 Mixed-Integer Rounding Inequalities www -> Math 4630/5630 Homework 4 Solutions Problem Solving ip Download 129.87 Kb. Share with your friends:
|
, for k L(t). 
, r K 
is the neighborhood of 
with size J and ||b 
hyperplanes. The value 
and 
where k(t) is the current interference plus noise and 
. k(t) is contributed by the interfering bits (we call them the direct interfering users in [9]) that are updated at the same step as the bit of interest. Clearly, the direct interfering users play a more important role in the bit flip conditions than the other interfering users, and thus play a more important role in fixed point region (decision region), error probability, and expected computational complexity. We expect from our preliminary study that as k(t) increases (by increasing the number of bits updated at a step), the decision region expands, error probability increases, and computational complexity decreases. We will rigorously analyze these roles of the direct interfering users.