CATALDI et al.: SLIDING-WINDOW RAPTOR CODES FOR EFFICIENT SCALABLE WIRELESS VIDEO BROADCASTING 1493
bols, where the degree is specified by a suitable statistical
distribution. A good design of the degree distribution is cru-
cial for the code performance. The Robust Soliton Distribution
(RSD)
, defined in [10], is characterized by two parameters:
, a suitable positive constant [10], and , representing the de-
coding failure probability when
coded symbols
are received. By decreasing
, the average degree of the coded
symbols increases and so does the complexity. It can be shown
that LT codes are asymptotically optimal, i.e.,
when
[10]. Nevertheless, LT codes exhibit more-than-linear
encoding/decoding complexity.
Raptor codes [11] represent an evolution of LT codes. They
exhibit lower complexity and at the same time excellent perfor-
mance. Raptor codes encompass a pre-coding stage (usually a
high rate low-density parity-check code—LDPC), concatenated
with an inner LT code, working on symbols obtained by prop-
erly grouping
bits at a time. The coding overhead of Raptor
codes is lower bounded by the overhead of the pre-code, and
does not vanish asymptotically as in the case of LT codes. The
decoding algorithm is composed of two steps. The inner LT de-
coder returns a hard bit-reliability vector. This latter is processed
by the outer LDPC decoder, using the belief propagation algo-
rithm [25]. This allows one to loosen the constraints on the LT
code degree distribution, as the pre-code is able to recover the
source symbols possibly not retrieved by LT decoding.
Notwithstanding their considerable performance and
promising applications in multimedia, DF codes also ex-
hibit some weaknesses. Because of their random nature, DF
codes achieve near-optimal performance with large data blocks
[10], [11]. Unfortunately, for short blocks, a random approach
can be inefficient in terms of overhead required to successfully
decode the original source.
B. Sliding-Window Principle
The concept of Sliding-Window Digital Fountain (SW-DF)
was first proposed in [24] for LT codes. The main idea is to
apply the DF code not on disjoint blocks of
source symbols,
but instead on a sliding window of length
. The presence of
memory between adjacent blocks allows to virtually extend the
block length, as is shown later in this section.
The traditional (fixed window—FW) coding approach, de-
picted in Fig. 1(a), can be compared to SW-DF reported in
Fig. 1(b). Each block of
source symbols is processed by a DF
code, generating a proper number
of coded symbols. After
the current block has been coded, the window is shifted
sym-
bols forward. Then, the DF code processes the new block of
input symbols, of which are new entries, whereas are
overlapped with the previous window.
For the sake of simplicity, let us assume that
is a multiple of
. In this way each source symbol enters successive
windows. In other words, if
is kept constant, as the window
shift
is decreased, the source symbols enter more and more
successive windows. We can define a virtual block length as
symbols, i.e., the length of the symbol sub-stream
where a given source symbol enters the encoding process. Let
us clarify this concept with an example. Let us assume
and and focus on a given source symbol, e.g., symbol 13.
Fig. 1. Comparison between fixed window and sliding window schemes.
(a) Traditional (FW) encoding scheme. (b) Sliding-window scheme.
TABLE I
M
AIN PARAMETERS OF
SW-DF
Windows 1 to 6 span the following source symbols: (1–5), (4–8),
(7–11), (10–14), (13–17). Symbol 13 is contained in
windows, i.e., 4 and 5. Hence, the interval in which symbol
13 can be picked up to form a coded symbol is (10–18), and
the virtual block length is
symbols. We
can notice that, by increasing the overlapping between adjacent
windows,
increases tending to the limit value .
Let
be the number of coded symbols output
per each source block of length
in the FW scheme. If SW-DF
is run with the same
, it will output a larger overall number of
symbols, as it processes a larger number of length-
blocks due
to the overlapping. In order to make SW-DF generate the same
coded symbol rate as the FW scheme, a number of symbols per
window smaller than
should be generated. In particular, the
same number of coded symbols generated by FW for each block
of length
, must be generated by SW-DF for each block of
length
. Hence, the number of symbols generated by SW-DF
for each window of length
is
(1)
It is worth noticing that, if
(i.e., no overlap), SW-DF
reduces to the FW case. Moreover, number of blocks tending
to infinity, the number of symbols generated becomes
. The main parameters that characterize SW-DF are
summarized in Table I.
This principle has been applied to LT codes in [24] (SW-LT
codes). The design of SW-LT codes is very similar to that of
traditional LT codes, the main difference lying in the degree
distribution, which takes into account the virtual data block ex-
tension. In fact, as a source data block has an actual span of
symbols as far as the generation of parity checks is con-
cerned, it is appropriate to consider a degree distribution over a
block length
. Although the degree distribution is designed
for block length
, the symbols are picked only within the cur-
rent window of size
. Hence, the computed degree distribution