Low-density parity-check (LDPC) codes are a subclass of linear block codes. These codes have parity-check matrices in which the ratio of the non-zero elements to all elements is low. This property is exploited in defining low complexity decoding algorithms. Low-density parity-check codes have good distance properties and error correction capability near Shannon limits. In this thesis, the sum-product and the bit-flip decoding algorithms for low-density parity-check codes are implemented on Intel Pentium M 1,86 GHz processor using the software called MATLAB. Simulations for the two decoding algorithms are made over additive white gaussian noise (AWGN) channel changing the code parameters like the information rate, the blocklength of the code and the column weight of the parity-check matrix. Performance comparison of the two decoding algorithms are made according to these simulation results. As expected, the sum-product algorithm, which is based on soft-decision decoding, outperforms the bit-flip algorithm, which depends on hard-decision decoding. Our simulations show that the performance of LDPC codes improves with increasing blocklength and number of iterations for both decoding algorithms. Since the sum-product algorithm has lower error-floor characteristics, increasing the number of iterations is more effective for the sum-product decoder compared to the bit-flip decoder. By having better BER performance for lower information rates, the bit-flip algorithm performs according to the expectations / however, the performance of the sum-product decoder deteriorates for information rates below 0.5 instead of improving. By irregular construction of LDPC codes, a performance improvement is observed especially for low SNR values.

Sum-product algorithm can be employed for obtaining the marginal probability density functions from a given joint probability density function (p.d.f.). The sum-product algorithm operates on a factor graph which represents the dependencies of the random variables whose joint p.d.f. is given. The sum-product algorithm can not be operated on factor-graphs that contain loops. For these factor graphs iterative sum-product algorithm is used. A factor graph which contains loops can be divided in to loop-free sub-graphs. Sum-product algorithm can be operated in these loop-free sub-graphs and results of these sub-graphs can be combined for obtaining the result of the whole factor graph in an iterative manner. This method may increase the convergence rate of the algorithm significantly while keeping the complexity of an iteration and accuracy of the output constant. A useful by-product of this research that is introduced in this thesis is a good approximation to message calculation in factor nodes of the inter-symbol interference (ISI) factor graphs. This approximation has a complexity that is linearly proportional with the number of neighbors instead of being exponentially proportional. Using this approximation and the sub-graph idea we have designed and simulated joint decoding-equalization (turbo equalization) algorithm and obtained good results besides the low complexity.

Soit μ une mesure de probabilité borélienne sur SL m+1 (R) tel que le sous-groupe engendré par le support de μ est Zariski dense. Soit V une représentation irréductible de dimension finie de SL m+1 (R). D’après un théorème de Furstenberg, il existe une unique mesure μ-stationnaire sur PV et nous nous somme intéressés à la décroissance de Fourier de cette mesure. Le résultat principal de cette thèse est que la transformée de Fourier de la mesure stationnaire a une décroissance polynomiale. À partir de ce résultat, nous obtenons un trou spectral de l’opérateur de transfert, dont les propriétés nous permettent d’établir un terme d’erreur exponentiel pour le théorème de renouvellement dans le cadre des produits de matrices aléatoires. L’ingrédient essentiel est une propriété de décroissance de Fourier des convolutions multiplicatives de mesures sur R n , qui est une généralisation d’un théorème de Bourgain en dimension 1. Nous établissons cet ingrédient en utilisant un estimée somme produit de He et de Saxcé.Dans la dernière partie, nous généralisons un résultat de Lax et Phillips et un résultat de Hamenstädt sur la finitude des petites valeurs propres de l’opérateur de Laplace sur les variétés hyperboliques géométriquement finies. / Let μ be a Borel probability measure on SL m+1 (R), whose support generates a Zariski dense subgroup. Let V be a finite dimensional irreducible linear representation of SL m+1 (R). A theorem of Furstenberg says that there exists a unique μ-stationary probability measure on PV and we are interested in the Fourier decay of the stationary measure. The main result of the thesis is that the Fourier transform of the stationary measure has a power decay. From this result, we obtain a spectral gap of the transfer operator, whose properties allow us to establish an exponential error term for the renewal theorem in the context of products of random matrices. A key technical ingredient for the proof is a Fourier decay of multiplicative convolutions of measures on R n , which is a generalisation of Bourgain’s theorem on dimension 1. We establish this result by using a sum-product estimate due to He-de Saxcé. In the last part, we generalize a result of Lax-Phillips and a result of Hamenstädt on the finiteness of small eigenvalues of the Laplace operator on geometrically finite hyperbolic manifolds

Dans le cadre discrétisé, la taille d'un ensemble à l'échelle δ est évaluée par son nombre de recouvrement par δ-boules (également connu sous le nom de l'entropie métrique). Dans cette thèse, nous étudions les propriétés combinatoires des ensembles discrétisés sous l'addition, la multiplication et les projections orthogonales. Il y a trois parties principales. Premièrement, nous démontrons un théorème somme-produit dans les algèbres de matrices, qui généralise un théorème somme-produit de Bourgain concernant l'anneau des réels. On améliore aussi des estimées somme-produit en dimension supérieure obtenues précédemment par Bougain et Gamburd. Deuxièmement, on étudie les projections orthogonales des sous-ensembles de l'espace euclidien et étend ainsi le théorème de projection discrétisé de Bourgain aux projections de rang supérieur. Enfin, dans un travail en commun avec Nicolas de Saxcé, nous démontrons un théorème produit dans les groupes de Lie parfaits. Ce dernier résultat généralise les travaux antérieurs de Bourgain-Gamburd et de Saxcé. / In the discretized setting, the size of a set is measured by its covering number by δ-balls (a.k.a. metric entropy), where δ is the scale. In this document, we investigate combinatorial properties of discretized sets under addition, multiplication and orthogonal projection. There are three parts. First, we prove sum-product estimates in matrix algebras, generalizing Bourgain's sum-product theorem in the ring of real numbers and improving higher dimensional sum-product estimates previously obtained by Bourgain-Gamburd. Then, we study orthogonal projections of subsets in the Euclidean space, generalizing Bourgain's discretized projection theorem to higher rank situations. Finally, in a joint work with Nicolas de Saxcé, we prove a product theorem for perfect Lie groups, generalizing previous results of Bourgain-Gamburd and Saxcé.

In this effort, we consider the performance of a dedicated short range communication (DSRC) system for inter-vehicle communications (IVC). The DSRC standard employs convolutional codes for forward error correction (FEC). The performance of the DSRC system is evaluated in three different channels with convolutional codes, regular low density parity check (LDPC) codes and quasi-cyclic (QC) LDPC codes. In addition, we compare the complexity of these codes. It is shown that LDPC and QC-LDPC codes provide a significant improvement in performance compared to convolutional codes. / Graduate

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.

Chapter 1 presents the definitions and basic properties of trigonometric functions including: Sum Identities, Difference Identities, Product-Sum Identities and Sum-Product Identities. These formulas provide effective tools to solve the problems in trigonometry. Chapter 2 handles the most important two theorems in trigonometry: The laws of sines and cosines and show how they can be applied to derive many well known theorems including: Ptolemy¡¦s theorem, Euler Triangle Formula, Ceva¡¦s theorem, Menelaus¡¦s Theorem, Parallelogram Law, Stewart¡¦s theorem and Brahmagupta¡¦s Formula. Moreover, the formulas of computing a triangle area like Heron¡¦s formula and Pick¡¦s theorem are also discussed. Chapter 3 deals with the method of superposition, inverse trigonometric functions, polar forms and De Moivre¡¦s Theorem.

We implement a package for the construction of a new class of Low Density Parity Check (LDPC) codes based on a new random high girth graph construction technique, and study the performance of the codes so constructed on both the Additive White Gaussian Noise (AWGN) channel as well as the Binary Erasure Channel (BEC). Our codes are “near regular”, meaning thereby that the the left degree of any node in the Tanner graph constructed varies by at most 1 from the average left degree and so also the right degree. The simulations for rate half codes indicate that the codes perform better than both the regular Progressive Edge Growth (PEG) codes which are constructed using a similar random technique, as well as the MacKay random codes. For high rates the ARG (Almost Regular high Girth) codes perform better than the PEG codes at low to medium SNR’s but the PEG codes seem to do better at high SNR’s. We have tried to track both near codewords as well as small weight codewords for these codes to examine the performance at high rates. For the binary erasure channel the performance of the ARG codes is better than that of the PEG codes. We have also proposed a modification of the sum-product decoding algorithm, where a quantity called the “node credibility” is used to appropriately process messages to check nodes. This technique substantially reduces the error rates at signal to noise ratios of 2.5dB and beyond for the codes experimented on. The average number of iterations to achieve this improved performance is practically the same as that for the traditional sum-product algorithm.

Network coding was introduced as a means to increase throughput in communication networks when compared to routing. Network coding can be used not only to communicate messages from some nodes in the network to other nodes but are also useful when some nodes in a network are interested in computing some functions of information generated at some other nodes. Such a situation arises in sensor networks. In this work, we study three problems in network coding. First, we consider the functional source coding with side information problem wherein there is one source that generates a set of messages and one receiver which knows some functions of source messages and demands some other functions of source messages. Cognizant of the receiver's side information, the source aims to satisfy the demands of the receiver by making minimum number of coded transmissions over a noiseless channel. We use row-Latin rectangles to obtain optimal codes for a given functional source coding with side information problem. Next, we consider the multiple receiver extension of this problem, called the functional index coding problem, in which there are multiple receivers, each knowing and demanding disjoint sets of functions of source messages. The source broadcasts coded messages, called a functional index code, over a noiseless channel. For a given functional index coding problem, the restrictions the demands of the receivers pose on the code are represented using the generalized exclusive laws and it is shown that a code can be obtained using the confusion graph constructed using these laws. We present bounds on the size of an optimal code based on the parameters of the confusion graph. For the case of noisy broadcast channel, we provide a necessary and sufficient condition that a code must satisfy for correct decoding of desired functions at each receiver and obtain a lower bound on the length of an error-correcting functional index code. In the second problem, we explore relation between network function computation problems and functional index coding and Metroid representation problems. In a network computation problem, the demands of the sink nodes in a directed acyclic multichip network include functions of the source messages. We show that any network computation problem can be converted into a functional index coding problem and vice versa. We prove that a network code that satisfies all the sink demands in a network computation problem exists if and only if its corresponding functional index coding problem admits a functional index code of a specific length. Next, we establish a relation between network computation problems and representable mastoids. We show that a network computation problem in which the sinks demand linear functions of source messages admits a scalar linear solution if and only if it is matricidal with respect to a representable Metroid whose representation fulfils certain constraints dictated by the network computation problem. Finally, we study the usage of the sum-product (SP) algorithm for decoding network codes. Though lot of methods to obtain network codes exist, the decoding procedure and complexity have not received much attention. We propose a SP algorithm based decoder for network codes which can be used to decode both linear and nonlinear network codes. We pose the decoding problem at a sink node as a marginalize a product function (MPF) problem over the Boolean smearing and use the SP algorithm on a suitably constructed factor graph to perform decoding. We propose and demonstrate the usage of trace back to reduce the number of operations required to perform SP decoding. The computational complexity of performing SP decoding with and without trace back is obtained. For nonlinear network codes, we define fast decidability of a network code at sinks that demand all the source messages and identify a sufficient condition for the same. Next, for network function computation problems, we present an MPF formulation for function computation at a sink node and use the SP algorithm to obtain the value of the demanded function.