Ebook
Fountain Codes, LT Codes, and Raptor Codes
Gökhan GÜL gg@tf.uni-kiel.de Susmita Adhikari susmita_adhikari@hotmail.com Eduard Mustafin emu@tf.uni-kiel.de
Abstract—In this paper, first we explain Fountain Codes. Second, the first practical applications of Fountain Codes, LT codes are treated. Last but not least, based on LT codes and a pre-coding scheme so called Raptor Codes are presented with some record-breaking properties.
I. INTRODUCTION The Binary Erasure Channel (BEC) is a channel model where the receiver either receives the transmitted bit or is informed with the erasure of the bit, that is, the bit was not received or erased. Therefore, the receiver has no idea about the transmitted bit with a certain probability p, and is exactly sure about the transmitted bit with a certain probability 1-p. According to Shannon, the capacity of BEC is 1-p, which means that for the alphabet size of 2 k , where k is the number of bits in the alphabet, no more than (1 − p )k bits/symbol can be reliably communicated over the binary erasure channel. Additionally, any feedback from the receiver to the transmitter will not increase the capacity of the channel and reliable communication should be possible at this rate. Automatic Repeat Request (ARQ) schemes have so long been used as a classical approach to solve the reliable communication problem [6]. However, excessive number of feedbacks used in the case of erasures causes wasteful usage of bandwidth, network overloads and intolerable delays. Another approach is to use Forward Error Correcting (FEC) codes. Very powerful FEC codes exist such as Reed-Solomon codes, which can recover K source symbols from any K encoded symbols of N total number of transmitted symbols. However, the rate R = K N should be determined in compliance with the erasure probability p, before the transmission. If p changes or is less or more than the expected, this either will cause problems on the decoder side or will result a rate less than the
Gökhan GÜL gg@tf.uni-kiel.de Susmita Adhikari susmita_adhikari@hotmail.com Eduard Mustafin emu@tf.uni-kiel.de
Abstract—In this paper, first we explain Fountain Codes. Second, the first practical applications of Fountain Codes, LT codes are treated. Last but not least, based on LT codes and a pre-coding scheme so called Raptor Codes are presented with some record-breaking properties.
I. INTRODUCTION The Binary Erasure Channel (BEC) is a channel model where the receiver either receives the transmitted bit or is informed with the erasure of the bit, that is, the bit was not received or erased. Therefore, the receiver has no idea about the transmitted bit with a certain probability p, and is exactly sure about the transmitted bit with a certain probability 1-p. According to Shannon, the capacity of BEC is 1-p, which means that for the alphabet size of 2 k , where k is the number of bits in the alphabet, no more than (1 − p )k bits/symbol can be reliably communicated over the binary erasure channel. Additionally, any feedback from the receiver to the transmitter will not increase the capacity of the channel and reliable communication should be possible at this rate. Automatic Repeat Request (ARQ) schemes have so long been used as a classical approach to solve the reliable communication problem [6]. However, excessive number of feedbacks used in the case of erasures causes wasteful usage of bandwidth, network overloads and intolerable delays. Another approach is to use Forward Error Correcting (FEC) codes. Very powerful FEC codes exist such as Reed-Solomon codes, which can recover K source symbols from any K encoded symbols of N total number of transmitted symbols. However, the rate R = K N should be determined in compliance with the erasure probability p, before the transmission. If p changes or is less or more than the expected, this either will cause problems on the decoder side or will result a rate less than the