Benutzer:Dirk Huenniger/hagen/cs1/ea2

Aufgabe 1a

$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

Aufgabe 1b

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

Aufgabe 1c

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

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

Wegen $a_{1}\rightarrow 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}\rightarrow b_{2}$ nicht mehr erfüllt werden

Aufgabe 2

${\overline {(X_{1}\wedge X_{2})\vee \left({\overline {\left(\left({\overline {X_{1}\wedge X_{2}}}\right)\wedge X_{2}\right)\vee \left(\left({\overline {X_{1}\wedge X_{2}}}\right)\wedge X_{1}\right)}}\right)}}$

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.

$X_{2}$	$X_{1}$	$A=X_{1}\wedge X_{2}$	$B={\overline {A}}\wedge X_{2}$	$C={\overline {A}}\wedge X_{1}$	$D={\overline {B\vee C}}$	${\overline {A\vee D}}$
0	0	0	0	0	1	0
0	1	0	0	1	0	1
1	0	0	1	0	0	1
1	1	1	0	0	1	0

Ich vereinfache den Ausdruck $\left({\overline {X_{1}\wedge X_{2}}}\right)\wedge X_{2}=\left({\overline {X_{1}}}\vee {\overline {X_{2}}}\right)X_{2}=X_{1}{\overline {X_{2}}}\vee 0=X_{1}{\overline {X_{2}}}$

und

$\left({\overline {X_{1}\wedge X_{2}}}\right)\wedge X_{1}=X_{2}{\overline {X_{1}}}$

somit

${\overline {X_{1}{\overline {X_{2}}}\vee X_{2}{\overline {X_{1}}}}}={\overline {X_{1}{\overline {X_{2}}}}}\wedge {\overline {X_{2}{\overline {X_{1}}}}}=\left({\overline {X_{2}}}\vee X_{1}\right)\wedge \left({\overline {X_{1}}}\vee X_{2}\right)=\left({\overline {X_{2}}}\wedge {\overline {X_{1}}}\right)\vee {\overline {X_{2}}}X_{2}\vee X_{1}{\overline {X_{1}}}\vee X_{1}X_{2}=\left({\overline {X_{2}}}\wedge {\overline {X_{1}}}\right)\vee X_{1}X_{2}$

und schlielich

${\overline {(X_{1}X_{2})\vee \left({\overline {X_{2}}}\wedge {\overline {X_{1}}}\right)\vee X_{1}X_{2}}}={\overline {X_{1}X_{2}}}\wedge {\overline {{\overline {X_{2}}}\wedge {\overline {X_{1}}}}}=\left({\overline {X_{1}}}\vee {\overline {X_{2}}}\right)\wedge \left(X_{1}\vee X_{2}\right)={\overline {X_{1}}}X_{2}\vee {\overline {X_{2}}}X_{1}$

Auch hier zur Sicherheit noch einmal die Wertetabelle.

$X_{2}$	$X_{1}$	${\overline {X_{1}}}X_{2}\vee {\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}\vee {\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.

Aufgabe 3

${\begin{array}{ccl}\left[{\overline {a_{n}}},...,{\overline {a_{0}}}\right]+1&=&-{\overline {a_{n}}}2^{n}+\left(\sum _{i=0}^{n}{\overline {a_{i}}}2^{i}\right)+1\\&=&-\left(1-a_{n}\right)2^{n}+\left(\sum _{i=0}^{n}\left(1-a_{i}\right)2^{i}\right)+1\\&=&-2^{n}+a_{n}2^{n}+\left(\left(\sum _{i=0}^{n}2^{i}\right)+1\right)-\left(\sum _{i=0}^{n}a_{i}2^{i}\right)\\&=&-2^{n}+a_{n}2^{n}+\left({\frac {2^{n}-1}{2-1}}+1\right)-\left(\sum _{i=0}^{n}a_{i}2^{i}\right)\\&=&a_{n}2^{n}-\sum _{i=0}^{n}a_{i}2^{i}\\&=&-\left[a_{n},...,a_{0}\right]\end{array}}$

Aufgabe 4a

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}\rightarrow t_{i}$ für $i\in \{0,...,{\frac {n}{2}}-1\}$. Ferner verbinde ich $s_{i+{\frac {n}{2}}}\rightarrow u_{i}$ für $i\in \{0,...,{\frac {n}{2}}-1\}$. Jetzt verbinde ich $b_{i\operatorname {mod} 2^{0.5\cdot n}}\rightarrow x_{i}$ für $i\in \{0,...,2^{n}-1\}$. Dabei steht $i\operatorname {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\operatorname {div} 2^{0.5\cdot n}}\rightarrow y_{i}$ für $i\in \{0,...,2^{n}-1\}$. Dabei steht $i\operatorname {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}\rightarrow a_{i}$ für $i\in \{0,...,2^{n}-1\}$. Damit ist das Schaltnetz vollständig definiert.

Aufgabe 4b

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$

Aufgabe 4c

$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)$

Aufgabe 5a

Da die Funktion $\langle \rangle$ bijektiv ist gebe ich anstelle der Binärdarstellung die Werte dieser Funktion an.

$\langle a\rangle$	$\langle b\rangle$	$\langle s\rangle$	$\langle s'\rangle$
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

Aufgabe 5b

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

GFDL

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.