TELKOM
NIKA
, Vol.13, No
.1, March 2
0
1
5
, pp. 238~2
4
9
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i1.1268
238
Re
cei
v
ed O
c
t
ober 1
0
, 201
4; Revi
se
d Decem
b
e
r
23, 2014; Accept
ed Ja
nua
ry 1
2
, 2015
A Low Complexity Navigation Data Estimation
Algorithm for Weak GNSS Signal Tracking
Shunxiao Wu*, Yangbo Huan
g, Shaojie Ni, Gang Ou
Coll
eg
e of Elec
tronic Scie
nce
and En
gi
neer
in
g, Nati
on
al Un
i
v
ersit
y
of D
e
fe
nse T
e
chnol
og
y, Ch
angs
ha
410
07
3, Huna
n, Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: shun
xi
ao
_
w
u
@
yea
h
.net
A
b
st
r
a
ct
T
he co
mp
utati
on l
o
a
d
of tra
d
i
tion
al
navi
gati
on d
a
ta estim
a
tion
algorithm
s
for w
eak GNS
S
sign
al
tracking
incre
a
s
es exp
o
n
enti
a
lly w
i
th res
pect
to the
nu
mb
er
of data
bits
ne
ede
d to
be
esti
mate
d. T
o
so
lv
e
this pro
b
l
e
m,
by ad
opti
ng t
he dy
na
mic p
r
ogra
m
mi
ng
p
h
ilos
o
p
h
y, a
navi
gatio
n d
a
t
a
bits
esti
mat
i
on
alg
o
rith
m is
pr
opos
ed. T
h
e
prop
osed
al
go
rithm
uses
t
h
e
partia
l
su
m
o
f
correlati
on v
a
lu
es as
data
bit
combi
natio
n s
earch
ing
branc
hes. It can pre
d
ict an
d e
xcl
u
de se
archi
ng b
r
anch
e
s of dat
a bit co
mb
in
ati
o
n
w
h
ich h
a
ve
s
m
all
coh
e
re
nt ac
cumul
a
ted
en
e
r
gy as
so
on as
poss
i
bl
e by an
gle
qu
ant
ific
ati
on, th
us re
duc
i
ng
its computati
o
n
loa
d
to b
e
l
i
n
early r
e
late
d to
the
n
u
m
ber
of data
bits ne
e
ded to
be
esti
mate
d. Si
mu
lat
i
o
n
results show
that for signa
l
of 500bps n
a
vig
a
tion d
a
ta
rate, the carrier track loop
w
i
th a frequency
discri
m
i
nator i
m
p
l
e
m
e
n
tin
g
0.12s co
here
n
t
accumul
a
tion
by navi
gati
o
n
data esti
mati
on i
m
pr
oves t
h
e
tracking s
ensiti
v
ity up to 7
d
B
compar
ed w
i
th tradi
ti
ona
l frequ
ency d
i
scr
iminat
or un
der
the sa
me tra
c
k
accuracy constraint.
Ke
y
w
ords
: GNSS w
eak sign
al trackin
g
, nav
igati
on d
a
ta bit
s
estimati
on, d
y
na
mic pr
ogra
m
mi
ng
1. Introduc
tion
With the fu
rther
wide
ning
appli
c
ation
of r
adi
o sate
llite navigatio
n, GNSS receiver i
s
facing a mo
re and more deman
ding
work e
n
viron
m
ent: In the coverage of the
urban
canyo
n
s
and vegetatio
n, the sattelite sign
al will b
e
att
enuated
by more than
a dozen o
r
e
v
en dozen
s dBs
comp
ared to
the op
en
sky
con
d
ition [1];
In the p
r
e
s
e
n
c
e
of st
ron
g
i
n
terferen
ce,
even if the
a
n
ti-
jaming tre
a
tment is pe
rforme
d in the
front-en
d
proce
s
sing, it will still re
sul
t
in signal p
o
we
r
antenuation obviously [2]. Improving
the track sensitivity will result
i
n
a higher rat
e
of successf
u
l
positio
ning u
nder
wea
k
si
gnal co
nditio
n
s, so the
ro
b
u
stne
ss of re
ceiver i
s
enh
anced. Freq
u
ency
discrimi
nator
perfo
rms
a key role in the
pro
c
e
ss
of tracking the freque
ncy of the sig
nal carrier,
so its pe
rformance have
large im
p
a
ct for improvi
ng tra
ck
sen
s
itivity [3]
[4]. By using the
correl
ation value se
que
n
c
e come fro
m
the pr
om
pt correlato
r
, frequen
cy discrimi
nator can
estimate the
freque
ncy tra
ck
deviation
whi
c
h is th
e sign
al’s
ca
rri
er freq
uen
cy
minus th
e lo
cal
repli
c
a
ca
rri
e
r
’s freq
uen
cy
. As a
freq
uen
cy e
s
timator, in
orde
r to
obtain
high
estimati
on
pre
c
isi
on, th
e du
ratio
n
of
data
u
s
ed
for
sin
g
le fre
quen
cy di
scri
mination
ope
ration
should
b
e
extended
[5]. Witho
u
t the
auxiliary
wa
ys to a
c
ce
ss the n
a
vigati
on d
a
ta in
a
d
vance, the
the
discrimi
nator need
s to e
s
timate the co
mbination
of navigation d
a
ta bits to a
c
hieve
co
heren
t
accumul
a
tion
. The
mod
e
rn
GNSS
si
gna
ls h
a
ve a
pil
o
t and
data
co
mpone
nt tra
n
s
imited
on
th
e
same
carrier,
and o
n
the
pil
o
t com
pon
ent
no d
a
ta mod
u
lation i
s
p
r
e
s
ent. Althou
g
h
the fre
que
n
cy
deviation can
be estimate
d by the pilot compo
nent
only with no need of d
a
ta estimatio
n
, a
discrimi
nator jointly use t
he correlatio
n value of pi
lot and d
a
ta
com
pone
nt
will get a
be
tter
performanc
e
[6].
So the navigation data
estimation al
gorithm
ha
s great sig
n
ifican
ce for d
e
sig
n
of
freque
ncy di
scrimin
a
tor u
nder
wea
k
si
gnal con
d
it
io
n. Many Lite
ratures have
re
sea
r
ched
the
data e
s
timati
on al
gorith
m
. Literature
[7
] adopt
s th
e
Viterbi al
gorit
hm of
dynam
ic p
r
o
g
ram
m
i
ng
philo
sophy to
impleme
n
t navigation
d
a
ta estim
a
tio
n
, but this
m
e
thod n
eed
s to estimate
the
sign
al amplitu
de, and its eff
e
ctiv
ene
ss is
limited by trace ba
ck
dept
h paramete
r
of the algorith
m
.
Literatu
re [8]
estimate
the
bit co
mbinat
ion ba
se
d o
n
the maximu
m ene
rgy
cri
t
erion, a
nd f
o
r
every 5 adja
c
ent bit
s
, it adopts
an exh
austive
sea
r
ch method. Lit
e
ratu
re [9] co
mbine
s
the f
a
st
Fouri
e
r tra
n
sf
orm (FFT)
wi
th the exhau
stive se
a
r
ch
of navigation
data messa
ge togethe
r, and
the FFT
s ne
eded
by fre
quen
cy di
scrimination i
s
redu
ce
d by usin
g
the
ch
ara
c
teri
stics of
navigation d
a
t
a only takes
the vaule of +1 and -1.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Low Com
p
l
e
xity
Navigati
on Data Esti
m
a
ti
on Algorithm
for Weak
GNSS .... (Shunxi
ao Wu)
239
A higher bit
rate ca
n sh
orten the tim
e
of
first fix and tran
sfe
r
inform
ation
for the
augum
entatio
n system, a lot of GNSS signal
s adopt
high navigati
on data rate, for example, the
Beidou S
a
tellite Navigation System
(B
DS)
us
es a
500 BPS navigation message for its
GEO
satellite’
s
civil signal
s. Those
t
r
aditional
data estimati
on al
gorithms can be easil
y
emplem
ent
ed
for the GPS
signal
whi
c
h has a data
rat
e
of
50 BPS,
while
when used for the
500 BPS signal it
encounte
r
s
a
big computa
t
ional bu
rde
n
and
can n
o
t
be implem
e
n
ted in real-ti
m
e. For the
bit
combi
nation
estimation
problem
of N b
i
ts, due to
i
n
verting all th
e data
bits
will not affect t
h
e
freque
ncy
e
s
timation, the
numbe
r
of bit
co
mbinatio
n
s
n
eed
ed to
be traversed
is
1
2
N
. For the
50 BPS GPS signal, take
N
to 5~8,
the sign
al-t
o-noi
se
ratio
obtained
b
y
cohe
rent
accumul
a
tion
will be high
enough. At this time, the number of bit combin
ations ne
ed to be
searched is l
e
ss. For the
500 BPS
signal, compared
with the 50bp
s
signal, to achieve the
same
coh
e
re
nt inte
gration
time, t
he d
a
ta bit
s
n
eed to
be
e
s
ti
mated i
n
crea
se
s 1
0
time
s.
Ta
ke
achievi
n
g
0.12s cohe
re
nt integ
r
ation
by tra
d
itional
al
go
rithm
a
s
an
exampl
e, for GPS
sign
al only
5
23
2
numbe
r of
bit com
b
inatio
n
s
shoul
d b
e
searche
d
, whil
e for the
BDS
’
s GEO
si
gna
l
59
2
numb
e
r of
bit combi
nati
ons
sho
u
ld b
e
se
arche
d
,
whi
c
h me
an
s the com
puta
t
ion load in
crease
54
2
times
.
With
su
ch a
n
expon
ation
a
l increm
ent
of co
mputat
ion loa
d
, it i
s
difficult to
impleme
n
t d
a
ta
estimation in
real time. Consequ
ently, when u
s
e
d
for GNSS si
gnal
s with hi
gher
data ra
te,
traditional
na
vigation data
estimation
algorith
m
s
can not effe
ctlivly suppo
rt a long
coh
e
rent
acc
u
mulation time.
To solve this proble
m
, a new n
a
vigation
data e
s
timation algo
ri
thm base o
n
dynamic
prog
ram
m
ing
philosi
phy [11] is p
r
op
o
s
ed. Th
e
pro
posed alg
o
rit
h
m uses th
e
partial
sum
of
correl
ation v
a
lue
s
a
s
dat
a bit
com
b
in
ation
sea
r
chi
ng b
r
an
ch
es.
It ca
n p
r
edi
ct an
d ex
clu
de
sea
r
ching b
r
a
n
ch
es of data
bit combinati
on wh
i
c
h hav
e small cohe
rent
accumul
a
ted energy as
soo
n
as p
o
ssible by angl
e quantification. This al
g
o
r
ithm’s
comp
utation com
p
l
e
xity is in linear
relation
shi
p
with the num
ber of data
bi
ts to be
e
s
timated, and it is applied in
a frequ
en
cy-lo
c
ked
loop (F
LL) fo
r wea
k
GNSS
sign
al trackin
g
.
2. Frequen
c
y
D
i
scriminator of Ma
ximization Ener
g
y
Criterion
The ne
w alg
o
r
ithm and it
s perfo
rman
ce i
s
illust
rated b
y
consi
d
e
r
ing
the tracking
of wea
k
GEO sig
nal o
f
BDS. With the assu
mptio
n
of mu
ltiple acce
ss inte
rf
eren
ce
ca
n b
e
negle
c
ted, t
h
e
sign
al re
ceive
d
by the recei
v
er can b
e
expre
s
sed a
s
:
0
()
2
(
)
(
)
c
o
s
(
2
)
(
)
rt
P
C
t
d
t
f
tn
t
(1)
In the a
bove
formula:
P
is the received
signal
power,
()
Ct
is
the
s
p
re
ad
sp
ec
tr
um
cod
e
,
()
dt
is the
navigation m
e
ssag
e,
0
f
is
the c
a
rrier frequenc
y
,
is the initial carrier
phase,
()
nt
is a Gau
ssi
a
n
white noi
se.
The data rat
e
for
()
dt
is 500
BPS, each data bit has a duration
of 2 ms.
Carrie
r
tracki
ng
fo
r Wea
k
sign
al
g
ene
ra
lly
adopt
s the
FLL
st
ru
cture, its im
plem
entation
block
diag
ra
m is
sh
own in
figure
1. Th
e
usual a
ppli
c
a
t
ion sena
rio i
s
that th
e receiver
swit
ch from
a ph
ase
-
lo
cked loo
p
(PLL
) tra
c
king
sta
t
e to FLL
tra
cki
ng state, so
the
b
oun
da
ry of navig
ation
data bits ca
n be assum
ed to be kno
w
n.
After wi
pe off the pseud
o-code and
ca
rri
er, the re
ceived
sign
al is ap
plied to the prompt co
rrel
a
tor, the in
tegral interval of the co
rrel
ator is a navigati
o
n
data bit, which mea
n
s th
e integral tim
e
of the correlator is
2
c
Tm
s
. To improve fre
quen
cy
discrimi
nation
perform
an
ce
, the output seque
nce of
the correl
ator is buffered an
d
group
ed eve
r
y
data bits, a
n
d
then
send f
o
r the di
scri
minator
whi
c
h ca
n jointly estimate the
freque
ncy tra
c
k
deviation an
d
the data bits. Then the fre
quen
cy discr
i
m
ination resu
lts put thro
ug
h the loop filter
and
control the num
eri
c
al
oscillator
(NCO
) u
s
ed fo
r gen
erate th
e local carrie
r, so th
e loo
p
update inte
rval is
c
TN
T
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 238 – 2
4
9
240
Figure 1. Block di
agram of
the
FLL for weak
sign
al tra
cki
ng
The freque
ncy discrimin
a
tor in
the F
L
L is
de
sign
e
d
by the
crit
erion
of maxi
mization
energy of
co
here
n
t a
c
cu
mulated
corralation val
u
e
,
whi
c
h
sh
o
u
ld p
e
rfo
r
m
two di
men
s
i
onal
sea
r
ch of fre
quen
cy devia
tion and
bit combinatio
n.
The p
r
op
ose
d
algo
rithm i
s
u
s
ed
to red
u
ce
the co
mputat
ion loa
d
of finding th
e a
c
cumul
a
ted
co
rrel
a
tion valu
e whi
c
h
hav
e the maxim
u
m
energy and its co
rrespon
di
ng bi
t combi
n
ation at a given frequ
en
cy track deviatio
n
.
For lo
w si
gna
l dynamic
co
ndition
s, the frequ
en
cy track deviation
can be a
s
sum
ed to be
fixed, neglect
i
ng the code
tracking
error, the
g
r
oup
of correlatio
n value
s
use
for freq
uen
cy
discrimi
nation
can be mo
de
lled as follo
w
[12]:
0
[]
c
o
s
(
2
)
[]
[]
s
i
n
(
2
)
[
]
2s
i
n
(
)
()
~(
0
,
1
)
,
1
,
2
,
,
ke
r
r
I
P
ke
r
r
Q
P
ce
r
r
c
er
r
c
IP
k
A
d
f
T
k
k
QP
k
A
d
f
T
k
k
CT
f
T
A
Nf
T
Nk
N
(2)
In the above model:
0
/
CN
is the
signal to noi
se ratio,
A
is the sign
al ampli
t
ude with a
norm
a
lized n
o
ise
en
ergy,
er
r
f
is th
e frequ
ency t
r
a
c
k error deviatio
n
,
is th
e
c
a
r
r
i
e
r
ph
ase
track
deviation,
k
d
is the navigation data bi
ts, its value is + 1 or 1,
[]
IP
k
an
d
[]
QP
k
a
r
e
the correl
atio
n value, and i
t
can be written as a
comp
lex value form
[]
[]
1
*
[]
x
k
I
Pk
j
Q
Pk
.
Acco
rdi
ng to the model of e
quation
(2
), ta
king
a simila
r a
nalysi
s
met
hod of
estimating f
r
eque
ncy of a
singl
e tone
sign
al bu
ried
in noise [5], the maximu
m likelih
ood j
o
int
estimato
r of the frequ
en
cy deviation an
d
navigation d
a
ta is as follo
ws:
2
1
2
0
ˆ
{,
}
a
r
g
{
m
a
x
m
a
x
{
[
]
}
}
N
jf
k
ml
m
l
k
f
D
k
fD
d
x
k
e
(3)
In the above
formula:
1
{}
,
{
1
,
1
}
N
kk
Dd
d
is t
he bit combi
n
ation written i
n
vecto
r
form
,
f
is the frequ
e
n
cy deviatio
n
to be
sea
r
ch
ed,
ˆ
ml
f
is th
e e
s
timated freq
u
ency d
e
viatio
n,
ml
D
is
the
e
s
timatio
n
re
sult
s
of
bit
com
b
inati
on.
In
the
o
p
timization
p
r
oble
m
d
e
fin
ed
by
equati
on
(3), calculatio
n its objective
fucntion ca
n be vi
ewed a
s
su
ch a proce
ss: firstly the origin
al
correl
ation va
lue i
s
ph
ase
rotated, the
n
data mo
dulati
on i
s
wi
ped
o
ff with a bit
combinatio
n fo
r
try, finally the cohe
re
nt a
c
cumulate
d
correlat
ion
val
ue a
n
d
its
e
nergy
is obta
i
ned. T
he
ph
ase
rotation i
s
u
s
ed to co
mpe
n
sate
side
effects o
n
co
h
e
rent a
c
cum
u
lation which
is re
sult fro
m
freque
ncy
de
viation. In a
given fre
que
ncy d
e
viation
,
by only sea
r
chi
ng th
e bit
com
b
inatio
n, a
maximum
co
here
n
t a
c
cu
mulated
ene
rgy ca
n b
e
fin
d
, it ca
n b
e
v
i
ewe
d
a
s
a f
unctio
n
()
ac
c
Ef
,
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Low Com
p
l
e
xity
Navigati
on Data Esti
m
a
ti
on Algorithm
for Weak
GNSS .... (Shunxi
ao Wu)
241
namely:
2
1
2
0
()
m
a
x
{
[
]
}
N
jf
k
ac
c
k
D
k
Ef
d
x
k
e
(4)
So the joint es
timator’s
output
ˆ
ml
f
is wh
ere
()
ac
c
Ef
t
a
kes it
s max
i
mum
v
a
lue.
A
s
sho
w
n i
n
fig
u
re
2, the m
a
ximum likeli
hood
esti
m
a
tor
can
be
ap
proximately i
m
pleme
n
ted,
by
usin
g the co
ndition that
()
ac
c
Ef
is a co
ntinuo
us fun
c
tion a
nd the interp
olation meth
od. This
estimated i
s
use
d
as the freque
ncy di
scriminato
r
of the FLL, its sp
e
c
ific ste
p
s a
r
e
as follows:
1) Set the fre
quen
cy tra
ck
deviation’
s po
ssi
ble value
section
[,
]
ma
x
m
a
x
f
f
, and take
L
sampl
e
point
s with eq
ual space
f
in this section, nam
el
y:
12
1
LL
f
ff
f
;
2) Cal
c
ulate
()
ka
c
c
k
EE
f
use the
propo
sed
data
estimatio
n
algorith
m
, an
d find o
u
t the
sampl
e
poi
nt with the largest en
ergy
{}
mk
E
m
ax
E
, then use
m
f
as the initial
estimate
d
freque
ncy de
viation value.
3) If
1
E
or
L
E
is the
maximum, n
o
interp
olatio
n is n
eed
ed,
dire
ctly limit the freq
uen
cy
deviation
to
1
f
or
L
f
, otherwise firstly ca
lculate the co
efficient
11
11
mm
mm
EE
EE
which can discri
be the
pea
k bia
s
, then the revise
d discrimi
nati
on re
sult is o
b
tained by
ˆ
2
m
ff
f
.
Figure 2. Dia
g
ram of the jo
int estimator
f
o
r freq
uen
cy deviation an
d
navigation d
a
ta
Let the real p
a
rt and the im
agina
ry part o
f
correlat
ion v
a
lue after ph
a
s
e rotatio
n
in step 2) to b
e
[]
r
I
Pk
and
[]
r
QP
k
res
p
ec
tively
，
namely
2
[]
[]
1
[
]
[
]
jf
k
rr
r
I
Pk
Q
P
k
j
x
k
e
x
k
，
then the
optimizatio
n probl
em of eq
uation (4
) can
be expre
s
se
d as:
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 238 – 2
4
9
242
22
1
0
1
0
()
m
a
x
{
(
)
(
)
}
()
[
]
()
[
]
acc
D
N
ir
k
k
N
qr
k
k
Ef
I
S
D
Q
S
D
SD
I
P
k
d
SD
Q
P
k
d
(5)
Thus th
e cal
c
ulatio
n of
k
E
can be
rega
rd
ed a
s
a navi
gation data
e
s
timation p
r
o
b
lem
whi
c
h u
s
e th
e pha
se rota
ted correl
atio
n value and
obtain the m
a
ximum ene
rgy of cohere
n
t
accumul
a
tion
. The correlat
ion value
[]
r
x
k
ca
n be vie
w
ed
as a t
w
o-
dim
ensi
onal ve
ct
or, then it
is 18
0 deg
re
e rotated
wh
en
k
d
is -1, while
k
d
is 1 co
rre
sp
ondi
ng to no rotation
. So the
navigation da
ta estimation
problem
ca
n be viewed
as: given
N
numbe
r of two-dim
e
n
s
iona
l
vectors
who
s
e directio
n ca
n be i
n
verted
180 d
e
g
r
ee,
f
i
nd out
a inve
rsio
n
combi
n
ation which can
make
t
he
su
m v
e
ct
or
{,
}
iq
SS
has the
maxi
mum en
ergy value. In n
e
xt sectio
n,
the low
compl
e
xity algorithm to sol
v
e this
probl
em will be addressed in det
ail.
3. Lo
w
c
o
mp
uta
t
ion com
p
lexit
y
na
v
i
g
a
tion da
ta es
timation
The propo
se
d navigation
data estim
a
tion al
go
rith
m view the pro
c
e
ss of
coherent
accumul
a
tion
as a multist
age de
cisi
on
process,
an
d take the succe
ssive n
a
vigation messag
e
bits a
s
a de
cisi
on vari
abl
e. In literature [7] the dynamic p
r
og
ra
mming p
r
og
ramming p
r
o
c
ess
dire
ctly uses
the bit combi
nation a
s
th
e
stat
e va
riabl
e, while
the
prop
osed
alg
o
rithm
used t
he
curre
n
t accu
mulated correlation value
as the state
v
a
riabl
e whi
c
h
can sta
n
d
s
for a bran
ch o
f
bit
combi
nation,
namely, the dynamic
pro
g
rammi
ng i
s
carrie
d out in
correlatio
n d
o
main. Let th
e
sub
s
et
m
A
of
2
to be the all po
ssi
ble a
c
cum
u
lated correla
t
ion values u
s
ing o
n
ly the first
m
correl
ation v
a
lue ve
ctor a
s
the
data
bi
ts varie
s
. T
h
en it i
s
e
a
sy
to find that
1
A
has
only one
element an
d the followi
ng recu
rsi
on form
ula is corre
c
t:
1
{[
1
]
,
[
1
]
}
1,
2
,
,
1
m
mr
r
s
sx
m
s
x
m
mN
A
A
(6)
After
N
A
be
de
rived by th
e
above
re
cu
rsio
n fo
rmula
,
by finding
its elem
ents of
maximum energy,
()
ac
c
Ef
can
be
obtaine
d. As t
he n
o
ise pa
rt
in the
origi
nal
co
rrelation
value i
s
irrel
e
vant to
each othe
r, t
he a
c
cumul
a
ted
correl
atio
n value
s
a
r
e
limited to a
small area
of two-
dimen
s
ion
a
l plane, whil
e with the increase of
m
, the
number of e
l
ements in
m
A
i
n
c
r
eases
expone
ntially. So fo
r a
la
rg
er
m
, the el
em
ents
dist
ributi
on of
m
A
sho
w
s a fe
ature
of
massive
gatheri
ng. Th
erefo
r
e with t
o
lera
nce of cert
ain ap
proximation, only a little elements in
m
A
is
need
ed to continue the
accumul
a
tion
in the
next
deci
s
io
n-m
a
ki
ng stag
e. These
kee
ped
for
accumul
a
tion
element
s are the mo
st likely to be
of
maximum e
nergy afte
r a
ll the co
rrel
a
tion
value a
r
e
accumulated,
an
d a lot
of oth
e
r el
ement
s i
s
ex
clude
d from con
s
ide
r
a
t
ion in the
after
stage
s in adv
ance. So a subset
m
in
m
A
is d
e
fined recursi
v
ly, which ex
clud
e all the
element
s
that can not
have the ma
ximum energ
y
by cont
inu
e
the coh
e
re
nt accumulati
on, and all the
element
s kee
ped for
co
ntinue a
c
cumul
a
tion is in thi
s
sub
s
et. Th
us the
wh
ole
pro
c
e
ss
of the
algorithm is
: firs
tly s
e
t
11
A
, then recursivly calcul
ate the
2
、
3
until
N
using i
t
s step to
step
re
cursiv
e rel
a
tion
ship
. At last find
out the ve
cto
r
of maximu
m ene
rgy ele
m
ent in
N
, and
use it a
s
the
result of co
h
e
rent a
c
cum
u
lati
on, the correspon
ding
deci
s
ion val
ue seque
nce
are
the e
s
timatio
n
result for b
i
t com
b
inatio
n. So a
p
r
op
erly
correlati
on valu
e ex
cl
usio
n m
e
tho
d
is
need
ed.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Low Com
p
l
e
xity
Navigati
on Data Esti
m
a
ti
on Algorithm
for Weak
GNSS .... (Shunxi
ao Wu)
243
The g
eom
etri
c p
r
in
ciple
u
s
ed for corrrel
a
tion value
e
x
clusi
on i
s
sh
ow i
n
figu
re
3
,
if there
are
two
elem
nets
1
y
,
2
y
in the
m
A
with the
sam
e
an
gle i
n
th
e
pola
r
-angl
e p
l
ane
and
12
||
|
|
y
y
,
then
contin
u
e
do
cohe
re
nt accum
u
lat
i
on fro
m
1
y
ca
n not
get th
e maximum
energy. Thi
s
con
c
lu
sio
n
ca
n be
p
r
oved
by re
du
cti
on t
o
ab
su
rdity.
Suppo
sing
th
at from
1
y
by th
e sub
s
eq
uent
Nm
step
of
coh
e
rent
a
ccu
m
u
lation, a
ne
w ve
ctor
r
is
adde
d to
1
y
an
d
1
y
r
has th
e
maximum energy in
N
A
. As
2
y
r
is also a correlation
value in
N
A
, it stand
s that
12
||
|
|
y
ry
r
…
. On the oth
e
r ha
nd, du
e
to the vecto
r
1
y
r
also is in
N
A
, it can be
con
c
lu
ded th
at
11
||
|
|
y
ry
r
…
. Theref
o
r
e the i
nne
r
prod
uct of
1
y
a
nd
r
shoul
d b
e
non
positive, that
mean
s th
e a
ngle i
s
betwe
en the
m
i
s
le
ss than
o
r
e
q
ual to
90
deg
ree
s
.
Usi
ng t
h
e
con
d
ition of
12
||
|
|
y
y
, it can
be
se
en evide
n
tly from figu
re
3
that
12
||
|
|
y
ry
r
, and thi
s
lead
s to the contradi
ction.
Figure 3. Geo
m
etry prin
cipl
e use
d
for exclu
s
ion
correl
ation value
s
Acco
rdi
ng to the above ge
ometri
c prin
ci
ple,
for elem
ents with the
same an
gle
in
m
A
,
only the
one
with
the
m
a
ximum e
n
e
r
gy is po
ssibl
e
to
be
co
ntinue
accu
mu
lated to
be
the
maximum e
n
e
rgy el
ement
in
N
A
, which m
ean
s that o
n
each ray of
2
, there i
s
at m
o
st o
n
ly
one elem
ent
in
m
. Because the angle’
s value
secti
on
is
contin
uou
s, limited
numbe
r of
correl
ation value can be
exclued by
dire
ctly us
in
g this pri
n
ci
ple. Beca
use
whe
r
e si
gn
al is
pre
s
ent,
()
ac
c
Ef
is si
gnifica
ntly greater t
han
en
ergy
of othe
r
bit co
mbinati
ons, th
e
ado
ption o
f
approp
riate q
uantitative treatment
will
not have
larg
e influe
nce
o
n
navig
ation
data e
s
timati
on
perfo
rman
ce.
So the algorithm takes
quanti
z
ati
on f
o
r the correl
ation value’
s angle in pol
ar-
angle pla
ne, the contin
uou
s se
ction
i
s
approximated
by a finite n
u
mbe
r
of discrete valu
es.
In
other words,
t
he
2
is divide
d
to a finite number of
se
cto
r
s, an
d ea
ch
se
ctor i
s
qua
ntized to its
middle ray.
Calcul
ating
m
an
d exclu
s
io
n correlation val
ue
on thi
s
b
a
s
is, it can b
e
guaranted
that in erve
ry
quantitative sector t
here i
s
at most o
n
ly
one el
ement i
n
m
. Qua
n
tizati
on of a
ngle
for the
algo
rit
h
m divide
d th
e
2
to
M
secto
r
s,
and
the
qua
ntized
ray
s
i
s
uniformly di
stributed,
namely
with
the inte
rval
of
, the di
screte
qua
ntitative angle
for
se
ction
[0
,
2
]
is:
12
M
. For a
n
y accumul
a
ted
correlation val
ue
{,
}
x
y
SS
at step
m
, it can b
e
expre
s
sed in
the polar-a
ngl
e plane a
s
fol
l
ow:
22
cos
(
),
s
i
n
(
)
[0
,
2
]
,
xy
xy
SE
S
E
ES
S
(7)
In the quantization pro
c
e
ss, the sample
pha
se
()
ks
in
,1
,
2
,
,
k
kM
whi
c
h is
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 238 – 2
4
9
244
most
cl
osel t
o
is sele
cted a
s
the qua
ntized angl
e, and
keep
s the en
ergy not ch
an
ged, so the
quanti
z
ed a
c
cumul
a
ted ve
ctor
{,
}
iq
SS
can be e
x
presse
d as f
o
llow:
()
()
c
o
s(
)
,
s
i
n(
)
ik
s
q
k
s
SE
S
E
(8)
Acco
rdi
ng to
the above
an
alysis, the
ne
w nav
ig
ation data
e
s
timation
alg
o
rithm can be
impleme
n
ted
as the flow
ch
art in Figure 4.
The process
of calculation
1
m
base
d
on
m
can be sp
ecfi
ce
d as follo
ws:
1) At initial set
1
m
to an empty set.
2) Fo
r ea
ch
element
y
in
m
, calculat
e the accu
mulated ve
ctor
y
whose
corre
s
p
ondin
g
next bit val
ue i
s
1,
and
the a
c
cumul
a
ted ve
ctor
y
wh
ose
corre
s
po
nding
next bi
t
value is -1.
3) Let
()
ky
to be
the qu
antized
angl
e of
y
, if there
i
s
n
on
e
l
ements in
1
m
has
a
quanti
z
ed
an
gle of
()
ky
, add
y
to
1
m
; otherwi
se,
let
z
to be th
e
eleme
n
t in
1
m
whi
c
h
has the
qua
ntized a
ngle of
()
ky
, then comp
a
r
e the am
ptitude value of
y
and
z
, if
||
|
|
y
z
，
the element
z
of
1
m
is repl
aced by
y
, else keep
1
m
uncha
ng
ed.
Figure 4. Flow ch
art of implementin
g
the navigation
data estimati
on algo
rithm
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Low Com
p
l
e
xity
Navigati
on Data Esti
m
a
ti
on Algorithm
for Weak
GNSS .... (Shunxi
ao Wu)
245
4) Ta
ke the same processi
ng for
y
to
y
.
From th
e recursive
calcul
a
t
ion process
of
m
, it can b
e
see
n
that ele
mment nu
mb
er of
m
is less than
M
. By noticing t
hat com
putati
on amo
unt
at
each iteratio
n step i
s
p
r
op
ortional
to the num
be
r of the
elem
ents in
m
, the total co
mputat
ion complexit
y
uppe
r bo
un
d is in
the
form of
M
N
. The
r
efore, for a fixed
M
, the co
mputation
co
mplexity of the algo
rithm
is in
linear
rel
a
tion
ship
with the
numbe
r of d
a
t
a bits to
b
e
e
s
timated. Of
cou
r
se, a
s
th
e increa
se
of
N
, incrment
i
n
M
is
nee
d
ed to
re
du
ce the
qu
ant
ification
erro
r, an
d thu
s
re
du
ce the
corre
s
p
ondin
g
perfo
rman
ce loss.
4. Performan
ce Analy
ses
In order to g
e
t the
spe
c
ifi
c
q
uantitative
anal
y
s
is re
sults, aim
ed f
o
r th
e GE
O
sign
als of
BDS, setting t
he cohe
re
nt a
c
cumulatio
n
ti
me to 0.12
s
(t
hat mea
n
s
N
=
60
$), th
e p
e
rform
a
n
c
e
of
data e
s
timati
on an
d fre
q
u
ency di
scrimi
nation u
nde
r
typical wea
k
sign
al conditi
on is verified
by
nume
r
ical si
mulation.
Con
s
id
erin
g
that unde
r th
e low dyn
a
m
i
c c
ondition,
the frequ
en
cy track
devia
tion is
relatively sm
all, so in the implem
emnt
of th
e
freq
u
ency discrimi
nator
the se
ction of
po
ssible
freque
ncy de
viation is set
to
[1
0
,
1
0
]
H
zH
z
, and 11 sampli
ng poi
nts with interval of 2Hz is
sele
ct
ed i
n
it
.
Whe
n
M
is sufficiently la
rge,
the pe
rform
a
nce i
m
prove
m
ent obtai
ne
d by in
cre
a
se
M
is
not
obvi
ous. Sim
u
lati
on
re
sults shows th
at ta
ke
10
2
M
can
en
sure
rel
a
tive
high
perfo
rman
ce,
so the pe
rformance sim
u
l
a
tion in
this p
aper i
s
ca
rri
e
d
out in su
ch
a ca
se.
4.1. The bit e
rror rate of n
a
v
i
gation da
ta es
timatio
n
For si
mpli
city, without co
n
s
ide
r
ing the
error
corre
c
ti
ng en
cod
e
a
nd de
cod
e
techni
que,
only the origi
nal bit erro
r rate is cou
n
te
d. Acco
rdin
g to the optimal data demo
dul
ation theory, the
theoreti
c
al e
r
ror rate
can b
e
cal
c
ulate
d
by the followi
ng formul
a [13]:
2
00
/2
(2
/
)
1
()
2
z
x
BER
Q
C
N
T
Qx
e
d
z
(9)
As the fre
q
u
ency diviatio
n sa
mpling i
n
terval of th
e discriminat
or i
s
2
Hz,
in the
simulatio
n
th
e pha
se rotation proc
ess is bypassed. T
he freq
uen
cy di
viation valu
e is take from
-
1Hz to 1Hz in
steps of 0.2
H
z, an
d for e
a
ch valu
e 20
00 gro
up of o
r
iginal
co
rrel
a
tion is gen
era
t
ed
for process.
The a
c
tual
st
atistic bit
error rate an
d t
he theo
reti
cal
bit error
rate
without tracking
deviation at d
i
fferent CNR
are a
s
sh
own
in table 1.
Table 1. The
statistic
re
sult
s of bit erro
r rate
CNR
（
dB-
H
z
）
The total
number of d
a
ta
bits
The measur
ed bit
error
rate
Theoretical bit
error
rate
27 1.32e6
0.08245
0.0783
26 1.32e6
0.10823
0.1035
25 1.32e6
0.13656
0.1304
24 1.32e6
0.16719
0.1580
23 1.32e6
0.19812
0.1859
22 1.32e6
0.22850
0.2131
21 1.32e6
0.25886
0.2392
20 1.32e6
0.28819
0.2637
It can be see
n
from table
1 that the measu
r
ed bit e
r
ror rate i
s
wel
l
close to the
bit err
rate
obtain
ed
by the
optima
l
dem
odulatio
n theo
ry. Th
e
lower the
CNR i
s
, the
g
r
ea
ter the
bit
error
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 238 – 2
4
9
246
differen
c
e i
s
,
but the
maximum differen
c
e i
s
not mo
re than
0.03.
Whe
n
the
CNR i
s
a
s
l
o
w a
s
2
0
dB-Hz, the
bit
error rate i
s
up to
clo
s
e
0.
3, at th
is con
d
ition
seri
ou
s loss
of fre
q
u
ency
discri
nat
ion
perfo
rman
ce i
s
expe
cted.
4.2. The freq
uenc
y
discriminator per
f
ormance
The p
e
rfo
r
ma
nce
of the
fre
quen
cy di
scri
minat
or un
de
r different
CNR i
s
inve
stiga
t
ed by
simulatio
n
.
With a
given
CNR an
d frequ
ency t
r
a
c
k de
viation, the
g
a
in
coeffici
ent
and
noi
se
le
vel
of the di
scrim
i
nator
at ce
rt
ain
conditio
n
can
be
refle
c
ted by
statis t
he ave
r
ge val
ue an
d vari
an
ce
of the di
scrin
a
tor’s outp
u
t. Fro
m
-7.5
Hz to
7.
5
Hz,
with the
inte
rval of 0.5
Hz, 16 frequ
en
cy
deviation val
ue is sele
cte
d
to gene
rat
e
the or
igi
n
a
l
correlatio
n value. At a
given CNR
and
freque
ncy
de
viation
2000
ori
g
inal
correlation val
ue
is p
r
o
d
u
c
ed.
By statisin
g t
he ave
r
g
e
va
lue
and varia
n
ce
value of discrimin
a
tor o
u
tput at
different CNR a
nd frequ
en
cy deviation, the
pero
r
ma
nce curve of the discrimin
a
tor is as sh
own in Figure 5.
Figure 5. The
performan
ce
curve
of the frequ
en
cy discrimi
nator
It can be see
n
that when
0
/
CN
is 25 db-Hz, the frequ
en
cy di
scrimi
nator
can reflect th
e
input freq
uen
cy deviation
exactly, but whe
n
the
0
/
CN
reduced to 20
db-Hz, the
p
e
rform
a
n
c
e
of the
discri
m
i
nator de
crea
sed
si
gnifica
ntly. Refered
to the
def
initi
on of
the
ave
r
age
d
gain
a
n
d
norm
a
lize varian
ce of p
h
a
se
discri
minat
ot in literature [2], the avera
ged
gain
d
K
a
nd
norm
a
lized v
a
rian
ce
n
for the fre
que
n
c
y di
scrimin
a
tor
can
be
define
d
. O
n
this ba
sis,
quantitative p
e
rform
a
n
c
e
compa
r
ison b
e
twee
n the
n
e
w fre
quen
cy
discrimin
a
tor of this pape
r
and the tradit
i
onal freq
uen
cy discirmi
na
tor can b
e
d
one, the re
su
lts are sho
w
n in Table 2.
In
orde
r to en
sure the
sam
e
length of co
rrel
a
tion valu
e is u
s
ed fo
r freque
ncy di
scrimin
a
tion, the
traditional
di
scrimin
a
tor i
s
d
e
si
gne
d
as foll
ows: a
)
Divide the
60
correl
atio
n value
s
i
n
to
30
grou
ps, with
each gro
up i
n
clu
d
ing the
two adja
c
e
n
t correlatio
n value
s
; b) For each g
r
ou
p of
data, firstly the ratio b
e
twee
n cro
ss
prod
uct
a
n
d
dot prod
uct
is cal
c
ul
ate
d
, and then
the
estimated
fre
quen
cy value
s
is produ
ce
d
by an a
r
c ta
ngent fun
c
tio
n
; c) the e
s
ti
mated valu
es got
from 30 g
r
ou
p of data is a
v
erage
d up to
form the final discrimin
a
tor output.
Table 2. Co
m
pari
s
on of di
scrimi
nator p
e
rforman
c
e
Discriminator t
y
p
e
CNR
（
dB-
Hz
）
averaged gain
Normalized
variance
（）
Hz
Ne
w
fre
quenc
y
detector
25
0.8857
3.1570
20
0.2423
25.1356
Traditional
25
0.1173
107.61
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Low Com
p
l
e
xity
Navigati
on Data Esti
m
a
ti
on Algorithm
for Weak
GNSS .... (Shunxi
ao Wu)
247
discriminator
20
0.0295
443.56
It can b
e
see
n
from T
able
2 that the n
o
rmalize
d
vari
a
n
ce
and th
e
averag
ed g
a
i
n
of the
new frequ
en
cy discrimin
a
tor is
sig
n
ifica
n
tly supe
ri
o
r
outperfo
rm
s the traditio
nal
discrimi
ntor
at
the two investigated CNR.
Espe
cially, when the CN
R is 20 dB-Hz,
the traditiona
l discriminato
r
’s
output is alm
o
st pure noi
se.
4.3. Ev
aluation of compu
t
ation
a
l complexit
y
The n
a
vigatio
n data e
s
tim
a
tion alg
o
rith
m is impl
eme
n
ted by C++
and
run
s
o
n
a 64 bit
serve
r
with 2
.
4 GHz CP
U,
so the amo
unt of
calcul
ation can b
e
measu
r
ed b
y
run time of the
pro
c
e
ss. B
e
cause the
mai
n
computatio
n load
of
the
discri
minato
r
embo
die
s
in
the navig
ation
data e
s
timati
on, the
run
time of the
ne
w fre
que
nc
y
discrimi
nator
in table
2 i
s
mainly con
s
u
m
ed
by data e
s
timation. The
r
ef
ore the
sin
g
le
run time
fo
r
data e
s
timation is o
b
taine
d
by divding
run
time of di
scri
minator with t
he time
s of
d
a
ta e
s
timatio
n
u
s
ed i
n
the
discri
minato
r
, the re
sult
s
are
sho
w
n in Ta
b
l
e 3.
Table 3. Average ru
n time for a sin
g
le na
vigation data
estimation
Method
CNR
(dB
-
Hz)
estimati
on times
Average run time
Ne
w
method
in this paper
25 17600
13.9
ms
20 17600
14.2
ms
Traditional meth
od
25
1
>1500 s
Adopting th
e
traditional
ex
hau
stive se
arch m
e
thod to
estimate
nav
igation d
a
ta,
even for
a si
ngle
bit combinatio
n, the run tim
e
i
s
g
r
eate
r
th
a
n
15
00
s, so
whe
n
u
s
e
d
f
o
r a
60
bit d
a
ta
estimation, t
he cal
c
ul
atio
n amount for the new
alg
o
rithm is le
ss than 0.00
0
01 times of the
traditional
alg
o
rithm. As th
e FLL up
date
s
every 12
0
ms, it can b
e
see
n
from the
above table t
hat
the processin
g
speed
of d
a
ta e
s
timatio
n
is
nea
r the
req
u
ire
m
ent
of re
al-time
impleme
n
tation,
and by
redu
cing
M
the p
r
o
c
essing
spee
d
ca
n b
e
im
proved m
o
re.
The
ne
w d
a
ta e
s
timation
algorith
m
ne
ed to sto
r
e
m
whi
c
h at mo
st can have
M
e
l
ements,
so it
s re
quired a
m
ount of
stora
ge
i
s
in linear relatio
n
s
hip with
M
. While the tra
d
itional alg
o
rith
m only nee
d
s
to sto
r
a
g
e
the
current maximum en
ergy amon
g the
bit co
m
b
i
nation
s
h
a
ve
bee
n
sea
r
ched, its requi
red
amount of storag
e is less.
This fact sh
ows t
hat the
dynamic p
r
og
rammin
g
alg
o
rithm
s
have
the
feature of re
p
l
acin
g the time comp
lexity
with the s
p
ace c
o
mplexity.
5. Simulation
As the data
estimation
ca
n be imple
m
ented with lit
tle comp
atio
n amout, thi
s
arti
cle
desi
gned a frequency di
scriminator for the 500 BPS
signal with a
0.12s
coherent accumulati
on
time. The F
LL’s t
r
ak capability improvement for
weak
signal of the new discrimi
nator is
investigate
d
by simulation.
The
se
co
nd-orde
r
FLL
st
ructu
r
e
is a
d
opted
fo
r si
mulation, an
d
by usi
ng
t
he
n
e
w
discrin
a
tor a
nd tradition
al
discrimin
a
to
r mentio
n
ed
in the previo
us sectio
n resp
ectively, two
tracking lo
op
s is de
sig
ned
for comp
are.
The initial value of dop
pl
er freq
uen
cy is -18
0
Hz, the
total length o
f
the simulation data is 1
2
0
s, and the
l
oop
s start wo
rk at a stea
d
y
trackin
g
sta
t
e
,
whi
c
h m
ean
s the initial vel
e
city an
d a
c
cerla
r
ati
on t
r
a
cki
ng
error is 0. As only
con
s
id
erin
g t
h
e
carrie
r tracki
ng, the
co
de
tra
cki
ng
de
viation is
a
s
sume
d to
be
ze
ro. A
c
cording to
the l
oop
para
m
eter
de
sign m
e
thod i
n
literatu
r
e in
[14], the
mai
n
ch
ara
c
te
rist
ics
of a tra
c
ki
ng loo
p
can
be
reflecte
d by the pro
d
u
c
t of the loop
noise ban
dwi
d
th
L
B
and the
loop upd
ate
interval
T
,
namely
L
B
T
.
For the
stati
c
situ
ation with ze
ro
do
pple
r
viration rate,
a
smalle
r
l
oop
band
width
sho
ud b
e
a
d
opted, so the
loop
parame
t
ers i
s
desi
g
n
ed un
de
r con
d
ition of
0.01
L
BT
. For the
dynamic
situ
ation of 3 Hz/s dop
ple
r
vira
tion ra
te, a wi
der lo
op ba
n
d
width
sho
u
d
be ado
pted, so
the loop
pa
ra
meters i
s
de
signed
und
er
con
d
ition of
0.025
L
BT
.
In
the static con
d
ition
of 2
0
dB-Hz signal,
the
trackin
g
error co
m
pari
s
on
of the two loop
s is
sh
own in
Figu
re 6; while i
n
the
Evaluation Warning : The document was created with Spire.PDF for Python.