\documentclass[10pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}

\DeclareMathOperator{\CSA}{CSA}
\DeclareMathOperator{\FA}{FA}
\DeclareMathOperator{\MUX}{MUX}
\DeclareMathOperator{\Dec}{Dec}
\DeclareMathOperator{\FDec}{FDec}
\DeclareMathOperator{\BCD}{BCD}
\DeclareMathOperator{\BA}{BA}
\DeclareMathOperator{\alu}{alu}
\DeclareMathOperator{\testi}{testi}
\DeclareMathOperator{\shifta}{shifta}
\DeclareMathOperator{\IR}{IR}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}

\thispagestyle{empty}

\title{Rechnerarchitektur - Übungsblatt 7 \\
	Übungsgruppe 8 - Di, 15-17 Uhr \\
	Steffen Heil}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Carsten Saar (Matrikelnummer 2030107) \\
	Thomas Ospelt (Matrikelnummer 2029959) \\
	Timo Adam (Matrikelnummer 2031946)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}
\begin{enumerate}[(a)]
  \item unter der Voraussetzung, dass die Instruktion \texttt{lhg} entsprechend der Konstruktion der ALU in der Vorlesung eine reguläre ALU-Operation ist, obwohl sie den Operanden RS1 nicht verwendet:
        $$ \alu = (\IR[31:26]=0^6) \wedge \IR[5] \wedge (\sim(\IR[4] \vee \IR[3])) $$
  \item unter der Voraussetzung, dass die Instruktionen \texttt{clri} und \texttt{seti} auch als Test-Operation mit Operaden RS1 und Immediate-Konstante gelten, obwohl die Immediate-Konstante nicht verwandt wird (entsprechend der Konstruktion aus der Vorlesung):
        $$ \testi = (\sim\IR[31]) \wedge \IR[30] \wedge \IR[29] $$
  \item $$ \shifta = (\IR[31:26]=0^6) \wedge (\sim(\IR[5] \vee \IR[4] \vee \IR[3])) \wedge \IR[0] $$
\end{enumerate}

\section*{Aufgabe 2}
Sei $x\in\{0,1\}^n; \; k<n$.
\paragraph{zu zeigen:}
$\lfloor \left<x\right> / 2^k\rfloor \cdot 2^k = \left<x[n-1:k]0^k\right>$.

\paragraph{Beweis:}
\begin{eqnarray*}
	\left\lfloor \frac{\left<x\right>}{2^k}\right\rfloor \cdot 2^k & = & \left\lfloor \frac{\displaystyle \sum_{i=0}^{n-1} x_i 2^i}{2^k}\right\rfloor \cdot 2^k \\
	& = & \left\lfloor \sum_{i=0}^{n-1} x_i \cdot \frac{2^i}{2^k}\right\rfloor \cdot 2^k \\
	& = & \left\lfloor \left(\sum_{i=0}^{k-1} x_i \cdot \frac{2^i}{2^k}\right) + \left(\sum_{i=k}^{n-1} x_i \cdot \frac{2^i}{2^k}\right)\right\rfloor \cdot 2^k
\end{eqnarray*}

\paragraph{Untersuche, welchen Wert der Term $\sum_{i=0}^{k-1} x_i \cdot \frac{2^i}{2^k}$ annehmen kann:}
Da $x_i \in \{0,1\}$, ist das Minimum des obigen Terms offensichtlich gleich $0$ und das Maximum gleich
\begin{eqnarray*}
	\sum_{i=0}^{k-1} \frac{2^i}{2^k} & = & \frac{1}{2^k} \cdot \sum_{i=0}^{k-1} 2^i \\
	& = & \frac{1}{2^k} \cdot (2^k-1) \\
	& = & \frac{2^k}{2^k} - \frac{1}{2^k} \\
	& = & 1 - \frac{1}{2^k} \\
	& < & 1 \text{ da } \frac{1}{2^k}>0 \text{ für endliche } k
\end{eqnarray*}

\paragraph{Untersuche, welchen Wert der Term $\sum_{i=k}^{n-1} x_i \cdot \frac{2^i}{2^k}$ annehmen kann:}
Es gilt:
$$\frac{2^i}{2^k} = 2^{i-k} \in \SetN \; \; \forall i \ge k$$
Ist $\frac{2^i}{2^k} = 2^{i-k} \in \SetN$, so gilt auch
$$x_i \cdot \frac{2^i}{2^k} \in \SetN \; \; \forall i \ge k \AND \forall x_i \in \{0,1\}$$
Die Summe einer Menge von natürlichen Zahlen ist ebenfalls wieder eine natürliche Zahl. Somit ist
$$\sum_{i=k}^{n-1} x_i \cdot \frac{2^i}{2^k} \in \SetN$$
Addiert man zu einer natürlichen Zahl $n\in\SetN$ eine rationale Zahl $q\in\SetQ$ mit $0 \le q < 1$, so gilt:
$$\lfloor n+q \rfloor = n$$
Für die obige Umformung ergibt sich dann
\begin{eqnarray*}
	\left\lfloor \frac{\left<x\right>}{2^k}\right\rfloor \cdot 2^k & = & \left\lfloor \underbrace{\left(\sum_{i=0}^{k-1} x_i \cdot \frac{2^i}{2^k}\right)}_{\in\SetQ, \ge0, <1} + \underbrace{\left(\sum_{i=k}^{n-1} x_i \cdot \frac{2^i}{2^k}\right)}_{\in\SetN}\right\rfloor \cdot 2^k \\
	& = & \left(\sum_{i=k}^{n-1} x_i \cdot \frac{2^i}{2^k}\right) \cdot 2^k \\
	& = & \sum_{i=k}^{n-1} x_i \cdot 2^i \\
	& = & \left(\sum_{i=k}^{n-1} x_i \cdot 2^i\right) + 0 \\
	& = & \left(\sum_{i=k}^{n-1} x_i \cdot 2^i\right) + \left(\sum_{i=0}^{k-1} 0 \cdot 2^i\right) \\
	& = & \left<x[n-1:k] 0^k\right>
\end{eqnarray*}
\hfill $\Box$

\newpage

\section*{Aufgabe 3}
\begin{enumerate}[ (a) ]

\item {\bfseries Zu zeigen:}
$$[a] \cdot [b] = \left<a\right> \cdot \left<b\right> - (a_{n-1}\cdot\left<b[n-2:0]\right>+\left<a[n-2:0]\right>\cdot b_{n-1})\cdot 2^n$$
\paragraph{Beweis:}
\begin{eqnarray*}
	[a] \cdot [b] & = & (-a_{n-1} \cdot 2^{n-1} + \left<a[n-2:0]\right>) \cdot (-b_{n-1} \cdot 2^{n-1} + \left<b[n-2:0]\right>) \\
	& = & \left(-a_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-2} a_i \cdot 2^i\right) \cdot \left(-b_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-2} b_i \cdot 2^i\right) \\
	& = & \left(-2a_{n-1} \cdot 2^{n-1} + a_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-2} a_i \cdot 2^i\right) \cdot \left(-2 b_{n-1} \cdot 2^{n-1} + b_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-2} b_i \cdot 2^i\right) \\
	& = & \left(-2a_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-1} a_i \cdot 2^i\right) \cdot \left(-2b_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-1} b_i \cdot 2^i\right) \\
	& = & \left(-a_{n-1} \cdot 2^n + \sum_{i=0}^{n-1} a_i \cdot 2^i\right) \cdot \left(-b_{n-1} \cdot 2^n + \sum_{i=0}^{n-1} b_i \cdot 2^i\right) \\
	& = & \left(-a_{n-1} \cdot 2^n + \left<a\right>\right) \cdot \left(-b_{n-1} \cdot 2^n + \left<b\right>\right) \\
	& = & a_{n-1} \cdot 2^n \cdot b_{n-1} \cdot 2^n - \left<a\right>b_{n-1} \cdot 2^n - a_{n-1} \cdot 2^n \cdot \left<b\right> + \left<a\right> \cdot \left<b\right> \\
	& = & a_{n-1}b_{n-1} \cdot 2^{2n} - b_{n-1} \cdot 2^n \cdot \left(a_{n-1} \cdot 2^{n-1} + \left<a[n-2:0]\right>\right) \\
	& & -a_{n-1} \cdot 2^n \cdot \left(b_{n-1} \cdot 2^{n-1} + \left<b[n-2:0]\right>\right) + \left<a\right> \cdot \left<b\right> \\
	& = & a_{n-1}b_{n-1} \cdot 2^{2n} - b_{n-1} \cdot 2^n \cdot a_{n-1} \cdot 2^{n-1} - b_{n-1} \cdot 2^n \cdot \left<a[n-2:0]\right> \\
	& & -a_{n-1} \cdot 2^n \cdot b_{n-1} \cdot 2^{n-1} - a_{n-1} \cdot 2^n \cdot \left<b[n-2:0]\right> + \left<a\right> \cdot \left<b\right> \\
	& = & a_{n-1}b_{n-1} \cdot 2^{2n} - a_{n-1}b_{n-1} \cdot 2^{2n-1} - a_{n-1}b_{n-1} \cdot 2^{2n-1} \\
	& & -a_{n-1} \cdot 2^n \cdot \left<b[n-2:0]\right> - b_{n-1} \cdot 2^n \cdot \left<a[n-2:0]\right> + \left<a\right> \cdot \left<b\right> \\
	& = & a_{n-1}b_{n-1} \cdot 2^n - 2a_{n-1}b_{n-1} \cdot 2^{2n-1} - a_{n-1} \cdot 2^n \cdot \left<b[n-2:0]\right> \\
	& & - b_{n-1} \cdot 2^n \cdot \left<a[n-2:0]\right> + \left<a\right> \cdot \left<b\right> \\
	& = & a_{n-1}b_{n-1} \cdot 2^n - a_{n-1}b_{n-1} \cdot 2^n - a_{n-1} \cdot 2^n \cdot \left<b[n-2:0]\right> \\
	& & -b_{n-1} \cdot 2^n \cdot \left<a[n-2:0]\right> + \left<a\right> \cdot \left<b\right> \\
	& = & \left<a\right> \cdot \left<b\right> - \left(a_{n-1} \cdot \left<b[n-2:0]\right> + \left<a[n-2:0]\right> \cdot b_{n-1}\right) \cdot 2^n
\end{eqnarray*}
\hfill $\Box$

\item {\bfseries Zu zeigen:}$[a] \cdot [b]$ lässt sich als 2's complement Zahl mit $2n$ Bit darstellen.
\paragraph{Beweis:}gegeben $a,b \in \{0,1\}^n$.
\begin{eqnarray*}
	\left[a\right] & = & -a_{n-1} \cdot 2^{n-1} + \left<a[n-2:0]\right> = -a_{n-1} \cdot 2^{n-1} + \left(\sum_{i=0}^{n-2} a_i \cdot 2^i\right) \\
	\left[b\right] & = & -b_{n-1} \cdot 2^{n-1} + \left< b [n-2:0]\right> = -b_{n-1} \cdot 2^{n-1} + \left(\sum_{i=0}^{n-2} b_i \cdot 2^i\right)
\end{eqnarray*}
Der kleinstmögliche darstellbare Wert einer 2's complement Zahl wird dann angenommen, wenn $a_{n-1}=1$ und $a_i=0 \forall i<n-1$, da nur das vorderste Bit $a_{n-1}$ negativ in die Summe einfließt (alle anderen Summanden sind positiv). Somit ist der kleinstmögliche darstellbare Wert einer 2's complement Zahl $2^{n-1}$. Der größtmögliche darstellbare Wert wird jedoch dann erreicht, wenn das vorderste Bit $a_{n-1}=0$ und $a_i=1 \forall i<n-1$, da alle Summanden $a_i$ positiv sind. Der größtmögliche darstellbare Wert ist also $\sum_{i=0}^{n-2} 2^i = 2^{n-1}-1$. Somit gilt: $a,b \in \{-2^{n-1}, \dots, 2^{n-1}-1\}$. \\
Man muss nun drei Fälle unterscheiden, die Vorzeichen von $[a]$ und $[b]$ betreffend: beide Vorzeichen sind negativ, beide sind positiv, die Vorzeichen sind verschieden.
\paragraph{Fallunterscheidung:}
\begin{enumerate}[1.]
	\item {\bfseries beide Vorzeichen negativ:}
	Das Vorzeichen dieses Produkts ist in jedem Fall positiv. Es muss also nur betrachtet werden, ob das Produkt in jedem Fall $\le 2^{2n-1}-1$ (bzw. $<2^{2n-1}$) ist. Es ist offensichtlich, dass das Produkt maximal wird, wenn beide Faktoren minimal werden. Dazu müssen $-2^{n-1}$ und $-2^{n-1}$ miteinander multipliziert werden:
	$$(-2^{n-1}) \cdot (-2^{n-1}) = 2^{2n-2} = 2^{2(n-1)} = \frac{1}{2} \cdot 2^{2n-1} \le 2^{2n-1}$$
	Dies gilt, da $2^{2n-1}>0$ ist. \\
	Das Produkt zweier negativer 2's complement Zahlen mit $n$ Bit liegt somit immer im Wertebereich einer 2's complement Zahl mit $2n$ Bit.

	\item {\bfseries beide Vorzeichen positiv:}
	Das Vorzeichen dieses Produkts ist ebenfalls in jedem Fall positiv. Somit muss man nur betrachten, ob das Produkt in jedem Fall $\le 2^{2n-1}-1$ (bzw. $<2^{2n-1}$) ist. Das Produkt wird genau dann maximal, wenn beide Faktoren ($2^{n-1}-1$) maximal werden. Es wird wieder multipliziert:
	$$(2^{n-1}-1) \cdot (2^{n-1}-1) < 2^{n-1} \cdot 2^{n-1}$$
	Somit liegt das Produkt zweier positiver 2's complement Zahlen mit $n$ Bit immer im Wertebereich einer 2's complement Zahl mit $2n$ Bit.

	\item {\bfseries verschiedene Vorzeichen:}
	Hier gibt es zwei Fälle: $[a]\ge0 \AND [b]<0$ und $[a]<0 \AND [b]\ge0$. Diese müssen jedoch nicht gesondert betrachtet werden, da die Multiplikation kommutativ ist. Das Vorzeichen dieses Produkts ist in jedem Fall negativ. Es muss also betrachtet werden, ob das Produkt in jedem Fall $\ge -2^{2n-1}$ ist. Das Produkt wird genau dann minimal, wenn die kleinstmögliche darstellbare Zahl $-2^{n-1}$ mit der größtmöglichen darstellbaren Zahl $2^{2n-1}-1$ multipliziert wird:
	\begin{eqnarray*}
		(-2^{n-1}) \cdot (2^{n-1}-1) = -2^{2n-2} + 2^{n-1} & \stackrel{!}{\ge} & -2^{2n-1} \\
		\Leftrightarrow 2^{2n-1} - 2^{2n-2} & \stackrel{!}{\ge} & -2^{n-1} \\
		\Leftrightarrow 2^{2n-2} \cdot (2-1) & \stackrel{!}{\ge} -2^{n-1} \\
		\Leftrightarrow \underbrace{2^{2n-2}}_{\ge0} & \stackrel{!}{\ge} \underbrace{-2^{n-1}}_{<0} \; \; \text{ (w)}
	\end{eqnarray*}
	Das Produkt zweier 2's complement Zahlen mit verschiedenen Vorzeichen und der Länge von $n$ Bits liegt immer im Wertebereich einer 2's complement Zahl mit $2n$ Bit.
\end{enumerate}
Da in allen drei möglichen Fällen das Produkt im Wertebereich einer 2's complement Zahl mit $2n$ Bit liegt, lässt sich $[a] \cdot [b]$ als 2's complement Zahl mit $2n$ Bit darstellen. \hfill $\Box$
\end{enumerate}

\section*{Aufgabe 4}
\begin{enumerate}[(a)]
	\item {\bfseries Konstruktion:} Seien $x_i'$ die Eingänge und $y_i'$ die Augänge des PP mit $\frac{n}{2}$ Bit. Dann gilt nach Konstruktion
	$$x_i' = x_{2i} \circ x_{2i+1}$$
	$$y_i = 
		\begin{cases}
			x_0, & \text{für } i=0 \\
			y_k', & \text{für } i=2k+1, k \in \SetN_{>0} \\
			x_i \circ y_{k-1}', & \text{für } i=2k, k \in \SetN_{>0} \\
			y_{\frac{n}{2}-1}', & \text{für } i=n-1
		\end{cases}
	$$
	Es soll gelten:
	$$y_0 = x_0$$
	$$y_i = x_i \circ \dots \circ x_0 \; \forall i \in \{1, \dots, n-1\}$$

	\paragraph{Induktionsvoraussetzung:}
	$$y_0' = x_0'$$
	$$y_i' = x_i' \circ \dots \circ x_0' \; \forall i \in \left\{1, \dots, \frac{n}{2}-1\right\}$$

	\paragraph{Induktionsanfang:}
	\begin{itemize}
		\item $n=1$: \\
		Nach Konstruktion gilt $y_0=x_0$. Dies erfüllt die geforderte Eigenschaft
		\item $n=2$: \\
		Nach Konstruktion gilt $y_0=x_0$. Aus $x_0'=x_0 \circ x_1$ folgt nach Induktionsvoraussetzung $y_0'=x_0'=x_0 \circ x_1$. Dies erfüllt die geforderte Eigenschaft.
	\end{itemize}

	\paragraph{Induktionsschritt:} $\frac{n}{2} \leadsto n$. Untersuche vier möglichen Fälle für $y_i$:
	\begin{itemize}
		\item $i=0$: \\
		$y_0=x_0$ gilt trivialerweise.
		\item $i=2k+1$:
		\begin{eqnarray*}
			y_i & \stackrel{\text{Konstr.}}{=} & y_k' \; \; \text{ mit } k = \frac{i-1}{2} \\
			& \stackrel{\text{IV}}{=} & x_k' \circ \dots \circ x_0' \; \; \text{ mit } k=\frac{i-1}{2} \\
			& \stackrel{\text{Konstr.}}{=} & (x_{2k} \circ x_{2k+1}) \circ \dots \circ (x_{2\cdot0} \circ x_{2\cdot0+1}) \; \; \text{ mit } k=\frac{i-1}{2} \\
			& = & (x_{i-1} \circ x_{i}) \circ \dots \circ (x_0 \circ x_1) \\
			& \stackrel{\text{Kommut.}}{=} & (x_i \circ x_{i-1}) \circ \dots \circ (x_1 \circ x_0) \\
			& \stackrel{\text{Assoz.}}{=} & x_i \circ x_{i-1} \circ \dots \circ x_1 \circ x_0
		\end{eqnarray*}
		Dieser Fall gilt ebenfalls.
		\item $i=2k$:
		\begin{eqnarray*}
			y_i & \stackrel{\text{Konstr.}}{=} & x_i \circ y_{k-1}' \; \; \text{ mit } k=\frac{i}{2} \\
			& \stackrel{\text{IV}}{=} & x_i \circ (x_{k-1}' \circ \dots \circ x_0') \; \; \text{ mit } k=\frac{i}{2} \\
			& \stackrel{\text{Konstr.}}{=} & x_i \circ \left((x_{2(k-1)} \circ x_{2(k-1)+1}) \circ \dots \circ (x_{2\cdot0} \circ x_{2\cdot0+1})\right) \; \; \text{ mit } k=\frac{i}{2} \\
			& = & x_i \circ \left((x_{i-2} \circ x_{i-1}) \circ \dots \circ (x_{2\cdot0} \circ x_{2\cdot0+1})\right) \\
			& \stackrel{\text{Kommut.}}{=} & x_i \circ \left((x_{i-1} \circ x_{i-2}) \circ \dots \circ (x_1 \circ x_0)\right) \\
			& \stackrel{\text{Assoz.}}{=} & x_i \circ \left(x_{i-1} \circ x_{i-2} \circ \dots \circ x_1 \circ x_0\right) \\
			& \stackrel{\text{Assoz.}}{=} & x_i \circ x_{i-1} \circ \dots \circ x_1 \circ x_0 \\
		\end{eqnarray*}
		Dieser Fall gilt auch.
		\item $i=n-1$:
		\begin{eqnarray*}
			y_i & \stackrel{\text{Konstr.}}{=} & y_{\frac{n}{2}-1}' \\
			& \stackrel{\text{IV}}{=} & x_{\frac{n}{2}-1}' \circ \dots \circ x_0' \\
			& \stackrel{\text{Konstr.}}{=} & \left(x_{2\cdot(\frac{n}{2}-1)} \circ x_{2\cdot(\frac{n}{2}-1)+1}\right) \circ \dots \circ (x_0 \circ x_1) \\
			& = & (x_{n-2} \circ x_{n-1}) \circ \dots \circ (x_0 \circ x_1) \\
			& \stackrel{\text{Kommut.}}{=} & (x_{n-1} \circ x_{n-2}) \circ \dots \circ (x_1 \circ x_0) \\
			& \stackrel{\text{Assoz.}}{=} & x_{n-1} \circ x_{n-2} \circ \dots \circ x_1 \circ x_0
		\end{eqnarray*}
		Auch dieser Fall gilt.
	\end{itemize}
\hfill $\Box$

\item
\begin{eqnarray*}
	C(PP_\circ(1)) & = & 0 \\
	C(PP_\circ(n)) & = & C\left(PP_\circ\left(\frac{n}{2}\right)\right) + \frac{n}{2} \cdot C(\circ) + \left(\frac{n}{2}-1\right) \cdot C(\circ) \\
	& = & C\left(PP_\circ\left(\frac{n}{2}\right)\right) + (n-1) \cdot C(\circ) \\
	D(PP_\circ(1)) & = & 0 \\
	D(PP_\circ(n)) & = & D\left(PP_\circ\left(\frac{n}{2}\right)\right) + 2 \cdot D(\circ)
\end{eqnarray*}

\end{enumerate}


\end{document}