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.

The theory of lattices --- a mathematical approach for representing infinite discrete points in Euclidean space, has become a powerful tool to analyze many point-to-point digital and wireless communication systems, particularly, communication systems that can be well-described by the linear Gaussian vector channel model. This is mainly due to the three facts about channel codes constructed using lattices: they have simple structure, their ability to achieve the fundamental limits (the capacity) of the channel, and most importantly, they can be decoded using efficient decoders called lattice decoders. Since its introduction to multiple-input multiple-output (MIMO) wireless communication systems, sphere decoders has become an attractive efficient implementation of lattice decoders, especially for small signal dimensions and/or moderate to large signal-to-noise ratios (SNRs). In the first part of this dissertation, we consider sphere decoding algorithms that describe lattice decoding. The exact complexity analysis of the basic sphere decoder for general space-time codes applied to MIMO wireless channel is known to be difficult. Characterizing and understanding the complexity distribution is important, especially when the sphere decoder is used under practically relevant runtime constraints. In this work, we shed the light on the (average) computational complexity of sphere decoding for the quasi-static, LAttice Space-Time (LAST) coded MIMO channel. Sphere decoders are only efficient in the high SNR regime and low signal dimensions, and exhibits exponential (average) complexity for low-to-moderate SNR and large signal dimensions. On the other extreme, linear and non-linear receivers such as minimum mean-square error (MMSE), and MMSE decision-feedback equalization (DFE) are considered attractive alternatives to sphere decoders in MIMO channels. Unfortunately, the very low decoding complexity advantage that these decoders can provide comes at the expense of poor performance, especially for large signal dimensions. The problem of designing low complexity receivers for the MIMO channel that achieve near-optimal performance is considered a challenging problem and has driven much research in the past years. The problem can solved through the use of lattice sequential decoding that is capable of bridging the gap between sphere decoders and low complexity linear decoders (e.g., MMSE-DFE decoder). In the second part of this thesis, the asymptotic performance of the lattice sequential decoder for LAST coded MIMO channel is analyzed. We determine the rates achievable by lattice coding and sequential decoding applied to such a channel. The diversity-multiplexing tradeoff under such a decoder is derived as a function of its parameter--- the bias term. In this work, we analyze both the computational complexity distribution and the average complexity of such a decoder in the high SNR regime. We show that there exists a cut-off multiplexing gain for which the average computational complexity of the decoder remains bounded. Our analysis reveals that there exists a finite probability that the number of computations performed by the decoder may become excessive, even at high SNR, during high channel noise. This probability is usually referred to as the probability of a decoding failure. Such probability limits the performance of the lattice sequential decoder, especially for a one-way communication system. For a two-way communication system, such as in MIMO Automatic Repeat reQuest (ARQ) system, the feedback channel can be used to eliminate the decoding failure probability. In this work, we modify the lattice sequential decoder for the MIMO ARQ channel, to predict in advance the occurrence of decoding failure to avoid wasting the time trying to decode the message. This would result in a huge saving in decoding complexity. In particular, we will study the throughput-performance-complexity tradeoffs in sequential decoding algorithms and the effect of preprocessing and termination strategies. We show, analytically and via simulation, that using the lattice sequential decoder that implements a simple yet efficient time-out algorithm for joint error detection and correction, the optimal tradeoff of the MIMO ARQ channel can be achieved with significant reduction in decoding complexity.

The theory of lattices --- a mathematical approach for representing infinite discrete points in Euclidean space, has become a powerful tool to analyze many point-to-point digital and wireless communication systems, particularly, communication systems that can be well-described by the linear Gaussian vector channel model. This is mainly due to the three facts about channel codes constructed using lattices: they have simple structure, their ability to achieve the fundamental limits (the capacity) of the channel, and most importantly, they can be decoded using efficient decoders called lattice decoders. Since its introduction to multiple-input multiple-output (MIMO) wireless communication systems, sphere decoders has become an attractive efficient implementation of lattice decoders, especially for small signal dimensions and/or moderate to large signal-to-noise ratios (SNRs). In the first part of this dissertation, we consider sphere decoding algorithms that describe lattice decoding. The exact complexity analysis of the basic sphere decoder for general space-time codes applied to MIMO wireless channel is known to be difficult. Characterizing and understanding the complexity distribution is important, especially when the sphere decoder is used under practically relevant runtime constraints. In this work, we shed the light on the (average) computational complexity of sphere decoding for the quasi-static, LAttice Space-Time (LAST) coded MIMO channel. Sphere decoders are only efficient in the high SNR regime and low signal dimensions, and exhibits exponential (average) complexity for low-to-moderate SNR and large signal dimensions. On the other extreme, linear and non-linear receivers such as minimum mean-square error (MMSE), and MMSE decision-feedback equalization (DFE) are considered attractive alternatives to sphere decoders in MIMO channels. Unfortunately, the very low decoding complexity advantage that these decoders can provide comes at the expense of poor performance, especially for large signal dimensions. The problem of designing low complexity receivers for the MIMO channel that achieve near-optimal performance is considered a challenging problem and has driven much research in the past years. The problem can solved through the use of lattice sequential decoding that is capable of bridging the gap between sphere decoders and low complexity linear decoders (e.g., MMSE-DFE decoder). In the second part of this thesis, the asymptotic performance of the lattice sequential decoder for LAST coded MIMO channel is analyzed. We determine the rates achievable by lattice coding and sequential decoding applied to such a channel. The diversity-multiplexing tradeoff under such a decoder is derived as a function of its parameter--- the bias term. In this work, we analyze both the computational complexity distribution and the average complexity of such a decoder in the high SNR regime. We show that there exists a cut-off multiplexing gain for which the average computational complexity of the decoder remains bounded. Our analysis reveals that there exists a finite probability that the number of computations performed by the decoder may become excessive, even at high SNR, during high channel noise. This probability is usually referred to as the probability of a decoding failure. Such probability limits the performance of the lattice sequential decoder, especially for a one-way communication system. For a two-way communication system, such as in MIMO Automatic Repeat reQuest (ARQ) system, the feedback channel can be used to eliminate the decoding failure probability. In this work, we modify the lattice sequential decoder for the MIMO ARQ channel, to predict in advance the occurrence of decoding failure to avoid wasting the time trying to decode the message. This would result in a huge saving in decoding complexity. In particular, we will study the throughput-performance-complexity tradeoffs in sequential decoding algorithms and the effect of preprocessing and termination strategies. We show, analytically and via simulation, that using the lattice sequential decoder that implements a simple yet efficient time-out algorithm for joint error detection and correction, the optimal tradeoff of the MIMO ARQ channel can be achieved with significant reduction in decoding complexity.

In the last decade, there has been an explosive growth in different applications of wireless technology, due to users' increasing expectations for multi-media services. With the current trend, the present systems will not be able to handle the required data traffic. Lattice codes have attracted considerable attention in recent years, because they provide high data rate constellations. In this thesis, the applications of implementing lattice codes in different communication systems are investigated. The thesis is divided into two major parts. Focus of the first part is on constellation shaping and the problem of lattice labeling. The second part is devoted to the lattice decoding problem. In constellation shaping technique, conventional constellations are replaced by lattice codes that satisfy some geometrical properties. However, a simple algorithm, called lattice labeling, is required to map the input data to the lattice code points. In the first part of this thesis, the application of lattice codes for constellation shaping in Orthogonal Frequency Division Multiplexing (OFDM) and Multi-Input Multi-Output (MIMO) broadcast systems are considered. In an OFDM system a lattice code with low Peak to Average Power Ratio (PAPR) is desired. Here, a new lattice code with considerable PAPR reduction for OFDM systems is proposed. Due to the recursive structure of this lattice code, a simple lattice labeling method based on Smith normal decomposition of an integer matrix is obtained. A selective mapping method in conjunction with the proposed lattice code is also presented to further reduce the PAPR. MIMO broadcast systems are also considered in the thesis. In a multiple antenna broadcast system, the lattice labeling algorithm should be such that different users can decode their data independently. Moreover, the implemented lattice code should result in a low average transmit energy. Here, a selective mapping technique provides such a lattice code. Lattice decoding is the focus of the second part of the thesis, which concerns the operation of finding the closest point of the lattice code to any point in N-dimensional real space. In digital communication applications, this problem is known as the integer least-square problem, which can be seen in many areas, e.g. the detection of symbols transmitted over the multiple antenna wireless channel, the multiuser detection problem in Code Division Multiple Access (CDMA) systems, and the simultaneous detection of multiple users in a Digital Subscriber Line (DSL) system affected by crosstalk. Here, an efficient lattice decoding algorithm based on using Semi-Definite Programming (SDP) is introduced. The proposed algorithm is capable of handling any form of lattice constellation for an arbitrary labeling of points. In the proposed methods, the distance minimization problem is expressed in terms of a binary quadratic minimization problem, which is solved by introducing several matrix and vector lifting SDP relaxation models. The new SDP models provide a wealth of trade-off between the complexity and the performance of the decoding problem.

In this thesis, different aspects of lattice-based precoding and decoding for the transmission of digital and analog data over MIMO fading channels are investigated: 1) Lattice-based precoding in MIMO broadcast systems: A new viewpoint for adopting the lattice reduction in communication over MIMO broadcast channels is introduced. Lattice basis reduction helps us to reduce the average transmitted energy by modifying the region which includes the constellation points. The new viewpoint helps us to generalize the idea of lattice-reduction-aided precoding for the case of unequal-rate transmission, and obtain analytic results for the asymptotic behavior of the symbol-error-rate for the lattice-reduction-aided precoding and the perturbation technique. Also, the outage probability for both cases of fixed-rate users and fixed sum-rate is analyzed. It is shown that the lattice-reduction-aided method, using LLL algorithm, achieves the optimum asymptotic slope of symbol-error-rate (called the precoding diversity). 2) Lattice-based decoding in MIMO multiaccess systems and MIMO point-to-point systems: Diversity order and diversity-multiplexing tradeoff are two important measures for the performance of communication systems over MIMO fading channels. For the case of MIMO multiaccess systems (with single-antenna transmitters) or MIMO point-to-point systems with V-BLAST transmission scheme, it is proved that lattice-reduction-aided decoding achieves the maximum receive diversity (which is equal to the number of receive antennas). Also, it is proved that the naive lattice decoding (which discards the out-of-region decoded points) achieves the maximum diversity in V-BLAST systems. On the other hand, the inherent drawbacks of the naive lattice decoding for general MIMO fading systems is investigated. It is shown that using the naive lattice decoding for MIMO systems has considerable deficiencies in terms of the diversity-multiplexing tradeoff. Unlike the case of maximum-likelihood decoding, in this case, even the perfect lattice space-time codes which have the non-vanishing determinant property can not achieve the optimal diversity-multiplexing tradeoff. 3) Lattice-based analog transmission over MIMO fading channels: The problem of finding a delay-limited schemes for sending an analog source over MIMO fading channels is investigated in this part. First, the problem of robust joint source-channel coding over an additive white Gaussian noise channel is investigated. A new scheme is proposed which achieves the optimal slope for the signal-to-distortion-ratio (SDR) curve (unlike the previous known coding schemes). Then, this idea is extended to MIMO channels to construct lattice-based codes for joint source-channel coding over MIMO channels. Also, similar to the diversity-multiplexing tradeoff, the asymptotic performance of MIMO joint source-channel coding schemes is characterized, and a concept called diversity-fidelity tradeoff is introduced in this thesis.

In the last decade, there has been an explosive growth in different applications of wireless technology, due to users' increasing expectations for multi-media services. With the current trend, the present systems will not be able to handle the required data traffic. Lattice codes have attracted considerable attention in recent years, because they provide high data rate constellations. In this thesis, the applications of implementing lattice codes in different communication systems are investigated. The thesis is divided into two major parts. Focus of the first part is on constellation shaping and the problem of lattice labeling. The second part is devoted to the lattice decoding problem. In constellation shaping technique, conventional constellations are replaced by lattice codes that satisfy some geometrical properties. However, a simple algorithm, called lattice labeling, is required to map the input data to the lattice code points. In the first part of this thesis, the application of lattice codes for constellation shaping in Orthogonal Frequency Division Multiplexing (OFDM) and Multi-Input Multi-Output (MIMO) broadcast systems are considered. In an OFDM system a lattice code with low Peak to Average Power Ratio (PAPR) is desired. Here, a new lattice code with considerable PAPR reduction for OFDM systems is proposed. Due to the recursive structure of this lattice code, a simple lattice labeling method based on Smith normal decomposition of an integer matrix is obtained. A selective mapping method in conjunction with the proposed lattice code is also presented to further reduce the PAPR. MIMO broadcast systems are also considered in the thesis. In a multiple antenna broadcast system, the lattice labeling algorithm should be such that different users can decode their data independently. Moreover, the implemented lattice code should result in a low average transmit energy. Here, a selective mapping technique provides such a lattice code. Lattice decoding is the focus of the second part of the thesis, which concerns the operation of finding the closest point of the lattice code to any point in N-dimensional real space. In digital communication applications, this problem is known as the integer least-square problem, which can be seen in many areas, e.g. the detection of symbols transmitted over the multiple antenna wireless channel, the multiuser detection problem in Code Division Multiple Access (CDMA) systems, and the simultaneous detection of multiple users in a Digital Subscriber Line (DSL) system affected by crosstalk. Here, an efficient lattice decoding algorithm based on using Semi-Definite Programming (SDP) is introduced. The proposed algorithm is capable of handling any form of lattice constellation for an arbitrary labeling of points. In the proposed methods, the distance minimization problem is expressed in terms of a binary quadratic minimization problem, which is solved by introducing several matrix and vector lifting SDP relaxation models. The new SDP models provide a wealth of trade-off between the complexity and the performance of the decoding problem.

In this thesis, different aspects of lattice-based precoding and decoding for the transmission of digital and analog data over MIMO fading channels are investigated: 1) Lattice-based precoding in MIMO broadcast systems: A new viewpoint for adopting the lattice reduction in communication over MIMO broadcast channels is introduced. Lattice basis reduction helps us to reduce the average transmitted energy by modifying the region which includes the constellation points. The new viewpoint helps us to generalize the idea of lattice-reduction-aided precoding for the case of unequal-rate transmission, and obtain analytic results for the asymptotic behavior of the symbol-error-rate for the lattice-reduction-aided precoding and the perturbation technique. Also, the outage probability for both cases of fixed-rate users and fixed sum-rate is analyzed. It is shown that the lattice-reduction-aided method, using LLL algorithm, achieves the optimum asymptotic slope of symbol-error-rate (called the precoding diversity). 2) Lattice-based decoding in MIMO multiaccess systems and MIMO point-to-point systems: Diversity order and diversity-multiplexing tradeoff are two important measures for the performance of communication systems over MIMO fading channels. For the case of MIMO multiaccess systems (with single-antenna transmitters) or MIMO point-to-point systems with V-BLAST transmission scheme, it is proved that lattice-reduction-aided decoding achieves the maximum receive diversity (which is equal to the number of receive antennas). Also, it is proved that the naive lattice decoding (which discards the out-of-region decoded points) achieves the maximum diversity in V-BLAST systems. On the other hand, the inherent drawbacks of the naive lattice decoding for general MIMO fading systems is investigated. It is shown that using the naive lattice decoding for MIMO systems has considerable deficiencies in terms of the diversity-multiplexing tradeoff. Unlike the case of maximum-likelihood decoding, in this case, even the perfect lattice space-time codes which have the non-vanishing determinant property can not achieve the optimal diversity-multiplexing tradeoff. 3) Lattice-based analog transmission over MIMO fading channels: The problem of finding a delay-limited schemes for sending an analog source over MIMO fading channels is investigated in this part. First, the problem of robust joint source-channel coding over an additive white Gaussian noise channel is investigated. A new scheme is proposed which achieves the optimal slope for the signal-to-distortion-ratio (SDR) curve (unlike the previous known coding schemes). Then, this idea is extended to MIMO channels to construct lattice-based codes for joint source-channel coding over MIMO channels. Also, similar to the diversity-multiplexing tradeoff, the asymptotic performance of MIMO joint source-channel coding schemes is characterized, and a concept called diversity-fidelity tradeoff is introduced in this thesis.

Cette thèse s’intéresse aux réseaux de confusion comme représentation compacte et structurée des hypothèses multiples produites par un moteur de reconnaissance de parole et transmises à un module de post-traitement applicatif. Les réseaux de confusion (CN pour Confusion Networks) sont générés à partir des graphes de mots et structurent l’information sous la forme d’une séquence de classes contenant des hypothèses de mots en concurrence. Le cas d’usage étudié dans ces travaux est celui des hypothèses de reconnaissance transmises à un module de compréhension de la parole dans le cadre d’une application de dialogue déployée par France Telecom. Deux problématiques inhérentes à ce contexte applicatif sont soulevées. De façon générale, un système de dialogue doit non seulement reconnaître un énoncé prononcé par un utilisateur, mais aussi l’interpréter afin de déduire sons sens. Du point de vue de l’utilisateur, les performances perçues sont plus proches de celles de la chaîne complète de compréhension que de celles de la reconnaissance vocale seule. Ce sont ces performances que nous cherchons à optimiser. Le cas plus particulier d’une application déployée implique de pouvoir traiter des données réelles et donc très variées. Un énoncé peut être plus ou moins bruité, dans le domaine ou hors-domaine, couvert par le modèle sémantique de l’application ou non, etc. Étant donnée cette grande variabilité, nous posons la question de savoir si le fait d’appliquer les mêmes traitements sur l’ensemble des données, comme c’est le cas dans les approches classiques, est une solution adaptée. Avec cette double perspective, cette thèse s’attache à la fois à enrichir l’algorithme de construction des CNs dans le but d’optimiser globalement le processus de compréhension et à proposer une stratégie adéquate d’utilisation des réseaux de confusion dans le contexte d’une application réelle. Après une analyse des propriétés de deux approches de construction des CNs sur un corpus de données réelles, l’algorithme retenu est celui du "pivot". Nous en proposons une version modifiée et adaptée au contexte applicatif en introduisant notamment un traitement différencié des mots du graphe qui privilégie les mots porteurs de sens. En réponse à la grande variabilité des énoncés à traiter dans une application déployée, nous proposons une stratégie de décision à plusieurs niveaux qui vise à mieux prendre en compte les spécificités des différents types d’énoncés. Nous montrons notamment qu’il est préférable de n’exploiter la richesse des sorties multiples que sur les énoncés réellement porteurs de sens. Cette stratégie permet à la fois d’optimiser les temps de calcul et d’améliorer globalement les performances du système / The work presented in this PhD deals with the confusion networks as a compact and structured representation of multiple aligned recognition hypotheses produced by a speech recognition system and used by different applications. The confusion networks (CN) are constructed from word graphs and structure information as a sequence of classes containing several competing word hypothesis. In this work we focus on the problem of robust understanding from spontaneous speech input in a dialogue application, using CNs as structured representation of recognition hypotheses for the spoken language understanding module. We use France Telecom spoken dialogue system for customer care. Two issues inherent to this context are tackled. A dialogue system does not only have to recognize what a user says but also to understand the meaning of his request and to act upon it. From the user’s point of view, system performance is more accurately represented by the performance of the understanding process than by speech recognition performance only. Our work aims at improving the performance of the understanding process. Using a real application implies being able to process real heterogeneous data. An utterance can be more or less noisy, in the domain or out of the domain of the application, covered or not by the semantic model of the application, etc. A question raised by the variability of the data is whether applying the same processes to the entire data set, as done in classical approaches, is a suitable solution. This work follows a double perspective : to improve the CN construction algorithm with the intention of optimizing the understanding process and to propose an adequate strategy for the use of CN in a real application. Following a detailed analysis of two CN construction algorithms on a test set collected using the France Telecom customer care service, we decided to use the "pivot" algorithm for our work. We present a modified and adapted version of this algorithm. The new algorithm introduces different processing techniques for the words which are important for the understanding process. As for the variability of the real data the application has to process, we present a new multiple level decision strategy aiming at applying different processing techniques for different utterance categories. We show that it is preferable to process multiple recognition hypotheses only on utterances having a valid interpretation. This strategy optimises computation time and yields better global performance

No description available.

In wireless networks, reliable communication is a challenging issue due to many attenuation factors such as receiver noise, channel fading, interference and asynchronous delays. Lattice coding and decoding provide efficient solutions to many problems in wireless communications and multiuser information theory. The capability in achieving the fundamental limits, together with simple and efficient transmitter and receiver structures, make the lattice strategy a promising approach. This work deals with problems of lattice detection over fading channels and time asynchronism over the lattice-based compute-and-forward protocol. In multiple-input multiple-output (MIMO) systems, the use of lattice reduction significantly improves the performance of approximate detection techniques. In the first part of this thesis, by taking advantage of the temporal correlation of a Rayleigh fading channel, low complexity lattice reduction methods are investigated. We show that updating the reduced lattice basis adaptively with a careful use of previous channel realizations yields a significant saving in complexity with a minimal degradation in performance. Considering high data rate MIMO systems, we then investigate soft-output detection methods. Using the list sphere decoder (LSD) algorithm, an adaptive method is proposed to reduce the complexity of generating the list for evaluating the log-likelihood ratio (LLR) values. In the second part, by applying the lattice coding and decoding schemes over asynchronous networks, we study the impact of asynchronism on the compute-and-forward strategy. While the key idea in compute-and-forward is to decode a linear synchronous combination of transmitted codewords, the distributed relays receive random asynchronous versions of the combinations. Assuming different asynchronous models, we design the receiver structure prior to the decoder of compute-and-forward so that the achievable rates are maximized at any signal-to-noise-ratio (SNR). Finally, we consider symbol-asynchronous X networks with single antenna nodes over time-invariant channels. We exploit the asynchronism among the received signals in order to design the interference alignment scheme. It is shown that the asynchronism provides correlated channel variations which are proved to be sufficient to implement the vector interference alignment over the constant X network.