摘要 |
Auf dem Gebiet der Informationsverarbeitung, z.B. bei Datenaustauschverfahren mit Quellenadressierung und bei Text-Editoren mit Zeilensuche mittels eines Identifiers, ist die Wiedergewinnung von gespeicherten Daten anhand eines Suchbegriffes bzw. Suchschlüssels (w) über diese Daten eine wichtige Aufgabenstellung. Um eine schnellere Entscheidung darüber herbeizuführen, ob ein dem zu prüfenden Suchschlüssel gleiches Datum in einem Speicher (7) vorhanden ist, wird ein Hasch-Verfahren angewendet. Dazu wird der Suchschlüssel in ein Polynom der Form <IMAGE> zerlegt, i = Laufvariable, k deren Grosstwert, wi = Polynomkoeffizient, p eine Potenz von 2, m = Anzahl Suchschlüssel in einer im Speicher (7) gespeicherten Adresstabelle. Der Suchvorgang erfolgt mittels einer rekursiven Hasch-Funktion der Form h(w) = hi(w) = hil(wi) + hio(hi-l(w)) (mod p) hl(w) = h11(w1) + h10(w0) unter Verwendung von im Speicher (7) gespeicherten HaschFunktionstabellen und Adress-Teiltabellen. Die Adressenvergleichsschaltung mit 3 Zwischenspeichern (1, 2, 3) für die Polynomkoeffizienten wi, einem Multiplexor 5, dem Speicher (7), einem Addierglied (13), 2 Registern (9, 15), einem Vergleiche,- (17), einem flankengetriggerten JK-Flip-Flop (19) mit ausgangsseitig angeschlossenem UND-Glied (20) und einem Steuerwerk (22) ermöglicht eine preisgünstige Realisierung des Suchverfahrens in Hardware.
|