Я давно хотел реализовать клеточный автомат «в железе» — то есть без программ, процессоров, микроконтроллеров, — на жёсткой логике. Например, широко известную игру «Жизнь». Однако каждый раз, когда я пытался представить себе реализацию, получалось нечто ужасное: сотни и сотни логических элементов ради того, чтобы собрать крошечное поле, на которое не влезет ничего, кроме одного глайдера. Поэтому я решил начать с чего-то более простого, — например, взять не двумерный клеточный автомат, а одномерный. Скажем, «Правило 110». В этой серии статей я расскажу, как мне удалось решить эту задачу.
Часть 1 — Изобретаем велосипед (Вы здесь)
Часть 2 — «Заработало!» (ссылка появится позже)
Часть 3 — Щупаем «Правило 110» (ссылка появится позже)
Клеточный автомат — это математическая конструкция, представляющая собой поле в клеточку, где каждая клетка может находиться в одном из нескольких состояний. Клеточный автомат развивается во времени, и делает это дискретно — по шагам. На каждом шаге все клетки одновременно определяют своё новое состояние по заранее заданным правилам, основываясь на собственном текущем состоянии и состоянии своих соседей. Обычно правила одинаковы для всех клеток.
Совсем простые правила могут порождать удивительно сложное поведение клеточного автомата в целом. В частности, игра «Жизнь» [1] — наиболее известный клеточный автомат — является полным по Тьюрингу: на достаточно большом (в пределе бесконечном) поле из специально организованных клеточных структур можно реализовать выполнение любого алгоритма. Есть, например, проекты калькуляторов, машины Тьюринга и даже реализация «Жизни» в «Жизни».
Этот автомат — двумерный (оперирует двумерным полем), но другие клеточные автоматы могут иметь другую размерность. Особый интерес представляют одномерные автоматы, как простейший нетривиальный вариант. Они представляют собой «ленту» из клеток. Бесконечный одномерный клеточный автомат с двумя состояниями клеток, где следующее состояние клетки зависит от неё самой и двух её соседей, называется элементарным клеточным автоматом. Всего таких автоматов, различающихся правилами перехода, существует 256, и они названы числами от 0 до 255 в соответствии с т.н. кодом Вольфрама. Клеточный автомат, которому присвоен номер 110 («Правило 110» [2]), как и «Жизнь», проявляет весьма сложное поведение, а в 2004 году было доказано, что он тоже является полным по Тьюрингу.
Для иллюстрации развития одномерного клеточного автомата сложилась удобная практика: каждое следующее состояние автомата рисуют под предыдущим, получая двумерное поле размером w×h, где w — это размер (количество ячеек) самого автомата, а h — количество визуализированных поколений. Получается диаграмма «пространство-время». На обложке изображено таким способом развитие одной чёрной клетки в «Правиле 110».
Сначала сформулируем задачу точнее.
«Правило 110» относится к элементарным клеточным автоматам, которые, по определению, имеют поле, бесконечное в обе стороны. Я поставил перед собой задачу реализовать его конечный аналог с размером поля, достаточным, чтобы пронаблюдать хотя бы несколько характерных структур. Скажем, не менее 30 клеток.
Не будем отходить от традиций и визуализируем развитие в привычной форме — в виде диаграммы «пространство-время». Количество поколений (строк в диаграмме) тоже возьмём не менее 30.
В качестве основной элементной базы возьмём старые добрые микросхемы 4000-й серии.
Поехали!
Правила перехода
Начнём с простого. Обязательно нужна будет логическая схема, реализующая правила перехода для одной клетки — собственно, само правило 110. В сущности, надо построить схему с тремя входами и одним выходом по таблице истинности. Обозначим саму клетку b, её левого соседа — a, правого соседа — c.
Такие задачи учат решать на первом курсе профильных вузов, так что в детали вдаваться не буду. Перебрав несколько эквивалентных вариантов, я остановился на том, который показался мне наиболее удачным и экономным: (a И b И c) ИЛИ-НЕ (b ИЛИ-НЕ c). Итого, логика перехода требует 3 логических элемента: один 3И и две штуки 2ИЛИ-НЕ. Для простоты будем называть эту схему «схемой 110».
Как же на основе такой логической ячейки собрать целый клеточный автомат?
Архитектура
Наивное решение выглядит так: Предположим, мы хотим симулировать элементарный клеточный автомат размером w=30 клеток в течение h=30 поколений. Тогда нам понадобится матрица из 900 ячеек, каждая из которых будет подсоединена к трём соседям сверху и по сигналам с них будет вычислять своё состояние. А для индикации на каждой из них можно поместить по светодиоду. Точнее говоря, так будут выглядеть 870 ячеек, а в верхнем ряду вместо них надо поместить какие-нибудь тумблеры, чтобы задавать начальное состояние. В этом примере потребуется 870 «схем 110», то есть 870 элементов 3И и 1740 элементов 2ИЛИ-НЕ. Это 725 корпусов микросхем стандартной логики 4000-й серии. Солидно, да? Как вы уже догадались, никакого желания идти таким путём у меня не возникло.
Я разработал совершенно другую систему. Покажу мои рассуждения, алгоритм, который я придумал, и как он конвертируется в аппаратную реализацию.
Забудем на минуту, что нам надо как-то визуализировать развитие клеточного автомата, сосредоточимся только на самой симуляции. Почему наивное решение требует так много логических элементов? Потому что оно полностью параллельное. Куда экономнее будет вычислять клетки последовательно, одну за другой, точно так же, как человек может вручную симулировать развитие клеточного автомата ручкой на бумаге — клетка за клеткой, поколение за поколением. Слева направо, сверху вниз. Сразу ясно, что хранить все поколения нет необходимости: для вычисления текущего поколения достаточно знать предыдущее. Чтобы вычислить клетку n в текущем поколении, нужно знать лишь три клетки предыдущего поколения: n−1, n, n+1. А раз мы вычисляем клетки одну за другой подряд, можно сказать, что это клетки, которые были вычислены w+1, w, w−1 шагов назад, соответственно. Те клетки, что были вычислены w+2, w+3 и т.д. шагов назад, уже никогда нам не понадобятся, их можно выкидывать. Те, что были вычислены w−2, w−3 и т.д. шагов назад, напротив, ещё понадобятся для вычисления следующих клеток. Получается, достаточно хранить скользящее окно из w+1 клеток, и вычислять новые значения по трём наиболее старым из них.
Этот алгоритм удивительно хорошо подходит для аппаратной реализации. С ролью скользящего окна отлично справится сдвиговый регистр длины w+1. Схему, которая по трём старым значениям вычисляет одно новое, мы уже подготовили. Соединяем одно с другим, и готово! Поколения клеточного автомата будут пробегать по регистру одно за другим. Всё, что потребуется — три логических элемента и один сдвиговый регистр. Конечно, придётся добавить ещё какие-то вспомогательные схемы, но есть все шансы, что реализация поля шириной 30 клеток уложится в 5–10 корпусов микросхем — ведь сдвиговые регистры выпускаются готовые. По сравнению с наивной реализацией, где выходило 725 корпусов, экономия фантастическая. Если считать не корпуса, а отдельные логические элементы, разница тоже выйдет существенная — попробуйте посчитать сами!
Разумеется, заменив «схему 110» на какую-то другую, можно реализовать и другие одномерные клеточные автоматы. Более того, на основе этого же принципа можно построить и двумерный клеточный автомат, хотя для него экономия элементов будет уже не столь колоссальной, поскольку в регистре придётся хранить целый кадр.
Как я узнал позже, подобный принцип использовали для реализации клеточных автоматов в 1950–1980-е [3, 4], а в цифровой обработке сигналов (DSP) обобщение того же подхода называется фолдингом (folding) [5]. Так что я, в сущности, изобрёл велосипед, однако додуматься самому было приятно, и результат порадовал.
Визуализация
Тут самое время вспомнить о том, что развитие надо как-то визуализировать; стоило бы приготовиться к ложке дёгтя в виде невероятно сложного вывода, которым придётся платить за столь упростившуюся реализацию автомата. Действительно, много ли радости с того, что строки будут пробегать по регистру одна за другой и пропадать? Хотя… Бегущие одна за другой строки — вам ничего это не напоминает? Телевизионная развёртка! У нас получился идеальный формат данных для вывода на электронно-лучевую трубку (ЭЛТ). Телевизор — это, пожалуй, перебор, а вот организовать подходящую развёртку на экране аналогового осциллографа будет несложно. Ложка дёгтя отменяется. Наоборот, проект приобретает элементы любимого многими oscilloscope art. Именно это замечательное совпадение и убедило меня, что идея достойна реализации.
Почему развёртка телевизионного типа так хорошо подошла?Причина вполне фундаментальна. Изначальная проблема с визуализацией связана с тем, что сдвиговый регистр преобразует параллельное в последовательное: клетки, которые в клеточном автомате находятся рядом друг с другом, он выдаёт по очереди одну за другой. А телевизионная развёртка производит как раз противоположную операцию: она преобразует последовательность сигналов в изображение, все части которого видны одновременно. По счастливому совпадению, и вычисление, и развёртка работают построчно слева направо, сверху вниз, так что не требуется вообще никаких преобразований.
Не хватает одной детали. Если мы хотим получить статичное изображение развития клеточного автомата на экране осциллографа, один и тот же кадр потребуется выводить несколько десятков раз в секунду. От хранения полного кадра мы отказались, значит каждый раз придётся прогонять развитие автомата заново. То есть надо хранить начальное состояние. Что ж, заведём для этого ещё один регистр размера w и будем переписывать его содержимое в рабочий сдвиговый регистр перед началом каждого кадра. Тогда в каждом кадре всё развитие будет прогоняться — и выводиться — заново. А предварительно записать начальное состояние в этот регистр памяти можно последовательно, подавая на вход то низкий, то высокий логический уровень и тактируя его вручную.
Недостатки
Пока что всё выглядит очень радужно, но небольшой недостаток у такой системы всё же есть. Это — граничные условия. У клеточных автоматов конечного размера поле имеет края, и клетки на краю поля имеют другое количество соседей, чем остальные, а потому ведут себя иначе. Чаще всего этого избегают, замыкая поле в кольцо — то есть считая, что самая левая клетка граничит с самой правой. Реже просто считают, что за границами поля — «нули» или «единицы». Иногда за границу помещают виртуальное зеркальное отражение соседних клеток. Подходящий вариант обычно выбирают в зависимости от конкретного клеточного автомата и его характерных структур. Моя же система сама диктует граничные условия, и довольно-таки дикие. В литературе такие условия называют спиральными (helical, spiral)[3, 6]: левая клетка каждого поколения соседствует с правой клеткой предыдущего поколения. Лучшим объяснением будет простая иллюстрация.
Забегая вперёд, для «Правила 110» граничные условия в целом очень важны, но, к счастью, в данном проекте это не помешало добиться результата. Подробнее об этом будет рассказано в третьей части этого цикла статей. При необходимости можно дополнить схему таким образом, чтобы искусственно задать любые другие граничные условия.
Также бросается в глаза взаимосвязь между размером поля и быстродействием схемы, неизбежная для любых последовательных решений. При этом скорость вычисления состояний ограничена сверху характеристиками элементной базы, а инерция зрения и длительность послесвечения осциллографа накладывают ограничения на частоту кадров снизу. Насколько это серьёзный недостаток? Давайте прикинем, какого наибольшего размера поле можно сделать с учётом этих ограничений. Микросхемы 4000-й серии имеют разные предельные частоты тактирования, от 3 до 16 МГц при 10 В питания, — возьмём наихудший случай, 3 МГц. Минимальная частота кадров, на которой не бросается в глаза мерцание, — около 50 кадров в секунду. Положим, около 15% времени уйдёт на обратный ход луча и т.п. Тогда в течение секунды можно будет отрисовать 2,55 миллиона точек. Это 51000 точек на кадр. Этого хватит на поле 225×225 клеток. Напомню, изначально речь шла про поле 30×30 клеток — то есть в 7,5 раза меньше по линейным размерам и в 56 раз меньше по площади. Так что для небольшого демо-проекта это вообще не ограничение.
Что дальше?
Собрав в голове полную картину, я занялся реализацией — подбором компонентов, разработкой схемы, экспериментами и сборкой конструкции. А что из этого получилось — я расскажу (и покажу) в следующей части, которая выйдет через неделю.
Источники
[1] Игра «Жизнь» в «Википедии»: en, ru.
[2] Правило 110 в «Википедии»: en, ru.
[3] Wolfram S. A New Kind of Science. Champaign, IL: Wolfram Media, 2002 (онлайн-версия). Примечания: «Special-purpose hardware for cellular automata», с. 868; «History of cellular automata», с. 878; «Nonlinear feedback shift registers», с. 1088.
[4] Toffoli T. CAM: A high-performance cellular-automaton machine // Physica D: Nonlinear Phenomena. 1984. Vol. 10, № 1–2. P. 195–204. DOI: 10.1016/0167-2789(84)90261-6.
[5] Folding (DSP implementation) в «Википедии»: en.
[6] Helical boundary conditions в «Википедии»: en.
При подготовке статьи использовался ИИ-ассистент (Claude) для вычитки и поиска ошибок в тексте. Вся содержательная работа проделана мной самостоятельно.
Комментарии 0