-Drucken ArtikelElektronische digitale schaltungen formal kann unterteilt werden in 2 Klasse:
Schema-Matching (KS) – nicht über Gedächtnis. Das Ausgangssignal gebildet, die in Abhängigkeit von der Kombination der Eingabe von Daten in festen Zeitpunkt (angesichts der Verzögerung auf die Umwandlung der Signale).Schema-matching, Ihre Arten und Prinzipien der Konstruktion kann ein Thema für einen anderen Artikel, als Beispiele: Verwaltete Reifen, Multiplexer und Demultiplexer, Decoder und Kodierer, Wandler-Codes, Kombination Zähler und Combiner und T. D.
Schema mit Memory – Algorithmus Ihrer Arbeit hängt vom Zustand der Eingänge und Speicher (hinaus, das war in früheren Zeiten). Diese Schema beschreibt die mit der Anwendung der Theorie der endlichen Automaten. Es geht um Sie und geht weiter.
Mit anderen Worten: die erste-Klasse — logische Einheiten, Bearbeitung Input. Die zweite Elemente mit dem Gedächtnis und der Reaktion auf das Signal in Abhängigkeit von der eingegebenen Daten in.
Abstrakt, Automatik
Der Automat muss realisieren wird, einige Funktionen, die Entwickler festgelegt. Er kann einfach сумматором, kann realisieren irgendwelche микрокоманду CPU, wählen Worte aus dem RAM oder mit den syntaktischen Analyse der Ausdrücke.
In der Allgemeinen Form, ohne ins Detail zu gehen, abstrakte Automaten kann man sich vorstellen wie folgt:
Oder, wenn Sie von der illustration zur mathematischen Beschreibung:
A = <A, B, C, δ, λ>
Bezeichnung:
Viele {A} – ist eine Menge von Werten auf den physikalischen Eingängen Automaten. Am Eingang in unserem Fall eine Abfolge von hohen und niedrigen Spannungspegeln, die Kodierung logische Nullen und Einsen.
Viele {B} – ist eine Menge von Werten auf die physikalischen Ausgänge Automaten.
Viele {C} – und viele, das ist der innere Zustand des Automaten – Speicher. Für die Zukunft C0 wir Kennzeichnung der ursprüngliche Zustand des Automaten.
δ = X × Z → Z ist eine Funktion der übergänge Automaten, Sie sind eindeutig bestimmen Sie den Zustand der ai in die wechselt der Automat aus dem Zustand der aj.
λ = X × Z → Y – Funktionen der Ausgänge, Sie bestimmen, was auf den Ausgang der Maschine in Abhängigkeit von den Eingängen und den internen Zustand.
δ und λ nicht gezeigt im Diagramm für eine visuelle vereinfachen.
Dies Automatik funktioniert diskret nach der Zeit, das heißt, die Werte der Eingänge, Ausgänge und den inneren Zustand der Maschine geändert werden in diskreten Zeitpunkten.
So sind wir in der Allgemeinen Form beschrieben, dass es eine Abstrakte Automatik. Ein Beispiel für eine solche Maschine kann Trigger, die groß-und Kleinschreibung Computer oder Addierer.
Markieren 2 Art der Spielautomaten:
Spielautomaten Meilen. Beschreibt ein System von Gleichungen:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t-1) ).
Die Automaten Moore. Beschreibt die Gleichungen:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t) ).
Wie zu sehen ist der Zustand des Automaten c(t) in der aktuellen Zeit ist eine Funktion seines Zustandes in der vorherigen Zeit und Input.
Unterscheiden sich die Automaten Blick Funktion des Ausgangs. In der Maschine Meilen Ausgangssignal bestimmt Input a(t) und den Zustand der Maschine, die in den vorherigen Zeitpunkt c(t-1). Das Ausgangssignal des Automaten Moore bestimmt ein paar Input a(t) und der Zustand im Moment c(t).
So kann man bemerken, dass von einer Art, kann das zweite und Umgekehrt, wobei beim übergang von Automaten Meilen zum Automaten Moore die Anzahl der internen Zustände des Automaten bleibt gleich, und bei dem übergang Anzahl der internen Zustände erhöhen kann. Auf diesem bleiben nicht im Detail werden, abgesehen, dass die synthetisierten(zog der Graf) das Maschinengewehr des Typs, die.
Also, auf diesem mit матчастью vorbei. Versuchen Sie zu beschreiben, Automaten.
Dh. Automatik-Typ Meilen erzeugt ein Ausgangssignal, wenn er ändert sich der Eingang, in Abhängigkeit von seiner früheren Zustand. Die Dauer des Ausgangssignals abhängig von der Länge der Eingabe, und nur von seiner Anwesenheit. In den Automaten Typ Moore Ausgangssignal hängt vom Zustand des Automaten in der aktuellen Zeit dh. der Automat wird produzieren ein bestimmtes Ausgangssignal während Ihren Zustand ändert.
Möglichkeiten, die Spielautomaten
Wie wir herausgefunden haben im ersten Teil — Automatik ist eine Reihe von Input-und output-Alphabete, vielen inneren Zustände und Funktionen, bestimmen übergänge und Ausgänge. Jedoch, in der Regel die Funktion δ und λ nicht festgelegt, und das Verhalten des Automaten muss man beschreiben anders.
Es gibt zwei grundlegende Möglichkeiten, Aufgaben Automaten:
- Mit Hilfe der Grafen von.
- Mit Hilfe der Tabellen übergänge und Ausgänge.
Die Grafen von
Der Graf von Automaten ist ein zusammenhängender graph-orientierte, dessen Gipfel symbolisieren die inneren Zustände des Automaten, und Bogen – die übergänge von einem Zustand in einen anderen.
Für den Grafen Meilen auf dem Bogen werden ähnliche und Wochenende Buchstaben. Wochenende Brief geschrieben über Bögen, als Symbol für das, dass die Ausgangs-Zustand ist abhängig vom Zustand des Automaten in der früheren Zeit.
Für den Grafen Automaten Moore auf die Bögen werden nur die Eingabe der Buchstaben, am selben Wochenende werden rund Gipfel.
Ein wichtiger Punkt: Wenn aus jedem Gipfel geht so viel Doug, wie viele gibt es die Eingabe der Buchstaben, die Maschine vollständig genannt. Mit anderen Worten – wenn aus jedem Gipfel definiert übergänge für jede Eingabe der Buchstaben. In unseren Beispielen Automatik Meilen vollständig, und die Maschine MUR – teilweise.
Und noch: Wenn von einem Gipfel rein Doug mehr, als die Eingabe der Buchstaben (das heißt 2 und mehr als Doug mit der gleichen Eingabe der Buchstaben), ist dies der Automat wird als nicht deterministisch. Das kann passieren, wenn der Aufbau формализованного Beschreibungen und dann muss man sein, einen übergang zu детерминированному Automaten, aber es ist nicht immer erfüllen können. Beschreibung dieses Prozesses auch ich übersehe, ein zeichnen deterministische Automat.
Auf diesem über alle Rubriken.
Tabelle übergänge und Ausgänge.
Graphen besser für den Menschen, und der Tabelle für die Maschine. Jede Maschine können Sie in einer Tabelle die übergänge und Ausgänge (TPV). In TPV Zeilen sind die inneren Zustände des Automaten, und die Spalten die Eingabe der Buchstaben.
Bauen TPV für unseren Grafen von Meilen und Moore. Wenn nicht definiert, welche entweder die Eingabe-oder Ausgabe-Buchstabe, dann stattdessen wird ein Bindestrich. Wenn nicht definiert Zustand, so gilt das gleiche einfache Regel.
TPV Grafen Meilen
In TPV Meilen in jeder Zelle aufgenommen übergänge und Ausgänge. Zum Beispiel, wenn der Automat befindet sich in der Lage, C0 und auf den Eingang kommt der Buchstabe a1, er wechselt in den Zustand S1 und am Ausgang wird der Buchstabe b3.
TPV Grafen Moore
Für den Grafen Moore bauen markierten Tabelle übergänge. Zeichnet sich eine zusätzliche Spalte für die Ausgabe von Buchstaben.
In der Zelle unter Input Brief geschrieben, in welchem Zustand der Automat wechselt, in der rechten Zelle, welche die Ausgabe Buchstaben gibt.
Ein Beispiel für die Synthese von Automaten
Mit Hilfe der abstrakten Automaten beschreiben kann fast alles. Sie beschreiben die Arbeit der digitale schaltungen, und Sie können – syntaktische oder lexikalische Analysator. Versuchen Sie zu beschreiben, Trigger – als nicht Automatik?
Um festzulegen, Graf müssen die verbale Beschreibung des Algorithmus der Arbeit Trigger. Lesen:
Verschlüsseln Input-und output-Alphabete:
A = {a0, a1}, wo a0 – Logik 1 am Eingang R, a1 – logische Einheit am Eingang S.
B = {b0, b1}, wo b0 – logische 0 am Ausgang Q, b1 – logische Einheit am Ausgang Q.
Bauen Graf Automaten Meilen:
Das ist so eine tolle Cheburashka war :-). Jetzt können Sie bauen Tabelle übergänge und Ausgänge:
Wenn bemalen diese Tabelle, indem Sie die Legende, in der die tatsächlichen, dann bekommen wir die Tabelle ist die Tabelle übergänge Trigger. Dann können Sie vereinfachen:
Zeichnen Sie die resultierende Funktion auf der Karte Veitch und minimieren:
Notieren, was passiert:
Bauen für die Funktion der Schaltung:
Ein wenig ungewöhnlich, um zu sehen Trigger in der булевом der Grundlinie, deshalb übersetzen Funktion in Basis-und zeichnen Sie das Schema in ihm:
Und auf dem Schema asynchrone RS-Trigger wird hier so:
Nun, wenn man ein wenig Anstrengung, dann können Sie selbst synthetisieren einfache Silvester-Girlande.