Schaltkreis Simulation

Dieses Applet wurde für Vorträge von Wiland Schmale und Kornelius Walter am Tag der Mathematik 2004 der Carl von Ossietzky Universität Oldenburg geschrieben.

http://www.uni-oldenburg.de/tdm/2004/Vortraege/Mitmachvorlesung.html

Der Titel des Vortrages lautete Mobil mit Polynomen und Schiebereien und beschäftigte sich mit Moblitelefonen und wie diese ihre Daten versenden.

Das Applet zeigt dabei einen Schaltplan, wie eine technische Realisierung der Multiplikation zweier binärer Polynome aussehen kann.

Das Problem

Die Übertragung von Daten zwischen Moblitelefonen ist nicht fehlerfrei. Bei der Sprache mag dies vielleicht nicht so schlimm sein, da man den anderen auch trotz Rauschen oder Knacken in der Leitung verstehen kann. Jedoch sollten Telefonnummern, Texte, Tarife und andere Daten doch möglichst ohne Fehler übertragen werden.

Die Lösung des Problems liegt in einer Codierung der Daten, so dass trotz Fehlern in der Übertragung, die Daten zurückgewonnen werden können, wenn die Fehleranzahl nicht zu hoch war.

Nur Nullen und Einsen

Wie für viele technische Geräte besteht für ein Moblitelefon die Welt nur aus Nullen und Einsen. Die Sprache wird dabei durch einen Analog-Digital-Wandler in diese Null-Eins-Welt übersetzt.

Die betrachteten Daten sind also eine Folge aus Nullen und Einsen und es stellt sich heraus, dass es sinnvoll ist, sie als binäre Polynome anzusehen. Denn dann kann man Fehler bei der Übertragung dadurch vermeiden, dass die Eingabe (als Polynom) mit Kodierungs-Polynomen multipliziert wird.

Dabei entspricht ein Term $ X^k$ im Polynom einer 1 als $ k$-tem Bit. Gibt es keinen solchen Term, ist das $ k$-te Bit eine 0.

Beispiel:

$\displaystyle D + 1$ $\displaystyle {}\mathop{\widehat{=}} {}\cdots 0\ 0\ 0\ 0\ 1\ 1\ ,$    
$\displaystyle D^2 + 1$ $\displaystyle {}\mathop{\widehat{=}} {}\cdots 0\ 0\ 0\ 1\ 0\ 1$    
$\displaystyle D^7+D^6+D^2+D+1$ $\displaystyle {}\mathop{\widehat{=}} {}\cdots 0\ 0\ 1\ 1\ 0\ 0\ 0\ 1\ 1\ 1\ $    

Um nun mit diesen Polynomen rechnen zu können, muss man wissen, wie man mit 0 und 1 rechnet, wenn es keine 2 gibt.

Dabei ist nur die erste Regel ungewohnt, die wir mit der Merkregel ``doppelt ist nichts'' versehen:

$\displaystyle 1 + 1$ $\displaystyle {}= 0,$ $\displaystyle 1 + 0$ $\displaystyle {}= 1 = 0 + 1,$ $\displaystyle 0 + 0$ $\displaystyle {}= 0,$    
$\displaystyle 1 \cdot 1$ $\displaystyle {}= 1,$ $\displaystyle 1 \cdot 0$ $\displaystyle {}= 0 = 0 \cdot 1,$ $\displaystyle 0 \cdot 0$ $\displaystyle {}= 0.$    

Und dann genauso mit Polynomen. Doppelt ist nichts:

$\displaystyle X + X = 0 ,\ X^2+X^2 = 0 ,\ X^3+X^3=0,\ldots , D^k+D^k=0. $

Hier nun ein paar Beispiele für das Multiplizieren von Polynomen. Man rechnet wie gewohnt, aber doppelt ist nichts!

  1. $ (X+1)\cdot(X+1)=(X+1)^2={X^2+X+X+1=}{X^2+1}$
  2. $ (X^2+X+1)\cdot(X+1)=$
    $ (X^2+X+1)\cdot X+(X^2+X+1)=$
    $ (X^3+X^2+X)+(X^2+X+1)=X^3+1$
  3. $ (X+1)\cdot(X^3+X+1)=(X^4+X^2+X)+(X^3+X+1)= X^4+X^3+X^2+1$

Sieht man sich die Koeffizientenfolgen von folgenden Produkten an, so sieht man, dass ein Multiplizieren mit $ X$ einem Verzögern um eine Stelle entspricht, wenn man die zeitliche Reihenfolge der Bits von rechts nach links liest.

$\displaystyle (X^{6}+X^4+X+1)X \mathop{\widehat{=}} \ldots 0\ 1\ 0\ 1\ 0\ 0\ 1\ 1\ 0$

$\displaystyle (X^{6}+X^4+X+1)X^3 \mathop{\widehat{=}} \ldots 0\ 1\ 0\ 1\ 0\ 0\ 1\ 1\ 0\ 0\ 0 $

Mit Hilfe eines Addierers (wobei 1+1=0 gilt) und Schieberegistern lässt sich also (wie im Applet zu sehen) eine Schaltung für jedes Polynom $ g$ bauen, die eine Bitfolge so verändert, dass sie dem Produkt des zugehörigen Polynoms mit $ g$ entspricht.