TU Wien:Technische Grundlagen der Informatik VU (Kastner)/Kapitel Codierung

• 01 Zahlendarstellung
• 02 Numerik
• 03 Codierung
• 04 Informationstheorie
• 05 Boolesche Algebra
• 06 KV-Diagramme und BDD
• 07 Moore- & Mealy-AutomatenTGI+GDS

  ---

• 08 Digitalschaltungen, KominatorikTGI
• 09 Sequentielle Logik
• 10 Speicher
• 14 Micro16
• 15 Befehlssatz
• 16 Pipelining
• 17 Speichermanagement
• 18 Chipsatz
• 19 Multi-Core
• 20 Netzwerke

Zeichencodierungen

• US-ASCII, 7-bit code
• Unicode
  • UTF-8, variable Länge
• ISO-Latin-1 (ISO 8859-1), 8-bit code

EAN-13

• Verwendet für Barcodes
• Zeichenvorrat: 0..9
• Aufbau
  • 1. implizierte Ziffer
  • 11 Zifferen
  • Prüfziffer
• zwei Randsymbole, ein Trennsymbol
• Prüfung: Summe der Ziffern, abwechselnd mit 1 und 3 multipliziert, ist durch 10 teilbar

Codierungstheorie

• Ziel: Schutz vor Fehlern bei Übertragung oder Speicherung
• Begründer: Golay und Hamming, ca. 1950

Mehrstufige Codierung:

• Quellencodierung
• Kanalcodierung: Fehlerredundanz
• Leitungscodierung für Übertragungsmedium

Arten von Binärcodes

• Blockcode: konstante Codewortlänge
  • Linearer Code: Summe von Codewörtern ist auch ein Codewort, Modulo-Arithmetik
  • Zyklischer Code: Linearer Code bei dem durch bitweises Rotieren (Shiften) gültige Codewörter enstehen.
  • Systematischer Code: Länge $n$, bestehen aus $m$ Informationsbits und $n-m$ Prüfbits
• Codes mit variabler Wortlänge

Fehlererkennende und korrigierende Codes

Hamming-Distanz

• An wie vielen Stellen unterscheiden sich zwei Codewörter?
• eines Codes: Minimum aller Abstände zwischen Wörtern innerhalb des Codes, Bestimmung mit Matrix
• $(D-1)$ Bit-Fehler erkennbar
• $k$ Bit-Fehler, $k<D/2$ korrigierbar

Prüfstellen-Codes

• Ein Paritätsbit (even/odd parity)
• Mehrere Paritätsbits, z.B. Hamming-Code
• mehrdimensional: z.B. Kreuz- oder Blockparität
• Prüfsumme, z.B. EAN, Polynomcodes

Polynomcodes

Bitfolge der Länge $k$ als Koeffizienten eines Polynoms vom Grad $k-1$: $a_{k-1}{x}^{k-1}+\mathrm{...}+a_1{x}^1+a_0{x}^0$

• Generatorpolynom als Prüffunktion im gleichen Format anhängen, teilt Wort ohne Rest
• Rechnungen modulo 2
• CRC Codes (Cyclic Redundancy Check): zyklische Polynomcodes

Hamming-Code

• linear
• von 1 durchnummeriert: Bits die Potenzen von 2 sind, sind Prüfbits
• Das Codebit $k$ trägt zu den Prüfbits, die summiert $k$ ergeben, bei.

Leitungscode NRZ (Non Return to Zero)

Variante	Codierung
NRZ-L	1 ist high, 0 ist low
NRZ-M	Pegelwechsel bei 1
NRZ-S	Pegelwechsel bei 0
RZ	unipolar, zweite Takthälfte low
Biphase-L	1 ist low in der Mitte, 0 ist high in der Mitte, wechselt zwischen gleichen Bits
Biphase-M	wechselt jede Periode, 1 ist Wechsel in der Mitte
Biphase-S	wechselt jede Periode, 0 ist Wechsel in der Mitte
D. Manchester	wechselt in der Mitte jeder Periode, 1 ist Wechsel am Bitanfang