PLAs

Alexander Schmidt wrote: : Sorry, noch eine Frage:

: "In der Praxis beschränkt man sich daher oft darauf als Schaltkreise nur : PLAs zuzulassen. Dies sind billige, universelle Standardschaltkreise, die : sich für individuelle Zwecke programmieren lassen. Sie sind zwar : kostengünmstig in der Massenproduktion, es gibt jedoch boolesche Funktionen : mit Schaltkreisen linearer Größe, für die alle PLAs exponentielle Größe : haben. Dazu gehört u.a. die Paritätsfunktion, die testet, ob die Anzahl der : 1en im Inputvektor ungerade ist."

: 1. Warum exponentiell ? Beispiel:

Was ist den da exponentiell, wenn ich für 2^n Bits 2^n-1 Gatter brauche? Das ist doch sowas von linear.

Gruß Willi

:>>: 1. Warum exponentiell ? :>Beispiel: :>8Bit Parity mit EXOR: :>4+2+1 Gatter entspricht 2^3-1 :>16Bit: :>8+4+2+1 entspr. 2^4-1

: Was ist den da exponentiell, wenn ich für 2^n Bits 2^n-1 Gatter : brauche? Das ist doch sowas von linear. Auch wieder wahr. Aber mir fällt ein, daß PLAs ja keine XORs, sondern nur Und-Terme haben. Damit wird es von der Ordnung 2^n/2, da ja _alle_ Kombinationen mit geraden Einsen verküpft werden müssen.