---
title: "Correlation Functions"
canonical: "https://docs.magma-maths.org/CodingTheory/PseudoRandomBitSequences/correlation.html"
source: "https://docs.magma-maths.org/CodingTheory/PseudoRandomBitSequences/correlation.md"
part: "Coding Theory"
chapter: "Pseudo-Random Bit Sequences"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "../../index.md"}
  - {"title": "Coding Theory", "source": "../index-coding-theory.md"}
  - {"title": "Pseudo-Random Bit Sequences", "source": "index-pseudo-random-bit-sequences.md"}
prev: {"title": "Linear Feedback Shift Registers", "source": "lfsr.md"}
next: {"title": "Decimation", "source": "misc.md"}
intrinsics:
  - {"name": "AutoCorrelation", "signature": "AutoCorrelation(S, t): SeqEnum, RngIntElt -> RngIntElt"}
  - {"name": "CrossCorrelation", "signature": "CrossCorrelation(S1, S2, t): SeqEnum, SeqEnum, RngIntElt -> RngIntElt"}
examples:
  - "ex-e9917a"
---

# Correlation Functions

<a id="function-autocorrelation-seqenum-rngintelt"></a>
## `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$.

<a id="example-ex-e9917a"></a>
## `Example: Autocorrelation of an LFSR Sequence (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
```

<a id="function-crosscorrelation-seqenum-seqenum-rngintelt"></a>
## `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$.