Заранее предупрежу: довольно много картинок.
В данной статье речь пойдёт о реализации игры «Жизнь» на логических элементах в симуляторе «Atanua».
Игра «Жизнь» является, пожалуй, одним из самых узнаваемых клеточных автоматов. Про неё написано не одна статья, в том числе и на Хабрахабре. Когда-то тоже заинтересовался ей, но как-то надолго не хватило.
Позже услышал где-то, что современные компьютеры имеют ограничение в скорости вызванное, в том числе и наличием некоторого канала связи между памятью и вычислительным ядром. В качестве решения предлагалось собрать считающую память. Я уже точно не помню, то ли я сам вспомнил про «Жизнь», то ли она упоминалась в той статье, но я захотел смоделировать её в логической схеме (если быть точным, то в матрице одинаковых схем). Почему именно «Жизнь»? Основными причинами были её распространённость и известность, а также тот факт, что «вселенные» в ней полны по Тьюрингу, что позволяет производить на ней любые вычисления и решать разнообразные задачи. Получается, на основе данного клеточного автомата можно создать компьютер.
В качестве инструмента был выбран симулятор Atanua (официальный сайт), так как довольно лёгкий в освоении и отображает состояние всех линий. В конечном итоге получилось следующее:
Одной удобной особенностью симулятора «Atanua» является то, что можно подключать схемы как, своего рода, микросхемы в другие проекты. Этим я и воспользовался, собрав матрицу для отладки и экспериментов.
Для более подробного рассмотрения левый верхний угол:
Кнопка «r» используется для сброса схемы. Кнопки, подписанные как «0», используются для установки ячейки в живое состояние. Хочу заметить, сброс повторным нажатием пока не реализован. 3 нижних заземления используются как ограничители схемы, чтобы не появлялось разнообразных артефактов. В Atanua провод может иметь 4 состояния:
При этом, если на вход логического элемента подано неопределённое состояние, то некоторые могут распознать его как 0, а некоторые как 1. Для этого и были поставлены ограничители в виде установки неиспользуемых выводов в 0.
На верхнее заземление не обращайте внимания. Первоначальный вариант схемы требовал инициализации, для чего этот выход и использовался. В настоящее время – это рудимент (чтобы не переделывать матрицу), и его состояние может быть любым. Ещё один провод, уходящий за край рисунка – это вывод тактового сигнала. Он идёт к набору генераторов, на которых тестировал максимальную скорость.
Теперь поподробнее о схеме ячейки. Из-за проблем с качеством скриншотов, я буду давать рисунки отдельных узлов.
На рисунке выше представлен 2-х разрядный зацикленный сдвиговый регистр на D триггерах, который выступает в роли памяти. С ним связан один не хороший момент, который мне ещё предстоит поправить: во время работы схема как бы мигает, так как в активном состоянии (когда в данный регистр записана информация, то есть в состоянии живой клетки) триггеры обмениваются между собой 0 и 1 и получается, что на выходе F (выход на индикацию состояния, на светодиод например) имеем то 0, то 1 (это заметно на видео в конце статьи). RST – это вход сброса. SET – вход установки ячейки в состояние живой клетки. Как уже упоминалось, сброс отдельной ячейки пока не предусмотрен. Слева сверху подходит тактовый сигнал. О соседних двух проводах далее.
В блоке проверки осуществляется проверка на условие игры. Сверху на рождение, снизу на выживание. Особенность данного блока состоит в том, что его можно подстроить и под другие правила, тем самым организовав аналогичные клеточные автоматы. Слева подходят выходы с сумматоров, снизу – те самые два провода, которые идут к регистру. Они, по сути, подсоединяются в разрез одной из передаточных линий регистра.
Пожалуй, самой большой и противоречивой частью схемы являются параллельно-последовательно подключенные сумматоры. Реализовав его, я решил проблему проверки необходимых условий «в лоб», просуммировав все входы A0-A7 от соседних ячеек и проверив результат на соответствие условиям. В данном случае суммируются сначала входы A0+A1+A2, A5+A6+A7, потом результат второй суммы выводы A3 и A4 и так далее. В конечном итоге получилось в конечном итоге 6 сумматоров и 1 полусумматор. Стоит отметить один из сумматоров можно также заменить на полусумматор, т.к. один из его входов не используется. Зачем я сделал один заземлённый вход (слева снизу тёмно-зелёный уходящий за пределы рисунка) – не помню. Изначально хотел её упростить при помощи ДНФ или КНФ, но решать карту Карно 16x16 желания пока не возникает. Так что не исключаю, того момента, что этот модуль может иметь альтернативный вид.
C – это вход таковой частоты, к схеме сумматоров отношения не имеет, идёт к регистру. Про Init я писал выше – рудимент от прошлого варианта.
Я не считаю игру «Жизнь» достойным клеточным автоматом для реализации считающей памяти, так как «программа» для такого компьютера займёт довольно много места и сложна в реализации. Но всё же схема позволяет по мечтать о микросхеме с реализацией ячеек этой игры. Думаю это было бы довольно интересно, увидеть аппаратную реализацию данного клеточного автомата. Причём я имею ввиду не микроконтроллеры с программой, а исключительно на ячейках из логических элементов.
Что же касается схемы, в ней конечно хватает недоработок, но для экспериментов вполне хватает. Буду ли её дорабатывать? Честно говоря, не знаю, как душа ляжет.
Напоследок несколько видео с работой:
Планер:
Малый корабль:
Уместился и пентадекатлон:
Файлы с проектом на Google Drive.
Резервная копия на Mail cloud.
Некоторое пояснение по содержимому:
live.atanua — ячейка;
LiveFieldM.atanua — матрица;
LiveField.atanua — небольшой элемент матрицы (8x8) из которых создавался LiveFieldM. Края не заземлены.
Для обнаружения сложить в одну папку. Если не поможет, отредактируйте файлы в любом текстовом редакторе (по структуре, обычные XML).
В данной статье речь пойдёт о реализации игры «Жизнь» на логических элементах в симуляторе «Atanua».
Игра «Жизнь» является, пожалуй, одним из самых узнаваемых клеточных автоматов. Про неё написано не одна статья, в том числе и на Хабрахабре. Когда-то тоже заинтересовался ей, но как-то надолго не хватило.
Напомню, что такое «Жизнь»:
Имеется некоторая матрица из клеток, которая зовётся «вселенной» (в идеале бесконечная). На каждой итерации (называемые «днями») любая клетка может быть «живой» или «мёртвой», причём её состояние зависит от предыдущей итерации по следующим правилам:
Окрестностью клетки считаются 8 окружающих её клеток (см. двумерная окрестность Мура порядка 1).
Подробнее о «Жизне» можно узнать в Википедии.
- Клетка оживает, если в её окрестности имеются 3 живые клетки.
- Клетка продолжает жить, если в ёе окрестности живы 2 или 3 клетки.
- В иных случаях клетка умирает.
Окрестностью клетки считаются 8 окружающих её клеток (см. двумерная окрестность Мура порядка 1).
Подробнее о «Жизне» можно узнать в Википедии.
Позже услышал где-то, что современные компьютеры имеют ограничение в скорости вызванное, в том числе и наличием некоторого канала связи между памятью и вычислительным ядром. В качестве решения предлагалось собрать считающую память. Я уже точно не помню, то ли я сам вспомнил про «Жизнь», то ли она упоминалась в той статье, но я захотел смоделировать её в логической схеме (если быть точным, то в матрице одинаковых схем). Почему именно «Жизнь»? Основными причинами были её распространённость и известность, а также тот факт, что «вселенные» в ней полны по Тьюрингу, что позволяет производить на ней любые вычисления и решать разнообразные задачи. Получается, на основе данного клеточного автомата можно создать компьютер.
В качестве инструмента был выбран симулятор Atanua (официальный сайт), так как довольно лёгкий в освоении и отображает состояние всех линий. В конечном итоге получилось следующее:
Схема одной ячейки
Одной удобной особенностью симулятора «Atanua» является то, что можно подключать схемы как, своего рода, микросхемы в другие проекты. Этим я и воспользовался, собрав матрицу для отладки и экспериментов.
Матрица ячеек
Для более подробного рассмотрения левый верхний угол:
Кнопка «r» используется для сброса схемы. Кнопки, подписанные как «0», используются для установки ячейки в живое состояние. Хочу заметить, сброс повторным нажатием пока не реализован. 3 нижних заземления используются как ограничители схемы, чтобы не появлялось разнообразных артефактов. В Atanua провод может иметь 4 состояния:
- тёмно-зелёный: лог. 0;
- светло-зелёный: лог. 1;
- красный: не правильно подключён;
- белый: не подключён (неопределённое состояние).
При этом, если на вход логического элемента подано неопределённое состояние, то некоторые могут распознать его как 0, а некоторые как 1. Для этого и были поставлены ограничители в виде установки неиспользуемых выводов в 0.
На верхнее заземление не обращайте внимания. Первоначальный вариант схемы требовал инициализации, для чего этот выход и использовался. В настоящее время – это рудимент (чтобы не переделывать матрицу), и его состояние может быть любым. Ещё один провод, уходящий за край рисунка – это вывод тактового сигнала. Он идёт к набору генераторов, на которых тестировал максимальную скорость.
Теперь поподробнее о схеме ячейки. Из-за проблем с качеством скриншотов, я буду давать рисунки отдельных узлов.
Регистр
На рисунке выше представлен 2-х разрядный зацикленный сдвиговый регистр на D триггерах, который выступает в роли памяти. С ним связан один не хороший момент, который мне ещё предстоит поправить: во время работы схема как бы мигает, так как в активном состоянии (когда в данный регистр записана информация, то есть в состоянии живой клетки) триггеры обмениваются между собой 0 и 1 и получается, что на выходе F (выход на индикацию состояния, на светодиод например) имеем то 0, то 1 (это заметно на видео в конце статьи). RST – это вход сброса. SET – вход установки ячейки в состояние живой клетки. Как уже упоминалось, сброс отдельной ячейки пока не предусмотрен. Слева сверху подходит тактовый сигнал. О соседних двух проводах далее.
Блок проверки
В блоке проверки осуществляется проверка на условие игры. Сверху на рождение, снизу на выживание. Особенность данного блока состоит в том, что его можно подстроить и под другие правила, тем самым организовав аналогичные клеточные автоматы. Слева подходят выходы с сумматоров, снизу – те самые два провода, которые идут к регистру. Они, по сути, подсоединяются в разрез одной из передаточных линий регистра.
Сумматоры
Пожалуй, самой большой и противоречивой частью схемы являются параллельно-последовательно подключенные сумматоры. Реализовав его, я решил проблему проверки необходимых условий «в лоб», просуммировав все входы A0-A7 от соседних ячеек и проверив результат на соответствие условиям. В данном случае суммируются сначала входы A0+A1+A2, A5+A6+A7, потом результат второй суммы выводы A3 и A4 и так далее. В конечном итоге получилось в конечном итоге 6 сумматоров и 1 полусумматор. Стоит отметить один из сумматоров можно также заменить на полусумматор, т.к. один из его входов не используется. Зачем я сделал один заземлённый вход (слева снизу тёмно-зелёный уходящий за пределы рисунка) – не помню. Изначально хотел её упростить при помощи ДНФ или КНФ, но решать карту Карно 16x16 желания пока не возникает. Так что не исключаю, того момента, что этот модуль может иметь альтернативный вид.
C – это вход таковой частоты, к схеме сумматоров отношения не имеет, идёт к регистру. Про Init я писал выше – рудимент от прошлого варианта.
Итог
Я не считаю игру «Жизнь» достойным клеточным автоматом для реализации считающей памяти, так как «программа» для такого компьютера займёт довольно много места и сложна в реализации. Но всё же схема позволяет по мечтать о микросхеме с реализацией ячеек этой игры. Думаю это было бы довольно интересно, увидеть аппаратную реализацию данного клеточного автомата. Причём я имею ввиду не микроконтроллеры с программой, а исключительно на ячейках из логических элементов.
Что же касается схемы, в ней конечно хватает недоработок, но для экспериментов вполне хватает. Буду ли её дорабатывать? Честно говоря, не знаю, как душа ляжет.
Напоследок несколько видео с работой:
Планер:
Малый корабль:
Уместился и пентадекатлон:
Файлы с проектом на Google Drive.
Резервная копия на Mail cloud.
Некоторое пояснение по содержимому:
live.atanua — ячейка;
LiveFieldM.atanua — матрица;
LiveField.atanua — небольшой элемент матрицы (8x8) из которых создавался LiveFieldM. Края не заземлены.
Для обнаружения сложить в одну папку. Если не поможет, отредактируйте файлы в любом текстовом редакторе (по структуре, обычные XML).