|
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИПонятие дискретного автомата В технике термином "автомат" пользуются для обозначения системы механизмов и устройств, в которой процессы получения преобразования, передачи и использования энергии, материалов и информации, необходимые для выполнения ее функций, осуществляются без непосредственного участия человека. К системам такого типа относятся: станки-автоматы, фасовочные автоматы, автоматы для съемки и изготовления фотографий, торговые автоматы и многое др. В кибернетику, однако, вошел и прочно в ней укрепился термин "дискретный автомат" или кратко просто "автомат" для обозначения гораздо более абстрактного понятия, а именно - модели, обладающей следующими особенностями: а) на входы модели в каждый из дискретных моментов времени поступают 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 велик: напряжение (Ua1 мало; триод Л2заперт (потенциал сетки отрицателен); анодный ток Iа2 - мал; напряжение на выходе Uвых велико Uвых=U1; 2) состояние : триод Л1 закрыт (потенциал на сетке отрицателен; анодный ток Iа1 мал: напряжение Ua1 велико: триод Л2открыт (потенциал сетки положителен); анодный ток Ia2 велик; напряжение на выходе мало, Uвых=U0. Эту схему можно переводить из состояния в состояние , воздействуя на ее вход. При поступлении импульса напряжения на вход схемы он, проходя через конденсатор С, преобразуется в два импульса: положительный и отрицательный. Параметры схемы подобраны так, что положительный импульс не оказывает влияния на ее работу, а отрицательный запирает открытый триод, что в свою очередь приводит к отпиранию ранее запертого триода, т.е. к переходу схемы в другое устойчивое состояние. Таким образом, каждый управляющий импульс изменяет состояние схемы и каждый четный импульс возвращает ее в исходное состояние. Условимся считать нулем малое напряжение на выходе триггеpa, а единицей - большое. Очевидно, выход триггера в j-й момент времени (j-й такт) однозначно определяется его состоянием . Поэтому зависимость выхода триггера от входа в настоящий момент и от состояния в предыдущий момент можно выразить как зависимость от входа в настоящий, момент и от выхода в предыдущий момент Таким образом, триггер осуществляет функцию задержки, т.е. запоминания состояния. Переходы триггера показаны в табл.3.2. Таблица 3.2
Из таблицы вытекает следующее выражение для логической функции перехода триггера
(3.6) Рассмотрим в качестве примера автомата с конечной памятью схему электронного счетчика, применяемого в цифровых вычислительных устройствах (рис. 3.3). Задача этой схемы состоит в подсчете количества импульсов, поступивших на ее вход. т.е. в преобразовании количества импульсов в двоичный код числа, выражающего это количество. Для этой цели образуем цепь из триггеров, показанную на рисунке. Здесь выход каждого предыдущего триггера соединен с входом последующего. Пусть сначала все триггеры находятся в нулевом состоянии, т.е. напряжение на их выходах равно U0. При поступлении первого импульса на вход триггера Т1, на его выходе появится напряжение U1, и на входе триггера T2, положительный импульс напряжения, на который он не реагирует. Второй импульс заставит T1, вернуться в нулевое состояние, в результате чего напряжение на его выходе изменит свое значение с U1 на U0, что вызовет отрицательный импульс на входе T2 и его переход в единичное состояние. Таким образом, T1 будет изменять свое состояние после каждого входного импульса, T2, после каждого второго импульса, T3 - после каждого четвертого и т.д., - после каждого импульса на входе схемы. Если теперь мы будем состояние каждого триггера рассматривать, как значение соответствующего разряда двоичного числа, то состояние всей цепи из г триггеров будет представлять собой число (в двоичной системе счисления) импульсов, поступивших на вход схемы. Pис.3.3 Счетчик импульсов на триггерах Емкость этой схемы - максимальное число R импульсов, которые могут быть ею сосчитаны, определяется числом г триггеров и равно максимальному двоичному числу, состоящему из г разрядов, а именно R= . Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем... ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры... Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|