Recently, lattices - a mathematical representation of infinite discrete points in the Euclidean space, have become an effective way to describe and analyze communication systems especially system those that can be modeled as linear Gaussian vector channel model. Channel codes based on lattices are preferred due to three facts: lattice codes have simple structure, the code can achieve the limits of the channel, and they can be decoded efficiently using lattice decoders which can be considered as the Closest Lattice Point Search (CLPS). Since the time lattice codes were introduced to Multiple Input Multiple Output (MIMO) channel, Sphere Decoder (SD) has been an efficient way to implement lattice decoders. Sphere decoder offers the optimal performance at the expense of high decoding complexity especially for low signal-to-noise ratios (SNR) and for high- dimensional systems. On the other hand, linear and non-linear receivers, Minimum Mean Square Error (MMSE), and MMSE Decision-Feedback Equalization (DFE), provide the lowest decoding complexity but unfortunately with poor performance. Several studies works have been conducted in the last years to address the problem of designing low complexity decoders for the MIMO channel that can achieve near optimal performance. It was found that sequential decoders using backward tree 
search can bridge the gap between SD and MMSE. The sequential decoder provides an interesting performance-complexity trade-off using a bias term. Yet, the sequential decoder still suffers from high complexity for mid-to-high SNR values. In this work, we propose a new algorithm for Bidirectional Fano sequential Decoder (BFD) in order to reduce the mid-to-high SNR complexity. Our algorithm consists of first constructing a unidirectional Sequential Decoder based on forward search using the QL decomposition. After that, BFD incorporates two searches, forward and backward, to work simultaneously till they merge and find the closest lattice point to the received signal. We show via computer simulations that BFD can reduce the mid-to-high SNR complexity for the sequential decoder without changing the bias value.

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.

No description available.

Cette thèse concerne la restauration aveugle d’images (formulée comme un problème inverse mal-posé et mal-conditionné), en considérant particulièrement les systèmes SIMO. Dans un premier temps une technique d’identification aveugle de ce système où l’ordre du canal est inconnu (surestimé) est introduite. Nous introduisons d’abord une version simplifiée à coût réduit SCR de la méthode des relations croisées (CR). Ensuite, une version robuste R-SCR basée sur la recherche d’une solution parcimonieuse minimisant la fonction de coût CR est proposée. La restauration d’image est ensuite assurée par une nouvelle approche inspirée des techniques de décodage des signaux 1D et étendue ici aux cas de la restauration d’images en se basant sur une recherche arborescente efficace (algorithme ‘Stack’). Plusieurs améliorations de la méthode ‘Stack’ ont été introduites afin de réduire sa complexité et d’améliorer la qualité de restauration lorsque les images sont fortement bruitées. Ceci en utilisant une technique de régularisation et une approche d’optimisation all-at-once basée sur la descente du gradient qui permet de raffiner l’image estimée et mieux converger vers la solution optimale. Ensuite, les mesures de la qualité d’images sont utilisées comme fonctions de coûts (intégrées dans le critère global) et ce afin d’étudier leur potentiel pour améliorer les performances de restauration. Dans le contexte où l’image d’intérêt est corrompue par d’autres images interférentes, sa restauration nécessite le recours aux techniques de séparation aveugle de sources. Pour cela, une étude comparative de certaines techniques de séparation basées sur la propriété de décorrélation au second ordre et la parcimonie est réalisée. / This thesis concerns the blind restoration of images (formulated as an ill-posed and illconditioned inverse problem), considering a SIMO system. Thus, a blind system identification technique in which the order of the channel is unknown (overestimated) is introduced. Firstly, a simplified version at reduced cost SCR of the cross relation (CR) method is introduced. Secondly, a robust version R-SCR based on the search for a sparse solution minimizing the CR cost function is proposed. Image restoration is then achieved by a new approach (inspired from 1D signal decoding techniques and extended here to the case of 2D images) based on an efficient tree search (Stack algorithm). Several improvements to the ‘Stack’ method have been introduced in order to reduce its complexity and to improve the restoration quality when the images are noisy. This is done using a regularization technique and an all-at-once optimization approach based on the gradient descent which refines the estimated image and improves the algorithm’s convergence towards the optimal solution. Then, image quality measurements are used as cost functions (integrated in the global criterion), in order to study their potential for improving restoration performance. In the context where the image of interest is corrupted by other interfering images, its restoration requires the use of blind sources separation techniques. In this sense, a comparative study of some separation techniques based on the property of second-order decorrelation and sparsity is performed.