Codes

Florian Hutter & Nicole Waibel

Index• Geschichte der Codes• ASCII

– Geschichte– Aufbau

• Unicode– Geschichte– Aufbau

• Huffman-Code– Definition– Aufbau

• Hamming-Code– Definition– Geschichte– Aufbau

• ECC– Definition– Arten– Fehlererkennung

Geschichte der Codes• Cäsar Schlüssel • Ende des 19. Jahrhunderts: kommerzielle Chiffren

für die Telegraphie • Die ersten Kodierungen von Zeichen für

Computer (1890)• IBM: 6-Bit-BCDIC-Code • EBCDIC (8-Bit-Code)• 20er Jahre erste Codierungsmaschinen • 1. und 2. Weltkrieg: Aufkommen der

Kryptographie • 1975 Erfindung der Public-Key-Kryptographie

ASCII - Geschichte• Ursprünglich: Darstellung von Schriftzeichen der

englischen Sprache • Erste Version kannte noch kein Kleinbuchstaben

(1963) • 1968 der bis heute gültige ASCII

– achte Bit des Bytes als Prüf- oder Parity-Bit zur Sicherstellung korrekter Übertragungen

ASCII-Aufbau• Es gehört zu jedem möglichen Binärzeichen ein

Zeichen. • alphabetischen Zeichen in Groß- und

Kleinbuchstaben • Sonderzeichen und Steuerzeichen,

Einteilung: • Zeichen 0 bis 31: Steuerzeichen• Zeichen 48 bis 57: Ziffern 0 bis 9 • Zeichen 65 bis 90: Großbuchstaben A bis Z• Zeichen 97 bis 122: Kleinbuchstaben a bis z

ASCII-Aufbau• ASCII-Code auf 8 Bit erweitert• „Code Pages“

– Problem: z.B. E-Mails nicht korrekt übertragen– japanische und chinesische Zeichen nicht

darstellbar DBCS

Unicode - Geschichte• Unicode-Standard 1991 veröffentlicht • 1996 von der "International Organization for

Standardization" (ISO) als ISO 10646 angenommen

• Unicode-Version 1.0 - Jahr 1991• Version 1.1 - Jahr 1993 • Version 2.0 - Jahr 1996 • Version 2.1 - Jahr 1998 • Version 3.0 - Jahr 2000

Unicode - AufbauUnicode (dt. etwa: "Einheitssschlüssel) • alphanumerischer Zeichensatz• ISO genormtes System zur Kodierung von

Textzeichen• "Universal Character Set" (USC; dt.: "Universeller

Zeichensatz"). • Buchstaben des lateinischen Alphabets, das

griechische, kyrillische, arabische, hebräische, thailändische Alphabet und die CJK-Schriften

• mathematische, kaufmännische und technische Sonderzeichen

Unicode - Aufbau• Die erste Ebene verwendet, die "Basic

Multilingual Plane" (BMP; Dt.: "Grundlegende mehrsprachige Ebene“)

• 16 Bit zur Kodierung jedes Zeichens (65.536 Zeichen)

• Kodierung: "Universal Character Set 2" (UCS-2; dt.: "Universelle Schriftzeichen-Menge 2") – zwei Byte für die Kodierung jedes Zeichens

"Double Byte Character Set"• Die ersten 256 Zeichen "ISO Latin-1" (ISO

8859-1); – 8 Bit kodiert.

Unicode - Aufbau• Die übrigen Ebenen des Unicode

– historische Schriftzeichen – alt-ägyptische Hieroglyphen– seltene chinesisches Schriftzeichen

• 32 Bit kodiert (4.294.967.296 Zeichen) • Kodierung: "Universal Character Set 4" (USC-4;

dt.: "Universelle Schriftzeichen-Menge 4") – vier Byte für die Kodierung jedes Zeichens

verwendet werden

Unicode - Aufbau• Skripten

– verschiedene Alphabete– Firmensymbole– Steuerzeichen

• Problem– verbreitet sich nur langsam

Huffman-Code• Algorithmus der Datenkompression• kodiert die Zeichen eines Textes nach ihrer

Häufigkeit • Huffman-Kodierbaum• Einsatzbereich:

– Grafikverarbeitung(JPEG, MPEG, Wavelet, LHA)

Huffman-Code - Aufbau

Ausgangssituation des Huffman-Algorithmus

Huffman-Code - Aufbau

Huffman-Code - Aufbau

Huffman-Code - Aufbau• Nachteile

– Umsetzung erfordert umständliche Bitoperationen

– Optimalität der Kompression

Hamming-Code• Richard Hamming • linearer fehlerkorrigierender Blockcode• Verwendung:

– digitalen Signalverarbeitung – Nachrichtentechnik– zur gesicherten Datenübertragung oder

Datenspeicherung • Besonderheit dieses Codes: Verwendung

mehrerer Paritätsbits

Hamming-Code - Geschichte• 1940er Jahren: Firma Bell Labs • Computer namens Bell Model V• Lochkarten durch Abnutzung Fehler • Computer übersprang die fehlerhaften Lochkarten• entwickelte speziellen Code

– Lesefehler selbstständig erkennen – korrigieren

• 1950 publizierte er diesen Hamming-Code

Hamming-Code - Aufbaun = 2k − k − 1

n… Datenblock umfasst n Bitsk… fixe KontrollstellenN… Codewortlänge

Hamming-Code - Aufbau

Fehlererkennung & Fehlerkorrektur

• Mögliche Fehlerursachen

– Rauschen

– Kurzzeitstörungen

– Signalverformung

– Nebensprechen

• Fehlererkennung

• Fehlerkorrektur

– Vorwärts Fehlerkorrektur (FEC)

– Anforderung auf Wiederholung der Übertragung

Mögliche Fehlerursachen• Rauschen

– Kann einzelne Bitfehler verursachen– Stärke des Rauschens ist entscheidend

• Kurzzeitstörungen – Elektrische Funken, Kratzer auf CDs– kosmische Strahlung

• Signalverformung • Nebensprechen

Fehlererkennung• Erkennung nur bei redundanten Nachrichten

möglich.• Mit Hilfe von Paritätsbit• Erkennungsverfahren unterscheiden sich nur

durch Anzahl von „Schutzbits“• N (Gesammtbit) = M (Nutzbit) + K (Schutzbit)

Fehlerkorrektur• 2 Wesentliche Arten:

– Vorwärts Fehlerkorrektur (FEC)– Anforderung auf Wiederholung der

Übertragung (ARQ = automatic repeat request).

Vorwärts Fehlerkorrektur (FEC)• Vorteil:

– Kann auf Simplexkanälen vorgenommen werden

• Nachteil:– Hohe Redundanz

Beispiel

Quellen• http://www-fs.informatik.uni-tuebingen.de/lehre/

ss05/proseminar/Folien/Codes.pdf • http://de.wikipedia.org/wiki/ASCII#Geschichte • http://de.wikibooks.org/wiki/

Assembler_(80x86_Prozessor)-Programmierung:_Grundlagen

• http://www.lexitron.de/main.php?detail=true&eintrag=119

• http://goethe.ira.uka.de/seminare/rftk/huffman/#ToC8

Danke für eure Aufmerksamkeit