Merge pull request #41 from michael-OST/master

Abschluss Bonuskapitel

5 files changed, 135 insertions, 10 deletions

diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex
index 83e0f94..c03b1a4 100644
--- a/buch/papers/reedsolomon/anwendungen.tex
+++ b/buch/papers/reedsolomon/anwendungen.tex
@@ -6,14 +6,40 @@
 \section{Anwendungen des Reed-Solomon-Codes
 	\label{reedsolomon:section:anwendung}}
 \rhead{Anwendungen}
-\textcolor{red}{Platzierung der Bilder? Quellenangabe der Bilder?}
 
 In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie Funktionieren. 
 In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed-Solomon-Code zum Einsatz kommt.
+
+Dabei teilen all diese Anwendungen das gleiche Problem: Die Daten können nur durch einen (höchst Wahrscheinlichen) fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode an diese Daten zu kommen als über diesen Kanal.
+
+
+In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpakete diese einfach noch einmal inert wenigen Millisekunden angefordert werden können.
+In der Raumfahrt ist dies nicht möglich, da aufgrund der beschränkten Speichermöglichkeit die gesammelten Daten so rasch wie möglich zur Erde gesendet werden. 
+Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden bis die Daten beim Empfänger ankommen.
+Fehlerhafte Daten kann also auf Grund der Zeitverzögerung nicht mehr angefordert werden. 
+
+Bei CDs oder DVDs gibt es zwar kein Zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk.
+Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden muss, so wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. 
+
+Ein ähnlicher Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. 
+
+%Wie man sieht, eignen sich Reed-Solomon-Codes vor allem für Anwendungen, bei der die Informationen nicht auf einen Anderen Weg beschafft werden kann. 
+%
+%
+%, bei denen die Wahrscheinlichkeit hoch ist, dass während der Übertragung 
+%
+%Es ist deshalb umso wichtiger die Daten Codiert zu lesen um so gleich die Lesefehler zu korrigieren.
+%
+% da aufgrund der grossen Distanz Stunden vergehen können bis gesendete Daten auf der Erde empfangen werden kann. 
+%
+
+
 Obwohl alle diese Codes nach dem gleichen Prinzip arbeiten gibt es starke Unterschiede in deren Funktionsweise. 
 Dies kommt vor allem daher, da die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitstellt wird,  auf denen die Codes implementiert wurden.
 Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um möglichst effizient zu arbeiten.
-%
+
+Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben verwendet man die Notation ($n$,$k$), wobei $n$ die Grösse des Nachrichtenblocks angibt und $k$ die Anzahl der Stellen, die für Nutzdaten gebraucht werden können.
+
 %Dies kommt vor allem daher, da diese Codes an ihre Hardware gebunden sind, auf denen sie implementiert worden sind.
 %Deshalb wurden diese Codes stark optimiert damit sie möglichst Effizient arbeiten können. 
 %
@@ -45,8 +71,17 @@ Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um mögli
 %In den letzten abschnitten haben wir uns ausführlich die Funktionsweise des Reed-Solomon-Codes angeschaut. In diesem Abschnitt möchten wir dem Leser ein paar bekannte beispiele vorstellen, in denen Reed-Solomon-Codes zum einsatz kommen. Es sei jedoch angemerkt, dass diese Anwendungen in der Umsetzung oft ein wenig anderst funktionieren als hier vorgestellt. Dies wurde vor allem wegen technischen optimierungen realisiert. (technische tricks und finessen), von der logik jedoch sehr stark an unserem Beispiel orientieren
 
 \subsection{Raumfahrt}
-Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie erstmals Anwendung in der Voyager Raumsonde der NASA. Die Daten der zwei im Jahre 1977 gestarteten Sonden werden mit einem RS(255,233)-Code \textcolor{red}{benötigt das weitere erklärungen, wie z.b. 255: grösse nachrichtenblock, 233: anzahl der nutzbaren daten ?} zusammen mit einem konventionellen Faltungscode übertragen. 
-
+Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie erstmals Anwendung in der Voyager Raumsonde der NASA. Die Daten der zwei im Jahre 1977 gestarteten Sonden (siehe Abbildung \ref{fig:voyager}) werden mit einem ($255$,$233$)-Code
+Codiert. 
+Der Nachrichtenblock hat somit eine Länge von $255$ Zahlen, wovon $233$ als Nutzlast zur Verfügung stehen.
+Damit ist es möglich bis zu $11$ Fehler im Nachrichtenblock zu korrigieren. 
+Der Codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut Codiert und anschliessend gesendet. Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, Funktioniert aber nach einem ganz anderen Prinzip. 
+Durch diese doppelte Codierung wird eine äusserst hohe Übertragungssicherheit garantiert.
+%
+%Dabei steht die Zahl 255 für grösse des Nachrichtenblocks, der die Anzahl 233
+%
+%
+% \textcolor{red}{benötigt das weitere Erklärungen, wie z.b. 255: grösse Nachrichtenblock, 233: anzahl der nutzbaren daten ?} zusammen mit einem konventionellen Faltungscode übertragen. Eine von der Sonde gesendete Nachricht hat eine Blockgrösse von 255 Zeichen, wovon 233 für die Nutzdaten gebraucht werden können. Dieser Code ist somit in der Lage 11 Fehler in einem Nachrichtenblock zu korrigieren. 
 %
 % Die zwei im Jahre 1977 gestarteten Sonden senden Daten mit der Hilfe eines RS(255,233)-Code für die digitalen Bilder sowie einem konventionellen Faltungscode.
 %
@@ -56,14 +91,14 @@ Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie ers
 \begin{figure}
 	\centering
 	\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Voyager_Sonde}
-	\caption{Voyager Raumsonde}
+	\caption{Mit einer Entfernung von über 22.8 Milliarden Kilometer ist die Voyager 1 Raumsonde das am weitesten entfernte, von Menschen erschaffene Objekt. Obwohl ihre Schwestersonde Voyager 2 zuerst ins All gestartet wurde befindet Sie sich ``nur'' 19 Milliarden Kilometer weit weg von der Erde. Aufgrund abnehmender Batterieleistung werden die beiden Sonden ihre wissenschaftlichen Aktivitäten etwa 2025 einstellen, bleiben aber bis in die 2030er mit uns in Kontakt.}
 	\label{fig:voyager}
 \end{figure}
 
 \subsection{CD/DVD}
 Compact discs verwenden sogar zwei ineinander verschachtelte Reed-Solomon-Codes, einen (32,28)-Code und einen (28,24)-Code.
-Beide Codes sind in der Lage, Fehler aus dem jeweils anderen gelesenen Block zu korrigieren. Dieses spezielle zusammenspielen dieser beiden Codes werden auch Cross-interleaved Reed-Solomon-Codes (CIRC) genannt.
-Diese Vorgehensweise erzielt eine hohe Robustheit gegenüber Produktionsfehler oder Verschmutzung auf der Disc. Bei CD's sind diese in der Lage bis zu 4000 fehlerhafte Bits am Stück (ca. $2.5mm$) zu erkennen und zu korrigieren. 
+Beide Codes sind in der Lage, Fehler aus dem jeweils anderen gelesenen Block zu korrigieren. Dieses spezielle Zusammenspielen dieser beiden Codes werden auch Cross-interleaved Reed-Solomon-Codes (CIRC) genannt.
+Diese Vorgehensweise erzielt eine hohe Robustheit gegenüber Produktionsfehlern oder Verschmutzung auf der Disc. Bei CDs sind diese in der Lage, bis zu 4000 fehlerhafte Bits am Stück (ca. $2.5mm$) zu erkennen und zu korrigieren. 
 
 Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeblöcken. Die DVD verwendet einen (208,192)-Code und einen (182,172)-Code.
 
@@ -73,12 +108,19 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb
 \begin{figure}
 	\centering
 	\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Compact_Disc}
-	\caption{Compact Disc}
+	\caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das ``einbrennen'' von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.}
 	\label{fig:cd}
 \end{figure}
 
 \subsection{QR-Codes}
-Quick Response Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel, nur dass QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Je nach grösse der Codierung ist der QR-Code im Endeffekt robuster gegen Beschädigungen. Bei Low Level Codes können 7\% der Daten Wiederhergestellt werden, beim High Level Code sind das sogar 30\%.
+Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Die Physische Grösse eines Codes ist stark abhängig von der Grösse der Codierung sowie dem Fehlerkorrektur-Level. Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein Qr-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die Gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes Zweckentfremdet werden. Dabei wird z.B. das Firmenlogo oder einen Schriftzug über den Qr-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist unter Abbildung \ref{fig:designqr} zu finden. 
+
+% 
+
+%So kann auf den ersten Blick nicht 
+%
+%
+% funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel, nur dass QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Je nach grösse der Codierung ist der QR-Code im Endeffekt robuster gegen Beschädigungen. Bei Low Level Codes können 7\% der Daten Wiederhergestellt werden, beim High Level Code sind das sogar 30\%. 
 
 \begin{figure}
 	\centering
@@ -88,6 +130,30 @@ Quick Response Codes funktionieren nach einem sehr ähnlichen Prinzip wie in uns
 	\subfigure[]{
 	\includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_l}
 	}
-	\caption{(a) High Level Code, (b) Low Level Code}
+%	\subfigure[]{
+%	\includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode_ohnelogo}
+%	}
+%	\subfigure[]{
+%	\includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode}
+%	}
+	\caption{Anhand der grösse würde man darauf schliessen, dass bei (a) mehr Informationen Codiert sind als bei (b). Tatsächlich aber beinhalten beide Codes die gleiche Information. Das liegt daran, da die Fehlerkorrekturfähigkeit von QR-Codes sich in insgesamt vier Levels aufteilen lassen. Der höchste Fehlerkorrektur-Level, der bei (a) angewendet wurde, ist in der Lage, bis zu 30\% der Daten wiederherzustellen. Der kleinste Level schafft etwa 7\%, der in (b) veranschaulicht wird. Da die Grösse also nichts über die Menge an Daten aussagt, könnte es sich bei (a) auch um einen Code mit viel Nutzdaten und kleinem Fehlerkorrektur-Level handeln. Der Unterschied ist von Auge nicht sichtbar.}
 	\label{fig:qr}
 \end{figure}
+
+\begin{figure}
+	\centering
+%	\subfigure[]{
+%		\includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_h}
+%	}
+%	\subfigure[]{
+%		\includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_l}
+%	}
+	\subfigure[]{
+		\includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode_ohnelogo}
+	}
+	\subfigure[]{
+		\includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode}
+	}
+	\caption{Während (a) noch ein unveränderter QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich dadurch die Fehlerkorrekturfähigkeit je nach grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.}
+	\label{fig:designqr}
+\end{figure}
\ No newline at end of file
diff --git a/buch/papers/reedsolomon/images/designer_qrcode.png b/buch/papers/reedsolomon/images/designer_qrcode.png
new file mode 100644
index 0000000..a9e0505
--- /dev/null
+++ b/buch/papers/reedsolomon/images/designer_qrcode.png
diff --git a/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png b/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png
new file mode 100644
index 0000000..fe4251d
--- /dev/null
+++ b/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png
diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex
index 6bd04f2..a400508 100644
--- a/buch/papers/reedsolomon/main.tex
+++ b/buch/papers/reedsolomon/main.tex
@@ -45,6 +45,12 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren
 
 \nocite{reedsolomon:weitz}
 \nocite{reedsolomon:informationkommunikation}
+\nocite{reedsolomon:voyager_programm}
+\nocite{reedsolomon:voyager}
+\nocite{reedsolomon:cd_wiki}
+\nocite{reedsolomon:cd}
+\nocite{reedsolomon:qr_wiki}
+\nocite{reedsolomon:qr}
 %\nocite{reedsolomon:mendezmueller}
 
 \printbibliography[heading=subbibliography]
diff --git a/buch/papers/reedsolomon/references.bib b/buch/papers/reedsolomon/references.bib
index 731bd35..e0a75a8 100644
--- a/buch/papers/reedsolomon/references.bib
+++ b/buch/papers/reedsolomon/references.bib
@@ -23,3 +23,56 @@
 	volume = {1}
 }
 
+@online{reedsolomon:voyager_programm,
+	title = {Information über das Voyager Programm},
+	url = {https://de.wikipedia.org/wiki/Voyager-Programm},
+	date = {2021-07-19},
+	year = {2021},
+	month = {7},
+	day = {19}
+}
+
+@online{reedsolomon:voyager,
+	title = {Bild der Voyager Raumsonde},
+	url = {https://en.wikipedia.org/wiki/Voyager_1},
+	date = {2021-07-19},
+	year = {2021},
+	month = {7},
+	day = {19}
+}
+
+@online{reedsolomon:cd_wiki,
+	title = {Alles über die CD},
+	url = {https://de.wikipedia.org/wiki/Compact_Disc},
+	date = {2021-07-19},
+	year = {2021},
+	month = {7},
+	day = {19}
+}
+
+@online{reedsolomon:cd,
+	title = {Funktionsweise des QR-Codes},
+	url = {https://www.stickpng.com/img/electronics/compact-discs/stack-compact-disc},
+	date = {2021-07-19},
+	year = {2021},
+	month = {7},
+	day = {19}
+}
+
+@online{reedsolomon:qr_wiki,
+	title = {Funktionsweise des QR-Codes},
+	url = {https://de.wikipedia.org/wiki/QR-Code},
+	date = {2021-07-19},
+	year = {2021},
+	month = {7},
+	day = {19}
+}
+
+@online{reedsolomon:qr,
+	title = {Tool zum erstellen von QR-Codes},
+	url = {https://www.qrcode-generator.ch},
+	date = {2021-07-19},
+	year = {2021},
+	month = {7},
+	day = {19}
+}
\ No newline at end of file