\documentclass[10pt,a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{thumbpdf}
\usepackage{graphicx}
\usepackage{float}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage[latin1]{inputenc}

\DeclareMathOperator{\CSA}{CSA}
\DeclareMathOperator{\FA}{FA}
\DeclareMathOperator{\FF}{FF}
\DeclareMathOperator{\MUX}{MUX}
\DeclareMathOperator{\Enc}{Enc}
\DeclareMathOperator{\Dec}{Dec}
\DeclareMathOperator{\FDec}{FDec}
\DeclareMathOperator{\BCD}{BCD}
\DeclareMathOperator{\BA}{BA}
\DeclareMathOperator{\PP}{PP}
\DeclareMathOperator{\alu}{alu}
\DeclareMathOperator{\testi}{testi}
\DeclareMathOperator{\shifta}{shifta}
\DeclareMathOperator{\IR}{IR}
\DeclareMathOperator{\CLA}{CLA}


\floatstyle{ruled}
\newfloat{schematic}{htbp}{los}
\floatname{schematic}{Schaltkreis}

\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 Sei $n=2^k$. Somit ist $k=\log_2 n$. \\
        $$ C(\PP_\circ(1)) = 0 $$
        $$ C(\PP_\circ(n)) = C \left( \PP_\circ \left( \frac{n}{2} \right) \right) +(n-1) \cdot C(\circ) $$
        \textbf{Behauptung:}
        \begin{eqnarray*}
          C(\PP_\circ(n)) & = & \left( 2^{k+1} - 2 \right) \cdot C(\circ) - k \cdot C(\circ) \\
                          & = & 2 \cdot 2^k \cdot C(\circ) - 2 \cdot C(\circ) - k \cdot C(\circ) \\
                          & = & 2n \cdot C(\circ) - 2 \cdot C(\circ) - \log_2 n \cdot C(\circ) \\
                          & = & \left( 2n - 2 - \log_2 n \right)  \cdot C(\circ) \\
        \end{eqnarray*}
        \textbf{Beweis:} \\
        Induktionsanfang $n=2^0=1$:
        \begin{eqnarray*}
          C(\PP_\circ(1)) & \stackrel{\text{Def}}{=} & 0 \\
          C(\PP_\circ(1)) & \stackrel{\text{Beh}}{=} & \left( 2 \cdot 1 - 2 - \log_2 1 \right) \cdot C(\circ) = 0 \cdot C(\circ) = 0 \\
        \end{eqnarray*}
        Induktionsvoraussetzung:
        $$ C(\PP_\circ(n)) = C \left( \PP_\circ \left( \frac{n}{2} \right) \right) +(n-1) \cdot C(\circ) $$
        Induktionsschritt $\frac{n}{2} \leadsto n$:
        \begin{eqnarray*}
          C(\PP_\circ(n)) & \stackrel{\text{IV}}{=} & C \left( \PP_\circ \left( \frac{n}{2} \right) \right) +(n-1) \cdot C(\circ) \\
                          & \stackrel{\text{Beh}}{=} & \left( 2 \cdot \frac{n}{2} - 2 - \log_2 \frac{n}{2} \right)  \cdot C(\circ) +(n-1) \cdot C(\circ) \\
                          & = & \left( n - 2 - (\log_2 n - \log_2 2) \right) \cdot C(\circ) +(n-1) \cdot C(\circ) \\
                          & = & \left( n - 2 - \log_2 n + 1 \right) \cdot C(\circ) +(n-1) \cdot C(\circ) \\
                          & = & \left( n - 1 - \log_2 n \right) \cdot C(\circ) +(n-1) \cdot C(\circ) \\
                          & = & \left( 2n - 2 - \log_2 n \right) \cdot C(\circ) \\
        \end{eqnarray*}
        \QED
  \item Sei $n=2^k$. Somit ist $k=\log_2 n$. \\
        $$ D(\PP_\circ(1))=0 $$
        $$ D(\PP_\circ(n)) \le D \left( \PP_\circ \left( \frac{n}{2} \right) \right) +2 \cdot D(\circ) $$
        \textbf{Behauptung:}
        $$ D(\PP_\circ(n)) \le 2 \cdot \log_2 n \cdot D(\circ) $$
        \textbf{Beweis:}
        Induktionsanfang $n=2^0=1$:
        \begin{eqnarray*}
          D(\PP_\circ(1)) & \stackrel{\text{Def}}{=} & 0 \\
          D(\PP_\circ(1)) & \stackrel{\text{Beh}}{\le} & 2 \cdot \log_2 1 \cdot D(\circ) = 2 \cdot 0 \cdot D(\circ) = 0 \\
          D(\PP_\circ(1)) & \stackrel{\text{Beh}}{=} & 0 \quad \text{da} \quad D(\PP_\circ(n)) \in \SetN \\
        \end{eqnarray*}
        Induktionsvoraussetzung:
        $$ D(\PP_\circ(n)) \le D \left( \PP_\circ \left( \frac{n}{2} \right) \right) +2 \cdot D(\circ) $$
        Induktionsschritt $\frac{n}{2} \leadsto n$:
        \begin{eqnarray*}
          D(\PP_\circ(n)) & \stackrel{\text{IV}}{\le} & D \left( \PP_\circ \left( \frac{n}{2} \right) \right) +2 \cdot D(\circ) \\
                          & \stackrel{\text{Beh}}{\le} & 2 \cdot \log_2 \frac{n}{2} \cdot D(\circ) +2 \cdot D(\circ) \\
                          & \le & 2 \cdot \left( \log_2 n - \log_2 2 \right) \cdot D(\circ) +2 \cdot D(\circ) \\
                          & \le & 2 \cdot \left( \log_2 n - 1 \right) \cdot D(\circ) +2 \cdot D(\circ) \\
                          & \le & \left( 2 \cdot \log_2 n - 2 + 2 \right) \cdot D(\circ) \\
                          & \le & 2 \cdot \log_2 n \cdot D(\circ) \\
        \end{eqnarray*}
        \QED
\end{enumerate}

\section*{Aufgabe 2}
\begin{enumerate}[(a)]
  \item Die Addition
        $$ \langle s \rangle = \langle a \rangle + \langle b \rangle + c_{-1} $$
        läßt sich zerlegen in
        $$ \langle c_{i-1}, s[i-1:0] \rangle = \langle a[i-1:0] \rangle + \langle b[i-1:0] \rangle + c_{-1} $$
        $$ \langle c_n, s[n-1:i] \rangle = \langle a[n-1:i] \rangle + \langle b[n-1:i] \rangle + c_{i-1} $$
        Letztere läßt sich wiederrum zerlegen in
        $$ \langle c_j, s[j:i] \rangle = \langle a[j:i] \rangle + \langle b[j:i] \rangle + c_{i-1} \quad\quad (*) $$
        $$ \langle c_n, s[n-1:j+1] \rangle = \langle a[n-1:j+1] \rangle + \langle b[n-1:j+1] \rangle + c_j $$
        Vorausgesetzt sei
        $$ p_{j,i}=1 $$
        Daraus folgt nach Definition
        $$ \langle a[j:i] \rangle + \langle b[j:i] \rangle = \langle 1^{j-i+1} \rangle $$
        Einsetzen in $(*)$ ergibt
        $$ \langle c_j, s[j:i] \rangle = \langle 1^{j-i+1} \rangle + c_{i-1} $$
        $$ c_j \cdot 2^{j-i+1} + \left( \sum_{k=i}^j s_k \cdot 2^{k-i} \right) = \left( \sum_{k=0}^{(j-i+1)-1} 2^k \right) + c_{i-1} $$
        $$ c_j \cdot 2^{j-i+1} + \left( \sum_{k=i}^j s_k \cdot 2^{k-i} \right) = \left( 2^{j-i+1} - 1 \right) + c_{i-1} $$
        Unterscheide zwei mögliche Fälle für $c_{i-1} \in \{0,1\}$.
        \begin{itemize}
          \item Sei zunächst $c_{i-1}=0$. Dann gilt
                $$ c_j \cdot 2^{j-i+1} + \left( \sum_{k=i}^j s_k \cdot 2^{k-i} \right) = 2^{j-i+1} - 1 $$
                $$ \Longleftrightarrow \quad c_j=0 \wedge s_k=1 \quad \forall k: i \le k \le j \quad \text{da } c_j, s_k \in \{0,1\} $$
                In diesem Fall gilt also $c_j=c_{i-1}$.
          \item Sei andererseits $c_{i-1}=1$. Dann gilt
                $$ c_j \cdot 2^{j-i+1} + \left( \sum_{k=i}^j s_k \cdot 2^{k-i} \right) = 2^{j-i+1} $$
                $$ \Longleftrightarrow \quad c_j=1 \wedge s_k=0 \quad \forall k: i \le k \le j \quad \text{da } c_j, s_k \in \{0,1\} $$
                In diesem Fall gilt also ebenfalls $c_j=c_{i-1}$.
        \end{itemize}
        \QED
  \item Vorausgesetzt sei
        $$ g_{j,i}=1 $$
        Daraus folgt nach Definition
        $$ \langle a[j:i] \rangle + \langle b[j:i] \rangle > \langle 1^{j-i+1} \rangle $$
        Einsetzen in $(*)$ aus Aufgabe 2a ergibt
        $$ \langle c_j, s[j:i] \rangle > \langle 1^{j-i+1} \rangle + c_{i-1} $$
        $$ c_j \cdot 2^{j-i+1} + \left( \sum_{k=i}^j s_k \cdot 2^{k-i} \right) > \left( \sum_{k=0}^{(j-i+1)-1} 2^k \right) + c_{i-1} $$
        $$ c_j \cdot 2^{j-i+1} + \left( \sum_{k=i}^j s_k \cdot 2^{k-i} \right) > \left( 2^{j-i+1} - 1 \right) + c_{i-1} $$
        Da $c_{i-1} \in \{0,1\}$ muss unabhängig von $c_{i-1}$ in jedem Fall gelten
        $$ c_j \cdot 2^{j-i+1} + \left( \sum_{k=i}^j s_k \cdot 2^{k-i} \right) > 2^{j-i+1} - 1 $$
        $$ c_j \cdot 2^{j-i+1} + \left( \sum_{k=i}^j s_k \cdot 2^{k-i} \right) \ge 2^{j-i+1} $$
        $$ \Longrightarrow \quad c_j=1 \quad \text{da } c_j, s_k \in \{0,1\} $$
        \QED  
  \item Siehe Schaltkreis 1 auf Seite \pageref{schematic2c}.
  \item Siehe Schaltkreis 2 auf Seite \pageref{schematic2d}.
  \item Seien
        $$ g_2 = g_{j,k}, \quad p_2 = p_{j,k}, \quad g_1 = g_{k-1,i}, \quad p_1 = p_{k-1,i} \quad \text{mit } i < k \le j $$
        \textbf{Zu zeigen:}
        $$ g_{j,i} = g_2 \vee \left( g_1 \wedge p_2 \right) $$
        \textbf{Beweis:}
        \begin{eqnarray*}
          g_{j,i} & \stackrel{!}{=} & g_2 \vee \left( g_1 \wedge p_2 \right) \\
                  & = & g_{j,k} \vee \left( g_{k-1,i} \wedge p_{j,k} \right) \\
        \end{eqnarray*}
        \begin{eqnarray*}
          g_{j,i}=1 & \Longleftrightarrow & g_{j,k}=1 \quad \vee \quad \Big( g_{k-1,i} \quad\wedge\quad p_{j,k} \Big) = 1 \\
                    & \Longleftrightarrow & g_{j,k}=1 \quad \vee \quad \Big( g_{k-1,i}=1 \quad\wedge\quad p_{j,k}=1 \Big) \\
                    & \Longleftrightarrow & \langle a[j:k] \rangle + \langle b[j:k] \rangle > \langle 1^{j-k+1} \rangle \quad \vee \\
                    & & \Big( \langle a[k-1:i] \rangle + \langle b[k-1:i] \rangle > \langle 1^{k-i} \rangle \;\wedge\; \langle a[j:k] \rangle + \langle b[j:k] \rangle = \langle 1^{j-k+1} \rangle \Big) \\
                    & \Longleftrightarrow & \langle a[j:k] \rangle + \langle b[j:k] \rangle > \langle 1^{j-k+1} \rangle \quad \vee \\
                    & & \Big( \langle a[k-1:i] \rangle + \langle b[k-1:i] \rangle > \langle 1^{k-i} \rangle \;\wedge\; 2^{k-i} \cdot \left( \langle a[j:k] \rangle + \langle b[j:k] \rangle \right) = 2^{k-i} \cdot \langle 1^{j-k+1} \rangle \Big) \\
                    & \Longleftrightarrow & \langle a[j:k] \rangle + \langle b[j:k] \rangle > \langle 1^{j-k+1} \rangle \quad \vee \\
                    & & \langle a[j:i] \rangle + \langle b[j:i] \rangle > \langle 1^{k-i} \rangle + 2^{k-i} \cdot \langle 1^{j-k+1} \rangle \\
                    & \Longleftrightarrow & \langle a[j:k] \rangle + \langle b[j:k] \rangle > \langle 1^{j-k+1} \rangle \quad \vee \\
                    & & \langle a[j:i] \rangle + \langle b[j:i] \rangle > \langle 1^{j-i+1} \rangle \\
                    & \stackrel{???}{\Longleftrightarrow} & \langle a[j:i] \rangle + \langle b[j:i] \rangle > \langle 1^{j-i+1} \rangle \quad \vee \\
                    & & \langle a[j:i] \rangle + \langle b[j:i] \rangle > \langle 1^{j-i+1} \rangle \\
                    & \Longleftrightarrow & \langle a[j:i] \rangle + \langle b[j:i] \rangle > \langle 1^{j-i+1} \rangle \\
                    & \Longleftrightarrow & g_{j,i}=1 \\
        \end{eqnarray*}
        \QED \\
        \textbf{Zu zeigen:}
        $$ p_{j,i} = p_2 \wedge p_1 $$
        \textbf{Beweis:}
        \begin{eqnarray*}
          p_{j,i} & \stackrel{!}{=} & p_2 \wedge p_1 \\
                  & = & p_{j,k} \wedge p_{k-1,i} \\
        \end{eqnarray*}
        \begin{eqnarray*}
          p_{j,i}=1 & \Longleftrightarrow & p_{j,k}=1 \quad\wedge\quad p_{k-1,i}=1 \\
                    & \Longleftrightarrow & \langle a[j:k] \rangle + \langle b[j:k] \rangle = \langle 1^{j-k+1} \rangle \quad\wedge\quad \langle a[k-1:i] \rangle + \langle b[k-1:i] \rangle = \langle 1^{k-i} \rangle \\
                    & \Longleftrightarrow & 2^{k-i} \cdot \langle a[j:k] \rangle + 2^{k-i} \cdot \langle b[j:k] \rangle = 2^{k-i} \cdot \langle 1^{j-k+1} \rangle \quad\wedge \\
                    & & \langle a[k-1:i] \rangle + \langle b[k-1:i] \rangle = \langle 1^{k-i} \rangle \\
                    & \Longleftrightarrow & 2^{k-i} \cdot \langle a[j:k] \rangle + \langle a[k-1:i] \rangle + 2^{k-i} \cdot \langle b[j:k] \rangle + \langle b[k-1:i] \rangle = \\
                    & & 2^{k-i} \cdot \langle 1^{j-k+1} \rangle + \langle 1^{k-i} \rangle \\
                    & \Longleftrightarrow & \langle a[j:i] \rangle + \langle b[j:i] \rangle = \langle 1^{j-k+1}, 0^{k-i} \rangle + \langle 1^{k-i} \rangle \\
                    & \Longleftrightarrow & \langle a[j:i] \rangle + \langle b[j:i] \rangle = \langle 1^{j-i+1} \rangle \\
                    & \Longleftrightarrow & p_{j,i}=1 \\
        \end{eqnarray*}
        \QED
  \item Gegeben sei die Funktion
        $$ \circ : \{0,1\}^2 \times \{0,1\}^2 \rightarrow \{0,1\}^2 $$
        $$ (g_2,p_2) \circ (g_1,p_1) := \left( g_2 \vee (g_1 \wedge p_2), p_2 \wedge p_1 \right) $$
        Die Funktion $\circ$ so assoziativ sein, es muss also gelten
        $$ ((a,b) \circ (c,d)) \circ (e,f) = (a,b) \circ ((c,d) \circ (e,f)) $$
        \textbf{Beweis:}
        \begin{eqnarray*}
                ((a,b) \circ (c,d)) \circ (e,f)
          & = & (a \vee (c \wedge b),b \wedge d) \circ (e,f) \\
          & = & ((a \vee (c \wedge b)) \vee (e \wedge (b \wedge d)),(b \wedge d) \wedge f) \\
          & = & ((a \vee (c \wedge b)) \vee (e \wedge (b \wedge d)),(b \wedge d) \wedge f) \\
          & = & ((a \vee (c \wedge b)) \vee (e \wedge (b \wedge d)),b \wedge d \wedge f) \\
          & = & ((a \vee (c \wedge b)) \vee (e \wedge (b \wedge d)),b \wedge (d \wedge f)) \\
          & = & (a \vee (c \wedge b) \vee (e \wedge d \wedge b),b \wedge (d \wedge f)) \\
          & = & (a \vee (c \wedge b) \vee ((e \wedge d) \wedge b),b \wedge (d \wedge f)) \\
          & = & (a \vee ((c \vee (e \wedge d)) \wedge b),b \wedge (d \wedge f)) \\
          & = & (a,b) \circ (c \vee (e \wedge d),d \wedge f) \\
          & = & (a,b) \circ ((c,d) \circ (e,f)) \\
        \end{eqnarray*}
        \QED
  \item \textbf{Zu zeigen:}
        $$ g_{i,0} = c_i \quad \text{für } 0 \le i \le n-1 $$
        \textbf{Beweis:}
        \begin{eqnarray*}
          g_{i,0}=1 & \Longleftrightarrow & \langle a[i:0] \rangle + \langle b[i:0] \rangle + c_{-1} > \langle 1^{i+1} \rangle \\
          & \Longleftrightarrow & \langle a[i:0] \rangle + \langle b[i:0] \rangle + c_{-1} \ge 2^{i+1} \\
          \langle c_i, s[i:0] \rangle & = & \langle a[i:0] \rangle + \langle b[i:0] \rangle + c_{-1} \\
          \langle c_i, s[i:0] \rangle & \ge & 2^{i+1} \\
          & \Longleftrightarrow & c_i = 1 \quad \text{da } \max(s[i:0])=2^{i+1}-1 \\
        \end{eqnarray*}
        \QED
  \item Seien alle Carrybits $c_i$ der Addition $\langle s \rangle = \langle a \rangle + \langle b \rangle$ bekannt. Die Operation
        eines Volladdierers ist wie folgt definiert:
        $$ \langle c_i, s_i \rangle = a_i + b_i + c_{i-1} $$
        Da vorausgesetzt ist, dass die Carrybits bereits bekannt sind, wollen wir $c_i$ nicht erneut berechnen, sondern nur $s_i$.
        Somit setzen wir:
        $$ \langle s_i \rangle = a_i + b_i + c_{i-1} \mod 2 $$
        Das $i$-te Bit der Summe läßt sich somit trivialerweise durch den boole'schen Ausdruck
        $$ s_i = \left( a_i \varoplus b_i \right) \varoplus c_{i-1} $$
        berechnen. Dieser Ausdruck läßt sich mit einem Schaltkreis der Tiefe 2 und Kosten 2 darstellen. Die Berechnung eines
        Summenbits ist offensichtlich nicht von der Berechnung der anderen Summenbits abhängig, so dass die Gesamtkosten für
        einen $n$-Bit-Addierer $2n$ betragen (das Bit $s_n$ der $(n+1)$ Bit breiten Summe ist gleich dem letzten Carrybit $c_{n-1}$
        und nach Voraussetzng bereits bekannt) und die Gesamttiefe $2$ ist. Beweis des obigen boole'schen Ausdrucks durch
        Wertetabelle:
        $$ \begin{array}{c|c|c||c|c||c|c}
          c_{i-1} & a_i & b_i & \langle c_i, s_i \rangle & \langle s_i \rangle & a_i \varoplus b_i & (a_i \varoplus b_i) \varoplus c_{i-1} \\ \hline \hline
          0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
          0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline
          0 & 1 & 0 & 1 & 1 & 1 & 1 \\ \hline
          0 & 1 & 1 & 2 & 0 & 0 & 0 \\ \hline
          1 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline
          1 & 0 & 1 & 2 & 0 & 1 & 0 \\ \hline
          1 & 1 & 0 & 2 & 0 & 1 & 0 \\ \hline
          1 & 1 & 1 & 3 & 1 & 0 & 1 \\
        \end{array} $$
        \QED
  \item Siehe Schaltkreis 3 auf Seite \pageref{schematic2i}.
        Unterschaltkreise ,,2c`` und ,,2d`` wie in der entsprechenden Aufgabe deklariert.
        Unterschaltkreis ,,$\PP_\circ(n)$`` wie auf dem 7. Übungsblatt deklariert.
  \item $$ C(\CLA_n) = 10n - 3 \log_2 n - 4 $$
  \item $$ D(\CLA_n) = 4 \log_2 n + 5 $$
\end{enumerate}

\begin{schematic}
  \label{schematic2c}
  \includegraphics[width=30.5mm]{info2_8_aufg2c}
  \caption{Aufgabe 2c}
\end{schematic}
        
\begin{schematic}
  \label{schematic2d}
  \includegraphics[width=40.5mm]{info2_8_aufg2d}
  \caption{Aufgabe 2d}
\end{schematic}
        
\begin{schematic}
  \label{schematic2i}
  \includegraphics[width=120mm]{info2_8_aufg2i}
  \caption{Aufgabe 2i}
\end{schematic}

\section*{Aufgabe 3}
Aus der Konstruktion für Encoder und Decoder ergibt sich
\begin{eqnarray*}
  C(\Enc_1) = 0 & & C(\Enc_n) = 2 \cdot C(\Enc_{n-1}) + n \\
  C(\Dec_1) = 1 & & C(\Dec_n) = C(\Dec_{n-1}) + 3 \\
\end{eqnarray*}
Da $x \in \{0,1\}^{32}$ und $x_i=1$ für genau ein $i \in \{0,\ldots,31\}$, benötigen wir einen $n=\log_2 32=5$ Bit Encoder und Decoder.
Für die Kosten der beiden Schaltkreise ergibt sich
$$ C(\Enc_5) = 41 $$
$$ C(\Dec_5) = 13 $$
Die Kosten der Konstruktion mit Encoder und Decoder sollen geringer sein als die Kosten ohne. Ohne Encoder und Decoder werden exakt
32 Flipflops benötigt, mit jedoch nur $\log_2 32=5$ Flipflops. Es soll also gelten
\begin{eqnarray*}
  32 \cdot C(\FF) & > & C(\Enc_5)+C(\Dec_5)+5 \cdot C(\FF) \\
  \Longleftrightarrow \quad 27 \cdot C(\FF) & > & C(\Enc_5)+C(\Dec_5) \\
  \Longleftrightarrow \quad C(\FF) & > & \frac{C(\Enc_5)+C(\Dec_5)}{27} \\
  \Longleftrightarrow \quad C(\FF) & > & \frac{41+13}{27} \\
  \Longleftrightarrow \quad C(\FF) & > & \frac{54}{27} \\
  \Longleftrightarrow \quad C(\FF) & > & 2 \\
\end{eqnarray*}
Die Kosten für ein Flipflop müssen größer $2$ sein, damit sich diese Konstruktion lohnt, also die Gesamtkosten mittels dieser
Konstruktion gesenkt werden können. Sind die Kosten für ein Flipflop gleich $2$, bleiben die Gesamtkosten gleich.


\end{document}