Схема, которая подсчитывает количество установленных бит на 15-битном входе

Question

Как построить эффективную по площади схему, которая подсчитывает количество установленных бит на 15-битном входе, используя 4-входные LUT (справочные таблицы). Выход очевидно 4-битный (считается 0-15). Некоторые утверждают, что это можно сделать, используя 9 LUT.

Answer 1

Ну, я начну. Ваш первый слой таблиц поиска будет выглядеть следующим образом:

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

Распределите четыре из них по своему 15-битному входу, возьмите выходные данные и пропустите их через две новые таблицы поиска, которые выглядят так:

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

... и так далее. Конечно, вам придется решить проблему всех нулей и всех одинаковых выходных данных в первом слое.

И я могу быть совершенно неправ.

Answer 2

Я могу сделать это за 10. Это первый каскадный этап (4 таблицы), затем двухступенчатый сумматор с переносом (3 и 3 таблицы).

Я подозреваю, что есть способ добиться большего успеха, потому что я не использовал каждый LUT полностью, но иногда простой дизайн стоит дополнительных затрат. Я пробовал другие подходы и все еще нуждался в 10.

Удачи на домашней работе. (

Answer 3

Вот некоторый C-код, который считает количество битов: C-код для подсчета количества битов «1» . Вам придется конвертировать это в ваше оборудование.