Inactivation Decoding of LT and Raptor Codes:
Analysis and Code Design

arXiv:1706.05814v1 [] 19 Jun 2017

Francisco Lázaro, Student Member, IEEE, Gianluigi Liva, Senior Member, IEEE,
Gerhard Bauch, Fellow, IEEE

Abstract—In this paper we analyze LT and Raptor codes under
inactivation decoding. A first order analysis is introduced, which
provides the expected number of inactivations for an LT code, as
a function of the output distribution, the number of input symbols
and the decoding overhead. The analysis is then extended to the
calculation of the distribution of the number of inactivations.
In both cases, random inactivation is assumed. The developed
analytical tools are then exploited to design LT and Raptor codes,
enabling a tight control on the decoding complexity vs. failure
probability trade-off. The accuracy of the approach is confirmed
by numerical simulations.
Index Terms—Fountain codes, LT codes, Raptor codes, erasure
correction, maximum likelihood decoding, inactivation decoding.

I. I NTRODUCTION

F

OUNTAIN codes [3], [4] provide an efficient solution
for data delivery to large user populations over broadcast
channels. The result is attained by encoding the data object
(e.g., a file) through an (n, k) linear code, where the number
of output (i.e., encoded) symbols n can grow indefinitely, enabling a simple rate adaptation to the channel conditions. Due
to this, fountain codes are often regarded as rateless codes.
Fountain codes were originally conceived for transmission
over erasure channels. In practice, different users experience
a different channel quality resulting in a different erasure
probability. When an efficient fountain code is employed, after
a user has received m = k +δ output symbols, with δ small, the
original input symbols can be recovered with high probability.
Luby transform (LT) codes were introduced in [5] as a first
example of practical fountain codes. In [5] an iterative erasure
decoding algorithm was introduced that performs remarkably
Francisco Lázaro and Gianluigi Liva are with the Institute
of Communications and Navigation of the German Aerospace
Center (DLR), Muenchner Strasse 20, 82234 Wessling, Germany.
Email:{Francisco.LazaroBlasco, Gianluigi.Liva}@dlr.de.
Gerhard Bauch is with the Institute for Telecommunication, Hamburg
University of Technology, Hamburg, Germany. E-mail: Bauch@tuhh.de.
Corresponding Address: Francisco Lázaro, KN-SAN, DLR, Muenchner
Strasse 20, 82234 Wessling, Germany. Tel: +49-8153 28-3211, Fax: +49-8153
28-2844, E-mail: Francisco.LazaroBlasco@dlr.de.
This work has been presented in part at the 54th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, USA,
September 2015 [1], and at the 2014 IEEE Information Theory Workshop,
Hobart, Tasmania, November 2014 [2].
This work has been accepted for publication in IEEE Transactions on
Communications, DOI: 10.1109/TCOMM.2017.2715805
c 2017 IEEE. Personal use of this material is permitted. Permission from
IEEE must be obtained for all other uses, in any current or future media,
including reprinting /republishing this material for advertising or promotional
purposes, creating new collective works, for resale or redistribution to servers
or lists, or reuse of any copyrighted component of this work in other works

well when the number of input symbols k is large. Raptor
codes [6]–[8] address some of the shortcomings of LT codes.
A Raptor code is a serial concatenation of an (h, k) outer linear
block code with an inner LT code.
Most of the literature on LT and Raptor codes considers
iterative decoding (see e.g. [9]–[15]). In [9], [14], [16] LT
codes under iterative decoding were analyzed using a dynamic
programming approach. This analysis models the iterative
decoder as a finite state machine and it can be used to derive
the probability of decoding failure of LT codes under iterative
decoding. Iterative decoding is particularly effective for large
input block sizes, with k at least in the order of several tens
of thousands symbols [8]. However, in practice, moderate and
small values of k are often used, due to memory limitations at
the receiver side, or due to the fact that the piece of data to be
transmitted is small. For example, the recommended value of
k for the Raptor codes standardized in [17] is between 1024
and 8192 symbols. In this regime, iterative decoding of LT
and Raptor codes turns to be largely sub-optimum. In actual
implementations, different decoding algorithms are used. In
particular, an efficient maximum likelihood (ML) decoding
algorithm usually referred to as inactivation decoding [18],
[19] is frequently employed.
Inactivation decoding belongs to a large class of Gaussian
elimination algorithms tailored to the solution of large sparse
linear systems [20]–[25]. The algorithm can be seen as an
extension of iterative decoding, where whenever the iterative
decoding process stops, a variable (input symbol) is declared
as inactive (i.e., removed from the equation system) and
iterative decoding is resumed. At the end of the process, the
inactive variables have to be solved using Gaussian elimination. If a unique solution is found, it is possible to recover all
the remaining input symbols by back-substitution (i.e., using
iterative decoding). A few works addressed the performance
of LT and Raptor codes under inactivation decoding. The
decoding failure probability of several types of LT codes
was thoroughly analyzed via tight lower and upper bounds in
[26]–[29]. In [30] the distance spectrum of fixed-rate Raptor
codes is characterized, which enables the evaluation of their
performance under ML erasure decoding (e.g., via upper union
bounds [31], [32]). Upper bounds on the failure probability
for binary and non-binary Raptor codes are introduced in
[33]. However, none of these works addressed inactivation
decoding from a complexity viewpoint. In fact, the complexity
of inactivation decoding grows with the third power of the
number of inactivations [24]. It is hence of large practical
interest to develop a code design which leads (on average) to

2

SUBMITTED TO IEEE TRANSACTIONS ON COMMUNICATIONS

a small number of inactivations.
In [25], inactivation decoding of low-density parity-check
(LDPC) codes was analyzed, providing a reliable estimate
of the expected number of inactivations. The approach of
[25] relies on bridging the inactivation decoder with the
Maxwell decoder of [34]. By establishing an equivalence
between inactive and guessed variables, it was shown how
to exploit the Area Theorem [35] to derive the average
number of inactivations. Though, the approach of [25] cannot
be extended to LT and Raptor codes due to their rateless
nature. In [36] the authors proposed a new degree distribution
design criterion to design the LT component of Raptor codes
assuming inactivation decoding. However, when this criterion
is employed there is not a direct control on the average output
degree. In [37], the authors present a finite length analysis of
batched sparse codes under inactivation decoding that provides
the expected number of inactivations needed for decoding.
In this paper we provide a thorough analysis of LT and Raptor codes under inactivation decoding. A first order analysis
is introduced, which allows estimating the expected number
of inactivations for an LT code, as a function of the output
distribution, the number of input symbols and the decoding
overhead. The analysis is then extended to the calculation of
the distribution of the number of inactivations. In both cases,
random inactivation is assumed. The developed analytical tools
are then exploited to design LT and Raptor codes, enabling a
tight control on the decoding complexity vs. failure probability
trade-off. The work presented in this paper is an extension of
the work in [1]. In particular, the different proofs in [1] have
been modified and extended. Furthermore, in this work we
not only consider LT codes but also a class of Raptor Codes.
An analysis based on a Poisson assumption approximation is
presented in the Appendix1 .
The rest of the paper is structured as follows. In Section II
we present the system model considered in this paper. Section III contains a detailed description of inactivation decoding
applied to LT codes. In Section IV we focus on the analysis
of LT codes under inactivation decoding. Section V shows
how to exploit the analysis of the LT component of a Raptor
code to estimate the number of inactivations for the Raptor
code. A Raptor code design methodology is presented too.
The conclusions are presented in Section VI.

II. P RELIMINARIES
Let v = (v1, v2, ..., vk ) be the k input symbols, out
of which the LT encoder generates the output symbols
c = (c1, c2, ..., cn ), where n can grown indefinitely. Each output
symbol is generated by first sampling a degree d from an
output degree distribution Ω = (Ω1, Ω2, Ω3, . . . Ωdmax ), where
dmax is the maximum output degree. In the following, we
1 In the Appendix we provide a simplified analysis, which, though related
to the one in [2], is fully developed here on the basis of the analysis provided
in Section IV of this paper. The simplified analysis is based on a Poisson
approximation, which is analyzed in depth in the Appendix, discussing its
limitations and comparing the analytical results with Monte Carlo simulations.

m

·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·

·
·
·


·
·
·
·
·
·
·
·
·
·
·
·


·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·

·
·

·
·
·
·
·
·

·

·
·

·
·
·

·
·
·
·

·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·

·
·
·
·



·
·
·

·
·

·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·


·
·
·
·
·
·
·
·


·
·
·

·
·
·
·
·

·
·

·
·
·

·

·
·

·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·


·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·
·
·
·
·

·
·
·


·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·



·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·

·
·
·
·
·

·
·

·
·
·
·

·
·
·
·

·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·

·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·


·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·

·
·
·
·
·

·
·
·

·


·

·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·

·
·
·
·
·
·

·


·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

·
·


·
·
·
·

·


·
·


·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·
·
·
·
·

·

·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·

·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·



·

·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·


·
·
·
·
·
·
·

·
·
·

·

·
·
·
·
·

·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·

·

·
·
·
·

·
·
·
·


·
·
·
·
·
·
·
·
·
·


·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·

·
·


·
·


·
·
·
·
·
·
·
·


·

·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·

·
·
·

·
·
·

·
·
·



·
·

·
·
·
·

·
·
·



·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·

·

·
·
·
·

·

·
·
·
·

·

·


·

·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·


·
·
·
·
·
·
·
·
·

·
·
·

·

·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·


·
·
·
·

·
·
·
·
·


·

·
·
·
·
·
·

·

·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·
·
·

·
·
·

·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·


·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·





·
·
·
·

·
·
·
·
·

·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·

·
·
·
·

·
·
·



·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·


·
·

·

·
·
·
·

·
·
·

·

·
·

·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·

·
·


·
·
·
·

·

·

·

·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·
·



·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·


·

·
·
·
·
·

·


·
·

·
·

·
·
·
·
·

·
·
·
·

·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·

·
·
·
·
·
·


·
·
·
·

·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·


·

·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·

·



·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·

·


·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·
·
·
·
·
·
·


·
·

·
·
·
·
·
·


·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·



·
·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·

·


·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·

·

·

·
·
·
·
·
·
·
·

·
·
·


·
·
·


·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·


·
·
·

·


·

·
·
·
·
·
·
·

·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·

·
·
·

·

·
·


·
·
·
·

·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·
·
·

·
·
·
·


·

·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·

·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·

·
·
·

·
·
·
·

·
·

·
·


·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·

·
·


·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·

·
·

·
·


·
·
·
·
·

·


·
·
·
·
·
·
·

·
·
·
·


·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·


·
·
·

·
·
·
·
·


·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·


·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·

·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·

·

·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·

·
·
·

·
·
·
·



·
·
·


·
·
·



·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·

·
·
·
·
·
·

·

·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·

·
·
·
·
·

·
·

·

·
·
·

·
·
·

·
·
·
·
·
·
·
·

·
·
·
·

·
·
·
·

·
·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·
·
·
·
·
·
·


·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·

·
·


·

·
·
·

·


·

·
·
·
·
·
·
·
·
·




·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·

·
·
·
·
·

·
·
·
·
·
·
·
·


·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

k
Fig. 1. Structure of the matrix G0T .

will make use of a polynomial representation of the degree
distribution in the form
Õ
Ω(x) :=
Ωd xd
d

where x is a dummy variable. Then, d distinct input symbols
are selected uniformly at random and their x-or is computed
to generate the output symbol. The relation between output
and input symbols can be expressed as
c = vG
where G is the generator matrix of the LT code.
The output symbols are transmitted over a binary erasure
channel (BEC) at the output of which the receiver collects
m = k + δ output symbols, where δ is referred to as absolute
receiver overhead. Similarly, the relative receiver overhead is
defined as  := δ/k. Denoting by y = (y1, y2, . . . , ym ) the m
received output symbols and by I = {i1, i2, . . . , im } the set of
indices corresponding to the m non-erased symbols, we have
y j = ci j .
This allows us to express the dependence of the received
output symbols on the input symbols as
G0T v T = y T

(1)

with G0 given by the m columns of G with indices in I.
ML erasure decoding requires the solution of (1). Note that
decoding is successful (i.e., the unique solution can be found)
if and only if rank [G0 ] = k.
III. I NACTIVATION D ECODING OF LT C ODES
Inactivation decoding is an efficient ML erasure decoding
algorithm, which can be used to solve the system of equations
in (1). We will illustrate inactivation decoding by means of an
example and with the aid of Figures 1 and 2. In the example,
we fix k = 50 and m = 60. The structure of G0T is given in
Figure 1 (in the figure, dark squares represent the non-zero
elements of G0T ). Inactivation decoding consists of 4 steps.

FRANCISCO LÁZARO ET AL.: INACTIVATION DECODING OF LT AND RAPTOR CODES: ANALYSIS AND CODE DESIGN

k−α

m−k+α


·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·

·
·
·
·



·

·

·


·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·



·
·


·

·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·


·

·
·

·
·
·
·
·

·
·

·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·

·
·
·
·
·
·
·
·

·

·
·
·
·

·

·

·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·

·

·
·
·


·


·
·
·
·
·

·

·
·

·

·
·

·
·
·

·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·


·
·
·
·
·
·

·
·
·

·
·
·

·

·
·

·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·

·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·

·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·

·
·
·
·

·



·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·


·


·
·
·
·
·
·
·
·


·
·
·
·

·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·

·


·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·


·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·


·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·

·
·

·
·

·
·
·
·
·


·
·

·
·
·
·
·

·


·
·
·
·

·
·
·



·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·


·


·
·
·
·

·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·

·


·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·

·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·



·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·

·
·
·
·
·

·

·

·

·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·


·

·
·

·
·
·


·


·
·


·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·

·
·

·
·
·

·
·

·


·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

·


·
·

·
·


·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·

·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·

·

·
·

·
·
·
·
·

·

·
·
·
·
·
·

·

·
·

·
·

·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·

·
·
·

·
·
·
·

·
·


·
·

·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·

·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·

·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·



·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·



·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·

·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·



·

·


·
·
·
·

·

·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·


·
·
·
·
·
·

·

·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·

·

·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·
·

·
·
·

·


·


·
·
·
·

·

·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·



·

·
·
·
·
·
·
·
·
·


·
·


·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·

·
·

·
·
·
·
·
·
·
·
·
·

·

·
·
·





·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·



·
·
·
·
·
·


·
·
·


·



·
·
·


·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·
·


·
·


·


·
·
·
·


·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·


·
·
·

·
·
·
·
·
·
·
·

·

·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·


·

·
·

·
·
·




·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·

·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·
·


·
·
·
·
·
·


·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·


·
·
·
·
·
·

·
·


·

·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·

·
·
·
·
·

·
·
·
·
·
·
·
·

·

k−α

(a) Triangulation process.

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·



·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·

·
·



·
·
·
·

·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·

·

·

·

·
·


·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·

·
·
·

·
·
·
·
·
·

·

·
·
·
·
·
·
·
·



·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·


·
·
·

·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·

·
·
·
·
·
·

·

·
·
·
·

·
·
·



·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·


·
·
·
·

·
·
·
·
·

·
·

·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·

·
·
·
·
·

·
·
·


·
·

·

·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·

·
·
·


·
·

·

·
·
·
·
·


·
·
·
·
·

·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·

·

·
·
·
·
·
·
·

·

·
·
·
·
·
·

·
·
·

·
·
·
·

·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·

·
·
·
·
·

·
·
·
·

·


·
·
·
·


·

·
·
·

·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·

·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·









·
·
·

·
·




·
·

·
·
·

·
·

·


·



·


·


·

·
·
·
·

·
·
·
·
·
·
·
·





·
·
·
·
·






·
·
·
·
·



·

·


·
·
·
·

·

·
·
·

·
·

·

·
·

·

·
·

k−α

α

·
·
·
·
·
·


·
·
·
·
·
·
·
·
·

·
·
·





·
·
·

·



·
·

·


·
·



·
·




·
·
·







·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·


·

·
·

·


·
·
·
·
·
·

·


·

·

·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·


·
·




·





·


·
·

·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·




·
·
·

·






·

·

·

·
·
·
·

·
·




α

(b) Zero matrix procedure.

·
·
·
·
·

·
·
·
·


·


·





·
·
·

·





·









·
·
·


·

·


·
·
·
·
·


·


·
·
·
·

·


·
·
·

·
·
·

·

·
·
·




·
·

·
·
·



·


·

·

·

·
·
·
·


·



·
·


·
·
·

·
·


·
·
·

·
·
·
·
·
·



·




·
·



·

·






·
·



·
·



·

·



·
·
·
·
·
·
·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

k−α

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·









·
·
·

·
·




·
·

·
·
·

·
·


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·





·
·
·
·
·






·
·
·
·
·



·

·


·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·


·
·
·
·
·
·
·
·
·

·
·
·





·
·
·

·



·
·

·


·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·


·
·
·
·
·


·

·
·

·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·


·
·

·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·




·
·
·

·



·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

α

(c) Gaussian elimination.

·
·
·
·
·

·
·
·
·


·


·





·
·
·

·





·









·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·


·
·
·

·
·
·

·

·
·
·




·
·

·
·
·



·


·

·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·


·
·
·

·
·
·
·
·
·



·




·
·



·

·






·
·



·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

3


·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

k−α

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·

α

(d) Back-substitution.

Fig. 2. Structure of G0T as inactivation decoding proceeds.

Step 1 (Triangulation). Initially, G0T is put in an approximate lower triangular form by means of column and row
permutations only. Given that no operation is performed on
the rows or columns of G0T , the density of G0T is preserved.
At the end of triangulation process, G0T can be partitioned in
four submatrices as


A D
B C
and as depicted in Figure 2a. In the upper left part we have
the (k − α) × (k − α) lower triangular matrix A. The matrix
under submatrix A is denoted by B and it has dimension
(m − k + α) × (k − α). The upper right part is given by the
(k − α) × α submatrix D, while the lower right submatrix is
denoted by C and it has dimension (m − k + α) × α. The α
rightmost columns of G0T (corresponding to matrices C and
D) are usually referred to as inactive columns. Note that the
manipulation of G0T is typically performed through inactivation
or pivoting algorithms (see e.g. [24], [38]), which aim at
reducing the number of inactive columns. In the rest of this
work, we will assume that the use of the random inactivation
algorithm [38], as it will be detailed later in the section.
Step 2 (Zero matrix procedure). Matrix A is put in a
diagonal form and matrix B is zeroed out by means of row
sums. As a result, on average the density of the matrices C
and D increases (Figure 2b).
Step 3 (Gaussian elimination). Gaussian elimination (GE)
is applied to solve the system of equations associated with C.
Being C in general dense, the complexity of this step is cubic
in the number of inactive columns α. As observed in [24],
this step drives, for large equation systems, the complexity of
inactivation decoding. After performing GE, matrix G0T has
the structure shown in Figure 2c.
Step 4 (Back substitution). If Step 3 succeeds, after determining the value of the inactive variables (i.e., of the
input symbols associated with the inactive columns), backsubstitution is applied to compute the values of the remaining
variables in v. This is equivalent to setting to zero all elements
of matrix D in Figure 2c. At the end G0T shows a diagonal
structure as shown in Figure 2d, and all input symbols are
recovered.

Recalling that a unique solution to the system of equations
exists if and only if G0 is full rank, we have that decoding
succeeds if and only if the rank of C at Step 3 equals the
number of inactive variables.
Given that the number of inactive variables is determined
by the triangulation step, and that the GE on C dominates the
decoding complexity for large k, a first analysis of inactivation
decoding can be addressed by focusing on the triangulation
procedure.
A. Bipartite Graph Representation of Inactivation Decoding
We introduce next a bipartite graph representation of the
LT code from the receiver perspective. The graph comprises
m + k nodes, divided in two sets. The first set consists of k
input symbol nodes, one per input symbol, while the second
set consists of m output symbol nodes, one per received output
symbol. We denote the set of input symbol nodes as V , and the
input symbol nodes in V as v1, v2, . . . , vk . Similarly, we denote
the set of output symbol nodes as Y with output symbol nodes
denoted by y1, y2, . . . , ym . Here, we purposely referred to input
and output symbol nodes with the same notation used for
their respective input and output symbols to emphasize the
correspondence between the two sets of nodes and the sets
of input and received output symbols. For simplicity, in the
following we will refer to input (output) symbol nodes and
to input (output) symbols interchangeably. An input symbol
node vi is connected by an edge to an output symbol node
y j if and only if the corresponding input symbol contributes
to the generation of the corresponding output symbol, i.e., if
and only if the (i, j) element of G0 is equal to 1. We denote
by deg(v) (or deg(y)) the degree of a node v (or y), i.e., the
number of its adjacent edges.
Triangulation can be modelled as an iterative pruning of the
bipartite graph of the LT code. At each iteration, a reduced
graph is obtained, which corresponds to a sub-graph of the
original LT code graph. The sub-graph involves only a subset
of the original input symbols, and their neighboring output
symbols. The input symbols in the reduced graph will be
referred to as active input symbols. We shall use the term
reduced degree of a node to refer to the degree of a node in
the reduced graph. Obviously, the reduced degree of a node is
less than or equal to its original degree. We denote by red(v)

4

(or red(y)) the reduced degree of a node v (or y). Let us
now introduce some additional definitions that will be used to
model the triangulation step.
Definition 1 (Ripple). We define the ripple as the set of output
symbols of reduced degree 1 and we denote it by R.
The cardinality of the ripple is denoted by r and the corresponding random variable as R.
Definition 2 (Cloud). We define the cloud as the set of output
symbols of reduced degree d ≥ 2 and we denote it by C .
The cardinality of the cloud is denoted by c and the corresponding random variable as C.
Initially, all input symbols are marked as active, i.e., the
reduced sub-graph coincides with the original graph. At every
step of the process, one active input symbol is marked as either
resolvable or inactive and leaves the graph. After k steps no
active symbols are present and triangulation ends. In order
to keep track of the steps of the triangulation procedure, the
temporal dimension will be added through the subscript u.
This subscript u corresponds to the number of active input
symbols in the graph. Given the fact that the number of active
input symbols decreases by 1 at each step, triangulation will
start with u = k active input symbols and it will end after
k steps with u = 0. Therefore, the subscript decreases as the
triangulation procedure progresses. Triangulation with random
inactivations works as follows. Consider the transition from u
to u − 1 active input symbols. Then,
• If the ripple Ru is not empty (ru > 0), the decoder selects
an output symbol y ∈ Ru uniformly at random. The only
neighbor of y is marked as resolvable and leaves the
reduced graph, while all edges attached to it are removed.
• If the ripple Ru is empty (ru = 0), one of the active
input symbols v is chosen uniformly at random2 and it is
marked as inactive, leaving the reduced graph. All edges
attached to v are removed.
The input symbols marked as inactive are recovered using
Gaussian elimination (step 3). After recovering the inactive
input symbols, the remaining input symbols, those marked
as resolvable, can be recovered by iterative decoding (back
substitution in step 4).
Example 1. We provide an example for an LT code with k = 4
input symbols and m = 4 output symbols (Figure 3).
i. Transition from u = 4 to u = 3. Initially, there are
two output symbols in the ripple (r4 = 2) (Figure 3a).
Thus, one of the input symbols in the ripple is randomly
selected and marked as resolvable. In this case symbol
v1 is selected and all its adjacent edges are removed.
The graph obtained after the transition is shown in
Figure 3b. Observe that the nodes y1 and y4 have left
the graph since their reduced degree is now zero.
ii. Transition from u = 3 to u = 2. As shown in Figure 3b
the ripple is now empty (r3 = 0). Thus, an inactivation
2 This is certainly neither the only possible inactivation strategy nor the one
leading to the least number or inactivations. However, this strategy makes the
analysis tractable. For an overview of the different inactivation strategies we
refer the reader to [38].

SUBMITTED TO IEEE TRANSACTIONS ON COMMUNICATIONS

has to take place. Node v2 is chosen (according to
a random selection) and is marked as inactive. All
edges attached to v2 are removed from the graph. As
a consequence, the nodes y2 and y3 that were in the
cloud C3 enter the ripple R2 (i.e., their reduced degree
is now 1), as shown in Figure 3c.
iii. Transition from u = 2 to u = 1. Now the ripple is
not empty (r2 = 2). The input symbol v3 is selected
(again, according to a random choice) from the ripple
and is marked as resolvable. All its adjacent edges are
removed. The nodes y2 and y3 leave the graph because
their reduced degree becomes zero (see Figure 3d).
iv. Transition from u = 1 to u = 0. The ripple is now empty
(Figure 3d). Hence, an inactivation takes place: node v4
is marked as inactive and the triangulation procedure
ends.
Note that in this example input symbol v4 has no neighbors,
i.e., the matrix G0 is not full rank and decoding fails.
IV. A NALYSIS UNDER R ANDOM I NACTIVATION
In this section we analyze the triangulation procedure with
the objective of determining the average number of inactivations, i.e., the expected number of inactive input symbols at
the end of the triangulation process. We will then extend the
analysis to obtain the probability distribution of the number
of inactivations.
A. Average Number of Inactivations
Following [9], [14], [16], we model the decoder as a finite
state machine with state at time u given by the cloud and the
ripple sizes at time u, i.e.
Su := (Cu, Ru ).

We aim at deriving a recursion for the decoder state, that is,
to obtain Pr{Su−1 = (cu−1, ru−1 )} as a function of Pr{Su =
(cu, ru )}. We do so by analyzing how the ripple and cloud
change in the transition from u to u − 1. In the transition
exactly one active input symbol is marked as either resolvable
or inactive and all its adjacent edges are removed. Whenever
edges are removed from the graph, the reduced degree of
one or more output symbols decreases. Consequently, some
of symbols in the cloud may enter the ripple and some of the
symbols in the ripple may become of reduced degree zero and
leave the graph.
We focus first on the symbols that leave the cloud and
enter the ripple during the transition at step u, conditioned on
Su = (cu, ru ). Since for an LT code the neighbors of the output
symbols are selected independently and uniformly at random,
in the transition each output symbol may leave the cloud and
enter the ripple independently from the other output symbols.
Hence, the number of symbols leaving Cu and entering Ru−1
is binomially distributed with parameters cu and Pu with
Pu : = Pr{Y ∈ Ru−1 |Y ∈ Cu }

=

Pr{Y ∈ Ru−1 , Y ∈ Cu }
Pr{Y ∈ Cu }

(2)

FRANCISCO LÁZARO ET AL.: INACTIVATION DECODING OF LT AND RAPTOR CODES: ANALYSIS AND CODE DESIGN

active symbols

active symbols
v1

v2

v3

v4

y1

y2

y3

y4

ripple, R4

5

r

v2

v3

y2

y3

ripple, R3 = ∅

cloud, C4

(a) u = 4.

active symbols
v4

i

v3

y2

y3

r

cloud, C3

v4

cloud, C2 = ∅

ripple, R2

(b) u = 3.

(c) u = 2.

active symbols
r

ripple, R1 = ∅

i

v4

r

cloud, C1 = ∅

(d) u = 1.

r

r

i

ripple, R0 = ∅

i

cloud, C0 = ∅

(e) u = 0.

Fig. 3. Triangulation procedure example

where random variable Y represents a randomly chosen output
symbol.
We first consider the numerator of (2). Conditioning on the
original degree of Y , we have the following proposition.
Proposition 1. The probability that an output symbol Y
belongs to the cloud at step u and enters the ripple at step
u − 1, condition to its original degree being d, is

Pr{Y ∈ Ru−1 , Y ∈ Cu |deg(Y ) = d} =

   −1



 (u − 1) k − u k

if 2 ≤ d ≤ k − u+2,
(3)
d−2 d


0
otherwise.

Proof: For an output symbol Y of degree d to belong to
the cloud at step u and to the ripple at step u − 1 we need that
the output symbol has reduced degree 2 before the transition
and reduced degree 1 after the transition. For this to happen
two events must take place:
• Y ∈ Ru−1 one of the d edges of output symbol Y is
connected to the symbol being marked as inactive or
resolvable at the transition,
• Y ∈ Cu another edge is connected to one of the u − 1
active symbols after the transition and at the same time
the remaining d −2 edges connected to the k −u not active
input symbols (inactive or resolvable).
The joint probability of Y ∈ Ru−1 and Y ∈ Cu can be
derived as
Pr{Y ∈ Ru−1, Y ∈ Cu } = Pr{Y ∈ Ru−1 } Pr{Y ∈ Cu |Y ∈ Ru−1 }

Let us focus first on Y ∈ Ru−1 . We consider an output symbols
of degree d, thus this is simply probability that one the d edges

of Y is connected to the symbol being marked as inactive or
resolvable at the transition, Pr{Y ∈ Ru−1 } = d/k.
Let us now focus on Pr{Y ∈ Cu |Y ∈ Ru−1 }. Since we
condition on Y ∈ Ru−1 we have that one of the d edges of
Y is already assigned to one input symbol. We now need to
consider the remaining d − 1 edges and k − 1 input symbols.
The probability that one of the d − 1 edges is connected to
the set of u − 1 active symbols is (d − 1)(u − 1)/(k − 1). At
the same time we must have exactly d − 2 edges going to the
k − u input symbols that were not active before the transition.
Hence, we have


 −1
u−1 k −u k −2
Pr{Y ∈ Cu |Y ∈ Ru−1 } = (d − 1)
k −1 d−2 d−2
By multiplying the two probabilities, applying few manipulations, and making explicit the conditioning on deg(Y ) = d, we
get
Pr{Y ∈ Ru−1 , Y ∈ Cu |deg(Y ) = d} = (u − 1)



   −1
k −u k
.
d−2 d

We shall anyhow observe that if deg(Y ) < 2, the output symbol
cannot belong to the cloud. Moreover, one needs to impose
the condition d − 2 ≤ k − u, since output symbols choose
their neighbors without replacement (an output symbol cannot
have more than one edge going to an input symbol). Hence,
for d < 2 and d > k − u + 2, the probability Pr{Y ∈ Ru−1 , Y ∈
Cu |deg(Y ) = d} is zero.
By removing the conditioning on the degree of Y in (3), we

6

SUBMITTED TO IEEE TRANSACTIONS ON COMMUNICATIONS

Proposition 3. The probability Pu that a randomly chosen
output symbol leaves the cloud Cu enters the ripple Ru−1
after the transition from u to u − 1 active input symbols is

have
k−u+2

Õ

Pr{Y ∈ Ru−1 , Y ∈ Cu } = (u − 1)

d=2

Ωd



   −1
k −u k
.
d−2 d

Let us now focus on the denominator of (2) which gives the
probability that a randomly chosen output symbol Y is in the
cloud when u input symbols are still active. This probability
is provided by the following proposition.
Proposition 2. The probability that the randomly chosen
output symbol Y is in the cloud when u input symbols are
still active is
k−u+1

Pr{Y ∈ Cu } = 1 − u

Õ

Ωd

d=1
k−u

−

Õ
d=1



Ωd



   −1
k −u k
+
d−1 d

   −1
k −u k
.
d
d

(4)

Proof: The probability of Y not being in the cloud is given
by the probability of Y having reduced degree 0 or being in the
ripple. Given that the two events are mutually exclusive, we
can compute such probability as the sum of the probabilities
of the two events,
Pr{Y ∈ Cu } = 1 − Pr{Y ∈ Ru ∪ redu (Y ) = 0}

= 1 − Pr{Y ∈ Ru } − Pr{redu (Y ) = 0}

(5)

where redu (Y ) denotes the reduced degree of output symbol
Y when u input symbols are still active. We first focus on
the probability of Y being in the ripple. Let us assume Y has
original degree d. The probability that Y has reduced degree 1
equals the probability of Y having exactly one neighbor among
the u active input symbols and the remaining d − 1 neighbors
among the k −u non-active (i.e., solved or inactive) ones. Thus,
we have

   −1
k−u 
k −u k
u d−1
. (6)
Pr{Y ∈ Ru |deg(Y ) = d} = d k−1  = u
k
d−1 d
d−1

The probability of Y having reduced degree 0 is the probability
that all d neighbors of Y are in the k − u non-active symbols.
The total number of different edge assignments is dk , and the
total number of edge assignments in which all d neighbors of
Y are in the k − u non-active symbols is k−u
d . Thus we have
Pr{redu (Y ) = 0|deg(Y ) = d} =



   −1
k −u k
.
d
d

(7)

By removing the conditioning on d in (6) and (7) and by
replacing the corresponding results in (5) we obtain (4).
The expression of Pu is finally given in the following
proposition.

(u − 1)

Pu =

1−u

k−u+1
Õ

Ωd

k−u+2
Õ

Ωd

k−u  k  −1
d−2 d

d=2

k−u  k  −1
d−1

d

d=1

−

k−u
Õ

.
Ωd

k−u  k  −1
d

d

d=1

Proof: The proof follows directly from (2) and Propositions 1 and 2.
Let us now focus on the number au of symbols leaving the
ripple during the transition from u to u − 1 active symbols. We
denote by Au the random variable associated with au . Two
cases shall be considered. In a first case, no inactivation takes
place because the ripple is not empty. Thus, an output symbol
Y is chosen at random from the ripple and its only neighbor
v is marked as resolvable and removed from the graph. By
removing v from the graph, other output symbols that are
connected to v and that are in the ripple leave the ripple. Thus,
for ru > 0 we have
Pr{Au = au |Ru = ru } =
 r −a

   a −1 
1 u u
ru − 1 1 u
1−
u
au − 1 u

(8)

with 1 ≤ au ≤ ru . In the second case, the ripple is empty
(ru = 0) and an inactivation takes place. Since no output
symbols can leave the ripple, we have
(
1 if au = 0
Pr{Au = au |Ru = 0} =
(9)
0 if au > 0.
We are now in the position to derive the transition probability
Pr{Su−1 = (cu−1, ru−1 )| Su = (cu, ru )}. Let us introduce the
cloud drift bu to denote the variation of number of cloud
elements in the transition from u to u − 1 active symbols,
i.e.,
bu := cu − cu−1 .
We can now express the cloud and ripple cardinality after the
transition respectively as
cu−1 = cu − bu

ru−1 = ru − au + bu .
Since output symbols are generated independently, the random variable associated to bu is binomially distributed with
parameters cu and Pu , and making use of (8), we obtain the
following recursion
Pr{Su−1 = (cu − bu, ru − au + bu )| Su = (cu, ru )}
 
cu b u
=
P (1 − Pu )cu −bu
bu u
 r −a

   a −1 
1 u u
ru − 1 1 u
1−
(10)
×
u
au − 1 u

FRANCISCO LÁZARO ET AL.: INACTIVATION DECODING OF LT AND RAPTOR CODES: ANALYSIS AND CODE DESIGN

45

which is valid for ru > 0, while for ru = 0, according to (9),
we have

35

(11)

Note that the probability of Su−1 = (cu−1, ru−1 ) can be computed recursively via (10), (11) by initializing the decoder state
as
 
m rk
Pr{Sk = (ck , rk )} =
Ω (1 − Ω1 )ck
rk 1
for all non-negative ck , rk such that ck + rk = m, where m is
the number of output symbols.
The following proposition establishes how the number of
inactivations can be determined using the finite state machine.
Theorem 1. Let T denote the random variable associated to
the number of inactivations at the end of the triangulation
process. The expected value of T is given by
E [T] =

k Õ
Õ
u=1 cu

Pr{Su = (cu, 0)}.

(12)

Proof: Let us denote by f = (f1, f2, · · · , fk ) the binary
vector associated to the inactivations performed during the
triangulation process, and let F = (F1, F2, · · · , Fk ) denote the
associated random vector. In particular, the u-th element of f,
fu is set to 1 if an inactivation is performed when u input
symbols are active, and it is set to 0 if no inactivation is
performed. Thus, for a given instance of inactivation decoding,
the total number of inactivations corresponds simply to the
Hamming weight of f, which we denote as w H (f). The
expected number of inactivations can be obtained as
Õ
E [T] =
w H (f) Pr {F = f}
f

!
=

Õ Õ
f

u

fu Pr {F = f} =

ÕÕ
u

f

fu Pr {F = f}

where the summation is taken over all possible vectors f.
We shall now define f\u = (f1, · · · , fu−1, fu+1, fk ), i.e., f\u
denotes a vector containing all but the u-th element of f. We
have
ÕÕÕ
E [T] =
fu Pr {F = f}
u f\u fu

=

ÕÕ
u

=
=

Õ
u

fu

Õ
f\u

fu

ÕÕ
u

fu

Pr {F = f}

fu Pr {Fu = fu }

Pr {Fu = 1} .

If we now observe that by definition
Õ
Pr {Fu = 1} =
Pr{Su = (cu, 0)}
cu

we obtain (12), and the proof is complete.

Equation (12)
Monte Carlo simulation

40

Average number of inactivations

Pr{Su−1 = (cu − bu, bu )| Su = (cu, 0)}
 
cu
=
Pu bu (1 − Pu )cu −bu .
bu

7

30
25
20
15
10
5
0
0.00

0.03

0.06

0.09

0.12

0.15


0.18

0.21

0.24

0.27

0.30

Fig. 4. Average number of inactivations vs. relative overhead  for an LT
code with k = 1000 and with degree distribution Ω(1) (x).

Figure 4 shows the expected number of inactivations for a
k = 1000 LT code with the output degree distribution
Ω(1) (x) : = 0.0098x + 0.4590x2 + 0.2110x3 + 0.1134x4 +
+ 0.1113x10 + 0.0799x11 + 0.0156x40

(13)

which is the one adopted by standardized Raptor codes [17],
[39]. The figure shows the number of inactivations according
to (12) and results obtained through Monte Carlo simulations.
In particular, in order to obtain the simulation results for each
value of relative overhead 1000 decoding attempts were carried
out. A tight match between the analysis and the simulation
results can be observed.
The results in this section are strongly based on [16],
where LT codes under inactivation decoding were analyzed.
The difference is that, when considering the triangulation step
of inactivation decoding, the decoding process does not stop
when the decoder is at state Su = (cu, 0). Instead, decoding
can be resumed after performing an inactivation.
B. Distribution of the Number of Inactivations
The analysis presented in Section IV-A provides the expected number of inactivations at the end of the triangulation
process under random inactivation decoding. In this section we
extend the analysis to obtain the probability distribution of the
number of inactivations. To do so, we extend the finite state
machine by including the number of inactive input symbols in
the state definition, i.e.,
Su = (Cu, Ru, Tu )

where Tu is the random variable associated to the number of inactivations at step u (when u input symbols are active). We proceed by deriving a recursion
to obtain Pr{Su−1 = (cu−1, ru−1, tu−1 )} as a function of
Pr{Su = (cu, ru, tu )}. Two cases shall be considered. When
the ripple is not empty (ru > 0) no inactivation takes place,

8

SUBMITTED TO IEEE TRANSACTIONS ON COMMUNICATIONS

at the transition from u to u − 1 active symbols the number of
inactivations is unchanged (tu−1 = tu ). Hence, we have

If the ripple is empty (ru = 0) an inactivation takes place. In
this case the number of inactivations increases by one yielding
Pr{Su−1 = (cu − bu, bu, tu + 1)| Su = (cu, 0, tu )}
 
cu
=
Pu bu (1 − Pu )cu −bu .
bu

6

5

4

3

2

1

(15)

The probability of Su−1 = (cu−1, ru−1, tu−1 ) can be computed
recursively via (14), (15) starting with the initial condition
 
m r
Pr{Sk = (ck , rk , tu )} =
Ω (1 − Ω1 )ck
r 1
for all non-negative ck , rk such that ck + rk = m and tk = 0.
Finally, the distribution of the number of inactivations needed
to complete the decoding process is given by3
ÕÕ
fT (t) =
Pr{S0 = (c0, r0, t)}.
(16)
c0

·10−2
Equation (16)
Monte Carlo simulation

Distribution of inactivations

Pr{Su−1
 =(cu − bu, ru − au + bu, tu )| Su = (cu, ru, tu )}
cu
=
Pu bu (1 − Pu )cu −bu
bu
 r −a

   a −1 
1 u u
ru − 1 1 u
1−
×
.
(14)
u
au − 1 u

7

r0

In Figure 5 the distribution of the number of inactivations is
shown, for an LT code with degree distribution Ω(1) (x) given in
(13), input block size k = 300 and relative overhead  = 0.02.
The chart shows the distribution of the number of inactivations
obtained through Monte Carlo simulations and by evaluating
(16). In order to obtain the simulation results for each value
of absolute overhead 10000 decoding attempts were carried
out. As before, we can observe a very tight match between
the analysis and the simulation results.

V. I NACTIVATION D ECODING OF R APTOR C ODES
The analysis introduced in Section IV holds for LT codes.
We shall see next how the proposed tools can be successfully
applied to the design of Raptor codes whose outer code
has a dense parity check matrix (see [30]). We proceed by
illustrating the impact of the LT component of a Raptor code
on the inactivation count. We then develop a methodology for
the design of Raptor codes based on the results of Section IV.
3 From (16) we may obtain the cumulative distribution F (t). The cumulaT
tive distribution of the number of inactivations has practical implications. Let
us assume the fountain decoder runs on a platform with limited computational
capability. For example, the decoder may be able to handle a maximum number of inactive symbols (recall that the complexity of inactivation decoding
is cubic in the number of inactivations, t). Suppose the maximum number of
inactivations that the decoder can handle is tmax . The probability of decoding
failure will be lower bounded by 1 − FT (tmax ).The probability of decoding
failure is actually higher than 1 − FT (tmax ) since the system of equations to
be solved in the Gaussian elimination (GE) step might be rank deficient.

0

0

5

10

15

20

25

30
t

35

40

45

50

55

60

Fig. 5. Distribution of the number of inactivations for an LT code with
k = 300, relative overhead  = 0.02 and degree distribution Ω(1) (x) given in
(13).

A. Average Number of Inactivations for Raptor Codes
Let us now consider a Raptor code based on the concatenation of a (dense) (h, k) outer code and an inner LT code.
We denote by HP the ((h − k) × h) parity-check matrix of
the outer code. At the input of the Raptor encoder, we have
a vector of k input symbols, u = (u1, u2, . . . , uk ). Out of
the input symbols, the outer encoder generates a vector of h
intermediate symbols v = (v1, v2, . . . , vh ). The intermediate
symbols serve as input to an LT encoder which produces the
codeword c = (c1, c2, . . . , cn ), where n can grow unbounded.
The relation between intermediate and output symbols can be
expressed as c = v G where G is the generator matrix of the LT
code. The output symbols are sent over a BEC, at the output of
which the receiver collects m = k + δ output symbols, denoted
as y = (y1, y2, . . . , ym ). The relation between the collected
output symbols and the intermediate symbols can be expressed
as
G0T v T = y T .
where G0 is a matrix that contains the m columns of G
associated to the m received output symbols. Due to the outer
code constraints, we have
HP v T = 0T
where 0 is the length-(h − k) zero vector. Let us now define
the constraint matrix M of the Raptor code


M := HPT |G0 .
ML decoding can be carried out by solving the system

T
M T v T = 0| y .
(17)
If we compare the system of equations that need to be solved
for LT and Raptor decoding, given respectively by (1) and (17),
we can observed how Raptor ML decoding is very similar to

FRANCISCO LÁZARO ET AL.: INACTIVATION DECODING OF LT AND RAPTOR CODES: ANALYSIS AND CODE DESIGN

Ω(2) (x) := 0.05x + 0.2x2 + 0.4x3 + 0.3x4 + 0.05x40 .
The Figure also shows the number of inactivations needed
to decode the two standalone LT codes. If we compare the
number of inactivations required by the Raptor and LT codes,
we can see how for both degree distributions, the number
of additional inactivations needed for Raptor decoding with
respect to LT decoding is very similar. We hence conjecture
that the impact of the (dense) outer code on the inactivation
count depends mostly on the number of the outer code paritycheck equations. This empirical observation provides a hint
on a practical design strategy for Raptor codes: If one aims
at minimizing the number of inactivations for a Raptor code
based on a given outer code, it is sufficient to design the
LT code component for a low (i.e., minimal) number of
inactivations. Based on this consideration, an explicit design
example is provided in the following subsection.
B. Example of Raptor Code Design
We consider a Raptor code with a (63, 57) outer Hamming
code and we assume decoding is carried out when the absolute
receiver overhead reaches δ = δ∗ , i.e., we carry out decoding
after collecting δ∗ output symbols in excess of k. Furthermore,
we want to have a probability of decoding failure, PF , lower
that a given value PF?. Thus, the objective of our code design
will be minimizing the number of inactivations needed for
decoding while achieving a probability of decoding failure
lower than PF?. Hence, the design problem consists of finding
a suitable output degree distribution for the inner LT code.
For illustration we will introduce a series of constraints in
the output degree distribution. In particular we constraint
the output degree distribution to have the same maximum
and average output degree as standard R10 Raptor codes
(Ω̄ ≈ 4.63 and dmax = 40, [17]). Furthermore, we constraint
the output degree distribution to have the same support as the
degree distribution of R10 raptor codes, that is, only degrees
1, 2, 3, 4, 10, 11 and 40 are allowed. These design constraints
allow us to perform a fair comparison between the Raptor
4 In practice, the outer codes used are not totally dense, but the rows of
their parity check matrix are usually denser that the rows of GT . This is, for
example, usually the case if the outer code is a high rate LDPC code, since
the check node degree increases with the rate.

20
Raptor code, Ω(1) (x)
LT code, Ω(1) (x)
Raptor code, Ω(2) (x)
LT code, Ω(2) (x)

18
16
Average number of inactivations

ML decoding of an LT code. The main difference lies in the
fact that matrix M is formed, for the first h − k columns,
by the transpose of the outer code parity-check matrix. The
high density of the outer code parity-check matrix lowers the
probability that the ripple contains (some of) the h − k output
symbols associated to the zero vector in (17) (this is especially
evident at the early steps of the triangulation process). As a
result, we shall expect the average number of inactivations to
increase with h − k, for a fixed overhead 4 .
In Figure 6 we provide the average number of inactivations
needed to decode two Raptor codes, as a function of the
receiver overhead δ. Both Raptor codes have the same outer
code, a (63, 57) Hamming code, but different LT degree
distributions. The first distribution is Ω(1) (x) from (13), and
the second distribution is

9

14
12
10
8
6
4
2
0

0

2

4

6

8

10

12

14

16

18

20

22

24

δ

Fig. 6. Expected number of inactivations two Raptor codes using a (63, 57)
Hamming code with LT degree distributions Ω(1) (x) and Ω(2) (x), and for two
LT codes with k = 63 and degree distributions Ω(1) (x) and Ω(2) (x).

code obtained through optimization and a Raptor code with
the same outer code and the degree distribution from R10
Raptor codes.
The design of the LT output degree distribution is formulated as a numerical optimization problem. For the numerical
optimization we used is simulated annealing (SA) [40]. More
concretely, we define the objective function to be minimized
to be the following function [41]

η = E[T] + φ P̄F
where E[T] is the number of inactivations needed to decode
the LT code and the penalty function φ is defined as
(

0
if P̄F < PF?

φ P̄F =
?
b 1 − PF /P̄F otherwise
being b a large positive constant5 , PF? the target probability
of decoding failure at δ = δ∗ and P̄F the upper bound to the
probability of decoding failure of the Raptor code in [33],
which for binary Raptor codes has the expression6
PF ≤ P̄F :=

h
Õ

Alo πlk+δ

l=1

where Alo is the multiplicity of codewords of weight l in the
outer code, and πl depends on the LT code output degree
5 In our example, b was set to 104 . A large b factor ensures that degree
distributions which do not comply with the target probability of decoding
failure are discarded.
6 The use of the upper bound on the probability of decoding failure, P̄
F
in place of the actual value of PF in the objective functions stems from the
need of having a fast (though, approximate) performance estimation to be used
within the SA recursion. The evaluation of the actual PF presents a prohibitive
complexity since it has to be obtained through Monte Carlo simulations. Note
also that the upper bound of [33] is very tight.

10

SUBMITTED TO IEEE TRANSACTIONS ON COMMUNICATIONS

100

distribution as

In particular, two code designs were carried out using the
proposed optimization. In the first case we set the overhead
to δ∗ = 15 and the target probability of decoding failure to
PF? = 10−3 , and we denote by Ω(3) the distribution obtained
from the optimization process. In the second case we chose
the same overhead, δ∗ = 15, and set the target probability
of decoding failure to PF? = 10−2 , and we denote by Ω(4) the
resulting distribution. The degree distributions obtained are the
following

10−1

10−2

10−3

10−4

Ω(3) (x) = 0.0347 x1 + 0.3338 x2 + 0.2268 x3 + 0.1548 x4

10−5

+ 0.1515 x10 + 0.0973 x11 + 0.0011 x40

+ 0.0797 x10 + 0.0762 x11 + 0.0248 x40 .

Monte Carlo simulations were carried out in order to assess
the performance of the two Raptor codes obtained as result
of the optimization process. In order to have a benchmark for
comparison, a third Raptor code was considered, employing
the same outer code (Hamming) and the degree distribution of
standard R10 Raptor codes given in (13). Note that in all three
cases we consider the same outer code, a (63, 57) Hamming
code, and thus, the number of input symbols is k = 57. To
derive the probability of decoding failure for each overhead
value δ simulations were run until 200 errors were collected,
whereas in order to obtain the average number of inactivations,
1000 transmissions were simulated for each overhead value δ.
Figure 7 shows the probability of decoding failure PF as
a function of δ for the three Raptor codes based on the
(63, 57) outer Hamming code and inner LT codes with degree
distributions Ω(1) (x), Ω(3) (x) and Ω(4) (x). The upper bound to
the probability of failure P̄F is also provided. It can be observed
how the Raptor codes with degree distributions Ω(3) (x) and
Ω(4) (x) meet the design goal, being their probability of decoding failure at δ = 15 below 10−3 and 10−2 , respectively. It
can also be observed that the probability of decoding failure of
the Raptor code with degree distribution Ω(1) (x) lies between
that of Ω(3) (x) and Ω(4) (x).
Figure 8 shows the average number of inactivations as
a function of the absolute receiver overhead for the three
Raptor codes considered. It can observed that the Raptor code
requiring the least number of inactivations is Ω(4) , followed
by Ω(1) , and finally the Raptor code with degree distribution
Ω(3) is the one requiring the most inactivations, and thus has
the highest decoding complexity.
The results in Figures 7 and 8 illustrate the tradeoff existing
between probability of decoding failure and number of inactivations (decoding complexity): In general if one desires to
improve the probability of decoding failure, it is necessary to
adopt LT codes with degree distributions that lead to a larger
average number of inactivations.

0

5

10

15

20

25

δ

Fig. 7. Probability of decoding failure PF vs. absolute receiver overhead δ
for binary Raptor codes with a (63, 57) Hamming outer code and LT degree
distributions Ω(1) (x), Ω(3) (x) and Ω(4) (x). The markers represent the result of
simulations, while the lines represent the upper bound to the probability of
decoding failure in [33].

22
Ω(1) (x)
Ω(3) (x)
Ω(4) (x)

20
18
Average number of inactivations

Ω(4) (x) = 0.0823 x1 + 0.4141 x2 + 0.1957 x3 + 0.1272 x4

(simulation)
(upper bound)
(simulation)
(upper bound)
(simulation)
(upper bound)

PF

πl =

Ω(1) (x)
Ω(1) (x)
Ω(3) (x)
Ω(3) (x)
Ω(4) (x)
Ω(4) (x)

min(l,
Õj)

j  h−j 
i l−i
Ωj
.
h
j=1
i=max(0,l+j−h)
l
i even

d
max
Õ

16
14
12
10
8
6
4
2
0

0

5

10

15

20

25

δ

Fig. 8. Number of inactivations vs. absolute receiver overhead δ for binary
Raptor codes with a (63, 57) Hamming outer code and LT degree distributions
Ω(1) (x), Ω(3) (x) and Ω(4) (x).

VI. C ONCLUSIONS
In this paper the decoding complexity of LT and Raptor
codes under inactivation decoding has been analyzed. Using
a dynamic programming approach, recursions for the number
of inactivations have been derived for LT codes as a function
of their degree distribution. The analysis has been extended to
obtain the probability distribution of the number of inactivations. Furthermore, the experimental observation is made that
decoding a Raptor code with a dense outer code results in an
increase of the number of inactivations, compared to decoding
a standalone LT code. Based on this observation, it has been

FRANCISCO LÁZARO ET AL.: INACTIVATION DECODING OF LT AND RAPTOR CODES: ANALYSIS AND CODE DESIGN

shown how the recursive analysis of LT codes can be used
to design Raptor codes with a fine control on the number of
inactivations vs. decoding failure probability trade-off.
A PPENDIX A
I NDEPENDENT P OISSON A PPROXIMATION
In Section IV we have derived recursive methods that can
compute the expected number of inactivations and the distribution of the number of inactivations required by inactivation
decoding. The proposed recursive methods, albeit accurate,
entail a non negligible computational complexity. In this
appendix we propose an approximate recursive method that
can provide a reasonably-accurate estimation of the number
of inactivations with a much lower computational burden.
The development of the approximate analysis relies on the
following definition.
Definition 3 (Reduced degree-d set). The reduced degree-d
set is the set of output symbols of reduced degree d. We denote
it by Zd .
The cardinality of Zd is denoted by zd and its associated
random variable by Zd . Obviously, Z1 corresponds to the
ripple. Furthermore, it is easy to see how the cloud C
corresponds to the union of the sets of output symbols of
reduced degree higher than 1, i.e.,
C =

dØ
max

Zd .

d=2

Moreover, since the sets Zd are disjoint, we have
C=

d
max
Õ

Zd .

d=2

We aim at approximating the evolution of the number of
reduced degree d output symbols, Zd , as the triangulation
procedure of inactivation decoding progresses. As it was done
in Section IV, in the following a temporal dimension shall
be added through subscript u (recall that the subscript u
corresponds to the number of active input symbols in the
graph). At the beginning of the triangulation process we have
u = k, and the counter u decreases by one in each step of
triangulation. Triangulation ends when u = 0. It follows that
Zd,u is the set of reduced degree d output symbols when u
input symbols are still active. Moreover, Zd,u and zd,u are
respectively the random variable associated to the number
of reduced degree d output symbols when u input symbols
are still active and its realization. We model the triangulation
process by means of a finite state machine with state

Su := Z1,u, Z2,u, . . . , Zdmax,u .
This model is equivalent to the one presented in Section IV-A. However, the evaluation of the state evolution is
now more complex due to the large state space. Yet, the analysis can be, greatly simplified by resorting to an approximation.
Before decoding starts (for u = k), due to the independence
of output symbols we have that Sk follows a multinomial
distribution, which for large number of output symbols m

11

can be approximated as the product of independent Poisson
distributions. Figure 9 shows the probability distribution of
Z1,u , Z2,u and Z3,u for an LT code with a robust soliton
distribution and k = 1000 obtained through Monte Carlo
simulation, for u = 1000, 500 and 20. The figure also shows
the curves of the Poisson distributions which match best the
experimental data in terms of minimum mean square error.
As we can observe, the Poisson distribution tightly matches
the experimental data not only for u = k, but also for smaller
values of u. Hence, we shall approximate the distribution of
the decoder state at step u as a product of independent Poisson
distributions,
Pr{Su = z u } ≈

dmax
Ö
λ
d=1

d,u

z d, u −λ d, u
e

zd,u !

(18)


where zu is the vector defined as zu = z1,u, z2,u, . . . zdmax,u, ,
i.e., we assume that the distribution of reduced degree d
output symbols when u input symbols are active follows a
Poisson distribution with parameter λd,u . We remark that by
introducing this assumption, the number of received output
symbols m is no longer constant but becomes a sum of Poisson
random variables. In spite of this mismatch, we will later see
how a good estimate of the number of inactivations can be
obtained resorting to this approximation.
Next, we shall explain how the parameters λd,u can be
determined. For this purpose let us define Bd,u as the random
variable associated with the number of output symbols of
reduced degree d that become of reduced degree d − 1 in
the transition from u to u − 1 output symbols. We have
Zd,u−1 = Zd,u + Bd+1,u − Bd,u .
If we take the expectation at both sides we can write








E Zd,u−1 = E Zd,u + E Bd+1,u − E Bd,u .
(19)


Let us now derive the expression of E Bd,u . We shall
distinguish two cases. First we shall consider output symbols
with reduced degree d ≥ 2. Since output symbols select
their neighbors uniformly at random, we have that Bd,u ,
d ≥ 2, conditioned on Zd,u = zd,u is binomially distributed
with parameters zd,u and Pd,u , where Pd,u is the probability
that the degree of Y decreases to d − 1 in the transition from
u to u − 1, i.e.,
Pd,u := Pr{Y ∈ Zd−1,u−1 |Y ∈ Zd,u }.

The following proposition holds.
Proposition 4. The probability that a randomly chosen output
symbol Y , with reduced degree d ≥ 2 when u input symbols
are active, has reduced degree d − 1 when u − 1 input symbols
are active is
d
Pd,u = .
u
Proof: Before the transition, Y has exactly d neighbors
among the u active input symbols. In the transition from u to
u −1 active symbols, 1 input symbol is selected at random and
marked as either resolvable or inactive. The probability that

12

SUBMITTED TO IEEE TRANSACTIONS ON COMMUNICATIONS

·10−2

Z1
Z2
Z3
Poisson approx.

20

10

0

0

50

100

150

200

250

300

350

400

450

(a) u = k = 1000

·10−2
probability

20

Hence, we have


m


1 Õ
1
Pr{Z1,u ≥ 1} +
E B1,u = 1 −
z1,u Pr{Z1,u = z1,u }
u
u z =1

10

0

1, u

0

40

80

120

160

200

240

(b) u = 500

·10−2



 1 
1
= 1−
1 − Pr{Z1,u = 0} + E Z1,u
u
u


 1
1 
1 − e−λ1, u + λ1,u .
= 1−
u
u


20

10

0

and removed from the graph. Furthermore, any other output
symbol in the ripple being connected to input symbol v also
leaves the ripple during the transition. Hence, for z1,u ≥ 1 we
have



1
z1,u − 1
E B1,u |Z1,u = z1,u ≥ 1 = 1 +
u
1 1
= 1 − + z1,u
u u
whereas for z1,u = 0 we have


E B1,u |Z1,u = 0 = 0.

0

50

100

150

200

250

300

350

400

450

(c) u = 20
number of output symbols

Fig. 9. Distribution of Z1, u , Z2, u and Z3, u for an LT code with robust
soliton distribution and k = 1000 obtained through Monte Carlo simulation.
The upper, middle and lower figures represent respectively the distribution
for u = 1000, 500 and 20. The black bars represent Z1, u , the light grey bars
Z2, u and the dark grey bars Z3, u . The red lines represent the best Poisson
distribution fit in terms of minimum mean square error.

the degree of Y gets reduced is simply the probability that one
of its d neighbors is marked as resolvable or inactive.
Thus, the expected value of Bd,u is


 
 d 

E Bd,u = E E Bd,u |Zd,u = E Zd,u .
(20)
u
If we now replace (20) in (19) a recursive expression is
obtained for λd,u , d ≥ 2,

d
d+1
λd,u−1 = λd,u +
λd+1,u − λd,u
(21)
u
 u

d
d+1
λd,u−1 = 1 −
λd,u +
λd+1,u
u
u


where we have replaced E Zd,u = λd,u according to our
Poisson distribution assumption.
We shall now consider the output symbols of reduced degree
1. In particular, we are interested in B1,u , the random variable
associated to the output symbols of reduced degree d = 1
that become of reduced degree 0 in the transition from u to
u − 1 active input symbols. Two different cases need to be
considered. In the first one, the ripple is not empty, and hence
there are one or more output symbols of reduced degree 1.
In this case, an output symbol Y is chosen at random from
the ripple and its only neighbor v is marked as resolvable

(22)

Replacing (22) in (19) a recursive expression is obtained as,





1
2
1 
λ1,u−1 = 1 −
λ1,u + λ2,u − 1 −
1 − e−λ1, u . (23)
u
u
u
The decoder state probability is obtained by setting the initial condition λd,k = m Ωd and applying the recursions in (21)
and (23). Furthermore, the expected number of inactivations
after the k steps of triangulation, can be approximated as
E [T] =

k
Õ
u=1

Pr{Z1,u = 0} ≈

k
Õ

e−λ1, u .

u=1

In Figure 10 we provide again the probability distribution
of Z1,u , Z2,u and Z3,u for an LT code with robust soliton
distribution (RSD) (see [5]) and k = 1000 obtained through
Monte Carlo simulation, for u = 1000, 500 and 20. The
figure also shows the curves of the approximation to Zi,u
obtained using the model in this section. We can observe
how the proposed method is able to track the distribution
of Zi,u very accurately for u = k and u = 500. However,
at the end of the triangulation process a divergence appears
as it can be observed for u = 20 in Figure 10 (c). The
source of this divergence could, in large part, be attributed
to the independence assumption made in (18). As the number
of active input symbols u decreases, the dependence among
the different Zi,u becomes stronger, and the independence
assumption approximation falls apart.
Figure 11 shows the average number of inactivations needed
to complete decoding for a linear random fountain code
(LRFC)7 and a RSD, both with average output degree Ω̄ = 12
and k = 1000. The figure shows results obtained by Monte
Carlo simulation and also the estimation of the number of
inactivations obtained under our Poisson approximation. A
tight match between simulation results and the estimation can
be observed. The experimental results indicate that, although
7 The degree distribution of a LRFC follows a binomial distribution with
parameters k and p = 1/2 (see [42]).

FRANCISCO LÁZARO ET AL.: INACTIVATION DECODING OF LT AND RAPTOR CODES: ANALYSIS AND CODE DESIGN

13

600

·10−2

Z1
Z2
Z3
Poisson approx.

20

500

10

0

0

50

100

150

200

250

300

350

400

450

(a) u = k = 1000

·10−2
probability

20

100

0

40

80

120

160

200

240

0
0.00

(b) u = 500

·10−2
20

0.05

0.10

0.15


0.20

0.25

0.30

Fig. 11. Average number of inactivations needed to decode a linear random
fountain code and a RSD for k = 1000 and average output degree Ω̄ = 12.
The markers represent simulation results and the lines represent the predicted
number of inactivations using the proposed Poisson approximation.

10

0

LRFC Poisson approx.
LRFC simulation
RSD Poisson approx.
RSD simulation

300

200

10

0

E [N]

400

0

50

100

150

200

250

300

350

400

450

(c) u = 20
number of output symbols

Fig. 10. Distribution of Z1, u , Z2, u and Z3, u for an LT code with robust
soliton distribution and k = 1000 obtained through Monte Carlo simulation.
The upper, middle and lower figures represent respectively the distribution for
u = 1000, 500 and 20. The black bars represent Z1, u , the light grey bars Z2, u
and the dark grey bars Z3, u . The red lines represent the Poisson distribution
approximation to Z d, u obtained employing the model in this section.

the independence assumption made does not hold in general,
it is a good approximation for most of the decoding process,
deviating from simulation results only at the last stages of
decoding. Thus, the proposed method can still provide a
good approximation of the number of inactivations needed for
decoding.
R EFERENCES
[1] F. Lázaro, G. Liva, and G. Bauch, “Inactivation decoding analysis for
LT codes,” in Proc. 52nd Annu. Allerton Conf. on Commun., Control,
and Computing, Monticello, Illinois, USA, Oct. 2015.
[2] F. Lázaro Blasco, G. Liva, and G. Bauch, “LT code design for inactivation decoding,” in Proc. 2014 IEEE Inf. Theory Workshop, Hobart,
Tasmania, Australia, Nov. 2014, pp. 441–445.
[3] J. Metzner, “An improved broadcast retransmission protocol,” IEEE
Trans. Commun., vol. 32, no. 6, pp. 679–683, Jun 1984.
[4] J. Byers, M. Luby, and M. Mitzenmacher, “A digital fountain approach
to reliable distribution of bulk data,” IEEE J. Select. Areas Commun.,
vol. 20, no. 8, pp. 1528–1540, Oct. 2002.
[5] M. Luby, “LT codes,” in Proc. 43rd Annual IEEE Symp. on Foundations
of Computer Science, Vancouver, Canada, Nov. 2002, pp. 271–282.
[6] P. Maymounkov, “Online codes,” Technical report, New York University,
Tech. Rep., 2002.
[7] A. Shokrollahi, “Raptor codes,” in Proc. of the 2004 IEEE Int. Symp.
on Inf. Theory, Chicago, Illinois, US, Jun. 2004, p. 36.
[8] M. Shokrollahi, “Raptor codes,” IEEE Trans. Inf. Theory, vol. 52, no. 6,
pp. 2551–2567, Jun. 2006.

[9] R. Karp, M. Luby, and A. Shokrollahi, “Finite length analysis of LT
codes,” in Proc. 2004 IEEE International Symp. on Inf. Theory, Chicago,
Illinois, US, Jun. 2004.
[10] E. Maneva and A. Shokrollahi, “New model for rigorous analysis of LTcodes,” in Proc. 2006 IEEE International Symp. on Inf. Theory, Seattle,
Washington, US, Jul. 2006, pp. 2677–2679.
[11] S. Puducheri, J. Kliewer, and T. E. Fuja, “The design and performance
of distributed LT codes,” IEEE Trans. Inf. Theory, vol. 53, no. 10, pp.
3740–3754, Oct 2007.
[12] E. Hyytia, T. Tirronen, and J. Virtamo, “Optimal degree distribution for
LT codes with small message length,” in IEEE Infocom, Anchorage,
USA, May 2007, pp. 2576–2580.
[13] D. Vukobratovic, C. Stefanovic, V. Crnojevic, F. Chiti, and R. Fantacci,
“Rateless packet approach for data gathering in wireless sensor networks,” IEEE J. Select. Areas Commun., vol. 28, no. 7, pp. 1169–1179,
Sep. 2010.
[14] G. Maatouk and A. Shokrollahi, “Analysis of the second moment of the
LT decoder,” IEEE Trans. Inf. Theory, vol. 58, no. 5, pp. 2558–2569,
May 2012.
[15] M. Shirvanimoghaddam, Y. Li, S. Tian, and B. Vucetic, “Distributed raptor coding for erasure channels: Partially and fully coded cooperation,”
IEEE Trans. Commun., vol. 61, no. 9, pp. 3576–3589, Sep. 2013.
[16] A. Shokrollahi, “Theory and applications of Raptor codes,” Mathknow,
vol. 3, pp. 59–89, 2009.
[17] “Technical Specification Group Services and System Aspects; Multimedia Broadcast/Multicast Service; Protocols and Codecs,” Jun. 2012,
3GPP TS 26.346 V11.1.0.
[18] M. Shokrollahi, S. Lassen, and R. Karp, “Systems and processes for
decoding chain reaction codes through inactivation,” Feb. 2005, uS
Patent 6,856,263.
[19] A. Shokrollahi and M. Luby, Raptor Codes. Foundations and Trends
in Commun. and Inf. Theory, Now Publishers Inc., 2011.
[20] C. Lanczos, “Solution of systems of linear equations by minimized
iterations,” J. Res. Nat. Bureau of Standards, vol. 49, pp. 33–53, 1952.
[21] E. R. Berlekamp, Algerbraic Coding Theory. McGraw-Hill, 1968.
[22] B. A. LaMacchia and A. M. Odlyzko, “Solving large sparse linear
systems over finite fields,” Advances in Cryptology-CRYPT090, pp. 109–
133, 1991.
[23] T. J. Richardson and R. L. Urbanke, “Efficient encoding of low-density
parity-check codes,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 638–
656, Feb 2001.
[24] D. Burshtein and G. Miller, “An efficient maximum likelihood decoding
of LDPC codes over the binary erasure channel,” IEEE Trans. Inf.
Theory, vol. 50, no. 11, nov 2004.

14

[25] E. Paolini, G. Liva, B. Matuz, and M. Chiani, “Maximum likelihood
erasure decoding of LDPC codes: Pivoting algorithms and code design,”
IEEE Trans. Commun., vol. 60, no. 11, pp. 3209–3220, Nov. 2012.
[26] B. Schotsch, H. Schepker, and P. Vary, “The performance of short
random linear fountain codes under maximum likelihood decoding,” in
Proc. 2011 IEEE International Conf. on Commun., Kyoto, Japan, Jun.
2011.
[27] B. Schotsch, R. Lupoaie, and P. Vary, “The Performance of Low-Density
Random Linear Fountain Codes over Higher Order Galois Fields under
Maximum Likelihood Decoding,” in Proc. 48th Annu. Allerton Conf. on
Commun., Control, and Computing, Monticello, Illinois, US, Oct. 2011.
[28] B. Schotsch, G. Garrammone, and P. Vary, “Analysis of LT codes over
finite fields under optimal erasure decoding,” IEEE Commun. Lett.,
vol. 17, no. 9, pp. 1826–1829, Sep. 2013.
[29] B. E. Schotsch, “Rateless coding in the finite length regime,” Ph.D.
dissertation, Inst. of Commun. Systems and Data Proc., RWTH Aachen,
Aachen, Germany, Jul. 2014.
[30] F. Lázaro, E. Paolini, G. Liva, and G. Bauch, “Distance spectrum of
fixed-rate Raptor codes with linear random precoders,” IEEE J. Select.
Areas Commun., vol. 34, no. 2, pp. 422–436, Feb 2016.
[31] C. Di, D. Proietti, I. Telatar, T. Richardson, and R. Urbanke, “Finitelength analysis of low-density parity-check codes on the binary erasure
channel,” Information Theory, IEEE Transactions on, vol. 48, no. 6, pp.
1570 –1579, jun 2002.
[32] G. Liva, E. Paolini, and M. Chiani, “Bounds on the error probability
of block codes over the q-ary erasure channel,” IEEE Trans. Commun.,
vol. 61, no. 6, pp. 2156–2165, Jun. 2013.
[33] F. Lázaro, G. Liva, E. Paolini, and G. Bauch, “Bounds on the error
probability of Raptor codes,” in Proc. IEEE Globecomm, Washington
DC, USA, Dec. 2016.
[34] C. Measson, A. Montanari, and R. Urbanke, “Maxwell construction: The
hidden bridge between iterative and maximum a posteriori decoding,”
IEEE Trans. Inf. Theory, vol. 54, no. 12, pp. 5277–5307, Dec. 2008.
[35] A. Ashikhmin, G. Kramer, and S. ten Brink, “Extrinsic information
transfer functions: Model and erasure channel properties,” IEEE Trans.
Inf. Theory, vol. 50, no. 11, pp. 2657–2673, Nov. 2004.
[36] K. Mahdaviani, M. Ardakani, and C. Tellambura, “On Raptor code
design for inactivation decoding,” IEEE Trans. Commun., vol. 60, no. 9,
pp. 2377–2381, Sep. 2012.
[37] T.-C. Ng and S. Yang, “Finite-length analysis of BATS codes,” in
Proc. of 2013 IEEE International Symp. on Network Coding, (NetCod),
Calgary, Alberta, Canada, Jun. 2013.
[38] E. Paolini, G. Liva, B. Matuz, and M. Chiani, “Maximum likelihood
erasure decoding of LDPC codes: Pivoting algorithms and code design,”
IEEE Trans. Commun., vol. 60, no. 11, pp. 3209–3220, Nov. 2012.
[39] M. Luby, A. Shokrollahi, M. Watson, and T. Stockhammer, “RFC 5053:
Raptor forward error correction scheme: Scheme for object delivery,”
IETF, Tech. Rep., Oct. 2007.
[40] S. Kirkpatrick, D. Gelatt, and M. Vecchi, “Optimization by simmulated
annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
[41] F. Lázaro Blasco, G. Liva, and G. Bauch, “Enhancing the LT component
of Raptor codes,” in Proc. of the 10th International ITG Conf. on
Systems, Commun. and Coding, SCC 2015, Hamburg, Germany, Feb.
2015.
[42] G. Liva, E. Paolini, and M. Chiani, “Performance versus overhead for
fountain codes over F q ,” IEEE Comm. Letters., vol. 14, no. 2, pp. 178–
180, 2010.

SUBMITTED TO IEEE TRANSACTIONS ON COMMUNICATIONS

