Spelling suggestions: "subject:"definite relaxation"" "subject:"indefinite relaxation""
1 |
Soft Demodulation Schemes for MIMO Communication SystemsNekuii, Mehran 08 1900 (has links)
In this thesis, several computationally-efficient approximate soft demodulation schemes are developed for multiple-input multiple-output (MIMO) communication systems. These soft demodulators are designed to be deployed in the conventional iterative receiver ('turbo') architecture, and they are designed to provide good performance at substantially lower computational cost than that of the exact soft demodulator. The proposed demodulators are based on the principle of list demodulation and can be classified into two classes, according to the nature of the list-generation algorithm. One class is based on a tree-search algorithm and the other is based on insight generated from the analysis of semidefinite relaxation techniques for hard demodulation.
The proposed tree-search demodulators are based on a multi-stack algorithm, developed herein, for efficiently traversing the tree structure that is inherent in the MIMO demodulation problem. The proposed scheme was inspired, in part, by the stack algorithm, which stores all the visited nodes in the tree in a single stack and chooses the next node to expand based on a 'best-first' selection scheme. The proposed algorithm partitions this global stack into a stack for each level of the tree. It examines the tree in the natural ordering of the levels and performs a best-first search in each of the stacks. By assigning appropriate priorities to the level at which the search for the next leaf node re-starts, the proposed demodulators can achieve performance-complexity trade-offs that dominate several existing soft demodulators, including those based on the stack algorithm and those based on 'sphere decoding' principles, especially in the low-complexity region.
In the second part of this thesis it is shown that the randomization procedure that is inherent in the semidefinite relaxation (SDR) technique for hard demodulation can be exploited to generate the list members required for list-based soft demodulation. The direct application of this observation yields list-based soft demodulators that only require the solution of one SDP per demodulation-decoding iteration. By approximating the randomization procedure by a set of independent Bernoulli trials, this requirement can be reduced to just one semidefinite program (SDP) per channel use. An advantage of these demodulators over those based on optimal tree-search algorithms is that the computational cost of solving the SDP is a low-order polynomial in the problem size. The analysis and simulation experiments provided in the thesis show that the proposed SDR-based demodulators offer an attractive trade-off between performance and computational cost.
The structure of the SDP in the proposed SDR-based demodulators depends on the signaling scheme, and the initial development focuses on the case of QPSK signaling. In the last chapter of this thesis, the extension to MIMO 16-QAM systems is developed, and some interesting observations regarding some existing SDR-based hard demodulation schemes for MIMO 16-QAM systems are derived. The simulation results reveal that the excellent performance-complexity trade-off of the proposed SDR-based schemes is preserved under the extension to 16-QAM signaling. / Thesis / Doctor of Philosophy (PhD)
|
2 |
Detection for multiple input multiple output channels : analysis of sphere decoding and semidefinite relaxationJaldén, Joakim January 2006 (has links)
The problem of detecting a vector of symbols, drawn from a finite alphabet and transmitted over a multiple-input multiple-output (MIMO) channel with Gaussian noise, is of central importance in digital communications and is encountered in several different applications. Examples include, but are not limited to; detection of symbols spatially multiplexed over a multiple-antenna channel and the multiuser detection problem in a code division multiple access (CDMA) system. Two algorithms previously proposed in the literature are considered and analyzed. Both algorithms have their origin in other fields of science but have gained mainstream recognition as efficient algorithms for the detection problem considered herein. Specifically, we consider the sphere decoder and semidefinite relaxation detector. By incorporating assumptions applicable in the communications context the performance of the two algorithms is addressed. The first algorithm, the sphere decoder, offers optimal performance in terms of its error probability. Further, the algorithm has proved extremely efficient in terms of computational complexity for moderately sized problems at high signal to noise ratio (SNR). Although it is recognized that the algorithm has an exponential worst case complexity, there has been a widespread belief that the algorithm has a polynomial average complexity at high SNR. A contribution made herein is to show that this is incorrect and that the average complexity, as the worst case complexity, is exponential in the number of symbols detected. Instead, another explanation of the observed efficiency of the algorithm is offered by deriving the exponential rate of growth and showing that this rate, although strictly positive for finite SNR, is small in the high SNR regime. The second algorithm, the semidefinite relaxation (SDR) detector, offers polynomial complexity at the expense of suboptimal performance in terms of error probability. Nevertheless, previous numerical observations suggest that error probability of the SDR algorithm is close to that of the optimal detector. Herein, the near optimality is of the SDR algorithm is given a precise meaning by studying the diversity of the SDR algorithm when applied to the (real valued) i.i.d.~Rayleigh fading channel and it is shown that the SDR algorithm achieves the same diversity order as the optimal detector. Further, criteria under which the SDR estimates coincide with the optimal estimates are derived and discussed. / Ett grundläggande problem som påträffats inom digital kommunikation är detektering av en symbolvektor, tillhörande ett ändligt symbolalfabet, som sänts över en MIMO (från engelskans multiple-input multiple-output) kanal med Gausiskt brus. Detta problem påträffas bland annat då symboler sänts över en trådlös kanal med flera antenner hos mottagaren och sändaren samt då flera användare i ett CDMA system simultant skall avkodas. In denna avhandling behandlas två mottagaralgoritmer konstruerade för detta ändamål. Algoritmerna har sin bakgrund i andra forskningsområden men kan i nuläget sägas vara mycket välkända inom kommunikationsområdet. De benämns vanligtvis som sfäravkodaren (eng. sphere decoder) samt den semidefinita relaxeringsdetektorn (eng. semidefinite relaxation detector). Algoritmerna analyseras i denna avhandling matematiskt genom att införa förenklande antaganden som är relevanta och applicerbara för de kommunikationsproblem som är av intesse. Den första algoritmen, sfäravkodaren, löser dessa detektionsproblem på ett optimalt sätt i betydelsen att den minimerar sannolikheten för att detektorn fattar ett felaktigt beslut rörande det sända meddelandet (symbolvektorn). Också vad gäller algoritmens komplexitet har simuleringar visat att den är oväntat låg, åtminstone vid höga signalbrusförhållanden (SNR). Trots att det är allmänt känt att algoritmen i sämsta fall har exponentiell komplexitet så har detta lett till den allmänt spridda uppfattningen att medelkomplexiteten (eller den förväntade komplexiteten) endast är polynomisk vid höga signalbrusförhållanden. Ett av huvudbidragen i denna avhandling är att visa att denna uppfattning är felaktig och att också medelkomplexiteten växer exponentiellt i antalet symboler som simultant detekteras. Ytterligare ett bidrag ligger i att ge en alternativ förklaring till den observerat låga medelkomplexiteten. Det visas att den exponentiella hastighet med vilken komplexiteten växer beror på signalbrusförhållande, och att den är låg för höga SNR. Den andra algoritmen, den semidefinita relaxeringsdetektorn, erbjuder polynomisk komplexitet vid en något högre felsannolikhet. Intressant nog har dock felsannolikheten tidigare, genom simuleringar, visat sig vara endast marginellt högre än felsannolikheten hos den optimala mottagaren. Bidraget som relaterar till den semidefinita relaxeringsmottagaren ligger i att både förklara och i att ge en specifik kvatifierbar mening åt uttalandet att felsannolikheten endast är marginellt högre. I syfte att åstadkomma detta studeras diversitetsordningen för detektorn, och det bevisas att diversitetsordningen för den semidefinita relaxeringsdetektorn är densamma som för den optimala mottagaren. Utöver detta karakteriseras också de krav som måste uppfyllas för att den detektorn skall finna den optimala lösningen. / QC 20100901
|
3 |
Joint beamforming, channel and power allocation in multi-user and multi-channel underlay MISO cognitive radio networksDadallage, Suren Tharanga Darshana 03 December 2014 (has links)
In this thesis, we consider joint beamforming, power, and channel allocation in a multi-user and multi-channel underlay cognitive radio network (CRN). In this system, beamforming is implemented at each SU-TX to minimize the co-channel interference. The formulated joint optimization problem is a non-convex, mixed integer nonlinear programming (MINLP) problem. We propose a solution which consists of two stages. At first, given a channel allocation, a feasible solutions for power and beamforming vectors are derived by converting the problem into a convex form with an introduced optimal auxiliary variable and semidefinite relaxation (SDR) approach. Next, two explicit searching algorithms, i.e., genetic algorithm (GA) and simulated annealing (SA)-based algorithm are proposed to determine optimal channel allocations. Simulation results show that beamforming, power and channel allocation with SA (BPCA-SA) algorithm achieves a close optimal sum-rate with a lower computational complexity compared with beamforming, power and channel allocation with GA (BPCA-GA) algorithm. Furthermore, our proposed allocation scheme shows significant improvement than zero-forcing beamforming (ZFBF).
|
4 |
Semidefinite Relaxation-Based Soft MIMO Demodulation via Efficient Dual ScalingSalmani, Mahsa January 2014 (has links)
<p>Soft multiple-input multiple-output (MIMO) demodulators are a core component of iterative receivers for MIMO communication systems that employ bit-interleaved coded modulation (BICM). The role of these demodulators is to extract a good approximation of the posterior likelihood of each bit transmitted at each channel use. The main challenge in designing a soft MIMO demodulator is to achieve the desired level of performance at a reasonable computational cost. This is important because in the case of a memoryless MIMO channel, the computational cost of the exact soft demodulator increases exponentially with the number of bits transmitted per channel use, and the cost grows faster in the case of the channels with memory.</p> <p>Several approximate low-complexity soft demodulators for memoryless channels have been proposed in the literature. In this thesis, we develop a low-complexity soft MIMO demodulator that is based on semidefinite relaxation (SDR) and uses the max-log approximation to reduce the cost of the demodulation. In particular, we develop a customized dual-scaling algorithm to solve the semidefinite program that constitutes the core computational task of the SDR-based soft demodulator. The computational cost per iteration of the customized dual algorithm is about half that of the existing customized primal-dual algorithm, and this leads to a reduction in the overall computational cost. We apply the customized dual-scaling algorithm to two different list-based soft demodulators, the list-SDR and single-SDR demodulators, and compare the performance, computational cost, and EXIT chart characteristics of these demodulators with other existing methods. This comparison shows that the developed demodulator provides a desirable trade-off between performance and complexity.</p> / Master of Applied Science (MASc)
|
5 |
Performance evaluation and enhancement for AF two-way relaying in the presence of channel estimation errorWang, Chenyuan 30 April 2012 (has links)
Cooperative relaying is a promising diversity achieving technique to provide reliable transmission, high throughput and extensive coverage for wireless networks in a variety of applications. Two-way relaying is a spectrally efficient protocol, providing one solution to overcome the half-duplex loss in one-way relay channels. Moreover, incorporating the multiple-input-multiple-output (MIMO) technology can further improve the spectral efficiency and diversity gain. A lot of related work has been performed on the two-way relay network (TWRN), but most of them assume perfect channel state information (CSI). In a realistic scenario, however, the channel is estimated and the estimation error exists. So in this thesis, we explicitly take into account the CSI error, and investigate its impact on the performance of amplify-and-forward (AF) TWRN where either multiple distributed single-antenna relays or a single multiple-antenna relay station is exploited.
For the distributed relay network, we consider imperfect self-interference cancellation at both sources that exchange information with the help of multiple relays, and maximal ratio combining (MRC) is then applied to improve the decision statistics under imperfect signal detection. The system performance degradation in terms of outage probability and average bit-error rate (BER) are analyzed, as well as their asymptotic trend. To further improve the spectral efficiency while maintain the spatial diversity, we utilize the maximum minimum (Max-Min) relay selection (RS), and examine the impact of imperfect CSI on this single RS scheme. To mitigate the negative effect of imperfect CSI, we resort to adaptive power allocation (PA) by minimizing either the outage probability or the average BER, which can be cast as a Geometric Programming (GP) problem. Numerical results verify the correctness of our analysis and show that the adaptive PA scheme outperforms the equal PA scheme under the aggregated effect of imperfect CSI.
When employing a single MIMO relay, the problem of robust MIMO relay design has been dealt with by considering the fact that only imperfect CSI is available. We design the MIMO relay based upon the CSI estimates, where the estimation errors are included to attain the robust design under the worst-case philosophy. The optimization problem corresponding to the robust MIMO relay design is shown to be nonconvex. This motivates the pursuit of semidefinite relaxation (SDR) coupled with the randomization technique to obtain computationally efficient high-quality approximate solutions. Numerical simulations compare the proposed MIMO relay with the existing nonrobust method, and therefore validate its robustness against the channel uncertainty. / Graduate
|
Page generated in 0.0845 seconds