03 Boolesche Funktionen und Addierer

Boolesche Funktionen und Addierer

3.1 Boolesche Funktion als Tabelle

Eine boolesche Funktion $\lambda$ ordnet jeder Eingangsbelegung $x_i$ (einem Bitvektor) einen Ausgangsvektor $y$ zu: $\lambda :x\to y$

Die Eingangsbelegungen werden durchnummeriert: Der Index $i$ ist genau der Dualwert der Eingangsbits. Beispiel mit 3 Eingängen $x_2{x}_1{x}_0$: $x_4=[1,0,0]\text{(denn }100_2=4\text{)},x_4(x_2)=1,x_4(x_1)=0,x_4(x_0)=0$

Doppelte Bezeichnung

$x_0,x_1,x_2$ sind die Eingangsvariablen (Spalten). $x_i$ mit $i=0\dots 7$ sind die Belegungen (Zeilen). Gleiche Buchstaben, verschiedene Bedeutung. Aus dem Kontext lesen!

3.2 Volladdierer (Folie S. 25)

Der Volladdierer addiert an Stelle $n$ die Bits $a_n$, $b_n$ und den Übertrag ${\ddot{u}}_{n-1}$ der Stelle davor. Heraus kommen Summenbit $s_n$ und neuer Übertrag ${\ddot{u}}_n$.

$i$	${\ddot{u}}_{n-1}$ ($x_2$)	$a_n$ ($x_1$)	$b_n$ ($x_0$)	${\ddot{u}}_n$ ($y_1$)	$s_n$ ($y_0$)	$t$
0	0	0	0	0	0	0
1	0	0	1	0	1	1
2	0	1	0	0	1	1
3	0	1	1	1	0	2
4	1	0	0	0	1	1
5	1	0	1	1	0	2
6	1	1	0	1	0	2
7	1	1	1	1	1	3

$t$ ist die Anzahl der Einsen am Eingang, also die Summe als Zahl. Es gilt $t=2\cdot {\ddot{u}}_n+s_n$. Der Ausgang $({\ddot{u}}_n,s_n)$ ist einfach $t$ als zweistellige Dualzahl.

Mehrere Belegungen können denselben Ausgang haben, z.B. $\lambda (x_1)=\lambda (x_2)=\lambda (x_4)=[0,1]$ (genau eine Eins am Eingang → Summe 1, kein Übertrag).

3.3 Funktionsindex (FI)

Definition

Man liest die Ausgangsspalte einer Funktion von $i=7$ bis $i=0$ (von unten nach oben) als Dualzahl und schreibt sie hexadezimal. Das ist der Funktionsindex. Er identifiziert die Funktion eindeutig.

Volladdierer:

• $\ddot{u}$: Spalte von unten $11101000_2$ → $F{I}_{\ddot{u}}=E8H$
• $s$: Spalte von unten $10010110_2$ → $F{I}_s=96H$

3.4 Einsmengen: Boolesche Mengenalgebra (BMA)

Statt der ganzen Tabelle notiert man nur, bei welchen Belegungen die Funktion 1 ist, die Einsmenge $x^1$: $x_s^1=\{x_1,x_2,x_4,x_7\},x_{\ddot{u}}^1=\{x_3,x_5,x_6,x_7\}$

Muster erkennen (Ergänzung, nicht aus der Mitschrift)

• $s=1$ genau bei ungerader Anzahl Einsen → $s=x_2\oplus x_1\oplus x_0$ (XOR über alle drei)
• $\ddot{u}=1$ genau bei mindestens zwei Einsen → Mehrheitsfunktion $\ddot{u}=x_1{x}_0\vee x_2{x}_0\vee x_2{x}_1$

Beides lässt sich an der Tabelle oben direkt nachprüfen.

3.5 Halbaddierer (Folie S. 32)

Der Halbaddierer addiert nur zwei Bits $a_0$, $b_0$, ohne eingehenden Übertrag.

Funktion:

$i$	$a_0$ ($x_1$)	$b_0$ ($x_0$)	${\ddot{u}}_0$ ($y_1$)	$s_0$ ($y_0$)
0	0	0	0	0
1	0	1	0	1
2	1	0	0	1
3	1	1	1	0

Einsmengen (BMA): $x_{\ddot{u}}^1=\{x_3\}$, $x_s^1=\{x_1,x_2\}$

Struktur als schaltalgebraischer Ausdruck (BAA): $y_1={\ddot{u}}_0=x_1{x}_0\text{(AND)}$ $y_0=s_0=\neg x_1{x}_0\vee x_1\neg x_0=x_1\oplus x_0\text{(XOR, Antivalenz)}$

Schaltung: ein XOR-Gatter (=1) für $S$, ein AND-Gatter (&) für $\ddot{U}$:

Selbsttest

Wie baut man aus zwei Halbaddierern und einem OR-Gatter einen Volladdierer? (Tipp: Erst $a_n+b_n$, dann das Ergebnis $+{\ddot{u}}_{n-1}$. Wann entsteht ein Übertrag?)

3.6 Syntax und Semantik (Folie S. 34)

Syntax

Gibt die Struktur einer Sprache an („Lehre vom Satzbau“): welche Ausdrücke überhaupt zulässig sind.

• zulässig: $x_1\vee x_1\neg x_0$
• nicht zulässig: $x_2\vee \wedge x_1\neg x_0$ (zwei Operatoren direkt hintereinander)

Die Operatoren haben in beiden Schreibweisen eigene Zeichen: Negation $\neg$, Konjunktion $\wedge$, Disjunktion $\vee$ (BAA); in der BMA die „geschwungenen“ Mengenzeichen.

Semantik

Lehre von der inhaltlichen Bedeutung. Sie ordnet einem zulässigen Ausdruck eine Bedeutung zu (z.B. „das ist die Summe eines Volladdierers“). Kernfrage: Welchen Wert (0 oder 1) hat ein Ausdruck $h(x)$ bei einer bestimmten Eingangsbelegung $x_i$? Dafür gibt es die Wertfunktion $W(h(x),x_i)\in \{0,1\}$.

3.7 Beispiel: Wertverlauf (Folie S. 50)

$h(x)=x_2\vee x_1{x}_0$

$i$	$x_2$	$x_1$	$x_0$	$h(x)$
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

Die ganze Spalte heißt Wertverlauf, ein einzelner Eintrag ist ein Wert der Wertfunktion, z.B. $W(x_2\vee x_1{x}_0,x_6)=1$.

$F{I}_h=11111000_2=F8H$

Abweichung zur Mitschrift

In der Mitschrift steht in Zeile $i=3$ eine 0. Richtig ist 1, weil $x_1{x}_0=1\cdot 1=1$. Der Funktionsindex F8H in der Mitschrift stimmt aber schon, er setzt die 1 voraus.

Offen

Die Langformen der Abkürzungen BAA und BMA stehen nicht ausgeschrieben in der Mitschrift. BMA wird dort als „Boolesche Mengenalgebra“ bezeichnet, BAA steht für die schaltalgebraischen Ausdrücke. Mit Folie abgleichen.

Zurück: 02 Logische Grundfunktionen