Schaltung, die die Anzahl der gesetzten Bits in 15-Bit-Eingang zählt

Question

Wie eine flächeneffiziente Schaltung aufzubauen, die die Anzahl der gesetzten Bits zählen in 15-Bit-Eingang mit 4-Eingangs-LUTs (Look-up-Tabellen). Der Ausgang ist offensichtlich 4-Bit (counts 0-15). Einige behaupten, dass es möglich ist 9 LUTs zu tun verwenden.

Answer 1

Ich kann es tun in 10. Es ist eine erste Zählerstufe (4 Tabellen), dann eine 2-Stufen-Addierer mit Übertrag (3 und 3 Tabellen).

Ich vermute, dass es eine Möglichkeit, es besser zu machen ist, weil ich nicht jede LUT vollständig genutzt haben, aber manchmal ein einfaches Design ist die Extrakosten wert. Ich habe versucht, andere Ansätze und brauchte noch 10.

Viel Glück auf Ihre Hausaufgaben. (:

Answer 2

Nun, ich werde Ihnen den Start. Ihre erste Schicht von Lookup-Tabellen wird wie folgt aussehen:

0 0 0 0 = 00
0 0 0 1 = 01
0 0 1 0 = 01
0 0 1 1 = 10
0 1 0 0 = 01
0 1 0 1 = 10
0 1 1 0 = 10
0 1 1 1 = 11
1 0 0 0 = 01
1 0 0 1 = 10
1 0 1 0 = 10
1 0 1 1 = 11
1 1 0 0 = 10
1 1 0 1 = 11
1 1 1 0 = 11
1 1 1 1 = 00

Verbreiten Sie vier von ihnen über Ihre fünfzehn-Bit-Eingang, die Ausgänge nehmen und sie durch zwei neue Lookup-Tabellen übergeben, die wie folgt aussehen:

0 0 0 0 = 000
0 0 0 1 = 001
0 0 1 0 = 010
0 0 1 1 = 011
0 1 0 0 = 001
0 1 0 1 = 010
0 1 1 0 = 011
0 1 1 1 = 100
1 0 0 0 = 010
1 0 0 1 = 011
1 0 1 0 = 100
1 0 1 1 = 101
1 1 0 0 = 011
1 1 0 1 = 100
1 1 1 0 = 101
1 1 1 1 = 110

... und so weiter. Natürlich wirst du das Problem aller Nullen und nur Einsen produzieren die gleiche Leistung in der ersten Schicht haben, zu lösen.

Und ich kann völlig falsch sein.

Answer 3

Hier einige C-Code, der die Anzahl der Bits zählt: C-Code zählen die Anzahl der '1'-Bits. Sie finden diese in der Hardware konvertieren.