Tutorium Digitaltechnik
WS 24/25
2. Codes
Maileen Schwenk: scma1315@[Link]
Begriffe
Bewertbar: Jede Ziffer besitzt eine Wertigkeit
(→ Polyadische Zahlensysteme)
Gewicht: Anzahl der 1en im Codewort
Hamming Distanz: Anzahl der unterschiedlichen Stellen zweier
Codewörter
Min/Max Distanz: Vergleich der Distanz aller Codewörter
Stetiger Code: Hamming Distanz zweier benachbarter
Codewörter ist immer gleich
Vollständig: Alle Bit-Kombinationen werden benutzt
Redundanz: Codierung benutzt nicht alle Bitkombinationen
=> R = log2(Npot) - log2(N)
Graycode
Nicht bewertbar
Stetig
Vollständig
Fehlerkorrektur
Parität:
Stellen werden mit xor verknüpft
Even Parity: gerade Anzahl an 1en
Odd Parity: ungerade Anzahl an 1en
Fehlererkennung von n Fehlern:
n = Dmin-1
Fehlerkorrektur von n Fehlern:
𝐷min −1
n= 2
Zeile 2 P2 y x x x x x x x x x …
xor
Zeile 3 P3 y x x x x x x x x …
Hammingcode
Verknüpfungen
Zeile 4 P4 y x x x x x x x …
Zeile 5 P5 y x x x x …
Gesamtbitanzahl 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 PE
Duale Schreibweise 0 0001 0 0010 0 0011 0 0100 0 0101 0 0110 0 0111 0 1000 0 1001 0 1010 0 1011 0 1100 0 1101 0 1110 0 1111 1 0000 1 0001 1 0010 1 0011 1 0100
Bitart P1 P2 D1 P3 D2 D3 D4 P4 D5 D6 D7 D8 D9 D10 D11 P5 D12 D13 D14 D15 PE
Zeile 1 P1
Zeile 2 P2
xor
Zeile 3 P3
Verknüpfungen
Zeile 4 P4
Zeile 5 P5
Paritätsbits (PE) an Stellen der Zweierpotenzen
Dmin = 3
-> 1 Fehler korrigieren
-> 2 Fehler erkennen
Fehlerstelle:
Fehler erkannt bei P1 und P2, P3 stimmt -> 011 = 3D
-> 3. Bit fehlerhaft
Klausur WS 97/98 A3
1)
Klausur WS 22/23 A2
2)
Graycode
3)
a) Wie lautet die Zahl 18 im Graycode? (Erstelle den Code dafür selbst)
b) Warum können mit dem Graycode keine Fehler erkannt werden?
Hamming Code
4)
a)
Es sollen die Datenbits D0 bis D6 im Hammingcode codiert werden. Wie viele
Paritätsbits werden benötigt, damit man einen Fehler korrigieren kann?
b)
Wie könnte man durch Logikbausteine bestimmen, an welcher Stelle ein Fehler
vorliegt? Zeichne eine zugehörige Schaltung.
Hammingcode
5) a)
Die folgenden Bits werden im Hammingcode codiert und übertragen. Der Empfänger
empfängt folgende Bits. Finde und korrigiere den Fehler.
D0 D1 D2 D3 D4 P0 P1 P2 P3
1 1 1 0 1 0 1 0 1
b) Eine Dezimalzahl mit 5 Ziffern wird zur Übertragung ziffernweise im Stibitzcode
codiert. Zur Fehlerkorrektur wird der Hammingcode verwendet. Der Empfänger
detektiert für die Ziffer Z4 … Z0 folgenden Hammingcode. Finde und korrigiere die
Fehler.
Z4 1 0 0 1 1 1 0
Z3 1 0 1 1 0 1 0
Z2 0 1 1 1 0 0 1
Z1 0 1 1 0 0 0 1
Z0 1 0 1 0 0 0 0
Klausur SS 06 A3
6) Im Zweierkomplement vorliegende 5-Bit-Dualzahlen werden für die
Datenübertragung mit Hilfe der Hamming-Codierung so gesichert, dass ein Bitfehler
pro Zahl korrigiert werden kann. Insgesamt werden 5 Zahlen übertragen. In der
folgenden Tabelle sind die vom Empfänger erfassten Bits angegeben.
Korrigieren Sie die fehlerhaften Bits und geben Sie die richtigen Zahlen als
Dezimalzahl mit Vorzeichen an. Mit A0 ... A4 werden die Bits der Zahlen bezeichnet.
A0 ist das LSB. A4 ist das MSB.
A4 A3 A2 A1 A0
D1 D2 D3 D4 D5 P1 P2 P3 P4
0 1 0 0 1 0 1 0 1
0 0 1 0 1 1 0 1 1
1 1 0 1 1 0 0 0 1
1 0 0 1 1 0 1 0 1
1 1 0 0 1 0 0 1 1