Benutzer:Dirk Huenniger/hagen/cs1/ea2

Aufgabe 1a

Aufgabe 1b

Aufgabe 1c

Aufgabe 2

Aufgabe 3

Aufgabe 4a

Aufgabe 4b

Aufgabe 4c

Aufgabe 5a

Aufgabe 5b

GFDL

$a_{1}$	$a_{2}$	$s$	$b_{1}$	$b_{2}$
0	0	0	0	0
0	0	1	0	0
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1

Man spart keine Gatter wenn man Schaltsymbole ersetzt. Die Frage habe ich demnach entweder nicht verstanden oder sie war grober Unfug.

Mit dem angegeenen Schaltnetz lassen sich nicht alle Permutationen realisieren. Wir betrachten als Beispiel die Permutation

$\begin{matrix} a_{1} \to b_{1} \\ a_{2} \to b_{2} \\ a_{3} \to b_{3} \\ a_{4} \to b_{4} \end{matrix}$

Wegen $a_{1} \to b_{1}$ muss gelten: $s_{1} = s_{3} = 0$

Jetzt landet $a_{2}$ aber auf dem Schaltnetz mit dem Eingang $s_{4}$ . Somit kann $a_{2} \to b_{2}$ nicht mehr erfüllt werden

$\overline{(X_{1} \land X_{2}) \lor (\overline{((\overline{X_{1} \land X_{2}}) \land X_{2}) \lor ((\overline{X_{1} \land X_{2}}) \land X_{1})})}$

Der Ausdruckt verwendet 11 Operationen. 4 Negationen, 5 Disjuktionen und 2 Konjuktionen. Das Schaltnetz hat 8 Gatter. Es gibt also drei zusätzliche Operationen.

Ich berechne die Wertetabelle.

Ich vereinfache den Ausdruck $(\overline{X_{1} \land X_{2}}) \land X_{2} = (\overline{X_{1}} \lor \overline{X_{2}}) X_{2} = X_{1} \overline{X_{2}} \lor 0 = X_{1} \overline{X_{2}}$

und

$(\overline{X_{1} \land X_{2}}) \land X_{1} = X_{2} \overline{X_{1}}$

somit

$\overline{X_{1} \overline{X_{2}} \lor X_{2} \overline{X_{1}}} = \overline{X_{1} \overline{X_{2}}} \land \overline{X_{2} \overline{X_{1}}} = (\overline{X_{2}} \lor X_{1}) \land (\overline{X_{1}} \lor X_{2}) = (\overline{X_{2}} \land \overline{X_{1}}) \lor \overline{X_{2}} X_{2} \lor X_{1} \overline{X_{1}} \lor X_{1} X_{2} = (\overline{X_{2}} \land \overline{X_{1}}) \lor X_{1} X_{2}$

und schlielich

$\overline{(X_{1} X_{2}) \lor (\overline{X_{2}} \land \overline{X_{1}}) \lor X_{1} X_{2}} = \overline{X_{1} X_{2}} \land \overline{\overline{X_{2}} \land \overline{X_{1}}} = (\overline{X_{1}} \lor \overline{X_{2}}) \land (X_{1} \lor X_{2}) = \overline{X_{1}} X_{2} \lor \overline{X_{2}} X_{1}$

Auch hier zur Sicherheit noch einmal die Wertetabelle.

$X_{2}$	$X_{1}$	$\overline{X_{1}} X_{2} \lor \overline{X_{2}} X_{1}$
0	0	0
0	1	1
1	0	1
0	0	0

Der Vereinfachte Ausdruck lautet somit

$\overline{X_{1}} X_{2} \lor \overline{X_{2}} X_{1}$ Er besteht aus zwei Neagtionen, zwei Disjunktionen und einer Konjuktion. Damit hat der Kosten von 5.Das ist kleiner als 11.

$\begin{matrix} [\overline{a_{n}}, ..., \overline{a_{0}}] + 1 & = & - \overline{a_{n}} 2^{n} + (\sum_{i = 0}^{n} \overline{a_{i}} 2^{i}) + 1 \\ = & - (1 - a_{n}) 2^{n} + (\sum_{i = 0}^{n} (1 - a_{i}) 2^{i}) + 1 \\ = & - 2^{n} + a_{n} 2^{n} + ((\sum_{i = 0}^{n} 2^{i}) + 1) - (\sum_{i = 0}^{n} a_{i} 2^{i}) \\ = & - 2^{n} + a_{n} 2^{n} + (\frac{2^{n} - 1}{2 - 1} + 1) - (\sum_{i = 0}^{n} a_{i} 2^{i}) \\ = & a_{n} 2^{n} - \sum_{i = 0}^{n} a_{i} 2^{i} \\ = & - [a_{n}, ..., a_{0}] \end{matrix}$

Man gibt die Hälfte der Eingangsbits auf den ersten Decoder und die andere Hälfte auf den zweiten Decoder. Dann betrachtet man die Menge aller Paare wobei ein Paar aus einem Ausgang des ersten Decoders und einem Ausgang des zweiten Decoders besteht. Für jedes Paar nimmt man seine beiden bestandteile und gibt sie zusammen auf ein AND Gatter mit zwei Eingängen. Den Ausgang dieses AND Gatters identifiziert man mit einem Ausgang des zu konstuierenden n-bit Decoders. Etwas mathematischer kann man das wie folgt ausdrücken. Seien $s_{n - 1}, .., s_{0}$ die Eingänge des zu konstruierenden Decoders und seinen $a_{2^{n} - 1}, .., a_{0}$ seine Ausgänge. Seinen $x_{i}$ und $y_{i}$ die Eingänge des i-ten zu verwendenden AND Gatters und $z_{i}$ sein Ausgang (also $i \in 0, ..., 2^{n} - 1$ ). Seien $t_{\frac{n}{2} - 1}, .., t_{0}$ die Eingänge des ersten benutzen Multiplexers und $b_{2^{0.5 \cdot n} - 1}, .., b_{0}$ seine Ausgänge. Für den zweiten benutzten Decoder entsprechend u für die Eingänge und c für die Ausgänge. Jetzt verbinde ich $s_{i} \to t_{i}$ für $i \in {0, ..., \frac{n}{2} - 1}$ . Ferner verbinde ich $s_{i + \frac{n}{2}} \to u_{i}$ für $i \in {0, ..., \frac{n}{2} - 1}$ . Jetzt verbinde ich $b_{i \mod 2^{0.5 \cdot n}} \to x_{i}$ für $i \in {0, ..., 2^{n} - 1}$ . Dabei steht $i \mod j$ für den Rest der bei der Division der ganzen Zahlen i und j anfällt. Ich verbinde also jeden Ausgang des ersten benutzen Multiplexers mit je $2^{0.5 \cdot n}$ verschiedenen AND Gattern. Etwas anders verbinde ich für den zweiten benutzten Multiplexer $c_{i div 2^{0.5 \cdot n}} \to y_{i}$ für $i \in {0, ..., 2^{n} - 1}$ . Dabei steht $i div j$ für das Ergebnis Division der ganzen Zahlen i und j, wobei der Rest weggeworfen, bzw. das Ergebnis der Division abgerundet wird. Schließlich verbinde ich noch $z_{i} \to a_{i}$ für $i \in {0, ..., 2^{n} - 1}$ . Damit ist das Schaltnetz vollständig definiert.

Die Konsten eines AND Gatters seien 1. Dann ist $C (n) = 2 \cdot C (n / 2) + 2^{n}$

Sei

$n = 2^{k}$

dann ist

$C (k) = 2 \cdot C (k - 1) + 2^{2^{k}}$

und

$C (k) = 2 \cdot (2 \cdot C (k - 2) + 2^{2^{k} - 1}) + 2^{2^{k}} = 2 \cdot 2 \cdot C (k - 2) + 2 \cdot 2^{2^{k} - 1} + 2^{2^{k}} \leq 2 \cdot 2 \cdot C (k - 2) + 2 \cdot 2^{2^{k}}$

und damit

$C (k) \leq 2^{k - 1} \cdot C (1) + (k - 1) 2^{k} \leq k \cdot 2^{k}$

somit

$C (n) \leq n \log n$

$T (n) = T (n / 2) + 1$

Lemma 2.19

$T (n) = 1^{\log n} + \sum_{i = 0}^{\log (n) - 1} 1^{i} \cdot 1 = \log (n)$

Da die Funktion $⟨ ⟩$ bijektiv ist gebe ich anstelle der Binärdarstellung die Werte dieser Funktion an.

$⟨ a ⟩$	$⟨ b ⟩$	$⟨ s ⟩$	$⟨ s^{'} ⟩$
0	0	0	1
0	1	1	2
0	2	2	3
0	3	3	4
1	0	1	2
1	1	2	3
1	2	3	4
1	3	4	5
2	0	2	3
2	1	3	4
2	2	4	5
2	3	5	6
3	0	3	4
3	1	4	5
3	2	5	6
3	3	6	7

Ich gehe davon aus das Halbaddierer und Volladdierer jeweils Kostenmass und Tiefenmass 1 haben. Tiefe ist 4. Kosten ist 5.

$A = X_{1} \land X_{2}$

$B = \overline{A} \land X_{2}$

$C = \overline{A} \land X_{1}$

$D = \overline{B \lor C}$

$\overline{A \lor D}$

Die Lizenz die nun folgt ist eigentlich für einen Übungszettel nicht notwendig. Wahrscheinlich ist dieser wegen der zu gerigen Schöpfungshöhe sowiso nicht schützenswert. Dennoch wird sie automatisch angehängt und kann von mir nicht wirklich abgeschaltet werden. Hiermit seinen Kursbetreuer und Korrekturkräfte berechtigt in einer ihrem Amt angemessenen Weise mit diesem Übungszettel zu verfahren. In der Tat habe ich in dieser Arbeit die Schaltsymbole für Voll und Halbaddierer von MichaelFrey verwendet und bin somit an die GFDL gebunden.