Mustererkennung mittels Korrelation

Eine wesentliche Aufgabe in der digitalen Signalverarbeitung (DSP) ist die Erkennung von Bitmustern, die in digitalen Signalen codiert sind. Solche Muster können beispielsweise Datenpakete in Kommunikationsprotokollen, Synchronisationssequenzen oder spezifische Codes darstellen, die in einem kontinuierlichen Datenstrom identifiziert werden müssen.

Die Korrelation ist eine fundamentale Methode zur Mustererkennung. Sie misst die Ähnlichkeit zwischen einem empfangenen Signal und einem bekannten Referenzmuster. Durch ihren Einsatz können Signale selbst in einem Umfeld mit Rauschen oder anderen Störungen zuverlässig erkannt werden, da die Methode hochsensibel auf die formale Übereinstimmung zweier Signale reagiert. In der Praxis ermöglicht die Korrelation so die präzise Lokalisierung von Bitmustern – eine essenzielle Voraussetzung für die Netzsynchronisation, Datenextraktion und Fehlererkennung.

Im Folgenden wird erläutert, wie die Korrelation mathematisch und praktisch eingesetzt wird und warum die unnormalisierte Form oft nicht ausreicht.

Beispiel: Unnormalisierte Korrelation

In einem empfangenen Datenstrom soll ein spezifisches Muster gefunden werden (dies könnte z. B. ein Pilotsignal in einer PSK-Übertragung sein):

sample = np.array([1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0])
muster = np.array([0.0, 1.0, 1.0])

sample = np.array([1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0])
muster = np.array([0.0, 1.0, 1.0])

Das gesuchte Muster ist im Signal exakt zweimal enthalten (ab Index 3 und ab Index 7).
Mittels Kreuzkorrelation lassen sich diese Positionen rechnerisch bestimmen:

correlation = np.correlate(sample, muster, mode='valid')

correlation = np.correlate(sample, muster, mode='valid')

Für jeden möglichen Startindex im sample wird ein Übereinstimmungswert berechnet. Je größer dieser Wert, desto wahrscheinlicher ist ein Treffer. Das Ergebnis für unser Array sieht so aus:

Korrelation:  [1. 0. 1. 2. 1. 0. 1. 2. 2. 1. 0. 0. 0. 0.]

Korrelation:  [1. 0. 1. 2. 1. 0. 1. 2. 2. 1. 0. 0. 0. 0.]

An den Indizes 3, 7 und 8 wird jeweils der maximale Wert von 2 erreicht. Die Positionen 3 und 7 sind korrekte Treffer. Position 8 liefert jedoch fälschlicherweise denselben hohen Wert, obwohl der Signalausschnitt dort [1.0, 1.0, 1.0] lautet.

Der Grund hierfür liegt in der mathematischen Berechnung der unnormalisierten Korrelation:

$$K[i] = \text{sample}[i] \cdot \text{muster}[0] + \text{sample}[i+1] \cdot \text{muster}[1] + \text{sample}[i+2] \cdot \text{muster}[2]$$

Da das Muster an der ersten Stelle eine 0.0 aufweist, wird das erste Element des jeweiligen Signalausschnitts bei der Multiplikation eliminiert. Folglich liefert der falsche Ausschnitt [1.0, 1.0, 1.0] in der Summe exakt dasselbe Ergebnis wie der echte Treffer [0.0, 1.0, 1.0].

Dieses Verhalten führt zu sogenannten "False Positives" (Fehlalarmen). Um dies zu verhindern, weicht man auf die normalisierte Kreuzkorrelation (NCC) aus.

Die Normalisierung

Um die Werte unabhängig vom Signalpegel vergleichbar zu machen, wird im ersten Schritt die euklidische Norm (L2-Norm) des Musters ermittelt. Beispielsweise mit der Funktion numpy.linalg.norm. Diese zieht die Wurzel aus der Summe der Quadrate aller Elemente:

$$\text{muster_norm} = \sqrt{0^2 + 1^2 + 1^2} = \sqrt{2} \approx 1{,}41421$$

Für jede Position im Signal wird nun ebenfalls die Norm des jeweils aktuellen Ausschnitts berechnet:

$$\text{ausschnitt_norm} = \sqrt{\text{ausschnitt}[i]^2 + \text{ausschnitt}[i+1]^2 + \text{ausschnitt}[i+2]^2}$$

Anschließend wird das Skalarprodukt beider Vektoren (in Python np.dot(ausschnitt, muster)) berechnet und durch das Produkt ihrer beiden Normen dividiert:

$$\text{NCC} = \frac{\text{Skalarprodukt}(\text{ausschnitt}, \text{muster})}{\text{ausschnitt_norm} \cdot \text{muster_norm}}$$

Was ändert sich dadurch im Beispiel?

• An Position 7 ([0.0, 1.0, 1.0]) beträgt die Norm des Ausschnitts ebenfalls $\sqrt{2}$. Die normalisierte Korrelation ergibt exakt $1{,}0$ (eine perfekte Übereinstimmung).
• An Position 8 ([1.0, 1.0, 1.0]) beträgt die Norm des Ausschnitts hingegen $\sqrt{3} \approx 1{,}732$. Durch die Division durch den nun größeren Nenner sinkt der Korrelationswert an dieser Stelle auf ca. $0{,}816$. Der Fehlalarm ist damit mathematisch sauber eliminiert.

Das folgende Programm zeigt die vollständige Berechnung:

import numpy as np

def normalized_cross_correlation(sample, muster):
    muster_norm = np.linalg.norm(muster)

    correlation = []
    for i in range(len(sample) - len(muster) + 1):
        ausschnitt = sample[i:i + len(muster)]
        ausschnitt_norm = np.linalg.norm(ausschnitt)
        
        if ausschnitt_norm == 0 or muster_norm == 0: # Division durch Null vermeiden
            correlation.append(0)
        else:
            korr = np.dot(ausschnitt, muster) / (ausschnitt_norm * muster_norm)
            correlation.append(korr)

    return np.array(correlation)

sample = np.array([1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0])
muster = np.array([0.0, 1.0, 1.0])

ncc = normalized_cross_correlation(sample, muster)

print("Normalisierte Kreuzkorrelation:\n", np.round(ncc, 3))

# Exakte Übereinstimmung finden (NCC == 1)
exakte_treffer = np.where(np.isclose(ncc, 1.0))[0] # np.isclose fängt Gleitkomma-Rundungsfehler ab

if exakte_treffer.size > 0:
    for treffer in exakte_treffer:
        print(f"Exakte Übereinstimmung an Position: {treffer}")
else:
    print("Keine exakte Übereinstimmung gefunden")

import numpy as np

def normalized_cross_correlation(sample, muster):
    muster_norm = np.linalg.norm(muster)

    correlation = []
    for i in range(len(sample) - len(muster) + 1):
        ausschnitt = sample[i:i + len(muster)]
        ausschnitt_norm = np.linalg.norm(ausschnitt)
        
        if ausschnitt_norm == 0 or muster_norm == 0: # Division durch Null vermeiden
            correlation.append(0)
        else:
            korr = np.dot(ausschnitt, muster) / (ausschnitt_norm * muster_norm)
            correlation.append(korr)

    return np.array(correlation)

sample = np.array([1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0])
muster = np.array([0.0, 1.0, 1.0])

ncc = normalized_cross_correlation(sample, muster)

print("Normalisierte Kreuzkorrelation:\n", np.round(ncc, 3))

# Exakte Übereinstimmung finden (NCC == 1)
exakte_treffer = np.where(np.isclose(ncc, 1.0))[0] # np.isclose fängt Gleitkomma-Rundungsfehler ab

if exakte_treffer.size > 0:
    for treffer in exakte_treffer:
        print(f"Exakte Übereinstimmung an Position: {treffer}")
else:
    print("Keine exakte Übereinstimmung gefunden")

Im obigen Skript wird streng nach einer exakten Übereinstimmung (NCC == 1.0) gesucht. In realen Übertragungsszenarien (z. B. über Funk) wird ein Signal jedoch fast immer durch Rauschen verfälscht, sodass eine 100%ige Übereinstimmung praktisch nie vorkommt. In solchen Fällen definiert man einen Schwellwert (Threshold), ab dem ein Signal als "erkannt" interpretiert wird. Nachgelagerte Fehlererkennungs- und Korrekturverfahren prüfen anschließend, ob die detektierten Datenpakete valide sind.