DE69202975T2

DE69202975T2 - Positionsbestimmende vorrichtung.

Info

Publication number: DE69202975T2
Application number: DE69202975T
Authority: DE
Inventors: John Burns; Sheelagh Lloyd
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1991-04-03
Filing date: 1992-04-03
Publication date: 1996-02-15
Anticipated expiration: 2012-04-04
Also published as: WO1992017859A1; EP0578692B1; EP0578692A1; DE69202975D1; US5442147A; JPH06506080A

Description

TECHNISCHES GEBIET

Die vorliegende Erfindung bezieht sich auf eine Positionserfassungs-Vorrichtung und insbesondere, aber nicht ausschließlich, auf eine Vorrichtung zum Erfassen der Position eines Anzeigeelements über einer zweidimensionalen gemusterten Oberfläche mittels der Erfassung von Mustermerkmalen der Oberfläche.

HINTERGRUNDTECHNIK

Es ist bekannt, eine lineare Position zu erfassen, indem ein lineares Muster vorgesehen wird, das eine pseudozufällige binäre Sequenz (PRBS, auch als eine "m-Sequenz" bekannt) (PRBS = Pseudo-Random Binary Sequence) codiert, und danach die Fenstereigenschaft einer solchen Sequenz verwendet wird, um eine Positionserfassung zu bewirken, indem eine Fensterlängen-Teilsequenz des Musters verwendet wird. Ein Beispiel eines derartigen Systems ist in dem Artikel "New Pseudorandom/Natural Code Conversion Method" von E.M. Petriu, erschienen in den Electronic Letters, 27. Oktober 1988, Ausg. 24, Nr. 22, beschrieben.
Mit "Fenstereigenschaft" ist die Eigenschaft gemeint, daß bei einer PRBS der Länge (2k-1), wobei k eine ganze Zahl ist, eine Teilsequenz der Länge k einzigartig sein wird und daher in der Sequenz eindeutig lokalisierbar ist; diese und weitere Eigenschaften von PRBSs sind z.B. in dem Artikel "Pseudo-Random Sequences and Arrays" von F. Jessie MacWilliams und Neil J.A. Sloane, erschienen in Proceedings of the IEEE, Ausg. 64, Nr. 12, Dezember 1976, beschrieben.
Die meisten bekannten Systeme, die die Fenstereigenschaft einer PRBS zur Positionserfassung benutzen, sind im wesentlichen auf eine lineare Positionserfassung begrenzt, obwohl der Weg, dem das PRBS-Muster folgt, bekanntlich nicht geradlinig sein muß (z.B. kreisförmig oder schlangenlinienförmig). Die EP-A-0,206,246 offenbart jedoch ein zweidimensionales Muster, das zwei orthogonale PRBS-Sequenzen der Fensterlänge 4 codiert; mittels der Verwendung eines Sensorkopfs, um eine Fläche des Musters zu erfassen, die ausreicht, um eine Fensterlängen-Teilsequenz entlang beider Sequenzen einzuschließen, wird es möglich, die Position des Erfassungskopfs über dem Muster zu bestimmen. Eine ähnliche Anordnung ist in der EP-A-0,171,284 offenbart, in der wiederum zwei orthogonale Sequenzen (in diesem Fall quinäre Sequenzen der Fensterlänge 3) verwendet sind, um ein Muster zu bilden, und ein Erfassungskopf einen Abschnitt des Musters erfaßt, der ausreicht, um Fensterlängen-Teilsequenzen beider Sequenzen einzuschließen.
Ein Nachteil der zweidimensionalen Positionslokalisierungssysteme, die oben beschrieben sind, besteht darin, daß dieselben eine Erfassungsanordnung erfordern, die groß genug ist, um Fensterlängen-Teilsequenzen entlang zweier orthogonaler Richtungen aufzunehmen.
Es ist eine Aufgabe der vorliegenden Erfindung, eine Positionserfassungsvorrichtung zu schaffen, um die Position über einer zweidimensionalen Oberfläche zu erfassen, die keinen derart großen Erfassungskopf erfordert.

OFFENBARUNG DER ERFINDUNG

Gemäß einem Aspekt der vorliegenden Erfindung wird eine Positionserfassungsvorrichtung mit folgenden Merkmalen geschaffen:
-- einem Musterelement mit einer Anordnung von Markierungen, die zusammen ein zweidimensionales Muster darstellen, das Merkmale aufweist, die das Muster dadurch zu einem Fenstertechnikmuster machen, daß ein beliebiger örtlicher Abschnitt des Musters einer gegebenen Größe hinsichtlich seiner Merkmale, hierin ein "Teilmuster", wenn isoliert betrachtet, durch die Merkmale derart charakterisiert ist, daß der Standort des Teilmusters bestimmt werden kann, für zumindest eine Ausrichtung des Teilmusters relativ zu dem Muster;
-- einem Anzeigeelement, das relativ zu dem Musterelement über die Anordnung von Markierungen bewegbar ist;
-- einer Teilmuster-Detektoreinrichtung zum Herleiten von Teilmusterdaten, die ein Teilmuster, das örtlich dem Anzeigeelement zugeordnet ist, in die zumindest eine Ausrichtung des Teilmusters relativ zu dem Muster darstellen, wobei die Teilmuster-Detektoreinrichtung eine Sensoreinrichtung aufweist, um die Markierungen derart zu erfassen, daß für eine beliebige Position des Anzeigeelements die Erfassungseinrichtung wirksam ist, um einen Abschnitt des Musters zu erfassen, der an dem Ort des Anzeigeelements liegt; und
-- einer Positionsbestimmungseinrichtung, die einen Speicher aufweist, der Musterdaten, die das Fenstertechnikmuster darstellen, hält, wobei die Positionsbestimmungseinrichtung auf die Teilmusterdaten anspricht, die von der Detektoreinrichtung hergeleitet werden, um durch Bezugnahme auf die Musterdaten die Position des Anzeigeelements relativ zu dem Musterelement zu bestimmen;
dadurch gekennzeichnet, daß die Sensoreinrichtung wirksam ist, um einen Abschnitt des Musters zu erfassen, der größenmäßig kleiner als das Teilmuster ist, und daß die Detektoreinrichtung wirksam ist, um die Ausgabe der Sensoreinrichtung derart zu verarbeiten, daß, während die Sensoreinrichtung über das Muster bewegt wird, Teilmusterdaten des gesamten Teilmusters fortschreitend gebildet werden.

Vorzugsweise gilt bei der Positionserfassungsvorrichtung:

(a) die Merkmale des Musters bilden erkennbar eine regelmäßige Anordnung, für die das Teilmuster in einer von M möglichen Ausrichtungen relativ zu dem Muster sein kann, wobei M eine positive ganze Zahl größer als Null ist, wenn ein beliebiges gegebenes Teilmuster des Musters isoliert von dem Muster betrachtet wird;
(b) das Fenstertechnikmuster derart ist, daß ein beliebiges gegebenes Teilmuster in dem Muster für N der M möglichen Ausrichtungen korrekt lokalisiert werden kann, wobei N eine positive ganze Zahl in dem Bereich 0< N≤M ist; und
(c) die Teilmuster-Detektoreinrichtung auf die regelmäßige Anordnung von Merkmalen anspricht, um das Teilmuster an dem Ort des Anzeigeelements zu identifizieren und um Teilmusterdaten zu der Positionsbestimmungseinrichtung zu liefern, welche das Teilmuster in einer der N der M möglichen Ausrichtungen relativ zu dem Muster, in dem es korrekt lokalisiert werden kann, darstellen.
Vorteilhafterweise sind diese Merkmale erkennbar in Reihen und Spalten angeordnet, die sich parallel zu der jeweiligen ersten und zweiten Koordinatenachse erstrecken, wobei jedes Merkmal in einer fiktiven Zelle geboten wird, die eine Linienberührung mit einer Mehrzahl von benachbarten solchen Zellen hat. Ein rechtwinkliges Zellenmuster ist bevorzugt, bei dem jede Zelle eine Linienberührung mit vier benachbarten Zellen hat, M einen Wert 4 hat und N einen der Werte 1, 2 und 4 hat.
Die Merkmale können dazu dienen, zumindest einen Teil eines zweidimensionalen Fenstertechnikarrays mit Reihen und Spalten von Elementen, die sich fiktiv parallel zu der ersten bzw. der zweiten Koordinatenachse erstrecken, zu codieren. Eine geeignete Form eines Arrays ist ein pseudozufälliges binäres Array. Eine weitere geeignete Form eines Arrays kann aus einer ersten und einer zweiten binären Sequenz der Länge m bzw. n gebildet sein, wobei m und n positive ganze Zahlen größer als Null sind, indem eine erste Spalte des Arrays aus der ersten Sequenz gebildet wird und indem jede nachfolgende (i)te Spalte gebildet wird, wobei "i" eine ganze Zahl in dem Bereich von 2 bis 2n+1 ist, indem der Wert des (i-1)te Elements der zweiten Sequenz betrachtet wird, und
- wenn das (i-1)te Element einen ersten binären Wert hat, indem die (i)te Spalte aus der ersten Sequenz, die bezüglich der (i-1)ten Spalte nicht verschoben ist, gebildet wird,
- wenn das (i-1)te Element einen zweiten binären Wert hat, indem die (i)te Spalte aus der ersten Sequenz gebildet wird, die zirkular um eine Position relativ zu der (i-1)ten Spalte verschoben ist.
Eine weitere Form eines Arrays kann durch das Kombinieren zweiter Fenstertechniksequenzen miteinander gebildet werden, die sich parallel zu der jeweiligen der ersten und der zweiten Koordinatenachse erstrecken, wobei jedes Element des Arrays eine spezielle Kombination von Werten der entsprechenden Elemente der Sequenzen darstellt.
Wenn die Merkmale dazu dienen, ein Array zu codieren, ist der Wert jedes Elements des Arrays vorzugsweise als ein entsprechender Merkmalswert codiert.
Vorzugsweise dienen die Mustermerkmale dazu, eine erste Fenstertechniksequenz von Elementen zu codieren, die sich fiktiv parallel zu der ersten Koordinatenachse erstrecken, und eine zweite Fenstertechniksequenz von Elementen, die sich fiktiv parallel zu der zweiten Koordinatenachse erstrecken.
In diesem Fall können die Sequenzen aus der folgenden Gruppe von Sequenzen ausgewählt sein:
(a) de Bruijn-Sequenzen;
(b) pseudozufällige binäre Sequenzen;
(c) ausrichtbare binäre Sequenzen, die jeweils die Eigenschaft aufweisen, daß, wenn eine Fensterlängen-Teilsequenz in der Sequenz auftritt, die Umkehrung derselben nicht auftritt; und
(d) komplementäre ausrichtbare binäre Sequenzen, die jeweils die Eigenschaft haben, daß, wenn eine Fensterlängen-Teilsequenz in der Sequenz auftritt, die Umkehrung des bitweisen Komplements der Teilsequenz nicht auftritt.
Vorteilhafterweise ist, wenn zwei Sequenzen codiert sind, jedes Element jeder Sequenz als eine entsprechende Änderung des Merkmalwerts codiert, wenn eine Bewegung zwischen benachbarten Zellen in eine Richtung parallel zu der Richtung des Ausmaßes der entsprechenden Sequenz stattfindet. Bei einer Implementierung ist die Codierung der Elementewerte derart, daß sichergestellt ist, daß jedes Merkmal durch seinen Wert von zumindest einem spezifischen Nachbarn unterschieden ist, mit dem eine Linienberührung besteht; tatsächlich kann die Codierung derart sein, daß jedes Merkmal durch den Wert von allen seinen Nachbarn, mit denen es eine Linienberührung besitzt, unterschieden ist. Tatsächlich kann die Codierung der Elementewerte ferner sicherstellen, daß jedes Merkmal auch durch seinen Wert von allen Nachbarn unterschieden ist, mit denen es eine Punktberührung besitzt. Alternativ kann jedes Merkmal von zumindest einem Nachbarmerkmal, mit dem es eine Linienberührung besitzt, mittels einer entsprechenden Separatorzone getrennt sein, die z.B. durch die Teilmuster-Detektoreinrichtung erfaßbar ist.
Vorzugsweise ist die Sensoreinrichtung mit dem Anzeigeelement beweglich und ist wirksam, um einen Abschnitt des Musters zu erfassen, der einem einzelnen Merkmal entspricht, wobei die Vorrichtung eine Rauminformations-Einrichtung einschließt, um der Teilmuster-Detektoreinrichtung Rauminformationen zu liefern, die die relative Anordnung benachbarter Elementewert-Codiermerkmale betreffen, und wobei die Teilmuster-Detektoreinrichtung wirksam ist, um die Rauminformationen zu verwenden, um die Teilmusterdaten zusammenzusetzen, die sich auf ein ganzes Teilmuster beziehen, während die Sensoreinrichtung über das Muster bewegt wird. Nützlicherweise weist die Rauminformations-Einrichtung Merkmale des Musters auf, die von der Sensoreinrichtung erfaßbar sind, während dieselbe zwischen den Elementewert-Codiermerkmalen bewegt wird; insbesondere können die Rauminformationen in den Werten codiert werden, die durch die Elementewert-Codiermerkmale dargestellt sind. Bei bestimmten Implementierungen können die Rauminformationen, die von der Teilmuster-Detektoreinrichtung geliefert werden, nur partiell sein, wobei in solchen Fällen die Detektoreinrichtung wirksam gemacht sein kann, um eine unveränderliche Bewegungsrichtung der Sensoreinrichtung über dem Muster anzunehmen, außer und bis nach der anfänglichen Positionsbestimmung ein Widerspruch zwischen den Musterdaten und den Teilmusterdaten bestimmt wird.
Im allgemeinen wird die relative Ausrichtung der Sensoreinrichtung bezüglich der Anordnung der Markierungen um eine Achse senkrecht zu der Anordnung variabel sein. Vorzugsweise schließt die Vorrichtung daher eine Ausrichtungsinformations-Einrichtung ein, um der Teilmuster-Detektoreinrichtung Ausrichtungsinformationen über die relative Ausrichtung zu liefern, wobei die Teilmuster-Detektoreinrichtung diese Informationen beim Herleiten der Teilmusterdaten verwendet, die ein Teilmuster darstellen, das in die zumindest eine Ausrichtung ausgerichtet ist. Günstigerweise weist die Ausrichtungsinformations-Einrichtung Merkmale des Musters auf, die mittels der Sensoreinrichtung erfaßbar sind, während dieselbe zwischen den Elementewert-Codiermerkmalen bewegt wird; insbesondere können die Ausrichtungsinformationen in den Werten, die durch die Elementewert-Codiermerkmale dargestellt sind, codiert sein.
Vorzugsweise wird nach einer anfänglichen Bestimmung des Standortes des Anzeigeelements eine beliebige inkrementale Änderung des Musterabschnitts, der von der Erfassungseinrichtung erfaßt wird, von der Positionsbestimmungseinrichtung verwendet, um basierend auf der inkrementalen Standortänderung des Anzeigeelements, das durch die Änderung in dem erfaßten Musterabschnitt angezeigt ist, einen aktualisierten Standort zu liefern. Falls das Muster eine Codierung von zwei Fenstertechniksequenzen von Elementen ist, die sich fiktiv entlang der entsprechenden ersten und zweiten Koordinatenachse erstrecken, ist die Positionsbestimmungs-Einrichtung günstigerweise wirksam, um den Standort des Anzeigeelements entlang der ersten und der zweiten Koordinatenachse getrennt zu aktualisieren, basierend auf einer beliebigen inkrementalen Änderung des Standorts entlang der entsprechenden Koordinatenachse, die durch eine Änderung des Elements oder der Elemente der entsprechenden Sequenz angezeigt ist, welche von dem erfaßten Musterabschnitt dargestellt wird; wobei die Positionsbestimmungs-Einrichtung beim Inkrementieren des Standorts des Anzeigeelements entlang zumindest einer Koordinatenachsen, eine unveränderte Bewegungsrichtung entlang derselben außer und bis das Element oder die Elemente der Sequenz, die sich entlang der einen Koordinatenachse erstreckt, welche durch den erfaßten Musterabschnitt dargestellt sind, von den vorhergesagten der gespeicherten Musterdaten, die sich auf diese Sequenz beziehen, die sich auf den gegenwärtigen Standort in der Sequenz bezieht, wie vorher durch die Positionsbestimmungs-Einrichtung bestimmt ist, unterscheiden, wobei die Positionsbestimmungs-Einrichtung beim Erfassen eines Unterschieds zwischen den erfaßten und den vorhergesagten Sequenzelementen ferner wirksam ist, um ein Wiedergewinnungsverfahren zu betreten, um ihren Standort entlang der einen Koordinatenachse wiederzugewinnen, wobei das Wiedergewinnungsverfahren das Herleiten von zumindest einem Kandidatenstandort für das Anzeigeelement auf der Basis einschließt, daß die Bewegungsrichtung des Anzeigeelements umgekehrt wurde, und das Vergleichen des Elements oder der Elemente, die entlang der Spur des Anzeigeelements erfaßt werden, mit denen, die laut Vorhersage entlang der Anzeigeelementspur liegen, wenn der oder alle Kandidatenstandorte erreicht werden, wodurch die Gültigkeit des oder jedes solchen Standortes getestet wird.
Vorzugsweise ist das Anzeigeelement eine in der Hand haltbare Schreibspitze, die die Sensoreinrichtung trägt.
Bei einem Ausführungsbeispiel ist das Musterelement ein planares Bauteil, das die Markierungen trägt, wobei sowohl das planare Bauglied als auch die Markierungen für sichtbares Licht transparent sind, wodurch es möglich ist, Gegenstände durch das Musterelement zu sehen. Bei einem weiteren Ausführungsbeispiel ist das Musterelement ein planares Bauglied, das die Markierungen trägt, wobei die Markierungen für sichtbares Licht transparent sind und die Schreibspitze eine Markierungsschreibspitze ist, die in der Lage ist, ein Markierungsmittel auf einer Oberfläche des planaren Bauglieds abzuscheiden, auf der die Markierungen mittels der Sensoreinrichtung erfaßt werden können, wobei das Arbeitsmittel optisch sichtbar ist, jedoch das Erfassen der Markierungen durch dasselbe ermöglicht. Bei einem weiteren Ausführungsbeispiel ist das Musterelement ein planares Bauteil, das die Markierungen trägt, wobei die Vorrichtung ferner eine markierbare Schicht aufweist, die über dem planaren Bauglied positioniert ist, wobei die Schicht mindestens partiell lichtundurchlässig ist und es ermöglicht, daß die Markierungen mittels der Sensoreinrichtung durch dieselbe erfaßt werden, und wobei die Schreibspitze eine Markierungsschreibspitze ist, die in der Lage ist, ein Markierungsmittel auf der Schicht abzuscheiden, wobei das Mittel gegenüber der Schicht optisch erkennbar ist, jedoch das Erfassen der Markierungen durch dieselbe ermöglicht.
Die vorliegende Erfindung schließt ferner getrennt ein Musterelement zur Verwendung in einer Positionserfassungsvorrichtung ein, wie in Anspruch 41 definiert ist, ebenso wie ein Verfahren zum Bestimmen des Standorts eines Anzeigers entlang einer vorbestimmten Sequenz von Mustermerkmalen, zu denen der Anzeiger bewegbar ist, wie in Anspruch 51 definiert ist.

BESTE ART ZUM DURCHFÜHREN DER ERFINDUNG

Allgemeine Form der Positionserfassungs-Vorrichtung

Wie in Fig. 1 gezeigt ist, weist die Positionserfassungs- Vorrichtung ein Musterelement 10 auf, das mit einem zweidimensionalen Muster 20 markiert ist, eine Erfassungsschreibspitze 11 zum Erfassen eines Teilmusters des Musters 20, eine Teilmuster-Bildverarbeitungseinheit 12, die mit der Ausgabe der Schreibspitze 11 gespeist wird, und eine Positionsbestimmungseinheit 13, die mit dem Ausgang der Einheit 12 verbunden ist und wirksam ist, um ein Ausgangssignal zu liefern, das die Position der Schreibspitze über dem Muster 20 anzeigt.
Das Musterelement 10 besitzt die Form eines planaren Trägerbauglieds 14, das auf einer Oberfläche eine Anordnung von Markierungen 15 trägt (siehe das Nebenbild in Fig. 1, das eine vergrößerte Ansicht eines Abschnitts der Oberfläche des Bauglieds 14 ist); die Markierungen 15 bilden zusammen das Muster 20.
Bei dem Ausführungsbeispiel von Fig. 1 ist das Muster 20 aus einer rechtwinkligen Anordnung von Markierungen 15 aufgebaut, wobei die Markierungen die Form von gedruckten Markierungen haben, die durch ihre optischen/Infrarot-reflektierenden Charakteristika erfaßbar sind. Es sollte jedoch offensichtlich sein, daß die Markierungen in einer Vielzahl von anderen Konfigurationen angeordnet sein können und mittels beliebiger geeigneter Charakteristika erfaßbar sein können, einschließlich mittels ihrer Oberflächenrauhigkeit, ihrer magnetischen Parameter, ihrer elektrischen Parameter, ihrer spezifischen optischen/Infrarot-Durchlässigkeit usw..
Das Muster 20 ist ein Fenstertechnikmuster in dem Sinne, daß eine beliebiger lokaler Abschnitt des Musters einer gegebenen Größe hinsichtlich seiner Mustermerkmale, wenn isoliert betrachtet, durch seine Merkmale derart charakterisiert ist, daß es möglich ist, den Standort des Musterabschnitts in dem Muster zu bestimmen, mindestens für eine bekannte Ausrichtung des Musterabschnitts relativ zu dem Muster als ein ganzes. Ein Musterabschnitt einer derartigen Größe, die es ermoglicht, seinen Standort zu bestimmen, wird hierin als ein "Teilmuster" bezeichnet.
In seiner weitesten Konzeption kann das Fenstertechnikmuster 20 z.B. durch ein Bild eines ungleichmäßigen Objekts (wie z.B. eines Portraits oder einer Landschaft) aufgebaut sein, da eine Teilfläche eines solchen Bildes, vorausgesetzt sie besitzt eine ausreichende Größe, eindeutig in dem Bild lokalisierbar sein wird. Jedoch liegt der primäre Mittelpunkt der vorliegenden Erfindung auf Mustern mit einer regelmäßigen Anordnung von Merkmalen, die darunterliegende mathematische Arrays oder Sequenzen mit bekannten Eigenschaften codieren. Von speziellem Interesse sind Fenstertechnikmuster mit rechtwinkligen Anordnungen von Merkmalen (d.h. Merkmalen, die in Reihen und Spalten parallel zu jeweiligen Koordinatenachsen verlaufen - es sei bemerkt, daß, obwohl diese Achsen senkrecht zueinander sein können oder nicht, der Ausdruck "rechtwinkliges Muster" hierin verwendet ist, um beide Situationen abzudecken). Die rechtwinkligen Muster, die hierin nachfolgend beschrieben sind, sind Codierungen von entweder zweidimensionalen Fenstertechnikarrays oder von Paaren von orthogonalen Fenstertechniksequenzen; in dem erstgenannten Fall hat ein Teilmuster die Form einer rechteckigen Fläche des Musters, wohingegen in dem letztgenannten Fall ein Teilmuster die Form von zwei orthogonalen linearen Segmenten des Musters besitzt.
Die Erfassungsschreibspitze 11 besitzt die duale Funktion eines Anzeigeelements, um auf einen speziellen Standort auf dem Muster 20 zu zeigen, und eines Sensors, um die Markierungen am Ort der Schreibspitze abzutasten, um ein Teilmuster an dem Standort zu erfassen, auf den mittels der Schreibspitze 11 gezeigt wird. Bei der vorliegenden Erfindung ist die Schreibspitze dazu bestimmt, in der Hand gehalten zu werden und ohne eine beliebige Beschränkung, die bezüglich ihrer Ausrichtung um eine Achse, die senkrecht zu dem Muster ist, gemacht ist, frei über das Muster bewegbar zu sein. Jedoch sind andere Ausführungsbeispiele möglich, bei denen die Schreibspitze z.B. auf einem X-Y-Wagen befestigt ist und bezüglich dem Muster eine feste Ausrichtung hat; außerdem müssen die zwei Funktionen der Erfassungsschreibspitze 11 nicht durch die gleiche physikalische Einheit durchgeführt werden.
Die Schreibspitze 11 weist einen Erfassungskopf 16 einer Form auf, die geeignet ist, um die physikalische Eigenschaft der Markierungen, die verwendet sind, um die Mustermerkmale zu liefern, zu erfassen; bei dem vorliegenden Ausführungsbeispiel ist der Erfassungskopf 16 ein optischer Sensor. Die Verarbeitung der Ausgabe des Erfassungskopfs wird durch die Teilmuster-Bildverarbeitungseinheit 12 bewirkt.
Vorausgesetzt es ist das Ziel, ein gesamtes Teilmuster am Ort der Schreibspitze 11 zu erfassen, sind drei Hauptlösungsansätze zur Mustererfassung möglich. Der erste Lösungsansatz, der kein Ausführungsbeispiel der Erfindung ist, besteht darin, eine Fläche des Musters 20 zu erfassen, die groß genug ist, um ein gesamtes Teilmuster auf einmal einzuschließen (wobei die Auflösung des Erfassungskopfs 16 ausreichend ist, um die charakteristischen Merkmale des Musters aufzulösen). Das Teilmusterbild, das so erfaßt wird, wird mittels der Teilmuster-Bildverarbeitungseinheit 12 verarbeitet, um Daten über die vorspringenden Merkmale des Musters zu gewinnen und die Teilmusterdaten, die für das Teilmuster am Ort der Schreibspitze 11 charakteristisch sind, herzuleiten.
Der zweite Lösungsansatz besteht darin, eine Musterfläche zu erfassen, die kleiner als ein Teilmuster ist, jedoch eine Anzahl von Mustermerkmalen enthält, und dann mit dem Erfassungskopf 16 über das Muster 20 abzutasten, um einen ausreichenden Teil des benachbarten Abschnitts des Musters zu erfassen, um in der Lage zu sein, ein vollständiges Teilmuster aufzubauen. In diesem Fall ist das Verfahren des Aufbauens eines vollständigen Teilmusters durch die Tatsache erleichtert, daß die Abtastrichtung des Erfassungskopfs 16 ohne weiteres durch die Untersuchung aufeinanderfolgender erfaßter Bilder festgestellt werden kann, so daß Merkmale, die zu unterschiedlichen Zeiten erfaßt werden, richtig aufeinander bezogen werden können. Das Verfahren der Mustermerkmalgewinnung und des Aufbauens eines Teilmusters (oder allgemeiner von Daten, die ein Teilmuster darstellen) wird mittels der Teilmuster-Bildverarbeitungseinheit 12 bewirkt.
Der dritte Lösungsansatz für die Musterabtastung besteht darin, nur ein einzelnes Mustermerkmal zu einer Zeit abzutasten, und dann mit dem Erfassungskopf über das Muster abzutasten, um zu ermöglichen, daß ein vollständiges Teilmuster in der Teilmuster-Bildverarbeitungseinheit 12 aufgebaut wird (dieser Lösungsansatz wird hierin als "Einpixel"-Erfassung bezeichnet). In diesem Fall ist das Problem der richtigen Wechselbeziehung nacheinander abgetasteter Mustermerkmale schwieriger, da Informationen über die Abtastrichtung erforderlich sind. Eine Lösung für dieses Problem besteht darin, derartige Informationen implizit von dem erfaßten Muster erhältlich zu machen, entweder auf eine homogene Art und Weise oder durch die Verwendung von expliziten Bewegungsrichtungs-Markierungen (beide Lösungsansätze werden vollständiger nachfolgend erklärt). Eine alternative Lösung besteht darin, eine externe Abtastrichtung-Erfassungseinrichtung vorzusehen, die eine Eingabe zu der Einheit 12 liefert; jedoch machen die zusätzlichen Kosten, die diese Lösung mit sich bringt, dieselbe unerwünscht. Eine weitere Lösung besteht darin, anzunehmen, daß mit dem Erfassungskopf 16 in einer geraden Linie über das Muster abgetastet wird, so daß nacheinander erfaßte Merkmale ohne weiteres in eine Wechselbeziehung gebracht werden können. Teilmusterdaten werden dann mittels der Einheit 12 zusammengesetzt und zu der Positionsbestimmungseinrichtung 13 geleitet; da aufeinanderfolgende Positionen bestimmt werden, ist es ohne weiteres offensichtlich, daß, wenn die Annahme über die geradlinige Bewegung falsch ist, die entsprechenden falschen Positionsablesungen weggeworfen werden können.
Unabhängig vom verwendeten Erfassungsverfahren ist die Teilmuster-Bildverarbeitungseinheit 12 wirksam, um Teilmusterdaten zur Positionsbestimmungseinheit 14 auszugeben. Diese letztgenannte Einheit bestimmt dann den Standort des Teilmusters in dem Gesamtmuster 20 durch Bezugnahme auf Musterdaten, die das Muster 20 darstellen, welche in einem Musterdatenspeicher 17 gespeichert sind. Die Einheit 13 kann diese Standortbestimmung durch eine Vielzahl von verschiedenen Möglichkeiten bewirken, z.B. durch Musteranpassungstechniken, durch die Verwendung eines Index, auf den über die Teilmusterstandorte zugegriffen wird, oder durch eine Berechnung, falls das Muster eine Codierung von mathematisch verarbeitbaren Sequenzen oder Arrays ist. Aus dem Vorhergehenden ist offensichtlich, daß die Musterdaten, die in dem Speicher 17 gehalten sind, obwohl sie das Muster darstellen, keine direkte Darstellung sein müssen, sondern eine indirekte Darstellung sein können, wie z.B. eine Reihe von Indexeinträgen oder eine mathematische Definition des Musters. Die Musterdaten müssen das Fenstertechnikmuster nur auf eine Art und Weise darstellen, die ausreicht, um zu ermöglichen, daß die absolute Musterposition aus den Daten, die für ein Teilmuster charakteristisch sind, festzustellen.
Während die allgemeine Anordnung und der Betrieb der Positionserfassungs-vorrichtung von Fig. 1 beschrieben wurde, wird nun eine detailliertere Betrachtung bezüglich der Form, des Aufbaus und der Erfassung von rechtwinkligen Fenstertechnikmustern gegeben.

Rechteckige Fenstertechnikmuster

Wie in Fig. 2 dargestellt ist, basieren die rechtwinkligen Fenstertechnikmuster, die hierin nachfolgend beschrieben werden sollen, auf einer rechtwinkligen Anordnung von Mustermerkmalen in Übereinstimmung mit Zellen C, die in Reihen und Spalten jeweils parallel zu Musterkoordinatenachsen Ap und Bp angeordnet sind. Zur Vereinfachung der Beschreibung wird die Achse Ap nachfolgend hierin als die horizontale Achse bezeichnet und eine Bewegung parallel zu derselben als eine horizontale Bewegung; genauso wird die Achse Bp als die vertikale Achse bezeichnet und eine Bewegung parallel zu derselben als vertikale Bewegung. Eine Zelle bei der Spaltenkoordinate "i" auf der horizontalen Achse Ap und der Reihenkoordinate "j" auf der vertikalen Achse Bp ist mit Cij bezeichnet. Jeder Zelle ist einer einer Anzahl von möglichen verschiedenen Werten zugewiesen und diese Zellenwerte bilden Mustermerkmale, die physikalisch durch Markierungen 15 dargestellt sind, welche für das Erfassungsverfahren, das verwendet werden soll, geeignet sind. Folglich können die Werte, die den Zellen zugewiesen sind, z.B. durch jeweilige Farben in dem endgültigen Muster dargestellt sein.
Die Zellenwerte sind verwendet, um ein darunterliegendes zweidimensionales Fenstertechnikarray oder ein Paar von Fenstertechniksequenzen zu codieren, die dem Muster 20 eine Fenstertechnikeigenschaft vermitteln; tatsächlich wird die Teilmuster-Positionsbestimmung im allgemeinen durch eine Rückgewinnung von Fenstertechnik-Teilarrays oder -Teilsequenzen von dem abgetasteten Teilmuster bewirkt. Die Beschaffenheit der verwendeten Codierung wird hierin nachfolgend ausführlicher beschrieben, jedoch sei für jetzt bemerkt, daß zwei Hauptcodierformen verwendet werden, nämlich eine absolute Codierung, bei der der Zellenwert direkt den Wert des darunterliegenden Arrays oder der Sequenz darstellt, und eine Übergangscodierung, bei der die wertmäßige Änderung bei der Bewegung zwischen den Zellen den Wert der darunterliegenden Sequenzen darstellt. Abhängig von dem verwendeten Codierschema können ferner bestimmte andere Informationen aus dem Zellenwertmuster herleitbar sein, wie nachfolgend offensichtlich wird.
Ein wichtiger Punkt beim Erfassen eines Teilmusters und beim Bestimmen der Position des Teilmusters in dem gesamten Muster (ob rechtwinklig oder nicht) ist die relative Ausrichtung des erfaßten Teilmusters bezüglich des Musters 20. Dieser Punkt wird nachfolgend betrachtet, bezugnehmend auf die Fig. 3 und 4 und bezüglich rechtwinkliger Muster.
Fig. 3 zeigt ein Muster 20, das aus einem rechtwinkligen Array von Mustermerkmalen F gebildet ist (jedes dargestellte Merkmal F entspricht einer Zelle Cij in Fig. 2, das Merkmal muß selbstverständlich nicht die gesamte Zellenfläche belegen, obwohl, wie später offensichtlich wird, dies im allgemeinen erwünscht ist, wenn eine Einpixel-Erfassung verwendet ist). Die Mustermerkmale verlaufen in Reihen parallel zu der vertikalen Achse Ap und in Spalten parallel zu der vertikalen Achse Bp. Wenn ein Teilmuster des Musters in Fig. 3 aus einer Anordnung von 3 x 3 Merkmalen zusammengesetzt ist, ist eines der vielen möglichen Teilmuster, die in dem Muster identifizierbar sind, das, das von den Merkmalen F1 bis F9 gebildet wird. Dieses Teilmuster besitzt drei Reihen, die aus den Merkmalen (F1, F2, F3), (F4, F5, F6) bzw. (F7, F8, F9) gebildet sind, die parallel zu einer ersten Koordinatenachse As des Teilmusters verlaufen, und drei Spalten, die aus den Merkmalen (F1, F4, F7), (F2, F5, F8) bzw. (F3, F6, F9) gebildet sind, die parallel zu einer zweiten Koordinatenachse Bs des Teilmusters verlaufen. Wenn das Teilmuster örtlich in dem Muster 20 betrachtet wird, wie in Fig. 2 gezeigt ist, sind die Koordinatenachsen Bp und Bs parallel; das Teilmuster befindet sich in seiner senkrechten Ausrichtung bezüglich des Musters, in der die Kombination der Mustermerkmale desselben für die gegebene Musterausrichtung in dem Muster einzigartig ist.
Jedoch wird im allgemeinen Fall das Teilmuster, das von dem Erfassungskopf 16 erfaßt wird, keine spezielle Ausrichtung aufweisen - es wird nur ein Teilmusterbild sein. Selbstverständlich ist es möglich, die rechtwinklige Beschaffenheit des Teilmusters zu erkennen. Dies wird es jedoch nicht ermöglichen, eine Trennung zwischen den vier möglichen Ausrichtungen, in 90º Intervallen, zu machen, in denen das rechtwinklige Teilmuster gleichermaßen liegen könnte. Die Fig. 4A, 4B, 4C und 4D zeigen diese vier möglichen Ausrichtungen für das Teilmuster von Fig. 3, beginnend mit einer relativen Ausrichtung von 0º zwischen den Achsen Ap und As in Fig. 4A und fortschreitend in Intervallen von 90º zu einer relativen Ausrichtung von 270º in Fig. 4D.
Diese Zweideutigkeit der Ausrichtung des erfaßten Teilmusters kann zu einer falschen Standortbestimmung führen, da das Muster mehr als einen Fall eines Teilmusters beinhalten kann, wenn alle Ausrichtungen betrachtet werden.
Fenstertechnikmuster, bei denen ein Teilmuster nur richtig lokalisiert werden kann, wenn das Teilmuster in der gleichen Ausrichtung wie das Muster betrachtet wird, werden hierin als "1-ausrichtbare" Muster bezeichnet. Tatsächlich gibt es Fenstertechnikmuster, bei denen ein Teilmuster in dem Muster ungeachtet der relativen Ausrichtung desselben korrekt lokalisiert werden kann; solche Muster werden hierin als "4-ausrichtbare" Muster bezeichnet. Zwischen den 1-ausrichtbaren und 4-ausrichtbaren Mustern gibt es Muster, die in dem Muster für zwei der vier möglichen relativen Ausrichtungen korrekt lokalisiert werden können; diese Muster werden hierin als "2-ausrichtbare" Muster bezeichnet.
Für die hierin betrachteten rechtwinkligen Fenstertechnikmuster hängt die Tatsache, ob ein Muster 1-, 2- oder 4-ausrichtbar ist, davon ab, ob das/die darunterliegenden Array/Sequenzen, die durch das Muster dargestellt werden, selbst 1-, 2- oder 4-ausrichtbar sind.
Bei einem 4-ausrichtbaren Muster existiert klarerweise das mögliche Problem des falschen Lokalisierens eines Musters aufgrund einer unbekannten Ausrichtung des Teilmusters bezüglich des Musters nicht. Jedoch existiert dieses Problem für 2-ausrichtbare und 1-ausrichtbare Muster, wobei es in diesen Fällen notwendig ist, Informationen über die Ausrichtung des Teilmusters zu erhalten, um es zu ermöglichen, daß das Teilmuster richtig ausgerichtet ist, bevor sein Standort bestimmt wird.
Eine Möglichkeit, die erforderlichen Ausrichtungsinformationen zu erhalten, bestünde darin, einen getrennten Ausrichtungssensor zum Erfassen der Ausrichtung der Erfassungsköpfe um eine Achse, die senkrecht zu dem Muster 20 ist, vorzusehen; jedoch ist ein solcher Lösungsansatz kostspielig. Eine weitere Möglichkeit wäre es, sicherzustellen, daß das Teilmuster stets in einer festen Ausrichtung relativ zu dem Muster erfaßt wird, indem der Erfassungskopf nicht-drehbar um eine Achse, die senkrecht zu dem Muster 20 ist, angeordnet wird; dieser Lösungsansatz ist wiederum wegen der praktischen Begrenzungen einer derartigen Anordnung nicht bevorzugt. Der bevorzugte Lösungsansatz für die Ausrichtungserfassung besteht darin, Ausrichtungsinformationen in dem Muster zu codieren, entweder als ein Teil der elementaren Array/Sequenz-Codierung oder durch Vorsehen spezieller Ausrichtungsmarkierungen, die in dem Muster 20 integriert sind und mittels des Erfassungskopfs 16 erfaßbar sind. Diese Ausrichtungsinformationen werden dann mittels der Einheit 12 erfaßt und verwendet, um Teilmusterdaten herzuleiten, die das Teilmuster in einer Ausrichtung darstellen, in der dasselbe mittels der Einrichtung 13 eindeutig in dem Muster lokalisiert werden kann.

Fenstertechnik-Arrays und -Sequenzen

Während die allgemeine Form von rechtwinkligen Fenstertechnikmustern betrachtet wurde, werden nun geeignete Fenstertechnik-Arrays und -Sequenzen, auf denen derartige Muster basieren können, erläutert. Obwohl die nachfolgend erläuterten Arrays und Sequenzen alle binär sind (d.h., daß die Bestandteil bildenden Elemente der Arrays und Sequenzen nur einen von zwei möglichen Werten annehmen können), ist dies lediglich zur Vereinfachung der Implementierung bevorzugt, während ternäre und Arrays und Sequenzen höherer Ordnung ebenfalls als die Basis für Fenstertechnikmuster verwendet werden können.

Zweidimensionale Arrays:

Zweidimensionale Arrays von Elementen können gebildet werden, die eine Fenstereigenschaft bezüglich Teilarrays einer gegebenen Größe besitzen. Folglich kann ein 1-ausrichtbares Array (aus dem ein 1-ausrichtbares Muster gebildet werden kann) gebildet werden, indem eine PRBS diagonal in eine zweidimensionale Arraystruktur geschrieben wird. Derartige Arrays sind in dem obengenannten Artikel von MacWilliams und Sloane offenbart, wobei diese Arrays, wie in dem Artikel bemerkt ist, eine Fenstertechnikeigenschaft zeigen.
Ein weiterer Typ eines binären Arrays, der verwendet werden kann, um 1-ausrichtbare, 2-ausrichtbare oder 4-ausrichtbare Muster zu bilden, ist im Anhang A offenbart. Dieser Arraytyp ist aus einer ersten und einer zweiten binären Sequenz der Länge m bzw. n aufgebaut, wobei "m" und "n" ganze Zahlen sind, indem eine erste Spalte des Arrays aus der ersten Sequenz gebildet wird, und indem jede nachfolgende (i)te Spalte gebildet wird, wobei "i" eine ganze Zahl in dem Bereich von 2 bis 2n+1 ist, indem der Wert des (i-1)ten Elements der zweiten Sequenz betrachtet wird, und,
- wenn das (i-1)te Element einen ersten binären Wert hat, indem die (i)te Spalte aus der ersten Sequenz, die bezüglich der (i-1)ten Spalte nicht verschoben ist, gebildet wird,
- wenn das (i-1)te Element einen zweiten binären Wert aufweist, indem die (i)te Spalte aus der ersten Sequenz gebildet wird, welche bezüglich der (i-1)ten Spalte zirkular um eine Position verschoben ist.
Wenn die binären Sequenzen PRBSs sind, sind die resultierenden Arrays 1-ausrichtbar; wenn eine oder beide binäre Sequenzen umkehrbare ausrichtbare binäre Sequenzen sind (siehe unten), ist das resultierende Array 2- oder 4-ausrichtbar.

Orthogonale Sequenzen:

Durch die Verwendung zweier binärer Sequenzen, von denen jede die Fenstertechnikeigenschaft besitzt, ist es möglich, rechtwinklige Fenstertechnikmuster aufzubauen. Im allgemeinen ist eine Sequenz verwendet, um Musteränderungen zu bestimmen, wenn eine Bewegung parallel zu einer Musterachse stattfindet, während die andere Sequenz Musteränderungen steuert, wenn eine Bewegung parallel zu der anderen Musterachse stattfindet. Folglich kann eine Positionierung entlang jeder Musterachse durch Bezugnahme auf die entsprechende Sequenz bestimmt werden. Derartige Muster können 1-ausrichtbar oder 2-ausrichtbar sein (jedoch im allgemeinen 4-ausrichtbar, da es notwendig ist, vor dem Bewirken der Positionsbestimmung zwischen den zwei Sequenzen zu unterscheiden). Damit ein Muster 2-ausrichtbar ist, müssen beide binären Sequenzen nicht nur fensterbildend sein, sondern dürfen, zumindest nach dem Codieren, nicht die gleiche Fenstertechnik-Teilsequenz ergeben, wenn sie in beide Richtungen gelesen werden.
Vier Typen verwendbarer Sequenzen können identifiziert werden:
Typ 1 - de Bruijn-Sequenzen;
Typ 2 - pseudozufällige Sequenzen;
Typ 3 - ausrichtbare Sequenzen (d.h. Sequenzen, bei denen jede Fensterteilsequenz der Länge m nur einmal auftritt, während ihre Umkehrung nicht auftritt);
Typ 4 - komplementär ausrichtbare Sequenzen (d.h. Sequenzen, bei denen jede Fensterteilsequenz der Länge m nur einmal auftritt, während die komplementäre Umkehrung nicht auftritt).
Alle vier Typen sind fensterbildend, wobei die ersten zwei Typen 1-ausrichtbare Muster erzeugen und die zweiten Typen 2-ausrichtbare Muster. Die Eignung jedes Sequenztypen hängt von der verwendeten Codierung und dem verwendeten Erfassungsverfahren ab.
Die beiden ersten Sequenztypen wurden in der Literatur ausführlich untersucht, während es scheint, als hätten die beiden zweiten Typen vorher keine Aufmerksamkeit erhalten. Es ist bekanntlich relativ einfach, Computersuchen durchzuführen, um ausrichtbare und komplementär ausrichtbare binäre Sequenzen zu finden, jedoch ist es selbst für maßvolle Fensterlängen sehr zeitaufwendig; es wäre daher nützlich, in der Lage zu sein, diese Sequenzen algorithmisch aufzubauen. Der Anhang B behandelt eine Möglichkeit, wie dies geschehen kann.

Musteraufbau - allgemeine Betrachtungen

Die genaue Art der Informationen, die wiedergewinnbar in dem Muster 20 enthalten sein müssen, um eine Teilmustererfassung und eine Positionsbestimmung zu ermöglichen, hängt von der Beschaffenheit des/der darunterliegenden Arrays/Sequenzen, dem verwendeten Codierverfahren und dem verwendeten Erfassungsverfahren ab. Allgemein gesprochen sind jedoch folgende Informationen erforderlich:
- Array/Sequenz-Elementewert
- Zellenstrukturierung
- Wechselbeziehung der Zellen beim Bilden eines Musters
- Musterausrichtung
Wie in Fig. 5 gezeigt ist, können Informationen über diese Punkte auf drei elementare Arten geliefert werden, nämlich inhärent in den Zellenwerten, die das/die darunterliegende Array/Sequenz codieren (siehe Linie 200); als explizite Hilfsmustermerkmale, die mit der Codierung kombiniert sind, die durch die Zellenwerte dargestellt ist (siehe Linie 201) und unabhängig von dem Muster (siehe Linie 202).
Die unterbrochenen gestrichelten Verbindungen zwischen den Informationspunkten der Musterausrichtung, der Wechselbeziehung der Zellen und der Zellenstrukturierung auf der einen Seite und die drei Verfahren 200, 201, 202 des Lieferns dieser Informationen auf der anderen sind dazu bestimmt, die Vielfalt der möglichen Kombinationen zu zeigen. Jeder der oben genannten Informationspunkte ist nachfolgend erläutert.
Der Bequemlichkeit halber wird hierin nachfolgend angenommen, daß der Wert jeder Zelle in dem Muster 20 als eine Farbe dargestellt ist, die für jeden möglichen Wert eindeutig ist, wobei offensichtlich ist, daß die nachfolgend gegebenen Lehren allgemein für jede andere Form einer physikalischen Darstellung des Zellenwerts gelten.

Array/Sequenz-Wertcodierung:

Es gibt zwei Hauptcodiertechniken, wobei eine darin besteht, jeder Zelle Cij eine Farbe zuzuteilen, die den absoluten Wert eines entsprechenden Elements des Arrays, das codiert werden soll, darstellt, während die andere darin besteht, einen Sequenzelementewert als eine Farbänderung zwischen zwei Zellen zu codieren, wenn eine Bewegung in eine Richtung, die mit der Musterachse, die zu der Sequenz gehört, ausgerichtet ist, stattfindet. Eine detailliertere Betrachtung der Übergangscodierung folgt später.

Zellenstrukturierung:

Es ist wichtig, in der Lage zu sein, einen Übergang von einer Zelle zu einer anderen zu erfassen, d.h., in der Lage zu sein, Zellgrenzen zu erfassen. Zellgrenzinformationen können durch die Verwendung eines Codierungsschemas, das sicherstellt, daß benachbarte Zellen nicht die gleiche Farbe haben, mit Zellenwerten (Verfahren 200 in Fig. 5) codiert werden (sogar wenn in dem Fall der Absolutwertcodierung der gleiche Elementwert des darunterliegenden Arrays oder der Sequenz codiert wird). Im einfachsten Fall kann angenommen werden, daß jede Zelle vier Nachbarn aufweist, zwei horizontal und zwei vertikal (diagonale Übergänge sind entweder verhindert oder werden anderweitig erfaßt, oder die Vorrichtung ist entworfen, um Fehler zu tolerieren, die die Folge solcher Übergänge sein können). Fig. 6 zeigt die Absolutwertcodierung eines binären Arrays unter Verwendung von vier Farben, wobei zwei jeweils jedem binären Wert "1" und "0" entsprechen. Wenn Übergänge zu diagonalen Nachbarn ebenfalls zuverlässig erfaßt werden sollen, muß das Codierschema zusätzlich sicherstellen, daß diese diagonalen Nachbarn stets bezüglich der betrachteten Zellen unterschiedlich gefärbt sind.
Zellgrenzinformationen können ferner durch das Vorsehen von Hilfsmustermerkmalen (Verfahren 201 in Fig. 5) und insbesondere durch das Vorsehen von Separatorzonen zwischen der den Wert definierenden Fläche jeder Zelle codiert werden. Fig. 7 zeigt die Absolutwertcodierung des gleichen binären Arrays, das in der Fig. 6 codiert ist, wobei drei Farben verwendet sind - eine erste Hintergrundfarbe, die durch Leerstellen in der Figur dargestellt sind, eine zweite Farbe, die einem ersten binären Wert entspricht (z.B. "0") und durch eine Schraffierung in einer ersten Richtung in Fig. 7 dargestellt ist, und eine dritte Farbe, die dem zweiten binären Wert entspricht (z.B. "1") und durch eine Schraffierung in einer zweiten Richtung in Fig. 7 dargestellt ist. Der Wert jeder Zelle Cij ist durch ein Quadrat 21 der entsprechenden zweiten oder dritten Farbe dargestellt, wobei dieses Farbquadrat (eine Markierung) kleiner ist als die Musterzellengröße und in seiner Zelle mittig positioniert ist, um um dasselbe herum einen Rand in der ersten Farbe zu belassen, der Separatorzonen zwischen den Farbquadraten 21 liefert, so daß benachbarte Quadrate die gleiche Farbe aufweisen können, ohne Probleme zu verursachen. Bei der relativen Dimensionierung der Separatorzonen und der Farbquadrate, die in Fig. 7 gezeigt ist, gibt es ein bestimmtes Risiko, das ein Einpixel-Erfassungskopf 16 zumindest teilweise entlang des Hintergrunds über das Muster wandern könnte und daher nicht in der Lage ist, die den Wert darstellenden Farbquadrate 21 richtig zu erfassen. Jedoch ist die Wahrscheinlichkeit, daß dies in einem signifikanten Ausmaß auftritt, gering, vorausgesetzt die Separatorzonen sind relativ schmal gehalten. Bei Fig. 6 gibt es selbstverständlich kein Risiko, daß der Erfassungskopf die den Wert darstellenden Zellflächen verfehlt.
Zellgrenzinformationen können ferner durch ein Kombination des Codierens mit Zellwerten (wie in Fig. 6) und der Verwendung von Separatorzonen (wie in Fig. 7) geliefert werden. Z.B. könnten Übergänge in der horizontalen Richtung erfaßbar gemacht werden, indem eine Änderung der Zellfarbe sichergestellt wird, während Übergänge in der vertikalen Richtung durch Separatorzonen markiert werden könnten.
Die Verwendung von Muster-unabhängigen Einrichtungen, um Zellgrenzen zu markieren, ist ebenfalls möglich, z.B. durch Vorsehen einer Einrichtung, die eine Bewegung des Erfassungskopfs 16 mittels vertikaler und horizontaler Entfernungen, die dem vertikalen und horizontalen Abstand der Zellen entsprechen, registriert. Derartige Anordnungen sind nicht bevorzugt.

Zellen-Wechselbeziehungsinformationen:

Es ist selbstverständlich notwendig, in der Lage zu sein, eine erfaßte Zelle positionsmäßig auf vorher erfaßte Zellen zu beziehen, um die relativen Standorte der Array/Sequenz-Elemente, die dadurch aus dem erfaßten Muster decodiert werden, festzustellen, um genau ein Fenstertechnik-Teilarray oder -Teilsequenzen aufzubauen. Wenn der Erfassungskopf 16 mehr als eine Zelle auf einmal erfaßt, kann die Wechselbeziehung der erfaßten Zellen ohne weiteres aus dem erfaßten Bild hergeleitet werden, wobei die Zellen-Wechselbeziehungsinformationen direkt übermittelt werden. Wenn jedoch ein Einpixel-Erfassungskopf verwendet ist, müssen die Zellen-Wechselbeziehungsinformationen mittels einer (oder mehrerer) der drei allgemeinen Verfahren 200, 201, 202 in Fig. 5 übermittelt werden, wobei sonst eine Annahme bezüglich der Erfassungskopfbewegung (z.B. das sich derselbe geradlinig bewegt) getroffen werden muß und das/die resultierende decodierte Array/Sequenz dann auf eine Konsistenz mit dieser Annahme überprüft werden muß. Tatsächlich kann für eine Einpixel-Erfassung eine akzeptable Lösung darin liegen, bestimmte Wechselbeziehungsinformationen vorzusehen und ferner bestimmte Annahmen bezüglich der Bewegungsrichtung zu treffen.
Die Codierung der vollen Zellen-Wechselbeziehungsinformationen zusammen mit den Zellenwertinformationen (Verfahren 200) macht es erforderlich, daß alle Nachbarzellen einer gegebenen Zelle bezüglich dieser Zelle und der anderen Nachbarzellen verschiedene Farben aufweisen, ungeachtet der darunterliegenden codierten Elementewerte. Selbst wenn nur horizontale und vertikale Übergänge betrachtet werden (und keine diagonalen Übergänge), ist ein Minimum von neun Farben erforderlich; wenn diagonale Übergänge berücksichtigt werden, sind mindestens siebzehn Farben notwendig, was aufgrund der Anforderungen, die auf dem Erfassungskopf 16 und dem dazugehörigen Farberfassungsschaltungsaufbau liegen, nicht bevorzugt ist.
Zellen-Wechselbeziehungsinformationen können in Hilfsmusterelementen beinhaltet sein (Verfahren 201 in Fig. 5), wobei eine bevorzugte Möglichkeit, dies durchzuführen, darin besteht, Separatorzonen, die vorgesehen sind, um Zellgrenzen darzustellen, farblich zu codieren. Somit stellt Fig. 8 einen Teil eines Musters dar, bei dem der Wert jeder Zelle durch ein geeignet gefärbtes Quadrat 21 dargestellt ist, und bei dem Separatorzonen 23 und 24 verwendet sind, um jede Zelle abzugrenzen. Die Separatorzonen 23 begrenzen jede Zelle in einer vertikalen Richtung und die Separatorzonen 24 begrenzen jede Zelle in einer horizontalen Richtung. Die Zonen 23 und 24 haben unterschiedliche Farben, wobei die Farben beider Zonen sich von den Farben, die für die Farbquadrate 21 verwendet sind, unterscheiden. Eine solche Anordnung liefert horizontale und vertikale Wechselbeziehungsinformationen während des Übergangs von einer Zelle zu einer anderen, zeigt jedoch nicht an, ob die neue Zelle über/unter (für eine vertikale Bewegung) oder rechts/links (für eine horizontale Bewegung) liegt. Bei dem Muster in Fig. 8 ist es deshalb notwendig, eine Annahme bezüglich dieser Richtungsinformationen zu treffen. Fig. 9 zeigt ein Muster, das ähnlich dem in Fig. 8 ist, bei dem es jedoch nicht notwendig ist, irgendwelche Annahmen bezüglich der Richtung zu treffen. In Fig. 9 sind wiederum Farbquadrate 21 verwendet, um Array/Sequenz-Elementewerte zu codieren, obwohl in diesem Fall die Färbung des Quadrats 21 zur Vereinfachung der Darstellung nicht gezeigt ist. Die Farbquadrate 21 sind mittels Separatorzonen 25 voneinander getrennt, von denen jede eine von vier möglichen Separatorzonenfarben besitzt, die von den Farben, die für die Quadrate 21 verwendet sind, verschieden sind. Die Separatorzonen, die benachbarte Quadrate 21 in Reihen trennen, die parallel zu der horizontalen Achse Ap verlaufen, sind alternativ in zwei von vier möglichen Separatorzonenfarben gefärbt, während die Zonen 25, die benachbarte Quadrate 21 in Spalten trennen, die parallel zu der vertikalen Achse Bp verlaufen, alternativ in den anderen zwei der vier möglichen Separatorzonenfarben gefärbt sind. Wann immer ein Einpixel-Erfassungskopf 16 von einem Farbquadrat 21 in ein anderes übergeht, kreuzt er eine Zone 25, deren Farbe eindeutig die Bewegungsrichtung des Erfassungskopfs 16 anzeigt. Außerdem kann ferner die Wechselbeziehung des Beginns und des Endes von Zellen bei einem diagonalen Übergang bestimmt werden, da diagonale Übergänge im allgemeinen das Kreuzen der Enden von zwei Separatorzonen einschließt, einer von jedem Typ.
Das Bereitstellen von Zellen-Wechselbeziehungsinformationen durch eine Einrichtung, die von dem Muster selbst unabhängig ist (Verfahren 202 in Fig. 5), ist selbstverständlich möglich (z.B. durch Erfassen der Bewegungsrichtung des Erfassungskopfs 16 über dem Muster), wird jedoch im allgemeinen nicht bevorzugt.

Musterausrichtungsinformationen:

Abhängig von den Ausrichtungscharakteristika des/der darunterliegenden Arrays/Sequenzen, müssen unterschiedliche Beträge an Ausrichtungsinformationen geliefert werden. Somit sind für Muster, die auf 4-ausrichtbaren Arrays basieren, keine Ausrichtungsinformationen notwendig, während es für Muster, die aus ausrichtbaren oder komplementär ausrichtbaren Sequenzen aufgebaut sind, im allgemeinen notwendig ist, zu identifizieren, welche Sequenz in die horizontale Richtung verläuft und welche in die vertikale Richtung verläuft.
Wie bei den anderen Informationstypen können die Musterausrichtungsinformationen entsprechend einem beliebigen (oder mehrerer) der Verfahren 200, 201, 202 in Fig. 5 verfügbar gemacht werden. Es sei jedoch bemerkt, daß sich die Ausrichtungsinformationen stark auf die Zellen-Wechselbeziehungsinformationen beziehen und im allgemeinen zusammen mit den letztgenannten geliefert werden können. Z.B. identifizieren die Separatorzonen 23, 24 des Musters in Fig. 8 schon die vertikalen bzw. horizontalen Übergänge, wobei dies die gesamten Ausrichtungsinformationen darstellt, die für ein 2-ausrichtbares Muster erforderlich sind (tatsächlich müssen die Separatorzonen 23, 24 nur identifizierte unterschiedliche Übergangsrichtungen aufweisen, um die gewünschten Zellen-Wechselbeziehungsinformationen zu ergeben - die Zugehörigkeit der Separatorzonen 23 zu vertikalen Übergängen und der Zonen 24 zu horizontalen Übergängen liefert tatsächlich die zusätzlichen Ausrichtungsinformationen).
Wenn Zellen-Wechselbeziehungsinformationen nicht speziell vorgesehen sind (z.B., da sie bei der Besichtigung offensichtlich sind, wie z.B. bei einem Erfassungskopf 16, der mehr als eine Zelle auf einmal erfaßt), können selbstverständlich die Ausrichtungsinformationen nicht in den Zellen-Wechselbeziehungsinformationen enthalten sein, wobei eine spezifische Einrichtung verwendet werden muß, um die Ausrichtungsinformationen zu tragen. Fig. 10 zeigt eine solche Möglichkeit des Bereitstellens von Ausrichtungsinformationen (mittels des Verfahrens 201 in Fig. 5). Insbesondere zeigt Fig. 10A, wie ein Farbquadrat 21, wie es in den Fig. 7, 8 und 9 verwendet ist, um Array/Sequenz-Elementewerte-Informationen zu codieren, in der Ecke desselben, die zu dem Ursprung der Achsen Ap und Bp gerichtet ist, mit einer Ausrichtungsmarkierung 22 einer von den Farben, die für das Farbquadrat 21 verwendet sind, verschiedenen Farbe, markiert sein kann. Wenn alle Farbquadrate eines Musters auf diese Art und Weise markiert wurden, ist es beim Erfassen eines Teilmusters eine relativ einfache Sache, die Ausrichtung des Teilmusters zu bestimmen. Somit kann z.B. das Teilmuster, das in Fig. 10B gezeigt ist (das den ersten drei Reihen und Spalten des Musters in Fig. 7 entspricht, wobei Ausrichtungsmarkierungen hinzugefügt sind), als um 270º bezüglich der Musterausrichtung in Fig. 10A gedreht betrachtet werden. Die Ausrichtungsmarkierungen 22 der Form in Fig. 10 sind selbstveständlich nur auf Fälle anwendbar, bei denen der Erfassungskopf 16 eine ausreichende Auflösung liefert, um die Beziehung zwischen zumindest einer solchen Markierung und ihrem dazugehörigen Farbquadrat 21 zu erkennen.

Beispielcodierungen

Während die Informationstypen diskutiert wurden, die nötigerweise zur Musterwiedergewinnung vorgesehen sind, und Beispiele gegeben wurden, wie jeder Informationstyp codiert sein könnte, werden als nächstes mehrere vollständige Codierungsschemata zur wiedergewinnbaren Codierung sowohl von Arrays als auch von Sequenzen betrachtet. Alle nachfolgend betrachteten Codierschemata codieren die erforderlichen Informationen in dem Muster 20 (d.h. durch Verwendung der Verfahren 200, 201 in Fig. 5); das Bereitstellen von Informationen, die unabhängig von dem Muster 20 sind, ist im allgemeinen nicht bevorzugt, da es ein zusätzliches Erfassungssystem erfordern würde.

Codierung von Arrays:

Zweidimensionale Arrays werden vorzugsweise mittels einer Absolutwertcodierung ihrer Elementewerte codiert. Für ein 2-ausrichtbares Array ist z.B. ein Codierschema wie das, das bei dem Muster in Fig. 8 verwendet ist, geeignet. Bei dem Muster in Fig. 8 sind die Array-Elementewerte mittels einer geeigneten von zwei Farben für die Farbquadrate 21 codiert; die Zellenstrukturierung ist mittels der Separatorzonen 23, 24 vorgesehen; Zellen-Wechselbeziehungsinformationen (vertikale, horizontale und diagonale Beziehungen) für eine Einpixel-Erfassung sind durch eine unterschiedliche Färbung der Zonen 23 und 24 vorgesehen; Ausrichtungsinformationen werden dadurch geliefert, daß bekannt ist, welche Zonenfarbe zu vertikalen Übergängen und welche zu horizontalen Übergängen gehört.

Codierung von Sequenzen unter Verwendung der Absolutwertcodierung:

Bei Mustern, die auf einem Paar von orthogonalen Sequenzen basieren, wobei sich eine horizontal und die andere vertikal erstreckt, müssen die Sequenzen für eine Absolutwertcodierung zuerst in ein zweidimensionales Array kombiniert werden, um ohne weiteres anwendbar zu sein. Fig. 11 zeigt zwei mögliche Arten des Herleitens eines geeigneten Arrays aus zwei orthogonalen Sequenzen (bei dem dargestellten Beispiel sind die Sequenzen zwei PRBSs, die als PRBS-1 und PRBS-2 bezeichnet sind).
In der Fig. 11A wurde PRBS-1 parallel zu der horizontalen Achse Ap aufgezeichnet und PRBS-2 wurde parallel zu der vertikalen Achse Bp aufgezeichnet. In jede Zelle Cij wurde das geordnete Paar von Elementewerten von PRBS-1 und PRBS-2 geschrieben, die der Zelle entsprechen. Es gibt vier mögliche derartig geordnete Paare, wobei diese (0,0), (0,1), (1,0) und (1,1) sind. Indem jedem verschiedenen geordneten Paar ein Wert zugewiesen wird, ist es möglich, jeder Zelle einen von vier möglichen Werten zuzuweisen. Es ist dieser Zellenwert, der nachfolgend in ein entsprechendes Mustermerkmal übersetzt wird.
In Fig. 11B wurden die zwei PRBSs entlang der Achsen Ap bzw. Bp aufgezeichnet. Jedoch wurden in diesem Fall die Elemente von PRBS-2 mit einem Abstand zweier Reihen zwischen benachbarten Elementen geschrieben, beginnend bei der zweiten Reihe. Jede ungerade numerierte Reihe des Zellenarrays (wobei die erste Reihe mit Reihe 1 numeriert ist) ist mit einer Kopie von PRBS-1 gefüllt. Jede gerade Reihe ist mit dem entsprechenden Elementewert von PRBS-2 gefüllt. Der Wert jeder Zelle ist folglich entweder Eins oder Null, da jede Zelle nur zu einem Element von einer der zwei PRBSs gehört.
Fig. 12 zeigt ein Muster, das durch eine Absolutwertcodierung eines Arrays erzeugt wird, welches durch das Kombinieren zweier ausrichtbarer (umkehrbarer) binärer Sequenzen auf die Art und Weise gebildet ist, die in Fig. 11A dargestellt ist (es ist offensichtlich, daß das Array und das resultierende Muster 2-ausrichtbar sind). Die Musterzellen können vier mögliche Werte annehmen und demgemäß sind vier Farben zum Codieren der Arrayelementewerte verwendet. Zellgrenzinformationen, Zellen-Wechselbeziehungsinformationen und Musterausrichtungsinformationen werden mittels weißer und schwarzer Separatorzonen 26, 27 auf die gleiche Art und Weise wie die Zonen 23, 24 des Musters in Fig. 8 geliefert (da das Muster 2-ausrichtbar ist, ist es nur notwendig, in der Lage zu sein, zwischen horizontalen und vertikalen Ausrichtungen zu unterscheiden). Insgesamt sind bei dem Muster in Fig. 12 sechs Farben verwendet. Bezüglich der Zellen-Wechselbeziehungsinformationen ist es mit einem Einpixel-Erfassungskopf 16 nicht möglich, die Richtung eines erfaßten Übergangs festzustellen, obwohl es möglich ist, zwischen horizontalen, vertikalen und diagonalen Übergängen zu unterscheiden. Es ist jedoch zweckmäßig, auf der Basis fortzufahren, daß die Bewegungsrichtung des Erfassungskopfs unverändert bleibt; diese Annahme ist nur in dem Fall einer Richtungsumkehr falsch, wobei ein solches Ereignis aufgrund der resultierenden Fehlübereinstimmungen mit dem erwarteten Muster schnell erfaßt werden kann. Wenn ein Erfassungskopf mit einem Mehrzellen-Sichtfeld verwendet ist, können alle notwendigen Bewegungsrichtungsinformationen aus dem erfaßten Bild hergeleitet werden.
Fig. 13 zeigt wie Fig. 12 ein Muster, das durch eine Absolutwertcodierung eines Arrays, das auf zwei ausrichtbaren (umkehrbaren) binären Sequenzen basiert, erzeugt ist; jedoch wurden in diesem Fall die Sequenzen auf die Art und Weise in ein Array kombiniert, die in Fig. 11B dargestellt ist, wodurch jede Zelle nur zwei mögliche Werte besitzt (tatsächlich ist Fig. 13 eine Codierung der Sequenzen, die in Fig. 11B gezeigt sind). Bei dem Beispiel in Fig. 13 ist der Zellgrenzpunkt durch die Verwendung farbiger Quadrate 21 auf einem Hintergrund einer unterschiedlichen Farbe gelöst (siehe Fig. 7); folglich sind nur zwei Farben notwendig, um einen Zellenwert darzustellen, eine für jeden möglichen binären Wert. Der Hintergrund wird durch zwei weitere Farben dargestellt, wobei die Zellen in ungeraden Musterreihen eine erste Hintergrundfarbe 28 aufweisen und die Zellen in geraden Musterreihen eine zweite Hintergrundfarbe 29 aufweisen. Folglich erscheinen die Farbquadrate 21 vor einem gestreiften Hintergrund, der sowohl bestimmte begrenzte Zellen-Wechselbeziehungsinformationen als auch Ausrichtungsinformationen liefert, die ausreichen, um anzuzeigen, welche Reihe sich auf welche der zwei darunterliegenden umkehrbaren Sequenzen bezieht.
Bei der Anordnung in Fig. 11B zum Kombinieren der Ap-Achsen-Sequenz und der Bp-Achsen-Sequenz in ein Array enthält jede alternierende Reihe Zellen, die das gleiche Element der Bp-Achsen-Sequenz darstellt; genauso enthält jede alternierende Reihe des Musters in Fig. 13 Farbquadrate 21, die das gleiche Element der Bp-Achsen-Sequenz darstellen. Folglich ist es möglich, das Muster in Fig. 13 zu modifizieren, indem die Farbquadrate 21 in der gleichen Reihe der Bp-Achsen-Sequenz zusammenlaufen. Auf Kosten der Verwendung einer zusätzlichen Farbe kann tatsächlich jede Reihe, die verwendet ist, um einen Elementewert der Bp-Achsen-Sequenz darzustellen, dies durchführen, indem sie vollständig mit einer von zwei eindeutigen Farben, die von dem binären Wert des Werts des Elements, das dargestellt wird, abhängt, gefärbt ist (diese Farben würden unterschiedlich zu denen sein, die verwendet sind, um die Elementewerte für die Ap-Achsen-Sequenz darzustellen). Die Farbquadrate 21 wären dann nicht langer verwendet, um die Bp-Achsen-Sequenz darzustellen. Außerdem können die Farbquadrate 21, die verwendet sind, um die Ap-Achsen-Sequenz darzustellen, nun parallel zu der Bp-Achse zu der Kante der benachbarten Reihen erweitert werden, da garantiert werden kann, daß diese Reihen eine bezüglich der Quadrate 21 der Ap-Achsen-Sequenz unterschiedliche Farbe aufweisen; die Hintergrundzonen, die die Quadrate 21 der Ap-Achsen-Sequenz in der Richtung parallel zu der Achse trennen, würden jedoch beibehalten werden, um eine Unterscheidung zwischen angrenzenden Zellen sicherzustellen. Folglich wird bei dieser modifizierten Form des Musters in Fig. 13 der Punkt der Zellgrenzerfassung durch die Technik in Fig. 6 gelöst, wenn eine Bewegung entlang der Reihen der Ap-Achsen-Sequenz stattfindet, und durch die Technik in Fig. 7, wenn eine Bewegung zwischen den Reihen stattfindet.

Codieren von Sequenzen unter Verwendung einer Übergangscodierung:

wenn ein Muster 20 direkt auf zwei darunterliegenden orthogonalen Fenstertechniksequenzen basiert, eine (hierin die horizontale Sequenz) zur Positionserfassung entlang der horizontalen Musterachse Ap und die andere (die vertikale Sequenz) zur Positionserfassung entlang der vertikalen Musterachse Bp ist es geeignet, ein Übergangscodierschema zu verwenden, um die Sequenzwerte zu codieren. Spezieller werden Änderungen des Zellwerts während horizontaler Übergänge von Zelle zu Zelle in dem Muster verwendet, um die Elementewerte der horizontalen Sequenz zu codieren, während Änderungen des Zellwerts während vertikaler Übergänge von Zelle zu Zelle verwendet werden, um die Elementewerte der vertikalen Sequenz zu codieren. Da Übergangscodierschemata eine praktische Wichtigkeit zu haben scheinen, ist nachfolgend ein allgemeiner Überblick über derartige Schemata gegeben, auf den folgend drei Beispielcodierungen betrachtet werden. Der Rückblick überdeckt sowohl Schemata mit als auch ohne Separatorzonen; wenn Separatorzonen (oder kurz nur "Separatoren") vorgesehen sind, geschieht jede Farbcodierung der Separatoren, um Zellen-Wechselbeziehungs- oder Musterausrichtungs-Informationen zu übermitteln, auf einer Absolutwertbasis, nicht auf einer Übergangsbasis. Schemata, die keine Separatoren verwenden, werden als "Nicht-Separator"- Schemata bezeichnet. Schemata, bei denen nur horizontale, oder nur vertikale, Übergänge mittels Separatoren markiert sind, werden als "Ein-Separator"-Schemata bezeichnet. Schemata, bei denen sowohl horizontale als auch vertikale Übergänge mittels jeweiliger farbiger Separatoren markiert sind, werden als "Zwei-Separator"-Schemata bezeichnet (Schemata, bei denen eine einzelne Separatorfarbe verwendet ist, um sowohl vertikale als auch horizontale Übergänge zu markieren, werden nicht betrachtet).
Bei der folgenden Diskussion soll eine erste binäre Fenstertechniksequenz (die X-Sequenz) codiert werden, die parallel zu der horizontalen Musterachse Ap verläuft, und eine zweite binäre Fenstertechniksequenz (die Y-Sequenz) soll codiert werden, die parallel zu der vertikalen Musterachse Bp verläuft.
Es sei angenommen, daß die Übergänge in der horizontalen Richtung (positive Richtung der Achse Ap) durch die Funktionen h&sub0; und h&sub1; gegeben sind und in die vertikale Richtung (positive Richtung der Achse Bp) durch die Funktionen v&sub0; und v&sub1;, wobei die Suffixe "0" und "1" den Wert des X- oder Y-Sequenzelements, das codiert werden soll, bezeichnen. Dies bedeutet, daß, wenn die gegenwärtige Zelle mit der Farbe c gefärbt ist, die nächste Zelle in einer horizontalen Richtung mit der Farbe h&sub0;(c) oder h&sub1;(c) gefärbt ist, entsprechend dem Wert des entsprechenden Sequenzelements. Die Bedingungen dieser Funktionen sind, daß das resultierende Muster Elementewertinformationen codieren muß, die Musterzellen strukturieren muß (durch Farbänderung zwischen benachbarten Zellen, wenn kein Separator vorliegt) und ausreichende Zellen-Wechselbeziehungs- und Musterausrichtungs-Informationen ermöglichen muß, die wiedergewonnen werden sollen; bezüglich der Zellen-Wechselbeziehungs- und Musterausrichtungs-Informationen sollte als der minimale Informationsbetrag, der wiedergewinnbar sein muß, der verwendet werden, der es ermöglicht, horizontale und vertikale Bewegungen zu unterscheiden und zu identifizieren. Eine weitere Bedingung besteht darin, daß die Codierung deutlich sein muß (d.h., daß, welcher Weg über das Muster auch immer genommen wird, die Anwendung der Codierfunktionen eine übereinstimmende Codierung für eine beliebige gegebene Stimmungszelle erzeugt).
Diese Bedingungen allein führen zu bestimmten Schlüssen über die minimale Anzahl an Farben, die für bestimmte Typen des Codierschemas notwendig sind. Folglich muß für die Codierung gelten, um deutlich zu sein:
hi(vj(c)) = vj(hi(c)) für alle Farben x und i,j &epsi; {0,1} da andernfalls ein Konflikt bei der Bestimmung der Farbe der Zelle, die diagonal an eine Zelle mit der Farbe c angrenzt, auftreten würde. Außerdem muß es, damit eine Decodierung möglich ist, möglich sein, zwischen h&sub0;(c) und h&sub1;(c) und zwischen v&sub0;(c) und v&sub1;(c) zu unterscheiden; in anderen Worten heißt das:
h&sub0;(c) ≠ h&sub1;(c) für alle Farben c und
v&sub0;(c) ≠ v&sub1;(c) für alle Farben c.
Gibt es keine Separatoren, dürfen keine angrenzenden Zellen mit der gleichen Farbe gefärbt sein (hierbei ist "angrenzend" als vertikal oder horizontal, nicht diagonal angrenzend verwendet), wobei eine horizontale Bewegung mittels der Zellenfarbe von einer vertikalen Bewegung unterscheidbar sein muß, so daß
c,h&sub0;(c),h&sub1;(c),v&sub0;(c),v&sub1;(c) alle für jede Farbe c unterschiedlich sein müssen.
Wenn es nur einen Satz von Separatoren gibt, folgt:
c,h&sub0;(c),h&sub1;(c) müssen alle für jede Farbe c unterschiedlich sein; oder
c,v&sub0;(c),v&sub1;(c) müssen alle für jede Farbe c verschieden sein.
Wenn zwei Sätze von Separatoren vorgesehen sind, können angrenzende Zellen selbstverständlich die gleiche Farbe haben.
Auf der Basis des Vorangegangenen gilt:
- Wenn es keine Separatoren gibt, sind mindestens fünf Farben notwendig.
- Wenn es nur einen Satz von Separatoren gibt, sind mindestens vier Farben notwendig.
- Wenn es zwei Sätze von Separatoren gibt, sind mindestens vier Farben notwendig.
Bei der obigen Erläuterung wurden nur horizontale und vertikale Übergänge betrachtet. Wenn diagonale Übergänge erlaubt sind, während eine solche Bewegung durchgeführt wird, gibt es zwei Informationsbits, die bestimmt werden müssen, eines für jede der Sequenzen X-Sequenz, Y-Sequenz, und die nachfolgend als das X-Bit bzw. das Y-Bit bezeichnet werden. Es gibt mehrere mögliche Informationsebenen, abhängig von dem verwendeten Codierschema. Folglich könnte es ausschließlich möglich sein, zu sagen, daß eine diagonale Bewegung durchgeführt wurde, oder es könnte ferner möglich sein, zu sagen, daß das X-Bit und das Y-Bit gleich (oder ungleich) sind, oder sogar die Werte sowohl des X-Bits als auch des Y-Bits; eine weitere Möglichkeit besteht darin, daß es möglich ist, entweder die Information festzustellen, daß das X-Bit und das Y-Bit gleich sind, oder den Wert der beiden Bits.
Hinsichtlich der Funktionen hi und vj können die Farben in dem folgenden Satz bei einer diagonalen Bewegung weg von einer Zelle mit der Farbe c auftreten:
{ (h&sub0;(v&sub0;(c)), h&sub0;(v&sub1;(c)), h&sub1;(v&sub0;(c)),h&sub1;(v&sub1;(c)) }
Es sei bemerkt, daß dieser Satz zumindest zwei Elemente aufweist, da h&sub0;(vj(c)) ≠ h&sub1;(vj(c)) und h&sub1;(v&sub0;(c)) ≠ h&sub1;(v&sub1;(c)). Die Größe dieses Satzes bestimmt die Informationsmenge, die erhalten werden kann, sobald bekannt ist, daß eine diagonale Bewegung stattgefunden hat. Ein Codierschema wird als r-Diagonal (wobei r = 2, 3, 4) bezeichnet, wenn die Größe dieses Satzes gleich r ist. Das Problem des Erfassens diagonaler Bewegungen ist unterschiedlich, abhängig von der Anzahl der Separatoren. Wenn es zwei Sätze von Separatoren gibt, werden diagonale Bewegungen automatisch durch die Separatoren erfaßt. Bei dem anderen Extrem, wenn es keine Separatoren gibt, müssen die diagonalen Werte nicht die gleichen wie beliebige horizontale oder vertikale Werte sein: in anderen Worten heißt das, daß für alle c die folgende Bedingung erfüllt sein muß:
{c,h&sub0;(c),h&sub1;(c),v&sub0;(c),v&sub1;(c)}{h&sub0;(v&sub0;(c)),h&sub0;(v&sub1;(c)), h&sub1;(v&sub0;(c)),h&sub1;(v&sub1;(c))} =
Wenn es einen Satz von Separatoren gibt, angenommen Trennzellen in eine vertikale Richtung, dann zeigt das Überqueren eines Separators an, daß entweder eine vertikale oder eine diagonale Bewegung stattfand. Bei einem Ein-Separator-Schema muß daher für jede Farbe c folgende Bedingung erfüllt sein:
{v&sub0;(c),v&sub1;(c)} {h&sub0;(v&sub0;(c)),h&sub0;(v&sub1;(c)),h&sub1;(v&sub0;(c)),h&sub1;(v&sub1;(c))} =
Die obengenannten zusätzlichen Bedingungen, die aus einer Betrachtung diagonaler Übergänge resultieren, bedeuten, daß:
- Wenn es keine Separatoren gibt, die folgenden Farbanzahlen erforderlich sind: acht für eine 2-Diagonal-Codierung; acht für eine 3-Diagonal-Codierung; und neun für eine 4-Diagonal-Codierung.
- Wenn es gerade einen Satz von Separatoren gibt, folgende Farbanzahlen erforderlich sind: fünf für eine 2-Diagonal-Codierung; sechs für eine 3-Diagonal-Codierung; und sieben für eine 4-Diagonal-Codierung.
- Wenn es zwei Sätze von Separatoren gibt, folgende Farbanzahlen erforderlich sind: vier für eine 2-Diagonal-Codierung; fünf für eine 3-Diagonal-Codierung; und sechs für eine 4-Diagonal-Codierung.
Wenn diagonale Übergänge erlaubt sind, sind Schemata, die 4-Diagonal-Eigenschaften liefern, bevorzugt, da sie die Wiedergewinnung der X-Bit- und Y-Bit-Informationen erleichtern.
Die vorangegangenen Bedingungen, die den Codierfunktionen auferlegt sind, garantieren nicht, daß vollständige Zellen- Wechselbeziehungs- oder Musterausrichtungs-Informationen wiedergewinnbar sein werden. Obwohl es gewöhnlich ausreichend ist, die Annahme zu treffen, daß die Bewegungsrichtung unverändert bleibt, bis ein Widerspruch erfaßt ist, beläßt dies noch einen Mangel an Ausrichtungsinformationen für 1-ausrichtbare Sequenzen (de Bruijn-Sequenzen und PRBSs). Außerdem müssen sowohl für ausrichtbare als auch für komplementär ausrichtbare Sequenzen den Codierfunktionen weitere Bedingungen auferlegt werden, um die 2-ausrichtbare Eigenschaft zu bieten. Diese weiteren Anforderungen der vier Typen von Sequenzen werden nachfolgend betrachtet:
Wird z.B. die horizontale Dimension betrachtet, in der die X-Sequenz codiert ist, sind die einzig möglichen Übergänge einer gegebenen Zelle der Farbe c h&sub0;(c), h&sub1;(c), h&sub0;&supmin;¹(c), h&sub1;&supmin;¹(c), wobei der obere Index "-1" einen umgekehrten Übergang anzeigt. Die weiteren Bedingungen, die der Codierfunktion auferlegt werden müssen, sind dann:
de Bruijn-Sequenzen - um volle Ausrichtungsinformationen zu ergeben, sind
h&sub0;(c),h&sub1;(c),h&sub0;&supmin;¹(c), h&sub1;&supmin;¹(c) alle unterschiedlich
PRBS - um volle Ausrichtungsinformationen zu ergeben:
h&sub0;(c) = h&sub0;&supmin;¹(c); h&sub1;(c) ≠ h&sub1;&supmin;¹(c) (in diesem Fall wird eine beliebige Fenstersequenz eine "1" enthalten und die Codierung dieser "1" ergibt beim Lesen die Richtungsinformationen)
Ausrichtbare Sequenzen - um die 2-ausrichtbare Eigenschaft zu liefern:
h&sub0;(c) = h&sub0;&supmin;¹(c);h&sub1;(c) = h&sub1;&supmin;¹(c)
Komplementär ausrichtbar - um die 2-ausrichtbare Eigenschaft zu liefern:
h&sub0; = h&sub1;&supmin;¹(c)
Es kann bemerkt werden, daß die obigen Bedingungen, die der Codierung der de Bruijn-Sequenzen auferlegt sind, vollständige Zellen-Wechselbeziehungs- und Musterausrichtungs- Informationen liefern, so daß keine Annahmen nötig sind, die die Bewegungsrichtung betreffen; Schemata, die den genannten Bedingungen genügen, benötigen jedoch eine beträchtliche Anzahl von Farben.
Während die Bedingungen betrachtet wurden, die allgemein von der Codierfunktion erfüllt sein müssen, sind zwei Typen derartiger Funktionen nachfolgend durch Beispiele beschrieben. Spezieller haben sich folgende zwei Funktionstypen als brauchbar erwiesen:
"Addition modulo N":
h&sub0;(c)=c+a(mod N),h&sub1;(c)=c-a (mod N),
v&sub0;(c)=c+b(mod N),v&sub1;(c)=c-b (mod N),
wobei a, b ≠ 0
"Bitweise Exclusive-OR":
h&sub0;(c)= c.XOR.a ; h&sub1;(c) = c.XOR.b
v&sub0;(c)= c.XOR.d ; v&sub1;(c) = c.XOR.e
wobei a,b,d,e ≠ 0,
a ≠ b und d ≠ e

Erstes Beispiel

Fig. 14 keine Separatoren, Fünffarbcodierung
h&sub0;(c)=c+1 (mod 5) ; h&sub1;(c)=c-1 (mod 5),
v&sub0;(c)=c+2 (mod 5) ; v&sub1;(c)=c-2 (mod 5)
Keine Diagonaleigenschaften
Geeignet für komplementär ausrichtbare Sequenzen.
Dieses Codierschema erzeugt das einfachste Muster in dem Sinne, daß es nur fünf Farben verwendet und keine Separatoren besitzt. Da es jedoch keine diagonalen Eigenschaften besitzt, ist das Schema nur für Situationen geeignet, in denen keine diagonalen Übergänge auftreten oder in denen dieselben nur selten auftreten. Fig. 14A ergibt die Codierungstabelle für das Schema, wobei jede horizontale Reihe das Ergebnis des Anwendens jeder der Codierfunktionen auf eine spezielle Farbe ergibt (die fünf möglichen Farben sind mit C1 bis C5 bezeichnet). Fig. 14B zeigt einen Abschnitt eines Musters, das durch Anwenden des Codierschemas erzeugt ist, um die X- und Y-Sequenzabschnitte, die in der Figur gezeigt sind, zu codieren. Fig. 14C ist eine Decodiertabelle, die, die alten und neuen Zellenfarben vorausgesetzt, einen Übergang in ein X-Bit oder Y-Bit decodiert, wobei den Bitwerten, die in der Tabelle gezeigt sind, ein X oder Y folgt, um die Sequenz anzuzeigen, zu der dieselben gehören.

Zweites Beispiel

Fig. 15 zwei Separatoren, Sechsfarbcodierung
h&sub0;(c) = c ; h&sub1;(c) = c.XOR.1
v&sub0;(c) = c ; v&sub1;(c) = c.XOR.2
Vier diagonale Eigenschaften
Geeignet für ausrichtbare Sequenzen
Dieses Codierschema realisiert die minimale Anzahl von Farben für eine 4-Diagonal-Codierung und erzeugt, wenn sie verwendet ist, um zwei ausrichtbare Sequenzen zu codieren, ein Muster eines beträchtlichen praktischen Nutzens (wenngleich keine vollständige Zellen-Wechselbeziehung geliefert wird, wobei die Annahme getroffen werden muß, daß die Bewegungsrichtung konstant bleibt, bis etwas anderes erwiesen ist). Von den sechs Farben sind zwei für die Separatoren verwendet (eine für die Separatoren, die überquert werden, wenn eine vertikale Bewegung stattfindet, und die andere für die Separatoren, die überquert werden, wenn eine horizontale Bewegung stattfindet); die übrigen vier Farben sind verwendet, um die Sequenz-Elementewertinformationen zu tragen. Fig. 15A zeigt eine Codiertabelle für das Schema, wobei die vier Farben, die zum Tragen der Elementewertinformationen verwendet sind, mit C1, C2, C3, C4 mit jeweiligen binären Werten von 00, 01, 10, 11 bezeichnet sind. Fig. 15B stellt einen Musterabschnitt dar, der aus der Verwendung des Codierschemas hergeleitet ist, um die Abschnitte der X- und Y-Sequenzen, die in den Fig. gezeigt sind, zu codieren (es ist offensichtlich, daß in Fig. 15B die Separatoren nicht dargestellt wurden - die tatsächliche Form des Musters ist ähnlich der, die in Fig. 12 gezeigt ist, wobei die Farben C1 bis C4 die Farben der Farbquadrate 21 sind). Fig. 15 zeigt eine Decodiertabelle zum Herleiten der X- und Y-Bitwerte aus den Farbübergängen, die aus einem Muster gelesen werden, das gemäß dem Schema codiert ist. Die Decodiertabelle ist in drei Abschnitte "horizontal", "vertikal" und "diagonal" geteilt, wobei der Abschnitt, der für einen speziellen Übergang relevant ist, von der Bewegungsrichtung des Erfassungskopfs abhängt, wie durch die Farbe des Separators (oder der Separatoren), die im Verlauf des Übergangs überquert werden, bestimmt wird. Ein diagonaler Übergang erzeugt selbstverständlich sowohl einen X-Bit- als auch einen Y-Bitwert, während horizontale und vertikale Übergänge nur ein X-Bit bzw. ein Y-Bit erzeugen.

Drittes Beispiel

Fig. 16 keine Separatoren, Achtfarbcodierung
h&sub0;(c) = c.XOR.4 ; h&sub1;(c) = c.XOR.2
v&sub0;(c) = c.XOR.1 ; v&sub1;(c) = c.XOR.7
Zwei diagonale Eigenschaften
Geeignet für ausrichtbare Sequenzen
Bei diesem Codierschema sind acht Farben C1 bis C8 mit jeweiligen binären Werten von (000) bis (111) verwendet. Fig. 16A zeigt eine Codiertabelle für das Schema. Fig. 16B stellt einen Abschnitt des Musters dar, der gemäß dem Schema codiert ist, und Fig. 16C zeigt eine partielle Decodiertabelle (ungefüllte Kästchen in der Tabelle zeigen diagonale Übergänge an, da das Codierschema jedoch nur zwei diagonale Eigenschaften besitzt, sind die X-Bit- und Y-Bitwerte nicht unmittelbar herleitbar).

Weitere Beispiele

Obwohl die Verwendung von Sequenzen, die weder ausrichtbar noch komplementär ausrichtbar sind, nicht bevorzugt ist, lauten der Vollständigkeit halber geeignete Codierfunktionen für die de Bruijn-Sequenzen und die PRBSs:
de Bruijn: h&sub0;(c)=c+1 (mod 5), h&sub1;(c)=c+2 (mod 5),
PRBS v&sub0;(c)=c (mod 3), v&sub1;(c)=c+1 (mod 3).
Diese Funktionen gelten selbstverständlich nur für eine Dimension und dienen ausschließlich dazu, die Verfügbarkeit von Funktionen zu zeigen, die die oben gegebenen Bedingungen erfüllen, um vollständige Zellen-Wechselbeziehungsinformationen für eine spezielle Sequenz zu erhalten.

Mustererfassung und Positionsbestimmung

Die allgemeine Funktionsweise des Sensors 11, der Teilmuster-Bildverarbeitungseinheit 12 und der Positionsbestimmungseinheit 13 wurde bereits beschrieben.
Für die oben beschriebenen Muster werden die Teilmusterdaten, die von der Teilmuster-Bildverarbeitungseinheit 12 zu der Positionsbestimmungseinneit 13 geleitet werden, im allgemeinen die Form von binären Daten besitzen, die das/die Teilarray/Teilsequenzen, die unter dem erfaßten Teilmuster liegen, in einer Ausrichtung darstellen, in der der Standort des/der Teilarrays/Teilsequenzen in dem Muster eindeutig bestimmt werden kann.
Wie oben gezeigt ist, kann eine Positionsbestimmung durch ein Übereinstimmungsverfahren, durch die Verwendung eines Index, welcher Teilmusterdaten auf eine Musterposition bezieht, oder durch Berechnung bewirkt werden. Die Positionsbestimmung durch eine Berechnung liefert einen guten Kompromiß zwischen Geschwindigkeit und Aufwand, speziell für große Arrays und Sequenzen. Wenn das Fenstertechnikmuster auf einer Kombination von zwei PRBSs basiert, kann der Standort jeder Fensterlängen-Teilsequenz, die erfaßt wird, in ihrer jeweiligen PRBS unter Verwendung einer Berechnungsmaschine bestimmt werden, um das Verfahren, das im Anhang C offenbart ist, zu implementieren. Wenn das Fenstertechnikmuster auf einem pseudozufälligen Array basiert, kann die Positionsbestimmung durch die Verwendung einer Berechnungsmaschine durchgeführt werden, die das Verfahren, das im Anhang D offenbart ist, implementiert.
Wie vorher bemerkt wurde, kann die Positionsbestimmungseinheit 13 nach der anfänglichen Bestimmung des Standorts der Schreibspitze 11 eingerichtet sein, um ihren Betriebsmodus auf einen solchen zu ändern, bei dem eine beliebige Änderung des Musters, das durch die Schreibspitze erfaßt wird, verwendet wird, um einen aktualisierten Standort basierend auf der inkrementalen Ortsänderung zu liefern, welche durch die Änderung des erfaßten Musters angezeigt wird. Der Betrieb in diesem Modus hängt von der Vorrichtung ab, die in der Lage ist, die Bewegungsrichtung der Schreibspitze korrekt zu bewerten; alternativ kann die Vorrichtung durch die Annahme einer unveränderten Bewegungsrichtung arbeiten, bis eine Fehlübereinstimmung zwischen einem erfaßten Musterelement und dem mittels des gespeicherten Musters vorhergesagten etwas anderes anzeigt, wobei die Vorrichtung danach eine Positionswiedergewinnungsoperation bewirkt. Um einen Fehler bei der Erfassung einer inkrementalen Änderung zu vermeiden, wodurch ein zunehmend anwachsender Positionsfehler entsteht, wenn sich aufeinanderfolgende Positionsänderungen akkumulieren, kann in geeigneten Intervallen eine absolute Positionsbestimmung bewirkt werden. Selbstverständlich sollte eine absolute Positionsbestimmung bewirkt werden, wann immer die Schreibspitze 11 von dem Muster abgehoben und an einer unterschiedlichen Position wieder aufgesetzt wird. Das Abheben der Schreibspitze kann ohne weiteres mittels eines geeigneten Sensors oder einfach mittels des Erkennens eines Verlustes des Musterbildes durch den Erfassungskopf 16 erfaßt werden.

Beispiel-Implementierung

Eine detailliertere Beschreibung eines auf einem Prozessor basierenden Ausführungsbeispiels der Positionserfassungsvorrichtung wird nun bezugnehmend auf die Fig. 17 bis 30 gegeben, welches einen Einpixel-Erfassungskopf 16 verwendet, um Mustermerkmale eines sechsfarbigen Musters 20 mit zwei Separatoren zu erfassen, das zwei ausrichtbare binäre Sequenzen codiert, und welches eine inkrementale Positionsaktualisierung verwendet, die einer anfänglichen Absolutpositionsbestimmung folgt. Mit bestimmten Unterschieden (die beschrieben werden sollen) bei der Tiefpegel-Verarbeitung, die durch die Vorrichtung in Fig. 17 bewirkt wird, kann die Vorrichtung sowohl mit einem Muster der Form in Fig. 12, bei dem die Sequenzwerte absolut codiert sind, als auch mit einem Muster der Form in Fig. 15, bei dem die Sequenzwerte durch Übergänge codiert sind, verwendet werden.
Bei der folgenden Beschreibung der Vorrichtung in Fig. 17 werden die zwei ausrichtbaren binären Sequenzen, die in dem Muster codiert sind, als die X-Sequenz (die Positionsinformationen in der horizontalen Koordinatenrichtung Ap liefert) und die Y-Sequenz (die Positionsinformationen in der vertikalen Koordinatenrichtung Bp liefert) bezeichnet.
Die Vorrichtung in Fig. 17 umfaßt ein Muster 20 (der Form in den Fig. 12 oder 15), einen Einpixel-Erfassungskopf 16, Niederpegel-Hardware 50 zum Erzeugen von Ausgaben, die die Werte der sukzessive überquerten X- und Y-Bits anzeigen, und ein Prozessorteilsystem 51 zum Bewirken einer Hochpegel-Verarbeitung der Ausgaben der Niederpegel-Hardware 50, um der Bewegung des Sensorkopfs 16 über das Muster 20 zu folgen.
Die Niederpegel-Hardware 50 ist in der Form eines funktionellen Blockdiagramms in Fig. 18 dargestellt und umfaßt einen Optoelektronikblock 80, der wirksam ist, um eine Ausgabe zu liefern, die die Farbe anzeigt, die von dem Sensorkopf 16 erfaßt wird, einen Farbinterpretierer 311, der einen 4-Bit- Code auf einen Bus 81 ausgibt, der die X- und Y-Bitwerte und das Vorliegen von Trennungszonen anzeigt, eine Steuerzustandsmaschine 82, die den Betrieb der Niederpegel-Hardware 50 steuert, einen Zwischenspeicher 85 zum Halten der X- und Y-Bitwerte eines Farbquadrats 21, das von dem Kopf 16 erfaßt wird, einen Zonenspeicher 84 zum Speichern der Daten über die Trennungszonen 26, 27, die vorher von dem Kopf 16 überquert werden, einen Unterbrechungsgenerator 83 zum Erzeugen von Unterbrechungen, um zu bewirken, daß das Hochpegel-Prozessorteilsystem 51 der Niederpegel-Hardware 50 anzeigt, wenn es die Abwicklung der letzten Unterbrechung, die von dem Unterbrechungsgenerator 83 erzeugt wurde, beendet hat.
Der Optoelektronikblock ist detaillierter in Fig. 19 gezeigt. Sowohl die Muster in Fig. 12 als auch in Fig. 15 verwenden sechs Farben (hierin mit C1 bis C6 bezeichnet), wobei vier dieser Farben C1 bis C4 für die Farbquadrate 21 verwendet sind, die X-, Y-Wertepaare darstellen, und zwei der Farben C5, C6 für die Trennungszonen 26, 27 (Separatoren), die die Quadrate trennen. Bei diesem Ausführungsbeispiel sind die sechs verschiedenen Farben C1 bis C6, die erfaßt werden sollen, in dem Muster 20 aus drei verschiedenen monochromatischen Farben der Wellenlängen x&sub1;, x&sub2; bzw. x&sub3; zusammengesetzt (es ist offensichtlich, daß diese Wellenlängen sich allgemein im sichtbaren oder in der Nähe des sichtbaren Spektrums befinden, einschließlich Infrarot). Insbesondere entsprechen drei der Musterfarben jeweils den einzelnen der monochromatischen Farben, während die anderen drei Musterfarben jeweils einer monochromatischen Farbpaarung entsprechen, d.h. (x&sub1;, x&sub2;), (x&sub1;, x&sub3;) und (x&sub2;, x&sub3;). Wenn ein Musterelement in einer speziellen Farbe dargestellt ist, dann ist dieses Element wirksam, um Licht, das auf dieses Element einfällt, welches eine Wellenlänge hat, die der oder jeder monochromatischen Komponentenfarbe der betroffenen Musterfarbe entspricht, zu reflektieren. Um die Farbe eines Musterelements zu bestimmen, ist es daher nur erforderlich, das Element mit allen drei monochromatischen Farben zu beleuchten und die reflektierte Strahlung zu analysieren, um zu bestimmen, welche monochromatische Farbe oder welches Paar von Farben im wesentlichen von dem Musterelement reflektiert wurde.
Folglich sind in Fig. 19 drei monochromatische Lichtquellen T&sub1;, T&sub2; und T&sub3;, die von einer Treiberelektronik 300 mit Leistung versorgt werden, angeordnet, um optische Signale der jeweiligen Wellenlänge x&sub1;, x&sub2; und x&sub3; in jeweilige Optikfasern 301, 302 und 303 zum Zwecke der Beleuchtung des Musters 20 auszugeben. Die Fasern 301, 302 und 303 sind zusammen mit Reflexionsstrahlungsfasern 304, 305 und 306 in einem flexiblen Bündel 307 gebildet, das sich von dem stationären Optoelektronikblock 80 zu dem Fühler 11 erstreckt. Die Fasern enden angrenzend an eine Fokussierungslinse und bilden zusammen mit derselben den Erfassungskopf 16. Die Fasern können zusammengespleißt sein.
Die Fasern 304, 305 und 306 nehmen Strahlung auf, die von dem Muster reflektiert wird, und leiten diese Strahlung über jeweilige Filter F&sub1;, F&sub2; und F&sub3; zu jeweiligen Photodioden 308, in denen die gefilterte Strahlung erfaßt wird. Fig. 20 zeigt die spezifische Durchlässigkeit der Filter F&sub1;, F&sub2; und F&sub3; als eine Funktion der Wellenlänge zusammen mit der Hüllkurve der Strahlung, die von den Lichtquellen T&sub1;, T&sub2; und T&sub3; gesendet wird. Wie zu sehen ist, läßt das Filter F&sub1; Licht von der Quelle T&sub1; durch, das Filter F&sub2; läßt Licht von der Quelle T&sub2; durch und das Filter F&sub3; läßt Licht von der Quelle T&sub3; durch.
Die Photodiodensignale werden verstärkt und der Pegel in einer Signalaufbereitungsschaltung 309 erfaßt, um drei Ausgangssignale einer monochromatischen Farbe zu erzeugen, die das Vorliegen oder das Fehlen von Wellenlängenkomponenten x&sub1;, x&sub2; und x&sub3; in der reflektierten Strahlung anzeigen.
Diese Ausgangssignale werden zu einer Farbbestimmungsschaltung 310 geleitet, die dazu dient, die Farbkomponenten in die entsprechenden der sechs Farben C1 bis C6 des Musters 20 zu übersetzen und einen geeigneten der sechs Ausgänge der Schaltung 310 zu erregen; diese Ausgänge bilden die Ausgaben der Optoelektronikschaltung 80, wobei der Ausgang, der die gegenwärtig erfaßte Farbe darstellt, auf einem logischen Pegel "1" ist und die anderen Ausgänge auf einem logischen Pegel "0" sind.
Es ist offensichtlich, daß die Optoelektronik 80 auf eine Vielzahl von verschiedenen Arten bezüglich der, die bezugnehmend auf die Fig. 19 und 20 beschrieben ist, angeordnet sein kann. Folglich könnten z.B. die monochromatischen Lichtquellen T&sub1;, T&sub2; und T&sub3; gepulst werden, um größere augenblickliche Leistungspegel zu ermöglichen, die erreicht und/oder moduliert und synchron erfaßt werden sollen, um die Rauschunempfindlichkeit zu verbessern. Wiederum könnten die drei getrennten monochromatischen Quellen T&sub1;, T&sub2; und T&sub3; durch eine Breitbandlichtquelle (eine Quelle "weißen Lichts") ersetzt werden. In diesem Fall wäre es möglich, die sechs Musterfarben durch jeweilige einzelne Wellenlängen mit der Musterfarbe darzustellen, die dann direkt mittels einer Anordnung von sechs Filtern und Photodetektoren erfaßt werden (es müßte dann selbstverständlich Sorge getragen werden, eine ausreichende Unterscheidung zwischen benachbarten Farben sicherzustellen). Außerdem könnten die Lichtquellen und die Detektoren alle in den Fühler 11 gehäust sein, wobei eine geeignete drahtlose Verbindung (z.B. eine Funkverbindung) vorgesehen wäre, um die Erfassungssignale zu dem Rest der Niederpegel-Hardware 50 zu leiten.
Zurückkehrend nun zu einer Betrachtung der Fig. 18 werden die sechs Farbausgaben der Optoelektronik zu dem Farbinterpretierer 311 geleitet, in dem ein 4-Bit-Code auf einer Leitung erzeugt wird. Jedes Bit B0 bis B3 der 4-Bit-Code-Ausgabe auf die Leitung 81 besitzt eine spezielle Bedeutung. Spezieller:
B0 - zeigt an, ob sich der Kopf 16 über einem Farbquadrat 21 (wobei in diesem Fall B0 = '0') oder einer Trennzone 26, 27 (wobei in diesem Fall B0 = '1') befindet;
B1 - zeigt die Identität der Trennzone, die von dem Kopf 16 erfaßt wird, an, wobei es einen Wert '0' besitzt, wenn eine Zone 26 (überquert durch die Bewegung entlang der X-Sequenz) angetroffen wird, und einen Wert '1', wenn eine Zone 27 (überquert durch eine Bewegung entlang der Y-Sequenz) angetroffen wird - es ist offensichtlich, daß der Wert von B1 nur gültig ist, wenn B0 = '1';
B2 - zeigt den X-Sequenz-Bitwert '0' oder '1' an, der von einem Farbquadrat 21 dargestellt wird, oder dem Übergang zu dem Quadrat, der vom Kopf 16 erfaßt wird -wobei der Wert von B2 nur gültig ist, wenn B0 = '0'; und
B3 - zeigt den Y-Sequenz-Bitwert ('0' oder '1') an, der von einem Farbquadrat dargestellt wird, oder dem Übergang zu dem Quadrat, der von dem Kopf 16 erfaßt wird - wobei der Wert von B3 nur gültig ist, wenn B0 = '0'.
Die Art des Farbinterpretierers 311 hängt davon ab, ob das Muster 20 die Form dessen in Fig. 12 oder Fig. 15 aufweist. Wenn das Muster die Form dessen in Fig. 12 aufweist, in der die Farben C1 bis C4 jeweils direkt ein X-Bit und ein Y-Bit codieren, kann der Farbinterpretierer die Form einer einfachen Decodiermatrix annehmen, die jede Farbe C1 bis C6 in einen entsprechenden Satz von Werten für die Bits B0 bis B3 in Übereinstimmung mit der Tabelle 87, die in Fig. 21 gezeigt ist, übersetzt. Wenn das Muster die Form dessen in Fig. 15 besitzt, bei der die Farben C1 bis C4 verwendet sind, um eine Übergangscodierung der X- und Y-Sequenz-Elementewerte zu implementieren, ist eine geeignete Form des Farbinterpretierers 311 wie die, die in Fig. 22 gezeigt ist.
Bei der Form des Farbinterpretierers 311 in Fig. 22 sind die Trennzonenfarben C5 bis C6 verwendet, um die Ausgangsbits B0 und B1 zu erzeugen. Spezieller werden die Farbsignalleitungen für die Farben C5 und C6 beide zu einem OR-Gatter 320 geführt, dessen Ausgabe ein Bit B0 liefert (eine logische "1", wann immer der Erfassungskopf über einer Trennzone ist, und andernfalls "0"). Das Signal der Farbsignalleitung für die Farbe C6 liefert direkt das Bit B1. Bezüglich der Farbquadratfarben C1 bis C4 werden 'alte' und 'neue' Anzeigen der Farbe, die von dem Erfassungskopf 16 erfaßt wird, bevor und nachdem derselbe eine Trennzone (oder Zonen) überquert, in jeweiligen Speichern 322 und 321 gehalten. Beide Speicher werden von einem Übergang von "1" auf "0" des Bits B0 derart getaktet, daß, wenn sich der Erfassungskopf in eine Position über einem neuen Farbquadrat bewegt, die Farbe des Quadrats im Speicher 321 gespeichert wird, während die Farbe, die vorher in dem Speicher gehalten wurde, zum Speicher 322 übertragen wird. Die Farben, die in den Speichern 321 und 322 gehalten sind, werden dann verwendet, um eine Decodiermatrix 323 zu treiben, um die Bits B2 und B3 zu liefern. Die Decodiermatrix 323 implementiert den "Diagonal"-Abschnitt der Decodiertabelle von Fig. 15C. Obwohl selbstverständlich nicht alle Übergänge, die von dem Erfassungskopf 16 durchgeführt werden, diagonale Übergänge sind, ist es möglich, nur den "Diagonal"-Abschnitt der Decodiertabelle zu verwenden, da die X-Bit- und Y-Bit-Informationen, die in diesem Abschnitt enthalten sind, mit den "Horizontal"- und "Vertikal"-Abschnitten vereinbar sind, und die Auswahl, ob das X-Bit, das Y-Bit oder beide zu verwenden sind, nachfolgend durch Bezugnahme auf die Bits B0 und B1 getroffen werden kann.
Die Zonen-bezogenen Bits B0, B1 der Codeausgabe durch den Farbinterpretierer 311 werden über den Bus 81 zu der Zonenspeichereinheit 84 geführt. Diese Einheit 84 ist mit zwei 2-Bit-Speicher-Zwischenspeichern 91 und 92 (in Fig. 18 mit 'LZ' bzw. 'PZ' bezeichnet) versehen, die beide auf eine Art und Weise, die hierin nachfolgend beschrieben wird, auf '00' rückgesetzt werden, wobei sie jeder sukzessiven durch eine Unterbrechung initiierten Übertragung eines X- und/oder Y-Bitwerts zu dem Teilsystem 51 folgen. Nach jedem Rücksetzen, wenn der Erfassungskopf 167 über das Muster 20 bewegt wird und eine oder mehrere Zonen 26, 27 antrifft, wird der LZ-Zwischenspeicher 91 verwendet, um die Identität der letzten Zone (daher 'LZ'-Zwischenspeicher) zu speichern, die von dem Erfassungskopf 16 überquert wurde, und der PZ-Zwischenspeicher 92 ist verwendet, um die Identität der vorletzten Zone, die von dem Kopf 16 überquert wurde, zu speichern (d.h. die zweitletzte Zone und daher 'PZ'-Zwischenspeicher; PZ = Penultimate Zone). Zu diesem Zweck ist die Einheit 84 ferner mit einem Zonenkomparator 89 und einer Zwischenspeicher-Steuereinheit 90 versehen. Der Zonenkomparator 89 ist aktiviert, wenn B0 = '1' (d.h. wenn der Kopf 16 über einer Zone 26, 27 ist), wobei er in diesem Zustand wirksam ist, um den gegenwärtigen Wert des Bitpaars B0 und B1, das auf dem Bus 81 vorliegt, mit dem Wert, der in dem LZ-Zwischenspeicher 91 gespeichert ist, zu vergleichen. Wenn diese Werte gleich sind, bleibt der Ausgang des Komparators tief (was ebenfalls sein Zustand ist, wenn der Komparator nicht aktiviert ist); wenn sich die verglichenen Werte unterscheiden, wird der Ausgang des Komparators hoch, wobei dieser Übergang bewirkt, daß die Zwischenspeichersteuereinheit 90 zuerst den Inhalt des LZ-Zwischenspeichers 91 in den PZ-Zwischenspeicher 92 taktet und danach die gegenwärtigen Werte der Bits B0, B1 in den LZ-Zwischenspeicher 91 taktet.
Das Verhalten der Zonenspeichereinheit 84, das dem Rücksetzen der Zwischenspeicher 91 und 92 folgt, ist daher wie folgt. Anfänglich sind sowohl der LZ- als auch der PZ-Zwischenspeicher 91 und 92 auf '00' gehalten. Diese Situation bleibt unverändert, bis der Erfassungskopf 16 eine Trennzone 26, 27 überquert. An diesem Punkt wird der Komparator 89 aktiviert und, da der Wert des Bitpaares B0, B1 sich unvermeidlich vom Inhalt des LZ-Zwischenspeichers 91 unterscheidet, wird die Zwischenspeicher-Steuereinheit 90 ausgelöst, wodurch bewirkt wird, daß die gegenwärtigen Werte von B0, B1 in dem Zwischenspeicher 91 gespeichert werden. Der Inhalt der LZ- und PZ-Zwischenspeicher bleibt danach unverändert, außer und bis die Zwischenspeicher 91, 92 rückgesetzt werden oder der Erfassungskopf 16 eine Zone überquert, die eine Identität besitzt (wie durch das Bit B1 angezeigt wird), die sich von der Zone unterscheidet, bezüglich der die Bits B0 und B1 vorher in dem LZ-Zwischenspeicher 91 gespeichert wurden. In diesem letzteren Fall löst der Zonenkomparator 89 die Zwischenspeicher-Steuereinheit aus, um den Inhalt des LZ-Zwischenspeichers 91 in dem PZ-Zwischenspeicher 92 zu speichern und die neuen gegenwärtigen Werte von B0 und B1 in dem LZ-Zwischenspeicher 91 zu speichern.
Es ist offensichtlich, daß die Zonenspeichereinheit 84 das zweite Auftreten einer Trennzone mit der gleichen Identität wie eine vorher gespeicherte Zone nicht registriert. Der Grund dafür liegt darin, daß ein zweites derartiges Auftreten in der Praxis tatsächlich nicht auftreten sollte, bevor die Zwischenspeicher 91, 92 rückgesetzt werden, so daß irgendein scheinbares zweites Auftreten im allgemeinen ignoriert werden kann.
Der Wert des Bitpaares B0, B1, der in dem LZ-Zwischenspeicher 91 gespeichert ist, wird als Signal LZ ausgegeben und genauso wird der Wert des Bitpaares B0, B1, das in dem PZ- Zwischenspeicher 92 gespeichert ist, als Signal PZ ausgegeben.
Die Steuerzustandsmaschine 82 besitzt vier Zustände (Leerlauf, Zwischenspeichern, I-Aktivieren, Rücksetzen), die auf eine Art und Weise in Wechselbeziehung stehen, die mittels des Zustandsübergangsdiagramms, das in dem Block gezeigt ist, der die Zustandsmaschine 82 in Fig. 18 darstellt. Die Bedingungen zwischen Übergängen zwischen den Zuständen sind durch Bögen angezeigt, die die Zustände verbinden. Diese Bedingungen und die Aktionen, die zu jedem Zustand gehören, werden nachfolgend beschrieben.
Leerlaufzustand - wird aus dem Rücksetzen-Zustand betreten, einen Taktimpuls nachdem der letztgenannte betreten wurde (wie durch eine '1' auf dem Bogen, der die Leerlauf- und Rücksetzen- Zustände verbindet, angezeigt ist). Zu diesem Zustand gehört keine Aktion.
Zwischenspeichern-Zustand - wird aus dem Leerlauf-Zustand betreten, wenn B0 = '0' (d.h. der Erfassungskopf 16 über einem Farbquadrat 21 ist) und zur gleichen Zeit der Inhalt des LZ-Zwischenspeichers ein anderer als '00' ist. Beim Betreten dieses Zustandes wird ein Signal 'LATCH' (Latch = Zwischenspeichern) von der Zustandsmaschine ausgegeben, um die Werte der Bits B2 und B3 in dem 2-Zellen- Zwischenspeicher 85 zwischenzuspeichern (wobei das Bit B2 der X-Bitwert und das Bit B3 der Y-Bitwert ist); das Zwischenspeichern tritt tatsächlich nach einer kurzen Verzögerung auf, die ausreicht, um sicherzustellen, daß B2 und B3 stabil sind.
I-Aktivierungszustand - wird aus dem Zwischenspeichern-Zustand betreten, einen Taktimpuls nachdem derselbe betreten wurde. Beim Eintritt in diesen Zustand wird ein Signal 'INT ENABLE' (INT ENABLE = Unterbrechung aktivieren) von der Zustandsmaschine ausgegeben, um den Unterbrechungsgenerator 83 zu aktivieren, um eine Übertragung von einem oder beiden Bitwerten, die in dem Zwischenspeicher 85 gespeichert sind, zu dem Prozessorteilsystem 51 zu initiieren.
Rücksetzen-Zustand - wird aus dem I-Aktivieren-Zustand betreten, wenn der Wert FLAG des Flag-Registers 86 gleich '1' ist (d.h. nach dem Abschluß der Bitwert-Übertragung zu dem Prozessorteilsystem 51). Beim Eintritt in diesen Zustand wird ein Signal 'RESET' (RESET = Rücksetzen) von der Zustandsmaschine ausgegeben, um die LZ- und PZ-Zwischenspeicher 91, 92 den X-Y-Zwischenspeicher 85 und das Flag-Register 86 für einen neuen Betriebszyklus bereit zu machen.
Die Zustandsmaschine 82 bewirkt folglich einen Betriebszyklus aus dem Leerlauf-Zustand, über ihre Zwischenspeichern, I-Aktivieren- und Rücksetzen-Zustände und zurück zu ihrem Leerlauf-Zustand, wann immer der Erfassungskopf 16 ein Farbquadrat 21 antrifft, nachdem er eine Trennzone 26, 27 überquert hat, nachfolgend zu dem letzten Rücksetzen des LZ-Zwischenspeichers, d.h. nachfolgend zu dem letzten Betriebszyklus der Zustandsmaschine. Während der Ausführung eines Betriebszyklusses bewirkt die Zustandsmaschine 82 die Übertragung eines X- und/oder Y-Sequenz-Bitwerts zu dem Prozessorteilsystem 51 und initialisiert dann die Niederpegel-Hardware, um ein neues X- und/oder Y-Bit zu erkennen.
Der Unterbrechungsgenerator 83 bestimmt, ob ein X-Bit, ein Y-Bit oder beide zu dem Prozessorteilsystem 51 übertragen werden sollen und initiiert diese Übertragung, wenn er von dem Signal INT ENABLE von der Zustandsmaschine 82 aktiviert ist, indem er eine geeignete von drei Unterbrechungen aktiviert. Der Unterbrechungsgenerator 83 ist um die Decodierlogik aufgebaut, die abhängig von den Werten der Signale LZ und PZ bestimmt, ob ein X- und/oder Y-Bit übertragen werden soll, wobei diese Bestimmung entsprechend der Wahrheitstabelle 88, die in dem Block gezeigt ist, der den Unterbrechungsgenerator 83 in Fig. 18 darstellt, getroffen wird. In dieser Wahrheitstabelle wurden die Werte von LZ und PZ als geordnete Paare von binären Werten gezeigt, wobei der erste Wert dem gespeicherten Wert von B0 und der zweite dem gespeicherten Wert von B1 entspricht. Da die Signale LZ und PZ nicht den Wert '01' annehmen können, wurden die Einträge in der Tabelle 88, die diesem Wert entsprechen, durchgestrichen. Außerdem sind Einträge, die LZ = '00' entsprechen, als 'N.A' ('keine Aktion' = no action) angegeben, da unter den Umständen keine Bitübertragung stattfinden kann, in denen der Unterbrechungsgenerator nicht mittels der Zustandsmaschine 82 aktiviert werden kann, um eine Unterbrechung zu erzeugen, wobei die Letztgenannte in ihrem Leerlauf-Zustand gehalten wird, bis sich LZ von '00' ändert. Wenn jedoch PZ = '00' und LZ gleich '10' ist, sollte der X-Bitwert (jedoch nicht der Y-Bitwert), der im Zwischenspeicher 85 gehalten ist, übertragen werden; dies ist der Fall, da die LZ- und PZ-Signale zeigen, daß die einzige Trennzone, die seit der letzten Übertragung überquert wurde, eine solche ist, die anzeigt, daß der Kopf 16 entlang der X-Sequenz bewegt wurde, wodurch ein neuer X-Bitwert (jedoch kein neuer Y-Bitwert) verfügbar ist. Genauso sollte, wenn PZ = '00' und LZ gleich '11' ist, der Y-Bitwert (jedoch nicht der X-Bitwert), der im Zwischenspeicher 85 gehalten ist, übertragen werden (die LZund PZ-Signale zeigen, daß nur eine Zone, die eine Überquerung der Y-Sequenz anzeigt, seit der letzten Übertragung angetroffen wurde). Wenn das Bit B0 sowohl von LZ als auch von PZ gleich '1' ist (wodurch impliziert wird, daß Zonen, die eine Bewegung entlang sowohl der X- als auch der Y-Sequenz anzeigen, seit der letzten Übertragung angetroffen wurden), sollten sowohl das X- als auch das Y-Bit im Zwischenspeicher 85 übertragen werden.
Wenn der Unterbrechungsgenerator 83 durch das Signal 'INT ENABLE' von der Zustandsmaschine 82 aktiviert wird, aktiviert der Generator 83 eine von drei Unterbrechungen, wie durch die Wahrheitstabelle 88 angezeigt ist. Wenn nur der X-Bitwert von dem Zwischenspeicher 85 übertragen werden soll, wird folglich eine Unterbrechung 'nimm X' aktiviert. Wenn nur der Y-Bitwert von dem Zwischenspeicher 85 übertragen werden soll, wird eine Unterbrechung 'nimm Y' aktiviert. Wenn sowohl der X- als auch der Y-Wert übertragen werden sollen, wird eine Unterbrechung 'nimm beide' aktiviert.
Nun werden zwei Beispiele des Gesamtverhaltens der Niederpegel-Hardware 50 für das Muster in Fig. 12 gegeben, bezugnehmend auf die zwei Erfassungskopf-Bewegungsspuren A und B, die in dieser Figur gezeigt sind.
Es sei zuerst eine Bewegung des Kopfs 16 entlang der Spur A von einem anfänglichen Quadrat 21A betrachtet, welches eine Farbe besitzt, die die X- und Y-Sequenz-Bitwerte von '1' bzw. '0' darstellt (siehe C3 in Tabelle 87 von Fig. 21). Es ist zu sehen, daß die Spur A parallel zu der Ap-Achse ist, d.h. nur entlang der X-Sequenz. Es sei angenommen, daß die Steuerzustandsmaschine 84 gerade einen Betriebszyklus abgeschlossen hat, so daß die Zwischenspeicher 91, 92 und 85 und das Flag-Register 86 alle in einem rückgesetzten Zustand sind, so daß die Ausgabe des Codewerts '0010' auf den Bus 81 von dem Farbinterpretierer 311 keine Aktion bewirkt, wobei die Zustandsmaschine 82 in ihrem Leerlauf-Zustand ist, wobei sie LZ benötigt, um sich von '00' zu ändern, und der Zonenspeicher deaktiviert ist, wobei er auf die Überquerung einer Trennzone wartet. Wenn sich der Erfassungskopf entlang der Spur A bewegt, trifft er auf eine X-Sequenz-Trennzone 26A (Farbe C5), wodurch bewirkt wird, daß der Farbinterpretierer 311 einen Codewert '1000' ausgibt. Folglich wird der Zonenspeicher 84 aktiviert und die Bits B0 und B1 des Codes ('10') werden in dem LZ-Zwischenspeicher 91 zwischengespeichert (der PZ-Zwischenspeicher hält weiterhin '00'); die Zustandsmaschine 82 bleibt in ihrem Leerlauf-Zustand. Der Erfassungskopf 16 trifft als nächstes das Farbquadrat 21B, das eine Farbe (Farbe C1) aufweist, die die X- und Y-Sequenz-Bitwerte von '0' bzw. '0' aufweist. Folglich gibt der Farbinterpretierer 311 einen Codewert '0000' auf den Bus 81 aus. Da LZ nun '10' ist, wenn der Codewert '0000' auf dem Bus 81 plaziert ist, wird bewirkt, daß die Zustandsmaschine 82 von ihrem Leerlauf-Zustand zuerst in ihren Zwischenspeichern-Zustand übergeht, um die X- und Y-Bitwerte ('0' und '0') in dem X/Y-Zwischenspeicher 85 zwischenzuspeichern, und dann in ihren I-Aktivieren-Zustand, indem sie den Unterbrechungsgenerator 83 aktiviert. Da LZ und PZ die Werte '10' bzw. '00' aufweisen, aktiviert der Unterbrechungsgenerator 83 die 'nimm-X'-Unterbrechung, um dem Prozessorteilsystem mitzuteilen, daß ein neuer X-Bitwert verfügbar ist und geholt werden sollte. Nachdem das Teilsystem 51 den X-Bitwert von dem Zwischenspeicher 85 geholt hat, setzt es FLAG = '1', wodurch bewirkt wird, daß die Zustandsmaschine 82 in ihren Rücksetzen-Zustand übergeht, wodurch die Elemente 85, 86, 91 und 92 rückgesetzt werden, und dann in ihren Leerlauf-Zustand.
Es sei als nächstes eine Bewegung des Kopfs 16 entlang der Spur B von dem Quadrat 21A betrachtet, wobei die Elemente 85, 86, 91 und 92 gerade durch die Zustandsmaschine 82 auf dem Weg derselben beim Zurückkehren in ihren Leerlauf-Zustand zurückgesetzt wurden. Der Betrieb der Niederpegel- Hardware setzt sich fort, wie oben beschrieben, wenn der Erfassungskopf aus dem Quadrat 21A und über die X-Sequenz- Trennzone 26A bewegt wird; folglich wird der Wert '10' in dem LZ-Zwischenspeicher 91 gespeichert, während der PZ-Zwischenspeicher 92 auf '00' bleibt und die Zustandsmaschine in ihrem Leerlauf-Zustand bleibt. Als nächstes trifft der Erfassungskopf 16 jedoch eine Y-Sequenz-Trennzone 27A (Farbe C6) anstelle des Antreffens eines neuen Farbquadrats (das eine Übertragungsoperation, wie die oben beschriebene, auslösen würde), wenn sich derselbe entlang der Spur B bewegt. Dies bewirkt, daß der Farbinterpretierer einen Codewert '1100' auf den Bus 81 ausgibt, was wiederum bewirkt, daß der Zonenspeicher den Inhalt ('10') des LZ-Zwischenspeichers 91 zu dem PZ-Zwischenspeicher 92 überträgt und die Werte von B0 und B1 auf dem Bus 81 ('11') in dem LZ-Zwischenspeicher 91 speichert. Zur gegebenen Zeit wird der Erfassungskopf 16 entlang der Spur B zu dem Farbquadrat 21C bewegt, welches eine Farbe (Farbe C2) besitzt, die die X- und Y-Sequenz-Bitwerte von '0' bzw. '1' darstellt. Der Farbinterpretierer 311 gibt einen Code '0001' auf den Bus 81 aus, was die Steuerzustandsmaschine aus ihrem Leerlauf-Zustand aus löst und zur Folge hat, daß der Unterbrechungsgenerator aktiviert wird und die 'nimm beide'-Unterbrechung aktiviert, um dem Prozessorteilsystem anzuzeigen, daß sowohl ein neuer X- als auch ein neuer Y-Bitwert verfügbar sind. Wenn das Prozessorteilsystem die Übertragung der X- und Y-Bitwerte abschließt, wird die Niederpegel-Hardware rückgesetzt und ihr Betriebszyklus neu initiiert.
Der Betrieb der Niederpegel-Hardware, wenn sie Spuren ähnlich den Spuren A und B über ein Muster der in Fig. 15 dargestellten Form folgt, ist im wesentlichen der gleiche, wie der oben beschriebene, selbstverständlich mit Ausnahme des Betriebs des Farbinterpretierers 311.
Die Fähigkeit der Hardware 50 in Fig. 18, Spuren zu bewältigen, die zwei getrennte Zonen 26, 27 aufeinanderfolgend ohne ein dazwischenliegendes Farbquadrat 21 kreuzen, ermöglicht es, daß die Hardware 50 die meisten Spuren über das Muster behandelt, besonders da die Größe der Farbquadrate, die in dem Muster in Fig. 12 gezeigt sind, im allgemeinen relativ bezüglich derer der Zonen 26, 27 erhöht werden kann. Wenn der Erfassungskopf 16 jedoch entlang einer anormalen Spur bewegt wird, für die die Niederpegel-Hardware nicht entworfen ist, müßte die Vorrichtung im schlimmsten Fall als Ganzes einfach die Standorterfassung neu initiieren, was an sich kein schwerwiegender Nachteil ist.
Die Niederpegel-Hardware 50 ist ferner wirksam, um ein Abhebe-Unterbrechungssignal zu erzeugen, wenn sie erfaßt, daß der Erfassungskopf 16 von dem Muster 20 entfernt wurde; diese Funktionalität wurde aus Gründen der Klarheit nicht in Fig. 18 dargestellt.
Der Schaltungsaufbau zum Implementieren der Niederpegel-Hardware ist für Fachleute offensichtlich und wird daher hierin nicht detaillierter beschrieben.
Es sei sich nun einer Betrachtung des Hochpegel-Prozessorteilsystems 51 zugewandt, wobei dieses Teilsystem wirksam ist, um mehrere Prozesse gleichzeitig durchzuführen, wobei diese aus einem Prozeß 60 (der XBIT-Prozeß), um eine Positionsbestimmung in der Richtung der X-Koordinate auf der Basis der X-Bitwerte, die von der Niederpegel-Hardware 50 geliefert werden, zu bewirken, einem Prozeß 61 (der YBIT- Prozeß), um eine Positionsbestimmung in der Richtung der Y-Koordinate auf der Basis der Y-Bitwerte, die von der Hardware 50 geliefert werden, zu bewirken, und einem Ausgabeprozeß 62, um auf der Basis der X- und Y-Positionen, die mittels der Prozesse 60 und 61 bestimmt werden, Absolutpositionsinformationen auszugeben, bestehen. Der Ausgabeprozeß 62 ist schnittstellenmäßig über einen Ausgabepuffer 63 in der Form von zwei FIFOS 76, 77 (FIFO = first-in first-out) mit den X-Bit- und Y-Bit-Prozessen 60 und 61 verbunden, wobei der Puffer wirksam ist, um eine Reihe von absoluten Xbzw. Y-Positionen zu speichern. Jeder Eintrag in die FIFOS 76, 77 umfaßt eine neue X- oder Y-Position, wie es geeignet ist, eine Sequenznummer, die die Reihenfolge der Erzeugung der X- und Y-Einträge anzeigt, und ein dazugehöriges Flag- Bit (die X-Y-Flag). Jeder Eintrag besitzt eine zweite dazugehörige Flag (die Aufschub-Flag), die, wenn sie gesetzt ist, anzeigt, daß der Eintrag nur vorläufig ist und noch nicht ausgegeben werden muß. Der Zweck der Aufschub-Flag wird hierin nachfolgend ausführlicher erklärt.
Es ist offensichtlich, daß die Funktionalität, die durch das Teilsystem 51 geschaffen wird, einen Teil der Funktionalität der Teilmuster-Bildverarbeitungseinheit 12 von Fig. 1 ebenso wie die gesamte Funktionalität der Positionsbestimmungseinheit 13 einschließt. Das Teilsystem 51 kann unter Verwendung eines geeigneten Mehrprogrammbetrieb-Prozessorsystems implementiert sein, wie für Fachleute offensichtlich ist.
Es sei der Betrieb des Prozessorteilsystems 51 detaillierter betrachtet. Das Teilsystem 51 steht mit der Niederpegel- Hardware 50 über einen X-Y-Bit-Eingabepuffer 64 in der Form eines FIFO-Puffers schnittstellenmäßig in Verbindung. Wenn die 'nimm X'-Unterbrechung von der Hardware 50 aktiviert wird, um die Verfügbarkeit eines neuen X-Sequenz-Bitwerts anzuzeigen, führt das Teilsystem 51 eine Unterbrechungsdienstroutine ISR-1 (ISR = Interrupt Service Routine) durch, die den X-Bitwert im Zwischenspeicher 85 zusammen mit einer Anzeige, daß derselbe ein X-Bitwert ist, in den Puffer 64 lädt. Genauso führt, wenn die 'nimm-Y'-Unterbrechung aktiviert wird, um die Verfügbarkeit eines neuen Y-Sequenz-Bitwerts anzuzeigen, das Teilsystem 51 eine Unterbrechungsdienstroutine ISR-2 durch, die den Y-Bitwert in dem Zwischenspeicher 85 zusammen mit einer Anzeige, daß derselbe ein Y-Bitwert ist, in den Puffer 64. Wenn die 'nimm beide'- Unterbrechung von der Hardware 50 aktiviert wird, führt das Teilsystem 51 eine Unterbrechungsdienstroutine ISR-3 durch, die die X- und Y-Bitwerte in dem Speicher 85 in dieser Reihenfolge zusammen mit jeweiligen Anzeigen der Sequenz, zu der jeder gehört, in den Puffer 64.
Der Puffer 64 bildet somit eine Eingabewarteschlange der Xund Y-Bitwerte und die X-Bit- und Y-Bit-Prozesse 60 und 61 nehmen Bits von dem Kopf dieser Warteschlange zur Verarbeitung, wobei X-Bitwerte nur mittels des X-Bit-Prozesses 60 genommen werden und Y-Bitwerte nur mittels des Y-Bit-Prozesses 61 genommen werden.
Schließlich bewirkt bezüglich der Wechselwirkung der Niederpegel-Hardware 50 mit dem Teilsystem 51 die Abhebe-Unterbrechung, die von der Niederpegel-Hardware 50 erzeugt wird, daß das Teilsystem 51 eine Unterbrechungsdienstroutine ISR-4 durchführt, die alle drei Hauptprozesse 60, 61, 62 rücksetzt und die Puffer 63 und 64 löscht.
Der X-Bit-Prozeß 60 wird als nächstes beschrieben, wobei offensichtlich ist, daß der Y-Bit-Prozeß 61 im wesentlichen der gleiche ist, mit der Ausnahme, daß derselbe mit Y-Sequenz-Bits arbeitet und nicht mit X-Sequenz-Bits.
Der X-Bit-Prozeß benutzt vier Hauptdatenstrukturen, wobei dieselben sind:
- ein X-Sequenz-Register 66, welches das X-Sequenz-Bitmuster speichert;
- ein X-Sequenz-Fensterindex 67, der für jede mögliche Fensterlängensequenz (N Bits lang) in der X-Sequenz (wenn beide Leserichtungen genommen werden) vorliegt, einen Zeiger in der X-Sequenz liefert, der die Position des letzten Bits der Fensterlängensequenz anzeigt (hinsichtlich eines Versatzes von dem Beginn der X-Sequenz), zusammen mit einer Richtungs-Flag, die die Leserichtung der X-Sequenz anzeigt;
- eine X-Zeiger-Liste 68, um einen oder mehrere X-Positionszeiger (und ihre dazugehörigen Richtungs-Flags) anzuzeigen, um die gegenwärtige tatsächliche X-Position (während des normalen Betriebs) oder gegenwärtige Kandidaten-X-Positionen (während eines Umkehrerholungsbetriebs, der nachfolgend beschrieben wird);
- ein Anfangs-X-Positions-Schieberegister 69 der Länge N, das verwendet ist, um während einer anfänglichen Absolutpositionsbestimmungs-Betriebsphase der Vorrichtung eine Fensterlängensequenz von N Bits aus den erfaßten X-Sequenz-Bits aufzubauen.
Der YBIT-Prozeß verwendet entsprechende Datenstrukturen, nämlich ein Y-Sequenz-Register 70, einen Y-Sequenz-Fensterindex 71, eine Y-Zeigerliste 72 und ein Anfangs-Y-Positionsregister 73.
Fig. 23 zeigt den XBIT-Prozeß 60 in der Form eines Flußdiagramms. Der XBIT-Prozeß steuert die Positionsnachführung in der Richtung der X-Koordinate, wobei die tatsächliche Nachführung durch geeignete Teilroutinen bewirkt wird. Es gibt drei elementare Nachführmodi, wobei diese sind:
- ein "absoluter" Nachführungsmodus, bei dem eine absolute Positionsbestimmung durch das Aufbauen einer Fensterlängensequenz von X-Bits in einem Register bewirkt wird, und dann der Fensterindex 67 verwendet wird, um eine absolute Position zu identifizieren, wobei dieser Nachführungsmodus anfänglich verwendet wird, um eine anfängliche absolute Position festzustellen;
- ein "inkrementaler" Nachführungsmodus, bei dem angenommen wird, daß jedes neue X-Bit, das empfangen wird, die gegenwärtige X-Position in die Richtung, die durch die Richtungs-Flag, die zu dem gegenwärtigen Positionszeiger gehört, angezeigt ist, inkrementiert, wobei dieser Modus verwendet wird, sobald eine anfängliche absolute Position festgesetzt wurde und bis das tatsächliche nächste X-Bit, das erfaßt wird, nicht mit dem nächsten X-Sequenz-Bit in der Richtung, die durch die Richtungs-Flag angezeigt ist (im allgemeinen tritt eine derartige Nichtübereinstimmung aufgrund einer Richtungs- oder Bewegungs-Umkehr auf), übereinstimmt; und
- ein "Umkehrerholungs"-Nachführungsmodus, bei dem ein Versuch unternommen wird, eine Erholung von einer Nichtübereinstimmung durchzuführen, die im inkrementalen Nachführungsmodus auftritt, indem angenommen wird, daß eine Bewegungsrichtungsumkehr aufgetreten ist und dann versucht wird, zu identifizieren, an welcher Position die Umkehr stattfand.
Die Nachführung in den "absoluten", "inkrementalen" und "Umkehrerholungs"-Nachführungsmodi wird durch jeweilige Routinen 100, 101, 102 bewirkt, wobei eine weitere Routine 103 ("RR-Anlaufen"; RR = Reversal Recovery = Umkehrerholung) als eine Initialisierungroutine zu der Umkehrerholungs-Routine 102 gehört. Eine globale Variable TMODE dient dazu, den gegenwärtig wirksamen Nachführungsmodus zu identifizieren, wobei dieser Variable einer der Werte 'A', 'I', 'R' zugewiesen ist, um jeweils den "absoluten", "inkrementalen" oder "Umkehrerholungs"-Nachführungsmodus anzuzeigen. Eine weitere globale Variable RESULT (RESULT = Ergebnis) ist verwendet, um anzuzeigen, ob die Nachführungsroutinen bei ihren Aufgaben erfolgreich waren, wobei diese Variable mögliche Werte 'S', um einen Erfolg anzuzeigen, 'D', um anzuzeigen, daß die Beurteilung verschoben werden muß, und 'L', um anzuzeigen, daß die Routine unerholbar die Spur der gegenwärtigen Position verloren hat, aufweist. Ferner sind bei dem Betrieb des XBIT-Verfahrens und seiner Teilroutinen drei Zahlen Cn1, Cn2 und Cn3 verwendet, wie nachfolgend deutlich wird.
Es sei als nächstes das Flußdiagramm in Fig. 23 detaillierter betrachtet, wobei nach dem Anlaufen des XBIT-Verfahrens ein Initialisierungsschritt 105 bewirkt wird. Während des Schritts 105 wird die X-Zeigerliste 68 auf einen leeren Zustand rückgesetzt, das Anfangs-X-Positionsregister 64 wird auf Null zurückgesetzt und die Ausgabe-FIFOs 76, 77 werden geräumt. Zusätzlich wird der Variable TMODE der Wert "A" zugewiesen, um das Nachführungsverfahren in dem absoluten Nachführungsmodus zu beginnen, der Variable RESULT wird der Wert "L" zugewiesen, um anzuzeigen, daß die Nachführung aus einem vollständig verlorenen Zustand begonnen werden soll, und den Zahlen Cn1, Cn2 und Cn3 wird der Wert '0' zugewiesen.
Danach führt das XBIT-Verfahren 60 den Schritt 106 durch, bei dem der oberste Eintrag in dem X/Y-Bitpuffer 64 untersucht wird und bei dem, wenn derselbe ein X-Bitwert ist, der Wert aus dem Puffer 64 entfernt wird und in der Variable NEW-X gespeichert wird. Andernfalls, wenn der oberste Eintrag in dem Puffer 64 kein X-Bitwert ist, wird der Schritt 106 in Intervallen wiederholt, bis ein X-Wert am Kopf des Puffers 64 auftritt (diese Re-Iteration findet intern im Schritt 106 statt).
Das XBIT-Verfahren 60 fährt nun fort, die richtige Nachführungsroutine auszuwählen und auszuführen, wobei diese Auswahl im Entscheidungsschritt 107 abhängig von dem gegenwärtigen Wert der Variable TMODE bewirkt wird. Unmittelbar nach dem Anlaufen des XBIT-Verfahrens 60 wird die absolute Nachführungsroutine 100 ausgewählt und durchgeführt, da TMODE während des Schrittes 105 selbstverständlich der Wert "A" zugewiesen wurde. Es ist jedoch später zu sehen, daß sich die Werte, die in TMODE gespeichert sind, auf "I" oder "R" ändern können, wenn die Nachführung fortfährt, wobei in diesem Fall der Entscheidungsschritt 107 die inkrementale Nachführungsroutine 101 bzw. die Umkehrerholungsroutine 102 auswählen wird.
Unabhängig davon, welche Nachführungsroutine 100, 101 und 102 ausgeführt wird, springt das XBIT-Verfahren 60 bei der Vollendung der ausgewählten Routine zum Entscheidungsschritt 108, indem der Wert der Variable RESULT, die verwendet ist, um den Erfolg oder ein anderes Ergebnis der ausgeführten Nachführungsroutine anzuzeigen, überprüft wird. Wenn in RESULT wieder der Wert "L" auftritt, wird dies als eine Anzeige dafür verwendet, daß die Positionsnachführung unerholbar fehlgeschlagen ist und erneut vom ersten Anfang an begonnen werden muß, indem zum Initialisierungsschritt 105 zurückgesprungen wird. Wenn in RESULT der Wert "S" wieder auftritt, zeigt dies an, daß die gegenwärtige X-Position mit Sicherheit bekannt ist, wobei in diesem Fall der inkrementale Nachführungsmodus implementiert werden kann (dies wird in Schritt 109 herbeigeführt, indem der Variable TMODE der Wert "I" zugewiesen wird). Wenn in RESULT der Wert "D" wieder auftritt, zeigt dies an, daß die gegenwärtige X-Position nicht mit Sicherheit bekannt ist, jedoch im Verfahren festgestellt werden soll; diese Situation kann entweder auftreten, wenn das XBIT-Verfahren in seinem absoluten Nachführungsmodus ist, und noch nicht genügend Bits akkumuliert wurden, um zu ermöglichen, daß die absolute Nachführungsroutine 60 eine absolute Bestimmung der gegenwärtigen X-Position bewirkt, oder wenn das Verfahren 60 in seinem Umkehrerholungs-Nachführungsmodus ist und die gegenwärtige X-Position nicht unzweideutig bestimmt wurde. Im allgemeinen wird der Nachführungsmodus nicht geändert, wenn "D" in RESULT wieder auftritt, so daß die Variable TMODE unverändert bleibt. Wenn jedoch die Umkehrerholung zuerst initiiert wird, wird dies mittels der inkrementalen Nachführungsroutine 101 bewirkt, die direkt die RR-Anlaufroutine 103 initiiert, ohne daß die Variable TMODE auf "R" eingestellt wird; in diesem Fall wird die Variable TMODE im Schritt 110 auf den Wert "R" eingestellt, wenn bestimmt ist, daß RESULT einen Wert D besitzt und der vorherige Wert von TMODE "I" war (Schritt 111).
Wenn entweder der Wert "S" oder "D" in RESULT wieder auftritt, springt nach einer beliebigen richtigen Wertzuweisung zu der Variable TMODE das XBIT-Verfahren zum Schritt 106 zurück, um einen neuen X-Bitwert zu holen.
Die absolute inkrementale und die Umkehrerholungs-Nachführungsroutine 100, 101 und 102 werden nun beschrieben.
Fig. 24 ist ein Flußdiagramm der absoluten Nachführungsroutine 100. Ein Betreten dieser Routine wird der neue X-Bitwert, der in NEW-X gespeichert ist, in das Anfangs-X-Positionsregister 69 eingegeben (Schritt 120), um mit weiteren X-Bitwerten akkumuliert zu werden, um ein Fensterlängenmuster für die X-Sequenz zu bilden. Die Gesamtzahl der XBIT- Werte, die gegenwärtig in dem Register 69 akkumuliert sind, sind in der Zahl Cn1 gehalten. Im Schritt 121 wird überprüft, ob die Zahl Cn1 schon den Wert N erreicht hat, welcher anzeigt, daß eine Fensterlängensequenz von X Bits im Schieberegister 69 akkumuliert wurde. Wenn die Zahl Cn1 kleiner als N ist, wird die Zahl erhöht (Schritt 122), um den neu hinzugefügten XBIT-Wert zu berücksichtigen, ein X-Positionseintrag wird in dem Ausgabe-FIFO 76 durchgeführt, wobei die dazugehörige Aufschub-Flag aus Gründen, die später deutlich werden, gesetzt wird (Schritt 123), und RESULT der Wert "D" zugewiesen wird (Schritt 124), um anzuzeigen, daß noch eine Fensterlängensequenz akkumuliert wird; danach wird die absolute Nachführungsroutine beendet.
Wenn der Test, der im Schritt 121 durchgeführt wird, aus dem Wert der Zahl Cn1 anzeigt, daß eine Fensterlängensequenz von N Bits im Register 69 akkumuliert wurde, springt die absolute Nachführungsroutine zu Schritt 125, in dem sie auf den Wert der Fensterlängensequenz, die im Register 69 im X-Fensterindex 67 gespeichert ist, blickt, mit der Absicht, die gegenwärtige absolute X-Position festzustellen. Wenn die Fensterlängensequenz erfolgreich im Index 67 gefunden wird, wird ein Zeiger an die entsprechende Position in der X-Sequenz in die X-Zeigerliste 68 eingegeben, zusammen mit einer Richtungs-Flag, die die Leserichtung der X-Sequenz anzeigt, welche die Fensterlängensequenz ergibt (Schritt 127). Ferner wird ein Positionseintrag in dem Ausgabe-FIFO 76 durchgeführt, wobei die dazugehörige Aufschub-Flag nicht gesetzt wird, wodurch angezeigt wird, daß der Eintrag bedingungslos ist. Da die gegenwärtige Position in der X-Sequenz bekannt ist, ist es möglich, die letzten (N-1) X-Einträge, die in dem Ausgabe-FIFO 76 als Aufschubeinträge markiert sind, durch tatsächliche X-Positionswerte zu ersetzen, wobei dies auch im Schritt 127 geschieht. Da alle X-Einträge, die als Aufschub markiert sind, die oberhalb der ersetzten X-Einträge in dem FIFO 76 positioniert sind, nicht nacheinander rückgewonnen werden können, müssen derartige Einträge gelöscht werden (dies wird wiederum im Schritt 127 durchgeführt). Im Schritt 128 wird RESULT der Wert "S" zugewiesen, um anzuzeigen, daß die X-Position erfolgreich gefunden wurde und der inkrementale Nachführungsmodus nun betreten werden kann.
Wenn die Fensterlängensequenz, die im Register 69 akkumuliert ist, nicht im Index 67 gefunden wird (Schritt 125 und 126), zeigt dies an, daß ein oder mehrere der akkumulierten Bits falsch sind, so daß das Akkumulationsverfahren fortgesetzt werden muß. In diesem Fall werden als nächstes die Schritte 123 und 124 ausgeführt, bevor die absolute Nachführungsroutine 100 verlassen wird. Es sei bemerkt, daß es nicht notwendig ist, die Zahl Cn1 zu erhöhen, da bereits N Bits akkumuliert wurden und eine weitere Verarbeitung auf der Basis des Verlierens des ältesten Bits, das in dem Register 69 akkumuliert ist, stattfindet, wenn jedes neue X-Bit in das Register hinzugefügt wird (wobei das Register 69 die Fensterlänge N besitzt). Zu gegebener Zeit wird das fehlerhafte Bit oder die Bits aus dem Register 69 geschoben und die Fensterlängensequenz, die in dem Register verbleibt, wird erfolgreich im Index 67 lokalisiert.
Fig. 25 ist ein Flußdiagramm der inkrementalen Nachführungsroutine 101. Diese Nachführungsroutine arbeitet auf der Basis, daß, sobald die absolute X-Position festgestellt wurde, jedes neue X-Bit einfach verwendet werden kann, um die X-Position um Eins zu erhöhen, wobei die Routine mit der Annahme arbeitet, daß die Richtung der X-Bewegung unverändert bezüglich der bleibt, die zu der anfänglichen absoluten Positionsbestimmung gehörte. Um die Gültigkeit dieser Annahme zu überprüfen, wird jedoch der Wert jedes neuen Bits, wie er von der Niederpegel-Hardware 50 zugeführt wird, mit dem Wert des nächsten X-Sequenz-Bits, wie es von der X-Sequenz, die im Register 66 bei der gegenwärtigen X-Position und der Bewegungsrichtung (wie durch den Zeiger in der Zeigerliste 68 angezeigt ist) gespeichert ist, vorhergesagt ist, verglichen. Diese Überprüfung wird mittels des Schritts 130 in dem Flußdiagramm in Fig. 25 durchgeführt. Wenn die tatsächlichen und die vorhergesagten Werte des neuen X-Sequenz-Bits übereinstimmen (Schritt 131), wird angenommen, daß die Annahme bezüglich der Bewegungsrichtung gültig ist, und der X-Positionszeiger, der in der Liste 68 gehalten ist, wird in die Bewegungsrichtung erhöht, welche mittels der dazugehörigen Richtungs-Flag angezeigt ist (Schritt 132). Danach wird die neue X-Position in dem Ausgabe-FIFO 76 gespeichert, wobei die dazugehörige Aufschub-Flag nicht gesetzt wird (Schritt 133), und der Wert "S" wird in RESULT (Schritt 134) gespeichert. Wenn jedoch der Wert der neuen X-Position, der tatsächlich erfaßt wurde, sich von dem Vorhergesagten der gespeicherten X-Sequenz unterscheidet, wird angenommen, daß eine Umkehr der X-Bewegungsrichtung stattgefunden hat, und eine Umkehrerholung wird initiiert, wobei die Umkehrerholungs-Anlaufroutine (RR-Anlaufen 103) aufgerufen wird.
Bevor die RR-Anlaufroutine 103 und die Hauptumkehrerholungsroutine 102 beschrieben wird, bezugnehmend auf die Flußdiagramme dieser Routinen, die in den Fig. 28 bzw. 29 gezeigt sind, wird zuerst eine allgemeine Beschreibung des Umkehrerholungsverfahrens gegeben.
Bezugnehmend auf das Muster in Fig. 12 zeigt Fig. 26A eine Reihe von sieben Farbquadraten 21, die sich in die X-Sequenz-Richtung erstrecken, wobei die Quadrate X-Sequenz-Bits b0 bis b7 darstellen. Die Farbquadrate 21 sind durch Trennzonen 26 getrennt. Die Spur C zeigt den Verlauf des Erfassungskopfs 16, während derselbe über die Quadrate, welche die Bits b0, b1, b2 und b3 darstellen, bewegt wird, wobei an diesem Punkt die Bewegungsrichtung des Erfassungskopfs umgekehrt wird und derselbe über die Quadrate, die die Bits b2, b1 und b0 darstellen, zurückläuft. Die gestrichelte Linie, die mit Spur D bezeichnet ist, ist die Spur, von der das Nachführungsverfahren annimmt, daß der Kopf 16 derselben von Bit b3 an folgt, bis ein Nachweis des Gegenteils erbracht ist.
Wenn die Nachführung in ihrem inkrementalen Modus ist, während sich der Erfassungskopf 16 entlang des Anfangsabschnitts der Spur C über die Quadrate, die die Bits b0, b1, b2 und b3 darstellen, bewegt, stimmt jeder aufeinanderfolgende Bitwert, der von dem Kopf 12 erfaßt wird, mit dem entsprechenden Bit, das von der X-Sequenz, die im Register 66 gehalten ist, vorhergesagt wird, überein. Wenn die Bewegungsrichtung des Erfassungskopfs 16 über dem Quadrat 21, das das Bit b3 darstellt, umgekehrt wird, ist das nächste tatsächliche Bit, das angetroffen wird, das Bit b2, wohingegen das nächste vorhergesagte Bit das Bit b4 ist. Bei dem vorliegenden Beispiel ist der X-Sequenz-Abschnitt, der überquert wird, derart, daß der Wert des Bits b2 gleich dem des Bits b4 ist. Folglich stimmt der Bitwert, der mittels der inkrementalen Nachführungsroutine vorhergesagt wird, mit dem tatsächlich erfaßten überein, so daß die Routine nicht über die Tatsache alarmiert wird, daß eine Richtungsumkehr über dem Quadrat, das das Bit b3 darstellt, stattgefunden hat. Die inkrementale Nachführungsroutine nimmt daher an, daß der Erfassungskopf 16 der Spur D folgt. Zu gegebener Zeit bewegt sich der Kopf 16 über das Quadrat, das das Bit b1 darstellt, und die inkrementale Nachführungsroutine testet den Wert des erfaßten Bits bezüglich des Werts des Sequenz-Bits b5, wobei sie annimmt, daß der Kopf 16 nun über demselben positioniert ist. Bei dem vorliegenden Beispiel sind die Werte der Bits b1 und b5 die gleichen, so daß die inkrementale Nachführungsroutine erneut nicht in der Lage ist, die Umkehr der Bewegungsrichtung zu erfassen, die über dem Quadrat, das das Bit b3 darstellt, stattgefunden hat. Der Erfassungskopf 16 setzt seine Bewegung entlang der Spur C fort und erreicht das Quadrat, das das Bit b0 darstellt. In dem vorliegenden Beispiel ist der Wert dieses Bits b0 von dem des Bits b6 unterschiedlich, so daß, wenn das inkrementale Nachführungsverfahren den Wert des nächsten vorhergesagten Bits entlang der Spur D (wobei dies Bit b6 ist) überprüft, es entdeckt, daß sich der vorhergesagte Bitwert von dem erfaßten Bitwert unterscheidet; zu diesem Zeitpunkt erfaßt das inkrementale Nachführungsverfahren somit, daß der Erfassungskopf 16 in einer bestimmten früheren Phase seine Bewegungsrichtung umgekehrt hat. Das Nachführungsverfahren besitzt jedoch kein Mittel, um den Punkt direkt festzustellen, an dem die Umkehr stattfand.
Fig. 26B ist ähnlich Fig. 26A, insofern sie die sieben Farbquadrate des Musters in Fig. 12 zeigt, die die Bits b0 bis b7 zeigen, jedoch wurde in diesem Fall die Spur C gezeichnet, um eine Richtungsumkehr zu zeigen, die über einer Trennzone 26 stattfindet und nicht über einem Farbquadrat 21. Bei dem dargestellten Beispiel tritt die Richtungsumkehr über der Zone 26 auf, die die Quadrate, die die Bits b3 und b4 darstellen, trennt. Das erste Quadrat, das von dem Erfassungskopf 16 nach dessen Umkehr angetroffen wird, ist das Quadrat, das das Bit b3 darstellt, wohingegen das inkrementale Nachführungsverfahren annimmt, daß das angetroffen Quadrat das ist, welches das Bit b4 darstellt. Bei dem vorliegenden Beispiel ist der Wert des Bits b3 gleich dem von b4, so daß das inkrementale Nachführungsverfahren die Umkehr nicht erfaßt, wenn es den tatsächlichen Wert des Bits b3 mit dem vorhergesagten Wert vergleicht. Genauso ist das nächste nachfolgende Quadrat, das von dem Kopf 16 angetroffen wird, das, das das Bit b2 darstellt, wobei dieses in dem vorliegenden Beispiel einen Wert besitzt, das dem Bit b5 entspricht, so daß das Nachführungsverfahren die Richtungsumkehr erneut nicht erfaßt. Jedoch bewegt sich zu gegebener Zeit der Kopf 16 über das Quadrat, das das Bit b1 darstellt, wobei das Nachführungsverfahren die Übereinstimmung des seiben mit dem vorhergesagten Wert des Bits b6 überprüft; bei dem vorliegenden Beispiel unterscheiden sich die Werte der Bits b1 und b6, so daß das Nachführungsverfahren an diesem Punkt erfaßt, daß eine Richtungsumkehr aufgetreten ist.
Unter Betrachtung des Musters in Fig. 15 ist die Fig. 26C im allgemeinen ähnlich den Fig. 26A und B, insofern sie eine Reihe von sieben Farbquadraten 21 zeigt, die sich in die X-Sequenz-Richtung erstrecken und durch Zonen 26 getrennt sind; nun sind es jedoch die Übergänge zwischen den Quadraten, die die X-Sequenz-Bits (hier b1 bis b6) darstellen. Die Spur C zeigt den Verlauf des Erfassungskopfs 16, während derselbe Übergänge bewirkt, die die Bits b1, b2 und b3 darstellen, wobei an diesem Punkt die Bewegungsrichtung des Erfassungskopfs über einem Farbquadrat umgekehrt wird und der Bewegungskopf, der sich nun in die entgegengesetzte Richtung bewegt, Übergänge bewirkt, die die Bits b3, b2 und b1 darstellen. Die mit der gestrichelten Linie markierte Spur D ist die Spur, von der das Nachführungsverfahren annimmt, daß der Kopf 16 derselben von dem Bit b3 aus folgt, bis ein Nachweis des Gegenteils erbracht ist.
Wenn die Nachführung in ihrem inkrementalen Modus ist, während sich der Erfassungskopf 16 entlang des Anfangsabschnittes der Spur C bewegt, wobei er die Bits b1, b2 und b3 erfaßt, stimmt jeder aufeinanderfolgende Bitwert, der von dem Kopf 12 erfaßt wird, mit dem entsprechenden Bit, das aus der X-Sequenz, die im Register 66 gehalten ist, vorhergesagt ist, überein. Wenn die Bewegungsrichtung des Erfassungskopfs 16 umgekehrt wird, ist das nächste tatsächliche Bit, das erfaßt wird, das Bit b3, wohingegen das nächste vorhergesagte Bit das Bit b4 ist. Bei dem vorliegenden Beispiel ist der X-Sequenz-Abschnitt, der überquert wird, ein solcher, daß der Wert des Bits b2 gleich dem des Bits b4 ist. Folglich stimmt der Bitwert, der mittels der inkrementalen Nachführungsroutine vorhergesagt wird, mit dem tatsächlich erfaßten überein, so daß die Routine nicht bezüglich der Tatsache gewarnt wird, daß eine Richtungsumkehr über dem Quadrat stattgefunden hat, daß die Übergänge, die die Bits b3 und b4 darstellen, gemeinsam haben. Die inkrementale Nachführungsmethode nimmt daher an, daß der Erfassungskopf 16 der Spur D folgt. Zu gegebener Zeit bewirkt der Kopf 16 den Übergang, der das Bit b2 darstellt, und die inkrementale Nachführungsroutine überprüft den Wert des erfaßten Bits bezüglich des Werts des Sequenz-Bits b5, von dem es annimmt, daß der Kopf 16 dasselbe eben erfaßt hat. Bei dem vorliegenden Beispiel sind die Werte der Bits b2 und b5 die gleichen, so daß die inkrementale Nachführungsroutine wiederum nicht in der Lage ist, die Bewegungsrichtungsumkehr zu erfassen, die über dem Quadrat stattgefunden hat, die die Übergänge, die die Bits b3 und b4 darstellen, gemeinsam haben. Der Erfassungskopf 16 setzt seine Bewegung entlang der Spur C fort und erfaßt zu gegebener Zeit das Bit b1. Bei diesem Beispiel unterscheidet sich der Wert dieses Bits b1 von dem von b6, so daß, wenn das inkrementale Nachführungsverfahren den Wert des nächsten vorhergesagten Bits entlang der Spur D (wobei dies das Bit b6 ist) überprüft, dasselbe entdeckt, daß sich der vorhergesagte Bitwert von dem erfaßten Bitwert unterscheidet; zu diesem Zeitpunkt erfaßt daher das inkrementale Nachführungsverfahren, daß der Erfassungskopf 16 seine Bewegungsrichtung in einer früheren Phase umgekehrt hat. Jedoch besitzt das Nachführungsverfahren kein Mittel, um den Punkt, an dem die Umkehr stattfand, direkt festzustellen.
Die Fig. 26D ist ähnlich der Fig. 26C, jedoch wurde in diesem Fall die Spur C gezeichnet, um eine Richtungsumkehr zu zeigen, die über einer Trennzone 26 und nicht über einem Farbquadrat 21 stattfindet. Bei dem dargestellten Beispiel tritt die Richtungsumkehr über der Zone 26 in dein Übergang auf, der das Bit b4 darstellt. Das erste Quadrat, das von dem Erfassungskopf 16 nach seiner Umkehr angetroffen wird, ist das Quadrat, das zuletzt von dein Kopf 16 angetroffen wurde, mit dem Ergebnis, daß ein Bit des Werts "0" decodiert wird (siehe Tabelle in Fig. 15C), wohingegen das inkrementale Nachführungsverfahren annimmt, daß das erfaßte Bit b4 ist. Bei dem vorliegenden Beispiel ist der Wert des Bits b4 gleich "0", so daß das inkrementale Nachführungsverfahren die Umkehr nicht erfaßt, wenn es den tatsächlichen Wert des erfaßten Bits mit dem vorhergesagten Wert vergleicht. Genauso ist das nächste nachfolgende Bit, das von dem Kopf 16 erfaßt wird, das Bit b3, wobei dieses bei dem vorliegenden Beispiel einen Wert besitzt, der dem des Bits b5 entspricht, so daß das Nachführungsverfahren erneut die Richtungsumkehr nicht erfaßt. Jedoch erfaßt der Kopf 16 zu gegebener Zeit das Bit b2, welches das Nachführungsverfahren auf Übereinstimmung mit dem vorhergesagten Werts des Bits b6 überprüft; bei dem vorliegenden Beispiel unterscheiden sich die Werte der Bits b1 und b6, so daß das Nachführungsverfahren an diesem Punkt erfaßt, daß eine Richtungsumkehr aufgetreten ist.
Für beide Beispiele der Muster in Fig. 12 und in Fig. 15 der Fig. 26A bis D, besteht alles, was das Nachführungsverfahren bemerkt, darin, daß am Bit b6 eine Unstimmigkeit zwischen dem erfaßten Bitwert und dem vorhergesagten Bitwert aufgetreten ist. Das Nachführungsverfahren besitzt keine Kenntnis darüber, ob die angenommene Richtungsumkehr über einem Farbquadrat oder einer Trennzone stattgefunden hat. Die einzige Begrenzung, die darüber gemacht werden kann, wo die Umkehr aufgetreten ist, besteht darin, daß dieselbe innerhalb von N/2 Bits der Bits b6 (wobei N die Fensterlänge der X-Sequenz ist) in eine Richtung stattgefunden haben muß, die entgegengesetzt zu der ist, die vorher als die Bewegungsrichtung des Erfassungskopfs 16 angenommen wurde.
Jedoch plazieren die tatsächlichen Sequenz-Bitwerte bestimmte Beschränkungen auf den vorangegangenen N-Bits darüber, wo die Umkehr stattgefunden haben könnte, da die Reihenfolge der Bitwerte, die in der Sequenz ab der Umkehrposition, jedoch in die zu der angenommenen entgegengesetzte Richtung (d.h. in die tatsächliche Bewegungsrichtung), auftreten, identisch der Sequenz von Bits sein müssen, die tatsächlich erfaßt werden. Es ist daher möglich, eine Anzahl von verschiedenen Umkehrpositionen zu fordern (wobei es für jede derselben eine dazugehörige gegenwärtige tatsächliche Position gibt) und ein anfängliches Eliminierungsverfahren durchzuführen, indem die Reihenfolge der Bitwerte, die ab jeder Umkehrposition angetroffen worden wären (wie von der gespeicherten Kopie der Sequenz vorhergesagt) mit den tatsächlich erfaßten Bitwerten verglichen wird. Tatsächlich wird bei der vorliegenden Erfindung statt des Speicherns der Werte der Bits, die zur Verwendung bei dem vorher genannten Eliminierungsverfahren erfaßt werden, die Tatsache ausgenutzt, daß für jede vorgeschlagene Umkehrposition die relevanten erfaßten Bitwerte direkt aus dem Sequenzsegment hergeleitet werden können, welches sich von der vorgeschlagenen Umkehrposition zu der gegenwärtig vorhergesagten (jedoch fehlerhaften) Position erstreckt, wobei die erfaßten Bitwerte folgende sind:
(i) die gleichen wie die Segmentbitwerte von der vorgeschlagenen Umkehrposition zu der Position, die der gegenwärtig vorhergesagten unmittelbar vorhergeht (dies gilt, da andernfalls eine Umkehr früher erfaßt worden wäre);
(ii) für das gegenwärtige Bit der entgegengesetzte Wert zu dem, der durch das Sequenzsegment gegeben ist (dies ist der Fall, da bei dem gegenwärtigen Bit eine Umkehr als eine Folge dessen, daß sich der vorhergesagte Bitwert von dem erfaßten Bitwert unterscheidet, erfaßt wurde).
Obwohl die vorliegende Erfindung die Eliminierung der vorgeschlagenen Umkehrpositionen mittels der Verwendung der gespeicherten Sequenz als ein Mittel zum Herleiten der Bitwerte, die tatsächlich erfaßt werden, durchführt, ist es offensichtlich, daß Ausführungsbeispiele, die die letzten N Bitwerte, die tatsächlich erfaßt werden, direkt speichern, ebenfalls möglich.
Das anfängliche Eliminierungsverfahren von möglichen Umkehrpositionen, wie es durch die vorliegende Erfindung ausgeführt wird, ist in Fig. 23 dargestellt, das Verfahren selbst ist mittels der RR-Anlaufroutine 103 implementiert.
Um bestimmte Umkehrpositionen zu eliminieren, ist eine Anzahl von Hypothesen ausgearbeitet, von denen jede fordert, daß eine Richtungsumkehr an einem Sequenz-Bit oder zwischen zwei solchen Bits stattgefunden hat; die möglichen Umkehrpositionen sind in Fig. 27 mittels der Sequenz-Strukturabstraktion, die auf der rechten Seite der Figur gezeigt ist und die aus den Sequenz-Bit-Quadraten sb0 bis sb6 (die den Bits b0 bis b6 entsprechen) und Zonen I, die zwischen den Sequenz-Bit-Quadraten liegen, dargestellt, wobei eine Richtungsumkehr sowohl auf Sequenz-Bit-Quadraten als auch dazwischenliegenden Zonen I möglich ist. Hinsichtlich des Musters in Fig. 12 (Absolutwertcodierung) entspricht eine Richtungsumkehr auf einem Sequenz-Bit-Quadrat oder auf einer dazwischenliegenden Zone jeweils einer Umkehr auf einem Farbquadrat oder einer Trennzone, während bezüglich des Musters von Fig. 15 (Übergangscodierung) eine Richtungsumkehr auf einem Sequenz-Bit-Quadrat bzw. einer dazwischenliegenden Zone einer Umkehr auf einer Trennzone (soweit ein Bit durch einen Übergang über eine solche Zone dargestellt ist) oder auf einem Farbquadrat entspricht. Die Sequenz-Strukturabstraktion der Fig. 27 ist folglich sowohl auf die Absolutwertcodierung als auch die Übergangscodierung anwendbar und, da sowohl die RR-Anlaufroutine 103 als auch die Umkehrerholungs-Routine 102 mit dieser Abstraktion arbeiten, sind diese Routinen ebenfalls sowohl auf die Absolutwertcodierung als auch auf die Übergangscodierung anwendbar.
Um die Umkehrpositions-Hypothesen auszuarbeiten und zu testen, werden für jede der möglichen gegenwärtigen tatsächlichen X-Sequenz-Positionen Zeiger erzeugt. Zu Zwecken der vorliegenden Erklärung wird, wenn p&sub0; den Zeiger darstellt, der auf das Sequenz-Bit-Quadrat (in dem Beispiel sb6) zeigt, auf dem eine Umkehr erfaßt wurde, der Zeiger, der auf das vorangegangene Sequenz-Bit-Quadrat (in dem Beispiel sb5) zeigt, mit (p&sub0;-1) bezeichnet, der Zeiger, der auf das Sequenz-Bit-Quadrat vor demselben (in dem Beispiel sb4) zeigt, mit (p&sub0;-2) bezeichnet usw.. In der Praxis zeigt jeder Zeiger auf das Sequenz-Bit, das durch das entsprechende Sequenz- Bit-Quadrat der Sequenz-Strukturabstraktion dargestellt ist, wobei bei der folgenden Beschreibung die Sequenz-Bits selbst allgemein bezeichnet werden und nicht die entsprechende Sequenz-Bit-Quadrat-Abstraktion.
Unter allen möglichen Hypothesen, die die Umkehrposition betreffen, gibt es eine, die einen speziellen Charakter aufweist, da dieselbe für das Muster in Fig. 12 unberücksichtigt gelassen werden kann und für das Muster in Fig. 15 anfänglich nicht überprüfbar ist; diese Hypothese (Hypothese 0) ist die, daß die Richtungsumkehr an der gegenwärtigen Bitposition stattgefunden hat. Es ist offensichtlich, daß diese Hypothese für das Muster in Fig. 12 keine Bedeutung hat; für das Muster in Fig. 15 entspricht dies jedoch einer Umkehr, die über einer Trennzone (wie in Fig. 26D) stattfindet. Die Hypothese 0 ist für das Muster in Fig. 15 anfänglich nicht überprüfbar, da es keine Informationen darüber gibt, wie irgendein Test auszuführen ist. Die Hypothese 0 muß daher im Falle des Musters in Fig. 15 als möglicherweise wahr zurückgehalten werden (und kann tatsächlich auch für das Muster in Fig. 12 zurückgehalten werden, während nachfolgende dieselbe Tests allgemein eliminieren). Da die Hypothese 0 nicht anfänglich überprüft wird, ist sie in Fig. 27 nicht gezeigt.
Die erste überprüfbare Hypothese (die Hypothese 1, die in Block 140, Fig. 27 gezeigt ist) ist die Umkehr, die an der Zwischenzone I, die zwischen den Sequenz-Bits, auf die die Zeiger p&sub0;, (p&sub0;-1) zeigen, liegt, auftritt, wobei diese Zone durch den Ausdruck "I(p&sub0;(p&sub0;-1))" angezeigt ist, die in Fig. 27 gezeigt ist. Ferner ist gemäß Hypothese 1 die gegenwärtige tatsächliche Position des Erfassungskopfs entlang der X-Sequenz an der Position, auf die der Zeiger (p&sub0;-1) zeigt, d.h. das Bit b5 in dem Beispiel. Diese Hypothese kann unmittelbar ausgeschlossen werden, wenn der Wert des Bits, auf den der Zeiger (p&sub0;-1) zeigt, der gleiche ist wie der Wert des Bits, auf den der Zeiger p&sub0; zeigt (in dem Beispiel, wenn b5 = b6), da bekannt ist, daß der Wert des entsprechenden erfaßten Bits sich von dem des Bits, auf den der Zeiger p&sub0; zeigt, unterscheidet. Es sollte bemerkt werden, daß in Fig. 27 die Vereinbarung verwendet ist, daß, wenn ein Zeiger von eckigen Klammern umgeben ist, derselbe der Wert des Bits ist, auf den der Zeiger zeigt, der bezeichnet ist.
Wenn die Überprüfung, ob die Hypothese 1 wahr ist, bestanden wird, wird zurückgehalten, daß der Zeiger (p&sub0;-1) möglicherweise auf die gegenwärtige tatsächliche Position des Erfassungskopfs 16 zeigt. Wenn der Test der Hypothese 1 jedoch nicht bestanden wird, wird der Zeiger (p&sub0;-1) ausgeschlossen, da bekannt ist, daß die tatsächliche gegenwärtige Position des Kopfs 16 nicht bei dem Bit sein kann, auf das der Zeiger zeigt.
Wurde die Hypothese 1 überprüft, wird als nächstes die Hypothese 2 (die im Block 141 in Fig. 23 gezeigt ist) betrachtet. Die Hypothese 2 besteht darin, daß die Umkehr bei dem Bit stattgefunden hat, auf das der Zeiger (p&sub0;-1) zeigt, und daß die gegenwärtige tatsächliche Position des Erfassungskopfs bei dem Bit ist, auf das der Zeiger (p&sub0;-2) zeigt. Die Hypothese wird wiederum durch Vergleichen des Werts des Bits, auf das der Zeiger p&sub0; zeigt, mit dem der hypothetischen tatsächlichen Position überprüft, d.h. der Position, die durch den Zeiger (p&sub0;-2) angezeigt ist. Wenn die überprüften Bitwerte gleich sind, kann die Hypothese 2 ausgeschlossen werden, da bekannt ist, daß der Wert des entsprechenden erfaßten Bits sich von dem des Bits, auf den p&sub0; zeigt, unterscheidet. Der Zeiger (p&sub0;-2) wird in diesem Fall ausgeschlossen. Andererseits wird die Hypothese 2 nicht ausgeschlossen und der Zeiger (p&sub0;-2) wird als möglicher Anzeiger der gegenwärtigen tatsächlichen Position zurückgehalten, wenn die überprüften Bitwerte unterschiedlich sind.
Nachdem die Hypothese 2 überprüft wurde, wird als nächstes die Hypothese 3 (Block 142) betrachtet. Diese Hypothese fordert, daß eine Umkehr über der Zone I, die die Bits trennt, auf die die Zeiger (p&sub0;-1) und (p&sub0;-2) zeigen, aufgetreten ist, wobei die gegenwärtige tatsächliche Position des Erfassungskopfs bei dem Bit ist, auf das der Zeiger (p&sub0;-3) zeigt. In diesem Fall kann die Hypothese zwei Überprüfungen unterworfen werden, wobei die erste Überprüfung eine solche ist, die für die Hypothesen 2 und 1 durchgeführt wurde, durch die der Wert des Bits, auf den der Zeiger p&sub0; zeigt, mit dem Wert des Bits, auf die der Zeiger zeigt, der gemäß der Hypothese die gegenwärtige tatsächliche Position anzeigt, verglichen wird; die Hypothese wird ausgeschlossen, wenn diese Bitwerte gleich sind. Der zweite Test für die Hypothese 3 besteht darin, ob die Werte der Bits, die zwischen der falschermaßen angenommenen Position und der hypothetischen tatsächlichen Position eingeschlossen sind, gleich sind (wobei der Bitwert auf der Seite der der geforderten Umkehrposition nächsten Position p&sub0; ein wahrer Anzeiger des Werts des entsprechenden erfaßten Bits ist). In anderen Worten heißt das, daß der Wert des Bits, auf den der Zeiger (p&sub0;-1) zeigt, mit dem Wert des Bits, auf den der Zeiger (p&sub0;-2) zeigt, verglichen wird und die Hypothese 3 ausgeschlossen und der Zeiger (p&sub0;-3) als ein möglicher Anzeiger der tatsächlichen Position ausgeschlossen wird, wenn sich die verglichenen Bitwerte unterscheiden.
Als nächstes wird die Hypothese 4 (Block 143 in Fig. 23) ausgearbeitet und überprüft, wobei diese Hypothese darin besteht, daß die Umkehr bei dem Bit stattfand, auf das der Zeiger (p&sub0;-2) zeigt, und daß die tatsächliche gegenwärtige Position durch den Zeiger (p&sub0;-4) angezeigt ist. Das Überprüfen dieser Hypothese verläuft im wesentlichen auf die gleiche Art und Weise wie bei Hypothese 3 und wird deshalb nicht detailliert beschrieben. Genauso werden weitere Hypothesen für Umkehrpositionen und tatsächliche gegenwärtige Positionen ausgearbeitet und überprüft, die aufeinanderfolgend weiter von der Position, auf die der Zeiger p&sub0; zeigt, entfernt liegen. Es ist offensichtlich, daß für jede hypothetische Umkehrposition und die entsprechende hypothetische tatsächliche gegenwärtige Position folgendes stattfindet:
(i) in jedem Fall (mit Ausnahme der Hypothese 0) ein erster Test, der den Vergleich der Bitwerte bei der hypothetischen tatsächlichen gegenwärtigen Position (p&sub0;-Cn2) und der Position, auf die p&sub0; zeigt, einschließt (wobei die Hypothese ausgeschlossen wird, wenn diese Werte gleich sind, da das entsprechende erfaßte Bit einen Wert besitzen muß, der sich von dem des Bits, auf den p&sub0; zeigt, unterscheidet);
(ii) in Fällen, in denen die hypothetische Umkehrposition um mindestens 1 Bit von der hypothetischen gegenwärtigen Position beabstandet ist, einen oder mehrere zweite Tests, in denen die Bitwerte der Bits des oder jedes Bitpaares, das symmetrisch um die hypothetische Umkehrposition angeordnet ist, verglichen werden (wobei die Hypothese ausgeschlossen wird, wenn sich diese Werte unterscheiden, da das Bit jedes Paares, das näher bei p&sub0; liegt, einen Wert aufweist, der gleich dem entsprechenden erfaßten Bit ist).
Es ist klar, daß je weiter die hypothetische tatsächliche Position von der Position p&sub0; entfernt ist, desto mehr Möglichkeiten es gibt, um die betroffene Hypothese zu überprüfen, da die Anzahl der eingeschlossenen Bitpaare, die dem zweiten Test unterworfen werden, anwächst, je größer die Trennung der hypothetischen tatsächlichen Position von p&sub0; ist.
Zu gegebener Zeit werden alle relevanten Hypothesen ausgearbeitet und überprüft sein (eine relevante Hypothese ist eine solche, für die die hypothetische tatsächliche Position innerhalb des Fensterlängenbereichs der Position p&sub0; liegt). Am Ende dieses Verfahrens wird es nur wenige verbleibende gültige Hypothesen geben, wobei diese Hypothesen durch die Zeiger auf deren hypothetische gegenwärtige tatsächliche Position dargestellt werden.
Wie bereits gezeigt wurde, ist das Verfahren, das oben allgemein bezugnehmend auf Fig. 27 beschrieben ist, mittels der RR-Anlauf-Routine 103 implementiert, welche mittels der inkrementalen Nachführungsroutine 101 initiiert wird, wenn eine Nichtübereinstimmung zwischen einem erfaßten Bitwert und dem vorhergesagten Bitwert entdeckt wird. Fig. 28 zeigt ein Flußdiagramm der RR-Anlaufroutine 103. Beim Betreten der Routine wird der Zahl Cn2 der Wert "1" zugewiesen, der Zahl Cn3 wird der Wert "0" zugewiesen und der Zeiger p&sub0; wird in der Zeigerliste 68 (Schritt 150) plaziert. Als nächstes wird ein Zeiger (p&sub0;-Cn2) erzeugt, wobei dies ein Zeiger auf eine hypothetische gegenwärtige tatsächliche Position (Schritt 150) ist. Danach werden die Tests, die zum Überprüfen der Gültigkeit der hypothetischen gegenwärtigen tatsächlichen Position möglich sind, durchgeführt (Schritt 152), wobei dies die oben beschriebenen ersten und zweiten Tests sind.
Wenn einer oder mehrere der Tests oder Tests, die zum Testen der gegenwärtig hypothetisch tatsächlichen Position verfügbar sind, nicht bestanden wird, wird der entsprechende Zeiger (p&sub0;-Cn2) ausgeschlossen (Schritt 153). Andererseits wird der Zeiger der hypothetischen gegenwärtigen tatsächlichen Position in der Zeigerliste 68 gespeichert (Schritt 154), wobei seine dazugehörige Richtungs-Flag eine Richtung anzeigt, die entgegengesetzt zu der ist, die zum Zeiger p&sub0; gehört, wenn alle Tests für die hypothetische gegenwärtige tatsächliche Position bestanden werden.
Nach dem Speichern oder dem Ausschließen des Zeigers (p&sub0;-Cn2) wird die Zahl Cn2 erhöht, um zu verfolgen, wieviele Zeiger für die hypothetischen gegenwärtigen tatsächlichen Positionen erzeugt und überprüft wurden (Schritt 155). Wenn der erhöhte Wert der Zahl Cn2 die Fensterlänge N der X-Sequenz überschreitet, werden keine weiteren Zeiger für die hypothetische gegenwärtige tatsächliche Position erzeugt (siehe Schritt 156). In dieser Phase kann der Zeiger p&sub0; von der Zeigerliste 68 gestrichen werden, wenn das Muster 20 die Form von Fig. 20 besitzt. Wenn der Wert der Zahl Cn2 kleiner als N ist, wenn derselbe im Schritt 156 überprüft wird, springt die Routine zu Schritt 151 zurück, um einen weiteren Zeiger für eine neue hypothetische gegenwärtige tatsächliche Position zu erzeugen, wobei die Verfahrensschritte 151 bis 155 wiederholt werden, bis alle Zeiger für alle möglichen gegenwärtigen und tatsächlichen Positionen erzeugt und überprüft wurden.
Als nächstes werden die Aufschub-Flags der vorangegangenen N/2 X-Positionseinträge in dem Ausgabe-FIFO 76 gesetzt, um anzuzeigen, daß einer oder mehrere dieser Positionswerte falsch sind und daß aktualisierte Werte geliefert werden, sobald dieselben verfügbar sind (Schritt 158). Ein neuer X-Positionseintrag, wobei dessen Aufschub-Flag gesetzt wird, wird ebenfalls in den FIFO 76 gemacht, bezüglich des gegenwärtig erfaßten Bits auf der Basis dessen eine Umkehr erfaßt wurde. Danach wird RESULT der Wert "D" zugewiesen (Schritt 159) und die RR-Anlaufroutine 103 wird verlassen.
Beim Verlassen der RR-Anlaufroutine 103 enthält die Zeigerliste 68 einen Satz von Zeigern auf eine Anzahl von hypothetischen tatsächlichen Positionen, die die anfänglichen Gültigkeitstests bestanden haben.
Infolge dessen, daß beim Verlassen der RR-Anlaufroutine 103 RESULT der Wert "D" zugewiesen wird, wird der Nachführungsmodus auf Umkehrerholung geändert, so daß die Umkehrerholungs-Routine 102 betreten wird, wenn der Erfassungskopf 16 ein neues X-Sequenz-Bit erfaßt. Das neu gelieferte X-Sequenz-Bit ermöglicht ein weiteres Überprüfen der hypothetischen tatsächlichen gegenwärtigen Positionen, die von den Zeigern dargestellt werden, die in der Zeigerliste 68 gespeichert sind, da der erfaßte Bitwert mit dem Wert verglichen werden kann, der wiederum durch Verwenden jeder hypothetischen gegenwärtigen tatsächlichen Position vorhergesagt wird. Somit wird, wie in dem Flußdiagramm der Umkehrerholungs-Routine, das in Fig. 29 gezeigt ist, im Schritt 161 der erste/nächste Zeiger in der Zeigerliste 68 verwendet und der Wert des nächsten Bits, das von diesem Punkt vorhergesagt wird, wird mit dem tatsächlichen erfaßten Bitwert verglichen (Schritt 162). Wenn es eine Nichtübereinstimmung zwischen dem vorhergesagten und dem erfaßten Bitwert gibt, wird der entsprechende Zeiger von der Zeigerliste 68 (Schritt 163) gestrichen. Andernfalls wird der relevante Zeiger erhöht und wieder in der Zeigerliste 68 gespeichert (Schritt 164), wenn sich der vorhergesagte und der erfaßte Bitwert entsprechen. Danach wird eine Überprüfung durchgeführt, um zu sehen, ob es irgendwelche weiteren Zeiger, die verarbeitet werden müssen, in der Zeigerliste 68 gibt (Schritt 165), und, wenn das der Fall ist, springt die Routine zum Schritt 161 zurück.
Sobald alle Zeiger in der Liste 68 verarbeitet wurden, wird die Gesamtzahl der Zeiger, die in der Liste verblieben sind, untersucht (Schritt 166). Wenn keine Zeiger in der Liste verbleiben, wurde eine unerholbare Situation angetroffen; dies kann, entweder aufgrund der Erfassung von Fehlern oder da die Bewegungsrichtung während des Umkehrerholungsverfahrens erneut umgekehrt wurde, aufgetreten sein. In jedem Fall wird RESULT der Wert "L" zugewiesen (Schritt 167) und die Umkehrerholungs-Routine wird verlassen.
Wenn jedoch die Anzahl der Zeiger, die in der Zeigerliste 68 verblieben sind, nur Eins ist, wird angenommen, daß dieser Zeiger richtig auf die gegenwärtige tatsächliche Position des Erfassungskopfs zeigt. Folglich fährt die Routine 102 fort, tatsächliche X-Positionswerte für alle X-Einträge herzuleiten, deren Aufschub-Flags in dem Ausgabe-FIFO 76 gesetzt sind, wobei diese neuen Positionswerte in den FIFO 76 eingegeben werden, zusammen mit der gegenwärtigen tatsächlichen Position (Schritt 168). Danach wird RESULT der Wert "S" zugewiesen und die Umkehrerholungsroutine wird verlassen.
Wenn es noch mehrere Einträge in der Zeigerliste 68 gibt, so daß es noch nicht möglich ist, zu entscheiden, welche wirklich die tatsächliche gegenwärtige X-Position ist, dann macht die Umkehrerholungs-Routine, die bestimmten Kriterien unterliegt, die nachfolgend erklärt werden sollen, einen aufgeschobenen Eintrag in den Ausgabe-FIFO 76, indem die Aufschub-Flag eines neuen X-Eintrags gesetzt wird (Schritt 172) und RESULT der Wert "D" zugewiesen wird, bevor die Umkehrroutine verlassen wird. Danach wird die Umkehrerholungs-Routine ausgeführt, während jeder neue X-Bitwert eingelesen wird, bis alle Zeiger außer dem richtigen aus der Zeigerliste eliminiert wurden.
Wenn nur eine Umkehr stattgefunden hat und es keine Lesefehler gibt, sollte das Eliminierungsverfahren innerhalb von (N-2) Iterationen der Umkehrerholungs-Routine erfolgreich sein. Ein Scheitern beim Isolieren des richtigen Zeigers innerhalb von (N-2) Iterationen zeigt an, daß die X-Position unerholbar verloren wurde. Um diese Situation zu erfassen, wird die Zahl Cn3 jedesmal erhöht, wenn die Überprüfung (Schritt 166) auf dem Zweig verlassen wird, der mehreren Zeigereinträgen in der Liste 68 entspricht, wobei diese Erhöhung im Schritt 170 bewirkt wird. Danach wird der Wert der Zahl Cn3 mit dem Wert (N-2) verglichen (Schritt 171), und nur wenn Cn3 kleiner oder gleich (N-2) ist, werden die Schritte 172 und 173 ausgeführt. Wenn der Wert der Zahl Cn3 größer als (N-2) ist, wird RESULT der Wert "L" zugewiesen (Schritt 174) und die Umkehrerholungs-Routine 180 wird verlassen.
Kurz gesagt ist zu sehen, daß das X-BIT-Verfahren 60 nach der Feststellung einer Anfangsposition durch Ausführen der absoluten Nachführungsroutine 100 fortfährt, um die gegenwärtige X-Position mittels des inkrementalen Verfahrens, das durch die inkrementale Nachführungsroutine 101 implementiert ist, zu verfolgen. Wenn die inkrementale Nachführungsroutine eine Unstimmigkeit zwischen dem tatsächlichen erfaßten Bitwert und dem Wert des nächsten vorhergesagten Bits der X-Sequenz erfaßt, wird angenommen, daß eine Umkehr aufgetreten ist, wobei das Umkehrerholungs-Verfahren durch die Ausführung der RR-Anlaufroutine 103 initiiert wird, um einen Satz von Zeigern auf mögliche gegenwärtige tatsächliche X-Positionen einzurichten und anfängliche Gültigkeitsüberprüfungen auf diesen Zeigern durchzuführen. Danach wird die Umkehrerholung 102 ausgeführt, während jeder neue X-Bitwert eingelesen wird und verwendet wird, um weitere Gültigkeitsüberprüfungen auf den Sätzen der möglichen Zeiger auf die gegenwärtige tatsächliche X-Position durchzuführen. Zu einer gegebenen Zeit wird entweder die gegenwärtige X-Position durch die Routine 102 festgestellt sein oder eine Entscheidung getroffen sein, daß die X-Position unerholbar verloren wurde.
Das YBIT-Verfahren 61 arbeitet in einer analogen Art für eine Bewegung entlang der Y-Sequenz.
Die Ausgaben der XBIT- und YBIT-Verfahren 60 und 61 werden als eine Folge von X- und Y-Positionseinträgen zum Speichern in den Ausgabe-FIFOs 76 bzw. 77 zu dem Ausgabepuffer 63 geleitet. Die Reihenfolge, in der die X- und Y-Positionseinträge von dem Puffer 63 empfangen werden, wird mittels eines Sequenznummergenerators 179 verfolgt, der jedesmal erhöht wird, wenn ein neuer X- oder Y-Eintrag empfangen wird, wobei jeder neue Eintrag mit dieser Sequenznummer markiert wird (durch die Nummer, die zusammen mit dem Eintrag in dem entsprechenden FIFO 76, 77 gespeichert wird). Wie vorher bemerkt wurde, besitzt jeder Eintrag ferner eine zugehörige Aufschub-Flag, die gesetzt werden kann, um anzuzeigen, daß der Eintrag nur ein vorläufiger ist und nicht von dem Prozessorteilsystem 51 ausgegeben werden sollte. Tatsächlich muß ein Eintrag, der mit Aufschub markiert ist, anfänglich keinen entsprechenden Positionswert besitzen, wobei dieser Wert später geliefert wird (dies ist sowohl der Fall, wenn die absolute Nachführungsroutine 100 eine Fenstersequenz vor dem Feststellen einer anfänglichen absoluten Position aufbaut, als auch, wenn die Umkehrerholungs-Routine 102 noch Zeiger aus dem Satz der möglichen Zeiger, die in der Liste 68 gespeichert sind, eliminiert).
Das XBIT- und das YBIT-Verfahren 60 und 61 können unabhängig in ihre entsprechenden FIFOs schreiben, obwohl, wenn beide dies innerhalb eines bezüglich zueinander kurzen Zeitintervalls durchführen, beide Einträge (der X- und der Y-Eintrag) die gleiche Sequenznummer erhalten. Es ist mittels eines geeigneten Systems von Semaphoren verhindert, daß das Ausgabeverfahren 62 mit den Verfahren 60 und 61 kollidiert und umgekehrt.
Das Ausgabeverfahren 62 wird nun bezugnehmend auf das Flußdiagramm, das in Fig. 30 gezeigt ist, beschrieben. Die elementare Operation des Ausgabeverfahrens besteht darin, die obersten X- und Y-Positionskopfeinträge aus den Ausgabe- FIFOS 76, 77 zu verwenden und dieselben als die gegenwärtigen Koordinaten des Erfassungskopfs 16 auszugeben. Jedoch ist dieses Verfahren durch die Möglichkeit von Einträgen in den FlFOs 76, 77, die mit Aufschub markiert sind, kompliziert. Das Ausgabeverfahren 62 muß nicht nur die Ausgabe einstellen, wenn ein Aufschubeintrag angetroffen wird, sondern die Operation des Ausgabeverfahrens sollte vorzugsweise hinter die der XBIT- und YBIT-Verfahren 60 und 61 verschoben werden, so daß sich in den FIFOs 76, 77 eine Warteschlange von Einträgen aufbaut, die es ermöglichen, daß das XBIToder das YBIT-Verfahren vorher verarbeitete Einträge beim Erfassen einer Umkehr entweder in die X- oder die Y-Koordinatenrichtung auf Aufschub setzen. Wenn gültige Einträge in den FIFOs 76, 77 existieren, sollte es trotzdem nicht ermöglicht sein, daß dieselben für immer unbenutzt bleiben. Es ist daher offensichtlich, daß das Ausgabeverfahren 62 eine Anzahl von sich widersprechenden Anforderungen berücksichtigen und bei seinem Betrieb einen bestimmten zufriedenstellenden praktischen Kompromiß liefern muß.
Sich nun einer Betrachtung der Fig. 30 zuwendend, besteht der erste Schritt, der von dem Ausgabeverfahren ausgeführt wird, darin, den Kopfeintrag jedes Ausgabe-FIFOs 76, 77 zu untersuchen (Schritt 180). Wenn die Aufschub-Flag des Kopfeintrags gesetzt ist (überprüft im Schritt 181), springt das Ausgabeverfahren zurück zum Schritt 180 und fährt fort, den Kopfeintrag zu überprüfen, bis die Aufschub-Flag von dem XBIT- oder YBIT-Verfahren rückgesetzt wird oder bis der Eintrag gelöscht ist.
Wenn die Aufschub-Flag keines Kopfeintrags gesetzt ist, fährt das Ausgabeverfahren als nächstes fort, die Anzahl der Einträge in jedem FIFO zu überprüfen (Schritt 182). Wenn es mehr als N/2 Einträge gibt, gibt das Ausgabeverfahren den obersten Eintrag der FIFOs 76, 77 als ein X/Y-Koordinatenpaar aus. Danach werden einer oder beide Kopfeinträge gemäß den Kriterien, die nachfolgend beschrieben sind (Schritt 186) entfernt und das Ausgabeverfahren springt zurück zum Schritt 180.
Eine typische Ausgabesequenz von X/Y-Paaren und das Verfahren zum Entfernen der Einträge aus dem Kopf der FIFOs 76, 77 wird als nächstes bezugnehmend auf folgende zwei Listen beschrieben, welche den typischen Inhalt der FIFOs 76, 77 darlegen. X O/P FIFO 76 Y O/P FIFO 77
In dieser Liste entspricht der oberste Eintrag dem Kopfeintrag jedes FIFOs und die Eintrags-Suffixe entsprechen der Sequenznummer, die den Einträgen zugewiesen ist. Jedesmal, wenn der Schritt 185 ausgeführt wird, werden die Kopfeinträge der zwei FIFOs als ein X/Y-Koordinatenpaar ausgegeben. Danach wird im Schritt 186 der Kopfeintrag jeder Liste untersucht und gelöscht, wenn:

entweder

die nächsten Einträge in beiden Listen gleich alt sind (wie durch deren als Suffix verwendete Sequenznummern angezeigt ist),

oder

der nächste Eintrag in der zu prüfenden Liste älter ist (d.h. eine niedrigere Sequenznummer hat) als der nächste Eintrag in der älteren Liste.
Die zwei Listen werden gleichzeitig untersucht in dem Sinne, daß, wenn erwägt wird, den Kopf einer Liste zu löschen, vor irgendeinem Entfernen des Kopfeintrags der anderen Liste ein Vergleich mit der anderen durchgeführt wird. Außerdem wird der Kopfeintrag einer Liste nicht entfernt, wenn dies die Liste leer zurücklassen würde.
Die vorhergehenden Streichkriterien besitzen die Wirkung des Sicherstellens, daß jeder Listeneintrag verwendet wird und mit dem letzten Wert der anderen Liste verwendet wird, der zu der Zeit, zu der er genommen wurde, gültig war. Für die gegebenen Beispiellisten würde die Sequenz der Ausgabe von X/Y-Koordinatenpaaren wie folgt lauten:
x&sub0;, y&sub0;
x&sub0;, y&sub1;
x&sub3;, y&sub2;
x&sub3;, y&sub2;
x&sub3;, y&sub4;
x&sub5;, y&sub4;
x&sub5;, y&sub6;
x&sub7;, y&sub7;
Wenn bei der Rückkehr nun zu einer Betrachtung von Fig. 30 die Überprüfung, die im Schritt 182 durchgeführt wird, zeigt, daß die Anzahl der Einträge in dem FIFO 63 kleiner als N/2 ist, wird ein Zeitgeber gestartet (Schritt 183) und eine Auszeit überprüft (Schritt 184). Wenn der Zeitgeber noch eine Zeitnahme durchführt, springt das Verfahren zur Überprüfung 182 zurück. Wenn der Zeitgeber jedoch die Zeitnahme beendet hat, springt das Verfahren zu Schritt 185, indem es den Kopfeintrag des FIFOs verarbeitet.
Die Schritte 182 bis 184 versuchen, sicherzustellen, daß es allgemein mindestens N/2 Einträge in jedem der FIFOs 76, 77 gibt (wobei diese Anzahl von Einträgen als die 'Zielwarteschlangen'-Länge bezeichnet wird), daß jedoch die Einträge zu dem Kopf der FIFOs hin nicht unbenutzt liegen, sondern mit einer bestimmten Rate, die mittels der Periode, die zeitlich durch die Schritte 183 und 184 bestimmt ist, durchgeschoben werden, wenn die Rate der Eintragseingaben sehr gering wird. Die Ziel-FIFO-Warteschlangenlänge von N/2 ist auf der Basis dessen ausgewählt, daß, wenn eine Umkehr erfaßt wird, die vorangegangenen N/2 Einträge für die X- (oder Y-) Position wenn möglich auf Aufschub gesetzt sind. Da es jedoch, wenn eine Umkehr erfaßt wird, nur die jüngsten der N/2 Einträge sein werden, die falsch sind, können Zielwarteschlangenlängen von weniger als N/2 akzeptabel sein, abhängig von der erkannten relativen Wichtigkeit der eingeschlossenen Faktoren.
Schließlich werden bezugnehmend auf Fig. 17 das XBIT-, das YBIT- und das Ausgabeverfahren 60, 61 und 62 alle neu initiiert und der Puffer 64 und die Ausgabe-FIFOs 76, 77 geräumt, wenn die Abhebe-Unterbrechung aktiviert wird, was bewirkt, daß die Unterbrechungsdienstroutine ISR-4 ausgeführt wird. In diesem Fall wird auch die Niederpegel-Hardware 50 rückgesetzt.
Selbstverständlich sind zu der oben beschriebenen Anordnung viele Variationen möglich. Im allgemeinen sei bemerkt, daß die Komplexität der Vorrichtung von der Form des Musters, das erfaßt wird und insbesondere davon, wieviele Informationen direkt durch das Muster geliefert werden und wieviele hergeleitet werden müssen, abhängt.

Anwendungen

Die beschriebene Mustererfassungsvorrichtung kann in einer Anzahl von verschiedenen Anwendungen verwendet werden.
Z.B. kann die elementare Vorrichtung von Fig. 1 als ein Graphik-Tableau verwendet werden. Bei einer solchen Anwendung kann eine binäre Sequenz von 2000 Elementen verwendet werden, um ein Muster des Typs aufzubauen, bei dem zwei binäre Sequenzen orthogonal angeordnet sind (wobei dieselbe Sequenz für beide verwendet werden kann), wenn Mustermerkmale von 0,5 mm erfaßt werden können und das Tableau eine Oberfläche von 500 mm x 1000 mm aufweist.
Dies impliziert eine Fensterlänge von 11 oder 12 Elementen, abhängig davon, ob eine PRBS oder eine umkehrbare Sequenz verwendet ist; die Teilmusterlänge wird daher in beiden Richtungen 5,5 oder 6 mm sein. Wenn eine Einpixel-Erfassung (Mustermerkmal) verwendet ist, kann die Position der Schreibspitze folglich mit einer nur geringen Bewegung der Schreibspitze bestimmt werden. Selbstverständlich ist keine Schreibspitzenbewegung erforderlich, wenn eine Fläche von 6 mm im Quadrat auf einmal erfaßt wird.
Fig. 31 zeigt die Verwendung der Positionserfassungsvorrichtung als eine Auflage für den Bildschirm 30 des Monitors 31 einer Workstation (Schnittansicht). Das Bauteil 14, das das Muster trägt, ist aus einem Material hergestellt, das für sichtbares Licht durchlässig ist, während das Muster selbst in einem Infrarot-reflektierenden Mittel auf das Bauteil gedruckt ist, welches ebenfalls für sichtbares Licht durchlässig ist. Folglich kann die Bildschirmanzeige durch das Muster 20 und das Bauteil 14 betrachtet werden. Um eine spezielle Position auf dem Bildschirm anzuzeigen (z.B. zum Zweck des Auswählens einer speziellen Funktion), wird die Schreibspitze 11 verwendet, um auf den Standort zu zeigen. Der Erfassungskopf 16 der Schreibspitze ist angeordnet, um auf das Infrarot-Reflexionsvermögen empfindlich zu sein und kann daher das Muster 20 lesen. Die Funktionen der Teilmuster-Bildverarbeitungseinheit 12 und der Positionsbestimmungseinheit 13 von Fig. 1 werden durch die Verarbeitungseinheit 32 der Workstation ausgeführt.
Auf eine der Fig. 31 ähnliche Art und Weise kann eine Transparentdokumentauflage vorgesehen werden, um zu ermöglichen, daß ein Dokument in ein elektronisches Format aufgezeichnet wird.
Fig. 32 zeigt die Verwendung der Positionserfassungsvorrichtung als eine elektronische "Weißtafel". Bei dieser Anwendung ist das Bauglied 14, das das Muster trägt, mit einer undurchlässigen weißen Oberfläche vorgesehen, auf die das Muster 20 aufgebracht ist. Das Muster besitzt die Form von Infrarot-empfindlichen Markierungen, die entweder für sichtbares Licht durchlässig (um das weiße Hintergrundbauglied 14 zu zeigen) oder selbst weiß sind, um mit dem weißen Hintergrundbauglied 14 ineinander überzugehen). Um auf die weiße Tafel zu schreiben, die aus dem Bauglied 14 und dem aufgebrachten Muster 20 zusammengesetzt ist, ist der Kopf der Schreibspitze 11 mit einem Markierelement 33 (siehe das Nebenbild in Fig. 32) versehen, das wirksam ist, um ein Markiermittel auf der weißen Tafel abzuscheiden. Dieses Markiermittel ist Infrarot-durchlässig, jedoch optisch sichtbar (in Fig. 32 wurde der Buchstabe "J" gezeigt, der auf die weiße Tafel geschrieben wurde). Der Erfassungskopf 16 der Schreibspitze 11 ist angeordnet, um die Infrarot-Mustermarkierungen zu erfassen, die nicht durch die Schrift auf der weißen Tafel verdeckt sind. Auf diese Art und Weise kann die Position der Schreibspitze über der weißen Platte erfaßt werden, so daß es möglich wird, ein Bild dessen, was auf die weiße Platte geschrieben wurde, aufzubauen (z.B. mittels einer geeignet programmierten Workstation 32).
Fig. 33 zeigt die Verwendung der Positionserfassungsvorrichtung als ein "Flip-Chart". Bei dieser Anwendung ist das Bauteil 14, das das Muster trägt, mit einem Muster 20, das optisch sichtbar sein kann, markiert. Ein markierbares Blatt 35 wird dann über dem Muster 20 plaziert. Dieses Blatt 35 liefert zumindest einen halbundurchlässigen Hintergrund, auf dem eine Person schreiben kann; jedoch ermöglicht das Blatt 35 das Erfassen des Musters 20 durch dasselbe mittels eines geeigneten Erfassungskopfs 16 der Schreibspitze 11. Wie bei dem Ausführungsbeispiel von Fig. 32 besitzt die Schreibspitze ein Markierelement, das wirksam ist, um ein Markiermittel auf dem Blatt 35 abzuscheiden. Dieses Markiermittel besitzt die Charakteristik, daß es ein Erfassen des Musters 20 durch dasselbe ermöglicht, während es zur gleichen Zeit gegenüber dem Hintergrund des Blattes 35 noch optisch sichtbar ist.
Eine alternative Implementierung des Flip-Charts von Fig. 33 wäre es, das Muster 20 auf der Rückseite jedes Blattes 15 zu plazieren und nicht auf dem Bauteil 14.

Varianten

Für Fachleute sind viele Variationen der oben beschriebenen Positionserfassungsvorrichtung offensichtlich. Obwohl die Muster und ihre darunterliegenden Arrays z.B. bezüglich einer rechtwinkligen Anordnung von Zellen beschrieben wurden, ist dies nicht die einzig mögliche Zellenanordnung. Zwei weitere mögliche Partitionierungen sind die, die auf dreieckigen und sechseckigen Gittern basieren, die gebildet werden, indem eine Oberfläche in kongruente regelmäßige Dreiecke bzw. Sechsecke geteilt wird. Diese beiden Gitter besitzen in bestimmten Situationen potentielle Vorteile.
- Bei einem dreieckigen Gitter besitzt jede Zelle nur drei Nachbarn (zusammen mit drei anderen Zellen, die sie an einem Punkt berührt). Bei einem rechtwinkligen Gitter besitzt jede Zelle vier Nachbarzellen und vier Zellen, die sie an einem Punkt berührt. Ein Codierschema vorausgesetzt, bei dem jeder Zellenübergang eine Farbänderung einschließen muß und bei dem jeder Nachbar einer gegebenen Zelle eine unterschiedliche "Farbe" aufweisen muß, d.h. derart, wie in Fig. 6 dargestellt ist, bietet ein dreiwinkliges Gitter die Möglichkeit, Muster mit weniger Farben herzuleiten. Dies könnte die Kosten und die Komplexität des Erfassungskopfs 16 reduzieren.
- Bei einem sechseckigen Gitter besitzt jede Zelle sechs Nachbarn (und keine Zelle, die sie an nur einem Punkt berührt). In bestimmten 'Einpixel'-Erfassungsumgebungen kann die Möglichkeit, daß sich der Erfassungskopf direkt von einer Zelle zu einer anderen Zelle bewegt, die dieselbe nur in einem Punkt berührt, nicht ausgeschlossen werden. In diesem Fall bietet das sechseckige Gitter wiederum die Möglichkeit, Schemata mit weniger Farben zu koordinieren (und/oder Grauschattierungen).
Als Beispiel zeigt Fig. 34 einen Abschnitt eines sechseckigen Gitters mit einer mittigen hexagonalen Zelle 350 und den sechs hexagonalen Zellen 351 bis 356, die dieselbe umgeben. Eine "horizontale" Achse Ap und eine "vertikale" Achse Bp sind definiert, wobei die hexagonalen Zellen in Reihen parallel zu diesen Achsen verlaufen. Die Zellen müssen gefärbt werden, um die Elementewerte der zwei binären Sequenzen, die sich parallel zu den Achsen Ap bzw. Bp erstrecken, darzustellen; Elementewerte "i" und "j" für die sich horizontal erstreckende Sequenz und "k" und "l" für die sich vertikal erstreckende Sequenz sind in Fig. 34 gezeigt. Zum Implementieren eines Übergangscodierschemas sind vier Codierfunktionen h&sub0;, h&sub1;, v&sub0;, v&sub1; auf eine Art und Weise definiert, die ähnlich dem Fall des rechtwinkligen Musters, das oben detailliert beschrieben ist, ist. Wenn die mittige hexagonale Zelle 350 mit "c" gefärbt ist, sind die Farben der umgebenden Zellen wie in Fig. 34 gegeben, wobei z.B. vk&supmin;¹ (c) die Farbe "y" bedeutet, welche die Eigenschaft hat, daß vk (y) = c. Es sei bemerkt, daß die Anwendung einer einzigen Funktion notwendig ist, um die Farbe der Zellen, die benachbart zu der Zelle 350 sind, entlang der horizontalen und der vertikalen Achse zu bestimmen, daß jedoch die Anwendung einer doppelten Funktion benötigt wird, um die Farbe der Zellen 356 und 353 zu bestimmen. Diese letztgenannten Zellen stehen zu der Zelle 350 effektiv in der gleichen Beziehung, wie diagonale Zellen in dem Fall des rechtwinkligen Musters.
Wenn die vier Codierfunktionen folgende Form aufweisen:
h&sub0;(c) = c+1 (mod 9)
h&sub1;(c) = c-1 (mod 9)
v&sub0;(c) = c+3 (mod 9)
v&sub1;(c) = c-3 (mod 9)
Sind die weiteren Übergänge von einer Zelle wirksam entlang ihrer Diagonale c+2, c-2, c+4, c-2.
Tatsächlich sind sechseckige Zellen wie quadratische Zellen, bei denen es nur zulässig ist, sich auf einer Diagonale zu bewegen (Beispiel diagonal aufwärts und links oder abwärts und rechts, jedoch nicht aufwärts und rechts oder abwärts und links). Somit wird ein beliebiges Codierschema, daß für ein rechtwinkliges Gitter (ohne Separatoren) arbeitet, bei dem diagonale Bewegungen erlaubt sind, auch für sechseckige Gitter arbeiten.
Es ist offensichtlich, daß bei einem Muster, daß auf einer sechseckigen Anordnung von Zellen basiert, ein Teilmuster bezüglich des Musters in sechs verschiedenen Ausrichtungen angeordnet sein kann und nicht in den vier Ausrichtungen, die bei einem rechtwinkligen Muster möglich sind. Dies muß selbstverständlich berücksichtigt werden, wenn bestimmt wird, welche Ausrichtungsinformationen geliefert werden müssen. Wenn zwei ausrichtbare Sequenzen in dem sechseckigen Muster codiert sind, wie in dem Beispiel, das oben gegeben ist, muß das Teilmuster in einer der zwei Ausrichtungen aus den möglichen sechs erfaßt werden, wobei Ausrichtungsinformationen, die dieses ermöglichen, mittels einer der drei Verfahren 200, 201, 203, die oben bezugnehmend auf Fig. 5 beschrieben sind, geliefert werden müssen.
Wie bereits bemerkt wurde, muß der physikalische Parameter, der verwendet ist, um die Mustermerkmale zu codieren, nicht optisch/infrarot sein, sondern könnte die Oberflächenrauhigkeit, die magnetische Permeabilität oder eine andere oder mehrere eines ganzen Bereichs von anderen möglichen physikalischen Charakteristika sein.
Die Einrichtung, die verwendet ist, um das Muster 20 zu erfassen, muß nicht einstückig mit dem Element aufgebaut sein, das verwendet ist, um auf eine spezielle Position auf dem Muster zu zeigen, deren Standort gefunden werden soll. Z.B. könnte ein fester (oder ein drehbar befestigter) Sensor verwendet werden, während das Zeigeelement ein Paar von Querdrähten sein könnte (entweder real oder durch ein elektronisches Bild aufgebaut, das über ein Bild des Musters 20 bewegt wird).
Es ist offensichtlich, daß die ausrichtbaren und komplementär ausrichtbaren binären Sequenzen, die oben beschrieben sind, ebenfalls verwendet werden können, wenn eine lineare Positionserfassung erforderlich ist und nicht die Positionserfassung über einer Fläche.

Anhang

Der folgende vierteilige Anhang ist als integrierter Teil dieser Beschreibung eingeschlossen:
Anhang A - ein Verfahren zum Aufbauen binärer Arrays mit der Fenstertechnikeigenschaft
Anhang B - Herleitung von ausrichtbaren und komplementär ausrichtbaren Sequenzen
Anhang C - Finden der Position einer Sequenz
Anhang D - Positionsfinden in einem pseudozufälligen Array

ANHANG A

Ein Verfahren zum Aufbauen binärer Arrays mit der Fenstertechnikeigenschaft.

1 Einleitung

Wir wollen binäre Arrays mit der Eigenschaft aufbauen, daß jedes k&sub1; x k&sub2;-Teilarray höchstens einmal in dem Array erscheint. Es ist einfach, binäre Sequenzen der Länge 2k-1 derart aufzubauen, daß jede Teilsequenz der Länge k höchstens einmal erscheint, wobei solche Sequenzen m-Sequenzen genannt werden. Wir werden ein Paar von m-Sequenzen verwenden, um ein Array mit der Fenstertechnikeigenschaft auf zubauen. Es ist von Interesse, in der Lage zu sein, die Position eines Teilarrays in dem Array zu finden, und wir werden ein Verfahren für dasselbe darlegen. Ein schwierigeres Problem besteht darin, das gleiche durchzuführen, wenn die Ausrichtung des Arrays nicht bekannt ist. Wir werden ferner ein Verfahren zum Aufbauen von Arrays darlegen, bei dem, ein k&sub1; x k&sub2;-Teilarray vorausgesetzt, es möglich ist, nicht nur die Position in dem Array zu bestimmen, sondern ferner die Ausrichtung des Arrays. Dieser Aufbau wird eine Sequenz erfordern, in der jede Teilsequenz der Länge k höchstens einmal erscheint, und wenn eine solche Sequenz auftritt, ihre Umkehrung nicht auftritt. Diese Sequenzen werden ausrichtbare m-Sequenzen genannt.

2 Aufbau

Es seien = (s&sub0;, s&sub1;,..., s&sub2;k&sub1;&submin;&sub2;) und t = (t&sub0;, t&sub1;,..., t&sub2;k&sub2;-1&submin;&sub2;) binäre m-Sequenzen. Wir bauen wie folgt ein (2k¹-1) x 2k2-1 Array auf. Die erste Spalte des Arrays ist gerade die Sequenz s. Um die zweite und nachfolgende Spalten zu bilden, blicken wir auf die Sequenz t. Wenn t&sub0; = 0, ist die zweite Spalte gerade wieder s, während, wenn t&sub0; = 1, die zweite Spalte s zirkular um eine Stelle abwärts verschoben ist, d.h. (s&sub2;k&sub1;&submin;&sub2;, s&sub0;,..., s&sub2;k&sub1;&submin;&sub3;). Die übrigen Spalten werden auf eine ähnliche Art und Weise aufgebaut: wenn ti-1 = 0, dann ist die (i+1)te Spalte wiederum die i-te Spalte, während, wenn ti-1 = 1, die (i+1)te Spalte die i-te Spalte, zirkular um einen Platz nach unten verschoben ist.

3 Finden der Position

Wir geben nun ein Verfahren zum Bestimmen der Position eines gegebenen k&sub1; x k&sub2;-Teilarrays, wobei angenommen wird, daß wir ein Verfahren zum Finden der Positionen von Teilsequenzen von s der Länge k&sub1; und der Teilsequenzen von der Länge k&sub2;-1 besitzen. Es sei angenommen, daß unser Teilarray Spalten &sub0;, &sub1;, ..., k2-1 besitzt. Dann ist &sub0; eine Teilsequenz von der Länge k&sub1; und wir können seine Position, angenommen r, finden. Wir blicken nun auf die anderen Spalten unseres Teilarrays und bestimmen deren relative Verschiebungen. Dies ist einfach, da für jedes i entweder i = i+1 gilt, wobei in diesem Fall die Verschiebung 0 ist, oder i ≠ i+1 gilt, wobei in diesem Fall die Verschiebung Eins ist. Wir sind somit in der Lage, eine Teilsequenz von der Länge k&sub2;-1 aufzubauen und können so deren Position, angenommen w, finden. Dann ist die horizontale Position unseres Teilarrays gerade w. Wenn wir eine Tabelle von sich anhäufenden Verschiebungen behalten (berechnet durch das Hinzufügen aufeinanderfolgender Elemente von t), können wir die Verschiebung der w-ten Spalte nachschlagen und dieselbe zu r modulo 2k1-1 addieren, um die vertikale Position unseres Teilarrays zu erhalten.

4 Beispiel

Es sei angenommen, daß k&sub1;=k&sub2;=3. Wir wählen = (0,0,1,0,1,1,1) und = (0,1,1). Dann ist das Array:
0011
0001
1100
0010
1101
1110
1111
Es sei angenommen, daß wir die Position des folgenden Teilarrays finden wollen:
100
010
101
Die erste Spalte ist (1, 0, 1), die in s an der Position 2 erscheint. Das Muster der Verschiebungen ist (1, 1), das in an der Position 1 erscheint. Die Tabelle der sich anhäufenden Verschiebungen ist (0, 0, 1, 2), genauso wie die vertikale Position des Teilarrays 2+0=2 ist. Die Position des Teilarrays ist dann (1,2), deren Richtigkeit leicht überprüft werden kann.

5 Ausrichtbare Arrays

Es ist möglich, ausrichtbare m-Sequenzen aufzubauen. Dies wird uns erlauben, Arrays aufzubauen, bei denen es möglich ist, nicht nur die Position eines Teilarrays zu bestimmen, sondern ferner zu sagen, ob sie Kopf-stehend ist oder nicht.
Wenn wir den Aufbau, der oben beschrieben ist, mit t, einer ausrichtbaren m-Sequenz durchführen, sagt uns die Ausrichtung der Teilsequenz von welche Richtung das Teilarray einnimmt. Wenn alternativ s eine ausrichtbare m-Sequenz ist, gibt uns die Ausrichtung der ersten Spalte als eine Teilsequenz von ebenfalls diese Informationen.
Es wäre nützlich, in der Lage zu sein, zu sagen, ob das Teilarray um 90º gedreht wurde. In diesem Fall sind die Spalten nicht länger die Teilsequenzen von s, so daß wir nicht die obigen Verfahren verwenden können. Diese Situation sollte vernünftigerweise leicht zu identifizieren sein, doch nur, wenn k&sub1; und k&sub2; eine vernünftige Größe besitzen. Dies ist der Fall, da die Wahrscheinlichkeit, daß nachfolgende Reihen in dem ursprünglichen Teilarray alle entweder gleich oder um 1 verschoben sind, extrem gering ist.

Anhang B

Herleitung von ausrichtbaren und komplementär ausrichtbaren Sequenzen

Wir werden die Aufgabe des Findens ausrichtbarer und komplementär ausrichtbarer Sequenzen bezüglich des Findens eines Weges durch einen gerichteten Graphen ausdrücken; dies ist auf dein Gebiet von de Bruijn-Sequenzen eine Standardpraxis. Wenn wir nach Sequenzen mit einer Fensterlänge in suchen, bauen wir einen direkten Graph auf, der gewöhnlich der de Bruijn-Graph genannt wird, dessen Scheitelpunkte mit den Sequenzen der Länge (m-1) bezeichnet sind und dessen Kanten mit den Sequenzen der Länge in wie folgt bezeichnet sind. Eine Kante ist von einem Scheitelpunkt, der mit (a&sub0;, a&sub1;, ..., am-2) bezeichnet ist, zu einem anderen Scheitelpunkt, der mit (b&sub0;, b&sub1;, ...., bm-2) bezeichnet ist, gezeichnet, wenn und nur wenn:
a&sub1; = b&sub0;, a&sub2; = b&sub1;,..., am-2 = bm-3.
Wenn diese Bedingung erfüllt ist, wird die Kante folgendermaßen bezeichnet:
(a&sub0;, a&sub1;,....,am-2, bm-2) = (a&sub0;, b&sub0;, ...., bm-3, bm-2).
Wir sehen, daß deshalb ein Weg durch den Graphen als eine Sequenz angesehen werden kann, deren aufeinanderfolgende Fenster der Sequenz aufeinanderfolgenden Kantenbezeichnungen entsprechen. Alle Sequenzen der Länge m, mit Ausnahme der Sequenzen, die nur aus Nullen und nur aus Einsen bestehen, treten als Kantenbezeichnungen auf. Diese treten nicht auf, da sie einen Scheitelpunkt mit sich selbst verbinden würden, was nicht erlaubt ist.

Ausrichtbare Sequenzen

Wir können eine grobe obere Grenze für die Länge einer ausrichtbaren Sequenz der Fensterlänge in erhalten. Die Gesamtzahl der Fenster der Länge m ist 2m. Wenn m gerade ist, ist die Anzahl der Palindrome gleich 2m/2, wohingegen, wenn in ungerade ist, die Anzahl der Palindrome gleich 2(m+1)2 ist. Der Rest der Fenster kann in Paaren gruppiert werden, jeweils eines mit seiner Umkehrung. Die maximale Länge einer ausrichtbaren Sequenz ist dann
wenn m gerade ist
wenn m ungerade ist.
Es scheint jedoch, daß diese obere Grenze niemals erreicht wird. Eine ausrichtbare Sequenz kann als ein Weg durch den de Bruijn-Graphen angesehen werden, der die Eigenschaft hat, daß, wenn eine Kante in dem Weg auftritt, die Kante mit der umgekehrten Bezeichnung nicht auftritt. Insbesondere kann keine Kante mit einer Palindrom-Bezeichnung auftreten. Unsere Aufgabe schließt ein, Eulersche Wege in einem gerichteten Graphen zu finden (das sind Wege, die jede Kante genau einmal verwenden). Es ist im allgemeinen einfach, einen Eulerschen Weg in einem Graph zu finden, wobei mehrere Algorithmen existieren (siehe z.B. Frank Harary, Graph Theory. Addison-Wesley, Reading, Mass., 1972).
Ein gerichteter Graph besitzt einen Eulerschen Weg, wenn er verbunden ist, und jeder Scheitelpunkt (mit Ausnahme möglicherweise der Start- und End-Scheitelpunkte) die gleiche Anzahl von ankommenden und abgehenden Kanten besitzt. Dies ist für den de Bruijn-Graphen tatsächlich der Fall. Wir wissen, daß es nicht erlaubt ist, Kanten mit Palindrom-Bezeichnungen zu verwenden, so daß wir dieselben entfernen müssen. Um die Euler-Eigenschaft beizubehalten, müssen wir tatsächlich vollständige Zyklen entfernen, die Palindrome enthalten. Dies ist daher der erste Schritt, Zyklen, die Palindrome enthalten, aufzubauen und zu entfernen. Die zweite Phase besteht darin, einen Weg durch den restlichen Graphen zu finden. Ein Standardverfahren besteht darin, zuerst einen überspannenden Baum aufzubauen, alle Kanten in diesem Baum zu markieren und dann einen Weg zurück durch den Graphen zu zeichnen, wobei wenn möglich immer eine unmarkierte Kante gewählt wird.
Wir können auch ausrichtbare Sequenzen der Fensterlänge 2m+1 rekursiv aus ausrichtbaren Sequenzen der Fensterlänge 2m aufbauen, unter Verwendung des Lempel-Homomorphismus. Dieser bildet binäre Sequenzen der Länge t auf binäre Sequenzen der Länge t-1 ab und ist definiert durch:
(x&sub0;,...., xt-1)T(x&sub0; x1,....,xt-2 xt-1)
Die inverse Abbildung von (y&sub0;,....yt-2) ist der Satz {(u&sub0;,....,ut-1) (vo,....,vt-1)}, wobei u&sub0; = 0, v&sub0; = 1 und
und
Wenn wir eine ausrichtbare Sequenz der Länge M und einer Fensterlänge 2m haben, die mit 2m-1 Nullen beginnt und mit 2m-1 Einsen endet, und deren inverse Abbildung unter dem Lempel-Homomorphismus betrachten, erhalten wir zwei Sequenzen, von denen eine mit 2m Nullen beginnt und mit einer Sequenz von 2m abwechselnden Nullen und Einsen endet, und die andere gleich dem Komplement derselben ist. Wenn wir die zweite Sequenz umkehren und die zwei Sequenzen zusammenfügen, wobei die Sequenz der abwechselnden Nullen und Einsen amalgamiert wird, erhalten wir eine Sequenz der Länge 2M + 2 - 2m, die mit einer Fensterlänge 2m + 1 ausrichtbar ist.
Ein Beispiel einer ausrichtbaren Sequenz der Fensterlänge ist nachfolgend gegeben:

Komplementär ausrichtbare Sequenzen

In diesem Fall sind wir in der Lage, Sequenzen einer maximalen Länge aufzubauen, wenn die Fensterlänge ungerade ist, jedoch sind wir nicht in der Lage, verglichen mit dem ausrichtbaren Fall irgendetwas zu verbessern, wenn die Fensterlänge gerade ist. Wenn die Fensterlänge m ungerade ist, kann eine Sequenz der Länge m in Paaren angeordnet werden, indem jede Sequenz der Umkehrung ihres Komplements zugeordnet wird, und jede komplementär ausrichtbare Sequenz kann höchstens eines jedes Paars als eine Teilsequenz enthalten. Die Anzahl dieser Paare ist eindeutig 2m-1. eine Sequenz der Länge n enthält n-m+1 Teilsequenzen der Länge m, so daß, wenn n die Länge einer komplementär ausrichtbaren Sequenz mit der Fensterlänge m ist, wir ableiten können, daß:
n - m + 1 < = 2m-1
und somit
n < = 2m-1 + m - 1
Wenn wir eine Fenstertechniksequenz aufbauen könnten, deren Teilsequenzen jeweils mehr Nullen als Einsen enthalten, wäre dieselbe automatisch komplementär ausrichtbar, da die Umkehrung des Komplements einer beliebigen Teilsequenz mehr Einsen als Nullen haben würde, und somit nicht selbst eine Teilsequenz wäre. Wir werden dies durchführen, indem wir auf einen Teilgraphen des de Bruijn-Graphen blicken. Dieser Teilgraph besteht aus allen Scheitelpunkten und Kanten, deren Bezeichnungen höchstens (m-1)/2 Einsen besitzen. Dann ergibt jeder beliebige Eulersche Weg durch diesen gerichteten Graphen eine komplementär ausrichtbare Sequenz maximaler Länge. Der folgende Algorithmus ergibt eine komplementär ausrichtbare Sequenz maximaler Länge. Die aufeinanderfolgenden Fenster der Sequenz sind durch w gegeben.
o Es sei = (w(0), w(1),...,w(m-1) auf (0,...,0) eingestellt.
o Wenn (w(1), ...,w(m-1) weniger als (m-1)/2 Einsen enthält, dann
- wenn wir noch nicht (w(1),...., w(m-1), 1) gesehen haben, dann
* setze = (w(1), ...,w(m-1), 1)
- sonst wenn wir noch nicht (w(1),...,w(m-1), 0) gesehen haben, dann
* setze = (w(1),...,w(m-1), 0)
- sonst
* stop
o sonst
- sonst wenn wir nicht schon (w(1),...,w(m-1), 0) gesehen haben, dann
* setze (w(1),...,w(m-1), 0)
- sonst
* stop.
In anderen Worten heißt das, daß wir zu der Sequenz 1 hinzufügen, wann immer wir können, und sonst 0 hinzufügen.
Wenn die Fensterlänge gerade ist, können wir einfach auf den Teilgraphen des de Bruijn-Graphen blicken, indem jede Bezeichnung höchstens (m-2)/2 Einsen besitzt, was eine komplementäre Ausrichtbarkeit garantieren würde. Dies ergibt jedoch keine langen Sequenzen, da alle Sequenzen mit m/2 Einsen, die keine komplementären Palindrome sind, jedoch schon von der Betrachtung durch dieses Verfahrens ausgeschlossen wurden.

Anhang C

Finden der Position einer Sequenz

1 Einführung

Dieser Anhang beschreibt die Berechnungen, die notwendig sind, um die Position einer Sequenz in der Ausgabe eines linearen Rückkopplungsschieberegisters zu bestimmen. Ein ähnlicher Lösungsansatz ist in "Equivalence of Nonlinear Shift-Registers" von J.L. Massey und R.W. Lier; IEEE Transactions on Information Theory VcL IT-10, Nummer 4, Oktober 1964, Seiten 378 - 379, offenbart.

2 Schreibweise

Es sei angenommen, daß wir ein lineares Rückkopplungsschieberegister mit Koeffizienten c&sub0;, c&sub1;, c&sub2;,...,ck-1 besitzen. Die Matrix C sei
Die Zustände des Schieberegisters seien &sub0;..., n-1, und für jedes r sei sr die Matrix, die durch Schreiben aller r,..., r+k-1 als eine Spalte und durch Zusammenfügen derselben, um eine binäre k x k-Matrix zu bilden, erhalten wird.
3 GF(2k)
Das Feld GF(2k) besteht aus allen Polynomen eines kleineren Grades als k mit binären Koeffizienten. Ein solches Element von GF(2k) besitzt folgende Form
a&sub0; + a1α + ... + ak-1 αk-1
Wobei alle ai gleich Null oder Eins sind. Selbstverständlich können dieselben als binäre Sequenzen der Länge k angenommen werden. Es wird eine komponentenweise Addition derart durchgeführt, daß es wie ein bitweises Exklusiv-OR aussieht. Eine Multiplikation ist schwieriger - Elemente werden als Polynome in α multipliziert, wobei dann höhere Werte von α unter Verwendung eines primitiven Polynoms reduziert werden.
(α) = c&sub0; + c1α + ... + ck-1 αk-1 + αk = 0.
Es sei P die k x k-Matrix mit den Einträgen in GF(2k)
wobei dann P die Eigenschaft hat, daß P-1CP diagonal ist.

4 Der Algorithmus

Der Algorithmus besitzt zwei Teile: der erste reduziert das Problem, auf das der diskreten Logarithmen in GF(2k), während der zweite den diskreten Logarithmus berechnet. Beide Teile des Algorithmusses bestehen aus einer Vorberechnungsphase und einer Phase, die jedesmal ausgeführt werden muß. Es gibt mehrere verschiedene Möglichkeiten, diskrete Logarithmen zu berechnen, und es ist nicht klar, welche in diesem Fall die beste sein würde. Der Coppersmith-Algorithmus ist für große Felder wirksam, ist jedoch ziemlich kompliziert und schließt faktorisierende Polynome ein. Der Pohlig-Silver-Hellman-Algorithmus ist viel einfacher und nachfolgend beschrieben.

4.1 Erster Teil

4.1.1 Vorberechnung

S&sub0; und die Inverse desselben müssen berechnet werden. S&sub0; wird durch Durchlaufen des Schieberegisters, bis die ersten k Zustände erhalten sind, berechnet. Es ist eine binäre k x k-Matrix, so daß das Finden der Inversen derselben einfach sein sollte.

4.1.2 Rest der Berechnung

Aus dem gegenwärtigen Zustand sr muß die Matrix sr berechnet werden, indem das Schieberegister durchlaufen wird, bis die nächsten (k-1) Zustände erhalten sind. Diese Matrix muß mit der Matrix S&sub0;&supmin;¹ multipliziert werden, um X = SrS&sub0;&supmin;¹ zu erhalten. Diese sind beide binäre k x k-Matrizen.
Der nächste Punkt, der berechnet werden muß, ist x, das Element in der ersten Reihe und der ersten Spalte von P&supmin;¹XP. Um dies durchzuführen, muß die erste Spalte von XP berechnet werden. Nun ist X eine binäre k x k-Matrix, und P ist eine k x k-Matrix mit Einträgen in GF(2k), so daß dies höchstens k² Additionen in GF(2k) darstellen sollte. Um x zu berechnen, sind k Multiplikationen und k Additionen in GF(2k) nötig.
Dieses Element x wird nun dem zweiten Teil des Algorithmusses übergeben.

4.2 Zweiter Teil (nach Pohlig, Silver und Hellman)

Zur Vereinfachung der Schreibweise sei Q für 2k-1 geschrieben. Q kann als das Produkt seiner primären Faktoren geschrieben werden:
Q = Πpi ni.
Das Ziel dieses Teils des Algorithmusses ist es, r zu finden, so daß gilt x = αr.

4.2.1 Vorberechnung

Für jedes pi muß eine Tabelle der pi-ten Einheitswurzeln berechnet werden. Diese besteht aus den Elementen αt(Q/pi), für t = 0,1,...(pi-1).

4.2.2 Rest der Berechnung

Der Gedanke besteht hier darin, wiederum r modulo jedes pini zu berechnen, und dann das chinesische Rest-Theorem zu verwenden, um die Ergebnisse zu kombinieren, um r zu erhalten.
Es sei p = pi und es sei angenommen, daß ni = 1. Dann muß die Größe y = xQ/P berechnet werden. Dies kann auf die gewöhnliche Art durch wiederholte Quadrierung und Multiplikation geschehen. Nun ist y eine p-te Einheitswurzel, so daß sie in der vorberechneten Tabelle nachgeschlagen werden kann. Wenn y = αt(Q/p) ist, dann gilt: r t (mod p).
Wenn ni> 1, dann wird der obige Prozeß ni-mal durchgeführt, wie folgt. Zuerst wird y&sub0; = xQ/P berechnet und in der Tabelle nachgeschlagen. Es sei angenommen, daß y&sub0; = αto(Q/p). Dann wird y&sub1; = (xα-to)Q/P berechnet und in der Tabelle nachgeschlagen. Es sei angenommen, daß y&sub1; = αt1(Q/P). Dieser Prozeß wird fortgesetzt und schließlich gilt
r t&sub0; + t&sub1; p+ ... +tni-1 pni-1 (mod pni).
Es gibt eine Möglichkeit, die Anzahl der Vergleiche zu verringern, die notwendig sind, um y in der Tabelle nachzuschlagen, mit dem Aufwand des Durchführens von mehr Multiplikationen, jedoch ist es wahrscheinlich für die Größe der vorliegenden Felder nicht vernünftig.
Das Ergebnis der obigen Berechnungen wird als ein Satz von Nummern ui eingestellt, so daß r ui (mod pi ni) für jedes i. Es ist nun einfach eine Sache des Anwendens des chinesischen Rest-Theorems, um den Wert von r zu erhalten. Es sei Mi = Q/pi ni und Ni sei derart, daß Mi Ni 1 (mod pi ni). Dies kann selbstverständlich alles vorher berechnet werden. Dann gilt: r Σ ui Mi Ni (mod Q).

Anhang D

Finden der Position in einem pseudozufälligen Array

1 Einführung

Dieser Anhang beschreibt eine Verallgemeinerung für zwei Dimensionen der Positionsfindungsberechnung für eine Sequenz, die im Anhang C beschrieben ist.

2 Schreibweise

Unter Voraussetzung eines pseudozufälligen Arrays A der Größe n&sub1; = 2k1-1 mal n&sub2;=2k1k2-1)/n1, gibt es Paar von Rekursionen, die A erzeugen, eine für eine vertikale Bewegung und eine für eine horizontale Bewegung. Wenn wir ein k&sub1; mal k&sub2;-Teilarray von A als einen Vektor der Länge k&sub1;k&sub2; schreiben, indem jede der Spalten wiederum derart ausgeschrieben wird, daß
geschrieben wird als
kann jede der zwei Rekursionen als k&sub1;k&sub2; mal k&sub1;k&sub2;-Matrix geschrieben werden, die auf diese Vektoren wirkt. Die Matrix für die vertikale Rekursion sei C und die für die horizontale Rekursion sei D. Da die Spalten Kopien einer pseudozufälligen Sequenz sind, besteht C tatsächlich aus k&sub2; Kopien einer k&sub1; mal k&sub1;-Matrix C&sub0;, angeordnet entlang der Diagonale:
Wenn wir nun den Vektor, der dem Teilarray mit der oberen linken Ecke bei (r,t) entspricht, mit r,t bezeichnen, haben wir
r,t = CrDt 0,0.

3 Der Algorithmus

Wir finden eine Matrix P, so daß P&supmin;¹DP diagonal ist und dann P&supmin;¹CP ebenfalls diagonal ist. Somit ist
P&supmin;¹CrDtP = (P&supmin;¹CrP) (P&supmin;¹DtP) = (P&supmin;¹CP) r (P&supmin;¹DP) t
ebenfalls diagonal.
Durch Wiederholen des gleichen Spiels wie in dein eindimensionalen Fall erhalten wir CrDt aus r,t und 0,0 indem die Matrizen S0,0 und sr, t aufgebaut werden. In dem eindimensionalen Fall bewegten wir uns einfach entlang der Sequenz, um diese Matrizen aufzubauen; im zweidimensionalen Fall können wir uns selbstverständlich vertikal, horizontal oder in einer Kombination dieser beiden bewegen, vorausgesetzt, daß die resultierenden Matrizen nicht singular sind.
Wir können dann CrDt unter Verwendung der vorberechneten Matrix P diagonalisieren und den ersten Eigenwert betrachten. Wenn der erste Eigenwert von C α ist, und der erste Eigenwert von D β ist, ist der erste Eigenwert x von CrDt gleich αrβt.
Wir wissen, daß Cn1 = Dn2 = I, die Identitätsmatrix. Wenn n&sub1; und n&sub2; ohne gemeinsamen Teiler sind, können wir xn¹ = βtn¹ und xn2 = αtn2 berechnen, und auf diesen zwei Elementen in den geeigneten Feldern diskrete logarithmische Berechnungen durchführen, um t bzw. r zu finden.

4 Beispiel

Wir werden das pseudozufällige 3 x 5-Array von [1] verwenden. Dieses Array ist
Die Matrizen zur Bewegung in die horizontale und die vertikale Richtung sind jeweils wie folgt gegeben.
und
Wir berechnen zuerst P, so daß P&supmin;¹DP diagonal ist. Die Eigenwerte von D genügen der Gleichung x&sup4;+x³+x²+x+1 = 0. Wenn wir eine der Wurzeln dieser Gleichung mit β bezeichnen, sind die anderen Wurzeln β², β³ und β&sup4; = β³+ß²+ß+l. Die Matrix P ist dann gleich
wobei wir aus dieser P&supmin;¹ zu folgender Matrix berechnen
Wir berechnen nun P&supmin;¹CP und können überprüfen, daß dieselbe tatsächlich diagonal ist.
Daher sehen wird, daß α, der erste Eigenwert von C, gleich β² + β³ ist. Es sei angenommen, daß der Anfangszustand des pseudozufälligen Arrays der Vektor (0010) ist, und daß der Zustand, dessen Position wir versuchen, zu finden, (1001) ist. Wir müssen nun die Matrizen s0,0 und sr,t bilden. In diesem kleinen Fall müssen wir uns tatsächlich horizontal bewegen, da uns eine vertikale Bewegung eine singulare Matrix liefert. Dies ist der Fall, da wir ein 4 x 4-Array benötigen, sich in unserem pseudozufälligen Array jedoch nur drei Reihen befinden. Eine horizontale Bewegung liefert uns jedoch in der Tat nicht-singulare Matrizen.
und
somit haben wir
Die erste Spalte von XP ist daher
Das bedeutet, daß das erste Element x von P&supmin;¹XP wie folgt lautet:
β&sup4;(β+1) + (β+β²(β³+β+1) +1. (β²+β) + (β²+β³) (ß³+1) = 1 + ß.
Wir müssen daher r und t finden, so daß gilt αrβt = x = 1 + β. Es sei bemerkt, daß bei diesem kleinen Beispiel beide Felder, in denen wir diskrete Logarithmen berechnen, erster Ordnung sind, und wir also nicht in der Lage sein werden, den Silver-Pohlig-Hellman-Algorithmus zu verwenden. Da die Felder so klein sind, können wir die Logarithmen jedoch einfach direkt berechnen. Bei einem großen Fall würde jedoch der Silver-Pohlig-Hellman-Algorithmus verwendet werden.
Wir berechnen zuerst y = x³, um t zu erhalten. Nun gilt x³ = (1+β)³ = 1+β+β²+β³ = β&sup4;, so daß wir ableiten, daß 3t 4 (mod 5) oder daß t = 3. Genauso berechnen wir x = x&sup5; = (1+β&sup5;) = 1+β&sub2;+β³ = 1 + α = α², und somit 5r = 2 (mod 3) oder r = 1. Wir fanden somit heraus, daß die Position des Vektors (1001) (3,1) ist, was bezugnehmend auf das Array überprüft werden kann.

Literaturverweis

[1] F.J. MacWilliams und J.J.A. Sloane. Pseudo-Random Sequences and Arrays. Proceedings of the IEEE, 64 Nr. 12:1715-1728, 1976.

Claims

1. Positionserfassungsvorrichtung mit folgenden Merkmalen:

-- einem Musterelement (10) mit einer Anordnung von Markierungen (15), die zusammen ein zweidimensionales Muster (20) darstellen, das Merkmale aufweist, die das Muster dadurch zu einem Fenstertechnikmuster machen, daß ein beliebiger lokaler Abschnitt des Musters einer gegebenen Größe bezüglich seiner Merkmale, hierin ein "Teilmuster", wenn isoliert betrachtet, derart durch seine Merkmale charakterisiert ist, daß es möglich ist, den Standort des Teilmusters für zumindest eine Ausrichtung des Teilmusters relativ zu dem Muster zu bestimmen;

-- einem Anzeigeelement (11), das relativ zu dem Musterelement (10) über die Anordnung von Markierungen (15) bewegbar ist;

-- einer Teilmuster-Detektoreinrichtung (11, 12) zum Herleiten von Teilmusterdaten, die ein Teilmuster, das örtlich dem Anzeigeelement (11) zugeordnet ist, in der zumindest eine Ausrichtung des Teilmusters relativ zu dem Muster (20) darstellen, wobei die Teilmuster-Detektoreinrichtung (11, 12) eine Sensoreinrichtung (16) einschließt, um die Markierungen (15) derart zu erfassen, daß für eine beliebige Position des Anzeigeelements (11) die Erfassungseinrichtung (16) wirksam ist, um einen Abschnitt des Musters (20) zu erfassen, der in dem Ortsbereich des Anzeigeelements (11) liegt; und

-- einer Positionsbestimmungseinrichtung (13), die einen Speicher (17) einschließt, der Musterdaten hält, die das Fenstertechnikmuster (20) darstellen, wobei die Positionsbestimmungseinrichtung (13) auf die Teilmusterdaten anspricht, die von der Detektoreinrichtung (11, 12) hergeleitet werden, um bezugnehmend auf die Musterdaten die Position des Anzeigeelements (11) relativ zu dem Musterelement (10) zu bestimmen;

dadurch gekennzeichnet, daß die Sensoreinrichtung (16) wirksam ist, um einen Abschnitt des Musters (20) zu erfassen, der eine kleinere Größe besitzt als das Teilmuster, und daß die Detektoreinrichtung (11, 12) wirksam ist, um die Ausgabe der Sensoreinrichtung (16) derart zu verarbeiten, daß während der Bewegung der Sensoreinrichtung (16) über das Muster (20) Teilmusterdaten eines gesamten Teilmusters nacheinander aufgebaut werden.

2. Positionserfassungsvorrichtung gemäß Anspruch 1, bei der:

(a) die Merkmale des Musters (20) erkennbar eine regelmäßige Anordnung bilden, bei der, wenn ein beliebiges gegebenes Teilmuster des Musters isoliert von dem Muster (20) betrachtet wird, das Teilmuster in einer beliebigen von M möglichen Ausrichtung bezüglich zu dem Muster liegen kann, wobei M eine positive ganze Zahl größer als Null ist.

(b) das Fenstertechnikmuster (20) derart ist, daß ein beliebiges gegebenes Teilmuster für N der M möglichen Ausrichtungen korrekt in dem Muster lokalisiert werden kann, wobei N eine positive ganze Zahl in dem Bereich 0< N≤M ist; und

(c) die Teilmuster-Detektoreinrichtung (11,12) auf die regelmäßige Anordnung von Merkmalen anspricht, um das Teilmuster in dein Ortsbereich des Anzeigeelements zu identifizieren und um die Teilmusterdaten der Positionserfassungseinrichtung zu liefern, welche das Teilmuster in einer der N der M möglichen Ausrichtungen relativ zu dem Muster darstellen, in welchem dasselbe korrekt lokalisiert werden kann.

3. Positionserfassungsvorrichtung gemäß Anspruch 2, bei der die Merkmale erkennbar in Reihen und Spalten angeordnet sind, die sich parallel zu einer jeweiligen ersten und zweiten Koordinatenachse erstrecken, wobei jedes Merkmal in einer fiktiven Zelle gebildet ist, die eine Linienberührung mit einer Mehrzahl von benachbarten derartigen Zellen aufweist.

4. Positionserfassungsvorrichtung gemäß Anspruch 3, bei der die Zelle einen Linienkontakt mit vier benachbarten Zellen aufweist, M einen Wert 4 aufweist und N einen der Werte 1,2 und 4 aufweist.

5. Positionserfassungsvorrichtung gemäß Anspruch 3 oder 4, bei der die Merkmale dazu dienen, zumindest einen Teil eines zweidimensionalen Fenstertechnikarrays zu codieren, welches Reihen und Spalten von Elementen aufweist, die sich parallel zu der ersten bzw. der zweiten Koordinatenachse erstrecken.

6. Positionserfassungsvorrichtung gemäß Anspruch 5, bei der das Array ein pseudozufälliges binäres Array ist.

7. Positionserfassungsvorrichtung gemäß Anspruch 5, bei der das Array aus einer ersten und einer zweiten binären Sequenz der Länge in bzw. n gebildet ist, wobei m und n positive ganze Zahlen größer als Null sind, indem eine erste Spalte des Arrays aus der ersten Sequenz gebildet ist und indem jede nachfolgende (i)te Spalte, wobei "i" eine ganze Zahl in dem Bereich von 2 bis 2n+1 ist, gebildet ist, indem der Wert des (i-1)ten Element der zweiten Sequenz betrachtet wird, und

- wenn das (i-1)te Element einen ersten binären Wert besitzt, Bilden der (i)te Spalte aus der ersten Sequenz, die bezüglich der (i-1)ten Spalte nicht verschoben ist,

- wenn das (i-1)te Element einen zweiten binären Wert besitzt, Bilden der (i)te Spalte aus der ersten Sequenz, die zirkular um eine Position bezüglich der (i-1)ten Spalte verschoben ist.

8. Positionserfassungsvorrichtung gemäß Anspruch 7, bei der die erste und die zweite binäre Sequenz durch jeweilige ausrichtbare binäre Sequenzen aufgebaut sind, von denen jede die Eigenschaft besitzt, daß, wenn eine Fensterlängen-Teilsequenz in der Sequenz auftritt, deren Umkehrung nicht auftritt.

9. Positionserfassungsvorrichtung gemäß Anspruch 5, bei der das Array durch das Kombinieren zweier Fenstertechniksequenzen gebildet ist, welche sich parallel zu der jeweiligen der ersten und der zweiten Koordinatenachse erstrecken, wobei jedes Element des Arrays eine spezielle Kombination von Werten der entsprechenden Elemente der Sequenzen darstellt.

10. Positionserfassungsvorrichtung gemäß Anspruch 9, bei der die Sequenzen aus der Gruppe der folgenden Sequenzen ausgewählt sind:

(a) de Bruijn-Sequenzen;

(b) pseudozufällige binäre Sequenzen;

(c) ausrichtbare binäre Sequenzen, von denen jede die Eigenschaft hat, daß, wenn eine Fensterlängen-Teilsequenz in der Sequenz auftritt, ihre Umkehrung nicht auftritt; und

(d) komplementär ausrichtbare binäre Sequenzen, von denen jede die Eigenschaft hat, daß, wenn eine Fensterlängen-Teilsequenz in der Sequenz auftritt, die Umkehrung des bitweisen Komplements der Teilsequenz nicht auftritt.

11. Positionserfassungsvorrichtung gemäß einem beliebigen der Ansprüche 5 bis 10, bei der der Wert jedes Elements des Arrays als ein entsprechender Merkmalswert codiert ist.

12. Positionserfassungsvorrichtung gemäß Anspruch 3 oder 4, bei der die Merkmale dazu dienen, eine erste Fenstertechniksequenz von Elementen zu codieren, die sich fiktiv parallel zu der ersten Koordinatenachse erstreckt, und eine zweite Fenstertechniksequenz von Elementen, die sich fiktiv parallel zu der zweiten Koordinatenachse erstreckt.

13. Positionserfassungsvorrichtung gemäß Anspruch 12, bei der die Sequenzen aus der folgenden Gruppe von Sequenzen ausgewählt sind:

(a) de Bruijn-Sequenzen;

(b) pseudozufällige binäre Sequenzen;

14. Positionserfassungsvorrichtung gemäß Anspruch 12 oder Anspruch 13, bei der der Wert jedes Elements jeder Sequenz als eine entsprechende Änderung des Merkmalwerts codiert ist, wenn eine Bewegung zwischen benachbarten Zellen in eine Richtung parallel zu der Richtung der Größe der entsprechenden Sequenz stattfindet.

15. Positionserfassungsvorrichtung gemäß Anspruch 14, bei der die Codierung der Elementewerte derart ist, daß sichergestellt ist, daß jedes Merkmal durch seinen Wert von zumindest einem spezifischen Nachbarn, mit dem dasselbe eine Linienberührung aufweist, unterschieden ist.

16. Positionserfassungsvorrichtung gemäß Anspruch 15, bei der die Codierung derart ist, daß jedes Merkmal durch den Wert von allen seinen Nachbarn, mit denen es eine Linienberührung besitzt, unterschieden ist.

17. Positionserfassungsvorrichtung gemäß Anspruch 16, bei der die Codierung der Elementewerte eine derartige ist, daß sichergestellt ist, daß jedes Merkmal ferner durch seinen Wert von seinen Nachbarn, mit denen es eine Punktberührung besitzt, unterschieden ist.

18. Positionserfassungsvorrichtung gemäß Anspruch 11, Anspruch 14 oder Anspruch 15, bei der jedes Merkmal von zumindest einem Nachbarmerkmal, mit dem es eine Linienberührung besitzt, mittels einer entsprechenden Trennzone (26, 27) getrennt ist, die von der Teilmuster-Detektoreinrichtung als solche erfaßbar ist.

19. Positionserfassungsvorrichtung gemäß Anspruch 1, bei der die Sensoreinrichtung (16) mit dem Anzeigeelement (11) bewegbar ist und wirksam ist, um einen Abschnitt des Musters zu erfassen, der größenmäßig kleiner als ein Teilmuster ist, der jedoch eine Mehrzahl von Merkmalen einschließt, wobei die Teilmuster-Erfassungseinrichtung wirksam ist, um die Teilmusterdaten, die sich auf ein ganzes Teilmuster beziehen, aufzubauen, während die Sensoreinrichtung über das Muster bewegt wird, indem die Kontinuität der Merkmale, die während der Bewegung erfaßt werden, berücksichtigt wird.

20. Positionserfassungsvorrichtung gemäß Anspruch 5 oder Anspruch 11, bei der die Sensoreinrichtung (16) mit dem Anzeigeelement 11 bewegbar ist und wirksam ist, um einen Abschnitt des Musters zu erfassen, der einem einzelnen Merkmal entspricht, wobei die Vorrichtung eine Rauminformations-Einrichtung einschließt, um der Teilmuster- Detektoreinrichtung Rauminformationen zu liefern, die die relative Anordnung benachbarter Elementewert-Codiermerkmale betreffen, und wobei die Teilmuster-Detektoreinrichtung wirksam ist, um die Rauminformationen zu verwenden, um die Teilmusterdaten, die sich auf ein ganzes Teilmuster beziehen, aufzubauen, während die Sensoreinrichtung über das Muster bewegt wird.

21. Positionserfassungseinrichtung gemäß Anspruch 20, bei der die Rauminformations-Einrichtung Merkmale des Musters aufweist, die von der Sensoreinrichtung erfaßbar sind, während dieselbe zwischen den Elementewert-Codiermerkmalen bewegt wird.

22. Positionserfassungsvorrichtung gemäß Anspruch 21, bei der die Rauminformationen in den Werten codiert ist, die durch die Elementewert-Codiermerkmale dargestellt sind.

23. Positionserfassungsvorrichtung gemäß Anspruch 20, bei der die Rauminformations-Einrichtung eine Einrichtung aufweist, getrennt von der Sensoreinrichtung, die Informationen herleitet, die die Bewegung des Sensors betreffen, welche zumindest Informationen über Richtungsänderungen der Sensoreinrichtung einschließen.

24. Positionserfassungsvorrichtung gemäß Anspruch 20, bei der die Rauminformationen, die der Teilmuster-Detektoreinrichtung geliefert werden, nur partiell sind, und die Detektoreinrichtung wirksam ist, um eine unveränderte Bewegungsrichtung des Sensors über das Muster anzunehmen, außer und bis nach einer Anfangspositionsbestimmung ein Widerspruch zwischen den Musterdaten und Teilmusterdaten bestimmt wird.

25. Positionserfassungsvorrichtung gemäß Anspruch 1, bei der die relative Ausrichtung der Sensoreinrichtung (16) bezüglich der Anordnung der Markierungen um eine Achse, die orthogonal zu der Anordnung ist, fest ist, wodurch die Herleitung der Teilmusterdaten, die ein Teilmuster darstellen, das in der zumindest einen Ausrichtung ausgerichtet ist, mittels der Teilmuster-Detektoreinrichtung erleichtert ist.

26. Positionserfassungsvorrichtung gemäß Anspruch 5 oder Anspruch 11, bei der die relative Ausrichtung der Sensoreinrichtung bezüglich der Anordnung von Markierungen um eine Achse, die orthogonal zu der Anordnung ist, variabel ist; wobei die Vorrichtung eine Ausrichtungsinformations-Einrichtung (22) einschließt, um der Teilmuster-Detektoreinrichtung Ausrichtungsinformationen bezüglich der relativen Ausrichtung zu liefern, wobei die Teilmuster-Detektoreinrichtung diese Informationen beim Herleiten der Teilmusterdaten, die ein Teilmuster darstellen, das in die zumindest eine Ausrichtung ausgerichtet ist, verwendet.

27. Positionserfassungsvorrichtung gemäß Anspruch 26, bei der die Ausrichtungsinformations-Einrichtung Merkmale des Musters aufweist, die mittels der Sensoreinrichtung erfaßbar sind, während dieselbe zwischen den Elementewert-Codiermerkmalen bewegt wird.

28. Positionserfassungsvorrichtung gemäß Anspruch 27, bei der die Ausrichtungsinformationen in den Werten codiert sind, welche durch die Elementewert-Codiermerkmale dargestellt sind.

29. Positionserfassungsvorrichtung gemäß Anspruch 1, bei der die Positionsbestimmungseinrichtung (13) den Standort des Teilmusters in dem Muster durch Vergleichen der Merkmale des Teilmusters mit den Merkmalen des Musters bestimmt.

30. Positionserfassungsvorrichtung gemäß Anspruch 1, bei der die Positionsbestimmungseinrichtung (13) den Standort des Teilmusters in dem Muster unter Verwendung eines Index bestimmt, der bezüglich der Daten, die in den Teilmusterdaten enthalten sind, adressierbar ist, wobei jeder adressierbare Indexeintrag Teilmuster-Standortdaten hält, die der Musterposition des Teilmusters entsprechen, das die Adressierung dieses Indexeintrags bewirkt.

31. Positionserfassungsvorrichtung gemäß Anspruch 1, bei der die Positionsbestimmungseinrichtung (13) den Standort des Teilmusters in dem Muster durch Berechnung bestimmt.

32. Positionserfassungsvorrichtung gemäß einem beliebigen der vorhergehenden Ansprüche, bei der nach einer Anfangsbestimmung des Standorts des Anzeigeelements (11) eine beliebige inkrementale Änderung des Musterabschnitts, der von der Erfassungseinrichtung erfaßt wird, von der Positionserfassungseinrichtung verwendet wird, um einen aktualisierten Standort zu liefern, der auf der inkrementalen Standortänderung des Anzeigeelements basiert, das durch die Änderung in dem erfaßten Musterabschnitt angezeigt wird.

33. Positionserfassungsvorrichtung gemäß Anspruch 32, bei der das Muster eine Codierung von zwei Fenstertechniksequenzen von Elementen ist, die sich fiktiv entlang einer ersten bzw. einer zweiten Koordinatenachse erstrecken, wobei die Positionsbestimmungseinrichtung wirksam ist, um den Standort des Anzeigeelements entlang der ersten und der zweiten Koordinatenachse getrennt zu aktualisieren, basierend auf einer beliebigen inkrementalen Standortänderung entlang der entsprechenden Koordinatenachse, die durch eine Änderung des Elements oder der Elemente der entsprechenden Sequenz angezeigt wird, welche durch den erfaßten Musterabschnitt dargestellt ist; wobei die Positionsbestimmungseinrichtung beim inkrementalen Erhöhen des Standorts des Anzeigeelements entlang zumindest einer Koordinatenachse eine unveränderte Bewegungsrichtung entlang derselben annimmt, außer und bis das Element oder die Elemente der Sequenz, die sich entlang der Koordinatenachse erstrecken, welche durch den erfaßten Musterabschnitt dargestellt sind, sich von den vorhergesagten der gespeicherten Musterdaten, die sich auf die Sequenz, die sich auf den gegenwärtigen Standpunkt in der Sequenz bezieht, wie er vorher durch die Positionsbestimmungseinrichtung bestimmt wurde, beziehen, unterscheiden, wobei die Positionsbestimmungseinrichtung beim Erfassen eines Unterschieds zwischen den erfaßten und den vorhergesagten Sequenzelementen ferner wirksam ist, um in ein Erholungsverfahren einzutreten, um seinen Ort entlang der einen Koordinatenachse wiederzugewinnen, wobei das Erholungsverfahren das Herleiten von zumindest einem Kandidatenstandort für das Anzeigeelement auf der Basis einschließt, daß die Bewegungsrichtung des Anzeigeelements sich umgekehrt hat, und das direkte oder indirekte Vergleichen des Elements oder der Elemente, die entlang der Spur des Anzeigeelements erfaßt werden, mit denen, über die vorhergesagt ist, daß sie entlang der Spur des Anzeigeelements beim Erreichen des oder jedes Kandidatenstandorts liegen, wodurch die Gültigkeit des oder jedes solchen Ortes überprüft wird.

34. Positionserfassungsvorrichtung gemäß Anspruch 33, bei der die Vorrichtung wirksam ist, um die Identität der Sequenzelemente, die entlang der Spur des Anzeigeelements erfaßt werden, zu speichern, wobei die Gültigkeit des oder jedes Kandidatenstandorts während des Erholungsverfahrens überprüft wird, indem auf der Basis, daß eine Bewegungsumkehr an einem Standort auf halbem Weg zwischen dem Kandidatenstandort und dem gegenwärtig bestimmten auftrat, das Sequenzelement oder die Elemente, die während der Bewegung zwischen dem halben Weg und den Kandidatenstandorten erfaßbar sind, vorhergesagt werden, indem dieselben mit den entsprechenden gespeicherten erfaßten Sequenzelementen verglichen werden, und indem der Kandidatenstandort ausgeschlossen wird, wenn dieser Vergleich eine Nicht-Übereinstimmung zur Folge hat.

35. Positionserfassungsvorrichtung gemäß Anspruch 33, bei der das Erholungsverfahren das Überprüfen der Gültigkeit des oder jedes Kandidatenstandorts einschließt, durch:

(i) Vorhersagen des Sequenzelements oder der Elemente, die an demselben erfaßbar sind, Vergleichen derselben mit dem Sequenzelement oder den Elementen, die für den gegenwärtig bestimmten, jedoch falschen Standort vorhergesagt sind, und Ausschliessen des Kandidatenstandorts, wenn dieser Vergleich eine Übereinstimmung ergibt, und/oder

(ii) unter der Annahme, daß eine Bewegungsumkehr an einem Standort auf halbem Weg zwischen dem Kandidatenstandort und dem gegenwärtig bestimmten Standort auftrat, Vorhersagen des Sequenzelements oder der Elemente, die während der Bewegung zwischen dem halben Weg und den Kandidatenstandorten erfaßbar sind, jedoch den letztgenannten Standort nicht einschließen, Vergleichen derselben mit den entsprechenden Sequenzelementen, die für die Bewegung zu dem gegenwärtig bestimmten, jedoch falschen, Standort vorhergesagt sind, und Ausschließen des Kandidatenstandorts, wenn dieser Vergleich eine Nicht-Übereinstimmung ergibt.

36. Positionserfassungsvorrichtung gemäß den Ansprüchen 33, 34 oder 35, bei der eine Mehrzahl von Kandidatenstandorten hergeleitet werden und nach dem Testen ihrer Gültigkeit nicht ausgeschlossen werden, wobei das Erholungsverfahren ferner das Erfassen weiterer inkrementaler Änderungen der erfaßten Sequenzelemente und das Vergleichen jedes neuen inkremental geänderten erfaßten Sequenzelements oder der Elemente mit Vorhersagen, die auf jedem verbleibenden Kandidatenstandort basieren, einschließt, wobei der verbleibende Kandidatenstandort ausgeschlossen wird, wenn dieser Vergleich eine Nicht-Übereinstimmung zur Folge hat.

37. Positionserfassungsvorrichtung gemäß einem beliebigen der vorhergehenden Ansprüche, bei der das Anzeigeelement (11) eine in der Hand haltbare Schreibspitze ist, die die Sensoreinrichtung trägt.

38. Positionserfassungsvorrichtung gemäß einem beliebigen der vorhergehenden Ansprüche, bei der das Musterelement (10) ein planares Bauteil ist, das die Markierungen trägt, wobei sowohl das planare Bauteil als auch die Markierungen für sichtbares Licht durchlässig sind, wodurch das Betrachten von Gegenständen durch das Musterelement möglich ist.

39. Positionserfassungsvorrichtung gemäß Anspruch 37, bei der das Musterelement (10) ein planares Bauglied ist, das die Markierungen trägt, wobei die Markierungen für sichtbares Licht durchlässig sind, und wobei die Schreibspitze eine Markierschreibspitze ist, die in der Lage ist, ein Markiermittel auf einer Oberfläche des planaren Bauglieds abzuscheiden, auf der die Markierungen mittels der Sensoreinrichtung erfaßt werden können, wobei das Arbeitsmittel optisch sichtbar ist, jedoch die Erfassung der Markierungen durch dasselbe ermöglicht.

40. Positionserfassungsvorrichtung gemäß Anspruch 37, bei der das Musterelement ein planares Bauglied ist, das die Markierungen trägt, wobei die Vorrichtung ferner eine markierbare Schicht aufweist, die über dem planaren Bauglied positioniert ist, wobei die Schicht mindestens partiell lichtundurchlässig ist und es ermöglicht, daß die Markierungen mittels der Sensoreinrichtungen durch dasselbe erfaßt werden, und wobei die Schreibspitze eine Markierschreibspitze ist, die in der Lage ist, ein Markiermittel auf der Schicht abzuscheiden, wobei dieses Mittel gegenüber der Schicht optisch erkennbar ist, jedoch das Erfassung der Markierungen durch dasselbe ermöglicht.

41. Ein Musterelement (10), das ein zweidimensionales Muster (20) mit Musterzellen, die in Reihen und Spalten angeordnet sind, welche sich parallel zu einer ersten bzw. zweiten Koordinatenachse erstrecken, darstellt, wobei jede Zelle (15) eine Mehrzahl von Nachbarzellen über jeweiligen Grenzen aufweist und eine Eigenschaft besitzt, die auf einen einer Mehrzahl von möglichen Werten eingestellt ist, wobei die Zellen dazu dienen, eine erste und eine zweite binäre Sequenz von Bits zu codieren, die parallel zu der ersten bzw. zweiten Achse sind, wobei jede Sequenz dadurch eine Fenstertechniksequenz ist, daß eine beliebige Teilsequenz einer vorbestimmten Bitlänge eindeutig in der gesamten Sequenz lokalisiert werden kann, wobei der Wert jedes Sequenz-Bits als eine entsprechende Änderung des Zelleneigenschaftswertes codiert ist, wenn eine Bewegung über die Grenze stattfindet, wobei die Änderung gemäß der folgenden vier Codierfunktionen, die den Eigenschaftswert der Zelle wiedergeben, wenn eine Bewegung von einer anderen Zelle, die einen Eigenschaftswert c besitzt, zu derselben stattfindet, dargestellt ist:

h&sub0;(c), h&sub1;(c) - für eine Bewegung parallel zu der ersten Achse

v&sub0;(c), v&sub1;(c) - für eine Bewegung parallel zu der zweiten Achse

Wobei die Suffixe "0" und "1" die Codierfunktion anzeigen, die verwendet werden inuß, um den entsprechenden Bitwert der betroffenen binären Sequenz zu codieren, wobei die Codierung derart ist, daß gilt:

h&sub0;(c) ≠ h&sub1;(c) und v&sub0;(c) ≠ v&sub1;(c)

hi(vj(c)) = vj(hi(c))

wobei "i" und "j" Glieder des binären Wertesatzes (0,1) sind, wobei jede Zelle von ihren Nachbarn unterscheidbar ist und Bewegungen parallel zu der ersten und der zweiten Achse jeweils identifizierbar sind.

42. Ein Musterelement gemäß Anspruch 41, bei dem die Zelle von ihren Nachbarn unterscheidbar ist und Bewegungen parallel zu der ersten und der zweiten Achse jeweils identifizierbar sind, indem die Wirkung der Codierfunktionen derart gewählt ist, daß eine beliebige gegebene Zelle und alle ihre Nachbarzellen in beiden Richtungen der ersten und der zweiten Achse unterschiedliche Werte der Eigenschaft c aufweisen.

43. Ein Musterelement gemäß Anspruch 41, bei dem jede Zelle von ihren Nachbarn unterscheidbar ist und Bewegungen parallel zu der ersten und der zweiten Achse jeweils identifizierbar sind, indem die Wirkung der Codierfunktionen derart gewählt ist, daß eine beliebige gegebene Zelle und ihre Nachbarzellen in beiden Richtungen einer der ersten oder der zweiten Achse unterschiedliche Werte der Eigenschaft c aufweisen, und ferner durch die Wirkung des Vorsehens von identifizierbaren Separatoren zwischen benachbarten Zellen in beiden Richtungen der anderen der ersten und der zweiten Achse.

44. Ein Musterelement gemäß Anspruch 41, bei dem die Zelle von ihren Nachbarn unterscheidbar ist und Bewegungen parallel zu der ersten und der zweiten Achse jeweils durch die Wirkung des Vorsehens identifizierbarer Separatoren (23, 24) zwischen benachbarten Zellen in beiden Richtungen sowohl der ersten als auch der zweiten Achse identifizierbar sind, wobei die Separatoren, die für eine Bewegung in beide Richtungen einer der Achsen relevant sind, von den Separatoren, die für eine Bewegung in beide Richtungen der anderen Achse relevant sind, unterschieden sind.

45. Ein Musterelement gemäß einem der Ansprüche 41 bis 44, bei dem die Codierfunktionen derart sind, daß die Werte der Eigenschaft c einer beliebigen gegebenen Zelle und aller Zellen, an die dieselbe diagonal angrenzt, eine derartige Wechselbeziehung aufweisen, daß es möglich ist, zumindest die Tatsache zu identifizieren, daß ein diagonaler Übergang durchgeführt wurde, wenn eine Bewegung von der gegebenen Zelle zu einer ihrer diagonal angrenzenden Zellen stattfindet.

46. Ein Musterelement gemäß einem beliebigen der Ansprüche 41 bis 45, bei dem die Codierfunktionen folgende Form aufweisen:

h&sub0;(c) = c + a (Modulo N)

h&sub1;(c) = c - a (Modulo N)

v&sub0;(c) = c + b (Modulo N)

v&sub1;(c) = c - b (Modulo N)

wobei a nicht gleich b ist.

47. Ein Musterelement gemäß einem beliebigen der Ansprüche 41 bis 45, bei dem die Codierfunktionen folgende Form aufweisen:

h&sub0;(c) = c.XOR.a

h&sub1;(c) = c.XOR.b

v&sub0;(c) = c.XOR.d

v&sub1;(c) = c.XOR.e

wobei XOR die bitweise Exklusiv-OR-Funktion darstellt; a, b, d, e nicht Null sind; a und b verschieden sind und d und e verschieden sind.

48. Ein Musterelement gemäß einem beliebigen der Ansprüche 41 bis 47, bei dem die Sequenzen ausrichtbare Sequenzen sind, und bei dem gilt:

h&sub0;(c) = h&sub0;&supmin;¹(c); h&sub1;(c) = h&sub1;&supmin;¹(c)

v&sub0;(c) = v&sub0;&supmin;¹(c); v&sub1;(c) = v&supmin;¹(c)

wobei der obere Index -1 den Umkehrübergang anzeigt.

49. Ein Musterelement gemäß einem beliebigen der Ansprüche 41 bis 47, bei dem die Sequenzen komplementär ausrichtbare Sequenzen sind, und bei dem gilt:

h&sub0; = h&sub1;&supmin;¹(c)

v&sub0; = v&sub1;&supmin;¹(c)

wobei der obere Index -1 den Umkehrübergang anzeigt.

50. Verschiebungserfassungsvorrichtung, die ein Musterelement (10) gemäß einem beliebigen der Ansprüche 41 bis 47 aufweist, ein Bauglied, das über das Element bewegbar ist, eine Erfassungseinrichtung, die mit dem Bauglied gekoppelt ist, um zu einer Zeit den Wert der Eigenschaft c einer einzelnen Zelle des Musters und, wenn vorgesehen, die Identität des Separators (23, 24) zu erfassen, und eine Prozessoreinrichtung, die auf die Ausgabe der Sensoreinrichtung anspricht, um die relative Verschiebung des Bauglieds über dem Musterelement zu bestimmen.

51. Ein Verfahren zum Bestimmen des Standorts eines Anzeigers (11) entlang einer vorbestimmten Sequenz von Mustermerkmalen (15), bezüglich derer der Anzeiger bewegbar ist, wobei das Verfahren das Bestimmen (100) eines Anfangsstandorts für den Anzeiger entlang der Sequenz und danach das inkrementale Aktualisieren (101) des bestimmten Standorts mittels folgender Schritte einschließt:

A. Erfassen eines Abschnitts der Sequenz von Mustermerkmalen in dem Ortsbereich des Anzeigers und Überwachen des erfaßten Sequenzabschnitts, um eine inkrementale Änderung in demselben zu erfassen,

B. beim Erfassen einer inkrementalen Änderung in dem erfaßten Abschnitt, Vergleichen (130) des erfaßten Sequenzabschnitts mit dem vorhergesagten, wie er in dem Ortsbereich vorliegt, wobei diese Vorhersage eine gespeicherte Darstellung der vorbestimmten Sequenz verwendet und auf der Basis bewirkt wird, daß eine inkrementale Änderung des gegenwärtig bestimmten Standorts in einer angenommenen Bewegungsrichtung stattgefunden hat, und

C. Einwirken auf das Ergebnis des Vergleichs wie folgt:

(i) wenn der Vergleich eine Übereinstimmung zwischen dem erfaßten und dem vorhergesagten Sequenzabschnitt erzeugt, Aktualisieren (133) des bestimmten Standorts des Anzeigers durch eine inkrementale Änderung in der angenommenen Bewegungsrichtung,

(ii) wenn der Vergleich eine Nicht-Übereinstimmung zwischen dem erfaßten und dem vorhergesagten Sequenzabschnitt erzeugt, Durchführen (103) eines Erholungsverfahrens, um den Standort des Anzeigers entlang der Sequenz wiederzugewinnen, wobei das Erholungsverfahren das Herleiten von zumindest einem Kandidatenstandort für den Anzeiger einschließt, auf der Basis, daß die Bewegungsrichtung des Anzeigers umgekehrt wurde, und das direkte oder indirekte Vergleichen der Sequenzabschnitte, die entlang der Spur des Anzeigers erfaßt wurden, mit denen, über die vorhergesagt wurde, daß sie beim Erreichen des oder jedes Kandidatenstandorts entlang der Spur des Anzeigers liegen, wodurch die Gültigkeit des oder jedes derartigen Standorts überprüft wird.

52. Ein Verfahren gemäß Anspruch 51, das den Schritt des Speicherns der Sequenzabschnitte, die entlang der Laufbahn des Anzeigers erfaßt werden, einschließt, wobei die Gültigkeit des oder jedes Kandidatenstandorts während des Erholungsverfahrens überprüft wird, indem auf der Basis, daß eine Bewegungsumkehr an einem Standort auf halbem Weg zwischen dem Kandidatenstandort und dem gegenwärtig bestimmten stattgefunden hat, die Sequenzabschnitte, die während der Bewegung zwischen dem halben Weg und den Kandidatenstandorten erfaßbar sind, vorhergesagt werden, dieselben mit den entsprechenden gespeicherten Sequenzabschnitten verglichen werden, und der Kandidatenstandort ausgeschlossen wird, wenn dieser Vergleich eine Nicht-Übereinstimmung ergibt.

53. Ein Verfahren gemäß Anspruch 51, bei dem das Erholungsverfahren das Überprüfen der Gültigkeit des Kandidatenstandorts auf folgende Art und Weise einschließt:

(i) Vorhersagen des Sequenzabschnitts, der an demselben erfaßbar ist, Vergleichen desselben mit dem Sequenzabschnitt, der für den gegenwärtig bestimmten Standort vorhergesagt ist, und Ausschließen des Kandidatenstandorts, wenn dieser Vergleich eine Ubereinstimmung ergibt, und/oder

(ii) auf der Annahme, daß eine Bewegungsumkehr an einem Standort auf halbem Weg zwischen dem Kandidatenstandort und dem gegenwärtig bestimmten Standort stattgefunden hat, Vorhersagen der Sequenzabschnitte, die während der Bewegung zwischen dem halben Weg und den Kandidatenstandorten erfaßbar sind, die jedoch den letztgenannten Standort nicht einschließen, Vergleichen derselben mit den entsprechenden Sequenzabschnitten, die für eine Bewegung zu dem gegenwärtig bestimmten Standort vorhergesagt wurden, und Ausschließen des Kandidatenstandorts, wenn dieser Vergleich eine Nicht-Übereinstimmung ergibt.

54. Ein Verfahren gemäß den Ansprüchen 51, 52 oder 53, bei dem eine Mehrzahl von Kandidatenstandorten hergeleitet werden und nach dem Testen ihrer Gültigkeit unausgeschlossen bleiben, wobei das Erholungsverfahren ferner das Erfassen weiterer inkrementaler Änderungen des erfaßten Sequenzabschnitts einschließt, sowie das Vergleichen jedes neuen inkremental geänderten erfaßten Sequenzabschnitts mit Vorhersagen, die auf jedem verbleibenden Kandidatenstandort basieren, wobei der verbleibende Kandidatenstandort ausgeschlossen wird, wenn dieser Vergleich eine Nicht-Übereinstimmung ergibt.