\documentclass{beamer} \usepackage{beamerthemesplit} \usepackage[ngerman]{babel} \usepackage[latin1]{inputenc} \usepackage[T1]{fontenc} \usepackage{graphicx} \usepackage{dsfont} \begin{document} \title{fehlerkorrigierende Codes} \author{Thomas Irgang} \institute{Katholische Universitt Eichsätt} \date{\today} \frame[plain]{\titlepage} \frame{\tableofcontents} \section{Was sind fehlerkorrigierende Codes ?} \begin{frame} \frametitle{Was feherkorrigierende Codes nicht sind} \begin{itemize} \item es geht nicht um Verschlüsselung \pause \item Daten sollen trotz Fehlern wieder herstellbar sein \end{itemize} \end{frame} \begin{frame} \frametitle{Definition fehlerkorrigierender Codes} \emph{Fehlerkorrigierende Codes sind Codes, die es ermöglichen trotz Fehlern, die bei der Übertragung oder Speicherung von Daten auftreten, die Daten wieder herzustellen.} \end{frame} \begin{frame} \frametitle{Wozu braucht man fehlerkorrigierende Codes} \begin{itemize} \item Internetverbindung \pause \item DVB-T \pause \item CD, DVD\ldots \end{itemize} \end{frame} \begin{frame} \frametitle{Modellvorstellung} \begin{itemize} \item ein Sender sendet eine Nachricht \item die Nachricht wird über einen Kanal übertragen \item beim übertragen treten Fehler auf \item der Empfänger versucht die Nachricht wiederherzustellen \end{itemize} \end{frame} \begin{frame} \frametitle{Problemstellung} \begin{itemize} \item Kann man an Hand der Nachricht erkennen ob ein Fehler aufgetreten ist? \pause \item Es müssen zusätliche Daten übertragen werden um die "`Nutzdaten"' validieren zu können. \pause \item Was kann man machen wenn Fehler festgestellt werden? \pause \item Die einfachse Möglichkeit ist es das Datenpaket nochmal zu senden. Dies funktioniert aber nicht immer!\\ Welche Möglichkeiten gibt es wenn die Nachricht nicht nochmal gesendet werden kann (z.B. verkratzte CD). Wir brauchen Verfahren, die die Daten wiederherstellen können. \end{itemize} \end{frame} \begin{frame} \frametitle{Ein Ansatz} Die Codewörter müssen sich paarweise jeweils in mehreren Bits unterscheiden! Was hilft das?\\ \pause Dadurch gibt es zwischen je zwei Codewörtern einen Bereich in dem kein Codewort liegt. Wenn jetzt weniger Fehler als dieser Minimalabstand von zwei Codewörtern auftreten, ergibt sich ein ungültiges Codewort.\\ \emph{$\Rightarrow$ es kann mehr als ein Fehler erkannt werden.}\\ \pause Wie können mit diesem Ansatz Fehler korrigiert werden? \end{frame} \begin{frame} \frametitle{Die Idee} Wenn der Code einen Minimalabstand von $\geq$ 3 hat, und nur ein Fehler auftritt, können wir das veränderte Codewort eindeutig einem Codewort zuweisen und damit einen Fehler korrigieren. \end{frame} \begin{frame} \frametitle{Ein Beispiel} Gegeben sind die Codewrter $a,b$ die aus jeweils aus einer Folge von vier Einsen und Nullen bestehen: $a:=0011$, $b:=1110$\\ a und b unterscheiden sich in: $\left. \begin{array}{c} {\color{red}00}1{\color{red}1} \\ {\color{red}11}1{\color{red}0} \end{array} \right\}$ drei Stellen.\\ Wenn wir jetzt ein verändertes Codewort x empfangen, z.B. $x=0110$, können wir es mit a und b vergleichen\\ a und x: $\left. \begin{array}{c} 0{\color{red}0}1{\color{red}1} \\ 0{\color{red}1}1{\color{red}0} \\ \end{array} \right\}$ unterscheiden sich in zwei Stellen.\\ b und x: $\left. \begin{array}{c} {\color{red}1}110 \\ {\color{red}0}110 \\ \end{array} \right\}$ unterscheiden sich in einer Stelle.\\ Damit können wir, unter der Annahme einer minimalen Fehlerzahl, x als b decodieren. \end{frame} \begin{frame} \frametitle{Der Hammingabstand} Die Anzahl der Stellen in denen sich zwei Codewörter unterscheiden bezeichnet man als \emph{Hammingabstand}.\\ Ein Code ist eine Menge von Codewörtern. Der minimale Hammingabstand eines Codes ist das Minimum des Abstands das zwei beliebige Codewörter des Codes haben. \end{frame} \begin{frame} \frametitle{Aufgaben} c(0)=00011, c(1)=00110, c(2)=01100, c(3)=11000\\ \begin{enumerate} \item Bestimme den minimalen Hamming-Abstand der Codewörter c(0), c(1), c(2), c(3)! \item Kann man das vernderte Codewort x=00010 eindeutig decodieren? \item Beschreiben Sie den Zusammenhang zwischen dem minimalen Hamming-Abstand eines Codes und seiner Eigenschaften bezüglich des erkennens und korrigierens von Fehlern? \end{enumerate} \end{frame} \begin{frame} \frametitle{Minimalabstand und Fehlereigenschaften} Der Code im Beispiel hat einen Minimalabstand von 2. Das hat zur Folge, dass es passiern kann, dass wenn nur ein Bit im übertragenen Wort verändert ist, das veränderte Wort Abstand 1 zu zwei Codewörtern hat. Daraus folgt: Ein Code C ist ein \emph{t-fehlerkorrigierender} Code falls der Minimalabstand zwischen zwei Codewörtern $\geq 2t+1$ ist. Ein solcher kann dann Code kann $2t$ Fehler erkennen.\\ Es muss also um jedes Codewort eine Umgebung mit Radius t geben in der in der jedes Wort eindeutig dem Codewort zugeordnet werden kann. \end{frame} \section{Mathematik und fehlerkorrigierende Codes} \begin{frame} \frametitle{Was hat das ganze mit Mathe zu tun?} um Codes anwenden zu können muss es möglich sein effektiv mit ihnen umzugehen! D.h.: \begin{itemize} \item Daten müssen schnell und einfach codiert werden können und \pause \item Daten müssen schnell und einfach wiederhergestellt und decodiert werden können. \end{itemize} An dieser Stelle kommt die lineare Algebra ins Spiel. \end{frame} \begin{frame} \frametitle{Vektoren und Codes} Wir können die Codewörter als Vektoren auffassen, dazu brauchen wir aber einige neue Regeln wie die Multiplikation und Addition mit 0 und 1 funktioniert. Dazu wird folgendes definiert: \begin{itemize} \item $0+0=0$, $0+1=1$, $1+1=0$ und \pause \item $0\cdot 0 = 0$, $0\cdot 1 = 0$, $1\cdot 1 = 1$ \end{itemize} Die Vektoren haben dabei beliebige Länge, die Addition von zwei Vektoren und die Multiplikation mit Skalaren, in diesem Fall nur 0 und 1, ändert sich dabei nicht. \end{frame} \begin{frame} \frametitle{linearer Codes} Als linearer Code wird ein Code bezeichnet, bei dem sich die Codewörter mit Hilfe von wenigen Codewörtern erzeugen lassen. D.h. wenn wir Codewörter a, b, c haben sind auch a+b, a+c, b+c, a+b+c, ... Codewörter. \end{frame} \begin{frame} \frametitle{Vorteile linearer Codes} Daraus ergeben sich einige Vorteile: \begin{itemize} \item Man kann mit Hilfe von wenigen Codewörtern den ganzen Code speichern \pause \item Der Code kann mit Hilfe von Matrizen ``verarbeitet'' werden. \end{itemize} Verarbeitet bedeutet in diesem Zusammenhang dass Daten codiert, decodiert und Fehler korrigiert werden. \end{frame} \begin{frame} \frametitle{Matrizenmultiplikation} Im folgenden brauchen wir die Multiplikation von Vektoren mit Matrizen. Diese Multiplikation ist allgemein definiert durch: \[ \left( \begin{array}{ccc} a_{11} & \ldots & a_{1n} \\ a_{21} & \ldots & a_{2n} \\ \ldots & \ldots & \ldots \\ a_{m1} & \ldots & a_{mn} \\ \end{array} \right) \cdot \left( \begin{array}{c} v_1 \\ v_2 \\ \ldots \\ v_4 \\ \end{array} \right) = \left( \begin{array}{c} \sum_{i=1}^n a_{1i} \cdot v_i \\ \sum_{i=1}^n a_{2i} \cdot v_i \\ \ldots \\ \sum_{i=1}^n a_{mi} \cdot v_i \\ \end{array} \right) \] (also: Zeile $\cdot$ Spalte)\\ Ein Beispiel dazu: \[ \left( \begin{array}{ccccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right) \cdot \left( \begin{array}{c} 1 \\ 1 \\ 0 \\ \end{array} \right) = \left( \begin{array}{c} 1 \cdot 1 + 0 \cdot 1 + 0 \cdot 0 \\ 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 0 \\ 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 \\ 0 \cdot 1 + 0 \cdot 1 + 0 \cdot 0 \\ 0 \cdot 1 + 0 \cdot 1 + 0 \cdot 0 \\ \end{array} \right) = \left( \begin{array}{c} 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ \end{array} \right) \] \end{frame} \begin{frame} \frametitle{Ein Beispiel} Die Matrix $G:=\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}\right)$ (G für Generatormatrix) erzeugt einen linearen 1-fehlerkorrigierenden Code. \end{frame} \begin{frame} \frametitle{Ein Beispiel} Wenn jetzt z.B. das Datenwort $x:=\left(\begin{array}{c} 0 \\ 1 \\ 1 \\ 0 \end{array}\right)$ codiert werden soll rechnet man einfach $G \cdot x = \left(\begin{array}{c} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \end{array}\right)$. Dadurch muss man statt 16 ($=2^4$) Codewörtern nur 4 speichern und kann die Daten mit Hilfe der Matrix schnell codieren. \end{frame} \begin{frame} \frametitle{Ein Beispiel} Damit können wir Daten effektiv codieren und Codes effektiv speichern. Um auch effektiv decodieren zu können brauchen wir noch etwas mehr Mathematik. \end{frame} \begin{frame} \frametitle{Minimalgewicht} Als \emph{Gewicht} eines Vektors wird seine Anzahl der von 0 verschiedenen Stellen bezeichnet.\\ Das Minimalgewicht eines Codes ist, analog zum Hammingabstand, das Minimum über das Gewicht über alle Codewörter. \end{frame} \begin{frame} \frametitle{Minimalgewicht = Minimalabstand} Es ergibt sich, dass bei linearen Codes das Minimalgewicht gleich dem Minimalabstand ist.\\ Daraus ergibt sich ein großer Vorteil: statt $|C|$ Codewörter miteinander zu vergleichen muss man nur das Minimalgewicht der $|C|$ Codewörter bestimmen.\\ Dadurch lassen sich die Fehlerkorrektureigenschaften von einem linearen Code schnell erkennen, aber Vorsicht, man muss dennoch alle Codewörter betracheten denn z.B. die Codewörter $a:=011100$ und $b:=111000$ haben beide Gewicht 3, der lineare Code zu dem diese gehören muss aber auch $a+b$ enthalten. Damit ergibt sich:\\ $\left.\begin{array}{cc} & 111000 \\ + & 011100 \\ \end{array} \right\} = 100100$ und damit hat der Code ein Minimalgewicht von $\leq 2$. \end{frame} \begin{frame} \frametitle{Aufgabe} Wie viele Fehler kann der folgende lineare Code erkennen/korrigieren? \[ \begin{array}{cccc} 0000000 & 0001110 & 0010111 & 0011001 \\ 0100101 & 0101011 & 0110010 & 0111100 \\ 1111111 & 1110001 & 1101000 & 1100110 \\ 1011010 & 1010100 & 1001101 & 1000011 \\ \end{array} \] \end{frame} \begin{frame} \frametitle{Wie kann man effektiv decodieren?} Wir können jetzt Datenwörter einfach codieren und einen Code mit Hilfe von $2^k$ geschickt gewählten Codewörter darstellen und die Eigenschaften eines solchen linearen Codes schnell einschätzen.\\ Aber wie können wir einfach fehlerkorriegiern und die Codewörter wieder decodieren? \end{frame} \begin{frame} \frametitle{der duale Code} Um einen linearen Code effektiv zu decodieren brauchen wir den dualen Code $C^\perp$. Was ist das?\\ V ist die Menge aller möglichen Codewörter mit n Zeichen. Der duale Code enthält die Codewörter für die gilt $c \cdot v = 0$. $c \cdot v$ bedeutet dabei $c \cdot v = \sum_{i=1}^n c_i \cdot v_i$ \end{frame} \begin{frame} \frametitle{die Kontrollmatrix} Wenn wir den dualen Code haben können wir die Kontrollmatrix angeben und sind damit wieder einen Schritt näher am Ziel.\\ Eine Matrix deren Zeilen eine Basis (d.h. der duale Code lässt sich mit diesen Vektoren erzeugen und die Anzahl dieser Vektoren ist Minimal) des dualen Codes sind nennt man \emph{Kontrollmatrix} des linearen Codes, das Produkt $H \cdot s$ nennt man das \emph{Syndrom}. Mit Hilfe des Syndroms können wir nun endlich einen linearen Code effektiv decodieren. \end{frame} \begin{frame} \frametitle{der Decodieralgorithmus} Jetzt kann man mit Hilfe einer Liste der Nebenklassenanführer folgendermaßen Fehler korrigieren: \begin{enumerate} \item Syndrom vom empfangen Wort x berechen \item Fehlervektor e mit Hilfe der Liste der Syndrome feststellen \item Codewort c durch $c=x+e$ berechnen \end{enumerate} \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Generatormatrix} Diesen Algorithmus können wir jetzt mal an einem Beispiel durchspielen. Wir benutzen wieder die Generatormatrix $G:=\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}\right)$\\ \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Kontrollmatrix I} Als erstes brauchen wir wieder eine Kontrollmatrix, also brauchen wir den dualen Code. Wir brauchen also drei Vektoren die den dualen Code erzeugen.\\ Dies ist z.B. bei den Vektoren $ \left( \begin{array}{c} 1\\0\\0\\1\\1\\0\\1 \end{array} \right),\ \left( \begin{array}{c} 0\\1\\0\\1\\0\\1\\1 \end{array} \right),\ \left( \begin{array}{c} 0\\0\\1\\0\\1\\1\\1 \end{array} \right) $ der Fall. Dies können wie nachrechnen. \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Kontrollmatrix II} Die Matrix $ K := \left( \begin{array}{ccccccc} 1 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 & 1 & 1\\ \end{array} \right) $ ist also eine Kontrollmatrix zu $G$. \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Syndrome} Mit Hilfe der Kontrollmatrix können wir jetzt die Syndrome berechnen. Wir berechnen die Syndrome der Einheitsvektoren, da dies alle möglichen Fehlervektoren sind. Dadurch erhalten wir: \[ \begin{array}{cc} 0000000 & 000 \\ 0000001 & 111 \\ 0000010 & 011 \\ 0000100 & 101 \\ 0001000 & 110 \\ 0010000 & 001 \\ 0100000 & 010 \\ 1000000 & 100 \\ \end{array} \] \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Codewörter} Jetzt mssen wir nur noch die die Codewörter ihren Datenwörtern zuordnen. Das ist aber einfach, denn wenn wir die Generatormatrix betrachten sehen wir dass die ersten 4 Bit des Codeworts das Datenwort sind. Es reicht also die letzten drei Bit abzuschneiden.\\ Jetzt haben wir alles um den Algorithmus anzuwenden. \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Codierung} Nehmen wir uns ein Datenwort z.B. $x=0110$. Als erstes codieren wir das Datenwort durch Multiplikation mit der Generatormatrix. \[ \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}\right) \cdot \left( \begin{array}{c} 0\\1\\1\\0 \end{array} \right) = \left( \begin{array}{c} 0\\1\\1\\0\\0\\1\\0 \end{array} \right) \] \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Übertragung} Wenn jetzt bei der Übertragung ein Fehler passiert und aus dem Codewort z.B. $ \left( \begin{array}{c} 1\\1\\1\\0\\0\\1\\0 \end{array} \right) $ wird \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Decodierung I} ergibt die Multiplikation mit der Kontrollmatrix $ \left( \begin{array}{ccccccc} 1 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 & 1 & 1\\ \end{array} \right) \cdot \left( \begin{array}{c} 1\\ 1\\ 1\\ 0\\ 0\\ 1\\ 0\\ \end{array} \right) = $\\ $ \left( \begin{array}{c} 1 + 0 + 0 + 0 + 0 + 0 + 0\\ 0 + 1 + 0 + 0 + 0 + 1 + 0\\ 0 + 0 + 1 + 0 + 0 + 1 + 0\\ \end{array} \right) = \left( \begin{array}{c} 1\\ 0\\ 0\\ \end{array} \right) $ \end{frame} \begin{frame} \frametitle{vollständiges Beispiel : Decodierung II} Dadurch erhalten wir den Fehlervektor $ \left( \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{array} \right) $ und $\left( \begin{array}{c} 1\\ 1\\ 1\\ 0\\ 0\\ 1\\ 0\\ \end{array} \right) + \left( \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{array} \right) = \left( \begin{array}{c} 0\\ 1\\ 1\\ 0\\ 0\\ 1\\ 0\\ \end{array} \right) . $ Das Datenwort ist demnach $ \left( \begin{array}{c} 0\\ 1\\ 1\\ 0\\ \end{array} \right) $ was korrekt ist. Die Korrektur funktioniert also. \end{frame} \end{document}