Paritätsprüfung eines Bitmusters

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2014-09-20T19:54:22+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. Bei gerader Parität wird dann bei einer ungeraden Anzahl von Einsen eine weitere Eins ergänzt, anderenfalls eine Null.

Beispiele:

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

Damit kann mit recht hoher Wahrscheinlichkeit ein Ü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 eine gerade Parität erfüllt ist.

(define bitmuster
  (lambda (n)
    (if (= n 0)
        ""
        (string-append (number->string (random 2)) (bitmuster (- n 1))))))

(define paritaet?
  (lambda (zk)
    (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) 0))))

(define bitliste
  (lambda (n)
    (if (= n 0) 
        ()
        (let ([zk (bitmuster 7)])
          (if (paritaet? zk)
              (cons (string-append zk "0") (bitliste (- n 1)))
              (cons (string-append zk "1") (bitliste (- n 1))))))))

(bitliste 10)

Zurück zum Algorithmusbegriff.

Paritätsprüfung eines Bitmusters

Grundlagen

Implementation

Suche