"Permutations-Problem"
- Ersteller Widlarizer
- Erstellt am
Widlarizer
Captain Special
Hallo zusammen,
sooo ich bin gerade dabei eine spezielle Ansteuerung für eine Schaltung in meiner Diplomarbeit zu entwerfen.
Grob gesagt habe ich ein Gatter, welches 4 Eingangssignale besitzt.
Das Schaltverhalten des Gatters soll bei verschiedenen Eingangskombinationen untersucht werden.
Das Problem momentan ist die Realisierung dieser Kombinationen, denn:
Jeder Übergang soll nur einmal auftreten.
Also zum Beispiel:
0000 -> 0001 -> 1001 -> 0110 -> bla blub.....
Ok, ich kann mich jetzt natürlich an einem Tag hinsetzen und das alles per Hand aufschreiben. Dauert dann aber wohl recht lange und ich hau garantiert irgendwo einen Fehler rein
Hat jemand eine Idee, wie man das sonst lösen könnte?
Gebe auch einen Kasten Bier aus
sooo ich bin gerade dabei eine spezielle Ansteuerung für eine Schaltung in meiner Diplomarbeit zu entwerfen.
Grob gesagt habe ich ein Gatter, welches 4 Eingangssignale besitzt.
Das Schaltverhalten des Gatters soll bei verschiedenen Eingangskombinationen untersucht werden.
Das Problem momentan ist die Realisierung dieser Kombinationen, denn:
Jeder Übergang soll nur einmal auftreten.
Also zum Beispiel:
0000 -> 0001 -> 1001 -> 0110 -> bla blub.....
Ok, ich kann mich jetzt natürlich an einem Tag hinsetzen und das alles per Hand aufschreiben. Dauert dann aber wohl recht lange und ich hau garantiert irgendwo einen Fehler rein
Hat jemand eine Idee, wie man das sonst lösen könnte?
Gebe auch einen Kasten Bier aus
The G
Lt. Commander
Den Teil hab ich nicht verstanden. Was meinst du damit genau? Dachte erst es geht um alle möglichen Kombinationen, das wäre ja dann einfach zählen von 0 bis 15.
The G
Lt. Commander
Das würde schon seinem eigenen Beispiel wiedersprechen:
Devastators
Grand Admiral Special
ich verstehe das Problem auch nicht.
Bei 4 Bytes gibt es nur 16 Kombinationen
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
fäddisch!
Widlarizer
Captain Special
Hi Jungs,
danke für eure Antworten. Hab mich wohl recht unglücklich ausgedrückt.
Ok, dann hole ich etwas weiter aus:
Devastators, RICHTIG es sind 16 mögliche Zustände, aber nicht Übergänge, von denen gibt es nämlich 256 (oder habe ich mich da verrechnet?)
Ich versuche es am besten Mal anhand eines Beispiels darzustellen. In meiner Studienarbeit musste ich nur mit 2 Quellen arbeiten, hatte also demnach 2 Bits, welche die Schaltung angeregt haben.
Ich verwendete eine IDEALE Pulsquelle (also stur 0 1 0 1 0 1 0 1 0 1 0 1) und eine programmierbare Version davon.
So sahen dann die Übergänge aus:
00 -> 11
11 -> 00
00 -> 10
10 -> 01
01 -> 10
10 -> 00
00 -> 11
11 -> 01
01 -> 11
usw. usw.
Ihr seht, dass die fett markierten Übergänge also doppelt vorhanden sind. Bei 2 Bit sind die Übergänge ja noch überschaubar, denn es sind ja nur 16.
Aber bei 4 Bit sieht das schon etwas anders aus.
Ich suche also so eine Art Zustandsgraph, der mir genau sagt welche Übergänge aufeinander folgen sollen, damit sie sich niemals wiederholen müssen um einen anderen Zustand in der Reihenfolge erst zu ermöglichen.
Wenn ich mein Posting lese, so zweifle ich aber immer noch daran, dass ich mich nun verständlicher ausgedrückt habe.
Bitte nicht böse mit mir sein...*seufz*
Kann sein, dass mich die DA schon etwas ZU sehr schlaucht für heute.
danke für eure Antworten. Hab mich wohl recht unglücklich ausgedrückt.
Ok, dann hole ich etwas weiter aus:
Devastators, RICHTIG es sind 16 mögliche Zustände, aber nicht Übergänge, von denen gibt es nämlich 256 (oder habe ich mich da verrechnet?)
Ich versuche es am besten Mal anhand eines Beispiels darzustellen. In meiner Studienarbeit musste ich nur mit 2 Quellen arbeiten, hatte also demnach 2 Bits, welche die Schaltung angeregt haben.
Ich verwendete eine IDEALE Pulsquelle (also stur 0 1 0 1 0 1 0 1 0 1 0 1) und eine programmierbare Version davon.
So sahen dann die Übergänge aus:
00 -> 11
11 -> 00
00 -> 10
10 -> 01
01 -> 10
10 -> 00
00 -> 11
11 -> 01
01 -> 11
usw. usw.
Ihr seht, dass die fett markierten Übergänge also doppelt vorhanden sind. Bei 2 Bit sind die Übergänge ja noch überschaubar, denn es sind ja nur 16.
Aber bei 4 Bit sieht das schon etwas anders aus.
Ich suche also so eine Art Zustandsgraph, der mir genau sagt welche Übergänge aufeinander folgen sollen, damit sie sich niemals wiederholen müssen um einen anderen Zustand in der Reihenfolge erst zu ermöglichen.
Wenn ich mein Posting lese, so zweifle ich aber immer noch daran, dass ich mich nun verständlicher ausgedrückt habe.
Bitte nicht böse mit mir sein...*seufz*
Kann sein, dass mich die DA schon etwas ZU sehr schlaucht für heute.
Devastators
Grand Admiral Special
00->00
00->01
00->10
00->11
01->00
01->01
01->10
01->11
10->00
10->01
10->10
10->11
11->00
11->01
11->10
11->11
welche sind doppelt, welche fehlen?
bei deinem beispiel sind es links 4 Kombinationen und rechts 4.
die Permutation dieser beiden bleibt dann bei 4*4 = 16.
0000 000 (=0)
0000 001 (=1)
0000 0010 (=2)
0000 0011 (=3)
0000 0100 (=4)
0000 0101 (=5)
0000 0110 (=6)
0000 0111 (=7)
0000 1000 (=8)
0000 1001 (=9)
...
u.s.w.
bei 4*4 Bits bleibt also gleich, halt bis 256
Du brauchst also nur die Zahlen 0-255 ins Binäre Format umwandeln und hast alle 256 Kombinationen
Dein Problem scheint zu sein, dass Du kein System hast die binären Zahlen zu notieren.
Orientiere dich einfach am zugehörigen Dezimalwert, oder sortierst Du die auch so:
1
2
3
5
7
3 (mist, doppelt)
4
9
8
12
11
u.s.w.
Zuletzt bearbeitet:
The G
Lt. Commander
So wie ich das verstanden habe soll das ein Pfad durch alle Kombinationen werden ohne einen Pfad doppelt zu benutzen. Klingt für mich irgendwie nach TSP. Damit dürfte es für große Zahlen verdammt schwer werden, bei 4 Bits müsste sich aber ein einfacher Algo dafür finden. Mein kleines aus den Fingern gesaugtes Programm gibt aus:
Wenn es 256 Übergänge sein sollen fehlen also ein Paar, mal schauen ob ich mir das genauer überlege
EDIT: 256 Übergänge wenn man zu sich selbst verweisen kann, ansonsten 256 - 15 = 241.Immer noch ein Hund drin...
EDIT2: 256 - 16 natürlich, macht 240. Problem gelöst, wo ist mein Bier
Code:
0: 0 -> 1
1: 1 -> 0
2: 0 -> 2
3: 2 -> 0
4: 0 -> 3
5: 3 -> 0
6: 0 -> 4
7: 4 -> 0
8: 0 -> 5
9: 5 -> 0
10: 0 -> 6
11: 6 -> 0
12: 0 -> 7
13: 7 -> 0
14: 0 -> 8
15: 8 -> 0
16: 0 -> 9
17: 9 -> 0
18: 0 -> 10
19: 10 -> 0
20: 0 -> 11
21: 11 -> 0
22: 0 -> 12
23: 12 -> 0
24: 0 -> 13
25: 13 -> 0
26: 0 -> 14
27: 14 -> 0
28: 0 -> 15
29: 15 -> 1
30: 1 -> 2
31: 2 -> 1
32: 1 -> 3
33: 3 -> 1
34: 1 -> 4
35: 4 -> 1
36: 1 -> 5
37: 5 -> 1
38: 1 -> 6
39: 6 -> 1
40: 1 -> 7
41: 7 -> 1
42: 1 -> 8
43: 8 -> 1
44: 1 -> 9
45: 9 -> 1
46: 1 -> 10
47: 10 -> 1
48: 1 -> 11
49: 11 -> 1
50: 1 -> 12
51: 12 -> 1
52: 1 -> 13
53: 13 -> 1
54: 1 -> 14
55: 14 -> 1
56: 1 -> 15
57: 15 -> 2
58: 2 -> 3
59: 3 -> 2
60: 2 -> 4
61: 4 -> 2
62: 2 -> 5
63: 5 -> 2
64: 2 -> 6
65: 6 -> 2
66: 2 -> 7
67: 7 -> 2
68: 2 -> 8
69: 8 -> 2
70: 2 -> 9
71: 9 -> 2
72: 2 -> 10
73: 10 -> 2
74: 2 -> 11
75: 11 -> 2
76: 2 -> 12
77: 12 -> 2
78: 2 -> 13
79: 13 -> 2
80: 2 -> 14
81: 14 -> 2
82: 2 -> 15
83: 15 -> 3
84: 3 -> 4
85: 4 -> 3
86: 3 -> 5
87: 5 -> 3
88: 3 -> 6
89: 6 -> 3
90: 3 -> 7
91: 7 -> 3
92: 3 -> 8
93: 8 -> 3
94: 3 -> 9
95: 9 -> 3
96: 3 -> 10
97: 10 -> 3
98: 3 -> 11
99: 11 -> 3
100: 3 -> 12
101: 12 -> 3
102: 3 -> 13
103: 13 -> 3
104: 3 -> 14
105: 14 -> 3
106: 3 -> 15
107: 15 -> 4
108: 4 -> 5
109: 5 -> 4
110: 4 -> 6
111: 6 -> 4
112: 4 -> 7
113: 7 -> 4
114: 4 -> 8
115: 8 -> 4
116: 4 -> 9
117: 9 -> 4
118: 4 -> 10
119: 10 -> 4
120: 4 -> 11
121: 11 -> 4
122: 4 -> 12
123: 12 -> 4
124: 4 -> 13
125: 13 -> 4
126: 4 -> 14
127: 14 -> 4
128: 4 -> 15
129: 15 -> 5
130: 5 -> 6
131: 6 -> 5
132: 5 -> 7
133: 7 -> 5
134: 5 -> 8
135: 8 -> 5
136: 5 -> 9
137: 9 -> 5
138: 5 -> 10
139: 10 -> 5
140: 5 -> 11
141: 11 -> 5
142: 5 -> 12
143: 12 -> 5
144: 5 -> 13
145: 13 -> 5
146: 5 -> 14
147: 14 -> 5
148: 5 -> 15
149: 15 -> 6
150: 6 -> 7
151: 7 -> 6
152: 6 -> 8
153: 8 -> 6
154: 6 -> 9
155: 9 -> 6
156: 6 -> 10
157: 10 -> 6
158: 6 -> 11
159: 11 -> 6
160: 6 -> 12
161: 12 -> 6
162: 6 -> 13
163: 13 -> 6
164: 6 -> 14
165: 14 -> 6
166: 6 -> 15
167: 15 -> 7
168: 7 -> 8
169: 8 -> 7
170: 7 -> 9
171: 9 -> 7
172: 7 -> 10
173: 10 -> 7
174: 7 -> 11
175: 11 -> 7
176: 7 -> 12
177: 12 -> 7
178: 7 -> 13
179: 13 -> 7
180: 7 -> 14
181: 14 -> 7
182: 7 -> 15
183: 15 -> 8
184: 8 -> 9
185: 9 -> 8
186: 8 -> 10
187: 10 -> 8
188: 8 -> 11
189: 11 -> 8
190: 8 -> 12
191: 12 -> 8
192: 8 -> 13
193: 13 -> 8
194: 8 -> 14
195: 14 -> 8
196: 8 -> 15
197: 15 -> 9
198: 9 -> 10
199: 10 -> 9
200: 9 -> 11
201: 11 -> 9
202: 9 -> 12
203: 12 -> 9
204: 9 -> 13
205: 13 -> 9
206: 9 -> 14
207: 14 -> 9
208: 9 -> 15
209: 15 -> 10
210: 10 -> 11
211: 11 -> 10
212: 10 -> 12
213: 12 -> 10
214: 10 -> 13
215: 13 -> 10
216: 10 -> 14
217: 14 -> 10
218: 10 -> 15
219: 15 -> 11
220: 11 -> 12
221: 12 -> 11
222: 11 -> 13
223: 13 -> 11
224: 11 -> 14
225: 14 -> 11
226: 11 -> 15
227: 15 -> 12
228: 12 -> 13
229: 13 -> 12
230: 12 -> 14
231: 14 -> 12
232: 12 -> 15
233: 15 -> 13
234: 13 -> 14
235: 14 -> 13
236: 13 -> 15
237: 15 -> 14
238: 14 -> 15
239: 15 -> 0Wenn es 256 Übergänge sein sollen fehlen also ein Paar, mal schauen ob ich mir das genauer überlege
EDIT: 256 Übergänge wenn man zu sich selbst verweisen kann, ansonsten 256 - 15 = 241.Immer noch ein Hund drin...
EDIT2: 256 - 16 natürlich, macht 240. Problem gelöst, wo ist mein Bier
Zuletzt bearbeitet:
ich glaub nu weiß ich was der TE meint.
es geht darum Folgen zu finden von 4 Bits, bei denen es keine doppelten gibt und die "verkettet" sind.
Also wenn ich als Startwert 0001 habe, und von da nach 0010 gehe, dann muss sich von 0010 weiter gehen zu einem anderen wert, bzw. kann auch zurück zu 0001, wenn ich dafür von dort aus nicht wieder zu 0010 gehe.
Es darf also jede änderung, von einer zahl zur anderen, nur einmal vorkommen.
es geht darum Folgen zu finden von 4 Bits, bei denen es keine doppelten gibt und die "verkettet" sind.
Also wenn ich als Startwert 0001 habe, und von da nach 0010 gehe, dann muss sich von 0010 weiter gehen zu einem anderen wert, bzw. kann auch zurück zu 0001, wenn ich dafür von dort aus nicht wieder zu 0010 gehe.
Es darf also jede änderung, von einer zahl zur anderen, nur einmal vorkommen.
The G
Lt. Commander
Der Algo ist recht einfach: Hab ne Matrix aus Booleans genommen die allen möglichen Übergänge enthält, also 16x16. Also wenn m[1][2] == true ist Übergang von 1 zu 2 erlaubt.
Dann als Startwert die 0 und los gehts:
Finde den ersten möglichen Übergang, setze aktuelle Position darauf und setze den Übergang auf false. Geht der Sprung zur 15 (war also der letzte Mögliche), setze alle Sprünge zur Anfangsposition auf false.
Der letzte Übergang ist dann von der 15 auf die 0 und feddisch.
Dann als Startwert die 0 und los gehts:
Finde den ersten möglichen Übergang, setze aktuelle Position darauf und setze den Übergang auf false. Geht der Sprung zur 15 (war also der letzte Mögliche), setze alle Sprünge zur Anfangsposition auf false.
Der letzte Übergang ist dann von der 15 auf die 0 und feddisch.
Widlarizer
Captain Special
@ The G:
THIS IS IT!!!
Genau das meinte ich. Vielen, viiielen lieben Dank. Sag mal, hast du das mit Matlab gemacht?
Ich habs einfach nicht hingekriegt. Die Dramatik an der Sache war, dass ich einen neuen Logikstil bereits fertig entworfen habe, es aber dann an der Testbench zur Ansteuerung mächtig hakte. Damit kann ich das nun endlich testen!
@Ge0rgy:
Du sagst es. So habe ich es gemeint, war aber anscheinend nicht in der Lage das recht simpel zu beschreiben. Vielleicht hätte ich von Anfang an sagen sollen:
Es gibt so und so viele Zustände und ich suche einen Pfad, bei dem alle Übergänge nur einmal durchlaufen werden.
@Devastators:
Jo, der Hinweis mit der Dezimalzahlen Notation ist gut. Danke.
EDIT:
Ach ja, wohin soll das Bier gehen?
THIS IS IT!!!
Genau das meinte ich. Vielen, viiielen lieben Dank. Sag mal, hast du das mit Matlab gemacht?
Ich habs einfach nicht hingekriegt. Die Dramatik an der Sache war, dass ich einen neuen Logikstil bereits fertig entworfen habe, es aber dann an der Testbench zur Ansteuerung mächtig hakte. Damit kann ich das nun endlich testen!
@Ge0rgy:
Du sagst es. So habe ich es gemeint, war aber anscheinend nicht in der Lage das recht simpel zu beschreiben. Vielleicht hätte ich von Anfang an sagen sollen:
Es gibt so und so viele Zustände und ich suche einen Pfad, bei dem alle Übergänge nur einmal durchlaufen werden.
@Devastators:
Jo, der Hinweis mit der Dezimalzahlen Notation ist gut. Danke.
EDIT:
Ach ja, wohin soll das Bier gehen?
Zuletzt bearbeitet:
The G
Lt. Commander
Hast Post, das Bier schenk ich dir 
Hallo!
Ich stehe bei meiner Diplomarbeit genau vor dem selben Problem wie Widlarizer. Ich muss meine Gatter mit 3 und vier Eingängen testen und brauche alle Zustandsübergänge (keine doppelt) für die programmierbaren Pulsquellen am Eingang. Ein Quelltext (vorzugsweise für MATLAB) wäre toll. Ich habe leider die Methode von The G nicht ganz verstanden, dass ich es mal eben nachprogrammieren könnte. Vielleicht lesen The G und oder Widlarizer ja noch hier mit und können mir was zuschicken.
Das wäre echt nett.
lg ZatraZ
Ich stehe bei meiner Diplomarbeit genau vor dem selben Problem wie Widlarizer. Ich muss meine Gatter mit 3 und vier Eingängen testen und brauche alle Zustandsübergänge (keine doppelt) für die programmierbaren Pulsquellen am Eingang. Ein Quelltext (vorzugsweise für MATLAB) wäre toll. Ich habe leider die Methode von The G nicht ganz verstanden, dass ich es mal eben nachprogrammieren könnte. Vielleicht lesen The G und oder Widlarizer ja noch hier mit und können mir was zuschicken.
Das wäre echt nett.
lg ZatraZ
Devastators
Grand Admiral Special
besteht der Sinn und Zweck einer Diplomarbeit eigentlich darin, sein gelerntes Wissen und Arbeitsweise mal in der Praxis umzusetzen, oder einfach nur einen Idioten zu finden der einen die Aufgaben löst?
Aufwachen, spätestens im Berufsleben fällt es sehr oft auf, dass man in der Schule nur abbgeschrieben hat...
Aufwachen, spätestens im Berufsleben fällt es sehr oft auf, dass man in der Schule nur abbgeschrieben hat...
JKuehl
Grand Admiral Special
Auch in einer Diplomarbeit braucht man ab und an mal einen Stupser in die richtige Richtung. Idealerweise hat man dafür aber einen Betreuer an der Uni der sich damit auskennt.
Vielleicht sollte zatraz aber mal kurz was über die verwendeten Gatter erklären. Handelt es sich um FlipFlops, um einfache Gatter wie AND/OR oder worum genau?
Dann würde ich das Problem einfach mit einem endlichen Automaten angehen.
Vielleicht sollte zatraz aber mal kurz was über die verwendeten Gatter erklären. Handelt es sich um FlipFlops, um einfache Gatter wie AND/OR oder worum genau?
Dann würde ich das Problem einfach mit einem endlichen Automaten angehen.
Devastators
Grand Admiral Special
den Stupser hat er schon gefunden, er will ja den fertigen Code in MTLAB...
k.A. ob das im Sinne des Erfinders ist.
Denkhilfen finde ich ja ok, fertige Programmteile nicht.
k.A. ob das im Sinne des Erfinders ist.
Denkhilfen finde ich ja ok, fertige Programmteile nicht.
Hi,
schon lustig das dem TO damals nicht vorgeworfen wurde er suche einen "Idioten".
Bei meiner Diplomarbeit habe ich ganz andere Schwerpunkte (Schaltungsentwurf und Optimierung), hier geht es nur um die Eingangssequenz für die Testbench. Bei den Gattern handelt es sich um Logikgatter (AND/OR, etc.) mit bis zu vier Eingängen. Mein Betreuer meinte das Problem müssten schon andere gehabt haben und ich könnte mich ja im Internet umschauen, ob jemand eine generelle Lösung hat (für n-Bit Eingänge am Gatter). Ausser diesem Thread hier habe ich aber nichts gefunden.
Wem es zu verwerflich ist muss mir ja nicht helfen, mein Betreuer und ich haben jedenfalls keine Probleme damit. Für solche Zwecke gibts ja auch Quellenangaben.
Es ist sicher nicht Sinn und Zweck einer DA das Rad neu zu erfinden.
lg ZatraZ
schon lustig das dem TO damals nicht vorgeworfen wurde er suche einen "Idioten".
Bei meiner Diplomarbeit habe ich ganz andere Schwerpunkte (Schaltungsentwurf und Optimierung), hier geht es nur um die Eingangssequenz für die Testbench. Bei den Gattern handelt es sich um Logikgatter (AND/OR, etc.) mit bis zu vier Eingängen. Mein Betreuer meinte das Problem müssten schon andere gehabt haben und ich könnte mich ja im Internet umschauen, ob jemand eine generelle Lösung hat (für n-Bit Eingänge am Gatter). Ausser diesem Thread hier habe ich aber nichts gefunden.
Wem es zu verwerflich ist muss mir ja nicht helfen, mein Betreuer und ich haben jedenfalls keine Probleme damit. Für solche Zwecke gibts ja auch Quellenangaben.
Es ist sicher nicht Sinn und Zweck einer DA das Rad neu zu erfinden.
lg ZatraZ
JKuehl
Grand Admiral Special
zatraz: ich uebersetze das einfach mal und vielleicht hilft es dir ja.
Matrix aus Booleans:
0 1 2 3 4
0
1
2
3
4
moegliche Uebergaenge: fuellst einfach ueberall ein TRUE (oder eine 1) ein (dazu musst du nur wissen wie du eine Matrix in z.B. Matlab anlegst) wenn z.b. ein Uebergang von 0 nach 1, und einer von 1 nach 4 und einer von 4 nach 0 moeglich sein soll. Sonst alles Nullen.
0 1 2 3 4
0 1 0 0 0
1 0 0 0 1
2 0 0 0 0
3 0 0 0 0
4 1 0 0 0
Erster moeglicher Uebergang waere dann von 0-->1. Aktuelle Position 1. Uebergang von 0 auf 1 false setzen (damit der nicht wieder benutzt wird, kein Zyklus auftritt)
also:
0 1 2 3 4
0 0 0 0 0
1 0 0 0 4
2 0 0 0 0
3 0 0 0 0
4 1 0 0 0
geht der Sprung zur 4, bist du im letzten Zustand angelangt. Lezter Zustand also von 4 auf 0, der PFad ist fertigf man hat alles durchlaufen und ist wieder bei 0 angelangt.
Wichtig:
ob man nun den letzten Uebergang (im Original von 15-->0, hier 4-->0) in der Matrix setzen muss oder nicht setzen darf musst du mal testen.
