25-01-2013, 02:27 PM
Expanding Window Fountain Codes for Unequal Error Protection
1Expanding Window.pdf (Size: 475.17 KB / Downloads: 29)
Abstract
A novel approach to provide unequal error protection
(UEP) using rateless codes over erasure channels, named
Expanding Window Fountain (EWF) codes, is developed and
discussed. EWF codes use a windowing technique rather than
a weighted (non-uniform) selection of input symbols to achieve
UEP property. The windowing approach introduces additional
parameters in the UEP rateless code design, making it more
general and flexible than the weighted approach. Furthermore,
the windowing approach provides better performance of UEP
scheme, which is confirmed both theoretically and experimentally.
INTRODUCTION
FOUNTAIN codes, also called rateless codes, were investigated
in [1] as an alternative to the automatic repeatrequest
(ARQ) schemes for reliable communication over lossy
networks. They enable the transmitter to generate a potentially
infinite stream of encoding symbols as random and equally
important descriptions of the message block of finite length.
RELATED WORK
In this section, a short overview of the recent work related
to the windowing UEP fountain scheme is provided. We focus
on recent contributions in fountain coding that provide UEP
property or are based on windowing techniques.
Rahnavard et al. [6] studied a class of fountain codes
which provide UEP and URT properties. In their work, the
message block to be transmitted is partitioned into classes of
different importance and input symbols from different classes
are assigned different probabilities of being chosen after a
degree of an output symbol has been selected, which produces
a bias towards certain classes of symbols. The assignment of
the probabilities is done in such a fashion that input symbols
from the more important classes are more likely to be chosen
in forming the output symbols, resulting in the UEP property.
Therefore, this approach is a generalization of LT codes in
which the neighbors of an output symbol are selected nonuniformly
at random.We refer to this approach as the weighted
approach.
Recently, different low-complexity approaches to fountain
coding were studied, where the set of input symbols is divided
into a number of overlapping subsets - windows, and only
input symbols from a predetermined window can be used in
forming each output symbol. To the best of our knowledge,
Studholme and Blake were the first to utilize windowing
approach in rateless codes, by introducing windowed erasure
codes [7], where only a certain predetermined portion of the
data set can be used in forming each output symbol. Their approach
aims for EEP fountain codes with low encoding complexity
and capacity achieving behavior assuming maximumlikelihood
(ML) decoding, and is particularly suitable for
short length codes. Targeting the real-time services such as
multimedia streaming, the sliding window fountain codes were
recently proposed in [8]. The sliding window fountain codes
move the fixed-sized window forward during the encoding
process, following the chronological ordering of data. For each
window position, the number of generated encoding symbols
is considerably smaller than the number of encoding symbols
neccessary to successfully decode the window based on those
symbols only, but since the consecutive windows overlap,
successful decoding at the receiver is still possible.
And-Or Tree Analysis of EWF Codes
The degree distributions derived in the previous section
allow us to apply asymptotic and-or tree (density evolution)
analysis on EWF codes. As a result, we obtain the expressions
for asymptotic erasure probabilities after