Вы можете найти различные алгоритмы для быстрого подсчета битов . Последние два: Nifty Parallel Count и MIT HAKMEM Count вполне могут быть легко преобразованы в ворота. Смотрите эту страницу для хорошего объяснения того, как это работает.
Вы можете сделать это с помощью оборудования Gates. Используйте четыре 1-битных сумматора, чтобы сложить пары бит вместе. Это дает вам четыре 3-битных числа. Добавьте их попарно, используя два 3-битных сумматора. Это дает вам два 4-битных числа для добавления с помощью одного 4-битного сумматора. Это оставляет вам 5-битное значение, но вы можете игнорировать верхний бит. Затем используйте два 4-битных компаратора для проверки значений 2 и 3.
Для минимального количества деталей, почему бы не сделать это аналоговым?
Создайте делитель напряжения с одним резистором сверху, а ваши 8 входов соединены снизу с помощью 8 резисторов параллельно. Затем просто используйте два компаратора, чтобы определить уровни напряжения, которые будут генерировать 2 или 3 бита. Это всего 6 частей:
Сеть с 8 резисторами будет выдавать напряжение от 0 В (для набора 0 битов) до 5 В (для набора 8 битов). 2 бита произведут 0.5v. 3 бита произведут 1.56v.
- С 0 или 1 битом, выход будет 00.
- С 2 или 3 битами, выход будет 01.
- С 4 или более битами, вывод будет 11.
Добавлено:
Спасибо DavidCary за отличное предложение. После долгих вычислений, я думаю, что я нашел набор резисторов, которые работают, но сначала вы должны тщательно проверить мои расчеты. Здесь я использую компараторы с выходами с открытым стоком, и мне кажется, что мне удалось получить один выход. Низкий означает мертвый в следующем раунде, Высокий - живой в следующем раунде.
Приятно то, что в этой схеме только два компонента больше, чем в другой схеме. Все они резисторы серии E8, поэтому их можно достать. Кроме того, R6 должен был иметь более высокое значение, например 4.7k или что-то в этом роде.
Что минимально? Микроконтроллер просто 1 часть, и может производить результат с минимальной задержкой (<1 ы). ATTiny20 - самый дешевый микроконтроллер на 54 цента с 10 входами / выходами в Digikey.μ
Таблица поиска также состоит из 1 части и работает быстрее, чем микроконтроллер. Забудьте о параллельных EEPROM, они дорогие. Используйте байтовый параллельный Flash . Это 512 кБайт, это в 2000 раз больше, чем нужно, но это самое дешевое решение (1 доллар). И вы можете добавить еще 6 1-битных функций за ту же цену.
Вы также можете использовать CPLD . Запишите функцию в VHDL или Verilog как один длинный оператор SOP (Sum Of Products) и позвольте синтезатору создать логику.
Регистр сдвига в порядке , если вы можете ждать результата; это самое медленное решение.
Наконец, вы можете сделать это с помощью логических элементов , но вы потратите много времени, чтобы свести SOP к минимальной форме, если вы хотите использовать все основные принципы. Ракетный магнит имеет правильную идею использования сумматоров, но его числа не совпадают: 1-битный половинный сумматор выдает 2 бита, а не 3. Таким образом, для сложения выходных данных половинных сумматоров два на два требуется два 2-битных половинных сумматора, что дает два немного результатов. Используйте 3-битный половинный сумматор, чтобы получить 4-битный результат. При использовании 1-битных полных сумматоров вам потребуется только один 2-битный сумматор.
источник
Гибридная параллельно-последовательная схема склонна быть намного более компактной, чем чисто параллельная схема. Например, если вы измените правила так, чтобы поле 3x3 превратило ячейку в центре мертвой, если осталось менее трех живых клеток или более четырех, и включило ее, если ровно три живых клетки (поведение под этими новые правила будут соответствовать оригиналу), можно упростить логику, выполнив двухэтапную последовательность:
Массив
tempVal[x,y]имеет два бита на ячейку; последняя операция суммирует три таких числа, чтобы получить значение 0-9 (хотя все значения, превышающие четыре, являются эквивалентными), которые затем можно использовать для вычисления однобитного состояния реального времени / мертвого состояния для следующего поколения.Кстати, альтернативой выполнению арифметической суммы на втором этапе и проверке значения было бы преобразование tempVal [x, y] в представление в одно касание, а затем явная проверка на наличие одной из девяти комбинаций значений, которые дали бы три клетки, или один из двенадцати, которые дали бы четыре.
источник