2136 lines
85 KiB
TeX
2136 lines
85 KiB
TeX
\chapter{Boolesche Algebra}
|
|
|
|
\textit{George Boole (1815-1864)}
|
|
|
|
\begin{itemize}[noitemsep]\index{Boolesche Algebra}
|
|
\item eine Art Rechensystem mit Werten, Operatoren und Regeln
|
|
\item die Wertemenge ist beschränkt $\Rightarrow$ es gibt eine endliche Anzahl von Werten
|
|
\item es gibt zwei zweistellige Operatoren ($\oplus$, $\otimes$) für die die Abgeschlossheit gilt.
|
|
|
|
\hspace*{8mm}$a,b\in \mathbb{W}$ \qquad
|
|
$a\otimes b\in \mathbb{W}$ \qquad
|
|
$a\oplus b\in \mathbb{W}$
|
|
\item Es müssen die vier Huntingston'schen Axiome gelten:
|
|
|
|
\end{itemize}
|
|
|
|
\section{Huntington'sche Axiome}\index{Huntington'sche Axiome}
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\begin{description}
|
|
\item[H1: Kommutativgesetz]\hfill\newline
|
|
$a\otimes b = b\otimes a$\newline
|
|
$a\oplus b = b\oplus a$
|
|
|
|
\item[H2: Distributivgesetz]\hfill\newline
|
|
$a\oplus (b\otimes c)=(a\oplus b)\otimes(a\oplus c)$\newline
|
|
$a\otimes (b\oplus c)=(a\otimes b)\oplus (a\otimes c)$
|
|
|
|
\item[H3: Neutrales Element]\hfill\newline
|
|
Es existieren zwei Elemente $e,n\in\mathbb{W}$ mit\newline
|
|
$a\oplus n=a$\newline
|
|
$a\otimes e=a$
|
|
\end{description}
|
|
\switchcolumn
|
|
\begin{description}
|
|
\item[H4: Inverses Element]\hfill\newline
|
|
Für alle $a\in\mathbb{W}$ gibt es $\overline{a}\in\mathbb{W}$ mit\newline
|
|
$a\otimes\overline{a}=n$\newline
|
|
$a\oplus\overline{a}=e$
|
|
|
|
\textit{Hinweis: Verknüpfung mit dem inversen Element ergibt das
|
|
neutrale Element der jeweils anderen Verknüpfung.}
|
|
\end{description}
|
|
\end{paracol}
|
|
|
|
\section{Schaltalgebra}\index{Schaltalgebra}
|
|
\textbf{Definition}: Schaltalgebra ist ein Spezialfall der Booleschen Algebra mit 2 Werten in der Wertemenge.
|
|
|
|
\begin{tabular}{ll}
|
|
Wertemenge:& $\{1,0\}=\{true, false\}=\{wahr, falsch\}=\{ein, aus\}$\\
|
|
Operatoren:& $\wedge, \vee$, $UND, ODER$ \\
|
|
neutrale Elemente:& $n~\hat{=}~0$, $e~\hat{=}~1$ (\textbf{N}ull, \textbf{E}ins)\\
|
|
Inverses Element:& $a=\overline{a}$
|
|
\end{tabular}
|
|
\bigskip
|
|
|
|
\textit{Warum heißt die Schaltalgebra Schaltalgebra?}
|
|
|
|
Die beiden Operatoren lassen sich einfach mit elektrischen Schaltkreisen und einfachen Ein-/Ausschaltern nachbilden. In \autoref{fig:und_verknuepfung} und \autoref{fig:oder_verknuepfung} auf Seite~\pageref{fig:oder_verknuepfung} wird dies anhand einer \texttt{UND}- und einer \texttt{ODER}-Verknüpfung dargestellt.
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{circuitikz}[font=\sffamily]
|
|
\draw % l steht für label
|
|
(0,0) to [battery1] (0,2) to [switch, l=a] (2.5,2) to [switch,l=b] (5,2) to [lamp] (5,0)
|
|
(0,0) -- (5,0)
|
|
;
|
|
\node[] at (2.5,1) {$a\wedge b$};
|
|
%\node [label=0:$-$] at ([xshift=12.5pt]batt.west) {};
|
|
\end{circuitikz}
|
|
\caption{\texttt{UND}-Verknüpfung}
|
|
\label{fig:und_verknuepfung}
|
|
\end{figure}
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{circuitikz}[font=\sffamily]
|
|
\draw % l steht für label
|
|
(0,0) to[battery1] (0,2) -- (1,2) to[switch,l=a, *-*] (4,2) -- (5,2) -- (5,0) -- (0,0)
|
|
(1,2) -- (1,3)
|
|
to[switch,l=b] (4,3) -- (4,2)
|
|
;
|
|
\node[] at (2.5,1) {$a\vee b$};
|
|
%\node [label=0:$-$] at ([xshift=12.5pt]batt.west) {};
|
|
\end{circuitikz}
|
|
\caption{\texttt{ODER}-Verknüpfung}
|
|
\label{fig:oder_verknuepfung}
|
|
\end{figure}
|
|
|
|
Zudem gibt es die Darstellung mit einer Wahrheitstabelle/Funktionstabelle/Wertetabelle. In \autoref{tbl:werte_und_oder} auf Seite~\pageref{tbl:werte_und_oder} werden hierzu die \texttt{UND}- und die \texttt{ODER}-Verknüpfung dargestellt.
|
|
|
|
\begin{table}[ht]
|
|
\centering
|
|
\begin{tabular}{c|c|c}
|
|
b & a & $a\wedge b$ \\
|
|
\midrule
|
|
0 & 0 & 0\\
|
|
0 & 1 & 0\\
|
|
1 & 0 & 0\\
|
|
1 & 1 & 1\\
|
|
\end{tabular}
|
|
\hspace*{5mm}
|
|
\begin{tabular}{c|c|c}
|
|
b & a & $a\vee b$ \\
|
|
\midrule
|
|
0 & 0 & 0\\
|
|
0 & 1 & 1\\
|
|
1 & 0 & 1\\
|
|
1 & 1 & 1\\
|
|
\end{tabular}
|
|
\caption{Wertetabelle für die \texttt{UND} und \texttt{ODER} Verknüpfung in der Schaltalgebra}
|
|
\label{tbl:werte_und_oder}
|
|
\end{table}
|
|
|
|
|
|
|
|
\begin{Tipp}[frametitle={Tipp: Wie am einfachsten $\vee$ und $\wedge$ merken?}]
|
|
Am einfachsten merkt man sich $\vee$ und $\wedge$ durch folgende Eselsbrücke:
|
|
|
|
\textbf{\uline{U}}ND ist nach \textbf{\uline{u}}nten geöffnet: $\wedge$\newline
|
|
\textbf{\uline{O}}DER ist nach \textbf{\uline{o}}ben geöffnet: $\vee$
|
|
\end{Tipp}
|
|
|
|
%\newpage
|
|
|
|
\subsection{Huntington'sche Axiome in der Schaltalgebra}\index{Huntington'sche Axiome -- Schaltalgebra}
|
|
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\begin{description}
|
|
\item[H1: Kommutativgesetz]\label{H1}\hfill\newline
|
|
$\forall a,b\in\mathbb{W}$\newline
|
|
$a\wedge b = b\wedge a$
|
|
$a\vee b = b\vee a$
|
|
|
|
\item[H2: Distributivgesetz]\label{H2}\hfill\newline
|
|
$a\wedge(b\vee c)=(a\wedge b)\vee (a\wedge c)$ \newline
|
|
$a\vee(b\wedge c)=(a\vee b)\wedge (a\vee c)$
|
|
|
|
\item[H3: Neutrales Element]\label{H3}\hfill\newline
|
|
$a\wedge 1 = a$\newline
|
|
$a\vee 0 = a$
|
|
|
|
\item[H4: Inverses Element]\label{H4}\hfill\newline
|
|
$\forall a \exists\overline{a}$ mit\newline
|
|
$a\wedge \overline{a}=0$\newline
|
|
$a\vee \overline{a}=1$ $\Rightarrow$ $\overline{1}=0$, $\overline{0}=1$
|
|
|
|
\end{description}
|
|
|
|
\switchcolumn
|
|
weitere (abgeleitete) Gesetze:
|
|
|
|
\begin{description}
|
|
\item[Assoziativgesetz] \hfill\newline
|
|
$a\wedge(b\wedge c) = (a\wedge b)\wedge c$\newline
|
|
$a\vee(b\vee c) = (a\vee b)\vee c$
|
|
|
|
\item[Idempotenzgesetz] \hfill\newline
|
|
$a\wedge a = a$ \newline
|
|
$a\vee a = a$
|
|
|
|
\item[Absorptionsgesetz] \hfill\newline
|
|
$a\wedge (a\vee b) = a$ \newline
|
|
$a\vee (a\wedge b) = a$
|
|
|
|
\item[De-Morgan-Gesetz] \hfill\newline
|
|
$\overline{a\wedge b} = \overline{a}\vee\overline{b}$\newline
|
|
$\overline{a\vee b} = \overline{a}\wedge\overline{b}$
|
|
\end{description}
|
|
|
|
\end{paracol}
|
|
\subsection{Beweis von Gesetzen}
|
|
Es werden drei Varianten zum Beweisen von Gesetzen vorgestellt:
|
|
|
|
\subsubsection{1. Ableitung/Umformung}
|
|
Mit Hilfe der Huntington'schen Axiome (und ggf. weiterer \textit{bereits bewiesene} Gesetze) kann eine Verknüpfung umgeformt und dadurch bewiesen werden. Beispiel:
|
|
\begin{align*}
|
|
a &\overset{!}{=} a\wedge a\\
|
|
a&\overset{H3}{=}a\wedge 1 \\
|
|
&\overset{H4}{=}a\wedge(a\vee\overline{a})\\
|
|
&\overset{H2}{=}(a\wedge a)\vee(a\wedge\overline{a})\\
|
|
&\overset{H4}{=}(a\wedge a)\vee 0 \\
|
|
&\overset{H3}{=}a\wedge a \text{ \textcolor{green}{\cmark}}
|
|
\end{align*}
|
|
|
|
|
|
\subsubsection{2. Wertetabelle erstellen und ablesen}
|
|
|
|
Als Beispiel wird das Absorptionsgesetz bewiesen, indem eine Wertetabelle erstellt wird.
|
|
\begin{align*}
|
|
a\wedge(a\vee b)\overset{!}{=}a
|
|
\end{align*}
|
|
|
|
\begin{center}
|
|
\begin{tabular}{c|c|c|c|cl}
|
|
b & a & $a\vee b$& $a\wedge(a\vee b)$& a&\\
|
|
\midrule
|
|
0 & 0 & 0 & 0 & 0 &\textcolor{green}{\cmark}\\
|
|
0 & 1 & 1 & 1 & 1 &\textcolor{green}{\cmark}\\
|
|
1 & 0 & 1 & 0 & 0 &\textcolor{green}{\cmark}\\
|
|
1 & 1 & 1 & 1 & 1 &\textcolor{green}{\cmark}\\
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\subsubsection{3. Existenz des Inversen Elements (über \hyperref[H4]{H4})}
|
|
\begin{align*}
|
|
\forall a\exists\overline{a}: a\wedge \overline{a}= 0 \\
|
|
a\vee \overline{a}=1
|
|
\end{align*}
|
|
|
|
Somit gilt für folgendes:
|
|
\begin{align*}
|
|
a\wedge b = 0 \\
|
|
a\vee b = 1\\
|
|
\Rightarrow a=\overline{b}
|
|
\end{align*}
|
|
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
Damit können wir den Beweis von De Morgan durchführen: $\overline{a\wedge b} \overset{!}{=} \overline{a}\vee \overline{b}$\newline
|
|
Wir wollen beweisen:
|
|
\begin{align}
|
|
\overline{~\overline{a\wedge b}~}\wedge (\overline{a}\wedge \overline{b}) \overset{!}{=}0\label{eq:de_morgan_1} \\
|
|
\overline{~\overline{a\wedge b}~}\vee (\overline{a}\vee \overline{b})\overset{!}{=}1\label{eq:de_morgan_2}
|
|
\end{align}
|
|
|
|
Bevor wir diese Gesetze jedoch beweisen können, müssen wir zuerst einige andere beweisen.
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
\textbf{Gesetz der doppelten Negation}: $\overline{\overline{x}}\overset{!}{=}x$
|
|
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
Über eine Wertetabelle
|
|
\begin{center}
|
|
\begin{tabular}{l|l|ll}
|
|
x & $\overline{x}$ & $\overline{~\overline{x}~}$\\
|
|
\midrule
|
|
0 & 1 & 0 & \textcolor{green}{\cmark} \\
|
|
1 & 0 & 1 & \textcolor{green}{\cmark} \\
|
|
\end{tabular}
|
|
\end{center}
|
|
\switchcolumn
|
|
Über die Interpretation von \hyperref[H4]{H4}:
|
|
\begin{align*}
|
|
\overline{\overline{x}}\wedge \overline{x}\overset{H4}{=}0 \\
|
|
\overline{\overline{x}}\vee \overline{x}\overset{H4}{=}1
|
|
\end{align*}
|
|
\end{paracol}
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\textbf{Beweis der 0-Absorption}:
|
|
\begin{align*}
|
|
x\wedge 0 &\overset{!}{=}0 \\
|
|
x\wedge 0 &\overset{H4}{=} x\wedge(x\wedge\overline{x})\\
|
|
&\overset{Ass.}{=} (x\wedge x)\wedge\overline{x}\\
|
|
&\overset{Idempot.}{=}x\wedge\overline{x}\\
|
|
&\overset{H4}{=}0\text{~\textcolor{green}{\cmark}}
|
|
\end{align*}
|
|
\switchcolumn
|
|
\textbf{Beweis der 1-Absorption}:
|
|
\begin{align*}
|
|
x\vee 1 &= 1 \\
|
|
x\vee 1 &\overset{H4}{=} x\vee (x\vee\overline{x})\\
|
|
&\overset{Ass.}{=}(x\vee x)\vee\overline{x}\\
|
|
&\overset{Idempot.}{=}x\vee \overline{x}\\
|
|
&\overset{H4}{=}1\text{~\textcolor{green}{\cmark}}
|
|
\end{align*}
|
|
\end{paracol}
|
|
|
|
|
|
|
|
\textbf{Beweisen von \autoref{eq:de_morgan_1}.}
|
|
\begin{align*}
|
|
\overline{~\overline{a\wedge b}~} \wedge (\overline{a}\vee \overline{b}) &\overset{dopp.~Neg}{=} (a\wedge b) \wedge (\overline{a}\vee b)\\
|
|
&\overset{H2}{=}~(a\wedge b \wedge \overline{a})\vee (a\wedge b \wedge \overline{b})\\
|
|
&\overset{H1}{=}~(b\wedge a \wedge \overline{a})\vee (a\wedge b \wedge \overline{b})\\
|
|
&\overset{H4}{=}~(b\wedge 0)\vee (a\wedge 0)\\
|
|
&\overset{0-Absorption}{=}0\vee 0\\
|
|
&\overset{Idempot.}{=}~0\text{~\textcolor{green}{\cmark}}
|
|
\end{align*}
|
|
|
|
\textbf{Wir beweisen \autoref{eq:de_morgan_2}}
|
|
\begin{align*}
|
|
\overline{~\overline{a\wedge b}~}\vee (\overline{a}\vee \overline{b})&\overset{!}{=}1 \\
|
|
\overline{\overline{a\wedge b}} \vee (\overline{a}\vee\overline{b})&\overset{dopp.~Neg.}{=}(a\wedge b)\vee (\overline{a}\vee\overline{b})\\
|
|
&\overset{H2}{=}(a\vee\overline{a}\vee\overline{b})\wedge(b\vee\overline{a}\vee\overline{b})\\
|
|
&\overset{H1}{=}(a\vee\overline{a}\vee\overline{b})\wedge(\overline{a}\vee b\vee \overline{b})\\
|
|
&\overset{H4}{=}(1\vee\overline{b})\wedge(\overline{a}\vee 1)\\
|
|
&\overset{\textit{1-Absorp.}}{=}1\wedge 1\\
|
|
&\overset{Idempot.}{=}1\text{~\textcolor{green}{\cmark}}
|
|
\end{align*}
|
|
|
|
\textbf{Wir beweisen das Assiozativgesetz über eine Wertetabelle:}
|
|
|
|
\begin{table}[h]
|
|
\centering
|
|
\begin{tabular}{c|ccc|c|c|c|cl}
|
|
Nr. & $c$ & $b$ & $a$ & $(a\vee b)$ & $(a\vee b)\vee c$ & $(b\vee c)$ & $a\vee (b\vee c)$ \\
|
|
\midrule
|
|
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textcolor{green}{\cmark} \\
|
|
1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & \textcolor{green}{\cmark} \\
|
|
2 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & \textcolor{green}{\cmark} \\
|
|
3 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & \textcolor{green}{\cmark} \\
|
|
4 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & \textcolor{green}{\cmark} \\
|
|
5 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & \textcolor{green}{\cmark} \\
|
|
6 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & \textcolor{green}{\cmark} \\
|
|
7 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \textcolor{green}{\cmark} \\
|
|
\end{tabular}
|
|
\caption{Beweis des Assoziativgesetzes}
|
|
\end{table}
|
|
|
|
\subsection{Boolescher Ausdruck}
|
|
|
|
\begin{Hinweis}
|
|
Wenn Herr Röthig im Unterricht \enquote{boolescher Ausdruck} sagt, meint er einen Ausdruck der Schaltalgebra.
|
|
\end{Hinweis}
|
|
|
|
Ein boolescher Ausdruck besteht aus Konstanten, Variablen und Operatoren!
|
|
|
|
\textbf{Operatoren}:
|
|
\begin{itemize}[noitemsep]
|
|
\item zweistellige Operatoren: $\wedge, \vee \Rightarrow$ verknüpfen zwei Werte, welche links und rechts des Operators notiert sind.
|
|
\item einstelliger Operator: $\overline{x} \Rightarrow$ bezieht sich auf nur einen Wert.
|
|
\item Alternative Schreibweisen:
|
|
\begin{itemize}[noitemsep]
|
|
\item $\neg x = \overline{x}$
|
|
\item $x \wedge y = x\cdot y=xy$
|
|
\item $x\vee y = x+y$ (selten verwendet)
|
|
\end{itemize}
|
|
|
|
\item Operatorenbindungskraft:\newline
|
|
Beispiel: $\neg x\vee y\neq \neg(x\vee y)$ bzw. $\overline{x}\vee y\neq \overline{x\vee y}$
|
|
\begin{itemize}[noitemsep]
|
|
\item $\neg$ bindet stärker als $\wedge$
|
|
\item $\wedge$ bindet stärker als $\vee$
|
|
\end{itemize}
|
|
|
|
Ausdrücke stärker bindender Operatoren werden zuerst ausgewertet. Die Reihenfolge der Auswertung kann auch mit Klammern gezielt beeinflusst werden, \dash Klammern binden stärker als jeder Operator\newline
|
|
$\Rightarrow$ die Auswertung von booleschen Ausdrücken erfolgt immer \enquote{von innen nach außen}.
|
|
\end{itemize}
|
|
|
|
\subsubsection{Belegung und Funktionen}
|
|
\begin{description}
|
|
\item[Belegung]\index{Belegung}
|
|
Zuordnung eines bestimmten Wertes zu jeder Variablen.
|
|
|
|
\item[Funktion]\index{Funktion} Zuweisung einer Ausgangsbelegung
|
|
(\enquote{Funktionswert}) zu jeder Eingangsbelegung.
|
|
\end{description}
|
|
|
|
\textbf{Hinweis}: Es gibt auch mehrstellige Funktionen, welche einer Eingangsbelegung
|
|
gleichzeitig mehrere Ausgangsbelegungen (in festgelegter Reihenfolge) zuweisen.
|
|
|
|
Eine $n$-stellige Funktion kann durch $n$ einstellige Funktionen dargestellt werden.
|
|
|
|
Darstellung (\enquote{Definition}) einer booleschen Funktion:
|
|
|
|
\begin{enumerate}[label=\alph*)]
|
|
\item über einen booleschen (Funktions-)Ausdruck. \newline
|
|
Beispiel: $f(a,b)=a\wedge b$ $\Rightarrow$ Funktion abhängig von
|
|
zwei Variablen $a$ und $b$.\newline
|
|
\phantom{Beispiel:} $f(a)\phantom{,b} = \neg a\phantom{\wedge ,}$ $\Rightarrow$ Funktion abhängig von einer Variablen $a$.
|
|
|
|
zweistellige Operatoren lassen sich als Funktionen von zwei Variablen darstellen.\newline
|
|
einstellige Operatoren lassen sich als Funktionen von einer Variablen darstellen.
|
|
|
|
\textit{Wie viele verschiedene Funktionen abhängig von $n$ Variablen gibt es?}\newline
|
|
$f(a)=\neg a=\neg\neg\neg a=\neg\neg\neg\neg\neg a=\neg(a\wedge a)$
|
|
|
|
Zwei Funktionen heißen äquivalent, wenn:
|
|
\begin{itemize}[noitemsep]
|
|
\item beide booleschen Funktionsausdrücke die gleiche Wertetabelle aufweisen \textit{oder}
|
|
\item der eine Funktionsausdruck in den anderen Ausdruck umgeformt werden kann.
|
|
\end{itemize}
|
|
|
|
So sind die Funktionsausdrücke im Beispiel oben alle äquivalent.
|
|
|
|
Die Umformung funktioniert auch bei Funktionen von Zahlen, während die
|
|
Wertetabelle bei zahlen nicht funktioniert, da es unendlich viele Werte gibt!
|
|
|
|
|
|
\textbf{Funktion abhängig von 0-Variablen:}
|
|
\begin{equation*}
|
|
\left.\begin{aligned}
|
|
f_0=0 \text{ \enquote{Nullfunktion}} \\
|
|
f_1=1 \text{ \enquote{Einsfunktion}}
|
|
\end{aligned}\right\rbrace
|
|
\Rightarrow \text{zwei verschiedene Funktionen abhängig von keiner Variablen}
|
|
\end{equation*}
|
|
|
|
|
|
\textbf{Funktionen abhängig von 1 Variable:}
|
|
\begin{center}
|
|
\begin{tabular}{l|l|l|l|l}
|
|
a & $f_0$ & $f_1$ & $f_2$ & $f_3$\\
|
|
\midrule
|
|
0 & 0 & 1 & 0 & 1 \\
|
|
1 & 0 & 0 & 1 & 1
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\begin{align*}
|
|
\left.\begin{aligned}
|
|
f_2(a)&=a \text{ \enquote{Identität von a}} \\
|
|
f_1(a)&=\overline{a} \text{ \enquote{Negation von a}} \\
|
|
f_0(a)&=0 \text{ \enquote{Nullfunktion}} \\
|
|
f_3(a)&=1 \text{ \enquote{Einsfunktion}} \\
|
|
\end{aligned}\right\rbrace
|
|
\Rightarrow \text{vier verschiedene Funktionen abhängig von einer Variablen}
|
|
\end{align*}
|
|
|
|
|
|
\textbf{Funktionen abhängig von 2 Variablen:}
|
|
|
|
\begin{tabular}{l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l}
|
|
b & a & $f_0$ & $f_1$ & $f_2$ & $f_3$ & $f_4$ & $f_5$ & $f_6$ & $f_7$ & $f_8$ & $f_9$ & $f_{10}$ & $f_{11}$ & $f_{12}$ & $f_{13}$ & $f_{14}$ & $f_{15}$\\
|
|
\midrule
|
|
0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
|
|
0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
|
|
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
|
|
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
|
|
\midrule
|
|
|
|
\multicolumn{2}{c|}{$f(a,b)$}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{0}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$\neg(a\vee b)$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$\overline{a\rightarrow b}$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$\overline{b}$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$\overline{b\rightarrow a}$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$\overline{a}$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$(a\vee b)\wedge\neg(a\wedge b)=a\overline{b}\vee\overline{a}b$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$\neg(a\wedge b)$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$a\wedge b$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$a \leftrightarrow b$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{a}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$b\rightarrow a$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{b}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$a\rightarrow b$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{$a\vee b$}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{1}} \\
|
|
\midrule
|
|
|
|
\multicolumn{2}{c|}{\parbox[t]{2mm}{\rotatebox[origin=c]{90}{Bezeichnung}}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Nullfunktion}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Nicht-ODER}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Inhibition (negierte Implikation)}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Negation von b}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Inhibition (negierte Implikation)}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Negation von a}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Exklusiv-Oder / Antivalenz}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Nicht-UND}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{UND-Funktion}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Äquivalenz}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Identität von a}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Implikation (aus b folgt a)}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Identität von b}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Implikation (aus a folgt b)}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{ODER-Funktion}}
|
|
& \parbox[t]{2mm}{\rotatebox[origin=c]{90}{Einsfunktion}}
|
|
\end{tabular}
|
|
|
|
\bigskip
|
|
|
|
$\Rightarrow$ insgesamt \textbf{16} verschiedene Funktionen abhängig von 2 Variablen!
|
|
\begin{Hinweis}[frametitle=Hinweis -- Implikation]
|
|
Implikation: $a\rightarrow b$ \enquote{Wenn $a$ gilt, gilt auch $b$}
|
|
|
|
\zB $a\hat{=}$ \enquote{es regnet}\newline
|
|
\phantom{\zB}$b\hat{=}$ \enquote{der Hof ist nass}
|
|
\end{Hinweis}
|
|
|
|
\end{enumerate}
|
|
|
|
Alle Funktionen abhhängig von $n$ Variablen, werden in \autoref{tbl:n_funktionen} auf Seite~\pageref{tbl:n_funktionen} dargestellt.
|
|
Die Anzahl unterschiedlicher Funktionen wächst mit steigender Anzahl von Eingangsvariablen rasant!
|
|
|
|
\begin{table}[h]
|
|
\centering
|
|
\begin{tabular}{c|c|c}
|
|
$n$ & \#Fkt = ${2^2}^n$ & \#ZeilenWertetabelle = $2^n$ \\
|
|
\midrule
|
|
0 & 2 & 1 \\
|
|
1 & 4 & 2 \\
|
|
2 & 16 & 4 \\
|
|
3 & 256 & 8 \\
|
|
4 & 65536 & 16 \\
|
|
5 & $\approx 4 Mrd.$ & 32 \\
|
|
6 & $\approx 16 Trillionen$ & 64
|
|
\end{tabular}
|
|
\caption{Boolesche Algebra -- Anzahl Funktionen und Zeilen in einer Wertetabelle}
|
|
\label{tbl:n_funktionen}
|
|
\end{table}
|
|
|
|
|
|
\begin{description}
|
|
\item[vollständiges Operatorensystem]\index{Operatorensystem} \hfill\newline
|
|
Ein vollständiges Operatorensystem ist eine Menge an (ein- und zweistelligen) Operatoren, mit deren Hilfe wir jede Funktion (abhängig von beliebig vielen Variablen) als algebraischen Funktionsausdruck darstellen können!
|
|
\end{description}
|
|
|
|
\begin{satz}
|
|
$\{\wedge,\vee,\neg\}$ sind ein vollständiges Operatorensystem der Booleschen Algebra.
|
|
\end{satz}
|
|
\textsf{\textbf{Beweis}}: Definition der Booleschen Algebra\ldots
|
|
|
|
\begin{satz}
|
|
$\{\wedge,\neg\}$ ist ein vollständiges Operatorensystem der Booleschen Algebra.
|
|
\end{satz}
|
|
\textsf{\textbf{Beweis}}: $a\vee b \overset{dopp.~Neg.}{=} \overline{~\overline{a\vee b}~}~\overset{de~Morgan}{=}~\overline{\overline{a}\wedge\overline{b}}$
|
|
|
|
\begin{satz}
|
|
$\{\vee,\neg\}$ ist ein vollständiges Operatorensystem der Booleschen Algebra.
|
|
\end{satz}
|
|
\textsf{\textbf{Beweis}}: $a\wedge b \overset{dopp.~Neg.}{=} \overline{~\overline{a\wedge b}~}~\overset{de~Morgan}{=}~\overline{\overline{a}\vee\overline{b}}$
|
|
|
|
\begin{satz}
|
|
$\{\overline{\wedge}\}$ ist ein vollständiges Operatorensystem der Booleschen Algebra
|
|
\end{satz}
|
|
\textsf{\textbf{Beweis}}: $\neg a\overset{Idempot.}{=}\neg(a\wedge a)=a\overline{\wedge}a$\newline
|
|
\phantom{\textsf{\textbf{Beweis:}}} $a\wedge b \overset{dopp.~Neg.}{=} \overline{~\overline{a\wedge b}~}=\overline{(a\overline{\wedge}b)}\overset{Idempot.}{=}\overline{(a\overline{\wedge}b)\wedge(a\overline{\wedge}b)} = (a\overline{\wedge}b)\overline{\wedge}(a\overline{\wedge}b)$
|
|
|
|
\begin{satz}
|
|
$\{\overline{\vee}\}$ ist ein vollständiges Operatorensystem der Booleschen Algebra.
|
|
\end{satz}
|
|
\textsf{\textbf{Beweis}}: $\neg a\overset{Idempot.}{=}\neg(a\vee a)=a\overline{\vee}a$\newline
|
|
\phantom{\textsf{\textbf{Beweis:}}} $a\vee b \overset{dopp.~Neg.}{=} \overline{~\overline{a\vee b}~}=\overline{(a\overline{\vee}b)}\overset{Idempot.}{=}\overline{(a\overline{\vee}b)\vee(a\overline{\vee}b)} = (a\overline{\vee}b)\overline{\vee}(a\overline{\vee}b)$
|
|
|
|
Anwendung: IC-Design, \zB Bausteine in \enquote{NAND-Technologie} realisiert.
|
|
|
|
\begin{Hinweis}
|
|
Wir arbeiten üblicherweise mit $\{\neg,\wedge,\vee\}$ als vollständiges Operatorensystem.
|
|
\end{Hinweis}
|
|
|
|
\textit{Frage}: Wie können wir feststellen, ob zwei Funktionen $f$ und $g$ äquivalent sind?
|
|
\begin{itemize}[noitemsep]
|
|
\item Vergleich anhand der Wertetabelle $\Rightarrow$ einfach
|
|
\item Vergleich der Booleschen Ausdrücke $\Rightarrow$ schwierig, denn für die Umformung gibt es immer viele Möglichkeiten.
|
|
|
|
\end{itemize}
|
|
|
|
Gibt es vielleicht \enquote{spezielle Boolesche Ausdrücke}, welche wir \enquote{einfach} vergleichen könnten?
|
|
|
|
$\Rightarrow$ Wir suchen einen \enquote{standardisierten}/\enquote{normierten} Funktionsausdruck!
|
|
|
|
Die Wertetabelle ist quasi \enquote{standardisiert} $\Rightarrow$ Wie kann man aus der Wertetabelle einen Funktionsausdruck gewinnen?
|
|
|
|
\begin{table}[h]
|
|
\centering
|
|
\begin{tabular}{c|ccc|cl}
|
|
Nr. & $c$ & $b$ & $a$ & $f(a,b,c)$ \\
|
|
\midrule
|
|
0 & 0 & 0 & 0 & 0 & \\
|
|
1 & 0 & 0 & 1 & 1 & $\Leftarrow$ $\overline{c}~\overline{b}~ a$ \\
|
|
2 & 0 & 1 & 0 & 1 & $\Leftarrow$ $\overline{c}~b~\overline{a}$ \\
|
|
3 & 0 & 1 & 1 & 1 & $\Leftarrow$ $\overline{c}~b~a$ \\
|
|
4 & 1 & 0 & 0 & 0 & \\
|
|
5 & 1 & 0 & 1 & 0 & \\
|
|
6 & 1 & 1 & 0 & 1 & $\Leftarrow$ $c~b~\overline{a}$ \\
|
|
7 & 1 & 1 & 1 & 0 & \\
|
|
\end{tabular}
|
|
\caption{Boolesche Algebra -- Von Wertetabelle zur Funktion}
|
|
\label{tbl:von_wertetabelle_zur_funktion}
|
|
\end{table}
|
|
|
|
Wir betrachten nur die \enquote{1}-Belegung von $f$ $\Rightarrow$ die Vollkonjunktion $\overline{c}~\overline{b}~ a$ ergibt nur für Zeile 1 eine \enquote{1}, für alle anderen Zeilen ergibt sich eine \enquote{0}. Somit ergeben alle Vollkonjunktionen verodert den entsprechenden Funktionsterm!\newline
|
|
$\overline{c}~\overline{b}~ a \vee \overline{c}~b~\overline{a} \vee \overline{c}~b~a \vee c~b~\overline{a}$ $\Rightarrow$ \acf{DNF} von $f$
|
|
|
|
\begin{description}
|
|
\item[\acl{DNF}]\index{Disjunkte Normalform} \hfill\newline
|
|
Die \acf{DNF} einer Funktion $f$ ist die Disjunktion (\texttt{ODER}-Verknüpfung) aller Vollkonjunktionen der Funktion $f$.
|
|
|
|
\item[Vollkonjunktion]\index{Vollkonjunktion} \hfill\newline
|
|
Eine Konjunktion (\texttt{UND}-Verknüpfung) von Literalen (für jede Variable ein Literal), für welche die Funktion den Funktionswert \enquote{1} ergibt, heißt Vollkonjunktion der Funktion $f$.
|
|
|
|
\item[Literal]\index{Literal} \hfill\newline
|
|
Eine Eingangsvariable in negierter oder nicht-negierter Form heißt Literal.
|
|
\end{description}
|
|
|
|
\begin{satz}
|
|
Die \acs{DNF} einer Funktion ist eindeutig bis auf die Reihenfolge der Vollkonjunktionen, sowie die Reihenfolge der Literale in den Vollkonjunktionen.
|
|
\end{satz}
|
|
\textsf{\textbf{Beweis}}: Über Wertetabelle bzw. die Regeln, wie wir die \acs{DNF} aus der Wertetabelle bilden.
|
|
|
|
\subsection{Darstellung von booleschen Funktionen}
|
|
|
|
\begin{enumerate}[noitemsep]
|
|
\item boolescher Ausdruck (allgemein)\newline
|
|
Spezialformen: \acs{DNF} (im weiteren Verlauf der Vorlesung lernen wir weitere kennen)
|
|
\item Wertetabelle
|
|
\item \hyperref[sec:schaltnetz]{Schaltnetz}
|
|
\item \hyperref[sec:kv_diagramm]{KV-Diagramm}
|
|
\end{enumerate}
|
|
|
|
\subsection{Schaltnetz}\label{sec:schaltnetz}
|
|
|
|
Darstellung einer booleschen Funktion als Graph. Graphen bestehen aus Knoten und Kanten. Knoten sind \enquote{Gatter} und entsprechen den Operatoren. Kanten sind die Verbindungen/\enquote{Leitungen} zwischen den Gattern.
|
|
|
|
Genauer: Schaltnetze sind gerichtete Graphen, \dash die Kanten haben jeweils eine Richtung (anders gesagt: Die Knoten haben Aus- und Eingänge).
|
|
|
|
\newpage
|
|
\subsubsection{Gatter}
|
|
%
|
|
%\begin{Achtung}
|
|
% Im folgenden gibt es leider eine technische Einschränkung. Das NICHT kann mit dem verwendeten Paket nicht auf die \enquote{deutsche Art} dargestellt werden. Beispiel:
|
|
% \begin{center}
|
|
% \begin{circuitikz}[font=\sffamily, circuit logic IEC]
|
|
% \draw (5,0) node[european xnor port] (port) {};
|
|
% \draw (0,0) node[xnor gate] (port) {};
|
|
% \end{circuitikz}
|
|
% \end{center}
|
|
% Die linke Seite zeigt ein korrektes XNOR, während auf der rechten Seite anstatt des \enquote{Kringels} ein schräger Strich am Ausgang gezeichnet wird. Alle Negationen enthalten im folgenden den schrägen Strich, auch wenn der \enquote{Kringel} die korrekte Darstellung ist!
|
|
%\end{Achtung}
|
|
|
|
\columnratio{0.4}
|
|
\begin{paracol}{2}
|
|
\begin{description}
|
|
\item[Identer] \enquote{eine Art Verstärker}
|
|
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols]
|
|
\node[buffer gate, draw] at (0, 0) (BUFFER) {};
|
|
\node (a) at ($(BUFFER.input) - (0.5, 0)$) {a};
|
|
\node (b) at ($(BUFFER.output) + (0.6, 0)$) {a};
|
|
|
|
\draw (a) -- (BUFFER.input);
|
|
\draw (b) -- (BUFFER.output);
|
|
\end{tikzpicture}
|
|
|
|
\item[Negation] Inverter/NOT/$\neg a$
|
|
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols]
|
|
\node[not gate, draw] at (0, 0) (nota) {};
|
|
\node (a) at ($(nota.input) - (0.5, 0)$) {a};
|
|
\node (b) at ($(nota.output) + (0.6, 0)$) {$\neg a$};
|
|
|
|
\draw (a) -- (nota.input);
|
|
\draw (b) -- (nota.output);
|
|
\end{tikzpicture}
|
|
|
|
\item[Konjunktion] UND/AND
|
|
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols]
|
|
\node[and gate, inputs={nn}] at (0,0) (AND) {};
|
|
\draw (AND.output) -- ++(right:5mm);
|
|
\foreach \a in {1,...,2} {
|
|
\draw (AND.input \a -| -0.8,0) -- (AND.input \a);
|
|
}
|
|
|
|
\node at (AND.input 1 -| -1.0,0) {a};
|
|
\node at (AND.input 2 -| -1.0,0) {b};
|
|
\node at (AND.output -| 1.5,0) {$a\wedge b$};
|
|
\end{tikzpicture}
|
|
\end{description}
|
|
\switchcolumn
|
|
\begin{description}
|
|
\item[Disjunktion] ODER/OR
|
|
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols]
|
|
\node[or gate, inputs={nn}] at (0,0) (OR) {};
|
|
\draw (OR.output) -- ++(right:5mm);
|
|
\foreach \a in {1,...,2} {
|
|
\draw (OR.input \a -| -0.8,0) -- (OR.input \a);
|
|
}
|
|
|
|
\node at (OR.input 1 -| -1.0,0) {a};
|
|
\node at (OR.input 2 -| -1.0,0) {b};
|
|
\node at (OR.output -| 1.5,0) {$a\vee b$};
|
|
\end{tikzpicture}
|
|
|
|
\item[Antivalenz] XOR/Exklusiv ODER (nur zwei Eingänge)
|
|
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols]
|
|
\node[xor gate, inputs={nn}] at (0,0) (XOR) {};
|
|
\draw (XOR.output) -- ++(right:5mm);
|
|
\foreach \a in {1,...,2} {
|
|
\draw (XOR.input \a -| -0.8,0) -- (XOR.input \a);
|
|
}
|
|
|
|
\node at (XOR.input 1 -| -1.0,0) {a};
|
|
\node at (XOR.input 2 -| -1.0,0) {b};
|
|
\node at (XOR.output -| 1.5,0) {$\overline{a \longleftrightarrow b}$};
|
|
\end{tikzpicture}
|
|
|
|
\item[Äquivalenz] XNOR (nur zwei Eingänge)
|
|
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols]
|
|
\node[xnor gate, inputs={nn}] at (0,0) (XNOR) {};
|
|
\draw (XNOR.output) -- ++(right:4mm);
|
|
\foreach \a in {1,...,2} {
|
|
\draw (XNOR.input \a -| -0.8,0) -- (XNOR.input \a);
|
|
}
|
|
|
|
\node at (XNOR.input 1 -| -1.0,0) {a};
|
|
\node at (XNOR.input 2 -| -1.0,0) {b};
|
|
\node at (XNOR.output -| 1.6,0) {$a \longleftrightarrow b$};
|
|
\end{tikzpicture}
|
|
|
|
\end{description}
|
|
|
|
\end{paracol}
|
|
|
|
Die Richtung der Kanten wird (meist) nicht explizit (\zB durch Pfeile), sondern implizit gegeben, dass die Eingänge sich bei den Gattern links (oder oben) und die Ausgänge rechts (oder unten) befinden.
|
|
Beispiel: siehe \autoref{fig:beispiel_gatter}.
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{circuitikz}[font=\sffamily]
|
|
\draw
|
|
(0,1) node[european and port] (orport) {}
|
|
node[below right=0mm of orport, european or port] (portAB) {}
|
|
node[below left=0mm and 20mm of portAB] (portC) {c}
|
|
(orport.in 1) node[anchor=east] {a}
|
|
(orport.in 2) node[anchor=east] {b}
|
|
(portAB.out) node[anchor=west] {$f(a,b,c)=(a\wedge b)\vee c$}
|
|
(orport.out) -| (portAB.in 1)
|
|
(portC) -| (portAB.in 2)
|
|
;
|
|
\end{circuitikz}
|
|
\caption{Beispiel für Gatter}
|
|
\label{fig:beispiel_gatter}
|
|
\end{figure}
|
|
|
|
\textbf{Weitere Regeln}: Jeder Ausgang und Eingang kann mit Hilfe eines \enquote{Kringels} ($\circ$, nicht ausgefüllter Kreis), negiert werden.
|
|
|
|
\texttt{UND}- und \texttt{ODER}-Gatter können auch mehr als zwei Eingänge haben. Vergleiche hierzu \autoref{fig:gatter_mehrere_eingaenge_1} und \autoref{fig:gatter_mehrere_eingaenge_2}.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[and gate, inputs={in}] at (0,2) (PORT) {};
|
|
\node[and gate, inputs={nn}] at (1.5,1) (PORT2) {};
|
|
\node[] at (-1,0) (C) {c};
|
|
|
|
\draw (PORT.input 1 -| -0.8,0) -- (PORT.input 1);
|
|
\draw (PORT.input 2 -| -0.8,0) -- (PORT.input 2);
|
|
\node at (PORT.input 1 -| -1.0,0) (A) {a};
|
|
\node at (PORT.input 2 -| -1.0,0) (B) {b};
|
|
|
|
\draw (PORT.output) -| ([xshift=-5mm]PORT2.input 1) -- (PORT2.input 1);
|
|
\draw (C) -| ([xshift=-5mm]PORT2.input 2) -- (PORT2.input 2);
|
|
\draw (PORT2.output) -- ([xshift=8mm]PORT2.output);
|
|
\node[right=of PORT2.output] {$\overline{a}\wedge b\wedge c$};
|
|
|
|
\end{tikzpicture}
|
|
\caption{Gatter -- Mehrere Eingänge -- Variante 1}
|
|
\label{fig:gatter_mehrere_eingaenge_1}
|
|
\end{figure}
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[and gate, inputs={inn}] at (0,0) (PORT) {};
|
|
|
|
\draw (PORT.input 1 -| -0.8,0) -- (PORT.input 1);
|
|
\draw (PORT.input 2 -| -0.8,0) -- (PORT.input 2);
|
|
\draw (PORT.input 3 -| -0.8,0) -- (PORT.input 3);
|
|
\node at (PORT.input 1 -| -1.0,0) (A) {a};
|
|
\node at (PORT.input 2 -| -1.0,0) (B) {b};
|
|
\node at (PORT.input 3 -| -1.0,0) (C) {c};
|
|
|
|
\draw (PORT.output) -- ([xshift=8mm]PORT.output);
|
|
\node[right=of PORT.output] {$\overline{a}\wedge b\wedge c$};
|
|
|
|
\end{tikzpicture}
|
|
\caption{Gatter -- Mehrere Eingänge -- Variante 2}
|
|
\label{fig:gatter_mehrere_eingaenge_2}
|
|
\end{figure}
|
|
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[and gate, inputs={nn}] at (0,2) (PORT) {};
|
|
\draw (PORT.input 1 -| -1.8,0) -- (PORT.input 1);
|
|
\draw (PORT.input 2 -| -0.8,0) -- (PORT.input 2);
|
|
\node at (PORT.input 1 -| -2.0,0) (A) {a};
|
|
\node at (PORT.input 2 -| -1.0,0) (B) {b};
|
|
|
|
\node[and gate, inputs={nn}] at (0,0) (PORT2) {};
|
|
\draw (PORT2.input 2 -| -0.8,0) -- (PORT2.input 2);
|
|
\node at (PORT2.input 2 -| -1.0,0) {c};
|
|
\draw (A) ++(right:5mm) |- (PORT2.input 1);
|
|
\node[knoten] at ([xshift=5mm]A) {};
|
|
|
|
\node[or gate, inputs={nn}] at (2,1) (PORT3) {};
|
|
|
|
\draw (PORT.output) -- ++(right:7mm) |- (PORT3.input 1);
|
|
\draw (PORT2.output) -- ++(right:7mm) |- (PORT3.input 2);
|
|
|
|
\draw ([xshift=8mm]PORT3.output) -- (PORT3.output);
|
|
\node[right=of PORT3.output] {$\overline{a \longleftrightarrow b}$};
|
|
|
|
\end{tikzpicture}
|
|
\caption{Gatter -- $(a\wedge b)\vee(a\wedge c)$}
|
|
\label{fig:gatter_leitung_aufspaltung}
|
|
\end{figure}
|
|
|
|
Wie \autoref{fig:gatter_leitung_aufspaltung} zeigt, sind Aufspaltungen von Leitungen möglich, indem die Leitungen über einen ausgefüllten Kreis ($\bullet$) miteinander verbunden werden.
|
|
|
|
Die \acs{DNF}: $\overline{c}~\overline{b}~ a \vee \overline{c}~b~\overline{a} \vee \overline{c}~b~a \vee c~b~\overline{a}$ ergibt das Gatter, wie es in \autoref{fig:gatter_dnf} auf Seite~\pageref{fig:gatter_dnf} dargestellt wird.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\node at (0.5,5.5) (C) {c};
|
|
\node at (1,5.5) (B) {b};
|
|
\node at (1.5,5.5) (A) {a};
|
|
|
|
|
|
\node[and gate, inputs={nii}] at (3,4.5) (PORT1) {};
|
|
\node[and gate, inputs={ini}] at (3,3) (PORT2) {};
|
|
\node[and gate, inputs={nni}] at (3,1.5) (PORT3) {};
|
|
\node[and gate, inputs={inn}] at (3,0) (PORT4) {};
|
|
\node[or gate, inputs={nnnn}] at (5,2) (PORT5) {};
|
|
|
|
\draw (PORT1.output) -- ([xshift=7mm]PORT1.output) |- (PORT5.input 1);
|
|
\draw (PORT2.output) -- ([xshift=5mm]PORT2.output) |- (PORT5.input 2);
|
|
\draw (PORT3.output) -- ([xshift=5mm]PORT3.output) |- (PORT5.input 3);
|
|
\draw (PORT4.output) -- ([xshift=7mm]PORT4.output) |- (PORT5.input 4);
|
|
% -| nutzt nur eine Koordinate
|
|
\draw (A) |- (PORT1.input 1); \node[knoten] at (PORT1.input 1 -| A) {};
|
|
\draw (A) |- (PORT2.input 1); \node[knoten] at (PORT2.input 1 -| A) {};
|
|
\draw (A) |- (PORT3.input 1); \node[knoten] at (PORT3.input 1 -| A) {};
|
|
\draw (A) |- (PORT4.input 1); \node[knoten] at (PORT4.input 1 -| A) {};
|
|
|
|
\draw (B) |- (PORT1.input 2); \node[knoten] at (PORT1.input 2 -| B) {};
|
|
\draw (B) |- (PORT2.input 2); \node[knoten] at (PORT2.input 2 -| B) {};
|
|
\draw (B) |- (PORT3.input 2); \node[knoten] at (PORT3.input 2 -| B) {};
|
|
\draw (B) |- (PORT4.input 2); \node[knoten] at (PORT4.input 2 -| B) {};
|
|
|
|
\draw (C) |- (PORT1.input 3); \node[knoten] at (PORT1.input 3 -| C) {};
|
|
\draw (C) |- (PORT2.input 3); \node[knoten] at (PORT2.input 3 -| C) {};
|
|
\draw (C) |- (PORT3.input 3); \node[knoten] at (PORT3.input 3 -| C) {};
|
|
\draw (C) |- (PORT4.input 3); \node[knoten] at (PORT4.input 3 -| C) {};
|
|
|
|
\draw (PORT5.output) -- ([xshift=8mm]PORT5.output);
|
|
\node[right=of PORT5.output] {$\overline{c}~\overline{b}~ a \vee \overline{c}~b~\overline{a} \vee \overline{c}~b~a \vee c~b~\overline{a}$};
|
|
|
|
\end{tikzpicture}
|
|
\caption{Gatter -- DNF Beispiel für $\overline{c}~\overline{b}~ a \vee \overline{c}~b~\overline{a} \vee \overline{c}~b~a \vee c~b~\overline{a}$}
|
|
\label{fig:gatter_dnf}
|
|
\end{figure}
|
|
|
|
\begin{Hinweis}
|
|
Sich überkreuzende Leitungen sind ohne ausgefüllten Kreis nicht miteinander verbunden!
|
|
\end{Hinweis}
|
|
|
|
\begin{Hinweis}
|
|
|
|
\enquote{Zusammenführen} von Leitungen ist verboten (elektrotechnisch würde dies einem Kurzschluss entsprechen!
|
|
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\node at (0,1) (A) {a};
|
|
\node at (0,0.5) (B) {b};
|
|
\draw ([xshift=5mm]A) -- (1,1) -- (1,0);
|
|
\draw ([xshift=5mm]B) -- (1,0.5);
|
|
\node[knoten] at (1,0.5) {};
|
|
\draw[red, thick] (-0.1,-0.1) -- (1.1,1.1) (1,-0.1) -- (-0.1,1.1);
|
|
\end{tikzpicture}
|
|
|
|
\end{Hinweis}
|
|
|
|
|
|
\enquote{Bauchgefühl}: Die Realisierung der \acs{DNF} als Schaltnetz erfordert (zu) viel \enquote{Aufwand}!
|
|
\newpage
|
|
\textbf{Was ist Aufwand?}\newline
|
|
Hier: Aufwand = \enquote{Hardware-Aufwand}, \dash wie viel kostet die Realisierung?
|
|
|
|
\textbf{Wie messen wir Aufwand?}
|
|
\begin{itemize}[noitemsep]
|
|
\item \textbf{Anzahl Gatter}: Hat ein Gatter mit 42 Eingängen denselben Aufwand wie ein
|
|
Gatter mit zwei Eingängen?
|
|
Unterschied Aufwand für \texttt{UND} und \texttt{ODER}? Was ist mit Negationen?
|
|
|
|
\item \textbf{Anzahl Transistoren}: Auf \acsp{IC} werden die Gatterfunktionen über
|
|
Transistoren als Schalter realisiert. \newline
|
|
\autoref{fig:npn_transistor} zeigt einen $npn$ Transistor. Es fließt Strom, falls
|
|
$U_{Basis} > U_{Emitter}$ \newline
|
|
\autoref{fig:pnp_transistor} zeigt einen $pnp$ Transistor. Es fließt Strom, falls
|
|
$U_{Basis} < U_{Emitter}$
|
|
|
|
\medskip
|
|
|
|
$\Rightarrow$ Für die Realisierung eines \texttt{UND}- oder \texttt{ODER}-Gatters mit $n$ Eingängen
|
|
werden $n$ Transistoren benötigt.\newline
|
|
$\Rightarrow$ Abschätzung des Aufwands in Transistoren über die Anzahl der Eingänge
|
|
der verwendeten \enquote{Basisgatter} (\texttt{UND}, \texttt{ODER})
|
|
|
|
$\Rightarrow$ Negation an Eingängen können ohne zusätzlichen Aufwand realisiert
|
|
werden (einfaches Argument: Ersatz des $npn$- durch $pnp$-Transistor)!
|
|
|
|
$\Rightarrow$ Negation am Ausgang kann ohne zusätzlichen Aufwand realisiert werden (einfaches Argument: Austausch von \enquote{1}- und Erd-Spannung an den Widerständen, siehe \autoref{fig:transistor_mit_pull_widerstaenden})!
|
|
|
|
Damit ist der Aufwand für die Realisierung der obigen \acs{DNF}: 16 Transistoren (4 \texttt{UND} mit jeweils 3 Eingängen und 1 \texttt{ODER} mit 4 Eingängen).
|
|
\end{itemize}
|
|
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{circuitikz}
|
|
\draw
|
|
(0,0) node[npn] (npn) {}
|
|
(npn.base) node[anchor=east] {Basis}
|
|
(npn.emitter) node[anchor=north] {Emitter}
|
|
(npn.collector) node[anchor=south] {Kollektor}
|
|
;
|
|
\end{circuitikz}
|
|
\caption{$npn$ Transistor}\index{Transistor!npn}
|
|
\label{fig:npn_transistor}
|
|
\end{figure}
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{circuitikz}
|
|
\draw
|
|
(0,0) node[pnp] (pnp) {}
|
|
(pnp.base) node[anchor=east] {Basis}
|
|
(pnp.collector) node[anchor=north] {Kollektor}
|
|
(pnp.emitter) node[anchor=south] {Emitter}
|
|
;
|
|
\end{circuitikz}
|
|
\caption{$pnp$ Transistor}\index{Transistor!pnp}
|
|
\label{fig:pnp_transistor}
|
|
\end{figure}
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{circuitikz}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\node at (0,0) (eins) {\enquote{1}};
|
|
\node[draw,below=of eins,label={[left]$R_{Pullup}$}] (widerstand) {};
|
|
\node at (widerstand |- 0,-2) (ecke) {};
|
|
|
|
\draw (ecke -| 1,0) node[nmos,rotate=-90] (mos) {};
|
|
\draw (ecke -| 2.5,0) node[nmos,rotate=-90] (mos2) {};
|
|
|
|
\draw (mos2.source) -- (mos.drain);
|
|
\draw (mos2.source) -- (mos.drain);
|
|
\draw (widerstand) -- (eins);
|
|
\draw (widerstand) |- (mos.source);
|
|
\draw (mos2.drain) -- ([xshift=5mm]mos2.drain);
|
|
\node[knoten] at ([xshift=5mm]mos2.drain) (knoten) {};
|
|
\node[draw,below=of knoten,label={[right]$R_{Pulldown}$}] (widerstand2) {};
|
|
\draw (widerstand2) -- (knoten);
|
|
\node[ground] at ([yshift=-5mm]widerstand2) (G) {};
|
|
\draw (widerstand2) -- (G);
|
|
|
|
\node at (1,-3.5) {$R_{Pullup} < R_{Pulldown}$};
|
|
\end{circuitikz}
|
|
\caption{Transistor - $R_{Pullup} $ und $ R_{Pulldown}$}
|
|
\label{fig:transistor_mit_pull_widerstaenden}
|
|
\end{figure}
|
|
|
|
|
|
\newpage
|
|
\section{Schaltnetzanalyse}\index{Schaltnetzanalyse}
|
|
In \autoref{fig:schaltnetzanalyse_1} wird ein Schaltnetz dargestellt, welches nun untersucht werden soll, um einen booleschen Funktionsterm zu erstellen.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\node[and gate, inputs={ni}] at (0,2) (AND1) {};
|
|
\node[and gate, inputs={ni}] at (0,0) (AND2) {};
|
|
\node[or gate, inputs={nn}] at (2,1) (OR) {};
|
|
|
|
\node at (AND1.input 1 -| -15mm,0) (B) {b};
|
|
\node at (B |- 0,10mm) (A) {a};
|
|
\node at (AND2.input 2 -| -15mm,0) (C) {c};
|
|
|
|
|
|
\draw (B)-- (AND1.input 1);
|
|
\draw (C)-- (AND2.input 2);
|
|
\draw (A) -- (A -| -8mm,0) |- (AND1.input 2);
|
|
\draw (A -| -8mm,0) |- (AND2.input 1);
|
|
\node[knoten] at (A -| -8mm,0) {};
|
|
|
|
\draw (AND1.output) -- ([xshift=5mm]AND1.output) |- (OR.input 1);
|
|
\draw (AND2.output) -- ([xshift=5mm]AND2.output) |- (OR.input 2);
|
|
|
|
\draw (OR.output) -- ([xshift=10mm]OR.output);
|
|
\node[anchor=west] at ([xshift=10mm]OR.output) {?};
|
|
|
|
\end{tikzpicture}
|
|
\caption{Schaltnetz für Schaltnetzanalyse -- $g(a,b,c)=(b\wedge\overline{a})\vee(a\wedge\overline{c})$}
|
|
\label{fig:schaltnetzanalyse_1}
|
|
\end{figure}
|
|
|
|
Es ergibt sich folgender Funktionsterm: $g(a,b,c)=(b\wedge\overline{a})\vee(a\wedge\overline{c})$
|
|
|
|
Dies als Wertetabelle geschrieben ergibt die \autoref{tbl:wertetabelle_schaltnetzanalyse}.
|
|
|
|
\begin{table}[h]
|
|
\centering
|
|
\begin{tabular}{c|ccc|c|c|c|c}
|
|
Nr. & c & b & a & $x_1 = b\overline{a}$ & $x_2 = a\overline{c}$ & $g=x_1\vee x_2$ & \\
|
|
\midrule
|
|
0 & 0 & 0 & 0 & 0 & 0 & 0 & \\
|
|
1 & 0 & 0 & 1 & 0 & 1 & 1 & $\overline{c}\overline{b}a$ \\
|
|
2 & 0 & 1 & 0 & 1 & 0 & 1 & $\overline{c}b\overline{a}$ \\
|
|
3 & 0 & 1 & 1 & 0 & 1 & 1 & $\overline{c}ba$ \\
|
|
5 & 1 & 0 & 0 & 0 & 0 & 0 & \\
|
|
5 & 1 & 0 & 1 & 0 & 0 & 0 & \\
|
|
6 & 1 & 1 & 0 & 1 & 0 & 1 & $cb\overline{a}$ \\
|
|
7 & 1 & 1 & 1 & 0 & 0 & 0 & \\
|
|
\end{tabular}
|
|
\caption{Wertetabelle aus Schaltnetz}
|
|
\label{tbl:wertetabelle_schaltnetzanalyse}
|
|
\end{table}
|
|
|
|
Es ergibt sich, dass diese \autoref{tbl:wertetabelle_schaltnetzanalyse} äquivalent zur \autoref{tbl:von_wertetabelle_zur_funktion} auf Seite~\pageref{tbl:von_wertetabelle_zur_funktion} ist, dabei aber weniger \texttt{UND} und \texttt{ODER} Gatter enthält.
|
|
Der Aufwand für $g(a,b,c)$ beträgt 6 Transistoren (entspricht der Anzahl der Eingänge der Elementargatter), während für \autoref{tbl:von_wertetabelle_zur_funktion} mit der Funktion $f(a,b,c)$ 16 Transistoren verwendet werden mussten.
|
|
|
|
\newpage
|
|
|
|
(1) und (3) verodert ergibt: \quad
|
|
$\overline{c}\overline{b}a\vee\overline{c}ba\overset{\hyperref[H2]{H2}}{=}\overline{c}a\wedge(\overline{b}\vee b)\overset{\hyperref[H4]{H4}}{=}\overline{c}a\wedge 1\overset{\hyperref[H3]{H3}}{=}\overline{c}a$ \quad (\acs{PI} und \acs{KPI})
|
|
|
|
(2) und (6) verodert ergibt: \quad
|
|
$\overline{c}b\overline{a}\vee cb\overline{a}\overset{\hyperref[H2]{H2}}{=}(\overline{c}\vee c)\wedge b \overline{a}\overset{\hyperref[H4]{H4}}{=}1\wedge b\overline{a}\overset{\hyperref[H3]{H3}}{=}b\overline{a}$ \quad (\acs{PI} und \acs{KPI})
|
|
|
|
(2) und (3) verodert ergibt: \quad
|
|
$\overline{c}b\overline{a}\vee \overline{c}ba = \overline{c}b$ \quad (\acs{PI})
|
|
|
|
Damit ergibt sich per allgemeiner Umformung:
|
|
$\overline{c}\overline{b}a\vee \overline{c}b\overline{a}\vee \overline{c}ba\vee cb\overline{a} = \overline{c}a \vee b\overline{a}$
|
|
|
|
\begin{satz}
|
|
Konjunktionen von Literalen können zu einer Konjunktion vereinfacht werden, wenn:
|
|
\begin{itemize}[noitemsep]
|
|
\item die beiden Konjunktionen sich nur in einem Literal unterscheiden
|
|
\item das unterscheidende Literal dieselbe Variable darstellt, einmal in negierter und einmal in nicht-negierter Form
|
|
\item \textit{es wird vereinfacht indem} das unterscheidende Literal in der vereinfachten Konjunktion weggelassen wird
|
|
\end{itemize}
|
|
\end{satz}
|
|
|
|
\textsf{\textbf{Beweis}}: Siehe \autoref{eq:beweis_konjunktion_vereinfachung}.
|
|
\begin{align}
|
|
a\wedge x \vee \overline{a}\wedge x &\overset{!}{=}x \nonumber \\
|
|
a\wedge x \vee \overline{a}\wedge x &\overset{\hyperref[H2]{H2}}{=}(a\vee \overline{a})\wedge x\overset{\hyperref[H4]{H4}}{=} 1 \wedge x \overset{\hyperref[H3]{H3}}{=} x \text{ \textcolor{green}{\cmark}} \label{eq:beweis_konjunktion_vereinfachung}
|
|
\end{align}
|
|
|
|
\begin{description}
|
|
\item[Implikant] Eine Konjunktion von Literalen, bei der die Funktion $f$ immer \enquote{1} ergibt, heißt Implikant\index{Implikant} $i$ der Funktion $f$ \enskip ($i\rightarrow f$).
|
|
\end{description}
|
|
|
|
\begin{satz}
|
|
Die Vollkonjunktion der Funktion $f$ (auch Minterm\index{Minterm} genannt) sind Implikanten der Funktion $f$.
|
|
\end{satz}
|
|
\begin{satz}
|
|
Die aus vorhandenen Implikanten gefundenen vereinfachten Konjunktionen sind ebenfalls Implikanten.
|
|
\end{satz}
|
|
|
|
\begin{description}
|
|
\item[\acf{PI}] \hfill\newline
|
|
Ein Primimplikant\index{Primimplikant} der Funktion $f$ ist ein Implikant der Funktion $f$, welcher mit keinem anderen Implikanten der Funktion $f$ zusammengefasst werden kann.
|
|
|
|
\item[\textit{Eine} \acf{DMF}] \hfill\newline
|
|
\textit{Eine} (\textit{nicht die}) \acf{DMF}\index{Disjunktive Minimalform} der Funktion $f$ ist eine Disjunktion von Primimplikanten der Funktion $f$, welche minimal ist.
|
|
|
|
\item[minimal] \enquote{minimal} bedeutet: \hfill
|
|
\begin{itemize}[noitemsep]
|
|
\item kleinste Zahl an Implikanten
|
|
\item kleine Zahl an Literalen in den Implikanten
|
|
\end{itemize}
|
|
\end{description}
|
|
|
|
Offensichtlich ist $\overline{c}a\vee b\overline{a}$ die \acs{DMF} von $f$! $\Rightarrow$ Der \acs{PI} $\overline{c}b$ wird für die \acs{DMF} nicht gebraucht!
|
|
|
|
\begin{description}
|
|
\item[\acf{KPI}]\index{Kernprimimplikant} Ein \acl{KPI} der Funktion $f$ ist ein \acs{PI} der Funktion $f$, welcher mindestens eine \enquote{1} in der Wertetabelle exklusiv abdeckt, \dash eine \enquote{1-Zeile} wird von keinem anderen \acs{KPI} abgedeckt.
|
|
\end{description}
|
|
|
|
\begin{satz}
|
|
Die \acs{DMF} enthält mindestens alle \acs{KPI} (siehe \autoref{satz:kv_dmf} auf Seite~\pageref{satz:kv_dmf}).
|
|
\end{satz}
|
|
|
|
|
|
\section{KV-Diagramm} \label{sec:kv_diagramm} \index{KV-Diagramm}
|
|
|
|
Das \acf{KV}-Diagramm ist die graphische Darstellung der Wertetabelle.
|
|
|
|
\subsection{\acs{KV}-Diagramm für Funktion abhängig von 1 Variable: $f(a)$}
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\centering
|
|
\begin{tabular}{c|c|c}
|
|
Nr. & a & $f(a)$ \\
|
|
\midrule
|
|
0 & 0 & $f(0)$ \\
|
|
1 & 1 & $f(1)$ \\
|
|
\end{tabular}
|
|
\switchcolumn
|
|
\centering
|
|
\karnaughmap{1}{$f(a):$}{{$a$}}{}{}
|
|
\end{paracol}
|
|
|
|
\subsection{\acs{KV}-Diagramm für Funktion abhängig von 2 Variablen: $f(a,b)$}
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\centering
|
|
\begin{tabular}{c|cc|c}
|
|
Nr. & b & a & $f(a,b)$ \\
|
|
\midrule
|
|
0 & 0 & 0 & $f(0,0)$ \\
|
|
1 & 0 & 1 & $f(1,0)$ \\
|
|
2 & 1 & 0 & $f(0,1)$ \\
|
|
3 & 1 & 1 & $f(1,1)$ \\
|
|
\end{tabular}
|
|
\switchcolumn
|
|
\centering
|
|
\karnaughmap{2}{$f(a,b):$}{{$b$}{$a$}}{}{}
|
|
\end{paracol}
|
|
|
|
\subsection{\acs{KV}-Diagramm für Funktion abhängig von 3 Variablen: $f(a,b,c)$}
|
|
|
|
Die Werte stammen aus \autoref{tbl:wertetabelle_schaltnetzanalyse}.
|
|
\medskip
|
|
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\centering
|
|
\begin{tabular}{c|ccc|c|c}
|
|
Nr. & c & b & a & $f(a,b)$ & \\
|
|
\midrule
|
|
0 & 0 & 0 & 0 & 0 & \\
|
|
1 & 0 & 0 & 1 & 1 & $\overline{c}\overline{b}a$ \\
|
|
2 & 0 & 1 & 0 & 1 & $\overline{c}b\overline{a}$ \\
|
|
3 & 0 & 1 & 1 & 1 & $\overline{c}ba$ \\
|
|
5 & 1 & 0 & 0 & 0 & \\
|
|
5 & 1 & 0 & 1 & 0 & \\
|
|
6 & 1 & 1 & 0 & 1 & $cb\overline{a}$ \\
|
|
7 & 1 & 1 & 1 & 0 & \\
|
|
\end{tabular}
|
|
\switchcolumn
|
|
\centering
|
|
\karnaughmap{3}{$f(a,b,c):$}{{$c$}{$b$}{$a$}}{01110010}{%
|
|
\linethickness{0.44mm}
|
|
\put(0,0.5){\textcolor{green}{\oval(1.9,0.9)[r]}}% 0,0.5 ist der Mittelpunk des Kreises, 0.9 der Durchmesser
|
|
\put(4,0.5){\textcolor{green}{\oval(1.9,0.9)[l]}}
|
|
\put(1.5,1){\textcolor{red}{\oval(0.9,1.9)}}
|
|
\put(1,0.5){\textcolor{blue}{\oval(1.9,0.9)}}
|
|
}
|
|
\end{paracol}
|
|
|
|
|
|
\subsection{\acs{KV}-Diagramm für Funktion abhängig von 4 Variablen: $f(a,b,c,d)$}
|
|
|
|
\columnratio{0.30}
|
|
\begin{paracol}{2}
|
|
\karnaughmap{4}{$f(a,b,c,d):$}{{$d$}{$c$}{$b$}{$a$}}{0011001100010001}{%
|
|
\linethickness{0.44mm}
|
|
\put(2,2){\textcolor{red}{\oval(1.9,1.9)}}% 2,2 ist der Mittelpunk des Kreises, 1.9 der Durchmesser
|
|
\put(2,2.5){\textcolor{blue}{\oval(3.9,0.9)}}
|
|
}
|
|
\switchcolumn
|
|
\begin{tabular}{lll}
|
|
Wenn & $3+7:$ & $ a\wedge b\wedge \overline{d}$ \\
|
|
Wenn & $11+15:$ & $ a\wedge b\wedge d$ \\
|
|
Wenn & \textcolor{red}{$3+7+11+15$}: &$a\wedge b$
|
|
\end{tabular}
|
|
|
|
Um etwas zusammenzufassen, muss es sich um einen Block (\enquote{ein Rechteck}) handeln. So kann \textcolor{blue}{$2+3+6+7$} als Block/\enquote{Linie} zusammengefasst werden, aber $2+3+6+7+11+15$ kann nicht zusammengefasst werden. Es muss in zwei Blöcke aufgeteilt werden.
|
|
\end{paracol}
|
|
|
|
|
|
Im \acs{KV}-Diagramm werden die \acs{PI} als maximal große, rechteckige Blöcke von $2^n$ \enquote{1}-Feldern abgebildet! Wenn ein \acs{PI} ein Feld besitzt, welches nur von diesen \acs{PI} (und keinem anderen \acs{PI}) überdeckt wird, dann ist dieser \acs{PI} ein \acs{KPI}.
|
|
|
|
\subsection{\acs{KV}-Diagramm für Funktion abhängig von 5 Variablen: $f(a,b,c,d,e)$}
|
|
|
|
\begin{center}
|
|
\karnaughmap{5}{$f(a,b,c,d,e):$}{{$e$}{$d$}{$c$}{$b$}{$a$}}{000100000000000000010000000000}{%
|
|
\linethickness{0.44mm}
|
|
\put(1.5,2.5){\textcolor{red}{\oval(0.9,0.9)}}
|
|
\put(6.5,2.5){\textcolor{red}{\oval(0.9,0.9)}}
|
|
}
|
|
\end{center}
|
|
|
|
\begin{Achtung}
|
|
Hier können die Felder 3 und 19 verbunden werden!
|
|
|
|
\enquote{Nachbar} eines Feldes bedeutet, dass sich die Belegung genau einer Variablen ändert. Im zweidimensionalen gibt es 4 Nachbarn $\Rightarrow$ 4 Variablen können sich ändern!
|
|
|
|
Für 5 und 6 Variablen wird ein \textbf{3-dimensionales} \acs{KV}-Diagramm benötigt, um die 5 oder 6 Nachbarn darstellen zu können.
|
|
\end{Achtung}
|
|
|
|
|
|
\subsection{Beispiel für ein KV-Diagramm mit 4 Variablen}
|
|
\columnratio{0.35}
|
|
\begin{paracol}{2}
|
|
\karnaughmap{4}{$f(a,b,c,d):$}{{$d$}{$c$}{$b$}{$a$}}{0101000100000011}{%
|
|
\linethickness{0.44mm}
|
|
\put(2.5,2){\textcolor{red}{\oval(0.9,1.9)}}% 2,2 ist der Mittelpunk des Kreises, 1.9 der Durchmesser
|
|
\put(2,2.5){\textcolor{purple}{\oval(1.9,0.9)}}
|
|
\put(1.5,3){\textcolor{green}{\oval(0.9,1.9)}}
|
|
\put(3,1.5){\textcolor{blue}{\oval(1.9,0.9)}}
|
|
}
|
|
\switchcolumn
|
|
\begin{tabular}{lll}
|
|
\textcolor{green}{$1+3$} & $a\overline{c}\overline{d}$ & \acs{KPI} \\
|
|
\textcolor{blue}{$14+15$} & $acd$ & \acs{KPI} \\
|
|
\textcolor{purple}{$3+7$} & $ab\overline{d}$ & \acs{PI} (keine \acs{KPI}) \\
|
|
\textcolor{red}{$7+15$} & $abc$& \acs{PI} (keine \acs{KPI})
|
|
\end{tabular}
|
|
|
|
\acs{DMF}: \newline
|
|
$f(a,b,c,d) = a\overline{c}\overline{d} \vee bcd \vee ab\overline{d}$\newline
|
|
$\phantom{f(a,b,c,d)} = a\overline{c}\overline{d}\vee bcd\vee abc$, denn es gibt zwei Möglichkeiten für die 7 (\textcolor{purple}{$3+7$} oder \textcolor{red}{$7+15$}).
|
|
\end{paracol}
|
|
\bigskip
|
|
|
|
\begin{satz}\label{satz:kv_dmf}
|
|
Die \acs{DMF} besteht manchmal auch aus nicht-\acs{KPI}, also \enquote{einfachen} \acs{PI}, wenn nicht alle \enquote{1} vom \acs{KPI} abgedeckt werden.
|
|
|
|
In diesem Fall kann die \acs{DMF} auch nicht-eindeutig sein! Sie kann aber trotzdem eindeutig sein, wenn die fehlenden Felder von \acsp{PI} mit unterschiedlicher Größe (und damit auch unterschiedlicher Variablenzahl) abgedeckt werden (möglich erst ab 5 Variablen)!
|
|
\end{satz}
|
|
|
|
|
|
\section{\acl{KNF} / \acl{KMF}}
|
|
\acs{DNF} und \acs{DMF} verknüpfen die \enquote{1}.
|
|
|
|
Die \acf{KNF} und die \acf{KMF} verknüpfen die \enquote{0}, bzw. wird sie aus den Wertetabellen durch die Nullen gebildet.
|
|
|
|
Beispiel: $(a\vee b\vee c)\wedge(\overline{a}\vee b\vee d)\wedge(c\vee d)$
|
|
|
|
\medskip
|
|
|
|
\begin{center}
|
|
\begin{tabular}{ccc|c|c}
|
|
c & b & a & $f(a,b,c)$ & Maxterm \\
|
|
\midrule
|
|
0 & 1 & 0 & 0 & $c\vee \overline{b}\vee a$
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\includegraphics[scale=0.7]{Bilder/KNF-DNF-Wikipedia.png}
|
|
\caption{KNF und DNF im Vergleich -- Quelle: \href{https://de.wikipedia.org/wiki/Konjunktive\_Normalform}{Wikipedia KNF}}
|
|
\end{figure}
|
|
|
|
\newpage
|
|
\section{Schaltwerke}
|
|
\begin{description}
|
|
\item[Schaltnetz] \index{Schaltnetz}
|
|
Realisierung einer booleschen Funktion.
|
|
\item[Funktion] \index{Funktion}
|
|
Ausgangsbelegung hängt unmittelbar und ausschließlich von der
|
|
Eingangsbelegung ab.
|
|
\item[Schaltwerke] \index{Schaltwerke}
|
|
Schaltwerke, bei denen auch Rückkopplungen von Aus- zu Eingängen möglich
|
|
und erlaubt sind.
|
|
\end{description}
|
|
|
|
|
|
|
|
Die \autoref{fig:schaltwerk} zeigt ein Schaltwerk, jedoch keine Funktion, da hier die Ausgangsbelegung auch von Ausgängen abhängt. Es gilt: $x=\neg(R\vee y')$ und $y=\neg(S\vee x')$ für die linke Seite und $x=\neg(R\wedge y')$ und $y=\neg(S\wedge x')$ für die rechte Seite.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[nor gate, inputs={nn}] at (0,2) (PORT) {};
|
|
\node[nor gate, inputs={nn}] at (0,0) (PORT2) {};
|
|
|
|
\node[left=of PORT.input 1] (A) {$S$};
|
|
\node[left=of PORT2.input 2] (B) {$R$};
|
|
\node[left=of PORT.input 2] (Y1) {$y'$};
|
|
\node[left=of PORT2.input 1] (X1) {$x'$};
|
|
|
|
\node[right=of PORT.output] (X) {$x$ $(Q*)$};
|
|
\node[right=of PORT2.output] (Y) {$y$ $(Q)$};
|
|
|
|
\draw (A) -- (PORT.input 1);
|
|
\draw (B) -- (PORT2.input 2);
|
|
\draw (Y1) -- (PORT.input 2);
|
|
\draw (X1) -- (PORT2.input 1);
|
|
\draw (X) -- (PORT.output);
|
|
\draw (Y) -- (PORT2.output);
|
|
|
|
\node at (0.5,1.25) {//};
|
|
\node at (0.5,0.7) {//};
|
|
|
|
\draw ($(X1)+(0.3,-0.02)$) -- ($(X1)+(0.3,0.6)$) -- ($(X)+(-0.85,-0.6)$) -- ($(X)+(-0.85,0)$);
|
|
\draw ($(Y1)+(0.3,0.02)$) -- ($(Y1)+(0.3,-0.6)$) -- ($(Y)+(-0.85,0.6)$) -- ($(Y)+(-0.85,0)$);
|
|
\node[knoten] at ($(X)+(-0.85,0)$) {};
|
|
\node[knoten] at ($(Y)+(-0.85,0)$) {};
|
|
\end{tikzpicture}
|
|
\qquad
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[nand gate, inputs={nn}] at (0,2) (PORT) {};
|
|
\node[nand gate, inputs={nn}] at (0,0) (PORT2) {};
|
|
|
|
\node[left=of PORT.input 1] (A) {$S$};
|
|
\node[left=of PORT2.input 2] (B) {$R$};
|
|
\node[left=of PORT.input 2] (Y1) {$y'$};
|
|
\node[left=of PORT2.input 1] (X1) {$x'$};
|
|
|
|
\node[right=of PORT.output] (X) {$x$ $(Q*)$};
|
|
\node[right=of PORT2.output] (Y) {$y$ $(Q)$};
|
|
|
|
\draw (A) -- (PORT.input 1);
|
|
\draw (B) -- (PORT2.input 2);
|
|
\draw (Y1) -- (PORT.input 2);
|
|
\draw (X1) -- (PORT2.input 1);
|
|
\draw (X) -- (PORT.output);
|
|
\draw (Y) -- (PORT2.output);
|
|
|
|
\node at (0.5,1.25) {//};
|
|
\node at (0.5,0.7) {//};
|
|
|
|
\draw ($(X1)+(0.3,-0.02)$) -- ($(X1)+(0.3,0.6)$) -- ($(X)+(-0.85,-0.6)$) -- ($(X)+(-0.85,0)$);
|
|
\draw ($(Y1)+(0.3,0.02)$) -- ($(Y1)+(0.3,-0.6)$) -- ($(Y)+(-0.85,0.6)$) -- ($(Y)+(-0.85,0)$);
|
|
\node[knoten] at ($(X)+(-0.85,0)$) {};
|
|
\node[knoten] at ($(Y)+(-0.85,0)$) {};
|
|
\end{tikzpicture}
|
|
\caption{Schaltwerk -- RS-Flip-Flop mit \texttt{NAND} und \texttt{NOR}}
|
|
\label{fig:schaltwerk}
|
|
\end{figure}
|
|
|
|
\section{Schaltwerksanalyse}
|
|
Analysiert das Verhalten des Schaltwerks.
|
|
|
|
\begin{enumerate}[noitemsep]
|
|
\item Das Auftrennen der rückgekoppelten Eingängen von den Ausgängen und entsprechende Neubenennung.
|
|
\item Aufstellen der Wertetabelle, wobei die vormals rückgekoppelten Eingänge als erstes aufgeführt werden (siehe \autoref{tbl:wertetabelle_schaltwerksanalyse} auf Seite~\pageref{tbl:wertetabelle_schaltwerksanalyse}).
|
|
\item Markieren der Zeilen der Wertetabelle als stabil oder instabil, je nachdem, ob die Belegungen der rückgekoppelten Eingänge mit den Belegungen der entsprechenden Ausgänge übereinstimmt ($x=x'$ und $y=y'$).
|
|
\item Bei instabilen Zeilen: Benennen der Folgezeilen, bis eine stabile Zeile erreicht wird oder ein Zyklus auftritt, bei welchem nie eine stabile Zeile erreicht werden kann (markiert mit $\lightning$).
|
|
\item Benennung der Zustände des Schaltwerks über die Belegung der rückgekoppelten Eingänge und Identifizieren derselben in den Zeilen der Wertetabelle.
|
|
\item Aufstellen des Zustandsübergangsdiagramms (Moore-Automat; Alternative: Mealy), wobei die Zustände mit der Belegung der rückgekoppelten Eingänge und die Zustandsgruppe mit der Belegung der unabhängigen Eingänge bezeichnet werden.
|
|
\item Interpretation des Verhaltens anhand des Automaten
|
|
\end{enumerate}
|
|
|
|
\subsection*{Beispiel zur Schaltwerksanalayse}
|
|
|
|
\begin{table}[h]
|
|
\centering
|
|
Es gilt: $x=\neg(S\vee y')$ und $y=\neg(R\vee x')$\newline
|
|
|
|
\begin{tabular}{c|cccc|cccl}
|
|
Nr. & $y'$ & $x'$ & $R$ & $S$ & $y$ & $x$ & stabil? & wird zu? \\
|
|
\midrule
|
|
0 & 0 & 0 & 0 & 0 & 1 & 1 & \textcolor{red}{\xmark} & $\rightarrow 12$ \textcolor{red}{$\lightning$} \\
|
|
1 & 0 & 0 & 0 & 1 & 1 & 0 & \textcolor{red}{\xmark} & $\rightarrow 9$ \\
|
|
2 & 0 & 0 & 1 & 0 & 0 & 1 & \textcolor{red}{\xmark} & $\rightarrow 6$ \\
|
|
3 & \textcolor{blue}{\textbf{0}} & \textcolor{blue}{\textbf{0}} & 1 & 1 & \textcolor{blue}{\textbf{0}} & \textcolor{blue}{\textbf{0}} & \textcolor{green}{\cmark} & \\
|
|
\midrule
|
|
4 & \textcolor{blue}{\textbf{0}} & \textcolor{blue}{\textbf{1}} & 0 & 0 & \textcolor{blue}{\textbf{0}} & \textcolor{blue}{\textbf{1}} & \textcolor{green}{\cmark} & \\
|
|
5 & 0 & 1 & 0 & 1 & 0 & 0 & \textcolor{red}{\xmark} & $\rightarrow 1 \rightarrow 9$ \\
|
|
6 & \textcolor{blue}{\textbf{0}} & \textcolor{blue}{\textbf{1}} & 1 & 0 & \textcolor{blue}{\textbf{0}} & \textcolor{blue}{\textbf{1}} & \textcolor{green}{\cmark} & \\
|
|
7 & 0 & 1 & 1 & 1 & 0 & 0 & \textcolor{red}{\xmark} & $\rightarrow 3$ \\
|
|
\midrule
|
|
8 & \textcolor{blue}{\textbf{1}} & \textcolor{blue}{\textbf{0}} & 0 & 0 & \textcolor{blue}{\textbf{1}} & \textcolor{blue}{\textbf{0}} & \textcolor{green}{\cmark} & \\
|
|
9 & \textcolor{blue}{\textbf{1}} & \textcolor{blue}{\textbf{0}} & 0 & 1 & \textcolor{blue}{\textbf{1}} & \textcolor{blue}{\textbf{0}} & \textcolor{green}{\cmark} & \\
|
|
10 & 1 & 0 & 1 & 0 & 0 & 0 & \textcolor{red}{\xmark} & $\rightarrow 2 \rightarrow 6$ \\
|
|
11 & 1 & 0 & 1 & 1 & 0 & 0 & \textcolor{red}{\xmark} & $\rightarrow 3$ \\
|
|
\midrule
|
|
12 & 1 & 1 & 0 & 0 & 0 & 0 & \textcolor{red}{\xmark} & $\rightarrow 0$ \textcolor{red}{$\lightning$} \\
|
|
13 & 1 & 1 & 0 & 1 & 0 & 0 & \textcolor{red}{\xmark} & $\rightarrow 1 \rightarrow 9$ \\
|
|
14 & 1 & 1 & 1 & 0 & 0 & 0 & \textcolor{red}{\xmark} & $\rightarrow 2 \rightarrow 6$ \\
|
|
15 & 1 & 1 & 1 & 1 & 0 & 0 & \textcolor{red}{\xmark} & $\rightarrow 3$ \\
|
|
\end{tabular}
|
|
\caption{Wertetabelle für ein Schaltwerk -- RS-Flip-Flop}
|
|
\label{tbl:wertetabelle_schaltwerksanalyse}
|
|
\end{table}
|
|
|
|
Ein allgemeines Zustandsübergangsdiagramm wird in \autoref{fig:zustanddiagramm_allgemein} dargestellt.
|
|
\begin{figure}[h] \centering
|
|
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=4.2cm,semithick]
|
|
\tikzstyle{every state}=[fill=white,draw=red,text=black,thick,minimum size=1.1cm]
|
|
\node[state] at (0,0) (A) {$y'x'$};
|
|
\node at (4,0) (B) {};
|
|
\path (A) edge [bend left] node {$R$ $S$} (B);
|
|
\end{tikzpicture}
|
|
\caption{Zustandsübergangsdiagramm -- Allgemeines Beispiel}
|
|
\label{fig:zustanddiagramm_allgemein}
|
|
\end{figure}
|
|
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=4.2cm,semithick]
|
|
\tikzstyle{every state}=[fill=white,draw=red,text=black,thick,minimum size=1.2cm]
|
|
|
|
\node[state] (A) {$01$};
|
|
\node[state] (B) [above right of=A] {$00$};
|
|
\node[state] (C) [below right of=B] {$10$};
|
|
\node[state] (D) [below right of=A] {$11$};
|
|
|
|
\path (B) edge [loop above] node {11} (B)
|
|
(A) edge [loop left] node {00,10} (A)
|
|
(C) edge [loop right] node {00,01} (C)
|
|
(A) edge [bend left] node {01} (C)
|
|
(C) edge [bend left] node {10} (A)
|
|
(A) edge [bend left] node {11} (B)
|
|
(B) edge [bend left] node {10} (A)
|
|
(C) edge [bend right] node {11} (B)
|
|
(B) edge [bend right] node {01} (C)
|
|
(D) edge [bend left] node {10} (A)
|
|
(D) edge [bend right] node {01} (C)
|
|
(D) edge node {11} (B)
|
|
|
|
(B) edge [bend right] node {00} ($(B)+(-3,1)$)
|
|
(D) edge [bend left] node {00} ($(D)+(-3,-1)$)
|
|
;
|
|
\node at ($(B)+(-3.2,1)$) {\Huge{\textcolor{red}{$\lightning$}}};
|
|
\node at ($(D)+(-3.2,-1)$) {\Huge{\textcolor{red}{$\lightning$}}};
|
|
|
|
\end{tikzpicture}
|
|
\caption{Zustandsübergangsdiagramm -- \acs{RS-FF}}
|
|
\label{fig:rs_flip_flop}
|
|
\end{figure}
|
|
|
|
Das gezeichnete und analysierte Schaltwerk in \autoref{fig:rs_flip_flop} ist ein \acl{RS-FF}. Ein Flip-Flop speichert 1~Bit an Informationen, \dash es gibt zwei (Arbeits-)Zustände!
|
|
|
|
\begin{center}
|
|
\begin{tabular}{ll}
|
|
$R=0$ $S=1$ & $\Rightarrow$ Arbeitszustand, \enquote{10} (gesetzt) \\
|
|
$R=1$ $S=0$ & $\Rightarrow$ Arbeitszustand \enquote{01} (gelöscht) \\
|
|
$R=S=0$ & $\Rightarrow$ Arbeitszustand bleibt erhalten \\
|
|
$R=S=1$ & $\Rightarrow$ nicht-Arbeitszustand \enquote{00} wird erreicht \\
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\textit{Problem}: Die Änderung auf $R=S=0$ bewirkt ein endloses ein Hin- und Herwechseln zwischen \enquote{00} und \enquote{11} (vgl. Zeile 12)
|
|
$\Rightarrow$ deshalb wird die Eingangsbelegung $R=S=1$ \enquote{verboten}.
|
|
|
|
\textit{Anwendungsbeispiel}: \acs{RS-FF}: Lichtschalter mit zwei getrennten Schaltstellen für \enquote{Ein} und \enquote{Aus}.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node at (0.6,0.6) (RSFF) {RS-FF};
|
|
\node (R) {~R};
|
|
\node[below=of R] (S) {~S};
|
|
\node[right=of R] (Q1) {Q~~};
|
|
\node[right=of S] (Q2) {Q*};
|
|
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
|
|
\draw (R) -- ($(R) + (-1,0)$);
|
|
\draw (S) -- ($(S) + (-1,0)$);
|
|
\draw (Q1) -- ($(Q1) + (1,0)$);
|
|
\draw (Q2) -- ($(Q2) + (1,0)$);
|
|
|
|
\end{tikzpicture}
|
|
\caption{Schaltsymbol -- RS-Flip-Flop}
|
|
\label{fig:rs_ff_symbol}
|
|
\end{figure}
|
|
|
|
\begin{Hinweis}
|
|
In \autoref{fig:rs_ff_symbol} wird ein RS-FF gezeigt. Bei $Q*$ liegt ein negiertes $Q$ an, weshalb die Darstellung in Büchern die Ausgänge $Q_1$ und $Q_2$ bevorzugen, wobei $Q_2$ negiert ist.
|
|
\end{Hinweis}
|
|
|
|
\subsection{\acl{TPS} und \acl{TFS}}
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node (R) {~R};
|
|
\node[below=of R] (S) {~S};
|
|
\node[right=of R] (Q1) {Q~~};
|
|
\node[right=of S] (Q2) {Q*};
|
|
\node at ($(S) + (-2,0)$) (D) {D};
|
|
|
|
\node[thick,circle, draw=black, inner sep=0pt, minimum size=5pt] at ($(R) + (-0.35,0)$) {};
|
|
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
|
|
\node at ($(Q1) + (1,0)$) (QOut) {Q};
|
|
\draw (Q1) -- (QOut);
|
|
|
|
\draw ($(R) + (-0.4,0)$) -- ($(R) + (-1,0)$) -- ($(S) + (-1,0)$);
|
|
\draw (S) -- (D);
|
|
\node[knoten] at ($(S) + (-1,0)$) (knoten) {};
|
|
|
|
\node at (-0.5,-2.2) (E) {$\hat{=}$~~~~D};
|
|
\node[right=of E] (Q) {Q};
|
|
\draw (E) -- (Q);
|
|
|
|
\end{tikzpicture}
|
|
\caption{\enquote{falsches} Schaltsymbol -- D-Flip-Flop}
|
|
\label{fig:d_ff_symbol_simpel}
|
|
\end{figure}
|
|
|
|
\begin{description}
|
|
\item[D-Flip-Flop] \index{D-FF}\enquote{Data}, nur ein Eingangssignal $D$, welches vom Flip-Flop übernommen und gespeichert wird.
|
|
$\Rightarrow$ Wie in \autoref{fig:d_ff_symbol_simpel} zu sehen ist, macht der D-Flip-Flop nur mit Taktsteuerung/Takt als Eingangssignal Sinn!
|
|
\end{description}
|
|
|
|
|
|
\begin{description}
|
|
\item[Takt]\index{Takt}
|
|
Ein weiteres Eingangssignal, welches bestimmt, ob die anderen Eingangssignale Auswirkungen auf die Ausgangssignale haben oder nicht. $\Rightarrow$ Nur bei aktivem Takt hat die Eingangsbelegung Auswirkung auf die Ausgangsbelegung. Bei inaktivem Takt bleibt die vorherige Ausgangsbelegung erhalten.
|
|
|
|
$\Rightarrow$ ein \enquote{taktgesteuertes Schaltnetz} wird zum Schaltwerk.
|
|
|
|
\item[\acf{TPS}]\index{Taktpegelsteuerung} Der Takt ist aktiv, solang der Takt einen bestimmten Pegel hat.
|
|
\begin{description}
|
|
\item[positive \acs{TPS}] Der Takt ist aktiv, solange Takt = \enquote{High}. \autoref{fig:rst_schaltwerk} zeigt diese als Schaltwerk und \autoref{fig:rst_ff_symbol} als Schaltzeichen.
|
|
\item[negative \acs{TPS}] Der Takt ist aktiv, solange Takt = \enquote{Low}
|
|
\end{description}
|
|
\end{description}
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[nor gate, inputs={nn}] at (0,1) (OR1) {};
|
|
\node[nor gate, inputs={nn}] at (0,-1) (OR2) {};
|
|
\node[and gate, inputs={nn}, left=of OR1] (AND1) {};
|
|
\node[and gate, inputs={nn}, left=of OR2] (AND2) {};
|
|
|
|
\node at (-3.5,0) (T) {T};
|
|
\node[right=of OR1] (Q1) {Q*};
|
|
\node[right=of OR2] (Q2) {Q~};
|
|
|
|
\node[left=of AND1.input 1] (S) {S};
|
|
\node[left=of AND2.input 2] (R) {R};
|
|
|
|
\node[knoten] at (T -| S) (K) {};
|
|
\node[knoten] at ($(Q1)+(-0.6,0)$) (K2) {};
|
|
\node[knoten] at ($(Q2)+(-0.6,0)$) (K3) {};
|
|
\draw (K2) -- ($(K2)+(0,-0.7)$)
|
|
-- ($(OR2.input 2) + (-0.4,0.5)$)
|
|
|- (OR2.input 1);
|
|
\draw (K3) -- ($(K3)+(0,0.7)$)
|
|
-- ($(OR1.input 2) + (-0.4,-0.5)$)
|
|
|- (OR1.input 2);
|
|
|
|
\draw (T) -- (K) |- (AND1.input 2);
|
|
\draw (K) |- (AND2.input 1);
|
|
\draw (S) -- (AND1.input 1) (R) -- (AND2.input 2);
|
|
\draw (Q1) -- (OR1.output) (Q2) -- (OR2.output);
|
|
\draw (AND1.output) -| (OR1.input 1);
|
|
\draw (AND2.output) -| (OR2.input 2);
|
|
|
|
\end{tikzpicture}
|
|
\caption{Schaltwerk -- RS-FF mit positiver \acl{TPS}}
|
|
\label{fig:rst_schaltwerk}
|
|
\end{figure}
|
|
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node at (0.6,0.6) (RSFF) {RS-FF mit TPS};
|
|
\node (R) {~R};
|
|
\node[below=of R] (S) {~S};
|
|
\node at ($(R) + (-0.2,-0.65)$) (T) {};
|
|
\node at ($(T) + (0.85,0)$) {T};
|
|
\node[right=of R] (Q1) {Q~~};
|
|
\node[right=of S] (Q2) {Q*};
|
|
|
|
\node at ($(Q1)+(1,0)$) (Q1Text) {Q};
|
|
\node at ($(Q2)+(1,0)$) (Q2Text) {Q*};
|
|
\node at ($(R)+(-1,0)$) (RText) {R};
|
|
\node at ($(S)+(-1,0)$) (SText) {S};
|
|
\node at ($(T)+(-0.8,0)$) (TText) {T};
|
|
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
|
|
\draw (R) -- (RText);
|
|
\draw (S) -- (SText);
|
|
\draw (T) -- (TText);
|
|
\draw (Q1) -- (Q1Text);
|
|
\draw (Q2) -- (Q2Text);
|
|
|
|
\draw ($(T)+(-0.1,-0.14)$) -- ++(0.25,0) -- ++(0,0.3) -- ++(-0.25,0);
|
|
\end{tikzpicture}
|
|
\caption{Schaltsymbol -- RS-FF mit \acl{TPS}}
|
|
\label{fig:rst_ff_symbol}
|
|
\end{figure}
|
|
|
|
|
|
\begin{description}
|
|
\item[\acf{TFS}]\index{Taktflankensteuerung} Der Takt ist aktiv, wenn der Takt den Pegel ändert.
|
|
\begin{description}
|
|
\item[positive \acs{TFS}] Takt wecheselt von \enquote{Low} nach \enquote{High}.
|
|
\item[negative \acs{TFS}] Takt wecheselt von \enquote{High} nach \enquote{Low}.
|
|
\end{description}
|
|
\end{description}
|
|
|
|
\textit{Realisierung der \acs{TFS}:} Eine Variante mit wenig Aufwandist die Verwendung eines \enquote{modifizierten} Taktsignals $T_{modifiziert}$ mit nur kurzen \enquote{High} und langem \enquote{Low}-Pegel.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[] (TORG) {$T_{original}$};
|
|
\node[below=of TORG] (TMOD) {$T_{modifiziert}$};
|
|
|
|
\node at ($(TMOD) + (0,-3.5)$) (TStrich) {$T_{neg}$};
|
|
\node[below=of TStrich] (TX) {$T_X$};
|
|
|
|
\draw (TORG) -- ++(1.1,0)-- ++(0,0.5)-- ++(0.5,0)-- ++(0,-0.5) -- ++(0.5,0) -- ++(0,0.5) -- ++(0.5,0) -- ++(0,-0.5) -- ++(0.5,0) -- ++(0,0.5) -- ++(0.5,0) -- ++(0,-0.5) -- ++(0.5,0);
|
|
|
|
\draw (TMOD) -- ++(1.1,0)-- ++(0,0.5)-- ++(0.15,0)-- ++(0,-0.5) -- ++(0.85,0) -- ++(0,0.5) -- ++(0.15,0) -- ++(0,-0.5) -- ++(0.85,0) -- ++(0,0.5) -- ++(0.15,0) -- ++(0,-0.5) -- ++(0.85,0);
|
|
|
|
|
|
\draw ($(TStrich)+(0.3,0.2)$) -- ++(0.8,0)-- ++(0,-0.5)-- ++(0.5,0)-- ++(0,0.5) -- ++(0.5,0) -- ++(0,-0.5) -- ++(0.5,0) -- ++(0,0.5) -- ++(0.5,0) -- ++(0,-0.5) -- ++(0.5,0) -- ++(0,0.5) -- ++(0.5,0);
|
|
|
|
\draw (TX) -- ++(1.1,0)-- ++(0,0.5)-- ++(0.15,0)-- ++(0,-0.5) -- ++(0.85,0) -- ++(0,0.5) -- ++(0.15,0) -- ++(0,-0.5) -- ++(0.85,0) -- ++(0,0.5) -- ++(0.15,0) -- ++(0,-0.5) -- ++(0.85,0);
|
|
|
|
|
|
\node at (0,-3.5) (TAND) {$T_{original}$};
|
|
\node[knoten] at (TAND -| 1.5,0) (K) {};
|
|
\node[not gate,inputs={n}] at ($(K)+(0.7,0.8)$) (NOT) {};
|
|
|
|
\node[and gate, inputs={nn}] at ($(TAND)+(3.5,0)$) (AND) {};
|
|
\node[right=of AND.output] (TXAND) {$T_{X}$};
|
|
\draw (AND.output) -- (TXAND);
|
|
\draw (TAND) -- (K) |- (NOT) (K) |- (AND.input 2)
|
|
(NOT.output) -- ($(NOT.output)+(0.3,0)$) |- (AND.input 1);
|
|
|
|
|
|
|
|
\draw[thick,orange,->] ($(TORG)+(1.1,0)$) .. controls (2.5,-1.5) and (0,-4) .. ($(TStrich)+(1.1,0)$);
|
|
\draw[thick,orange,->] ($(TORG)+(1.1,0)$) .. controls (2.5,-1.5) and (-0.3,-4.5) .. ($(TX)+(1.1,0.2)$);
|
|
\draw[thick,orange,->] ($(TORG)+(1.6,0)$) .. controls (3,-1.5) and (0.5,-4) .. ($(TStrich)+(1.6,0)$);
|
|
|
|
\end{tikzpicture}
|
|
\caption{Verzögerung -- \acl{TFS}}
|
|
\label{fig:verzoegerung_tfs}
|
|
\end{figure}
|
|
|
|
\autoref{fig:verzoegerung_tfs} veranschaulicht die \acl{TFS}. $T_{original}$ wird mit sich selbst negiert \texttt{UND}-verknpüft, sodass $T_X$ immer den Wert \enquote{0} hat. \autoref{tbl:verzoegerung_tfs} stellt dies in einer Wertetabelle dar. Da jedoch jedes Bauteil eine gewisse Verzögerung verursacht (in diesem Fall ist das \texttt{NOT} gemeint), hat $T_X$ für kurze Zeit den Wert \enquote{1}, nämlich dann, wenn $T_{original}$ von \enquote{0} auf \enquote{1} wechselt ($T_{original}$ und $T_{neg}$ haben dann kurz beide den Wert \enquote{1})!
|
|
|
|
$\Rightarrow$ Damit verhalten sich \acs{TPS}-Flip-Flops wie \acs{TFS}-Flip-Flops gegenüber dem ursprünglichen Taktsignal $T_{Original}$.
|
|
|
|
\autoref{fig:rst_d_ff_tfs_symbol} zeigt die Schaltsymbole für einen RS-FF und D-FF jeweils mit \acs{TFS}.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node at (0.6,0.6) (RSFF) {RS-FF mit TFS};
|
|
\node (R) {~R};
|
|
\node[below=of R] (S) {~S};
|
|
\node at ($(R) + (-0.2,-0.65)$) (T) {};
|
|
\node at ($(T) + (0.85,0)$) {T};
|
|
\node[right=of R] (Q1) {Q~~};
|
|
\node[right=of S] (Q2) {Q*};
|
|
|
|
\node at ($(Q1)+(1,0)$) (Q1Text) {Q};
|
|
\node at ($(Q2)+(1,0)$) (Q2Text) {Q*};
|
|
\node at ($(R)+(-1,0)$) (RText) {R};
|
|
\node at ($(S)+(-1,0)$) (SText) {S};
|
|
\node at ($(T)+(-0.8,0)$) (TText) {T};
|
|
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
|
|
\draw (R) -- (RText);
|
|
\draw (S) -- (SText);
|
|
\draw (T) -- (TText);
|
|
\draw (Q1) -- (Q1Text);
|
|
\draw (Q2) -- (Q2Text);
|
|
|
|
\draw ($(T)+(-0.1,0.2)$) -- ++(0.25,-0.2) -- ++(-0.25,-0.2);
|
|
\end{tikzpicture}
|
|
\hspace*{1cm}
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node at (0.65,0.6) (RSFF) {D-FF mit TFS};
|
|
\node (R) {};
|
|
\node[below=of R] (S) {~S};
|
|
\node at ($(R) + (-0.2,-0.65)$) (T) {};
|
|
\node at ($(T) + (0.85,0)$) {T};
|
|
\node[right=of S] (Q2) {Q};
|
|
|
|
\node at ($(Q2)+(1,0)$) (Q2Text) {Q~};
|
|
\node at ($(S)+(-1,0)$) (DText) {D};
|
|
\node at ($(T)+(-0.8,0)$) (TText) {T};
|
|
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
|
|
\draw (S) -- (DText);
|
|
\draw (T) -- (TText);
|
|
\draw (Q2) -- (Q2Text);
|
|
|
|
\draw ($(T)+(-0.1,0.2)$) -- ++(0.25,-0.2) -- ++(-0.25,-0.2);
|
|
\end{tikzpicture}
|
|
\caption{Schaltsymbol -- RS-Flip-Flop und D-Flip-Flop je mit \acs{TFS}}
|
|
\label{fig:rst_d_ff_tfs_symbol}
|
|
\end{figure}
|
|
|
|
\begin{table}
|
|
\centering
|
|
\begin{tabular}{c|c|c|c}
|
|
Nr. & $T_{orig}$ & $T'$ & $T_X$ \\
|
|
\midrule
|
|
0 & 0 & 1 & 0 \\
|
|
1 & 1 & 0 & 0 \\
|
|
\end{tabular}
|
|
\caption{Wertetabelle - Verzögerung bei der \acl{TFS}}
|
|
\label{tbl:verzoegerung_tfs}
|
|
\end{table}
|
|
|
|
|
|
\textit{Anwendung D-FF}: als schneller Speicher, \zB im CPU-Register, L1-Cache $\Rightarrow$ als klassischer 1~Bit-Speicher
|
|
|
|
\newpage
|
|
\subsubsection{JK-Flip-Flop}
|
|
\enquote{JK} steht für \enquote{Jack Kilby}, bzw. \enquote{Jump-Kill}.
|
|
|
|
Er besitzt dasselbe Verhalten wie der RS-Flip-Flop, verhindert aber die verbotene Eingangsbelegung $R=S=1$ $\Rightarrow$ $J=K=1$ ist erlaubt, dann togglet das JK-Flip-Flop zwischen gesetzt und rückgesetzt. $\Rightarrow$ Bei Wechsel auf $J=K=0$ behält das JK-Flip-Flop in jedem Fall den letzten vorigen Zustand bei.
|
|
|
|
\textit{Besonders gut}: JK-Flip-Flop mit \acl{TFS}: Der Flip-Flop toggelt bei $J=K=1$ und aktiver Tanktflanke genau \textit{ein} mal!
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node at (0.6,0.6) (RSFF) {RS-FF};
|
|
\node (R) {~R};
|
|
\node[below=of R] (S) {~S};
|
|
\node[right=of R] (Q1) {Q~~};
|
|
\node[right=of S] (Q2) {Q*};
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
|
|
\node[and gate, inputs={nn},left=of R] (AND1) {};
|
|
\node[and gate, inputs={nn},left=of S] (AND2) {};
|
|
|
|
\node[left=of AND1.input 2] (K) {K};
|
|
\node[left=of AND2.input 1] (J) {J};
|
|
\draw (K) -- (AND1.input 2);
|
|
\draw (J) -- (AND2.input 1);
|
|
|
|
\draw (R) -- (AND1) (S) -- (AND2);
|
|
\draw (Q1) -- ($(Q1) + (1.4,0)$);
|
|
\draw (Q2) -- ($(Q2) + (1.4,0)$);
|
|
|
|
\node[knoten] at ($(Q1) + (0.8,0)$) (KN1) {};
|
|
\node[knoten] at ($(Q2) + (0.8,0)$) (KN2) {};
|
|
\draw (KN1) -- ++(0,1) -| ($(AND1.input 1) + (-0.5,0)$) -- (AND1.input 1);
|
|
\draw (KN2) -- ++(0,-0.8) -| ($(AND2.input 2)+ (-0.5,0)$) -- (AND2.input 2);
|
|
\end{tikzpicture}
|
|
\caption{JK-Flip-Flop}
|
|
\label{fig:kj_ff}
|
|
\end{figure}
|
|
|
|
|
|
\subsection{\acf{T-FF}}
|
|
Den \acf{T-FF} gibt es nur mit \acf{TFS}! Im Grunde ist es ein \acs{JK-FF} mit $J=K=1$, kann aber auch als \acs{D-FF} realisiert werden. \autoref{fig:jk_als_t_ff} und \autoref{fig:d_als_t_ff} stellen diese beiden Umsetzungen dar und \autoref{fig:symbol_t_ff} zeigt das Schaltsymbol bzw. Gatter des \acs{T-FF}.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node at (0.6,0.6) (RSFF) {JK-FF mit TFS};
|
|
\node (R) {~J};
|
|
\node[below=of R] (S) {~K};
|
|
\node at ($(R) + (-0.2,-0.65)$) (T) {};
|
|
\node at ($(T) + (0.85,0)$) {T};
|
|
\node[right=of R] (Q1) {};
|
|
\node[right=of S] (Q2) {Q};
|
|
|
|
\node at ($(Q2)+(1,0)$) (Q2Text) {Q};
|
|
\node at ($(R)+(-1,0)$) (RText) {\enquote{1}};
|
|
\node at ($(S)+(-1,0)$) (SText) {\enquote{1}};
|
|
\node at ($(T)+(-0.8,0)$) (TText) {T};
|
|
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.2,-0.3)$);
|
|
|
|
\draw (R) -- (RText);
|
|
\draw (S) -- (SText);
|
|
\draw (T) -- (TText);
|
|
\draw (Q2) -- (Q2Text);
|
|
|
|
\draw ($(T)+(-0.1,0.2)$) -- ++(0.25,-0.2) -- ++(-0.25,-0.2);
|
|
\end{tikzpicture}
|
|
\caption{JK-FF als T-FF}
|
|
\label{fig:jk_als_t_ff}
|
|
\end{figure}
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node at (0.6,0.9) (RSFF) {D-FF};
|
|
\node (R) {};
|
|
\node[below=of R] (S) {~D};
|
|
\node at ($(R) + (-0.2,-0.65)$) (T) {};
|
|
\node at ($(T) + (0.85,0)$) {T};
|
|
\node[right=of S] (Q2) {Q*};
|
|
\node[above=of Q2] (Q1) {Q};
|
|
|
|
\node at ($(Q1)+(1,0)$) (Q1Text) {~Q};
|
|
\node at ($(T)+(-0.8,0)$) (TText) {T};
|
|
|
|
\draw ($(R)+(-0.3,0.5)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
|
|
\draw (T) -- (TText);
|
|
\draw (Q1) -- (Q1Text);
|
|
\draw (Q2) -| ($(Q2)+(1,-1)$) -| ($(S) + (-1,0)$) -- (S);
|
|
|
|
\draw ($(T)+(-0.1,0.2)$) -- ++(0.25,-0.2) -- ++(-0.25,-0.2);
|
|
\end{tikzpicture}
|
|
\caption{D-FF als T-FF}
|
|
\label{fig:d_als_t_ff}
|
|
\end{figure}
|
|
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node at (0.6,0.6) (RSFF) {T-FF};
|
|
\node (R) {~~};
|
|
\node[below=of R] (S) {~~};
|
|
\node at ($(R) + (-0.2,-0.65)$) (T) {};
|
|
\node at ($(T) + (0.75,0)$) {T};
|
|
\node[right=of R] (Q1) {Q*~};
|
|
\node[right=of S] (Q2) {Q~~};
|
|
|
|
\node at ($(Q1)+(1,0)$) (Q1Text) {Q*};
|
|
\node at ($(Q2)+(1,0)$) (Q2Text) {Q};
|
|
\node at ($(R)+(-1,0)$) (RText) {};
|
|
\node at ($(S)+(-1,0)$) (SText) {};
|
|
\node at ($(T)+(-0.7,0)$) (TText) {T};
|
|
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
|
|
\draw (T) -- (TText);
|
|
\draw (Q1) -- (Q1Text);
|
|
\draw (Q2) -- (Q2Text);
|
|
|
|
\draw ($(T)+(-0.1,0.2)$) -- ++(0.25,-0.2) -- ++(-0.25,-0.2);
|
|
\end{tikzpicture}
|
|
\caption{Schaltsymbol/Gatter des T-FF}
|
|
\label{fig:symbol_t_ff}
|
|
\end{figure}
|
|
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
|
|
\node at (0.6,0.6) {T-FF};
|
|
\node at (0,0) (R) {~~};
|
|
\node[below=of R] (S) {~~};
|
|
\node at ($(R) + (-0.2,-0.65)$) (T) {};
|
|
\node at ($(T) + (0.65,0)$) {T};
|
|
\node[right=of S] (Q2) {Q~~};
|
|
\node at ($(R)+(-1,0)$) (RText) {};
|
|
\node at ($(S)+(-1,0)$) (SText) {};
|
|
\node at ($(T)+(-0.6,0)$) (TText) {T};
|
|
\draw ($(R)+(-0.3,0.3)$) rectangle ($(Q2)+(0.3,-0.3)$);
|
|
\draw (T) -- (TText);
|
|
\draw ($(T)+(-0.1,0.2)$) -- ++(0.25,-0.2) -- ++(-0.25,-0.2);
|
|
|
|
|
|
\node at (3.6,0.6) {T-FF};
|
|
\node at (3,0) (R2) {~~};
|
|
\node[below=of R2] (S2) {~~};
|
|
\node at ($(R2) + (-0.2,-0.65)$) (T2) {};
|
|
\node at ($(T2) + (0.65,0)$) {T};
|
|
\node[right=of S2] (Q22) {Q~~};
|
|
\node at ($(Q22)+(1,0)$) (Q2Text2) {};
|
|
\node at ($(R2)+(-1,0)$) (RText2) {};
|
|
\node at ($(S2)+(-1,0)$) (SText2) {};
|
|
\draw ($(R2)+(-0.3,0.3)$) rectangle ($(Q22)+(0.3,-0.3)$);
|
|
\draw (Q22) -- (Q2Text2);
|
|
\draw ($(T2)+(-0.1,0.2)$) -- ++(0.25,-0.2) -- ++(-0.25,-0.2);
|
|
|
|
|
|
\node at (6.6,0.6) {T-FF};
|
|
\node at (6,0) (R3) {~~};
|
|
\node[below=of R3] (S3) {~~};
|
|
\node at ($(R3) + (-0.2,-0.65)$) (T3) {};
|
|
\node at ($(T3) + (0.65,0)$) {T};
|
|
\node[right=of S3] (Q23) {Q~~};
|
|
\node at ($(Q23)+(1,0)$) (Q2Text3) {};
|
|
\node at ($(R3)+(-1,0)$) (RText3) {};
|
|
\node at ($(S3)+(-1,0)$) (SText3) {};
|
|
\draw ($(R3)+(-0.3,0.3)$) rectangle ($(Q23)+(0.3,-0.3)$);
|
|
\draw (Q23) -- (Q2Text3);
|
|
\draw ($(T3)+(-0.1,0.2)$) -- ++(0.25,-0.2) -- ++(-0.25,-0.2);
|
|
|
|
\draw (Q2) -- ($(Q2) + (1,0)$) |- (T2);
|
|
\draw (Q22) -- ($(Q22) + (1,0)$) |- (T3);
|
|
|
|
\node at (2,-1.4) {$Q_0$};
|
|
\node at (5,-1.4) {$Q_1$};
|
|
\node at (8,-1.4) {$Q_2$};
|
|
|
|
\end{tikzpicture}
|
|
\vspace{5mm}
|
|
\begin{tabular}{c|ccc|ccc|c}
|
|
Takt $T$ & $Q_0$ & $Q_1$ & $Q_2$ & $Q_2$ & $Q_1$ & $Q_0$ & \\
|
|
\midrule
|
|
0 & 0 & 0 & 0 & 0 & 0 & 0 & \\
|
|
1 & 1 & 1 & 1 & 1 & 1 & 1 & 7 \\
|
|
0 & 1 & 1 & 1 & & & & \\
|
|
1 & 0 & 1 & 1 & 1 & 1 & 0 & 6 \\
|
|
0 & 0 & 1 & 1 & & & & \\
|
|
1 & 1 & 0 & 1 & 1 & 0 & 1 & 5 \\
|
|
0 & 1 & 0 & 1 & & & & \\
|
|
1 & 0 & 0 & 1 & 1 & 0 & 0 & 4 \\
|
|
0 & 0 & 0 & 1 & & & & \\
|
|
1 & 1 & 1 & 0 & 0 & 1 & 1 & 3 \\
|
|
0 & 1 & 1 & 0 & & & & \\
|
|
1 & 0 & 1 & 0 & 0 & 1 & 0 & 2 \\
|
|
\multicolumn{7}{c}{\ldots} \\
|
|
\end{tabular}
|
|
\caption{3~Bit~Zähler -- Rückwärtszähler}
|
|
\label{fig:3_bit_zaehler}
|
|
\end{figure}
|
|
|
|
Wie in \autoref{fig:3_bit_zaehler} auf Seite~\pageref{fig:3_bit_zaehler} zu sehen ist, handelt es sich um einen Rückwärtszähler. Würde anstatt $Q$ $Q*$ verwendet werden, also der Ausgang jeweils negiert werden, aber weiterhin $Q$ für die Werteberechnung verwendet werden, so würde es sich um einen Vorwärtszähler handeln. Gegebenenfalls kann mit \texttt{XOR} and den Ausgängen $Q_0$ und $Q_1$ ein \enquote{Schalter} eingebaut werden, mit dem zwischen Vorwärts- und Rückwärtszähler gewechselt werden kann.
|
|
|
|
Anwendungsen:
|
|
\begin{enumerate}[noitemsep]
|
|
\item Frequenzteiler (Frequenzhalbierer)
|
|
\item Zähler (Rückwärtszähler oder Vorwärtszähler)
|
|
\item Ein-/Ausschalter mit mehreren Bedienstellen, welche jeweils zum Ein- und Ausschalten gedacht sind.
|
|
\end{enumerate}
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
%\textit{Siehe Graphik Nr 5}
|
|
\textit{8 Transistoren (2 \texttt{AND} und 2 \texttt{NOR} mit jeweils 2 Eingängen)}
|
|
\medskip
|
|
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[nor gate, inputs={nn}] at (0,1) (OR1) {};
|
|
\node[nor gate, inputs={nn}] at (0,-1) (OR2) {};
|
|
\node[and gate, inputs={in}, left=of OR1] (AND1) {};
|
|
\node[and gate, inputs={nn}, left=of OR2] (AND2) {};
|
|
|
|
\node at (-3.5,0) (T) {T};
|
|
\node[right=of OR1] (Q1) {Q*};
|
|
\node[right=of OR2] (Q2) {Q~};
|
|
|
|
\node[left=of AND1.input 1] (S) {};
|
|
\node[left=of AND2.input 2] (R) {};
|
|
|
|
\node[knoten] at (T -| S) (K) {};
|
|
\node[knoten] at ($(Q1)+(-0.6,0)$) (K2) {};
|
|
\node[knoten] at ($(Q2)+(-0.6,0)$) (K3) {};
|
|
\draw (K2) -- ($(K2)+(0,-0.7)$)
|
|
-- ($(OR2.input 2) + (-0.4,0.5)$)
|
|
|- (OR2.input 1);
|
|
\draw (K3) -- ($(K3)+(0,0.7)$)
|
|
-- ($(OR1.input 2) + (-0.4,-0.5)$)
|
|
|- (OR1.input 2);
|
|
|
|
\draw (T) -- (K) |- (AND1.input 2);
|
|
\draw (K) |- (AND2.input 1);
|
|
\draw (AND1.input 1) -- ($(AND1.input 1)+(-1.5,0)$) -| ($(R)+(-1.5,0)$);
|
|
\draw ($(R)+(-1.5,0)$) -- (AND2.input 2);
|
|
\draw ($(R)+(-1.5,0)$) -- ($(R)+(-2,0)$);
|
|
\node at ($(R)+(-2.4,0)$) {D};
|
|
\draw (Q1) -- (OR1.output) (Q2) -- (OR2.output);
|
|
\draw (AND1.output) -| (OR1.input 1);
|
|
\draw (AND2.output) -| (OR2.input 2);
|
|
|
|
\node[knoten] at ($(R)+(-1.5,0)$) {};
|
|
|
|
\end{tikzpicture}
|
|
\bigskip
|
|
|
|
\textit{6 Transistoren (2 \texttt{NAND} mit jeweils 3 Eingängen)}
|
|
\medskip
|
|
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
\node[nand gate, inputs={inn}] at (0,1) (NAND1) {};
|
|
\node[nand gate, inputs={nnn}] at (0,-1) (NAND2) {};
|
|
|
|
\node at (-2,0) (T) {T};
|
|
\node[right=of NAND1] (Q1) {Q*};
|
|
\node[right=of NAND2] (Q2) {Q~};
|
|
|
|
\node[knoten] at ($(Q1)+(-0.6,0)$) (K2) {};
|
|
\node[knoten] at ($(Q2)+(-0.6,0)$) (K3) {};
|
|
\draw (K2) -- ($(K2)+(0,-0.7)$)
|
|
-- ($(NAND2.input 2) + (-0.4,0.5)$)
|
|
|- (NAND2.input 1);
|
|
\draw (K3) -- ($(K3)+(0,0.7)$)
|
|
-- ($(NAND1.input 3) + (-0.4,-0.5)$)
|
|
|- (NAND1.input 3);
|
|
|
|
\node[] at ($(NAND2.input 3) + (-2.8,0)$) (D) {D};
|
|
|
|
\draw (T) -- ($(T)+(1,0)$) |- (NAND1.input 2);
|
|
\draw ($(T)+(1,0)$) |- (NAND2.input 2);
|
|
\node[knoten] at ($(T)+(1,0)$) {};
|
|
\draw (Q1) -- (NAND1.output) (Q2) -- (NAND2.output);
|
|
|
|
\draw (NAND1.input 1) -- ($(NAND1.input 1) + (-2,0)$) |- ($(NAND2.input 3) + (-2,0)$) -- (NAND2.input 3);
|
|
\draw ($(NAND2.input 3) + (-2,0)$) -- ($(NAND2.input 3) + (-2.4,0)$);
|
|
\node[knoten] at ($(NAND2.input 3) + (-2.12,0)$) {};
|
|
|
|
\end{tikzpicture}
|
|
\caption{Hardwareaufwand für D-FF}
|
|
\label{fig:hw_aufwand_dff}
|
|
\end{figure}
|
|
|
|
Wie in \autoref{fig:hw_aufwand_dff} auf Seite~\pageref{fig:hw_aufwand_dff} zu sehen ist, beträgt der Hardwareaufwand für den \acs{D-FF} 8 Transistoren bzw. 6 Transistoren bei 1-Bit Speicherkapazität.
|
|
|
|
\subsection{Kondensator}
|
|
Andere Speichertechnologie mit weniger Aufwand. Für die Ladung gilt: $Q=C\cdot U$ \newline
|
|
Einsatz: \zB Hauptspeicher des Universalrechners
|
|
|
|
\begin{itemize}[noitemsep]
|
|
\item speichert Ladung
|
|
\begin{itemize}[noitemsep]
|
|
\item Kondensator aufgeladen $\hat{=} 1$
|
|
\item Kondensator entladen ~~ $\hat{=} 0$
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\draw[very thick] (0.3,-0.66) -- ++(0.4,0);
|
|
\draw[very thick] (0.2,-0.53) -- ++(0.58,0);
|
|
\draw[very thick] (0.1,-0.4) -- ++(0.8,0);
|
|
|
|
\draw[thick] (0.5,-0.4) -- ++(0,0.7);
|
|
|
|
\draw[very thick] (-0.1,0.3) -- (1.1,0.3) ++ (0,0.3) -- ++(-1.2,0);
|
|
|
|
\draw[thick] (0.5,0.6) -- (0.5,1.5) -- ++(2,0) -- ++(0,-2.3);
|
|
\draw[ultra thick,<->,red] (2.5,1.1) -- ++(0,-1.2);
|
|
\node[] at (3.45,0.5) (text) {$Q=C\cdot V$};
|
|
\end{tikzpicture}
|
|
\caption{Kondensator -- Wie messen, ob er geladen ist?}
|
|
\label{fig:kodensator_messen}
|
|
\end{figure}
|
|
|
|
Um den Ladungszustand festzustellen, muss die Spannung gemessen werden (siehe \autoref{fig:kodensator_messen} auf Seite~\pageref{fig:kodensator_messen})! Wird die Spannung gemessen, so gibt es einen Stromfluss $\Rightarrow$ Die Ladung geht verloren! Siehe deshalb \autoref{fig:kondensator_select} auf Seite~\pageref{fig:kondensator_select}.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[scale=1.2,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\draw[very thick] (0.3,-0.66) -- ++(0.4,0);
|
|
\draw[very thick] (0.2,-0.53) -- ++(0.58,0);
|
|
\draw[very thick] (0.1,-0.4) -- ++(0.8,0);
|
|
|
|
\draw[thick] (0.5,-0.4) -- ++(0,0.7);
|
|
|
|
\draw[very thick] (-0.1,0.3) -- (1.1,0.3) ++ (0,0.3) -- ++(-1.2,0);
|
|
|
|
\draw[thick] (0.5,0.6) -- (0.5,1.5);
|
|
|
|
\node[] at (1,1.8) (knoten1) {};
|
|
\draw[thick] (0.5,1.5) -- ++(0.5,0) -- (knoten1);
|
|
\draw[very thick] ($(knoten1) + (-0.3,0)$) -- ++(0.6,0);
|
|
|
|
\node[] at (2.2,1.8) (knoten2) {};
|
|
\draw[very thick] ($(knoten2) + (-0.3,0)$) -- ++(0.6,0);
|
|
|
|
\draw[thick] ($(knoten1) + (-0.3,0.4)$) -- ($(knoten2) + (0.3,0.4)$);
|
|
\draw[thick] (knoten2) -- ++(0,-0.3) -- ++(0.5,0) -- ++(0,-2.2);
|
|
|
|
\draw[ultra thick,<->,red] (2.7,1.1) -- ++(0,-1.2);
|
|
\node[] at (4.5,0.5) (text) {read/write bzw. Data};
|
|
\node[] at (1.5,2.6) (text) {Select};
|
|
\end{tikzpicture}
|
|
\caption{Kondensator -- Speicherzustand messen oder halten über Transistor}
|
|
\label{fig:kondensator_select}
|
|
\end{figure}
|
|
|
|
\begin{Hinweis}
|
|
Nach \textbf{jedem} Lesen muss der Speicherzustand wieder aufgefrischt werden.\newline
|
|
Dies macht eine Refresh-Logik.
|
|
\end{Hinweis}
|
|
|
|
\textbf{2. Problem}: Leckströme führen zum ständigen/langsamen Ladungsverlust, sodass der gesamte Speicher zyklisch, also regelmäßig, komplett durchgelesen werden muss, damit er wieder \enquote{aufgefrischt} wird.
|
|
|
|
Es ist kein \acs{D-FF} für jeden Kondensatorspeicher (Refreshlogik) notwendig, sondern nur so viele, wie vom Kondensatorspeicher gleichzeitig gelesen werden (\zB 64~Bit)!
|
|
|
|
Schreiben des Kondensatorspeichers
|
|
$\Rightarrow$ Anlegen der entsprechenden Spannung für 1 oder 0 / \enquote{High} oder \enquote{Low} / $5V$ oder $0V$ zum Aufladen oder Entladen des Kondensators.
|
|
$\Rightarrow$ Spannung an \texttt{data} Anlegen statt zu Messen und \texttt{select=1}.
|
|
|
|
\textit{Nachteil:} langsames Schreiben wegen Auf-/Entladekurve beim Kondensator (siehe \autoref{fig:ladekurve_kondensator} auf Seite~\pageref{fig:ladekurve_kondensator}).
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}
|
|
|
|
\begin{axis}[grid=both,
|
|
xmax=15,ymax=1,
|
|
axis lines=middle,
|
|
restrict y to domain=0:13,
|
|
enlargelimits]
|
|
\addplot[thick,green,domain=0:13] {(1-pow(2.71828,-x/2))} node[above] {Ladekurve};
|
|
\addplot[thick,red,domain=0:13] {pow(2.71828,-x/2)} node[above] {Entladekurve};
|
|
\end{axis}
|
|
|
|
\end{tikzpicture}
|
|
\caption{(Ent-)Ladekurve des Kondensators}
|
|
\label{fig:ladekurve_kondensator}
|
|
\end{figure}
|
|
|
|
|
|
$\Rightarrow$ Auch beim Lesen wegen notwendigem Refresh!
|