Гра «Життя» на логічних елементах

Заздалегідь попереджу: досить багато картинок.

У даній статті мова піде про реалізацію гри «Життя» на логічних елементах в симуляторі «Atanua».

Гра «Життя» є, мабуть, одним із найбільш упізнаваних клітинних автоматів. Про неї написано не одна стаття, в тому числі і на Хабрахабре. Колись теж зацікавився їй, але як-то надовго не вистачило.

Нагадаю, що таке «Життя»:Є деяка матриця з клітин, що зветься «всесвіту» (в ідеалі нескінченна). На кожній ітерації (звані «днями») будь-яка клітина може бути «живою» або «мертвою», причому її стан залежить від попередньої ітерації за наступними правилами:

  • Клітка оживає, якщо в її околиці є 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 полусумматор. Варто відзначити один з суматорів можна замінити на полусумматор, оскільки один з його входів не використовується. Навіщо я зробив один заземлений вхід (зліва знизу темно-зелений минає, за межі малюнка) – не пам'ятаю. Спочатку хотів її спростити за допомогою ДНФ або КНФ, але вирішувати карту Карно 8x8 бажання поки що не виникає. Так що не виключаю, того моменту, що цей модуль може мати альтернативний вид.

C – це вхід такої частоти, на схемі суматорів відношення не має, йде до регістру. Про Init я писав вище – рудимент від минулого варіанту.

Підсумок
Я не вважаю гру «Життя» гідним клітинним автоматом для реалізації вважає пам'яті, так як «програма» для такого комп'ютера займе досить багато місця і складна в реалізації. Але все ж схема дозволяє мріяти про мікросхемі з реалізацією осередків цієї гри. Думаю це було б досить цікаво, побачити апаратну реалізацію даного клітинного автомата. Причому я маю на увазі не мікроконтролери з програмою, а виключно на комірках з логічних елементів.

Що ж стосується схеми, в ній звичайно вистачає недоробок, але для експериментів цілком вистачає. Буду її доопрацьовувати? Чесно кажучи, не знаю, як душу ляже.

Наостанок кілька відео з роботою:

Планер:



Малий корабель:



Вмістився і пентадекатлон:



Файли з проектом на Google Drive.

Певне пояснення по вмісту:

live.atanua — комірка;
LiveFieldM.atanua — матриця;
LiveField.atanua — невеликий елемент матриці (8x8), з яких створювався LiveFieldM. Краю не заземлені.

Для виявлення скласти в одну папку. Якщо не допоможе, відредагуйте файли в будь-якому текстовому редакторі (по структурі, звичайні XML).

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.