58 lines
3.6 KiB
Markdown
58 lines
3.6 KiB
Markdown
## Logiksynthese und -minimierung
|
|
|
|
- #### **Deduzierte Schaltungen lassen sich nicht effizient "von Hand entwickeln"**
|
|
-> Wir brauchen Methodik für Schaltkreissynthese
|
|
|
|
- #### **Logiksynthese und -minimierung: Versuch, Logik der Schaltung:**
|
|
- zu generieren bzw.
|
|
- zu minimieren
|
|
|
|
- #### **Unterscheidung zwischen:**
|
|
- **kombinatorischer Synthese** (Realisierung einer Booleschen Funktion)
|
|
- **sequentieller Synthese** (Realisierung eines endlichen **Automaten**; kann als Boolesche Funktion repräsentiert werden)
|
|
|
|
- #### Ausgangspunkt: Funktionsbeschreibung (Wahrheitstabelle, Boolescher Ausdruck, ... )
|
|
|
|
## Wdhlg. : Synthese (simpel)
|
|
|
|
- #### Realisierung beliebiger Wahrheitstabellen durch **<font color="#00b0f0">Grundgatter</font> möglich
|
|
- #### Vorgehen:
|
|
- Für jede Zeile mit Ausgabewert 1:
|
|
Und-Gatter mit passender Eingangsbeschaltung
|
|
- Oder-Verknüpfung aller Und-Gatter
|
|
|
|
- ### Funktioniert für alle Tabellen, aber
|
|
- <font color="#c00000">teuer</font>
|
|
- <font color="#c00000">nicht skalierbar</font>
|
|
![[20260119_kmaps_260129_183719.jpg]]
|
|
|
|
## Weitere Grundlagen
|
|
|
|
- #### Die Booleschen Ausdrücke <font color="#ff0000">x<sub>i</sub></font> und <font color="#ff0000">x<sub>i</sub>' </font>heißen <font color="#00b0f0">Literale</font>
|
|
- x<sub>i</sub> ist <font color="#00b0f0">positives Literal</font>
|
|
- x<sub>i</sub>' ist <font color="#00b0f0">negatives Literal</font>
|
|
- #### Eine Konjunktion von Literalen heißt <font color="#00b0f0">Monom</font>, wenn:
|
|
- jedes Literal kommt höchstens einmal vor
|
|
- es kommt nicht sowohl das <font color="#00b0f0">positive</font> als auch das <font color="#00b0f0">negative</font> <font color="#00b0f0">Literal</font> einer Variable vor
|
|
- Monome: **x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>, x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>'
|
|
- #### Ein Monom heißt <font color="#00b0f0">vollständig</font> oder <font color="#00b0f0">Minterm</font>, wenn <font color="#ff0000">jede Variable</font> entweder als <font color="#00b0f0">positives</font> oder als <font color="#00b0f0">negatives</font> <font color="#00b0f0">Literal</font> vorkommt
|
|
|
|
- #### Eine Disjunktion von paarweise verschiedenen Monomen heißt <font color="#00b0f0">Polynom</font>. Sind alle <font color="#00b0f0">Monome</font> des <font color="#00b0f0">Polynoms</font> <font color="#00b0f0">vollständig</font>, so heißt das Polynom <font color="#00b0f0">vollständig</font>
|
|
|
|
- #### Eine Boolesche <font color="#00b0f0">Funktion</font> ist von ihrer Darstellung als Formel zu unterschieden
|
|
- Die <font color="#00b0f0">Interpretationsfunktion</font> $\psi$ weist einer Formel die entsprechende Funktion zu
|
|
- $f = (a+b) * c$ und $g = a * c + b * c$ sind unterschiedliche Formeln aber $\psi(f) = \psi(g)$
|
|
## Logiktoptimierung
|
|
|
|
- #### Gegeben: Eine Boolesche Funktion $f$
|
|
- #### Ziel: Darstellung von $f$ als <font color="#00b0f0">Minimalpolynom</font> $p$, das heißt ein Polynom sodass gilt:
|
|
- $\psi(p) = f$
|
|
- Die Anzahl an <font color="#00b0f0">Monomen</font> in $p$ ist **minimal**
|
|
- Die Anzahl der <font color="#00b0f0">Literale</font> in $p$ ist **minimal**
|
|
- #### Idee: $x_1x_2x_3 + x_1x_2\bar{x_3} = x_1x_2$
|
|
- Die Belegung von $x_3$ hate keinen Einfluss auf den Wahrheitswert des Polynoms
|
|
- $x_1x_2$ ist ein sogenannter <font color="#00b0f0">Implikant</font> von $x_1x_2x_3 + x_1x_2\bar{x_3}$
|
|
- #### Allgemein: Ein Monom(!) $q$ ist ein Implikant der Funktion $f$ falls $\psi(q) \leq f$
|
|
Das bedeutet das der Implikant kleiner oder optimierter als der Funktion ist
|
|
- #### <font color="#00b0f0">Ein Primimplikant von f</font> ist ein maximaler Implikant $q$ von $f$, d.h. es gibt keinen Implikanten $s(s \neq q)$
|
|
- |