In wireless communication, MIMO (multiple input multiple output) is one of the promising technologies which improves the range and performance of transmission without increasing the bandwidth, while providing high rates. High speed hardware MIMO decoders are one of the keys to apply this technology in applications. In order to support the high data rates, the underlying hardware must have significant processing capabilities. FPGA improves the speed of signal processing using parallelism and reconfigurability advantages. The objective of this thesis is to develop an efficient hardware architectural model for the universal lattice decoder and prototype it on FPGA. The original algorithm is modified to ensure the high data rate via taking the advantage of FPGA features. The simulation results of software, hardware are verified and the BER performance of both the algorithms is estimated. The system prototype of the decoder with 4-transmit and 4-receive antennas using a 4-PAM (Pulse amplitude modulation) supports 6.32 Mbit/s data rate for parallelpipeline implementation on FPGA platform, which is about two orders of magnitude faster than its DSP implementation.

No description available.

<p> Solving the integer least squares problem min ||Hs- x|| 2 , where the unknown vector s is comprised of integers, the coefficient matrix H and given vector x are comprised of real numbers arises in many applications and is equivalent to find the closest lattice point to a given one known as NP-hard. In multiple antenna systems, the received signal represented by vector xis not arbitrary, but an lattice point perturbed by an additive noise vector whose statistical properties are known. It has been shown the Sphere Decoding, in which the lattice points inside a hyper-sphere are generated and the closest lattice point to the received signal is determined, together with Maximum Likelihood (ML) method often yields a near-optimal performance on average (cubic) while the worst case complexity is still exponential. By using lattice basis reduction as pre-processing step in the sub-optimum decoding algorithms, we can show that the lattice reduction aided sphere decoding (LRSD) achieves a better performance than the maximum likelihood sphere decoding (MLSD) in terms of symbol error rate (SER) and average algorithm running time. In the FIR (Finite Impulse Response) MIMO channel, the channel matrix is Toeplitz and thus gives us the leverage to use the fact that all its column vectors all linearly independent and the matrix itself is often well-conditioned. </p> <p> In this thesis, we will develop a lattice reduction added sphere decoding algorithm along with an improved LLL algorithm, and provide the simulations to show that this new algorithm achieves a better performance than the maximum likelihood sphere decoding. </p> <p> In chapter 1, we define our system model and establish the foundations for understanding of mathematical model - namly the integer least squares problem, and thus the choice of the simulation data. In chapter 2, we explain the integer least squares problems and exploit serveral ways for solving the problems, then we introduce the sphere decoding and maximum likelihood at the end. In chapter 3, we explore the famous LLL reduction algorithm named after Lenstra, Lenstra and Lovasz in details and show an example how to break Merkle-Hellman code using the LLL reduction algorithm. Finally, in chapter 4 we give the LLL reduction aided sphere decoding algorithm and the experiment setup as well as the simulation results against the MLSD and conclusions, further research directions. </p> / Thesis / Master of Science (MSc)

Dans cette thèse, nous présentons nos travaux dans le domaine des algorithmes de décodage des codes LDPC non-binaires généralisés. Les codes LDPC binaires ont été initialement proposés par Gallager en 1963, et après quelques avancées théoriques fondamentales, ils ont été proposés dans des standards tels que DVB-S2, WI-MAX, DSL, W-LAN etc. Plus tard, les codes LDPC non-binaires (NB-LDPC) ont été pro- posés dans la littérature, et ont montré une meilleure performance pour de petites tailles de code ou lorsqu'ils sont utilisés sur des canaux non-binaires. Cependant, les avan- tages de l'utilisation de codes NB-LDPC impliquent une augmentation importante de la complexité de décodage. Pour un code défini dans un corps de Galois GF (q), la complexité est d'ordre O (q2). De même, la mémoire requise pour le stockage des messages est d'ordre O (q). Ainsi, l'implémentation d'un décodeur LDPC défini sur un corps de Galois pour q > 64 devient impossible dans la pratique. L'objectif prin- cipal de cette thèse est de développer des algorithmes avec une bonne performance et complexité réduite de sorte qu'ils deviennent implémentables. Pour une performance de décodage optimisée, non seulement l'algorithme est important, mais également la structure du code joue un rôle clé. Avec cet objectif à l'esprit, une nouvelle famille de codes appelés " cluster-NB-LDPC codes " a été élaborée ainsi que des améliorations spécifiques du décodeur non-binaire pour ces codes. Le résultat principal est que nous avons pu proposer des décodeurs pour les codes cluster-NB-LDPC avec une complex- ité réduite par rapport aux décodeurs classiques pour les codes NB-LDPC définis sur les corps de Galois, sans aucune perte de performance dans la capacité de correction vi Résumé d'erreur. Dans la première partie de la thèse, nous avons modifié l'algorithme EMS pour les cluster-codes. La généralisation directe de l'algorithme EMS aux codes cluster-NB- LDPC n'est pas réaliste . Il y a une perte de performance et une augmentation de la complexité. Par conséquent, nous proposons quelques modifications dans la procé- dure, qui non seulement améliore considérablement les performances de décodage, mais diminue également la complexité. Au niveau des noeuds de parité, cet algo- rithme conserve les mêmes limites sur le nombre d'opérations que l'algorithme EMS pour GF (q)-codes, O (nmlognm) avec nm << q. Nous proposons ensuite une autre méthode, basée sur la diversité des codes cluster, afin d'améliorer les performances de l'algorithme EMS pour les codes cluster-LDPC. Il contribue également à réduire la complexité globale du décodeur. Finalement, nous comparons les performances de décodage en utilisant cette méthode et analysons l'effet sur la complexité de décodage. Dans la dernière partie du chapitre, nous proposons une nouvelle direction pour le décodage des codes LDPC. Elle est basée sur la création des listes des mots de code qui correspondent à des noeuds de parité. Les listes sont construite de manière récur- sive dans une structure en arbre, ce qui en fait un bon candidat pour l'implémentation matérielle. Il s'agit d'une méthode nouvelle et doit encore être améliorée mais à pre- miére vue nous avons obtenu de bons résultats avec un nombre réduit d'operations.

We investigate into the limitations of the sum-product algorithm for binary low density parity check (LDPC) codes having isolated short cycles. Independence assumption among messages passed, assumed reasonable in all configurations of graphs, fails the most in graphical structures with short cycles. This research work is a step forward towards understanding the effect of short cycles on error floors of the sum-product algorithm. We propose a modified sum-product algorithm by considering the statistical dependency of the messages passed in a cycle of length 4. We also formulate a modified algorithm in the log domain which eliminates the numerical instability and precision issues associated with the probability domain. Simulation results show a signal to noise ratio (SNR) improvement for the modified sum-product algorithm compared to the original algorithm. This suggests that dependency among messages improves the decisions and successfully mitigates the effects of length-4 cycles in the Tanner graph. The improvement is significant at high SNR region, suggesting a possible cause to the error floor effects on such graphs. Using density evolution techniques, we analysed the modified decoding algorithm. The threshold computed for the modified algorithm is higher than the threshold computed for the sum-product algorithm, validating the observed simulation results. We also prove that the conditional entropy of a codeword given the estimate obtained using the modified algorithm is lower compared to using the original sum-product algorithm.