Chaotic data sequences are found in nature in everything from turbulence in the weather to tumor growth in biological systems. Chaotic sequences are the result of non-linear differential equations that govern physical systems, which for years have eluded closed form solution and therefore a coherent, mathematical explanation.

Most advances in chaos theory have resulted with the advent of the computer from the mid-20th century forward because the solutions to these non-linear equations have been found in individual cases with computer simulation of the difference equations that approximate them.

The use of these difference equations that approximate chaotic solutions has also found use in the world of encryption, compression and wireless transmission. In these areas it is found that understanding the theory behind non-linear equations may not be as essential as in using its obscure nature to compress or hide data more efficiently.

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

Based on these applications, there has been a necessity to develop a deterministic, chaotic expansion algorithm that approximates these non-linear differential equations, which may also lead to the development 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 the expansion formula are matched to the sequence through linear determination.

The initial conditions of the sequence are used in the linear determination of the coefficients in the formula that are then used to fit the sequence. This method has uses in compression of data sequences, for instance, where the few values of the initial conditions and prameters of the equation are the only data required to reproduce the original sequence.

The Expansion Formula
A standard Wein-Bridge oscillator circuit was modified so that the frequency of the oscillator is a function of the output voltage (which is changing with time) raised to the second power. This is accomplished by the use of a MOSFET in parallel with one of the Wein-bridge feedback resistors.

The differential equations that govern the chaotic oscillator circuit were reduced to difference equations (see reference [3]) and then analyzed for chaotic behavior. The result is the difference equation in (1) which has been expanded by following the form of the original difference equation of two variables (one for each of the capacitors in the circuit, and raising additional terms p to the power p, where p is the number of initial conditions which correspond to additional capacitors in the oscillator circuit. Analyzing the results of Equation (1) below in software shows bifurcations approaching an attractor based on 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 the oscillator) with x_n-i raised to the 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 number of terms in the expansion. The accuracy of the approximation is based on p, which determines both the number of terms in the expansion and the power of each term.

The requirements for approximating a sequence is to linearly determine the coefficients k_i based on the expansion formula of (1) as shown below  in (2):

Where K_i is the coefficient matrix and X_n is the current value matrix that consists of a selection of values in the sequence which should include the initial conditions of the sequence based on the sensitivity of the system to initial conditions.

X_h is the history matrix which are history values in the sequence raised to the power p, where the history values are the terms x^p_n-i shown in (1). K_i is then found as the product of the current value matrix X_n and the history matrix X_h.

{pagebreak}Simulating the Expansion Formula in Software
The following BASIC code simulates the expansion formula for two initial conditions. Each initial conditions is represented by x[n] and x[n-1] and the output of the sequence generator is printed to a file.

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

Rem Simulation of Chaotic Expansion Formula with two initial conditions (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 are characteristic
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

{pagebreak}

Approximating other chaotic sequences
The requirements for approximating a sequence is to linearly determine the coefficients ki based on the expansion formula of (1):

Where K_i is the coefficient matrix and X_n is the current value matrix that consists of a selection of values in the sequence which should include the initial conditions of the sequence based on the sensitivity of the system to initial conditions.

X_h is the history matrix which are history values in the sequence raised to the power p, where the history values are the terms x^p_n-i shown in Equation (1) above. K_i is then found as the product of the current value matrix X_n and the history matrix X_h.

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

We will refer to Equation (3) above as the target function and we note that it approaches a chaotic attractor at a = 3.8 with a corresponding initial condition x₀ = 0.7. To approximate this sequence with these conditions we use the first five points of the sequence, {x₀...x₅} which includes the initial condition, in the solution of (2).

We also use values throughout the sequence for the solution of (2) that would indicate changes or bifurcation on a phase diagram so that these are reflected in the expansion formula. The mathematical solution of (2) for expansion constants ki as it applies to the simple first-order equation of (3) with x₀ = 0.7 is as follows:

By incorporating the ki constants above into (1) and using the same initial condition x₀ = 0.7, we find the mean-squared error by taking the square of the difference of the approximation expansion of (1) from the target function of (3) over 5000 sequence points starting with the initial condition.

The MSE is found to be 0.14, and the standard deviation of the error terms found by taking the absolute value of the difference between the approximation (1) and target function (3) is 0.486 over 5000 sequence points.

From this standard deviation of the error terms it is found that 82.6% of the error terms are less within one standard deviation of the mean of the target function. By randomly changing constants in (4), the MSE is found to increase into single or double digits greater than 1 and with a confidence interval from the standard deviation of error terms that is less than that for a normal distribution.

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

Of course the compression is lossy (MSE is 0.14 from above), so the benefits of loss versus compression ratio have to be weighed. Below is an example C program that compresses a file 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 conditions for
// a three-variable expansion. This is all that is requried to compress a file
// so these values are written out as the compressed file after they are
determined

    main(argc,argv)
    int argc;
    char *argv[];
{
    float outbuff[BINS];     // this is the write buffer that is written to the compressed file
    float x[BINS];             // this is the input buffer from the source file
    float k1,k2,k3;           //k1-k3 are the constants to be determined from source file values
    float det; // the determinant for the 3x3 array allows solution of k1-k3
    float xm1_3, xm2_3, xm3_3; //initial conditions all raised to the 3rd power
    int i,j,k,filesize; // count variables and filesize
    FILE *f1,*f2; // f1 is the source file, f2 is the compressed output file
    char ch;

    printf("ChaoCompress \n");
    printf("Usage: compress

\n");

    printf(" \n\n");

    if(NULL==(f1=fopen(argv[1],"r")))
        {
        fprintf(stderr,"Can't open infile \n");
        fclose(f1);
}

i = 0;
j = 0;
det = 0;
filesize = 0;

// initialize variables then read in values 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 is built 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 conditions x(-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); //write total 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 conditions x(-1),x(-2),x(-3)
fprintf(f2,"%f",xm2_3);
fprintf(f2,"%f",xm3_3);
fclose(f2);

}

{pagebreak}Using the encryption formula in encryption
An example of the expansion formula in encryption is found in the Chaocrypt program (Figure 1 below), which uses the private encryption keys provided by the user as the initial conditions for generating a sequence from the formula in (1).

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

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

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

Michael Harney is an Electrical Engineer working in industrial and vehicle electronics. He is the holder of  four patents and has a Bachelor of Science in Electrical Engineering from Utah State University

References:
[1] Carroll, T.L., Phys. Rev. E 59, 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 for CDMA