Fachrat Informatik - Forum

Quoted

Original von Sascha
Wir suchen eine Mitschrift des zweiten Übungsblattes!!!

Wer hat eine und kann Sie uns zuschicken?!

P.S. Genauer gesagt geht es um den Beweis des MAJ-Problems

MAJ? Du meinst LEQ, oder?

Quoted

Original von Sascha
Es geht um den Vergleich mit n/2. Dieses kommt bei LEQ vor und auch auf Seite 9 (unten)...

Ah, jetzt, ja.

LEQ kann man auf mehrere Weisen lösen. Die erste:

Wenn man die Eingabezahlen a und b im Zweierkomplement addiert (also voneiner subtrahiert, siehe Übungsblatt 1), dann ist das höchstwertige Ergebnisbit genau dann gleich Null, wenn a >= b gilt. Vertauscht man nun a und b erhält man einen Schaltkreis, der LEQ berechnet.


Die zweite Möglichkeit:

Es seien a = a_{n - 1} ... a_{0} und b = b_{n - 1} ... b_{0}.

Es gilt a < b, wenn beim bitweisen Vergleich von a und b (vom LSB zum MSB) die erste Nichtübereinsteimmung bei a eine Null liefert, bei b jedoch eine Eins. Es gilt a = b, wenn alle Bits von a und b übereinstimmen.

Sei e_i = [[ a_i = b_i ]] = (NOT a_i XOR b_i). e_i ist also genau dann eins, wenn a_i = b_i gilt.

Zudem sei d_i = AND_{j = 0}^{i - 1} e_j AND NOT a_i AND b_i. d_i ist also genau dann Eins, wenn alle Bits übereinstimmen, die niederwertiger als das i-te Bit sind, und zudem a_i = 0 und b_i = 1 gilt.

d_n sei dabei AND_{j = 0}^{n-1} e_j.

Nun gilt: [[ a <= b ]] = OR_{i = 0}^{n} d_i.

Sauber! Das war sehr hilfreich! Danke!