**Project Report**

**Vijay Sekhri**

**CMPS619**

######### PART ONE

# 

# Acknowledgement

I would like to thank Dr. TRN Rao who gave me the opportunity to take a
research course under him. His course was very beneficial for me, and I
appreciate his presence. Further I would like to thank my manager Mr.
Nol Premasathian  who continues providing help to me in building this
software project.

**Aim**: To test the randomness of given sequences.

**Introduction:**

**Random**

> In plain English Random means having no specific pattern, purpose, or
> objective. In Mathematics Random means an event in which all outcomes
> are equally likely.

**Randomness**

Randomness is the property of being Random.

**What is Random Sequence? \[Knuth et al\]**

The mathematical theory of probability and statistics carefully avoids
answering the question. It refrains from making absolute statements, and
instead expresses everything in terms of how much probability is to be
attached to statement involving random sequence of independent events.
Following are two statements given by two different authors:

> D. H. Lehmer (1951): "*A random sequence is a vague notion embodying
> the idea of a sequence in which each term is unpredictable to the
> uninitiated and whose digits pass a certain number of tests,
> traditional with statisticians and depending somewhat on the uses to
> which the sequence is to be put*"
>
> J.N Franklin (1962): "*The sequence (1) is random if it has every
> property that is shared by all infinite sequence of independent
> samples of random variables from the uniform distribution*."
>
> Random numbers are used for variety of purposes including computer
> games but they are also used on a more serious scale for the
> generation of cryptographic keys and for some classes of scientific
> experiments. For cryptographic use, however, it is important that the
> numbers used to generate keys are not just seemingly random; they must
> be truly unpredictable.
>
> Generating a truly random sequence is nearly impossible. Using
> arithmetic techniques to produce random sequence is computationally
> expensive and difficult. One such tool for generation random sequence
> is **Linear Feedback Shift Registers (LFSR)**, which in itself has
> some limitations. The basic operation of LFSR will be explained later
> in this report. One major drawback being that the sequence has a
> period after which it repeats itself. However, no algorithm using a
> finite state machine can produce a truly random sequence, since the
> finiteness forces the sequence to be periodic. The best we can do is
> to use very long period sequences, called ***pseudo-random
> sequences.***
>
> John Von Neumann (1951) -- *Anyone who considers arithmetical methods
> of producing random digits is, of course, in a state of sin*.
>
> There are various Cryptographic algorithms, which use these random
> numbers and sequences, and the most demanding of them all is **One
> Time Pad.** The important property of One Time Pad is that it needs as
> many random bits as a key as there are bits of information. In essence
> randomness is the soul for cryptology.
>
> **Randomness Tests by Knuth**

A)  **Chi-Square Test**. This test is perhaps the best known of all
    statistical tests, and it is the basic method that is used with many
    other tests. Let us consider and example of throwing dice to
    illustrate the Chi Square test.

> When we have just one dice we know that the probability of outcome of
> every event is same that is 1/6. If we have two dice then there are 11
> possible outcomes and the probability of occurrence of events differs.
> So we will consider a two dice throwing experiment here. Let s be the
> sum of numbers on the two dice and ps be the probability of occurrence
> of that sum. The probability distribution of each event is given as
> follows:
>
> Table1

  ----------------------------------- -----------------------------------
  s                                   ps

  2                                   1/36

  3                                   1/18

  4                                   1/12

  5                                   1/9

  6                                   5/36

  7                                   1/6

  8                                   5/36

  9                                   1/9

  10                                  1/12

  11                                  1/18

  12                                  1/36
  ----------------------------------- -----------------------------------

> If we throw the dice n time such that n is a big number then s will
> tend to be equal to nps. Lets assume that Ys is the observed number.
> For an experiment one, lets assume the following outcomes and values
> of n=144.
>
> Table 2

  ----------------------- ----------------------- -----------------------
  s                       Ys                      nps

  2                       2                       4

  3                       4                       8

  4                       10                      12

  5                       12                      16

  6                       22                      20

  7                       29                      24

  8                       21                      20

  9                       15                      16

  10                      14                      12

  11                      9                       8

  12                      6                       4
  ----------------------- ----------------------- -----------------------

We can see that the observed number is different from the expected
number. So if we take the square of differences between the observed and
expected values we will come up with a number that indicated variance
from the expected behavior. So if we define V as

2 2 2

V= (Y2-np2)+ (Y3-np3)+.....+ (Y12-np12)

It indicated the variance from the expected behavior. But note here that
(Y7-np7) is more likely to occur than (Y2-np2), but we have given equal
weight age to both of them. In actual practice we should give (Y7-np7)
1/6 as much importance as (Y2-np2). So we should change the formula for
V as follows:

2 2 2

V= (Y2-np2)+ (Y3-np3)+.....+ (Y12-np12)

\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\--
\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\--
\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\--

np2 np3 np12

Now V represents the actual variance from the expected behavior. Using
the data from

2 2 2

V= (2-4)+ (4-8)+.....+ (6-4) = 343

\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-- \-\-\-\-\-\-\-\-\-\-\-\-\--
\-\-\-\-\-\-\-\-\-\-\-- \-\-\-\-\-\-\-\-\-\-\-\-\--

4 8 4 48

Now the **main point** to be noted here is that is the quantity V good
or bad for the experiment. Well as we can see that V denotes the
variance from the expected behavior, we can state that if V approaches
zero that means the sequence is behaving exactly as expected and cannot
be termed as random. On the other hand if V approaches a very big number
that of course has some limit, it means that the result of experiment is
being predictable again. In other words it will again be showing
significant departure from random behavior. So the good value for V
would be not very low and not very high. High and low V will be in
respect with degrees of freedom, which in this case is 11. The value of
V should lie close to 50% range in the table specified by Knuth (The art
of computer programming, page 39). If there are k degrees of freedom
then we look at k-1 row of the table specified by Knuth.

\[Knuth et al\] We can summarize the chi-square test as follows. A
fairly large number, n of independent observation is made. We count the
number of observations falling into each of k categories, and compute
the quantity V given by the formula above. Then V is compared with
numbers in table given by Knuth (with v=k-1). If V is less than the
99-percent entry or greater than 1 percent entry, we reject the numbers
as not sufficiently random. If V lies between 99 and 95 percent or
between5 and 1 percent, the numbers are "suspect": if V lies between 95
and 90 percent, or 10 and 5 percent,, the numbers might be "almost
suspect". The chi-square test is often done at least three times on
different sets of data, and if at least two of the three are suspect the
numbers are regarded as not sufficiently random.

B)  **Equidistribution Test (Frequency Test).** Theoretically this test
    counts the frequency of occurrence of each number in a random
    sequence and then applies chi-square test of those frequency counts.
    Formally it is defined as follows:

> For each integer r, 0 \<= r \< d, count the number of times Yj = r for
>
> 0 \< = j \< n, and then apply the chi-square test using k=d and
> probability ps =1/d for each category. Here the sequences of integers
> will be uniformly distributed between = and d-1.
>
> For example lets suppose a sequence of integers with digits between 0
> and 4. So for each digit i.e. o to 3 we count the number of times the
> digit is occurring in the complete sequence. The probability of each
> digit to occur is ¼ (as there are just four different digits). If the
> sequence is 1000 digits long then expected occurrence of each digit
> will be 250 (nps=1000x1/4). The chi-square test should yield a value
> of chi-square coefficient, which should lie near 50 percent range, to
> be able to consider the sequence to be random. The degree of freedom
> in this example is 4 and so we will look at 3^rd^ (4-1) row in the
> table given by Knuth.

C)  **Serial Test.** This test is one step ahead of frequency test. It
    also counts the frequency of occurrence, but not just of single
    digits. It counts the frequency of occurrence of pairs of digits.
    Note that there can d\*d number of different pairs, if there are
    total d different digits. So the actual probability of occurrence of
    a pair is 1/(d\*d). So we can again apply chi-square test on these
    pairs with probability as mentioned above and with n=n/2. Note here
    that we can just have n/2 total possible pairs for a sequence of
    length n. This is because we select the pairs as (Y1, Y2), (Y3,
    Y4).... (Yn-1, Yn). Formally this test is defined as follows:

> Count the number of times the pair (Y2j,Y2j+1) = (q, r) occurs, for 0
> \<= j \< n, these counts are to be made for each pair of integers (q,
> r) with 0 \< = q, r \< d, and we apply chi-square test to these k=d\*d
> categories with probability 1/(d\*d) in each category.

Note that we can even generalize this test for not just pairs of two
digits but also pairs of three digits, four digits and so on. The
chi-square coefficient value should lie between 50 percent range to
consider the sequence as random.

# Gap Test. (A *block* is a subsequence of the form \...011110\... and a *gap* is one of the form \...10000001\...., either type is called a *run*.) This test as given in the book "The Art of Computer Programming" by Knuth is entirely based upon number of gaps of different lengths. Length of a gap refers to the number of consecutive 0's in a gap. For ex a gap 1000001 has length 5. Now it turns out that this test can be generalized and can be names as Run test. Though there is a altogether different test known as Run Test stated by Knuth but we will call the following test Run Test. Either a gap or a block is known as Run. So all this test will do is count the number of Runs in a sequence for all lengths possible. As we can guess that the larger the length of the Run the lesser is the probability of its occurrence. So once we have counted all the Runs with different lengths, we can again apply chi-square test on these counts. But now the question is what is the probability of occurrence of a Run of a given length. We can easily calculate this by the following formula.

> Let Ps be the probability of occurrence of a Run of length s.
>
> 1
>
> Then Ps is equal to \-\-\-\-\-\-\-\-\-\-\--
>
> s
>
> 2
>
> Let n be the total number of Runs found in the given sequence. Now we
> know the probability distribution and observed Runs, so we can
> calculate the expected numbers of Runs by simply multiplying n with
> the probability. Note here that we can have Run of length as large as
> the sequence itself. The probability of that Run will tend to approach
> zero. So to generalize we assume that we can get a Run of infinite
> length, which proves the correctness of the above formula. We know
> that the sum of and infinite geometric progression (GP) series is
> given by A/(1-R), where A is the first term and R is the common ratio.
> In this case first term is ½ and common ratio is again ½. So the sum
> of the infinite series comes to be 1, which is what the probability
> should be. Another point of discussion here is that till what length
> of Runs should we use in the chi-square test. It is mentioned by Knuth
> that if the expected number of occurrence is 5 or larger on then we
> should include it in the test. As can be seen that with larger length
> the probability reduces so much that the expected number will become
> quite less than 5. So we should not use those length Runs and larger.

Another very interesting test mentioned by Knuth is Permutation Test,
but the real application of that test lies in real numbers not with the
sequences if 0's and 1's. So I am not including that test as a part of
this project.

# Golomb Tests

Before I state about Golomb test, we need to look into the basic
operations of LFSR. The following two paragraphs are taken from the net
and are copyright by Texas Instrument.

An **LFSR** is a shift register that, when clocked, advances the signal
through the register from one bit to the next most-significant bit (see
Figure 1). Some of the outputs are combined in exclusive-OR
configuration to form a feedback mechanism. A linear feedback shift
register can be formed by performing exclusive-OR on the outputs of two
or more of the flip-flops together and feeding those outputs back into
the input of one of the flip-flops as shown in Figure 2.

\[Courtesy Texas Instrument\]

![](media/image1.png){width="5.997222222222222in" height="1.95625in"}

![](media/image2.png){width="5.989583333333333in"
height="2.5229166666666667in"}

Linear feedback shift registers make extremely good pseudorandom pattern
generators. When the outputs of the flip-flops are loaded with a seed
value (anything except all 0s, which would cause the LFSR to produce all
0 patterns) and when the LFSR is clocked, it will generate a
pseudorandom pattern of 1s and 0s. Note that the only signal necessary
to generate the test patterns is the clock.

As shown in figure 1 the shift register can be viewed as r tubes in a
row, where tube is nothing but a storage area commonly known as flip
flop. The purpose of the shift register is to shift the contents of each
tube to the next tube in the time with the next clock pulse. If we do
not insert any new signal into the first tube as the signals move
forward then eventually the empty signal will move forward leading all
the tubes to be empty. In order to avoid this inactive state of the
shift registers we use feedback shift register in which usually the
outputs from various tubes are passed from some function, onto the fist
tube again. This helps in always generating some new signals into the
first tube and generating a random sequence of bits from the last tube.
All the signals taken together at a instant of a time defines the state
of the **LFSR**. But eventually a time will come when all the tubes will
face the same signals again or in other words the LFSR will come to the
same state again. The maximum number of the states that a LFSR can
generate is known as the period of **LFSR**. Clearly for an r-tube shift
register there are 2^r^ --1 different possible states.

Lets turn back now to the Golomb's principles of randomness. There are
three basic principles stated by Golomb:

A)  In every period, the number of 1's is nearly equal to the number of
    0's. More precisely the difference between the number of zeros and
    ones should not exceed 1. In respect of an r-tube shift register
    there should be 2^r-1^ ones and 2^r-1^-1 zeros.

B)  Half the runs in a period have length 1, one-quarter have length
    2,\..., 1/2^i^ have length i. Moreover, for any length, half the
    runs are blocks and the other half gaps. In terms of period p of the
    sequence (p=2^r-^-1), there are (p+1)/2 runs, half of them blocks
    and half of them gaps. Of the blocks, half have length 1, one-fourth
    have length two, etc. and likewise for the gaps.

C)  **Agreements:** Given two sequences of same length agreement is the
    number of same symbols at each location of the two sequences. For
    example consider the following two sequences

> 1000110
>
> 0100111
>
> Here the agreements is four as the bit position 3^rd^,4^th^,5^th^ and
> 6^th^ matches in both the sequences.
>
> **Disagreements:** Given two sequences of same length disagreement is
> the number of different symbols at each location of the two sequences.
> For example consider the following two sequences
>
> 1000110
>
> 0100111
>
> Here the agreements is four as the bit position 1^st^ ,2^nd^ and 7^th^
> differs in both the sequences.

**Autocorrelation AC(k):** AC(k) = (Agreements - Disagreements)/p where
we are comparing a sequence of period p and its shift by k places. For
example given a sequence 100011101, if we shift it with 2 places we get
011000111. P in this case will be 8 that is the length if the sequence
itself. So the Autocorrelation can be found using the above formula.

Note that a sequence of period p can be shifted to at most p-1 places,
after which the same sequence will be generated. Now if we calculate
autocorrelation for all the p-1 different sequences and then take the
variance of all the calculated values, we should end up with a small
variance if the sequence is random enough.

**The variance** is given by the formula

![](media/image3.png){width="1.25in" height="0.3645833333333333in"}

where N is the total number of samples. In this case it is p-1.

X is the actual observed value. In this case it is AC(k)

U is the mean of all the AC(k)'s.

# Observations

The results of Knuth Randomness test and Golomb's randomness principles
are follows:

A)  The following file has period 97.

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***NUMBER OF ZEROS** :49 **NUMBER OF ONES** :48*

*The number of zeros and number of ones differ just by one.*

*So the test passed.*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*GAP LENGTH 1 : Observed 11 Desired 11.75*

*GAP LENGTH 2 : Observed 7 Desired 5.875*

*GAP LENGTH 3 : Observed 3 Desired 2.9375*

*GAP LENGTH 5 : Observed 2 Desired 0.734*

***TOTAL NUMBER OF GAPS** :23*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*BLOCK LENGTH 1 : Observed 11 Desired 11.75*

*BLOCK LENGTH 2 : Observed 8 Desired 5.875*

*BLOCK LENGTH 3 : Observed 3 Desired 2.9375*

*BLOCK LENGTH 4 : Observed 1 Desired 1.46875*

## BLOCK LENGTH 8 : Observed 1 Desired 0.091

***TOTAL NUMBER OF BLOCKS** :24*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***TOTAL NUMBER OF RUNS** : 47*

*Number of Gaps and number of Runs differs by one.*

*So the test passed.*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***PERIOD OF SEQUENCE** 97*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***MEAN AC**:-0.0103093 **VARIENCE** :0.0148928*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

### 

### 

### 

### 

### 

### 

### 

### 

### 

### 

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

###  FREQUENCY TEST

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

### n 97 Probability P\[0\] 0.5 Observed Y\[0\] 49 Desired n\*P\[0\] 48.5

### n 97 Probability P\[1\] 0.5 Observed Y\[1\] 48 Desired n\*P\[1\] 48.5

### 

### The Chi Square Coefficient for FREQUENCY Test is 0.0103093

*The Chi Square Coefficient lies between 95 and 75 percent range in the
table given by Knuth.*

### 

### 

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

###  SERIAL TEST

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

### n 48 Probability P\[0\] 0.25 Observed Y\[0\] 10 Desired n\*P\[0\] 12

### n 48 Probability P\[1\] 0.25 Observed Y\[1\] 14 Desired n\*P\[1\] 12

### n 48 Probability P\[2\] 0.25 Observed Y\[2\] 14 Desired n\*P\[2\] 12

### n 48 Probability P\[3\] 0.25 Observed Y\[3\] 10 Desired n\*P\[3\] 12

### 

### The Chi Square Coefficient for SERIAL Test is 1.33333

*The Chi Square Coefficient lies between 75 and 50 percent range in the
table given by Knuth*

### 

### 

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

###  GAP TEST

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

### n 47 Probability P\[0\] 0.5 Observed Y\[0\] 22 Desired n\*P\[0\] 23.5

### n 47 Probability P\[1\] 0.25 Observed Y\[1\] 15 Desired n\*P\[1\] 11.75

### n 47 Probability P\[2\] 0.125 Observed Y\[2\] 6 Desired n\*P\[2\] 5.875

### n 47 Probability P\[3\] 0.0625 Observed Y\[3\] 1 Desired n\*P\[3\] 2.9375

### n 47 Probability P\[4\] 0.03125 Observed Y\[4\] 2 Desired n\*P\[4\] 1.46875

### 

### The Chi Square Coefficient for GAP Test is 2.46742AP Test is 2.46742

*The Chi Square Coefficient lies between 75 and 50 percent range in the
table given by Knuth*

B)  The following file has period 1824.

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***NUMBER OF ZEROS** :912 **NUMBER OF ONES** :912*

*The number of zeros and number of ones differ just by zero.*

*So the test passed.*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*GAP LENGTH 1 : Observed 228 Desired 227.5*

*GAP LENGTH 2 : Observed 116 Desired 113.75*

*GAP LENGTH 3 : Observed 53 Desired 56.875*

*GAP LENGTH 4 : Observed 29 Desired 28.4375*

*GAP LENGTH 5 : Observed 15 Desired 14.21875*

*GAP LENGTH 6 : Observed 8 Desired 7.109*

*GAP LENGTH 7 : Observed 2 Desired 3.5546*

*GAP LENGTH 8 : Observed 1 Desired 1.7773*

#### GAP LENGTH 9 : Observed 3 Desired 0.8886

***TOTAL NUMBER OF GAPS** :455*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*BLOCK LENGTH 1 : Observed 227 Desired 227.5*

*BLOCK LENGTH 2 : Observed 116 Desired 113.75*

*BLOCK LENGTH 3 : Observed 52 Desired 56.875*

*BLOCK LENGTH 4 : Observed 34 Desired 28.4375*

*BLOCK LENGTH 5 : Observed 10 Desired14.21875*

#### BLOCK LENGTH 6 : Observed 10 Desired 7.109

*BLOCK LENGTH 7 : Observed 2 Desired 3.5546*

*BLOCK LENGTH 8 : Observed 2 Desired 1.7773*

*BLOCK LENGTH 9 : Observed 1 Desired 0.8886*

*BLOCK LENGTH 11 : Observed 1 Desired 0.22216*

***TOTAL NUMBER OF BLOCKS** :455*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***TOTAL NUMBER OF RUNS** : 910*

*Number of Gaps and number of Runs differs by zero.*

*So the test passed.*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***PERIOD OF SEQUENCE** 1824*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***MEAN AC**:-0.000548546 **VARIENCE** :0.000795085*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

***FREQUENCY TEST***

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*n 1824 Probability P\[0\] 0.5 Observed Y\[0\] 912 Desired n\*P\[0\]
912*

*n 1824 Probability P\[1\] 0.5 Observed Y\[1\] 912 Desired n\*P\[1\]
912*

*The Chi Square Coefficient for FREQUENCY Test is 0.*

*The Chi Square Coefficient lies between 100 and 99 percent range in the
table given by Knuth*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

#####  SERIAL TEST

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*n 911 Probability P\[0\] 0.25 Observed Y\[0\] 230 Desired n\*P\[0\]
227.75*

*n 911 Probability P\[1\] 0.25 Observed Y\[1\] 234 Desired n\*P\[1\]
227.75*

*n 911 Probability P\[2\] 0.25 Observed Y\[2\] 218 Desired n\*P\[2\]
227.75*

*n 911 Probability P\[3\] 0.25 Observed Y\[3\] 230 Desired n\*P\[3\]
227.75*

##### The Chi Square Coefficient for SERIAL Test is 0.63337

*The Chi Square Coefficient lies between 95 and 75 percent range in the
table given by Knuth*

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

#####  GAP TEST

*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

*n 910 Probability P\[0\] 0.5 Observed Y\[0\] 455 Desired n\*P\[0\] 455*

*n 910 Probability P\[1\] 0.25 Observed Y\[1\] 232 Desired n\*P\[1\]
227.5*

*n 910 Probability P\[2\] 0.125 Observed Y\[2\] 105 Desired n\*P\[2\]
113.75*

*n 910 Probability P\[3\] 0.0625 Observed Y\[3\] 63 Desired n\*P\[3\]
56.875*

*n 910 Probability P\[4\] 0.03125 Observed Y\[4\] 25 Desired n\*P\[4\]
28.4375*

*n 910 Probability P\[5\] 0.015625 Observed Y\[5\] 18 Desired n\*P\[5\]
14.2188*

*n 910 Probability P\[6\] 0.0078125 Observed Y\[6\] 4 Desired n\*P\[6\]
7.10938*

*n 910 Probability P\[7\] 0.00390625 Observed Y\[7\] 3 Desired n\*P\[7\]
3.55469*

*n 910 Probability P\[8\] 0.00195312 Observed Y\[8\] 4 Desired n\*P\[8\]
1.77734*

#### The Chi Square Coefficient for GAP Test is 7.06881 

*The Chi Square Coefficient lies between 75 and 50 percent range in the
table given by Knuth*

##### 

C)  The following file has period 7489.

> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> ***NUMBER OF ZEROS** :3745 **NUMBER OF ONES** :3744*

*The number of zeros and number of ones differ just by one.*

*So the test passed.*

> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *GAP LENGTH 1 : Observed 936 Desired 935.75*
>
> *GAP LENGTH 2 : Observed 468 Desired 467.875*
>
> *GAP LENGTH 3 : Observed 232 Desired 233.9375*
>
> *GAP LENGTH 4 : Observed 118 Desired 116.968*
>
> *GAP LENGTH 5 : Observed 60 Desired 54.484*
>
> *GAP LENGTH 6 : Observed 32 Desired 29.242*
>
> *GAP LENGTH 7 : Observed 13 Desired 14.621*
>
> *GAP LENGTH 8 : Observed 3 Desired 73105.*
>
> *GAP LENGTH 9 : Observed 4 Desired 3.6552*
>
> *GAP LENGTH 10 : Observed 2 Desired 1.8276*
>
> *GAP LENGTH 11 : Observed 1 Desired 0.9138*
>
> *GAP LENGTH 12 : Observed 1 Desired 0.456*
>
> *GAP LENGTH 16 : Observed 1 Desired 0.0285*
>
> ***TOTAL NUMBER OF GAPS** :1871*
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *BLOCK LENGTH 1 : Observed 936 Desired 935.75*
>
> *BLOCK LENGTH 2 : Observed 468 Desired 467.875*
>
> *BLOCK LENGTH 3 : Observed 237 Desired 233.9375*
>
> *BLOCK LENGTH 4 : Observed 110 Desired 116.968*
>
> *BLOCK LENGTH 5 : Observed 61 Desired 54.484*
>
> *BLOCK LENGTH 6 : Observed 31 Desired 29.242*
>
> *BLOCK LENGTH 7 : Observed 17 Desired 14.621*
>
> *BLOCK LENGTH 8 : Observed 3 Desired 73105*
>
> *BLOCK LENGTH 9 : Observed 5 Desired 3.6552*
>
> *BLOCK LENGTH 10 : Observed 2 Desired 1.8276*
>
> *BLOCK LENGTH 11 : Observed 2 Desired 0.9138*
>
> ***TOTAL NUMBER OF BLOCKS** :1872*
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> ***TOTAL NUMBER OF RUNS** : 3743*

*Number of Gaps and number of Runs differs by one.*

*So the test passed.*

> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> ***PERIOD OF SEQUENCE** 7489*
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> ***MEAN AC**:-0.000133534 **VARIENCE** :0.000232251*
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

######  FREQUENCY TEST

> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *n 7489 Probability P\[0\] 0.5 Observed Y\[0\] 3745 Desired n\*P\[0\]
> 3744.5*
>
> *n 7489 Probability P\[1\] 0.5 Observed Y\[1\] 3744 Desired n\*P\[1\]
> 3744.5*

###### The Chi Square Coefficient for FREQUENCY Test is 0.000133529

*The Chi Square Coefficient lies between 100 and 99 percent range in the
table given by Knuth*

> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

######  SERIAL TEST

> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *n 3744 Probability P\[0\] 0.25 Observed Y\[0\] 936 Desired n\*P\[0\]
> 936*
>
> *n 3744 Probability P\[1\] 0.25 Observed Y\[1\] 929 Desired n\*P\[1\]
> 936*
>
> *n 3744 Probability P\[2\] 0.25 Observed Y\[2\] 943 Desired n\*P\[2\]
> 936*
>
> *n 3744 Probability P\[3\] 0.25 Observed Y\[3\] 936 Desired n\*P\[3\]
> 936*

###### The Chi Square Coefficient for SERIAL Test is 0.104701

*The Chi Square Coefficient lies between 99 and 95 percent range in the
table given by Knuth*

> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**

######  GAP TEST

> *\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\**
>
> *n 3743 Probability P\[0\] 0.5 Observed Y\[0\] 1872 Desired n\*P\[0\]
> 1871.5*
>
> *n 3743 Probability P\[1\] 0.25 Observed Y\[1\] 936 Desired n\*P\[1\]
> 935.75*
>
> *n 3743 Probability P\[2\] 0.125 Observed Y\[2\] 469 Desired n\*P\[2\]
> 467.875*
>
> *n 3743 Probability P\[3\] 0.0625 Observed Y\[3\] 228 Desired
> n\*P\[3\] 233.938*
>
> *n 3743 Probability P\[4\] 0.03125 Observed Y\[4\] 121 Desired
> n\*P\[4\] 116.969*
>
> *n 3743 Probability P\[5\] 0.015625 Observed Y\[5\] 63 Desired
> n\*P\[5\] 58.4844*
>
> *n 3743 Probability P\[6\] 0.0078125 Observed Y\[6\] 30 Desired
> n\*P\[6\] 29.2422*
>
> *n 3743 Probability P\[7\] 0.00390625 Observed Y\[7\] 6 Desired
> n\*P\[7\] 14.6211*
>
> *n 3743 Probability P\[8\] 0.00195312 Observed Y\[8\] 9 Desired
> n\*P\[8\] 7.31055*
>
> *n 3743 Probability P\[9\] 0.000976562 Observed Y\[9\] 4 Desired
> n\*P\[9\] 3.65527*
>
> *n 3743 Probability P\[10\] 0.000488281 Observed Y\[10\] 3 Desired
> n\*P\[10\] 1.82764*

###### The Chi Square Coefficient for GAP Test is 6.91909

*The Chi Square Coefficient lies between 75 and 50 percent range in the
table given by Knuth*

####### Conclusion

A)  It turns out that the Frequency test given by Knuth and Golomb's
    first randomness postulate opposes each other. This is because if
    number of zeros and ones are equal as stated by Golomb then the
    expected number of zeros and ones will be exactly equal to the
    observed number of zeros and one for the Knuth frequency test. This
    will lead the chi-square coefficient move towards zero and such less
    value of this coefficient will lie in the 99 to 100 percent range.
    This range is consider to be non random.

B)  The Gap test of Knuth and Golomb second postulate both, uses the
    number of Runs as their criteria for determining randomness. In fact
    they again oppose each other in the sense that if the expected
    number of Runs (of different lengths) matches the observed number of
    Runs then again the chi-square coefficient will tend to move towards
    zero i.e. 100 percent range. This certainly is not a random
    sequence.

**SOURCE CODE**

***#include \<stdio.h\>***

***#include \<iostream.h\>***

***#include \<string.h\>***

***#include \<strings.h\>***

***#include \<stdlib.h\>***

***class RandomAccessFile{***

***private: FILE\* filePointer;***

***char\* fileName;***

***public :***

***RandomAccessFile(char\* name){***

***fileName=name;***

***if ((filePointer = fopen(fileName, \"r\")) == NULL){***

***cout\<\< \"Cannot open \\n\"\<\<fileName;***

***}***

***}***

***char readChar(){***

***char charBuf\[1\];***

***if(fscanf(filePointer,\"%c\",charBuf)!=EOF){***

***return(charBuf\[0\]);***

***}else{***

***return(\'\\0\');***

***}***

***}***

***void readLine(char\* buf){***

***fscanf(filePointer,\"%s\",buf);***

***}***

***int writeLine(char\* line){***

***return(fprintf(filePointer,\"%s\",line));***

***}***

***int sizeOfFile(){***

***char charBuf\[1\];***

***int count=0;***

***while(fscanf(filePointer,\"%c\",charBuf)!=EOF){***

***count++;***

***}***

***fclose(filePointer);***

***if ((filePointer = fopen(fileName, \"r\")) == NULL){***

***cout\<\< \"Cannot open \\n\"\<\<fileName;***

***}***

***return(count);***

***}***

***void close(){***

***fclose(filePointer);***

***}***

***};***

***class Utility{***

***private:;***

***public:***

***void rightShift(char array\[\],int size,int shiftSize,char
returnArray\[\]){***

***int i;***

***for(i=0;i\<size;i++){***

***returnArray\[i\]=array\[(i+size-shiftSize)%size\];***

***}***

***}***

***unsigned long int exp(int x,int power){***

***int i;***

***unsigned long int sum=1;***

***for(i=0;i\<power;i++){***

***sum=sum\*x;***

***}***

***return(sum);***

***}***

***void matchesAndMisMatches(char array1\[\],char array2\[\],int
size,int\* matches,int\* misMatches){***

***int i;***

***\*matches=0;***

***\*misMatches=0;***

***for(i=0;i\<size;i++){***

***if(array1\[i\]==array2\[i\]){***

***\*matches=\*matches+1;***

***}else{***

***\*misMatches=\*misMatches+1;***

***}***

***}***

***//cout\<\<\"inside matches \"\<\<\*matches\<\<\" mis
\"\<\<\*misMatches\<\<\"\\n\";***

***}***

***void removeNewlineFromFile(char\* fileName){***

***FILE\* filePointer;***

***if ((filePointer = fopen(\"tempFile.txt\", \"w\")) == NULL){***

***cout\<\< \"Cannot open tempFile\\n\";***

***}***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***char tempChar\[1\]={\'a\'};***

***while(tempChar\[0\]!=\'\\0\'){***

***tempChar\[0\]=randomAccessFile-\>readChar();***

***if((tempChar\[0\]!=\'\\n\')&&(tempChar\[0\]!=\'\\0\')){***

***fprintf(filePointer,\"%c\",tempChar\[0\]);***

***}***

***}***

***/\*tempChar\[0\]=\'\\0\';***

***fprintf(filePointer,\"%c\",tempChar\[0\]);\*/***

***fclose(filePointer);***

***}***

***};***

***class GolombTest{***

***private:***

***Utility utility;***

***public:***

***void countZerosOnes(char\* fileName,int\* numberOfZeros,int\*
numberOfOnes){***

***int countZero=0;***

***int countOne=0;***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***char tempChar=\'a\';***

***while(tempChar!=\'\\0\'){***

***tempChar=randomAccessFile-\>readChar();***

***if(tempChar==\'0\'){***

***countZero++;***

***}***

***if(tempChar==\'1\'){***

***countOne++;***

***}***

***}***

***\*numberOfZeros=countZero;***

***\*numberOfOnes=countOne;***

***randomAccessFile-\>close();***

***}***

***void countRuns(char\* fileName){***

***int countZero=0;***

***int countOne=0;***

***int countBlocks=0;***

***int countGaps=0;***

***int i=0;***

***int lengthOfArray;***

***bool firstOne=false;***

***bool zeroSeen=false;***

***bool firstZero=false;***

***bool oneSeen=false;***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***lengthOfArray=randomAccessFile-\>sizeOfFile()/4;***

***int arrayOfGaps\[lengthOfArray\];***

***int arrayOfBlock\[lengthOfArray\];***

***for(i=0;i\<lengthOfArray;i++){***

***arrayOfGaps\[i\]=0;***

***arrayOfBlock\[i\]=0;***

***}***

***char tempChar=\'a\';***

***while(tempChar!=\'\\0\'){***

***tempChar=randomAccessFile-\>readChar();***

***if(tempChar==\'1\'){***

***firstOne=true;***

***}***

***if(firstOne){***

***if(tempChar==\'0\'){***

***countZero++;***

***zeroSeen=true;***

***}***

***if((zeroSeen)&&(tempChar==\'1\')){***

***arrayOfGaps\[countZero\]++;***

***countZero=0;***

***zeroSeen=false;***

***}***

***}***

***if(tempChar==\'0\'){***

***firstZero=true;***

***}***

***if(firstZero){***

***if(tempChar==\'1\'){***

***countOne++;***

***oneSeen=true;***

***}***

***if((oneSeen)&&(tempChar==\'0\')){***

***arrayOfBlock\[countOne\]++;***

***countOne=0;***

***oneSeen=false;***

***}***

***}***

***}***

***randomAccessFile-\>close();***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\";***

***for(i=0;i\<lengthOfArray;i++){***

***if(arrayOfGaps\[i\]\>0){***

***countGaps=countGaps+arrayOfGaps\[i\];***

***cout\<\<\"GAP LENGTH \"\<\<i\<\<\"
:\"\<\<arrayOfGaps\[i\]\<\<\"\\n\";***

***}***

***}***

***cout\<\<\"TOTAL NUMBER OF GAPS :\"\<\<countGaps\<\<\"\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\";***

***for(i=0;i\<lengthOfArray;i++){***

***if(arrayOfBlock\[i\]\>0){***

***countBlocks=countBlocks+arrayOfBlock\[i\];***

***cout\<\<\"BLOCK LENGTH \"\<\<i\<\<\"
:\"\<\<arrayOfBlock\[i\]\<\<\"\\n\";***

***}***

***}***

***cout\<\<\"TOTAL NUMBER OF BLOCKS :\"\<\<countBlocks\<\<\"\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\";***

***cout\<\<\"TOTAL NUMBER OF RUNS :
\"\<\<(countGaps+countBlocks)\<\<\"\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\";***

***}***

***void autoCorelation(char\* fileName){***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***int lengthOfFile=randomAccessFile-\>sizeOfFile();***

***int i;***

***int iMinus1;***

***int matches;***

***int misMatches;***

***float AC\[lengthOfFile-1\];***

***float mean=0.0;***

***float varience=0.0;***

***char fileArray\[lengthOfFile\];***

***char shiftedFileArray\[lengthOfFile\];***

***cout\<\<\"\\n\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\";***

***cout\<\<\"PERIOD OF SEQUENCE \"\<\<lengthOfFile\<\<\"\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\\n\";***

***for(i=0;i\<lengthOfFile;i++){***

***fileArray\[i\]=randomAccessFile-\>readChar();***

***}***

***for(i=1;i\<lengthOfFile;i++){***

***utility.rightShift(fileArray,lengthOfFile,i,shiftedFileArray);***

***/\*for(int j=0;j\<lengthOfFile;j++){***

***cout\<\<fileArray\[j\];***

***}***

***cout\<\<\"\\n\";***

***for(int j=0;j\<lengthOfFile;j++){***

***cout\<\<shiftedFileArray\[j\];***

***}***

***cout\<\<\"\\n\";\*/***

***iMinus1=i-1;***

***utility.matchesAndMisMatches(fileArray,shiftedFileArray,lengthOfFile,&matches,&misMatches);***

***AC\[iMinus1\]=(matches-misMatches)/(float)lengthOfFile;***

***mean=mean+AC\[iMinus1\];***

***//cout\<\<\"AC(\"\<\<i\<\<\") :\"\<\<AC\[iMinus1\]\<\<\"\\tAggrements
:\"\<\<matches\<\<\"\\tDisaggrements \"\<\<misMatches\<\<\"\\n\";***

***}***

***mean=mean/(lengthOfFile-1);***

***for(i=0;i\<lengthOfFile-1;i++){***

***varience=varience+(AC\[i\]-mean)\*(AC\[i\]-mean);***

***}***

***varience=varience/(lengthOfFile-2);***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\";***

***cout\<\<\" MEAN AC:\"\<\<mean\<\<\"\\tVARIENCE
:\"\<\<varience\<\<\"\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\\n\"
;***

***}***

***};***

***class ChiSquare{***

***private: GolombTest gt;***

***Utility utility;***

***int findOccurance(char firstChar,char secondChar,char\* fileName){***

***int count=0;***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***char tempFirstChar=randomAccessFile-\>readChar();***

***char tempSecondChar=\'a\';***

***while((tempFirstChar!=\'\\0\')&&(tempSecondChar!=\'\\0\')){***

***tempSecondChar=randomAccessFile-\>readChar();***

***if((tempFirstChar==firstChar)&&((tempSecondChar==secondChar))){***

***count++;***

***}***

***tempFirstChar=tempSecondChar;***

***}***

***randomAccessFile-\>close();***

***return(count);***

***}***

***void findTotal(int Y\[\],char\* fileName){***

***int i;***

***for(i=0;i\<4;i++){***

***Y\[i\]=0;***

***}***

***//int count=0;***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***char tempFirstChar=randomAccessFile-\>readChar();***

***char tempSecondChar=\'a\';***

***while((tempFirstChar!=\'\\0\')&&(tempSecondChar!=\'\\0\')){***

***tempSecondChar=randomAccessFile-\>readChar();***

***if((tempFirstChar==\'0\')&&((tempSecondChar==\'0\'))){***

***Y\[0\]=Y\[0\]+1;***

***}***

***if((tempFirstChar==\'0\')&&((tempSecondChar==\'1\'))){***

***Y\[1\]=Y\[1\]+1;***

***}***

***if((tempFirstChar==\'1\')&&((tempSecondChar==\'0\'))){***

***Y\[2\]=Y\[2\]+1;***

***}***

***if((tempFirstChar==\'1\')&&((tempSecondChar==\'1\'))){***

***Y\[3\]=Y\[3\]+1;***

***}***

***tempFirstChar=randomAccessFile-\>readChar();***

***}***

***randomAccessFile-\>close();***

***}***

***public:***

***double calculateV(int n,int k,int Y\[\],double p\[\]){***

***int i;***

***double v=0.0;***

***for(i=0;i\<k;i++){***

***v=v+(
((double)Y\[i\]-(double)n\*p\[i\])\*((double)Y\[i\]-(double)n\*p\[i\])
)/(n\*p\[i\]);***

***cout\<\<\"n \"\<\<n\<\<\"\\tProbability P\[\"\<\<i\<\<\"\]
\"\<\<p\[i\]\<\<\"\\tObserverd Y\[\"\<\<i\<\<\"\] \"\<\<Y\[i\]\<\<\"\\t
Desired n\*P\[\"\<\<i\<\<\"\] \"\<\<(n\*p\[i\])\<\<\"\\n\";***

***}***

***return(v);***

***}***

***double frequency(char\* fileName){***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***int n=randomAccessFile-\>sizeOfFile();***

***int zero,one;***

***int Y\[2\];***

***double p\[2\]={0.5,0.5};***

***gt.countZerosOnes(fileName,&zero,&one);***

***Y\[0\]=zero;***

***Y\[1\]=one;***

***randomAccessFile-\>close();***

***return(calculateV(n,2,Y,p));***

***}***

***double serial(char\* fileName){***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***int n=randomAccessFile-\>sizeOfFile()-1;***

***int Y\[4\];***

***double p\[4\]={0.25,0.25,0.25,0.25};***

***/\*Y\[0\]=findOccurance(\'0\',\'0\',fileName);***

***Y\[1\]=findOccurance(\'0\',\'1\',fileName);***

***Y\[2\]=findOccurance(\'1\',\'0\',fileName);***

***Y\[3\]=findOccurance(\'1\',\'1\',fileName);\*/***

***findTotal(Y,fileName);***

***randomAccessFile-\>close();***

***return(calculateV(n/2,4,Y,p));***

***}***

***double gap(char\* fileName){***

***int countZero=0;***

***int countOne=0;***

***int countRun=0;***

***int k=0;***

***int i=0;***

***int lengthOfArray;***

***bool firstOne=false;***

***bool zeroSeen=false;***

***bool firstZero=false;***

***bool oneSeen=false;***

***RandomAccessFile\* randomAccessFile=new
RandomAccessFile(fileName);***

***lengthOfArray=randomAccessFile-\>sizeOfFile();***

***//lengthOfArray=4;***

***int arrayOfGaps\[lengthOfArray\];***

***int arrayOfBlock\[lengthOfArray\];***

***int arrayOfRun\[lengthOfArray\];***

***double p\[lengthOfArray\];***

***for(i=0;i\<lengthOfArray;i++){***

***arrayOfGaps\[i\]=0;***

***arrayOfBlock\[i\]=0;***

***arrayOfRun\[i\]=0;***

***}***

***char tempChar=\'a\';***

***while(tempChar!=\'\\0\'){***

***tempChar=randomAccessFile-\>readChar();***

***if(tempChar==\'1\'){***

***firstOne=true;***

***}***

***if(firstOne){***

***if(tempChar==\'0\'){***

***countZero++;***

***zeroSeen=true;***

***}***

***if((zeroSeen)&&(tempChar==\'1\')){***

***arrayOfGaps\[countZero\]++;***

***countZero=0;***

***zeroSeen=false;***

***}***

***}***

***if(tempChar==\'0\'){***

***firstZero=true;***

***}***

***if(firstZero){***

***if(tempChar==\'1\'){***

***countOne++;***

***oneSeen=true;***

***}***

***if((oneSeen)&&(tempChar==\'0\')){***

***arrayOfBlock\[countOne\]++;***

***countOne=0;***

***oneSeen=false;***

***}***

***}***

***}***

***randomAccessFile-\>close();***

***for(i=0;i\<lengthOfArray;i++){***

***countRun=countRun+arrayOfGaps\[i\]+arrayOfBlock\[i\];***

***}***

***for(i=0;i\<lengthOfArray-1;i++){***

***k++;***

***arrayOfRun\[i\]=arrayOfGaps\[i+1\]+arrayOfBlock\[i+1\];***

***p\[i\]=(double)1.0/(utility.exp(2,(i+1)));***

***if(countRun\*p\[i\]\<1){***

***break;***

***}***

***}***

***return(calculateV(countRun,(k-1),arrayOfRun,p));***

***}***

***};***

***void main(){***

***GolombTest gt;***

***Utility utility;***

***ChiSquare chiSquareObject;***

***//int Y\[11\]={2,4,10,12,22,29,21,15,14,9,6};***

***//double
p\[11\]={((double)1/36),((double)1/18),((double)1/12),((double)1/9),((double)5/36),((double)1/6),((double)5/36),((double)1/9),((double)1/12),((double)1/18),((double)1/36)};***

***//cout\<\<\"The v is
\"\<\<chiSquareObject.calculateV(144,11,Y,p)\<\<\"\\n\";***

***char\* fileName=\"tempFile.txt\";***

***utility.removeNewlineFromFile(\"file3.txt\");***

***int zero,one;***

***gt.countZerosOnes(fileName,&zero,&one);***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\";***

***cout\<\<\"NUMBER OF ZEROS :\"\<\<zero\<\<\"\\tNUMBER OF ONES
:\"\<\<one\<\<\"\\n\" ;***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n\\n\\n\";***

***gt.countRuns(fileName);***

***gt.autoCorelation(fileName);***

***double tempResult;***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\"\<\<\"\\n\";***

***cout\<\<\" \\t\\tFREQUENCY TEST\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\"\<\<\"\\n\";***

***tempResult=chiSquareObject.frequency(fileName);***

***cout\<\<\"\\nThe Chi Square Cofficient for FREQUENCY Test is
\"\<\<tempResult\<\<\"\\n\\n\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\"\<\<\"\\n\";***

***cout\<\<\" \\t\\tSERIAL TEST\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\"\<\<\"\\n\";***

***tempResult=chiSquareObject.serial(fileName);***

***cout\<\<\"\\nThe Chi Square Cofficient for SERIAL Test is
\"\<\<tempResult\<\<\"\\n\\n\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\"\<\<\"\\n\";***

***cout\<\<\" \\t\\tGAP TEST\\n\";***

***cout\<\<\"\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\"\<\<\"\\n\";***

***tempResult=chiSquareObject.gap(fileName);***

***cout\<\<\"\\nThe Chi Square Cofficient for GAP Test is
\"\<\<tempResult\<\<\"\\n\";***

***}***

######### PART TWO

**Aim**: To develop a secure chatting (Server and Client) software.

**Introduction:** Chatting software is the one in which clients can
share messages with another. The most basic form of chatting is the one
in which a single client sends a message and it is echoed to all the
online clients. This type of chatting software is simplest in nature in
respect of server development. All the server needs to maintain is the
list of online clients and as soon as it receives a message it sends it
to all the clients, which are online. A more challenging type of
software is the one in which a single client can send a message to any
online client without echoing it to any other online client. In this
case the server has to again maintain a list on online clients and in
addition, it has to follow some protocol in order so send the message to
appropriate client. My aim of this project is for the later type of
chatting software. Further it aims at making the software securing by
using some encryption techniques and then sending the messages over the
net.

**Overview Of Design:**

Spawning a new Client process.

Spawning a new process.

IPC between Client Processes in plain Text

IPC between Book keep process and Client process in plain text

Communication over the network between Client and the Server (Client
Process) in Encrypted text.

**Server:** The Server is a state full concurrent server. The server in
the beginning spawns a process known as book keep, which maintains the
database of the online clients. On every successful connection
establishment, server spawns a new client process that handles all the
secure communication between the client and itself on the TCP socket and
use IPC (Inter Process Communication) to communicate with other
processes. All Client processes would be provided the process ID of Book
Keep process and vice a versa. The Communication over the net and within
process follows a well-defined protocol.

**Client**: The Client when first connected to the Server (Client
process) will use Diffie-Hellman procedure to exchange the keys between
themselves. Once the keys are generated the client will use this key to
encrypt every message it will send to the server and decrypt every
message it will receive from it. (The Encryption and Decryption
algorithm is not certain yet). The server (client process A) will
decrypt all the messages it will get and use IPC to send that message to
another process in plain text. The other client process (say B) will use
its own key to encrypt it again and do sent it the its client. In this
way all the communication over the net will be in the encrypted form.

**Implementation:**

When a client tries to connect to the server using TCP connection, the
server spawns a new process for this client, which is just a replica of
the server itself. It further prompts the user to specify his name that
could be used by the book keep process to store all the names of online
clients. This new process is responsible to handle to all the
communications regarding its client. The server assigns a new process Id
to this new process (say A). Further the main server process gives the
process Id of the book keep process to the newly spawned server process
(A) and the process Id of this newly spawned server process (A) to the
book keep process. At this time both the book keep and the server
process have the process Ids of each other. Now the book keep process
returns a list of all-online client names to the newly spawned server
process (A), which in turn sends it back to the client himself. The
client can then specify to whom he wants to chat by specifying the name
of that client. This name goes back to the server process (A), and now
it tries to fetch the process Id of another server process (say B) that
is serving the client with the name specified. It gets the process Id of
that server process (B) by asking the book keep process. The book keep
process maintains a list of all online clients with their process Id's
and names of the clients. Once the book keep process returns the process
Id (B) of the specified name to the process (A) who requested it, it
also sends a message to that process (B) whose Id was requested, stating
that some one (A) with this process Id and name is trying to connect to
you (B). This message when reaches the other server process (B), it
sends the same message to his online client. At this stage both A and B
blocks down their clients until some confirmation comes from B to A
again. This happens only when the client at B agrees to communicate with
A. The client at B sends a message "Talk A" to its own server process
(B). Now since both A and B have process Id's of each other they do not
need to use Book Keep process anymore. So B sends a message to server
process A that connection established at my end. The server process A on
receiving this message from B sends a message to its client that the
connection is now established thereby removing the blocks on both the
clients. Not at this time both the clients can communicate with each
other by just sending any message to its server process. The server
process sends (A) that message to another server process (B) to which it
is supposed to be connected and then that process B sends it to the
client. Vice a versa happens if client at B wants to send a message to
A.

Note at this stage when two clients are communicating, another client
can come in and try to communicate with either A or B. In order to avoid
that I have made the server a state full server in which at state one it
can accept messages from all other processes and responds accordingly.
When it is communicating with any other client it goes to state two in
which though it can accept all the message but it wont do anything about
it. This way no one can interfere between the chatting of any two
clients. The format of the messages, which flows from the client to the
server and from one process to another, follows a defined protocol. For
example in order to get the Id of the process to whom another process
wants to communicate the following format will be used.

\"GET ID:SELFID:NAMEof PROCESS" where Name is that name of the process
whose ID is REQUESTED\" . If process A wants to fetch the Id from book
keep, of process B it will send the following message to Book keep
process "GET ID:A:B". Similarly all other messages follows a well
defined formats to easy the server development.

**Observation:**

It turns out that in order to make this chatting software secure, we
need to exchange some keys, which we will use for encryption and
decryption. Well Diffie-Hellman algorithm is most appropriate for
exchanging keys. Initially I thought of the following procedure to make
the whole algorithm secure.

The client and the server process (A) will use Diffie-Hellman algorithm
to exchange keys. In the similar way the client and the server process B
will use Diffie-Hellman algorithm to exchange different keys. Now in
order to send a message X from client A to client B, The client A will
use its own pair of keys to encrypt the message and send it to server
process A, The server process will decrypt the message using its pair of
keys and send the plain text to the server process B. The server process
B will again encrypt it using its own set of keys and send it to its
client B. The client B will decrypt iy using the same pair of keys that
it generated using Diffie-Hellman algorithm. This way ever message will
be decrypted and encrypted twice during transmission.

Note here it is possible to send single characters from client A to
client B. So encrypting these single characters even after padding them
is really not a good idea both in terms of security and time complexity.
My discussion with Dr. TRN Rao helped me to leave the security issue out
from this project. So finally the chatting software works but it is not
using any encryption or decryption standard for secure communication.

**SOURCE CODE**

**Server.cpp**

**#include \<string.h\>**

**#include \<iostream.h\>**

**#include \<sys/socket.h\>**

**#include \<sys/types.h\>**

**#include \<sys/ipc.h\>**

**#include \<sys/msg.h\>**

**#include \<iostream.h\>**

**#include \<stdio.h\>**

**#include \<strings.h\>**

**#include \<stdlib.h\>**

**#include \<arpa/inet.h\>**

**#include \<fcntl.h\>**

**#include \<unistd.h\>**

**#define MSGSZ 128**

**#define MAXNAMELENGTH 10**

**#define MAXLENGTH 128**

**class IpcMessageQ**

**{**

**private:**

**//int MSGSZ;**

**int msqid;**

**int msgflg;**

**long mtype;**

**key_t key;**

**size_t buf_length;**

**public:**

**IpcMessageQ() {**

**//MSGSZ=128;**

**msgflg = IPC_CREAT \| 0666;**

**key = 1234;**

**(void) fprintf(stderr, \"\\nmsgget: Calling msgget(%#lx,\\%#o)\\n\",
key, msgflg);**

**if((msqid = msgget(key,msgflg)) \< 0){**

**perror(\"msgget\");**

**}else{**

**(void) fprintf(stderr,\"msgget:msgget succceeded: msqid =
%d\\n\",msqid);**

**}**

**}**

**void messageSend(char\* messageText,long processId){**

**//cout\<\<\"line1\\n\";**

**struct**

**{**

**long mtype;**

**char mtext\[MSGSZ\];**

**} msgbuf;**

**int i;**

**buf_length=strlen(messageText);**

**//cout\<\<\"buf length \"\<\<buf_length\<\<\"\\n\";**

**for(i=buf_length;i\<MSGSZ;i++){**

**strcat(messageText,\"\\0\");**

**//cout\<\<\"inloop \";**

**}**

**strcpy(msgbuf.mtext,messageText);**

**//cout\<\<\"mtext \" \<\<msgbuf.mtext\<\<\"\\n\";**

**msgbuf.mtype=processId;**

**//if (msgsnd(msqid, &msgbuf, buf_length,IPC_NOWAIT) \< 0) {
//IPC_NOWAIT**

**if (msgsnd(msqid, &msgbuf, MSGSZ,IPC_NOWAIT) \< 0) { //IPC_NOWAIT**

**perror(\"msgsnd\");**

**}**

**}**

**void messageReceive(char\* rbuf,long processId)**

**{**

**struct**

**{**

**long mtype;**

**char mtext\[MSGSZ\] ;**

**} msgbuf;**

**if (msgrcv(msqid, &msgbuf, MSGSZ,processId, IPC_NOWAIT) \< 0){**

**//perror(\"msgrcv\");**

**//if(strlen(msgbuf.mtext)==0){**

**strcpy(rbuf,\"\\0\");**

**//}**

**}else{**

**if(strlen(msgbuf.mtext)==0){**

**strcpy(rbuf,\"\\0\");**

**}else{**

**strcpy(rbuf,msgbuf.mtext);**

**//printf(\"%s\\n\", rbuf);**

**//cout\<\<\"from ipc \"\<\<rbuf\<\<\" my id
\"\<\<getpid()\<\<\"\\n\";**

**strcpy(msgbuf.mtext,\"\\0\");**

**}**

**}**

**}**

**};**

**// former code starts from here**

**class Communicate{**

**private: int des;**

**public:**

**Communicate(int descriptor){**

**des=descriptor;**

**}**

**int sendMessage(char\* text){**

**int len = strlen(text);**

**if (send(des,text,len,0)==-1){**

**cout\<\<\"send has an error\\n\";**

**return(-1);**

**}**

**return(len);**

**}**

**int receiveMessage(char\* buf){**

**int len;**

**int count=-1;**

**if( recv(des,buf,MAXLENGTH,MSG_DONTWAIT)==-1){**

**//if((len= recv(des,buf, MAXLENGTH,0))==-1){**

**strcpy(buf,\"\\0\");**

**return(-1);**

**}**

**do{**

**count++;**

**if(count\>MAXLENGTH){**

**sendMessage(\"Incorrect Format\\n\");**

**count=0;**

**break;**

**}**

**}while(buf\[count\]!=\'\\n\');**

**buf\[count\]=\'\\0\';**

**return(count);**

**}**

**int writeMessage(char\* text){**

**int len = strlen(text);**

**if (write(des,text,len)==-1){**

**cout\<\<\"write has an error\\n\";**

**return(-1);**

**}**

**return(len);**

**}**

**int readMessage(char\* buf){**

**int len;**

**if((len= read(des,buf,MAXLENGTH))==-1){**

**strcpy(buf,\"\\0\");**

**return(-1);**

**}**

**return(len);**

**}**

**};**

**class Socket{**

**private: int descriptor;**

**Communicate\* objCommunicate;**

**struct sockaddr_in serverAddress;**

**public:**

**Socket(char\* ipAddr,int port){**

**bzero(&serverAddress,sizeof(serverAddress)); //initializing the
serveraddress to zero**

**serverAddress.sin_family=AF_INET; //specifying the parameters of
socket address structure**

**serverAddress.sin_port=htons(port);**

**serverAddress.sin_addr.s_addr=inet_addr(ipAddr);**

**descriptor=socket(AF_INET,SOCK_STREAM,0);**

**if(descriptor\<0){**

**cout\<\<\"error:couldnot connect\\n\";**

**return;**

**}**

**connect(descriptor, (struct sockaddr\*) &serverAddress,
sizeof(serverAddress));**

**objCommunicate =new Communicate(descriptor);**

**}**

**Socket(int des){**

**descriptor=des;**

**objCommunicate =new Communicate(des);**

**}**

**Communicate\* getCommunicate(){**

**return(objCommunicate);**

**}**

**};**

**class ServerSocket{**

**private: struct sockaddr_in serverAddress;**

**struct sockaddr_in clientAddress;**

**int listenfd;**

**Socket\* socketPointer;**

**public:**

**ServerSocket(int port,int LISTENQ){**

**bzero((char\*)&serverAddress,sizeof(serverAddress)); //initializing
the serveraddress to zero**

**serverAddress.sin_family=AF_INET; //specifying the parameters of
socket address structure**

**serverAddress.sin_port=htons(port);**

**serverAddress.sin_addr.s_addr=htonl(INADDR_ANY);**

**socket(AF_INET,SOCK_STREAM,0);**

**listenfd=socket(AF_INET,SOCK_STREAM,0);**

**if(listenfd\<0){**

**cout\<\<\"error:server not able to complete the connection\\n\";**

**}**

**if(bind(listenfd,((struct
sockaddr\*)&serverAddress),sizeof(serverAddress))\<0){**

**perror(\"server: bind\");**

**}**

**listen(listenfd, LISTENQ);**

**}**

**Socket\* Accept(){**

**int clientLength=sizeof(clientAddress);**

**int des= accept(listenfd,(struct
sockaddr\*)&clientAddress,(socklen_t\*)&clientLength);**

**if(des\<0){**

**cout\<\<\"connection not accepted\\n\";**

**}**

**socketPointer=new Socket(des);**

**return(socketPointer);**

**}**

**};**

**class Talk{**

**private:**

**int MAXCLIENTS;**

**int bookKeep;**

**int childId;**

**IpcMessageQ\* ipcObject;**

**ServerSocket\* serverSocket;**

**public: Talk(int portNumber,int listenQ){**

**// MAXLENGTH=50;**

**serverSocket=new ServerSocket(portNumber,listenQ);**

**MAXCLIENTS=100;**

**ipcObject=new IpcMessageQ();**

**int bookKeep=fork();**

**int childId;**

**if (bookKeep==0){**

**handleBookKeep();**

**}else{**

**while (true){**

**Socket\* clientSocket = serverSocket-\>Accept();**

**childId=fork();**

**char message\[MAXLENGTH\];**

**//char message1\[MAXLENGTH\];**

**char charChildId\[MAXNAMELENGTH\];**

**char charBookKeep\[MAXNAMELENGTH\];**

**sprintf(charChildId,\"%d\",childId);**

**sprintf(charBookKeep,\"%d\",bookKeep);**

**// cout\<\<\"child id \"\<\<charChildId\<\<\" bookKeep
\"\<\<charBookKeep\<\<\"parent id \"\<\<getpid()\<\<\"\\n\";**

**if(childId==0){**

**handleClient(clientSocket);**

**}else{**

**strcpy(message,\"MY ID:\");**

**strcat(message,charChildId);**

**strcat(message,\"\\0\");**

**ipcObject-\>messageSend(message,bookKeep);**

**strcpy(message,\"BOOKKEEPID:\");**

**strcat(message,charBookKeep);**

**strcat(message,\"\\0\");**

**ipcObject-\>messageSend(message,childId);**

**}**

**}**

**}**

**}**

**void handleBookKeep(){**

**typedef struct {**

**char name\[MAXNAMELENGTH\];**

**int databaseID;**

**}record;**

**int currentLocation=0;**

**int i;**

**int myID=getpid();**

**char buf\[MAXLENGTH\];**

**char\* tempBuf;**

**record database\[MAXCLIENTS\];**

**while (true){**

**ipcObject-\>messageReceive(buf,myID);**

**char\* processID;**

**if(strlen(buf)!=0){**

**tempBuf=strtok(buf,\":\");**

**if(strcmp(tempBuf,\"MY ID\")==0){ //the id of process forked by server
for new client**

**processID=strtok(NULL,\":\");**

**database\[currentLocation\].databaseID=atoi(processID);**

**currentLocation++;**

**}**

**if(strcmp(tempBuf,\"MY NAME\")==0){ //the name of new client protocol
is MY NAME:ID:\"NAME\"**

**//cout\<\<\"In my name process id \"\<\<getpid()\<\<\"\\n\";**

**int intReceivedID=atoi(strtok(NULL,\":\"));**

**for(i=0;i\<currentLocation;i++){**

**if(database\[i\].databaseID==intReceivedID){**

**strcpy(database\[i\].name,strtok(NULL,\":\"));**

**break;**

**}**

**}**

**char onlineList\[MAXCLIENTS\*(MAXNAMELENGTH+1)+13\] ;**

**strcpy(onlineList,\"ONLINE LIST:\");**

**for(i=0;i\<currentLocation;i++){**

**strcat(onlineList,database\[i\].name);**

**strcat(onlineList,\"\\t\");**

**}**

**strcat(onlineList,\"\\0\");**

**ipcObject-\>messageSend(onlineList,intReceivedID);**

**}**

**if(strcmp(tempBuf,\"GET ID\")==0){ //one client asking for the ID of
another client(by giving its name) with whom it wants to talk**

**char\* secondToken=strtok(NULL,\":\");**

**int intSelfID=atoi(secondToken);**

**int intRequestedID;**

**// protocol is \"GET ID:SELFID:NAMEof PROCESS whose ID is
REQUESTED\"**

**char selfName\[MAXNAMELENGTH\];**

**char requestedID\[MAXNAMELENGTH\];**

**char messageToSend\[MAXNAMELENGTH+9\];**

**char\* providedName=strtok(NULL,\":\");**

**for(i=0;i\<currentLocation;i++){**

**if (strcmp(database\[i\].name,providedName)==0){**

**intRequestedID=database\[i\].databaseID;**

**sprintf(requestedID,\"%d\",intRequestedID);**

**strcpy(messageToSend,\"REQUESTED ID:\");**

**strcat(messageToSend,requestedID);**

**strcat(messageToSend,\"\\0\");**

**ipcObject-\>messageSend(messageToSend,intSelfID);**

**break;**

**}**

**}**

**for(i=0;i\<currentLocation;i++){**

**if (database\[i\].databaseID==intSelfID){ //TEMP ID: SELFID:SELFNAME**

**char message\[2\*MAXNAMELENGTH+10\];**

**selfName=database\[i\].name;**

**strcpy(message,\"TEMP ID:\");**

**strcat(message,secondToken);**

**strcat(message,\":\");**

**strcat(message,selfName);**

**strcat(message,\"\\0\");**

**ipcObject-\>messageSend(message,intRequestedID);**

**break;**

**}**

**}**

**}**

**}**

**}**

**}**

**void handleClient(Socket\* clientSocket){**

**Communicate\* objCommunicate=clientSocket-\>getCommunicate();**

**int myID=getpid();**

**//cout\<\<\"child id should be \"\<\<myID\<\<\"\\n\";**

**int requestedFriendID;**

**int tempID;**

**int bookKeepID;**

**int state=0;**

**char buf4Ipc\[MAXLENGTH\];**

**char buf4Socket\[MAXLENGTH\];**

**char\* firstToken;**

**char\* secondToken;**

**char charMyID\[MAXNAMELENGTH\];**

**bool bothSide=false;**

**sprintf(charMyID,\"%d\",myID);**

**while(true){**

**strcpy(buf4Ipc,\"\\0\");**

**ipcObject-\>messageReceive(buf4Ipc,myID);**

**if (strlen(buf4Ipc)!=0){**

**if(state==0){**

**firstToken=strtok(buf4Ipc,\":\");**

**if (strcmp(firstToken,\"BOOKKEEPID\")==0){**

**secondToken=strtok(NULL,\":\");**

**bookKeepID=atoi(secondToken);**

**}**

**if (strcmp(firstToken,\"ONLINE LIST\")==0){**

**char message\[MAXCLIENTS+MAXNAMELENGTH+12\];**

**char realMessage\[MAXCLIENTS+MAXNAMELENGTH+16\];**

**char charLen\[MAXNAMELENGTH\];**

**int len;**

**secondToken=strtok(NULL,\":\");**

**strcpy(message,\"ONLINE LIST:\");**

**strcat(message,secondToken);**

**strcat(message,\"\\n\\0\");**

**len=strlen(message);**

**sprintf(charLen,\"%d\",len);**

**strcpy(realMessage,charLen);**

**strcat(realMessage,\":\");**

**strcat(realMessage,message);**

**objCommunicate-\>sendMessage(realMessage);**

**}**

**if (strcmp(firstToken,\"REQUESTED ID\")==0){**

**secondToken=strtok(NULL,\":\");**

**requestedFriendID=atoi(secondToken);**

**}**

**if (strcmp(firstToken,\"TEMP ID\")==0){**

**tempID=atoi(strtok(NULL,\":\"));**

**bothSide=true;**

**char message\[MAXNAMELENGTH+28\];**

**secondToken=strtok(NULL,\":\");**

**strcpy(message,\"THE CLIENT WITH NAME \");**

**strcat(message,secondToken);**

**strcat(message,\" IS TRYING TO CONNECT. RESPOND WITH TALK:\");**

**strcat(message,secondToken);**

**strcat(message,\"\\n\");**

**objCommunicate-\>sendMessage(message);**

**}**

**if (strcmp(firstToken,\"CONNECTION ESTABLISHED\")==0){**

**state=1;**

**objCommunicate-\>sendMessage(\"Connection Established\\n\");**

**}**

**} else{**

**if (state==1){**

**strcat(buf4Ipc,\"\\n\");**

**objCommunicate-\>sendMessage(buf4Ipc);**

**}**

**}**

**}**

**objCommunicate-\>receiveMessage(buf4Socket);**

**if(strlen(buf4Socket)!=0){**

**//cout\<\<\"from socket \"\<\<buf4Socket\<\<\"\\n\";**

**if (state==0){**

**char message\[MAXLENGTH\];**

**firstToken=strtok(buf4Socket,\":\");**

**//cout\<\<\"first token \"\<\<firstToken\<\<\"\\n\";**

**if (strcmp(firstToken,\"MY NAME\")==0){**

**//cout\<\<\"inside ha ha \\n\";**

**strcpy(message,\"MY NAME:\");**

**strcat(message,charMyID);**

**strcat(message,\":\");**

**strcat(message,strtok(NULL,\":\"));**

**strcat(message,\"\\0\");**

**//cout\<\<\"my name sent to bookkeep id \"\<\<bookKeepID\<\<\"\\n\";**

**ipcObject-\>messageSend(message,bookKeepID);**

**}**

**if(strcmp(firstToken,\"TALK\")==0){**

**if(!bothSide){**

**//cout\<\<\"not bothside\\n\";**

**strcpy(message,\"GET ID:\");**

**strcat(message,charMyID);**

**strcat(message,\":\");**

**strcat(message,strtok(NULL,\":\"));**

**strcat(message,\"\\0\");**

**ipcObject-\>messageSend(message,bookKeepID);**

**}else{**

**//cout\<\<\"bothside\\n temp id \"\<\<tempID\<\<\"\\n\";**

**strcpy(message,\"CONNECTION ESTABLISHED:\\0\");**

**ipcObject-\>messageSend(message,tempID);**

**objCommunicate-\>sendMessage(\"Connection Established\\n\");**

**requestedFriendID=tempID;**

**state=1;**

**}**

**}**

**}else{**

**if(state==1){**

**ipcObject-\>messageSend(buf4Socket,requestedFriendID);**

**}**

**}**

**}**

**}**

**}**

**};**

**void main(int argc,char\*\* argv){**

**int port=1111;**

**//cout\<\<\"argv 0 \"\<\<argv\[0\]\<\<\" argv1
\"\<\<argv\[1\]\<\<\"\\n\";**

**if(argc\>0){**

**port=atoi(argv\[1\]);**

**cout\<\<\"port \"\<\<port\<\<\"\\n\";**

**}**

**Talk talk(port,5);**

**//ServerSocket serverSocket(1234,5);**

**//cout\<\<\"Listening\....\\n\";**

**//Socket\* clientSocket=serverSocket.Accept();**

**//Communicate\* communicate=clientSocket-\>getCommunicate();**

**//communicate-\>sendMessage(\"From Server\\n\");**

**//char buf\[20\];**

**//while(true){**

**// communicate-\>receiveMessage(buf);**

**// if(strlen(buf)\>0){**

**// break;**

**//}**

**// }**

**//cout\<\<\"server\"\<\<buf\<\<\"\\n\";**

**}**

**References:**

**Donald R. Knuth**, The Art of Computer Programming Vol 2.

**Solomon W. Golomb**, Shift Register Sequences.

**Texas Instruments** web site, [www.ti.com](http://www.ti.com/)