Paritätsprüfung eines Bitmusters

Aus ProgrammingWiki

Autoren: Richard Walde; Veit Berger (2014)

Grundlagen

Bei der seriellen Datenübertragung ist es mitunter möglich, ein Paritätsbit zu vereinbaren.
So kann im RS-232-Standard (vgl. nebenstehende Abbildung) an eine Folge von 7 Datenbit ein Paritätsbit angefügt werden. Im Fall einer geraden Parität wird bei einer ungeraden Anzahl von Einsen eine weitere Eins ergänzt, anderenfalls eine Null.

Beispiele:

"1001010" --> "10010101"
"0101000" --> "01010000"  

Damit können mit recht hoher Wahrscheinlichkeit Übertragungsfehler erkannt werden, wenn die Paritätsprüfung des Empfängers bei gerader Parität keine gerade Anzahl von Einsen ergibt. Eine Fehlerkorrektur ist natürlich nicht möglich.

Implementation

Mit den nachfolgende Prozeduren soll eine beliebige Anzahl zufälliger Bitmuster der Länge 7 generiert werden.
Anschließend wird zu jedem Bitmuster ein Paritätsbit ergänzt, so dass wahlweise eine gerade bzw. eine ungerade Parität erfüllt ist.

(define gerade 0) (define ungerade 1) (define bitmuster (lambda (n) (if (= n 0) "" (string-append (number->string (random 2)) (bitmuster (- n 1)))))) (define paritaet? (lambda (zk art) (letrec ([zaehlen (lambda (zk) (cond [(= (string-length zk) 0) 0] [(eqv? (string-ref zk 0) #\1) (+ 1 (zaehlen (substring zk 1 (string-length zk))))] [else (zaehlen (substring zk 1 (string-length zk)))]))]) (= (modulo (zaehlen zk) 2) art)))) (define bitliste (lambda (n art) (if (= n 0) () (let ([zk (bitmuster 7)]) (if (paritaet? zk art) (cons (string-append zk "0") (bitliste (- n 1) art)) (cons (string-append zk "1") (bitliste (- n 1) art)))))))

(bitliste 10 gerade)

ausführen

Zurück zum Algorithmusbegriff.