МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ

Понятие дискретного автомата

В технике термином "автомат" пользуются для обозначения системы механизмов и устройств, в которой процессы получения преобразования, передачи и использования энергии, материалов и информации, необходимые для выполнения ее функций, осуществляют­ся без непосредственного участия человека. К системам такого ти­па относятся: станки-автоматы, фасовочные автоматы, автоматы для съемки и изготовления фотографий, торговые автоматы и многое др.

В кибернетику, однако, вошел и прочно в ней укрепился термин "дискретный автомат" или кратко просто "автомат" для обозначения гораздо более абстрактного понятия, а именно - модели, обладаю­щей следующими особенностями:

а) на входы модели в каждый из дискретных моментов времени поступают m входных величин каждая из которых может принимать конечное число фиксированных значений из входного алфавита ;

б) на выходах модели можно наблюдать выходных величин каждая из которых может принимать конечное число фиксированных значений из выходного алфавита У;

в) в каждый момент времени модель может находиться в одном из состояний ;

г) состояние модели в каждый момент времени определяется входной величиной в этот момент и состоянием z в предыдущий момент времени;

д) модель осуществляет преобразование ситуации на входе в ситуацию на выходе за­висимости от ее состояния в предыдущий момент времени.

Такая модель (см. рис.3.1) удобна для описания многих ки­бернетических систем.

Автоматы, у которых ситуация на выходах однозначно определяется ситуацией х на входах, мы будем относить к классу автоматов без памяти. Автоматы, у которых у зависит не только от значения х в данный момент, но и от состояния модели z, опре­деляемого значениями х в предыдущие моменты времени, относятся к классу автоматов с конечной памятью.

Рис.3.1 Дискретный автомат

Мы ограничимся рассмотрением лишь простейших из дискретных автоматов, входной и выходной алфавиты которых состоят всего из двух букв: 0 и 1. Это оправдывается тем что, как оказывается в теории автоматов, автоматы с такими "бедными" алфавитами способ­ны решать такие же задачи, как и автоматы с любыми другими алфа­витами.

Теория дискретных автоматов приобрела большое значение для решения некоторых фундаментальных проблем информатики, которые связаны с принципиальными возможностями переработки информации в ИС.

Логический автомат

Преобразования входных величин в выходные, осуществляемые дискретными автоматами без памяти, работающими в двухбуквенном алфавите, эквивалентны преобразованиям, совершаемым в формальной логике. Поэтому мы будем называть их логическими автоматами, а функции, описывающие преобразования, выполняемые логическими ав­томатами, - логическими, функциями. Математическим аппаратом, ис­пользуемым для решения задач анализа и синтеза логических авто­матов, является алгебра логики. Исторически первый вариант ал­гебры логики был разработан английским ученым Джорджем Булем в 1843 г., вследствие чего она часто называется булевой алгеброй.

Каждый выход ид логического автомата может принимать значе­ние 0 или 1 в зависимости от значений входных переменных х. Оп­ределим число всех возможных логических функций преобразования х в , если входных величин равно т, каждая из них может прини­мать значение 0 или 1. Для этого расположим все входные величины в ряд и будем рассматривать их как разряды двоич­ного числа. Ясно, что число r различных сочетаний значений вход­ных величин равно числу различных двоичных чисел, содержащих г разрядов, откуда следует, что . Но каждой из г ситуаций на входе может соответствовать одно из двух значений выхода 0 или 1. Поэтому общее число N всех различных логических функций для ло­гического автомата с m двоичными входами равно

(3. 1)

Логические функции образуются из некоторых элементарных ло­гических функций. Мы будем пользоваться тремя элементарными ло­гическими функциями:

1. х - отрицание x (читается "не x"). Функция отрицания оз­начает, что , если =1; и =1, если .

2. - логическое умножение или конъюнкция (читается " и "). Функция логического умножения означает, что его резуль­тат равен единице только тогда, когда и равен нулю во всех остальных случаях.

3. - логическое сложение или дизъюнкция (читается " или "). Функция логического сложения означает, что его ре­зультат равен нулю только тогда, когда и , и равен еди­нице во всех остальных случаях.

Логические функции могут задаваться таблицами, в которых указывается значение функции у (индекс i будем опускать) для всех сочетаний аргументов х. В табл.3.1 приведены значения двух элементарных логических функций от двух аргументов: и . Эту таблицу нужно читать по строкам: " если =..., a =..., то и =..., а или =...". Логические функции широко используются в теории нейронных сетей и входят в математический аппарат, применяемый при исследованиях процессов переработки информации мозгом.

Таблица 3.1

Из элементарных логических функций можно составлять логи­ческие функции, описывающие свойства различных логических авто­матов.

Автомат с конечной памятью

При изучении автоматов с конечной памятью обычно интересу­ются только установившимися состояниями, которые они принимают через достаточно большое время после изменения входных воздейс­твий. Процессы перехода системы из одного установившегося состо­яния в другое здесь полагаются протекающими достаточно быстро по сравнению с интервалами времени между изменениями входных воз­действий. Поэтому поведение автомата с конечной памятью удобно рассматривать в дискретные моменты времени ,..., отделен­ные друг от друга интервалами t. При этом мы будем полагать, что и выходные воздействия могут изменяться только в моменты ..., которые называются тактами.

В соответствии с определением выход автомата с конечной па­мятью в j-й такт зависит от состояния автомата в (j-1)-й такт и состояния входов в j -й такт. Поэтому переходы такого автомата из одного состояния в другое, в общем виде, описываются выражениями

(3.2)

где - выход автомата в j-й такт зависит от состояния ав­томата в (j-l)-й такт, - состояние автомата в (j-1)-й такт.

(3.3)

- вход автомата в j-й такт, F и G - некоторые логические функции состояния выхода и входа.

Для того чтобы автомат осуществлял преобразование 3.2, не­обходимо, чтобы он, кроме элементов, реализующих логические функции, содержал также элемент задержки, выход которого опреде­ляется значением его состояния в предыдущий такт, т. е. Элемент, выход которого у связан с входом х выражением

(3.4)

или, в частности

(3.5)

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

Одним из распространенных дискретных элементов, обладающих памятью, является триггер, представляющий собой устройство с двумя устойчивыми состояниями. Это устройство может переходить из одного состояния в другое под воздействием сигнала управле­ния.

Триггер может строиться из различных конструктивных элемен­тов и, в частности, из электронных элементов, как это показано на схеме рис.3.2. В этой схеме благодаря положительным обратным связям (связи между анодным током одного триода и напряжением на сетке другого) схема может находиться в одном из следующих двух режимов:

1) состояние : триод Л1 открыт (потенциал на сетке поло­жителен); анодный ток I_а1 велик: напряжение (U_a1 мало; триод Л2заперт (потенциал сетки отрицателен); анодный ток I_а2 - мал; напряжение на выходе Uвых велико Uвых=U₁;

2) состояние : триод Л1 закрыт (потенциал на сетке отри­цателен; анодный ток I_а1 мал: напряжение U_a1 велико: триод Л2открыт (потенциал сетки положителен); анодный ток I_a2 велик; напряжение на выходе мало, Uвых=U₀. Эту схему можно переводить из состояния в состояние , воздействуя на ее вход. При пос­туплении импульса напряжения на вход схемы он, проходя через конденсатор С, преобразуется в два импульса: положительный и отрицательный. Параметры схемы подобраны так, что положительный импульс не оказывает влияния на ее работу, а отрицательный запи­рает открытый триод, что в свою очередь приводит к отпиранию ра­нее запертого триода, т.е. к переходу схемы в другое устойчивое состояние. Таким образом, каждый управляющий импульс изменяет состояние схемы и каждый четный импульс возвращает ее в исходное состояние.

Условимся считать нулем малое напряжение на выходе триггеpa, а единицей - большое. Очевидно, выход триггера в j-й момент времени (j-й такт) однозначно определяется его состоянием . Поэтому зависимость выхода триггера от входа в настоящий момент и от состояния в предыдущий момент можно выразить как зависи­мость от входа в настоящий, момент и от выхода в предыдущий мо­мент Таким образом, триггер осуществляет функцию задержки, т.е. запоминания состояния. Переходы триггера показаны в табл.3.2.

Таблица 3.2

Из таблицы вытекает следующее выражение для логической функции перехода триггера

(3.6)

Рассмотрим в качестве примера автомата с конечной памятью схему электронного счетчика, применяемого в цифровых вычисли­тельных устройствах (рис. 3.3). Задача этой схемы состоит в подсчете количества импульсов, поступивших на ее вход. т.е. в преобразовании количества импульсов в двоичный код числа, выра­жающего это количество.

Для этой цели образуем цепь из триггеров, показанную на ри­сунке. Здесь выход каждого предыдущего триггера соединен с вхо­дом последующего. Пусть сначала все триггеры находятся в нулевом состоянии, т.е. напряжение на их выходах равно U₀. При поступле­нии первого импульса на вход триггера Т₁, на его выходе появится напряжение U₁, и на входе триггера T₂, положительный импульс нап­ряжения, на который он не реагирует. Второй импульс заставит T₁, вернуться в нулевое состояние, в результате чего напряжение на его выходе изменит свое значение с U₁ на U₀, что вызовет отрица­тельный импульс на входе T₂ и его переход в единичное состояние. Таким образом, T₁ будет изменять свое состояние после каждого входного импульса, T₂, после каждого второго импульса, T₃ - после каждого четвертого и т.д., - после каждого импульса на входе схемы. Если теперь мы будем состояние каждого триггера рассматривать, как значение соответствующего разряда двоичного числа, то состояние всей цепи из г триггеров будет представлять собой число (в двоичной системе счисления) импульсов, поступивших на вход схемы.

Pис.3.3 Счетчик импульсов на триггерах

Емкость этой схемы - максимальное число R импульсов, кото­рые могут быть ею сосчитаны, определяется числом г триггеров и равно максимальному двоичному числу, состоящему из г разрядов, а именно R= .

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: