Joined: Sep 25, 2006
Posts: 688
Status: Offline
|
|
Meiner Meinung nach kann man das Minimalpolynom noch nach einem anderen Verfahren bestimmen und zwar bei n Variablen in der Schaltfunktion mit höchstens n Iterationen. Wahrscheinlich mache ich noch irgendwo einen riesigen Denkfehler, aber ich finde ihn nicht.
Meine Überlegungen und der (versuchte) Beweis sind wahrscheinlich etwas "abstrus", ich wäre Ihnen (und jedem anderen) daher wirklich *überaus* dankbar, wenn Sie die Mühe auf sich nehmen könnten, die Ausführungen durchzusehen.
Kurz skizziert durchlaufe ich die Menge der Implikanten, wähle in jedem Durchlauf den relativ billigsten Implikanten aus, füge ihn der Lösungsmenge hinzu und entferne ihn und alle anderen Implikaten, die von ihm überdeckt werden aus dem verbleibenden Teilproblem. Das wiederhole ich so lange, bis die Implikatenmenge leer ist. Da maximal n Implikanten vorhanden sind, ist eine Lösung nach maximal n Durchläufen gefunden.
Jetzt versuche ich mich einmal etwas konkreter auszudrücken:
[Anmerkung: #M stellt wie immer hier im Kurs die Kardinalität von M dar]
Sei f eine n-stellige Schaltfunktion, sei A = {1,0}^n, Tr(f) = {a aus A| f(a) = 1}, M die Menge der Implikaten von f, L(m) die Formelgrösse eines Monoms m, jeweils wie im Skript definiert. Sie I die Menge der Monome im Minimalpolynom.
Sei m aus M ein Monom, a aus A. Sei phi_m(a) eine Einsetzung von a in das Monom m. Sei die Menge aller Variablenbelegungen, für die m unter f den Wert 1 annimmt V_m = {a aus A | phi_m(a) = 1}. Die große Vereinigung von V_m für alle m aus M entspricht somit wieder Tr(f), und V_m ist Teilmenge von Tr(f).
Ich gehe nun wie folgt vor:
Im Anfang:
setze I := leere Menge
ITERIERE:
[finde den mit der Anzahl der abgedeckten Variablenbelegungen gewichtet günstigsten Implikanten]
Ermittle für jedes Monom m aus M die gewichteten Kosten: setze k_m = L(m) / #V_m. Ermittle das wertmäßig kleinste k_m. Wenn mehr als ein k_m mit gleichem Wert existieren, dann wähle ein Beliebiges, hier das im Auftreten Erste. Setze m = dem zum gewählten k_m gehörenden m.
Setze I := I vereinigt m.
[Jetzt entfernen wir alle Variablenbelegungen aus Tr(f), die durch m "abgedeckt" werden.]
Setze Tr(f)' = Tr(f) \ {b | b in V_m}
Setze V_m' für alle m aus M = {a aus A' | phi_m(a) = 1}
Setze M' = M \ {n aus M | V_m' ist leere Menge}
Wenn M' ungleich der leeren Menge: führe eine weitere Iteration für A', V_m', M'
Die Iteration terminiert, wenn alle Variablenbelegungen durch Implikanten abgedeckt wurden. Die Menge L beinhaltet nun alle Monome eines Minimalpolynomes (dieses ist nicht eindeutig bestimmt). Das Minimalpolynom selbst ist somit das "grosse oder" über alle l aus L.
Mit dem formalen Beweis tue ich mich naturgemäß noch schwer. Ich versuche, meine Überlegung darzustellen: von entscheidender Bedeutung ist die zur Findung des billigsten Monoms vorgenommene Gewichtung. Ich ermittele jeweils die Formelgrösse, und teile diese dann durch die Anzahl der Variablenbelegungen, die durch das Monom abgedeckt werden. Ich erhalte somit die Kosten zur Realisierung einer einzigen Variablenbelegung.
Wichtig ist dabei die Struktur des Hypercubes. Dieser hat n Dimensionen. Ich gehe zunächst einmal davon aus, dass es keine "don't care" Belegungen in f gibt. Dann spannt jeder Implikant einen Unterraum innerhalb des Hypercube auf (die abgedeckten Belegungen müssen somit immer einer Zweier-Potenz entsprechen). Der Unterraum hat somit k = log(#V_m) Dimensionen, daraus folgt, dass das Monom Teil eines (n-k) dimensionalen Raumes dieser 2^k-Unterräume ist. Dieser Raum hat somit (n-k) Basen. Jede einzelnen im Monom benutzte Variable bildet aber genau eine Basis. Somit besteht das Monom aus genau (n-k) Variablen. Der Einfachheit halber gehe ich nun davon aus, dass die Kosten einer einzelnen Variable 1 betragen (ich kann ja die invertierten Variablenbelegungen einmalig ermitteln und jede Variable sowohl invertiert als auch nicht invertiert zur Verfügung stellen[mathematisch so bedenklich ausgedrückt, aber im Schaltnetz realisierbar]).
Dann muss ein Monom, das ein anderes Monom echt überdeckt, immer geringere gewichtete Kosten besitzen als das überdeckte. Sei m_u das überdeckte Monom, m_b das Monom, das m_u überdeckt. Eine Überdeckung kann nur dann vorliegen, wenn der m_u gebildete Unterraum (UR) vollständig in dem von m_b gebildeten Unterraum enthalten ist. Sei d_u die Anzahl der Dimensionen des UR von m_u, d_b die der des UR von m_b. Dann ist immer d_u < d_b, (bzw. d_u = d_b wenn die Monome sich gegenseitig überdecken, was ich aber im Moment nicht betrachte). Daraus folgt, dass L(m_b) < L(m_u) .
Setze b = d_u - d_b, die Anzahl der Basen, die m_b weniger besitzt als m_u [und somit d_b = d_u - b]. Dann ist L(m_u) = L(m_b) + b. Gleichzeitig überdeckt m_b aber b Dimensionen des Hypercube mehr als m_k. Sei d die Anzahl der von m_b zusätzlich überdeckten einzelnen Variablenbelegungen wie folgt:
Der Gesamtraum ist n-Dimensional. Die Anzahl der Elemente in dem von m_b aufgespannten Unterraum beträgt somit #V_m_b = 2^(n-d_b), analog beträgt die Anzahl der in dem von m_u aufgespannten Unterraum #V_m_u = 2^(n-d_u). Dann ist
d = #V_m_b - #V_m_u
= 2^(n-d_b) - 2^(n-d_u)
= 2^(n - (d_u - b)) - 2^(n - d_u) mit db=... oben
= 2^(n - d_u + b) - 2^(n - d_u)
Setze h = n - d_u, dann vereinfacht:
= 2^(h + b) - 2^h
Dabei ist h aus IN_0 und (unter unseren Voraussetzungen) b aus IN.
Mit vollständiger Induktion kann gezeigt werden, dass für alle h, b immer gilt
d >= 2^b
Damit wächst #V_m_b mindestens um den Faktor d schneller als #V_m_u und somit potenziell schneller. Insbesondere ist #V_m_b >= #V_m_u * d [und somit #V_m_b / d >= #V_m_u] und somit #V_m_u <= #V_m_b / d.
Weiter wächst d deutlich schneller als b (das linear wächst), insbesondere gilt immer b < d und b <= log(d).
Die gewichteten Kosten werden nun aber berechnet als k = L(m) / #V_m, hier also
k_b = L(m_b) / #V_m_b und
k_u = L(m_u) / #V_m_u
mit L(m_u) = L(m_b) + b sowie #V_m_u <= #V_m_b / d
und somit: k_u >= (L(m_b) + b) / (#V_m_b / d)
Ich muss zeigen, dass immer k_u > k_b, also k_u - k_b > 0:
L(m_b) + b / (#V_m_b / d) - L(m_b)/#V_m_b
= ((L(m_b) + b)*d)/#V_m_n - L(m_b)/#V_m_b
= (d(L(m_b) + b) - L(m_b)) / #V_m_b
Da d >= 2^b, ist d(L(m_b) + b) - L(m_b) > 0, außerdem ist nach Konstruktion #V_m_b > 0. Da damit sowohl Zähler als auch Nenner > 0 sind, ist auch der Term als solches > 0. Daraus folgt aber, dass k_u > k_b ist, die Kosten des überdeckten Monoms sind also grösser als die Kosten des überdeckenden Monoms.
Dadurch wird in der obigen Iteration immer jeweils das überdeckende Monom ausgewählt. Überdecken sich nun zwei Monome gegenseitig, so kann man analog beweisen, dass die Kosten beider Monome identisch sind. Man kann daher ein Beliebiges wählen.
Da sich diesem Fall die Monome vollständig überdeckten, werden auch die zu betrachtende Restmengen Tr(f)', V_m' und M' sich nicht verändern. Daher kann die Iteration ohne weitere Beachtung des Sonderfalls fort geführt werden.
Sofern in der Schaltfunktion "don't care" Belegungen vorkommen, muss meiner Meinung nach der Beweis angepasst werden. Allerdings meine ich, dass die Grundstruktur des Beweises erhalten bleibt, da sich durch die "don't care" Belegungen die Struktur der zu betrachtenden Räume nicht ändert. Ich meine sogar, der Unterschied liegt nur in der Findung von k. Hier ist k nicht mehr k = log(#V_m) sondern k = [log(#V_m)], wobei [] Gauss-Klammern darstellen sollen, die nach oben aufrunden.
Im Fazit meine ich, dass man nach dem beschriebenen Verfahren die Überdeckung in allen Fällen mit O(n) finden kann... was mich natürlich wieder bedenklich stimmt. Ich habe allerdings bisher keinen Fall konstruieren können und auch kein Argument gefunden, wo das nicht funktioniert. Das liegt wahrscheinlich daran, dass ich in meinem Gedankengebilde mittlerweile gefangen bin...
Für Hinweise wäre ich daher überaus dankbar.
Mit freundlichen Grüßen,
Rainer Gerhards |
|
|
| |
|
Home Page 
Administration 
Logout 
Web Links 
FAQ
Search
Register
Log in to check your private messages
Log in
Maximize
::