Grundlagen der funktionsorientierten Programmierung mit SCHEME/Paritätsprüfung eines Bitmusters

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
'''Autoren: Richard Walde; Veit Berger (2014)'''

<code id="541dd916e6555" hidden>
;-- M. Hielscher / Chr. Wagenknecht --
(define random-maker
  (let* ((multiplier 48271)
         (modulus 2147483647)
         (apply-congruence
          (lambda (current-seed)
            (let ((candidate (modulo (* current-seed multiplier) modulus)))
              (if (zero? candidate)
                  modulus
                  candidate))))
         (coerce
          (lambda (proposed-seed)
            (if (integer? proposed-seed)
                (- modulus (modulo proposed-seed modulus)) 19880214))))
  (lambda (initial-seed)
    (let ((seed (coerce initial-seed)))
      (lambda args
        (cond ((null? args)
               (set! seed (apply-congruence seed))
               (/ (- modulus seed) modulus))
              ((null? (cdr args))
               (let* ((proposed-top
                       (ceiling (abs (car args))))
                      (exact-top
                       (if (inexact? proposed-top)
                           (inexact->exact proposed-top)
                           proposed-top))
                      (top
                       (if (zero? exact-top)
                           1
                           exact-top)))
                 (set! seed (apply-congruence seed))
                 (inexact->exact (floor (* top (/ seed modulus))))))
              ((eq? (cadr args) 'reset)
               (set! seed (coerce (car args))))
              (else
               (display "random: unrecognized message")
               (newline))))))))

(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)

(define random (random-maker (time-nanosecond (current-time))))
</code>

== Grundlagen ==

[[Bild:RS232-Kabel1.jpg|miniatur|RS-232-Kabel zur seriellen Datenübertragung]]

Bei der seriellen Datenübertragung ist es mitunter möglich, ein Paritätsbit zu vereinbaren.<br />
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.<br />

'''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.

<code id="541dd916e65d1">
(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))))))))
</code>

<run id="541dd916e6653">
(bitliste 10)
</run>

Zurück zum [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der Algorithmusbegriff|Algorithmusbegriff]].