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.

> 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

Run in calculatorCopy input

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\).