4. Vergleich von Zahlen

Vergleich von Zahlen

  • *

    Hallo,

    *wusste jetzt auch nicht recht wo ich diese Frage rein packen kann*

    ich habe mal ne Frage zu den Vergleich zweier Bitfolgen a und b auf a<b und a=b. Und dies in einen Schaltplan, oder als boolescher Ausdruck.
    Dafür darf ich AND OR NOT und XOR Bausteine verwenden.

    Am Anfang würde ich die "Länge" der Bitfolgen a und b vergleichen wollen, falls nun a länger ist folgt sofort, dass a>b ist, somit muss irgend wo und wie eine 1 ausgegebenen werden. Wie kann ich diesen Anfang in einen Schaltplan darstellen?
    Falls die Längen gleich sind, fängt man bei den vordersten Bit von a und b an und vergleicht, wenn der forderste Bit bei a=1 und b=0, dann folgt a>b, wenn a=0 und b=1, dann a<b und wenn a=0 und b=0 oder a=1 und b=1, dann muss man zum nächsten Bit nach "rechts"( man kann dies doch einfach per rechtsshiften machen, aber wie kann ich dies im Schaltplan darstellen).

    Hoffe auf ein paar Tipps oder Links:)

    MfG
    Storm

    0
  • F

    Du könntest das ganze über Rekursion lösen:
    (A_{l-1},\dots,A\_0)<(B\_{l-1},\dots,B\_0) \Leftrightarrow (A\_{l-1},\dots,A\_k)<(B\_{l-1},\dots,B\_k) \vee \par ((A\_{l-1},\dots,A\_k)=(B\_{l-1},\dots,B\_k) \wedge(A\_{k-1},\dots,A\_0)<(B\_{k-1},\dots,B_0))
    Daraus könntest du dann z. B. einen linear kaskadierten oder baumartigen Komparator bauen, indem du die Bits einzeln vergleichst und über Verknüpfungsmodule den Gesamtausdruck auswertest.
    Das wäre mein Tip 🙂
    Sind wirklich Bitfolgen unterschiedlicher Länge zugelassen, oder haben die Zahlen eine feste Bitlänge und sehen dann halt so aus 0...010101?

    Für "=" natürlich äquivalent ...

    0
  • *

    Hi,

    es ist nicht angegeben, dass die Bitfolgen gleich lang sind, aber man kann sicher die kürzere mit Nullen auffüllen. Oder ich nehme einfach an, dass diese schon so in der Art wie du geschrieben hasst "zu den Vergleich ankommen".

    Hmm, irgend was kapier ich da noch nicht. In der Rekursion steht ja:
    a und b Bitfolgen
    a<b äquivalent zu (aI-1...ak);
    bis zu welchen k, ich denke bis jetzt bis zu der Stelle wo die Stellen von a und b gleich sind, z.B. [11001] und [11000] wäre k=3?
    Erst mal bis dahin, vielleicht erklärt sich dann das andere danach.

    Danke für die Hilfe, ist der erste Schaltplan den wir bauen müssen...

    Habe noch eine pdf gefunden:
    http://www-date.upb.de/EDU/LEC/TIA/Vorlesung/arithmetik/Druckversion/vGESAMT_4.pdf.gz

    0
  • F

    k ist frei wählbar, du unterteilt den Vergleich in kleinere Vergleiche, z. B. erhälst du für k = l-1 einen linear aufgebauten Komparator.

    0
  • *

    Ah, danke

    habe jetzt solch ein Komperator aufgebaut und es klappt auch:), nun leider noch ein Problem. Die Bitfolgen a und b sollen nun im 2-er Komplement sein und verglichen werden. Da habe ich jetzt erst mal überlegt, dass ich ja nicht bis zum vordersten Bit(ganz links) sondern nur bis zum vorletzten auf < und = testen muss, denn das vorderste Bit repräsentiert ja das Vorzeichen. Nun habe ich das probiert in einer Schaltung zu realisieren. Bin aber auf ein paar Probleme gekommen.
    an und bn sind die Vorzeichenbit.
    Q ist der Ausgang für "<" bis zum Bit n-1
    Q' ist der Ausgang für "=" bis zum Bit n-1

    E ist der Ausgang für "<" mit Vorzeichen
    E' ist der Ausgang für "=" mit Vorzeichen

    Nun habe ich folgende Fälle:
    Fall: an=1 und bn=0
    - a<b also Q=1 und Q'=0 führt zu a<b also E=1 und E'=0
    - a>b also Q=0 und Q'=0 führt zu a<b also E=1 und E'=0
    - a=b also Q=0 und Q'=1 führt zu a<b also E=1 und E'=0
    Fall: an=0 und bn=1
    - a<b also Q=1 und Q'=0 führt zu a>b also E=0 und E'=0
    - a>b also Q=0 und Q'=0 führt zu a>b also E=0 und E'=0
    - a=b also Q=0 und Q'=1 führt zu a>b also E=0 und E'=0
    Fall an=bn
    - es bleibt alles gleich, also Q=E und Q'=E'

    Das Problem ist diese Fälle in einen Schaltplan zu realisieren. Mein Anfang war:
    "x" := xor
    "*" := and
    "+" := or
    "~" := not
    Am Anfang prüfe ich (an x bn) und das verknüpfe ich dann mit Q', also E'=((an~ x bn)*Q'). Dies dürfte eigentlich schon mal für den "="-Ausgang klappen.

    Für den "<" Ausgang habe ich bis jetzt keinen funktionierenden Plan gefunden. Zur Verknüpfung von Q hatte ich noch verglichen ob nun an=1 oder
    bn=1 ist, mittels (an x bn)*bn.

    MfG
    Storm

    0
  • F

    Hmm, reicht es nicht die beiden Bits an und bn zu invertieren? Dann müßtest du den Vergleich wie bei unsigned int durchführen können, oder?

    0
  • *

    Ja, das ist eine gute Idee, ich frag mich warum ich die einfachen Lösungen nie sehe... Werd es gleich mal "einbauen" und testen.

    Nebenbei, gibt es eine Art Programm wo man solche Schaltpläne aufgbauen und testen kann? Ich denke da an sowas ähnliches wie Matlab, dort kann man glaub auch eine Art Schaltplan bauen.

    0
  • F

    Ja, mit Simulink könnte man sowas machen. Hast du schon mal mit VHDL gearbeitet? Guck dir mal VHDL Simili™ an, das ist eine freie Entwicklungsumgebung. Damit kannst du solche Schaltungen dann programmieren und am Computer simulieren.

    0
  • F

    Oder auch:
    http://www.tkgate.org/

    0
  • *

    Danke für deine Hilfe und Auskunft:)
    Habe mich bis jetzt noch nicht mit der Programmierung von solchen Schaltungen befassen müssen. Werd mir aber mal dafür Zeit nehmen müssen, ist doch besser wenn man dann ein Programm hat womit man solche Dinge testen kann.

    MfG
    Stefan

    0
Anmelden zum Antworten