Herwig Feichtinger

Fehlerkorrigierende Übertragungsverfahren lassen sich überall dort sinnvoll einsetzen, wo Fehler nie gehäuft auftreten, sondern nur ab und zu. Je häufiger man Fehler zulassen und automatisch korrigieren will, desto mehr Prüfzeichen muß man zusätzlich zur eigentlichen Information übertragen (Redundanz). Der Informatiker Hamming hatte die theoretischen Grundlagen für fehlerkorrigierende Übertragungsverfahren längst geschaffen, bevor es eine Anwendung dafür gab; heute nennt man die zusätzlichen Prüfbits ihm zu Ehren Hamming-Bits.

Es gibt sehr unterschiedliche Möglichkeiten der Korrektur-Bit-Gewinnung; sie alle beruhen im Prinzip aber darauf, die zu übertragenden Datenbits als Matrix aufzuschreiben und aus deren Zeilen und Spalten mehrere Paritätsbits aufzusummieren. Die mehr oder weniger willkürlich angenommene Bitmatrix des hier verwendeten Verfahrens zeigt Bild 1.

Aus den für eine ASCII-Textübertragung nötigen sieben Datenbits b0...b6 werden sechs Korrektur-Bits h0...h5 gewonnen, indem für jede Zeile und Spalte der Matrix festgestellt wird, ob die Summe der Bits gerade oder ungerade ist.
Die Möglichkeit der Fehlerkorrektur ergibt sich aus folgender Überlegung: Wenn ein Datenbit falsch übertragen wird, so wird der Rechner auf der Empfangsseite ein vom empfangenen in zwei Bits abweichendes Prüfbyte ermitteln. Diese zwei Bits geben unter Zuhilfenahme der Matrix die Nummer des falschen Datenbits an, das dann nur noch invertiert werden muß. Wird im Prüfbyte selbst ein (und nur ein) Bit falsch übertragen, so stellt der Empfänger fest, daß dies kein sinnvoller Matrixcode ist, und ignoriert diesen Fehler einfach. Zwei falsche Bits werden zumindest in den meisten Fällen erkannt, können aber nicht mehr korrigiert werden.
Welche Ergebnisse beim bitweisen Vergleich gesendeter Codes auftreten können, geht aus Bild 2 hervor; es sind logischerweise genau sieben, entsprechend der Anzahl der Datenbits des zu korrigierenden Zeichens.

Entsprechend h0...h5 trägt der hier verwendete Algorithmus Zweierpotenzen für die Spalten und Zeilen der Matrix ein und addiert sie für jede Bitposition.
Wird beispielsweise b4 (das Bit in der Mitte der Matrix) falsch übertragen, so weicht der empfangsseitig ermittelte Hamming-Code vom übertragenen in h1 und h4 ab. 2¹ + 2⁴ ergibt 2 + 16 = 18. Der Rechner braucht nun lediglich in einer Tabelle wie in Bild 2 nachzusehen, welches Bit (nämlich b4) er invertieren muß.

Bei der Übertragung wird jedem Textzeichen ein zusätzliches Zeichen mit den sechs Korrektur-Bits angehängt. Da also nur sechs der sieben ASCII-Bits ausgenutzt werden, kann man dafür sorgen, daß alle Prüfzeichen in den Bereich der „druckenden" Codes fallen, so daß keine Steuerzeichen (hex 00...1F und 7F) generiert werden. Das ist recht einfach, indem man zu jedem Prüf-Byte hex 20 addiert, so daß die Prüfzeichen im Bereich hex 20...5F liegen. Das ist wichtig, weil viele DFÜ-Programme einerseits die meisten Steuerzeichen sperren, andererseits bestimmte Codes zu unerwünschten Effekten im Rechner fuhren würden.
Von dieser Überlegung ausgehend entstand ein 6502-Programm, das im Originalartikel abgedruckt war.
[Find the 6502 listing here]

Für die Z80 Version stehen im Wesentlichen zwei Routinen zur Verfügung:

• fsend: Aus dem im Akku stehenden Zeichen wird das Hamming-Byte berechnet. Dieses Byte steht bei Ende der Routine im Akku, das Zeichen ist in das Register C kopiert.
• fempf: Aus dem Zeichen im Register C und dem Hamming-Byte im Akku wird im Fehlerfall versucht, das Zeichen zu korrigieren. Am Ende steht das Zeichen im Akku und im Register B. Ist eine Korrektur nicht möglich, so ist die Carry Flag gesetzt und im Akku steht ein Fragezeichen.

title Hamming Korrektur name ('HAMMING') entry fsend,fempf ; ; Ermitteln des Hamming-Bytes aus einem Zeichen ; ; Eingabe: Zeichen im Akku ; Ausgabe: Hamming-Byte im Akku ; Zeichen im Register C ; fsend equ $ hamming: call hamm ; Hamming-Byte ermitteln add a,' ' ; Als ASCII zurueck ret ; ; Zeichen restaurieren ; ; Eingabe: Hamming-Byte im Akku ; Zeichen in Register C ; Ausgabe: Zeichen im Akku und Register B ; Im Fehlerfall ist Carry gesetzt ; und Akku haelt Fragezeichen ; fempf equ $ dehamming: sub ' ' ; ASCII-Offset entfernen ld d,a ; Hamming-Byte retten ld a,c ; Zeichen holen call corr ; Korrektur ermitteln ld b,a ; Zeichen abspeichern ret nc ld a,'?' ; Fehler - Fragezeichen einsetzen ret ; ; Hamming-Code berechnen ; hamm: ld c,a ; Zeichen retten ld e,a xor a ; Ergebnis initialisieren ld b,7 ; Zaehler fuer 7 Bit ld hl,tab+6 ; Tabelle laden hamm1: sla e ; Zeichen schieben jp p,hamm2 ; Bit testen xor (hl) ; Boole'sche Addition hamm2: dec hl djnz hamm1 ret corr: call hamm ; Hamming-Code berechnen xor d ; Bits vergleichen ld e,01000000b ld b,7 ; Zaehler fuer 7 Bit ld hl,tab+6 ; Tabelle laden corr2: cp (hl) ; Vergleich jr z,corr3 srl e cp e jr z,corr4 dec hl djnz corr2 scf ; Korrektur nicht moeglich ld a,c ret corr3: ld a,c xor e ; Korrigieren ret corr4: ld a,c or a ret ; tab: db 1+8,1+16,1+32 db 2+8,2+16,2+32 db 4+8 end

[Listing]

Z80-Programm zum Senden und Empfangen eines Zeichens mit automatischer Fehlerkorrektur

Das nachstehende Testprogramm nimmt Textzeilen entgegen, bis eine Leerzeile eingegeben wird. Danach werden aus den einzelnen Zeichen die Hamming-Bytes gebildet. Der Wert des Zeichens wird um 1 erhöht und es wird nun versucht, eine Korrektur durchzuführen. Im Extremfall kann eine Abweichung von allen sieben möglichen Bits stattfinden.
Dies ist z.B. der Fall beim Zeichen ?:

ASCII Zeichen	?
Hexwert	0x3F
Binärwert	0111111
1 addieren	0000001
Ergibt Binärwert	1000000
Hexwert	0x40

title Hamming Korrektur name ('HAMTEST') ext fsend,fempf OS equ 0000h BDOS equ 0005h TPATOP equ BDOS+1 .conout equ 2 .rdline equ 10 null equ 00h lf equ 0ah cr equ 0dh MAXCHR equ 16 ld sp,(TPATOP) ; Stack laden txtloop: call rdline ; Text einlesen jp nc,OS ; Ende, wenn Zeile leer call codetext ; Text "versenden" und "empfangen" jr txtloop ; ; Text "versenden" und "empfangen" ; codetext: ld hl,$txt ; Zeiger auf Text HammTxt: ld a,(hl) ; Zeichen holen or a ; Test ob Ende ret z ; Ja push hl push hl ld (o$chr),a ; Originalzeichen speichern call fsend ; Hamming-Byte berechnen pop hl push af ; Hamming-Byte retten ld a,(hl) ; Zeichen holen inc a ; Fehler einbauen ld (d$chr),a ; Speichern ld c,a pop af call fempf ; Zeichen wiederherstellen ld (h$chr),a ; Resultat speichern sbc a,a ; Bei Carry liegt Fehler vor xor 0ffh add a,'!' ; Leer- oder Ausrufungszeichen ld (k$chr),a call result ; Ergebnis ausgeben pop hl inc hl jr HammTxt ; ; Resultatszeile ; o$chr: db 'x - ' d$chr: db 'x - ' h$chr: db 'x ' k$chr: db '! [' bits: db '0 Bit(s)]' db cr,lf,null ; ; Ergebnis ausgeben ; result: ld hl,o$chr ld a,(d$chr) xor (hl) ; Anzahl verschiedener Bits ausgeben ld ix,bits ld (ix),'0' ; Null voreinstellen ld b,7 ; Anzahl Bits getbdif: rra ; Test ob Bit gesetzt jr nc,nobit ; Nein inc (ix) ; Bitzaehler erhoehen nobit: djnz getbdif call string ; Dann Ergebnis ausgeben ret ; ; Zeichenkette auf Konsole ausgeben ; string: ld a,(hl) or a ; Test Ende ret z ; Ja call conout ; Sonst Ausgabe inc hl jr string ; ; Zeile von Tastatur einlesen ; ; Bei vorhandenen Zeichen wird Carry gesetzt ; rdline: ld hl,what call string ; Anzeige, dass Eingabe benoetigt wird ld de,txt ld c,.rdline call BDOS ; Text einlesen ld a,(txt+1) or a ; Test ob Zeichen vorhanden ret z ; Nein ld c,a ld b,0 ld hl,$txt add hl,bc ld (hl),b ; Textende angeben call nl ; Zeilenvorschub scf ; Anzeige vorhandener Zeichen ret ; what: db 'Texteingabe max ' db '0' + MAXCHR / 10 db '0' + MAXCHR MOD 10 db ' Zeichen (leer fuer Ende):' db cr,lf,null ; ; Neue Zeile ausgeben ; nl: ld a,cr call conout ld a,lf ; ; Zeichen im Akku ausgeben ; conout: push af push bc push de push hl ld e,a ld c,.conout call BDOS ; Ausgabe pop hl pop de pop bc pop af ret ; ; Zeichenpuffer ; txt: db MAXCHR+1 ds 1 $txt: ds MAXCHR+1 end

[Listing]

Z80-Testprogramm

[Dieser Absatz bezieht sich auf den Originalartikel]
Die Wirksamkeit der fehlerkorrigierenden Datenfernübertragung hängt sehr stark davon ab, welcher Art die Fehler sind, die typischerweise auf der Leitung auftreten. Handelt es sich vorwiegend um sehr kurze Knack-Geräusche (z.B. Schaltspitzen bei Ortsgesprächen), so werden die resultierenden Bitfehler korrigiert. Sogenannten Bündelstörungen, bei denen mehrere aufeinanderfolgende Bits gestört sind, ist das Verfahren naturgemäß nicht gewachsen; sie treten bei Ferngesprächen manchmal auf.
Verfolgt man die Übertragung am Bildschirm, so sieht man, daß nach der ersten Zeile jede mit einem B beginnt; ebenso steht nach jedem Leerraum ein B (Bild 4): Das ist zufällig sowohl der Korrektur-Code für Return als auch für Space. (Notwendigerweise gibt es diese Mehrdeutigkeit des Prüfzeichens, da ja sechs Hamming-Bits aus sieben Datenbits erzeugt werden.) Das B nach dem letzten Return sollte man nicht löschen, weil sonst die letzte Zeile nicht korrekt abgeschlossen wird.