Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.cplire.ru/rus/InformChaosLab/papers/coc00ade.pdf Äàòà èçìåíåíèÿ: Tue Jul 18 14:44:36 2000 Äàòà èíäåêñèðîâàíèÿ: Sat Dec 22 05:41:32 2007 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: trees

Separation of Chaotic Signals Using their Inherent Dynamical Nature
Yuri V. Andreyev and Alexander S. Dmitriev
Institute of Radioengineering and Electronics of Russian Academy of Sciences Mokhovaya st. 11, GSP-3, Moscow, 103907 Russia tel: (095) 202-59-55, fax: (095) 203-84-14, e-mail: chaos@mail.cplire.ru

Elena V. Efremova
Moscow Institute of Physics and Technology Institutskii st. 9, Dolgoprudny, Moscow region, 141700 Russia tel: (095) 202-59-55, fax: (095) 203-84-14, e-mail: chaos@mail.cplire.ru
Abstract. Here we describe a method for separating the sum of chaotic signals into the individual components, using the inherent underlying dynamics of the chaotic sources. Capabilities of the method are demostrated on example of discrete-time systems, one-dimensional logistic maps. We demonstrate that the proposed approach based on backward iteration of the mapping equations describing the chaotic sources has good resistance in respect to additive external noise. Keywords: chaotic synchronization, signal separation, multiplexing, effect of noise on chaotic systems, processing chaotic signals The discovery of the effects of chaotic synchronization [1]­[2] and synchronous chaotic response [3] has drawn attention to application of chaotic signals to communications [4]­[8]. This interest is associated first of all with a possibility of accomplishing chaotic receivers (driven or response dynamic systems) that can self-synchronize with chaotic transmitters (drive chaotic systems). However, potential applications of the chaotic synchronization and synchronous chaotic response are not confined to this. As was shown recently [9], with the help of these effects, the sum of chaotic signals can be broken into the components. The problem of separation of chaotic signals is of great interest in analysis of natural or artificial ch aotic signals. In particular, its efficient solution can give an impact to development of novel principles of multiple access in communication systems. Indeed, the multiple access in communication systems is ensured by a shared use of the same frequency channel by several users by means of dividing the frequency band into several frequency sub-bands (frequency division multiple access, FDMA), giving each user individual time slots (time division multiple access, TDMA), or using special codes (code division multiple access, CDMA) [10]. Separation of chaotic signals by means of backtracking cannot be attributed to any of the above methods. The problem that is discussed here is as follows. Let there be m pairs of drive and response systems (transmitters and receivers, respectively). To transmit chaotic signals xj(k), j = 1, ..., m, from transmitters to receivers a single communication channel is used in which the signals xj(k) are summed. In general, noise (k) is added in the channel to the sum of the chaotic signals. At the receiving side each receiver retrieves its own signal from the sum. Consider the problem of chaotic signal separation on example of a single channel connecting two pairs of transmitters and receivers. Let the dynamics of the transmitters be described by similar maps (.) with different parameters µ. Let us denote them by 1(x) = (x, µ 1) and 2(x) = (x, µ2). The dynamics of both drive ch aotic systems are then described by the equations x1(k+1) = 1(x1(k)), x2(k+1) = 2(x2(k)), where k is discrete time. The signal in the channel is u(k) = x1(k) + x2(k) + (k). (2) was with was was (1)

Recently, a scheme for chaotic signal multiplexing proposed, where the response systems were coupled each other and the effect of chaotic sinchronization used [9]. The dynamics of the multiplexing process described by the equations y1(k+1) = 1(y1(k)) + [u(k) ­ 1(y1(k)) ­ 2(y2(k))], y2(k+1) = 2(y2(k)) + [u(k) ­ 1(y1(k)) ­ 2(y2(k))],

(3)

where y1,2(k) were the signals in the response maps and was the coupling strength. In the case of synchronization the terms within the brackets become small (of the order of the noise level (k)), so y1(k) x1(k) and y2(k) x2(k), thus, the receivers retrieve their "own" signals. As was shown in [9], this scheme for multiplexing chaotic signals could operate in the absence of external noise, though it was very sensitive to noise if it was added. In this paper, we introduce a novel scheme for chaotic signals separation and prove that it is more noise resis-


tant than the scheme [9]. Hence, we show that the boundary of noise resistance can be considerably shifted toward higher noise levels, and that one can expect practical accomplishment of this approach in a physical experiment. Let for certainty the chaotic sources be described by the maps of logistic parabola (x) = µx(1­x) x1(k+1) = µ1x1(k)(1 ­ x1(k)), x2(k+1) = µ2x2(k)(1 ­ x2(k)). (4)

The idea of the proposed separation scheme is as follows. The receiver, a chaotic signal separator, incorporates copies of the maps that generate chaotic signals in the transmitters. The sum signal u(k) is fed to the receiver input. Let in the receiver at moment k there be not only an estimate of the sum of chaotic signals u(k), but also separate estimates of the values of the chaotic signals of both drive systems, i.e., an estimate ~ 1(k) for the signal x x1(k) and ~ 2(k) for x2(k). Let us iterate the maps of the x response systems y1(k+1) = µ1y1(k)(1 ­ y1(k)), y2(k+1) = µ2y2(k)(1 ­ y2(k)) (5)

iteration. The branch can be chosen as follows. Let us iterate maps (6) with the initial conditions y1(k) = ~ 1(k) x and y2(k) = ~ 2(k). As a result, at (k­1)th moment we x have two signal estimates ~ 11(k­1) and ~ 12(k­1) for the x x first response system, and two estimates ~ 21(k­1) and x ~ 2(k­1) for the second system. These estimates give us x2 four possible estimates of the sum signal at (k­1)th moment: uij(k­1) = ~ 1i (k­1) + ~ 2j(k­1), i, j = 1, 2. From x x the other hand, we know that the signal that came to the receiver from the channel at (k­1)th moment was u(k­1). We can make the proper choice of the branch by means of comparing the value of u(k­1) with those of uij(k­1). Indeed, the proper choice is given by that combination of the branches that minimizes deviation of the estimates of the sum of two chaotic signals from the sum signal that came in the receiver at that moment: (7) |u(k­1) ­ ~ i (k­1) ­ ~ j(k­1)| x x
1 2

one step backward with initial conditions ~ 1(k) and x ~ (k), respectively. This is equivalent to one-step forx2 ward iteration of maps ­1(.), inverse to maps (.) (Fig. 1) y1(k­1) = 1­1(y1(k)), y2(k­1) = 2­1(y2(k)). (6)

The scheme for the choice of the proper branch combinations at (k­1)th and other moments is illustrated in Fig. 2. The values of signal u(l), l < k, are denoted by asterisks. At lth moment of four possible values of uij(l) we take the one most close to u(l), do the same at (l­1)th moment, and so on. Thus, the discussed procedure allows us to separate the signals for any time moment l < k.

Fig. 2. Choice between the sum signal branches, produced by iteration of inverse maps. The values of the sum signal at the receiver input are denoted by asterisks. l is discrete time; uij(l) = ~ 1i(l) + ~ 2j(l), i, j = 1, 2. x x

Fig. 1. Two-valued inverse map function ­1(.).

Since maps (5) are stretching on the average (over the attractors) by forward iteration, by backward iteration they are (on the average) contracting. Hence the estimates for signals x1 and x2 at (k­1)th moment, obtained from the estimates ~ 1(k) and ~ 2(k), will on the average x x be more accurate that the initial estimates ~ 1(k) and x ~ (k). Note, however, that maps (6) are two-valued. x2 Each one-step iteration gives two values for a single argument. So, we have to choose the "proper" branch after

If is Lyapunov exponent of a map (averaged over the map attractor), then the average stretching factor of the map is e, and the inverse map contraction factor is e­. So, the estimate errors 1(l) and 2(l) of the separated signals ~ 1(l) and ~ 2(l) decrease exponentially (on the x x average) 1(l) = 1(k)exp(­1(k ­ l)), 2(l) = 2(k)exp(­2(k ­ l)), (9) where 1(k) = | ~ 1(k) ­ x1(k)| and 2(k) = | ~ 2(k) ­ x2(k)| x x are initial estimate errors, and 1 and 2 are Lyapunov exponents of the trajectories of the first and second response systems, respectively.


Above, we discussed the scheme of signal separation under condition that estimates ~ 1(k) and ~ 2(k) of the x x transmitter signals are known at kth moment. However, in general, at kth moment there are no separate estimates of the drive systems' states. As was found in numerical simulation, as such initial estimates, we can take any arbitrary pair of points y1(k) and y2(k) belonging to the attractors of maps (5). Having started from these initial conditions the calculated trajectories of the response systems converge with time to the trajectories of the drive systems. It is the time of convergence that depends on a particular choice of the initial points on the attractors. To ensure rapid convergence and to improve the initial signal estimates at kth moment, we take a set of m initial values y1j(k), j = 1, ..., m, for the variable y1(k). Each initial point must belong to the attractor, and the entire set must cover it more or less evenly. Also, we take a similar set of initial conditions for y2(k). Let be the given initial accuracy of the separated variable estimates. We make all possible pairs of {y1i (k), y2j(k)}, i, j = 1, ..., m, from the initial condition sets, and take those satisfying the inequality |u(k) ­ y1i (k) ­ y2j(k)| < . (10) We iterate the maps for each of the taken pairs one step backward and obtain quadruple number of pairs. Among them we choose the one that minimizes condition (7) and take it as a pair of good initial estimates ~ 1(k) and x ~ (k) of the reiever signal at moment k. x2 The efficiency of the proposed scheme of chaotic signal separation was investigated on example of the drive systems described by logistic maps (4) with the parameters set at µ1 = 3.7 and µ2 = 3.8 (Lyapunov exponents 1 = +0.355 and 2 = +0.432). In the absence of noise, the signals of two logistic maps are efficiently separated. The accuracy of the signals ~ (k) and ~ (k) recovered in the receivers increases x1 x2 exponentially with each step of backward iteration, in accordance with expression (9). In our numerical experiments with double-precision calculations (16 significant digits, i.e., 10­16 accuracy) the limit attainable separation accuracy is achieved after ­ln(10­16)/ 100 iteration steps, while a pretty good accuracy of 10­3 after 20 steps. Consequently, the procedure allows signal separation as exact as the accuracy of the machine arithmetic, with a few less accurate samples at the end of the signal sequence. This less accurate ending may be treated as the precedure expense. Since the method of chaotic signal separation proved to be functional in the absence of noise, we concentrated our further efforts on the investigation of the method resistance with respect to the channel noise. Gaussian, normally distributed noise (k) with variance was added in the channel to the transmitters' signals u(k) =

x1(k) + x2(k) + (k). The calculated signal recovery error x1,2(k) ­ ~ 1,2(k) was treated as a residual noise in the x received signal. The noise levels (signal-to-noise ratio, SNRS) of the separated signals were calculated as functions of the noise level SNRC in the channel signal u(k), SNRC = <(x1 + x2)2>/2 (all signals were normalized to have zero mean values). Both were calculated in dB. As a criterion of the efficiency of signal separation K, dB, we used the difference between the noise levels in the separated signals and in the signal u(k) K = SNRS ­ SNRC. (11) The signal separation is effective when the noise level in the separated signal is lower than the channel noise, i.e., K > 0, and ineffective if the noise level in the signal is much higher than that in the channel (K << 0). The calculation results are presented in Fig. 3.

(a)

(b) Fig. 3. (a) Signal-to-noise ratio for the separated signals, SNRS, and (b) relative separation time as functions of noise in the channel, SNRC. Curves are shown for (1) method [9], (2) single-branch algorithm, and (3) algorithm with 16 branches. The results were obtained with 10,000-sample chaotic sequences.

Curve for the in the higher

1, given for comparison, corresponds to the results scheme [9]. As can be seen from Fig. 3a, the noise signals separated by the method [9] is always than the channel noise and the criterion K > 0 is


never fulfilled. Our results are represented by curve 2, which shows that effective separation is observed above the SNRC level of 65 dB. Note that to the right of this point the level of noise in the separated signals rapidly decreases according to relations (9), and its value is determined only by the number of backward iteration steps and the machine calculation accuracy. This means that the signals are not only separated but also cleaned off noise. In the process of separation, sporadic faults can occur (Fig. 4). Even a single and very short burst can seriously spoil the SNRS value. Therefore, we introduced another efficiency criterion, the relative time of effective signal separation (Fig. 3b), here the signals are considered separated if the local signal estimation error is < 0.1, or ­ 20 dB. Evidently, separation is effective if is close to one. As can be seen from Fig. 3b, the corresponding values of both methods are close to those of Fig. 3a.

Fig. 4. Signal separation faults with the single-branch algorithm. = x1­ ~ 1; noise level is approx. 40 dB; l is x discrete time.

Another criterion of the method efficiency may be the value of noise added to the channel signal (SNRC) at which the separation method provides some prescribed value of the recovered signals SNR, e.g., 40 dB. Indeed, 40 dB is quite a good accuracy of the signal recovery (rms signal error of the order of 0.01). The above method gives 40 dB SNRS at SNRC = 60 dB, while the method of [9] at SNRC = 110­120 dB. The results in Figs. 4a and 4b indicate that effective separation by the discussed method is possible at SNRC > 65 dB. Simulation of the separation procedure shows that with increasing external noise the rate of the faults also increases, which gradually ruins the method efficiency. Analysis of the signal waveforms recovered with this method shows that strong channel noise (k) at a particular moment can considerably shift the actual sum of the transmitters' signals u(k) = x1(k) + x2(k) + (k), and that the faults occur due to a wrong choice of the inverse map branches at that step. This wrong choice is then followed by convergence of the receivers trajectories from wrong points to the transmitters signals, which can take a number of steps. These irregular bursts of estimation error of the drive and response systems are the only reason for the residual noise SNRS. Obviously, the faults occur because the decision on what

branch to take is made locally, in one point of time domain, and the preceding and the following histories are not taken into account. This short analysis gives rise to an idea to trace a few branches simultaneously besides the "optimal" one and to choose among them by means of minimizing the estimation error signal averaged over a certain time interval. In the new algorithm, inverse maps (6) are iterated, and on each step each branch of the sum signal gives four, on the next step each of them again gives four, etc. The tree of branches grows too fast, so, on each step we keep trace of no more than M branches, optimal in a certain sense. This is done here as follows. Let at kth moment already be M pairs of estimates ( ~ 1j(k), ~ 2j(k)), j, = 1, ..., M, x x corresponding to M branches of the sum signal. On the next step the number of possible branches is quadrupled: ( ~ 1ji (k­1), ~ 2jq(k­1)), i, q = 1, 2, and we have to select x x M "best" branches among 4M that correspond to 4M pairs of the sum signal estimates. We use a criterion of the minimum of deviation of sums ~ 1ji (k­1) + ~ 2jq(k­ x x 1), i, q = 1, 2, from the sum signal u(k­1) at the receiver input. Then the procedure is repeated for k­2, k­3, etc. However, this evident approach with the choice of a group of optimal pairs does not essentially improve separation. The reason is as follows. In the above algorithm with the single branch, in the case of a relatively low level of the channel noise the trajectories converge to the true solution (i.e., to the transmitters' signals) from any initial conditions. Imagine now that several branches are kept after each iteration. If no special efforts are made, amongst these branches there may appear "clusters" (bundles, bunches) of very close branches. With further iteration and selection, the branches from the same cluster get even closer to each other while the corresponding estimates of the trajectories converge to the same solution. If the external noise leads to a fault in the choice of the proper branch, it happens simultaneously to all branches from the cluster. So, it's useless to keep trace of more than one branch from the cluster. Thus, we conclude with the following algorithm. Let at kth moment there be M pairs of estimates ( ~ 1j(k), x ~ j(k)), j, = 1, ..., M, which correspond to M branches of x2 the calculated sum signal. We iterate maps (6) once, using these estimates as M sets of initial conditions. As a result, at (k­1)th moment we obtain 4M branches of preimages. Then we look for clusters of close branches. Suppose we have N clusters (Fig. 5). To choose M best branches, we obey the following rules. 1. Take one best branch from each cluster (below we discuss what means the "best" here), and get N really different branches. 2. If N > M, then take only M best branches according to criterion (7). Otherwise, keep all N branches. The operation is repeated at (k­2)th, (k­3)th step, etc.


Thus, moving from the final element of the u(k) sequence that came to the receiver input to its beginning, we obtain M variants of the pairs of sequences ( ~ 1j(i), ~ 2j(i)), j, = x x 1, ..., M; i = l, ..., k. The pair minimizing the functional G on the operation time interval (l, k) G=

Acknowledgements
The work was supported in part by the Russian Foundation for Basic Investigations (Grants No. 97-01-00800 and No. 99-02-18315).

(u
k i =l

(i ) - ~1j (i ) - ~2j (i ) x x

)

2

(12)

References
[1] H. Fujisaka, T. Yamada, Progr. Theor. Phys. 69 (1983) 32. [2] V.S. Afraimovich, N.N. Verichev, M.I. Rabinovich, Izv. VUZov. Radiofizika. 29 (1986) 1050. [3] L.M. Pecora, T.L. Caroll, Phys. Rev. Lett. 64 (1990) 821. [4] L.Kocarev, K.S.Halle, K.Eckert, L.Chua, Int. Journ. Bifurcation and Chaos. 2 (1992) 709. [5] K.Cuomo, A.Oppenheim, Phys. Rev. Lett. 71 (1993) 65. [6] Yu.L.Belsky, A.S.Dmitriev, Radiotekhnika i Electronika. 38 (1993) 1310. [7] A.R.Volhovsky, N.V.Rulkov, Pis'ma v GTF. 19 (1993) 71. [8] H.Dedieu, M.Kennedy, M.Hasler, IEEE Circuits and Systems. CAS-40 (1993) 634. [9] L.S. Tsimring, M.M. Sushchik, Phys. Lett. A. 213 (1996) 155. [10] S.Haykin, Communication Systems. (Wiley, New York, 1994).

is considered the pair of separated signals.

Fig. 5. Branch clusters at a certain time moment. Clusters are outlined by circles, dots in the circles designate pairs of estimates ( ~ 1j(l), ~ 2j(l)). x x

To take the best branch at lth iteration step from the cluster ( ~ 1j(k­l), ~ 2j(k­l)), for each branch we calculate x x rms deviations of the sum signal estimates from a fragment of the received sequence on a certain comparison time interval (k­l, k­l+T). The branch with the minimum deviation is considered the best. The results of separation chaotic signals with this algorithm are presented in Figs. 4a and 4b (curve 3). Sixteen branches were traced (M = 16) and the best-in-cluster branch was taken from a comparison over T = 50 time interval. The results indicate that the algorithm separates chaotic signals at the noise level of about 25 dB, which is 35­40 dB better than the algorithm with the single branch. Thus, the methods for separating chaotic signals from their sum proposed in this paper can operate not only in the absence but also in the presence of noise. The method for separation using a single branch allows us to separated chaotic signals at SNRC > 60­65 dB, and the algorithm with several traced branches gives efficient separation of logistic map signals at SNRC as low as 25 dB. The presented results give hope for successful physical experiments on signal separation based on inherent dynamic properties of chaotic systems.