No description available.

ITC/USA 2008 Conference Proceedings / The Forty-Fourth Annual International Telemetering Conference and Technical Exhibition / October 27-30, 2008 / Town and Country Resort & Convention Center, San Diego, California / We design irregular Low-Density Parity-Check (LDPC) codes for free-space optical (FSO) channels for different transmitter-receiver link distances and analyze the error performance for different atmospheric conditions. The design considers atmospheric absorption, laser beam divergence, and random intensity fluctuations due to atmospheric turbulence. It is found that, for the same transmit power, a system using the designed codes works over much longer link distances than a system that employs regular LDPC codes. Our analysis is particularly useful for portable optical transceivers and mobile links.

In mobile communication, the user’s information is transmitted through a wireless communication link that is subjected to a range of deteriorating effects. The quality of the transmission can be presented by the rate of transfer and the reliability of the received stream. The capacity of the communication link can be reached through the use of channel coding. Channel coding is the method of adding redundant information to the user’s information to mitigate the deteriorating effects of the communication link. Mobile WiMAX is a technology that makes use of orthogonal frequency division multiplexing (OFDM) modulation to transmit information over a wireless communication channel. The OFDM physical layer has a high peak average to power ratio (PAPR) characteristic that saturates the transmitter’s amplifier quite easily when proper backoff is not made in the transmission power. In this dissertation an optimized graph code was used as an alternative solution to improve the system’s performance in the presence of a saturated transmission’s amplifier. The graph code was derived from a degree distribution given by the density evolution algorithm and provided no extra network overhead to implement. The performance analysis resulted in a factor of 10 improvement in the error floor and a coding gain of 1.5 dB. This was all accomplished with impairments provided by the mobile WiMAX standard in the construction of the graph code. / Dissertation (MEng)--University of Pretoria, 2009. / Electrical, Electronic and Computer Engineering / unrestricted

Ces dernières années ont vu naitre un intérêt grandissant pour les décodeurs correcteurs d'erreurs opérant sur des circuits non fiables. En effet, la miniaturisation croissante des composants électroniques ainsi l'échelonnage agressif de la tension d'alimentation ont pour conséquence la diminution de la fiabilité des systèmes. Par conséquent, les futures générations de circuits électroniques seront intrinsèquement non fiables. En outre, les décodeurs correcteurs d'erreurs sont indispensables non seulement pour assurer une transmission fiable de l'information mais aussi pour concevoir des systèmes de stockage performants.Nous nous intéressons, dans cette thèse, plus particulièrement aux décodeurs à précision finie Min-Sum (MS), Self-Corrected Min-Sum (SCMS) et Stochastiques.Nous commençons par effectuer une analyse statistique du décodeur Min-Sum opérant sur des circuits à comportement probabiliste. Pour ce faire nous introduisons des modèles d'erreurs probabilistes pour les composants logiques et les opérateurs arithmétiques du décodeur et étudions leurs propriétés de symétrie. Puis nous effectuions une analyse asymptotique rigoureuse et en déduisons les équations d'évolution de densité du décodeur Min-Sum bruité. Nous mettons ainsi en évidence l'effet positif, dans certains cas, du bruit issu du circuit sur la capacité de correction du décodeur. Nous révélons ensuite l'existence d'un phénomène de seuil particulier que nous nommons seuil fonctionnel. Ce dernier peut être considéré comme la généralisation du seuil classique pour les décodeurs non fiables. Nous corroborons ensuite les résultats asymptotiques par des simulations Monte-Carlo.Nous implémentons des décodeurs LDPC bruités pour plusieurs paramètres de bruit et montrons que les décodeurs LDPC bruité ont des résultats très proches de ceux des décodeurs non bruités. Nous pouvons par conséquent considérer le circuit d'autocorrection comme un patch bruité appliqué au décodeur MS bruité afin d'améliorer la robustesse du décodeur face au bruit issu des composants non fiables. Nous évaluons par railleurs l'impact de l'ordonnancement et montrons qu'un ordonnancement série dégrade fortement la robustesse des décodeurs bruités MS et SCMS qui ne parviennent plus à atteindre une capacité de correction acceptable.Pour finir nous étudions les performances des décodeurs stochastiques pourvus de mémoires d'arêtes et opérant sur des circuits non fiables. Nous proposons deux modèles d'erreurs décrivant le comportement probabiliste des composants du décodeur. Nous montrons que, dans certains cas, le bruit issu du circuit non fiable permet de réduire le plancher d'erreur. Nous en déduisons alors que le décodeur stochastique est intrinsèquement tolérant aux fautes. / Over the past few years, there has been an increasing interest in error correction decoders built out of unreliable components. Indeed, it is widely accepted that future generation of electronic circuit will be inherently unreliable, due to the increase in density integration and aggressive voltage scaling. Furthermore, error correction decoders play a crucial role both in reliable transmission of information and in the design of reliable storage systems. It is then important to investigate the robustness of error correction decoders in presence of hardware noise.In this thesis we focus on LDPC decoders built out of unreliable computing units. We consider three types of LDPC decoders: the finite-precision Min-Sum (MS) decoder, the Self-Corrected Min-Sum (SCMS) decoder and the Stochastic decoder.We begin our study by the statistical analysis of the finite-precision Min-Sum decoder with probabilistic components. To this end, we first introduce probabilistic models for the arithmetic and logic units of the decoder and discuss their symmetry properties. We conduct a thorough asymptotic analysis and derive density evolution equations for the noisy Min-Sum decoder. We highlight that in some particular cases, the noise introduced by the device can increase the correction capacity of the noisy Min-Sum with respect to the noiseless decoder. We also reveal the existence of a specific threshold phenomenon, referred to as functional threshold, which can be viewed as the generalization of the threshold definition for noisy decoders. We then corroborate the asymptotic results through Monte-Carlo simulations.Since density evolution cannot be defined for decoders with memory, the analysis of noisy Self-corrected Min-Sum decoders and noisy Stochastic decoders was restricted to Monte-Carlo simulations.We emulate the noisy SCMS decoders with various noise parameters and show that noisy SCMS decoders perform close to the noiseless SCMS decoder for a wide range of noise parameters. Therefore, one can think of the self-correction circuit as a noisy patch applied to the noisy MS decoder, in order to improve its robustness to hardware defect. We also evaluate the impact of the decoder scheduling on the robustness of the noisy MS and SCMS decoders and show that when the serial scheduling is used neither the noisy MS decoder nor the noisy SCMS decoder can provide acceptable error correction.Finally, we investigate the performance of stochastic decoders with edge-memories in presence of hardware noise. We propose two error models for the noisy components. We show that in some cases, the hardware noise can be used to lower the error floor of the decoder meaning that stochastic decoders have an inherent fault tolerant capability.

Luby Transform Codes were the first class of universal erasure codes introduced to fully realize the concept of scalable and fault‐tolerant distribution of data over computer networks, also called Digital Fountain. Later Raptor codes, a generalization of the LT codes were introduced to trade off complexity with performance. In this work, we show that an even broader class of codes exists that are near optimal for the erasure channel and that the Raptor codes form a special case. More precisely, Raptorlike codes can be designed based on an iterative (joint) decoding schedule wherein information is transferred between the LT decoder and an outer decoder in an iterative manner. The design of these codes can be formulated as a LP problem using EXIT Charts and density evolution. In our work, we show the existence of codes, other than the Raptor codes, that perform as good as the existing ones. We extend this framework of joint decoding of the component codes to the additive white Gaussian noise channels and introduce the design of Rateless codes for these channels. Under this setting, for asymptotic lengths, it is possible to design codes that work for a class of channels defined by the signal‐to‐noise ratio. In our work, we show that good profiles can be designed using density evolution and Gaussian approximation. EXIT charts prove to be an intuitive tool and aid in formulating the code design problem as a LP problem. EXIT charts are not exact because of the inherent approximations. Therefore, we use density evolution to analyze the performance of these codes. In the Gaussian case, we show that for asymptotic lengths, a range of designs of Rateless codes exists to choose from based on the required complexity and the overhead. Moreover, under this framework, we can design incrementally redundant schemes for already existing outer codes to make the communication system more robust to channel noise variations.

Turbo Trellis-Coded Modulation (TTCM) is an attractive scheme for higher data rate transmission, since it combines the impressive near Shannon limit error correcting ability of turbo codes with the high spectral efficiency property of TCM codes. We build a punctured parity-concatenated trellis codes in which a TCM code is used as the inner code and a simple parity-check code is used as the outer code. It can be constructed by simple repetition, interleavers, and TCM and functions as standard TTCM but with much lower complexity regarding real world implementation. An iterative bit MAP decoding algorithm is associated with the coding scheme. Orthogonal Frequency Division Multiplexing (OFDM) modulation has been a promising solution for efficiently capturing multipath energy in highly dispersive channels and delivering high data rate transmission. One of UWB proposals in IEEE P802.15 WPAN project is to use multi-band OFDM system and punctured convolutional codes for UWB channels supporting data rate up to 480Mb/s. The HomePlug Networking system using the medium of power line wiring also selects OFDM as the modulation scheme due to its inherent adaptability in the presence of frequency selective channels, its resilience to jammer signals, and its robustness to impulsive noise in power line channel. The main idea behind OFDM is to split the transmitted data sequence into N parallel sequences of symbols and transmit on different frequencies. This structure has the particularity to enable a simple equalization scheme and to resist to multipath propagation channel. However, some carriers can be strongly attenuated. It is then necessary to incorporate a powerful channel encoder, combined with frequency and time interleaving. We examine the possibility of improving the proposed OFDM system over UWB channel and HomePlug powerline channel by using our Turbo TCM with QAM constellation for higher data rate transmission. The study shows that the system can offer much higher spectral efficiency, for example, 1.2 Gbps for OFDM/UWB which is 2.5 times higher than the current standard, and 39 Mbps for OFDM/HomePlug1.0 which is 3 times higher than current standard. We show several essential requirements to achieve high rate such as frequency and time diversifications, multi-level error protection. Results have been confirmed by density evolution. The effect of impulsive noise on TTCM coded OFDM system is also evaluated. A modified iterative bit MAP decoder is provided for channels with impulsive noise with different impulsivity.

This dissertation studies methods to achieve reliable communication over unreliable channels. Iterative decoding algorithms for low-density parity-check (LDPC) codes and generalized LDPC (GLDPC) codes are analyzed. A new class of error-correcting codes to enhance the reliability of the communication for high-speed systems, such as optical communication systems, is proposed. The class of spatially-coupled GLDPC codes is studied, and a new iterative hard- decision decoding (HDD) algorithm for GLDPC codes is introduced. The main result is that the minimal redundancy allowed by Shannon’s Channel Coding Theorem can be achieved by using the new iterative HDD algorithm with spatially-coupled GLDPC codes. A variety of low-density parity-check (LDPC) ensembles have now been observed to approach capacity with iterative decoding. However, all of them use soft (i.e., non-binary) messages and a posteriori probability (APP) decoding of their component codes. To the best of our knowledge, this is the first system that can approach the channel capacity using iterative HDD. The optimality of a codeword returned by the weighted min-sum (WMS) algorithm, an iterative decoding algorithm which is widely used in practice, is studied as well. The attenuated max-product (AttMP) decoding and weighted min-sum (WMS) decoding for LDPC codes are analyzed. Applying the max-product (and belief- propagation) algorithms to loopy graphs are now quite popular for best assignment problems. This is largely due to their low computational complexity and impressive performance in practice. Still, there is no general understanding of the conditions required for convergence and/or the optimality of converged solutions. This work presents an analysis of both AttMP decoding and WMS decoding for LDPC codes which guarantees convergence to a fixed point when a weight factor, β, is sufficiently small. It also shows that, if the fixed point satisfies some consistency conditions, then it must be both a linear-programming (LP) and maximum-likelihood (ML) decoding solution.

Dans cette thèse, nous nous sommes intéressés au problème de codage de sources avec information adjacente au décodeur seulement. Plus précisément, nous avons considéré le cas où la distribution jointe entre la source et l'information adjacente n'est pas bien connue. Dans ce contexte, pour un problème de codage sans pertes, nous avons d'abord effectué une analyse de performance à l'aide d'outils de la théorie de l'information. Nous avons ensuite proposé un schéma de codage pratique efficace malgré le manque de connaissance sur la distribution de probabilité jointe. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur un algorithme de type Espérance-Maximisation. Le problème du schéma de codage proposé, c'est que les codes LDPC non-binaires utilisés doivent être performants. C'est à dire qu'ils doivent être construits à partir de distributions de degrés qui permettent d'atteindre un débit proche des performances théoriques. Nous avons donc proposé une méthode d'optimisation des distributions de degrés des codes LDPC. Enfin, nous nous sommes intéressés à un cas de codage avec pertes. Nous avons supposé que le modèle de corrélation entre la source et l'information adjacente était décrit par un modèle de Markov caché à émissions Gaussiennes. Pour ce modèle, nous avons également effectué une analyse de performance, puis nous avons proposé un schéma de codage pratique. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur une reconstruction MMSE. Ces deux composantes exploitent la structure avec mémoire du modèle de Markov caché. / In this thesis, we considered the problem of source coding with side information available at the decoder only. More in details, we considered the case where the joint distribution between the source and the side information is not perfectly known. In this context, we performed a performance analysis of the lossless source coding scheme. This performance analysis was realized from information theory tools. Then, we proposed a practical coding scheme able to deal with the uncertainty on the joint probability distribution. This coding scheme is based on non-binary LDPC codes and on an Expectation-Maximization algorithm. For this problem, a key issue is to design efficient LDPC codes. In particular, good code degree distributions have to be selected. Consequently, we proposed an optimization method for the selection of good degree distributions. To finish, we considered a lossy coding scheme. In this case, we assumed that the correlation channel between the source and the side information is described by a Hidden Markov Model with Gaussian emissions. For this model, we performed again some performance analysis and proposed a practical coding scheme. The proposed scheme is based on non-binary LDPC codes and on MMSE reconstruction using an MCMC method. In our solution, these two components are able to exploit the memory induced by the Hidden Markov model.

Une courbe de fragilité sismique qui présente la probabilité de défaillance d’une structure en fonction d’une intensité sismique, est un outil performant pour l’évaluation de la vulnérabilité sismique des structures en génie nucléaire et génie civil. On se concentre dans cette thèse sur l’approche par simulations numériques pour la construction des courbes de fragilité sismique. Une étude comparative des méthodes paramétriques existantes avec l’hypothèse log-normale est d’abord réalisée. Elle permet ensuite de proposer des améliorations de la méthode du maximum de vraisemblance dans le but d’atténuer l’influence de l’excitation sismique lors de son processus de construction. Une autre amélioration est l’application de la méthode de simulations par subsets pour l’évaluation de la probabilité de défaillance faible. Enfin, en utilisant la méthode de calcul de l’évolution des fonctions de densité de probabilité qui permet d’évaluer la probabilité conjointe entre la réponse structurale et les variables aléatoires du système et de l’excitation, nous proposons également une nouvelle technique non-paramétrique de construction des courbes de fragilité sismique sans utiliser l’hypothèse de la loi log-normale. La validation des améliorations et de la nouvelle technique est réalisée sur des exemples numériques. / A seismic fragility curve that shows the failure probability of a structure in function of a seismic intensity is a powerful tool for the evaluation of the seismic vulnerability of structures in nuclear engineering and civil engineering.We focus in this thesis on the numerical simulations-based approach for the construction of seismic fragility curves. A comparative work between existent parametric methods with the lognormal assumption of the fragility curves is first performed. It then allows proposing improvements to the maximum likelihood method in order to mitigate the influence of seismic excitation during its construction process. Another improvement is the application of the subsets simulation method for the evaluation of the low probability of failure. Finally, using the Probability Density Evolution Method (PDEM) for evaluating the joint probability between a structural response and random variables of a system and/or excitations, a new technique for construction of seismic fragility curves was proposed. The seismic fragility curve can be derived without the assumption of lognormal law. The improvements and the new technique are all validated by numerical examples.

This thesis investigates both theoretical and practical aspects of the design and analysis of modern error-control coding schemes, namely low-density parity-check (LDPC) codes and rateless codes for unequal error protection (UEP). It also studies the application of modern error-control codes in efficient data dissemination in wireless ad-hoc and sensor networks. Two methodologies for the design and analysis of UEP-LDPC codes are proposed. For these proposed ensembles, density evolution formulas over the binary erasure channel are derived and used to optimize the degree distribution of the codes. Furthermore, for the first time, rateless codes that can provide UEP are developed. In addition to providing UEP, the proposed codes can be used in applications for which unequal recovery time is desirable, i.e., when more important parts of data are required to be recovered faster than less important parts. Asymptotic behavior of the UEP-rateless codes under the iterative decoding is investigated. In addition, the performance of the proposed codes is examined under the maximum-likelihood decoding, when the codes have short to moderate lengths. Results show that UEP-rateless codes are able to provide very low error rates for more important bits with only a subtle loss in the performance of less important bits. Moreover, it is shown that given a target bit error rate, different parts of the information symbols can be decoded after receiving different numbers of encoded symbols. This implies that information can be recovered in a progressive manner, which is of interest in many practical applications such as media-on-demand systems. This work also explores fundamental research problems related to applying error-control coding such as rateless coding to the problem of reliable and energy-efficient broadcasting in multihop wireless ad-hoc sensor networks. The proposed research touches on the four very large fields of wireless networking, coding theory, graph theory, and percolation theory. Based on the level of information that each node has about the network topology, several reliable and energy-efficient schemes are proposed, all of which are distributed and have low complexity of implementation. The first protocol does not require any information about the network topology. Another protocol, which is more energy efficient, assumes each node has local information about the network topology. In addition, this work proposes a distributed scheme for finding low-cost broadcast trees in wireless networks. This scheme takes into account various parameters such as distances between nodes and link losses. This protocol is then extended to find low-cost multicast trees. Several schemes are extensively simulated and are compared.