Umkehrung von Logikfunktionen (z.B.: XOR)

#1
Hallo Community!

Weiß nicht ob das der richtige Threadtitel für das Thema ist. Ich erkläre deswegen kurz mal was ich will.
Und zwar hab ich das Ergebnis einer XOR Verknüpfung. Jetzt will ich aber alle möglichen Werte
der Eingangsvariablen wissen, die sie annehmen können:

Als Beispiel:

0b10011100 ist der Endwert der XOR Verknüpfung.

Die Bitpositionen die Null sind, sind ja einfach...
Eingang A: 0b?11???11
Eingang B: 0b?11???11

Allerdings will ich alle ubekannten Zustände (?) wissen die mir der Endwert der XOR Verknüpfung liefert.

Hier vielleicht ein einfacherer Endwert:

0b00000001 -> Endwert XOR

Eingang A: 0b11111111
Eingang B: 0b11111110

oder

Eingang A: 0b11111110
Eingang B: 0b11111111

Diese beiden Werte sollte ich in diesem Beispiel herausbekommen.
Ich hoffe, ich konnte das so einigermaßen erklären worauf ich hinaus will.

Toll wäre es, wenn es hierzu schon einen fertigen Algorithmus geben würde.
Gut, die einfachste Möglichkeit wäre Bruteforce, aber es muss doch irgendwie eine elegantere Lösung vorhanden sein.

Vorweg vielen Dank!
 

CDW

Moderator
Mitarbeiter
#2
Die Bitpositionen die Null sind, sind ja einfach...
Eingang A: 0b?11???11
Eingang B: 0b?11???11
...

Gut, die einfachste Möglichkeit wäre Bruteforce, aber es muss doch irgendwie eine elegantere Lösung vorhanden sein.
Nope.

0 == 1 xor 1
0 == 0 xor 0

dazu:
1 == 1 xor 0
1 == 0 xor 1
Die Bitstellen im Ergebiss sind absolut unabhängig voneinaner und pro Bit haben wir also immer 2 mögliche "Kandidaten".

Daher würde ich die Anzahl der möglichken Schlüsselpaare auf 2^n mit n = Anzahl der verarbeiteten Bitstellen, schätzen. oder (2^n) / 2, wenn man die Symmetriefälle für die Einabe != 0 berücksichtigt ;)
PoC in Python
Code:
def pairs(x):
...     cands = set()
...     for i in xrange(2**8):
...         cands.add((i, x^i))
...     return cands

>>> sorted(pairs(0b10011100))
[(0, 156), (1, 157), (2, 158), (3, 159), (4, 152), (5, 153), (6, 154), (7, 155), (8, 148)
, (9, 149), (10, 150), (11, 151), (12, 144), (13, 145), (14, 146), (15, 147), (16, 140),
(17, 141), (18, 142), (19, 143), (20, 136), (21, 137), (22, 138), (23, 139), (24, 132),
...
108), (241, 109), (242, 110), (243, 111), (244, 104), (245, 105), (246, 106), (247, 107)
, (248, 100), (249, 101), (250, 102), (251, 103), (252, 96), (253, 97), (254, 98), (255,
99)]

>>> sorted(pairs(0b1))
[(0, 1), (1, 0), (2, 3), (3, 2), (4, 5), (5, 4), (6, 7), (7, 6), (8, 9), (9, 8), (10, 11)
, (11, 10), (12, 13), (13, 12), (14, 15), (15, 14), (16, 17), (17, 16), (18, 19), (19, 18
...
, 232), (234, 235), (235, 234), (236, 237), (237, 236), (238, 239), (239, 238), (240, 241
), (241, 240), (242, 243), (243, 242), (244, 245), (245, 244), (246, 247), (247, 246), (2
48, 249), (249, 248), (250, 251), (251, 250), (252, 253), (253, 252), (254, 255), (255, 2
54)]

>>> sorted(pairs(0b0))
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9), (10, 10)
, (11, 11), (12, 12), (13, 13), (14, 14),
 
Zuletzt bearbeitet:
#4
Sorry, für die späte Rückmeldung.

Schade.
0 == 1 xor 1
0 == 0 xor 0

dazu:
1 == 1 xor 0
1 == 0 xor 1
Das 0 XOR 0 auch 0 ergibt, hab ich im Threadtext nicht berücksichtigt. Mein Fehler.

Habs mittlerweile in C gleich gelöst.
Aber vielleicht fällt mir eine einfachere bzw. beschleunigte Art in VHDL ein.
Habe eh schon lange nicht mehr ein FPGA Projekt gemacht. Hätte da schon eine Idee. :)
 
Oben