Die Autokorrelation eines Dokuments ist eine Kennzahl für die Ähnlichkeit von Teilen des Dokuments. Mit Hilfe der Autokorrelation kann unter Umständen die Schlüssellänge eines verschlüsselten Dokuments ermittelt werden.
Korrelation
Die folgenden Aussagen über Korrelation gelten hier für eine unabhängige gleichverteilte Binärfolge:
Die Ähnlichkeit zweier Folgen wird üblicherweise durch ihre Korrelation gemessen. Die Korrelation C zweier Folgenabschnitte der Länge n berechnet sich als die Zahl A der übereinstimmenden und der Zahl D der nicht übereinstimmenden Folgenglieder nach der Formel:
C := (A-D) / n
Der Erwartungswert für die Korrelation zweier unabhängiger Zufallsfolgen ist demnach also Null. Zwei Folgen, die häufiger übereinstimmen, haben dagegen einen positiven Korrelationswert. Im Grenzfall völliger Übereinstimmung ist A=n, D=0 und daher C=1. Umgekehrt erhält man bei weniger als n/2 Übereinstimmungen eine negative Korrelation. Der Betrag der Korrelation zweier Folgen ist daher ein Maß für deren Abhängigkeit.
Autokorrelation
Die Autokorrelationsfunktion C(t) misst die Ähnlichkeit einer Folge (s[i])=s[1] s[2] ... und der um t Stellen verschobenen Folge (s[i+t])=s[t] s[t+1] ... .
Man betrachtet einen Folgenabschnitt der Länge n und definiert:
A(t) := Anzahl der übereinstimmenden Glieder der Folgen (s[i]) und (s[i+t]) im betrachteten Abschnitt.
D(t) := Anzahl der nicht übereinstimmenden Glieder der Folgen (s[i]) und (s[i+t]) im betrachteten Abschnitt.
Die Autokorrelationsfunktion C(t) = (A(t)-D(t)) / n .
Im Falle von endlichen Folgen wird die Folge s (azyklisch) um t Positionen verschoben, das heißt die Folge (s[i+t]) hat nur n-t Folgenglieder (wenn n die Länge der Folge (s[i]) ist). Zur Berechnung der Autokorrelation betrachtet man nun die Folgen s[1] s[2] ... s[n-t+1] und s[t] s[t+1] ... s[n] und berechnet deren Korrelation.
Die Autokorrelationsfunktion wird unter anderem bei der Ermittlung der Periodenlänge zur automatischen Analyse des Vigenère-Verschlüsselungsverfahrens und Verschlüsselung durch byteweise Addition und exklusives Oder benutzt. Siehe dazu das Kapitel Szenarien.