\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}

\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{\QED}{\ensuremath{\hspace*{\fill}\square}}

\thispagestyle{empty}

\begin{center}
  {\Large Übungsblatt 5} \\
  Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
  Carsten Saar (Matrikelnummer 2030107) \\
  Thomas Ospelt (Matrikelnummer 2029959) \\
  Timo Adam (Matrikelnummer 2031946) \\
  Übungsgruppe 8 - Di, 15-17 Uhr \\
  Steffen Heil \\
\end{center}

\newpage
\section*{Aufgabe 1}
\begin{eqnarray*}
{[s]} & = & -s_{n-1} 2^{n-1} + \left<s[n-2:0]\right> \\
{[a]} & = & -a_{n-1} 2^{n-1} + \left<a[n-2:0]\right> \\
{[b]} & = & -b_{n-1} 2^{n-1} + \left<b[n-2:0]\right>
\end{eqnarray*}

\begin{eqnarray*}
[a] = [b] & \Leftrightarrow & -a_{n-1}2^{n-1} + \left(\sum_{i=0}^{n-2}a_i2^i\right) = -b_{n-1}2^{n-1} + \left(\sum_{i=0}^{n-2}b_i2^i\right) \\
& \Leftrightarrow & -a_{n-1}2^{n-1} + \left(\sum_{i=0}^{n-2}a_i2^i\right) - \left[-b_{n-1}2^{n-1}+\left(\sum_{i=0}^{n-2}b_i2^i\right)\right] = 0 \\
& \Leftrightarrow & -a_{n-1}2^{n-1}+ \left(\sum_{i=0}^{n-2}a_i2^i\right) + b_{n-1}2^{n-1} - \left(\sum_{i=0}^{n-2}b_i2^i\right) = 0 \\
& \Leftrightarrow & (b_{n-1}-a_{n-1})2^{n-1} + \left(\sum_{i=0}^{n-2}(b_i-a_i)2^i\right) = 0 \\
& \Leftrightarrow & b_i - a_i = 0 \; \; \forall i \\
& \Leftrightarrow & b_i = a_i \; \; \forall i \\
& \Leftrightarrow & a_i = b_i \; \; \forall i \; \; (*)
\end{eqnarray*}

\begin{eqnarray*}
[s] & = & [a]-[b] = (a_{n-1}-b_{n-1})2^{n-1} + \left(\sum_{i=0}^{n-2}(b_i-a_i)2^i\right) \\
& = & -s_{n-1}2^{n-1} + \left(\sum_{i=0}^{n-2}s_i2^i\right) = 0 \\
& \Leftrightarrow & s_i = a_i -b_i \; \; (**)
\end{eqnarray*}

\glqq$\Rightarrow$\grqq : $s[n-1:0]=0^n \Rightarrow [a]=[b]$:
\begin{eqnarray*}
s[n-1:0] = 0^n & \Leftrightarrow & s_i = 0 \; \; \forall i \\
& \stackrel{(**)}{\Leftrightarrow} & a_i - b_i = 0 \; \; \forall i \\
& \Leftrightarrow & a_i = b_i \; \; \forall i \\
& \stackrel{(*)}{\Leftrightarrow} & [a]=[b]
\end{eqnarray*}

\glqq$\Leftarrow$\grqq : $[a] = [b] \Rightarrow s[n-1:0] = 0^n$:
\begin{eqnarray*}
[a] = [b] & \stackrel{(*)}{\Leftrightarrow} a_i = b_i \; \; \forall i \\
& \Leftrightarrow & a_i - b_i = 0 \\
& \stackrel{(**)}{\Leftrightarrow} & s_i = 0 \\
& \Leftrightarrow & s[n-1:0]=0^n
\end{eqnarray*}

\section*{Aufgabe 2}
\subsubsection*{Soll-Funktionsweise des Decoders:}
$$ \Dec_n(x[n-1:0]) = d[2^n-1:0] \text{ mit } d_i = \begin{cases}
                                                      0 & \text{für } i \neq \langle x \rangle \\
                                                      1 & \text{für } i = \langle x \rangle \\
                                                    \end{cases} $$
\subsubsection*{Funktionsweise des Decoders aus der Vorlesung:}
Sei im folgenden $x_{n-1}=1$. Nach Konstruktions-Definition ist
$$ d[2^{n-1}-1:0]=0^{2^{n-1}} $$
$$ d[2^n-1:2^{n-1}] = Dec_{n-1}(x[n-2:0]) $$
\subsubsection*{Beweis:}
Die Korrektheit des $\Dec_{n-1}$ ist als Voraussetzung gegeben. Somit gilt
$$ d_i = 0 \quad\forall i \in \{0,\ldots,2^{n-1}-1\} $$
$$ d_i = 1 \quad\Longleftrightarrow\quad i = \langle x[n-2:0] \rangle + 2^{n-1} \quad\forall i \in \{2^{n-1},\ldots,2^n-1\} $$
Da $\forall i < 2^{n-1} \quad d_i=0$ folgt offensichtlich
$$ d_i = 1 \quad\Longleftrightarrow\quad i = \langle x[n-2:0] \rangle + 2^{n-1} \quad\forall i \in \{0,\ldots,2^n-1\} $$
$$ d_i = 1 \quad\Longleftrightarrow\quad i = \langle x[n-1:0] \rangle \quad\forall i \in \{0,\ldots,2^n-1\} $$
Dies entspricht der Definition der Funktionsweise des Decoders. \QED

\section*{Aufgabe 3}
\begin{enumerate}[(a)]
\item $ \FDec_1(x[0:0]) := d[1:0] $ mit $ d_0 = \overline{x_0} $ und $ d_1 = x_0 $ \\
      $ \FDec_n(x[n-1:0]) := d[2^n-1:0] $ mit \\
      $ l \left[ 2^{n/2}-1:0 \right] = \FDec_\frac{n}{2} \left( x \left[ \frac{n}{2}-1:0 \right] \right) $ und \\
      $ h \left[ 2^{n/2}-1:0 \right] = \FDec_\frac{n}{2} \left( x \left[ n-1:\frac{n}{2} \right] \right) $ und \\
      $ d_i := l_{i \text{ mod } 2^{n/2}} \wedge h_{i \text{ div } 2^{n/2}} $ \\
\item Soll-Funktionsweise des Decoders:
      $$ \FDec_n(x[n-1:0]) = d[2^n-1:0] \text{ mit } d_i = \begin{cases}
                                                            0 & \text{für } i \neq \langle x \rangle \\
                                                            1 & \text{für } i = \langle x \rangle \\
                                                          \end{cases} $$
      \textbf{Induktionsanfang $n=1$:}
      $$ \FDec_n(x[n-1:0]) = \FDec_1(x_0) = d[1:0] $$
      \begin{eqnarray*}
        d_0 & = & \begin{cases}
                    0 & \text{für } 0 = i \neq \langle x \rangle = x_0 \\
                    1 & \text{für } 0 = i = \langle x \rangle = x_0 \\
                  \end{cases} \\
        d_0 & = & \begin{cases}
                    0 & \text{für } x_0 \neq 0 \\
                    1 & \text{für } x_0 = 0 \\
                  \end{cases} \\
        d_0 & = & \overline{x_0} \quad\text{(nach Soll-Funktionsweise)} \\
        d_0 & = & \overline{x_0} \quad\text{(nach Konstruktion)} \\
        d_1 & = & \begin{cases}
                    0 & \text{für } 1 = i \neq \langle x \rangle = x_0 \\
                    1 & \text{für } 1 = i = \langle x \rangle = x_0 \\
                  \end{cases} \\
        d_1 & = & \begin{cases}
                    0 & \text{für } x_0 \neq 1 \\
                    1 & \text{für } x_0 = 1 \\
                  \end{cases} \\
        d_1 & = & x_0 \quad\text{(nach Soll-Funktionsweise)} \\
        d_1 & = & x_0 \quad\text{(nach Konstruktion)} \\
      \end{eqnarray*}
      \textbf{Induktionsschritt $n \leadsto 2n$:} \\
      Die Korrektheit des $\FDec_n$ sei als Induktionsvoraussetzung gegeben.
      \begin{eqnarray*}
        l[2^n-1:0] & = & \FDec_n(x[n-1:0]) \\
        l_i        & \stackrel{\text{IV}}{=} & \begin{cases}
                                                       0 & \text{für } i \neq \langle x[n-1:0] \rangle \\
                                                       1 & \text{für } i = \langle x[n-1:0] \rangle \\
                                                     \end{cases} \\
        h[2^n-1:0] & = & \FDec_n(x[2n-1:n]) \\
        h_i        & \stackrel{\text{IV}}{=} & \begin{cases}
                                                       0 & \text{für } i \neq \langle x[2n-1:n] \rangle \\
                                                       1 & \text{für } i = \langle x[2n-1:n] \rangle \\
                                                     \end{cases} \\
        l_i \wedge h_j = 1 & \Longleftrightarrow & i = \langle x[n-1:0] \rangle \quad\wedge\quad j = \langle x[2n-1:n] \rangle \\
        d_i = 1 & \Longleftrightarrow & l_{i \text{ mod } 2^n} \quad\wedge\quad h_{i \text{ div } 2^n} = 1 \\
                & \Longleftrightarrow & i \text{ mod } 2^n = \langle x[n-1:0] \rangle \quad\wedge\quad i \text{ div } 2^n = \langle x[2n-1:n] \rangle \\
                &   & \text{daraus sollte folgen, dass} \\
        d_i = 1 & \Longleftrightarrow & i = \langle x[2n-1:0] \rangle \\
                &   & \text{andererseits wissen wir, dass gilt} \\
        i       & = & (i \text{ div } 2^n) \cdot 2^n + (i \text{ mod } 2^n) \\
                & = & (\langle x[2n-1:n] \rangle) \cdot 2^n + (\langle x[n-1:0] \rangle) \\
                & = & \langle x[2n-1:0] \rangle \\
      \end{eqnarray*}
      Somit folgt, dass das $i$-te Ergebnis-Bit des $\FDec_n$ genau dann gleich $1$ ist, wenn $i=\langle x[2n-1:0] \rangle$.
      Dies stimmt mit den geforderten Eigenschaften des Decoders überein. \QED
\item $C(\FDec_1) = 1, \quad C(\FDec_n) = 2 \cdot C(\FDec_\frac{n}{2}) + 2^n$ \\
      \textbf{Behauptung:}
      $$ C(\FDec_n) = n + n \cdot \sum_{k=1}^{\log_2 n} 2^{2^k-k} $$
      \textbf{Induktionsanfang $n=1$:}
      $$ C(\FDec_n) = C(\FDec_1) = 1 \quad\text{(nach Definition)} $$
      $$ C(\FDec_n) = C(\FDec_1) = 1 + 1 \cdot \sum_{k=1}^{\log_2 1} 2^{2^k-k} = 1 + \sum_{k=1}^0 2^{2^k-k} = 1 \quad\text{(nach Behauptung)} $$
      \textbf{Induktionsschritt $n \leadsto 2n$:}
      \begin{eqnarray*}
        C(\FDec_{2n}) & \stackrel{\text{Def}}{=} & 2 \cdot C(\FDec_\frac{2n}{2} ) + 2^{2n} \\
                      & = & 2 \cdot C(\FDec_n) + 2^{2n} \\
                      & \stackrel{\text{Beh}}{=} & 2 \cdot \left( n + n \cdot \sum_{k=1}^{\log_2 n} 2^{2^k-k} \right) + 2^{2n} \\                      
                      & = & 2n + 2n \cdot \left( \sum_{k=1}^{\log_2 n} 2^{2^k-k} \right) + 2^{2n} \\                      
                      & = & 2n + 2n \cdot \left[ \left( \sum_{k=1}^{\log_2(2n)} 2^{2^k-k} \right) - 2^{2^{\log_2(2n)}-\log_2(2n)} \right] + 2^{2n} \\                      
                      & = & 2n + 2n \cdot \left[ \left( \sum_{k=1}^{\log_2(2n)} 2^{2^k-k} \right) - \frac{2^{2^{\log_2(2n)}}}{2^{\log_2(2n)}} \right] + 2^{2n} \\
                      & = & 2n + 2n \cdot \left[ \left( \sum_{k=1}^{\log_2(2n)} 2^{2^k-k} \right) - \frac{2^{2n}}{2n} \right] + 2^{2n} \\
                      & = & 2n + 2n \cdot \left( \sum_{k=1}^{\log_2(2n)} 2^{2^k-k} \right) - 2^{2n} + 2^{2n} \\
                      & = & 2n + 2n \cdot \left( \sum_{k=1}^{\log_2(2n)} 2^{2^k-k} \right) \\
      \end{eqnarray*}
      \QED
\end{enumerate}

\section*{Aufgabe 4}
siehe Anhang (Zeichnungen)

\section*{Aufgabe 5}
Berechne unter der Voraussetzung
\begin{itemize}
  \item dass die Breite der Eingangssignale 32 Bit beträgt und
  \item dass als Addierer ein Conditional Sum Adder verwendet wird
\end{itemize}
die Tiefe des in der Vorlesung vorgestellten ALU-Schaltkreises. \\[1cm]
\begin{enumerate}[(i)]
  \item Betrachte zunächst die Tiefe für den CSA. Für $n=2^k, \: k \in \SetN_{>0}$ gilt
        $$ D(\CSA_1)=D(\FA)=3 $$
        $$ D(\CSA_n)=D(\CSA_\frac{n}{2})+D(\MUX_{\frac{n}{2}+1})=D(\CSA_\frac{n}{2})+3 $$
        Beziehungsweise in geschlossener Form für $n=2^k, \: k \in \SetN$
        $$ D(\CSA_n)= 3 \log_2 n + 3 $$
  \item Betrachte zunächst die für die Addition und Subtraktion zu durchlaufenden Pfade. Die Eingangssignale $a_i$ kommen direkt
        zum CSA, die Eingangssignale $b_i$ müssen jedoch bevor sie zum CSA gelangen, jeweils ein XOR-Gatter durchlaufen (Tiefe $1$).
        Der CSA hat eine Tiefe von $3 \log_2 n + 1 = 3 \log_2 32 + 3 = 3 \cdot 5 + 3 = 18$. Bis zum Endergebnis werden zwei
        MUXe durchlaufen, jeder von diesen hat für sich betrachtet die Tiefe $3$, allerdings entstammen beide Steuerbits dem
        Kommandosignal und sind nicht vom Ergebnis des CSA abhängig. Die erforderlichen Negierungen der Steuersignale im Inneren
        der MUXe können somit für die Tiefenbetrachtung außer Acht gelassen werden, womit sich die Tiefe beider MUXe in dieser
        Betrachtung auf $2$ reduziert (in jedem der MUXe durchläuft jedes Signal jeweils ein AND-Gatter und ein OR-Gatter). 
        Die maximale Gesamttiefe der Addition bzw. Subtraktion beträgt somit $1+18+2+2=23$.
  \item Betrachte jetzt den Logikteil, der für die Operationen $\wedge_{32}, \vee_{32}, \varoplus_{32}$ und $b[15:0] \cdot 2^{16}$ zuständig
        ist. Die Pfade für die Operationen $\wedge_{32}, \vee_{32}$ und $\varoplus_{32}$ sind gleich lang; jedes Bit der Eingangssignale
        durchläuft ein AND-, OR- bzw. XOR-Gatter (Tiefe $1$) und vier MUXe (Tiefe jeweils $2$ nach Vorbetrachtung analog zu Punkt (ii).
        Für die Operation $b[15:0] \cdot 2^{16}$ werden nur vier MUXe durchlaufen, dieser Pfad ist somit kürzer als für die anderen drei
        Operationen und muss somit bei der Betrachtung der maximalen Tiefe der ALU nicht weiter berücksichtigt werden. Die Tiefe der
        Operationen $\wedge_{32}, \vee_{32}$ und $\varoplus_{32}$ beträgt somit $1 + 4 \cdot 4 = 17$.
  \item Betrachte schließlich den Vergleichsteil der ALU, der für die Operationen $0_{32}, >, =, \ge, <, \neq, \le$ und $1_{32}$
        verantwortlich ist. Der Tester erhält drei Signale zero, positive und negative, die aussagen, ob die Differenz $[a]-[b]$
        gleich null, positiv oder negativ ist. Zur Erzeugung dieser Signale ist es erforderlich, die Signale $b_i$ zu invertieren
        (Tiefe $1$) und zusammen mit den unveränderten Signalen $a_i$ in einen CSA zu geben (Tiefe $18$), wobei der Carry-Eingang
        des CSA auf $1$ gesetzt wird. Das Signal negative erhält man, indem man $a_{31}, b_{31}$ und $c_{31}$ per XOR-Gatter verknüpft
        (verschachtelte Anordnung zweier XOR-Gatter, Tiefe $2$). Das Signal zero erhält man, indem man alle Bits der Differenz
        miteinander verodert (zuerst werden mit 16 AND-Gattern jeweils zwei Bits verodert, mit 8 AND-Gattern werden dann jeweils
        zwei der Zwischenergebnisse verodert usw., Tiefe $\log_2 n = 5$) und das Ergebnis anschließend negiert (Tiefe $1$).
        Das Signal positive erhält man, indem man die Signale negative und zero verodert (Tiefe $1$) und anschließend negiert
        (Tiefe $1$). Die größte Tiefe hat damit das Signal positive mit einer Tiefe von $1+18+\max\{2,6\}+1+1=27$.
        Jedes der Signale zero, positive und negative wird mit einem Bit des Kommandobits per AND-Gatter verknüpft
        (Tiefe $1$) und diese Ergebnisse dann per OR-Gatter verknüpft. Dabei ist eine verschachtelte Anordnung der OR-Gatter
        erforderlich, da aber das Signal positive die größte Tiefe hat, wird man es an das untere OR-Gatter anschließen, so dass
        die zusätzliche Tiefe nur $1$ ist. Dieses Ergebnis muss anschließend noch einen MUX (Tiefe 2, Begründung wie oben) durchlaufen.
        Die Gesamttiefe des Vergleichsteils der ALU ist somit $27+1+1+2=31$.
  \item \textbf{Konklusion:}
        Die größte Tiefe hat wie gezeigt des Vergleichsteil mit einer Tiefe von $31$, so dass die Gesamttiefe der ALU $31$ beträgt.
\end{enumerate}

\section*{Aufgabe 6}
\subsubsection*{(a)}
siehe Anhang (Zeichnung) \\
        Ich betrachte im folgenden die binäre Darstellung der Zahlen $a$ und $b$. Ihre besonderen
        Eigenschaften als BCD-Ziffern werden als Voraussetzung berücksichtigt. Nach Voraussetzung gilt
        $$ \langle a \rangle < 10, \quad \langle b \rangle < 10, \quad c \in \{0,1\} $$
        Somit gilt offensichtlich
        $$ \langle s \rangle = \langle a \rangle + \langle b \rangle + c < 20 $$
        Zunächst addieren wir mittels eines $\CSA_4$ beide BCD-Zahlen unter Einbeziehung des Carry-Eingangs binär
        (Tiefe $3 \cdot \log_2 4 + 3 = 3 \cdot 2 + 3 = 9$).
        Dann gilt es zu prüfen, ob das 5 Bit breite Ergebnis größer oder gleich 10 ist. Aus der Darstellung
        $$ \langle s \rangle = 16 \cdot s_4 + 8 \cdot s_3 + 4 \cdot s_2 + 2 \cdot s_1 + s_0 $$
        läßt sich erkennen, dass $\langle s \rangle \ge 10$ genau dann gilt, wenn
        $$ o := s_4 \vee ( s_3 \wedge ( s_2 \vee s_1 ) ) = 1 $$
        Diese Funktion läßt sich durch einen Schaltkreis der Tiefe $3$ berechnen. 
        Ist $o=0$, also $\langle s \rangle < 10$, dann ist das errechnete binäre Ergebnis bereits die gewünschte untere
        BCD-Ziffer. Die zweite, obere BCD-Ziffer setzt sich in diesem Fall einfach binär aus vier Nullen zusammen. Ist hingegen
        $o=1$, also $\langle s \rangle \ge 10$, dann muss das errechnete binäre Ergebnis um 10 vermindert werden, bevor es als
        untere BCD-Ziffer ausgegeben wird. Die zweite BCD-Ziffer setzt sich binär aus drei Nullen gefolgt von einer Eins zusammen.
        Im Schaltkreis wird aus der binären Summe gleichzeitig die um 10 verminderte Summe berechnet. Per Multiplexer
        wird anhand des Overflow-Signals $o$ ausgewählt, welches Ergebnis ausgegeben werden soll.
        Genaue Realisierung des Schaltkreises anhand Zeichnung.

\subsubsection*{(b)}
        Für einen n-Ziffern-BCD-Addierer gilt
        $$ \BCD^{-1}(s) = \underbrace{ \BCD^{-1}(a) }_{ \in \{0,\ldots,10^n-1 \} } +
                          \underbrace{ \BCD^{-1}(b) }_{ \in \{0,\ldots,10^n-1 \} } +
                          \underbrace{ c }_{ \in \{0,1\} } $$
        Somit gilt offensichtlich
        $$ \BCD^{-1}(s) \in \{ 0,\ldots,2 \cdot (10^n-1)+1\} = \{ 0,\ldots,2 \cdot 10^n-1 \} $$
        Das Ergebnis eines n-Ziffern-BCD-Addierers ist per Definition eine $(n+1)$-Ziffern-BCD-Zahl, welche einen
        maximal möglichen Wertebereich von $\{0,\ldots,10^{n+1}-1\}$ hat. Per Definition enthält die $(n+1)$-te
        BCD-Ziffer das Ergebnis der ganzzahligen Division von der Summe $\BCD^{-1}(s)$ durch $10^n$. Da nach obiger
        Betrachtung für die Summe gilt
        $$ \BCD^{-1}(s) < 2 \cdot 10^n $$
        heißt dies für die $(n+1)$-te BCD-Ziffer, dass diese immer kleiner als $2$ sein muss. Eine BCD-Ziffer
        stellt Zahlen aus dem Bereich $\{0,\ldots,9\}$ in Binärkodierung dar. Alle Zahlen $<2$ lassen sich bereits
        mit einem Bit kodieren, so dass automatisch gelten muss
        $$ s_{4n+3} = s_{4n+2} = s_{4n+1} = 0 $$
        Daraus folgt, dass n-Ziffern-BCD-Addierer kaskadierbar sind, indem das niederwertigste Bit der $(n+1)$-ten
        BCD-Ziffer als Carry-In-Bit für den folgenden n-Ziffern-BCD-Addierer verwendet wird. \QED


\end{document}