In this thesis we have presented an implementation of soft Multi Input Multi Output (MIMO) detection, single tree search algorithm on Graphics Processing Units (GPUs). We have compared its performance on different GPUs and a Central Processing Unit (CPU). We have also done a performance study of iterative decoding algorithms. We have shown that by increasing the number of outer iterations error rate performance can be further improved. GPUs are specialized devices specially designed to accelerate graphics processing. They are massively parallel devices which can run thousands of threads simultaneously. Because of their tremendous processing power there is an increasing interest in using them for scientific and general purpose computations. Hence companies like Nvidia, Advanced Micro Devices (AMD) etc. have started their support for General Purpose GPU (GPGPU) applications. Nvidia came up with Compute Unified Device Architecture (CUDA) to program its GPUs. Efforts are made to come up with a standard language for parallel computing that can be used across platforms. OpenCL is the first such language which is supported by all major GPU and CPU vendors. MIMO detector has a high computational complexity. We have implemented a soft MIMO detector on GPUs and studied its throughput and latency performance. We have shown that a GPU can give throughput of up to 4Mbps for a soft detection algorithm which is more than sufficient for most general purpose tasks like voice communication etc. Compare to CPU a throughput increase of ~7x is achieved. We also compared the performances of two GPUs one with low computational power and one with high computational power. These comparisons show effect of thread serialization on algorithms with the lower end GPU's execution time curve shows a slope of 1/2. To further improve error rate performance iterative decoding techniques are employed where a feedback path is employed between detector and decoder. With an eye towards GPU implementation we have explored these algorithms. Better error rate performance however, comes at a price of higher power dissipation and more latency. By simulations we have shown that one can predict based on the Signal to Noise Ratio (SNR) values how many iterations need to be done before getting an acceptable Bit Error Rate (BER) and Frame Error Rate (FER) performance. Iterative decoding technique shows that a SNR gain of ~1:5dB is achieved when number of outer iterations is increased from zero. To reduce the complexity one can adjust number of possible candidates the algorithm can generate. We showed that where a candidate list of 128 is not sufficient for acceptable error rate performance for a 4x4 MIMO system using 16-QAM modulation scheme, performances are comparable with the list size of 512 and 1024 respectively.

In this dissertation a computationally efficient cognitive multiple-input multiple-output (MIMO) orthogonal frequency division duplexing (OFDM) detector is designed to decode perfect space-time coded signals which are able maximize the diversity and multiplexing properties of a rich fading MIMO channel. The adaptive nature of the cognitive detector allows a MIMO OFDM communication system to better meet to needs of future wireless communication networks which require both high reliability and low run-time complexity depending on the propagation environment. The cognitive detector in conjunction with perfect space-time coding is able to achieve up to a 2 dB bit-error rate (BER) improvement at low signal-to-noise ratio (SNR) while also achieving comparable runtime complexity in high SNR scenarios.

With the wide spread of wireless technology, the time for 4G has arrived, and 5G will appear not so far in the future. However, no matter whether it is 4G or 5G, low latency is a mandatory requirement for baseband processing at base stations for modern cellular standards. In particular, in a future 5G wireless system, with massive MIMO and ultra-dense cells, the demand for low round trip latency between the mobile device and the base station requires a baseband processing delay of 1 ms. This is 10 percentage of today’s LTE-A round trip latency, while at the same time massive MIMO requires large-scale matrix computations. This is especially true for channel estimation and MIMO detection at the base station. Therefore, it is essential to ensure low latency for the user data traffic. In this master’s thesis, LTE/LTE-A uplink physical layer processing is examined, especially the process of channel estimation and MIMO detection. In order to analyze this processing we compare two conventional algorithms’ performance and complexity for channel estimation and MIMO detection. The key aspect which affects the algorithms’ speed is identified as the need for “massive complex matrix inversion”. A parallel coding scheme is proposed to implement a matrix inversion kernel algorithm on a single instruction multiple data stream (SIMD) vector processor. The major contribution of this thesis is implementation and evaluation of a parallel massive complex matrix inversion algorithm. Two aspects have been addressed: the selection of the algorithm to perform this matrix computation and the implementation of a highly parallel version of this algorithm. / Med den breda spridningen av trådlös teknik, har tiden för 4G kommit, och 5G kommer inom en överskådlig framtid. Men oavsett om det gäller 4G eller 5G, låg latens är ett obligatoriskt krav för basbandsbehandling vid basstationer för moderna mobila standarder. I synnerhet i ett framtida trådlöst 5G-system, med massiva MIMO och ultratäta celler, behövs en basbandsbehandling fördröjning på 1 ms för att klara efterfrågan på en låg rundresa latens mellan den mobila enheten och basstationen. Detta är 10 procent av dagens LTE-E rundresa latens, medan massiva MIMO samtidigt kräver storskaliga matrisberäkningar. Detta är särskilt viktigt för kanaluppskattning och MIMO-detektion vid basstationen. Därför är det viktigt att se till att det är låg latens för användardatatrafik. I detta examensarbete, skall LTE/LTE-A upplänk fysiska lagret bearbetning undersökas, och då särskilt processen för kanaluppskattning och MIMO-detektion. För att analysera denna processing jämför vi två konventionella algoritmers prestationer och komplexitet för kanaluppskattning och MIMO-detektion. Den viktigaste aspekten som påverkar algoritmernas hastighet identifieras som behovet av "massiva komplex matrisinversion". Ett parallellt kodningsschema föreslås för att implementera en "matrisinversion kernel-algoritmen" på singelinstruktion multidataström (SIMD) vektorprocessor. Det största bidraget med denna avhandling är genomförande och utvärdering av en parallell massiva komplex matrisinversion kernel-algoritmen. Två aspekter har tagits upp: valet av algoritm för att utföra denna matrisberäkning och implementationen av en högst parallell version av denna algoritm.

As the world becomes more globalised, user equipment such as smartphones and Internet of Things devices require increasingly more data, which increases the demand for wireless data traffic. Hence, the acceleration of next-generational networks (5G and beyond) focuses mainly on increasing the bitrate and decreasing the latency. A crucial technology for 5G and beyond is the massive MIMO. In a massive MIMO system, a detector processes the received signals from multiple antennas to decode the transmitted data and extract useful information. This has been implemented in many ways, and one of the most used algorithms is the Zero Forcing (ZF) algorithm. This thesis presents a novel parallel design to accelerate the ZF algorithm using the Cholesky decomposition. This is implemented on a GPU, written in the CUDA programming language, and compared to the existing state-of-the-art implementations regarding latency and throughput. The implementation is also validated from a MATLAB implementation. This research demonstrates promising performance using GPUs for massive MIMO detection algorithms. Our approach achieves a significant speedup factor of 350 in comparison to a serial version of the implementation. The throughput achieved is 160 times greater than a comparable GPU-based approach. Despite this, our approach reaches a 2.4 times lower throughput than a solution that employed application-specific hardware. Given the promising results, we advocate for continued research in this area to further optimise detection algorithms and enhance their performance on GPUs, to potentially achieve even higher throughput and lower latency. / <p>Our examiner Mahdi wants to wait six months before the thesis is published. </p>

The Hilbert space of probability mass functions (pmf) is introduced in this thesis. A factorization method for multivariate pmfs is proposed by using the tools provided by the Hilbert space of pmfs. The resulting factorization is special for two reasons. First, it reveals the algebraic relations between the involved random variables. Second, it determines the conditional independence relations between the random variables. Due to the first property of the resulting factorization, it can be shown that channel decoders can be employed in the solution of probabilistic inference problems other than decoding. This approach might lead to new probabilistic inference algorithms and new hardware options for the implementation of these algorithms. An example of new inference algorithms inspired by the idea of using channel decoder for other inference tasks is a multiple-input multiple-output (MIMO) detection algorithm which has a complexity of the square-root of the optimum MIMO detection algorithm. Keywords: The Hilbert space of pmfs, factorization of pmfs, probabilistic inference, MIMO detection, Markov random fields iv

The efficient high-throughput VLSI implementation of Soft-output MIMO detectors for high-order constellations and large antenna configurations has been a major challenge in the literature. This thesis introduces a novel Soft-output K-Best scheme that improves BER performance and reduces the computational complexity significantly by using three major improvement ideas. It also presents an area and power efficient VLSI implementation of a 4x4 64-QAM Soft K-Best MIMO detector that attains the highest detection throughput of 2 Gbps and second lowest energy/bit reported in the literature, fulfilling the aggressive requirements of emerging 4G standards such as IEEE 802.16m and LTE-Advanced. A low-complexity and highly parallel algorithm for QR Decomposition, an essential channel pre-processing task, is also developed that uses 2D, Householder 3D and 4D Givens Rotations. Test results for the QRD chip, fabricated in 0.13um CMOS, show that it attains the lowest reported latency of 144ns and highest QR Processing Efficiency.

The efficient high-throughput VLSI implementation of Soft-output MIMO detectors for high-order constellations and large antenna configurations has been a major challenge in the literature. This thesis introduces a novel Soft-output K-Best scheme that improves BER performance and reduces the computational complexity significantly by using three major improvement ideas. It also presents an area and power efficient VLSI implementation of a 4x4 64-QAM Soft K-Best MIMO detector that attains the highest detection throughput of 2 Gbps and second lowest energy/bit reported in the literature, fulfilling the aggressive requirements of emerging 4G standards such as IEEE 802.16m and LTE-Advanced. A low-complexity and highly parallel algorithm for QR Decomposition, an essential channel pre-processing task, is also developed that uses 2D, Householder 3D and 4D Givens Rotations. Test results for the QRD chip, fabricated in 0.13um CMOS, show that it attains the lowest reported latency of 144ns and highest QR Processing Efficiency.

Multi-antenna wireless systems have become very popular due to their theoretically predicted higher spectral efficiencies and improved performance compared to single-antenna systems. Large-scale multiple-input multiple-output (MIMO) systems refer to wireless systems where communication terminals employ tens to hundreds of antennas to achieve in-creased spectral efficiencies/sum rates, reliability, and power efficiency. Large-scale multi-antenna systems are attractive to meet the increasing wireless data rate requirements, without compromising on the bandwidth. This thesis addresses key signal processing issues in large-scale MIMO systems. Specifically, the thesis investigates efficient algorithms for signal detection and channel estimation in large-scale MIMO systems. It also investigates ‘spatial modulation,’ a multi-antenna modulation scheme that can reduce the number of transmit radio frequency (RF) chains, without compromising much on the spectral efficiency. The work reported in this thesis is comprised of the following two parts: 1 investigation of low-complexity receiver algorithms based on Markov chain Monte Carlo (MCMC) technique, tabu search, and belief propagation for large-scale uplink multiuser MIMO systems, and 2 investigation of achievable rates and signal detection in generalized spatial modulation. 1. Receiver algorithms for large-scale multiuser MIMO systems on the uplink In this part of the thesis, we propose low-complexity algorithms based on MCMC techniques, Gaussian sampling based lattice decoding (GSLD), reactive tabu search (RTS), and factor graph based belief propagation (BP) for signal detection on the uplink in large-scale multiuser MIMO systems. We also propose an efficient channel estimation scheme based on Gaussian sampling. Markov chain Monte Carlo (MCMC) sampling: We propose a novel MCMC based detection algorithm, which achieves near-optimal performance in large dimensions at low complexities by the joint use of a mixed Gibbs sampling (MGS) strategy and a multiple restart strategy with an efficient restart criterion. The proposed mixed Gibbs sampling distribution is a weighted mixture of the target distribution and uniform distribution. The presence of the uniform component in the sampling distribution allows the algorithm to exit from local traps quickly and alleviate the stalling problem encountered in conventional Gibbs sampling. We present an analysis for the optimum choice of the mixing ratio. The analysis approach is to define an absorbing Markov chain and use its property regarding the expected number of iterations needed to reach the global minima for the first time. We also propose an MCMC based algorithm which exploits the sparsity in uplink multiuser MIMO transmissions, where not all users are active simultaneously. Gaussian sampling based lattice decoding: Next, we investigate the problem of searching the closest lattice point in large dimensional lattices and its use in signal detection in large-scale MIMO systems. Specifically, we propose a Gaussian sampling based lattice decoding (GSLD) algorithm. The novelty of this algorithm is that, instead of sampling from a discrete distribution as in Gibbs sampling, the algorithm iteratively generates samples from a continuous Gaussian distribution, whose parameters are obtained analytically. This makes the complexity of the proposed algorithm to be independent of the size of the modulation alpha-bet. Also, the algorithm is able to achieve near-optimal performance for different antenna and modulation alphabet settings at low complexities. Random restart reactive tabu search (R3TS): Next, we study receiver algorithms based on reactive tabu search (RTS) technique in large-scale MIMO systems. We propose a multiple random restarts based reactive tabu search (R3TS) algorithm that achieves near-optimal performance in large-scale MIMO systems. A key feature of the proposed R3TS algorithm is its performance based restart criterion, which gives very good performance-complexity tradeoff in large-dimension systems. Lower bound on maximum likelihood (ML) bit error rate (BER) performance: We propose an approach to obtain lower bounds on the ML performance of large-scale MIMO systems using RTS simulation. In the proposed approach, we run the RTS algorithm using the transmitted vector as the initial vector, along with a suitable neighborhood definition, and find a lower bound on number of errors in ML solution. We demonstrate that the proposed bound is tight (within about 0.5 dB of the optimal performance in a 16×16MIMO system) at moderate to high SNRs. Factor graph using Gaussian approximation of interference (FG-GAI): Multiuser MIMO channels can be represented by graphical models that are fully/densely connected (loopy graphs), where conventional belief propagation yields suboptimal performance and requires high complexity. We propose a solution to this problem that uses a simple, yet effective, Gaussian approximation of interference (GAI) approach that carries out a linear per-symbol complexity message passing on a factor graph (FG) based graphical model. The proposed algorithm achieves near-optimal performance in large dimensions in frequency-flat as well as frequency-selective channels. Gaussian sampling based channel estimation: Next, we propose a Gaussian sampling based channel estimation technique for large-scale time-division duplex (TDD) MIMO systems. The proposed algorithm refines the initial estimate of the channel by iteratively detecting the data block and using that knowledge to improve the estimated channel knowledge using a Gaussian sampling based technique. We demonstrate that this algorithm achieves near-optimal performance both in terms of mean square error of the channel estimates and BER of detected data in both frequency-flat and frequency-selective channels. 2. Generalized spatial modulation In the second part of the thesis, we investigate generalized spatial modulation (GSM) in point-to point MIMO systems. GSM is attractive because of its ability to work with less number of transmit RF chains compared to traditional spatial multiplexing, without com-promising much on spectral efficiency. In this work, we show that, by using an optimum combination of number of transmit antennas and number of transmit RF chains, GSM can achieve better throughput and/or BER than spatial multiplexing. We compute tight bounds on the maximum achievable rate in a GSM system, and quantify the percentage savings in the number of transmit RF chains as well as the percentage increase in the rate achieved in GSM compared to spatial multiplexing. We also propose a Gibbs sampling based algorithm suited to detect GSM signals, which yields impressive BER performance and complexity results.

The Fifth Generation (5G) mobile communication system is the latest technology in wireless communications. This technique brings several advantages, in particular by using multiple receiver antennas that serve multiple transmitters. This configuration used in 5G is called Massive Multiple Input Multiple Output (MIMO), and it increases link reliability and information throughput. However, MIMO systems face two challenges at link layer: channel estimation and MIMO detection. In this work, the focus is only on the MIMO detection problem. It consists in retrieving the original messages, sent by the transmitters, at the receiver side when the received message is a noisy signal. The optimal technique to solve the problem is called Maximum Likelihood (ML), but it does not scale and therefore with MIMO systems it cannot be used. Several sub-optimal techniques have been tested during years in order to solve MIMO detection problem, trying to balance the complexity-performance trade-off. In recent years, Approximate Message Passing (AMP) based techniques brought interesting results. Moreover, deep learning (DL) is spreading in several and different fields, and also in MIMO detection, it has been tested with promising results. A neural network called MMNet brought the most interesting results, but new techniques have been developed. These new techniques, despite they are promising, have not been compared with MMNet. In this thesis, two new techniques AMP and DL based, called Ortoghonal AMP Network Second (OAMP-Net2) and Learnable Vector AMP (LVAMP), have been tested and compared with the state of art. The aim of the thesis is to discover if one or both the techniques can provide better results than MMNet, in order to discover a valid alternative solution while dealing with MIMO detection problem. OAMP-Net2 and LVAMP have been developed and tested on different channel models (i.i.d. Gaussian and Kronecker) and on MIMO systems of different sizes (small and medium-large). OAMP-Net2 revealed to be a consistent technique that can be used in solving MIMO detection problem. It provides interesting results on both i.i.d Gaussian and Kronecker channel models and with different sizes matrices. Moreover, OAMP-Net2 has good adaptability, in fact it provides good results on Kronecker channel models also when it is trained with i.i.d. Gaussian matrices. LVAMP instead has performances that are similar to MMSE, but with a lower complexity. It adapts well to complex channels such as OAMP-Net2. / Femte generationens (5G) mobila kommunikationssystem är den senaste tekniken inom trådlös kommunikation. Denna teknik ger flera fördelar, i synnerhet genom att använda flera mottagarantenner som betjänar flera sändare. Denna konfiguration som används i 5G kallas Massive Multiple Input Multiple Output (MIMO), och den ökar länktillförlitligheten och informationsgenomströmningen. MIMO-system står dock inför två utmaningar i länkskiktet: kanaluppskattning och MIMO-detektering. I detta arbete ligger fokus endast på MIMO-detekteringsproblemet. Den består i att hämta de ursprungliga meddelandena, skickade av sändarna, på mottagarsidan när det mottagna meddelandet är en brusig signal. Den optimala tekniken för att lösa problemet kallas Maximum Likelihood (ML), men den skalas inte och därför kan den inte användas med MIMO-system. Flera suboptimala tekniker har testats under flera år för att lösa MIMO-detekteringsproblem och försöka balansera komplexitet-prestanda-avvägningen. Under de senaste åren har Approximate Message Passing (AMP)-baserade tekniker gett intressanta resultat. Dessutom sprids djupinlärning (DL) inom flera och olika områden, och även inom MIMO-detektering har det testats med lovande resultat. Ett neuralt nätverk kallat MMNet gav de mest intressanta resultaten, men nya tekniker har utvecklats. Dessa nya tekniker, trots att de är lovande, har inte jämförts med MMNet. I detta examensarbete har två nya tekniker AMP- och DL-baserade, kallade Ortoghonal AMP Network Second (OAMP-Net2) och Learnable Vector AMP (LVAMP), testats och jämförts med den senaste tekniken. Syftet med avhandlingen är att ta reda på om en eller båda teknikerna kan ge bättre resultat än MMNet, för att upptäcka en giltig alternativ lösning samtidigt som man hanterar MIMO-detekteringsproblem. OAMP-Net2 och LVAMP har utvecklats och testats på olika kanalmodeller (i.i.d. Gaussian och Kronecker) och på MIMO-system av olika storlekar (small och medium-large).OAMP-Net2 visade sig vara en konsekvent teknik som kan användas för att lösa MIMO-detekteringsproblem. Det ger riktigt intressanta resultat på både i.i.d Gaussian och Kronecker kanalmodeller och med matriser i olika storlekar. Dessutom har OAMP-Net2 god anpassningsförmåga, faktiskt ger den bra resultat på Kronecker kanalmodeller även när den tränas med i.i.d. Gaussiska matriser. LVAMP har istället prestanda som liknar MMSE, men med lägre komplexitet. Den anpassar sig väl till komplexa kanaler somOAMPNet2.

Ce travail présente deux contributions clés dans le domaine des réseaux de communication sans fil 4G+/5G, en particulier dans le domaine de la détection MIMO d’ordre supérieur et le design (conception) de réseau relai semi-duplex. La première partie de ce travail de recherche s’intéresse au développement d’une stratégie de détection MIMO d’ordre supérieur pour les terminaux 4G+/5G existants et futurs, d’un point de vue à la fois théorique et pratique. Une nouvelle technique de décomposition QR Bloc de prétraitement est proposée pour un récepteur LTE dans un scénario limité à un seul utilisateur, interférence limitée, ainsi qu’un scénario point par point dont les résultats surlignent les avantages et inconvénients en performance et complexité. La deuxième partie de cette étude comprend une étude de faisabilité d’une stratégie de message novatrice à deux phases et trois parties pour un réseau relai semi-duplex à couche physique, qui comporte un codage de superposition et un décodage d’annulation d’interférence successif, conscient des interférences. Un point clé de cette étude était d’analyser la performance du schéma d’adaptation des liaisons proposées dans le régime non asymptotique et d’évaluer l’efficacité spectrale (ES) par rapport aux hypothèses théoriques des blocs d’asymptotiquement grandes longueurs. Une comparaison ES supplémentaire est également présentée, avec une transmission de relais à deux étapes non coopérative et une stratégie de transmission point à point. Les résultats obtenus révèlent les gains d'ES qui peuvent être obtenus en exploitant la coopération de couche physique entre le relais et la station de base. / The evolution of wireless communication networks has always been rapidly progressive partly due to the demands of today’s data hungry users. This dissertation presents two key contributions to the body of knowledge in the evolving area of physical layer 4G+/5G communication technologies, especially in the domain of Higher-order MIMO detection and half-duplex relay network design. The initial part of this research investigates the development of a higher-order MIMO detection strategy for existing and future 4G+/5G receivers, from both a theoretical and practical perspective. A novel pre-processing Block QR decomposition technique has been proposed for an LTE receiver in a single-user interference-limited scenario as well as a point-to-point scenario with the results highlighting the complexity advantages and limitations in performance. The second part of this study involves a practical feasibility study of a novel two-phase three-part-message strategy for a physical layer half-duplex relay network, which features superposition coding and interference-aware successive interference cancellation decoding. A key aim of this study was to analyze the performance of the proposed link adaptation scheme in the non-asymptotic regime (finite block-length and discrete constellation signaling), and evaluate the spectral efficiency (SE) against the theoretical assumptions of asymptotically large block-lengths. An additional SE comparison with a non-cooperative two-hop relay transmission and point-to-point transmission strategy is also presented. The resulting outcomes reveal the SE gains that can be had by exploiting physical layer cooperation between the relay and base station.