
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00002588/00001
Material Information
 Title:
 Spectrum spreading codes from the logistic difference equation
 Creator:
 Reed, Dana Ann
 Publication Date:
 1989
 Language:
 English
 Physical Description:
 103 leaves : ; 29 cm
Subjects
 Subjects / Keywords:
 Computer simulation ( lcsh )
Telecommunication systems ( lcsh ) Computer simulation ( fast ) Telecommunication systems ( fast )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Bibliography:
 Includes bibliographical references (leaves 6667).
 General Note:
 Submitted in partial fulfillment of the requirements for the degree, Master of Science, Department of Electrical Engineering, Department of Computer Science and Engineering.
 Statement of Responsibility:
 Dana Ann Reed.
Record Information
 Source Institution:
 University of Colorado Denver
 Holding Location:
 Auraria Library
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 21104516 ( OCLC )
ocm21104516
 Classification:
 LD1190.E54 1989m .R43 ( lcc )

Full Text 
SPECTRUM SPREADING CODES FROM THE
LOGISTIC DIFFERENCE EQUATION
by
Dana Ann Reed
B.S., University of Colorado at Denver, 1986
' A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Department of
Electrical Engineering and Computer Science
1989
This thesis for the Master of Science degree by
Dana Ann Reed
has been approved for the
Department of Electrical Engineering and Computer Science
by
ACKNOWLEDGMENTS
While there are many people who have helped me during the course of
this research effort, I would like to give special thanks to John Clark for introducing
me to chaos theory and for lending technical assistance to this project I would also
like to thank my husband, Bill Rathfon, for his motivation, encouragement, and
technical support during this endeavor.
iv
Reed, Dana Ann (M.S., Electrical Engineering)
Spectrum Spreading Codes from the Logistic Difference Equation
Thesis directed by Professor John R. Clark
This paper details an investigation into the feasibility of using the chaotic
regions of the one dimensional logistic map to generate binary sequences for the
purpose of spectrum spreading for communication systems. Computer simulations
were used to generate and analyze these sequences (as well as other spectrum
spreading sequences) for their functionality as spectrum spreading codes.
The logistic difference equation has several parameters associated with it
that were varied to determine the effects upon the binary sequences generated.
Results obtained showed that binary sequences with useful statistical properties are
generated using the logistic equation when certain constraints are placed upon the
equation parameter variations. The sequences produced by this method appear to be
as useful as the linear recursive sequences which are already widely used.
Therefore, further investigation of these logistic sequences is warranted. The results
of this analysis and implications for practical use are presented herein.
The form and content of this abstract are approved. I recommend its publication.
Signed
'acuity member in charge of thesis
CONTENTS
CHAPTER
1. INTRODUCTION................................................. 1
2. DESIRABLE PROPERTIES ASSOCIATED WITH
BINARY SEQUENCES........................................... 5
2.1 Statistical Properties of Random Sequences.............. 5
2.1.1 Statistical Properties of Linear Recursive Sequences.. 7
2.2 Other Desirable Properties............................. 11
3. INTRODUCTION TO THE ONE DIMENSIONAL
LOGISTIC
MAP........................................................ 14
3.1 Historical Background.................................. 15
3.2 Software for Generating Plots of the Logistic Equation. 16
3.3 Behavior of the Logistic Map........................... 17
4. BINARY SEQUENCES GENERATED FROM THE
LOGISTIC DIFFERENCE EQUATION................................ 27
4.1 Starting Values........................................ 29
4.2 Thresholding......................................... 41
4.3 Variation of ji Parameter.............................. 45
4.4 Sequence Lengths....................................... 52
4.5 Comparison with other Pseudorandom Sequences........... 54
5. CONCLUSIONS AND ADDITIONAL RESEARCH IDEAS................... 61
5.1 Summary and Conclusions................................ 61
5.2 Avenues for Further Research........................... 63
VI
REFERENCES.................................................. 66
APPENDICES
A. CODE GENERATION AND ANALYSIS SOFTWARE............... 68
A.l Code Generation................................. 68
A.2 Analysis Subroutines............................ 70
A.3 Reporting Subroutines,.......................... 72
A.4 Long Logistic Code Generation................... 73
B. CODE GENERATION AND ANALYSIS PROGRAM................ 75
C. LONG SEQUENCE GENERATION PROGRAM..................... 97
D. LOGISTIC PROGRAM CODE................................ 102
vu
TABLES
TABLE
2.1 Code generated from feedback taps [5,2]............................. 9
2.2 Run distribution for sequence of table 2.1......................... 10
4.1 Iterates for starting values 0.4 and 0.6........................... 35
4.2 Iterates for starting values 0.45 and 0.55......................... 36
4.3 Code and statistical data for starting
value of 0.4555555555 .............................................. 38
4.4 Code and statistical data for starting
value of 0.4555555556............................................... 39
4.5 Single threshold sequences (Expected/Observed)..................... 42
4.6 Double threshold sequences (Expected/Observed)..................... 44
4.7 Sequences generated with variations of i parameter
500 Iterations...................................................... 50
4.8 Sequences generated with variations of p parameter
10000 Iterations.................................................... 51
4.9 (a) Sequences of varying lengths p=3.9991....................... 55
4.9 (b) Sequences of varying lengths i=3.9996....................... 56
4.9 (c) Sequences of varying lengths i=3.9999....................... 57
4.10 Comparison of LRS, random number generator
and logistic sequences.............................................. 59
vrn
FIGURES
FIGURE
2.1 Index of discrimination......................................... 7
2.2 Shift register generator with feedback taps [5,2].................. 8
2.3 Autocorrelation function of sequence in table 2.1............... 11
3.1 Logistic map with i between 0.0 and 4.0.......................... 18
3.2 Logistic map with i between 2.5 and 4.0.......................... 19
3.3 Logistic map period three window.................................. 20
3.4 Logistic map with x between 0.59 and 0.61,
i between 3.9994 and 3.9996....................................... 21
3.5 Logistic map.................................................... 23
3.6 Convergence constant............................................. 25
3.7 Scaling constant.................................................. 25
4.1 50 Iterations..................................................... 30
4.2 200 Iterations.................................................... 31
4.3 1000 Iterations................................................... 32
4.4 10000 Iterations.................................................. 33
4.5 Logistic plot with 3.999 < [i < 4.000
0.0
4.6 Autocorrelation function for sequence
generated using p.=3.9994........................................ 48
CHAPTER 1
INTRODUCTION
Spread spectrum communication systems use pseudo random binary
sequences to increase the overall signal bandwidth significantly beyond that which is
necessary to actually convey the information desired. Frequently, the pseudo
random binary sequences used for this purpose are called linear recursive sequences
(LRS). These binary codes are known by a variety of other names also such as
msequences, pn sequences, linear maximal sequences, etc. Linear recursive
sequences are usually generated using shift register generators with linear feedback
techniques. This type of sequence has many valuable statistical properties which
make the frequency spectrum of the sequence appear quite "noiselike", resulting in
direct sequence spread spectrum signals that are able to "hide" in the noise. These
statistical properties, then, are quite valuable in spread spectrum communication
systems. There are some drawbacks in using LRS codes for spectrum spreading
purposes, however. If a secure communication system is required, linear recursive
sequences should not be used because they are quite easily identified and duplicated.
In the same vein, the fact that there are a limited number of sequences of a given
length available for use also limits the security of such systems. A number of ploys
have been used to work around this security issue, truncation of extremely long
sequences, encryption of the information before spreading, etc. Unfortunately,
these "workarounds" just lead to increasingly complex systems. It would seem that
a simpler solution might be to find sequences with the same desirable statistical
properties and better security properties. A search for more secure sequences with
2
the same desirable statistical properties is the focus of this research effort
The question then becomes, how can pseudo random binary sequences
be generated with the same valuable statistical properties but with a much more
secure nature? It is quickly obvious that since LRS sequences are generated using
linear feedback techniques, the use of nonlinearities in the feedback loop should
serve to hamper the efforts of the eavesdropper in his quest to discover the makeup
of the spreading code. Research into this area has been somewhat limited with the
most extensive work being done by Solomon Golomb [3]. In theory, the simple
removal of the restriction that the feedback logic be linear leads to a dramatic increase
in the number of maximum length shift register sequences of a given number of
stages. In his book, Shift Register Sequences. Golomb points out that the number
of sequences available using linear feedback logic for a generator with n stages is:
H2" 1)
n
(where <> is an Euler number) which to a first approximation yields:
n
If the linear feedback restriction is removed, the number of maximal length
sequences available for a generator with n stages is:
To appreciate the difference between thesee two equations, as an example take a
generator with five stages. The largest number of maximal length sequences using
only linear feedback techniques is six, whereas the maximum number of sequences
available using some type of nonlinear feedback is an astonishing 2048. This huge
increase in the number of available sequences is surely justification for exploring
nonlinear feedback techniques. Unfortunately, very little is known about shift
register sequences using nonlinear feedbacks due to the complexity of the analysis
involved in studying the nonlinear feedback techniques. The study of nonlinear
3
feedbacks quickly becomes quite complex, and it is not even known what types of
feedbacks lead to maximal length sequences. Then, even when a maximal length
sequence is found, the statistical properties of the sequence, such as run length
distribution, are not necessarily very good. While these nonlinear feedback ideas
seem promising, much work remains to be done in this area. For this effort,
however, another method of acquiring the desired sequences was explored.
If nonlinear feedback techniques aren't used, what other means of
generating more secure codes are available for exploration? Quite recently, a new
science called Chaos has come into the scientific limelight [4]. Chaos is the study of
nonlinear dynamical systems whose steadystate behavior has random, noiselike
properties. It would seem then that a chaotic system might very well yield se
quences with the desired properties. The focus of this research effort has been to
use one of the simplest chaotic systems known, the logistic equation, to generate
binary sequences and study their statistical and other properties. The logistic
equation quite simply is:
X+1= VXnQ Xn)
If the tuning parameter, fi, is kept between 0 and 4, the values of xn stay between 0
and 1. To generate sequences from this equation, a threshold is set and binary
values are generated by assigning a value of 1 to Xq values above the threshold, and
a value of 0 to Xq values below the threshold. This effort explored what effects
varying the parameter p, the threshold value, the starting Xq value, etc. had on the
generated sequences. Many of the sequences developed using this equation were
found to have not only interesting statistical properties but other desirable attributes
as well.
This research effort and report have been organized in the following
manner. The second chapter discusses what statistical and other properties make a
sequence useful for communication purposes. It is necessary to understand what
statistical properties are desirable so as to have a measure against which to judge any
sequences generated using the logistic equation. Chapter 2 also discusses properties
other than statistical ones that are necessary for a useful system. In doing this
research, it was necessary to develop some software to generate and analyze binary
sequences. Chapter 3 is an introduction to chaos and the logistic equation, giving
some background information on this equation and describing what has been
discovered about the chaotic nature of this equation. Chapter 4 then describes how
this discrete logistic map was used to generate binary sequences and what effects
varying the different parameters of the equation had on the sequences generated.
Chapter 5 summarizes the conclusions reached by this effort, and describes some
avenues for further research that were discovered during this endeavor. There are
four appendices which contain the software code used and a description of the
algorithms contained in this code. Appendix A briefly describes the software
developed for use in this research effort, while Appendices B, C and D contain the
actual software code.
CHAPTER 2
DESIRABLE PROPERTIES ASSOCIATED
WITH BINARY SEQUENCES
Before a search for new binary sequences can be made, there must exist
a set of evaluation criteria with which these new sequences can be judged. These
criteria must ensure that any new sequence generated contains the critical properties
necessary to make it useful for spread spectrum communication purposes. There are
statistical properties associated with binary codes that cause the power spectrum of
the spread signal to appear very "noiselike". These statistical properties are very
desirable in the spreading code for a variety of reasons. By making the spectrum
appear "noiselike", the signal can be hidden in the thermal noise allowing the prob
ability of intercept of the signal to be lessened. In addition to certain statistical prop
erties, there are other properties that make one code more desirable than another.
Ease and simplicity of generation, security from eavesdropping, and good cross
correlation properties are also important factors for consideration in deciding which
codes are most useful. Because linear recursive sequences (also known as linear
maximal codes, pn codes, and msequences) are so widely used in spread spectrum
systems, the properties of these sequences will also be discussed in this chapter for
comparison with other sequences generated.
2.1 Statistical Properties of Random Sequences
No periodic finite sequence can ever be said to be truly random, con
sequently requirements for good statistical properties of binary sequences can be
6
drawn by defining certain properties as being associated with randomness and
accepting any sequence which has these properties as a pseudo random sequence.
One way to decide what statistical properties of a binary sequence are associated
with randomness is to look at a familiar experiment with known random properties.
Tossing a twosided fair coin results in a truly random binary sequence if the coin
tossing goes on for an infinite period of time. One observation which can be made
from this hypothetical experiment is that as the number of trials is increased, the
number of heads and tails obtained are almost equal. If the experiment continued
indefinitely, we would expect the ratio of the number of heads to the number of tails
to approach a value of one. Therefore, one property associated with randomness is
that each state of the binary sequence should have an almost equal number of
occurrences. A second observation that can be made is that runs of heads (more
than one head occurring in consecutive tosses of the coin) and runs of tails will
occur with certain predictable frequencies. More specifically, short runs are more
frequent than long runs. About half of the runs will have a length of one, one
quarter of the runs will have a length of two, one eighth of the runs will have a
length of three and so on. Furthermore, the number of runs of heads of a given
length will approximately equal the number of runs of tails of the same length. One
final property associated with randomness (not necessarily gleaned from the coin
tossing experiment) is a sharply peaked autocorrelation function. The auto
correlation function, C(x), for a periodic sequence is defined as follows. If a
sequence is defined thus:
Sequence = a0, al5 a2.....ap
then the autocorrelation of this sequence can be defined by:
In a random sequence, the autocorrelation function will have a sharp peak when x is
p
7
zero, but will have fairly small values for any other value of x. A measure of how
sharply peaked the autocorrelation function of a particular sequence is can be
defined by a variable called the "index of discrimination" or ID [1]. The larger the
ID of a sequence, the more sharply peaked the autocorrelation function is. The
index of discrimination is defined as the difference between the correlation peak
when x = 0, and the largest minor correlation peak when x 0. (See Figure 2.1)
These three properties, therefore, will be used to judge the "randomness" of binary
sequences developed during the course of this research effort
2.1.1 Statistical Properties of Linear Recursive Sequences
Because linear recursive sequences have excellent "randomness"
properties, it is desirable to look at the randomness properties defined above using
these particular sequences.
A linear recursive sequence is generated using a feedback shift register
as shown in Figure 2.2. Certain feedback tap combinations yield sequences of
maximal length (using all possible states except for the all zeroes state) with very
distinct statistical properties. (A good reference for more information on LRS
sequences and choosing feedback taps is Dixon's book, [1].) For the purpose of
illustration, a shift register generator with five stages and feedback taps from stages
five and two will be considered. The sequence produced by the shift register
1
\
8
generator, starting with a seed of five ones, is shown in Table 2.1. A different
starting seed can be used, but the sequence produced will be identical, just shifted in
time. The only state not permitted is the all zeroes state as this places the generator
in an endless loop.
Observing the generated sequence, note that the period of the sequence
is 2n 1 bits long. This is the maximum length attainable when every state but the all
zeroes state is used. The sequence length is odd, therefore there is one more 1 than
0. It is a property of the linear recursive sequence that there is always an odd period
length (p = 2m+l) with m zeroes and m+1 ones. Thus, the linear recursive se
quence meets the first requirement for randomness in that there are approximately the
same number of ones and zeroes in the generated sequence. From a practical stand
point, a good balance of ones and zeroes is necessary for obtaining good carrier
suppression in the power spectrum which is dependent upon the symmetry of the
modulating signal.
The number of runs of length p in a linear recursive sequence has been
shown to be 2n_(P+2). This equation holds for both runs of 0's and runs of l's. In
addition, there is always one run of l's of length n and no runs of l's of length n1.
For the 0's there is no run of length n and one run of length n1. All other numbers
of run lengths can be calculated using the formula. The run distribution for the
State
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
9
Table 2.1 Code generated from feedback taps [5,2]
12345 State 12345
11111 17 10 100
01111 18 01010
00111 19 10 10 1
10011 20 11010
11001 21 1110 1
01100 22 01 1 10
10110 23 10 111
01011 24 non
0010 1 25 01101
10010 26 .00110
01001 27 0001 1
00100 28 1000 1
00010 29 1 1000
00001 30 11100
10000 31 11110
01000 1 inn
Code: 1111100110100100001010111011000
10
sequence in Table 2.1 is shown in Table 2.2. Once again, the linear recursive
sequence meets the second property that has been associated with randomness.
Table 2.2 Run distribution for sequence of Table 2.1
Number of runs
Run length (Bits) l's 0's Number of Bits Incl
1 4 4 8
2 2 2 8
3 1 1 6
4 0 1 4
5 1 0 5
31 Total
The third and final property associated with randomness is a sharply
peaked autocorrelation function. The autocorrelation function of a linear maximal
sequence has the invaluable property of being twovalued. This twovalued auto
correlation function yields C(x = 0) = k and C(x ^ 0) = X where k = 2a~l and X =
2a'2. If the sequence ofl's and 0's is replaced by +ls and Is, the correlation
function becomes C(x = 0) = 2l and C(x 0) = 1. This in turn causes the ID
(index of discrimination) to have the maximum value for a particular length
sequence:
ID = 2
Ordinarily, the autocorrelation function is figured as if the sequence contained +ls
and Is since computationally this is easier to calculate. The algorithm for calculat
ing the autocorrelation function simply compares the sequence with a shifted
version of itself on a bit by bit basis. The number of times the bits disagree is
subtracted from the number of times the bits agree. This difference yields the value
11
of the function at that particular shift point This algorithm makes it simple to
calculate the autoconelation function using a computer. The autocorrelation
function for the example sequence is shown in Figure 2.3. It is obvious that a
twovalued autocorrelation function makes synchronization of the transmitter and
receiver in a direct sequence spread spectrum system easy since the receiver can
discriminate between the signals on a yes/no basis.
I 0 shift magnitude+31
nonzero shift
magnitude 1
Figure 2.3 Autocorrelation function of sequence in Table 2.1
In summary, the linear recursive sequences display all three randomness
properties considered necessary to call a sequence "pseudo random". The linear
recursive sequences are certainly deterministic, but their noiselike properties greatly
aide in their usefulness in direct sequence spread spectrum systems. Sequences with
similar statistical properties are desired in order to be of the most use in these types
of communication systems.
2.2 Other Desirable Properties
It is not enough that sequences have statistical properties that make them
appear pseudo random. Other properties must also be considered when choosing a
sequence for a spectrum spreading code. How easily are the codes or sequences
generated and implemented? If a sequence is difficult to generate or reproduce, it is
probably not a very useful sequence. Another question for consideration should be;
12
how many different codes can be generated or produced by only minor
modifications of the hardware or the software? It may be necessary to change the
code being used in a system frequently for security or other reasons. If only a
limited number of sequences exist or can be implemented, this can present a serious
drawback to the system designer. Another factor that may enter into the design
process is determining what type of crosscorrelation properties a code has with
other codes generated similarly. In an environment where many direct sequence
systems may be operating simultaneously, it is important that a receiver not erron
eously think it has synched to its own transmitter because the crosscorrelation with
a similar code in the area is high. It is equally important that long sequences are able
to be generated from a given implementation because statistically, the longer the
sequence, the more the sequence appears random. And finally, in addition to all
these other properties, it is often desirable to have a sequence that makes eaves
dropping difficult or impossible. If it is important for messages to be unobtainable
by other than the intended receiver, then a code must be secure as well as containing
many of the other properties mentioned.
Again it is useful to make some comments on the additional properties
of linear recursive sequences. Linear recursive sequences are used in a great many
systems not only because of their pseudo random nature but also because of their
relative simplicity of implementation. These codes are easily generated with either
shift register generators or software implementations. The number of codes of a
given length can be calculated from
N =
H2n 1)
n
where N is the number of codes of length 2n 1 that can be generated, and the
numerator is an Euler number. The Euler number is the number of positive integers,
including one, which are relatively prime to and less than 2 1. If fairly long codes
13
are desired, a great many different codes of the same length can be generated by
varying the feedback taps. If shorter codes are desired, such as a code of length
4095 bits, then there are only 96 possible different codes that can be generated by
varying the feedback taps. Sometimes this presents some difficulty or limitation for
the system designer. Theoretically, codes as long as necessary can be generated by
simply adding more shift register stages, but in hardware, implementation of ex
tremely long codes can become somewhat more cumbersome. The only real draw
back, however, in using linear recursive sequences for spectrum spreading is that
they are not secure. Linear recursive sequences are easily duplicated given only a
short sequential number of bits (2n) from the sequence. This means that for a code
4095 chips long, it takes only 20 sequential chips to break the code so that it can be
duplicated. Once the code can be duplicated, any information carried on the code
can be recovered. Dixon describes one simple approach to linear code breaking
(requiring 2n+l chips) which is by no means the only method for linear code break
ing [1]. In short, linear recursive sequences are widely used because of their
statistical properties and their ease of implementation, yet if a secure system is
desired these codes cannot be used.
As different sequences are generated during this research effort, they
will be examined for their statistical properties, implementation considerations, and
their ability to ensure secure communications. Consideration will also be given to
crosscorrelation properties with other sequences. Conclusions about the usefulness
of generated sequences will be based upon all the properties discussed in this
Chapter.
CHAPTER 3
INTRODUCTION TO THE ONE DIMENSIONAL LOGISTIC MAP
It was mentioned in Chapter One that the primary objective of this
research effort was to generate binary sequences which would have all the desirable
statistical characteristics of the linear recursive sequence, and yet provide a much
more secure code than the linear recursive sequence is able to. A sequence that is
minimally susceptible to future prediction is required to eliminate the ability of an
"eavesdropper" to predict future values of the code, replicate it, and then extract the
information. Because a chaotic system has been described as "a deterministic
system that exhibits random behavior" [12], perhaps this type of system could be
used to generate the desired sequences.
Before beginning a discussion of the chaotic system chosen for this
research effort, it is appropriate to address the issue of chaos itself. Chaos is, in
simple terms, a form of steadystate response from a nonlinear system. When
nonlinearity is involved, there exists a large range of parameter values where the
steadystate response of a system is totally aperiodic. At the same time, this
aperiodic steadystate response is bounded. There are several properties of chaotic
systems which help refine the above definition. First, the frequency spectrum of a
chaotic system is not discrete, but has a continuous broadband aspect, much like
that of noise. Secondly, chaotic systems have a very sensitive dependence on initial
conditions. A system that is given two initial conditions arbitrarily close to one
another will produce two trajectories that eventually diverge until for all practical
purposes these trajectories are totally uncorrelated. This leads to the conclusion that
15
without infinite precision arithmetic, longterm predictions of systems exhibiting
chaotic behavior are impossible!
The properties of chaotic systems described above imply that a system
of this type would be quite useful in generating a "noiselike" sequence that is still
deterministic but extremely difficult for anyone without a great deal of prior know
ledge of the system to replicate. For this research effort, the one dimensional
discrete logistic map was chosen to generate the desired sequences. The primary
motivation in choosing this particular equation was its relative simplicity. The
logistic map is probably one of the simplest nonlinear difference equations that could
be used In spite of its simplicity, the dynamics of this nonlinear discrete map are
extremely rich and complicated. There are fixed periodic trajectories intermingled
within chaotic regions. There is so much to explore in just this "simple" equation
that chaos theorists have been kept busy for years studying the complexities of this
difference equation.
3.1 Historical Background
The logistic map, or nonlinear logistic difference equation, is a one
dimensional quadratic map on the unit interval. The equation for this discrete map is
given by:
f(Xn) = *n+i= WnOXn)
The logistic map is bounded for values of x between zero and one. The variable ji,
also known as the tuning parameter, is kept between zero and four to restrict the map
to the unit interval. Iteration of this equation is accomplished by selecting an initial
value for x (xt) and applying the function to this value to arrive at the next x (X2).
The x2 value is then used in the equation to arrive at x3, etc.
An abundance of practical applications for this equation exist. It was
introduced in 1845 by P.F. Verhulst to simulate the growth of a population in which
16
generations do not overlap [14]. The variable x^ was used to predict population
growth or decline for the next year based on the present years population and the
tuning parameter i. The value of the parameter (i is based on fertility, availability of
food supplies, etc. An example of the use of this equation in economics might be to
model the relationship between the price of a commodity and its available quantity
[9]. In short, there are many contexts in which this simple difference equation can
be applied. If a system exhibits the property that when x values are small they tend
to increase and when x values are large they tend to decrease, this equation can
possibly be used as a model for the system as a whole. One would expect these x
values to develop towards some mean values due to the feedback mechanism
involved, but it has been found that the iterations on x can display a very com
plicated chaotic behavior as the i parameter is increased towards its maximum.
3.2 Software for Generating Plots of the Logistic Equation
It is very helpful in exploring the nature of the logistic equation to be
able to plot the various iterates of x as a function of the tuning parameter p. A very
simple computer program can be written that allows one to view the nature of this
interesting equation in a fair amount of detail [10]. It was extremely helpful in this
research effort to be able to use such a program to determine where the best areas of
x and p were for generating the desired binary sequences.
An example of one such program is given in Appendix D. This pro
gram was written in Turbo Pascal (version 1.1) on a 512k Apple Macintosh com
puter. The basic algorithm behind the logistic program is given by the following
steps:
1. Select an initial value for x.
2. For Qi=starting value) to (p=ending value),
a. Iterate x for a user selected number of
17
times to eliminate transients and arrive at
steadystate.
b. Plot next N iterates of x with p. on the
horizontal axis and x on the vertical axis.
c. Go to the next p. value.
In addition to this basic algorithm, the program in Appendix D allows the user to
select the starting and ending values of p, the starting and ending values of x, how
many times to iterate x before beginning to plot, and how many x values to generate
once the iterations are done. Examples of the output of this program are given in
figures 3.1 through 3.4. Figure 3.1 illustrates the mapping in its entirety with
values of x between zero and one and values of i between zero and four. Figure
3.2 "zooms in" to show more detail of the first bifurcation area from p=2.5 to
p=4.0. In figure 3.3, the graph is further magnified and a close up of the period
three window (3.8 < p. <, 3.9) can be seen. Figure 3.4 shows an extremely limited
area where p. ranges between 3.994 and 3.996, and x values are between 0.59 and
0.61. Note theseeming randomness of the points in the final figure. These plots
were used to look for areas where the greatest amount of apparent randomness could
be found.
3.3 Behavior of the Logistic Map
Because the logistic equation is a quadratic, plotting the values of Xq+1
versus x,, simply yields a parabola (see figure 3.5) [4]. The steepness of this
parabola is determined by the tuning parameter X. As p increases so does the
steepness of the parabola. For p=4.0, the peak value of this parabola reaches one,
explaining the necessity of limiting i to values of four or less if x is to remain within
the unit interval. The line x^ x^ has also been plotted in each of the graphs of
figure 3.5. Figure 3.5 (a) shows the parabola associated with a p value of 0.8. If a
Figure 3.1 Logistic map with p between 0.0 and 4.0
oo
Figure 3.2 Logistic map with i between 2.5 and 4.0
VO
Figure 3.3 Logistic map period three window
N)
o
*. 4
!
Figure 3.4 Logistic map with x between 0.59 and 0.61,
i between 3.994 and 3.996 i
22
starting value of x,, is chosen, drawing a vertical line up to the parabola yields the
value of Xq+1. To obtain the value of x^, one can simply draw a horizontal line
over to the intersection of the 45 line which effectively plugs the next value of x
into the iterative equation. Drawing another vertical line back to the parabola results
in a value for x^. This process can be repeated to obtain an entire sequence of
iterated x values. For a tuning parameter value of [1=0.8, it is obvious from the
figure that after only a few iterations the values of x would settle to a steadystate
value of zero. Refer back to figure 3.1 to note that any values of i less than one will
all result in a steadystate value of zero for x. From figure 3.1 it can also be seen
that values of [L between one and three lead to a single steadystate value of x. This
is demonstrated using the parabola with i=2.5 in figure 3.5 (b). In this figure, as
the values of x are iterated through the equation, the steadystate value of x rapidly
approaches the intersection of the Xq= Xq+1 line with the parabola. As the steepness
of the "hump" continues to increase ([i>3), the steadystate values of x never settle
to just one value (see figure 3.5 (c)). Between the parameter values of [i=3.0 and
p=3.57, there exists an infinite number of bifurcations or splittings of the
steadystate stable points, and beyond [1=3.57, chaos begins (see figure 3.5 (d)).
The window of [t values between 3.0 and 3.57 is characterized by a
splitting of stable x values into cycles with periods of 2n (n:*). As each
bifurcation occurs, however, the width or window of [i values where a cycle
remains stable decreases rapidly. Note in figure 3.1 that for 3.0< [i<3.44, there is a
stable period two cycle, but the width of the stable period four cycle is much
narrower. The period eight cycle is just discernible on the plot, and periods of 2
where n>3 are impossible to distinguish. This entire bifurcation process is a
convergent one even though there are an infinite number of 2n cycles before [i
reaches its critical value. In the case of the logistic equation, this critical [^ value, or
23
Figure 3.5 Logistic map
24
point of accumulation, is approximately 3.57 (3.56994571869...). A physicist
named Mitchell Feigenbaum became interested in this quadratic map and discovered
that the bifurcation process was a regular one, where the convergence to jij. was
geometric [16]. Furthermore, this convergence rate was applicable to more than just
the logistic equation. Feigenbaum's convergence constant, 6=4.669201609..., can
be used to describe the route to chaos through period doubling for any differentiable
unimodal function. This property is known as the property of universality. Both
this constant and another Feigenbaum universal constant that applies to functions
like the logistic equation are demonstrated in figures 3.6 and 3.7 [14].
Feigenbaum's constant for defining the ratio at which bifurcations take place is given
by:
8 =
I i m
n+2 ~ /Vi
This is demonstrated in figure 3.6. Even though this constant is approached as n>
oo, the convergence to this constant is quite rapid and therefore this constant can be
used to determine approximately where each bifurcation will take place even for
fairly small values of n. If p. in the above equation has 29 places of accuracy, 8n
will converge to 5 to 13 decimal places by n=20. The second universal Feigenbaum
constant is defined in figure 3.7 and is a=2.5029078750... This constant is a
scaling factor which describes the ratio of the distances of the points in a 2n cycle
that are closest to x=0.5 (or the mean of x). This ratio is given by:
 a = I i m ^n
n^~ an
Again, the convergence to this constant is quite rapid and very similar to the
convergence exhibited by the other Feigenbaum constant, 8.
As the tuning parameter p is increased beyond p^ the equation moves
into the chaotic regime. Figure 3.1 shows that in this region, there are periods of
regularity mixed in with chaotic periods. Gose to any tuning parameter value of p
25
Figure 3.7 Scaling Constant
26
which shows a periodic trajectory lies another i value which shows a chaotic
trajectory. These regions are so densely interwoven it is often quite difficult to
determine whether a certain parameter value leads to a periodic or chaotic trajectory.
It has been shown [15] that there are an infinity of i windows which have a periodic
trajectory of period k (k > >) in this region. At the same time, there are many
parameter values that lead to aperiodic or chaotic trajectories intermingled between
these windows. As the parameter values move towards 4, the windows where
periodic trajectories take place become infinitely thin making the decision as to
whether one is in a chaotic or periodic region even more difficult to ascertain.
Practically speaking, because of finite arithmetic precision and the length of time
necessary for the transients of the equation to die out, it is often desirable to resort to
statistical models to explain the behavior in the chaotic region.
CHAPTER 4
BINARY SEQUENCES GENERATED FROM THE
LOGISTIC DIFFERENCE EQUATION
Having looked at the nature of the one dimensional logistic map, binary
sequences can now be generated from the iterates of this equation. This chapter
presents the binary sequences that were produced and discusses how variations in
parameters associated with the logistic map affected the sequences that were gen
erated. As stated in Chapter 2, a useful spread spectrum communication sequence
requires the following properties: an approximately equal number of ones and
zeroes, a random distribution of run lengths, and a noiselike, sharply peaked auto
correlation function. In Chapter 3, the true "randomness" of the chaotic regions of
the logistic map was discussed briefly. For the purposes of this investigation,
however, true randomness of the iterates is not really required. (Refer back to the
linear recursive sequences described in Chapter 2 which are not at all truly random
especially when the maximal length is used). All that is necessary for a binary
logistic sequence are iterates that can be thresholded to yield a binary sequence with
the characteristics described in Chapter 2. Therefore, based upon the characteristics
of the logistic equation, it appears that good pseudorandom sequences could be
generated either in a chaotic region or a periodic region with a very long period.
Using the chaotic region of the logistic map to generate binary se
quences for the described purpose appears to be a good way to produce an almost
limitless variety of sequences with very long periods. (These sequences can only be
aperiodic if infinite precision arithmetic is used in the iteration of the equation.) This
28
ability to generate large numbers of different sequences with very long periods was
another of the desirable properties described in Chapter 2. Furthermore, these
binary logistic sequences are easily generated using a simple computer algorithm and
can readily be altered just by varying certain input parameters. This property can be
quite valuable to a spread spectrum communication system designer. Finally, while
it is a difficult question to answer, it looks as if sequences generated from the
logistic equation would be extremely difficult for an eavesdropper to reproduce.
Unless the eavesdropper knew exactly what parameters (starting x value, i value,
threshold values, etc.) were used to generate a given sequence, it would be almost
impossible for him to reproduce the sequence.
This chapter describes how various binary sequences were generated,
and presents the results of varying the parameters associated with the logistic
equation on the sequences generated. How useful these sequences would be in an
actual spread spectrum system is discussed more in Chapter 5. The sequences
described in this chapter were produced with the software programs presented in
Appendix A. Because there are so many variables in this production process, the
variables and the effects that each variable had on the sequences generated were
studied one at a time. The first variable to be looked at was the starting value of x
used to begin the iteration process. After the effects of varying the starting value
were determined, effects of varying the thresholding parameters were investigated.
Next, various values of the tuning parameter p were observed to determine if certain
values produced better sequences than other values, and finally the effects of varying
sequence length on the statistical randomness of the sequence was investigated.
Each of these areas is discussed in more detail in the following sections.
29
4.1 Starting Values
The program which produces sequences from the logistic equation
allows the user a great deal of flexibility in setting up several parameters. The user
is required to select i, a starting value for x, a range of x values to use in the se
quence generation, a threshold for generating the sequence of l's and 0's, and the
number of presequence iterations to be performed. Before beginning a discussion
of starting x values, it is instructive to point out how the number of presequence
iterations can affect sequence generation even though the number of presequence
iterations is not really an equation parameter. Several iterations of the equation are
usually performed to allow the transients to damp out before the actual steadystate x
values appear. The number of iterations required for the transients to settle is depen
dent upon the value of i being used. For values of i less than than three, the
transients die out quickly and steadystate is reached after only a few iterations. As
i approaches three (the first bifurcation point) the number of iterations required for
the transients to settle increases astronomically. When this bifurcation point is
passed, once again the transients settle out quickly. This process of increased
"settling time" is repeated each time the parameter i approaches a bifurcation point
Once the critical value ji^. = 3.57 is reached, the iterates never settle to steadystate
values no matter how many iterations are done. Figures 4.1 through 4.4 show the
region right around the first bifurcation point with varying "preplot" iterations. The
first figure is plotted after only 50 iterations, the second figure has undergone 200
iterations, the third 1000, and the last 10,000 iterations before being plotted. Note
that the actual splitting point moves to the right in each successive figure as the
number of iterations increases. If the vertical scale of the plots were decreased,
perterbations in the x values would still be evident even after 10,000 iterations.
Because the chaotic region was used in this study to generate the sequences of
Figure 4.1 50 Iterations
u>
o
Figure 4.2 200 Iterations
Figure 4.3 1000 Iterations
to
M
Figure 4.4 10000 Iterations w
Kji
34
interest, presequence iterations were not really required. (Recall from Chapter 3
that because the periodic windows are so narrow in the chaotic region, transients die
out very slowly and a periodic trajectory will be difficult to distinguish from a
chaotic trajectory [9]. This property allows more freedom in choosing i parameter
values in the chaotic region, and eliminates the need for presequence iterations.)
However, it should be noted that "different" sequences could be generated just by
varying the number of presequence iterations. These sequences would not actually
be different, just various segments of one very long sequence.
Because the logistic map is a quadratic, there should be two starting
values which lead to the same iteration sequence. Working on a computer, how
ever, the two values which should lead to the same sequence don't always do so. If
the two initial values which should lead to the same sequence can be exactly rep
resented in binary notation, the resulting sequences will be identical. On the other
hand, if these initial values cannot be represented exactly in binary, the sequences
produced from these starting points will begin to diverge fairly quickly. Table 4.1
shows the x values for different sequences of iterations. These sequences have
starting values of 0.4 and 0.6 respectively. Since both of these values lead to the
same next x value, the sequences produced should be identical. However, neither of
these numbers can be represented exactly in binary notation and the sequences begin
to diverge in the least significant decimal place as quickly as the eighth iteration. By
the thirtieth iteration, the last four decimal places are different Table 4.2 shows the
x values for two sequences with different starting values that lead to the exact same
sequence. The starting values used in this case were 0.45 and 0.55 which can both
be represented exactly in binary notation. It must be stressed at this point that com
puter architecture plays an important role in the production of sequences from the
logistic equation due not only to the binary representation of decimal digits, but also
35
Starting x = 0.4: 0.93120000000000000 1 Starting x = 0.6: 0.93120000000000000
0.24857825280000000 0 0.24857825280000000
0.72473396753540925 1 0.72473396753540925
0.77403921808287924 1 0.77403921808287924
0.67862172697579370 1 0.67862172697579370
0.84620580117047785 1 0.84620580117047785
0.50494918775532122 0 0.50494918775532121
0.96990496149738280 1 0.96990496149738280
0.11325458938135557 0 0.11325458938135557
0.38966059097781451 0 0.38966059097781451
0.92276183348854322 1 0.92276183348854322
0.27653703672417239 0 0.27653703672417240
0.77624949969066615 1 0.77624949969066616
0.67390251001214778 1 0.67390251001214776
0.85266071800452238 1 0.85266071800452242
0.48744602174895481 0 0.48744602174895471
0.96938850280468046 1 0.96938850280468045
0.11513680172694827 0 0.11513680172694830
0.39529563622634616 0 0.39529563622634626
0.92746354528220694 1 0.92746354528220702
0.26102667972449449 0 0.26102667972449421
0.74841999852242258 1 0.74841999852242207
0.73055551681638391 1 0.73055551681638490
0.76375531622225686 1 0.76375531622225508
0.70008055667824948 1 0.70008055667825311
0.81467495085656857 1 0.81467495085656294
0.58580114017725467 0 0.58580114017726844
0.94143607765581840 1 0.94143607765580924
0.21392065465412350 0 0.21392065465415490
0.65245539968592195 1 0.65245539968599166
0.87981852229363046 1 0.87981852229354800
0.41026301367600980 0 0.41026301367625286
0.93875542034769343 1 0.93875542034786268
0.22307548272821313 0 0.22307548272763686
0.67245370952709673 1 0.67245370952585835
0.85460770611293374 1 0.85460770611459098
0.48210309408945409 0 0.48210309408489375
0.96875723894425678 1 0.96875723894362344
0.11743460563694499 0 0.11743460563924879
For this table of values the following parameters were used:
X = 3.88
X Range = 0,1
Threshold = 0.65
Size = 40
No iterations
Table 4.1 Iterates for starting values 0.4 and 0.6
1
0
1
1
1
1
0
1
0
0
1
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
36
Starting x = 0.45: 0.96030000000000000 1 Starting x = 0.55: 0.96030000000000000
0.14792077080000000 0 0.14792077080000000
0.48903603949982340 0 0.48903603949982340
0.96953359129218420 1 0.96953359129218420
0.11460824179526480 0 0.11460824179526480
0.39371598770650813 0 0.39371598770650813
0.92617038987549185 1 0.92617038987549185
0.26530973931828053 0 0.26530973931828053
0.75629146837964866 1 0.75629146837964866
0.71514097095491777 1 0.71514097095491777
0.79041172695231188 1 0.79041172695231188
0.64276479193247429 0 0.64276479193247429
0.89091867103577201 1 0.89091867103577201
0.37706845942622835 0 0.37706845942622835
0.91136480496877744 1 0.91136480496877744
0.31342250926403883 0 0.31342250926403883
0.83493269900860861 1 0.83493269900860861
0.53474193808305810 0 0.53474193808305810
0.96531683122434387 1 0.96531683122434387
0.12990335672782165 0 0.12990335672782165
0.43855048159802395 0 0.43855048159802395
0.95534895195008100 1 0.95534895195008100
0.16551044799689575 0 0.16551044799689575
0.53589294965095896 0 0.53589294965095896
0.96500138112157245 1 0.96500138112157245
0.13104201635351687 0 0.13104201635351687
0.44181562445766338 0 0.44181562445766338
0.95686456435786356 1 0.95686456435786356
0.16014610695630623 0 0.16014610695630623
0.52185740576621676 0 0.52185740576621676
0.96814634479510330 1 0.52185740576621676
0.11965531943733891 0 0.11965531943733891
0.40871114499462670 0 0.40871114499462670
0.93766541841301477 1 0.93766541841301477
0.22678204831839957 0 0.22678204831839957
0.68036556941017334 1 0.68036556941017334
0.84377685412081451 1 0.84377685412081451
0.51145180133468934 0 0.51145180133468934
0.96949116223522033 1 0.96949116223522033
For this table of values the following parameters were used:
i = 3.88
XRange = 0,l
Threshold = 0.65
Size = 40
No iterations
Table 4.2 Iterates for starting values 0.45 and 0.55
1
0
0
1
0
0
1
0
1
1
1
0
1
0
1
0
1
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
1
1
0
1
to the degree of precision available on a given system. These seeming limitations
can be an advantage when designing new codes, since these limitations can actually
lead to a larger number of different codes being produced.
One of the properties of chaos is a sensitive dependence upon initial
conditions. Because of this property, small changes in the starting x values used to
generate binary sequences can lead to completely different sequences being gen
erated. In studying this sensitivity to initial conditions, sequences of length 500
were used without any initial iterations. The same i value was used (3.88) for each
sequence generated, along with the same threshold value (0.65), and range of x
values (0 ^ x < 1). The only parameter allowed to vary was the starting value. The
acquired data showed that even with very small changes in the starting value of x,
the sequences produced were quite different Sequences were generated with
starting values that varied initially in the third decimal place (0.455 and 0.456).
These sequences proved to iterate differently after the first eleven values. For
example, the sequence produced with a starting value of 0.455 led to a sequence
with 272 ones and 228 zeroes. The sequence produced with a starting value of
0.456 led to a sequence with 241 ones and 259 zeroes. Next, the starting values
were varied in the fourth decimal place (0.4555 and 0.4554) which again resulted in
totally different sequences after only eleven iterations. As the starting values got
closer and closer together, the sequences still diverged from one another quite
rapidly. The last trial is depicted in tables 4.3 and 4.4. Table 4.3 shows the
sequence generated from a starting value of 0.4555555555, while table 4.4 contains
the sequence with a starting value of 0.4555555556, a difference in starting value of
only 10"10. (Note that in the code generating program, the starting x value is never
used for sequence generation but only as an initial seed for the equation. This seed
38
The generated code is:
100100100100101010010111010010110100100lQOlQQlQOl00101111111010010
010111010010010010110101010101001011010101001001011010010010010111
010110101010010010110100101101001011010101010010010110100100100101
111010010010111110101011110100101111010010010010110100101110100101
101001010100100100100101110100100100100101110100101110101010100101
111101010101010101111101010101001010100101110100100100101010010010
111010010010010010111110100101010010010010010101001001011111110100
10111010010010111010010010010111010010
Statistical Data:
The number of ones is: 248
The number of zeros is: 252
The number of runs of ones of length 1 are: 144
The number of runs of zeros of length 1 are: 100
The number of runs of ones of length 2 are: 11
The number of runs of zeros of length 2 are: 76
The number of runs of ones of length 3 are: 12
The number of runs of ones of length 4 are: 3
The number of runs of ones of length 5 are: 4
The number of runs of ones of length 7 are: 2
This code was generated using the following parameters:
Mu = 3.88
Start = .4555555555
Threshold = 0.65
Length =500
No iterations
X Range = 0,1
Table 4.3 Code and Statistical Data for Starting value of
0.4555555555
39
The generated code is:
1001001001001010100101110100101101001Q01001001001001001001QQ1Q0100
101111111010010010101010101010101010010101110100100101101001011101
001011010010111010010010111010010010101001001010100101010010010010
111010010010010111010010110100101101001001001010101010101001001011
010010101010101010101010010111010010110101010100100101010010111010
010010111111111111010010010111010111010010111010110100100100100100
101111101001001001001001011101001001011101001001011010101010101010
01011010111010010010010010110100101110
Statistical Data:
The number of ones is: 244
The number of zeros is: 256
The number of runs of ones of length 1 are: 150
The number of runs of zeros of length 1 are: 104
The number of runs of ones of length 2 are: 11
The number of runs of zeros of length 2 are: 76
The number of runs of ones of length 3 are: 16
The number of runs of ones of length 5 are: 1
The number of runs of ones of length 7 are: 1
.The number of runs of ones of length 12 are: 1
This code was generated using the following parameters:
Mu = 3.88
Start = .4555555556
Thresh = .65
Length = 500
no iterations
Range = 0,1
Table 4.4 Code and Statistical Data for Starting value of
0.4555555556
40
can be thought of as x0i while the first iterate (x^ is the beginning value used in the
generation of the binary sequence.) From the analysis data in tables 4.3 and 4.4, it
is obvious these two slightly different starting values lead to totally different
sequences. In fact, after only fiftythree iterations, the generated binary sequences
were no longer the same. Obviously, binary sequences produced in such a manner
depend heavily upon the initial starting value, with very small deltas in the starting
values leading to totally different sequences after only a few iterations.
The significance of the sensitivity of sequence generation to the initial
value becomes apparent when the number of different sequences that can be gen
erated is realized If the exact same parameters are used with the exception of start
ing value, at least half of all the real numbers between zero and one will lead to a
different sequence. (Exactly half would lead to unique sequences if it weren't for
the fact that computers use binary representations of the decimal values.) Even
when allowing for finite precision (lessening the number of different available
starting values), the number of different sequences that can be generated from just a
variation in the starting value is staggering. This is a real advantage when a secure
i
code is required in a communication system. Slight changes to the starting values
used for code generation could be made at periodic time intervals much like using a
different encryption key. These slight variations would make detection and
duplication of the code extremely difficult
One problem observed in the sequences generated up to this point
however, is that the sequencess are not statistically very random (refer back to tables
4.2 and 4.3). While the number of ones and zeroes are approximately equal, the run
length distributions do not look at all like those produced by a truly random binary
sequence. Therefore, the next parameter to be varied experimentally in the search
for pseudorandom sequences was the threshold value.
41
4.2 Thresholding
In order to create a binary sequence from a sequence of real numbers, a
threshold value must be used to determine whether the equation iterates become ones
or zeroes. In the last section, a single threshold value (0.65) was used for the se
quence generation. This value was chosen (refer back to figure 3.1) because about
half of the x values seemed to lie above this .value, and half below. However, it was
also pointed out in the last section that the sequences generated using this single
threshold are not very random. The longest runs were composed of ones alone,
while the longest run of zeros was only of length two. These sequences do not have
the necessary statistical run length distributions to make them useful. Table 4.5
shows a comparison of expected values versus observed values for the different
sequences generated by varying the threshold. Varying the single threshold value
did not help the run length distribution look more.random, therefore, a second
thresholding function was added to the sequence generation process.
Using the short program called "Logistic" (described in Chapter 3),
various magnified sections of the chaotic region were observed for uniformity.
Sequences were then produced by limiting the range of x values that were used to
generate the binary values. For example, if the limiting range for x was chosen to be
0.5 ^ x Ã‚Â£ 0.7, then only when x fell between these values during the iteration pro
cess would the threshold for deciding between a one or a zero be applied. Only
those x values falling within the required range of x are then used to generate the
binary sequence. Using this "double thresholding" approach led to sequences that
had much more random statistical properties.
As before, while exploring the effects of thresholding, only the
threshold values themselves were allowed to change. The other parameters of the
logistic equation were kept constant It is fairly obvious from plots of the logistic
Threshold Num of l's Num of 0's Runs of length 1 Ones Zeroes Length of longest run Ones Zeroes
0.65 500/500 500/500 125/281 125/196 8/11 8/2
0.70 500/451 500/549 125/349 125/213 8/9 8/2
0.71 500/442 500/558 125/363 125/220 8/9 8/2
0.72 500/432 500/568 125/376 125/218 8/9 8/2
0.73 500/419 500/581 125/393 125/219 8/7 8/2
0.74 500/412 500/588 125/402 125/222 8/5 8/2
0.745 500/403 500/597 125/403 125/217 8/1 8/7
0.75 500/398 500/602 125/398 125/209 8/1 8/9
Parameters for Sequence Generation:
Mu = 3.88
Start x = 0.5
X range = 0 to 1
Length = 1000
No iterations
Table 4.5 Single Threshold Sequences (Expected/Observed)
5
43
map that the best ranges for x are quite dependent upon the parameter (I that is being
used. Consequently, the first parameter that was set during this phase of the ex
periment was i. A p. value of 3.97 was chosen basically by observing a small area
around this region with the Logistic plotting routine. It was desired to use a p. value
in what appeared to be a chaotic region, and one that generated iterates across the full
range of x values from 0 to 1. No presequence iterations were used since it was
assumed the parameter value was in a chaotic (or very long periodic) region. A
length of 500 was chosen for each sequence generated, and a starting value of
x=0.5 was used for all experiments. The threshold for creating ones and zeroes
from the x iterates was chosen to be the midpoint of the x range in every case. From
both the experiements and observations made using the Logistic plotting routine, the
best range of x values appear to be around the middle of the 0 to 1 range. For most
p. values greater than 3.9, in fact, the midrange of x values appears to have the most
even distribution of iterates. Table 4.6 lists the statistical results of some of the
sequences generated during this phase of experimentation. Again, the values in the
table list expected results versus observed results. Note the greater degree of ran
domness in the run lengths than was seen when the entire range of x values was
used for sequence generation (table 4.5).
While the statistical properties of the sequences generated using double
thresholding were much better than those without double thresholding, most of the
sequences still cannot be considered pseudorandom. Therefore the very important
question of how the tuning parameter p. affects sequence generation still remains and
the next logical choice of parameter value to vary is that of the tuning parameter, p..
X Range Threshold Num of l's Num of 0's Runs of length 1 Ones Zeroes Length of longest run Ones Zeroes
0.0 0.2 0.1 250/274 250/226 62/100 62/120 7/7 7/5
0.1 0.3 0.2 250/156 250/344 62/65 62/30 7/6 7/17
0.2 0.4 0.3 250/249 250/251 62/68 62/75 7/5 7/8
0.3 0.5 0.4 250/302 250/198 62/45 62/64 7/12 7/6
0.4 0.6 0.5 250/234 250/266 62/70 62/60 7/5 7/6
0.5 0.7 0.6 250/217 250/283 62/60 62/41 7/17 7/12
0.6 0.8 0.7 250/256 250/244 62/54 62/56 7/9 7/10
0.7 0.9 0.8 250/289 250/211 62/43 62/54 7/11 7/6
0.8 1.0 0.9 250/366 250/134 62/53 62/134 7/19 7/2
0.28 0.32 0.3 250/265 250/235 62/61 62/71 7/8 7/10
Parameters for Sequence Generation:
Mu = 3.97
Start x = 0.5
Length = 500
No iterations
Table 4.6 Double Threshold Sequences (Expected/Observed)
4^.
b.
45
4.3 Variation of i parameter
Observing the different plots of the logistic map, it is obvious that once
(i increases beyond (ic> there are periodic regions closely interwoven within the
chaotic regions. The periodic windows become so narrow as p. gets close to four
that it is quite difficult to distinguish which parameter values lead to chaotic orbits
and which parameter values lead to periodic orbits. In fact, it is often impossible to
make this determination experimentally because of finite precision arithmetic.
(Recall from section 4.1 that the transients in this region damp out very slowly.) It
has been shown that the fraction of parameter values above iig that are actually
chaotic is 0.8979 [14]. This ratio, however, in no way describes the widths of any
chaotic windows in the parameter range 3.57 ^ i <14.0 but as i approaches four,
the widths of the periodic regions tend to get narrower, and the chances of landing in
a periodic region seem to be lessened. If periodic regions are encountered very near
four, generally these regions are very narrow and the periods associated with them
are quite likely (but not necessarily) to be very long. It is also apparent from the
logistic plots that the iterates appear to be distributed more uniformly in the
parameter region near four which should lead to more randomlike sequences. (See
figure 4.5) Therefore, for experimenting with changes in i values on binary
sequence generation, it was decided to keep the i values close to four.
As before, all the other parameter values were held constant. A starting
value of 0.5 was used, and x was limited to the range 0.45 Ã‚Â£ x <, 0.55. The thres
hold value for x was set in the middle of the x range at 0.5, and a sequence length of
500 was used. The number of presequence iterations used was 500 to detect any
periodic parameter values with smaller length periods. (For example, the window
3.999371 < i Ã‚Â£ 3.999373 yields a period 7 window which is quite obvious after
500 iterations.) The i parameter was varied from 3.9990 to 3.9999 by increments
Figure 4.5 Logistic plot with 3.999 < p < 4.000,
0.0 < x < 1.0
47
of 0.0001. None of these parameter values yielded periodic sequences (at least of
length 500 or less). Judging the sequences generated for randomness by the three
criteria discussed in Chapter 2 yields the observation that all ten sequences generated
seem to qualify as pseudorandom. All ten sequences had approximately equal
frequencies of ones and zeroes. A chisquare statistic was computed on the
frequency of ones and zeroes for each sequence [17]. The chisquare statistic for
every sequence generated fell between the 5% and 95% confidence levels for one
degree of freedom. Therefore, a fairly high level of confidence in the randomness of
the frequency distribution of ones and zeroes is obtained. All of the sequences
generated had noiselike autocorrelation functions and a relatively high index of
discrimination (ID value). Figure 4.6 shows an example of the autocorrelation
function of the sequence generated from a i value of 3.9994. Just as the auto
correlation function for random noise has a sharp correlation peak, so do the
autocorrelation functions for these sequences. Judging the randomness of the run
length distributions is more difficult than judging the other two criteria. For a
random run length distribution, approximately half of the runs will have a length of
one, one fourth of the runs will have a length of two, one eighth of the runs will
have a length of three, etc. Furthermore, there should be an approximately equal
number of runs of ones of a given length and runs of zeroes of the same length.
This appears to hold fairly well for the sequences generated but there is no real
quantitative way to judge how well the run length distributions of the generated
sequences approximate those of a true random sequence. (The chisquare statistic is
not valid for run length distributions because the run lengths are not independent of
one another [17].) Therefore, a second experiment was done using the exact same
set of parameter values as the first time except for the number of presequence
iterations. In section 4.1, it was explained that presequence iterations simply
Figure 4.6 Autocorrelation function for
sequence generated using i = 3.9994
49
determine where on a longer sequence values for the desired length sequence begin
to be taken. Thus, by increasing the number of presequence iterations to 10000,
another 500 bit "chunk" of a much longer sequence is obtained. The run length
distributions of these second "chunks", along with the frequency distributions of
ones and zeroes, are helpful in determining if the sequences can be considered
pseudorandom. The second experiment repeated the sequence generation and
analysis using the same (i values as before and 10,000 presequence iterations. Once
again, none of the sequences generated appeared to be periodic. A summary of the
results for both experiments are listed in tables 4.7 and 4.8. The expected values for
each table entry are listed under the entry heading. As in the first experiment, all ten
sequences had random frequency distributions of ones and zeroes (the chisquare
statistics computed were between the 5% and 95% confidence levels), noiselike
autocorrelation functions, and what appeared to be fairly random run length distri
butions. Comparing the run length distributions of the two experiments for any
obvious patterns revealed nothing that would indicate a lack of randomness. For
example, comparing the two sequences generated using a (i value of 3.9991, it can
be seen that the first sequence where 500 iterations were used resulted in a sequence
with 247 ones and 253 zeroes. The second sequence (where 10000 iterations were
used) resulted in 264 ones and 236 zeroes. Both of these frequency distributions of
ones and, zeroes result in chisquare statistics falling between the 5% and 95% con
fidence levels. Note, however, that more ones than zeroes or viceversa are not
consistently generated which leads to even more confidence in the randomness of the
sequences generated. Comparing the run length distributions of the two sequences,
again it can be seen that there are no obvious parallels or patterns between the two
sequences. Similar results were found comparing the other sequences generated
using 500 iterations with their counterparts generated using 10000 iterations. More
Num Ones 250 Num Zeroes 250 Chi Square Runs of length 1 Runs of length 2 Runs of length 3 Longest Run ID
Ones 62.5 Zeroes 62.5 Ones 31.3 Zeroes 31.3 Ones 15.6 Zeroes 15.6 Ones 7 Zeroes 7
3.9990 239 261 .968 77 74 40 31 9 20 6 6 440
3.9991 247 253 .072 67 69 32 29 15 13 7 7 428
3.9992 251 249 .008 63 59 27 31 19 21 7 7 436
3.9993 251 249 .008 63 60 28 35 16 20 7 8 440
3.9994 263 237 1.352 54 72 39 33 27 10 7 6 440
3.9995 258 242 .512 63 64 34 35 14 15 10 5 436
3.9996 231 269 2.888 63 59 26 27 22 20 6 9 428
3.9997 246 254 .128 61 66 33 21 14 15 10 8 412
3.9998 241 259 .648 55 51 39 38 12 16 7 13 432
3.9999 251 249 .008 63 53 23 33 11 13 11 7 440
Parameters for Sequence Generation:
X range = 0.45 to 0.55
Threshold = 0.5
Start x = 0.5
Length = 500
Iterations = 500
Table 4.7 Variations of [i parameter 500 Iterations
n Num Ones 250 Num Zeroes 250 Chi Square Runs of length 1 Runs of length 2 Runs of length 3 Longest Run ID
Ones 62.5 Zeroes 62.5 Ones 31.3 Zeroes 31.3 Ones 15.6 Zeroes 15.6 Ones 7 Zeroes 7
3.9990 274 226 4.608 68 83 28 25 19 16 10 8 440
3.9991 264 236 1.568 61 62 27 32 16 17 10 6 440
3.9992 235 265 1.8 56 50 32 25 14 17 13 8 436
3.9993 268 232 2.592 61 70 31 33 21 16 11 7 444
3.9994 262 238 1.152 66 65 20 30 17 15 7 6 420
3.9995 236 264 1.568 59 50 24 29 19 19 9 9 432
3.9996 240 260 3.2 63 62 31 27 18 19 7 8 448
3.9997 247 253 .072 63 60 26 34 19 15 8 7 444
3.9998 267 233 2.312 50 68 39 28 20 18 6 7 440
3.9999 257 243 .392 64 62 27 36 20 13 8 7 444
Parameters for Sequence Generation:
X range = 0.45 to 0.55
Threshold = 0.5
Start x = 0.5
Length = 500
Iterations = 10000
Table 4.8 Variations of i parameter 10000 Iterations
52
will be said about the randomness of the run length distributions later in the chapter
when comparisons are made between the logistic sequences and LRS and random
number generator sequences.
 Producing sequences from different parameter values confirms the initial
observation that most of the parameter values near four will result in extremely long
sequences that are pseudorandom. None of the parameter values used in the preced
ing experiments indicated "better parameter values to use for more random se
quences. However, a designer using these sequences for communication purposes
would need to verify that all parameter values being used lead to sequences with the
necessary statistical characteristics.
4.4 Sequence Lengths
Now that the best equation parameters have been determined for gen
erating pseudorandom sequences, a question arises as to how long these sequences
can actually be. When sequences longer than 500 bits are generated using the
logistic equation, are the statistical properties of these longer sequences still random?
What lengths of sequences can be expected before a periodic cycle is encountered?
These questions were investigated using the same equation parameters that were
used in the last section, but before discussing the results of the sequence length
experiments, it is necessary to reexamine the role finite precision and computer
number representation play in sequence generation.
hi section 5.1 the fact that computer architecture plays a role in the se
quences generated was revealed when investigating how different starting values
affected sequence generation. Computer architecture also plays a role in determining
the longest sequences that can be generated because of finite precision arithmetic.
Theoretically, any sequences produced from a chaotic region are aperiodic. In
reality, however, the precision available on the computer generating the sequences
determines the longest sequences that can be generated. If the computer being used
has an accuracy to five decimal places, the longest sequences that can be generated
(providing the i parameter is chaotic) are approximately 105 or 100000 bits long.
The more decimal places of accuracy available on a machine, the longer the possible
sequence length. On a machine with 64 bits of precision (approximately 19 decimal
places of accuracy), the longest possible sequence would be around 1019 bits. For
all practical purposes, a sequence of this length can be thought of as aperiodic. The
capability of being able to generate sequences of very long lengths is important for
spread spectrum communication systems. Not only do longer length sequences
result in more "noiselike" frequency spectra, but longer length sequences are more
difficult for a wouldbe eavesdropper to decode. A sequence containing 1018 bits
clocked at a rate of 100 Mbits/sec, for example, would not repeat for 1010 seconds
(317 years), which certainly discourages most decoding efforts.
A word of caution needs to be said at this point, however, since se
quences of these enormous lengths are only possible if the tuning parameter being
used in the iteration process leads to a chaotic trajectory. In manycases, the para
meter chosen may lead to a periodic trajectory resulting in a much shorter sequence
being generated. Therefore, the only statement that can be made as to available
sequence length is that sequence length is bounded by finite precision arithmetic and
the value of the tuning parameter. So many factors play a role in sequence length
determination (number of iterations required for transients to damp out, for example)
that it is difficult at best (impossible at worst) to actually determine the sequence
length experimentally. It is important, then, for a spread spectrum communication
system designer to ensure that any sequences generated for use in his system have
the length required for that system's particular needs.
54
To experiment with longer sequence lengths, the program described in
Appendix A, section A.4, was used. This program enabled sequences with very
long lengths to be created and partially analyzed by not storing the generated
sequence. From the experiments on different (1 parameter values, three p. values
were chosen to use in generating longer length sequences. All other equation
parameters remained the same (x range 0.45 to 0.55, threshold = 0.5, starting x
value = 0.5, number of iterations = 500). Sequences of lengths 500,1000,2000,
4000, 8000,16000,32000, and 64000 bits were generated for each of the three i
values chosen (3.9991,3.9996, and 3.9999). A summary of the results of this
experiment is contained in tables 4.9 (a) through (c). Table 4.9 (a) lists the results
for sequences generated using a (i parameter value of 3.9991. Tables 4.9 (b) and (c)
list the results for parameter values of 3.9996 and 3.9999 respectively. The
expected values for each result are given direcdy above the observed values in each
of these tables. As in the previous section, no periodic sequences were encountered,
and each of the sequences generated could be labeled pseudorandom using the
criteria developed in Chapter 2. As the sequence lengths increased, the number of
runs of a given length increased proportionally, and nothing that could be considered
nonrandom was revealed by the data collected.
4.5 Comparison with other Pseudorandom Sequences
At this point in the discussion, a comparison between sequences gen
erated using the logistic equation, a linear feedback shift register generator (LRS),
and a random number generator is useful. Because LRS sequences are decidedly
nonrandom as the number of samples from the entire sequence increases towards the
actual period of the sequence, 500 bit sections of much longer sequences were used
for statistical comparison with the other pseudorandom sequences generated. The
period of the random number generator sequence is also much longer than 500 bits,
Length Number of ones zeroes Chi Square Run Length 1 ones zeroes Run Length 2 ones zeroes Run Length 3 ones zeroes Run Length 4 ones zeroes Longest Run ones zeroes
1000 E 500 503 497 .036 E 125 124 123 E 62.5 61 62 E 31.3 31 34 E 15.6 14 14 E 8 10 7
2000 E 1000 991 1009 .162 E 250 244 232 E125 120 129 E 62.5 59 65 E 31.3 26 26 E 9 10 10
4000 E 2000 1975 2025 .625 E 500 509 491 E 250 242 255 E 125 110 121 E 62.5 68 60 E10 10 16
8000 E4000 3959 4041 .841 E1000 1027 994 E 500 495 523 E 250 233 233 E125 129 121 E11 10 16
16000 E8000 7910 8090 2.03 E 2000 2069 1982 E1000 1000 1059 E 500 464 468 E 250 253 266 E12 13 16
32000 E16000 15743 16257 8.26 E4000 4187 4029 E 2000 1995 2052 E1000 968 960 E 500 482 512 E13 16 16
64000 E32000 31806 32194 2.35 E 8000 8096 7986 E4000 3993 4033 E 2000 1985 1984 E 1000 989 1000 E14 16 16
Parameters for Sequence Generation:
X range = 0.45 to 0.55
Threshold = 0.5
Start x = 0.5
Iterations = 500
Table 4.9(a) Sequences of varying lengths, i = 3.9991
Length Number of ones zeroes Chi Square Run Length 1 ones zeroes Run Length 2 ones zeroes Run Length 3 ones zeroes Run Length 4 ones zeroes Longest Run ones zeroes
1000 E 500 485 515 .900 E125 130 124 E 62.5 56 59 E 31.3 39 39 E 15.6 18 15 E 8 8 9
2000 E 1000 960 1040 3.20 E 250 249 242 E125 116 112 E 62.5 74 73 E 31.3 36 33 E 9 8 10
4000 E2000 1977 2023 .529 E 500 496 501 E 250 247 236 E 125 133 134 E 62.5 69 61 E10 8 10
8000 E4000 3983 4017 .145 E 1000 994 1002 E 500 525 490 E 250 238 277 E125 125 107 E11 10 10
16000 E 8000 8114 7886 3.25 E2000 1995 2052 E 1000 998 990 E 500 498 513 E 250 278 237 E 12 12 12
32000 E 16000 16066 15934 .545 E4000 3982 4019 E2000 1997 2011 E1000 1021 998 E 500 530 504 E 13 12 13
64000 E 32000 32094 31906 .552 E 8000 8004 8094 E4000 4004 4001 E2000 2058 1976 E 1000 1009 1010 E 14 13 15
Parameters for Sequence Generation:
X range = 0.45 to 0.55
Threshold = 0.5
Start x = 0.5
Iterations = 500
Table 4.9(b) Sequences of vaiying lengths, i = 3.9996
On
Length Number of ones zeroes Chi Square Run Length 1 ones zeroes Run Length 2 ones zeroes Run Length 3 ones zeroes Run Length 4 ones zeroes Longest Run ones zeroes
1000 E 500 508 492 .256 E 125 122 113 E 62.5 56 68 E 31.3 29 28 E 15.6 13 18 E8 11 7
2000 E1000 979 1026 1.35 E 250 248 220 E125 115 133 E 62.5 63 63 E 31.3 20 32 E 9 11 10
4000 E2000 1973 2027 .729 E 500 490 463 E250 231 250 E125 138 131 E 62.5 51 70 E10 11 10
8000 E4000 3983 4017 .145 E1000 982 961 E 500 473 500 E250 272 250 E 125 116 129 E 11 12 10
16000 E8000 8074 7926 1.37 E2000 1976 1996 E 1000 968 997 E 500 506 492 E250 250 239 E 12 13 11
32000 E16000 16179 15821 4.01 E4000 3944 4016 E2000 1988 1985 E1000 1020 1050 E 500 515 473 E 13 13 12
64000 E 32000 32135 31865 .992 E8000 7917 7993 E4000 4060 3967 E2000 1942 2035 E1000 1011 1008 E 14 13 19
Parameters for Sequence Generation:
X range = 0.45 to 0.55
Threshold = 0.5
Start x = 0.5
Iterations = 500
Table 4.9(c) Sequences of varying lengths, i = 3.9999
L/1
'J
58
but only 500 bit "chunks" were studied using different seed values to determine
what portion of the overall sequence was used. Using only truncated sections of
the overall period of each of these generators certainly seems justified in light of the
fact that there is no way to determine what portion of the entire sequence is obtained
from the logistic sequence generator. Finally, 500 bit lengths were again used in the
logistic sequences with no estimation as to how long the actual periods of these
sequences are.
The LRS sequences studied were generated using the software de
scribed in Appendix A. A 33 bit shift register generator with feedback taps from
stages 13 and 33 (see figure 2.2) was simulated. Sequences of length 500 bits were
removed from the otherwise 233l bit sequence by deciding where in the long se
quence to remove the continuous 500 bit shorter sequence. Four different 500 bit
sequences were extracted from the longer sequence and analyzed according to the
criteria given in Chapter 2. A summary of the results of this comparison analysis is
given in table 4.10. It is obvious that at least the first 500 bit "chunk" removed from
the longer LRS sequence lacks randomness. The index of discrimination (calculated
from the autocorrelation function) is much smaller than the ID values calculated for
all of the logistic sequences. A low ID value indicates a substantial minor correlation
peak in the autocorrelation function which is decidedly not noiselike. The other
three 500 bit sequences generated from the LRS sequence look more random, but
still have ID values that are generally lower than those associated with the logistic
sequences or the sequences generated from the random number generator. The
frequency distribution of ones and zeroes for the four LRS sequences are all within
the acceptable range for randomness (chisquare statistics calculated range between
the 5% and 95% confidence levels). However, many of the run lengths are much
Sequence Type Parameter Num Ones 250 Num Zeroes 250 Chi Square Runs of length 1 Runs of length 2 Longest Run ID
Ones 62.5 Zeroes 62.5 Ones 31.3 Zeroes 31.3 Ones 7 Zeroes 7
RNG 1000 277 223 5.83 59 55 26 38 16 9 444
RNG 1 2000 257 . 243 .392 52 58 41 32 8 6 444
RNG CA 3000 235 265 1.80 62 51 30 31 7 8 440
RNG 4000 255 245 .200 65 67 27 32 8 9 432
LRS 0 266 234 2.05 13 19 9 9 32 13 256
LRS 500 263 237 1.35 37 42 27 24 11 9 408
LRS a 10000 261 239 .968 57 66 28 25 9 7 396
LRS 50000 272 228 1.15 51 65 37 29 17 6 404
Logistic 3.9991 247 253 .072 67 69 32 29 7 7 428
Logistic 3.9993 251 249 .008 63 60 28 35 7 8 440
Logistic 3. 3.9996 231 269 2.89 63 59 26 27 6 9 428
Losistic 3.9999 251 249 .008 63 53 23 33 7 11 440
Table 4.10 Comparison of LRS, random number generator, and logistics squences
VO
60
longer than would be expected for a true pseudorandom sequence, especially in the
case of the first sequence.
The 500 bit sequences generated with the program module using the
Turbo Pascal random number generator displayed more randomness than the trun
cated LRS sequences did. The ID values for all four sequences were quite good
indicating only very small minor correlation peaks such as would be associated with
random noise. The frequency distribution of ones and zeroes was also in the accep
table range for randomness. With the exception of the first sequence, the run length
distributions also looked quite random. The first sequence had several runs of much
longer lengths than would be expected for a 500 bit sequence. It is not the fact that
these longer run lengths exist that is disturbing, just that so many were enountered in
this one sequence. An occasional run length that is much longer than expected
would be normal for a true random sequence, however, the first sequence has a total
of five runs that are longer than expected. Nonetheless, this sequence is still better
than the first truncated LRS sequence which had 12 runs with lengths longer than
expected.
Overall, based on comparisons with truncated LRS sequences and
truncated random number generator sequences, the logistic sequences seem to be
just as random as the other two if not more so. The 500 bit logistic sequences
created during these experiments showed high ID values (indicating noiselike
autocorrelation functions), good ones and zeroes frequency distributions, and
random run length distributions. Certainly based upon all the tests run during this
investigation, these sequences can be labeled pseudorandom.
CHAPTERS
CONCLUSIONS AND ADDITIONAL RESEARCH IDEAS
5.1 Summary and Conclusions
The purpose of this research effort was to explore the possibility of
using binary sequences generated from the logistic map for use as spectrum spread
ing codes. The statistical properties necessary for generating this type of code were
studied in Chapter 2. It was determined that spectrum spreading codes need to be
pseudorandom with a random frequency distribution of ones and Zeroes, a noiselike
autocorrelation function, and a random distribution of run lengths. In addition to
having good random statistical properties, codes generators useful for spread spec
trum communication systems need to be easy to implement, capable of creating a
large variety of different codes with only minor changes, and be able to generate
codes with a variety of lengths, especially the longer lengths. Once it was deter
mined what properties were required for the type of codes desired, the nature of the
logistic map was explored. The chaotic areas of the logistic map seemed as if they
might be capable of generating sequences with many of the desired properties.
Chapter 3 described the logistic equation used for code generation, and Chapter 4
described the results obtained during this research effort The logistic map has many
parameters which can be varied to create different sequences. It was found that
small variations in the initial value used to iterate the equation led to totally different
sequences being generated. This sensitive dependence upon initial conditions is due
to the chaotic nature of the logistic map. "Double" thresholding was found to
improve the statistical nature of the sequences generated, and the best areas to use
62
for sequence generations were found to be the mid range of x values. Even though
there are many periodic regions within the chaotic regions of the logistic map, if the
i parameter is kept close to four, most parameter values seem to lead to long
sequences with good random statistical properties. Finally, it was found that
generating longer sequences confirms the random nature of the codes created using
the logistic map. The primary question remains then, are these codes useful for
spectrum spreading purposes?
The codes generated using the logistic equation have good statistical
properties when certain constraints are observed. Codes generated using double
thresholding and i parameter values near four can be considered pseudorandom
based upon the criteria developed in Chapter 2. The fact that the logistic sequences
generated are pseudorandom certainly makes them a candidate for use as spectrum
spreading codes. It was also shown that a practically limitless numbert of different
codes can be generated by making small variations in initial conditions such as the
starting x value or the i parameter value. Without the limitation of finite precision
arithmetic, the number of possible different sequences would theoretically be
infinite. However, even given finite precision arithmetic the number of different
sequences possible is astronomical. Therefore, these sequences meet another
criterion for good spectrum spreading codes, namely that many different codes can
be generated by making only minor changes in the generator. The fact that the
sequences are quite random and there are so many different sequences possible also
seems to indicate that these codes might afford more security than the LRS
sequences that are frequently used as spectrum spreading codes. Finally, the
sequences generated using the logistic map are extremely easy to create in software.
The program module used to create the sequences for this study is less
63
than one page in length. Again, this is a plus for the generation of spectrum
spreading codes.
Nothing was found that would preclude the use of these codes for
spectrum spreading purposes. However, more research into actual implementation
issues needs to be done before conclusions can be drawn as to whether these codes
have practical applications in the spread spectrum communication area. (More dis
cussion on implementation issues is contained in the next section.) Certainly from
the research done here, these sequences look very promising for use as spectrum
spreading codes.
5.2 Avenues for Further Research
The research done here sparked many additional questions and possi
bilities for further research. While the sequences generated using the logistic map
look quite promising as spectrum spreading codes, could they also be used as en
cryption codes as well? Stream ciphers are encryption streams of binary bits that are
modulotwo added to the binary message being transmitted from sender to receiver
[18]. One method of creating stream ciphers is to use feedback shift register gen
erators. As seen when studying the linear recursive sequences in Chapter 2, non
linearities must be introduced to prevent easy decoding of these encryption streams.
Therefore, instead of using nonlinear feedback techniques with shift register gen
erators, why not use sequences generated from the logistic map? This research
effort has shown that sequences of extremely long lengths are possible making the
use of such sequences as encryption codes quite plausible. Of course, as part of the
effort to decide whether these sequences are suited for encryption purposes, work
must also be done to see how easily such sequences can be "broken" or decoded.
Another area of exploration generated from this research effort would be
the study of how other discrete maps could be used to produce binary sequences.
64
There are many more onedimensional unimodal functions that could be used in
place of the logistic map. In fact, other equations might prove even more useful than
the logistic equation. The function described by the following equation is chaotic in
the region 1 < X, < 2:
Xjc , x < 0.5
X(lx) , x > 0.5
This function is unimodal and behaves much like the logistic map except there are no
stable cycles present in the chaotic region. Another function that could be used is
given by:
ax , x < 1
ax1P , x > 1
This equation is chaotic in the region 2 < 0 < and also contains no stable cycles in
the chaotic region [9]. Since the width of the chaotic region is very wide, this
equation might provide wider windows of parameter values which lead to chaotic
trajectories, making the selection of appropriate tuning parameter values simpler.
Additionally, there is no reason why two and three dimensional discrete maps could
not be used to generate binary sequences as well [13].
Finally, an important question arises from this effort: how can these
codes be implemented for practical use? As stated earlier, before any real consider
ation can be given to using these sequences as spectrum spreading codes, imple
mentation issues must be addressed. Sequences from the logistic map (or other
discrete maps) can easily be implemented in software, but it may or may not be
practical in some situations to use a software implementation. Switched capacitor
circuits have been used to simulate onedimensional discrete maps [13,19]. An
implementation using circuits such as these might be more practical in some cases.
65
It seems that perhaps it is time to put our knowledge of chaotic systems
to work for us. Using chaotic trajectories to generate pseudorandom binary se
quences might very well be a good place to start
REFERENCES
[1] Robert C. Dixon, Spread Spectrum Systems. New York: John Wiley &
Sons, 1984.
[2] George R. Cooper and Clare D. McGillem. Modem Communications and
Spread Spectrum. New York: McGrawHill, 1986.
[3] Solomon W. Golomb, Shift Register Sequences. San Francisco, California:
HoldenDay, 1967.
[4] James Gleick, Chaos. Making a New Science. New York, New York:
Viking Penguin Inc., 1987.
[5] Turbo Pascal For the Mac. User's Guide and Reference Manual. Scotts
Valley, California: Borland International Inc., 1986.
[6] Stephen K. Park and Keith W. Miller, "Random Number Generators: Good
Ones Are Hard to Find," Communications of the ACM. Volume 31 Number
10, October 1988, pp. 11921201.
[7] R.N. Clark, "A Pseudorandom Number Generator," Simulation. November
1985, pp. 252255.
[8] Paul F. Hultquist, "Statistical Tests of a Random Number Generator,"
Simulation. August 1986, pp. 7274.
[9] Robert M May, "Simple Mathematical Models with Very Complicated
Dynamics," Nature. Volume 261, June 10,1976, pp. 459467.
[10] A. K. Dewdney, "Computer Recreations: Probing the Strange Attractions of
Chaos," Scientific American. July 1987, pp. 108111.
[11] Celso Grebogi, Edward Ott, and James A. Yorke, "Chaos, Strange
Attractors, and Fractal Basin Boundaries in Nonlinear Dynamics, Science.
Volume 238, October 30,1987, pp. 632638.
[12] Thomas S. Parker and Leon O. Chua, "Chaos: A Tutorial for Engineers,"
Proceedings of the IEEE. Volume 75 number 8, August 1987, pp.
9821008.
[13] Angel RodriguezVazquez, Jose L. Huertas, Adoracion Rueda, Belen
PerezVerdu, and Leon O. Chua, "Chaos from SwitchedCapacitor Circuits:
Discrete Maps," Proceedings of the IEEE. Volume 75 number 8, August
1987, pp. 10901106.
67
[14] Heinz Georg Shuster, Deterministic Chaos: An Introduction. Weinheim;
Basel; Cambridge; New York: VCH, 1988.
[15] TienYien Li and James York, "Period Three Implies Chaos," American
Mathematical Monthly. Volume 82, 1975, pp. 985992.
[16] Mitchell J. Feigenbaum, "Quantitative Universality for a Class of Nonlinear
Transformations," Journal of Statistical Physics. Volume 19, Number 1,
1978, pp. 2552.
[ 17] Donald E. Knuth, The Art of Computer Programming. Volume 2
Seminumerical Algorithms. Reading, Mass: AddisonWesley, 1981.
[18] William G. Chambers, Basics of Communications and Coding. New York:
Clarendon Press, Oxford University Press, 1985.
[19]
Takashi Matsumoto, "Chaos in Electronic Circuits," Proceedings of the
IEEE. Volume 75 number 8, August 1987, pp. 10331057.
APPENDIX A
CODE GENERATION AND ANALYSIS SOFTWARE
During the course of this investigation, it was necessary to develop
some software routines which would generate and analyze different types of codes.
Consequently, a package was developed in Turbo Pascal (Borland version 1.1) on
the Apple Macintosh to generate three different types of codes and to analyze these
codes for the three statistical properties of "randomness" described in Chapter 2.
This software enabled a detailed comparison of the statistical properties of the dif
ferent types of codes generated. The menu driven software contains three basic
types of routines; code generation routines, analysis routines, and report generating
routines. A second program, much shorter than the above package, was also written
to enable exploration of logistic sequences with very long lengths. The purpose of
this chapter is to briefly describe the capabilities of these two pieces of software, and
to explain the various algorithms developed to do statistical analysis on the codes
generated. Sections A.1 through A.3 contain descriptions of the main software
package, while section A.4 elaborates on the program to generate logistic sequences
with very long lengths. (The actual software code is contained in Appendices B and
C.)
A.1 Code Generation
Three different kinds of codes can be generated with this software.
There are routines to generate linear recursive sequences, routines to generate
sequences from a thresholded random number generator, and routines to generate
sequences from the chaotic logistic equation. The first two types of sequences were
69
generated to allow comparisons of statistical properties to be made with the
sequences generated from the logistic equation. The software enables the user to
generate two sequences and store them both in memory in separate arrays. The
maximum length for each sequence is 4000 bits.
Linear recursive sequence (LRS) generation was incorporated into the
software for two reasons. First, because the statistical properties of these sequences
are so well known, LRS sequences were useful for testing the analysis routines to
ensure their correctness. Secondly, LRS sequences are invaluable for comparison
purposes with other types of sequences generated because of their excellent
"noiselike" properties. The software allows the user to select the number of stages
in the shift register generator (forty stages maximum), the length of the sequence
(four thousand bits maximum), the starting position of the sequence, and the
feedback taps desired. (Tables of appropriate feedback taps to generate maximal
length sequences can be found in many sources [1].) Once the code is generated, it
is stored in one of two code arrays which can be printed or sent to the analysis and
reporting routines.
A routine to generate sequences from a "thresholded" random number
generator was also included in the software package. Again, this type of sequence
was used primarily to explore the statistical properties of binary sequences asso
ciated with "randomness". The random number generator uses the algorithm [5]:
NewX = (75 OldX) mod (231 1)
While the algorithm associated with this random number generator is not deemed
one of the better algorithms, it proved quite adequate for the purposes of this
experimentation effort [6]. Once the random number is generated, it is divided by
the period of the generator (231 1) to obtain a number between zero and one. This
value is then thresholded at 0.5 creating a sequence of ones and zeroes. For the
70
purposes of this research effort, the. resulting sequences proved to be random
enough. The routine also allows the user to select the initial "seed" for the generator
and the length of the code to be generated (four thousand bits maximum). Again,
the code is stored in one of two arrays for further processing and analysis.
Finally, the third code (and one of primary interest) was generated using
the logistic equation and thresholding functions. Recalling the logistic equation:
Xn+l = l^nC1 *n)
this routine allows the user to select an initial value for Xg, a value for ji, whether to
iterate the equation a number of times before generating die sequence, the sequence
length, and values for the two threshold functions. The primary threshold function
simply "rounds" the xn+1 value to a one if this value is greater than or equal to the set
threshold value, and down to a zero if the Xg+1 value is less than the set threshold
value. The user can select values for the secondary threshold function as well. This
threshold function allows the user to set upper and lower limits on the values of xn+1
that are used in the generation of the binary sequence. This secondary thresholding
function was added to obtain more statistically random and balanced sequences from
the logistic equation. In addition, the routine gives the user the option of printing the
Xg values associated with each member of the sequence. During the course of this
investigation, the effects of varying each of these parameters on the generated
sequence was studied so it was necessary that the user be able to select values for
each of these various parameters.
A.2 Analysis Subroutines
Several analysis subroutines are included in this software package. The
analysis subroutines allow the user to investigate the "randomness" of the sequences
created by the code generation subroutines. The analysis subroutines include a
module to analyze the number of ones and zeroes in a sequence, a module to explore
71
the run length distributions of these sequences, a module to calculate and plot the
autocorrelation function of the generated sequences, a module to calculate the index
of discrimination of a sequence, and modules to calculate and plot crosscorrelation
functions of two different sequences.
The module that calculates the number of ones and zeroes in a sequence
also calculates the run length distributions of the sequence. The routine requests
information from the user as to whether sequence number one or sequence number
two is to be analyzed, and what the length of this sequence is. The routine then
allows the user the option of printing the results on the screen or obtaining a hard
copy printout of the results.
Another module is used to calculate both the autocorrelation function
and the index of discrimination of the user selected sequence. The module uses the
algorithm described in Chapter Two for generating the autocorrelation function.
The equation used to calculate this function is:
p
c(t)=
ft =1
(The routine assumes +ls and Is for ease of computation, therefore the Os in the
generated sequences are converted to Is before the autocorrelation function is
computed.) A shifted duplicate of the sequence is compared to the actual sequence
on a bit by bit basis. The number of disagreements between bits is subtracted from
the number of agreements to obtain the value of the autocorrelation function at that
particular shift value. The maximum value of the autocorrelation function is always
the length of the sequence. This maximum value occurs at the zero shift point (x=0).
The module then calculates the index of discrimination which is a single value. This
ID value is the difference between the maximum peak of the autocorrelation
function and the second highest peak [1]. (In general, the higher the value of the
index of discrimination, the better the sequence is for communication purposes.)
72
After both the autocorrelation function and the index of discrimination are
calculated, the module allows the user to select a screen or hardcopy printout of the
results. Because the autocorrelation function could be quite lengthy, the module
also allows the user to select whether or not to actually print the autocoirelation
function or whether to just print the index of discrimination value.
The final analysis routine available to the user calculates a
crosscorrelation function between two previously generated sequences. In order to
calculate a crosscorrelation function between two sequences, the sequences must be
the same length. The crosscorrelation function is calculated exactly like the
autocorrelation function with one shifted sequence being compared to the second
sequence which is not shifted. Again, the difference between the number of
agreements and disagreements becomes the value of the function at the particular
shift point As in the other analysis routines, the user may select a screen or
hardcopy printout of the results.
The output from the autocorrelation and crosscorrelation modules is
simply a tabulation of the function values. However, for the most part, both cor
relation functions are easier to understand when they are plotted, therefore a routine
was developed to allow these functions to be plotted. This plotting routine is
discussed in the next section.
A.3 Reporting Subroutines
In addition to the hardcopy reporting of the analysis subroutines, there
are two subroutines that deal strictly with the output of data: the code printing
subroutine, and the correlation plotting subroutine.
The code printing subroutine simply allows the user to get a hardcopy
printout of either code number one or code number two. The user selects the desired
code for hardcopy printout and then enters the length of this code. The generated
73
code is then sent to the printer. Each of the code generation subroutines also allows
the user to access this printout module if desired.
The plotting subroutine allows the user to obtain a screen or hardcopy
printout of the plotted autocorrelation or crosscorrelation functions. The routine
requests that the user select either the autoconelation or crosscorrelation function
for plotting, and also requests the length of the particular correlation function. In
addition, the user can specify how much of the function should be plotted at any one
time. For example, if the autocorrelation function has 1000 points, the user may
wish to plot only 500 points at a time so that all the points can appear on the screen
at once. The user can request points 1 through 500 be plotted and then make a
second plot of points 501 through 1000. The subroutine automatically scales the
plots in the vertical direction based upon the maximum value of the correlation
function. Maximum and minimum values of each plot are printed at the bottom of
the plot for comparison purposes.
A.4 Lone Logistic Code Generation
At one point in this research, the 4000 bits maximum sequence length
became a limitation in the type of analysis that could be performed on the logistic
sequences. Consequently, a short program was written to enable the creation of
sequences from this equation with an unlimited maximum length. (This was
accomplished by not storing the generated sequence in an array.) In addition to
sequence generation, this program also enables some analysis to be done on the
sequence as it is created. Another function of the program is to "plot" these
sequences on the screen so the user can look for nonrandom patterns that might
develop.
Since there is not a maximum length to the sequences that can be
generated using this program, the user must input the length of sequence desired.
74
(A length of 124,800 bits will exactly fill the screen the way this program is set up.)
As the sequence is generated, the number of ones and zeroes are calculated along
with the run length distribution. The algorithm for doing this analysis is identical to
that which was used in the main software package with the exception that in this
program the algorithm works on the sequence as its generated, not on the stored
sequence after generation. Because the sequence is not stored anywhere during
creation, it is not possible to calculate any correlation functions for these lengthy
sequences.
During the sequence generation, if the bit created is a 1 the next pixel on
the screen is darkened. If the bit created is a zero, the pixel remains white. This plot
is built as the program runs and generates the sequence. The routine for plotting is
set up such that there are 480 pixels in the horizontal direction and 260 pixels in the
vertical direction. The maximum length sequence that will fit on the screen at any
one time then is 124,800 bits. Certainly longer sequences can be generated with this
program, but not all the sequence can be seen in the plotting routine.
The program runs by first asking for user input on such items as
sequence length, value for i, starting and stopping values for x,,, a threshold value
for creating the binary sequence, and an initial seed value for starting the sequence.
The user is also allowed the option of iterating the logistic equation before Xq values
are used for sequence generation. While the program runs, the sequence is being
"plotted" to the screen. When the sequence generation is finished, the program
waits for a keypress to enable the user to send the finished plot to the printer if
desired. Once any key is pressed, the program then sends the analysis data to the
printer for hardcopy reporting of the results.
APPENDIX B
CODE GENERATION AND ANALYSIS PROGRAM
program codemaker2(input,output);
uses PasPrinter,Sane,Memtypes,Quickdraw;
{This program was written in TurboPascal Version 1.1 by Borland on an Apple
Macintosh with 512K memory. The system has two disk drives, one 800K drive
internal to the unit and one external 800K drive.}
const
regsize=35;
codelength=4000;
type
code=airay[l..codelength] of integer;
register=airay[l..regsize] of integer,
var
codeonearray, codetwoairay, autocorairay, crosscorarray:code;
maxregister:register,
codeoneflag, codetwoflag, progendflag, autocorflag, crosscorflagrboolean;
maincounfcinteger,
printer,outfile: text;
function exorgate(inl ,in2:integer):integer,
var tempi,temp2:integer;
{This function simply does an exclusiveor on the inputs it receives and
returns the result This function is called by the linear recursive sequence
generating routine.}
begin
templ:=inl+in2;
if odd(templ) then
temp2:=l
else
temp2:=0;
exorgate:=temp2
end;
76
function threshold(x,t:real):integer,
var temp:integer,
{This function is the threshold function that turns real values into a binary
sequence depending upon the value of the threshold (t) that is sent to the
function.}
begin
if x
temp:=0
else
temp:=l;
threshold:=temp
end;
function maxairayitem(startnum,stopnum,arraynum,actcodelength:integer):integer;
var
i,temp:integer,
{This function finds the maximum value in the autocorrelation array and
returns this value to the calling routine. The autocorrelation and plotting
routines use this function.}
begin
temp:= l*acteodelength;
for i:=startnum to stopnum do
begin
if array num=l then
begin
if autocorarray[i] > temp
then temp:= autocorarray[i]
end;
if arraynum=2 then
begin
if crosscorarray[i]>temp then
temp:= crosscorarray[i]
end;
end;
maxanayitem:=temp;
end;
77
function minairayitem(startnum,stopnum,arraynum,actcodelength:integer):integer;
var
i,temp:integer,
{This function finds the minimum value in an array and returns this value to
the calling routine. The plotting routine uses this function.}
begin
temp:=actcodelength;
for i:=startnum to stopnum do
begin
if arraynum=l then
begin
if autocorarray[i]
temp:= autocorarray[i]
end;
if arraynum=2 then
begin
if crosscorairay[i]
temp:= crosscorairay[i]
end;
end;
minairayitem:=temp
procedure printcode(actcodelength,codenum:integer);
var
j,k,selection:integer;
{This procedure allows the user to obtain either a hardcopy or a screen print
of either code number one or code number two. This procedure is called by
all of the code generation routines. If it is desired to print out a code from
the main menu, the procedure printcodestart is called from the main menu
routine and that procedure calls this procedure.}
begin
repeat
writelnCFor hardcopy print enter 1: For screen print enter 2:');
readln(selection);
until (selection>0) and (selection<3);
if selections 1 then
begin
rewrite(outfile,'code T);
writeln(outfile,The generated code is:');
writeln(outfile);
k:=0;
for j:=l to acteodelength do
begin
k:=k+l;
if codenum=l then
write(outfile,codeonearray[j])
else
write(outfile,codetwoairay [j]);
if k>80 then
begin
k:=0;
writeln(outfile)
end;
end;
writeln(outflle);
writeln(outfile);
writeln(outfile);
end;
if selection=2 then
begin
writeln(The generated code is:');
writeln;
for j:=l to actcodelength do
begin
if codenum=l then
write(codeonearray[j])
else
write(codetwoarray[j]);
end;
writeln;
readln;
end;
if selection=l then close(outfile);
procedure printcodestart;
var
codenum,actcodelength:integer,
{This procedure is a precursor to the printcode procedure. This procedure
obtains input from the user on which code is to be printed, the length of this
code and sends this information to the printcode procedure. This procedure
is called by the main menu routine.}
begin
clearscreen;
writeln(Please enter code to be printed (1 of 2)');
readln(codenum);
writelnCPlease enter length of code');
readln(actcodelength);
printcode(acteodelength,codenum);
end;
procedure linrnax(codenum:integer);
var
tempi, i, temp2, numtaps, reglength, actcodelength, selection:integer,
tap:anay[l. jegsize] of integer;
iterations, j:longint;
{This routine generates a linear recursive sequence with user specified feed
back taps and code length. Once the code is generated, the routine calls the
printcode procedure to print the code to the screen or the printer.}
begin
clears creen;
writelnCPlease enter the register size');
readln(reglength);
writelnCPlease enter the codelength');
readln(acteodelength);
writeln(Please enter starting point for code');
readln(iterations);
writelnCPlease enter number of feedback taps');
readln(numtaps);
writelnCPlease enter feedback taps');
for i:=l to numtaps do
begin
readln(tap[i])
end;
for i:=l to regsize do
begin
maxregister[i]:=l
end;
if iterations>0 then
for j:=l to iterations do
begin
temp2:=0;
for i:=l to numtaps do
temp2:=exorgate(maxregister[tap[i]],temp2);
for i:=reglength downto 2 do
maxregister[i]: =maxregister[i1];
maxregister[ 1] :=temp2
end;
for j:=l to actcodelength do
begin
80
temp2:=0;
for i:=l to numtaps do
temp2:=exorgate(maxregister[tap[i]],temp2);
if codenum=l then
codeoneairay[j]:=maxregister[reglength]
else
codetwoairay [j] :=maxregister[reglength];
for i:=reglength downto 2 do
maxregister [i] :=maxregister[i1];
maxregister[ 1 ] :=temp2
end;
if codenum= 1 then
codeoneflag:=true
else
codetwoflag:=true;
printcode(actcodelength,codenum);
procedure logistic(codenum:integer);
var
t:real;
actcodelengthj, temp, selection, itflag,xflag,iterations:integer,
x,mu,lowerbound,upperbound:extended;
{This procedure generates a binary sequence using the logistic equation. The
user selects a value for the parameter mu, the starting x value, a value for
the maximum and minimum values of x to be used for the sequence, a threshold
value for determining which values of x become Is and which values become Os,
a code length, how many iterations before the code is generated, etc. This
procedure calls the printcode routine to allow the display of the code gener
ated on either the screen or the printer.}
begin
clearscreen;
writelnOPlease enter a value for mu');
readln(mu);
writeln(Please enter a starting value for x between 0 and 1*);
readln(x);
writelnOPlease enter the lower bound on x');
readln(lowerbound);
writelnOPlease enter the upper bound on x');
readln(upperbound);
writeln(Tlease enter a threshold for function');
readln(t);
writelnOPlease enter a code length');
readln(actcodelength);
writelnCPlease enter a 1 for x values and a 0 for no x values');
ieadln(xflag);
writeln(Please enter a 1 for iterations and a 0 for no iterations');
readln(itflag);
if itflag=l then
begin
writelnCHow many iterations?');
readln(iterations)
end;
for j:=l to codelength do
begin
if codenum=l then
codeoneairay[j]:=0
else
codetwoarray[j]:=0
end;
if itflag=l then
for j:=l to iterations do
x:=mu*x mu*x*x;
if xflag=l then
rewrite(outfile,'Starting values 5');
j:=l;
while (j
begin
x:=mu*x mu*x*x;
if xflag=l then
write(outfile,x: 18:17, ');
if (x>lowerbound) and (x
begin
temp:=threshold(x,t);
if xflag=l then
write(outfile,temp);
if codenum=l then
codeoneairay [j] :=temp
else
codetwoarray [j] :=temp;
j:=j+l
end;
if xflag=l then
writeln(outfile);
end;
if codenum=l then
codeoneflag:=true
else
codetwoflag:=true;
82
printcode(actcodelength,codenum);
if xflag=l then close(outfile);
end;
procedure randseq(codenum:integer);
var
ij,temp2,actcodelength,selection:integer,
temp 1 ^extended;
{This procedure generates a binary sequence from the random number generator.
The user is asked for a starting seed and a codelength. Once the code is gen
erated, the routine calls the printcode procedure as in the other code gen
eration routines.}
begin
clearscieen;
writelnCPlease enter a seed for the random number generator);
readln(k);
writelnCPlease enter the desired codelength');
readln(actcodelength);
for i:=l to actcodelength do
begin
k:=k+l;
tempi :=randomx(k);
temp 1 :=temp1/2147483646;
temp2:=iound(templ);
if codenum=l then
codeonearray [i] :=temp2
else
codetwoairay [i] :=temp2;
end;
if codenum=l then
codeoneflag:=true
else
codetwoflag:=true;
prmtcode(actcodelength,codenum);
end;
83
procedure
printanalyze(onescount,zeroscount,actcodelength:integer;onesrun,zerosrun:code);
var
selection,i:integer,
{This routine is called by the code analysis routines (analyzeone and analyzetwo).
This routine allows the analysis information on the codes to be printed either
to the screen or to the printer. The analysis information passed to this
routine includes the number of ones and zeros in the code and the run length
distribution of the code.}
begin
repeat
writeln(lf hardcopy output desired, enter 1: For screen print, enter 2');
readln(selection);
until (selection>0) and (selection<3);
if selections 1 then
begin
rewrite(outfile,Temp 2');
writeln(outfile,The number of ones is: '.onescount);
writeln(outfile,The number of zeros is: ,zeroscount);
writeln(outfile);
writeln(outfile);
for i:=l to actcodelength do
begin
if onesrun[i]<>0 then
writeln(outfile,The number of runs of ones of length ',i,' are:
,onesrun[i]);
if zerosrun[i]<>0 then
writeln(outfile,The number of runs of zeros of length '4/ are:
,zerosrun[i]);
end;
writeln(outfile);
writeln(outfile);
writeln(outfile);
end;
if selection=2 then
begin
writeln(The number of ones is:',onescount);
writeln(The number of zeros is: ',zeroscount);
writeln;
writeln;
readln;
for i:=l to actcodelength do
begin
if onesrun[i]<>0 then
writeln(The number of runs of ones of length ',i,' are: ,onesrun[i]);
if zerosrun[i]<>0 then
84
writeln('The number of runs of zeros of length ',i,' are: ,zerosrun[i]);
end;
readln;
end;
if selection=l then close(outfile);
end;
procedure analyzeone(actcodelength:integer);
var
onesrun,zerosrun:code;
i,onescount,zeroscount,onesruncount,zerosruncount:integer;
{This routine analyzes the contents of sequence or code number one. The
routine begins by initializing two arrays called onesrun and zerosrun to all
zeroes. The counters to keep track of the number of ones and zeroes and the
length of runs of each of these states are also initialized to zero. The
variables onescount and zeroscount keep track of the number of ones and zeros
in the code as this routine goes through the array that contains the code.
The arrays onesrun and zerosrun keep track of the number of runs of a particular
length of either ones or zeroes. For example, if the routine encounters a
run of ones of length 5, it will increment position five of the onesrun array
so that the new value of onesrun[5] will be the old value plus one. When the
routine is finished, the number of runs of ones of length 1 will be stored in
onesrun[l], the number of runs of ones of length 2 will be stored in
onesrun[2], etc. The same is true for the run lengths of the zeros state.
The routine calls the procedure printanalyze to print out the results that
were determined during the execution of this routine.}
begin
for i:=l to actcodelength do
begin
onesrun[i]:=0;
zerosrun[i]:=0
end;
onescount:=0;
zeroscount=0;
onesruncount:=0;
zerosruncount:=0;
if codeonearray[l]=l then
begin
onescount:=onescount+1;
onesruncount:=onesruncount+1
end;
if codeonearray[l]=0 then
begin
zeroscount:=zeroscount+1;
zerosruncount=zerosruncount+1
85
end;
for i:=2 to actcodelength do
begin
if codeoneairay[i]=codeoneairay[il] then
begin
if codeonearray[i]=l then
begin
onescount:=onescount+1;
onesruncount:=onesruncount+1;
end;
if codeoneairay[i]=0 then
begin
zeroscount:=zeroscount+1;
zerosruncount:=zerosruncount+1
end;
end
else
begin
if codeoneairay[i]=l then
begin
zerosrunfzerosruncount] :=zerosrun[zerosruncount]+1;
zerosruncount:=0;
onesruncount:=onesruncount+1;
onescount:=onescount+1;
end;
if codeonearray[i]=0 then
begin
onesrun[onesruncount] :=onesrun[onesruncount]+1;
onesruncount:=0;
zerosruncount:=zerosruncount+1;
zeroscount:=zeroscount+1;
end;
end;
end;
if onesruncountoO then
onesrun[onesruncount]:=onesrun[onesruncount]+l;
if zerosruncountoO then
zerosrun[zerosruncount]:=zerosrun[zerosruncount]+l;
printanalyze(onescount,zeroscount,actcodelength,onesrun,zerosrun);
procedure analyzetwo(actcodelength:integer);
var
onesrun,zerosrun:code;
i,onescount,zeroscount,onesruncount,zerosruncount:integer;
{This routine is identical to analyzeone except that this routine analyzes
the contents of sequence or code number two. The routine begins by
initializing two arrays called onesrun and zerosrun to all zeroes. The
counters to keep track of the number of ones and zeroes and thelength of runs
of each of these states are also initialized to zero. The variables
onescount and zeroscount keep track of the number of ones and zeros in the
code as this routine goes through the array that contains the code. The
arrays onesrun and zerosrun keep track of the number of runs of a particular
length of either ones or zeroes. For example, if the routine encounters a
run of ones of length 5, it will increment position five of the onesrun array
so that the new value of onesrun [5] will be the old value plus one. When the
routine is finished, the number of runs of ones of length 1 will be stored in
onesrun[l], the number of runs of ones of length 2 will be stored in
onesrun[2], etc. The same is true for the run lengths of the zeros state.
The routine calls the procedure printanalyze to. print out the results that
were determined during the execution of this routine.}
begin
for i:=l to actcodelength do
begin
onesrun[i]:=0;
zerosrun[i]:=0
end;
onescount:=0;
zeroscount =0;
onesruncount:=0;
zerosruncount:=0;
if codetwoarray[l]=l then
begin
onescount:=onescount+1;
onesruncount:=onesruncount+1
end;
if codetwoarray[l]=0 then
begin
zeroscount:=zeroscount+1;
zerosruncount=zerosruncount+1
end;
for i:=2 to actcodelength do
begin
if codetwoarray[i]=codetwoarray[il] then
begin
if codetwoarray[i]=l then
begin
onescount:=onescount+1;
onesruncount:=onesruncount+1;
end;
if codetwoarray[i]=0 then
begin
zeroscount=zeroscount+1;
zerosruncount:=zerosruncount+1
end;
end
else
begin
if codetwoarray[i]=l then
begin
zerosrun[zerosruncount] :=zerosrun[zerosruncount]+1;
zerosruncount=0;
onesruncount:=onesruncount+1;
onescount:=onescount+1;
end;
if codetwoarray [i] =0 then
begin
onesrun[onesruncount] :=onesrun[onesruncount]+1;
onesruncount:=0;
zerosruncount:=zerosruncount+1;
zeroscount:=zeroscount+1;
end;
end;
end;
if onesruncountoO then
onesrun[onesruncount]:=onesrun[onesruncount]+l;
if zerosruncountoO then
zerosrun[zerosruncount] :=zerosmn[zerosruncount]+1;
printanalyze(onescount,zeroscount,actcodelength,onesrun,zerosrun);
procedure analyzes tart;
var
codenum,actcodelength:integer,
{This routine is called by the main menu routine when the user selects the
analyze code function on the menu. This short routine determines which
code is to be analyzed and the length of that particular code. The routine
then calls either analyzeone or analyze two depending upon which code is to
be analyzed.}
begin
clearscreen;
writelnCWhich code do you want to analyze? (1 or 2)');
readln(codenum);
wiiteln(Tlease enter the codelength);
readln(actcodelength);
if codenum=l then
analyzeone(actcodelength)
88
else
analyzetwo(actcodelength);
end;
procedure autocor,
var
i,j,k,temp 1.agree,disagree,codenum,choice,idvalue,actcodelength:integer;
tempxode;
startnum,stopnum,counter,airaynum,selection:integer;
exitflag:boolean;
label 10;
{This routine calculates both the autocorrelation function and the index of
discrimination value. This routine is called from the main menu. The routine
first checks that the code for which the autocorrelation function has been
requested has been generated. The routine then proceeds to calculate the
autocorrelation function based upon the number of agreements minus the num
ber of disagreements encountered when the code is compared to a shifted ver
sion of itself. The length of the autocorrelation function is the length
of the code itself. Once the autocorrelation function has been calculated,
the index of discrimination value is determined by callin the maxarrayitem
function to determine the second highest peak of the autocorrelation fun
ction. The printout of this calculated information is then done. The user
can select whether to print out both the autocorrelation function (tabulation
of values) or just the index of discrimination value.)
begin
exitflag:=false;
clearscreen;
writeln('Please enter code to be autocorrelated (1 or 2)');
readln(codenum);
writeln(Tlease enter the length of this code');
readln(actcodelength);
if codenum=l then
if not codeoneflag then
exitflag:=true;
if codenum=2 then
if not codetwoflag then
exitflag:=true;
if exitflag then
begin
writeln(The code you selected has not been generated');
goto 10
end;
for i:=l to actcodelength do
begin
if codenum=l then
temp[i]: =codeonearray [i]
else
temp[i]:=codetwoairay[i];
end;
for j:=l to actcodelength do
begin
agree:=0;
disagree :=0;
for i:=l to actcodelength do
begin
if codenum=l then
begin
if codeoneairay[i]=temp[i] then
agree:=agree+l
else
disagree:=disagree+1;
end;
if codenum=2 then
begin
if codetwoairay [i]=temp[i] then
agree:=agree+l
else
disagree:=disagree+1
end;
end;
autocorairay[j]:=agreedisagree;
templ:=temp[actcodelength];
for k:=actcodelength downto 2 do
begin
temp[k] :=temp[k1]
end;
temp[l]:=templ
end;
anraynum:=l;
startnum:=2;
stopnum:=actcodelength;
idvalue:=actcodelength 
maxarrayitem(startnum,stopnum,arraynum,actcodelength);
repeat
writelnCFor hardcopy print enter 1: For screen print enter 2:');
readln(selection);
until (selection>0) and (selection<3);
repeat
writelnCFor printout of autocorrelation function and ID value enter 1: For ID
value only enter 2;');
readln(choice);
until (choice>0) and (choice<3);
if selection=l then
begin
rewrite(printer,'printer:');
writeln(printer,'The ID value of the selected code is: .idvalue);
writeln(printer);
if choice=l then
begin
writeln(printer,The autocorrelation function is:');
writeln(printer);
counten=0;
for i:=l to actcodelength do
begin
write(printer,autocorairay[i],',');
counter.=counter+1;
if counter>24 then
begin
counter:=0;
writeln(printer,");
end;
end;
writeln(printer,");
end;
end;
if selection=2 then
begin
writeln(The ID value of the selected code is: '.idvalue);
writeln;
if choice=l then
begin
writeln(The Autocorrelation function is:');
writeln;
for i:=l to actcodelength do
begin
write(autocorarray[i],',')
end;
writeln;
end;
readln;
end;
10:
end;
procedure crosscor,
var
i,j,k, tempi, agree, disagree, codenum, actcodelength, selection, counteninteger;
temp:code;
exitflag:boolean;
91
label 10;
{This routine calculates the crosscorrelation function between two sequences
of the same length. The algorithm used to determine the crosscorrelation
function is identical to that used to determine the autocorrelation function.
Once the crosscorrelation function has been computed, the user is allowed the
option of either printing the crosscorrelation function on the screen or
sending the tabulated values to the printer.}
begin
exitflag:=false;
clearscreen;
writeln(Tlease enter the length of the codes to be correlated');
readln(actcodelength);
if not codeoneflag then
exitflag:=true;
if not codetwoflag then
exitflag:=true;
if exitflag then
begin
writeln('One of the codes you selected has not been generated');
goto 10
end;
for i:=l to actcodelength do
temp[i] :=codeonearray [i];
for j:=l to actcodelength do
begin
agree:=0;
disagree:=0;
for i:=l to actcodelength do
begin
if codetwoairay [i]=temp[i] then
agree :=agree+l
else
disagree:=disagree+1;
end;
crosscorarray [j] :=agreedisagree;
tempi:=temp[actcodelength];
for k:=actcodelength downto 2 do
begin
temp[k]:=temp[kl]
end;
temp[l]:=templ
end;
repeat
writelnCFor hardcopy print enter 1: For screen print enter 2:');
readln(selection);
until (selection>0) and (selection<3);
if selection=l then
begin
rewrite(printer,'printer:');
writeln(printer,'The cross correlation function is:');
writeln(printer);
counter:=0;
for i:=l to actcodelength do
begin
write(printer,crosscorairay[i],',');
counter:=counter+1;
if counter>24 then
begin
counter=0;
writeln(printer,");
end;
end;
writeln(printer,");
end;
if selection=2 then
begin
for i:=l to actcodelength do
begin
write(crosscorarray[i],',')
end;
writeln;
readln;
end;
10:
end;
procedure plotfunc(menuitem:integer);
var
temp,i,maxnum, minnum,figurenum, actcodelength, startnum:integer,
horizscalefact,xfact,stopnum:integer,
vertscalefacfcreal;
{This procedure plots either the autocoirelation or crossconelation
functions. This procedure is called by the initplot procedure. The function
allows the user to determine what part of the correlation function to plot
to the screen. Different sections can be plotted if the correlation function
is too long to fit onto one screen. The procedure does automatic scaling on
both the x and y axes. Hardcopy of the results of this procedure have been
obtained by doing a printscreen.}
begin
clearscreen;
writeln(Tlease enter the length of the correlation function');
readln(actcodelength);

