Fountain codes have recently gained wide attention in the communications research community due to their capacity-approaching performance and rateless properties that allow them to seamlessly adapt to unknown channel statistics. This thesis of fers two key contributions. For the first, we consider the problem of low complexity decoding of Luby Transform (LT) and Raptor codes, which are classes of Fountain codes. We introduce a decoding method which has a significantly reduced compu tational load compared to the commonly used alternative of message-reset decoding with a flooding schedule. This method combines the recently proposed technique of informed dynamic scheduling combined with incremental decoding. Simulation re sults for the example of the binary symmetric channel show complexity reductions (in terms of the total required number of decoding iterations) by 87% compared to conventional message-passing decoding and 54% compared to a recently proposed incremental decoding scheme for Raptor codes. Having proposed our novel decoding method, we then focus on applying rateless codes to free-space optical (FSO) transmission systems. FSO systems enable high speed communication with relatively small deployment costs. However, FSO systems suffer a critical disadvantage, namely susceptibility to fog, smoke, and similar con ditions. A possible solution to this dilemma is the use of hybrid systems employing FSO and radio frequency (RF) transmission. As for the second contribution of this thesis, we propose the application of rateless coding for such hybrid FSO/RF sys tems. The advantages of our approach are (i) the full utilization of available FSO and RF channel resources at any time and (ii) very little feedback from the receiver. In order to substantiate these claims, we establish the pertinent capacity limits for hybrid FSO/RF transmission and present simulation results for transmission with off-the-shelf Raptor codes, which achieve realized rates close to these limits under a wide range of channel conditions.

Fountain codes have recently gained wide attention in the communications research community due to their capacity-approaching performance and rateless properties that allow them to seamlessly adapt to unknown channel statistics. This thesis of fers two key contributions. For the first, we consider the problem of low complexity decoding of Luby Transform (LT) and Raptor codes, which are classes of Fountain codes. We introduce a decoding method which has a significantly reduced compu tational load compared to the commonly used alternative of message-reset decoding with a flooding schedule. This method combines the recently proposed technique of informed dynamic scheduling combined with incremental decoding. Simulation re sults for the example of the binary symmetric channel show complexity reductions (in terms of the total required number of decoding iterations) by 87% compared to conventional message-passing decoding and 54% compared to a recently proposed incremental decoding scheme for Raptor codes. Having proposed our novel decoding method, we then focus on applying rateless codes to free-space optical (FSO) transmission systems. FSO systems enable high speed communication with relatively small deployment costs. However, FSO systems suffer a critical disadvantage, namely susceptibility to fog, smoke, and similar con ditions. A possible solution to this dilemma is the use of hybrid systems employing FSO and radio frequency (RF) transmission. As for the second contribution of this thesis, we propose the application of rateless coding for such hybrid FSO/RF sys tems. The advantages of our approach are (i) the full utilization of available FSO and RF channel resources at any time and (ii) very little feedback from the receiver. In order to substantiate these claims, we establish the pertinent capacity limits for hybrid FSO/RF transmission and present simulation results for transmission with off-the-shelf Raptor codes, which achieve realized rates close to these limits under a wide range of channel conditions.

Fountain codes have recently gained wide attention in the communications research community due to their capacity-approaching performance and rateless properties that allow them to seamlessly adapt to unknown channel statistics. This thesis of fers two key contributions. For the first, we consider the problem of low complexity decoding of Luby Transform (LT) and Raptor codes, which are classes of Fountain codes. We introduce a decoding method which has a significantly reduced compu tational load compared to the commonly used alternative of message-reset decoding with a flooding schedule. This method combines the recently proposed technique of informed dynamic scheduling combined with incremental decoding. Simulation re sults for the example of the binary symmetric channel show complexity reductions (in terms of the total required number of decoding iterations) by 87% compared to conventional message-passing decoding and 54% compared to a recently proposed incremental decoding scheme for Raptor codes. Having proposed our novel decoding method, we then focus on applying rateless codes to free-space optical (FSO) transmission systems. FSO systems enable high speed communication with relatively small deployment costs. However, FSO systems suffer a critical disadvantage, namely susceptibility to fog, smoke, and similar con ditions. A possible solution to this dilemma is the use of hybrid systems employing FSO and radio frequency (RF) transmission. As for the second contribution of this thesis, we propose the application of rateless coding for such hybrid FSO/RF sys tems. The advantages of our approach are (i) the full utilization of available FSO and RF channel resources at any time and (ii) very little feedback from the receiver. In order to substantiate these claims, we establish the pertinent capacity limits for hybrid FSO/RF transmission and present simulation results for transmission with off-the-shelf Raptor codes, which achieve realized rates close to these limits under a wide range of channel conditions. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

Network coding (NC) is an optimal data dissemination technique where intermediate nodes linearly combine incoming packets. To recover a network-coded message, a sink must use a Gaussian elimination decoder, but this high-complexity decoder may not be acceptable in resource-constrained applications like sensor networks. A good alternative to Gaussian elimination is for the sink to apply the well-known belief propagation (BP) algorithm; however, the performance and complexity of BP decoding is dependent on the statistics of the linearly-combined packets. In this work, we propose two protocols that address this issue by applying fountain coding paradigms to network codes. For a two-source, single-relay, and single-sink network, named the Y-network, if the relay can network-code incoming packets while maintaining the key properties of the fountain code, then BP decoding can be applied efficiently to recover the original message. Particularly, the sink should see a Soliton-like degree distribution for efficient BP decoding. The first protocol, named Soliton-like rateless coding (SLRC), recognizes that certain encoded packets are essential for BP decoding to perform well. Therefore, the relay protects these important packets by immediately forwarding them to the sink. It can be shown analytically that the proposed scheme is resilient to nodes leaving the transmission session. Through simulations, the SLRC scheme is shown to perform better than buffer-and-forwarding, and the Distributed LT code. Although SLRC achieves good performance, the degree distribution seen by the sink is non-optimal and assumes that a large number of packets can be buffered, which may not always be possible. Extending SLRC, we propose the Improved Soliton-like Rateless Coding (ISLRC) protocol. Assuming a resource-constrained relay, the available resources at the relay are effciently utilized by performing distribution shaping; packets are intelligently linearly combined. The aggregate degree distribution for the worst case is derived and used in performing an asymptotic error analysis using an AND-OR tree analysis. Simulation results show that even under the worst case scenario of ISLRC, better performance can be achieved compared to SLRC and other existing schemes. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2011-10-07 21:13:03.862

This thesis investigates four FEC (forward error correction) coding schemes for their suitability for a broadcast system where there is one energy-rich transmitter and many energy-constrained receivers with a variety of channel conditions. The four coding schemes are: repetition codes (the baseline scheme); Reed-Solomon (RS) codes; Luby-Transform (LT) codes; and a type of RS and LT concatenated codes. The schemes were tested in terms of their ability to achieve both high average data reception success probability and short data reception time at the receivers (due to limited energy). The code rate (Rc) is fixed to either 1/2 or 1/3. Two statistical channel models were employed: the memoryless channel and the Gilbert-Elliott channel. The investigation considered only the data-link layer behaviour of the schemes. During the course of the investigation, an improvement to the original LT encoding process was made, the name LTAM (LT codes with Added Memory) was given to this improved coding method. LTAM codes reduce the overhead needed for decoding short-length messages. The improvement can be seen for decoding up to 10000 number of user packets. The maximum overhead reduction is as much as 10% over the original LT codes. The LT-type codes were found to have the property that can both achieve high success data reception performance and flexible switch off time for the receivers. They are also adaptable to different channel characteristics. Therefore it is a prototype of the ideal coding scheme that this project is looking for. This scheme was then further developed by applying an RS code as an inner code to further improve the success probability of packet reception. The results show that LT&RS code has a significant improvement in the channel error tolerance over that of the LT codes without an RS code applied. The trade-off is slightly more reception time needed and more decoding complexity. This LT&RS code is then determined to be the best scheme that fulfils the aim in the context of this project which is to find a coding scheme that both has a high overall data reception probability and short overall data reception time. Comparing the LT&RS code with the baseline repetition code, the improvement is in three aspects. Firstly, the LT&RS code can keep full success rate over channels have approximately two orders of magnitude more errors than the repetition code. This is for the two channel models and two code rates tested. Secondly, the LT&RS code shows an exceptionally good performance under burst error channels. It is able to maintain more than 70% success rate under the long burst error channels where both the repetition code and the RS code have almost zero success probability. Thirdly, while the success rates are improved, the data reception time, measured in terms of number of packets needed to be received at the receiver, of the LT&RS codes can reach a maximum of 58% reduction for Rc = 1=2 and 158% reduction for Rc = 1=3 compared with both the repetition code and the RS code at the worst channel error rate that the LT&RS code maintains almost 100% success probability.

Fountain codes were introduced to provide higher reliability, lower complexities, and more scalability for networks such as the Internet. In this thesis, we study Luby- Transform (LT) codes which are the realization of Fountain codes. In the LT codes, a sparse random factor graph is dynamically generated on both the encoder and decoder sides of the communications channel. The graph is generated from an ensemble degree distribution. The LT codes are also known as rateless codes, in the sense that they can generate potentially limitless codeword symbols from original data and self-adjust to channels with different erasure probabilities. LT Codes also have a very low encoding and decoding complexities when comparing with some traditional block codes, e.g., Reed Solomon (RS) codes and Low-Density-Parity-Check (LDPC) codes. Therefore, LT Codes are suitable for many different kinds of applications such as broadcast transmission. LT codes achieve the capacity of the Binary Erasure Channel (BEC) asymptotically and universally. For finite lengths, the search is continued to nd codes closer to the capacity limits at even lower encoding and decoding complexities. Most previous work on single-layer Fountain coding targets the design via the right degree distribution. The left degree distribution of an LT code is left as Poisson to protect the universality. For finite lengths, this is no longer an issue; thus, we focus on the design of better codes for the BEC and noisy channels as well at practical lengths. We propose two encoding schemes for BEC and noisy channels by shaping the left degree distribution. Our left degree shaping provides codes outperforming regular LT code and all other competing schemes in the literature. For instance, at a bit error rate of 10_{-7} and k = 256, our scheme provides a realized rate of 0.6 which is 23.5% higher than Sorensen et al.'s scheme over BEC. In addition, over noisy channels our proposed scheme achieves an improvement of 14% in the released rates at k = 100 and 30 Belief Propagation (BP) iterations. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2013-08-22 19:40:59.885

[pt] A construção de novos códigos através de modificações (alongamento, puncionamento, etc) de um código conhecido é uma prática comum quando se lida com códigos clássicos. Neste trabalho é mostrado que bons códigos podem ser obtidos com algumas dessas técnicas, aparentemente não efetivas aos códigos fontanais. Os Códigos LT (Luby Transform) Sistemáticos Alongados são apresentados e, a partir de simulações realizadas em programa desenvolvido para tal, mostra-se um melhor desempenho em relação aos seus códigos-mãe correspondentes, sob uma mesma condição de redundância. A técnica de alongamento pode ser bastante útil, minimizando a necessidade de trabalhar-se com blocos de informação grandes, caracterizada nos códigos fontanais e, por conseqüência, nos códigos LT. / [en] Construction of new codes by modifying (extending,puncturing,etc) a known code is common practice when dealing with classical codes.We have shown in this thesis that good codes can be obtained with these techniques,apparently not effective for fountain codes.Lengthened Systematic Luby Transform Codes have being demonstrated ,through simulation ,to perform better when compared to the mother codes, under the same redundancy condition.Lengthening might be a useful technique which alleviates the need for large frame requirements posed by the fountain codes.

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.

No description available.

Thesis (MScEng)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The discovery of sparse graph codes, used in forward error correction strate- gies, has had an unrivaled impact on Information theory over the past decade. A recent advancement in this field, called Fountain codes, have gained much attention due to its intelligent rate adaptivity, and lend itself to applications such as multicasting and broadcasting networks. These particular properties can be considered valuable in a wireless sensor network setting as it is capable of providing forward error correction, and the added conceptual network protocol related extensions. A wireless sensor network testbed in France, called SensLAB, provides an experimental facility for researchers to develop and evaluate sensor network protocols, aside from a simulation environment. Tremendous value can be added to the SensLAB community if an appropriate forward error correction design, such as Fountain codes, is deemed feasible for use on such a platform. This thesis investigates the use of Fountain codes, in a binary erasure channel environment, as a forward error correction strategy for the distribution of reliable data content over the SensLAB platform. A short message length LT code using two different decoding mechanisms were developed and evaluated for possible implementation. Furthermore, a short message length Raptor code was developed by using supplementary theory and optimisation techniques that permit scalability in terms of the message size. The results favoured the Raptor code design as it performs close to near optimal while still satisfying the rateless- and universality property, at low computational complexity. / AFRIKAANSE OPSOMMING: Die ontdekking van yl-grafiekkodes, van toepassing op foutkorreksie strategieë, het onlangs 'n ongeewenaarde impak op Informasieteorie gehad. In 'n onlangse vooruitgang in hierdie veld, genoem Fonteinkodes, word daar meer fokus geplaas op die intelligente tempo aanpassingsvermoë van hierdie kodes, wat nuttige toepassing kan inhou in multi-saai- en uitsaai netwerke. Hierdie eienskappe kan moontlik as waardevol beskou word in draadlose sensor netwerke weens die fout regstellingsvermoë en die bykomende konseptuele netwerk protokol verwante uitbreidings. 'n Draadlose sensor netwerk toetsplatvorm in Frankryk, genoem die SensLAB, bied navorsers die geleentheid om eksperimentele sensor netwerk protokolle te ontwikkel en te toets buite 'n tipiese simulasie-omgewing. Groot waarde kan bygevoeg word aan die SensLAB gemeenskap indien 'n geskikte foutkorreksie strategie ontwikkel word, soos Fonteinkodes, en as geskik beskou kan word vir hierdie platvorm. In hierdie tesis word Fonteinkodes saam met die SensLAB platvorm ondersoek, binne die raamwerk van 'n binêre verlieskanaal, om vir foutkorreksie oor die verspreiding van betroubare data in SensLAB op te tree. 'n Kort boodskap LT kode word voorgestel deur van twee verskillende dekoderings meganismes gebruik te maak. 'n Alternatief, genaamd Raptorkode, was ook ondersoek. 'n Raptorkode. 'n Kort boodskap Raptor kode, wat ontwikkel is met bykomende teorie en optimeringstegnieke, word ook voorgestel. Die bykomende tegnieke bied 'n skaleerbare boodskap lengte terwyl dit tempoloos en universeel bly, en lae kompleksiteit bied.