DE3889150T2

DE3889150T2 - Filter n-ten Ranges.

Info

Publication number: DE3889150T2
Application number: DE3889150T
Authority: DE
Inventors: Carol Bagdis; Glenn D House; Wanda T Reise
Original assignee: Polaroid Corp
Current assignee: Polaroid Corp
Priority date: 1987-06-15
Filing date: 1988-05-24
Publication date: 1994-08-04
Anticipated expiration: 2008-05-25
Also published as: CA1286732C; US4802108A; JPS6416114A; EP0295464A3; DE295464T1; EP0295464B1; DE3889150D1; EP0295464A2

Description

Die Erfindung bezieht sich auf eine Signalverarbeitung allgemein und insbesondere auf eine Bild- und/oder Sprachverarbeitung. Insbesondere bezieht sich die Erfindung auf ein nicht-lineares Filter und auf ein Verfahren, welches anwendbar ist, um eine Filterung n-ten Ranges vorzunehmen mit geeigneter Wahl des Ranges zur Zentralwertfilterung.

Beschreibung des Standes der Technik

Die Filterung n-ten Ranges wird weit verbreitet benutzt bei der Sprach- und Bildverarbeitung. Es ist eine Technik zur Durchführung einer nicht-linearen Glättung eines eindimensionalen oder eines mehrdimensionalen Signals, welches aus diskreten Abtastwerten besteht. Durch das Filter wird für jeden solchen Eingangs-Abtastwert ein Ausgangs-Abtastwert erzeugt. Jeder Eingangs-Abtastwert und eine gewisse vorgewählte Zahl von benachbarten Abtastwerten werden in einem Gleitfenster gesammelt. Der Ausgangswert ist der n-te niedrigste Abtastwert innerhalb des Fensters, wenn n die Rangordnung des Filters ist. Wenn n der mittlere Abtastwert ist (d. h. es gibt gerade so viele Abtastwerte im Fenster mit einem größeren Wert als der mittlere Abtastwert wie Abtastwerte im Fenster mit einem niedrigeren Wert), so wird die Rangordnung des Filters auf ein Mittelwertsfilter bezogen. Die resultierende Ausgangsfolge für gefilterte Abtastwerte sucht Polynomen-Trends in der Eingangs-Abtastwertfolge zu folgen, während deutliche Diskontinuitäten kurzer Dauer ausgefiltert werden. D. h. diese Art der Filterung ist speziell zweckmäßig zur Reduzierung der Effekte hoher Übergangsstörspitzen in dem behandelten Signal.
Im Stande der Technik sind zahlreiche Ausführungen verwirklicht oder vorgeschlagen worden, mit denen sowohl eine eindimensionale als auch eine zweidimensionale Rangordnungsfilterung, speziell eine Mittelwertsfilterung, durchgeführt werden kann. Eine derartige Filterung erfordert eine beträchtliche Verarbeitungszeit und macht die Verwirklichung noch schwieriger.
In der Literatur finden sich Analysen verschiedener Möglichkeiten einer Rangordnungsfilterung mit spezieller Berücksichtigung der Komplexheit und Geschwindigkeit der Verarbeitung einschließlich Type und Zahl der Operationen, die durchgeführt werden müssen, und Zahl der erforderlichen Taktzyklen. Bisher wurde das Augenmerk auf die Tatsache gerichtet, daß die VLSI-Technologie dem Systemdesigner ein hohes Potential zur Durchführung paralleler Operationen liefert, wobei das Potential für Mittelwertsfilter ausgebildet ist. Jedoch lassen die früheren Versuche in dieser Richtung sehr viel Raum für weitere Verbesserungen.
Oflazer diskutiert ein Einchip-Eindimensional-Mittelwertfilter, welches eine ungerade/gerade Transpositionsart als Highlevel-Algorithmus und ein systolitisches Datenflußkonzept bei dem Bitlevel benutzt, um einen hohen Durchsatz zu erreichen. K. Oflazer, "Design and Implementation of a Single Chip 1-D Median Filter", I. E. E. E. Trans. on Acoustics, Speech and Sig. Proc., Vol. ASSP-31, Nr. 5, Oktober 1983, S. 1165-1168. Der Verfasser bemerkt, daß die Netzwerkimplementierung der Ungerade/Gerade-Transposition Chipflächen erfordert, die proportional zum Quadrat der Fenstergröße sind, und demgemäß ist seine Ausbildung nur für Mittelwertfilter mit kleinen Fenstergrößen geeignet.
Huang et al. haben einen zweidimensionalen Mittelwertfilteraufbau und -algorithmus und ein zugeordnetes Verfahren beschrieben, die auf der Speicherung des Grauwert-Histogramms der MN-Bildelemente in einem Fenster von M x N Zahlen basieren und auf der Aktualisierung des Histogramms, wenn sich das Fenster bewegt. T. S. Huang et al., "Fast Two- Dimensional Median Filtering Algorithm", I. E. E. E. Trans. on Acoustics, Speech on Sig. Proc., Vol. ASSP-27, Nr. 1, Februar 1979, S. 13-18. Gemäß Huang et al. benötigt das Histogramm nur eine partielle Aktualisierung, wenn das Fenster bewegt wird. Durch Beobachtung, wieviele Bildelemente über und unter den vorherigen Mittelwert fallen, kann der frühere Mittelwert einfach jeweils dann eingestellt werden, wenn das Fenster bewegt wird, und zwar auf den richtigen neuen Mittelwert, indem stufenweise im Histogramm nach oben und unten gegangen wird. Der Algorithmus erfordert ein schnelles RAM für das Histogramm, aber die Zeit für die Stufenprozedur ist datenabhängig. Infolgedessen muß man für den schlimmsten Fall eine Zahl von Stufen zulassen gleich der Zahl von "Buckets" im Histogramm. Dieser Algorithmus erfordert etwa 2N+10 Vergleiche, um den Mittelwert von jeder MN-Gruppe von Abtastwerten zu erlangen.
Danielsson hat vorgeschlagen, den mittleren oder jeden anderen Rangordnungswert dadurch zu finden, daß eine Gruppe von Histogrammen gesammelt wird. P. Danielsson, "Getting the Median Faster", Computer Graphics and Image Processing, Vol. 17, S. 71-78 (1981). Dieses Verfahren resultiert jedoch in einem mühsamen Histogrammsammelprozeß. In der Veröffentlichung bemerkt Danielsson, daß Kruse vorgeschlagen hat, statt der Anordnung von Histogrammen eine wiederholte Benutzung der Argumente vorzunehmen und sie mit einem sukzessive verfeinerten Mittelwert zu vergleichen. Unglücklicherweise erfordert dies, wie Danielsson beobachtet hat, daß jedes Argument "k"mal wiederholt werden muß, wobei k die Zahl der Danielsson-Typ-Histogramme und die Zahl von Bits pro Abtastwert ist.
Der Erfindung liegt die Aufgabe zugrunde, eine verbesserte Anordnung und ein verbessertes Verfahren zur Rangordnungsfiltrierung zu schaffen.
Weiter bezweckt die Erfindung die Schaffung eines verbesserten Verfahrens und verbesserten Gerätes zur Mittelwertsfilterung.
Ein weiteres Ziel der Erfindung besteht darin, eine Rangordnungsfilteranordnung zu schaffen, die wirksam ist und integrierte Schaltungen unter Benutzung eines Siliziumcompilers verwendet.
Ein weiteres Ziel der Erfindung besteht darin, eine Anordnung zu schaffen, die eine lineare Beziehung zwischen Fenstergröße (d. h. Zahl der Abtastwerte im Fenster sowie Zahl der Bits in jedem Abtastwert) und der erforderlichen Chipfläche darstellt.

Zusammenfassung der Erfindung

Die Erfindung bezieht sich auf ein Verfahren und eine Vorrichtung zur Auffindung einer gewählten Rangordnungszahl aus mehreren Abtastwertzahlen in Binärformat. Es wird zunächst die Zahl der höchstwertigen Binärziffern von 1 oder 0 in den Abtastwertzahlen gezählt, und die höchstwertige Binärstelle für die gewählte Rangordnungszahl wird als Funktion davon gewählt, ob die Zahl der so gezählten höchstwertigen Binär-1- oder Binär-0-Werte einen vorbestimmten Schwellwert erreicht. Sämtliche folgenden niedrigwertigeren Binärbits für jede der Abtastwertzahlen wird dann auf den gleichen Wert gesetzt wie das höchstwertige Bit jener Abtastwertzahl, bei der das höchstwertige Binärbit von dem vorher gewählten Binärbit unterschieden ist. Dann wird die Zahl der nächsten höchstwertigen Binär-1- oder Binär-0- Ziffern in der Abtastwertzahl gezählt, und das nächste höchstwertige Binärbit für die gewählte Rangordnungszahl wird als Funktion davon gewählt, ob die Zahl der nächsten höchstwertigen Binär-1- oder Binär-0-Stellen, die auf diese Weise gezählt wurden, einen vorbestimmten Schwellwert erreicht. All die folgenden Binärbits geringerer Wertigkeit für jede Austastwertzahl werden dann auf den gleichen Wert wie das nächste höchstwertige Binärbit jener Austastwertzahl gesetzt, in der das nächste höchstwertige Binärbit von dem vorher gewählten Binärbit für das nächste höchstwertige Binärbit der gewählten Rangordnungszahl unterschieden ist. Dieses Verfahren wird fortgesetzt, indem in der beschriebenen Weise nacheinander wenigerwertige Binärbits in der Abtastwertzahl vorgeschoben werden, bis die geringstwertigen Binärbits der Abtastwertzahlen behandelt worden sind.
Der Schwellwert wird dadurch bestimmt, daß von der Zahl der Abtastwertzahlen die Rangordnungszahl subtrahiert wird, wenn die Binär-1-Werte gezählt werden. Wenn umgekehrt die Binär-0-Werte gezählt werden, dann ist der Schwellwert gleich der Rangordnungszahl. Eine Schaltung zur Verwirklichung des Verfahrens der Erfindung umfaßt wenigstens eine erste gewählte Gruppe von Logikschaltungen entsprechend der Zahl der Abtastwertzahlen. Die Schaltung weist außerdem wenigstens eine Summierungsstufe für die Gruppe der logischen Schaltungen und eine Schwellwertschaltung für die Summierungsschaltung auf. Die Schwellwertschaltungen liefern beide Ausgangssignale, die die Rangordnungszahl definieren, und außerdem Steuersignale nach den Logikkreisen. Mehrere Flip-Flops, und zwar eines für jedes Bit der Abtastwertzahlen, wirken als Schieberegister, um Gruppen gleichwertiger Binärbits von den Abtastwertzahlen nach den logischen Kreisen zu überführen.

Beschreibung der Zeichnung

Die neuartigen Merkmale, die als charakteristisch für die Erfindung angesehen werden, ergeben sich insbesondere aus den beiliegenden Ansprüchen. Die Erfindung selbst jedoch, sowohl was die Anordnung als auch das Arbeitsverfahren betrifft, zusammen mit anderen Zielen und Vorteilen, ist am besten aus der folgenden Beschreibung von Ausführungsbeispielen ersichtlich, die in Verbindung mit der beiliegenden Zeichnung beschrieben werden:
Fig. 1 zeigt ein Flußdiagrainm des erfindungsgemäßen Verfahrens,
Fig. 2 ist eine schematische Darstellung eines beispielsweisen Feldes von fünf 4-Bit-Abtastwerten, deren Mittelwert unter Benutzung des Verfahrens nach Fig. 1 zu bestimmen ist,
Fig. 3 bis 6 liefern kollektiv eine Reihe von Illustrationen, welche die Folge der Erzeugung der Bits der Mittelwerte für das Beispiel nach Fig. 2 erkennen lassen, und zwar unter Benutzung des Verfahrens nach Fig. 1,
Fig. 7 ist ein Blockschaltbild, welches den Aufbau eines Gerätes zur Durchführung des Verfahrens nach Fig. 1 veranschaulicht, und zwar bei der Anwendung auf fünf Abtastwerte mit je fünf Bits,
Fig. 8 ist ein Blockschaltbild, welches weitere Einzelheiten einer Einzelbit-Schnittstufe gemäß Fig. 7 erkennen läßt, und
Fig. 9 ist eine Wahrheitstabelle für den MF-Logikblock gemäß Fig. 8.

Beschreibung des bevorzugten Ausführungsbeispiels

Das Verfahren gemäß der Erfindung wird beispielsweise in Verbindung mit dem Flußdiagramm nach Fig. 1 für ein Rangordnungsfilter veranschaulicht, bei welchem die Rangordnung so gewählt ist, daß sie den Mittelwert bildet.
Die erste Stufe (Schritt 100) bestimmt den Schwellwert als direkte Funktion der selektiven Rangordnungsbildung einer Zahl von Abtastwerten in einem gewählten Fenster von Abtastwerten. Bei diesem Beispiel müssen die binären 1er gezählt werden, so daß der Schwellwert durch Subtraktion der Rangordnungszahl von der Zahl der Abtastwerte bestimmt wird. Wenn umgekehrt binäre 0en zu zählen sind, dann wäre der Schwellwert gleich der Rangordnungszahl. Für den Mittelwertfilter, bei dem die Zahl der Abtastwerte gerade ist, kann entweder der kleinere oder der größere der beiden Mittelabtastwerte im Fenster gewählt werden, um als Mittelwert-Rangordnungszahl betrachtet zu werden.
Nachdem der Schwellwert für den Mittelwertfilter in der beschriebenen Weise bestimmt wurde, werden die Binärdarstellungen der Abtastwerte im Fenster in einem zweidimensionalen Feld (Schritt 101) so angeordnet, daß jede Zeile einen Abtastwert repräsentiert und die jeweiligen Bits der Abtastwerte in vertikalen Reihen ausgerichtet sind. Fig. 2 zeigt eine solche Anordnung für einen Fall mit fünf 4-Bit-Abtastwerten, welche die Dezimalwerte 1, 5, 2, 9 bzw. 6 aufweisen. Die verschiedenen Reihen des Feldes sind, wie am besten aus Fig. 3 ersichtlich, mit 1 bis 4 von dem höchstwertigen Bit (MSB) bis zu dem geringstwertigen Bit (LSB) numeriert, und ein Index "x" wird benutzt, um die Reihenzahl anzugeben.
Das in Fig. 1 in Form eines Flußdiagramms veranschaulichte Verfahren schreitet dann fort, um den Mittelwert zu bestimmen. Es wird mit der Reihe Nr. 1 begonnen (Schritt 102; x = 1), und dies ist jene Reihe, die die höchstwertigen Bits enthält. Die Zahl der binären 1er in dieser Reihe wird gezählt (Schritt (104). Die Zählung der 1er in der Reihe wird dann gegen den vorher bestimmten Schwellwert (Schritt 106) überprüft. Wenn die Zahl der binären 1er größer ist als der Schwellwert, dann wird das höchstwertige Bit in dem Ausgangswort (mit Bx 1 oder kurz B&sub1; bezeichnet) dem Binärwert 1 (Schritt 108) zugeordnet, und die binären 1er- Bits in jeder Zeile rechts von jeder binären 0 in der ersten Reihe (Schritt 110) werden auf binär 0 gesetzt. Wenn jedoch die Zahl der binären 1er in der ersten Reihe kleiner oder gleich dem Schwellwert ist, dann zweigt die Steuerung vom Schritt 106 auf den Schritt 112 ab, wo das Ausgangsbit B&sub1; auf binär 0 gesetzt ist (Schritt 112); und die binären 0-Bits in jeder Zeile rechts einer jeden binären 1 in der ersten Reihe (Schritt 114) werden auf binär 1 geändert.
Von den beiden Schritten 110 oder 114 wird unter der Annahme, daß alle Reihen nicht verarbeitet sind, die Reihennummer um 1 erhöht, und die Steuerung läuft auf den Schritt 104 zurück, an welcher Stelle das Verfahren für die Bitposition der nächstgeringeren Wertigkeit wiederholt wird. Wenn sämtliche Reihen verarbeitet sind, ist die Ausgangs-Rangordnungszahl vollständig, und das Fenster kann durch eine gewählte Zahl von Abtastwerten bewegt werden, um das Verfahren wieder zu starten und einen folgenden gefilterten Ausgangswert zu erzeugen. Die Benutzung des Schwellwertes ist, wie sich ergibt, ein zweckmäßiger Weg, um zu entscheiden, ob die Abtastwerte mehr binäre 0en oder mehr binäre 1er in irgendeiner gewählten Bitposition haben, wodurch eine Suche möglich wird, um sich Bit um Bit auf den Abtastrangwert einzupeilen. Obgleich die Bestimmung des Schwellwerts beispielsweise unter Bezugnahme auf den Mittelwertfilter diskutiert wird, ist leicht verständlich, daß der Schwellwert so gewählt werden kann, daß er irgendeiner gewählten Rangordnung für einen Filter entspricht, und dies ist keineswegs beschränkt auf den Mittelwertfilter.
Unter Benutzung des Ausführungsbeispiels nach Fig. 2 wird das Verfahren nach Fig. 1 nunmehr Schritt für Schritt für ein Mittelwertfilter diskutiert, wie dies am besten aus den Fig. 3 bis 6 hervorgeht. Der anfängliche Status des Feldes ist in Fig. 3 bei 120 dargestellt. Bei diesem Beispiel wird der Schwellwert in der vorbeschriebenen Weise als 2 bestimmt, d. h. die Zahl der Abtastwerte (5) - Mittelwert- Rangordnungszahl (3) = 2. Die Zahl der binären 1er in der ersten Reihe (d. h. der am weitesten links liegenden Reihe mit den höchstwertigen Bits) wird so bestimmt, daß sie kleiner ist als der Schwellwert von 2, so daß das erste Bit des Mittelwertes eine binäre 0 ist (wie unter der strichlierten Linie angegeben). Gemäß dem Schritt 114 werden alle Bitwerte in der vierten Zeile des Feldes rechts der Reihe 1 auf den Wert binär 1 gesetzt, weil eine binäre 1 in der ersten Reihe der vierten Zeile vorhanden ist. Das Feld ist nunmehr in der Weise modifiziert, wie dies bei 122 in Fig. 4 dargestellt ist. Wenn man als nächstes zu der zweiten Reihe fortschreitet, ist ersichtlich, daß dort drei binäre 1er vorhanden sind, und dies ist größer als der Schwellwert von 2. Demgemäß wird der zweitwertigste Bit des Mittelwertes auf binär 1 gestellt, und jene binären 1er in jeder Zeile rechts der binären 0 der zweiten Reihe werden auf binär 0 gesetzt, wodurch sich das Feld 124 gemäß Fig. 5 ergibt.
Nunmehr wird auf die dritte Reihe (d. h. die nächstwertige Reihe) übergegangen, und es ist aus dem Feld 124 gemäß Fig. 5 ersichtlich, daß nur zwei binäre 1er vorhanden sind, und dies ist weniger oder gleich dem Schwellwert von 2. Deshalb wird das dritte Bit des Abtastwertes auf binär 0 gesetzt, wie dies aus Fig. 5 ersichtlich ist. Des weiteren werden die binären 0en in allen Zeilen (d. h. den Zeilen 4 und 5) rechts der binären 1er in der dritten Reihe auf binär 1 gesetezt, wobei nur ein einziges Bit in der Zeile 5 geändert wird, da das andere Bit in der Zeile 4 bereits auf binär 1 steht. Das resultierende Feld ist in Fig. 6 bei 125 dargestellt.
Das vierte Bit des Mittelwertes ergibt sich aus der vierten Reihe des Feldes 126 als binär 1, da diese Reihe nunmehr drei binäre 1er besitzt, und dies ist mehr als der Schwellwert von 2; demgemäß ist das vierte Bit des Mittelwertes eine binäre 1, wie aus Fig. 6 ersichtlich.
Der Wert der Mittelwertszahl ist nunmehr die binäre Zahl 0101, und dies ist äquivalent der Dezimalzahl 5, und dies ist der Mittelwert der fünf Abtastwerte im Fenster.
Das obige Verfahren resultiert aus der Tatsache, daß Bits in einer Zeile, die entweder auf binär 0 oder binär 1 gesetzt sind, dauerhaft gesetzt sind und danach nicht geändert werden können. Wenn beispielsweise der Fall betrachtet wird, wo eine Zeile auf binär 1 gesetzt ist, beginnend mit der r-ten Reihe, dann sind für jede Reihe, deren Reihennummer größer ist als r (d. h. die an einer geringwertigeren Bitposition steht), wenn mehr binäre 0en als binäre 1er in der Reihe vorhanden sind, die Zeilen benachbart zu jeder binären 1 in der Reihe auf binär 1 gestellt; und wenn die Zeilen bereits auf binär 1 gestellt sind, dann behalten sie jenen Wert bei. Wenn mehr binäre 1er als binäre 0en in der Reihe vorhanden sind, dann werden die Zeilen benachbart zu jeder binären 1 in der Reihe nicht geändert. Umgekehrt soll eine Situation betrachtet werden, wo eine Zeile beginnend mit der r-ten Reihe auf binär 0 gesetzt ist. Dann sind für jede Reihe, deren Reihenzahl größer als r ist (d. h. eine geringwertigere Bitposition hat), wenn mehr binäre 1er als binäre 0en in der Reihe sind, die Zeilen benachbart zu jeder binären 0 in der Reihe auf binär 0 gestellt; und wenn die Zeilen schon auf binär 0 gesetzt sind, verbleiben sie auf diesem Wert. Wenn mehr binäre 0en als binäre 1er in der Reihe vorhanden sind, dann werden die Zeilen benachbart zu jeder binären 0 in der Reihe nicht geändert.
Aus der vorstehenden Beschreibung ergibt sich, daß das erfindungsgemäße Verfahren keinen Speicher für irgendeine frühere Zeile erfordert (d. h. eine Reihe mit einer geringeren Reihenzahl und einer Bitposition mit höherer Wertigkeit); auch ist keine laufende Summe erforderlich, die aufrechterhalten werden muß. Sämtliche Operationen erfolgen auf einer Bitbasis, und die Einstellung (auf binär 0 oder binär 1) der Bits in den Reihen geringerer Wertigkeit der Bitstelle tritt innerhalb eines einzigen Taktzyklus auf. Im Gegensatz zu den meisten bekannten Versuchen ist die Logik sehr einfach. Außerdem ist keine zusätzliche Logik erforderlich, um irgendwelche Spezialfälle zu behandeln, was im allgemeinen nicht der Fall ist bei den erwähnten bekannten Anordnungen.
Die Hardware zur Durchführung des Verfahrens nach der Erfindung erfordert einige wenige Standardbausteine, die gleichförmig miteinander verbunden sind. Ein Bit-Scheibenaufbau ist zu bevorzugen, weil dadurch die Schaltung auf fast jede Größe erweitert werden kann. Die Größe der Schaltung und die entsprechenden integrierten Schaltungschips können schlimmstenfalls linear gemäß der Zahl der Abtastwerte im Fenster und auf die Größe von jedem Abtastwert skaliert werden. Die Benutzung einiger weniger standardisierter Bausteine oder "Zellen" ermöglicht außerdem einen integrierten Schaltungsaufbau.
Nunmehr wird auf Fig. 7 Bezug genommen. Hier ist ein Blockschaltbild 10 dargestellt, mit dem das erfindungsgemäße Verfahren verwirklicht werden kann, und diese Schaltung umfaßt eine programmierbare Schaltung 151, die die Fensterlänge bestimmt, und fünf Bitschaltungen 152 bis 160, die in Reihe zueinander geschaltet sind. Die die Fensterlänge bestimmende Schaltung 151 wird in der nachstehend beschriebenen Weise so programmiert, daß ein Abtastwertfenster definiert wird, das fünf Abtastwerte mit je fünf Bits enthält, obgleich verständlicherweise die Schaltung 10 auch so programmiert werden könnte, daß weniger Abtastwerte verarbeitet werden. Sämtliche Bitstufen 152 bis 160 sind identisch, und daher ist es lediglich erforderlich, im einzelnen die Arbeitsweise einer solchen Stufe 152 zu beschreiben, die in ihren Einzelheiten in Fig. 8 dargestellt ist.
Aus Fig. 8 ist ersichtlich, daß die Bitstufe 152 einen String von seriell geschalteten D-Flip-Flops 162 bis 170 aufweist, die zusammen ein Schieberegister bilden, um ein Bit gewählter Wertigkeit von jedem Abtastwert zu empfangen (gemäß dem Ausführungsbeispiel ist es bei der Bitschaltung 152 das höchstwertige Bit). Jedes der Flip-Flops 162 bis 170 liefert bei Q ein Ausgangssignal, welches durch das Ausgangssignal bestimmt wird, welches dem Eingang D um einen Taktimpuls früher zugeführt wurde. Wenn demgemäß beispielsweise eine binäre 1 am Eingang D eines Flip-Flops 162 bis 170 auftritt, dann wird am Ausgang Q nach dem nächsten Taktimpuls eine binäre 1 stehen. Für die Bitstufe 152 ist es klar, daß die Flip-Flops 162 bis 170 so getaktet sind, daß sie kollektiv als ein serielles Schieberegister arbeiten. Demgemäß liefert jedes der fünf Flip-Flops schließlich Ausgänge der höchstwertigen Bits von einem der fünf Abtastwerte.
Nunmehr wird auf Fig. 9 Bezug genommen. Hier ist eine Tabelle für die binären Eingangs- und Ausgangssignale mehrerer MF-Logikschaltungen 172 bis 180 dargestellt. Die Bitschaltung 152 gemäß Fig. 8 empfängt die höchstwertigen Bits von den Abtastwerten, und die Zin-, Oin-Eingangssignale der MF-Logikschaltungen 172 bis 180 werden von der programmierbaren Schaltung 151 für die Fensterlänge empfangen, die sämtliche Zin-, Oin-Eingangssignale auf binär 0 stellt. Indem auf diese Weise die Zin-, Oin- Steuersignale nach den MF-Logikschaltungen 172 bis 180 in dieser Weise gesetzt sind, bewirken die MF-Logikschaltungen eine Übertragung der D-Eingänge ohne Änderung der entsprechenden Ain-Leitungen, die ihrerseits an eine Summierungsschaltung 190 angeschlossen sind. Demgemäß werden die höchstwertigen Bits der fünf Abtastwerte ohne Änderung durch die jeweiligen Flip-Flops 162 bis 170 und die MF-Logikschaltungen 172 bis 180 auf die Summierungsschaltung 190 übertragen. Die Summierungsschaltung 190 bewirkt ihrerseits ein Aufaddieren der Ausgangsbits von allen MF-Logikschaltungen in der Bitstufe 152, um eine Zählung der Zahl der binären 1er in der Reihe mit höchstwertigen Bits aus dem Feld der Abtastwerte zu bewirken. Die Ausgangszählung wird dann einer Schwellwertschaltung 192 zugeführt, die die vorher gezählte Zahl der binären 1er zu dem gewählten Schwellwert addiert. Im Falle des Mittelwertfilters würde der Schwellwert in einer Weise wie oben erwähnt bestimmt, und im Falle irgendeines anderen Filters einer Rangordnung würde der Schwellwert gemäß der gewählten Rangordnung bestimmt.
Die Schwellwertlogikschaltung 192 liefert ihrerseits einen Ausgang mit binär 1, wenn die Zahl der binären 1er, die von der Summierungsstufe 190 gezählt wurde, den vorbestimmten Schwellwert überschreitet. Dann wird die binäre 1 von der Schwellwertschaltung 192 ausgegeben, um das höchstwertige Bit zu liefern, nämlich eine binäre 1 der Mittelwertzahl am Ausgang B, um gleichzeitig den Aout-Anschluß jeder MF- Logikschaltung 172 bis 180 auf binär 1 zu setzen. Nunmehr wird auf die Wahrheitstabelle gemäß Fig. 9 Bezug genommen. Hieraus ist ersichtlich, daß für jene MF-Logikschaltungen, bei denen D und Aout beide binäre 1er sind, Zout und Oout beide binär 0 sind, wodurch die entsprechende MF-Logikschaltung in der nächstfolgenden Bitstufe 154 freigeschaltet wird, um den nächstwertigen Bit von dem Abtastwert nach Ain ohne Änderung zu übertragen. Für jene MF-Logikschaltungen jedoch, bei denen Aout binär 1 und D binär 0 ist, wird Zout binär 1 und Oout wird binär 0, wodurch die entsprechenden Logikschaltungen in der nächstfolgenden Bitschaltung 154 freigeschaltet werden, um Ain auf binär 0 zu setzen, unabhängig von dem Binärwert des nächstwertigen Bits aus dem Abtastwert.
Wenn umgekehrt die Zahl der binären 1er, die von der Summierungsstufe 190 gezählt wurden, den vorbestimmten Schwellwert nicht übersteigt, dann liefert die Schwellwertlogik 192 einen Ausgang von binär 0. In diesem Fall wird die binäre 0 von der Schwellwertschaltung 192 ausgegeben, um das höchstwertige Bit, binär 0, der Mittelwertzahl am Ausgang B zu liefern und gleichzeitig den Aout-Anschluß jeder MF- Logikstufe 172 bis 180 auf binär 0 zu setzen. Hier wird wiederum auf die Wahrheitstabelle gemäß Fig. 9 Bezug genommen. Hieraus ist ersichtlich, daß für jene MF-Logikschaltungen, wo Ain und D beide binär 0 sind, Zout und Oout beide binär 0 werden, wodurch die entsprechende MF-Logikschaltung in der nächstfolgenden Bitstufe 154 freigeschaltet wird, um das nächstwertige Bit aus dem Abtastwert auf Ain ohne Änderung zu übertragen. Für jene MF-Logikschaltungen jedoch, bei denen Aout binär 0 und D binär 1 ist, wird Zout binär 0, und Oout wird binär 1, wodurch die entsprechende Logikschaltung in der nächstfolgenden Bitstufe 154 freigeschaltet wird, um Ain auf binär 1 zu setzen, und zwar unabhängig von dem Binärwert des nächstwertigen Bits des Abtastwertes. So ergibt sich aus der Wahrheitstabelle gemäß Fig. 9, daß dann, wenn Zout, Oout von der MF-Logikschaltung in der vorerwähnten Weise auf binär 0 bzw. binär 1 geändert wurden, alle folgenden Binärbits geringerer Wertigkeit für diesen Abtastwert auf binär 1 gesetzt werden, während umgekehrt dann, wenn Zout, Oout der MF-Logikschaltung in der erwähnten Weise auf binär 1 bzw. binär 0 geändert wurden, sämtliche folgenden Binärbits geringerer Wertigkeit für diesen Abtastwert auf binär 0 gesetzt werden.
Diese Charakteristik der oben beschriebenen Schaltung 10 gemäß der Erfindung kann auch benutzt werden, um die Schaltung freizuschalten und das Fenster von Abtastwerten und Prozeßabtastwerten von weniger als fünf zu ändern, ohne daß die Schaltung modifiziert würde. Dies kann einfach dadurch geschehen, daß die programmierbare Fensterlängenschaltung 151 gesteuert wird, um logische Binär-0- bzw. Binär-1-Eingangssignale den Eingängen Zin bzw. Oin der MF-Logikschaltung 178 zu liefern, und logische Binär-1- bzw. Binär-0-Eingangssignale den Eingängen Zin bzw. Oin der MF-Logikschaltung 180 zuzuführen. Wiederum ergibt sich aus der Wahrheitstabelle gemäß Fig. 9, daß alle folgenden logischen MF-Schaltungen (nicht dargestellt), die seriell in einer Zeile an die MF-Logikschaltung 178 angeschlossen sind, die, wie vorbeschrieben, Zin-, Oin-Eingänge aufweist, die auf binär 0 bzw. binär 1 gesetzt sind, bewirken, daß Binär-1-Logikeingangssignale an ihren entsprechenden Summierungsschaltungen (nicht dargestellt) erscheinen. In gleicher Weise bewirken alle folgenden MF-Logikschaltungen (nicht dargestellt), die seriell in einer Zeile gegenüber der MF-Logikschaltung 180 angeordnet sind, die, wie oben erwähnt, Zin, Oin-Eingänge aufweist, die auf binär 1 bzw. binär 0 gesetzt sind, daß Binär-O-Eingangssignale zu den entsprechenden Summierungsschaltungen (nicht dargestellt) gelangen. So ist ohne weiteres verständlich, daß die Wirkung sämtlicher Flip-Flops und MF-Logikschaltungen (nicht dargestellt), die seriell in einer Zeile mit dem Flip-Flop 168 und der MF-Logikschaltung 178 geschaltet sind, durch sämtliche Flip-Flops und MF-Logikschaltungen (nicht dargestellt), die seriell in einer Zeile mit dem Flip-Flop 170 und der MF-Logikschaltung 180 geschaltet sind, ausgeglichen wird, wodurch die Schaltung 10 gemäß Fig. 7 beschränkt wird auf eine Arbeitsweise als Rangordnungsfilter oder als Mittelwertsfilter für nur diese drei Abtastwerte, wobei wirksam die letzten beiden Abtastwerte ausgeschaltet werden. Die Schaltung 10 nach Fig. 7 kann auch auf einfache Weise ausgedehnt werden, um mehr als fünf Abtastwerte zu verarbeiten, indem die erforderlichen Flip-Flops und MF-Logikschaltungen jeder Bitschaltung 152 bis 160 zugeordnet werden und indem die Zahl der Eingänge an der Summierungsstufe vergrößert wird. Die Zahl der Binärbits für jeden Abtastwert kann leicht erhöht bzw. erniedrigt werden, indem einfach die Zahl der Bitkreise erhöht oder erniedrigt wird.
Es ist klar, daß, nachdem der Mittelwert oder der Rangordnungswert jenachdem für eine spezielle Gruppe von Abtastwerten innerhalb eines ersten gewählten Fensters vorgesehen ist, eine neue Gruppe von Abtastwerten innerhalb eines weiteren gewählten Fensters in die Bitschaltungen 152 bis 160 durch die jeweiligen Flip-Flops in der erwähnten Weise getaktet werden kann. So ermöglicht die modulare Natur der oben beschriebenen Schaltung leicht eine Erweiterung oder Zusammenziehung.
Die Erfindung wurde vorstehend in Verbindung mit mehreren miteinander verbundenen Bitschaltungen 152 bis 160 beschrieben. Es ist jedoch für den Fachmann klar, daß nur eine Bitschaltung erforderlich ist und daß sie wiederholt in der beschriebenen Weise benutzt werden kann, um jedes Bit in der Rangordnungszahl zu bestimmen. Die jeweiligen Taktsignale müssen ebenso wie eine Verriegelungsschaltung vorgesehen werden, um die Steuersignale zu halten, nachdem jedes Bit in der Rangordnungszahl bestimmt worden ist.
Vorstehend wurden das Verfahren und ein typisches Ausführungsbeispiel der Erfindung beschrieben. Es sind jedoch zahlreiche Abwandlungen, Ergänzungen oder Verbesserungen für den Fachmann denkbar. Beispielsweise führt die modulare Gestalt der erwähnten Schaltungsanordnung leicht zu einer Expansion oder Kontraktion. Außerdem kann der Rang des gewählten Abtastwertes innerhalb der Gruppe von Abtastwerten geändert werden, indem der Schwellwert geändert wird. Die Größe des Fensters der Abtastwerte kann ebenfalls innerhalb der Grenzen der Schaltung geändert werden. Das heißt, daß die Gruppe von Abtastwerten im Fenster kleiner sein kann als die maximale Fenstergröße, für die die Schaltung ausgelegt ist, und unnötige Zeilen in der Schaltung können wirksam paarweise wegfallen, indem eine Zeile auf alle binären 0en gesetzt und die andere Zeile auf alle binären 1er gesetzt wird.
Weitere Ausführungsbeispiele der Erfindung einschließlich Ergänzungen, Subtraktionen, Streichungen und andere Modifikationen der beschriebenen Ausführungsbeispiele der Erfindung sind für den Fachmann klar, und sie liegen im Rahmen der folgenden Ansprüche.

Claims

1. Verfahren zur Ermittlung einer gewählten Rangordnungszahl aus mehreren Abtastwertzahlen in Binärformat mit den folgenden Schritten:

- es wird entweder die Zahl der höchstwertigen Binär-0-Ziffern oder der Binär-1-Ziffern in den Abtastwertzahlen gezählt, und es wird das höchstwertige Binärbit für die gewählte Rangordnungszahl als Funktion davon gewählt, ob die Zahl der höchstwertigen Binär-0- oder Binär-1-Ziffern, die auf diese Weise gezählt wurden, einen vorbestimmten Schwellwert erreicht;

- es werden alle folgenden Binärbits geringerer Wertigkeit für jede Abtastwertzahl auf den gleichen Wert wie das höchstwertige Bit jener Abtastwertzahl für alle jene Abtastwertzahlen gesetzt, bei denen das höchstwertige Binärbit von dem Binärbit unterschieden ist, das bei dem vorhergehenden Schritt gewählt wurde;

- es wird entweder die Zahl der nächstwertigen Binär-0- Ziffern oder Binär-1-Ziffern in den Abtastwertzahlen gezählt, und es wird das nächstfolgende Binärbit für die gewählte Rangordnungszahl als Funktion davon gewählt, ob die Zahl der so gezählten nächstwertigen Binär-0- oder Binär-1- Ziffern den vorbestimmten Schwellwert trifft;

- es werden alle folgenden Binärbits geringerer Wertigkeit für jede Zahl auf den gleichen Wert gesetzt wie das nächsthöherwertige Binärbit jener Zahl, und zwar für all jene Zahlen, bei denen das nächsthöherwertige Binärbit von dem Binärbit unterschieden ist, welches bei dem unmittelbar vorangegangenen Schritt gewählt wurde; und

- es werden die vorangegangenen zwei Schritte für die restlichen Binärbits der Abtastwerte wiederholt.

2. Verfahren nach Anspruch 1, bei welchem bei der Vorbestimmung des Schwellwertes die Zahl gleich entweder der Zahl der Abtastwerte minus der gewählten Rangordnungszahl gewählt wird, wenn die Binär-1-Ziffern gezählt werden, oder der gewählten Rangordnungszahlen, wenn die Binär-0-Ziffern gezählt werden.

3. Schaltung zur Ermittlung einer gewählten Rangordnungszahl aus mehreren Abtastwerten, von denen jeder ein binäres Format aufweist und eine gewählte Zahl von Bits umfaßt, die in einer Ordnungsfolge vom höchstwertigen Bit nach dem geringstwertigen Bit angeordnet sind, wobei die Schaltung folgende Elemente umfaßt:

- ein Schieberegister, welches sämtliche Binärbits aller Abtastwerte in gewählten Gruppen darstellt, wobei jede der Gruppen eine Ordnungsfolge aller Binärbits gleicher Wertigkeit aus allen Abtastwerten enthält;

- eine Logikschaltung, die auf ein gewähltes Eingangs- Steuersignal anspricht, um alle Binärbits, die vom Schieberegister für jede gewählte Gruppe dargestellt werden, nach einem Ausgang zu übertragen, wobei die Logikschaltung auf eine andere Mode der gewählten Eingangs-Steuersignale anspricht, um andere gewählte Binärbits am Ausgang anstelle der entsprechenden Binärbits von den gewählten Gruppen zu liefern;

- eine Summierungseinrichtung, die die Binärbits vom Ausgang der Logikschaltung empfängt und sämtliche Binärbits mit der gleichen Binärziffer in jeder Gruppe summiert, einschließlich der anderen gewählten Binärbits, die von der Logikschaltung anstelle der Binärbits von der gewählten Gruppe geliefert werden, um ein Ausgangssignal zu erzeugen, welches die Summation für jede der Gruppen anzeigt; und

- eine Schwellwertschaltung, die auf das Ausgangssignal der Summierungsschaltung für jede Gruppe anspricht, um die Binärbits der Rangordnungszahl als Funktion davon zu liefern, ob das Ausgangssignal der Summierungsschaltung für jede Gruppe einen vorbestimmten Schwellwert überschreitet, wobei der Binärbit-Ausgang der Schwellwertschaltung auch als Steuersignal für die Logikschaltung arbeitet.

4. Schaltung nach Anspruch 3, welche eine programmierbare Stufe zur Begrenzung der Zahl von Abtastwerten aufweist, die durch die Schaltung verarbeitet werden, indem der andere Mode der gewählten Eingangs-Steuersignale nach der Logikeinrichtung derart vorgesehen wird, daß die Logikschaltung die anderen gewählten Binärbits am Ausgang anstelle der Binärbits von den gewählten Gruppen liefert.

5. Schaltung nach Anspruch 3, bei welcher die Logikschaltung wenigstens einen Logikkreis für jedes Bit in den Abtastwerten umfaßt, wobei die Summierungsstufe wenigstens eine Summierungsschaltung für jede der gewählten Gruppen umfaßt, die die Ordnungsfolge von Binärbits gleicher Wertigkeit enthält, und die Schwellwertstufe wenigstens eine Schwellwertdetektorschaltung für jede Summierungsstufe aufweist.

6. Schaltung nach Anspruch 5, bei welcher die Logikschaltungen wenigstens eine gewählte Zahl von Logikschaltungen aufweisen, die der Zahl der Abtastwerte entspricht, und eine zweite gewählte Zahl von Logikschaltungen entsprechend der Zahl der Abtastwerte, wobei die Summierungsstufen wenigstens eine erste Summierungsstufe aufweisen, die Ausgangssignale von allen Logikschaltungen der ersten gewählten Zahl von Logikschaltungen empfängt, und eine zweite Summationsschaltung die Ausgangssignale von sämtlichen Logikschaltungen der zweiten gewählten Zahl von Logikschaltungen empfängt, und wobei die Schwellwertdetektorschaltungen wenigstens eine erste Schwellwertdetektorschaltung aufweisen, die Ausgangssignale von der ersten Summationsstufe empfängt, und eine zweite Schwellwertdetektorschaltung die Ausgangssignale von der zweiten Summierungsstufe empfängt.

7. Schaltung nach Anspruch 6, bei welcher jede Logikschaltung der ersten gewählten Zahl von Logikschaltungen das höchstwertige Bit von unterschiedlichen Abtastwerten nach der ersten Summierungsstufe überträgt und die erste Summierungsstufe danach alle höchstwertigen Bits der gleichen gewählten Binärziffern summiert, um ein Ausgangssignal zu liefern, welches die Summation anzeigt, wobei die erste Schwellwertdetektorschaltung auf das Ausgangssignal von der ersten Summierungsstufe anspricht, um ein Eingangs- Steuersignal für jede Logikstufe in der ersten gewählten Zahl von Logikschaltungen als Funktion davon zu liefern, ob das Ausgangssignal von der ersten Summationsstufe den vorbestimmten Schwellwert überschreitet, und wobei jede Logikschaltung in der ersten gewählten Zahl von Logikschaltungen, die auf die Steuersignale ansprechen, die hiervon empfangen wurden, danach ein Ausgangs-Steuersignal einer entsprechenden Logikstufe in der zweiten gewählten Zahl von Logikstufen liefert, und jede Logikstufe der zweiten gewählten Zahl von Logikstufen entweder das nächstwertige Bit eines anderen Abtastwertes oder einen Binärbitwert der zweiten Summationsstufe als Funktion des Steuersignals liefert, das von der entsprechenden Logikstufe der ersten gewählten Zahl von Logikstufen empfangen wurde.

8. Schaltung nach Anspruch 7, bei welcher das Steuersignal für jede Logikstufe der zweiten gewählten Zahl von Logikstufen die Übertragung eines Binärbitwertes identisch dem entsprechenden höchstwertigen Binärbit für jeden höchsten Binärbitwert bewirkt, der unterschieden ist von dem Binärbitwert-Ausgang von der ersten Schwellwertdetektorstufe, unabhängig von dem entsprechenden zweiten höchstwertigen Bitwert, der vom Schieberegister der Logikschaltung der zweiten gewählten Gruppe von Logikstufen präsentiert wurde, wobei das Steuersignal nach jeder Logikstufe der zweiten gewählten Zahl von Logikstufen die Übertragung des entsprechenden zweiten höchstwertigen Bitwertes bewirkt, der durch das Schieberegister für jeden höchstwertigen Binärbitwert präsentiert wurde, der identisch ist dem Binärbitwert-Ausgang von der ersten Schwellwertdetektorschaltung.

9. Schaltung nach Anspruch 8, mit einer programmierbaren Stufe zur Begrenzung der Zahl der Abtastwerte, die durch die Schaltung verarbeitet werden, wobei die programmierbare Stufe wenigstens einem oder mehreren Paaren der ersten gewählten Zahl von Logikschaltungen Steuersignale derart liefert, daß eines der Paare der ersten gewählten Zahl von Logikschaltungen die Übertragung einer binären 0 nach der ersten Summierungsschaltung bewirkt und das andere der Paare der ersten gewählten Zahl von Logikschaltungen die Übertragung einer binären 1 nach der ersten Summationsstufe bewirkt, wobei eines der Paare der ersten gewählten Zahl von Logikschaltungen auch ein Steuersignal der entsprechenden Logikstufe der zweiten gewählten Zahl von Logikstufen derart liefert, daß die entsprechende Logikschaltung der zweiten gewählten Zahl von Logikstufen die Übertragung einer binären 0 nach der zweiten Summierungsschaltung bewirkt, während das andere Paar der ersten gewählten Zahl von Logikstufen ein Steuersignal der entsprechenden Logikstufe der zweiten gewählten Zahl von Logikstufen derart liefert, daß die entsprechende Logikschaltung der zweiten gewählten Zahl von Logikstufen die Übertragung einer binären 1 nach der zweiten Summierungsstufe bewirkt.

10. Schaltung nach Anspruch 8, bei welcher die gewählte Rangordnungszahl die Mittelwertzahl ist und die vorbestimmte Schwellwertzahl gleich ist entweder der Zahl der Abtastwertzahlen minus der gewählten Rangordnungszahl, wenn die gewählte Binärziffer 1 ist, oder gleich der Rangordnungszahl, wenn die gewählte Binärziffer 0 ist.

11. Schaltung nach Anspruch 7, bei welcher das Schieberegister wenigstens ein Flip-Flop für jede Logikstufe aufweist und die Flip-Flops wenigstens eine erste gewählte Zahl von seriell geschalteten Flip-Flops aufweist, entsprechend der Zahl der Logikstufen in der ersten gewählten Zahl von Logikstufen, wobei die erste gewählte Zahl von Flip-Flops jeweils mit der ersten gewählten Zahl der Logikstufen verbunden ist und derart getaktet wird, daß seriell von einem Flip-Flop nach dem nächsten Flip-Flop der ersten gewählten Zahl von seriell verbundenen Flip-Flops die aufeinanderfolgenden höchstwertigen Bits der Abtastwertzahlen hindurchlaufen, und wenigstens eine zweite gewählte Zahl seriell geschalteter Flip-Flops entsprechend der Zahl der Logikstufen in der zweiten gewählten Zahl von Logikstufen mit der zweiten gewählten Zahl von Logikstufen verbunden und so getaktet ist, daß seriell von einem Flip-Flop nach dem nächsten Flip-Flop der zweiten gewählten Zahl von seriell verbundenen Flip-Flops die aufeinanderfolgenden zweitwertigen Bits der Abtastwertzahlen hindurchlaufen.