TIL How to Choose Sources of Fullfillment

Einführung in die Technische Informatik Prof. Dr.-Ing. Dirk Koch dirk.koch@ziti.uni-heidelberg.de Basiert auf Material von Prof. Ulrich Brüning, Prof. Hans-Martin Lipp, Prof. Jürgen Becker, Prof. Jürgen Teich, Prof. Daniel Ziener, Prof. Franz J. Hauck, Prof. Dr. Klaus Merle, … Nachricht und Signal Kapitel 2 2 Information und Nachricht • Information ist ungeachtet seines häufigen Gebrauchs nicht formal definiert, jedoch der Gemeinsprache als Kenntnis über reale oder gedankliche Sachverhalte und Vorgänge bekannt • Beispiel: unterschiedliche Interpretation derselben Nachricht wichtig: Kontext der Information „Herr Maier ist geflogen” Kündigung Sehr geehrter Herr Maier, die von Ihnen beschaffte EDV-Anlage CVK7.5 hat errechnet, daß bereits 10% ihrer Leistung ausgereicht hätten, um Ihre Arbeitskraft voll zu ersetzen. CVK7.5 bedauert deshalb, Ihnen mitteilen zu müssen, daß mit der Übernahme der Betriebsführung zum 01.01.2001 durch CVK7.5 … Information und Nachricht Definitionen: Nachricht und Daten • Nachricht (DIN ISO/IEC 2382): Gebilde aus Zeichen oder kontinuierlichen Funktionen, die aufgrund bekannter und unterstellter Abmachungen Information darstellen und die vorrangig zum Zweck der Weitergabe als zusammengehörig angesehen und deshalb als Einheit betrachtet werden. • Daten: Gebilde aus Zeichen oder kontinuierlichen Funktionen, die aufgrund bekannter oder unterstellter Abmachungen Information darstellen, vorrangig zum Zweck der Verarbeitung oder als deren Ergebnis. • Achtung: Daten können Informationen darstellen sind selbst aber keine Informationen. 3 Information und Nachricht Definitionen: • Zeichen: ein Element aus einer endlichen Menge von Objekten • Zeichenvorrat (Alphabet): zur Darstellung von Information vereinbart – Morsezeichen ‘-‘ { – , · , } – Morsealphabet ‘-…’ {.-, -…, -.-., …, –.. } – Buchstaben ‘G’ {A, B, C, … , Z} – Ziffern ‘4’ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} – Beliebiger Zeichensatz ‘’ {,  , , , } – Verkehrszeichen … – und ja – Emojis ‘’ {, , } – vielfältige weitere Beispiele für “Zeichen” und “Alphabete ” 4 Information und Nachricht Definitionen: • Symbol: ein Zeichen (oder eine Zeichenfolge) wird als Symbol bezeichnet, wenn ihm in der gegebenen Situation eine bestimmte Bedeutung zugeordnet ist -> Beispiele für Symbole und Ihre Zuordnung in jeweiliger Situation , , , – Spielkarten: – Schalt-„Zeichen”: – Elektroherd: – Kühlschrank: – mathematische Symbole: + , – , . , / , =  ♣, ♠, ♥, ♦ 5 Physikalische Größen als Nachrichtenträger • Technische Darstellung von Information / Nachrichten / Daten  Notwendigkeit eines Trägers, meist physikalischer Natur  Aufprägen einer Nachricht: Veränderungen charakteristische Parameter Physikalische Größe Veränderbarer Parameter Spannung, Strom Amplitude, Frequenz, Phasenlage Widerstand Widerstandswert Gewicht Betrag Reflexionsfähigkeit Reflexionsfaktor Durchlässigkeit Transmissionsfaktor 6 Kontinuierliche und diskrete Signale Typen von Signalen: • Theoretisch:  kontinuierliches Signal physikalisch + messtechnisch nicht realisierbar  zeitdiskretes, wertkontinuierliches Signal -> diskrete Abtastzeitpunkte W W 7 Kontinuierliche und diskrete Signale Typen von Signalen:  zeitkontinuierliches, wertdiskretes Signal Bsp.: Quantisierungseffekte  zeitdiskretes, wertdiskretes Signal:  digitales Signal Digitaltechnik: Einschränkung der Zahl möglicher Werte (Intervalle) W W 8 Signale mit begrenzter Zahl von Werten • In der Digitaltechnik: Einschränkung der Anzahl der Werte für Signale  preiswerte und zuverlässige technische Lösung • Ein Digitalwert repräsentiert dann ein Intervall an Werten Maximalwert physikalische Größe Minimalwert I 4 I 4 I 5 I 6 I 3 I 3 I 2 I 1 Problem: exakte (“harte“) Diskrimination an Intervallgrenzen 9 Signale mit begrenzter Zahl von Werten • Problem: Intervallübergänge Trick: jeweils zwischen 2 Intervallen undefinierte Bereiche einfügen • Zuordnungsproblem mit technisch einfachen Mitteln lösbar • Undefinierte Bereiche -> Digitalwertzuordnung “willkürlich“ undefinierter Bereich I 4 I 3 Besser: “weiche“ Diskrimination 10 Maxim alwert physikalische Größe H igh-Interv all, H U ndef inierter Bereich Low-Interv all, L Minim alwe rt T echnische Lö sung TT L-T echnik V.24-Schnittstelle Schalter T ransmissionsfa ktor L-Bereich 0 … 0,8 V -12 .. -3 V niederohmig 0 .. 40 % H-Bereich 2,0 … 5 V 3 … 12 V hochohmig 70 … 100% Binärsignale • Signaldarstellung mit der geringsten Digitalwertezahl (nämlich zwei) • Die Realisierung zugehöriger technischer Lösungen ist besonders einfach • Die beiden Intervalle werden üblicherweise mit H bzw. L benannt 11 Binärsignale • Oder man diskriminiert mit einer Hysterese „eine Änderung der Ursache erzeugt verzögert eine Änderung der Wirkung“ • Beispiel  Horizontal: Ursache (Eingang)  Vertikal: Wirkung (Ausgabe)  Starte bei ABC (Neukurve)  Dann E…LEF…  Ursache: Temperatur  Wirkung: an (heizen) oder aus 12 Temperatur (heizen) aus an Bsp.: Temperaturregelung bei einem Bügeleisen Binärsignale • Binärregelung (Zweipunkregelung) eines Bügeleisens 13 Binärsignale • Abtasten mit Hysterese (keine Änderung des Zustandes im Hysterese-Fenster) 14 Binärsignale 15 • Signaldarstellung: Auswahl aus zwei Werten -> elementarste Entscheidungsmöglichkeit • Ein Binärsignal enthält eine Information von 1 Bit (engl. bit: binary digit) • Abstraktion von technischer Darstellung: -> Alternativen häufig mit “0“ bzw. “1“ bezeichnet • Ein Binärsignal zur Informationsdarstellung nicht ausreichend -> Zusammengesetzte Repräsentationen aus mehreren Binärsignalen werden verwendet -> weitergehende kombinatorische Möglichkeiten • Binärsignal: x  {L,H}: Binärvektoren X = (xn, … , x1) Binärsignale 16 1 2 3 4 … n L LL LLL LLLL LL…LLLL H LH LLH LLLH LL…LLLH HL LHL LLHL LL…LLHL 2 HH LHH LLHH LL…LLHH HLL LHLL LL…LHLL HLH LHLH LL…LHLH HHL LHHL LL…LHHL HHH LHHH LL…LHHH HLLL LL…HLLL HLLH LL…HLLH HLHL LL…HLHL HLHH LL…HLHH HHLL LL…HHLL HHLH LL…HHLH HHHL LL…HHHL HHHH LL…HHHH HH…HHHL HH…HHHH Zahl der möglichen Wertekombinationen Zahl der Binärsignale 2 . 2 = 4 2 . 2 . 2 =8 2 . 2 . 2 . 2 = 16 2 . 2 . … . 2 = 2 n Binärsignale 17 • Mit n Binärstellen lassen sich also 2n unterschiedliche Kombinationen bilden • Anzahl Binärsignale zur Darstellung von N Werten (Zeichen) -> inverse Funktion: • Weiterhin: Berücksichtigung, dass nur ganzzahlige Anzahl Bits zur Darstellung von Binärsignalen möglich sind Darstellung von N Werten: Bits werden benötigt n  log2 N  ldN n  ld N  ln 2 ln log log log log 2 x x a x x b b a    Einführung in die Technische Informatik Prof. Dr.-Ing. Dirk Koch dirk.koch@ziti.uni-heidelberg.de Basiert auf Material von Prof. Ulrich Brüning, Prof. Hans-Martin Lipp, Prof. Jürgen Becker, Prof. Jürgen Teich, Prof. Daniel Ziener, Prof. Franz J. Hauck, Prof. Dr. Klaus Merle, … Informationsgehalt Informationsgehalt 19 • Neben Darstellung von Zeichen: -> Aussage über Informationsgehalt eines Zeichens interessant -> Zeichen quantitativ im Vergleich zu anderen Zeichen oder im Hinblick auf technischen Darstellungsaufwand zu bewerten (wieviel Bits brauchen wir zum Speichern?) • Ermittlung des Informationsgehalts He eines Zeichens e • Annahme: ein Zeichen trägt umso mehr Information, je seltener es beim Empfänger eintrifft! • Also: Informationsgehalt He eines Zeichens steigt mit abnehmender Auftrittswahrscheinlichkeit p dieses Zeichens Informationsgehalt 20 • Definition: Informationsgehalt eines Zeichens e • Die Einheit entspricht, wie beim Binärsignal bereits einführt: 1 Bit • Also: Einheit entspricht der elementaren Entscheidung zwischen zwei gleichwahrscheinlichen Möglichkeiten -> p = 0,5 • Voraussetzung: Beobachtete Zeichen voneinander unabhängig p He ld 1  ln 2 ln log log log log 2 x x a x x b b a    Informationsgehalt 21 Beispiele: gleich- bzw. ungleichwahrscheinliche Symbole   p=1/4 p=1/4 p=1/4 p=1/4 H He = 2 bit e = 2 bit He = 2 bit p=1/8 p=7/8 “As” “kein As” He = 3 bit He = 0,2 bit Voraussetzung: Kartenspiel mit 32 Karten ♦ ♣ ln 2 ln log log log log 2 x x a x x b b a    Informationsgehalt 22 • Betrachtung nichtgleichwahrscheinlicher Zeichen: • Frage: -Informationsgehalt eines Zeichens in einer Zeichenfolge • Voraussetzung: Alphabet mit N Zeichen • Es gilt: (die Summe Auftrittswahrscheinlichkeit eines jeden Zeichens i) • In einer Folge mit L Zeichen ist die zu erwartende Häufigkeit eines speziellen Zeichens i: L p(i)   1 1    N i p i Informationsgehalt 23 • Alle beobachteten Zeichen vom Typ i liefern insgesamt den Informationsgehalt • Alle N Zeichen zusammen betrachtet: Informationsgehalt pro Zeichen: • Man nennt H Entropie der Quelle • Weitere quantitative informationstheoretische Betrachtungen -> moderne Informationstheorie (C. Shannon)     pi L p i Hei L p i ld 1        pi H p i ld N i 1 1     Optimale Codes 24  Der Morse-Code hat die statistischen Eigenschaften der (englischen) Sprache ausgenutzt, um eine möglichst kurze Darstellung der Nachricht zu erzielen  Häufig auftretende Buchstaben werden möglichst kurzen Codewörtern zugeordnet, während für seltene Buchstaben längere Codewörter gewählt werden  Wie können wir diesen Trick in Computern nutzen? Optimale Codes 25  Optimale Codes versuchen die im Mittel auftretende durchschnittliche Codewortlänge zu minimieren  Der minimal erreichbare Idealwert ist dabei der durchschnittliche Informationsgehalt H des Zeichenvorrats  Entropie der Sendequelle  Für einen Zeichenvorrat {x1, x2, x3, … xn} gilt: m         n i i i n i i e i p x H p x H x p x ld 1 1 ( ) 1 ( ) ( ) ( )    n i i i m p x m x 1 ( ) ( )  Informationsgehalt H:  Codewortlänge : m(xi ): Länge CW für xi m Hatten wir gerade: Optimale Codes – Huffman Code 26  Effiziente Codierungstechnik für Datenkompression • JPEG • MPEG • ZIP (und vieles mehr)  Codierung mit variabler Bitlänge der Codewörter • effizienter als Codierung mit fester Bitlänge  Präfixfreie-Codierung • kein Codewort ist Präfix eines anderen Codewortes  Vorgehesweise Huffmann-Codierung: Greedy-Algorithmus (greedy=“gierig”) Optimale Codes – Huffman Code 27 • präfix-freier Code • Bedingung: Häufigkeit des Auftretens aller Zeichen ist bekannt • Ziel: häufiger auftretende Zeichen werden kürzer codiert als seltenere • Arbeitsweise: 1. Auflisten alle Zeichen nach ihrer Häufigkeit (bilden Blätter in einem Baum) 2. Wähle die zwei Blätter mit den geringsten Häufigkeiten 3. Mache sie zu Knoten eines binären Teilbaumes, wobei die Häufigkeiten für beiden Blätter/Knoten addiert werden 4. Füge den Teilbaum statt der Blätter/Knoten wieder in die Liste ein 5. Wiederhole Schritte 2 bis 4, bis nur ein Baum vorhanden ist 6. Markiere alle Kanten: – Vater → linker Sohn mit ‘0’ – Vater → rechter Sohn mit ‘1’ 7. Das Codewort ergibt sich aus dem Pfad von der Wurzel zum Blatt Optimale Codes – Huffman Code (Beispiel) 28 (a) Bilde Häufigkeiten (und sortiere Blätter) f:5 e:9 c:12 b:13 d:16 a:45 beafadababcdaacddbabebadaadaacdadcadaaebabfaadaacc eadacadaefaabaeadaaaeaadacaceadeacabacabffabdabaca Optimale Codes – Huffman Code (Beispiel) 29 (a) f:5 e:9 c:12 b:13 d:16 a:45 (b) (c) f:5 e:9 c:12 b:13 14 d:16 a:45 0 1 f:5 e:9 14 d:16 a:45 c:12 b:13 25 0 1 0 1 beafadababcdaacddbabebadaadaacdadcadaaebabfaadaacc eadacadaefaabaeadaaaeaadacaceadeacabacabffabdabaca 30 (d) (e) f:5 e:9 a:45 c:12 b:13 14 d:16 25 30 55 0 0 0 0 1 1 1 1 f:5 e:9 a:45 c:12 b:13 14 d:16 25 30 0 0 0 1 1 1 Optimale Codes – Huffman Code 31 (f) f:5 e:9 a:45 c:12 b:13 14 d:16 25 30 55 100 1 1 1 1 1 0 0 0 0 0 f 1100 e 1101 d 111 c 100 b 101 a 0 Symbol Code Präfixfreier Code: Kein Codewort stellt den Beginn eines anderen Codewortes dar Optimale Codes – Huffman Code 32 (f) f:5 e:9 a:45 c:12 b:13 14 d:16 25 30 55 100 1 1 1 1 1 0 0 0 0 0 1100 1101 111 100 101 0 Code 4 4 3 3 3 1 m f 5×4=20 e 9×4=36 d 16×3=48 c 12*3=36 b 13×3=39 a 45×1=45 Symbol Komprimieren: abeef  0101110111011100 Dekomprimieren: 010110011111011100  abcdef Man startet immer von der Wurzel und traversiert den Graphen bis man ein Blatt erreicht. Das zeigt uns das Zeichenende an und wir fangen wieder mit dem nächsten Bit bei der Wurzel an. ( ) ( ) i i p x  m x Σ=224 Optimale Codes – Huffman Code (Algorithmus) 33 begin n  |C|; // C ist sortierte Menge der zu codierenden Elemente Q  C; // Q ist sortierte Liste (-> verwendete Datenstruktur) for i 1 to n-1 do z  ALLOCATE-NODE(); // Erstellung eines neuen Knotens z im Codierbaum x  EXTRACT-MIN(Q); // Bestimme Knoten minimaler Auftrittshäufigkeit (AH) in Q, entferne diesen aus Q und speichere ihn in x y  EXTRACT-MIN(Q); // Bestimme Knoten minimaler AH in Q, entferne diesen aus Q und speichere ihn in Y left[z]  x; // Knoten x wird linker Nachfolgeknoten von z im Codierbaum right[z]  y; // Knoten y wird rechter Nachfolgeknoten von z im Codierbaum f[z]  f[x] + f[y]; // Bestimmung der AH des vereinten Knotens z INSERT(Q, z); // neuer Knoten z wird in Q (= Codierbaum) entsprechend seiner AH end; return EXTRACT-MIN(Q); // letztes verbleibendes Listenelement in Q (= Wurzel des Codierbaums) wird als Endergebnis ausgegeben end Code wird nicht in der Klausur gefragt! Optimale Codes 34 • Baum kann statisch oder dynamisch verwendet werden • Statisch: Codierung ist fest vorgegeben (macht bei Text sinn) • Dynamisch: Der Baum wird zur Kompressionszeit erzeugt und mit zum Empfänger geschickt • Huffman ist nicht optimal  Wir diskretisieren die Anzahl der verwendeten Bits (dieses spiegelt nicht immer exakt die Auftrittswahrscheinlichkeit wieder)  die mittlere Codewortlänge kann 1 Bit länger sein als die Entropie • Lösung: Arithmetischer Kodierer (wird in JPEG2000 genutzt) Optimale Codes – Arithmetischer Kodierer (Idee) 35 a b c d • Aufteilen eines [0,1] Intervalls in rationale Teile nach Symbol-Auftrittswahrscheinlichkeit • Zum Kodieren „zoomen“ wir in den zuletzt gewählten Bereich rein dazu erzeugen wir immer mehr Genauigkeit (Bits) • Das Beispiel kodiert: acd a b c d a b c d Wird nicht in der Klausur gefragt! Lauflängenkodierung (engl.: Run Length Encoding, RLE) 36 • Viele Daten enthalten Läufe, d.h. Folgen identischer Zeichen (z.B. Farbwerte in einem Bild) • Idee: Folge identischer Zeichen durch (Anzahl, Zeichen) kodieren • Problem: – Unterscheidung der Anzahlangabe von Daten gleicher Repräsentierung  RLE kodiert Läufe beliebiger Zeichen typischerweise durch – [Zeichen, Marker, Anzahl] => sinnvoll nur bei Anzahl > 3 – Marker in Daten kodiert durch (Marker, Marker) • Beispiel: Marker: # – Daten „AAABBBBBBBCDDEEEEEEEEEEEF#34777777“ – kodiert: „AAAB#7CDDE#11F##347#6“ (komprimiert) • Vereinfachung in Sonderfällen möglich • z.B. bei 7-Bit-Zeichen ==> MSB-Bit als Markierung des Zählers • Kann mit Huffman kombiniert werden (Denken Sie Nach wie!) Wörterbuch-Kompression (Lempel-Ziv) 37 • Wörterbuch mit Tupeln (Phrase, Codewort) wird schrittweise erzeugt • Phrase: Folgen von Eingabezeichen • Erzeugte Codewörter enthalten Verweise in das Wörterbuch • Vorteile • adaptiv (selbstanpassend) • optimal, wenn Tabelle beliebig groß und Eingabe unendlich lang • Problem: Datenstruktur für das Wörterbuch • Tabelle, Baum, Hash-Funktion (keine Angst, das lernen Sie in anderen Veranstaltungen) • Verfahren: • LZ77 (Lempel, Ziv, 1977), neuere Varianten pkzip, gzip • LZ78 (Lempel, Ziv, 1978), Baum statt Tabelle als Basis • LZW (Lempel, Ziv, Welch 1984), komplexeres Tabellenverfahren, Basis von compress Wörterbuch-Kompression (Idee anhand von LZSS) 38 • Trick: wir merken uns die letzten dekomprimierten Symbole in einer Liste (engl. Dictionary) • Wir Kodieren entweder (entschieden durch ein führendes Bit): • Neues Zeichen: 0, Symbol • Referenz auf Liste: 1, Position, Länge • Beispiel: LZSS Kompression von BARBARA mit einer 4-Einträge tiefen Liste • Komprimieren ist schwieriger, da wir möglichst lange Referenzen in der Liste finden wollen. (Da gibt es aber Tricks die Sie in Algorithmen kennenlernen werden.) 3 2 1 0 0, ‘B’ B 0, ‘A’ 3 2 1 0 0, ‘R’ B A R B A 1, 2, 3 3 2 1 0 3 2 1 0 B A R B A R 0, ‘A’ 3 2 1 0 B A R B A R A B A R B A R A Einführung in die Technische Informatik Prof. Dr.-Ing. Dirk Koch dirk.koch@ziti.uni-heidelberg.de Basiert auf Material von Prof. Ulrich Brüning, Prof. Hans-Martin Lipp, Prof. Jürgen Becker, Prof. Jürgen Teich, Prof. Daniel Ziener, Prof. Franz J. Hauck, Prof. Dr. Klaus Merle, … Codierung Codewörter 40 Allgemein: Code ist Vorschrift für eindeutige Zuordnung (Codierung) Die Zuordnung muss nicht umkehrbar eindeutig sein Beispiel: Zuordnung von Zeichen verschiedener Alphabete Zeichenvorrat (Urmenge) anderer Zeichenvorrat (Bildmenge) Digitaltechnik: Abstraktion der Werte “L“ und “H“ durch Symbole “0“ und “1“ Beispiel Morsecode: ist nicht vollständig umkehrbar “.-“ wird für “a“ und “A“ benutzt Codewörter • Codewörter sind elementare Einheiten zur Darstellung von Informationen • Beispiel: • Anzahl möglicher Codewörter mit m Binärstellen: –Maximale Anzahl N von m-stelligen Codewörtern: –Anzahl strukturierter m-stelliger Codewörter mit k Einsen: m2 m N  2 !( )! ! k m k m k m          1100 4 1101 4 111 3 100 3 101 3 0 1 Codewort Anzahl Binärstellen Strukturierte Codes • Allgemein gilt: Codes legen fest, wie Codewörter zu interpretieren sind • Beispiel für einen strukturierten Code: Anzahl Wörter im 2-aus-5-Code: – m = 5 k = 2 – Folgende Codewörter sind möglich: • Der 2-aus-5-Code eignet sich besonders zur Darstellung von Dezimalziffern Beispiel: Strichcode (5 Striche, 3 schmal 2 breit) (Postleitzahlenkod.) • 2-aus-5-Code ist fehlererkennend 10 2!(5 2)! 5! 2 5           N  42 00110 01001 00011 00101 01010 01100 10001 10010 10100 11000 Codes für die Analog/Digital-Umsetzung • Wandlung von stetigen Signalen in zusammengesetzte Binärsignale • Beispiel Wage: 43 Aufgabe: Festlegung einer geeigneten Zuordnung: Stetiger Wertebereich  Binärer Wertebereich 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Feder Gewicht __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ Ablesefenster Analog/DigitalW andler Codes für die Analog/Digital-Umsetzung • Wandlung: stetige (analoge) Signale in Binärsignale (Binärvektoren) – Problem: Übergänge, bei denen sich mehr als eine Binärstelle ändert – Beispiel: 0 1 1    1 0 0 – Beim Wechsel müssen nicht alle Binärstellen gleichzeitig wechseln – Dadurch: große Abweichungen für Werte der Binärsignale möglich: 0 1 1    111, 001, 010, 101, 110 oder 000    1 0 0 44 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Feder Gewicht __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ Ablesefenster Analog/DigitalW andler (all diese Codierungen könnten beim Übergang abgetastet werden)  fehlerhafte Übergänge in andere Codewörter möglich Code-Eigenschaften: Hammingdistanz • Eigenschaften von/zwischen Codewörtern – Definition: Hammingdistanz HD (auch Hammingabstand genannt) Seien die Codewörter CWi , CWj  {0, 1}n , Hdij = Anzahl der Stellen, an denen sich CWi und CWj unterscheiden. Dann heißt Hdij die Hammingdistanz von CWi und CWj . – Also: Die Hammingdistanz HD zwischen zwei gleich langen Codewörtern gibt die Anzahl der unterschiedlichen Binärstellen an. • Beispiele: Bestimmung HD 011 100 HD = 3 1000 1010 HD = 1 11000 00101 HD = 4 45 Code-Eigenschaften: Hammingdistanz – Definition: Minimale Hammingdistanz HDmin Sei X  {0, 1}n beliebig, und Hdmin(X) = min{ Hdij | CWi , CWj  X  CWi  CWj } Dann heißt Hdmin(X) minimale Hammingdistanz von X – Beispiel: Codewörter des (2 aus 5)-Codes haben folgende minimale Hammingdistanz: Hdmin(2 aus 5) = 2 – Die minimale Hammingdistanz ist eine entscheidende Eigenschaft eines Codes, um Übertragungsfehler erkennen und korrigieren zu können Begriff: Einschrittige Codes – Codes, bei denen zwei benachbarte Codewörter immer eine Hammingdistanz von eins haben, heißen einschrittig. 46 00011 00101 01001 10001 00110 01010 10010 01100 10100 11000 Spezielle Codes: Gray-Code • Konstruktion des Gray-Codes – Geg.: Gray-Code mit m = x Binärstellen liegt vor – Doppelt so langen Gray-Code mit mneu = x+1 Binärstellen erzeugen:  in umgekehrter Reihenfolge an gegebenen Code anhängen (Spiegelung an der Horizontalen)  und zusätzliche Binärstelle anfügen (zuerst 2x+1/2 Nullen, dann 2x+1/2 Einsen) – Der Code ist zyklisch, wenn man von der mittleren Spiegelachse gleich viele Codewörter noch oben und unten nutzt 47 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1 Spezielle Codes: Austauschcodes • Notwendig: Datenaustausch zwischen digitalen Systemen:  spezielle Codes werden benötigt  Texte aus Buchstaben, Ziffern, Satzzeichen, Sonderzeichen (characters) übertragbar •ASCII-Code – Verbreitung: ASCII-Code (American Standard Code for Information Interchange) kodiert mit 7 Bit 128 Zeichen: reicht für englischen Sprachraum weitgehend aus – Bitgruppen werden zusammengefasst -> spezielle Bedeutung / Namen: •MSB (Most Significant Bits) bezeichnen 3 höherwertigen Bits •LSB (Least Significant Bits) bezeichnen 4 niederwertigen Bits – Zuordnung: Zeichen  Codewort MSB teilen alle Zeichen in Gruppen zu je 16 Zeichen ein (lexikographische Anordnung von Zeichen + Codewörtern) 48 Spezielle Codes: ASCII-Code 49 LSB MSB Binär 000 001 010 011 100 101 110 111 Steuerzeichen Großbuchstaben Kleinbuchstaben 0000 NUL DLE SP 0 @ P ` p 0001 SOH DC1 ! 1 A Q a q 0010 STX DC2 „ 2 B R b r 0011 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 0101 ENQ NAK % 5 E U e u 0110 ACK SYN & 6 F V f v 0111 BEL ETB ´ 7 G W g w 1000 BS CAN ( 8 H X h x 1001 HT EM ) 9 I Y i y 1010 LF SUB * : J Z j z 1011 VT ESC + ; K [ k { 1100 FF FS , < L \ l | 1101 CR GS – = M ] m } 1110 SO RS . > N ^ n ~ 1111 SI US / ? O _ o DEL This may beep in your DOS box: echo x | tr ‘x’ ‘\007‘ Spezielle Codes: Austauschcodes Beispiel: ASCII-Codierung –Buchstabe “A“: A = 41H = 100 0001B (Bitgruppen analog zu Hexadezimalsystem (später!)) –Praxis: verschiedene 8, 16 und sogar 32 Bit Codes in Gebrauch  Spezialzeichen verschiedener Sprachen darstellbar –Weitere Beispiele: – verbreitester Austauschcode ist der UNICODE  65536 (und mehr) Zeichen darstellbar  ASCII-Code: erste 128 Zeichen des UNICODES  enthält Erweiterungen für viele Sprachen – 7-Segment-Code: digitale Ziffernanzeige, etc. – Punktmatrixanzeigen: Drucker, etc. – OCR-Code (Optical Character Recognition): Maschinenlesbarkeit – Blindenschrift, Thermometercode, etc. 50 MSB LSB VT100 51 • ASCII-Computer-Terminal • Eines der ersten Computerterminals, welches ANSIEscape-Sequenzen zur Steuerung des Cursors benutzt hat • War sehr weit verbreitet • Standard wird auch heute noch verwendet https://en.wikipedia.org/wiki/ ANSI_escape_code Wird nicht in der Klausur gefragt! BCD-Codierung • Binärdarstellung der 10 Dezimalziffern (z.B. Tastatur-Eingabe) • Zur Codierung der 10 Ziffern werden Bit benötigt, d.h. Tetraden ==> Tetradenkodierung • 6 der 16 möglichen Kodierungen stellen keine gültigen Dezimalziffern dar (Pseudotetraden),  BCD-Code nicht dicht Kodierung der Dezimalziffern durch Dual-Äquivalent: BCD (Binary Coded Decimal)-Codierung Beispiel: Dezimalzahl 812710  als BCD-Zahl: 1000 0001 0010 0111BCD  als Dualzahl: 0001 1111 1011 11112 • Vorteil: Zahlen leicht zu lesen • Nachteile:  nicht-optimale Speicherplatz-Nutzung  Probleme bei Ausführung arithmetischer Operationen 52 log 2 10  4 • Block -Code: • jedes Codewort nutzt gleich viele Bits (n-stelliger) Block-Code • n-stelliger Block-Code ist dicht, wenn alle b ∈ B n Codew örter genutzt werden • Beispiel : Hexadezimalsystem (HEX Code) 4 Bits dargestellt durch das Alphabet { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F } • Ein Hex Zeichen (4 Bits) wird auch Nibble genannt • Sehr gut lesbar (engl. human readable) • Spezielle Editoren (Hex-Editor) Block -Codes 53 Fano-Bedingung • Wichtig: sofort decodierbare Codes, d.h. Zeichenfolgen aus Codeworten können, von vorne beginnend, eindeutig Wort für Wort decodiert werden, ohne nachfolgende Zeichen zu beachten • Codes sind sofort dekodierbar, wenn Fano-Bedingung erfüllt: Kein Codewort ist Präfix (Anfangsstück) eines anderen Codeworts • bedeutet: zu codierende Zeichen treten im Codebaum nur als Blätter auf • Codes mit erfüllter Fano-Bedingung heißen auch präfixfrei • Jeder Blockcode der Länge n erfüllt Fano-Bedingung automatisch: Zur Dekodierung jeweils Blöcke von n Codezeichen gebildet u. Dekodiert Beispiel: BCD-Kodierung der dezimalen Ziffern in Tetraden • Beispiel: C = {0, 10, 011, 11111} ist eindeutiger Code, aber nicht sofort decodierbar Beispiel Quellcodierung: PCM und PWM • Pulscodemodulation PCM • Pulsbreitenmodulation PWM (engl. Pulse-width modulation) • Umwandlung zwischen analogen und digitalen Signalen (z.B. Audio) • Abtasttheorem (Nyquist): Abtastrate: min. 2 x Grenzfrequenz des Ursprungssignals Codes für serielle Übertragung • Problem: der Empfänger muss den Zeitpunkt zum Abtasten der zu empfangenden Bits erkennen • Sequentiell mit Start-/Stopbit; Bsp. RS232 (sehr weit verbreitet da einfach): • Extra Übertragung eines Taktes (Bsp. SPI – u.A. in Speicherkarten, auch I2C): (sehr robust, benötigt Takt der doppelt so schnell sein muss wie die Daten) Start ‘0’ d0 d1 d2 d3 d4 d5 d6 d7 P (parity) Stop ‘1’ TX (send) i7 i6 i5 i4 i3 i2 i1 i0 d7 d6 d5 d4 d3 d2 d1 d0 SS (enable) SCK MISO (data) Befehl Daten Details werden nicht in der Klausur gefragt! 56 Codes für serielle Übertragung • Codierung von Clock und Daten in ein Signal (Biphase-Modulation, Manchester Coding), Beispiel S/PDIF (Audio): (robust und benötigt nur eine Leitung; Problem: Signalwechsel schneller als Daten) • 8b-10b Code: kodiere 8-Bit Wörter als 10-Bit Symbole (viele Varianten)  verhindere lange Läufe von aufeinanderfolgenden 0 oder 1  erzwingt Signaländerungen die zur Synchronisation genutzt werden Besispiele 8b-10b in SATA, 128b-130b Variante in PCIe 3.0 (sehr effizient) Details werden nicht in der Klausur gefragt! 1 0 0 1 1 0 1 0 clock data encoded always toggle between bits if data is ‘1’, then toggle in the middle of the bit window Einführung in die Technische Informatik Prof. Dr.-Ing. Dirk Koch dirk.koch@ziti.uni-heidelberg.de Basiert auf Material von Prof. Ulrich Brüning, Prof. Hans-Martin Lipp, Prof. Jürgen Becker, Prof. Jürgen Teich, Prof. Daniel Ziener, Prof. Franz J. Hauck, Prof. Dr. Klaus Merle, … Codes für Fehlererkennung / Fehlerkorrektur Codes für Fehlererkennung / -korrektur  Geeignete Codes können Fehler erkennen und sogar korrigieren  Notwendig: Hinzufügen zusätzlicher (redundanter) Informationen  zusätzlicher Darstellungsaufwand (Kosten!) Annahme: Höchstanzahl gleichzeitig zu berücksichtigender Fehler ist fest meistens: höchstens 1 oder 2 Bitfehler gleichzeitig  (Teil-)Systematik bei Festlegung des Codes notwendig Möglichkeiten: minimale Hammingdistanz, Paritätsbits, Blocksicherungsverfahren, Hamming-Codes, etc. Paritätsbit-Prüfverfahren:  Fehler bei Code-Übertragung erkennbar  zusätzliches Paritätsbit anhängen: – im Binärwort enthaltene Einsen werden entweder auf gerade (even parity) oder ungerade (odd parity) Anzahl ergänzt  Überprüfung beim Empfänger 59 Beispiel: Ergänzung des Paritätsbit • Gerade Parität: Paritätsbit ergänzt Gesamtzahl an 1-er zu einer geraden Anzahl • Ungerade Parität entsprechend ungerade Anzahl an 1-er Dezimal Binär gerade Parität ungerade Parität 0 0000 0000 0 0000 1 1 0001 0001 1 0001 0 2 0010 0010 1 0010 0 3 0011 0011 0 0011 1 4 0100 0100 1 0100 0 5 0101 0101 0 0101 1 6 0110 0110 0 0110 1 7 0111 0111 1 0111 0 8 1000 1000 1 1000 0 9 1001 1001 0 1001 1 Fehler: 1001 1011 0 1011 1 Fehlererkennung durch Parität  Das Prinzip der Paritätssicherung ist zweidimensional anwendbar  Blocksicherungsverfahren mit doppelter Quersummenergänzung  Nachricht wird in Blöcke von n Codewörtern mit Paritätsbit eingeteilt zusätzlich: am Ende jedes Blocks ein weiteres Codewort einfügen  enthält alle Paritätsbits der Spalten  Also: bei Auftreten von Einfachfehlern lassen sich Spalte und Zeile eindeutig ermitteln:  Einfachfehler sind damit korrigierbar  gleichzeitig sind noch weitergehende Fehlererkennungsverfahren möglich: Bündelstörung erkennbar  Bündelstörung: zeitlich konzentrierte Fehler, d.h. über einen Zeitraum ist die Verbindung gestört, können erkannt bzw. behoben werden Fehlerkorrektur durch Blocksicherung 61 • Berechne für jede Zeile und Spalte Prüfbits (Quersummen) • Übertrage Prüfbits zusammen (zusätzlich) mit dem Datenblock • Berechne Prüfbits auf der Empfangsseite und vergleiche mit empfangenen Prüfbits (Unterschiede zeigen Fehler an) Fehlerkorrektur durch Blocksicherung 0 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 gesendete Bitfolge Quersumme der Spalten Quersumme der Zeilen Fehler Fehler empfangene Bitfolge Fragen • Wie skaliert dieses Verfahren? • Ist es eine gute Idee besonders große Blöcke zu sichern? Übertragung und Speicherung von Nachrichten und Daten 63 • Spezielle Anforderungen an Codierung • Darstellungsaufwand minimieren (Kosten, Performanz)  hatten wir gerade behandelt • Schutz gegen Verfälschungen + typische Fehlerfälle • Weiteres Problem: Annahme des Einzelfehlerfalls trifft häufig in Übertragungssystemen nicht zu  zeitlich konzentrierte Fehler (Störung über einen Zeitraum)  Bündelstörungen treten auf • Konsequenz: dedizierte zusätzliche Maßnahmen notwendig Bündelstörung 64 •Problem: häufig eine längere Auswirkung einer Störung auf ein Signal (wenn z.B. unser Übertragungssystem einen kurzen Aussetzer hat) •Dadurch können mehrere Bits nacheinander gestört werden •Bündelfehler: bisher besprochene Codes sind nicht geeignet •Lösung: Bei der Zeichenverflechtung werden die Binärstellen eines Zeichens (Binärwort) nicht nacheinander übertragen sondern durch  Verwürfelung oder Scrambling der Stellen •Also: länger anhaltender Störeinfluss (Bündelstörung) bestimmter Länge verfälscht nur Binärstellen von unterschiedlichen Codewörtern • Unterscheidung abhängig von Lage und Menge fehlerhaft empfangener Bits:  Bitfehler, Burstfehler und Symbolfehler können innerhalb des übertragenen Bitstroms auftreten • Hängt vom konkreten Anwendungsfall ab  Festplatte, SSD, Ethernet (Netzwerk), Radio-Verbindung Fehlerraten, aber auch welche Fehler können toleriert werden (Bsp. Audio) gesendeter Bitstrom empfangener Bitstrom Bit Symbol Bitfehler 3-bitBurstfehler 5-bitBurstfehler 4-bitBurstfehler fehlerfrei empfangenes Bit fehlerhaft empfangenes Bit Fehlermuster 65 Bündelstörung: Zeichenverflechtung 66 • Geänderte Reihenfolge der Übertragung: a1 a2 a3 a4 a5 a6 a7 Codewort 1 b1 b2 b3 b4 b5 b6 b7 Codewort 2 c1 c2 c3 c4 c5 c6 c7 Codewort 3 d1 d2 d3 d4 d5 d6 d7 Codewort 4 e1 e2 e3 e4 e5 e6 e7 Codewort 5 Paritätsbit • Gesendete Folge: a1, b1, c1, d1, e1, a2, b2, … • Dadurch sind Bündelfehler bis zur Anzahl der Prüfbits erkennbar (hier d2, e2, a3, b3, c3) Hamming-Distanz • Welche Hamming-Distanz ist erforderlich um eine geforderte Anzahl von Fehlern erkennen, bzw. korrigieren zu können?  Satz: HDmin <-> Anzahl erkennbarer / korrigierbarer Fehler a.) Sei X  {0, 1}n ein Code mit HDmin(X) = d Dann sind bis zu (d –1)-Fehler erkennbar! b.) Sei HDmin(X) = d = 2e + 1 Dann sind bis zu e = ((d – 1) / 2)-Fehler korrigierbar! 67 Hamming-Distanz • Beweis: a.) Sei X  {0, 1}n ein Code mit HDmin(X) = d Dann sind bis zu (d –1)-Fehler erkennbar! Bei bis zu (d – 1) gleichzeitigen Fehlern ist man sicher, dass kein gültiges Codewort vorliegt, da alle gültigen Codewörter mindestens Hammingdistanz d haben per Definition. 68 Hamming-Distanz • Beweis: b.) Sei HDmin(X) = d = 2e + 1 Dann sind bis zu e = ((d – 1) / 2)-Fehler korrigierbar! Zu b.): Jedes empfangene Codewort CWi mit höchstens e´ (<=e) Fehlern unterscheidet sich vom gesendeten Codewort CWj an höchstens e´ Stellen, d.h. von jedem anderen gültigen Codewort CWk  X unterscheidet sich CWi an mindestens (2e + 1) – e´ >= 2e´ + 1 – e´ = e´+ 1 Binärstellen Also: HDik >= e´+ 1, d.h. das ursprünglich gesendete Codewort CWj ist eindeutig aus dem empfangenen (ggf. fehlerhaften) CWi zuzuordnen! 69 Hamming-Distanz • Beispiel 1: HDmin(X)=3 2-Fehler erkennen Achtung: die beiden Möglichkeiten sind alternativ! 000 111 001 011 Fehler Fehler Korrektur Korrektur Korrekturgrenze 000 111 001 011 Fehler Fehler Erkennungsgrenze Erkennungsgrenze Fehler Fehler 000 010 001 011 111 110 100 x1 x3 x2 101 Es sei angenommen, dass wir nur die Wörter 000 und 111 nutzen. oder 1-Fehler korrigieren 70 Hamming-Distanz • Beispiel 2: HDmin(X)=6 Variante I: 5-Fehler erkennen Variante II: 1-Fehler korrigieren und bis zu 4-Fehler erkennen 000000 Fehler Fehler Fehler Fehler Fehler 111111 Fehler Fehler Fehler Fehler Fehler 000001 000011 000111 001111 011111 Erkennungsgrenze Erkennungsgrenze 000000 Fehler Fehler Fehler Fehler 111111 Fehler Fehler Fehler Fehler Korrektur 000001 000011 000111 001111 011111 Erkennungsgrenze Erkennungsgrenze Korrektur 71 Hamming-Distanz Achtung: die drei Varianten sind alternativ! Variante III: 2-Fehler korrigieren und bis zu 3-Fehler erkennen 000000 Fehler Fehler Fehler 111111 Fehler Fehler Fehler Korrektur 000001 000011 000111 001111 011111 Korrektur Erkennungsgrenze Erkennungsgrenze • Beispiel 2: HDmin(X)=6 72 • Erhöhung der min. Hamming-Distanz durch Paritätsbildung Bsp: 001100 1 0 001001 1 0 001100 001001 Erhöhung des Hamming-Abstandes 001100 1 001101 0 • Problem: Das Verfahren ist nicht trivial durch weitere Prüfstellen erweiterbar! Bsp: 001100 001101 Hier keine Erhöhung des Hamming-Abstandes durch zusätzliche Prüfbits! 73 • Trick: Generiere Prüfsummen nur auf Teilwörter. • Beispiel: Die 4 Bit Binärzahl X=(x4, x3, x2, x1) soll durch den Prüfvektor Y=(y3, y2, y1) 1-Fehler korrigierbar gemacht werden. [HDmin(X)=3] Fehlerkorrektur Prüfbitgenerator Kanal Fehlerkorrektur X (X,Y) (X’,Y’) X 74 x1 x2 x3 x4 X Y y1 = x1 x2 x4 y2 = x1 x3 x4 y3 = x2 x3 x4 Fehlerkorrektur Prüfbitgenerator Kanal Fehlerkorrektur X (X,Y) (X’,Y’) X 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 y1 x4 x2 x1 Prüfbitgenerierung Fehlerkorrektur y1 y3 y2 x4 x1 x3 x2 Überdeckung der Stellen xi durch Prüfbits • Jedes Element xi wird durch eine eindeutige Kombination von Prüfbits gesichert. • Beispiel: ein Einzelfehler an der Stelle x1 verändert genau die Prüfbits y1 und y2. • Einzelfehler von Prüfbits sind erkennbar. (Das empfangene Codewort X ist weiterhin gültig.) y1 = x4 x2 x1 y2 = x4 x3 x1 y3 = x4 x3 x2       76 x’1 x’2 x’3 x’4 y*2 y*1 y*3 X y*=y’ y*=y’ y*=y’ y’1 y’2 y’3 Vergleiche berechnetes Prüfbit mit dem Übertragenen Korr. Korr. Korr. Korr. y1 y3 y2 x4 x1 x3 x2 y1 y3 y2 x1 x3 x2 Fehlerkorrektur Prüfbitgenerator Kanal Fehlerkorrektur X (X,Y) (X’,Y’) X Prüfbitgenerator Kanal Fehlerkorrektur X (X,Y) (X’,Y’) X Fehlerkorrektur x4 x3 x2 x1= 1 0 0 1 (X,Y) = (1 0 0 1, 1 0 0) (X‘ ,Y‘) = (1 0 0 0, 1 0 0) Y* (1 0 0 0) = 1 1 1 Vergleich: y * 3 y * 2 y * 1 = 1 1 1 y‘ 3 y‘ 2 y‘ 1 = 1 0 0 y1 y3 y2 x4 x1 x3 x2 Änderung von y * 2 und y * 1 ist Indikator für den Fehler an Stelle x1, also X = 1 0 0 1. 78 Zuordnung der Informationsstellen xi zu den Prüfstellen yj • Die Stellen xi und yj lassen sich gemeinsam in einem Schema darstellen, das der Binärdarstellung ab dem Wert 1 entspricht („duale Kennzahlen“). • Beispiele: Eintrag (1): y1=001, Eintrag (6): x3=110 (in der Tabelle von unten gelesen) • Prüfstellen yj besitzen nur eine einzige 1 in einer Spalte. • Alle anderen Spalten stellen (von rechts beginnend) die Stellen xi da. • Eine Prüfstelle yj überprüft alle Informationsstellen xi , die in der Zeile, in der yj den Wert 1 besitzt, selbst eine 1 in der Tabelle haben. Beispiel: y2 überprüft x4, x3 und x1. Konstruktion von Hamming-Codes 0 1 0 y2 (2) 1 0 1 x2 (5) 1 0 0 y3 (4) 0 1 1 x1 (3) 1 1 0 1 1 0 1 0 1 y1 (1) x3 (6) x4 (7) 79 Zuordnung der Informationsstellen – Erweiterung des Schemas Konstruktion von Hamming-Codes 0 0 1 0 y2 (2) 0 1 0 1 x2 (5) 0 1 0 0 y3 (4) 0 0 1 1 x1 (3) 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 y1 (1) x3 (6) x4 (7) y4 (8) x5 (9) x6 (10) x7 (11) x8 (12) x9 (13) x10 (14) x11 (15) • Notwendige Anzahl k an Prüfstellen yj bei gegebener Anzahl m an Informationsstellen xi zur Bildung eines Hamming-Codes mit HDmin=3: • Beispiele: k 3 4 5 6 m 2 … 4 5 … 11 12 … 26 27 … 57 2k >= m+k+1 80 0 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 m k d2 d3 d4 d5 d6 d7 Prüfbare und korrigierbare Codes (Erweiterungen):  Notwendige Anzahl von Prüfstellen k in Abhängigkeit der Anzahl der Informationsstellen m, um minimale Hamming-Distanz HDmin = d zu erhalten Hamming-Codes 81 Hamming-Codes • Beispiel: 1 F-korrigierbare Codes  m = 4: Informationsstellen  k = 3: Prüfstellen  Zuordnung zu Dezimalzahlen y1 = x4 x2 x1 y2 = x4 x3 x1 y3 = x4 x3 x2       0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1. CW 2. CW 3. CW 4. CW 5. CW 6. CW 7. CW 8. CW 9. CW 10. CW 11. CW 12. CW 13. CW 14. CW 15. CW 16. CW Codewort x4 x3 x2 x1 y3 y2 y1 Dezimal Zyklische Redundanzprüfung (engl. cyclic redundancy check – CRC) Idee (W. Wesley Peterson, 1961) • n-Bit-Folge (cn-1,cn-2,…,c1,c0) mit ci ∈ {0,1} als Koeffizienten eines Polynoms , betrachtet • Beispiel: 1 1 0 0 1 0 1 entspricht dem Polynom P(x) = x6 + x5 + x2 + x0 • Sender und Empfänger vereinbaren Generatorpolynom (von Grad k) • Datenblock wird als Polynom P(x) interpretiert, welches um k angehängte Nullen (so viele wie der Grad) ergänzt wird und durch Gk(x) geteilt wird • Empfänger erhält bei korrekter Übertragung nach der Division durch Gk(x) den Rest 0 ( ) , {0,1} 1 0       P x c x x n i i i      1 0 ( ) k i i k k i G x x c x 83 Zyklische Redundanzprüfung (engl. cyclic redundancy check – CRC) • In der Praxis nutzt man normalerweise sog. Galois-Feld Arithmetik  Arithmetik ist auf einzelne Bitstellen beschränkt und wir nutzen keine Überläufe auf nächst höhere Stelle: ± (2n +1) = 1 mod(2), n ∈ N und ± (2n) = 0 mod(2) Addition/Subtraktion: Multipl.: Division: • wegen mod(2) brauchen Zahlenüber/-unterläufe nicht betrachtet werden  bei Addition / Subtraktion genügt bitweises Exklusiv-Oder (= gerade Parität) • Beispiel: 1 1 0 0 0 1 ± 0 1 1 0 1 0 0 0 * 0 1 1 – 1 0 – 0 : 0 1 10000 11100 10000 11100 -11100 -10000 +11100 +10000 01100 = 01100 01100 = 01100 A B 84 Cyclic Redundancy Check – CRC (Beispiel) Die Nachricht sei: 1 0 1 1 1 0 0 1; das Generatorpolynom x4+x+1 (1 0 0 1 1) Grad=4 1 0 1 1 1 0 0 1 0 0 0 0 : 1 0 0 1 1 = 1 0 1 0 0 1 1 1 XOR ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 0 0 1 1 ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 0 1 0 0 0 0 ↓ ↓ ↓ ↓ ↓ 1 0 0 1 1 ↓ ↓ ↓ ↓ ↓ 0 0 0 1 1 1 0 0 ↓ ↓ 1 0 0 1 1 ↓ ↓ 0 1 1 1 1 0 ↓ 1 0 0 1 1 ↓ 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 Ergänzen um Grad Nullen (0) Weiter bei nächster 1 anfangen Wenn Stellen übersprungen werden, so hängen wir entsprechend viele Stellen an das Ergebnis 0 CRC, Rest der Division Zu sendende Nachricht: 101110011001 1 1 0 0 0 1 ± 0 1 Wir benötigen nur den Rest (nicht den Quotienten) Cyclic Redundancy Check – CRC (Beispiel) Die empfangene Nachricht sei: 101110011001; Das Generatorpolynom x4+x+1 (10011) 1 0 1 1 1 0 0 1 1 0 0 1 : 1 0 0 1 1 = 1 0 1 0 0 1 1 1 XOR ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 0 0 1 1 ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 0 1 0 0 0 0 ↓ ↓ ↓ ↓ ↓ 1 0 0 1 1 ↓ ↓ ↓ ↓ ↓ 0 0 0 1 1 1 1 0 ↓ ↓ 1 0 0 1 1 ↓ ↓ 0 1 1 0 1 0 ↓ 1 0 0 1 1 ↓ 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 Ergänzen um Grad Nullen (0) Weiter bei nächster 1 anfangen Wenn Stellen übersprungen werden, so hängen wir entsprechend viele Stellen an das Ergebnis 0 CRC, Rest der Division Eine null zeigt an, dass kein Fehler gefunden wurde 86 Zyklische Redundanzprüfung (engl. cyclic redundancy check – CRC) • Sehr weit verbreitet • Definition von geeigneten Generatorpolynomen ist komplex (wir greifen normalerweise auf gegebene Polynome zurück) • Variante von CRC-32: Adler32 (Mark Adler)  zlib (gzip-Komprimierung), tar-Archiven und in Java zur Prüfung genutzt  Sehr schnell, erkennt gut auch Mehrbitfehler  Fehlererkennung: • alle Einzelbitfehler, Doppelbitfehler, Dreibitfehler • alle Fehlermuster mit ungerader Bitfehleranzahl • alle Fehlerbüschel mit 16 oder weniger Bits • 99,997% aller 17-Bit-Fehlerbüschel • 99,998% aller Fehlerbüschel mit Länge ≥ 18 Bit • Restfehlerrate < 0,5* 10-5 der ursprünglichen Blockfehlerrate 87

Share this Post: