Rechneraufbau & Rechnerstrukturen, Folie 1.1 © W. Oberschelp, G. Vossen

W. OberschelpG. Vossen

Kapitel 1

Rechneraufbau & Rechnerstrukturen, Folie 1.2 © W. Oberschelp, G. Vossen

1. Schaltfunktionen und ihre Darstellung

Zahlendarstellungen

Boolesche Algebra

Schaltfunktionen und Boolesche Funktionen

Schaltnetze

Geordnete binäre Entscheidungs-Diagramme (OBDD)

Rechneraufbau & Rechnerstrukturen, Folie 1.3 © W. Oberschelp, G. Vossen

b-adische Darstellung natürlicher Zahlen

Rechneraufbau & Rechnerstrukturen, Folie 1.4 © W. Oberschelp, G. Vossen

Boolesche Körper

Rechneraufbau & Rechnerstrukturen, Folie 1.5 © W. Oberschelp, G. Vossen

Boolesche Algebra

Rechneraufbau & Rechnerstrukturen, Folie 1.6 © W. Oberschelp, G. Vossen

Gesetze einer Booleschen Algebra

Rechneraufbau & Rechnerstrukturen, Folie 1.7 © W. Oberschelp, G. Vossen

Schaltfunktionen

I O

Rechneraufbau & Rechnerstrukturen, Folie 1.8 © W. Oberschelp, G. Vossen

Weitere Beispiele

1

2 3

4 5

k

k

k

k k

k

k

2

3 4

5

7

6

8k

A

k 1

k 9

Rechneraufbau & Rechnerstrukturen, Folie 1.9 © W. Oberschelp, G. Vossen

Boolesche Funktionen

Rechneraufbau & Rechnerstrukturen, Folie 1.10 © W. Oberschelp, G. Vossen

1-stellige Boolesche Funktionen

Rechneraufbau & Rechnerstrukturen, Folie 1.11 © W. Oberschelp, G. Vossen

2-stellige Boolesche Funktionen

Rechneraufbau & Rechnerstrukturen, Folie 1.12 © W. Oberschelp, G. Vossen

Beispiel

Rechneraufbau & Rechnerstrukturen, Folie 1.13 © W. Oberschelp, G. Vossen

Darstellungssatz für Boolesche Funktionen

Rechneraufbau & Rechnerstrukturen, Folie 1.14 © W. Oberschelp, G. Vossen

Beispiel (Forts.)

Rechneraufbau & Rechnerstrukturen, Folie 1.15 © W. Oberschelp, G. Vossen

Grundbausteine zur Realisierung von Booleschen Funktionen

x y+ x y+

(K omplement-G atter)N egation

A ddition(O der-G atter)

M ultip lika tion(U nd-G atter)

x

xy

xy

F unktion

x x x

IE E E -S ymbo l

U nserS ymbo l

xy

xyx y x y

Rechneraufbau & Rechnerstrukturen, Folie 1.16 © W. Oberschelp, G. Vossen

Beispiel (Forts.)

1, x2 , x3 )f(x

x 2 x 3x1

Rechneraufbau & Rechnerstrukturen, Folie 1.17 © W. Oberschelp, G. Vossen

Beispiel (Forts.)x 1 x 2 x 3

f(x1, x2 )3, x

Rechneraufbau & Rechnerstrukturen, Folie 1.18 © W. Oberschelp, G. Vossen

DAG-Darstellung

v

^^

^ ^

I nput I nput I nput

O utput

^

^

v

Rechneraufbau & Rechnerstrukturen, Folie 1.19 © W. Oberschelp, G. Vossen

Flimmerschaltung

zv

x

Rechneraufbau & Rechnerstrukturen, Folie 1.20 © W. Oberschelp, G. Vossen

Geordnete binäre Entscheidungs-Diagramme (OBDD)

OBDD: Ordered Binary Decision Diagrams

Ein OBDD zur Variablenordnung x1 <…<xn ist ein markierter, gerichteter, zykelfreier Graph (DAG) mit einem Startknoten (Wurzel) und zwei Endknoten (Blätter).

Die beiden Blätter sind mit 0 oder 1 markiert, die anderen Knoten haben je zwei unterscheidbare Ausgänge 0 und 1 und sind mit Variablen derart markiert, dass bei jedem vollen Weg (d.h. einem Pfad, der von der Wurzel zu einem Blatt führt) die Reihenfolge der hierbei an den Knoten auftretenden Variablen verträglich mit der gegebenen Ordnung ist, d.h. die Indizes treten in der vorgegebenen Reihenfolge (evtl. mit Auslassungen) auf.

Ein OBDD stellt eine Boolesche Funktion f dar, wenn bei jedem vollen Weg die Variablenbelegung zu demjenigen Blatt führt, das in der Funktionstabelle von f festgelegt ist. Im OBDD fehlende Variablen können übergangen werden.

Definition:

Rechneraufbau & Rechnerstrukturen, Folie 1.21 © W. Oberschelp, G. Vossen

OBDD zur Ordnung x1 < x2 < x3 < x4

x1

x2 x2

x3x3x3x3

x4 x4 x4x4 x4x4x4x4

1 0

Rechneraufbau & Rechnerstrukturen, Folie 1.22 © W. Oberschelp, G. Vossen

Boolesche Funktion dazu

Rechneraufbau & Rechnerstrukturen, Folie 1.23 © W. Oberschelp, G. Vossen

OBDD zur Schwellenwertfunktion T25

x1

x2 x2

x3x3

x4

x5

x4

1 0

Rechneraufbau & Rechnerstrukturen, Folie 1.24 © W. Oberschelp, G. Vossen

Ende Kapitel 1