# Correlation Functions

## `AutoCorrelation(S, t): SeqEnum, RngIntElt -> RngIntElt`

Computes the autocorrelation of a sequence $S$, where $S$ must have universe ${\bf F}_{2}$. The autocorrelation is defined to be

$$
C(t) = \sum_{i=1}^{L}  (-1)^{ S[i] + S[i+t] }
$$

where $L$ is the length of the sequence, and the values of $S[i+t]$ wrap around to the beginning of the sequence when $i+t > L$.

## `Example: Autocorr Example (ex-e9917a)`

It is well known that the LFSR’s with maximal periods have nice autocorrelation properties. This is illustrated below.

```magma
> C<D> := PrimitivePolynomial (GF(2), 5);
> C;
D^5 + D^2 + 1
> s := [GF(2)|1,1,1,1,1];
> t := LFSRSequence(C, s, 31);
> t;
[ 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0,
1, 1, 0, 0, 0 ]
> AutoCorrelation (t, 2);
-1

```

## `CrossCorrelation(S1, S2, t): SeqEnum, SeqEnum, RngIntElt -> RngIntElt`

Computes the crosscorrelation of two binary sequences $S_1$ and $S_2$, where $S_1$ and $S_2$ must each have universe ${\bf F}_{2}$, and they must have the same length $L$. The crosscorrelation is defined to be:

$$
C(t) = \sum_{i=1}^{L} (-1)^{ S_1[i] + S_2[i+t] }
$$

and the values of $S_2[i+t]$ wrap around to the beginning of the sequence when $i+t > L$.