2004 RISP International Workshop on Nonlinear
Circuit and Signal Processing (NCSP'04)
Hawaii, USA, Mar. 5-7, 2004.

Research on a Positioning Using Chaotic Sequence
Natsumi Dake and Yoshifumi Nishio
Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, Japan
Tel: +81-88-656-7470, Fax: +81-88-656-7471
Email: {dake, nishio}@ee.tokushima-u.ac.jp

X n+1

1. Introduction

0.5

Chaos is nonperiodic and could generate sequences with
infinite length theoretically [1][2]. Although the sequenceslook like a noise, the values can be predicted exactly if thedynamics and the initial value are provided. On the otherhand, positioning is an important subject to pinpoint one’sposition. In positioning, though the GPS is famous, anothersystem using the m-sequence for ITS (Intelligent TransportSystems) has been also proposed [3].
In this study, a possibility of the chaotic sequence for a kindof positioning is investigated. At first, a chaotic sequence
generated by the skew tent map with a given number is stored.
When a few number of successive values are obtained fromthe storage, the position of the head of the successive values isestimated. The least squares method is used for the judgmentof the position. As varying the length of the sequence andthe signal-to-noise ratio of the data-reading channel, the error
rate is evaluated by computer simulations.
2. Chaotic sequence
In this study, the skew tent map is used to generate chaoticsequences. The skew tent map is known as the simplest onedimensional map generating chaos. The map is shown in Fig.
1. If the top coordinate is given as (a, 0.5), the equation describing the skew tent map is asaxn+ 0.5 −
(1)
xn+1 =0.5 + a
0.5 + a
xn+1 =0.5 +a
0.5 − a(−0.5 ≤ xn ≤ a)−xn
0.5 − a(2)(a < xn ≤ 0.5).
Because of the sensitive dependence on initial values andparameters, we could generate a number of different chaotic
sequences by changing the initial value x 0 or the parameter
a.

0.4
0.3
0.2
0.1
0-0.1
-0.2
-0.3
-0.4
-0.5
-0.5

-0.4

-0.3

-0.2

-0.1

00.1

0.2

0.3

0.4

0.5

XnFigure 1: Skew tent map.

3. System model
A chaotic sequence x 0 , x1 , x2 , · · ·, xN (N : Chaotic sequence length) is generated by giving an initial value x 0 to
the skew tent map with a fixed value of the parameter of a.
These values are memorized in a storage keeping the order.
We consider to estimate the position of the head of a few
number of successive values when the successive values areobtained from the storage. In the case of no noise, only one
value is enough to decide the position by virtue of the nonperiodic feature of chaotic sequences. However, under noisy environment, some number of successive values are necessary
to decide the position. We consider the case that M successive values (M : Data length) are extracted from the storage.
When an additive white Gaussian noise is added to the values, the error rate to decide the position is evaluated. In thisstudy, the least squares method is used for the judgment ofthe position.
4. Simulation result
In the following computer simulations, the parameter of- 269 -the skew tent map is fixed as a = 0.05. The computer simulations are carried out as(1) fixing the chaotic sequence length and changing thesignal-to-noise ratio,(2) changing the chaotic sequence length and fixing the data
length or the signal-to-noise ratio,(3) setting a threshold.

log10(ER)
0-0.5
-1
-1.5
-270dB
80dB
90dB
100dB

-2.5
-3

4.1. Fixing chaotic sequence length-3.5

At first, we carried out computer simulations as fixing thechaotic sequence length as N = 100 and changing the signalto-noise ratio for the data lengths M = 3, 4, 5, 8.
The graph of the error rate is shown in Fig. 2. The data in
the graph is the average of 100,000 results for different initialvalues.
We can say that increasing the data length makes the error
rate small.

-4-4.5-5
100

1000

10000

Figure 3: Error rate for the fixed data length (M = 3).
log10(ER)03458log10(ER)
-1

0

3
4
58-1100000

Chaos series length-2-2-3-3-4-4-5

110

100

1000

10000

100000Chaos series length-5203040506070

8090

Figure 4: Error rate for the fixed signal-to-noise ratio(S/N =100dB).

100

S/N[dB]

Figure 2: Error rate for the fixed chaotic sequence length(N = 100).
large, the computational effort will increase. Hence, we consider to set a threshold in order to reduce that. Namely, if theread-out data is enough to be close to the data extracted from
4.2. Changing chaotic sequence length
the storage, further extraction is given up and the position isSecondly, we carried out computer simulations as changing decided as a right one.
In order to estimate an appropriate value of the threshold,the chaotic sequence length from N = 100 to N = 100000.
thecalculated values by the least squares method are shown
In the simulations, 100,000 trials are carried out as fixing theinFigs.
5 and 6 for the cases of M = 3 and 8, respectively. In
initial value of the chaotic sequence as x 0 = 0.111111. Figthe
figures,
black circles show the minimums and grey (red)ure 3 shows the error rate when the data length is fixed assquares
show
the second smallest values. Other conditions
M = 3 and the signal-to-noise ratio is varied as S/N =70dB,
aresetas
N=1000 and S/N =100dB.
80dB, 90dB, and 100dB. While Fig. 4 shows the error rate
From
thefigures,
we can say that the position is correctly
when the signal-to-noise ratio is fixed as S/N =100dB anddecided
ifthethresholdis set within [10 −9 , 10−10 ] for M =the data length is varied as M = 3, 4, 5, and 8.
3. Further, for the case of M = 8, the threshold around 10 −7
would decide a correct position with a high probability.
4.3. Setting threshold
Figure 7 shows the error rate when the threshold is given
In this study, the read-out data has to be compared with all to the system. The chaotic sequence length is fixed as N =of the memorized data in the storage in order to decide the po- 1000 and the signal-to-noise ratio is fixed as S/N =100dB.
sition of the read-out data. Thus, if the data length becomes The data length is changed as M = 3, 5, and 8.

- 270 -

log10(ER)value

01-0.50.01-1-1.50.0001

-2

1e-06

35
8-2.5-3

1e-08

-3.5

1e-10-4-4.5

1e-12

1e-14-5
1e-12

0

100

200

300

400

500

600

700

800

900

1e-11

1e-10

1e-09

1e-08

1e-07

1e-06

1000

1e-05

0.0001Threshold

TRIAL

Figure 7: Error rate with the threshold.

Figure 5: The minimum and the second smallest value by theleast squares method (M = 3).

stop position
1000

value

35
8

900

1800

0.01

700

0.0001

600
500

1e-06
400

1e-08

300

1e-10

200
100
1e-12

1e-12

1e-11

1e-10

1e-09

1e-08

1e-07

1e-06

1e-05

0.0001Threshold
1e-14

0100200300400500600700

800900Figure 8: Stop position with the threshold.

1000TRIAL

Figure 6: The minimum and the second smallest value by theleast squares method (M = 8).

At last, we show the graph of the stop position of comparing for the decision in Fig. 8. For the threshold value morethan 10−10 , the computation time becomes less than the halfof the case without the threshold.

Reference[1] E. Atlee Jackson, Perspectives of Nonlinear Dynamics 1,Cambridge University Press, 1991.
[2] Katsufusa Syono, Chaos Engineering, Springer-Verlag
Tokyo, 2002.
[3] Takaaki Hasegawa, “A Vehicular Driving Assistant System Using Spread Spectrum Techniques,” IEICE Trans. Fundamentals, vol. E81-A, no. 11, pp. 2334-2340, 1988.

5. Conclusions
In this study, a positioning system using chaotic sequence
has been proposed and the basic property of the system has
been investigated by computer simulations.
Acknowledgement
This work was partly supported by The Telecommunications Advancement Foundation’s Research Grant.

- 271 -

- 272 -