aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-07-27 07:59:15 +0200
committerGitHub <noreply@github.com>2021-07-27 07:59:15 +0200
commit7a478c340ee1f9ceddfd5b62a21b95b69127f4c5 (patch)
tree91a55b0d5337147515c27108c58d67f7c623af77 /buch/papers
parentremove rs (separate paper) (diff)
parentBonus-Chapter updated (diff)
downloadSeminarMatrizen-7a478c340ee1f9ceddfd5b62a21b95b69127f4c5.tar.gz
SeminarMatrizen-7a478c340ee1f9ceddfd5b62a21b95b69127f4c5.zip
Merge pull request #46 from michael-OST/master
Bonus-Chapter updated
Diffstat (limited to 'buch/papers')
-rw-r--r--buch/papers/reedsolomon/anwendungen.tex35
-rw-r--r--buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.pngbin0 -> 45679 bytes
-rw-r--r--buch/papers/reedsolomon/main.tex1
-rw-r--r--buch/papers/reedsolomon/references.bib11
4 files changed, 33 insertions, 14 deletions
diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex
index c03b1a4..b9b1d69 100644
--- a/buch/papers/reedsolomon/anwendungen.tex
+++ b/buch/papers/reedsolomon/anwendungen.tex
@@ -7,21 +7,20 @@
\label{reedsolomon:section:anwendung}}
\rhead{Anwendungen}
-In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie Funktionieren.
+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.
+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 Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpaketen diese einfach noch einmal innert 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.
+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.
+Einen ähnlichen 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.
%
@@ -33,7 +32,6 @@ Ein ähnlicher Ansatz verfolgen QR-Codes, wobei die Information auch dann noch g
% 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.
@@ -75,8 +73,14 @@ Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie ers
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.
+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,
+Codiert seine Information aber auf eine andere weise. Aus jedem unterteilten Block wird vor dem Versenden ein Paritätsbit erzeugt und dem Block angehängt. Anhand diesem Paritätsbit überprüft der Empfänger, ob bei der Übertragung der Block beschädigt wurde. Ist dies der Fall, wird der Block bei der Decodierung nicht beachtet. Diese so entstandenen ``Lücken'' im Datenstrom werden wiederum vom Reed-Solomon-Code korrigiert. Dieses Zusammenspiel beider Codes garantiert so eine hohe Robustheit gegenüber Übertragungsfeher.
+
+%
+% 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
%
@@ -107,13 +111,18 @@ 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{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.}
+ \subfigure[]{
+ \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc}
+ }
+ \subfigure[]{
+ \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc_zoomed_in}
+ }
+ \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das Einpressen oder 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 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.
+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 Menge an codierten Daten sowie dem verwendeten 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.
%
@@ -154,6 +163,6 @@ Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen
\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.}
+ \caption{Während (a) noch einen unveränderten 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 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/Compact_Disc_zoomed_in.png b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png
new file mode 100644
index 0000000..69556d0
--- /dev/null
+++ b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png
Binary files differ
diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex
index e68b947..ab4e4be 100644
--- a/buch/papers/reedsolomon/main.tex
+++ b/buch/papers/reedsolomon/main.tex
@@ -49,6 +49,7 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren
\nocite{reedsolomon:voyager}
\nocite{reedsolomon:cd_wiki}
\nocite{reedsolomon:cd}
+\nocite{reedsolomon:strichepunkte}
\nocite{reedsolomon:qr_wiki}
\nocite{reedsolomon:qr}
%\nocite{reedsolomon:mendezmueller}
diff --git a/buch/papers/reedsolomon/references.bib b/buch/papers/reedsolomon/references.bib
index e0a75a8..b84b5a4 100644
--- a/buch/papers/reedsolomon/references.bib
+++ b/buch/papers/reedsolomon/references.bib
@@ -51,7 +51,7 @@
}
@online{reedsolomon:cd,
- title = {Funktionsweise des QR-Codes},
+ title = {Abbildung einer CD},
url = {https://www.stickpng.com/img/electronics/compact-discs/stack-compact-disc},
date = {2021-07-19},
year = {2021},
@@ -59,6 +59,15 @@
day = {19}
}
+@online{reedsolomon:strichepunkte,
+ title = {Abbildung der Striche und Punkte einer CD},
+ url = {https://www.researchgate.net/figure/The-readable-area-of-a-CD-is-magnified-in-order- to-see-the-pit-and-land-sizing-The_fig7_303401629},
+ date = {2021-07-26},
+ year = {2021},
+ month = {7},
+ day = {26}
+}
+
@online{reedsolomon:qr_wiki,
title = {Funktionsweise des QR-Codes},
url = {https://de.wikipedia.org/wiki/QR-Code},