Paritätsprüfung eines Bitmusters

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2018-10-02T19:44:27+00:00. Aktuelle Version

Autoren: Richard Walde; Veit Berger (2014)

Grundlagen

RS-232-Kabel zur seriellen Datenübertragung

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 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)

Zurück zum Algorithmusbegriff.

Paritätsprüfung eines Bitmusters

Grundlagen

Implementation

Suche