TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.7, July 201
4, pp
. 5469 ~ 54
7
5
DOI: 10.115
9
1
/telkomni
ka.
v
12i7.403
8
5469
Re
cei
v
ed
Jul
y
28, 201
3; Revi
sed
Jan
u
a
r
y 27, 2
014;
Acce
pted Fe
brua
ry 16, 20
14
Rateless Codes Design Scheme Based on Two Stages
Yunji Li
1
*, Xiaolong
Yang
2
, Keping Long
2
1
School of Co
mmunicati
on &
Information En
gin
eeri
ng,
Un
iv
. of Electronic Sci. &
T
e
ch. of
Chin
a
Qingsh
u
ih
e Ca
mpus, No. 200
6, Xi
yu
an Av
e, W
e
st Hi-T
e
ch
Z
one, 611
73
1, Che
ngd
u, Sich
uan, P. R.Chin
a
2
School of Co
mputer & Com
m
unic
a
tion En
gin
eer
i
ng, Un
iv
. of Sci. &
T
e
ch
. of Beijing
No. 30
Xue
y
u
a
n
Roa
d
, Hai
d
ia
n District, Beiji
ng, 100
08
3, P.
R.Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:
y
u
njil
i_
uestc
@soh
u.com
A
b
st
r
a
ct
Current r
a
teles
s
codes c
o
d
i
ng
sche
m
es
ig
no
red t
he
ord
e
r r
e
covery
of pac
kets. T
o
cope
w
i
th thi
s
prob
le
m,
aver
a
ge
d
e
lay an
d max
i
mu
m me
mory
c
ons
um
p
t
ion w
e
re pr
op
osed
as perfor
m
a
n
ce i
n
d
i
ces
to
character
i
z
e
th
e ord
e
r recov
e
ry perfor
m
anc
e,
then a c
odi
ng sch
e
m
e b
a
s
ed o
n
tw
o stages c
odi
ng w
a
s
prop
osed
to
i
m
pr
ove
the
or
der r
e
covery
p
e
rformanc
e.
En
co
di
n
g
o
f
the fro
n
t
k co
de
d
sym
bo
l
s
i
s
the fi
rst
stage, w
h
ich t
he i
th
co
ded sy
mb
ol is
co
mp
o
s
e of the i
th
p
a
cket and
other
d
i
-1 packets w
h
ich
are
c
h
o
s
e
n
from the fro
n
t i-1 packets w
i
th equ
al pr
ob
a
b
ility. Enco
di
n
g
of the re
ma
i
n
in
g infi
nite co
ded sy
mb
ols is
the
secon
d
stag
e
w
h
ich the p
a
ck
ets are ch
ose
n
from a
ll
packe
ts equa
l pr
oba
bly. T
he si
mul
a
tion r
e
sults s
how
that the r
a
tele
ss codes
fro
m
the pr
op
osed
sche
m
e
hav
e
better or
der r
e
covery p
e
rfor
mance,
meanw
h
ile
have h
i
g
h
ban
dw
idth efficien
cy and go
od u
n
ifor
mity recov
e
ry than LT
co
des.
Ke
y
w
ords
: rateless co
des, or
der recov
e
ry, tw
o stages
codi
ng, LT codes, systematic
LT codes
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
In wirel
e
ss n
e
tworks, auto
m
atic retran
smissi
on requ
est
(A
RQ) was comm
only
adopte
d
to combat chann
el fadin
g
, and enha
nce
comm
un
ication reliabi
lity. However, communi
ca
tion
system
s with a large number
of feedbacks will
ca
use “feedback storm”.
Hybrid A
R
Q was
develop
ed
wi
th assi
stan
ce
of forwa
r
d e
rro
r
co
rre
ctio
n (FE
C
) cod
e
to
significa
ntly redu
ce
the
freque
nt feed
backs. More
often than no
t, efficient FEC co
de ne
ed
s to match
wi
th the cha
n
n
e
l.
Ho
wever, it is difficult to know the a
c
cu
rate
pri
o
ri
kn
owle
dge of chann
el in wi
reless net
works.
What'
s
m
o
re,
it is i
n
tra
c
tabl
e in
netwo
rk
multic
as
t e
v
en
th
o
u
g
h
th
e
s
o
ur
ce
k
n
ows th
e
c
o
nd
itio
n o
f
all chan
nel
s if they are not identical be
ca
u
s
e the so
urce ca
nnot
cha
nge the coding
sch
em
e
according to
the con
d
ition
s
of one o
r
some (n
ot
all) chan
nel
s. To over
come t
he drawba
ck of
FEC
code, ratele
ss co
d
e
s were
p
r
o
posed,
wh
ich ca
n rema
rka
b
ly prom
ote tran
smi
s
sion
efficien
cy without any prio
ri chan
nel kno
w
led
ge.
Ratele
ss
co
des over lo
ssy chan
nels do
not
req
u
ire
any p
r
i
o
ri
kno
w
le
dg
e of the
cha
nnel
s. Th
erefo
r
e, ratel
e
ss co
de
s are very su
itabl
e can
d
idate
s
for lossy mu
lticast chan
n
e
ls,
nonu
niform chann
els, and
time-varying
cha
nnel
s. Th
e
first reali
z
at
ion of ratele
ss co
de
s is Lu
by
Tran
sfo
r
m (L
T) code
s [1]. LT code
s ca
n be p
r
e
c
od
e
d
with a
blo
c
k code to yiel
d Ra
ptor
cod
e
s
[2]. LDPC-LT
(Lo
w
De
nsit
y Parity Ch
eck)
and
RS
-LT
(Reed
-Solo
m
on) ar
e two
com
m
on
Ra
ptor
cod
e
s.
The
r
ef
ore, the
pe
rfroman
c
e
of L
T
code
s
has
i
m
porta
nt effe
ct on
Raptor
cod
e
s.
LT
co
des
with robust soliton dist
ribu
tion (RS
D
)
have good capacity-
achi
evability [1]. The bigger
k
is,
the
better capacit
y
-achi
e
vabilit
y perform
ance LT co
des have. But LT codes
have several drawbacks
becau
se the
purp
o
se of L
T
co
des is o
n
l
y to impr
ove
the tran
smi
s
sion efficie
n
cy.
First d
r
a
w
ba
ck
is the p
o
o
r
in
termedi
ate p
e
rform
a
n
c
e
whi
c
h me
an
s that it only recove
rs few
packet
s
whe
n
the
receiver
can
n
o
t receive suf
f
icient co
ded
symbol
s.
The
poor inte
rme
d
iate perfo
rm
ance will affe
ct
the real
-time
appli
c
ation, e
s
pe
cially for
bigge
r
k
. The
second i
s
the longe
r average del
ay, which
is al
so di
sa
d
v
antageo
us t
o
re
al-time
a
pplication
s
. The third
is th
e se
riou
s
disorde
r
recovery,
whi
c
h the
i
th
packet is ofte
n be re
cove
red before the
(
i
-1)
th
pa
cket
. The diso
rde
r
re
covery is
not
con
d
u
c
ive to real-time ap
plicatio
ns. Be
side
s, so
m
e
times, the so
u
r
ce
can
not g
e
t the accu
ra
te
cha
nnel
kno
w
ledge, but it can get
the wo
rst condition
s from statistical estimation,
history data
or
other
resea
r
ch re
sults.
Co
nsid
eratio
n o
f
wors
t co
ndi
tions is
appli
ed to network multicast f
o
r
many nonu
niform chan
nel
s.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5469 – 54
75
5470
In this pape
r, we propo
se a
rateless cod
e
s
de
sign
sch
e
me to redu
ce the averag
e delay,
diso
rde
r
reco
very, and im
prove the u
n
i
f
ormity re
covery and tran
smissi
on effici
ency. Unifo
r
mity
recovery me
ans that the numbe
r
of re
covered pa
ckets from any
i
coded
symb
ols is cl
ose to
i
.
The
uniformit
y re
covery
ca
n be
explai
ne
d by the
follo
wing
exampl
e. If
k
balls will
be distri
but
ed
to
N
≥
k
boxe
s
whil
e e
n
sure
the
sum
nu
mber of b
a
lls of the
front
i
boxe
s
d
o
e
s
not exceed
i
an
d
the
N
th
box m
u
st h
a
s at le
a
s
t on
e b
a
ll. T
he u
n
iform
di
stributio
n of
b
a
ll is simil
a
r to the
uniformi
t
y
rec
o
v
e
ry
of ra
teles
s
co
de
s. T
he order
re
covery mean
s
that the
i
th
packet is re
cove
red befo
r
e the
(
i
+1
)
th
pa
cket. The prop
osed schem
e h
a
s two p
r
om
i
nent advanta
ges. The first is the better
perfo
rman
ce
of orde
r re
co
very. The se
cond is the hi
g
her tra
n
smi
ssion efficien
cy.
This pap
er is organi
zed
a
s
follo
ws. So
me related
works are d
e
scrib
ed i
n
se
ction 2.
Section 3 d
e
s
cribe
s
the
system model
. Maximu
m memory
con
s
umptio
n, averag
e delay
and
uniformity re
covery entrop
y
are defined
in sect
ion 4.
Section 5 propo
se
s a co
ding sche
me
to
achi
eve the
g
ood
perfo
rma
n
ce
of ab
ove
indices.
T
he simulatio
n
re
sults
are sho
w
n and analy
z
ed
in se
ction 6. Finally, we draw some con
c
lu
sion
s.
2. Related Work
The first dra
w
ba
ck of LT code
s was
studi
e
d
in [3], where the
authors got the outer
boun
d whi
c
h
the fractio
n
of packet
s
th
at can
be re
covered fo
r
any deg
ree
distrib
u
tion,
and
desi
gne
d a degree di
stri
bution to get
close to
this bou
nd. Th
e fractio
n
of packets
can
be
recovered a
s
a perfo
rman
ce ind
e
x ha
s limitation be
cau
s
e p
a
rt of
diso
rde
r
ly p
a
ckets m
a
y be
unu
sabl
e in many appli
c
ations. A scheme ha
s b
o
th good int
e
rme
d
iate p
e
rform
a
n
c
e
and
capacity-achi
e
vability with sma
ller num
ber of feedbacks
was stud
ied in [4]. Shifted LT (SLT)
cod
e
s mo
dified the robu
st soliton di
strib
u
tion of
LT co
des at the so
urce, based o
n
the numbe
r of
input symb
ols alrea
d
y de
co
ded at the
re
ceivers [5].
T
he u
s
e of fee
dba
cks i
s
con
t
radicto
r
y to the
essen
c
e
of rateless
cod
e
s
a
nd it i
s
i
n
feasi
b
le in
some
ap
plications su
ch
as
deep
-spa
ce
comm
uni
cati
on a
nd
netwo
rk multicast.
Ali Talari
et
a
l
optimized th
e ratel
e
ss
co
des with
ge
n
e
tic
algorith
m
un
der the
assu
mption
that the source
k
nows the
ch
annel e
r
a
s
u
r
e rate [6]. T
he
assumptio
n
may not appli
c
abl
e in man
y
scen
a
rio
s
a
nd the algo
rithm is very co
mplex. Ali Talari
et al
pro
p
o
s
e
d
an
effici
ent
pa
ckets sorti
ng al
go
rithm
for hi
gh i
n
termediate
re
co
very rate
of
LT
c
o
des
[6, 7], which is
only to improve the in
terme
d
iate pe
rform
ance
re
gardl
ess of the order
recovery. A family of syst
ematic
ratele
ss
co
de
s tha
t
are unive
rsally cap
a
city-approa
chin
g
on
BEC reg
a
rdl
e
ss of the
chann
el erasu
r
e rate
were
studie
d
in [
8
], which onl
y propo
se
d
an
approa
ch to d
e
sig
n
system
atic LT code
s.
Distri
buted L
T
code
s were prop
osed i
n
[9, 10
], which are to imp
r
ove the tran
smissio
n
efficien
cy of ratele
ss
cod
e
s by de
sig
n
a degr
ee
distrib
u
tion such that the
code
d sym
bols
received
by the de
stinatio
n follow the
RSD i
n
d
egree. The
e
s
se
nce
of di
strib
u
tion LT
cod
e
s i
s
multi-source
s fusion.
Une
q
ual erro
r p
r
ot
ection i
s
im
p
o
rtant in vid
e
o
and i
m
age
appli
c
ation
s
. An
codi
ng
sche
me ba
se
d on
expandi
ng
windo
w for
un
equal
erro
r
p
r
otectio
n
wa
s
pro
p
o
s
ed
i
n
[11,
12]
,
whi
c
h cl
a
ssif
i
e
d
k
in
put
packet
s
into
Q
different im
portant
cla
s
ses. The
sche
me gua
rant
e
e
s
the re
covery
of the most importa
nt packets
reg
a
rdl
e
ss of o
r
de
r a
nd uniformity recovery of the
same im
port
ant packet
s
. Cla
s
ses of o
p
timal ratele
ss co
de
s we
re
prop
ose
d
in
[13], which i
s
to
desi
gn
ratele
ss code
s
ba
sed o
n
the
tra
nditional
lin
e
a
r
blo
c
k sy
stematic code.
In this pap
er,
we
use th
e defin
ition of syste
m
atic ratele
ss code
s in
[2
, 8]. The syst
ematic
ratele
ss
co
de
s of [13]
are
the
sp
ecial case of
our sche
me.
The
ratel
e
ss
cod
e
s of [
13] have
go
od inte
rme
d
i
a
te
perfo
rman
ce,
order recovery a
nd
high
tran
smi
ssi
on
efficien
cy
when th
e e
r
a
s
ure
rate
is lo
w.
Ho
wever, the
performan
ce
advantage
o
f
above is
no
t obvious
wh
en the erasu
r
e rate i
s
hig
h
.
Beyond that, the majo
r di
sadva
n
tage
of [13] is
tha
t
the scheme
is not
suit to une
qual e
r
ro
r
prote
c
tion.
3. Sy
stem Model
We assu
me that
pa
rts of diso
rde
r
ly
p
a
c
ke
ts
are u
n
a
vailable
be
cause all
the
packet
s
must be
se
nt to next step
or p
r
ocesse
d
in orde
r.
In gene
ral, only
intact data
ca
n be u
s
ed. T
h
is
assumptio
n
is tenable in streaming m
edi
a, f
ile distribu
tion and som
e
other ap
plications.
If there a
r
e
k
packet
s
to b
e
tran
smitted,
the ide
a
l rateless
cod
e
s
are th
at the receive
r
s
can
recover
all packet
s
wi
th hi
gh probability from a slightly gr
eater num
ber
of coded symbols,
and the
k
p
a
ckets a
r
e reco
vered evenly
and orde
rly.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Ratele
ss Co
d
e
s Desi
gn Schem
e Based
on Two Stag
es (Yu
n
ji Li)
5471
We u
s
e
an e
x
ample to ex
plain the
pro
posed mo
del.
If there are {
x
1
,
x
2
, …,
x
10
}
packet
s
will be encoded into {
y
1
,
y
2
,
y
3
, …} infinite co
ded
sym
bols. As
sh
o
w
n in T
able 1
.
n
r
is the nu
mber
of re
ceive
d
coded
sym
bol
s.
p
r
i
s
the re
covered
pa
ckets. We ca
n see
that sche
me
A has
lo
wer
band
width eff
i
cien
cy than
schem
e
B, C a
nd D. Schem
e C h
a
s
poo
r
orde
r recovery perform
an
ce,
and it will consume
s
mo
re memo
ry to store t
he
diso
rde
r
ly pa
ckets. Sche
me D ha
s p
oor
uniformity recovery performance, whi
c
h will caus
es
more average delay. In summary, scheme B
has better perform
a
nce
of bandw
i
d
th utilization,
uniformity and
order
recovery
than ot
her
s
c
hemes
from intuition.
Table 1. Example for O
r
de
r, Uniformi
ty Re
covery an
d Bandwi
d
th Efficiency
n
r
2
3
4 5 6
7
8
9
10
11
12
13
14
15
A-
p
r
x
4
x
7
x
2
x
1
,
x
8
x
5
x
3
,
x
6
,
x
9
,
x
10
B-
p
r
x
1
x
2
x
3
x
4
x
5
,
x
6
x
7
x
8
x
9
x
10
C-
p
r
x
10
x
9
x
8
x
7
x
6
x
5
x
4
x
2
x
3
,
x
1
D-
p
r
x
9
,x
3
x
8
x
2
,
x
4
x
1
, ,
x
5
,
x
6
,
x
7
,
x
10
The detail
s
of RSD can
be found in [1]. The prob
ability of degree
-1 and d
e
g
ree
-
2
gene
rated
from RS
D i
s
very high i
n
a wid
e
rang
e
of
c
and
δ
, where
δ
i
s
allowable fail
ure
probability of the decoder to reco
ver t
he data from a given number
k
of
cod
ed symb
ols.
Con
s
tant
c
i
s
almo
st
set
a
s
0
<
c
<1. It is s
u
itable to
choos
e
c
and
δ
as
c
=0.
2
,
δ
=0.05
[14] in
the
followin
g
sim
u
lation
s studi
es.
4. Three Nov
e
l Performan
ce Indices
Based
on th
e pro
p
o
s
ed i
deal ratele
ss cod
e
s m
o
d
e
l, we p
r
op
o
s
e three p
e
rf
orma
nce
indices to e
s
timate the ratele
ss
cod
e
s of differe
nt coding
schem
es. Ma
ximum memory
con
s
um
ption
and ave
r
a
ge
delay cha
r
a
c
terize the
disorde
r
. Uniformity recovery
entro
py (URE)
cha
r
a
c
teri
ze
s the uniformit
y recove
ry p
e
rform
a
n
c
e.
The thre
e no
vel indice
s a
nd overhead
can
comp
re
hen
si
vely describe
the perfo
rma
n
ce of ratel
e
ss co
de
s. The overhe
ad of rateless code
s is
defined a
s
th
e numb
e
r of
output co
ded
symbol
s tha
t
the receiver need
s to col
l
ect in orde
r to
recover the in
put messag
e
s
with high p
r
obability, and
it is measure
d
as a multipl
e
of the number
k
of input sy
mbols [1].
4.1. Maximum Memor
y
Consumptio
n
It is difficult t
o
kno
w
whi
c
h an
d h
o
w
many pa
cket
s a
r
e
re
cove
red
wh
en th
e
re
ceive
r
receives
a co
ded sym
bol b
e
ca
use the rateless
code
s are ra
ndom
code
s. The
random
ne
ss
will
result in di
so
rder
re
cove
ry of packet
s
in
the
re
ceive
r
. The
n
u
mbe
r
of
diso
rd
erly packet
s
can be
u
s
ed
as
d
i
so
r
d
er
me
as
ur
e
m
en
t. T
h
e r
a
te
le
ss
c
o
d
e
s
co
mmunic
a
tio
n
is a
d
y
n
a
m
ic pr
oc
es
s
becau
se the
receiver
simu
ltaneou
sly re
ceive
s
an
d d
e
co
de
s the
coded
symbol
s. The
disord
erly
packet
s
will be stored
and
waiting unti
l
som
e
of
them are
order, whi
c
h
cause the
number of
diso
rde
r
ly pa
ckets i
s
cha
nging.
He
re,
we
onl
y co
nsid
er th
e m
e
mory
con
s
u
m
ption for the
recovered pa
ckets. Maxim
u
m memo
ry con
s
um
pt
ion is the a
c
cumulation of
the numbe
r of
diso
rde
r
ly p
a
c
kets
of de
co
ding
pro
c
e
s
s, whi
c
h
can
reflect the
di
sorde
r
deg
ree.
We
explai
n t
he
maximum
m
e
mory con
s
u
m
ption with scheme
A
in
Table
1. When the
re
ce
iver re
ceive
s
5
symbol
s, packet
x
4
is reco
vered an
d st
ored, an
d wai
t
ing for the packet
x
1
,
x
2
a
nd
x
3
. So
x
4
is a
diso
rde
r
ly pa
cket. The n
u
m
ber
of disorderly pa
ck
ets is 2
whe
n
th
e re
ceive
r
re
ceive
s
the ei
ghth
cod
ed symb
o
l
. When the receive
r
re
cei
v
es 13
th
sym
bol, packet
x
1
and
x
8
are
recovered. The
memory con
s
umption
i
s
5 becau
se
the new re
co
ve
re
d pa
ckets
wil
l
be sto
r
ed f
o
r sequ
en
cin
g
.
After the
se
quen
cin
g
, th
e pa
cket
x
1
and
x
2
will
be
se
nt to
next ste
p
,
and th
e me
mory
con
s
um
ption become
s
3.
The numb
e
r of
disord
erly
p
a
c
k
e
ts
is
4
w
h
en
th
e r
e
ce
ive
r
r
e
c
e
ives
th
e
14
th
symbol,
and then it b
e
com
e
s
8 wh
en the re
ceiv
er re
ceive
s
th
e 15
th
symbol
. Therefo
r
e, the
maximum m
e
mory
co
nsu
m
ption of
schem
e A
i
s
8. And
so
on, the
m
a
ximum me
mory
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5469 – 54
75
5472
con
s
um
ption
of scheme
B, C an
d D i
n
T
able 1
ar
e
2, 10, 10
respe
c
tively. There
f
ore, sch
e
me
B
has le
ss maximum memo
ry con
s
umptio
n
than others.
4.2. Av
erage Dela
y
Real
-time i
s
i
m
porta
nt in
many ap
plica
t
ions.
Delay i
s
a
go
od
pa
rameter to
ch
ara
c
teri
ze
the real
-time. We defin
e del
ay of the
i
th
p
a
cket as the f
o
llows:
i
dl
j
i
(1)
W
h
er
e
j
is
the recovery time of the
i
th
packet, whi
c
h
the re
ceive
r
can
not re
cov
e
r
th
e
i
th
packet until it receives the
j
th
coded
symb
ol. If
ij
, the
i
th
p
a
cket will wait for the recovery of all
former
i
-1 pa
ckets. Averag
e delay is defi
ned a
s
formul
a (2):
1
1
k
i
i
dl
dl
k
(2)
The average
delay of scheme
A, B,
C and D in
Table 1
are 6.8, 2.1, 4.1 and 5.2
respe
c
tively.
So, sch
eme
B has the lea
s
t averag
e de
lay among th
e four sche
m
e
s.
4.3. Uniformi
t
y
Reco
v
e
r
y
Entrop
y
Entropy i
s
a
physi
cs te
rminology
whi
c
h
used to
estimate
the
co
nfusi
on
d
egre
e
of
system. In informatio
n, entropy is u
s
ed t
o
estima
te th
e amount of informatio
n. In this pape
r, we
use
unifo
rmit
y recovery
en
tropy (URE) t
o
e
s
timate
th
e unifo
rmity o
f
the di
stributi
on of
re
cove
red
packet
s
. We assume that the receiver recove
rs
k
i
pa
ckets wh
en it receive
s
i
coded sym
bol
s,
and re
cove
rs
k
i+1
packets
whe
n
it recei
v
es
i
+1
cod
e
d
sy
mbol
s.
The
k
i+1
-
k
i
packets a
r
e the
new
recovered
when th
e recei
v
er receives
the (
i
+1
)
th
co
ded
symbol
s.
All
k
pa
ckets
a
r
e re
cove
red
whe
n
r
co
ded
symbols a
r
e
received. URE is defined a
s
follows:
1
11
0
0
lo
g
,
0
l
o
g
0
0
,
0
r
ii
ii
i
kk
k
k
URE
k
kk
(3)
From intuition
,
the schem
e B and C has
better uniformity recovery
in Table 1. The URE
of sche
me
s
A, B, C a
nd
D a
r
e
1.60
94
, 2.1640,
2.1
640 and
1.35
92 re
spe
c
tively.
The sche
me
B
and C h
a
ve b
e
tter uniformit
y recove
ry pe
rforma
nce than schem
e A and D. The
calcul
ation
s
an
d
intuition a
r
e
con
s
i
s
tent. T
herefo
r
e,
URE is a
su
ita
b
l
e index to
e
s
timate the
u
n
iformity of the
recovered pa
ckets.
Form a
bove,
we ca
n se
e
that sche
m
e
B
has the b
e
st pe
rform
a
nce a
m
ong t
he four
scheme
s
. Th
e co
mputatio
n re
sult
s of th
ree
novel pe
rforman
c
e i
ndi
ce
s a
r
e
simil
a
r to the i
n
tuition
judgem
ent. Our obje
c
tive is to design a
codi
ng
schem
e has the
cha
r
acte
rs as
scheme B.
5. Enoding Scheme
w
i
th
Maximum Channel Eras
ure Ra
te
The en
codi
n
g
is divided i
n
to two stag
es. T
he first stage i
s
the encodin
g
of the front
k
cod
ed symb
o
l
s. Enco
ding
of the remain
ing infinite
co
ded sym
bols
is the se
co
nd
stage. At first,
the source obtains degr
ee probability
di
stribution
u
(
i
)
from RS
D, ge
nerate
s
k
d
egr
e
e
s
ac
co
rd
ing
to
u
(
i
), an
d a
rra
nge
s them
from the sm
allest to
the l
a
rge
s
t o
r
de
r, then co
mput
es the ave
r
a
ge
degree
d
av
of the
k
degre
e
s. In the first st
age, the
source g
e
ts the
i
th
(1
≤
i
≤
k
) de
gree
d
i
and
c
h
ooses
d
i
-1 packet
s
fro
m
{
x
1
,
x
2
, …,
x
i-1
} eq
uiproba
bl
y, then en
co
d
e
s th
e
d
i
-1
p
a
ckets an
d the
i
th
pack
e
t into the
i
th
cod
ed symbol
with
XOR ope
ratio
n
.
In
the
seco
nd stage,
th
e sou
r
ce cho
o
ses
an inte
ger
d
j
(
k
<
j
) eq
uipro
bably fro
m
ceil[
d
av
(1-
p
m
)] to ceil[
p
m
d
av
+
k
/2(1-
p
m
)] a
s
t
he d
egree, th
en
cho
o
s
e
s
d
j
p
a
ckets e
quip
r
obably from
k
pa
ckets an
d encode
s th
em into the
j
th
coded
sym
bol
with XOR op
eration. The
sou
r
ce rep
e
a
t
s the se
con
d
stage until
all receivers receive sufficient
cod
ed sy
m
b
o
l
s t
o
re
cov
e
r
all pac
ket
s
.
H
e
re,
p
m
is th
e
maximum ch
annel e
r
a
s
u
r
e rate. Ceil[A] is
a mathem
atical functio
n
which
ro
und
s t
he ele
m
ent
s
of A to the n
eare
s
t inte
ge
r which g
r
eat
er
than or eq
ual
to A. The details of the co
ding sch
e
me
are sho
w
n a
s
Figure 1.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Ratele
ss Co
d
e
s Desi
gn Schem
e Based
on Two Stag
es (Yu
n
ji Li)
5473
The u
s
e of RSD is in orde
r to take adv
antage
of the
capa
city-a
ch
ievability of RSD. The
ratio of
small
degree
s of t
he front
k
co
ded
symbol
s
is hig
h
. We
a
rra
nge th
e small deg
re
es in
front
be
ca
use
the co
ded
symbol
s wh
ich have sm
all de
gre
e
a
r
e ea
sy to
b
e
de
co
ded.
The
recovered packets
will be
used in the
s
ubsequent decodi
ng. T
he packets of
the
i
th
coded
sym
bol
are from the firs
t to the
i
th
packet, which may improve the or
de
r re
cov
e
ry
. After step 3, the
receiver ha
s
received
n
≤
k
co
ded symb
ols and re
co
vered
n
r
≤
n
p
a
c
k
et
s.
I
f
it
c
hoo
se
s a
sm
all
degree
d
j
i
n
step 4 and
choo
se
s
d
j
pa
ckets, th
e p
r
obability that
d
j
cho
s
e
d
p
a
c
kets have
b
een
recoverd may be so high t
hat the code
d symbol co
mpro
se of th
e
d
j
packets i
s
red
und
an
cy. On
the co
ntra
ry, if
d
j
is very l
a
rge, it may i
n
crea
se the
decodin
g
difficulty for
1
sr
dn
. So we
cho
o
se the
degree
from
ceil[
d
av
(1-
p
m
)]
to
ceil[
p
m
d
av
+
k
/2(1-
p
m
)].
The l
o
wer
b
ound
an
d u
p
per
boun
d of the
degree in th
e
se
con
d
sta
g
e
are i
n
verse
l
y propo
rtiona
l to
p
m
. The d
egre
e
range i
s
from 0 to
d
av
whe
n
p
m
=1,
and from
d
av
to
k
/2 when
p
m
=0. Th
e av
erag
e u
ppe
r
boun
d for
ma
ny
times of
com
putation of d
egre
e
i
s
ab
o
u
t
k
/2 a
c
cordi
ng to
RSD. S
o
we
ch
ose
d
av
and
k
/2 as
the
base lower b
ound a
nd up
p
e
r bou
nd respectively, and
then adju
s
t the bou
nd a
c
cordin
g to
p
m
.
Figure 1. Encoding Algo
rith
m
6. Simulation
The ratele
ss
cod
e
s from t
he propo
se
d
scheme
are
systematic rat
e
less code
s with
very
high p
r
ob
abili
ty if it choo
ses
suitable
p
a
ram
e
ters in
RSD b
e
cau
s
e the probabi
lity of degree
-1
alway
s
is so high that it can gen
erate
many
deg
ree
-
1 even thou
gh the gen
eration pro
c
e
ss is
rand
om. Anot
her adva
n
tag
e
of the prop
ose
d
sc
hem
e
is that the propo
sed
sche
me ca
n re
cov
e
r
all
k
pa
ckets
orde
rly wh
en
the era
s
u
r
e rate is ze
ro.
Figure 2. Maximum Memo
ry Consumptio
n
Fi
gure 3. Unif
ormity Re
cov
e
ry Entropy
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
0.
93
0.
94
0.
95
0.
96
0.
97
0.
98
0.
99
1
E
r
as
ure ra
t
e
Ma
x
i
mu
m me
mo
ry
c
o
n
s
u
m
p
t
i
o
n
O
u
r
s
c
hem
e
M
E
R
=
0.
5
O
u
r
s
c
hem
e
M
E
R
=
0.
75
O
u
r
s
c
hem
e
M
E
R
=
0.
95
LT
c
o
d
e
s
S
c
hem
e o
f
[
13]
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
1
1.
5
2
2.
5
3
3.
5
4
K
=
500
E
r
as
ur
e r
a
t
e
U
n
ifo
r
m
i
ty
r
e
c
o
v
e
r
y
e
n
tr
o
p
y
O
u
r
s
c
hem
e M
E
R
=
0.
5
O
u
r
s
c
hem
e M
E
R
=
0.
75
O
u
r
s
c
hem
e M
E
R
=
0.
95
LT
c
odes
S
c
hem
e of
[
1
3
]
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5469 – 54
75
5474
We
sim
u
late
d the
maxim
u
m me
mory
con
s
um
ption,
overhea
d, a
v
erage
d
e
lay and
URE
unde
r
k
=50
0
and
p
m
=0.5
, 0.75, 0.95,
c
=0.
2
,
δ
=0.
05 [14]. In the simul
a
tio
n
, the deco
d
i
ng
algorith
m
is
Gau
ssi
an eli
m
ination
which can
de
c
ode
all packet
s
thoro
ughly mo
re than BP (b
elief
prop
agatio
n)
algorith
m
. The results of si
mulation
are illustrate
d in Figure 2
-
5. For convenie
n
ce
,
the maximum
memory co
n
s
umptio
n is n
o
rmali
z
e
d
.
From Figure 2, we can
se
e that the prop
o
s
ed
scheme i
s
su
perio
r in m
a
ximum mem
o
ry
con
s
um
ptio
n
than LT
cod
e
s, an
d is a
p
proximate to t
he
scheme
of [13]. The le
ss maximu
m
memory
co
n
s
umptio
n it
has, the
mo
re p
a
cket
s
are
recovered o
r
derly. The
a
d
vantage i
s
very pro
m
ine
n
t whe
n
the
era
s
u
r
e
rat
e
is l
o
w. T
h
e
maximum m
e
mory
con
s
u
m
ption of L
T
cod
e
s is
al
ways ve
ry m
u
ch i
n
a ve
ry wide
ran
g
e
of
era
s
u
r
e
rate.
The maxim
u
m memo
ry consumption
o
f
the pro
p
o
s
e
d
sche
me in
crea
se
s
with the
increa
se of e
r
asure rate. The advanta
ge of
maximum memo
ry con
s
um
ption
of the propo
sed
scheme
is d
ue to the
de
gree
arra
nge
ment
an
d p
a
c
kets
ch
oice
mechani
sm
in the
i
th
(1
≤
i
≤
k
)
cod
ed sym
b
o
l
. The small
degree
s are arrang
ed in
front, whi
c
h t
he co
ded
symbols
with small
degree
are v
e
ry ea
sy to b
e
de
cod
ed. T
he reco
vere
d
packet
s
will
contri
bute to
the su
bsequ
e
n
t
decodin
g
. The degree arrangem
ent m
e
ch
ani
sm will
be benefici
a
l
to the reduction of disord
er.
The pa
ckets
of the
i
th
coded symbol i
s
from the front
i
packets, which ma
ke th
e latter pa
ckets
appe
ar in
the
latter code
d
symbol
s. So, the pa
cket
s
choi
ce
me
ch
anism
al
so i
s
in favor
of the
redu
ction
of d
i
sorde
r
. Although the
sche
me of [
13] ha
s bette
r go
od
decodin
g
pe
rforman
c
e i
n
the
front
k
co
ded
symbol
s, the
pro
p
o
s
ed
scheme
and th
e
sche
me of
[13] has simil
a
r p
e
rfo
r
man
c
e
becau
se of the advantag
e of the pr
opo
sed schem
e a
nd ch
ann
el erasu
r
e.
The UREs fo
r LT cod
e
s, the pro
p
o
s
ed
schem
e a
nd the scheme
of [13] are shown in
Figure 3.
The
URE of
the
p
r
opo
se
d
sche
me i
s
d
e
sce
n
ded
with
the i
n
crea
se
of e
r
asu
r
e
rate
an
d
bigge
r tha
n
t
hat of LT
cod
e
s
and th
e
schem
e of
[1
3
]
unde
r different erasure
rates. Th
e bi
g
ger
URE i
s
, the
better pe
rfo
r
man
c
e of u
n
iformity
re
covery and in
termedi
ate p
e
rform
a
n
c
e t
h
e
scheme
ha
s. But the LT
cod
e
s
ha
s
poor
unifo
rmi
t
y recove
ry perfo
rman
ce
unde
r different
era
s
u
r
e rate
s. The improve
m
ent of uniformity re
covery
of our schem
e is due to the arrang
eme
n
t
of the front
k
degree
s for that the code
d
symbols
with
small deg
ree
are ea
sy to be decoded a
n
d
the previous recovered packets
will help to
the subsequent decoding.
So,
there are
more
recovered pa
ckets in any front
i
cod
ed symbols.
Figure 4. Average
Delay
Figure 5. Overhea
d
The ave
r
ag
e
delay is sho
w
n in Fi
gure 4.
T
he
pro
p
o
s
e
d
sch
e
me
ha
s le
ss ave
r
ag
e delay
than that of L
T
cod
e
s
and
the schem
e o
f
[13] under
d
i
fferent era
s
u
r
e rate
s. Th
e averag
e del
a
y
of LT code
s
is very long i
n
a wide ran
ge of
era
s
u
r
e rates. Th
e
advantage
of the propo
sed
s
c
h
e
m
e is ver
y
p
r
o
m
in
en
t
w
h
en
er
as
ur
e r
a
te is
lo
w
,
an
d
th
e a
v
e
r
ag
e
de
la
y is
inc
r
ea
se
d
w
i
th
th
e
increa
se of e
r
asure rate.
The
average
delay gain p
r
ofits from
th
e packet
s
sel
e
ction of the
i
th
(1
≤
i
≤
k
)
code
d symbol a
n
d
the deg
ree
arra
nge
ment
mech
ani
sm
of the front
k
code
d symb
ols,
whi
c
h is
simil
a
r to the red
u
c
tion of maximum memo
ry con
s
umptio
n
.
Figure 5
sho
w
s the
overh
ead
s of th
e
ratele
ss
co
de
s from the
th
ree
coding
schem
es.
The ove
r
he
a
d
of ou
r
sche
me is
de
crea
sed
with th
e i
n
crea
se
of
k
and i
s
lo
we
r
than that of
L
T
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
80
10
0
12
0
14
0
16
0
18
0
20
0
22
0
24
0
26
0
E
r
as
u
r
e r
a
t
e
De
l
a
y
O
u
r
s
c
h
em
e
M
E
R
=
0.
1
5
O
u
r
s
c
h
em
e
M
E
R
=
0.
2
5
O
u
r
s
c
h
em
e
M
E
R
=
0.
3
5
LT
c
ode
s
S
c
h
e
m
e
of
[
13]
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
1
1.
0
1
1.
0
2
1.
0
3
1.
0
4
1.
0
5
1.
0
6
1.
0
7
E
r
a
s
ur
e r
a
t
e
O
v
erhea
d
O
u
r
s
c
h
e
me
MER
=
0
.
5
O
u
r
s
c
he
m
e
M
E
R
=
0.
75
O
u
r
s
c
he
m
e
M
E
R
=
0.
95
LT
c
o
des
S
c
hem
e of
[
1
3]
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Ratele
ss Co
d
e
s Desi
gn Schem
e Based
on Two Stag
es (Yu
n
ji Li)
5475
cod
e
s, an
d is simila
r to that of [13] under di
ffe
rent
era
s
ure rate
s. The overh
ead gai
n of the
prop
osed
scheme a
nd th
e sche
me of
[13] is d
ue t
o
the line
a
rly
indep
end
en
ce of the
fro
n
t
k
cod
ed sym
b
o
l
s, whi
c
h me
ans that the f
r
ont
k
cod
ed
symbol
s hav
e no re
dun
da
ncy inform
ation.
But the LT co
des
can
not e
n
su
re the line
a
r inde
pen
de
nce of the fro
n
t
k
cod
ed sy
mbols.
From a
bove
discu
ssi
on, we can
see th
at the prop
osed sche
me h
a
s bette
r perf
o
rma
n
ce
of unifo
rmity recovery, m
e
mory
con
s
u
m
ption, av
e
r
ag
e del
ay an
d
overhe
ad th
a
n
LT
code
s i
n
a
wide
ran
ge of
era
s
u
r
e
rate
s. Beyond th
at, our
sc
he
me can g
ene
rate
systemat
ic code
with
high
probability. Our scheme al
so is
superior
to or similar t
o
the scheme of [13].
7. Conclusio
n
In this pape
r, we pro
p
o
s
e
a novel rate
l
e
ss co
de
s de
sign
scheme
based on two
stage
s
codi
ng and forward equal
probability. The enco
ding of the front
k
co
ded
sy
mbols i
s
the
first
stage whi
c
h
the
i
th
coded
symbol is co
m
pose of the
i
th
packet and
d
i
-1 pa
ckets which a
r
e cho
s
en
from the firs
t to the (
i
-1
)
th
p
a
cket with e
q
ual proba
bility. The se
con
d
stage
ch
oo
se
s a de
gre
e
d
j
rand
omly fro
m
ceil[
d
av
(1-
p
m
)] to ceil[
p
m
d
av
+
k
/2(1-
p
m
)]
and then ch
ooses
d
j
pa
ckets fro
m
the
k
packet
s
. The
sou
r
ce re
pe
ats the seco
nd st
ag
e unti
l
all receivers have de
cod
ed all
k
packets
.
The si
mulatio
n
re
sults
sh
o
w
that the p
r
opo
s
ed
codi
n
g
schem
e ha
s le
ss
avera
g
e
delay, mem
o
ry
con
s
um
ption,
overhe
ad an
d better unifo
rmity re
covery than LT co
des
without feedb
acks. Th
e
prop
osed scheme ha
s b
e
tter uniformi
t
y recovery
p
e
rform
a
n
c
e t
han the sch
e
m
e of [13]. The
perfo
rman
ce
of
overh
ead, averag
e
d
e
la
y
and
ma
xim
u
m
mem
o
ry con
s
um
ption of
the
p
r
opo
sed
scheme i
s
su
perio
r to o
r
si
milar to the
schem
e of
[13]
. Beside
s, all
packet
s
of th
e ratele
ss co
des
of the propo
sed schem
e are recovered o
r
de
rly whe
n
the era
s
u
r
e ra
te is ze
ro.
Ackn
o
w
l
e
dg
ements
This
wo
rk i
s
sup
porte
d by
Cha
ng
Jian
g Schol
ars P
r
og
ram of th
e MoE of Ch
ina, 973
Program
(No
.
2012
CB31
5905
), NSF
C
(No
s
.
6
1
2
0108
9, 610
7
1101,
6117
2
050, 6
1172
0
48,
6117
3149,
6
1100
184
), NCET Prog
ram
,
Sichu
an Y
o
uth Sci. &
Te
ch. F
oun
d
(No. 09Z
Q02
6
-032),
Funda
mental
Re
sea
r
ch Fu
nds for th
e Cent
ral Universities (No. ZY
GX2009
J0
05
).
Referen
ces
[1] M
Luby
.
LT
-co
des.
T
he 43rd Annu. IEEE S
y
mp. Foundati
o
ns of
Compute
r
Science. 20
0
2
: 271-2
80.
[2]
A Shokrol
l
ah
i. Raptor C
odes.
IEEE Transactions on Infor
m
a
t
ion Theory
. 2
0
06; 52(6): 2
551
-256
7.
[3
] Su
j
a
y
Sa
ng
havi
.
Intermed
i
at
e Perfor
mance
of R
a
teless
C
odes.
Inf
o
rmati
on th
eor
y
w
o
r
kshop
20
07
.
T
ahoe Cit
y
,
CA
. 2007: 47
8-48
2.
[4]
Saej
oon
Kim,
Seun
gh
yu
k
Lee. Improv
e
d
Inte
rmed
i
at
e Performa
nc
e of Rat
e
less
Cod
e
s. 11th
Internatio
na
l C
onfere
n
ce o
n
Advanc
ed C
o
mmunica
ti
on T
e
chn
o
lo
g
y
. Ph
oen
i
x
Park; 20
09; 3: 168
2-
168
6.
[5]
Andre
w
Ha
ge
d
o
rn, Agar
w
a
l S
,
Starobinsk
i
D
,
et al. Ratel
e
s
s
codi
ng
w
i
t
h
F
eedb
ack.
IEEE INFOCOM
Rio d
e
Jan
e
iro.
2009: 1
791-
17
99.
[6]
Ali T
a
lari, Beh
z
ad Sh
ahr
asbi
, Nazan
i
n R
a
h
navar
d.
Efficient Symbol Sorti
n
g
fo
r Hi
gh
In
te
rme
di
ate
Recov
e
ry Rate
of LT
Codes
. Informatio
n
T
heor
y
Proc
ee
din
g
2010. Austi
n
, T
X
. 2010: 244
3-24
47.
[7]
Ali T
a
lari, Naz
ani
n Rah
nav
ar
d. On the Interm
edi
ate S
y
m
b
ol Rec
o
ver
y
R
a
te of Ratel
e
ss
Codes.
IEEE
T
r
ansactio
n
s o
n
Co
mmu
n
icati
ons
. 201
2; 60(
5): 1237-
12
42.
[8]
Xi
ao
jun Y
uan,
Li Pin
g
. On S
y
stematic LT
Codes.
IEEE Comm
unications letters
. 2008; 1
2
(6): 681-
68
3.
[9]
Srinath P
uduc
heri, J Kli
e
w
e
r,
T
homas E F
u
ja.
T
he Design
and P
e
rforman
c
e of Distrib
ute
d
LT
Codes
.
IEEE Transactions on Infor
m
a
t
ion Theory.
2
0
07; 53(1
0
): 374
0-37
54.
[10]
Srinath P
uduc
heri, J
Kli
e
w
e
r,
T
homas E F
u
ja.
Distrib
uted LT
Co
des.
Informati
on T
heory.
IE
EE
Internatio
na
l Symp
osi
u
m on. Seattle, W
A
. 2005: 98
7 - 991.
[11]
Dino S
e
jd
in
ovi’
c, Dejan Vuk
o
bratovi
’
c, et al. Exp
and
in
g W
i
ndo
w
F
o
unta
i
n
Codes for Un
equ
al Erro
r
Protection.
IEEE Transactions
on Comm
unic
ations.
20
09; 5
7
(9): 251
0-2
5
1
6
.
[12]
Deja
n Vuk
obr
atovic, Vlad
imi
r
Stankovic, Dino S
e
jd
in
ovi
c
., et al. Scalabl
e vid
eo m
u
lticast usi
n
g
expa
ndi
ng
w
i
n
d
o
w
fou
n
tai
n
codes
. IEEE Trans. Multimedia.
2009; 1
1
(6): 1
094-
110
4.
[13]
Vija
y G
Subr
a
m
ani
an, D
o
u
g
l
a
s J
Leith.
On
a c
l
ass
of o
p
timal r
a
tel
e
ss c
odes.
46th
An
nua
l Al
lerto
n
Confer
ence
on
Communic
a
tio
n
, Control, an
d
Com
puti
ng. Ur
ban
a-Ch
amp
a
i
gn, IL. 2008: 4
18-4
25.
[14]
Ping
yi F
a
n. Ne
t
w
ork i
n
formati
on theor
y. Be
iji
ng: T
s
inghua U
n
iversit
y
Press.
2009: 1
51-1
6
8
.
Evaluation Warning : The document was created with Spire.PDF for Python.