Mustererkennung mittels Korrelation

Ein wesentliche Aufgabe in der digitalen Signalverarbeitung 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, die in der DSP zur Mustererkennung eingesetzt wird. Sie erlaubt es, die Ähnlichkeit zwischen einem empfangenen Signal und einem bekannten Referenzmuster zu messen. Durch den Einsatz der Korrelation können Signale in einem Umfeld mit Rauschen oder anderen Störungen zuverlässig erkannt werden, da sie besonders empfindlich auf die Übereinstimmung zwischen zwei Signalen reagiert. Insbesondere in der Praxis ermöglicht die Korrelation die präzise Lokalisierung von Bitmustern, was für Synchronisation, Datenextraktion und Fehlererkennung essenziell ist.

Im Folgenden wird erläutert, wie die Korrelation mathematisch und praktisch zur Erkennung von Bitmustern eingesetzt wird und welche Vorteile sie in der digitalen Signalverarbeitung bietet.

Beispiel:

In einer Gruppe von Werten soll ein 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])

Das Muster ist 2 mal im Beispiel enthalten.

Mittels Korrelation können die Positionen bestimmt werden.

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

Für jede Position in sample wird ein Wert für eine Übereinstimmung berechnet. Je größer er ermittelte Korrelationswert ist, desto wahrscheinlicher handelt es sich um eine Übereinstimmung.

Das Ergebnis der Korrelation ist wie folgt:

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

An der Stelle 3,7 und 8 ist der höchste Wert der Übereinstimmung. Die Position 8 ergibt eine Übereinstimmung, da dort alle 3 Zeichen im Muster vorhanden sind.
Der Grund liegt in der Methode wie eine Korrelation berechnet wird.

Für jede Position in sample wird folgende Berechnung durchgeführt:

korrelation = sample[i] * muster [0]. + sample[i+1] * muster[1]  + sample[i+2] * muster[2]

aufgrund der Berechnung ist der Wert für die Korrelation von 0,1,1 mit 0,1,1 identisch mit der Korrelation von 1,1,1 mit 0,1,1

Dieses Verhalten ist natürlich nicht zufriedenstellend, deshalb weicht man auf eine normalisierte Korrelation aus.

Im ersten Schritt wird ein Normwert für das Muster ermittelt.
Die Funktion numpy.linalg.norm kommt dazu zum Einsatz. Diese berechnet die Wurzel aus der Summe der Quadrate jedes Elements im Muster den Normalwert.

muster_norm = SQRT ( 0*0 + 1*1 + 1*1). = 1,44142

Für jede Position in sample wird nun ebenfalls zunächst der Normwert wie oben berechnet.

ausschnitt_norm = SQRT (ausschnitt[i]2 +  ausschnitt[i+1]2 + ausschnitt[i+2]2 )

An jeder Position wird nun jeweils das Skalarprodukt mit np.dot(ausschnitt, muster) berechnet und durch das Produkt der zugehörigen Normalwerte dividiert.

An der Position 7 ist der Normalwert für den Ausschnitt = 1.41421, an der Position 8 ist er dagegen 1.7320. Durch die Division ergibt sich an der Position 8 nun einen kleinerer Wert für die Korrelation. Statt der 1 wie aus der unnormierten Variante ist er nun 0.816.

Das folgende Programm zeigt die Berechnung komplett:

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:", ncc)

# Exakte Übereinstimmung finden (NCC == 1)
exakte_treffer = np.where(np.isclose(ncc, 1.0))[0] #np.isclose wird verwendet um Rundungsfehler zu berücksichtigen
if exakte_treffer.size > 0:
    for treffer in exakte_treffer:
        print(f"Exakte Übereinstimmung an Position: {treffer}")
else:
  print("Keine exakte Übereinstimmung gefunden")

Im Programm wird eine exakte Übereinstimmung ermittelt, da nur die Korrelation = 1 berücksichtigt wird. In “echten” Signalen kommen durch Störungen oder Übertragungseffekte nur selten 100%ige Übereinstimmungen vor. In diesem Fall legt man einen Schwellwert fest in dem man Signale als erkannt interpretiert.
Durch Fehlererkennungs- und Fehlerkorrekturcodes kann dann ermittelt werden, ob Übertragungsfehler vorliegen.