Benutzer:Reseka/Endlicher linearer Automat

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Reseka auf.

Ein endlicher linearer Automat im Sinne der Automatentheorie ist ein spezieller determinierter endlicher Automat mit dem Verhalten eines linearen Systems. Dazu müssen seine Eingabe-, Zustands- und Ausgabealphabete die algebraische Struktur eines endlichen Körpers besitzen und seine Überführungs- und Ergebnisfunktion müssen diesbezüglich lineare Abbildungen sein.

Im Sinne der Systemtheorie ist ein endlicher linearer Automat ein determiniertes, konzentriertes, endliches, lineares, zeitinvariantes, kausales dynamisches System mit diskreter Zeit. Dadurch ist einerseits seine didaktische Behandlung einfach, bietet jedoch andererseits die grundlegenden Erkenntnisse einer allgemeinen Theorie der LTI-Systeme.

Technisch gesehen, ist ein endlicher linearer Automat die modellmäßige Verallgemeinerung eines linearen binären Schaltsystems, also eines Schaltwerks, welches nur aus Exklusiv-Oder-Gattern und D-Flipflops besteht.

Ein endlicher linearer Automat ist nicht zu verwechseln mit einer linear beschränkten Turingmaschine, welche auch linear beschränkter Automat, linear bounded automaton oder LBA genannt wird.

Die Zustandsgleichungen

Endliche Symbolmengen

Bei einem endlichen linearen Automat müssen die drei endlichen Symbolmengen des Eingabealphabets $X$, des Zustandsalphabets $Z$ und des Ausgabealphabets $Y$ gleichmächtig und algebraisch so strukturiert sein, dass sie einen endlichen Körper – also ein Galoisfeld $GF(p^{n})$ mit der Primzahl $p$ und der natürlichen Zahl $n$ – mit den Operationen Addition $+$ und Multiplikation $\cdot$ bilden.

Im Spezialfall der praktisch wichtigen binären linearen Automaten reduzieren sich die Alphabete auf das zweiwertige Galoisfeld $GF(2)$, welches durch die Restklasse modulo 2, also die Menge $\{0,1\}$ mit der Antivalenz als Addition und Subtraktion und der Konjunktion als Multiplikation, gebildet wird. Auch mit den anderen auf Restklassen modulo einer Primzahl basierenden endlichen Körpern lässt sich recht einfach rechnen, da „auf Computern“ meist ein Rest- bzw. Modulo-Befehl vorhanden ist.

Beim allgemeinen Fall von Mehrgrößensystemen sind die Eingangs-, Zustands- und Ausgangssymbole in (verschieden dimensionalen, hier fett gedruckten) Potenzmengen $\mathbf {X} =X^{k}$, $\mathbf {Z} =Z^{l}$ bzw. $\mathbf {Y} =Y^{m}$ „gebündelt“.

Lineare Signalräume

Die diskontinuierliche Zeit $t$ durchläuft bei zeitdiskreten Signalen in zeitinvarianten Systemen üblicherweise die natürlichen Zahlen $\mathbb {N}$ von $0$ bis $\infty$.

Ein zeitdiskretes Signal wird durch die Abbildung der Zeitmenge $T=\mathbb {N}$ in die jeweilige Symbolmenge modelliert. Das heißt beispielsweise für das Signal am i-ten Eingang $x_{i}(t):\,T\rightarrow X$.

Bei einem Mehrgrößensystem werden Eingangs-, Zustands- und Ausgangssignale als diskrete vektorielle Zeitfunktionen $\mathbf {x} (t)={\begin{pmatrix}x_{1}(t)\\x_{2}(t)\\\vdots \\x_{k}(t)\end{pmatrix}}$, $\mathbf {z} (t)={\begin{pmatrix}z_{1}(t)\\z_{2}(t)\\\vdots \\z_{l}(t)\end{pmatrix}}$ bzw. $\mathbf {y} (t)={\begin{pmatrix}y_{1}(t)\\y_{2}(t)\\\vdots \\y_{m}(t)\end{pmatrix}}$ definiert. Diese Abbildungen der Zeitmenge $T=\mathbb {N}$ in die Potenzmengen $\mathbf {X}$, $\mathbf {Z}$ bzw. $\mathbf {Y}$ sind also Vektoren aus Folgen (hier in spitze Klammern geschrieben), beispielsweise $\mathbf {x} ={\begin{pmatrix}\langle x_{1}(0),x_{1}(1),x_{1}(2),\dots \rangle \\\langle x_{2}(0),x_{2}(1),x_{2}(2),\dots \rangle \\\vdots \\\langle x_{k}(0),x_{k}(1),x_{k}(2),\dots \rangle \end{pmatrix}}$, können aber auch als Folgen von Vektoren interpretiert werden. Dabei ist zwischen dem Wert einer Folge zu einer konkreten Zeit $t$, z. B. $x(t)$, und der Folge „als Ganzes“, z. B. $x=\langle x(t)\rangle$, zu unterscheiden.

Im Fall von Eingrößenystemen sind Eingabe- und Ausgabealphabet eindimensional.

Die Mengen aller Eingangs-, Zustands- und Ausgangssignale bilden jeweils lineare Räume und werden Signalräume genannt.

Überführungs- und Ergebnisfunktion

Überführungsfunktion und Ergebnisfunktion des Automaten sind per Definition lineare Funktionen. Deshalb können – wie bei zeitdiskreten LTI-Systemen üblich – die Zustandsgleichungen als lineares Differenzengleichungssystem in Form von Matrizen und Vektoren geschrieben werden:

$\mathbf {z} (t+1)=\mathbf {A} \cdot \mathbf {z} (t)+\mathbf {B} \cdot \mathbf {x} (t)$

$\mathbf {y} (t)=\mathbf {C} \cdot \mathbf {z} (t)+\mathbf {D} \cdot \mathbf {x} (t)$

Zur vollständigen Beschreibung muss noch der Anfangszustand $\mathbf {z} (0)$ gegeben sein. Oft wird jedoch der sogenannte Nullstand $\mathbf {z} (0)=0$ angenommen.

Auf der Basis der Zustandsgleichungen lässt sich das Systemverhalten bei gegebenem Eingangssignal und Anfangszustand iterativ berechnen bzw. simulieren.

Obwohl sich aufgrund der Endlichkeit der Symbolmengen auch bei linearen Automaten Überführungs- und Ergebnisfunktion in Form von Überführungs- und Ergebnistabelle oder als Zustandsgraph darstellen lassen, wird zur Verhaltensanalyse üblicherweise die analytische Darstellung verwendet.

Beispiel

Ein „einfacher“ linearer Automat besitze das skalare Eingangssignal $x(t)$, das skalare Ausgangssignal $y(t)$ und das zweidimensionale Zustandssignal $\mathbf {z} (t)={\begin{pmatrix}z_{1}(t)\\z_{2}(t)\end{pmatrix}}$. Alle Signalalphabete basieren auf $GF(3)$, also dem Restklassenring modulo 3. Damit erhalten wir die Signalalphabete $X=Y=\{0,1,2\}$ und $Z^{2}=\left\{{\begin{pmatrix}0\\0\end{pmatrix}},{\begin{pmatrix}0\\1\end{pmatrix}},{\begin{pmatrix}0\\2\end{pmatrix}},{\begin{pmatrix}1\\0\end{pmatrix}},{\begin{pmatrix}1\\1\end{pmatrix}},{\begin{pmatrix}1\\2\end{pmatrix}},{\begin{pmatrix}2\\0\end{pmatrix}},{\begin{pmatrix}2\\1\end{pmatrix}},{\begin{pmatrix}2\\2\end{pmatrix}}\right\}$. Dabei ist zu beachten, dass die Subtraktion durch die Addition des 3er-Komplements ersetzt werden kann, also beispielsweise gilt $1-2=1+1=2$.

Das System der Zustandsgleichungen sei

$z_{1}(t+1)=z_{1}(t)+2\cdot z_{2}(t)+2\cdot x(t)$

$z_{2}(t+1)=z_{2}(t)+x(t)$

$y(t)=z_{1}(t)+2\cdot z_{2}(t)+2\cdot x(t)$

In Matrizenschreibweise wird es übersichtlicher und systematischer:

${\begin{pmatrix}z_{1}(t+1)\\z_{2}(t+1)\end{pmatrix}}={\begin{pmatrix}1&2\\0&1\end{pmatrix}}\cdot {\begin{pmatrix}z_{1}(t)\\z_{2}(t)\end{pmatrix}}+{\begin{pmatrix}2\\1\end{pmatrix}}\cdot x(t)$

$y(t)={\begin{pmatrix}1&2\end{pmatrix}}\cdot {\begin{pmatrix}z_{1}(t)\\z_{2}(t)\end{pmatrix}}+{\begin{pmatrix}2\end{pmatrix}}\cdot x(t)$

Damit lauten die vier Systemmatrizen

$\mathbf {A} ={\begin{pmatrix}1&2\\0&1\end{pmatrix}}$

$\mathbf {B} ={\begin{pmatrix}2\\1\end{pmatrix}}$

$\mathbf {C} ={\begin{pmatrix}1&2\end{pmatrix}}$

$\mathbf {D} ={\begin{pmatrix}2\end{pmatrix}}$

Dabei ist die „Durchgriffsmatrix“ $\mathbf {D}$ zum Skalar „mutiert“.

Allgemeine Lösung der Zustandsgleichungen

Die Zustandsgleichungen stellen ein System von linearen Rekursions- oder Differenzengleichungen mit konstanten Koeffizienten dar, dessen Lösung sich (ausgehend vom Anfangszustand zur Zeit $t=0$) geschlossen schreiben lässt:

$\mathbf {z} (t)=\mathbf {A} ^{t}\cdot \mathbf {z} (0)+\sum \limits _{\tau =0}^{t-1}\mathbf {A} ^{t-1-\tau }\cdot \mathbf {B} \cdot \mathbf {x} (\tau )$

$\mathbf {y} (t)=\mathbf {C} \cdot \mathbf {A} ^{t}\cdot \mathbf {z} (0)+\sum \limits _{\tau =0}^{t-1}\mathbf {C} \cdot \mathbf {A} ^{t-1-\tau }\cdot \mathbf {B} \cdot \mathbf {x} (\tau )+\mathbf {D} \cdot \mathbf {x} (t)$

Das ist die (in der Literatur) sogenannte „allgemeine Responseformel“. Sie bestimmt das Ein-/Ausgangsverhalten des linearen Automaten vollständig.

Beide Behauptungen kann man durch vollständige Induktion beweisen. Alternativ lassen sie sich direkt „klassisch“ ermitteln oder indirekt über eine diskrete Operatorenrechnung herleiten.

Der freie Vorgang

Verschwinden alle Eingangssignale $\mathbf {x} (t)=\mathbf {0}$, dann hängt das Verhalten des Automaten nur vom Anfangszustand $\mathbf {z} (0)$ ab und heißt freier Vorgang oder Nullinputantwort.

Wie in der Literatur zur Theorie der LTI-Systeme üblich, definieren wir die das Systemverhalten grundsätzlich beschreibende Fundamentalmatrix

$\mathbf {\Phi } (t)=\mathbf {A} ^{t}$

Aufgrund der Endlichkeit der Elemente von $\mathbf {A}$ kann es auch nur endlich viele unterschiedliche Matrixpotenzen $\mathbf {A} ^{t}$ geben. Deshalb kann die Fundamentalmatrix $\mathbf {\Phi } (t)$ oft „geschlossen“ berechnet werden.

Mit der Fundamentalmatrix erhält man die Lösung des (aufgrund eines 0-Eingangssignals entstandenen) homogenen linearen Differenzengleichungssystems

$\mathbf {z} (t)=\mathbf {A} ^{t}\cdot \mathbf {z} (0)=\mathbf {\Phi } (t)\cdot \mathbf {z} (0)$

bzw.

$\mathbf {y} (t)=\mathbf {C} \cdot \mathbf {A} ^{t}\cdot \mathbf {z} (0)=\mathbf {C} \cdot \mathbf {\Phi } (t)\cdot \mathbf {z} (0)$

Für das oben genannte Beispiel lautet die Fundamentalmatrix

$\mathbf {\Phi } (t)=\mathbf {A} ^{t}={\begin{pmatrix}1&2\\0&1\end{pmatrix}}^{t}$

Für die ersten Matrixpotenzen erhält man

$\mathbf {A} ^{0}={\begin{pmatrix}1&2\\0&1\end{pmatrix}}^{0}={\begin{pmatrix}1&0\\0&1\end{pmatrix}}$

$\mathbf {A} ^{1}={\begin{pmatrix}1&2\\0&1\end{pmatrix}}^{1}={\begin{pmatrix}1&2\\0&1\end{pmatrix}}$

$\mathbf {A} ^{2}={\begin{pmatrix}1&2\\0&1\end{pmatrix}}^{2}={\begin{pmatrix}1&1\\0&1\end{pmatrix}}$

$\mathbf {A} ^{3}={\begin{pmatrix}1&2\\0&1\end{pmatrix}}^{3}={\begin{pmatrix}1&0\\0&1\end{pmatrix}}=\mathbf {A} ^{0}$

Ab der dritten Potenz wiederholen sich die Werte der Matrixpotenz, so dass sich für die Folge der Fundamentalmatrizen eine Periodizität ergibt:

$\mathbf {\Phi } =\langle \mathbf {\Phi } (t)\rangle =\left\langle {\begin{pmatrix}1&0\\0&1\end{pmatrix}},{\begin{pmatrix}1&2\\0&1\end{pmatrix}},{\begin{pmatrix}1&1\\0&1\end{pmatrix}},{\begin{pmatrix}1&0\\0&1\end{pmatrix}},\dots \right\rangle =\left\langle {\overline {{\begin{pmatrix}1&0\\0&1\end{pmatrix}},{\begin{pmatrix}1&2\\0&1\end{pmatrix}},{\begin{pmatrix}1&1\\0&1\end{pmatrix}}}}\right\rangle$

Damit lässt sich (ausgehend vom Anfangszustand $\mathbf {z} (0)={\begin{pmatrix}2\\2\end{pmatrix}}$) beispielsweise direkt $\mathbf {z} (20)$ berechnen:

$\mathbf {z} (20)=\mathbf {\Phi } (20)\cdot \mathbf {z} (0)=\mathbf {\Phi } (2)\cdot \mathbf {z} (0)={\begin{pmatrix}1&1\\0&1\end{pmatrix}}\cdot {\begin{pmatrix}2\\2\end{pmatrix}}={\begin{pmatrix}1\\2\end{pmatrix}}$

Daraus folgt für das zugehörige Ausgangssignal

$y(20)=\mathbf {C} \cdot \mathbf {z} (20)={\begin{pmatrix}1&2\end{pmatrix}}\cdot {\begin{pmatrix}1\\2\end{pmatrix}}=2$

Der erzwungene Vorgang

Verschwindet der Anfangszustand (d. h. das System ist im 0-Zustand), dann reduzieren sich die Formeln des vom Eingangssignalvektor $\mathbf {x} (t)$ erzwungenen Vorgangs oder der Nullzustandsantwort wie folgt:

$\mathbf {z} (t)=\sum \limits _{\tau =0}^{t-1}\mathbf {A} ^{t-1-\tau }\cdot \mathbf {B} \cdot \mathbf {x} (\tau )=\sum \limits _{\tau =0}^{t-1}\mathbf {\Phi } (t-1-\tau )\cdot \mathbf {B} \cdot \mathbf {x} (\tau )$

$\mathbf {y} (t)=\sum \limits _{\tau =0}^{t-1}\mathbf {C} \cdot \mathbf {A} ^{t-1-\tau }\cdot \mathbf {B} \cdot \mathbf {x} (\tau )+\mathbf {D} \cdot \mathbf {x} (t)=\sum \limits _{\tau =0}^{t-1}\mathbf {C} \cdot \mathbf {\Phi } (t-1-\tau )\cdot \mathbf {B} \cdot \mathbf {x} (\tau )+\mathbf {D} \cdot \mathbf {x} (t)$

Mit der Definition der Gewichtsmatrix

$\mathbf {H} (t)={\begin{cases}\mathbf {D} &{\text{für }}t=0\\\mathbf {C} \cdot \mathbf {A} ^{t-1}\cdot \mathbf {B} &{\text{für }}t>0\end{cases}}$

folgt für den Ausgangssignalvektor

$\mathbf {y} (t)=\sum \limits _{\tau =0}^{t}\mathbf {H} (t-\tau )\cdot \mathbf {x} (\tau )=\mathbf {H} (t)\ast \mathbf {x} (t)$

Dabei steht das Sternchen $\ast$ für den diskreten Faltungsoperator.

Belegt man nur den i-ten Eingang mit einem (zeitdiskreten) Einheitsimpuls $\langle x_{i}(t)\rangle =\langle 1,0,0,0,\dots \rangle$, dann entsteht am j-ten Ausgang die Impulsantwort $\langle y_{j}(t)\rangle =\langle h_{ij}(0),h_{ij}(1),h_{ij}(2),h_{ij}(3),\dots \rangle$. Deshalb ist die Gewichtsmatrix die Matrix der Impulsantworten. Die Impulsantwort eines endlichen linearen Automaten ist zwingend periodisch.

In unserem Beispiel ist die Gewichtsmatrix $\mathbf {H} (t)$ zu einer Gewichtsfunktion $h(t)$ „degeneriert“:

$h(t)={\begin{cases}2&{\text{für }}t=0\\{\begin{pmatrix}1&2\end{pmatrix}}\cdot {\begin{pmatrix}1&2\\0&1\end{pmatrix}}^{t-1}\cdot {\begin{pmatrix}2\\1\end{pmatrix}}&{\text{für }}t>0\end{cases}}$

oder für die ersten Zeitpunkte ausgerechnet:

$h(t)=\langle 2,1,0,2,\dots \rangle =\langle {\overline {2,1,0}}\rangle$

Die Darstellung in Operatorschreibweise

Diskrete Operatorenrechnung

Während sich für zeitdiskrete lineare Systeme mit kontinuierlichen Signalalphabeten die z-Transformation etabliert hat, ist diese für endliche Signalalphabete aufgrund des dort fehlenden Stetigkeitsbegriffs nicht anwendbar. In der Literatur wird deshalb unter der Bezeichnung D-Transformation oder Zeta-Transformation eine Operatorenrechnung auf der Basis der erzeugenden Funktion favorisiert. Diese wird entweder als Transformation oder auf algebraische Weise (ähnlich der Operatorenrechnung nach Mikusiński) eingeführt.

Kern dieser Methoden ist neben der „normalen“ Folgenaddition die Folgenmultiplikation auf Basis der diskreten Faltungssumme. Eine wesentliche Rolle spielt dabei die Folge $\langle 0,1,0,0,\dots \rangle$, deren Multiplikation eine Rechtsverschiebung realisiert, welche praktisch einer Verzögerung um einen „Takt“ entspricht. Sie wird, je nach Autor, mit $d$ (von „delay“), $\zeta$ (Zeta als Gegenüberstellung zur z-Transformation) oder auch $x$ (insbesondere in der Algebra und Informatik) bezeichnet und ihre Potenzen gestatten die Darstellung von endlichen und unendlichen Folgen als Polynome bzw. unendliche Reihen.

Aus dem so definierten Integritätsring wird der Quotientenkörper konstruiert, dessen Elemente als Operatoren oder Signalquotienten bezeichnet werden, da jetzt eine Division zur Verfügung steht.

Lösung der Zustandsgleichungen

Wir schreiben die Zustandsgleichungen als Folgen in Operatorschreibweise:

${\frac {\mathbf {z} -\mathbf {z} (0)}{d}}=\mathbf {A} \cdot \mathbf {z} +\mathbf {B} \cdot \mathbf {x}$

$\mathbf {y} =\mathbf {C} \cdot \mathbf {z} +\mathbf {D} \cdot \mathbf {x}$

Wir formen die erste Gleichung um

$\mathbf {z} =d\cdot \left(\mathbf {A} \cdot \mathbf {z} +\mathbf {B} \cdot \mathbf {x} \right)+\mathbf {z} (0)$

und lösen nach $\mathbf {z}$ auf

$\mathbf {z} -d\cdot \mathbf {A} \cdot \mathbf {z} =\left(\mathbf {E} -d\cdot \mathbf {A} \right)\cdot \mathbf {z} =\mathbf {z} (0)+d\cdot \mathbf {B} \cdot \mathbf {x}$

Wir erhalten die Zustands- und Ausgangsfolge in Operatorform:

$\mathbf {z} =\left(\mathbf {E} -d\cdot \mathbf {A} \right)^{-1}\cdot \left(\mathbf {z} (0)+d\cdot \mathbf {B} \cdot \mathbf {x} \right)$

$\mathbf {y} =\mathbf {C} \cdot \left(\mathbf {E} -d\cdot \mathbf {A} \right)^{-1}\cdot \left(\mathbf {z} (0)+d\cdot \mathbf {B} \cdot \mathbf {x} \right)+\mathbf {D} \cdot \mathbf {x}$

Die Fundamentalmatrix in Operatorschreibweise

Die zu invertierende Matrix kann man durch „Ausdividieren“ als unendliche Reihe schreiben:

$\left(\mathbf {E} -d\cdot \mathbf {A} \right)^{-1}=\sum \limits _{i=0}^{\infty }{d^{i}\cdot \mathbf {A} ^{i}}=\langle \mathbf {A} ^{i}\rangle$

An der Matrixpotenz erkennt man, dass sie die Operatorform der Fundamentalmatrix ist:

$\mathbf {\Phi } =\left(\mathbf {E} -d\cdot \mathbf {A} \right)^{-1}$

Damit folgen für Zustands- und Ausgangsfolge in Operatorform

$\mathbf {z} =\mathbf {\Phi } \cdot \left(\mathbf {z} (0)+d\cdot \mathbf {B} \cdot \mathbf {x} \right)$

$\mathbf {y} =\mathbf {C} \cdot \mathbf {\Phi } \cdot \left(\mathbf {z} (0)+d\cdot \mathbf {B} \cdot \mathbf {x} \right)+\mathbf {D} \cdot \mathbf {x}$

Nach Rücktransformation erhalten wir die oben angegebene allgemeine Lösung.

Die Übertragungsmatrix

Für verschwindenden Anfangszustand erhält man den erzwungenen Vorgang

$\mathbf {y} =\left(\mathbf {C} \cdot \mathbf {\Phi } \cdot d\cdot \mathbf {B} +\mathbf {D} \right)\cdot \mathbf {x} =\mathbf {H} \cdot \mathbf {x}$

In der Beziehung $\mathbf {y} =\mathbf {H} \cdot \mathbf {x}$ kann man sofort die oben angegebene Operatorform der Faltung von $\mathbf {y} (t)=\mathbf {H} (t)\ast \mathbf {x} (t)$ erkennen.

Daraus lässt sich schlussfolgern, dass die Operatorform der Gewichtsmatrix die Übertragungsmatrix des linearen Automaten ist:

$\langle \mathbf {H} (t)\rangle =\mathbf {H} =\mathbf {C} \cdot \left(\mathbf {E} -d\cdot \mathbf {A} \right)^{-1}\cdot d\cdot \mathbf {B} +\mathbf {D} =\mathbf {C} \cdot \mathbf {\Phi } \cdot d\cdot \mathbf {B} +\mathbf {D}$

Beispiel

Im oben angeführten Beispiel lautet die Operatorform der Fundamentalmatrix

$\mathbf {\Phi } =\left({\begin{pmatrix}1&0\\0&1\end{pmatrix}}-d\cdot {\begin{pmatrix}1&2\\0&1\end{pmatrix}}\right)^{-1}={\begin{pmatrix}1-d&-2d\\0&1-d\end{pmatrix}}^{-1}$

Diese Matrix kann mit einem beliebigen Verfahren invertiert werden. Hier bietet sich das Verfahren über die Adjunkte an. Nach Ermittlung der Determinante (unter Beachtung des Vorzeichens in $GF(3)$)

$\det {\begin{pmatrix}1-d&-2d\\0&1-d\end{pmatrix}}=(1-d)^{2}=1-2d+d^{2}=1+d+d^{2}$

kann man die „Inverse“ sofort schreiben:

$\mathbf {\Phi } ={\frac {1}{1+d+d^{2}}}\cdot {\begin{pmatrix}1-d&2d\\0&1-d\end{pmatrix}}={\begin{pmatrix}{\frac {1}{1-d}}&{\frac {2d}{1+d+d^{2}}}\\0&{\frac {1}{1-d}}\end{pmatrix}}$

Damit erhalten wir für die Übertragungsmatrix

$\mathbf {H} ={\begin{pmatrix}1&2\end{pmatrix}}\cdot {\begin{pmatrix}{\frac {1}{1-d}}&{\frac {2d}{1+d+d^{2}}}\\0&{\frac {1}{1-d}}\end{pmatrix}}\cdot d\cdot {\begin{pmatrix}2\\1\end{pmatrix}}+{\begin{pmatrix}2\end{pmatrix}}={\begin{pmatrix}{\frac {1}{1-d}}&{\frac {2}{1+d+d^{2}}}\end{pmatrix}}\cdot {\begin{pmatrix}2d\\d\end{pmatrix}}+{\begin{pmatrix}2\end{pmatrix}}$

$\langle h(t)\rangle =\mathbf {H} ={\frac {d+d^{2}}{1+d+d^{2}}}+2={\frac {2}{1+d+d^{2}}}=2+d+2d^{3}+d^{4}+2d^{6}+d^{7}+\dots =\langle 2,1,0,2,1,0,2,1,0,\dots \rangle =\langle {\overline {2,1,0}}\rangle$

Spezialfälle

Durch einige typische Einschränkungen erhält man folgende Spezialfälle, die auch beliebig kombiniert werden können.

Einfache lineare Automaten

Einfache lineare Automaten (Eingrößensysteme – SISO, siehe unser Beispiel) besitzen – im Gegensatz zu Mehrgrößensystemen (MIMO) – nur ein Eingangs- und ein Ausgangssignal, aber i. A. mehrere Zustandssignale. $\mathbf {B}$ ist dann ein Spaltenvektor, $\mathbf {C}$ ein Zeilenvektor und $\mathbf {D}$ ein Skalar. $\mathbf {A}$ bleibt weiterhin eine „echte“ Matrix.

Statische lineare Automaten

Statische lineare Automaten sind Automaten „ohne Gedächtnis“ bzw. ohne Verzögerungselemente. Deshalb speichern sie keine Information über ihre Vergangenheit. Ihre Ausgangssignale hängen nur direkt und „unverzögert“ (bezüglich der Taktphasen) von den Eingangssignalen ab. Systemtheoretisch besitzen sie nur einen einzigen konstanten Zustand. Ihre Ergebnisfunktion hängt deshalb nicht vom Zustand ab und ihre Überführungsfunktion existiert nicht:

$\mathbf {y} (t)=\mathbf {D} \cdot \mathbf {x} (t)$

Statische Automaten werden durch Zusammenschaltung mit Verzögerungselementen zu „dynamischen Automaten“. Ein Beispiel für einen binären statischen Automaten ist die (Mehrfach-) Antivalenz.

Autonome lineare Automaten

Da autonome lineare Automaten keine Eingänge besitzen, hängen bei ihnen die Systemfunktionen nicht vom Eingangssignalvektor ab:

$\mathbf {z} (t+1)=\mathbf {A} \cdot \mathbf {z} (t)$

$\mathbf {y} (t)=\mathbf {C} \cdot \mathbf {z} (t)$

Es gibt keinen erzwungenen Vorgang und damit keine Gewichts- bzw. Übertragungsmatrix. Die Zustandsfolge verbleibt in einem festen Zyklus. Abhängig vom Anfangszustand generieren autonome lineare Automaten periodische Ausgangsfolgen. Deshalb können sie als Signalgeneratoren, beispielsweise als Pseudozufallszahlengenerator, verwendet werden. Hierbei ist besonders die Konstruktion maximalperiodischer Schieberegister von Bedeutung.

Für unser Beispiel ergibt sich ohne Eingangssignal folgendes Ausgangssignal in Operatorschreibweise:

$\mathbf {y} =\mathbf {C} \cdot \mathbf {\Phi } \cdot \mathbf {z} (0)={\begin{pmatrix}1&2\end{pmatrix}}\cdot {\begin{pmatrix}{\frac {1}{1-d}}&{\frac {2d}{1+d+d^{2}}}\\0&{\frac {1}{1-d}}\end{pmatrix}}\cdot {\begin{pmatrix}z_{1}(0)\\z_{2}(0)\end{pmatrix}}={\begin{pmatrix}{\frac {1}{1-d}}&{\frac {2}{1+d+d^{2}}}\end{pmatrix}}\cdot {\begin{pmatrix}z_{1}(0)\\z_{2}(0)\end{pmatrix}}$

$y={\frac {1}{1-d}}\cdot z_{1}(0)+{\frac {2}{1+d+d^{2}}}\cdot z_{2}(0)$

Diese lineare Überlagerung kann man wieder als Folgen schreiben:

$\langle y(t)\rangle =z_{1}(0)\cdot \langle 1,1,1,\dots \rangle +z_{2}(0)\cdot \langle 2,1,0,2,1,0,2,1,0,\dots \rangle$

Der Anfangszustand von $z_{1}$ wird also einfach „durchgereicht“. Ist $z_{2}(0)=1$, dann ist die Ausgangsfolge natürlich $\langle 2,1,0,2,1,0,2,1,0,\dots \rangle$, ist $z_{2}(0)=2$, dann wird daraus $\langle 1,2,0,1,2,0,1,2,0,\dots \rangle$. Sind beide $1$, dann entsteht $\langle 0,2,1,0,2,1,0,2,1,\dots \rangle$, …

Binäre lineare Automaten

Die Symbolmengen dieses Automaten werden durch den endlichen Körper $GF(2)$ repräsentiert. Dieser hat die rechentechnisch vorteilhafte Eigenschaft, dass die Subtraktion identisch zur Addition ist.

Ihre praktische Realisierung erfolgt durch Schaltsysteme, welche minimal mit Exklusiv-Oder-Gattern und D-Flipflops realisiert werden können. Erst durch diese technische Realisierung haben lineare Automaten praktische Bedeutung erlangt.

Reale Anwendungsbeispiele sind:

• Lineare Schieberegister
• Erzeugung periodischer Binärfolgen
• Erzeugung von Pseudozufallszahlen
• Signaturbildung
• Zyklische Redundanzprüfung

Literatur

• Arthur Gill: Linear sequential circuits; analysis, synthesis, and applications. McGraw-Hill, New York 1966, LCCN 66-029752. 

• Michael Gössel: Angewandte Automatentheorie II. Lineare Automaten und Schieberegister. Akademie-Verlag, Berlin 1972, ISBN 978-3-11-252609-5. 

• Franz Pichler: Mathematische Systemtheorie – Dynamische Konstruktionen. Walter de Gruyter, Berlin, New York 1975, ISBN 3-11-003909-5. 

• Gerhard Wunsch: Systemtheorie. Akademische Verlagsgesellschaft Geest&Portig K.-G., Leipzig 1975, DNB 750192968. 

• Gerhard Wunsch, Helmut Schreiber: Digitale Systeme – Grundlagen. Verlag Technik, Berlin 1982, DNB 840950934. 

• Gerhard Wunsch: Geschichte der Systemtheorie – Dynamische Systeme und Prozesse. R. Oldenbourg Verlag, München 1985, ISBN 3-486-29531-4. 

• Gerhard Wunsch: Handbuch der Systemtheorie. R. Oldenbourg Verlag, München Wien 1986, ISBN 3-486-20017-8.