\documentclass[12pt]{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 4}
\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}
\subsubsection*{1.}
\begin{itemize}
	\item
		\verb!srl R10 R21 R12! \\
%		shiftet den Wert in R21 um R12 stellen nach rechts und speichert das Ergebnis in R10
		shifts den value stored in R21 by the value stored in R12 and stores the result in register R10.

	\item
		\verb!seqi R5 R18 109! \\
%		testet ob der Inhalt von R18 = 109 ist und speichert falls ja eine 1 und falls nein eine 0 in R5
		tests, if the content stored in R18 equals 109. if R18=109, 1 is stored in register R5, if not, 0 is stored in register R5.
\end{itemize}

\subsubsection*{2.}
\begin{itemize}
	\item
		\verb!000000 00011 11001 01111 00000 100110!
	
	\item
		\verb!001000 01001 00011 0000000001111010!
\end{itemize}


\newpage

\section*{Aufgabe 2}
\begin{eqnarray*}
	rtype(c) & = & (IR[31:26](c) = 0^6) \\
	jtype(c) & = & (IR[31:28](c) = 0^4 \AND (IR[27:26](c) = 10 \OR IR[27:26](c) = 11)) \\
	itype(c) & = & /rtype(c) \AND /jtype(c) \\
	alui(c) & = & (IR[31:29](c) = 001 \AND (IR[28:26](c) \in \{000,001,010,011,100,101,110,111\})) \\
	testi(c) & = & (IR[31:29](c) = 011 \AND (IR[28:26](c) \in \{000,001,010,011,100,101,110,111\})) \\
	shi(c) & = & (IR[31:26](c) = 0^6 \AND IR[5:2](c)=0^4 \AND IR[1:0](c) \in \{00,10,11\}) \\
	alu(c) & = & (IR[31:26](c) = 0^6 \AND IR[5:3](c)=100 \\
	& & \AND IR[2:0](c) \in \{000,001,010,011,100,101,110,111\}) \\
	test(c) & = & (IR[31:26](c) = 0^6 \AND IR[5:3](c)=101 \\
	& & \AND IR[2:0](c) \in \{000,001,010,011,100,101,110,111\}) \\
	sh(c) & = & (IR[31:26](c) = 0^6 \AND IR[5:3](c)= 0^3 \AND IR[2:0](c) \in \{1,00,110,111\}) \\
	j(c) & = & (IR[31:26](c)= 0^410) \\
	jal(c) & = & (IR[31:26](c)=0^411) \\
	jr(c) & = & (IR[31:26](c) = 010110) \\
	jalr(c) & = & (IR[31:26](c) = 010111) \\
	jump(c) & = & ((IR[31:28](c)=0^4 \OR IR[31:28]=0101) \\
	& & \AND (IR[27:26](c)=10 \OR IR[27:26](c)=11))
\end{eqnarray*}


\newpage

\section*{Aufgabe 3}
\begin{itemize}
	\item Lemma 1 \\
		$e \in \{0,1\}^{30}$. $e$ is 30-bit wide and $a[31:1]$ ist 31-bit wide so $e \neq a[31:1]$ can never be true. $\rightarrow$ nothing to prove!\\
		Assuming that the lemma has to be
		$$\forall i. \forall a \in \{0,1\}^{32}. \exists e \in  \{0,1\}^{30}. e \neq a[31:2] \rightarrow c^{i}.m(a) = c^{i+1}.m(a)$$
		$e \not\in CR \Longleftrightarrow a[31:2] \in CR \stackrel{(SC 3)}{\Longrightarrow} /store(c^i)$. \\
		If we have no store in step $i$, the memory at address $a$ is unchanged:
		$$c^{i+1}.m(a) = c^i.m(a)$$
		$e \in CR \Longleftrightarrow a[31:2] \not\in CR \Longrightarrow \text{we can have } store(c^i)$.
		$$c^{i+1}.m(a) = c^i.m(a)$$
		only holds if $a \not\in \{ea(c^i),...,ea(c^i) +_{32} d(c^i)_{32}\}$.
	
	\item Lemma 2 \\
		If $a[31:2] \in CR$ there is no store in step $i$ and no store in step $i+1$ because of SC 3. $(*)$ \\[0.2cm]
		$Ind(i)$: \\
		$i=0$: $$c^i.m(a) = c^0.m(a)$$
		$i \leadsto i+1$:
		\begin{eqnarray*}
			c^{i+1}.m(a) & \stackrel{(*)}{=} & c^i.m(a) \\
			& \stackrel{(IH)}{=} & c^0.m(a)
		\end{eqnarray*}
		\QED
\end{itemize}


\newpage

\section*{Aufgabe 5}
\begin{eqnarray*}
	C(n) & = & (n-2) \cdot C_{or} + C_{nor} \\
	& = & (n-2) \cdot 1 + 1 \\
	& = & n-1 \\[0.3cm]
	D(n) & = & (\lceil \log(n)\rceil -1) \cdot D_{or} + D_{nor} \\
	& = & (\lceil \log(n)\rceil -1) \cdot 1 + 1 \\
	& = & \lceil \log(n)\rceil
\end{eqnarray*}
Proof:
\subsubsection*{cost}
$n=1$: $$C(1) = 1-1 = 0$$
$n \leadsto n+1$:
\begin{eqnarray*}
	C(n+1) & = & (n-1) \cdot C_{or} + C_{nor} \\
	& \stackrel{(IH)}{=} & C(n) \cdot C_{or} + C_{nor} \\
	& = & C(n) + 1
\end{eqnarray*}

\subsubsection*{delay}
$n=1$: $$D(1) = \lceil \log(1)\rceil = 0$$
$n \leadsto 2n$:
\begin{eqnarray*}
	D(2n) & = & (\lceil \log(2n)\rceil -1) \cdot D_{or} + D_{nor} \\
	& = & (\lceil \log(n) + 1\rceil -1) \cdot D_{or} + D_{nor} \\
	& = & (\lceil \log(n)\rceil +1-1) \cdot D_{or} + D_{nor} \\
	& = & \lceil \log(n)\rceil \cdot D_{or} + D_{nor} \\
	& \stackrel{(IH)}{=} & D(n) \cdot D_{or} + D_{nor} \\
	& = & D(n) +1
\end{eqnarray*}

\end{document}