No description available.

Thesis (Ph. D.)--Oregon State University, 2008. / Printout. Includes bibliographical references (leaves 137-141). Also available on the World Wide Web.

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

The importance of quantum error correction in paving the way to build a practical quantum computer is no longer in doubt. Despite the large body of literature in quantum coding theory, many important questions, especially those centering on the issue of "good codes" are unresolved. In this dissertation the dominant underlying theme is that of constructing good quantum codes. It approaches this problem from three rather different but not exclusive strategies. Broadly, its contribution to the theory of quantum error correction is threefold. Firstly, it extends the framework of an important class of quantum codes - nonbinary stabilizer codes. It clarifies the connections of stabilizer codes to classical codes over quadratic extension fields, provides many new constructions of quantum codes, and develops further the theory of optimal quantum codes and punctured quantum codes. In particular it provides many explicit constructions of stabilizer codes, most notably it simplifies the criteria by which quantum BCH codes can be constructed from classical codes. Secondly, it contributes to the theory of operator quantum error correcting codes also called as subsystem codes. These codes are expected to have efficient error recovery schemes than stabilizer codes. Prior to our work however, systematic methods to construct these codes were few and it was not clear how to fairly compare them with other classes of quantum codes. This dissertation develops a framework for study and analysis of subsystem codes using character theoretic methods. In particular, this work established a close link between subsystem codes and classical codes and it became clear that the subsystem codes can be constructed from arbitrary classical codes. Thirdly, it seeks to exploit the knowledge of noise to design efficient quantum codes and considers more realistic channels than the commonly studied depolarizing channel. It gives systematic constructions of asymmetric quantum stabilizer codes that exploit the asymmetry of errors in certain quantum channels. This approach is based on a Calderbank- Shor-Steane construction that combines BCH and finite geometry LDPC codes.

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.

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.

Quantum error correction codes were introduced as a means to protect quantum information from decoherance and operational errors. Based on their approach to error control, error correcting codes can be divided into two different classes: block codes and convolutional codes. There has been significant development towards finding quantum block codes, since they were first discovered in 1995. In contrast, quantum convolutional codes remained mainly uninvestigated. In this thesis, we develop the stabilizer formalism for quantum convolutional codes. We define distance properties of these codes and give a general method for constructing encoding circuits, given a set of generators of the stabilizer of a quantum convolutional stabilizer code, is shown. The resulting encoding circuit enables online encoding of the qubits, i.e., the encoder does not have to wait for the input transmission to end before starting the encoding process. We develop the quantum analogue of the Viterbi algorithm. The quantum Viterbi algorithm (QVA) is a maximum likehood error estimation algorithm, the complexity of which grows linearly with the number of encoded qubits. A variation of the quantum Viterbi algorithm, the Windowed QVA, is also discussed. Using Windowed QVA, we can estimate the most likely error without waiting for the entire received sequence.

Quantum error correction codes were introduced as a means to protect quantum information from decoherance and operational errors. Based on their approach to error control, error correcting codes can be divided into two different classes: block codes and convolutional codes. There has been significant development towards finding quantum block codes, since they were first discovered in 1995. In contrast, quantum convolutional codes remained mainly uninvestigated. In this thesis, we develop the stabilizer formalism for quantum convolutional codes. We define distance properties of these codes and give a general method for constructing encoding circuits, given a set of generators of the stabilizer of a quantum convolutional stabilizer code, is shown. The resulting encoding circuit enables online encoding of the qubits, i.e., the encoder does not have to wait for the input transmission to end before starting the encoding process. We develop the quantum analogue of the Viterbi algorithm. The quantum Viterbi algorithm (QVA) is a maximum likehood error estimation algorithm, the complexity of which grows linearly with the number of encoded qubits. A variation of the quantum Viterbi algorithm, the Windowed QVA, is also discussed. Using Windowed QVA, we can estimate the most likely error without waiting for the entire received sequence.