\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 1}
\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: partition lemma}

\begin{eqnarray*}
\left\langle a\left[n-1:m\right]\right\rangle \cdot 2^m + \left\langle a\left[m-1:0\right]\right\rangle &\stackrel{\text{Def.}}{=}& 2^m \cdot \displaystyle \sum^{n-1}_{i=m} a_i \cdot 2^{i-m} + \sum^{m-1}_{i=0} a_i \cdot 2^i\\
&=& \sum^{n-1}_{i=m} (a_i \cdot 2^{i-m} \cdot 2^m) + \sum^{m-1}_{i=0} a_i \cdot 2^i \\
&=& \sum^{n-1}_{i=m} a_i \cdot 2^i + \sum^{m-1}_{i=0} a_i \cdot 2^i \\
&=& \sum^{n-1}_{i=0} a_i \cdot 2^i \\
&\stackrel{\text{Def.}}{=}& \left\langle a\left[n-1:0\right]\right\rangle
\end{eqnarray*}
\QED

\newpage

\section*{Aufgabe 2: binary fractions}

\begin{eqnarray*}
	\langle a[n-1:0].f[1:p]\rangle & = & \sum_{i=0}^{n-1} a_i \cdot 2^i + \sum_{i=1}^p f_i \cdot 2^{-i} \\
	& = & \sum_{i=p}^{p+n-1} a_{i-p} \cdot 2^{(i-p)} + \sum_{i=1}^p f_i \cdot 2^{-i} \\
	& = & \sum_{i=p}^{p+n-1} a_{i-p} \cdot 2^i \cdot 2^{-p} + \sum_{i=1}^p f_i \cdot 2^{-i} \\
	& = & \left(\sum_{i=p}^{p+n-1} a_{i-p} \cdot 2^i + \sum_{i=1}^p f_i \cdot 2^{-i} \cdot 2^p \right) \cdot 2^{-p} \\
	& = & \left(\sum_{i=p}^{p+n-1} a_{i-p} \cdot 2^i + \sum_{i=1}^p f_i \cdot 2^{p-i} \right) \cdot 2^{-p} \\
	& = & \left(\sum_{i=p}^{p+n-1} a_{i-p} \cdot 2^i + \sum_{i=0}^{p-1} f_{p-i} \cdot 2^i \right) \cdot 2^{-p} \\
	& = & \langle af\rangle \cdot 2^{-p}
\end{eqnarray*}

\newpage

\section*{Aufgabe 3: basic properties of two's complement numbers}


\begin{itemize}
	\item sign extension: $[a] = [a_{n-1}a]$
		\begin{eqnarray*}
		\left[a_{n-1}a\right] &=& -a_{n-1} \cdot 2^n + \left\langle a\left[n-1:0\right]\right\rangle \\
		&=& -a_{n-1} \cdot 2^n + a_{n-1} \cdot 2^{n-1} + \left\langle a\left[n-2:0\right]\right\rangle \\
		&=& \left[a\right] \\
		\end{eqnarray*}
		\QED
	\item sign bit: $[a]<0 \leftrightarrow a_{n-1} = 1$ \\
		zu zeigen: $\langle a[n-2:0]\rangle < 2^{n-1}$
		\begin{eqnarray*}
		[a] < 0 \Leftrightarrow -a_{n-1} \cdot 2^{n-1} + \langle a[n-2:0]\rangle & < & 0 \\
		\Leftrightarrow \langle a[n-2:0]\rangle & < & a_{n-1} \cdot 2^{n-1} \\
		\Leftrightarrow a_{n-1} & \stackrel{(1)}{=} & 1 \\[0.5cm]
		\text{da } 2^{n-1} > \langle a[n-2:0]\rangle & \ge & 0 \quad (1)
		\end{eqnarray*}
		Beweis der Hilfsbehauptung: \\
		\begin{itemize}
			\item $n=1$: $$\langle a[-1:0]\rangle = 0 < 1 = 2^0$$
			\item $n \leadsto n+1$:
			\begin{eqnarray*}
				\langle a[n-2:0]\rangle & = & a_{n-2} \cdot 2^{n-2} + \langle a[n-3:0]\rangle \\
				& \stackrel{IV}{<} & a_{n-2} \cdot 2^{n-2} + 2^{n-2} \\
				& \le & 2^{n-2} + 2^{n-2} = 2^{n-1}
			\end{eqnarray*}
		\end{itemize}
		\QED
	\item $[a] \equiv \langle a[n-2:0]\rangle \mod 2^{n-1} \Leftrightarrow \exists k \in \SetZ: \; [a] - \langle a[n-2:0]\rangle = k \cdot 2^{n-1}$
		\begin{eqnarray*}
			[a] - \langle a[n-2:0]\rangle & = & -a_{n-1} \cdot 2^{n-1} + \langle a[n-2:0]\rangle - \langle a[n-2:0]\rangle \\
			& =& -a_{n-1} \cdot 2^{n-1} \Rightarrow k = -a_{n-1}
		\end{eqnarray*}
		\QED
	\item $[a] \equiv \langle a\rangle \mod 2^n$
		\begin{eqnarray*}
			[a] - \langle a\rangle & = & -a_{n-1} \cdot 2^{n-1} + \langle a[n-2:0]\rangle - \langle a[n-1:0]\rangle \\
			& = & -a_{n-1} \cdot 2^{n-1} + \langle a[n-2:0]\rangle - a_{n-1} \cdot 2^{n-1} - \langle a[n-2:0]\rangle \\
			& = & -2 \cdot a_{n-1} \cdot 2^{n-1} \\
			& = & -a_{n-1} \cdot 2^n \Rightarrow k = -a_{n-1}
		\end{eqnarray*}
		\QED
	\item $-[a] = [\overline{a}] + 1$
		\begin{eqnarray*}
		\left[\overline{a}\right] + 1 &=& - \overline{a_{n-1}} \cdot 2^{n-1} + \left\langle \overline{a\left[n-2:0\right]}\right\rangle + 1 \\
		&=& - \overline{a_{n-1}} \cdot 2^{n-1} + ( \sum_{i=0}^{n-2} \overline{a_i} \cdot 2^i ) + 1 \\
		&=& - ( 1-a_{n-1} ) \cdot 2^{n-1} + ( \sum_{i=0}^{n-2} (1-a_i) \cdot 2^i ) + 1 \\
		&=& - 2^{n-1} + a_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-2} 2^i - ( \sum_{i=0}^{n-2} a_i \cdot 2^i ) + 1 \\
		&=& - 2^{n-1} + a_{n-1} \cdot 2^{n-1} + 2^{n-1} - 1 - ( \sum_{i=0}^{n-2} a_i \cdot 2^i ) + 1 \\
		&=& a_{n-1} \cdot 2^{n-1} - \sum_{i=0}^{n-2} a_i \cdot 2^i \\
		&=& - (-a_{n-1} \cdot 2^{n-1} + \left\langle a\left[n-2:0\right]\right\rangle ) \\
		&=& - \left[a\right] \\
		\end{eqnarray*}
		\QED
\end{itemize}

\newpage

\section*{Aufgabe 4: cheap full adder}
\bild{16}{fa.jpg}{Full Adder}{}

\newpage

\section*{Aufgabe 5: arithmetic unit}

\begin{eqnarray*}
	[a] & = & -a_{n-1} \cdot 2^{n-1} + \langle a[n-2:0]\rangle \\
	& = & -2a_{n-1} \cdot 2^{n-1} + a_{n-1} \cdot 2^{n-1} + \langle a[n-2:0]\rangle \\
	& = & -a_{n-1} \cdot 2^n + \langle a \rangle
\end{eqnarray*}

\begin{eqnarray*}
	[s] & = & \left\{ {\begin{array}{cl} [a] + [b] \mod 2^n & : sub = 0 \\ 	{[a] - [b]} \mod 2^n & : sub = 1 \end{array}}\right. \\
	\Leftrightarrow -s_{n-1} \cdot 2^n + \langle s\rangle & = & \left\{\begin{array}{cl} -a_{n-1} \cdot 2^n + \langle a\rangle + (-b_{n-1} \cdot 2^n + \langle b\rangle) \mod 2^n & : sub = 0 \\ -a_{n-1} \cdot 2^n + \langle a\rangle - (-b_{n-1} \cdot 2^n + \langle b\rangle) \mod 2^n & : sub = 1\end{array}\right. \\
	\Leftrightarrow \langle s\rangle & = & \left\{\begin{array}{cl} \langle a\rangle + \langle b\rangle \mod 2^n & : sub = 0 \\ \langle a\rangle - \langle b\rangle \mod 2^n & : sub = 1\end{array}\right.
\end{eqnarray*}


\end{document}