# Applying Chaos Theory to Embedded Applications

Chaotic data sequences are found in nature in everything fromturbulence in the weather to tumor growth in biological systems. Chaoticsequences are the result ofnon-linear differentialequations that govern physical systems, whichfor years have eluded closed form solution and therefore a coherent,mathematical explanation.

Most advances in chaos theory haveresulted with the advent of the computer from the mid-20th centuryforward because the solutions to these non-linear equations have beenfound in individual cases with computer simulation of the differenceequations that approximate them.

The use of these difference equations that approximate chaoticsolutions has also found use in the world of encryption, compressionand wireless transmission. In these areas it is found thatunderstanding the theory behind non-linear equations may not be asessential as in using its obscure nature to compress or hide data moreefficiently.

Because non-linear differential equations are so sensitive toinitial conditions, these initial conditions are often used as the keysto encryption, the codebook for compression or the type of whiteningsequence that is generated for spread spectrum[4] .

Based on these applications, there has been a necessity to develop adeterministic, chaotic expansion algorithm that approximates thesenon-linear differential equations, which may also lead to thedevelopment of the characteristic equation that underlies the data [1] .

In this article a unique chaotic expansion formula that isÂ presented that approximates, where the coefficients of theexpansion formula are matched to the sequence through lineardetermination.

The initial conditions of the sequence are used in the lineardetermination of the coefficients in the formula that are then used tofit the sequence. This method has uses in compression of datasequences, for instance, where the few values of the initial conditionsand prameters of the equation are the only data required to reproducethe original sequence.

**The Expansion Formula**

A standard Wein-Bridge oscillator circuit was modified so that thefrequency of the oscillator is a function of the output voltage (whichis changing with time) raised to the second power. This is accomplishedby the use of a MOSFET in parallel with one of the Wein-bridge feedbackresistors.

The differential equations that govern the chaoticoscillator circuit were reduced to difference equations (see reference [3] ) and thenanalyzed for chaotic behavior. The result is the difference equation in(1) which has been expanded by following the form of the originaldifference equation of two variables (one for each of the capacitors inthe circuit, and raising additional terms p to the power p , where p isthe number of initial conditions which correspond to additionalcapacitors in the oscillator circuit. Analyzing the results of Equation(1) below in software shows bifurcations approaching an attractor basedon the initial conditions x_{n} and parameter k.

The difference equation in (1) uses history terms x_{n} ,where x_{n} is the currently computed sequence value, x_{n-i} is the history of sequence values for historical index i, and k_{i} is the coefficient for each history sample (which is related to the gain of theoscillator ) with x_{n-i} raised tothe power p .

The general form of (1) above is then a finite expansion of power sequences where the power p of each term is the same numberof terms in the expansion. The accuracy of the approximation is basedon p ,which determines both the number of terms in the expansion andthe power of each term.

The requirements for approximating a sequence is to linearlydetermine the coefficients k_{i} based on the expansion formulaof (1) as shown belowÂ in (2) :

Where K_{i} is the coefficient matrix and X_{n} isthe current value matrix that consists of a selection of values in thesequence which should include the initial conditions of the sequencebased on the sensitivity of the system to initial conditions.

X_{h } is the history matrix which are history values in thesequence raised to the power p ,where the history values are the terms x^{p} _{n-i} shown in (1) . K_{i} isthen found as the product of the current value matrix X_{n} andthe history matrix X_{h} .

**Simulating the Expansion Formula in Software **

The following

More initial conditions can be added (

**Rem Simulation of Chaotic ExpansionFormula with two initialconditions (x1, x2). Rem x1 = x[n], x2= x[n-1] .When x1=x2 the unstable region is x1 <-.263 and x1 >.263 if Rem param1 = 3 and param2 = 2Rem For these parameters, chaotic behavior occurs whenRem x1 > -.263 and x1 <.263 (assuming x1 = x2) Rem x1 and x2 are initial conditions, param1 and param2 arecharacteristicRem values of the equation (see line70) Rem stability points are proportional to (1/param1 || 1/param2) Rem If param1 = param2, stability points = 1/(2*param1) Rem current paramters on line 12 and 1312 param1 = 313 param2 = 215 INPUT “INPUT INITIAL X1 VALUE “; x116 INPUT “INPUT INITIAL X2 VALUE “; x220 INPUT “INPUT OUT FILE NAME “; FILE$Rem Line 20 asks for the output file to write data toRem the output file is data sequentially calculated on line 70Rem and is basically time-domain output50 OPEN “O”, #1, FILE$52 For A = 2.8 To 4! Step 0.02560 For I = 1 To 100065 Rem characteristic equation below70 x = param1 * A * X1 * X1 – param2 * A * X2 * X271 X2 = X1: X1 = xRem Line 71 says – update x1 and x2. x2 is the oldest value so it getsRem transfered from x1 first. Then x1 gets updated from the new x valueRem The differential equation starts with Vc1 and Vc2 and all of itsRem derivatives. The difference equation takes this and converts theRem derivatives to Vo(k-n) where n is the nth derivative of Vc. ThisRem is because the time rate of change of function (derivative) canRem be expressed as [Vo(k) – Vo(k-1)]/T, where T is taken to be 1 timeRem unit, or T = 1 for the first derivative. Rem 72 IF I > 80 THEN 80 ELSE 90**

**80 Print #1, A, x85 N = N + 190 Next I95 Next A100 Close #1105 Print N**

Approximating other chaoticsequences

The requirements for approximating asequence is to linearly determine the coefficients ki based on theexpansion formula of (1):

Where K_{i} is the coefficientmatrix andX_{n} is the current value matrix that consists of a selectionof valuesin the sequence which should include the initial conditions of thesequence based on the sensitivity of the system to initial conditions.

X_{h} is the history matrixwhich arehistory values in the sequence raised to the power p, where the historyvalues are the terms x^{p} _{n-i} shown in Equation (1)above. K_{i } is thenfound as the product of the current value matrix X_{n} and thehistorymatrix X_{h} .

We consider an example of approximatinga simple, first-order sequence of population dynamics [2]:

We will refer to Equation (3) above asthe target function and we note that it approaches a chaotic attractorat a = 3.8 with a corresponding initial condition x_{0} = 0.7.Toapproximate this sequence with these conditions we use the first fivepoints of the sequence, {x_{0} …x_{5} } which includesthe initial condition,in the solution of (2).

We also use values throughout thesequence for the solution of (2) that would indicate changes orbifurcation on a phase diagram so that these are reflected in theexpansion formula. The mathematical solution of (2) for expansionconstants ki as it applies to the simple first-order equation of (3)with x_{0 } = 0.7 is as follows:

By incorporating the ki constants aboveinto (1) and using the same initial condition x_{0} = 0.7, wefind themean-squared error by taking the square of the difference of theapproximation expansion of (1) from the target function of (3) over5000 sequence points starting with the initial condition.

The MSE is found to be 0.14, and thestandard deviation of the error terms found by taking the absolutevalue of the difference between the approximation (1) and targetfunction (3) is 0.486 over 5000 sequence points.

From this standard deviation of theerror terms it is found that 82.6% of the error terms are less withinone standard deviation of the mean of the target function. By randomlychanging constants in (4), the MSE is found to increase into single ordouble digits greater than 1 and with a confidence interval from thestandard deviation of error terms that is less than that for a normaldistribution.

If we were attempting to store thesequence generated by (3) in a smaller data set (basically compressingit), we would only have to store the four initial conditions of (4) andthe constants of the equation (1) to recreate the sequence. Thecompression ratio in this example would be 5000 sequence points / 4initial conditions = 1250.

Of course the compression is lossy (MSEis 0.14 from above), so the benefits of loss versus compression ratiohave to be weighed. Below is an example C program that compresses afile by finding the constants (k1, k2, k3) and initial conditions(m1_3, m2_3, m3_3) of the expansion formula for p = 3.

#include

#include

#define BINS 5

// This program is for determining the constants and initial conditionsfor

// a three-variable expansion. This is all that is requried to compressa file

// so these values are written out as the compressed file after theyare

determined

Â Â Â main(argc,argv)

Â Â Â int argc;

Â Â Â char *argv[];

{

Â Â Â float outbuff[BINS]; Â Â Â // this isthe write buffer that is written to thecompressed file

Â Â Â float x[BINS]; Â Â Â Â Â Â Â Â Â // this is the input buffer from the source file

Â Â Â float k1,k2,k3; Â Â Â Â Â Â Â Â //k1-k3 are the constants to bedetermined from sourcefile values

Â Â Â float det; // the determinant for the 3×3 arrayallows solution ofk1-k3

Â Â Â float xm1_3, xm2_3, xm3_3; //initial conditions allraised to the3rd power

Â Â Â int i,j,k,filesize; // count variables and filesize

Â Â Â FILE *f1,*f2; // f1 is the source file, f2 is thecompressed output file

Â Â Â char ch;

Â Â Â printf(“ChaoCompress n”);

Â Â Â printf(“Usage: compress

Â Â Â printf(” nn”);

Â Â Â if(NULL==(f1=fopen(argv[1],”r”)))

Â Â Â Â Â Â {

Â Â Â Â Â Â fprintf(stderr,”Can't open infilen”);

Â Â Â Â Â Â fclose(f1);

}

i = 0;

j = 0;

det = 0;

filesize = 0;

// initializevariables then read invalues from source file

while(i <= BINS) {

Â Â Â Â Â Â fscanf(f1,”%f”,&x[i]);

Â Â Â Â Â Â i++;

}

// Get file count

while ((ch=getchar())!= EOF)

Â Â Â Â Â Â j++;

Â Â Â fclose(f1);

Â Â Â filesize = BINS*sizeof(float) + j;

Â Â Â // find determinant from source file values

Â Â Â // then solve for k1 – k3, adjoint of matrix isbuilt into this formula

Â Â Â det = pow(x[2],3)*( pow(x[2],6) -pow((x[3]*x[1]),3) )

Â Â Â + pow(x[1],3)*( pow((x[1]*x[4]),3) -pow((x[2]*x[3]),3) )

Â Â Â – pow(x[0],3)*( pow((x[2]*x[4]),3) – pow(x[3],6) );

Â Â Â k1=(x[3]*(pow(x[2],6)-pow((x[1]*x[3]),3) )

Â Â Â – x[4]*(pow((x[1]*x[2]),3) – pow((x[0]*x[3]),3) )

Â Â Â + x[5]*(pow(x[1],6) – pow((x[0]*x[2]),3) )) / det;

Â Â Â k2= (x[3]*(pow((x[1]*x[4]),3) -pow((x[3]*x[2]),3) )

Â Â Â Â Â Â Â Â Â +x[4]*(pow((x[0]*x[4]),3) – pow(x[2],6) )

Â Â Â Â Â Â Â Â -x[5]*(pow((x[2]*x[1]),3) – pow((x[0]*x[3]),3))) / det;

k3 =(x[3]*(pow((x[2]*x[4]),3) -pow(x[3],6) )

Â Â Â Â Â Â + x[4]*(pow((x[2]*x[3]),3) -pow((x[1]*x[4]),3) )

Â Â Â Â Â Â + x[5]*(pow((x[1]*x[3]),3) -pow(x[2],6) )) / det;

Â Â Â //calculate initial conditionsx(-1),x(-2), and x(-3) after finding k1-k3

Â Â Â xm1_3 = -(x[2] – k3*pow(x[1],3) +k2*pow(x[0],3) ) / k1;

Â Â Â xm2_3 = -(x[1] – k3*pow(x[0],3) +k2*xm1_3 ) / k1;

Â Â Â xm3_3 = -(x[0] – k3*xm1_3 + k2*xm2_3 )/ k1;

if(NULL==(f2=fopen(argv[2],”w”)))

Â Â Â {

fprintf(stderr,”Can't open outfile n”);

fclose(f2);

}

fprintf(f2,”%d”,filesize); //writetotal filesize first

fprintf(f2,”%f”,k1); Â Â Â // write constants k1-k3

fprintf(f2,”%f”,k2);

fprintf(f2,”%f”,k3);

fprintf(f2,”%f”,xm1_3); Â Â Â //write initial conditionsx(-1),x(-2),x(-3)

fprintf(f2,”%f”,xm2_3);

fprintf(f2,”%f”,xm3_3);

fclose(f2);

}

**Using the encryption formula in encryption**

An example of the expansion formula in encryption is found in the Chaocryptprogram (**Figure 1 below** ), which uses the privateencryption keys provided by the user as the initial conditions forgenerating a sequence from the formula in (1) .

This sequence is then XORed with the input data to produce theencrypted data. The use of the same keys in the decryption routineproduces a sequence which when XORed with the encrypted data producesthe original, unencrypted data.

This technique of encryption has been shown to be useful as thesequence is hard to predict (even ifthe formula in (1) is known ),without knowing the keys that were used to create the initialconditions.

In conclusion, chaos theory is becoming more useful in encryption (where the chaotic sequence is used tosecure data ), in data compression (where the chaotic sequence is curve-fittedto the data and the initial conditions that generate the sequence areused as compression values ) and in wireless transmission (where the chaotic sequence is used tocreate a whiter sequence for Direct Sequence Spead Spectrum).

MichaelHarney is an Electrical Engineer working in industrial and vehicleelectronics. He is the holder ofÂ four patents and has a Bachelorof Science in Electrical Engineering from Utah State University

**References: **

[1] Carroll, T.L., Phys. Rev. E59, 1615″1621, 1999.

[2] Lawrance, A.J.,Balakrishna, N. J. Royal Stat Soc Vol. 63, No. 4,2001, pp. 843-853

[3] Harney, M. URL: http://www.signaldisplay.com/chaos.zip

[4] Umeno,Ken; Kitayama,Ken-ichi, Improvement of SNR with Chaotic Spreading Sequences forCDMA