Kombinatorik

• Bezeichnung auch: Schaltnetze, Transfer-Logik

• Ausgangssignale Y lassen sich eindeutig aus den Eingangssignalen X berechnen, wobei

  • keine inneren Zustände (Gedächtnisfunktionen) vorkommen und

  • keine logischen Rückkopplungen existieren.

  Y = f (X)

• Codeumsetzer:

  • Codierer und Decodierer,

  • Multiplexer,

  • Arithmetisch-logische Einheiten

  • ...

• Zahlencodierung

• Logische Codes und Anzeigecodierungen

• Buchstaben- und Symbolcodierungen

engl. Encoder/Decoder meist verwendet für

• Encoder, Codierer: Logischer Code - Dualzahl

• Decoder: Dualzahl - Logik- oder Anzeigecode

Zahlencodierung mit fester Stellenwertigkeit, n = Anzahl der Bits

BILD

Spezielle Zahlencodierung nach logischen Vorgaben

• z.B.: Ändere zur benachbarten Zahl immer nur 1 Bit

• Beispiele: BILD

Folie

führen die Umrechnungen zwischen verschiedenen Codierungen aus

BILD

BILD

BILD

Auswahl aus mehreren Datenkanälen: n auf 1

BILD

Anwendungen:

• Netzwerk - Routing

• Datenquellen-Auswahl

• Datenübertragungen im Zeitmultiplex-Verfahren, Senderseite

Gegenstück zum Multiplexer: Datenweitergabe an n Ausgänge

BilD

Anwendungen:

• Routing in Computernetzwerken

• Alternative Weitergabe von Ausgabedaten

• Datenübertragungen im Zeitmultiplex-Verfahren, Empfängerseite

• Überprüfung, ob Anzahl der Einsen gerade oder ungerade

BILD

Anwendungen:

• Erzeugung von Prüfbits, wenn Datenfehler nicht auszuschließen sind

• Bestandteil von Codierern für Datenübertragung

• Pseudo-Zufallsgeneratoren

BILD

Anwendungen:

• Increment-Logik (für Zähler-Anwendungen)

• Bestandteil des Volladdierers

• Addition der niedrigste Stelle von mehstelligen Addierern

Anwendungen:

• Bestandteil von mehrstelligen Addierern, Multiplizierern, Rechenwerken

BILD

BIlD

Anwendungen:

• Bestandteil von Multiplizierern und Rechenwerken, auch für die Subtraktion nutzbar

Beachte: Bei großer Bitbreite (z.B. n = 64) große Verzögerung in der Übertragskette.

Ausweg: Zusätzliche Übertragslogik mittels Generate / Propagate

Einfache Subtraktion von zwei Bits ohne Übertragseingang

BILD

Anwendungen:

• Decrement-Logik (für Zähler-Anwendungen)

• Bestandteil des Vollsubtrahierers

• Subtraktion der niedrigste Stelle in mehstelligen Subtrahierern

• Einfache Subtraktion von zwei Bits mit Übertragseingang

BILD

Anwendungen:

• Bestandteil von mehrstelligen Subtrahierern und komplexen Rechenwerken

• Zu subtrahieren seinen zwei n-stellige Dualzahlen

BILD

Anwendungen:

• Bestandteil von Rechenwerken, insbesondere Vergleichsoperationen, auch für die Division genutzt

• Auch hier ist die Anwendung einer schnellen Übertragslogik sinnvoll

• Größenvergleich zweier n-stellige Dualzahlen A und B

• Inputs: Dualzahlen A und B

• Outputs liefern drei mögliche Aussagen (A>B); (A=B); (A<B)

• Unterschiedliche technische Lösungen

  
  

BILD

Anwendungen:

• Ergebnisse dienen der Steuerung von Programmabläufen

• Die elementare 1-Bit-Multiplikation entspricht dem AND:

BILD

Mehrstelliger Multiplizierer müssen die Zwischenergebnisse aller Elementar-Multiplikationen aufsummieren. Beispiel für 4Bit:

BILD

• Jede Binärstelle des Operanden A muss mit jeder Binärstelle des Operanden B multipliziert (AND-verknüpft) werden.

• Alle Partialprodukte müssen entsprechend ihrer Stellenwertigkeiten addiert werden,

• also enthält jede Zelle einen Volladdierer.

• Die Überträge werden nach links und die Summen nach untenweitergeleitet.

• Verbesserung: Schnelle Übertragslogik

BILD

• Hohe Integrationsgrade erlauben >10^7 Gatter je mm^2 Chipfläche

• Jede Kombinatorische Schaltung lässt sich als KDN/KKN ausdrücken

• Inputs: n Eingänge: xn-1; xn-2; ..... ; x1; x0

• Outputs: spezif. OR/AND-Verknüpfung der Vollkonjunktions/diskuntionsterme

• Eine LUT (LookUp-Table) ist eine "in Hardware gegossene" Logiktabelle

Der Weg zur technischen Lösung:

• n = Anzahl aller Logikeingänge

• Adressbereich 2n = Tabellenzeilen

• m = Anzahl der Ausgabe-Bits

• Größe der LUT: 2n * m

• KDN benötigt 2n Vollkunjunktionen

• OR-Verknüpfungen in Form einer "Speichermatrix"

Kennzeichen:

• Technischer Aufwand hoch

• Rechenzeiten sehr kurz

Beispiele:

BILD

FOLIE

• Wesentlicher Bestandteil aller Prozessoren

• Inputs: Zwei Operanden A und B sowie ein Steuervektor S

• Output: Ergebnis der Operation Q incl. Nebenergebnisse (Flags)

• Umfang möglicher Operationen bstimmt die Komplexität

• Operandenbreite n = 4....128 Bit

BILD

Anwendung innerhalb einer CPU für Rechenleistungen und logische Operationen

• Logikoperationen: Alle Verknüpfungen parallel für alle Bitpositionen ohne Auswirkungen auf benachbarte Bitpositionen

• Arithmetik: Übertragsverarbeitung nötig, Auswirkung auf benachbarte Bitpositionen

Beispiel für eine einfache Logikstruktur: n-Bit-Logikoperation / Addition

BILD

• Es gibt viele verschiedene Codierungen, die meist im Hinblick auf technische Anwendungen definiert werden.

• Zur Umrechnung zwischen verschiedenen Codierungen stellt man Logiktabellen auf, woraus sich Logikpläne entwickeln lassen.

• Multiplexer besitzen n Dateneingänge und m Auswahleingänge, die vorgeben, welcher Dateneingang den Ausgang bestimmt.

• Demultiplexer verteilen die Daten eines Einganges auf mehrere Ausgänge. Gesteuert wird das von m Auswahleingängen.

• Paritätsgeneratoren ermitteln, ob ein n-Bit-Datenwort eine gerade oder ungerade Anzahl von Einsen enthält.

• Addierer, Subtrahierer, Komparatoren, Multiplizierer usw. führen mathematische Operationen auf logische Verknüpfungen zurück.

• Eine LUT (LookUp-Table) kann jede beliebige Kombinatorik in Form ihrer KDN oder KKN abbilden, ist technisch entsprechend aufwendig.

• Arithmetisch-Logische Einheiten sind komplexe Logikschaltungen, mit denen man zwischen verschiedenen Operationen wählen kann.