Achtung: Dies ist eine historische Web-Site. Aktuell ist https://rainer.gerhards.net/ (engl) bzw https://www.rainer-gerhards.de/ (deutsch). Alle dynamischen Funktionen, Formulare etc auf dieser Seite sind abgeschaltet.
Datenschutzerklärung Impressum

 
Aug 01, 2017 - 06:46 PM


Select language
Preferred language:


Online
There are 1 unlogged user and 0 registered users online.

You can log-in or register for a user account here.

Anmeldung




 


 Log in Problems?
 New User? Sign Up!



Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Author Message
rgerhardsOffline
Post subject: Bestimmung von Minimalpolynomen  PostPosted: Mar 06, 2009 - 07:32 AM



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
 
 View user's profile Send private message  
Reply with quote Back to top
Display posts from previous:     
Jump to:  
All times are GMT + 1 Hour
Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Powered by PNphpBB2 © 2003-2007 The PNphpBB Group
Credits
:: RSS Feed: ::
Page created in 0.13162112236 seconds.

Ferientips - das Urlaubsweb - Jan Gerhards - Ulrike Gerhards - Ulrike Gerhards Foto Site