19-01-2013, 11:27 AM
Raptor Codes
1Raptor Codes.pdf (Size: 603.12 KB / Downloads: 99)
Abstract
LT-codes are a new class of codes introduced by Luby
for the purpose of scalable and fault-tolerant distribution of data
over computer networks. In this paper, we introduce Raptor codes,
an extension of LT-codes with linear time encoding and decoding.
We will exhibit a class of universal Raptor codes: for a given integer
and any real , Raptor codes in this class produce a
potentially infinite stream of symbols such that any subset of symbols
of size is sufficient to recover the original symbols
with high probability. Each output symbol is generated using
operations, and the original symbols are recovered
from the collected ones with operations.
We will also introduce novel techniques for the analysis of the
error probability of the decoder for finite length Raptor codes.
Moreover, we will introduce and analyze systematic versions of
Raptor codes, i.e., versions in which the first output elements of
the coding system coincide with the original elements.
INTRODUCTION
THE binary erasure channel (BEC) of communication was
introduced by Elias [1] in 1955, but it was regarded as a
rather theoretical channel model until the large-scale deployment
of the Internet about 40 years later.
On the Internet, data is transmitted in the form of packets.
Each packet is equipped with a header that describes the source
and the destination of the packet, and often also a sequence
number describing the absolute or relative position of the packet
within a given stream. These packets are routed on the network
from the sender to the receiver. Due to various reasons, for example
buffer overflows at the intermediate routers, some packets
may get lost and never reach their destination. Other packets
may be declared as lost if the internal checksum of the packet
does not match. Therefore, the Internet is a very good real-world
model of the BEC.
FOUNTAIN CODES AND LT-CODES
The theoretical idea of Fountain codes was introduced in [4]
and the first practical realizations of Fountain codes were invented
by Luby [5]–[7]. They represent a new class of linear
error-correcting codes. Let be a positive integer, and let be
a degree distribution on . A Fountain code with parameters
has as its domain the space of binary strings of length
, and as its target space the set of all sequences over , denoted
by . Formally, a Fountain code with parameters
is a linear map in which the coordinates are independent
random variables with distribution over . The block
length of a Fountain code is potentially infinite, but in applications
we will solely consider truncated Fountain codes, i.e.,
Fountain codes with finitely many coordinates, and make frequent
and implicit use of the fact that unlike traditional codes
the length of a Fountain code is not fixed a priori.
RAPTOR CODES
The results of the previous section imply that LT-codes
cannot be encoded with constant cost if the number of collected
output symbols is close to the number of input symbols. In this
section, we will present a different class of Fountain codes. One
of the many advantages of the new construction is that it allows
for encoding and decoding with constant cost, as we will see
below.
FINITE-LENGTH ANALYSIS OF RAPTOR CODES
The analysis in the previous section is satisfactory from an
asymptotic but not from a practical point of view. The analysis
of the decoding process of the corresponding LT-codes relies
on martingale arguments to enable upper bounds on the error
probability of the decoder. The same is true for the pre-code.
Such bounds are very far from tight, and are especially bad when
the number of input symbols is small.
In this section, we will introduce a different type of error analysis
for Raptor codes of finite length with BP decoding. This
analysis relies on the exact calculation of the error probability
of the LT-decoder, derived in [11], combined with the calculation
of the error probability for certain LDPC codes [17].