[pt] Para transmissão da informação de maneira confiável, em canais com apagamento, foram criados os códigos LT (Luby Transform), uma das principais classes de códigos fontanais. Estes códigos não têm uma taxa fixa, em outras palavras, eles têm taxa versátil. Esta dissertação aborda o estudo da transmissão de imagens através de canal ruidoso, AWGN (Aditive White Gaussian Noise), com o uso de Códigos LT. Investigou-se o desempenho usando uma modulação BPSK, dois esquemas foram testados: Um esquema para canal que inclui apagamento (BESC) e um outro que foi proposto usando um código Hamming em série com um código LT. O esquema LT-Hamming apresentou um ganho de código maior que o esquema BESC e o código convolucional de semelhantes características. Foi testado o esquema LT-Hamming para diferentes tipos de imagens em um canal AWGN usando a técnica SPIHT para a compressão das imagens. Para obter uma medida objetiva da qualidade da imagem recuperada foi usado o parâmetro PSNR (Peak Sinal to Noise Ratio) e foram apresentadas algumas imagens com o objetivo de analisar sua qualidade através de uma inspeção visual. Dado que o código LT é versátil para o que diz respeito à taxa de código, foi proposto um método para método para atribuir diferentes níveis de proteção da informação codificada, UEP (Unequal Error Protection). / [en] To transfer reliably information in erasure channels, LT (Luby Transform) codes were created, they are part of the main class of fountain codes, this codes don’t have fixed rate, in other words, they have a versatile code rate. This thesis address to the study of images transmission through noisy channel, AWGN (Aditive White Gaussian Noise) using LT codes. We investigated the performance using a BPSK modulation, two schemes were tested: A scheme of channel that includes deletion (BESC) and another that was proposed, using a Hamming code in series with a LT code. The LT-Hamming scheme present a gain code larger than BESC scheme and convolutional codes of similar characteristics. Was tested LT-Hamming scheme for different types of images on AWGN channel using the SPIHT technique for images compression. To obtain an objective measure of image quality was used the PSNR (Peak Signal Noise Ratio) and some images were presented in order to analize its quality through visual inspection given that LT code is a versatile for what concern the code rate it was proposed a method to assign different protection levels to the code information, UEP (Unequal Error Protection).

[pt] Esta dissertação aborda o estudo de códigos fontanais (códigos LT e códigos Raptor) que são uma classe de códigos criados para a transmissão de dados de maneira confiável e eficiente através de canais os quais podem ser modelados como canais com apagamento. Os códigos LT e códigos Raptor são denominados códigos fontanais, devido a que eles são uma boa aproximação para o conceito de fontanas digitais. Além disso, eles são classificados como códigos de taxa versátil, no sentido que o número de símbolos codificados que podem ser gerados a partir dos dados de entrada é potencialmente ilimitado. Códigos LT são capazes de recuperar, com probabilidade maior do que (1 − delta), um conjunto de k símbolos de entrada a partir de quaisquer k + O((raiz quadrada de k)(ln(2))(k/delta)) símbolos codificados recebidos, com uma média de O(k ln(k/delta)) operações XOR. Os códigos Raptor são uma extensão de códigos LT, na qual o processo de codificação é composto de duas etapas: um código de bloco de comprimento fixo (denominado pré- código) e um código LT com uma distribuição de graus apropriada. Investigou-se o desempenho dos códigos LT usando duas novas distribuições de graus (Sóliton Robusta Melhorada e Sóliton Robusta Truncada) e foi proposto um modelo de códigos LT Bidimensionais, na qual os símbolos de entrada são agrupados em forma de matriz. Neste esquema os blocos correspondentes às linhas da matriz são codificados usando um código LT e, em seguida, a matriz resultante tem suas colunas também codificadas usando um código LT. Ainda que a complexidade do esquema tenha sido dobrada o desempenho alcançado pelos códigos LT Bidimensionais superou o desempenho dos códigos LT convencionais para situações em que a qualidade do canal BEC é elevada. / [en] Fountain Codes (LT Codes and Raptor Codes) are a class of codes proposed to efficient and reliably transmit data through Erasure Channels. LT Codes and Raptor Codes are a good approximation to the concept of digital fountain and as such are named as fountain codes. They are said to be rateless codes in the sense that the number of symbols produced by the encoder could grow, potentially, to infinite. With probability of success larger than (1−delta), a decoder of an LT code based scheme can recover the k transmitted symbols from any received block of k + O((square root k)(ln(2))(k/delta)) correct symbols with an average of O(k ln(k/delta)) XOR operations. Raptor codes are an extension of the LT codes idea, with a tandem scheme where a fixed length block code (namely a pre- code) is followed by an LT code that uses a properly chosen degree distribution. In this dissertation the performance of LT codes with two recently proposed degree distributions, the Improved Robust Soliton and the Truncated Soliton Robust Distribution were investigated. A new scheme called Bidimensional LT Codes, has been proposed. In this scheme the input symbols are structured in a matrix form and afterwards the blocks corresponding to the lines of the matrix are encoded with an LT code. The columns of the new matrix so obtained are next encoded with a similar LT code. The complexity of the new scheme is doubled and yet its performance only just surpasses that of the conventional LT scheme for high quality BEC.

Fountain codes have demonstrated great results for the binary erasure channel and have already been incorporated into several international standards to recover lost packets at the application layer. These include multimedia broadcast/multicast sessions and digital video broadcasting on global internet-protocol. The rateless property of Fountain codes holds great promise for noisy channels. These are more sophisticated mathematical models representing errors on communications links rather than only erasures. The practical implementation of Fountain codes for these channels, however, is hampered by high decoding cost and delay. In this work we study trapping sets in Fountain codes over noisy channels and their effect on the decoding process. While trapping sets have received much attention for low-density parity-check (LDPC) codes, to our knowledge they have never been fully explored for Fountain codes. Our study takes into account the different code structure and the dynamic nature of Fountain codes. We show that 'error-free' trapping sets exist for Fountain codes. When the decoder is caught in an error-free trapping set it actually has the correct message estimate, but is unable to detect this is the case. Thus, the decoding process continues, increasing the decoding cost and delay for naught. The decoding process for rateless codes consists of one or more decoding attempts. We show that trapping sets may reappear as part of other trapping sets on subsequent decoding attempts or be defeated by the reception of more symbols. Based on our observations we propose early termination methods that use trapping set detection to obtain improvements in realized rate, latency, and decoding cost for Fountain codes. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2009-10-29 14:33:06.548

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.