\documentclass[11pt,a4paper]{scrartcl}
\usepackage[a4paper,left=1.5cm,right=3.0cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage[ngerman]{babel}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathrsfs}
\usepackage{scrextend}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{tikz-qtree}
\usepackage{mathtools}
\usepackage{latexsym}
\usepackage{algorithmicx}
\usepackage{csquotes}
\usepackage{pdfpages}
\usepackage{pgfplots}
\usepackage{hyperref}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usetikzlibrary{arrows.meta}

\newcommand{\siehe}[1]{\marginpar{\footnotesize \textit{#1}}}

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]

%Kann man in Formeln verwenden
\newcommand*{\bps}{\frac{\text{b}}{\text{s}}}
\newcommand*{\kbps}{\frac{\text{Kb}}{\text{s}}}
\newcommand*{\mbps}{\frac{\text{Mb}}{\text{s}}}
\newcommand*{\gbps}{\frac{\text{Gb}}{\text{s}}}
\newcommand*{\tbps}{\frac{\text{Tb}}{\text{s}}}

\title{Merkzettel für die Klausur}
\author{Marco Ammon, Julia Hindel}
\date{18. September 2018}

\begin{document}
\maketitle
\section*{Paketverzögerung}
\begin{enumerate}  
	\item Bitrate $R$ in $\bps$
	\item Paketgröße $L$ in Bit
	\item Ausbreitungsverzögerung  $D = \frac{l}{v}$, wobei $l$ die Länge der Verbindung und $v$ die Signalausbreitungsgeschwindigkeit ist
	\item Kanalpuffergröße in Bit: $R\cdot D = R \cdot \frac{l}{v} = \frac {\frac{l}{v}}{\frac{1}{R}}$\\
	 $\Longrightarrow$ Anzahl der gesendeten Bits während 1. Bit sich vom Sender zum Empfänger ausbreitet \siehe{Einführung, 21}
	\begin{enumerate}
		\item $RD > 1$:
		\begin{enumerate}
			\item $t = D$: erstes Bit erreicht Empfänger, $R\cdot D$ Bits versendet
		\end{enumerate}
		\item  $RD < 1$:
		\begin{enumerate} 
			\item $t = D$: Anfang des Bits empfangen, $R\cdot D \cdot 100 \%$ des Bits versendet
	  		\item $t= \frac{1}{R}$ : Bit komplett gesendet 
	 		\item $t=\frac{1}{R} + D$ : Bit komplett empfangen
		\end{enumerate} 
	
	\end{enumerate}  
	\item Kanalpuffergröße in Paketen $a = \frac{R\cdot D}{L} = \frac {\frac{l}{v}}{\frac{L}{R}}$
	\item Sendezeit leitungsverb. : $R_\text{eff} = \frac{R}{x}$ mit $x$ den Slots pro Sekunde/Frequenz
	
	\item Paketverzögerung: \siehe{Übung 1, 11\\ Übung 2, 2}	
	\begin{align*}
		d &= \underbrace{d_{trans}}_{\text{Übertragung, Bits auf Link},\frac{L}{R}} + \underbrace{d_{prop}}_{\text{Ausbreitung im Medium} \frac{l}{v}}\\
		&+ \underbrace{d_{proc}}_\text{Verarbeitung (Bitfehler, Links bestimmen)} + \underbrace{d_{queue}}_\text{Warteschlange (Wartezeit auf Link)}
	\end{align*}
	
    \item Paketverzögerung mit mehreren Links: \siehe{Übung 2.6}
	 \begin{align*}
	 \left(\sum \limits_{i=1}^E {d_{trans_i} + d_{prop_i} + d_{proc_i} + d_{queue_i}} \right) + d_{proc}
	 \end{align*}
	 
	 \item Übertragung in Paketen über mehrere Links: \siehe{Übung 1, 25}
	 \begin{equation*}
	 d_{trans} = n_{links} \cdot \frac{L}{R} + (n_{pakete} -1) \cdot \frac{L}{R}
	 \end{equation*}
	 (wenn leitungsvermittelt: $n_{links} = 1$)
	\item mittlere Warteschlangenverzögerung \siehe{Übung 2.4}
	\begin{align*}
	d &= \frac{d_{ges}}{N}\\ 
	d_{ges} &= \sum \limits_{i=1}^N {(i-1)\cdot \frac{L}{R}} = \frac{N\cdot (N-1)}{2} \cdot \frac{L}{R}	
	\end{align*}	
	\item Verkehrsintensität: \siehe{Übung 1, 20\\ Übung 2.5}
	
	$\lambda$: durchschnittliche Paketankunftsrate (Pakete pro Sekunde)
	\begin{align*}
	\rho &= \dfrac{L \cdot \lambda}{R} 
	\begin{cases*}
		d_{queue}\text{ fällt} & \text{falls $\rho < 1$}\\
		d_{queue}\text{ steigt} & \text{falls $\rho = 1$}\\
		d_{queue} \rightarrow \infty, \text{ da mehr Pakete ankommen als abgearbeitet werden} & \text{falls $\rho > 1$}
	\end{cases*}	
	\end{align*}
	\item Wahrscheinlichkeit, dass $n$ Nutzer gleichzeitig senden: \siehe{Übung 1.3c}
	$P_n = \binom{\text{max}}{n}\cdot (P_{user})^n\cdot(1-P_{user})^{\text{max} - n}$ 
	
	\item Wahrscheinlichkeit, dass mehr als $n$ Nutzer gleichzeitig senden: \siehe{Übung 1.3d}
	$\sum_{n}^{\text{max}} P_i = 1 - \sum_{i=0}^{n} P_i$
\end{enumerate}
\section*{TCP-Leistungsanalyse}
\begin{enumerate}
	\item Verbindungsaufbau: $2\cdot RTT$ \siehe{Transport, 134} für:\begin{enumerate}
		\item $C \rightarrow S:$ \texttt{SYN} (seqnum: client\_isn)
		\item $S \rightarrow C:$ \texttt{SYN + ACK} (seqnum: server\_isn, acknum: $\text{client\_isn} +1$)
		\item $C \rightarrow S:$ \texttt{ACK + Request} (seqnum: $\text{client\_isn} +1$, acknum: $\text{server\_isn} +1$)
	\end{enumerate}
	\item Verbindungsabbau: \siehe{Transport, 136}
	\begin{enumerate}
		\item $C \rightarrow S:$ \texttt{FIN} (seqnum: client\_sqn)
		\item $S \rightarrow C:$ \texttt{ACK} (seqnum: server\_sqn, acknum: $\text{client\_sqn} + 1$)
		\item $S \rightarrow C:$ \texttt{FIN} (seqnum: server\_sqn)
		\item $C \rightarrow S:$ \texttt{ACK} (seqnum: $\text{client\_sqn} + 1$, seqnum: $\text{server\_sqn} +1$)
		\item $C$ wartet noch 2 Segmentlebensdauern auf mögliche alte Segmente (\enquote{time wait}),\\
		$S$ ist nach dem Erhalt des letzten ACKs fertig
	\end{enumerate}
	\item festes Fenster, keine Wartezeiten: \siehe{Transport, 162\\ Übung 4, 9\\ Übung 5, 4} \begin{equation*}
	d = \underbrace{2\cdot RTT}_{\text{Verbindungsaufbau}} + \underbrace{\frac{O}{R}}_\text{Datei übertragen} 
	\end{equation*}
	
	tritt ein falls gilt: \begin{equation*}
	\underbrace{\frac{WL}{R}}_\text{Senden eines Fensters der Größe $WL$} \geq \underbrace{\frac{L}{R}}_\text{Senden Segment} + \underbrace{RTT}_\text{ACK von Server bei Client}
	\end{equation*}
	\item festes Fenster, mit Wartezeit (also $\frac{WL}{R} < \frac{L}{R} + RTT$): \siehe{Transport, 163\\ Übung 4, 8\\ Übung 5, 6}
	Wartezeit pro Fenster: \begin{equation*}
	\frac{L}{R} + RTT - \frac{WL}{R}
	\end{equation*}
	
	$K$ Fenster $\Rightarrow (K-1)$-mal Warten, Anzahl benötigter Fenster $K \coloneqq \left\lceil \frac{O}{WL}\right\rceil \Rightarrow (K-1)$-mal Warten
	\begin{equation*}
	d = 2RTT + \frac{O}{R} + \left(K-1\right) \left(\frac{L}{R} + RTT - \frac{WL}{R}\right)
	\end{equation*}
	\item Dynamisches Fenster: \siehe{Transport, 164\\ Übung 5, 8}
	\begin{equation*}
	d = 2 RTT + \frac{O}{R} + d_\text{SSW}
	\end{equation*}
	
	warten, wenn $\frac{WL}{R} \leq \frac{L}{R} + RTT \Rightarrow$ Wartezeit nach $K$. Fenster: $\max \{\frac{L}{R} + RTT - 2^{K-1}\cdot \frac{L}{R}; 0\}$\\
	Wartezeiten bis Fenster Q: $\max\{k: T \cdot \frac{L}{R} +RTT - 2^{k-1} \cdot \frac{L}{R};0\}$\\
	Anzahl Fenster K um O zu übertragen: $K= \min\{k:\sum_{i=1}^{k} x^{i-1}\cdot L >= 0\}$	
	\siehe{Transport, 166\\ Übung 5, 9}
	\begin{align*}
	Q &= \left\lfloor \log_2 \left(1 + \frac{RTT}{\frac{L}{R}}\right) \right\rfloor +1 & \text{bis zu welchem Fenster Wartezeiten}\\
	K &= \left\lceil \log_2 \left(\frac{O}{L} + 1\right) \right\rceil & \text{Anzahl Fenster um $O$ zu übertragen}\\
	\underbrace{P}_\text{Anzahl SSW} &= \min \{\underbrace{Q}_\text{Nicht mehr warten, $O$ groß genug}; \underbrace{K-1}_\text{Warten, wenn $O$ zu klein}\} & \text{Wartezeit bei endlich großem Objekt $O$}\\
	d &= 2RTT + \frac{O}{R} + P\cdot \left(RTT + \frac{L}{R}\right) - \left(2^P -1\right) \cdot \frac{L}{R}
	\end{align*}
	
	\item mehrere Links $T$: \siehe{Übung 5.2}
	\begin{align*}
	d &= 2\cdot RTT_T + \frac{O}{R} + \left( T-1 \right)\cdot \frac{L}{R} + P_T \cdot \left( RTT_T + \frac{TL}{R}\right) - \left(2^{P_T} -1\right)\cdot \frac{L}{R}\\
	Q_T &= \left\lfloor \log_2 \left(T + \frac{RTT}{\frac{L}{R}}\right) \right\rfloor +1\\
	K &= \text{wie normal}
	\end{align*}
	
	\item um Faktor 2 erhöhen, also Fenstergröße $W^3$: \siehe{Übung 5.1}
	\begin{align*}
	d &= 2\cdot RTT + \frac{O}{R} + P\cdot \left( \frac{L}{R}+RTT\right) - \frac{P-1}{2} \cdot \frac{L}{R}\\
	Q &= \left\lfloor \log_3 \left(1+ \frac{RTT}{\frac{L}{R}}\right) \right\rfloor + 1\\
	K &= \left\lceil \log_3\left(\frac{2O}{L} +1\right)\right\rceil
	\end{align*}
	\item Verzögerung \texttt{HTTP} mit $M$ Objekten und 1 Basisseite:\begin{enumerate}
		\item nicht-persistent: \siehe{Übung 5, 18\\ Aufgabe 5.1}
		\begin{equation*}
		\left(M+1\right) \left(2\cdot RTT + \frac{O}{R} + \text{SSW}\right)
		\end{equation*}
		\item persistent mit Pipelining: Q und K konstant \siehe{Übung 5, 18\\ Aufgabe 5.3}
		\begin{equation*}
		2\ RTT + \underbrace{RTT}_\text{Anfrage Bilder} + \left( M+1 \right) \cdot \frac{O}{R} + \text{gem. SSW}
		\end{equation*}
		\begin{equation*}
		\text{gem. SSW} = \text{SSW} + RTT - \max\left\lbrace\frac{L}{R} + RTT - \left(2^{K-1} \cdot \frac{L}{R}\right);0\right\rbrace
		\end{equation*}
		\item nicht-persistent mit $X$ parallelen Verbindungen ($\frac{M}{X}$ ganze Zahl):\\ in $SSW_{parallel}$ R durch $\frac{R}{X}$ ersetzen \siehe{Übung 5, 18\\ Aufgabe 5.2}
		\begin{equation*}
		\left( \frac{M}{X} + 1 \right)\cdot 2\cdot RTT + \left( M + 1\right) \cdot \frac{O}{R} + SSW_{\text normal} + SSW_{\text parallel}
		\end{equation*}
	\end{enumerate}
	\item Flusskontrolle: \siehe{Transport, 144}
	\begin{enumerate}
		\item $\text{effective window} > 0 \Rightarrow \text{senden}$
		\item $\text{LastByteWritten} - \text{LastByteAcked} \leq \text{MaxSendBuffer} \Rightarrow \text{Anwendung schreibt}$ \siehe{Transport, 147}
		\item Freier Speicher bei Empfänger:\\
		$\text{advertised window} = \text{maxRcvBuffer} - \left( \left( \text{NextByteExpected} - 1\right) - \text{LastByteRead}\right)$ \siehe{Transport, 146}
		\item Falls mehr als 16 Bit für Fenstergröße benötigt werden: Scaling Factor $F \leq 14$, dann gilt $\text{window} = \text{advertised window} \cdot 2^F$ \siehe{Transport, 150}
	\end{enumerate}
	\item Überlastkontrolle: \begin{enumerate}
		\item $\text{max window} = \min\left\lbrace \text{congestion window}; \text{advertised window} \right\rbrace$ \siehe{Transport, 152}
		\item $\text{effective window} = \text{max window} - \left(\text{LastByteSent} - \text{LastByteAcked}\right)$ \siehe{Transport, 152}
		\item Bitrate $R \approx \frac{\text{congestion window}}{RTT}$
		\item Slow-Start: \siehe{Transport, 153f}
		\begin{enumerate}
			\item anfangs congestion window $=$ MSS, nach jedem ACK $\text{congestion window} += \text{MSS}$ (also exponentiell), bis 3 doppelte ACKs eintreffen oder Threshold (anfangs unendlich) erreicht
			\item Multiplicative Decrease (3 doppelte ACKs):\\
			$\text{Threshold} = \frac{\text{congestion window}}{2};\text{congestion window} /= 2$
			\item Additive Increase: Mit jedem ACK: $\text{congestion window} += \text{MSS}\cdot \frac{\text{MSS}}{\text{congestion window}}$
			\item nach Timeout: $\text{Threshold} = \frac{\text{congestion window}}{2}; \text{congestion window} = \text{MSS}$ (dann wird Slow-Start bis zum Threshold und danach AIMD durchgeführt)
		\end{enumerate}
	\end{enumerate}
\end{enumerate}
\section*{Bitfehlerwahrscheinlichkeiten} \siehe{Transport, 12}
	\begin{enumerate}
		\item mindestens 1 Bitfehler im Segment: $1 - (1-p)^L$
		\item 2 Bitfehler im Segment: $P_\text{2\_Fehler} \coloneqq \#_\text{Paare} \cdot P_\text{bestimmtes Paar fehlerhaft} = \frac{(L-1)\cdot L}{2} \cdot P_\text{bestimmtes Paar fehlerhaft}$
		\item mittlere Anzahl Pakete bis 2 Bitfehler im gleichen Segment: $\frac{1}{P_\text{2\_Fehler}}$
	\end{enumerate}
\section*{Fehlerkontrolle}
	\begin{enumerate}
	\item Stop-And-Wait: \siehe{Transport, 18}
	\begin{enumerate}
		\item (Leitungs-)Durchsatz: \siehe{Transport, 92}
		\begin{equation*}
			\frac{L}{N \cdot \left(\frac{L}{R} + 2D \right)}
		\end{equation*} 
		\item Normierter Durchsatz: \siehe{Transport, 92}
		\begin{equation*}
		S = \frac{1}{N (1+2a)}
		\end{equation*}
		\item Falls keine Fehler: $N=1$ \siehe{Transport, 91\\ Übung 4, 3}
		\item Mittlere Anzahl der Sendeversuche pro Paket bei Fehlerwahrscheinlichkeit $p$: \siehe{Transport, 93}
		\begin{equation*}
		N = \sum_{i=1}^{\infty} i\cdot p^{i-1} \cdot (1-p) = \frac{1}{1-p} \Rightarrow S =\frac{1-p}{1+2a}
		\end{equation*}
	\end{enumerate}
	\item Selective-Repeat (mit Pakete auf Kanal $a = \frac{R\cdot D}{L}$): \begin{enumerate}
		\item 1. Fall: Fenster groß genug, dass bis zum ACK-Empfang gesendet werden kann, also $W > 1+2a$: \begin{enumerate}
			\item ohne Fehler: \siehe{Transport, 95\\ Übung 4, 9}
			\begin{equation*}
			S = \frac{W\cdot L}{W\cdot \frac{L}{R}} \cdot \frac{1}{R} = 1
			\end{equation*}
			\item mit Fehlerwahrscheinlichkeit $p$: \siehe{Transport, 99\\ Übung 4, 16}
			\begin{equation*}
			S = 1-p
			\end{equation*}
		\end{enumerate}
		
		\item 2. Fall: Es muss auf ACK gewartet werden, also $W < 1+2a$: \begin{enumerate}
			\item ohne Fehler: \siehe{Transport, 95\\Übung 4, 8}
			\begin{equation*}
			S = \frac{W \cdot L}{\frac{L}{R} + 2D} \cdot \frac{1}{R} = \frac{W}{1+2a}
			\end{equation*}
			\item mit Fehlerwahrscheinlichkeit $p$: \siehe{Transport, 99\\ Übung 4, 16}
			\begin{equation*}
			S = \frac{W\cdot (1-p)}{1+2a}
			\end{equation*} 
		\end{enumerate}
	\end{enumerate}
	\item Go-Back-N (ohne Fehler wie Selective-Repeat) mit Fehlerwahrscheinlichkeit $p$:
	\begin{enumerate}
		\item Mittlere Anzahl Sendeversuche pro Paket:
		\begin{equation*}
			N = \sum_{i=1}^{\infty} ((1-K)+K_i)\cdot p^{i-1} \cdot (1-p) = \frac{1-p+ K\cdot p}{1-p}
		\end{equation*}
		\item $W \geq 1+2a$: $\left(K = 1+2a\right)$ \siehe{Transportschicht, 101\\Übung 4, 18}
		\begin{equation*}
		S = \frac{1-p}{1+2ap}
		\end{equation*}
		\item $W < 1+2a$: $\left(K=W\right)$ \siehe{Transportschicht, 101\\Übung 4, 18}
		\begin{equation*}
		S = \frac{W\cdot (1-p)}{(1-p + W\cdot p) \cdot (1+2a)}
		\end{equation*}
	\end{enumerate}
\end{enumerate}
\section*{Sequenznummernraum mit $m = 2^n$ Werten}
\siehe{Transport, 61\\Transport, 81}
\begin{enumerate}
	\item Falls Empfangsfenstergröße = 1: $W < m$ hinreichend
	\item Falls Sendefenstergröße = Empfangsfenstergröße $>$ 1: $ W < \frac{m+1}{2}$
\end{enumerate}
\section*{Leistungsanalyse Medienzugriff}
\siehe{Sicherung, 19}
\begin{enumerate}
	\item (Slotted-)ALOHA: \siehe{Sicherung, 28}
	\begin{enumerate}
		\item Wahrscheinlichkeit für Senden ohne Kollision bei Sendewahrscheinlichkeit $p$: \siehe{Sicherung, 36}
		\begin{align*}
		&\underbrace{p}_\text{Knoten sendet} \cdot \underbrace{P}_\text{kein anderer Knoten sendet in $[t_0 -1, t_0]$} \cdot \underbrace{P}_\text{kein anderer Knoten sendet in $[t_0, t_0+1]$}\\
		&= p\cdot (1-p)^{N-1}\cdot (1-p)^{N-1} = p \cdot (1-p)^{2N-2}\\
		\end{align*}
		\item Normalisierter Durchsatz: \siehe{Sicherung, 36}
		\begin{equation*}
		S = N \cdot p(1-p)^{2(N-1)}
		\end{equation*}
		\item Sendeversuche pro Slot: $G=N\cdot p \Rightarrow p=\frac{G}{N}$ \siehe{Sicherung, 37}
		\begin{enumerate}
			\item ALOHA: $G=0,5$ \siehe{Sicherung, 37}
			\item Slotted-ALOHA: $G=1$ \siehe{Sicherung, 39}
		\end{enumerate}
	\end{enumerate}
	\item CSMA \siehe{Sicherung, 41\\ Übung 8, 4}
	\begin{enumerate}
		\item notwendige Voraussetzung: Ausbreitungsverzögerung $d_\text{prop} <$ Rahmensendezeit $\frac{L}{R}$ \siehe{Sicherung, 42}
		\item verwendet ACKs
		\item bei fehlendem ACK nach Timeout $\Rightarrow$ Backoff (warten) $\Rightarrow$ Resend
		\item Varianten: \siehe{Sicherung, 43\\Übung 8, 6}
		\begin{enumerate}
			\item 1-persistent: Bei belegtem Medium warten bis frei, dann sofort senden
			\item nicht-persistent: Bei belegtem Medium Backoff
			\item $p$-persistent: Wenn Medium wieder frei, Senden mit Wahrscheinlichkeit $p$ oder einen weiteren Slot abwarten ($1-p$) 
		\end{enumerate}
	\end{enumerate}
	\item CSMA/CD \siehe{Sicherung, 48\\ Übung 8, 11\\ Übung 8.2}
	\begin{enumerate}
		\item mit allen CSMA-Varianten kombinierbar
		\item keine ACKs
		\item verwendet \enquote{listen while talking}
		\item Normierter Durchsatz: \siehe{Sicherung, 52}
		\begin{align*}
		S_{max} &= \frac{Sendezeit}{Sendezeit + Ausbreitungszeit +Wettbewerbszeit}\\
		&= \frac{\frac{L}{R}}{\frac{L}{R} +D + (e-1)\cdot 2D} = \frac{1}{1+4,4a}
		\end{align*}
		\item Minimale Rahmengröße $L$: \siehe{Sicherung, 50}
		\begin{equation*}
		\frac{L}{R} > 2\cdot D \Rightarrow L > 2\cdot R \cdot D
		\end{equation*}
		\item Erfolg
		\begin{align*}
			p = \frac{1}{N}\\
			P_\text{erfolg} = N\cdot p(1-p)^{N-1}\\
			(P_\text{erfolg})^{\text max} = \frac{1}{e}
		\end{align*}
		$\Rightarrow$ alle $e$ Slots erfolgreicher Sendeversuch
	\end{enumerate}
	\item Ethernet \siehe{Sicherung, 63}
	\begin{enumerate}
		\item 1-persistentes CSMA/CD
		\item Hub: eine Kollisionsdomäne, Signal wird auf alle Ports weitergeleitet \siehe{Sicherung, 66}
		\item Bridge: Aufteilung in verschiedene Kollisionsdomänen, enthält \enquote{Switching Fabric} \siehe{Sicherung, 67}
		\item VLAN entweder port- oder tag-basiert \siehe{Sicherung, 72}
	\end{enumerate}
\end{enumerate}

\section*{Verteilte Hash-Tabellen}
\siehe{Anwendung, 87}
\begin{enumerate}
	\item jeder Peer hat Bezeichner $p\in \lbrack 0, 2^m)$ bei $m$ Bits
	\item jedes Datenelement hat Schlüssel $k$ aus gleichem Raum
	\item Speicherung und Auslesen von $k$ auf Peer $p = \text{succ}(k) = \left( k+a \right) \mod 2^m$ mit minimalem $a$
	\item Effizienzsteigerung durch Fingertabellen auf jedem Peer $p$: \siehe{Anwendung, 89\\ Übung 3.1}
	\begin{enumerate}
		\item $m$ Einträge: 
		\begin{equation*}
		FT_{p}[i] = \left(p+2^{i-1}\right)\mod 2^m 	
		\end{equation*}
		\item Lookup von $k$ beginnend auf beliebigem  Peer $p$:
		\begin{align*}
		\text{lookup}(k,p) = \begin{cases}
		p &, p = k\\
		FT_p[1] &, p < k\leq FT_p[1]\\
		\text{lookup}(k, FT_p[i]) &, FT_p[i] \leq k < FT_p[i+1]\ \text{mit}\ 1 < i < m\\
		\text{lookup}(k, FT_p[m]) &, FT_p[m] \leq k
		\end{cases}
		\end{align*}
	\end{enumerate}
\end{enumerate}

\section*{Cyclic Redundancy Check}
\siehe{Sicherung, 14}
\begin{enumerate}
	\item Nutzdaten $D$ mit $d$ Bits, Prüfdaten $R$ mit $r$ Bits, Generatorpolynom $G$ mit $r+1$ Bits
	\item $R$ ist Rest bei $(D\cdot 2^r) / G$
	\item $(D,R)$ ist folglich $\left(D\cdot 2^r\right) \oplus R$
	\item Korrekt falls $(D,R) / G = 0$
\end{enumerate}

\section*{Shannons Theorem}
\begin{enumerate}
	\item Maximale Datenrate $R$ bei Bandbreite $B$: $R = B \cdot \log_2(1+ \frac{S}{N})$ \siehe{Physikalisch, 24}
	\item $x\ dB = 10 \log_{10} \frac{S}{N} \Rightarrow \frac{S}{N} = 10^{\frac{x}{10}}$ \siehe{Physikalisch, 24}
\end{enumerate}

\section*{Mathematisches}
\begin{enumerate}
	\item Binomialkoeffizient:
	\begin{equation*}
	\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}
	\end{equation*}
	\item Gaußsche Summenformel:
	\begin{equation*}
	\sum_{k=1}^{n} k = \frac{n \cdot (n+1)}{2}
	\end{equation*}
	\item Quadratische Pyramidalzahl:
	\begin{equation*}
	\sum_{k=1}^{n} k^2 = \frac{n\cdot (n+1)\cdot (2n+1)}{6} = \frac{2n^3+3n^2+n}{n}
	\end{equation*}
	\item Geometrische Reihe für $\vert q\vert < 1$:
	\begin{equation*}
		\sum_{k=0}^{\infty} \left( a_0\cdot q^k \right) = \frac{a_0}{1- q}
	\end{equation*}
\end{enumerate}
\end{document}