Kapitel 10 - Leitungscodes & Fehlererkennung (CRC)

← Startseite · Kap. 9 Software Interrupt · 10 Leitungscodes & CRC · → Kap. 11 Weiterführende Themen Verwandt: Kap. 4 Serielle Schnittstelle · Kap. 7 Signalverarbeitung Quellen: [Q: ZF §11/§11a] (keine eigenen Folien) · [Q: KL20 Aufg. 5 CRC, Aufg. 6 Manchester] · [Q: ALT 2009/2012/2013 CRC, Übungsklausur Codierung]

CRC ist in JEDER Klausur (12 Punkte). Manchester-Dekodierung ebenfalls. Beide unbedingt üben.

1. Einordnung (OSI Schicht 1)

Leitungscodes gehören zur Bitübertragungsschicht (Physical Layer): definieren physikalische Verbindung, Signale und Codierung von Bitfolgen in übertragbare Signale.

Pegel: High-active (High=1) vs. Low-active (Low=1).
Problem einfacher Codes: lange Folgen gleicher Bits → keine Pegelwechsel → Fehler schwer erkennbar, Empfänger verliert Synchronisation (Takt).

2. Binäre Leitungscodes: NRZ, NRZI

NRZ (Non Return to Zero): Pegel = Bit direkt (0=Low, 1=High). Standard bei asynchron (RS-232). Synchronisationsprobleme bei langen gleichen Folgen.
NRZI (NRZ Invert): Information steckt im Pegelwechsel, nicht im Pegel.
- NRZI-S (Space): Wechsel bei 0, kein Wechsel bei 1 (z. B. USB).
- NRZI-M (Mark): Wechsel bei 1, kein Wechsel bei 0.
- Vorteil: bessere Synchronisation; aber lange Folgen ohne Wechsel bleiben problematisch.

3. RZ (Return to Zero, ternär)

Drei Pegel (−1, 0, +1): 1 = positiver Puls, 0 = negativer Puls; nach halber Taktzeit zurück auf 0.

Vorteil: selbsttaktend (Flanke in jedem Bit).
Nachteil: doppelte Bandbreite (Baudrate = 2·Bitrate), Gleichspannungsanteil (galvanische Trennung schwer).

4. Manchester-Code

Kombiniert Takt + Daten: ein Bit = Flanke in der Mitte des Taktintervalls.

IEEE 802.3 (Ethernet): fallende Flanke = 0, steigende Flanke = 1.
G. E. Thomas (Manchester-I, invertiert): steigende Flanke = 0, fallende Flanke = 1 (genau umgekehrt).
Eigenschaften: gleichspannungsfrei (Mittelwert 0), selbsttaktend, Codierung/Dekodierung per XOR (Daten ⊕ Takt); Nachteil: doppelte Bandbreite.

Manchester dekodieren (KL20 6.8/6.9): Für jedes Bit in der Mitte die Flanke ansehen.

IEEE 802.3: steigend→1, fallend→0.

G. E. Thomas: steigend→0, fallend→1 (Ergebnis der einen Konvention ist das bitweise Komplement der anderen).

5. Baudrate vs. Bitrate

Bitrate: übertragene Informationsbits pro Sekunde.
Baudrate: übertragene Symbole (Pegelzustände) pro Sekunde.
NRZ / NRZI-S: 1 Symbol = 1 Bit → Baudrate = Bitrate.
Manchester / RZ: 1 Bit = 2 Symbole → Baudrate = 2 · Bitrate.

6. Fehlererkennung: VRC / LRC / Checksum

Redundanz hinzufügen, um Fehler zu erkennen:

VRC (Vertical Redundancy Check): Querparität = Paritätsbit je Zeichen. Erkennt 1-Bit-Fehler; versagt, wenn sich Daten- und Prüfbit so ändern, dass Parität wieder stimmt (gerade Fehleranzahl).
LRC (Longitudinal Redundancy Check): Längsparität über Spalten eines Blocks.
Checksum (Summenprüfung): Bytes addieren (oft mod 256), Zweierkomplement als Prüfsumme (FCS) anhängen; Empfänger addiert alles inkl. FCS → Ergebnis muss 0 sein.

7. CRC (Cyclic Redundancy Check)

Leistungsfähig, basiert auf Polynomdivision in Modulo-2-Arithmetik.

Bitfolgen = Koeffizienten von Polynomen.
Modulo-2: Addition = Subtraktion = XOR (kein Übertrag). 1+1=0, 0−1=1.

Generatorpolynom → binär

Ein Polynom vom Grad g → (g+1) Bits; Bit gesetzt, wo der Term vorkommt (inkl. x⁰=1).

x⁵ + x² + 1 → Terme x⁵,x²,x⁰ → 100101 (6 Bit).
x⁵ + x³ + 1 → 101001. x⁵ + x³ + x → 101010. x⁵+x²+x+1 → 100111.
CRC-4 (x⁴+x+1, Standard) → 10011 (5 Bit) → 4 Prüfbits.

Sende-Verfahren (Prüfbits erzeugen)

Nachricht um g Nullen nach links verschieben (g = Grad = Anzahl Prüfbits).
Diese Folge mod-2 durch das Generatorpolynom teilen (XOR-Schritte).
Der Rest (g Bit) = Prüfsumme (FCS) → an die Originaldaten anhängen.

Empfangs-Prüfung

Empfangene Nachricht (Daten + FCS) mod-2 durch dasselbe Polynom teilen. Rest = 0 → fehlerfrei; Rest ≠ 0 → Fehler.

Worked Example (KL20 Aufg. 5.2)

Generator CRC-4 = 10011 (x⁴+x+1), Nachricht 00110010. Grad g = 4 → 4 Nullen anhängen: 0011 0010 0000.

Handrechen-Regel: Von links durchgehen; steht am aktuellen führenden Bit eine 1, XOR die 5 Bit 10011 darunter; steht eine 0, ein Bit weiterrücken. Die letzten 4 Bit = CRC.

Vollständige Modulo-2-Division (XOR):

 001100100000        ← Nachricht + 4 Nullen
  10011              ← Divisor unter erster 1 (Pos. 2):  11001 ⊕ 10011
  -----
  0101000100000  →   an nächster führender 1 (Pos. 3):   10100 ⊕ 10011
   10011
   -----
  0000111100000  →   nächste führende 1 (Pos. 5):        11100 ⊕ 10011
     10011
     -----
  0000011110000  →   Pos. 6:                              11110 ⊕ 10011
      10011
      -----
  0000001101000  →   Pos. 7:                              11010 ⊕ 10011
       10011
       -----
  0000000010 0 1     Rest steht in den letzten 4 Bit

Kompakt (Restregister nach jedem XOR): 11001→01010, 10100→00111, 11100→01111, 11110→01101, 11010→01001 → Rest = 1001.

Ergebnis KL20 5.2: Checksumme 1001 (rechnerisch bestätigt). Gesendet wird 00110010 1001. (Rechenweg als vollständige XOR-Kaskade auch in den Übungen §CRC.)

Weitere Aufgabentypen

Gültigkeit prüfen (KL20 5.4): Empfangene Folge (Daten+FCS) durch Generator teilen → Rest 0 = gültig. Für 11110010 mit 10011 ist der Rest 0000 → gültig.
Anzahl Iterationen (KL20 5.5): = Anzahl der Datenbits (jedes Bit „wird einmal eingeschoben"), also bei 8-Bit-Nachricht (11110010) → 8 Schritte (Länge der Nachricht = Anzahl Datenbits vor den Nullen; genauer: so viele Shift-Schritte, wie die Gesamtlänge Datenbits beträgt).
HW (KL20 5.3): CRC braucht EXOR-Gatter + Schieberegister → LFSR.

Linear Feedback Shift Register: Kette aus Flipflops (Schieberegister) + XOR-Gattern. Rückkopplungen = Koeffizienten des Generatorpolynoms. Pro Takt 1 Bit; am Ende steht der Rest (CRC) im Register.

Gängige Standards

CRC	Anwendung
CRC-5	USB Token
CRC-16	USB-Daten
CRC-CCITT	Bluetooth, X.25
CRC-32	Ethernet (802.3), Internet, USB 3.0

8. Hamming-Distanz

Anzahl Bit-Positionen, in denen sich zwei Codewörter unterscheiden (per XOR + Einsen zählen).

Fehler erkennen bis k Bit: d ≥ k + 1.
Fehler korrigieren bis k Bit: d ≥ 2k + 1.

Prüfungsrelevanz

CRC (immer!): Generatorpolynom → binär; Prüfbits per mod-2-Division; Code in binär+hex; Gültigkeit (Rest 0); Iterationen; HW (LFSR: XOR + Schieberegister).
Manchester dekodieren (IEEE 802.3 vs. G.E. Thomas - invertiert zueinander); NRZ/Manchester einzeichnen; welcher Code selbsttaktend?
Baudrate vs. Bitrate (Manchester = 2× Bit).
VRC/LRC/Checksum, Hamming-Distanz (erkennen d≥k+1, korrigieren d≥2k+1).

Typische Fehler: Grad/Bitzahl des Polynoms falsch (Grad g → g+1 Bit, g Prüfbits) · zu wenige Nullen anhängen (genau g) · mod-2 mit „echtem" Subtrahieren verwechseln (es ist XOR!) · Manchester-Konventionen vertauschen · Baud=Bit bei Manchester.

← Kap. 9 Software Interrupt · → Kap. 11 Weiterführende Themen