\documentclass[12pt,a4paper]{article}

\usepackage{amstext}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{pstricks}
\usepackage{pst-plot}
\usepackage{gastex}
%\usepackage{ngerman}
\usepackage{wasysym}
\usepackage{rotating}

\title{\textsc{Embedded Systems \\ \large Assignment 9}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \and \shortstack[c]{Pascal Gwosdek\\ \scriptsize 2505221}}
\date{}

\pagestyle{fancy}

\lhead{Assignment 9}
\chead{}
\rhead{Dithmar (2031259), Gwosdek (2505221)}
\lfoot{Embedded Systems}
\cfoot{Page \thepage}
\rfoot{SS 2007}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\exercise}[1]{\subsection{#1}}
\renewcommand{\theenumi}{\textbf{\alph{enumi}}}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\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}[2]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[#1]{#2}\\[0.2cm]
	\end{figure}
	}

\newcommand{\m}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\+}{\phantom{-}}
\newcommand{\f}{\frac}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}
\setcounter{section}{9}

\exercise{Scheduling}
First of all, we give the set of tasks by using $d_i$ instead of $D_i$: \\
\begin{center}
\begin{tabular}{c|cccc}
& $J_1$ & $J_2$ & $J_3$ & $J_4$ \\
\hline
$a_i$ & 0 & 4 & 2 & 6 \\
$C_i$ & 6 & 2 & 4 & 2 \\
$d_i$ & 18 & 8 & 9 & 10
\end{tabular}
\end{center}
Now we state the tree by using this set of tasks: \\[0.3cm]
\begin{picture}(158,125)(0,-125)
\node[NLangle=0.0](n0)(39.67,-32.15){$J_1$}

\node[NLangle=0.0](n1)(75.69,-32.15){$J_2$}

\node[NLangle=0.0](n2)(115.96,-32.15){$J_3$}

\node[NLangle=0.0](n3)(15.67,-60.15){$J_2$}

\node[NLangle=0.0](n4)(35.67,-60.15){$J_3$}

\node[NLangle=0.0](n5)(55.67,-60.15){$J_4$}

\node(n6)(95.67,-4.15){}

\drawedge[ELpos=85,ELdist=-3.5](n6,n0){6}

\drawedge[ELpos=75,ELdist=-3.0](n6,n1){6}

\drawedge[ELpos=85,ELdist=2.5](n6,n2){6}

\drawedge[ELpos=75,ELdist=-3.5](n0,n3){8}

\drawedge[ELpos=75,ELdist=-5.0](n0,n4){10}

\drawedge[ELpos=75,ELdist=2.0](n0,n5){8}

\node[NLangle=0.0](n7)(95.96,-60.15){$J_1$}

\node[NLangle=0.0](n8)(131.9,-60.15){$J_2$}

\node[NLangle=0.0](n9)(119.96,-88.15){$J_1$}

\node[NLangle=0.0](n10)(143.96,-88.15){$J_4$}

\node[NLangle=0.0](n11)(143.96,-116.15){$J_1$}

\drawedge[ELpos=80,ELdist=-5.5](n2,n7){12}

\drawedge[ELpos=75,ELdist=2.5](n2,n8){8}

\drawedge[ELpos=75,ELdist=-5.5](n8,n9){14}

\drawedge[ELpos=75,ELdist=3.5](n8,n10){10}

\drawedge[ELpos=75,ELdist=3.5](n10,n11){16}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n12)(75.75,-40.15){\lightning}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n13)(75.75,-48.15){$J_3$}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n14)(15.67,-68.15){\lightning}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n16)(15.67,-76.15){$J_3$}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n18)(35.67,-68.15){\lightning}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n19)(35.67,-76.15){$J_3$}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n20)(55.67,-68.15){\lightning}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n21)(55.67,-76.15){$J_2$}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n22)(95.96,-68.15){\lightning}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n24)(95.96,-75.88){$J_2$}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n25)(119.96,-96.15){\lightning}

\node[NLangle=0.0,Nw=0.0,Nh=0.0,Nmr=0.0](n26)(119.96,-104.15){$J_4$}
\end{picture}

\newpage
\exercise{Scheduling}
\begin{enumerate}
\item
\begin{enumerate}[1.]
\item In the first step, we have to \textit{modify the activation times}. Using the algorithm gives the following:
\begin{itemize}
\item $a_A^* = a_A = 0$
\item selecting task $B$.
\item
\begin{eqnarray*}
a_B^* & = & max(\{a_H^* + C_H | H \to B\} \cup {a_B}) \\
& = & max(\{a_A^* + C_A\} \cup \{a_B\}) \\
& = & max(\{2,0\}) \\
a_B^* & = & 2
\end{eqnarray*}
\item selecting task $C$.
\item
\begin{eqnarray*}
a_C^* & = & max(\{a_H^* + C_H | H \to C\} \cup \{a_C\}) \\
& = & max(\{2,5,0\}) \\
a_C^* & = & 5
\end{eqnarray*}
\item selecting task $D$.
\item
\begin{eqnarray*}
a_D^* & = & max(\{a_H^* + C_H | H \to D\} \cup \{a_D\}) \\
& = & max(\{2,5,8,0\}) \\
a_D^* & = & 8
\end{eqnarray*}
\item selecting task $E$.
\item
\begin{eqnarray*}
a_E^* & = & max(\{a_H^* + C_H | H \to E\} \cup \{a_E\}) \\
& = & max(\{2,5,8,13,0\}) \\
a_E^* & = & 13
\end{eqnarray*}
\item selecting task $F$.
\item
\begin{eqnarray*}
a_F^* & = & max(\{a_H^* + C_H | H \to F\} \cup \{a_F\}) \\
& = & max(\{2,5,8,13,14,0\}) \\
a_F^* & = & 14
\end{eqnarray*}
\item selecting task $G$.
\item
\begin{eqnarray*}
a_G^* & = & max(\{a_H^* + C_H | H \to G\} \cup \{a_G\}) \\
& = & max(\{2,5,8,13,14,19,0\}) \\
a_G^* & = & 19
\end{eqnarray*}
\end{itemize}
\item In the second step, we have to \textit{modify the deadlines}. Using the algorithm, we get the following:
\begin{itemize}
\item $d_G^* = d_G = 25$ \\
$d_G = 25$ since $d_G = a_G + D_G = 0 + 25 = 25$.
\item selecting task $F$.
\item
\begin{eqnarray*}
d_F^* & = & min(\{d_H^* - C_H | F \to H\} \cup \{d_F\}) \\
& = & min(\{d_G^* - C_G\} \cup \{d_F\}) \\
& = & min(\{20,25\}) \\
d_F^* & = & 20
\end{eqnarray*}
\item selecting task $E$.
\item
\begin{eqnarray*}
d_E^* & = & min(\{d_H^* - C_H | E \to H\} \cup \{d_E\}) \\
& = & min(\{18,20,25\}) \\
d_E^* & = & 18
\end{eqnarray*}
\item selecting task $D$.
\item
\begin{eqnarray*}
d_D^* & = & min(\{d_H^* - C_H | D \to H\} \cup \{d_D\}) \\
& = & min(\{17,18,20,25\}) \\
d_D^* & = & 17
\end{eqnarray*}
\item selecting task $C$.
\item
\begin{eqnarray*}
d_C^* & = & min(\{d_H^* - C_H | C \to H\} \cup \{d_C\}) \\
& = & min(\{12,17,18,20,25\}) \\
d_C^* & = & 12
\end{eqnarray*}
\item selecting task $B$.
\item
\begin{eqnarray*}
d_B^* & = & min(\{d_H^* - C_H | B \to H\} \cup \{d_B\}) \\
& = & min(\{9,12,17,18,20,25\}) \\
d_B^* & = & 9
\end{eqnarray*}
\item selecting task $A$.
\item
\begin{eqnarray*}
d_A^* & = & min(\{d_H^* - C_H | A \to H\} \cup \{d_A\}) \\
& = & min(\{6,9,12,17,18,20,25\}) \\
d_A^* & = & 6
\end{eqnarray*}
\end{itemize}
We now have a new task set $\mathcal{J}^*$, which looks like this: \\
\begin{center}
\begin{tabular}{c|ccccccc}
& $A$ & $B$ & $C$ & $D$ & $E$ & $F$ & $G$ \\
\hline
$a_i^*$ & 0 & 2 & 5 & 8 & 13 & 14 & 19 \\
$C_i$ & 2 & 3 & 3 & 5 & 1 & 2 & 5 \\
$d_i^*$ & 6 & 9 & 12 & 17 & 18 & 20 & 25
\end{tabular}
\end{center}
\end{enumerate}
\item We use the results from the previous exercise to run EDF, obtaining an EDF-schedule for $\mathcal{J}^*$: \\
(the schedule is depicted on the next page) \\
\scalebox{0.8}{\rotatebox{90}{
%A
\begin{pspicture}(-1,0)(25,0)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(25,0)
\put(-1,0){A}
\psline{->}(0,0)(0,1)
\psline{->}(6,1)(6,0)
\psframe[fillstyle=vlines](0,0)(3,0.5)
\end{pspicture}
}}
\scalebox{0.8}{\rotatebox{90}{
%B
\begin{pspicture}(-1,0)(25,2)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(25,0)
\put(-1,0){B}
\psline{->}(2,0)(2,1)
\psline{->}(9,1)(9,0)
\psframe[fillstyle=vlines](2,0)(5,0.5)
\end{pspicture}
}}
\scalebox{0.8}{\rotatebox{90}{
%C
\begin{pspicture}(-1,0)(25,2)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(25,0)
\put(-1,0){C}
\psline{->}(5,0)(5,1)
\psline{->}(12,1)(12,0)
\psframe[fillstyle=vlines](5,0)(8,0.5)
\end{pspicture}
}}
\scalebox{0.8}{\rotatebox{90}{
%D
\begin{pspicture}(-1,0)(25,2)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(25,0)
\put(-1,0){D}
\psline{->}(8,0)(8,1)
\psline{->}(17,1)(17,0)
\psframe[fillstyle=vlines](8,0)(13,0.5)
\end{pspicture}
}}
\scalebox{0.8}{\rotatebox{90}{
%E
\begin{pspicture}(-1,0)(25,2)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(25,0)
\put(-1,0){E}
\psline{->}(13,0)(13,1)
\psline{->}(18,1)(18,0)
\psframe[fillstyle=vlines](13,0)(14,0.5)
\end{pspicture}
}}
\scalebox{0.8}{\rotatebox{90}{
%F
\begin{pspicture}(-1,0)(25,2)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(25,0)
\put(-1,0){F}
\psline{->}(14,0)(14,1)
\psline{->}(20,1)(20,0)
\psframe[fillstyle=vlines](14,0)(16,0.5)
\end{pspicture}
}}
\scalebox{0.8}{\rotatebox{90}{
%G
\begin{pspicture}(-1,0)(25,2)
\psaxes[tickstyle=bottom,labelsep=-17pt]{-}(25,0)
\put(-1,0){G}
\psline{->}(19,0)(19,1)
\psline{->}(25,1)(25,0)
\psframe[fillstyle=vlines](19,0)(24,0.5)
\end{pspicture}
}}
\end{enumerate}

\exercise{Fault tree analysis}
\begin{enumerate}
\item
\begin{itemize}
\item Determine formula of the fault tree:
$$fault = ((C \OR E) \AND A) \OR (B \AND (A \OR (D \AND \neg E)))$$
\item Get DNF of fault:
\begin{eqnarray*}
((C \OR E) \AND A) & \OR & (B \AND (A \OR (D \AND \neg E))) \\
= (C \AND A) \OR (E \AND A) & \OR & (B \AND A) \OR (B \AND D \AND \neg E)
\end{eqnarray*}
\item Minimize: \\
The term is already minimal (wrt. the DNF). The prime implicants are:
\begin{itemize}
\item $(C \AND A)$: "Hauptrechner fails and this is not recognized"
\item $(E \AND A)$: "Hauptrechner fails and the switch does not trigger the Fehlererkennung"
\item $(B \AND A)$: "Both Hauptrechner and Reserverechner fail"
\item $(B \AND D \AND \neg E)$: "'false positive'. Reserverechner fails, Hauptrechner is said to have failed and the switch triggers Fehlererkennung"
\end{itemize}
\end{itemize}
\item We can immediately compute the probability of a prime implicant to occur:
\begin{eqnarray*}
P(C \AND A) & \stackrel{ind.}{=} & P(C) \cdot P(A) = 0.006 \cdot 0.1 = 0.0006 \\[0.3cm]
P(E \AND A) & \stackrel{ind.}{=} & P(E) \cdot P(A) = 0.05 \cdot 0.1 = 0.005 \\[0.3cm]
P(B \AND A) & \stackrel{ind.}{=} & P(B) \cdot P(A) = 0.1 \cdot 0.1 = 0.01 \\[0.3cm]
P(B \AND D \AND \neg E) & \stackrel{ind.}{=} & P(B) \cdot P(D) \cdot P(\neg E) \\
& = & P(B) \cdot P(D) \cdot (1-P(E)) \\
& = & 0.1 \cdot 0.02 \cdot (1-0.05) = 0.002 \cdot 0.95 = 0.0019
\end{eqnarray*}
$\Longrightarrow$ The lower bound of reliability if $(1-0.01) = 0.99 = 99\%$
\end{enumerate}

\end{document}
