SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Учебный процесс
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Моделирование дискретных и непрерывных автоматов средствами электронных таблиц


© Кузнецов Б.П., д.т.н. (МУФО, Санкт-Петербург) 2005

Исходный текст программы к статье (~6 кб)

Проявляя дальнейший интерес к возможным вариантам использования ранее предложенных мной экспоненциальных автоматов решил проверить функционирование модели нового аналогового устройства на базе Э-триггеров. Бумажно-формульные старания быстро надоели ввиду необычайной громоздкости вычислений из-за обилия обратных связей. С калькулятором WINDOWS мороки еще больше, знакомый мне MathLab не установлен, программирующей среды С++ и в помине нет на компьютере, с VB принципиально не хотелось связываться, и, единственное, что можно было из вычислительных средств достопочтимого офисного компьютера попробовать, оставалась электронная таблица имени Большого Билла в версии 2003.

Однако, с детства ПК мне запомнилось, что программы электронных таблиц осуществляют мгновенные расчеты всех ячеек таблицы в пределах доступной (геометрически на поле таблицы) области определения переменных, но памятью (запоминанием результатов для последующих циклов вычислений) такие программы не обладают. То есть, вроде бы с моделированием работы конечных и, тем более непрерывных, автоматов в EXELе делать нечего. Хотя, если одну и ту же формулу в столбце ячеек повторять, модифицируя соответствующие ссылки на номер строки, можно получать таблицы произвольных функциональных зависимостей (разрешенных Microsoft) c использованием механизма автоматической модификации ссылок в пределах выделяемого диапазона строк (таблицу считаем сверху вниз). Памятуя также о необходимости обязательного насильственного задания начального состояния автомата, удалось изобрести велосипед следующей конструкции: в столбце переменной состояния первая сверху клетка, ответственная за хранение значения начального состояния, не должна входить в диапазон, выделяемый для модифицируемой формулы вычисления состояния.

После этого «открытия» за несколько минут была освоена соответствующая техника, еще полчаса ушло на перевод бумажных формул в машинные с выделением диапазонов, десяток секунд на задание значения начального состояния и скачка входной переменной – и готова таблица функционирования для некоторого частного случая жизни Э-автомата вида:

Щелкнув по значку ДИАГРАММЫ и выполнив бездумные действия, быстро получил график, чудно иллюстрирующий знакомую работу аналогового Э-триггера. Так как все сохранилось в пределах видимого на дисплее, то с удовольствием привожу графический отчет о доставившей удовольствие работе:

Полная версия рисунка

Теперь можно моделировать любую совокупность аналоговых триггеров и играть с ними сколько захочется.

Желающие ознакомиться с формульным содержимым ячеек диапазона А4 : F5 могут обратиться по следующей ссылке.

В дополнение к собственным интересам, а также ради спортивного интереса, я решил преобразовать эксельный Э-триггер в дискретный RS-триггер (идеальный генерирующий вариант, представленный в работах В.С. Любченко), принципиально игнорируя особенности его функционирования в среде якобы параллельных вычислений электронной таблицы (по поведению предложенной модели триггера желающие могут составить отчетливое представление о последовательности вычислений электронной таблицы).

В этой статье автор хотел представить полностью некоторый канонический подход к моделированию конечных автоматов, но, с учетом пиксельного веса двух представленных здесь картинок, пришлось ограничиться только триггером, моделирующем не два И-НЕ с перекрестными связями, а изначальную диаграмму переходов соответствующего автомата Мура. При этом, все-таки, предлагается один из элементов каноники, которая будет полностью изложена в следующей статье.

Итак, имеем для начала следующее, именуемое открытой для раскрашивания частично-проектной документацией на конечный автомат:

Так как EXELем сейчас владеют и бабушки-секретарши и внучки-школьницы, то уж С++ программеру наверняка под силу заполнить десяток-второй клеточек не сильно сложными математическими примитивами. Но следует помнить, что как и всякий Билл-продукт, EXEL не составляет исключение. В частности, мой вариант 2003 обладает чисто логической ошибкой, не позволившей реализовать упомянутый в начале статьи велосипед при использовании логических функций И, ИЛИ, НЕ. Поэтому пришлось применить смесь арифметики и EXEL-функции ЕСЛИ. Сразу предупреждаю, что возможности для моделирования автоматов электронной таблицей (как и кодирования в программе) – не перечислимы, поэтому к представляемому ниже (и в следующей статье) подходу следует относиться и критически и творчески. По моим представлениям, уже рисунок автомата RS-триггера, хотя и подкрашенный, должен вызывать разное толкование. Это подтверждает и результат моделирования, показанный ниже и доказывающий некоторую несостоятельность пометки дуг на рисунке. Автор предоставляет возможность читателям самостоятельно исправить ситуацию и высказаться на форуме или в форме статьи.

На этом снимке электронной таблицы показан (полученный неформально) тест автоматной модели RS-триггера и идентичная ему временная диаграмма (которую в аппаратной реализации триггера смотрят на приборе, называемом осциллографом). Поскольку не ставилась задача обертки данного отнюдь не полуфабриката в красивую упаковку, то претензии по оформлению не принимаются – это дело либо вкуса, либо требования пиара. Признаю также, что порядок следования столбцов не совсем соответствует требованиям справа-налево от входов к выходам – почему бы не стать на место леворукого или япана.

Полная версия рисунка

Предлагаемым элементом каноники является выделение отдельных столбцов не только для каждой вершины графа, но и для каждой его дуги, включая петли (входы и выходы – естественно, но в данном конкретном случае выход автомата Мура однозначно соотносится с вершиной графа). Столбцы, обозначенные Pij, являют собой признаки активизации дуги перехода: 1 – дуга активизирует переход (в том числе сохраняет предыдущее состояние, если это петля Pii), 0 – переход, соответствующий дуге не выполняется; первый индекс в обозначении дуги являет вершину предыдущего состояния, откуда исходит дуга, второй индекс указывает направление перехода – вершину нового состояния. Состояниям (вершинам графа) соответствуют столбцы Т0 и Т1, где ИСТИНА обозначает пребывание автомата в данном состоянии, а ЛОЖЬ – пребывание автомата в состоянии, не соотнесенном с данным столбцом.

Начальное состояние автомата представлено вектором 10 в строке 4 (в клетках А и В). Этот вектор можно заменить на дополняющий его вектор 01, или совсем не по правилам – векторами 00 и 11 – выбор исследователя. (надо было использовать ИСТИНА и ЛОЖЬ, но в спешке опустил этот момент и не стал повторять операцию вырезания из копии экрана и вставки рисунка в этот документ)

Рабочим диапазоном служат строки с 5-й по 33-ю. Независимыми величинами, значения которых проставляются произвольным образом, являются входные переменные R и S в столбцах G и Н. Никакие формулы для них не требуются. Активность дуг задается формулами в клетках С D E F со следующим содержанием:

где:

  • фигурные скобки и двоеточия между инденксами ячеек обозначают модификацию формулы в пределах задаваемых через двоеточие диапазонов в столбцах (особенность EXEL),
  • знак * арифметического умножения реализует операцию И,
  • вычитание из единицы реализует логическую инверсию – операцию НЕ.

Пребывание автомата в состояниях Т0 и Т1 задается формулами в клетках А и В пятой строки:

где результатом операции ИЛИ служит логический признак ненулевой положительной арифметической суммы логических переменных.

Диаграмма как штатный компонент EXEL выбирается и настраивается на усмотрение исследователя – я сделал выбор особенно не задумываясь и без каких-либо настроек.

Ощущение при моделировании достаточно острое – изменив ноль на единицу или наоборот в клетке столбцов входов, мгновенно получаешь пересчитанную таблицу и изменения в графике.

Проверьте – не пожалеете.

воскресенье, 17 апреля 2005 г. 16:42:38