Клеточный автомат на микросхемах малой интеграции. Часть 1 — Изобретая велосипед

Мне давно хотелось построить клеточный автомат непосредственно «в железе»: без программ, процессоров и микроконтроллеров, используя только жёсткую логику. Например, реализовать знаменитую игру «Жизнь». Но стоило задуматься о подробностях, как возникала пугающая картина: сотни логических элементов ради крохотного поля, на котором едва поместится один глайдер. Поэтому я решил начать с более простой задачи и вместо двумерного автомата взять одномерный — скажем, «Правило 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И и два 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-й серии при напряжении питания 10 В составляет от 3 до 16 МГц в зависимости от микросхемы. Возьмём худший случай — 3 МГц. Минимальная частота, при которой мерцание не бросается в глаза, составляет около 50 кадров в секунду. Предположим, что примерно 15% времени занимает обратный ход луча и другие служебные операции. Тогда за секунду можно отрисовать 2,55 миллиона точек, или 51 000 точек на кадр. Этого достаточно для поля размером 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 для вычитки текста и поиска ошибок. Вся содержательная работа выполнена мной самостоятельно.

 

Источник