Applying Chaos Theory to Embedded Applications - Embedded.com

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 xn and parameter k.

The difference equation in (1) uses history terms xn ,where xn is the currently computed sequence value, xn-i is the history of sequence values for historical index i, and ki is the coefficient for each history sample (which is related to the gain of theoscillator ) with xn-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 ki based on the expansion formulaof (1) as shown below  in (2) :

Where Ki is the coefficient matrix and Xn 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.

Xh is the history matrix which are history values in thesequence raised to the power p ,where the history values are the terms xp n-i shown in (1) . Ki isthen found as the product of the current value matrix Xn andthe history matrix Xh .

Simulating the Expansion Formula in Software
The following BASIC code simulates theexpansion formula for two initial conditions. Each initial conditionsis represented by x[n] and x[n-1] and the output of the sequencegenerator is printed to a file.

More initial conditions can be added (which improves the accuracy ofapproximating the sequence) by following the example of the codefor x[n-2], x[n-3], etc. and by taking the terms to the power whichcorresponds to the number of initial conditions. The limit of thisexpansion is the floating-point capability of the processor.

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 = 2
Rem For these parameters, chaotic behavior occurs when
Rem x1 > -.263 and x1 <.263 (assuming x1 = x2)
Rem x1 and x2 are initial conditions, param1 and param2 arecharacteristic
Rem 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 13
12 param1 = 3
13 param2 = 2
15 INPUT “INPUT INITIAL X1 VALUE “; x1
16 INPUT “INPUT INITIAL X2 VALUE “; x2
20 INPUT “INPUT OUT FILE NAME “; FILE$
Rem Line 20 asks for the output file to write data to
Rem the output file is data sequentially calculated on line 70
Rem and is basically time-domain output
50 OPEN “O”, #1, FILE$
52 For A = 2.8 To 4! Step 0.025
60 For I = 1 To 1000
65 Rem characteristic equation below
70 x = param1 * A * X1 * X1 – param2 * A * X2 * X2
71 X2 = X1: X1 = x
Rem Line 71 says – update x1 and x2. x2 is the oldest value so it gets
Rem transfered from x1 first. Then x1 gets updated from the new x value
Rem The differential equation starts with Vc1 and Vc2 and all of its
Rem derivatives. The difference equation takes this and converts the
Rem derivatives to Vo(k-n) where n is the nth derivative of Vc. This
Rem is because the time rate of change of function (derivative) can
Rem be expressed as [Vo(k) – Vo(k-1)]/T, where T is taken to be 1 time
Rem unit, or T = 1 for the first derivative.
Rem 72 IF I > 80 THEN 80 ELSE 90

80 Print #1, A, x
85 N = N + 1
90 Next I
95 Next A
100 Close #1
105 Print N

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

Where Ki is the coefficientmatrix andXn 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.

Xh is the history matrixwhich arehistory values in the sequence raised to the power p, where the historyvalues are the terms xp n-i shown in Equation (1)above. Ki is thenfound as the product of the current value matrix Xn and thehistorymatrix Xh .

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 x0 = 0.7.Toapproximate this sequence with these conditions we use the first fivepoints of the sequence, {x0 …x5 } 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 x0 = 0.7 is as follows:

By incorporating the ki constants aboveinto (1) and using the same initial condition x0 = 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 n”);

   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

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.