Наши любимые дети

Теперь попробуем разобраться с элементарными клеточными автоматами, обладающими одним входом и двумя выходами. Не правда ли, что это напоминает железнодорожную стрелку? Поэтому я их называю "маршрутизаторами". Можно представить себе, что поезд, пришедший на вход такой стрелки может поехать по обному из двух возможных маршрутов - налево или направо. Но клеточный автомат не стрелка и единичка, появившаяся на входе - не поезд.
Сколько же вариантов маршрутизации информации можно создать по такой схеме? Прежде всего надо не зацикливаться на единичке. Будто бы только она одна и есть та самая информация, которая должна куда-то на этой "стрелке" поехать. Возможно несколько вариантов продолжения маршрута после того, как единичка приехала к стрелке. Так как выхода два, то они могут принимать 4 варианта состояний: 00, 01, 10 и 11. То же самое может случиться, если управляющим сигналом будет 0. Если совместить все эти варианты, то получим 16 схем, приведенных в таблице:

Четыре строки таблицы, выделенные желтым цветом, ничего не меняют на выходе элементарного клеточного автомата. Значит они нам не нужны. Остается 12 вариантов элементарных клеточных автоматов релейного типа.

Пример алгоритма 8 варианта приведен ниже:

Глаза (свойства) Глаз Номер клетки 1 2 0 2 1 1 0 0 2 0 0

Клетки (функции) Аргумент Номер клетки 1 2 0 0 1 1 1

Теперь посмотрим каким образом в этой схеме можно задействовать автоматы типа триггеров. Особенностью всех алгоритмов является начальная инициализация клеток элементарного клеточного автомата в 0. Следовательно, начальное состояние всех выходных клеток любого элементарного клеточного автомата всегда 00.
Возможны три варианта различных состояний выходных клеток по приходу управляющего сигнала на вход, отличные от этого значения, это - 01, 10 и 11. Так как такие состояния могут рассматриваться и при управляющей единице и при управляющем нуле, то всего получается 6 триггерных элементарных клеточных автоматов. Управляющий сигнал либо устанавливает одно из этих состояний в выходных клетках, если они имели нулевое состояние, либо сбрасывает их в 00, если состояние отличалось от 00.

Примеры двух вариантов реализации одного и того же триггерного алгоритма с двумя выходными состояниями 00 и 01 и переключающей единицей приведены ниже:

Глаза (свойства) Глаз Номер клетки 1 2 0 1 3 1 0 0 2 0 0

Клетки (функции) Аргумент Номер клетки 1 2 0 3 1 0 2

Глаза (свойства) Глаз Номер клетки 1 2 0 2 2 1 0 0 2 0 0

Клетки (функции) Аргумент Номер клетки 1 2 0 0 2 1 0 3

В результате построения алгоритмов удалось установить, что для схемы "один вход - два выхода" существует 12 релейных и 6 триггерных полезных вариантов элементарных клеточных автоматов. Хотелось бы, что бы читатели предложили еще какие-либо варианты.

О схемах "один вход - три выхода" будет следующая статья.

Читайте также

Последние новости