\documentclass[10pt]{article}

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

\thispagestyle{empty}

\title{Computer Architecture 1 - Übungsblatt 2}
\author{Dirk Heine, 2030941 \\
	Jan Hendrik Dithmar, 2031259 \\
	Steffen Heil, 2019358
}
\date{}

\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{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage

\section*{Aufgabe 1: bijection}
\subsubsection*{(i)}
{\bf Beweis: Die Abbildung
$$\langle\ \rangle: \{0,1\}^n \to \{0, ..., 2^{n}-1\};\ 
\langle a \rangle := \sum_{i=0}^{n-1} a_i 2^i$$
ist bijektiv.}\\
\\
\begin{enumerate}
\item {\bf Injektivität} \\
Seien $a,b \in \{0,1\}^n$ und $a \ne b$.\\
Sei $k = \max \{ i | a_i \ne b_i \}$ und o.B.d.A. $a_k < b_k$.
\begin{eqnarray*}
a_k < b_k & \Rightarrow & a_k = 0 \wedge b_k = 1
\end{eqnarray*}
Damit:
\begin{eqnarray*}
\langle a \rangle - \langle b \rangle
& = & \sum_{i=0}^{n-1} a_i 2^i - \sum_{i=0}^{n-1} b_i 2^i\\
& = & \sum_{i=k+1}^{n-1} a_i 2^i + a_k 2^k +  \sum_{i=0}^{k-1} a_i 2^i\\
&   & - \left( \sum_{i=k+1}^{n-1} b_i 2^i + b_k 2^k +  \sum_{i=0}^{k-1} b_i 2^i \right) \\
& = & \sum_{i=k+1}^{n-1} a_i 2^i - \sum_{i=k+1}^{n-1} b_i 2^i + a_k 2^k - b_k 2^k + \sum_{i=0}^{k-1} a_i 2^i - \sum_{i=0}^{k-1} b_i 2^i\\
& = & 0 \cdot 2^k - 1 \cdot 2^k + \sum_{i=0}^{k-1} a_i 2^i - \sum_{i=0}^{k-1} b_i 2^i\\
& < & 0
\end{eqnarray*}
\item {\bf Surjektivität}\\
Da $\#(\{0,1\}^n) = 2^n = \#(\{0, ..., 2^{n}-1\})$ und da $\langle \rangle$ injektiv ist, ist $\langle \rangle$ surjektiv.
\end{enumerate}
Damit ist gezeigt, dass $\langle \rangle$ bijektiv ist.

\subsubsection*{(ii)}
{\bf Beweise: Die Abbildung
$$[\ ]: \{0,1\}^n \to \{-2^{n-1}, ..., 2^{n-1}-1\};\ 
[a] := -a_{n-1} \cdot 2^{n-1} + \langle a[n-2:0] \rangle$$
ist bijektiv.}\\
\begin{enumerate}
\item {\bf Injektivität}\\
Seien $a,b \in \{0,1\}^n$ und $a \ne b$.\\

\begin{enumerate}
\item $a_{n-1} = b_{n-1}$
\begin{eqnarray*}
&             & a[n-2:0] \ne b[n-2:0]\\
& \Rightarrow & \langle a[n-2:0] \rangle \ne \langle b[n-2:0] \rangle\\
& \Rightarrow & - 2^{n-1} a_{n-1} + \langle a[n-2:0] \rangle \ne - 2^{n-1} b_{n-1} + \langle b[n-2:0] \rangle\\
& \Rightarrow & [a] \ne [b]
\end{eqnarray*}
\item $a_{n-1} \ne b_{n-1}$,  o.B.d.A. sei $a_{n-1} < b_{n-1}$
\begin{eqnarray*}
&             & \langle a[n-2:0] \rangle \ge 0 \wedge \langle b[n-2:0] \rangle < 2^{n-1}\\
& \Rightarrow & - 2^{n-1} a_{n-1} + \langle a[n-2:0] \rangle \ge 0 > - 2^{n-1} b_{n-1} + \langle b[n-2:0] \rangle\\
& \Rightarrow & [ a ] \ne [ b ]
\end{eqnarray*}
\end{enumerate}

\item {\bf Surjektivität}\\
Da $\#(\{0,1\}^n) = 2^n = \#(\{-2^{n-1}, ..., 2^{n-1}-1\})$ und da $[\ ]$ injektiv ist, ist $[\ ]$ surjektiv.
\end{enumerate}
Damit ist gezeigt, dass $[\ ]$ bijektiv ist.

\newpage

\section*{Aufgabe 2: associativity}
\begin{eqnarray*}
	((g_2,p_2) \circ (g_1,p_1)) \circ (g_3,p_3) & = & (g_2 \OR (g_1 \AND p_2), p_1 \AND p_2) \circ (g_3,p_3) \\
	& = & ([g_2 \OR (g_1 \AND p_2)] \OR [g_3 \AND (p_1 \AND p_2)], p_1 \AND p_2 \AND p_3) \\
	& = & (g_2 \OR [(p_2 \AND g_1) \OR (p_2 \AND (g_3 \AND p_1))], p_1 \AND p_2 \AND p_3) \\
	& = & (g_2 \OR [p_2 \AND (g_1 \OR (g_3 \AND p_1))], p_1 \AND p_2 \AND p_3) \\
	& \stackrel{(*)}{=} & (g_2 \OR [(g_1 \OR (g_3 \AND p_1)) \AND p_2], p_1 \AND p_2 \AND p_3) \\
	& \stackrel{(*)}{=} & (g_2, p_2) \circ (g_1 \OR (g_3 \AND p_1), p_1 \AND p_3) \\
	& \stackrel{(*)}{=} & (g_2, p_2) \circ ((g_1,p_1) \circ (g_3,p_3))
\end{eqnarray*}
\QED \\
Beweis von $(*)$:
\begin{eqnarray*}
	(g_2,p_2) \circ ((g_1,p_1) \circ (g_3,p_3)) & = & (g_2,p_2) \circ (g_1 \OR (g_3 \AND p_1), p_1 \AND p_3) \\
	& = & (g_2 \OR ((g_1 \OR (g_3 \AND p_1)) \AND p_2), p_1 \AND p_2 \AND p_3)
\end{eqnarray*}


\newpage

\section*{Aufgabe 3: cost of parallel prefix computation}
\begin{eqnarray*}
	C(l) & = & \sum_{i=1}^l (2^i-1) \\
	& = & \sum_{i=1}^l 2^i - l \\
	& = & \sum_{i=0}^l 2^i - 1 - l \\
	& = & 2^{l+1} - 1 - 1 - l \\
	& = & 2^{l+1} - l - 2
\end{eqnarray*}
Ind($l$): ($n=2^l$)
\begin{itemize}

\item $l=1$:
\begin{eqnarray*}
	C(1) & = & 1 \\
	& = & 2^{1+1} - 1 - 2
\end{eqnarray*}

\item $l \leadsto l+1$:
\begin{eqnarray*}
	C(l) & = & C(l-1) + 2^l - 1 \\
	& \stackrel{IV}{=} & 2^l - (l-1) - 2 + 2^l - 1 \\
	& = & 2^{l+1} - l - 2
\end{eqnarray*}
\end{itemize}
\QED


\newpage

\section*{Aufgabe 4: Adder}
$$neg \stackrel{!}{=} a_{n-1} \oplus b_{n-1} \oplus c_{n-1}$$
Proof:
\begin{eqnarray*}
	[a] + [b] + c_{in} & = & -a_{n-1} \cdot 2^{n-1} + \langle a[n-2:0]\rangle - b_{n-1} \cdot 2^{n-1} + \langle b[n-2:0]\rangle + c_{in} \\
	& = & -(a_{n-1} + b_{n-1}) \cdot 2^{n-1} + \underbrace{\langle a[n-2:0]\rangle + \langle b[n-2:0]\rangle + c_{in}}_{\langle c_{n-2}, s[n-2:0]\rangle} \\
	& = & -(a_{n-1} + b_{n-1}) \cdot 2^{n-1} + c_{n-2} \cdot 2^{n-1} + \langle s[n-2:0]\rangle \\
	& = & -2^{n-1} (\underbrace{a_{n-1} + b_{n-1} + c_{n-2}}_{\langle c_{n-1}, s_{n-1}\rangle} -2c_{n-2}) + \langle s[n-2:0]\rangle \\
	& = & -2^{n-1}(2c_{n-1} + s_{n-1} - 2c_{n-2}) + \langle s[n-2:0]\rangle \\
	& = & [s[n-1:0]] - 2^n (c_{n-1} - c_{n-2}) = \delta
\end{eqnarray*}
Cases:
\begin{itemize}
	\item $c_{n-1} = 1, c_{n-2} = 0$:
		\begin{eqnarray*}
			\delta & = & [s] - 2^n \\
			& = & -2^n - \underbrace{[s[n-1:0]]}_{\le 2^{n-1} -1} \\
			& \le & -2^{n-1} - 1 \not\in T_n
		\end{eqnarray*}
	\item $c_{n-1} = 0, c_{n-2} = 1$:
		\begin{eqnarray*}
			\delta & = & [s] + 2^n \\
			& = & 2^n + \underbrace{[s[n-1:0]]}_{\ge -2^{n-1}} \\
			& \ge & 2^{n-1} \not\in T_n
		\end{eqnarray*}
	\item $c_{n-1} = c_{n-2}$:
		\begin{eqnarray*}
			\delta & = & [s] \in T_n
		\end{eqnarray*}
\end{itemize}
Looking at case $c_{n-1} = c_{n-2}$
\begin{eqnarray*}
	\Rightarrow \delta & = & [s[n-1:0]] \\
	& = & -s_{n-1} \cdot 2^{n-1} + \langle s[n-2:0]\rangle \\
	& = & -2^{n-1} (a_{n-1} + b_{n-1} - c_{n-2}) + \langle s[n-2:0]\rangle
\end{eqnarray*}
\begin{center}
\begin{tabular}{c|c|c|c|c}
	$a_{n-1}$ & $b_{n-1}$ & $c_{n-1} = c_{n-2}$ & $(a_{n-1} + b_{n-1} - c_{n-2})[0]$ & $neg = a_{n-1} \oplus b_{n-1} \oplus c_{n-1}$ \\ \hline
	0 & 0 & 0 & 0 & 0 \\ \hline
	1 & 0 & 0 & 1 & 1 \\ \hline
	0 & 1 & 0 & 1 & 1 \\ \hline
	1 & 1 & 0 & 0 & 0 \\ \hline
	0 & 0 & 1 & 1 & 1 \\ \hline
	1 & 0 & 1 & 0 & 0 \\ \hline
	0 & 1 & 1 & 0 & 0 \\ \hline
	1 & 1 & 1 & 1 & 1
\end{tabular}
\end{center}


\end{document}