LT code : decoding algorithm and its applications

Reliable transmission over error-prone channels is always a problem for network researchers. To control errors in transmissions, the technique Forward Error Correction (FEC) was proposed in 1940s. Among different coding schemes, Reed-Solomon and Low Density Parity Check codes are the most successful ones. Although these codes can achieve channel capacity, the performance relies on knowledge of channel condition since the coding rate is determined beforehand. To overcome this, fountain codes were proposed. For a given number of source symbols, fountain codes can generate potentially limitless encoded symbols. Luby Transform (LT) codes are the first realizations of fountain codes. The low complexity of both encoding and decoding makes LT codes applicable in many different applications from data transmission to storage system. This thesis is dedicated to improve LT decoding algorithm under certain circumstance and apply LT codes in multimedia transmission and in cloud storage system. Past research has shown that LT codes can perform well for a large number of source symbols. However, mathematical analysis and simulation results have revealed that the packet overhead for LT decoders can be as large as $100\%$ when the number of source symbols is small. LT-W decoding was proposed to tackle this problem. In the first part of this thesis, we make an observation that LT decoders often fail to recover all the source symbols, while LT encoders have a high probability of producing a full-rank coefficient matrix. Through rigorous analysis and extensive experiments, we show that LT-W decoding can dramatically reduce the overhead for LT codes with small input symbol. LT codes have been proven successful in content delivery due to their abilities to handle varying channel conditions without much feedback. However, original LT codes are not unable to provide intermediate outputs when delivering layer-coded media content. Although some methods have been proposed to produce intermediate outputs based on adjusting the distribution of LT codes, they are typically content-dependent and unable to guarantee that a more important layer can always be decoded before the decoding of a less important layer. In the second part of this thesis, we propose a simple joint Unequal Loss Protection (ULP) and LT coding (ULP-LT) scheme for layered media delivery, where different numbers of FEC are allocated to different layers to guarantee the priority and LT codes are used to deal with varying channel conditions. Simulation results show that with a small amount of overhead allocated to ULP, the ULP-LT scheme can produce good intermediate performance while still enjoying the nice features provided by LT codes. Lastly, we investigate the delay performance of a LT-based cloud storage system. LT codes are popular for storage systems due to their efficient recovery. However, in order to ensure high success decoding of LT codes based storage, retrieval of additional fragments is required, and this requirement could introduce additional delay. We show that multiple stage retrieval of fragments is effective to reduce the file-retrieval delay. We first develop a delay model for various multiple stage retrieval schemes applicable to our considered system. By employing the developed model, we study optimal retrieval schemes given requirements on success decodability. Our numerical results suggest a fundamental tradeoff between the file-retrieval delay and the target probability of successful file decoding, as well as that the file-retrieval delay can be significantly reduced by optimally scheduling packet requests in a multi-stage fashion.DOCTOR OF PHILOSOPHY (SCE